## From semantics to types:

## the case of the imperative λ-calculus

Ugo de’Liguoro, Riccardo Treglia

University of Turin, Italy

MFPS XXXVII - Salzburg, 30 August - 3 September 2021

## Overview

Goal: to find a type assignment system to reason about functional programs with side-effects

Approach: Moggi’s idea of modeling effectful computations using monads
Background: computational core λ_{c} + Intersection Types

Contents: definition of λimp out of a domain equation solution of the equation as a filter model;

derivation of a type assignment system out of the interpretation of terms as filters of types

In this paper:

Denotational Semantics of λ_{imp}
and its type system

In a companion paper: Operational Semantics of λimp

(soon in PPDP’21)

## Overview

Goal: to find a type assignment system to reason about functional programs with side-effects

Approach: Moggi’s idea of modeling effectful computations using monads
Background: computational core λ_{c} + Intersection Types

Contents: definition of λimp out of a domain equation solution of the equation as a filter model;

derivation of a type assignment system out of the interpretation of terms as filters of types

In this paper:

Denotational Semantics of λ_{imp}
and its type system

In a companion paper: Operational Semantics of λimp

(soon in PPDP’21)

## Overview

Goal: to find a type assignment system to reason about functional programs with side-effects

Approach: Moggi’s idea of modeling effectful computations using monads

Background: computational core λ_{c} + Intersection Types
Contents: definition of λimp out of a domain equation

solution of the equation as a filter model;

derivation of a type assignment system out of the interpretation of terms as filters of types

In this paper:

Denotational Semantics of λ_{imp}
and its type system

In a companion paper: Operational Semantics of λimp

(soon in PPDP’21)

## Overview

Goal: to find a type assignment system to reason about functional programs with side-effects

Approach: Moggi’s idea of modeling effectful computations using monads
Background: computational core λ_{c} + Intersection Types

Contents: definition of λimp out of a domain equation solution of the equation as a filter model;

derivation of a type assignment system out of the interpretation of terms as filters of types

In this paper:

Denotational Semantics of λ_{imp}
and its type system

In a companion paper: Operational Semantics of λimp

(soon in PPDP’21)

## Overview

Goal: to find a type assignment system to reason about functional programs with side-effects

_{c} + Intersection Types

Contents: definition of λimp out of a domain equation solution of the equation as a filter model;

derivation of a type assignment system out of the interpretation of terms as filters of types

In this paper:

Denotational Semantics of λ_{imp}
and its type system

In a companion paper: Operational Semantics of λimp

(soon in PPDP’21)

## Overview

Goal: to find a type assignment system to reason about functional programs with side-effects

_{c} + Intersection Types

Contents: definition of λimp out of a domain equation solution of the equation as a filter model;

derivation of a type assignment system out of the interpretation of terms as filters of types

In this paper:

Denotational Semantics of λ_{imp}
and its type system

In a companion paper:

Operational Semantics of λimp

(soon in PPDP’21)

## Modeling effects by monads

To model computational effects, Moggi (1991) proposed monads (here in Wadler’s type theoretic formulation)

pT, unit , ‹q where

TA “ the type of computations over values of type A unit V “ the trivial computation returning the value V

M ‹ F “ the application to the computation M of F^{:}:TA ÝÑTB
that is the (unique) extension of F : A ÝÑTB s.t.

F^{:}punit V q “ F V
V : A

unit V :TA

M :TA F : A ÝÑTB M ‹ F :TB

## The untyped computational core λ

_{c}

## (dLT 2020)

Given a monadT, consider the call-by-value reflexive object (Moggi 1988) D “ D ÝÑTD

relating the typesD andTD; hence we have two kinds of terms Val : V , W ::“ x | λx.M

Com : M, N ::“ rV s | M ‹ V writing rV s ” unit V , with typing rules

Γ, x :D$ x :D

Γ, x :D$ M :TD Γ $ λx.M :D ÝÑTD “ D Γ $ V :D

Γ $ rV s :TD

Γ $ M :TD Γ $ V :D “ D ÝÑTD Γ $ M ‹ V :TD

## The untyped computational core λ

_{c}

## (dLT 2020)

Given a monadT, consider the call-by-value reflexive object (Moggi 1988) D “ D ÝÑTD

relating the typesD andTD; hence we have two kinds of terms Val : V , W ::“ x | λx.M

Com : M, N ::“ rV s | M ‹ V writing rV s ” unit V , with interpretation maps

