Logical Semantics for the First Order ς -Calculus

Logical Semantics for the First Order ς -Calculus

Ugo de’ Liguoro, Torino

Steffen van Bakel, Imperial College, London

ICTCS, Bertinoro, Oct 13-15, 2003

Questions we are addressing

Object calculi have been investigated by syntactical means, under the assumption that their models are

λ-models of some kind. We think that λ-models deserve further investigation in the special concern of

object-oriented concepts and calculi, answering the following:

Questions we are addressing

Object calculi have been investigated by syntactical means, under the assumption that their models are

λ-models of some kind. We think that λ-models deserve further investigation in the special concern of

object-oriented concepts and calculi, answering the following:

Which structures are suitable as models of object calculi?

Questions we are addressing

Object calculi have been investigated by syntactical means, under the assumption that their models are

λ-models of some kind. We think that λ-models deserve further investigation in the special concern of

object-oriented concepts and calculi, answering the following:

Which structures are suitable as models of object calculi?

Is there a simple description of types and values?

Questions we are addressing

Object calculi have been investigated by syntactical means, under the assumption that their models are

λ-models of some kind. We think that λ-models deserve further investigation in the special concern of

object-oriented concepts and calculi, answering the following:

Which structures are suitable as models of object calculi?

Is there a simple description of types and values?

Is there a logical description of such models, allowing for an assignment system to derive properties of

terms?

The untyped ς -calculus

The grammar of terms of the untyped ς-calculus is:

a, b ::= x | [`<sub>i</sub> = ς(x<sub>i</sub>)b<sub>i</sub><sup>i∈I</sup>] | a.` | a.` ⁽) ς(x)b

where

L = {`

_i

| i ∈ N }

is a denumerable set of labels.

The untyped ς -calculus

The grammar of terms of the untyped ς-calculus is:

a, b ::= x | [`<sub>i</sub> = ς(x<sub>i</sub>)b<sub>i</sub><sup>i∈I</sup>] | a.` | a.` ⁽) ς(x)b

where

L = {`

_i

| i ∈ N }

is a denumerable set of labels. The reduction relation is defined by:

[`<sub>i</sub> = ς(x<sub>i</sub>)b<sub>i</sub><sup>i∈I</sup>].`_j → b_j{x_j ^← [`_i = ς(x_i)b_i^i∈I]}

[`<sub>i</sub> = ς(x<sub>i</sub>)b<sub>i</sub><sup>i∈I</sup>].`_j ⁽) ς(x)b → [`<sub>i</sub> = ς(x<sub>i</sub>)b<sub>i</sub><sup>i∈I\j</sup>, `_j = ς(x^A)b]

where

a {x

^←

b }

is the replacement of

x

by

b

in

a

, avoiding variable clashes.

The first order typed system OB ₁

The set of types is defined by the following grammar:

A, B ::= K | [`_i : B_i ^i∈I] where

I

is a finite set of indexes.

Type judgements

The type judgements are defined by the following natural deduction system (where

A = [`

_k

: B

_k ^k∈I

]

^):

Type judgements

The type judgements are defined by the following natural deduction system (where

A = [`

_k

: B

_k ^k∈I

]

^):

(^Var) (x^A ∈ E) E ` x^A

Type judgements

The type judgements are defined by the following natural deduction system (where

A = [`

_k

: B

_k ^k∈I

]

^):

(^Var) (x^A ∈ E) E ` x^A

(^ValObject) E, x^A_i ` b^B_i ⁱ

(∀i ∈ I) E ` [`_i = ς(x^A_i )b^B_i ^{i i∈I}]^A

Type judgements

