RELATED WORK AND CONCLUSION

PP(D,matche₀with{p1⇒ e1,. . . , pn⇒ en})

For every expression e and environment D, the set PP(D, e) is an equivalence class of pairs modulo renaming of the type variables in a pair.

LEMMA 9.12. For every expression e and environment D, ifhA, vi ∈ PP(D, e), then

(1) Dom( A)= (FV(e) − Dom(D)) ∪ FVR(D|FV(e)), and

(2) hA⁰, v⁰i ∈ PP(D, e) if and only if there is a bijection s : Tv → Tv such that s( A)= A⁰and s(v)= v⁰.

PROOF. By induction on Definition 9.11.

Indeed Definition 9.11 specifies an inference algorithm: to perform type infer-ence on an expression e with respect to the environment D simply follow the def-inition of PP(D, e), choosing fresh type variables and using the≤2-satisfaction, Lub_≤2-satisfaction, and PAT algorithms as necessary.

THEOREM 9.13. (Soundness and completeness of PP for`Loc,Rec,Con

∧2 ). For ev-ery expression e and environment D:

(Soundness). IfhA, vi ∈ PP(D, e), then D; A `Loc,Rec,Con

∧2 e : v.

(Completeness). If D; A⁰ `Loc,Rec,Con

∧2 e : v⁰, then there are a pair hA, vi ∈ PP(D, e) and a substitution s such that A⁰≤1s( A) and s(v)≤2v⁰.

PROOF. See Appendix A.3.

10. RELATED WORK AND CONCLUSION

The literature related to the present work has been partially quoted through the paper. We add here a brief survey on inference algorithms for systems involving intersection types.

The system of intersection types [Coppo and Dezani-Ciancaglini 1980; Coppo 1980; Coppo et al. 1981; Barendregt et al. 1983] is undecidable. A first approach for designing a (semi-)algorithm for finding a principal pair is that of splitting the problem in two parts: first find a normal form for the term being typed (this problem is undecidable) and then build a principal pair for the normal form (this problem is decidable). To show that the approach is sound it is necessary to prove that both the normal form and the original term have the same typings.

This approach has been followed, for instance, by Coppo et al. [1980], Ronchi della Rocca and Venneri [1984], and van Bakel [1993].

The first unification-based approach to intersection type inference was pro-posed by Ronchi della Rocca [1988] where, in particular, a decidable restriction which bounds the height of types is presented. More recently, Kfoury and Wells [1999] presented a simpler unification-based approach using a novel form of unification, calledβ-unification.

In spite of the fact that System F [Girard 1972; Reynolds 1974] and its finite rank restrictions above 3 have neither principal typings nor decidable type in-ference [Wells 1994; Kfoury and Wells 1994], combining intersection types and universal quantification results in a system with principal typings [Margaria and Zacchi 1995]. Moreover, decidable restrictions of the combined system have been developed (e.g. [Damiani and Giannini 1994; Coppo and Giannini 1995;

Jim 2000]).

Due to the expressive power of the corresponding type systems, the inference algorithms mentioned above are inherently quite expensive. More efficient in-ference algorithms can be developed by considering the rank 2 restriction of intersection types [Leivant 1983; van Bakel 1993; Yokouchi 1995; Jim 1996].

Following this line of research, in the present paper we have proposed a sound and complete principal pair inference algorithm for a rank 2 intersection type system with new typing rules for assigning rank 2 types to:

(1) local definitions, by using the principal pair property of the system to asso-ciate a different instance of the principal typing to each occurrence of the locally defined identifier;

(2) mutually recursive definitions, by allowing a restricted form of polymorphic recursion (as explained in Section 6, this rule is a slight improvement of a rule proposed by Jim [1996, 1995]);

(3) conditional expressions, by restricting the use of intersection in the types assigned to the branches in order to preserve the principal pair property.

Both the techniques for local definitions and recursive definitions do not depend on the particulars of rank 2 intersection typing, but apply to any system with principal pairs. The technique for conditional expressions, instead, is tailored to rank 2 intersection types. However, the strategy of introducing metrics on types to limit the use of the intersection type constructor in the types assigned to the branches of the conditionals expressions might also be useful for other type systems.

APPENDIX

A.1 An Extension of Jim’s Subtype Satisfaction Algorithm (Theorem 9.2)

We say that two≤_∀2,1-satisfaction problems are equivalent if they have the same solutions.

A unification problem is a ≤_∀2,1-satisfaction problem that involves only equalities.⁴⁰

40A unification problem can be solved by Robinsons’s algorithm (see, for instance, Chapter 3 of Hindley [1997]), which can decide whether it is solvable, and, if so, return a most general solution.

The following lemma implies Theorem 9.2.

LEMMA A.1. Every≤∀2,1-satisfaction problem is equivalent to a unification problem. In particular, there is an algorithm that, given a≤∀2,1-satisfaction prob-lem, either proves that it cannot be satisfied or transforms it into an equivalent unification problem.

PROOF. Following Jim [1996, 1995], we prove the lemma by providing the transformation algorithm. We first introduce a set of transformation rules of the form

t≤ ui ⇒ ∃−→α .P (where t ∈ T2∪ T_∀2).

Each rule transforms an inequality in a≤∀2,1-satisfaction problem. The trans-formation rules are in Figure 13. Note that, for each transtrans-formation rule t ≤ ui ⇒ ∃−→α .P, we have that

FTV(t)∪ FTV(ui) = FTV(∃−→α .P). (4) In particular, the type variables −→α are either fresh type variables introduced by the transformation rule (i.e., they do not appear in the left-hand side) or are the bound variables of t (when t∈ T∀2).

The transformation algorithm is specified as a rewrite relation on problems,

=⇒, defined by the rule:

(=⇒) vs≤ ui ⇒ ∃−→α .P

∃−→β .(P⁰] {vs ≤ ui}) =⇒ ∃−→β ] −→α .(P⁰∪ P)

where the operator “]” denotes disjoint union (this implies that the variables

−→α must be fresh).

To see that the rewriting relation=⇒ describes an algorithm which proves the lemma, observe that:

(1) every rewriting step (corresponding to the application of one of the rules in Figure 13) transforms a ≤_∀2,1-satisfaction problem into another ≤_∀2,1 -satisfaction problem,

(2) every rewriting step preserves the set of solutions (note that the condition (4) above is necessary to ensure this preservation),

(3) every inequality matches the left-hand side of at most one rule, and (4) repeated application of these rules must terminate.⁴¹ This is proved by

defining a metric| · | on problems for which each rewriting step is strictly decreasing. The size of inequalities will be defined by structural induction.

By point (3), it is sufficient to consider the cases given by the left-hand sides of the rules in Figure 13. For the base case we set |u0 ≤ u| = 1.

Every other case is simply defined so that the size of the left-hand side of a rule is greater than the sum of the of the inequalities appearing on the corresponding right-hand side. For example, define

—|(ui → v) ≤ α| = |α1≤ ui| + |v ≤ α2| + 1,

—|(ui → v) ≤ (u1→ u2)| = |u1≤ ui| + |v ≤ u2| + 1,

41In the original termination proof given in Jim [1996, 1995] there is an error. Here we are following the termination proof given in Jim [2000].

Fig. 13. Transformation rules for≤∀2,1-satisfaction.

—|t ≤ (u1∧ · · · ∧ un)| = |t ≤ u1| + · · · + |t ≤ un| + 1, and

—|(∀−→α .v) ≤ u| = |v ≤ u| + 1.

The function|·| is defined by structural induction (since types on right-hand sides either appear as syntactic subtypes on left-hand sides, or are type variables) and, by construction, gives a decreasing metric on problems.

Normal forms are either unification problems (i.e. do not contain inequalities) or contain at least an inequality of the form ui→ v ≤ u0where u0is a simple type which is neither a type variable nor an arrow type (such an inequality is clearly not satisfiable).

Remark A.2. (Comparison with Jim’s subtype satisfaction algorithm).

Lemma A.1 and Theorem 9.2 are a slight extension of results presented by Jim [1996, 1995]. The main differences are in the transformation rules. The transformation rules in Figure 13 either produce a unification problem or a satisfaction problem which is clearly not satisfiable. The transformation rules in Jim [1996, 1995], instead, always produce a unification problem. This dif-ference is due to the richer set of types handled by our rules⁴²: if we restrict ourselves to the set of types considered in Jim [1996, 1995] the rules in Figure 13 always produce a unification problem.

A.2 A Lub Satisfaction Algorithm (Theorem 9.7)

We say that a Lub_≤2-satisfaction problem and a≤_∀2,1-satisfaction problem are equivalent if they have the same solutions.

A Lub_≤2-satisfaction problemh j, {v1,. . . , vn}i is binary if n = 2. The following lemma implies Theorem 9.7 restricted to binary Lub_≤2-satisfaction problems.

LEMMA A.3. Every binary Lub_≤2-satisfaction problem is equivalent to a

≤_∀2,1-satisfaction problem. In particular, there is an algorithm that, given a Lub_≤2-satisfaction problem transforms it into an equivalent≤_∀2,1-problem.

42The rules in Jim [1996, 1995] consider only type variables, arrow types, and top-level conjunctions.

We also consider parametric datatypes.

Fig. 14. Transformation algorithm for binary Lub_≤2-satisfaction.

PROOF. We prove the lemma by providing the transformation algorithm. The transformation algorithm is specified as a recursive function TA defined by the clauses in Figure 14.

To show that the recursive function TA describes an algorithm that proves the lemma, for every binary Lub_≤2-satisfaction problem h j, {v1, v2}i we will prove that:

(1) TA( j, v₁, v₂) is terminating and returns a≤∀2,1-satisfaction problem, (2) FTV(TA( j, v₁, v₂))⊆ FTV({v1, v₂}), and

(3) the transformation preserves the set of solutions (i.e. h j, {v1, v₂}i and TA( j, v1, v2) are equivalent).

Points (1) and (2) are straightforward, so we consider only point (3). The proof is by induction on j ∈ {0, . . . , Max{Ind^→(v₁), Ind^→(v₂)}}.

j = 0. From the definition of TA (see Figure 14) we have TA(0, v1, v2)= ∃α.P, whereα is fresh and P = {v1≤ α, v2≤ α}.

— If s is a solution of h0, {v1, v₂}i then Ind^∧(Lub_≤2(s(v₁), s(v₂))) = 0, which implies s(v₁)= s(v2)∈ T0. So s is a solution of∃α.P.

— If s is a solution of ∃α.P then s(v1) = s(v2) ∈ T0, which implies Ind^∧(Lub_≤2(s(v₁), s(v₂)))= 0. So s is a solution of h0, {v1, v₂}i.

j > 0. By definition of Lub_≤2-satisfaction problem we have j ≤ Max{Ind^→(v₁), Ind^→(v₂)}}, so at least one of v1and v₂is an arrow type.

— If they are both arrow types, say v₁ = ui1 → v₁⁰ and v₁ = ui2 → v₂⁰, then TA( j, ui₁ → v⁰₁, ui₂ → v⁰₂) = TA( j − 1, v⁰₁, v⁰₂). By definition of Lub_≤2 we have that, for every substitution s, Lub_≤2(s(v1), s(v2))= s(ui1)∧ s(ui2)→ Lub_≤2(s(v⁰₁), s(v₂⁰)). Soh j, {v1, v2}i and h j − 1, {v₁⁰, v₂⁰}i are equivalent, and the result follows by induction.

— If v1is a type variableα and v2= ui → v, for some v = ui1→ · · · → uim→ u (m≥ 0) with u ∈ T0such that u is not an arrow type andα 6∈ FTV(u) (the symmetric case is similar), then TA( j,α, ui → v) = ∃α1α2] −→β .({α = α1→

Fig. 15. Transformation algorithm for n-ary Lub_≤2-satisfaction.

α2}∪ P), where α1,α2are fresh type variables, and∃−→β .P = TA( j −1, [α :=

α1 → α2]v,α2). We now prove thath j, {α, ui → v}i and ∃α1α2] −→β .({α = α1→ α2} ∪ P) are equivalent.

— By definition of Lub_≤2 we have that every solution s ofh j, {α, ui → v}i is such that s(α) = u1 → u2 and Ind^∧(Lub_≤2(s(α), s(ui → v))) ≤ j . So s = s⁰◦[α := α1 → α2] for some fresh type variables α1,α2 and substitution s⁰ such that s⁰(γ ) = s(γ ) for every γ 6∈ {α1,α2} and s⁰ is a solution of h j − 1, {[α := α1 → α2]v,α2}i. By induction s⁰ is a solution to∃−→β .P = TA( j − 1, [α := α1→ α2]v,α2), so s is a solution to

∃α1α2] −→β .({α = α1→ α2} ∪ P).

— If s is a solution to∃α1α2] −→β .({α = α1 → α2} ∪ P), then s = s⁰◦[α :=

α1→ α2], for some substitution s⁰such that s⁰(γ ) = s(γ ) for every γ 6∈

{α1,α2} and s⁰is a solution of∃−→β .P = TA( j − 1, [α := α1→ α2]v,α2).

By induction s⁰ is a solution toh j − 1, {[α := α1→ α2]v,α2}i, so s is a solution toh j, {α, ui → v}i.

— Otherwise h j, {v1, v2}i has no solutions and is, therefore, equivalent to

∃².{int=bool}.

The following lemma generalizes LemmaA.3 to n-ary Lub_≤2-satisfaction problems, and so implies Theorem 9.7.

LEMMA A.4. Every Lub_≤2-satisfaction problem is equivalent to a ≤_∀2,1 -satisfaction problem. In particular, there is an algorithm that, given a Lub_≤2 -satisfaction problem transforms it into an equivalent≤_∀2,1-problem.

PROOF. We prove the lemma by providing the transformation algorithm.

The transformation algorithm is specified as a recursive function TAⁿdefined by the clauses in Figure 15, that generalizes the function TA in Figure 14 to an arbitrary number of arguments.

To show that the recursive function TAⁿdescribes an algorithm that proves the lemma, for every n-ary (n≥ 1) Lub_≤2-satisfaction problemh j, {v1,. . . , vn}i

we will prove that, if j ≤ Ind^→(v1) then⁴³

(1) TAⁿ( j, v₁,. . . , vn) is terminating and returns a≤_∀2,1-satisfaction problem, (2) FTV(TAⁿ( j, v₁,. . . , vn))⊆ FTV({v1,. . . , vn}), and

(3) the transformation preserves the set of solutions (i.e. h j, {v1,. . . , vn}i and TAⁿ( j, v₁,. . . , vn) are equivalent).

Points (1) and (2) are straightforward, so we consider only point (3). The proof is by induction on n.

n= 1. Every substitution s is a solution to h j, {v1}i. Therefore, h j, {v1}i and ∃².∅

are equivalent.

n> 1. By induction h j, {v1,. . . , vn−1}i and TAⁿ⁻¹( j, v₁,. . . , vn−1) are equivalent.

Therefore, if TAⁿ⁻¹( j, v1,. . . , vn−1) has no solutions, thenh j, {v1,. . . , vn}i and

∃².{int = bool} are equivalent (they both have no solutions). Assume that TAⁿ⁻¹( j, v₁,. . . , vn−1) = ∃−→α .P has solutions. For all s ∈ MGS(∃−→α .P) we have that, by Lemma A.3,

h j, Lubⁿ_≤⁻¹₂ (s(v₁),. . . , s(vn−1)), s(v_n)i and TA( j, Lubⁿ_≤⁻¹₂ (s(v₁),. . . , s(vn−1)), s(v_n)) are equivalent. Let TA( j, Lubⁿ⁻¹_≤

2 (s(v₁),. . . , s(vn−1)), s(v_n)) = ∃−→β .P⁰ and −→γ = FTVR(s) − (−→α ] −→β ). We now prove that h j, {v1,. . . , vn}i and

∃−→α ] −→β ] −→γ .(P ∪ P⁰) are equivalent.

— If s⁰ is a solution to h j, {v1,. . . , vn}i then it is a solution of h j, {v1,. . . , vn−1}i. So there is s ∈ MGS(∃−→α .P) such that s ≤ s⁰ and FTV(v_n) ∩ FTVR(s) = ∅. Since s is idempotent, s⁰ is a solution to TA( j, Lubⁿ_≤⁻¹₂ (s(v₁),. . . , s(vn−1)), s(v_n))= ∃−→β .P⁰. Therefore, s⁰is also a so-lution to∃−→α ] −→β ] −→γ .(P ∪ P⁰).

— If s⁰ is a solution to∃−→α ] −→β ] −→γ .(P ∪ P⁰), then s⁰ is a solution to both h j, {v1,. . . , vn−1}i and h j, {Lubⁿ_≤⁻¹₂ (s(v1),. . . , s(vn−1)), s(vn)}i, for some s ∈ MGS(∃−→α .P) such that FTV(vn)∩ FTVR(s) = ∅. Therefore, since s ≤ s⁰ and s is idempotent, Ind^∧(Lubⁿ_≤2(s⁰(v1),. . . , s⁰(vn)))≤ j . s⁰is a solution to h j, {v1,. . . , vn}i.

A.3 Soundness and Completeness of the Inference Algorithm for`Loc, Rec, Con

∧2 (Theorem 9.13)

Let `<sup>sd</sup><sub>∧2</sub> be the syntax directed restriction of`Loc,Rec,Con

∧2 obtained by removing rule (SUB) and by replacing the rules (IFI) and (MATCHI) by the following rules:

(IFISD)

D; A` e0:bool D; A<sub>1</sub>` e1: v₁ D; A₂` e2: v₂ v= Lub≤2(v₁, v₂)

Ind^∧(v)≤ Max{ Min{Ind^→(v⁰₁)| D; A⁰₁` e1: v<sub>1</sub><sup>0</sup>}, Min{Ind<sup>→</sup>(v<sup>0</sup><sub>2</sub>)| D; A<sup>0</sup><sub>2</sub>` e2: v₂⁰} } D; A+ A1+ A2`ife₀thene₁elsee₂: v

43By definition of Lub_≤2-satisfaction problem we have 0≤ j ≤ Max{Ind^→(v1),. . . , Ind^→(vn)}. The condition j ≤ Ind^→(v1) is necessary to ensure that, for every k ∈ {1, . . . , n}, h j, {v1,. . . , vk}i is a Lub_≤2-satisfaction problem (i.e. 0≤ j ≤ Max{Ind^→(v1),. . . , Ind^→(vk)}).

(MATCHISD) Indeed, system`<sup>sd</sup><sub>∧2</sub>is as powerful as system`Loc,Rec,Con

∧2 , as shown by the follow-ing lemma.

LEMMA A.5. (System`<sup>sd</sup><sub>∧2</sub>is as powerful as system`Loc,Rec,Con

∧2 ). For every ex-pression e and environment D, if D; A`Loc,Rec,Con

∧2 e : v, then D; A⁰ `^sd_∧2 e : v⁰for

The result can be proved by showing that (the proof is by structural induction on`Loc,Rec,Con

∧2 derivations), for every expression e, environment D, and environ-ment D⁰, such that D⁰ ≤2 D, if D; A`Loc,Rec,Con

∧2 e : v, then D⁰; A⁰ `^sd_∧2 e : v⁰ for some A⁰and v⁰such that A≤1 A⁰and v⁰≤2v.

By Lemma A.5, we have that Theorem 9.13 (Soundness and completeness of PP for`Loc,Rec,Con

∧2 ) is implied by the following result.

LEMMA A.6. (Soundness and completeness of PP for`^sd_∧2). For every expres-sion e and environment D:

(Soundness). IfhA, vi ∈ PP(D, e), then D; A `^sd_∧2 e : v.

(Completeness). If D; A⁰`^sd_∧2 e : v⁰, then there are a pairhA, vi ∈ PP(D, e) and a substitution s such that A⁰= s(A) and s(v) = v⁰.

PROOF. Both soundness and completeness by structural induction on e.

44Observe that

— v₁≤2v₂implies FTV(v₁)⊆ FTV(v2), and

— A₂≤1A₁implies FTV( A₂)⊇ FTV(A1).

e= x.

(Soundness). We have to consider three cases.

— If x : ∀−→α .hA0, v₀i ∈ D, then hs(A0), s(v₀)i ∈ PP(D, x), for some fresh renaming s of −→α . We have D; s(A0)`^sd_∧2 x : s(v0) by rule (IDlocal).

— If x :∀−→α .v ∈ D, use rule (IDglobal).

— If x6∈ Dom(D), use rule (IDundefined).

(Completeness). Again, we have to consider three cases.

— If x : ∀−→α .hA0, v₀i ∈ D, then the last (and only) rule applied must be (I_Dlocal).

— If x :∀−→α .v ∈ D, the last (and only) rule applied must be (IDglobal).

— If x6∈ Dom(D), the last (and only) rule applied must be (IDundefined).

In all the three cases the proof is immediate.

e= c.

(Soundness). Use rule (CONST).

(Completeness). Immediate, since the last (and only) rule applied must be (CONST).

e= λx.e0.

(Soundness). We have to consider two cases.

— If x∈ FV(e0), thenhA, x⁰: ui, v₀i ∈ PP(D, e0[x := x⁰]) andhA, ui → v0i ∈ PP(D,λ x.e0). By induction, D; A, x⁰: ui`^sd_∧2 e₀[x := x⁰] : v₀, and by rule (ABS) we get:

D; A`^sd_∧2 λx.e0: ui→ v0.

— If x 6∈ FV(e0), thenhA, v0i ∈ PP(D, e0) andhA, α → v0i ∈ PP(D, λ x.e0) for some fresh type variableα. By induction, D; A `^sd_∧2 e₀: v₀, and by rule (ABSVAC) we get:

D; A`^sd_∧2 λx.e0:α → v0. (Completeness). Again, we have to consider two cases.

— If x ∈ FV(e0), then the last rule applied must be (ABS). We have v⁰ = ui⁰→ v₀⁰ and D; A⁰, x⁰: ui⁰`^sd_∧2 e₀[x := x⁰] : v₀⁰. By induction there exist a fresh pairh(A, x⁰: ui), v₀i ∈ PP(D, e0[x := x⁰]) and a substitution s such that

A⁰, x⁰: ui⁰= s(A, x⁰: ui) and s(v0)= v⁰0.

SohA, ui → v0i ∈ PP(D, λ x.e0) and s are the desired pair and substitu-tion.

— If x 6∈ FV(e0), then the last rule applied must be (ABSVAC). We have v⁰= u → v₀⁰ and D; A⁰ `^sd_∧2 e₀: v₀⁰. By induction there exist a fresh pair hA, v0i ∈ PP(D, e0) and a substitution s such that

A⁰= s(A) and s(v0)= v₀⁰.

SohA, α → v0i ∈ PP(D, λ x.e0), where α is a fresh type variable, and [α := u] ◦ s are the desired pair and substitution.

e= e0e1.

(Soundness). We havehA0, v0i ∈ PP(D, e0) and, by induction, D; A0`^sd_∧2 e0: v0.

— If v0 is a type variable α, then we must have a fresh pair hA1, v1i ∈ PP(D, e₁), A= s(A0+ A1) and v= s(α2), where s∈ MGS(∃².{v1≤ α1, α = α1→ α2} for fresh type variables α1andα2. By induction, D; A₁`^sd_∧2 e₁: v₁. By substitutivity

D; s( A₀)`<sup>sd</sup><sub>∧2</sub> e<sub>0</sub>: s(α), and D; s( A1)`^sd_∧2 e1: s(v1).

Then, by rule (APP), we have:

D; s( A0+ A1)`^sd_∧2 e0e1: s(α2).

— If v₀ = u1 ∧ · · · ∧ un → v⁰, then we must have fresh pairs hAi, v_ii ∈ PP(D, e₁) (for all i ∈ {1, . . . , n}), s ∈ MGS(∃².{vi ≤ ui | i ∈ {1, . . . , n}}, A= s(A0+ A1+ · · · + An), and v= s(v⁰). By induction and substitutivity

D; s( A₀)`<sup>sd</sup><sub>∧2</sub> e<sub>0</sub>: s(u<sub>1</sub>∧ · · · ∧ un→ v<sup>0</sup>), and D; s( A1)`^sd_∧2 ei : s(vi) (for all i∈ {1, . . . , n}).

Then, by rule (APP), we have:

D; s( A₀+ A1+ · · · + An)`^sd_∧2 e₀e₁: s(v⁰).

(Completeness). The last rule applied must be (APP). We have D; A⁰₀ `<sup>sd</sup><sub>∧2</sub> e<sub>0</sub> : u<sup>0</sup><sub>1</sub>∧ · · · ∧ u<sup>0</sup>n→ v<sup>0</sup>, D; A<sup>0</sup><sub>i</sub> `^sd_∧2 e₁ : u⁰_i (∀i ∈ {1, . . . , n}), and A⁰ = A⁰₀+ A⁰₁+ · · · + A⁰n. By induction both PP(D, e₀) and PP(D, e₁) are not empty and, by Lemma 9.12.(2), it is enough to consider the following two cases on the structure of the pairshA0, v0i ∈ PP(D, e0).

— v0= α (a type variable). By induction there exists a substitution s0such that

A⁰₀= s0( A0) and s0(α) = u⁰₁∧ · · · ∧ u⁰_n→ v⁰.

By definition of substitution, s0(α) ∈ T0, so we have that n= 1 and v⁰= u for some u∈ T0.

By induction and Lemma 9.12.(2) there is a fresh pair hA1, v₁i ∈ PP(D, e₁) and a substitution s₁such that

A⁰₁= s1( A₁) and s₁(v₁)= u⁰₁.

Let P = {v1≤ α1, α = α1→ α2}, where α1,α2are fresh. The substitution s⁰ = s0◦s1◦{α1 := u⁰₁,α2 := u} is a solution of the satisfaction problem

∃².P and is such that

A⁰= s0( A₀)+ s1( A₁)= s⁰( A₀+ A1), and s⁰(α2)= u = v⁰.

So there is s∈ MGS(∃².P) such that

hs(A0+ A1), s(α2)i ∈ PP(D, e0e1) and s≤ s⁰.

— v0= u1∧ · · · ∧ um → v. By induction there exists a substitution s0such that

A⁰₀= s0( A₀) and s₀(v)= u⁰₁∧ · · · ∧ u⁰_m→ v⁰.

By induction and Lemma 9.12.(2), for all j ∈ {1, . . . , m}, there are fresh pairshAj, v_ji ∈ PP(D, e1) and substitutions s_j such that

A⁰_j = sj( Aj) and sj(vj)= u⁰j.

Let P = {vj ≤ uj | j ∈ {1, . . . , m}}. The substitution s⁰= s0◦s1◦ · · · ◦smis a solution of the satisfaction problem∃².P and is such that A⁰= s0( A₀)+ s1( A1)+ · · · + sm( Am)= s⁰( A0+ A1+ · · · + Am), and s⁰(v)= v⁰. So there is s∈ MGS(∃².P) such that

hs(A0+ A1+ · · · + Am), s(v)i ∈ PP(D, e0e₁) and s≤ s⁰.

e=letx = e0ine₁.

(Soundness). We have fresh pairs hA0, v₀i ∈ PP(D, e0) and hA1, vi ∈ PP((D, x⁰ : ∀−→α .hA0, v₀i), e1[x := x⁰]), where −→α = FTV(A0)∪ FTV(v0). By induction, D; A₀`<sup>sd</sup><sub>∧2</sub> e<sub>0</sub>: v<sub>0</sub>and D, x<sup>0</sup>:∀−→α .hA0, v<sub>0</sub>i; A1`^sd_∧2 e₁[x := x⁰] : v₁.

— If x∈ FV(e1), then A= A1. So by rule (LETPSI) we have:⁴⁵ D; A`^sd_∧2 letx = e0ine1: v.

— If x6∈ FV(e1), then A= A1+ A0. So by rule (LETPSI) we have:

D; A`^sd_∧2 letx = e0ine₁: v.

(Completeness). The last rule applied must be (LETPSI). We have D; A⁰₀`<sup>sd</sup><sub>∧2</sub> e<sub>0</sub> : v<sub>0</sub><sup>0</sup>, Ind<sup>→</sup>(v<sub>0</sub><sup>0</sup>) = Min{Ind<sup>→</sup>(v<sup>00</sup><sub>0</sub>) | D; A<sup>00</sup><sub>0</sub> `^sd_∧2 e₀ : v⁰⁰₀}, D, x⁰ : ∀−→α .hA⁰₀, v₀⁰i;

A⁰₁`^sd_∧2 e₁[x := x⁰] : v⁰, and A⁰=

(A⁰₁, if x∈ FV(e1) A⁰₁+ A⁰₀, otherwise

Let x∈ FV(e1) (the other case is similar). By induction there are fresh pairs hA0, v0i ∈ PP(D, e0), hA1, v1i ∈ PP((D, x⁰ : ∀−→α .hA⁰₀, v₀⁰i), e1[x := x⁰]), and substitutions s0, s1, such that:

0. A⁰₀= s0( A₀) and s₀(v₀)= v₀⁰, 1. A⁰₁= s1( A₁) and s₁(v₁)= v⁰.

By point (0), there are a fresh pairhA2, vi ∈ PP((D, x⁰:∀−→α .hA0, v₀i), e1[x := x⁰]) and a substitution s₂such that:

2. A⁰₁= s2( A₂) and s₂(v)= v⁰.

SohA2, vi ∈ PP(D,letx = e0ine₁) and s₂are the desired pair and substitu-tion.

e=reci0{x1= e1,. . . , xn= en} (i0∈ {1, . . . , n}).

(Soundness). We have fresh pairshAi, vii ∈ PP(D, ei[x1:= x₁⁰]· · · [xn := xn⁰]) (for all i ∈ {1, . . . , n}), and s ∈ MGS(∃².{Gen(A1+ · · · + An, vj) ≤ uij | j ∈ { j1,. . . , jm}}), with {x⁰_j1,. . . , x⁰_jm} = {x₁⁰,. . . , x_n⁰} ∩ (Dom(A1+ · · · + An)) and

45The rule can be applied, since:

Ind^→(v0)= Min{Ind^→(v₀⁰)| D; A⁰0`^sd_∧2e0: v₀⁰} (by induction and Proposition 7.9).

