DomainsX-September2011,Swansea Ugode’Liguoro λµ andRelatedCalculi ADomainLogicApproachtoModelsof

A Domain Logic Approach to Models of λµ and Related Calculi

Ugo de’Liguoro

joint work with Steffen van Bakel and Franco Barbanera

Domains X - September 2011, Swansea

Motivations

Motivations

Parigot’s λµ-calculus interprets classical proofs as functional programs plus (some kind of) continuations

Motivations

Parigot’s λµ-calculus interprets classical proofs as functional programs plus (some kind of) continuations

Continuations are a powerful concept, but make reasoning hard

Motivations

Parigot’s λµ-calculus interprets classical proofs as functional programs plus (some kind of) continuations

Continuations are a powerful concept, but make reasoning hard

Intersection type assignment system have been successfully used in the study of the pure λ-calculus, and also of term rewriting, object calculi, etc.

Motivations

Parigot’s λµ-calculus interprets classical proofs as functional programs plus (some kind of) continuations

Continuations are a powerful concept, but make reasoning hard

Intersection type assignment system have been successfully used in the study of the pure λ-calculus, and also of term rewriting, object calculi, etc.

We take λµ as a significant case study to investigate how intersection systems might be of help to reason about programming with continuations.

Motivations

Parigot’s λµ-calculus interprets classical proofs as functional programs plus (some kind of) continuations

Continuations are a powerful concept, but make reasoning hard

Intersection type assignment system have been successfully used in the study of the pure λ-calculus, and also of term rewriting, object calculi, etc.

We take λµ as a significant case study to investigate how intersection systems might be of help to reason about programming with continuations.

Previous work (not all successful) by: Dougherty, Ghilezan, Lescanne (on λµ˜µ) and van Bakel (on X , λµ˜µ and λµ).

Overview

Overview

continuation semantics (Streicher, Reus) +

domain logic (Abramsky) =

filter model for λµ (like Barendregt, Coppo, Dezani)

Overview

continuation semantics (Streicher, Reus) +

domain logic (Abramsky) =

filter model for λµ (like Barendregt, Coppo, Dezani)

We eventually show that simply typed λµ-terms (in Parigot’s system) have non trivial types in our system.

Are SN λµ-terms characterizable in our system?

Continuation Semantics (Streicher-Reus [SR98])

Continuation domain equations







R results

D = [C → R] denotations C = (D×C) continuations

If (R,D,C) are a solution thenD is an extensional λ-model:

D≃ [C → R] ≃ [(D×C) → R] ≃ [D → [C → R]] ≃ [D →D]

while C is the infinite product:

C ≃D×D× · · ·

Intersection Type Representation of ω-Algebraic Lattices

Given A ∈ ωALG

LA : σ, τ ::= · · · | σ∧τ | ω

≤A: a preorder s.t.

σ ≤Aω ω is the top

σ ∧ τ ≤ σ, τ

ρ ≤ σ, ρ ≤ τ ⇒ ρ ≤ σ ∧ τ the meet of σ, τ Let

Θ : LA → K(A) be surjective and s.t. σ ≤Aτ ⇔ Θ(σ) ⊒ Θ(τ ) then

F^A:= Filt(LA) ≃ Filt(LA/≤A) ≃ Filt(K^op(A)) ≃ A via the continuous extension of ↑ σ 7→ ↑ Θ(σ)

Type Theory ≤

Fix R ∈ ωALG:

LR : ρ ::= νa | ω | ρ∧ρ (a ∈ K(R))

≤R: ν⊥ =R ω νa⊔ b =^Rν^a∧ν^b

b ⊑ a ∈ K(R) ⇒ νa ≤R νb

Proposition

Define F^R = Filt(L^R/≤R); then R ≃ F^R because of L^R/LR ≃ K^op(R) via

Θ(νa) = a, Θ(ω) = ⊥, Θ(ρ∧ρ^′) = Θ(ρ) ⊔ Θ(ρ^′)

Type Theories ≤

and ≤

Type languages (constructed following the approximants of the inverse-limit construction):

C0 = {⊥}

Dn = [Cn→ R]

Cn+1 = Dn× Cn

D = limnDn

C = limnCn

=⇒

LC₀ κ0 ::= ω

LDn δn ::= ρ | κn→ ρ | δn∧δn| ω LC_n+1 κn+1 ::= δn× κn| κn∧κn| ω

LD = S

nLDn

LC = S

nLCn

or equivalently

LD: δ ::= ρ | κ → ρ | ω | δ∧δ LC : κ ::= δ × κ | ω | κ∧κ

Type Theories ≤

and ≤