The type judgements are defined by the following natural deduction system (where

A = [`

_k

: B

_k ^k∈I

]

^):

(^Var) (x^A ∈ E) E ` x^A

(^ValObject) E, x^A_i ` b^B_i ⁱ

(∀i ∈ I) E ` [`_i = ς(x^A_i )b^B_i ^{i i∈I}]^A

(^ValSelect) E ` a^A

(j ∈ I) E ` (a<sup>A</sup>.`_j)^Bj

Type judgements

The type judgements are defined by the following natural deduction system (where

A = [`

_k

: B

_k ^k∈I

]

^):

(^Var) (x^A ∈ E) E ` x^A

(^ValObject) E, x^A_i ` b^B_i ⁱ

(∀i ∈ I) E ` [`_i = ς(x^A_i )b^B_i ^{i i∈I}]^A

(^ValSelect) E ` a^A

(j ∈ I) E ` (a<sup>A</sup>.`_j)^Bj

(^ValUpdate) E ` a<sup>A</sup> E, x<sup>A</sup> ` b^Bj

(j ∈ I) E ` (a<sup>A</sup>.`_j ⁽) ς(y^A)b^Bj)^A

Predicates (intersection types)

The set L of predicates is inductively defined by:

σ, τ ::= κ | ω | (σ∧τ) | (σ→τ ) | h`_i : σ_i^i∈Ii

Predicates (intersection types)

The set L of predicates is inductively defined by:

σ, τ ::= κ | ω | (σ∧τ) | (σ→τ ) | h`_i : σ_i^i∈Ii The intended meanings are:

κ

atomic predicates,

ω

is “true”;

Predicates (intersection types)

The set L of predicates is inductively defined by:

σ, τ ::= κ | ω | (σ∧τ) | (σ→τ ) | h`_i : σ_i^i∈Ii The intended meanings are:

κ

atomic predicates,

ω

is “true”;

σ

∧

τ

is conjunction;

Predicates (intersection types)

The set L of predicates is inductively defined by:

σ, τ ::= κ | ω | (σ∧τ) | (σ→τ ) | h`_i : σ_i^i∈Ii The intended meanings are:

κ

atomic predicates,

ω

is “true”;

σ

∧

τ

is conjunction;

σ →τ

is true of functions sending elements that satisfy

σ

into elements that satisfy

τ

;

Predicates (intersection types)

The set L of predicates is inductively defined by:

σ, τ ::= κ | ω | (σ∧τ) | (σ→τ ) | h`_i : σ_i^i∈Ii The intended meanings are:

κ

atomic predicates,

ω

is “true”;

σ

∧

τ

is conjunction;

σ →τ

is true of functions sending elements that satisfy

σ

into elements that satisfy

τ

;

h`

_i

: σ

_i^i∈I

i

holds of records whose item at

`

_i

satisfies

σ

_i (for all

i ∈ I

^).

Predicates entailment

The pre-order

≤

on predicates is such that:

σ ≤ τ ⇒ h` : σi ≤ h` : τ i

h`<sub>i</sub> : σ<sub>i</sub><sup>i∈I</sup>i ≤ h`_j : τ_j^j∈Ji, if J ⊆ I h`<sub>i</sub> : σ<sub>i</sub><sup>i∈I</sup>i ∧ h`_j : τ_j^j∈Ji ≤ h`_k : ρ_k ^{(k ∈ I ∪ J)}i,

where







ρ_k = σ_k∧τ_k, if k ∈ I∩J, ρ_k = σ_k, if k ∈ I\J, ρ_k = τ_k, if k ∈ J\I plus axioms for the arrow,

ω

and conjunction.

σ ≤ τ

reads as “

σ

implies

τ

”.

Predicate Assignment

A basis

Γ

is a finite set of statements

x

^B

: σ

with distinct subjects. Let

A ≡ [`

_i

: B

_i^i∈I

]

^and

B, B

_i any type, then:

Predicate Assignment

A basis

Γ

is a finite set of statements

x

^B

: σ

with distinct subjects. Let

A ≡ [`

_i

: B

_i^i∈I

]

^and

B, B

_i any type, then:

(^Var) (x^B : σ ∈ Γ) Γ ` x^B : σ

Predicate Assignment

A basis

Γ

is a finite set of statements

x

^B

: σ

with distinct subjects. Let

A ≡ [`

_i

: B

_i^i∈I

]

^and

B, B

_i any type, then:

(^Var) (x^B : σ ∈ Γ) Γ ` x^B : σ

(^TypeObject) Γ, x^A_i : σ_i ` b^B_i ⁱ : τ_i

(∀i ∈ I & J ⊆ I) Γ ` [`_i = ς(x^A_i )b_i^i∈I]^A : h`_j:σ_j→τ_j^j∈Ji

Predicate Assignment

A basis

Γ

is a finite set of statements

x

^B

: σ

with distinct subjects. Let

A ≡ [`

_i

: B

_i^i∈I

]

^and

B, B

_i any type, then:

(^Var) (x^B : σ ∈ Γ) Γ ` x^B : σ

(^TypeObject) Γ, x^A_i : σ_i ` b^B_i ⁱ : τ_i

