• Non ci sono risultati.

From semantics to types: the case of the imperative λ-calculus

N/A
N/A
Protected

Academic year: 2022

Condividi "From semantics to types: the case of the imperative λ-calculus"

Copied!
30
0
0

Testo completo

(1)

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

(2)

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)

(3)

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)

(4)

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)

(5)

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)

(6)

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)

(7)

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)

(8)

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

(9)

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

(10)

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 KDeq JM ‹ V K

TDe “ pJM KTDeq ‹ ΦpJV KDeq

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

(11)

The partiality and state monad S over Dom

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

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

SX “SÝÑ pX ˆSqK equipped with two (families of) operators unit and ‹:

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

"

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

K if cpςq “ K

for c PSX and ς PS

(12)

A domain equation

Theorem

There exists a domainDP Dom solving the equation D “ D ÝÑS ÝÑ pD ˆSqK

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

(13)

Algebraic operators ` a la Plotkin and Power

Algebraic operators are morphisms opX : pTX qnÝÑTX s.t.

opX ˝ pf:ˆ ¨ ¨ ¨ ˆ f: loooooomoooooon

n

q “ f:˝ opX with f : X ÝÑTX

In general, if A is a domain of abstract arities and P of parameters then op : P ˆ pTX qAÝÑTX – pTX qAÝÑ pTX qP

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 ˆ pSDqD ÝÑSD »DÝÑSD by get`d ς “ d pς p`qq ς Taking P “D and A “ 1, we define:

set`:Dˆ pSDq1ÝÑSD»DˆSDÝÑSD by set`pd , c q ς “ c pςr` ÞÑ d sq

(14)

Algebraic operators ` a la Plotkin and Power

Algebraic operators are morphisms opX : pTX qnÝÑTX s.t.

opX ˝ pf:ˆ ¨ ¨ ¨ ˆ f: loooooomoooooon

n

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

op : P ˆ pTX qAÝÑTX – pTX qAÝÑ pTX qP

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 ˆ pSDqD ÝÑSD »DÝÑSD by get`d ς “ d pς p`qq ς Taking P “D and A “ 1, we define:

set`:Dˆ pSDq1ÝÑSD»DˆSDÝÑSD by set`pd , c q ς “ c pςr` ÞÑ d sq

(15)

Algebraic operators ` a la Plotkin and Power

Algebraic operators are morphisms opX : pTX qnÝÑTX s.t.

opX ˝ pf:ˆ ¨ ¨ ¨ ˆ f: loooooomoooooon

n

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

op : P ˆ pTX qAÝÑTX – pTX qAÝÑ pTX qP

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 ˆ pSDqD ÝÑSD »DÝÑSD by get`d ς “ d pς p`qq ς Taking P “D and A “ 1, we define:

1

(16)

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¨KS

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 .MqKSDe “ 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

(17)

Types as (duals of) compact points

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

D – IpKpDqq – F pKoppDqq for any D P ω-ALG

An intersection type theory Th “ pL, ďq is a finitary presentation of KoppDq s.t. KpDq Q d Ð[ σdP 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

(18)

Types as (duals of) compact points

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

D – IpKpDqq – F pKoppDqq for any D P ω-ALG

An intersection type theory Th “ pL, ďq is a finitary presentation of KoppDq s.t.

KpDq Q d Ð[ σdP 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

(19)

Types as (duals of) compact points

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

D – IpKpDqq – F pKoppDqq for any D P ω-ALG

An intersection type theory Th “ pL, ďq is a finitary presentation of KoppDq s.t.

KpDq Q d Ð[ σdP 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

(20)

The filter model F

D

– rF

D

Ý Ñ S F

D

s of λ

imp

Theorem

There are theories ThD and ThSD such that FD “ FDÝÑSD– rFD ÝÑSFDs

Proof. By defining the theories ThD, ThS, ThC withC“ pDˆSqK, and ThSD by mutual induction:

LD: δ ::“ δ ÝÑ τ | δ ^ δ1| ωD LS : σ ::“ x` : δy | σ ^ σ1| ωS

