and Ugo de’Liguoro

Subtyping object and recursive types logically

Steffen van Bakel

and Ugo de’Liguoro

†

Department of Computing, Imperial College, London

‡

Dipartimento di Informatica, Universit`a di Torino

Subtyping as Subsumption

The basic rule of subtyping is subsumption:

E ⊢ a:A E ⊢ A <: B E ⊢ a:B

Subtyping is then a matter of substitution in typed contexts:

E ⊢ a : A E ⊢ A<:B E, x : B ⊢ b[x] : C E ⊢ b[a] : C

If this is safe then the system is sound.

Semantics of Subtyping

Essentially two approaches:

inclusion semantics: PER semantics [Buce-Longo, Bruce-Mitchell]

cohercion semantics [Tannen-Coquand-Gunter-Scedrov]

Problems:

with PERs: persistent techincal problems while modeling recursive types and bounded quantification;

with cohercion: too close to syntax, as difficult to use as direct reasoning on term syntax.

We propose a third approach based on logical semantics and domain logic.

Equational Subtyping

This is the idea of equational subsumption:

E ⊢ a = a^′ : A E ⊢ A <: B E ⊢ a = a^′ : B

If A<:B then the equational theory associated with A is as strong as the theory associated with B, that is:

any equation holding at A, holds at B as well, the converse does not hold in general;

dually: if a context x : B ⊢ b[x] : C is such that either b[a] ⇓ v and b[a^′] ⇑ or b[a] ⇓ v, b[a^′] ⇓ v^′ with v 6= v^′ : C (a and a^′ are separable at B) then the same holds with x : A ⊢ b[x] : C.

Two terms are observationally equivalent at A if they are not separable at A for any context of ground type.

The case of Records

Consider the following terms representing records:

r ≡ {ℓ₀ := 0, ℓ₁ := 1, ℓ₂ := 2} : {ℓ₀ : Int, ℓ₁ : Int, ℓ₂ : Int}

s ≡ {ℓ₀ := 1, ℓ₁ := 1, ℓ₂ := 2} : {ℓ₀ : Int, ℓ₁ : Int, ℓ₂ : Int}

Then in λ-calculi with records (see e.g. book [Mitchell]) r 6= s : {ℓ₀ : Int, ℓ₁ : Int, ℓ₂ : Int}

r = s : {ℓ₁ : Int, ℓ₂ : Int}, because ℓ₀ is not accessible in contexts of type {ℓ₁ : Int, ℓ₂ : Int}

r = s : {ℓ₁ : Int} as before, which now follows from {ℓ₁ : Int, ℓ₂ : Int}<:{ℓ₁ : Int}

The case of Objects

Consider the ς-terms, where A ≡ [ℓ₀:Int, ℓ₁:Int] (from [Abadi-Cardelli 96]):

a ≡ [ℓ₀ = ς(x^A₀ )1, ℓ₁ = ς(x^A₁ )1]

b ≡ [ℓ₀ = ς(x^A₀ )1, ℓ₁ = ς(x^A₁ )x.ℓ₀]

6⊢ a = b : A because they are separated by x : A ⊢ (x.ℓ₀ ⇐ ς(y^A)0).ℓ₁ : Int

⊢ a = b : [ℓ₀:Int] in first order theories and extensions

6⊢ a = b : [ℓ₁:Int], but they can be consistently equated [Gordon-Rees 96]

Logical Semantics

The logical meaning of any a is defined as:

[[a]]^L = the set of predicates σ such that a |= σ.

Since equality:

a = b : A

is modeled by identity of meanings, and it depends on the type A, the logical mening should depend on types:

[[a : A]]^L = the set of predicates σ making sense of A s.t. a |= σ.

To formalize the idea of “making sense of A” we stratify predicatese into a family {L_A}_A of sets, called languages.

This is inspired to Abramsky’s Domain Logic, where the interpretation of a type A is a domain isomorphic to filter space generated by the Lindemabaum algebra (L_A,≤_A). The main difference is that there is no accepted domain theoretic interpretation of subtyping, and polymorphism was missing in the Abramsky’s work.

A Predicate Assignment System

To formalize this idea we introduce a system to derive judgments of the form:

Γ ⊢ a:A : σ

where a is a term of first order ς-calculus, A is a type, σ is a predicate and Γ = {x₁:A₁:σ₁, . . . , x_k:A_k:σ_k} is a basis.

It is a Church system and an extended Curry system at the same time: if we set Γ = {xb ₁:A₁, . . . , x_k:A_k} and Γ = {x˜ ₁:σ₁, . . . , x_k:σ_k}

and a˜ to be the type erasure of a then we expect that

Γ ⊢ a:A : σ ⇒ bΓ ⊢ a:A & ˜Γ ⊢ ˜a:σ

where the former is a derivable judgment of the (first order) typed ς-calculus, the latter is derivable in a Curry assignment system for the untyped ς-calculus.

Arrow Types

The definition of L_A is by induction over A; we give it togather with rules for introducing and eliminating type constructors and giving meaning to predicates in L_A. E.g. the

(unproblematic) case of arrow type is

σ ∈ L_A, τ ∈ L_B ⇒ σ→τ ∈ L_A→B

and rules are:

Γ, x:A:τ ⊢ a:B : σ Γ ⊢ λx^A.a:A→B : τ →σ

Γ ⊢ a:A→B : τ →σ Γ ⊢ b:A : τ Γ ⊢ a(b):B : σ

Recursive Types

If the type theory has µX.A ≃ A{X

←

σ∈ L_A{X

←

which is only apparently circular, but we need some trivial predicate ω to start with, and a rule

Γ ⊢ a:A{X

←

Γ ⊢ a:µX.A : σ

Since the type theory of the ς-calculus does not identify µX.A and A{X

←

technical reasons, we have

σ∈ L_A{X

←

and

Γ ⊢ a:A{X

←

Γ ⊢ fold(µX.A, a):µX.A : µ(σ)

Γ ⊢ a:µX.A : µ(σ)

Γ ⊢ unfold(a):A{X

←

Record Types

The ς-calculus has not record types. Let us introduce them to explain our subsequent choices; fix A ≡ {ℓ_i:B_i ^{(i ∈ I)}} then:

σ ∈ L_Bj, j ∈ I ⇒ {ℓ_j:σ} ∈ L_A

Then assignment rules are

Γ ⊢ {ℓb _i:=b_i ^{(i ∈ I)}}:A Γ ⊢ b_j:B_j: σ

(j ∈ I) Γ ⊢ {ℓ_i:=b_i ^{(i ∈ I)}}:A : {ℓ_j:σ}

Γ ⊢ a:A : {ℓ_j:σ}

(j ∈ I) Γ ⊢ a.ℓ_j:B_j: σ

Object Types: introduction and elimination

If we had recursive terms, we would stipulate (like [Abramsky]):

Γ, x:A:σ ⊢ a:A : τ Γ ⊢ fixx.a:A : σ Γ ⊢ fixx.a:A : τ

Objects are either some kind of recursive records, or records whose field selection is a form of self application [Kamin, Abbadi-Cardelli], hence involving recursion; therefore if

A ≡ [ℓ_i:B_i ^{(i ∈ I)}] then

σ→τ ∈ L_Bj, j ∈ I ⇒ hℓ_j:σ→τ i ∈ L_A,

and rules

Γ, x_i:A:σ_i ⊢ b_i:B_i: τ_i (∀i ∈ I)

(j ∈ I) Γ ⊢ [ℓ_i = ς(x^A_i )b_i ^{(i ∈ I)}]:A : hℓ_j:σ_j→τ_ji

Γ ⊢ a:A : hℓ_j:σ→τ i Γ ⊢ a:A : σ Γ ⊢ a.ℓ_j:B_j : τ

In the introduction rule we check the self variables x_i against the precodnitions σ_i; in the elimination rule the object a is required to satify σ to derive the post-condition τ of a.ℓ_j.

Object types: overriding

Bacuse of the previous treatment of object predicates, we can handle method overriding as if it were plain record updating:

Γ ⊢ a:A : σ Γ, y:A:ρ ⊢ b:B_j: τ Γ ⊢ (a.ℓ_j

↼ ↽

Γ ⊢ a:A : hℓ_j:σi Γ, y:A:ρ ⊢ b:B_i: τ

(i 6= j) Γ ⊢ (a.ℓ_i

↼ ↽

Note that these are essentially rules for record updating.

Logical Rules

Over predicates in L = S

A L_A it is defined a notion of implication, σ ≤ τ which is indeed a preorder relation, where:

σ ≤ ω for any σ,

σ

∧

σ ≤ τ ⇒ µ(σ) ≤ µ(τ ), hℓ : σi ≤ hℓ : τ i.

Note that → is not the adjoint of

∧

Languages are clsed under ω and intersection, but not under ≤: this is just a technical choice.

ω ∈ L_A and σ, τ ∈ L_A ⇒ σ

∧

Rules:

Γ ⊢ a:Ab Γ ⊢ a:A : ω

Γ ⊢ a:A : σ Γ ⊢ a:A : τ Γ ⊢ a:A : σ

∧

An example

Let O,E ∈ LInt represent the properties of being odd and even integer respectively; then we can derive of b ≡ [ℓ₀ = ς(x^A₀ )1, ℓ₁ = ς(x^A₁ )x.ℓ₀]

x:A:ω ⊢ 1:Int :O

x:A:hℓ₀:ω→Ei ⊢ x:A : hℓ₀:ω→Ei x:A:hℓ₀:ω→Ei ⊢ x:A : ω x:A:hℓ₀:ω→Ei ⊢ (x.ℓ₀):Int :E

⊢ b:A : hℓ₀:ω→O, ℓ₁:hℓ₀:ω→Ei→Ei

abbreviating hℓ₀:ω→Oi

∧

A AA

⊢ b:A : hℓ₀:ω→O, ℓ₁:hℓ₀:ω→Ei→Ei y:A:ω ⊢ 2:Int :E

⊢ (b.ℓ₀

↼ ↽

which is what we expected.

Subsumption

The subsumption rule now takes the form:

Γ ⊢ a:A : σ Γ ⊢ A<:Bb σ ≤ τ

(τ ∈ L_B) Γ ⊢ a:B : τ

Because of the side condition, if Γ ⊢ a:A : σ and τ ∈ L_B whenever x:B:τ ∈ Γ then σ ∈ L_A. More interesting, if ≤_A=≤↾ L_A then

[[a:A]]_E = {σ ∈ L_A | ∃Γ.bΓ = E & Γ ⊢ a:A : σ}

is a filter over (L_A,≤_A): this was the basis of a filter model for the ς-calculus without subtyping in [van Bakel-de’Liguoro 2003].

The Soundness of Logic Semantics

if E ⊢ A<:B then L_η(A) ⊑^♮ L_η(B), for any assignment η of languages to type variables consistent with the context E, where

U ⊑^♮ V ⇐⇒∀u ∈ U ∃v ∈ V. u ≤ v & ∀v ∈ V ∃u ∈ U. u ≤ v. (Egli-Milner) In particular, in case of closed record or object types A and B we have:

E ⊢ A<:B ⇒ L_A ⊇ L_B

which is quite close to what happens in the theory of behavioral subtyping [Liskov-Wing].

If Γ ⊢ A<:Bb , and Γ ⊢ a : Ab then

Γ ⊢ a:B:τ ∃σ ∈ L_A. σ ≤ τ & Γ ⊢ a:A:σ

If [[a:A]]_E = [[b:A]]_E and E ⊢ A<:B then [[a:B]]_E = [[b:B]]_E, so that E ⊢ a = b:A ⇒ [[a:A]]_E = [[b:A]]_E (soundness).

Computational Adequacy

Let a ⇓ v mean “a evaluates to the value v”, and a ⇓ that a ⇓ v for some v; we say that a and b are observationally equivalent, a ≃^O_A b if

∀ground type K,context c[_],value v. ⊢ v:K & _ : A ⊢ c[_] : K ⇒ (c[a] ⇓ v⇐⇒c[b] ⇓ v)

Adequacy Theorem

For any closed a of type A, a ⇓ if and only if there exists σ ∈ L_A such that ω 6≤ σ (i.e. σ is a non trivial predicate) and ⊢ a:A : σ is derivable.

From this it follows that [[a:A]]_E = [[b:A]]_E implies a ≃^O_A b.

Discussion

Recall that, given A ≡ [ℓ₀:Int, ℓ₁:Int],

a ≡ [ℓ₀ = ς(x^A₀ )1, ℓ₁ = ς(x^A₁ )1]

b ≡ [ℓ₀ = ς(x^A₀ )1, ℓ₁ = ς(x^A₁ )x.ℓ₀]

which both have type A. Then we have

⊢ a:A : hℓ₁:ω→1i is derivable while the best we can say about b is

⊢ b:A : hℓ₁:hℓ₀:ω→1i→1i, hence [[a:A]] 6= [[b:A]] as it should be;

we have [[a:[ℓ₀:Int]]] = [[b:[ℓ₀:Int]]]: indeed ⊢ a = b : [ℓ₀:Int] is derivable in the ς-calculus equational theory;

since hℓ₁:ω→1i ∈ L_[ℓ

1:Int], we also have [[a:[ℓ₁:Int]]] 6= [[b:[ℓ₁:Int]]], which is however sound: we get the desired equality by adding:

I ∩ J = ∅, A ≡ [ℓ_i:B_i ^i∈I∪J], A^′ ≡ [ℓ_i:B_i ^i∈J], hℓ : τ →ρi ∈ L_A′ : Γ ⊢ a:A : hℓ : hℓ_i:σ_i ^i∈Ii

∧

Γ ⊢ a:A^′: hℓ:τ →ρi

Conclusions and further work

We have obtained so far:

a system which seems to combine nicely the type theory and the logic of a relatively complex calculus, involving functional, recursive and object types, by means of

simple tools (the logic is a propositional calculus; type reconstruction and assignment semi-algorithms can be devised in an integrated fashion);

it gives a syntactic characterization of relevant computational properties (like convergence), and concrete denotational model (a filter model in the sense of [Barendregt-Coppo-Dezani] and Abramsky’s Domain Logic, addressing the new theme of polymorphism in that setting.

It seems worthy to work out:

an extension of the system including second order types and bounded quantification;

a proper treatment of the store and other imperative features;

a systematic comparison with Hoare-style logics, like Abadi-Leino logic for object calculi, as well as behavioral subtyping;

whether authomatic tools can be devised to perform abstract interpretation at type checking time based on the proposed system.

References

Subtyping semantics:

K. B. Bruce, J. C. Mitchell, “PER models of subtyping, recursive types and higher-order polymorphism”, 1992

V. Breazu-Tannen, T. Coquand, C. A. Gunter, A. Scedrov, “Inheritance as implicit coercion”, 1991

Object calculi:

M. Abadi, L. Cardelli, A Theory of Objects, 1996 Logical semantics:

H. P. Barendregt, M. Coppo, M. Dezani, “A Filter Lambda Model and the Completeness of Type Assignment”, 1983

S. Abramsky, “Domain Theory in Logical Form”, 1991 Previous work by the authors

U. de’Liguoro, “Subtyping in logical form”, 2002

S. van Bakel, U. de’Liguoro, “Logical Semantics of the First Order Sigma-Calculus”, 2003