(∀i ∈ I & J ⊆ I) Γ ` [`_i = ς(x^A_i )b_i^i∈I]^A : h`_j:σ_j→τ_j^j∈Ji

(^ValSelect) Γ ` a<sup>A</sup> : h`_j:σ_j→τ_j^j∈Ji Γ ` a^A : σ_k

(k ∈ J) Γ ` a.`^B_k ^k : τ_k

Predicate Assignment

A basis

Γ

is a finite set of statements

x

^B

: σ

with distinct subjects. Let

A ≡ [`

_i

: B

_i^i∈I

]

^and

B, B

_i any type, then:

(^Var) (x^B : σ ∈ Γ) Γ ` x^B : σ

(^TypeObject) Γ, x^A_i : σ_i ` b^B_i ⁱ : τ_i

(∀i ∈ I & J ⊆ I) Γ ` [`_i = ς(x^A_i )b_i^i∈I]^A : h`_j:σ_j→τ_j^j∈Ji

(^ValSelect) Γ ` a<sup>A</sup> : h`_j:σ_j→τ_j^j∈Ji Γ ` a^A : σ_k

(k ∈ J) Γ ` a.`^B_k ^k : τ_k

Γ ` a<sup>A</sup> : h`_j:σ_j^j∈Ji Γ, y^A : σ ` b^Bk : τ

Example

Let

A ≡ [`

₀

:

^I

, `

₁

:

^{I and}

a ≡ [`

₀

= ς(x

^A

)1

^,

`

₁

= ς(x

^A

)x.`

₀

]

, such that

` a

^A. Then (where I stands for the type Integer, and ^O and ^E for its sub-type Odd, and Even.)

x^A : ω ` 1^I : O

x^A : h`<sup>0</sup> : ω→O<sub>i `</sub> x^A : h`<sup>0</sup> : ω→O<sub>i</sub> x<sup>A</sup> : h`⁰ : ω→O<sub>i `</sub> x<sup>A</sup> : ω x<sup>A</sup> : h`⁰ : ω→Oi ` (x.`⁰)^I : O

` a<sup>A</sup> : h`⁰ : ω→O, `<sup>1</sup> : h`⁰ : ω→Oi→Oi

Note that

`

₀ is a field;

`

₁ is the method ^get

`

₀.

Example (2)

By rule

(

^ValUpdate

)

one might derive

` a<sup>A</sup> : h`₀ : ω→O, `<sub>1</sub>ih`₀ : ω→Oi→O y^A : ω ` 2I : ^E

` (a.`₀ ⁽) ς(y^A)2)^A : h`<sub>0</sub> : ω→<sup>E</sup>, `₁ : h`₀ : ω→^Oii→O

Example (2)

By rule

(

^ValUpdate

)

one might derive

` a<sup>A</sup> : h`₀ : ω→O, `<sub>1</sub>ih`₀ : ω→Oi→O y^A : ω ` 2I : ^E

` (a.`₀ ⁽) ς(y^A)2)^A : h`<sub>0</sub> : ω→<sup>E</sup>, `₁ : h`₀ : ω→^Oii→O

Now

(a.`

_{0 (}⁾

ς (y

^A

)2).`

₁

→

^∗

2

, and we assume

6` 2 :

^O,

but

6` (a.`

_{0 (}⁾

ς (y

^A

)2).`

₁

:

^O because rule

(

^ValSelect

)

does not apply since

6` (a.`₀ ⁽) ς(y^A)2) : h`₀ : ω→Oi.

Example (3)

On the other hand, the following is legal as well, by rule (^TypeObject):

x^A : ω ` 1^I : ^O

x^A : h`<sup>0</sup> : ω→<sup>E</sup>i ` x^A : h`<sup>0</sup> : ω→<sup>E</sup>i x<sup>A</sup> : h`⁰ : ω→^Ei ` x<sup>A</sup> : ω x<sup>A</sup> : h`⁰ : ω→^Ei ` (x.`⁰)I _{: E}

` a<sup>A</sup> : h`⁰ : ω→^O, `<sup>1</sup>h`⁰ : ω→^Ei→^Ei

Example (3)

On the other hand, the following is legal as well, by rule (^TypeObject):

x^A : ω ` 1^I : ^O

x^A : h`<sup>0</sup> : ω→<sup>E</sup>i ` x^A : h`<sup>0</sup> : ω→<sup>E</sup>i x<sup>A</sup> : h`⁰ : ω→^Ei ` x<sup>A</sup> : ω x<sup>A</sup> : h`⁰ : ω→^Ei ` (x.`⁰)I _{: E}

` a<sup>A</sup> : h`⁰ : ω→^O, `<sup>1</sup>h`⁰ : ω→^Ei→^Ei

Therefore, by rule (^ValUpdate), we have the assignment:

` a<sup>A</sup> : h`⁰ : ω→^O, `<sup>1</sup>h`⁰ : ω→^Ei→^Ei y^A : ω ` 2^I : ^E

` (a.`^{0 (}) ς(y^A)2)^A : h`<sup>0</sup> : ω→<sup>E</sup>, `¹ : h`⁰ : ω→^Ei→^Ei

Predicate Assignment (2)

The assignment system is completed by the following

‘logical’ rules:

(ω) E ` a^B

(E / Γ) Γ ` a^B : ω

(∧^I) Γ ` a<sup>B</sup> : σ Γ ` a^B : τ Γ ` a^B : σ∧τ

(≤) Γ ` a<sup>B</sup> : σ σ ≤ τ Γ ` a^B : τ

If E is a context and

Γ

a basis, we say that E fits into

Γ

^,

written

E / Γ

^{, if}

x

^A

: σ ∈ Γ

^implies

x

^A

∈ E

^.

Invariance under conversion

If Γ ` a^A : ρ, and

a → a

^{0, then Γ ` a0A : ρ.}

If Γ ` a^A : ρ and

a

⁰

→ a

^{where E ` a0A for}

E / Γ

^{, then}

Γ ` a^0A : ρ.

Types and Predicates

The set of all predicates L is stratified into a family

{L

_A

}

_A of sets of predicates called languages, indexed over types (considering A→B as a type):

Types and Predicates

The set of all predicates L is stratified into a family

{L

_A

}

_A of sets of predicates called languages, indexed over types (considering A→B as a type):

ω ∈ L_A

Types and Predicates

The set of all predicates L is stratified into a family

{L

_A

}

_A of sets of predicates called languages, indexed over types (considering A→B as a type):

ω ∈ L_A

σ ∈ L_A τ ∈ L_A σ∧τ ∈ L_A

Types and Predicates

The set of all predicates L is stratified into a family

{L

_A

}

_A of sets of predicates called languages, indexed over types (considering A→B as a type):

ω ∈ L_A

σ ∈ L_A τ ∈ L_A σ∧τ ∈ L_A

σ ∈ L_A τ ∈ L_B σ→τ ∈ L_A→B

Types and Predicates

The set of all predicates L is stratified into a family

{L

_A

}

_A of sets of predicates called languages, indexed over types (considering A→B as a type):

ω ∈ L_A

σ ∈ L_A τ ∈ L_A σ∧τ ∈ L_A

σ ∈ L_A τ ∈ L_B σ→τ ∈ L_A→B σ ∈ L_A→Bj

(A = [`<sub>i</sub> : B<sub>i</sub><sup>i∈I</sup>], j ∈ I) h`_j : σi ∈ L_A

Types and Predicates

The set of all predicates L is stratified into a family

{L

_A

}

_A of sets of predicates called languages, indexed over types (considering A→B as a type):

ω ∈ L_A

σ ∈ L_A τ ∈ L_A σ∧τ ∈ L_A

σ ∈ L_A τ ∈ L_B σ→τ ∈ L_A→B σ ∈ L_A→Bj

(A = [`<sub>i</sub> : B<sub>i</sub><sup>i∈I</sup>], j ∈ I) h`_j : σi ∈ L_A

σ ∈ L_A

(σ ≤ τ) τ ∈ L_A

Types and Predicates

The set of all predicates L is stratified into a family

{L

_A

}

_A of sets of predicates called languages, indexed over types (considering A→B as a type):

ω ∈ L_A

σ ∈ L_A τ ∈ L_A σ∧τ ∈ L_A

σ ∈ L_A τ ∈ L_B σ→τ ∈ L_A→B σ ∈ L_A→Bj

(A = [`<sub>i</sub> : B<sub>i</sub><sup>i∈I</sup>], j ∈ I) h`_j : σi ∈ L_A

σ ∈ L_A

(σ ≤ τ) τ ∈ L_A

If τ ∈ L_B whenever x^B : τ ∈ Γ and Γ ` a^A : σ is derivable, then