A1+ · · · + An = A, x⁰_j1 : uij1,. . . , x⁰_jm : uijm. By induction and substitutivity D; s( A_i)`^sd_∧2 e_i[x₁:= x₁⁰]· · · [xn := x_n⁰] : s(v_i) (for all i∈ {1, . . . , n}). By Defini-tion 9.1, for all j ∈ { j1,. . . , jm}, s(Gen(A1+ · · · + An, v_j))≤_∀2,1s(ui_j) and, by Lemma 3.8, Gen(s( A₁+ · · · + An), s(v_j))≤∀2,1s(ui_j). Then, by rule (REC2), we have:

D; s( A)`^sd_∧2 reci0{x1= e1,. . . , xn= en} : s(vi0).

(Completeness). The last rule applied must be (REC2). We have D; A⁰_i `^sd_∧2 e_i[x₁:= x₁⁰]· · · [xn:= x_n⁰] : v_i⁰(for all i∈ {1, . . . , n}), Gen(A⁰₁+ · · · + A⁰_n, v⁰_j)≤_∀2,1 ui⁰_j (for all j ∈ { j1,. . . , jm}), with {x⁰_j1,. . . , x⁰_jm} = {x₁⁰,. . . , x_n⁰} ∩ Dom(A⁰₁+

· · · + A⁰_n) and A⁰₁+ · · · + A⁰_n= A⁰, x⁰_j1 : ui⁰_j1,. . . , x⁰_jm : ui⁰_jm.

By induction, for all i ∈ {1, . . . , n}, there are fresh pairs hAi, v_ii ∈ PP(D, e_i[x₁:= x₁⁰]· · · [xn:= xn⁰]) and substitutions s_i such that

A⁰_i = si( Ai) and si(vi)= v⁰_i.

Let A₁+· · ·+An= A, x⁰j1 : ui_j1,. . . , x⁰jm: ui_jmand P = {Gen(A1+· · ·+An, v_j)≤ ui_j | j ∈ { j1,. . . , jm}}. The substitution s⁰= s1◦ · · · ◦snis such that

A⁰= s⁰( A) and s⁰(vi0)= v⁰_i0

and is a solution of the satisfaction problem∃².P. So there is s ∈ MGS(∃².P) such that

hs(A), s(vi0)i ∈ PP(D,reci0{x1= e1,. . . , xn= en}) and s≤ s⁰.

e=ife0thene1elsee2.

(Soundness). We have fresh pairshA0, v0i ∈ PP(D, e0),hA1, v1i ∈ PP(D, e1), hA2, v2i ∈ PP(D, e2), and substitutions s0 ∈ MGS(∃².{v0 ≤ bool}), s ∈ MGS(h j, {v1, v2}i), where j = Max(Ind^→(v1), Ind^→(v2)). By induction and substitutivity

D; s0( A0)`^sd_∧2 e0: s0(v0), and