LC : κ ::“ δ ˆ σ | κ ^ κ1 | ωC LSD: τ ::“ σ ÝÑ κ | τ ^ τ1 | ωSD

plus axioms and rules e.g.

pσ ÝÑ κq ^ pσ ÝÑ κ1q ďSD σ ÝÑ κ ^ κ1

σ1ďS σ κ ďC κ1 σ ÝÑ κ ďSD σ1ÝÑ κ1

(21)

The interpretations JV K

FD

and JM K

FSD

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

FSD

e “ pJM K

FSD

eq ‹FpJV K

FD

eq

Defining (after BCD’83)

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

pX ‹FY 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ˆ σ2P LSD | Dδ1, σ1.σ ÝÑ δ1ˆ σ1PJM K

FSDe & δ1ÝÑ σ1ÝÑ δ2ˆ σ2PJV K

FDeu where Filt X is the least filter including X .

(22)

The interpretations JV K

FD

and JM K

FSD

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

FSD

e “ pJM K

FSD

eq ‹FpJV K

FD

eq Defining (after BCD’83)

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

pX ‹FY 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ˆ σ2P LSD | Dδ1, σ1.σ ÝÑ δ1ˆ σ1PJM K

FSDe &

δ1ÝÑ σ1 ÝÑ δ2ˆ σ2PJV K

FDeu where Filt X is the least filter including X .

(23)

From interpretations to typing rules

To Γ “ tx1: δ1, . . . , xn: δnu 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ψ | ϕ1PJP1K

FeΓ1 & ¨ ¨ ¨ & ϕnPJPnK

FeΓnu

(24)

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 : ψ

(25)

Example

From

JM ‹ V K

FSDeΓ “ pJM K

FSDeΓq ‹FpJV K

FDeΓq

“ Filttσ ÝÑ δ2ˆ σ2P LSD | Dδ1, σ1.σ ÝÑ δ1ˆ σ1PJM K

FSDeΓ &

δ1 ÝÑ σ1ÝÑ δ2ˆ σ2PJV K

FDeΓu

we get the rule

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

(26)

The type assignment system

Rewriting as rules the clauses in the definition ofJV K

FD andJM K

FSD, 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 : ψ

(27)

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

FDe “ tδ P LD| DΓ. e |ùF Γ & Γ $ V : δu

2 JM K

FSDe “ tτ P LSD| DΓ. e |ùF Γ & Γ $ M : τ u For D – D ÝÑ SD, P P Val Y Com, ϕ P LDY LSD 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 LSD

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

(28)

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

FDe “ tδ P LD| DΓ. e |ùF Γ & Γ $ V : δu

2

JM K

FSDe “ tτ P LSD| DΓ. e |ùF Γ & Γ $ M : τ u

For D – D ÝÑ SD, P P Val Y Com, ϕ P LDY LSD 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 LSD

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

(29)

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

FDe “ tδ P LD| DΓ. e |ùF Γ & Γ $ V : δu

2

JM K

FSDe “ tτ P LSD| DΓ. e |ùF Γ & Γ $ M : τ u For D – D ÝÑ SD, P P Val Y Com, ϕ P LDY LSD 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 LSD

(30)

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

Riferimenti

Documenti correlati

[r]

Our approach stems from realizing the existence of a structural analogy, introduced in [9], which to our knowledge had not been hitherto pointed out in the literature, between

Generalized log odds ratio analysis for the association in two-way contingency table PAGE 5.. 2 Notations and odds

Ripercorriamo ora i medesimi passi della costruzione della scala pitagorica, includendo un fattore primo in più nella categoria dei numeri (20): la base teorica aggiunge al

La matrice diagonalizzante P è la matrice le cui colonne sono costituite dagli autovettori associati agli autovalori della

4 School of Physics State Key Laboratory of Nuclear Physics and Technology, Peking University, Beijing, China. 5 University of Chinese Academy of Sciences,

The decay amplitudes and the production polarisation are determined from the moments using a Bayesian analysis.. The marginalisation over unwanted parameters is performed using

(iii) With respect to the order ≺ D , every question move has one successor, the corresponding answer; while every answer move a has infinitely many imme- diate successors which are