σ ∈ L

_A^.

Untyped ς -models (1)

D = hD, L,

^emp

,

lcond

,

sel

i

^{is an untyped}

ς

-model if:

Untyped ς -models (1)

D = hD, L,

^emp

,

lcond

,

sel

i

^{is an untyped}

ς

-model if:

D is a λ-model and

L = {`

_i

| i ∈ N }

^{is a}

denumerable set of labels;

Untyped ς -models (1)

D = hD, L,

^emp

,

lcond

,

sel

i

^{is an untyped}

ς

-model if:

D is a λ-model and

L = {`

_i

| i ∈ N }

^{is a}

denumerable set of labels;

emp ∈ D, sel

: D × L → D

, lcond

: D × L × D → D

;

Untyped ς -models (1)

D = hD, L,

^emp

,

lcond

,

sel

i

^{is an untyped}

ς

-model if:

D is a λ-model and

L = {`

_i

| i ∈ N }

^{is a}

denumerable set of labels;

emp ∈ D, sel

: D × L → D

, lcond

: D × L × D → D

; such that (writing lcond and sel in a Curryfied form):

sel

(

^lcond

x `

_i

y )`

_i

= y

,

i 6= j ⇒

^sel

(

^lcond

x `

_i

y )`

_j

=

^sel

x `