D; s( A_i)`^sd_∧2 e_i: s(v_i) (for all i∈ {1, 2}).

Then by rule (IFISD) we have⁴⁶

D; s₀( A₀)+ s(A1)+ s(A2)`<sup>sd</sup><sub>∧2</sub> ife<sub>0</sub>thene<sub>1</sub>elsee<sub>2</sub>: Lub<sub>≤2</sub>(s(v<sub>1</sub>), s(v<sub>2</sub>)). (Completeness). The last rule applied must be (IFISD). We have D; A<sup>0</sup><sub>0</sub>`^sd_∧2 e₀: bool, D; A⁰₁`<sup>sd</sup><sub>∧2</sub> e<sub>1</sub>: v<sub>1</sub><sup>0</sup>, D; A<sup>0</sup><sub>2</sub>`^sd_∧2 e₂: v⁰₂, A⁰= A⁰₀+ A⁰₁+ A⁰₂, v⁰= Lub_≤2(v⁰₁, v₂⁰), and

Ind^∧(v⁰)≤ Max{ Min{Ind^→(v₁⁰⁰)| D; A⁰⁰₁`<sup>sd</sup><sub>∧2</sub> e1: v<sup>00</sup><sub>1</sub>}, Min{Ind<sup>→</sup>(v<sub>2</sub><sup>00</sup>)| D; A<sup>00</sup><sub>2</sub>`^sd_∧2 e₂: v⁰⁰₂} }

46The rule can be applied, since

Ind^∧(Lub_≤2(s(v₁), s(v₂)))≤ j (since s∈ MGS(h j, {v1, v2}i)), and

j = Max(Ind^→(v₁), Ind^→(v₂))

= Max{ Min{Ind^→(v⁰₁)| D; A⁰1`<sup>sd</sup><sub>∧2</sub>e1: v<sup>0</sup><sub>1</sub>}, Min{Ind<sup>→</sup>(v2)| D; A<sup>0</sup>2`^sd_∧2e2: v₂⁰} } (by induction and Proposition 7.9).

By induction there are fresh pairshA0, v0i ∈ PP(D, e0),hA1, v1i ∈ PP(D, e1), hA2, v2i ∈ PP(D, e2), and substitutions s0, s1, s2, such that:

0. A⁰₀= s0( A₀) and s₀(v₀)=bool, 1. A⁰₁= s1( A₁) and s₁(v₁)= v⁰₁, 2. A⁰₂= s2( A₂) and s₂(v₂)= v⁰₂.

Let P= {v0≤bool}. The substitution s⁰⁰= s0◦s1◦s2

— is such that

A⁰₀+ A⁰₁+ A⁰₂= s⁰⁰( A₀+ A1+ A2)), and Lub_≤2(s⁰⁰(v₁), s⁰⁰(v₂))= v⁰,

— is a solution of the≤∀2,1-satisfaction problem∃².P, and

— is a solution to the Lub_≤2-satisfaction problem h j, {v1, v2}i, where j = Max(Ind^→(v1), Ind^→(v2)).⁴⁷

So there are

— s₃∈ MGS(∃².P), and

— s∈ MGS(h j, {v1, v₂}i), such that

hs3( A0)+ s(A1)+ s(A2), Lub_≤2(s(v1), s(v2))i ∈ PP(D,ife0thene1elsee2), s⁰⁰= s⁰₃◦s3and s⁰⁰= s⁰⁰⁰◦s, for some substitutions s⁰₃, s⁰⁰⁰ such that Dom(s⁰₃)∩ Dom(s⁰⁰⁰)= ∅, FTVR(s⁰₃)∩Dom(s⁰⁰⁰)= ∅, Dom(s⁰⁰⁰)∩FTV(s⁰₃(s₃( A₀)))= ∅, and Dom(s⁰₃)∩(FTV(s(A1))∪FTV(s(A2))∪FTV(s(v1))∪s(FTV(v2)))= ∅. Therefore, s⁰= s⁰⁰⁰◦s⁰₃is such that

A⁰₀+ A⁰₁+ A⁰₂= s⁰(s3( A0)+ s(A1)+ s(A2)), and s⁰(Lub_≤2(s(v1), s(v2)))= v⁰.

e=matche₀with{p1⇒ e1,. . . , pn⇒ en}.

(Soundness). We have fresh pairshA0, v0i ∈ PP(D, e0),hUl, uli ∈ PAT(p⁰l) andhAl, vli ∈ PP(D, el⁰) (for all l ∈ {1, . . . , n}), and substitutions

s∈ MGS(∃α.{ v0≤ α} ∪ (S

1≤l≤n{ul ≤ α, uil ,1≤ ul ,1,. . . , uil ,hl ≤ ul ,hl})), s⁰ ∈ MGS(h j, {s(v1),. . . , s(vn)}i), with { yl ,1,. . . , yl ,hl} = Dom(Ul)∩ Dom(Al), Ul = Ul⁰,{ yl ,1 : ul ,1,. . . , yl ,hl : ul ,hl}, Al = Al⁰,{ yl ,1 : uil ,1,. . . , yl ,hl : uil ,hl}, α fresh type variable, and j = Max(Ind^→(s(v1)),. . . , Ind^→(s(vn))). By induc-tion and substitutivity

D; s⁰(s( A₀))`^sd_∧2 e₀: s⁰(s(v₀)),

s⁰(s(Ul))Bp⁰l : s⁰(s(ul)) and D; s⁰(s( Al))`^sd_∧2 e⁰_l : s⁰(s(vl)) (for all l ∈ {1, . . . , n}).

Then by rule (MATCHISD) we have⁴⁸

D; s⁰(s( A0+ A⁰₁+ · · · + A⁰n)`^sd_∧2 matche0with{p1⇒ e1,. . . , pn⇒ en} : Lubⁿ_≤2(s⁰(s(v₁)),. . . , s⁰(s(v_n))).

47In fact

Ind^∧(Lub_≤2(s⁰⁰(v1), s⁰⁰(v2)))= Ind^∧(v⁰)= Ind^∧(Lub_≤2(v₁⁰, v⁰₂))

≤ Max{ Min{Ind^→(v⁰⁰₁)| D; A⁰⁰1`<sup>sd</sup><sub>∧2</sub>e<sub>1</sub>: v<sub>1</sub><sup>00</sup>}, Min{Ind<sup>→</sup>(v<sub>2</sub><sup>00</sup>)| D; A<sup>00</sup>2`^sd_∧2e₂: v⁰⁰₂} }

= Max(Ind^→(v₁), Ind^→(v₂))

= j

(by induction and Proposition 7.9).

48The rule can be applied, since

Ind^∧(Lubⁿ_≤2(s⁰(s(v1)),. . . , s⁰(s(vn))))≤ j

(Completeness). The last rule applied must be (MATCHISD). We have

— is a solution of the≤∀2,1-satisfaction problem∃α.P, and

— is a solution to the Lub_≤2-satisfaction problem h j, {s(v1),. . . , s(vn)}i,

ACKNOWLEDGMENTS

I thank Mario Coppo, Mariangiola Dezani, Paola Giannini, Ines Margaria, Maddalena Zacchi, and the referees of earlier versions of this paper, for valu-able comments and suggestions. I also thank Emiliano Leporati for much use-ful feedback during the preparation of his Master thesis [Leporati 2000]. I’m particularly grateful to the TOPLAS referees for insightful and constructive comments, which greatly improved the submitted version.

REFERENCES

ADITYA, S.ANDNIKHIL, R. 1991. Incremental polymorphism. In Functional Programming Lan-guages and Computer Architecture. LNCS 523. Springer, 379–405.

BARENDREGT, H. P., COPPO, M.,ANDDEZANI-CIANCAGLINI, M. 1983. A filter lambda model and the completeness of type assignment. J. Symb. Logic 48, 931–940.

COPPO, M. 1980. An extended polymorphic type system. In Mathematical Foundations of Com-puter Science. LNCS 88. Springer, 194–204.

COPPO, M.ANDDEZANI-CIANCAGLINI, M. 1980. An extension of basic functional theory for lambda-calculus. Notre Dame J. Formal Logic 21, 4, 685–693.

COPPO, M., DEZANI-CIANCAGLINI, M.,ANDVENNERI, B. 1980. Principal Type Schemes and Lambda-calculus Semantics. In To H. B. Curry. Essays on Combinatory Logic, Lambda-Lambda-calculus and Formalism, R. Hindley and J. Seldin, Eds. Accademic Press, London, 480–490.

COPPO, M., DEZANI-CIANCAGLINI, M., ANDVENNERI, B. 1981. Functional Characters of Solvable Terms. Zeith. Math. Logik Und Grund. Math. 27, 45–58.

COPPO, M.ANDGIANNINI, P. 1995. Principal Types and Unification for Simple Intersection Types Systems. Information and Computation 122, 1, 70–96.

DAMAS, L. M. M. 1984. Type Assignment in Programming Languages. Ph.D. thesis, University of Edinburgh.

DAMAS, L. M. M.AND MILNER, R. 1982. Principal type schemas for functional programs. In POPL’82. ACM, 207–212.

DAMIANI, F. 2000. Typing local definitions and conditional expressions with rank 2 intersection.

In FOSSACS’00 (part of ETAPS’00). LNCS 1784. Springer, 82–97.

DAMIANI, F.ANDGIANNINI, P. 1994. A Decidable Intersection Type System based on Relevance. In TACS’94. LNCS 789. Springer, 707–725.

GIRARD, J. Y. 1972. Interpretation fonctionelle et elimination des coupures dans l’aritmetique d’ordre superieur. Ph.D. thesis, Universit´e Paris VII.

HENGLEIN, F. 1993. Type inference with polymorphic recursion. ACM Trans. Prog. Lang.

Syst. 15, 2, 253–289.

HINDLEY, R. 1997. Basic Simple Type Theory. Number 42 in Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, London.

JIM, T. 1995. Rank 2 type systems and recursive definitions. Tech. Rep. MIT/LCS/TM-531, LCS, Massachusetts Institute of Technology.

JIM, T. 1996. What are principal typings and what are they good for? In POPL’96. ACM, 42–53.

JIM, T. 2000. A polar type system. In ICALP Workshops. Proceedings in Informatics, vol. 8.

Carleton-Scientific, 323–338.

KFOURY, A. J., TIURYN, J.,ANDURZYCZYN, P. 1993. Type reconstruction in the presence of polymor-phic recursion. ACM Trans. Prog. Lang. Syst. 15, 2, 290–311.

KFOURY, A. J.ANDWELLS, J. B. 1994. A direct algorithm for type inference in the rank-2 fragment of the second-order lambda -calculus. In LISP and Functional Programming ’94. ACM.

KFOURY, A. J.ANDWELLS, J. B. 1999. Principality and Decidable Type Inference for Finite-Rank Intersection Types. In POPL’99. ACM, 161–174.

LEIVANT, D. 1983. Polymorphic Type Inference. In POPL’83. ACM, 88–98.

LEPORATI, E. 2000. Intersezione al rank 2 per MiniOcaml. M.S. thesis, Dipartimento di Informat-ica, Universit `a di Torino.

MARGARIA, I.ANDZACCHI, M. 1995. Principal typing in a∀∧ discipline. J. Logic Comp. 5, 367–381.

MEERTENS, L. 1983. Incremental polymorphic type checking in B. In POPL’83. ACM, 265–275.

MILNER, R., TOFTE, M., HARPER, R.,ANDMACQUEEN, D. 1997. The Definition of Standard ML -Revised. MIT Press.

MILNER, R., TOFTE, M., HARPER, R.,ANDMACQUEEN, D. 1997. The Definition of Standard ML -Revised. MIT Press.

Nel documento Definitions and Conditional Expressions (pagine 36-51)