J¨K

D : Val ÝÑ Env ÝÑD J¨K

TD : Com ÝÑ Env ÝÑTD

Jx K

De “ epxq Jλx .M K

De “ Ψpλλ d PD.JM K

TDerx ÞÑ d sq J rV s K

TDe “ unit pJV K^{D}eq JM ‹ V K

TDe “ pJM K^{TD}eq ‹ ΦpJV K^{D}eq

where e P Env “ Var ÝÑD, Φ :DÝÑ rD^{„} ÝÑTDs and Ψ “ Φ^{´1}

## The partiality and state monad S over Dom

Set L “ t`0, `_{1}, . . .u locations and Y P Dom

S “ Y^{L}“ rL ÝÑ Y s domain of states
The partiality and state monad is the triple pS, unit , ‹q:

SX “SÝÑ pX ˆSq_{K}
equipped with two (families of) operators unit and ‹:

unit x ς “ px, ςq pc ‹ f q ς “

"

f pxqpς^{1}q if cpςq “ px, ς^{1}q ‰ K

K if cpςq “ K

for c PSX and ς PS

## A domain equation

### Theorem

There exists a domainDP Dom solving the equation
D “ D ÝÑS ÝÑ pD ˆSq_{K}

whereS “ L ÝÑD. IfS is the monad with states inS thenD solves D “ D ÝÑSD

## Algebraic operators ` a la Plotkin and Power

Algebraic operators are morphisms op_{X} : pTX q^{n}ÝÑTX s.t.

op_{X} ˝ pf^{:}ˆ ¨ ¨ ¨ ˆ f^{:}
loooooomoooooon

n

q “ f^{:}˝ op_{X} with f : X ÝÑTX

In general, if A is a domain of abstract arities and P of parameters then
op : P ˆ pTX q^{A}ÝÑTX – pTX q^{A}ÝÑ pTX q^{P}

oppp, kq ‹ f “ f^{:}poppp, k qq “ oppp, f^{:}˝ k q “ oppp, λλ x.pkpxq ‹ f qq

### Example

In case ofT “S, taking P “ 1 and A “Dwe define:

get_{`}: 1 ˆ pSDq^{D} ÝÑSD »DÝÑSD by get_{`}d ς “ d pς p`qq ς
Taking P “D and A “ 1, we define:

set_{`}:Dˆ pSDq^{1}ÝÑSD»DˆSDÝÑSD by set_{`}pd , c q ς “ c pςr` ÞÑ d sq

## Algebraic operators ` a la Plotkin and Power

Algebraic operators are morphisms op_{X} : pTX q^{n}ÝÑTX s.t.

op_{X} ˝ pf^{:}ˆ ¨ ¨ ¨ ˆ f^{:}
loooooomoooooon

n

q “ f^{:}˝ op_{X} with f : X ÝÑTX
In general, if A is a domain of abstract arities and P of parameters then

op : P ˆ pTX q^{A}ÝÑTX – pTX q^{A}ÝÑ pTX q^{P}

oppp, kq ‹ f “ f^{:}poppp, k qq “ oppp, f^{:}˝ k q “ oppp, λλ x.pkpxq ‹ f qq

### Example

In case ofT “S, taking P “ 1 and A “Dwe define:

get_{`}: 1 ˆ pSDq^{D} ÝÑSD »DÝÑSD by get_{`}d ς “ d pς p`qq ς
Taking P “D and A “ 1, we define:

set_{`}:Dˆ pSDq^{1}ÝÑSD»DˆSDÝÑSD by set_{`}pd , c q ς “ c pςr` ÞÑ d sq

## Algebraic operators ` a la Plotkin and Power

Algebraic operators are morphisms op_{X} : pTX q^{n}ÝÑTX s.t.

op_{X} ˝ pf^{:}ˆ ¨ ¨ ¨ ˆ f^{:}
loooooomoooooon

n

q “ f^{:}˝ op_{X} with f : X ÝÑTX
In general, if A is a domain of abstract arities and P of parameters then

op : P ˆ pTX q^{A}ÝÑTX – pTX q^{A}ÝÑ pTX q^{P}

oppp, kq ‹ f “ f^{:}poppp, k qq “ oppp, f^{:}˝ k q “ oppp, λλ x.pkpxq ‹ f qq

### Example

In case ofT “S, taking P “ 1 and A “Dwe define:

get_{`}: 1 ˆ pSDq^{D} ÝÑSD »DÝÑSD by get_{`}d ς “ d pς p`qq ς
Taking P “D and A “ 1, we define:

1

## The imperative calculus λ

_{imp}

Syntax

Val : V , W ::“ x | λx.M

Com : M, N ::“ rV s | M ‹ V |get_{`}pλx .Mq|set_{`}pV , Mq p` P Lq
Semantics

J¨K

D: Val ÝÑ Env ÝÑD J¨K^{S}

D: Com ÝÑ Env ÝÑSD

Jx K

De “ epxq Jλx .M K

De “ Ψpλλ d PD.JM K

SD

erx ÞÑ d sq J rV s K

SD

e “ unit pJV K

Deq JM ‹ V K

SD

e “ pJM K

SD

eq ‹ ΦpJV K

Deq

Jget`pλx .MqK^{SD}e “ get_{`}ΦpJλx .M K