_j, i 6= j ⇒ lcond(lcond x `<sub>i</sub> y) `_j z =

lcond(lcond x `<sub>i</sub> z) `_j y.

Untyped ς -models (2)

To build an untyped ς-model it suffices to solve:

D = At + [L → D]_⊥ + [D → D]

Since any D is a λ-model, we shall freely use abstraction notation. Moreover, we use the abbreviations:

h·i = emp

h`<sub>i</sub> = d<sub>i</sub><sup>i</sup> ∈ {1,...,n}i = lcond(. . . (lcond emp `₁ d₁) . . .)`<sub>n</sub> d<sub>n</sub> d · `_i = sel d `_i

d · `<sub>i</sub> := e = lcond d `_i e

Predicate Interpretation

If

D

is a solution of

D = At + [L → D]

_⊥

+ [D → D]

^,

then

[[ σ ]]

^D_η

⊆ D

^:

[[ ω ]]

_η

= D

,

[[ κ ]]

_η

= η ( κ )

^{, where}

η : [[ κ ]] → ℘(D)

^,

[[ σ

∧

τ ]]

_η

= [[ σ ]]

_η

∩ [[ τ ]]

_η^,

[[ σ → τ ]]

_η

= {d ∈ D | ∀e ∈ [[ σ ]]

_η

. de ∈ [[ τ ]]

_η

}

^,

[[h`

_i

: σ

_i ^i∈I

i]]

_ξ

= {d ∈ D | ∀i ∈ I. d · `

_i

∈ [[ σ

_i

]]

_η

}

^.

If

σ ≤ τ

then, for any

η

,

[[ σ ]]

_η

⊆ [[ τ ]]

_η^.

Type Interpretation

Let

D

be any domain: a retraction over

D

is a continuous function

ρ : D → D

^{such that}

ρ

²

= ρ ◦ ρ = ρ

.

Types can be interpreted by retractions setting (Scott):

[[A]]^D = {d ∈ D | ρ_A(d) = d}.

Type Interpretation

Let

D

be any domain: a retraction over

D

is a continuous function

ρ : D → D

^{such that}

ρ

²

= ρ ◦ ρ = ρ

.

Types can be interpreted by retractions setting (Scott):

[[A]]^D = {d ∈ D | ρ_A(d) = d}.

Proposition. Let

A ≡ [`

_i

: B

_i ^i∈I

]

^{: if}

ρ

_Bi is a retraction for all

i ∈ I

, then there exists a retraction

ρ

_A such that

ρ_A(d) = h`<sub>i</sub> = ρ<sub>A→Bi</sub>(d · `_i) ^i∈Ii, where

ρ

_A→B

(d) = λx.ρ

_B

(d(ρ

_A

(x)))

^.

Term Interpretation over Retraction Models

We say that

(D , {ρ

_A

}

_A

)

^{is a} retraction model if D is an untyped ς-model and

{ ρ

_A

}

_A is a family of retractions such that

