Intersection Types for the Computational λ-Calculus

the Computational λ-Calculus

Ugo de’Liguoro, Riccardo Treglia

University of Turin, Italy

INRIA - Sophia Antipolis 16-12-2019

Why effects in functional languages

Semantic theories are an established field providing foundations to software analysis and verification

We have nice theories of the semantics for functional programming languages, but procedural languages commonly used for both sequential and concurrent programming have non-functional features, collectively called effects Since Algol’60 project various λ-calculi have been used as metalanguages providing semantics to programming languages in general, and a successful approach among others is based on the notion of computational monad [Moggi89, 91]

Monads have been studied and implemented mainly for typed languages; here we address the issue of modelling effects in the untyped case.

Why effects in functional languages

Semantic theories are an established field providing foundations to software analysis and verification

but procedural languages commonly used for both sequential and concurrent programming have non-functional features, collectively called effects Since Algol’60 project various λ-calculi have been used as metalanguages providing semantics to programming languages in general, and a successful approach among others is based on the notion of computational monad [Moggi89, 91]

Monads have been studied and implemented mainly for typed languages; here we address the issue of modelling effects in the untyped case.

Why effects in functional languages

Semantic theories are an established field providing foundations to software analysis and verification

We have nice theories of the semantics for functional programming languages, but procedural languages commonly used for both sequential and concurrent programming have non-functional features, collectively called effects

Since Algol’60 project various λ-calculi have been used as metalanguages providing semantics to programming languages in general, and a successful approach among others is based on the notion of computational monad [Moggi89, 91]

Monads have been studied and implemented mainly for typed languages; here we address the issue of modelling effects in the untyped case.

Why effects in functional languages

Semantic theories are an established field providing foundations to software analysis and verification

We have nice theories of the semantics for functional programming languages, but procedural languages commonly used for both sequential and concurrent programming have non-functional features, collectively called effects Since Algol’60 project various λ-calculi have been used as metalanguages providing semantics to programming languages in general, and a successful approach among others is based on the notion of computational monad [Moggi89, 91]

we address the issue of modelling effects in the untyped case.

Why effects in functional languages

Semantic theories are an established field providing foundations to software analysis and verification

We have nice theories of the semantics for functional programming languages, but procedural languages commonly used for both sequential and concurrent programming have non-functional features, collectively called effects Since Algol’60 project various λ-calculi have been used as metalanguages providing semantics to programming languages in general, and a successful approach among others is based on the notion of computational monad [Moggi89, 91]

Monads have been studied and implemented mainly for typed languages; here we address the issue of modelling effects in the untyped case.

Computational Monads (after Wadler)

A monad is a triple pT , unit, ‹q Types

D is the type ofvalues;

TD is the type ofcomputations(with effects) overD.

Operators

unit_D :DÑTD (Haskell: return);

‹D,E :TD Ñ pDÑTEq ÑTE (Haskell: ąą“).

Axioms

punit d q ‹ f “ f d a ‹ unit “ a

pa ‹ f q ‹ g “ a ‹ λλ d.pf d ‹ g q

Computational Monads (after Wadler)

D

TD unitD

?

f^˚“ λλ x. x ‹ f- TE f

-

pf^˚˝ unit q d “ unit d ‹ f “ f d d P D

Computational Monads (after Wadler)

C D

TC unitC

?

g^˚ - TD

unitD

?

f^˚ -

g

-

TE f

-

TC id_TC

? pf^˚˝ g q^˚“ λλ y . y ‹ pλλ x. g x ‹ f q

- TE id_TE 6

pf^˚˝ g q^˚m “ m ‹ pλλ x. g x ‹ f q “ pm ‹ g q ‹ f m P TC

Moggi’s type-free λ

Moggi considered a type-free version of his λc, obtained by type erasure:

Terms : e, e¹ ::“ v | n Values : v ::“ x | λx.e

NonValues : n ::“ let x “ e in e¹ | e e¹

Problems:

a quite rich syntax with complex equational theory

a reduction e e¹ is defined with seven rules (five about let) no clear model interpreting non values like: x x and x x x

Untyped computational λ-calculus: λ

We consider Moggi’s call-by-value reflexive object:

D“DÑTD

hence there are two types,D andTD, and two kinds of terms:

Val : V , W ::“ x | λx.M (values)