ω≤C ω× ω (δ1× κ1)∧(δ2× κ2) ≤C (δ1∧κ2) × (κ1∧κ2) δ1≤Dδ2 κ1≤C κ2

δ1× κ1≤Cδ2× κ2

Theory ≤D:

ω≤Dω→ ω ν=Dω→ ν (κ → δ1)∧(κ → δ2) ≤Dκ→ (κ1∧κ2) κ2≤Cκ1 δ1≤Dδ2

κ1→ δ1≤Dκ2→ δ2

Solution of Continuation Equations

Filter Domains solving Continuation Equations Let F^C = Filt(LC/ ≤C) and F^D = Filt(LD/ ≤D):

F^D ≃ [F^C → F^R] and F^C ≃ F^D× F^C

Via the mappings F : F^D → [F^C → F^R] and G : [F^C → F^R] → F^D F d k = {ρ ∈ LR | ∃κ → ρ ∈ d. κ ∈ k]}

G f = {V

i ∈Iκi → ρi∈ LD| ∀i ∈ I . ρi∈ f (↑ κi)}

and the mappings H : F^C → (F^D× F^C) and K : (F^D× F^C) → F^C H k = h{δ ∈ LD | δ × κ ∈ k}, {κ ∈ LD | δ × κ ∈ k}i K hd, ki = {δ × κ ∈ LC | δ ∈ d & κ ∈ k}

The λ-calculus: syntax and continuation semantics

Syntax:

M, N ::= x | λx.M | MN (terms) Semantics [SR98]:

[[·]]^D: Trm → Env →D where D=C → R

[[x]]^Dek = e xk

[[λx.M]]^Dek = [[M]]^De[x :=d]k^′ hd,k^′i =k [[MN]]^Dek = [[M]]^De h[[N]]^De,ki

where e ∈ Env = Var →D,d∈D andk,k^′∈C so that [[M]]^Dek ∈ R.

Type interpretation

[[νa]]^R = {r ∈ R | a ⊑ r } [[δ × κ]]^R = [[δ]]^D× [[κ]]^C

[[κ → ρ]]^D = {d ∈ D | ∀k ∈ [[κ]]. d(k) ∈ [[ρ]]^R} [[ρ]]^D = [[ω → ρ]]^D

[[ω]]^A = A for A = R, D, C

[[σ∧τ ]]^A = [[σ]]^A∩ [[τ ]]^A

Let σ, τ ∈ LA

Soundness of Type Interpretation

1 [[σ]]^A ⊆ A and [[σ]]^A = ↑ Θ(σ)

2 σ ≤Aτ ⇒ [[σ]]^A⊆ [[τ ]]^A

The λ-calculus: continuation models and validity

A continuation model (a model for short) is a triple M = (R, D, C ) satisfying the continuation equations, together with the maps [[·]]^R, [[·]]^D and [[·]]^C.

A basis is a set Γ = {x1: δ1, . . . , xn: δn}, with xi ∈ Var, δi∈ LD. A judgement is an expression Γ ⊢ M : δ, with δ ∈ LD.

The concepts of satisfaction and validity are the standard ones:

e |= Γ ⇔ ∀x : δ ∈ Γ. e(x) ∈ [[δ]]^D

Γ |=MM : δ ⇔ ∀e ∈ Env. e |= Γ ⇒ [[M]]^De ∈ [[δ]]^D Γ |= M : δ ⇔ ∀M. Γ |=MM : δ

where e ∈ Env = Var →D is any environment.

Γ ⊢ M : δ is valid if and only if Γ |= M : δ

The filter model

Consider the model F = (F^R, F^D, F^C):

The filter model

Consider the model F = (F^R, F^D, F^C):

Rules from interpretation in F

defininens, right hand side of defining clause = premises definiendum, left hand side of defining clause = conclusion

The filter model

Consider the model F = (F^R, F^D, F^C):

Rules from interpretation in F

defininens, right hand side of defining clause = premises definiendum, left hand side of defining clause = conclusion Observing that

[[M]]^FDe ∈ [[δ]]^FD ⇔ δ ∈ [[M]]^FDe

Rules from interpretation clauses: (→ I) and (→ E)

Rules from interpretation clauses: (→ I) and (→ E)

Consider the interpretation of λx.M in F^D:

[[λx.M]]^FDe h↑ δ, ↑ κi=[[M]]^FDe[x :=↑ δ] ↑ κ where h↑ δ, ↑ κi ≃ ↑ (δ × κ). This reads as the inference rule:

Γ, x : δ ⊢ M : κ → ρ (→ I) Γ ⊢ λx.M : δ × κ → ρ

Rules from interpretation clauses: (→ I) and (→ E)

Consider the interpretation of λx.M in F^D:

[[λx.M]]^FDe h↑ δ, ↑ κi=[[M]]^FDe[x :=↑ δ] ↑ κ where h↑ δ, ↑ κi ≃ ↑ (δ × κ). This reads as the inference rule:

Γ, x : δ ⊢ M : κ → ρ (→ I) Γ ⊢ λx.M : δ × κ → ρ

Similarly in case of MN, from

[[MN]]^FDe ↑ κ=[[M]]^FDe h[[N]]^FDe, ↑ κi and for any δ ∈ [[N]]^FDe we get:

Γ ⊢ M : δ × κ → ρ Γ ⊢ N : δ (→ E) Γ ⊢ MN : κ → ρ

Remark

By extending LD with δ1→ δ2types and putting δ × κ → ρ =D δ → (κ → ρ) we have by subsumption:

Γ ⊢ λx.M : δ × κ → ρ δ × κ → ρ ≤Dδ → (κ → ρ) Γ ⊢ M : δ → (κ → ρ)

that (a form of) the standard rule (→ I) is admissible:

Γ, x : δ ⊢ M : κ → ρ Γ ⊢ λx.M : δ → (κ → ρ) Similarly for rule (→ E).

The λµ-calculus: syntax and reduction

λµ syntax:

M, N ::= x | λx.M | MN |µα.Q (terms)

Q ::= [α]M (commands)

Structural substitution:

T[α ⇐ L]≡ the replacement of all[α]N by[α]NLin T Reduction:

(β) : (λx.M)N −→ M[N/x]

(µ) : (µβ.Q)N −→ µβ.Q[β ⇐ N]

(ren) : [α]µβ.Q −→ Q[α/β]

(µη) : µα.[α]M −→ M if α 6∈ fn(M)

The λµ-calculus: term semantics

Env = (Var →D) + (Name →C) [[·]]^D : Trm → Env →D

[[·]]^C : Cmd → Env →C [[x]]^Dek = e xk

[[λx.M]]^Dek = [[M]]^De[x :=d]k^′ hd,k^′i =k [[MN]]^Dek = [[M]]^De h[[N]]^De,ki

[[µα.Q]]^Dek = dk^′ hd,k^′i = [[Q]]^Ce[α :=k]

[[[α]M]]^Ce = h[[M]]^De,ki k = e α

where e ∈ Env, d ∈D and k,k^′ ∈C. We immediately have:

M =_βµ N ⇒ ∀e ∈ Env,k ∈C, [[M]]^Dek = [[N]]^Dek

Typing judgements

Typing judgements are triples of a basis, a term/command judgement and acontext:

basis: Γ = {x1: δ1, . . . , xn: δn}, with xi ∈ Var, δi ∈ LD

judgement:

term: M : δ with M ∈ Trm, δ ∈ LD

command: Q : κ with Q ∈ Cmd, κ ∈ LC

context: ∆ = {α1: κ1, . . . , αm: κm}, with αi∈ Name, κi∈ LC

A typing judgement has either forms:

Γ ⊢ M : δ | ∆ or Γ ⊢ Q : κ | ∆

The λµ-calculus: validity revised

Let e ∈ Env:

e |= Γ, ∆ ⇔ ∀x : δ ∈ Γ. e(x) ∈ [[δ]]^D & ∀α : κ ∈ ∆. e(α) ∈ [[κ]]^C Γ |=MM : δ | ∆ ⇔ ∀e ∈ Env. e |= Γ, ∆ ⇒ [[M]]^De ∈ [[δ]]^D and similarlyM |= Γ ⊢ Q : κ | ∆

Γ |= M : δ | ∆ (Γ |= Q : κ | ∆) ⇔

∀M. Γ |=MM : δ | ∆ (Γ |=MQ : κ | ∆)

Say that Γ ⊢ M : δ | ∆ (Γ ⊢ Q : κ | ∆) is valid if Γ |= M : δ | ∆ (Γ |= Q : κ | ∆)

Rules from interpretation clauses: (×)

Consider:

[[[α]M]]^FCe =h[[M]]^FDe, e αi then for any δ ∈ [[M]]^FDe and κ ∈ (e α):

δ × κ ∈ [[[α]M]]^FCe from which we obtain the rule

Γ ⊢ M : δ | α : κ, ∆ Γ ⊢ [α]M : δ × κ | α : κ, ∆(×)

Rules from interpretation clauses: (µ)

Recall that

[[µα.Q]]^FDe ↑ κ = d · k^′ where [[Q]]^FCe[α :=↑ κ] = hd, k^′i Filter application is d · k^′ = {ρ | ∃κ^′ → ρ ∈ d. κ^′ ∈ k^′} hence