ρ_A(d) = h`<sub>i</sub> = ρ<sub>A→Bi</sub>(d · `_i) ^i∈Ii where A ≡ [`_i : B_i ^i∈I].

Term Interpretation over Retraction Models

We say that

(D , {ρ

_A

}

_A

)

^{is a} retraction model if D is an untyped ς-model and

{ ρ

_A

}

_A is a family of retractions such that

ρ_A(d) = h`<sub>i</sub> = ρ<sub>A→Bi</sub>(d · `_i) ^i∈Ii where A ≡ [`_i : B_i ^i∈I].

The term interpretation [[a^A]]^D_ξ ∈ D, where ξ is an environment, is defined:

[[x^A]]_ξ = ξ(x)

[[[`<sub>i</sub> = ς(x<sup>A</sup><sub>i</sub> )b<sup>B</sup><sub>i</sub> <sup>i i∈I</sup>]]]<sub>ξ</sub> = h`_i = λd.[[b^B_i ⁱ]]_{ξ[xi:=ρA(d)]} ^i∈Ii [[(a^A.`<sub>i</sub>)<sup>Bi</sup>]]<sub>ξ</sub> = ([[a<sup>A</sup>]]<sub>ξ</sub>· `_i)[[a^A]]_ξ

Soundness

Set

ξ |= E

if

ξ (x

^A

) ∈ [[ A ]]

^{D whenever}

x

^A

∈ E

^;

E |= a

^A if for all

ξ

s.t.

ξ |= E

,

[[ a

^A

]]

^D_ξ

∈ [[ A ]]

^D;

ξ |= Γ

^if

x

^A

: σ ∈ Γ

^implies

ξ (x

^A

) ∈ [[ σ ]]

_η

⊆ [[ A ]]

^D;

Γ |= a

^A

: σ

if for all

ξ

s.t.

ξ |= Γ

^,

[[ a

^A

]]

^D_ξ

∈ [[ σ ]]

_η

⊆ [[ A ]]

^D.

Soundness

Set

ξ |= E

if

ξ (x

^A

) ∈ [[ A ]]

^{D whenever}

x

^A

∈ E

^;

E |= a

^A if for all

ξ

s.t.

ξ |= E

,

[[ a

^A

]]

^D_ξ

∈ [[ A ]]

^D;

ξ |= Γ

^if

x

^A

: σ ∈ Γ

^implies

ξ (x

^A

) ∈ [[ σ ]]

_η

⊆ [[ A ]]

^D;

Γ |= a

^A

: σ

if for all

ξ

s.t.

ξ |= Γ

^,

[[ a

^A

]]

^D_ξ

∈ [[ σ ]]

_η

⊆ [[ A ]]

^D.

Then

1. If

E ` a

^A then

E |= a

^A;

2. if

Γ ` a

^A

: σ

then

Γ |= a

^A

: σ

.

The Filter Model

If F is the set of filters over L (nonempty, upward closed sets of predicates closed under ∧), the it is a λ-model such that:

emp

= ↑h·i

^;

F · `

_i

= { σ | h`

_i

: σ i ∈ F }

^;

(F · `

_i

:=

G ) =







h`

_j

: σ

_j ^j∈J

i | (j 6= i & h`

_j

: σ i ∈ F ) ∨ (j = i & σ

_i

∈ G)

F is an untyped ς-model.

Languages: retractions over F

The family

{ ρ

_A

}

_A ^where

ρ

_A

(F ) = F ∩ L

_A, is a family of retractions turning F into a retraction model. Indeed, for all

F ∈ F

^{and type}

A ≡ [`

_i

: B

_i ^{i ∈ I}

]

^:

F ∩ L_A = h`<sub>i</sub> = λX.(F · `_i)(X ∩ L_A) ∩ L_Bi ^{i ∈ I}i, where

λX.e [X] = { σ → τ | τ ∈ e[↑ σ ]}

represents a continuous function over F.

Moreover,

[[ σ ]]

_η

= {F ∈ F | σ ∈ F }

is a predicate interpretation such that, if

η ( κ ) ⊆ [[ K ]]

^whenever

κ ∈ L

_K^{, then}

[[ σ ]]

_η

⊆ [[ A ]]

^if

σ ∈ L

_A^.

Completeness

For all a^A such that E ` a^A, for some E, and all environment

ξ

s.t.

ξ |= E

:

[[a^A]]^F_ξ = {σ | ∃Γ. ξ |= Γ & Γ ` a^A : σ}

Γ ` a^A : σ ⇐⇒ Γ |= a^A : σ.

Further steps

Account for (first order) subtyping (some ideas, many problems).

Study higher order calculi, possibly including classes and class inheritance (mixins).

Consider hybrid calculi, like objects and MA (work in progress with Barbanera).