Deq

Jset^{`}pV , MqK

SDe “ set`pJV K

De,JM K

SDeq

where Env “ Var ÝÑD, Φ :DÝÑ rD Ý^{„} ÑSDs and Ψ “ Φ^{´1}

## Types as (duals of) compact points

In ω-ALG, the full subcategory of Dom of algebraic lattices with countable basis, we have

D – IpKpDqq – F pK^{op}pDqq for any D P ω-ALG

An intersection type theory Th “ pL, ďq is a finitary presentation of K^{op}pDq s.t.
KpDq Q d Ð[ σ^{d}P LD and d Ď e ðñ σeďD σd

JM K

D “ Ů

td P KpDq | d ĎJM K

Du “ Ů KpJM K

Dq d ĎJM K

D ðñ Ó d Ď KpJM K

Dq ðñ JM K

F Ě Ò σd

ðñ JM K

F Q σd

ðñ $ M : σd

## Types as (duals of) compact points

In ω-ALG, the full subcategory of Dom of algebraic lattices with countable basis, we have

D – IpKpDqq – F pK^{op}pDqq for any D P ω-ALG

An intersection type theory Th “ pL, ďq is a finitary presentation of K^{op}pDq s.t.

KpDq Q d Ð[ σ^{d}P LD and d Ď e ðñ σeďD σd

JM K

D “ Ů

td P KpDq | d ĎJM K

Du “ Ů KpJM K

Dq d ĎJM K

D ðñ Ó d Ď KpJM K

Dq ðñ JM K

F Ě Ò σd

ðñ JM K

F Q σd

ðñ $ M : σd

## Types as (duals of) compact points

In ω-ALG, the full subcategory of Dom of algebraic lattices with countable basis, we have

D – IpKpDqq – F pK^{op}pDqq for any D P ω-ALG

An intersection type theory Th “ pL, ďq is a finitary presentation of K^{op}pDq s.t.

KpDq Q d Ð[ σ^{d}P LD and d Ď e ðñ σeďD σd

JM K

D “ Ů

td P KpDq | d ĎJM K

Du “ Ů KpJM K

Dq d ĎJM K

D ðñ Ó d Ď KpJM K

Dq ðñ JM K

F Ě Ò σd

ðñ JM K

F Q σd

ðñ $ M : σd

## The filter model F

_{D}

## – rF

D## Ý Ñ S F

_{D}

## s of λ

imp### Theorem

There are theories Th_{D} and Th_{S}_{D} such that F_{D} “ FDÝÑSD– rFD ÝÑSF_{D}s

Proof. By defining the theories Th_{D}, Th_{S}, Th_{C} withC“ pDˆSq_{K}, and Th_{S}_{D}
by mutual induction:

L_{D}: δ ::“ δ ÝÑ τ | δ ^ δ^{1}| ωD L_{S} : σ ::“ x` : δy | σ ^ σ^{1}| ωS

L_{C} : κ ::“ δ ˆ σ | κ ^ κ^{1} | ωC L_{S}_{D}: τ ::“ σ ÝÑ κ | τ ^ τ^{1} | ω_{S}D

plus axioms and rules e.g.

pσ ÝÑ κq ^ pσ ÝÑ κ^{1}q ď_{S}D σ ÝÑ κ ^ κ^{1}

σ^{1}ďS σ κ ďC κ^{1}
σ ÝÑ κ ď_{S}D σ^{1}ÝÑ κ^{1}

## The interpretations JV K

FD

## and JM K

F_{S}D

From the definition of ‹ in case ofSwe get JM ‹ V K

F_{SD}

e “ pJM K

F_{SD}

eq ‹^{F}pJV K

F_{D}

eq

Defining (after BCD’83)

X ¨ Y “ tψ | Dϕ P Y . ϕ ÝÑ ψ P X u
for X P F_{S}D, Y P FD and Z P FS we have

pX ‹^{F}Y q ¨ Z “

#

pY ¨ Uq ¨ V if X ¨ Z “ U ˆ V ‰ ÒC ωC

ÒC ωC otherwise then we conclude that

JM ‹ V K

FSDe “ Filtt σ ÝÑ δ^{2}ˆ σ^{2}P L_{S}D |
Dδ^{1}, σ^{1}.σ ÝÑ δ^{1}ˆ σ^{1}PJM K

FSDe &
δ^{1}ÝÑ σ^{1}ÝÑ δ^{2}ˆ σ^{2}PJV K

FDeu where Filt X is the least filter including X .

## The interpretations JV K

FD

## and JM K

F_{S}D

From the definition of ‹ in case ofSwe get JM ‹ V K

F_{SD}

e “ pJM K

F_{SD}

eq ‹^{F}pJV K

F_{D}

eq Defining (after BCD’83)

X ¨ Y “ tψ | Dϕ P Y . ϕ ÝÑ ψ P X u
for X P F_{S}D, Y P FD and Z P FS we have

pX ‹^{F}Y q ¨ Z “

#

pY ¨ Uq ¨ V if X ¨ Z “ U ˆ V ‰ ÒC ωC

ÒC ω_{C} otherwise
then we conclude that

JM ‹ V K

FSDe “ Filtt σ ÝÑ δ^{2}ˆ σ^{2}P L_{S}D |
Dδ^{1}, σ^{1}.σ ÝÑ δ^{1}ˆ σ^{1}PJM K

FSDe &

δ^{1}ÝÑ σ^{1} ÝÑ δ^{2}ˆ σ^{2}PJV K

FDeu where Filt X is the least filter including X .

## From interpretations to typing rules

To Γ “ tx1: δ_{1}, . . . , x_{n}: δ_{n}u we associate the environment eΓ: Var ÝÑ FD

e_{Γ}px q “

#

ÒD δ if x : δ P Γ
ÒD ω_{D} otherwise

Then from the semantics of Q ” oppP1, . . . , Pnq we have JQ K

FeΓ“ Filttψ | ϕ1PJP^{1}K

FeΓ_{1} & ¨ ¨ ¨ & ϕnPJP^{n}K

FeΓ_{n}u

## From interpretations to typing rules

Factoring out the Filtt¨ ¨ ¨ u operator by the rules

pωq Γ $ P : ω

Γ $ P : ϕ Γ $ P : ψ p^q Γ $ P : ϕ ^ ψ

Γ $ P : ϕ ϕ ď ψ pďq Γ $ P : ψ

it suffices to guarantee JQ K

FeΓĚ tψ | ϕ1PJP1K

FeΓ1 & ¨ ¨ ¨ & ϕnPJPnK

FeΓnu which is obtained by the rule

Γ_{1}$ P1: ϕ_{1} ¨ ¨ ¨ Γ_{n}$ Pn: ϕ_{n}
Γ $ Q : ψ

## Example

From

JM ‹ V K

FSDeΓ “ pJM K

FSDeΓq ‹^{F}pJV K

FDeΓq

“ Filttσ ÝÑ δ^{2}ˆ σ^{2}P L_{S}D |
Dδ^{1}, σ^{1}.σ ÝÑ δ^{1}ˆ σ^{1}PJM K

FSDeΓ &

δ^{1} ÝÑ σ^{1}ÝÑ δ^{2}ˆ σ^{2}PJV K

FDeΓu

we get the rule

Γ $ M :σ ÝÑ δ^{1}ˆ σ^{1} Γ $ V :δ^{1}ÝÑ σ^{1}ÝÑ δ^{2}ˆ σ^{2}
Γ $ M ‹ V :σ ÝÑ δ^{2}ˆ σ^{2} p‹q

## The type assignment system

Rewriting as rules the clauses in the definition ofJV K

F_{D} andJM K

F_{SD}, we obtain

pvarq Γ, x : δ $ x : δ

Γ, x : δ $ M : τ pλq Γ $ λx.M : δ ÝÑ τ Γ $ V : δ

punitq Γ $ rV s : σ ÝÑ δ ˆ σ

Γ $ M : σ ÝÑ δ^{1}ˆ σ^{1} Γ $ V : δ^{1}Ñ σÝ ^{1}ÝÑ δ^{2}ˆ σ^{2}
p‹q
Γ $ M ‹ V : σ ÝÑ δ^{2}ˆ σ^{2}

Γ, x : δ $ M : σ ÝÑ κ

pgetq
Γ $ get_{`}pλx .Mq : px` : δy ^ σq ÝÑ κ

Γ $ V : δ Γ $ M : px` : δy ^ σq ÝÑ κ ` R dompσq psetq Γ $ set`pV , Mq : σ ÝÑ κ

pωq Γ $ P : ω

Γ $ P : ϕ Γ $ P : ψ p^q Γ $ P : ϕ ^ ψ

Γ $ P : ϕ ϕ ď ψ pďq Γ $ P : ψ

## Results

For A “ D, S, pD ˆ SqK, and SD, and ϕ P L^{A} define:
JϕK

F“ tX P FA | ϕ P X u

### Theorem (Type Semantics)

Let e |ù^{F} Γ if and only if epxq PJδK

F whenever x : δ P Γ; then

1 JV K

F_{D}e “ tδ P LD| DΓ. e |ù^{F} Γ & Γ $ V : δu

2 JM K

FSDe “ tτ P L_{SD}| DΓ. e |ù^{F} Γ & Γ $ M : τ u
For D – D ÝÑ SD, P P Val Y Com, ϕ P L^{D}Y L_{SD} define

Γ |ù^{D} P : ϕ ðñ @e P Env. e |ù^{D} Γ ùñJP K

De PJϕK

D

and let Γ |ù P : ϕ if and only if Γ |ù^{D} P : ϕ for all D modeling λimp

### Corollary (Soundness and Completeness)

For all V P Val and δ P LD, and for all M P Com and τ P L_{SD}

Γ $ V : δ ðñ Γ |ù V : δ and Γ $ M : τ ðñ Γ |ù M : τ.

## Results

For A “ D, S, pD ˆ SqK, and SD, and ϕ P LA define:

JϕK

F“ tX P FA | ϕ P X u

### Theorem (Type Semantics)

Let e |ù^{F} Γ if and only if epxq PJδK

F whenever x : δ P Γ; then

1 JV K

F_{D}e “ tδ P LD| DΓ. e |ù^{F} Γ & Γ $ V : δu

2

JM K

FSDe “ tτ P L_{SD}| DΓ. e |ù^{F} Γ & Γ $ M : τ u

For D – D ÝÑ SD, P P Val Y Com, ϕ P L^{D}Y L_{SD} define
Γ |ù^{D} P : ϕ ðñ @e P Env. e |ù^{D} Γ ùñJP K

De PJϕK

D

and let Γ |ù P : ϕ if and only if Γ |ù^{D} P : ϕ for all D modeling λimp

### Corollary (Soundness and Completeness)

For all V P Val and δ P LD, and for all M P Com and τ P L_{SD}

Γ $ V : δ ðñ Γ |ù V : δ and Γ $ M : τ ðñ Γ |ù M : τ.

## Results

For A “ D, S, pD ˆ SqK, and SD, and ϕ P LA define:

JϕK

F“ tX P FA | ϕ P X u

### Theorem (Type Semantics)

Let e |ù^{F} Γ if and only if epxq PJδK

F whenever x : δ P Γ; then

1 JV K

F_{D}e “ tδ P LD| DΓ. e |ù^{F} Γ & Γ $ V : δu

2

JM K

FSDe “ tτ P L_{SD}| DΓ. e |ù^{F} Γ & Γ $ M : τ u
For D – D ÝÑ SD, P P Val Y Com, ϕ P L^{D}Y L_{SD} define

Γ |ù^{D} P : ϕ ðñ @e P Env. e |ù^{D} Γ ùñJP K

De PJϕK

D

and let Γ |ù P : ϕ if and only if Γ |ù^{D} P : ϕ for all D modeling λimp

### Corollary (Soundness and Completeness)

For all V P Val and δ P LD, and for all M P Com and τ P L_{SD}

## Future work

We have described a particular case of a general pattern Next steps could be

to describe categorically the method followed here

to consider a generic monad T and generic algebraic operators over T

to consider other categories than ω-ALG, such as coherent spaces, event structures, and Rel