Combining Type Disciplines
F.Cardone U. de'Liguoro M. Dezani Ciancaglini
Dedicated to Corrado Bohm on the occasion of his 70th birthday
Abstract
We present a type inference system for pure -calculus which includes, in addition to arrow types, also universal and existential type quanti ers, intersection and union types, and type recursion. The interest of this system lies in the fact that it o ers a possibility to study in a uni ed framework a wide range of type constructors. We investigate the main syntactical properties of the system, including an analysis of the preservation of types under parallel reduction strategies, leading to a form of the subject- reduction property. We describe a model for this system where types are special subsets of aD1model for-calculus, without imposing any formal contractiveness constraint on types of the kind considered for a closely related system in MacQueen, Plotkin and Sethi [17].
Introduction
Current research in the theory of programming languages has emphasized the relevance of investigating the properties of type disciplines with a suciently rich set of type constructors, in order to achieve greater exibility in the use of type annotations as descriptions of the functional behaviour of programs. One of many possible ways to meet this requirement is exempli ed by the family of higher-order, strongly typed languages patterned after the Theory of Constructions (Coquand and Huet [14]), in which a type of a program can be considered as alogical speci cation of it. Another, orthogonal, line of research consists in studying rst order type constructors more directly related to the intuition of a type as a collection of values.
From the latter viewpoint it is important to emphasize the connections between computational properties of expressions (e.g. strong normalizability, subject reduction or even strictness properties) and the possible forms of their typings. There are by now several examples in the literature which demonstrate the interest of this line of research. Theintersection types of Coppo and Dezani [12], originally introduced for studying the normalization properties of pure -terms, have been shown to characterize exactly the class of strongly normalizable -terms (Pottinger [22]). Recursive typesin which the recursion variable occurs only posistively can be assigned only to strongly normalizing terms (Mendler [18]), and interesting developments in the use of intersection types to detect strictness properties of functional programs have been found recently (Coppo and Ferrari [13]). It turns out that combinations of some of these type constructors o er an abstract environment for studying features coming from the theory and practice of programming. In particular, recent research by John Reynolds (Reynolds [24, 25]) has shown how to encode record types using intersection, and their interaction with general type recursion allows, to a certain extent, to formalize examples from object oriented programming, like that of a class of points described by the type:
Point = P:(setX : Int!P ^getX : Int):
Benjamin Pierce (Pierce [21]) has also devised the following example, showing that some real expressive power is gained whenunion types are added to intersection types. The
if
then
else
operator is such that the type NegNum_PosNum can be assigned to the termn
=if
bthen
1else
;1. To test whethern
is zero, using the function
IsZero : (NegNum!False)^(Zero!True)^(PosNum!False);
amounts to derive the typing
IsZero
n
: False:Without using union types, the best information about IsZero
n
is that it is just a boolean value. Recently, ML types have been re ned using intersection and union type constructors (Pfenning [15]). Moreover, some examples show the utility of adding intersection types to the Logical Frameworks (Pfenning [20]). In these extensions decidability of type inference (resp. type checking) is preserved by permitting only the intersection of types which are subtypes of a common ML (resp. LF) type.The form of polymorphismdescribed by universal and existential type quanti cation has been used in the description of free algebras (Bohm and Berarducci [5]) and abstract data types (Mitchell and Plotkin [19]).
More recently, Pierce and Turner have proposed an alternative approach to the embedding of some features of object-oriented programming into higher-order typed systems with existential types, in order to avoid the use of recursive types which are, instead, the main motivation to the introduction ofF-bounded quanti cation of Cook, Canning, Hill, Mitchell and Oltho [6]. In the analysis of object-oriented programming, the interaction of polymorphism and rst-order type constructors has also proved to be a exible tool, especially when a notion of subtyping is added to the system and polymorphic type constructors include bounded universal quanti cation and record types as in the languages Fun (Cardelli and Wegner [8]) and Quest (Cardelli [7]).
In this perspective, the present paper studies a type inference system which, in addition to the standard function type constructor, has intersection and union operators, type recursion and both universal and existential type quanti ers. We are interested in exploring the consequences of having a wide range of type constructors on the syntactical and semantical properties of the resulting type system. Here we give two equivalent formulations of the type system, one in a natural deduction style and the other in the form of a sequent calculus, and show the invariance of types with respect to a general notion ofparallel reduction of terms, a property which fails for ordinary -reduction of -terms. The natural deduction formulation coincides with the system introduced by MacQueen, Plotkin and Sethi [17], where, however, no proof- theoretic investigation of the system is carried out, while a semantical interpretation based on a complete metric space of ideals is presented. In the present paper we describe a new interpretation for the system, which does not require any restriction on the formation rules for types as those imposed in that approach, and is based on the approximation properties of D1 -models (Scott [26]) of which the types are taken to be particular subsets. We do not consider subtyping rules for our system, for their formalization in sequent calculus destroys the symmetry of the rules. It is this symmetry that allows us to prove a restricted form of the Haupsatz, the main technical tool used in establishing the preservation of types under parallel reduction.
Observe however that subtyping rules like those of Cardelli and Wegner [8] are satis ed by the semantical interpretation we propose, essentially because it formalizes in a natural way the intuitions on which these rules are based.
Section 1 and 2 are essentially due to the last two authors, while section 3 is essentially due to the rst author.
1 The type assignment system.
In the present section we describe the syntax of the type inference system that we shall study in the sequel.
The rules for the system are presented in two equivalent ways: the rst one is that given by [17], and is patterned after a natural deduction system of the kind considered in [23]. The second formulation is a sequent calculus in the style of [27], for which a restricted form of cut elimination will be proved in the next section.
De nition 1.1 (Types)
The set T of types is inductively de ned by
- t0;t1;:::2
T
(V
set of type variables, ranged over bys;t;:::) - !2T
(type constant)- ; )(! );(^ );(_ )2
T
- t2
V
; 2T
)t: ;8t: ;9t: 2T
.Convention
: we omit parentheses according to the precedence rule: \^and_over!".Atyping statementis an expression of the form M : , where M is a -term and a type; M is called the subjectand thepredicate of the typing statement. Abasic typing statement is a typing statement whose subject is a variable. Abasisis a set of basic typing statements such that subjects are pairwise distinct. If B is a basis, FV(B) will denote the set of free term and type variables which occur in B. B;x : will denote the basis B[fx : gwhen B is a basis such that either x62FV(B) or x : 2B.
Astatementis an expression of the form B `M : (where B is a basis and M : is a typing statement) that can be derived by the axioms and rules of De nition 1.2.
De nition 1.2 (Natural Deduction Formulation)
The axioms and rules to derive statements are:
(Ax) B;x : `x : (!) B`M : !
(!E) B`M : ! B`N :
B`MN : (!I) B;x : `M :
B`x:M : ! (I) B`M : [t:=t]
B`M : t: (E) B`M : t:
B`M : [t:=t]
(8I) B`M :
B`M :8t: if t62FV(B) (8E) B`M :8t:
B`M : [ =t]
(9I) B`M : [ =t]
B`M :9t: (9E) B;x : `M : B `N :9t:
B`M[N=x] : if t62FV(B)[FV( ) (^I) B`M : B`M :
B`M : ^ (^E) B`M : ^
B`M : B`M : ^ B`M : (_I) B `M :
B`M : _ B `M :
B `M : _ (_E) B;x : `M : B;x : `M : B `N : _ B`M[N=x] :
The admissibility of the following rules is straightforward.
(Weakening) B`M :
B;x : `M : (Strengthening) B;x : `M :
B`M : if x62FV(M):
This presentation looks familiar and intuitive, and it shares with natural deduction systems the nice property of de ning the \meaning" of type operators directly, through introduction-elimination rules.
However, if one is interested in the proof theoretical properties of the system it is useful to translate it into a sequent calculus style. To this aim we introduce a type assignment system whose rules are symmetrically introductions to the left and to the right of type constructors. Although we do this primarily for technical reasons, we think that this system is of interest on its own.
This calculus is not a pure sequent calculus since we still consider bases assetsof premises, in order both to keep the two systems as close as possible, and to avoid in the following proofs the boring treatment of structural rules. The \multiplicative" character of its rules is however a typical feature of Gentzen's original calculus that we preserve.
A sequent is an expression of the form B :; M : that can be derived by the axioms and rules of De nition 1.3.
We write B;B0 to mean B[B0, provided that this is a still a basis, i.e. x is the subject of the same basic typing statement whenever x is in FV(B) and in FV(B0).
De nition 1.3 (Sequent Calculus Formulation)
The axioms and rules to derive sequents are:
B;x : :;x : Ax B :;M : ! ! B;x : :;M : B0:;N :
B;B0;y : ! :;M[yN=x] : !L B;x : :;M :
B :;x:M : ! !R B;x : [t:=t] :;M :
B;x : t: :;M : L B :;M : [t:=t]
B :;M : t: R B;x : [=t] :;M :
B;x :8t: :;M : 8L B :;M :
B :;M :8t: 8R if t62FV(B) B;x : :;M :
B;x :9t: :;M : 9L if t62FV(B)[FV( ) B :;M : [=t]
B :;M :9t: 9R B;x : :;M :
B;x : ^ :;M : B;x : :;M :
B;x : ^ :;M : ^L B`M : B0:;M : B;B0:;M : ^ ^R B;x : :;M : B0;x : :;M :
B;B0;x : _ :;M : _L B :;M :
B :;M : _ B :;M :
B :;M : _ _R B;x : :;M : B0:;N :
B;B0:;M[N=x] : cut:
It is immediate to verify that rules (Weakening) and (Strengthening) are admissible also in the sequent formulation.
Recall that, by the notational convention just before this de nition, the set of assumptions in the conclusion of each rule has to be actually a basis, that is each term variable must occur at most once. There is no loss of generality in this restriction. In fact if B :;M : and B0 :;N : , using^L we can always build B00 and B000 such that B00 :;M : and B000:;N : , and B00;B000is a basis. More precisely B00 and B000will contain x : ^ whenever x : 2B and x : 2B0.
Notation
(i) IfDis a derivation ending with B :;M : we writeD: B :;M : .
(ii) We shall denote an arbitrary rule of the sequent calculus by Bi:;M : i
B :;N : rule
assuming that the index i will have the correct value (i.e. i=0, i=1 or i=1,2) and that the involved terms and types will t the rules as de ned in De nition 1.3.
The proof of the equivalence between the two formulations is standard.
Lemma 1.4 (Substitution Lemma)
B;x : `M : and B`N : ) B`M[N=x] : .
Proof. This can be proved as usual for Curry type systems, by induction on the derivation of B;x : `M : .
However in the present setting we can shorten the proof as follows:
(_E) B;x : :;M : B;x : :;M : (_I) B`N : B `N : _ B :;M[N=x] : :
2
Theorem 1.5 (Equivalence between
`and
:;)
For all basesB,M 2and types ,
B`M : , B :;M : .
Proof. ()) By induction on the derivation of B `M : , distinguishing cases according to the last inference.
We consider only the interesting cases, i.e. the elimination rules.
Case (!E):
(!E) B `M : ! B`N : B`MN : becomes
x : :;x : Ax ind. hyp.
B :;N :
B;y : ! :;yN : !L ind. hyp.
B `M : !
B :;MN : cut
Case ( E) where 2f;8;^g:
( E) B`M : B`M : becomes
x : :;x : Ax
x : :;x : L ind. hyp.
B`M :
B :;M : cut
Case (9E):
(9E) B;x : `M : B`9t:N : B`M[N=x] :
becomes ind. hyp.
B;x : :;M :
B;x :9t: :;M : 9L ind. hyp.
B`N :9t:
B :;M[N=x] : cut
since t62FV(B)[FV( ).
Case (_E):
(_E) B;x : `M : B;x : `M : B`N : _ B`M[N=x] :
becomes ind. hyp.
B;x : :;M : ind. hyp.
B;x : :;M :
B;x : _ :;M : _L ind. hyp.
B`N : _
B :;M[N=x] : cut .
(() Symmetrically, by induction on the derivation of B :; M : . In case of cut use the Substitution Lemma 1.4. The other non trivial cases are the left rules.
Case!L: B;x : :;M : B0:;N :
B;B0;y : ! :;M[yN=x] : !L
We can freely assume that x62FV(B0). Now by the induction hypothesis and the admissibility of weakening we have
B;B0;y : ! ;x : `M : and B;B0;y : ! `N : :
From this, by (Ax) and (!E), we get B;B0;y : ! `yN : , hence the thesis follows by the Substitution Lemma.
Case L where 2f;8;_g:
B;x : :;M : B;x : :;M : L :
We have that B;x : `M : implies B;x : `M : since each occurrence of the axiom (Ax) B;x : `x :
can be replaced by the following deduction
( E) (Ax) B;x : `x : B;x : `x : :
Case9L: B;x : :;M :
B;x :9t: :;M : 9L where t62FV(B)[FV():
By the induction hypothesis B;x : `M : , hence, if y is fresh, B;y : `M[y=x] : , being deductions independent of the names of variables. By weakening B;x :9t:;y : `M[y=x] : so we can conclude:
(9E) B;x :9t:;y : `M[y=x] : B;x :9t:`x :9t:
B;x :9t:`M : if t62FV(B)[FV( ) since M[y=x][x=y]M.
Case_L: B;x : :;M : B0;x : :;M :
B;B0;x : _ :;M : _L :
By the induction hypothesis B;x : `M : , hence, if y is fresh, B;B0;x : _ ;y : `M[y=x] : , being deductions independent of the names of variables and using weakening. Similarly, B;B0;x : _ ;y : ` M[y=x] : ; hence the thesis follows from:
(_E) B;B0;x : _ ;y : `M[y=x] : B;B0;x : _ ;y : `M[y=x] : B;B0;x : _ `x : _ B;B0;x : _ `M : :
2
2 Invariance of types under parallel reduction of subjects.
The type assignments`and :; are not invariant under -reduction of subjects. The problem is that in rule cut we lose the correspondence between subterms and subdeductions; many occurrences of the same subterm correspond infact to a unique subdeduction. For example one can deduce the type ( ! ! )^( !
! ) ! ( ! _) ! ! both for xyz:x(yz)(yz) and for xyz:x((u:u)yz)((u:u)yz), but this type cannot be deduced for xyz:x(yz)((u:u)yz) or xyz:x((u:u)yz)(yz) (Benjamin Pierce showed us this example). Analogously the type (8t:!! )!( !9t:)! ! (where t does not occur in ) can be deduced for the rst two but not for the second two -terms. Then in this system types are preserved neither under -reduction nor under -expansion. Similar examples show that types are not preserved under
-reduction.
One may ask why the second example does not provide a counterexample to the Type Preservation theorem of [19] which states the invariance of types under -reduction of subjects. Indeed Mitchell and Plotkin's calculus is a strongly typed calculus and the erasure map from typed terms to pure -terms is not onto; now it turns out that the term of type (8t: ! ! ) ! ( ! 9t:) ! ! whose erasure is
xyz:x((u:u)yz)((u:u)yz) does not reduce to any term corresponding either to xyz:x(yz)((u:u)yz) or to xyz:x((u:u)yz)(yz); on the contrary its immediate reduct corresponds to xyz:x(yz)(yz).
Invariance under -reduction is a desirable property, since it gives us the feeling that the rules in the system are, in a sense, correct. But in the present case rules 9E, _E and cut could hardly be considered
uncorrect; indeed, beside their similarity with rules of the sequent calculus in logic, they turn out to be sound e.g. with respect to the semantics we propose in section 3 of the present paper.
Instead it seems that the phenomenon we are about arises from a mismatch between the type system and the possibility of unbalanced reductions of the subject. In fact we prove the system :; to be invariant under parallel reduction, hence, by the equivalence of :; and `, the same property is established for `. More precisely types are invariant under -reductions which are done simultaneously on all occurences of the same subterm which corresponds to the same subdeduction. Since this reduction relation is co nal with the usual -reduction, we conclude that each term will have, soon or later, all the types of its expansions, which is in particular true for normal forms.
Our proof is inspired by Gentzen's proof of the Hauptsatz [27]. Following his lines we introduce the notions of rank and degree of cuts, that are used to show that the cut elimination procedure terminates. A similar but simpler proof is carried out for a sistem without ,8 and9in [2].
The main di erence between our proof and that by Gentzen lies in the fact that we do not have a normal from property (indeed in presence of the universal type and of recursive types also non strongly noramlizable terms are typable), but only a property of preservation of types under the complete development of a suitable setF of redexes (a \uniform set", see De nition 2.5).
Some technical remarks about the de nition of degree are in order. Firstly the degree of a cut is de ned to be di erent from 0 only if this cut is relative to a redex belonging to F (see De nition 2.11). Secondly union and intersection are proof functional connectives, in the sense of Lopez-Escobar [
?
]: in particular rules^R and_L require the same subject in both premises. This implies that cuts whose cut type is an arrow type have to be eliminated all together and after any other cut whose cut type has a \logical" connective as its main operator: this is the reason why arrows have a minimal degree. Finally problems arise from rules
L, R,8L and9R, since the cut elimination in general results in a cut whose cut type is more complex than the original one: this contradicts the fact that the proof has been shortened, so that the obvious solution is to make degree a function of the \history" of the type occurrence we are considering.
In each rule of the sequent calculus it is natural to distinguish between the type occurrence which has been just generated from the other ones. This can be formalized as follows.
De nition 2.1 (Fathers and Generated Types)
(i) Given any arbitrary rule
rule Bi:;M : i B :;N : we say that:
- the occurrence ofi in a premise is thefatherof the occurrence of i i (this is true in all left rules and in rulecut);
- if x : 2Bi and x : 2B with then the occurrence of is afatherof the occurrence of; - if the rule isa cut of the shape in Figure 1 then both occurrences of x : and of y : in theleft
premise are fathers of the occurrence of x : in the conclusion.
(ii) Looking at the shapes of logical rules as shown in Figure 1 we say that:
- ! is the typegenerated by!L and !R from and ; - is the typegeneratedby L and 0R from ;
- ^ is the type generatedby ^R from and ; - _ is the type generatedby _L fromand .
Clearly if i6= 0 each type either is generated or it has at least one father, the only exception being rule!L, where the generated type may have two fathers..
The standard de nition of type degree is the number of type symbols. We need a more re ned notion of type degree which depends on the structure of the derivation rather than on the syntax of the types; in particular it should give the same degree to all arrow types and distinguish between occurrences of the same non arrow type. In fact we need take to take into account the number of rules which have been used in generating the occurrence of non arrow types. This will be clari ed in remark 2.12.
^R B :;M : B0:;M :
B;B0:;M : ^ _L B;x : :;M : B0;x : :;M : B;B0;x : _ :;M :
L B;x : :;M :
B;x : :;M : 2f^;8;9;g 0R B :;M :
B :;M : 02f_;8;9;g
!L B;x : :;M : B0:;N :
B;B0;y : ! :;M[yN=x] : !R B;x : :;M : B :;x:M : ! B;x : ;y : :;M : B;x : :;x :
B;x : :;M[x=y] : cut
Figure 1: Possible shapes of logical rules.
De nition 2.2 (Degree of Type Occurrences)
The degree of an occurrence of a typein a deductionDis de ned by induction on D:
- if occurs in the conclusion of Axor! then its degree is 0;
- if occurs in the conclusion of a logical rule or of the cut and if it is not the generated type, then its degree is the maximum of the degrees of its fathers;
- if! is the type generated by!L then its degree is the maximum between the degrees of its fathers and 0:5;
- if ! is the type generated by !R then its degree is0:5;
- if ^ (_ ) is the type generated by^R (_L) fromand then its degree is the maximum of the degrees of and plus1;
- if is the type generated by L ( 2f;8;9;^g) or by 0R ( 02f;8;9;_g) from then its degree is the degree of plus1.
De nition 2.3 (Cut-type and Rank)
Given a cutcut B;x : :;M : B0:;N : B;B0:;M[N=x] : we callthe cut-type.
(i) Theleft rankof the cut is the largest number of consecutive statements in a path such that the lowest of these is the left premise of the cut and the basis of each of these statements contains x : .
(ii) Theright rank of the cut is the largest number of consecutive statements in a path such that the lowest of these statements is the right premise of the cut and is the predicate of the succedent of each of these statements.
(iii) Therankof the cut is the sum of its left and right ranks.
De nition 2.4 (Ready Cuts and Ready Derivations)
(i) Acutisready i it has rank2;
(ii) aderivationisready i it contains only ready cuts.
where is either Ax or !
B;x : ! :;x : ! B0:;M : ! ! B;B0:;M : ! cut (g)
where is any type constructor
B;x : :;x : Ax Bi:;M : i
B0:;M : R
B;B0:;M : cut
(f)
Bi :;M :
B;x : :;M : L B0;y : :;y : Ax B;B0;y : :;M[y=x] : cut (e)
B;x : :;P : B00;x : :;P :
B;B00;x : _ :;P : _L B0:;Q : B0:;Q : _ _R B;B0;B00:;P[Q=x] : cut (d)
B;x : :;P :
B;x : ^ :;P : ^L B0:;Q : B00:;Q : B0;B00:;Q : ^ ^R B;B0;B00:;P[Q=x] : cut (c)
where 2f;9;8g
B;x : :;P :
B;x : :;P : L B0:;Q : 0 B0:;Q : R B;B0:;P[Q=x] : cut (b)
B;z : :;P : B0:;R :
B;B0;x : ! :;P[xR=z] : !L B00;y : :;Q : B00:;y:Q : ! !R B;B0;B00:;P[xR=z][y:Q=x] : cut (a)
Figure 2: Possible shapes of ready cuts.
If a cut is ready either its left and right premises are respectively the conclusions of the left and right introduction rule for the principal constructor of the cut-type, or one of its premises is an axiom or an instance of rule !. Figure 2 shows all possible shapes of ready cuts.
We introduce now a notion of parallel reduction. The parallelism comes out from the fact that in each reduction step more than a single redex is contracted.
In order to formalize this idea we de ne the notion of uniform set of redex occurrences in a term.
Informallya set of redex occurrences in a term M is called uniform if, whenever it contains a redex occurrence, every other occurrence of the same redex is in the set as well.
As usual any -term M can be identi ed with its binary syntactical tree, where nodes are represented by the subset f0;1gwhich is the tree domain of M; if N is a subterm of M, and its syntactical subtree is rooted at 2f0;1gin the tree of M, then we say that \N occurs at in M", and denote this occurrence byh ;Ni.
De nition 2.5 (Uniform and
1-uniform Set of Redexes)
LetM be any -term, then:(i) Occ(M) =fh ;NijN occurs at in Mg;
(ii) Red(M) =fh ;(x:P)Qi2Occ(M)jP;Qany terms;xany variableg; (iii) F Red(M) isuniformi
h ;Ri2F^h ;Ri2Red(M))h ;Ri2F;
(iv) F Red(M) is1-uniformi F is uniform and fRj9 :h ;Ri2Fgis a singleton.
In the sequel we need the notions of residual and development, which are well known concepts of -calculus theory: we refer the reader to [3] chapter 11, from which we take the notation.
De nition 2.6 (Parallel Reduction)
The reduction relation)pover -terms is de ned by:M )pN i 9F Red(M):Fis uniform and(M;F)!!cplN where(M;F)!!cplN is the complete development of(M;F) (see [3], p. 286).
In the literature the idea of parallel reduction in the framework of the -calculus is usually formalized by the Gross-Knuth Reduction as de ned in [4] and [16] (see also [3], 13:2:7).
De nition 2.7 (Gross-Knuth Reduction)
M !gkN i (M;Red(M))!!cplN:
Actually this is a particular case of the relation)p since Red(M) is trivially uniform.
Lemma 2.8
LetFRed(M)be uniform and F=F1[:::[Fm where each Fi is1-uniform. If(M;F)!!cpl N, then there areN0;:::;Nm and a permutation of orderm such that M N0,N Nm and for all1im,
(Ni;1;F0(i))!!cplNi
whereF0(i) is the set of residuals of redexes in F(i) with respect to the -reduction M ! Ni;1, and F0(i) is1-uniform.
Proof. We introduce an ordering on the 1-uniform sets of redexes of M. Let F =fh h;Rijh2Hgand
F
0=fh k;R0ijk2Kg; then
FF
0i 9h2H8k2K: klex h;
where lex is the lexicographic order. This is a total ordering and we take as the permutation s.t. for all i,F(i) <F(i+1). If i < j then F(i) <F(j), so that all occurrences of R02F(j) either contain the same copies of redexes R 2F(i) by 1-uniformity, in which case they are modi ed in the same way while
contracting the R; or they do not contain any such occurrence, in which case they remain unchanged. In any case their residuals are syntactically equal, so that theF0(i)are 1-uniform. Now the thesis follows from the uniqueness of the result of a complete development (see [3], Theorem 11:2:25) since then the reduction (M;F)!!cplN can be rearranged as we need.
2
De nition 2.9 (Cuts generating
F-redexes)
LetDbe a deduction whose conclusion subject isM; x a uniformFRed(M); nally letcut B;x : :;P : B0:;y:Q : B;B0:;P[y:Q=x] :
be a cut in D. We say that the above cut generates F-redexes of M i P has at least a subterm of the shape xR, such that all occurrences of (y:Q0)R0 in M belong to F, where(y:Q0)R0 is a xed instance of (y:Q)R.
Remark 2.10
We have to consider the substitution instance (y:Q0)R0 instead of (y:Q)R itself because of the possibility that other cuts, placed under the given one in the current deduction, substitute variables inside (y:Q)R.De nition 2.11 (Cut Degree)
Let D be a deduction whose conclusion subject is M; x a uniformF Red(M). Moreover letcut B;x : :;P : B0:;Q : B;B0:;P[Q=x] :
be a cut inference in D. Then the degree of this cut inDrelative to F is de ned by cases:
- if this cut does not generate F-redexes then its degree is0;
- otherwise its degree is the sum of the degrees of the occurrences of its cut-type in the left and right premises of the cut.
Remark 2.12
Our de nition of cut degree is not the classical one, which simply records the number of symbols of the cut-type. The distinctive features of our cut degree are:(i) if the degree is 0 then the cut does not generateF-redexes;
(ii) if the degree is 1 then the cut is ready and the cut-type is an arrow;
(iii) if the degree is greater than 1 and the cut-type is an arrow then the cut is not ready;
(iv) otherwise the degree is a function of the number of inferences of the form L an R which have been used in generating the occurrences of the cut-type.
Feature (i) has to be so because we will eliminate only cuts generatingF-redexes. Moreover when eliminating a cut generating anF-redex, whose cut-type is of the form ! , the redexes generated by the new cuts produced by the contraction cannot be in F; hence their degree relative to F will be 0. Indeed if the contraction of a redex inF produces new redexes, these will never be contracted in the development ofF. Feature (ii) will imply that, if in a ready deduction the maximum degree of a cut generating F-redexes is 1, then all cuts generatingF-redexes have as cut-type an arrow type (i.e. they have the shape of Figure 2 (a)). As a matter of fact our proof of subject reduction (proof of 2.16) actually hints to an algorithm which performs a preliminary elimination of all \logical" cuts, which does not a ect the subject, ending with the
\parallel" elimination of arrow cuts, which causes actual -contraction.
Feature (iv) takes into account that when we shall eliminate a ready cut whose premises are conclusions of say8L and8R, the number of symbols of the cut-type of the newly generated cut may well be greater than that of the original cut-type, despite of the intuition that the derivation has been sempli ed. Note that in this third case the degree of the cut is always greater than 2.
De nition 2.13 (Degree of Deductions)
(i) LetD be a deduction whose conclusion subject isM; x a uniformF Red(M). Thedegree (D;F) of Drelative to F is the highest degree of a cut in D.
(ii) Let D : B :; M : and D0 : B0 : ; M : ; then D0 is non-increasing with respect to D i
(D0;F)(D;F)for all uniform FRed(M).
We prove that we can transform deductions by adding assumptions, by changing the names of (free) term variables and by eliminating the cuts with shapes (f) and (g) of Figure 2, preserving readiness and non increasing the cut degrees.
We say that a deductionD0issimilarto a deductionDi D0is obtained fromDby adding (basic) typing statements to the bases, renaming term variables and substituting type expressions to free occurrences of type variables. This means that D0and D have the same deduction tree and di er only for the bases and for the names of term variables and, possibly, because type-occurrences are substitution instances of their counterparts inD. Since the notion of degree does not depend on the length of type expressions involved in cuts, but rather on the structure of the derivation in which they occurr, similar deductions have the same degree with respect to any uniformF.
Lemma 2.14
(i) IfD: B :;M : and B0B then there is D0: B0:;M : such thatD0 is similar to D. (ii) IfD: B;x : :;M : and y is fresh then there is
D
0: B;y : :;M[y=x] : such that D0is similar to D.
(iii) IfD: B :;M : , is a type andt is any type variable, then there isD0: B[ =t] :;M : [ =t]such that D0is similar to D.
(iv) All occurrences of ready cuts of the shapes (f) and (g) of Figure 2 can be eliminated preserving readiness and obtaining a non-increasing deduction of the same statement.
Proof. (i). Easy by adding the premises of B0;B to each statement, possibly renaming some variables not in B.
(ii). Immediate, since deductions are independent of the names of (free) term variables.
(iii). By de nition of similarity.
(iv). Let us consider a cut of the shape (f) or (g):
B;x : :;x : Ax Bi:;M : i
B0:;M : R
B;B0:;M : cut
B;x : ! :;x : ! B0:;M : ! ! B;B0:;M : ! cut where is either Ax or !. In both cases (i) implies that we can replace
B0:;M : by B;B0:;M : obtaining a deduction which satis es the given conditions. 2 The following Lemma (proved in the Appendix) claims that every deduction can be transformed into a ready deduction of the same statement. This can be accomplished without increasing the complexity of the proof. Formally:
Lemma 2.15 (Rank Lemma)
For any derivationD: B :;M : there exists a ready derivationD
0: B :;M : such that D0is non increasing with respect to D.
Theorem 2.16 (Invariance of Types under Parallel Reduction)
(i) B :;M : and M )pN implyB :;N : .
(ii) B `M : and M )pN implyB`N : .
Proof. (i) If M )pN then for someF Red(M), (M;F)!!cplN. By Lemma 2.8 this reduction can be splitted into a nite number of steps, whoseF's are 1-uniform. Hence it suces to prove the thesis whenF is 1-uniform. On the other hand by Lemmas 2.14 (iv) and 2.15, we can assume that the givenD: B :;M : is ready and does not contain cuts of shapes (f) and (g). Since redexes inF are exactly those which determine the positive degrees of cuts, we prove the theorem as a kind of cut elimination: indeed it is a such, being parametrized with respect toF.
If (D;F) = 0 andDis ready, then no cut generatesF-redexes, henceF-redexes may occur only as subterms of terms of type !: in this case clearly B :;N : is derivable introducing by rule ! the reducta of those subterms of M.
If (D;F) = 1 then all cuts which generateF-redexes have an arrow type as cut-type; hence, by the readiness ofD, they have the shape
B;z : :;P : B0:;R :
B;B0;x : ! :;P[xR=z] : !L B00;y : :;Q : B00:;y:Q : ! !R B;B0;B00:;P[xR=z][y:Q=x] : cut Then all these cuts can be replaced as follows:
B;z : :;P : B00;y : :;Q : B0:;R : B0;B00:;Q[R=y] : cut B;B0;B00:;P[Q[R=y]=z] : cut
and in the remaining parts of Dthe subjects have to be reduced (by)p) in order to match P[Q[R=y]=z].
Eventually we get a deduction of degree 0.
If (D;F) > 1 then all cuts with degree (D;F) are of the shape (b), (c) or (d) of Figure 2. In fact all cuts are ready and moreover all cuts of shape (e) have degree 0, since they cannot generate any redex. We replace the cuts of shape (b) when =9:
B;x : :;P :
B;x :9t: :;P : 9L B0:;Q : [=t]
B0:;Q :9t: 9R B;B0:;P[Q=x] : cut
by B;x : [=t] :;P : B0:;Q : [=t]
B;B0:;P[Q=x] : cut
where the left premise of the new cut is obtained by a derivation similar to the subderivation whose conclusion was B;x : :;P : , which is non-increasing by Lemma 2.14 (iii). The degree of each occurrence of the cut-type decreases by 1, so that the degree of the cut is lowered by 2. The cases =8 or = are similar.
Finally cuts of shape (c) or (d) are replaced by
B;x : :;P : B0;B00:;Q : B;B0;B00:;P[Q=x] : cut
where some basic statements are added to the bases of the premises using Lemma 2.14 (i). It is easy to verify that we obtain cuts of lower degrees.
After these transformations have been performed we get a derivation, sayD0, of lower degree; we then apply Lemma 2.15 to obtain a ready derivation which is non-increasing with respect to D0, so that the inductive hypothesis applies.
(ii) Immediate form (i) and from Theorem 1.5. 2
Corollary 2.17 (Invariance under Gross-Knuth Reduction)
(i) B `M : ; M !gkN )B `N : .
(ii) B `M : ; M ! N )9L: N! L and B`L : .
Proof. (i) Immediate from Theorem 2.16 (ii) and the remark after De nition 2.7.
(ii) Is a consequence of (i) and of the co nality of!gkwith respect to! , proved in [3] 13:2:11. 2 Note that the above proof cannot be transformed into a proof of normalization of -terms (which does not hold since we allow recursive type and the universal type !). Indeed the parameter F is essential to the proof and cannot be dropped; what we have actually shown is a kind of typed version of the nite development theorem of the untyped -calculus.
3 Semantics
In the present section we describe the construction of a model for our type system, based on a technique introduced in Coppo [11] that permits to interpret type recursion even when type constructors are not monotonic with respect to the (semantical) relation of subtyping induced by the interpretation of types as sets of values. This technique di ers from that used by MacQueen, Plotkin and Sethi [17] in exploiting only the approximation properties of the domain in which untyped terms are interpreted, without any appeal to a complete metric space structure that can be de ned on the collection of (denotations of) types. This approach to type interpretations has some advantages over that followed by MacQueen, Plotkin and Sethi [17], in not requiring any restriction on the formation rules for types and also in o ering a powerful proof technique for many semantical properties of the type system (see Cardone and Coppo [10] for some examples).
Starting from a model D1 of the -calculus, obtained as the inverse limit of a sequence of complete lattices as in Scott [26], each type will be interpreted as a subset of D1 satisfying constraints derived from the order-theoretic nature of this model. For example, as every type can be assigned to the combinator (x:xx)(x:xx), and the interpretation of in every continuous -model D is the least element ? (see Barendregt [3]), we require that each of the subsets of D1 that we will consider as candidates for the interpretation of types should contain?. Furthermore, if AD1is such a subset and A is a directed set, then also F2A: this condition yields the correctness of the typing of the xed-point combinator Y as a term of type (!)!, for any type .
The explicit construction of the domain D1 (refer to Barendregt [3] for a detailed description) starts from the two-points lattice D0 =f?;>g and, given the lattice Dn, the lattice Dn+1 is de ned to be the lattice ofcontinuous functions [Dn! Dn] from Dn to itself, with an embedding n : Dn! Dn+1 and a projection n: Dn+1!Dn. The inverse limit of the diagram
::: n;2;Dn;1 n;1; Dn n;Dn+1 n+1; :::
satis es the recursive domain equation D1= [D1!D1], with isomorphisms : D1![D1!D1] and : [D1!D1]!D1. This induces an operation of application over D1 de ned by
de = (d)(e) for d;e2D1:
The construction of D1endows it with an approximation structure, orthogonal to its order structure, which takes the form of a denumerable sequence of continuous mappings ()n: D1!D1, that provide an image of each Dninside D1, and in fact we shall identify in the sequel Dnwith the nite subset fdnjd2D1g of D1. In particular, the following properties will be used without explicit mention throughout this section (see Barendregt [3], 18.2.8 and 18.2.9):
Proposition 3.1 (Properties of approximation mappings)
The familyf()n: D1!D1gn2IN satis- es the following conditions, for allf;d2D1 and m;n;k2IN:1. Ifd =>thend0=>, otherwised0=?. 2. (dn)m= (dm)n= dmin(m;n).
3. d =Fn2INdn.
4. Ifnkthen fn+1dk= fn+1dn.
5. Ifnkthen (fk+1dn)n= fn+1dn. 6. fn+1dn= fn+1d = (fdn)n.
7. f = fn+1 if and only if 8d2D1:fd = (fdn)n.
A consequence of this Proposition is that for d;e2D1, de =Fn2INdn+1en.
We shall require each subset A of D1which interprets a type to be closed under each of these mappings, in the sense that d2A implies that dn2A for all n2IN. We obtain in this way a collection of subsets of D1 that is closed under a wide range of type constructors, and also o ers some technical advantages over ideals that have been often used in the semantics of type inference systems (see, for example, MacQueen, Plotkin and Sethi [17]).
De nition 3.2 (Pro nite Subsets)
(i) The classP
of pro nite subsets of D1 is de ned to consist of those subsetsAof D1 such that:?;>2A;
Aiscomplete: ifhd(i)ii2INis an increasing chain inD1such that8i2IN:d(i)2A, thenFi2INd(i)2A;
A isclosed under approximations: d2A impliesdn2A, for alln2IN.
(ii) For pro nite subsetsA;BofD1, the relationA<nB is de ned to hold if and only ifAB anddn2A wheneverd2B.
Note that>belongs to every pro nite subset of D1: this would not be possible if we used ideals (the only ideal containing>is D1). Observe the close connection between this class of subsets of D1and the class of relations used in Amadio [1] and Cardone [9] in the construction of models for strongly typed, polymorphic languages with type recursion and subtyping.
Obviously, the intersection of an arbitrary familyX of pro nite subsets of D1is pro nite, so the structure
h
P
;iis a complete lattice havingf?;>gand D1as bottom and top elements, respectively. We shall denote the in nitary lattice operations byinf
andsup
whenever convenient (observe however that the supremum of a nite familyof pro nite subsets coincides with their set-theoretic union). The following Proposition collects the main properties of this lattice. For a pro nite subset A, the notation Andenotes the setfdnjd2Ag.Proposition 3.3 (Properties of Pro nite Subsets)
ForA2P
and any n2IN: 1. AnA;2. An2
P
; 3. An<nAn+1;4. For any familyX
P
,(SA2XAn)2P
; 5. For any familyXP
we have(
sup
X)n= [A2XAn: Proof.(1) Immediate, as A is closed under approximations.
For proving (2), observe that An is complete because every nite subset of D1 is obviously complete.
Furthermore, in order to show that Anis also closed under approximations, let d2An. There are two cases:
m > n: dm= d (because d2Dn), so dm2An.
mn: As d2A (by (1)), dm2A, and dm= (dm)n2An,