Com: L, M, N ::“ unit V | M ‹ V (computations) having types:

x :D$ x :D x :D$ M :TD

$ λx .M :DÑTD “D

$ V :D

$ unit V :TD

$ M :TD $ V :D“D ÑTD

$ M ‹ V :TD

Untyped computational λ-calculus: λ

We consider Moggi’s call-by-value reflexive object:

D“DÑTD

hence there are two types,D andTD, and two kinds of terms:

Val : V , W ::“ x | λx.M (values)

Com: L, M, N ::“ unit V | M ‹ V (computations) and a natural interpretation:

rr¨ss^D : Val Ñ EnvDÑD rr¨ss^TD: Com Ñ EnvD ÑTD where ρ P EnvD“ Var ÑD and

rrx ss^D_ρ “ ρpxq rrunit V ss^TD_ρ “ unitDrrV ss^D_ρ

rrλx .Mss^D_ρ “ λλ d PD. rrMss^TD_ρrxÞÑds rrM ‹ V ss^TD_ρ “ rrMss^TD_ρ ‹D,D rrV ss^D_ρ

Reduction

Orienting monad axioms we get ÝÑ Ď Com ˆ Com as the compatible closure of:

pβcq unit V ‹ pλx.Mq ÝÑ MrV {xs (id) M ‹ λx.unit x ÝÑ M

(ass) pL ‹ λx .Mq ‹ λy .N ÝÑ L ‹ λx.pM ‹ λy .Nq for x R FV pNq where MrV {xs denotes the capture avoiding substitution of V for all free occurrences of x in M.

To have extensionality we add:

pηcq unit λx .punit x ‹ V q ÝÑ unit V if x R FV pV q

Confluence

Several critical pairs:

punit V ‹ λx Mq ‹ λy . N (ass)

- unit V ‹ λx pM ‹ λy . Nq

MrV {xs ‹ λy . N pβcq

?

”

pM ‹ λy . NqrV {x s pβcq

?

where x R FVpNq

Confluence

Several critical pairs:

pM ‹ λy Nq ‹ λx . unit x (ass)

- M ‹ λy . pN ‹ λx. unit xq

M ‹ λy . N

(id) (id)

-

Confluence

Several critical pairs:

pM ‹ λx . unit x q ‹ λy . N (ass)

- M ‹ λx. punit x ‹ λy Nq

M ‹ λy . N (id)

?

α M ‹ λx. Nrx{y s

pβcq

?

where x R FVpNq

Confluence

Theorem

If ÝÑ is either ÝÑβc or ÝÑβcηc then

M ÝÑ N^˚ and M ÝÑ L^˚ implies

NÝÑ M^{˚ 1} and LÝÑ M^{˚ 1} for some M¹P Com.

Proof: by the parallel reduction technique.

Also the reduction relation is confluent; this has been shown by Hamana in 2018, by an implicit proof.

λ

versus type free λ

let is definable:

let x “ M in N ” M ‹ λx.N No primitive functional application but

pλx .MqV ” punit V q ‹ pλx .Mq VM ” M ‹ V

MN ” M ‹ λz.pN ‹ zq for some fresh z By this we retrieve ordinary call-by-value reduction rule:

pβvq pλx .MqV ” punit V q ‹ pλx .Mq ÝÑβ_c MrV {xs

λ

versus type free λ

There exist the mappings

t¨u^V: Values Ñ Val t¨u^C: NonValues Ñ Com where e.g.

tλx .v u^V“ λx .unit tv u^V and tλx.nu^V “ λx .tnu^C tnv u^C“ tnu^C‹ pλz .unit tv u^V‹ z q and

tnn¹u^C“ tnu^C‹ pλz .tn¹u^C‹ z q for fresh z tlet x “ n in v u^C“ tnu^C‹ λx .unit tv u^V and tlet x “ v in n¹u^C“ unit tv u^V‹ λx .tn¹u^C Then putting

tnu “ tnu^C tv u “ unit tv u^V we have

e e¹ñ teuÝÑ^˚ βcηc te¹u

Types and assignment system

Definition (Intersection types for values and computations)

ValType: δ ::“ α | δ Ñ τ | δ ^ δ | ωV refineD (value types) ComType: τ ::“ T δ | τ ^ τ | ωC refineTD (computation types)

Types and assignment system

Definition (Intersection types for values and computations)

ValType: δ ::“ α | δ Ñ τ | δ ^ δ | ωV refineD (value types) ComType: τ ::“ T δ | τ ^ τ | ωC refineTD (computation types)

x : D $ x : D x : D $ M : TD

$ λx .M : D Ñ TD “ D

Types and assignment system

Definition (Intersection types for values and computations)

ValType: δ ::“ α | δ Ñ τ | δ ^ δ | ωV refineD (value types) ComType: τ ::“ T δ | τ ^ τ | ωC refineTD (computation types)

x : δ P Γ (Ax) Γ $ x : δ

Γ, x : δ $ M : τ pÑ Iq Γ $ λx.M : δ Ñ τ

Types and assignment system

Definition (Intersection types for values and computations)

ValType: δ ::“ α | δ Ñ τ | δ ^ δ | ωV refineD (value types) ComType: τ ::“ T δ | τ ^ τ | ωC refineTD (computation types)

x : δ P Γ (Ax) Γ $ x : δ

Γ, x : δ $ M : τ pÑ Iq Γ $ λx.M : δ Ñ τ

$ V : D

$ unit V : TD

$ M : TD $ V : D “ D Ñ TD

$ M ‹ V : TD

Types and assignment system

Definition (Intersection types for values and computations)

ValType: δ ::“ α | δ Ñ τ | δ ^ δ | ωV refineD (value types) ComType: τ ::“ T δ | τ ^ τ | ωC refineTD (computation types)

x : δ P Γ (Ax) Γ $ x : δ

Γ, x : δ $ M : τ pÑ Iq Γ $ λx.M : δ Ñ τ

Γ $ V : δ

punit Iq Γ $ unit V : T δ

Γ $ M : T δ Γ $ V : δ Ñ τ pÑ Eq Γ $ M ‹ V : τ

where Γ, x : δ “ Γ Y tx : δu with x : δ R Γ.

Subtyping

Definition

A subtyping relation is defined as the smallest relation on types such that:

δ ďVωV ωVďVωVÑ ωC

pδ Ñ τ q ^ pδ Ñ τ¹q ďVδ Ñ pτ ^ τ¹q

δ¹ďVδ τ ďCτ¹ δ Ñ τ ďVδ¹Ñ τ¹ τ ďCωC T δ ^ T δ¹ďCT pδ ^ δ¹q

δ ďVδ¹ T δ ďCT δ¹ So we add pertinent rules:

Γ $ P : ω

pωq Γ $ P : σ Γ $ P : σ¹ Γ $ P : σ ^ σ¹

p^I q Γ $ P : σ σ ď σ¹ Γ $ P : σ¹

pSubq

where either P P Val , ω ” ωV, σ, σ¹P ValType and ď “ ďV or P P Com, ω ” ωC, σ, σ¹P ComType and ď “ ďC.

Subtyping

Definition

A subtyping relation is defined as the smallest relation on types such that:

δ ďVωV ωVďVωVÑ ωC

pδ Ñ τ q ^ pδ Ñ τ¹q ďVδ Ñ pτ ^ τ¹q

δ¹ďVδ τ ďCτ¹ δ Ñ τ ďVδ¹Ñ τ¹ τ ďCωC T δ ^ T δ¹ďCT pδ ^ δ¹q

δ ďVδ¹ T δ ďCT δ¹ So we add pertinent rules:

Γ $ P : ω

pωq Γ $ P : σ Γ $ P : σ¹ Γ $ P : σ ^ σ¹

p^I q Γ $ P : σ σ ď σ¹ Γ $ P : σ¹

pSubq

where either P P Val , ω ” ωV, σ, σ¹P ValType and ď “ ďV or P P Com, ω ” ωC, σ, σ¹P ComType and ď “ ďC.

Subject reduction and expansion

Theorem (Subject reduction)

If Γ $ M : τ and M ÝÑ N then Γ $ N : τ .

Theorem (Subject expansion)

If Γ $ M : τ and N ÝÑ M then Γ $ N : τ .

Type interpretation

Given ξ P TypeEnv_D “ TypeVar Ñ 2^D define

rr¨ss^D: ValType ˆ TypeEnvDÑ 2^D rr¨ss^TD : ComType ˆ TypeEnvDÑ 2^TD by

rrαss^Dξ “ ξpαq rrδ Ñ τ ss^Dξ “ td P D | @a P rrT δss^TDξ . a ‹ d P rrτ ss^TDξ u rrT δss^TD_ξ “ tunit d | d P rrδssξu

rrωVss^Dξ “ D rrδ ^ δ¹ss^Dξ “ rrδss^Dξ X rrδ¹ss^Dξ

rrωCss^TD_ξ “ TD rrτ ^ τ¹ss^TD_ξ “ rrτ ss^TD_ξ X rrτ¹ss^TD_ξ

Lemma

δ ďVδ¹ ñ @ξ P TypeEnv_D. rrδss^Dξ Ď rrδ¹ss^Dξ

τ ďCτ¹ ñ @ξ P TypeEnv_D. rrτ ss^TDξ Ď rrτ¹ss^TD_ξ

Soundness and completeness

A model of λ^u_c is a structure M “ pD, T , unit , ‹q such that pT , unit , ‹q is a monad and D » D Ñ TD ρ, ξ |ù^MΓ if ρpxq P rrΓpxqss^D_ξ for all x P dom pΓq

Γ |ù^MV : δ (Γ |ù^MM : τ ) if ρ, ξ |ù^MΓ implies rrV ss^D_ρ P rrδss^D_ξ (rrMss^TDρ P rrτ ss^TD_ξ )

Γ |ù V : δ (Γ |ù M : τ ) if Γ |ù^MV : δ (Γ |ù^MM : τ ) for all M.

Theorem

Γ $ V : δ ô Γ |ù V : δ Γ $ M : τ ô Γ |ù M : τ

Convergence

Let ó Ď Com⁰ˆ Val⁰ be the smallest relation satisfying:

unit V ó V

M ó V NrV {xs ó W M ‹ λx.N ó W Define

M ó ô DV P Val⁰. M ó V Lemma

M ó ô DV P Val⁰. M ÝÑ unit V^˚

Characterization by non trivial typing

Let I : TypeVar ÑPVal⁰be a map; then define

|δ|_I Ď Val⁰ |τ |_IĎ Com⁰ by induction as follows:

|α|I“ Ipαq

|δ Ñ τ |I“ tV P Val⁰| @M P |T δ|I. M ‹ V P |τ |Iu

|T δ|I“ tM P Com⁰| DV P |δ|I. M ó V u

|ωV|I“ Val⁰ and |ωC|I“ Com⁰

|δ ^ δ¹|_I“ |δ|_IX |δ¹|_I and |τ ^ τ¹|_I “ |τ |_IX |τ¹|_I. Lemma

Let Γ $ M : τ where Γ “ tx1: δ1, . . . , xk : δku and M P Com. For any V1, . . . , Vk P Val⁰ and I, if ViP |δi|I for all i “ 1, . . . , k then MrV1{x1s ¨ ¨ ¨ rVk{xks P |τ |I.

Characterization by non trivial typing

Theorem

For all M P Com⁰we have:

M ó ô D τ ‰Cω_C. $ M : τ.

Proof. If M ó then MÝÑ unit V for some V P Val^{˚ 0}; since $ V : ωV we have

$ unit V : T pωVq ‰Cω_C, so $ M : τ by subject expansion.

If $ M : τ and M P Com⁰ then M P |τ |I and for all I; τ ‰CωCimplies τ ďCT pωVq and hence |τ |IĎ |T pωVq|I “ tN P Com⁰| N óu.

State monad

A statefull computation is a function:

initial state ÞÑ pcomputed value, initial stateq

State monad: pS, unitS, ‹Sq where

SD “ S Ñ D ˆ S, where say S Ď L Ñ D and L is a set of locations unitSd “ λλ s. pd, sq

a ‹Sf “ λλ s. let pd, s¹q “ a s in f d s¹ and suppose:

D » D Ñ pS Ñ D ˆ Sq Then

Com : M, N ::“ . . . |!`|` :“ M where

rr!`ss<sup>SD</sup>ρ “ λλ s. psr`s, sq

rr` :“ Mss<sup>SD</sup>ρ “ rrMss<sup>SD</sup>ρ ‹Sλλ d s. pd, sr` ÞÑ dsq

State monad

StateType : σ ::“ x` : δy | σ ^ σ¹| ωS

ValType : δ ::“ α | δ Ñ τ | δ ^ δ¹| ωV

ComType : τ ::“ σ Ñ δ ˆ σ¹| τ ^ τ | ωC

Γ $ V : δ

Γ $ unit V : σ Ñ pδ ˆ σq

Γ $ M : σ Ñ pδ ˆ σ¹q Γ $ V : δ Ñ σ¹Ñ pδ¹ˆ σ²q Γ $ M ‹ V : σ Ñ pδ¹ˆ σ²q

and observe that (omitting ξ):

rrδ Ñ σ¹Ñ pδ¹ˆ σ²qss^D “ rrpδ ˆ σ¹q Ñ pδ¹ˆ σ²qss^D

State monad

Postulating

δ ďVδ¹ñ x` : δy ďSx` : δ¹y x` : δy ^ x` : δ¹y ďS x` : δ ^ δ¹y we can write the typing rules:

σ ďSx` : δy Γ $ !` : σ Ñ δ ˆ σ

Γ $ M : σ Ñ δ ˆ σ¹ σ²“ σ¹rx` : δy{x` : ys Γ $ ` :“ M : σ Ñ δ ˆ σ²

where σ¹rx` : δy{x` : ys is the replacement of x` : y by x` : δy in σ¹ Γ $ M : σ Ñ δ ˆ σ¹ Γ $ N : σ¹Ñ δ¹ˆ σ²

Γ $ M; N ” M ‹ λ .N : σ Ñ δ¹ˆ σ²

which is a derived rule, making it apparent that the value of M, that has type δ, is discarded, while the produced state of type σ¹is passed to N.

State monad

Suppose δ ‰Vδ¹:

$ V : δ

$ unit V : x` : δ<sup>1</sup>y Ñ δ ˆ x` : δ¹y

$ ` :“ unit V : x` : δ¹y Ñ δ ˆ x` : δy Now

rrV ss^DP rrδss^D and rr` :“ unit V ss<sup>SD</sup>P rrx` : δ¹y Ñ δ ˆ x` : δyss^SD but

rr` :“ unit V ss^SDR tunitSd | d P rrδss^Du

Monadic type interpretation

Definition

Type interpretations rr¨ss^D and rr¨ss^TD are monadic if for any d P D and a P TD:

(i) d P rrδss^D_ξ ñ unit d P rrT δss^TD_ξ

(ii) d P rrδ¹Ñ T δss^D_ξ & a P rrT δ¹ss^TD_ξ ñ a ‹ d P rrT δss^TD_ξ

This definition is not inductive! in particular rrT δss^TD_ξ depends on itself and also on rrT δ¹ss^TD_ξ for any δ¹.

Monadic type interpretation

Suppose that D₈“ limÐDnwhere D0is arbitrary and Dn`1“ rDnÑ TDns Then we can inductively define

rrδss^D_ξⁿĎ Dn and rrτ ss^TD_ξ ⁿĎ TDn

so that we have Theorem

The mappings rrδss^D_ξ⁸“ limÐrrδss^D_ξⁿ and rrτ ss^TD_ξ ⁸“ limÐrrτ ss^TD_ξ ⁿ are monadic type interpretations. In particular for any ξ P EnvD₈:

rrδ Ñ τ ss^D_ξ⁸“ td P D8| @d¹P rrδss^D_ξ⁸ d pd¹q P rrτ ss^TD_ξ ⁸u

rrT δss^TD_ξ ⁸“ tunit d P TD8| d P rrδss^D_ξ⁸u Y

ta ‹ d P TD8| Dδ¹. d P rrδ¹Ñ T δss^D_ξ⁸ & a P rrT δ¹ss^TD_ξ ⁸u

Conclusion and open issues

Results

Moving from equation D “ D Ñ TD for a generic computational monad T we have defined a type assignment system that is sound and complete for a pure untyped computational λ-calculus.

The type assignment system enjoys basic properties of intersection type systems: invariance under conversion, soundness and completeness w.r.t.

standard domain semantics, computational adequacy.

Ongoing work

Is there a reasonable notion of type refinement w.r.t. generic T -types?

Is there a uniform way to instantiate the generic type system to concrete monads, preserving basic properties?

Can we extend this approach to algebras and coalgebras of a monad?

Reference

Full paper available on arXiv.org:

Ugo de’Liguoro, Riccardo Treglia

Intersection Types for the Computational lambda-Calculus, July 2019.

http://arxiv.org/abs/1907.05706