(κ^′ → ρ) × κ^′ ∈ [[Q]]^FCe[α :=↑ κ] ⇒ ρ ∈ [[µα.Q]]^FDe ↑ κ and we obtain the rule

Γ ⊢ Q : (κ^′→ ρ) × κ^′ | α : κ, ∆ Γ ⊢ µα.Q : κ → ρ | ∆ (µ)

The type assignment system ⊢

(Var) Γ, x : δ ⊢ x : δ | ∆

Γ, x : δ ⊢ M : κ → ρ | ∆ (→ I) Γ ⊢ λx.M : δ × κ → ρ | ∆

Γ ⊢ M : δ × κ → ρ | ∆ Γ ⊢ N : δ | ∆ (→ E) Γ ⊢ MN : κ → ρ | ∆

Γ ⊢ M : δ | α : κ, ∆ (×) Γ ⊢ [α]M : δ × κ | α : κ, ∆

Γ ⊢ Q : (κ^′→ ρ) × κ^′| α : κ, ∆ (µ) Γ ⊢ µα.Q : κ → ρ | ∆

T = M, Q; A = D, C ; σ, τ ∈ LA: (ω)

Γ ⊢ T : ω | ∆

Γ ⊢ T : σ | ∆ Γ ⊢ T : τ | ∆ (∧) Γ ⊢ T : σ∧τ | ∆

Γ ⊢ T : σ | ∆ σ≤Aτ (≤) Γ ⊢ T : τ | ∆

Properties of the type assignment system

Theorem: subject reduction and expansion If M −→_βµ N then

Γ ⊢ M : δ | ∆ ⇔ Γ ⊢ N : δ | ∆

Theorem: soundness and completeness

Γ ⊢ M : δ | ∆ ⇔ Γ |= M : δ | ∆

Proof based on the filter model construction and the fact that [[M]]^FDe = {δ | ∃Γ, ∆. e |= Γ, ∆ & Γ ⊢ M : δ | ∆}

Parigot’s (first order) type assignment system ⊢

Propositional types:

A, B ::= ϕ | ⊥A| A → B Rules:

Γ, x : A ⊢ x : A | ∆ Γ, x : A ⊢ M : B | ∆

Γ ⊢ λx.M : A → B | ∆

Γ ⊢ M : A → B | ∆ Γ ⊢ N : A | ∆ Γ ⊢ MN : B | ∆

Γ ⊢ Q : ⊥B | α : A, ∆ Γ ⊢ µα.Q : A | ∆

Γ ⊢ M : A | α : A, ∆ Γ ⊢ [α]M : ⊥A | α : A, ∆

Translating Parigot’s types into intersection types

Translating Parigot’s types into intersection types

Take a ∈ R \ {⊥}, and write ν ≡ νa. Consider the maps from propositional types into ours, A^C ∈ LC and A^D ∈ LD:

ϕ^C = ν × ω

⊥^C_A = (A^C → ν) × A^C (A → B)^C = (A^C → ν) × B^C A^D = A^C → ν

Write Γ^D = {x : A^D | x : A ∈ Γ} and ∆^C = {α : A^C | α : A ∈ ∆}

Translating Parigot’s types into intersection types

Take a ∈ R \ {⊥}, and write ν ≡ νa. Consider the maps from propositional types into ours, A^C ∈ LC and A^D ∈ LD:

ϕ^C = ν × ω

⊥^C_A = (A^C → ν) × A^C (A → B)^C = (A^C → ν) × B^C A^D = A^C → ν

Write Γ^D = {x : A^D | x : A ∈ Γ} and ∆^C = {α : A^C | α : A ∈ ∆}

Theorem

1 Γ ⊢P M : A | ∆ ⇒ Γ^D ⊢∧ M : A^D | ∆^C

2 Γ ⊢P Q : A | ∆ ⇒ Γ^D ⊢∧ Q : A^C | ∆^C

Conjecture: exactly all strongly normalizable terms are typeable in a subsystem ⊢∧⁻, essentially eliminating ω.

Conclusions and future work

1 we have defined a type theory which describes a denotational model of λµ

2 the type assignment system induces a filter model of the λµ-calculus

3 all terms which are typeable in Parigot’s (first order) assignment system have a non trivial typing in our system

4 we conjecture that non trivial typing in a proper subsystem of ours characterizes strongly normalizable terms

5 the system we have proposed could characterize other

interesting sets of terms, and more interestingly might provide a tool to investigate Parigot’s computational interpretation of classical proofs

Reference

Steffen van Bakel, Franco Barbanera and Ugo de’ Liguoro,

“A Filter Model for λµ-calculus”, Proc. of TLCA 2011, LNCS 6690, 213-228; full version:

http://www.di.unito.it/∼deligu/papers/BBL FLM.pdf