It suces to show that, ifD: B :;M : is a derivation ending with one occurrence of a cut of rank r > 2, in which all other cuts are ready, thenD can be transformed into a derivationD0: B :;M : containing some occurrences of the original cut with lower rank and possibly some new cuts of rank 2, while preserving the readiness of all other cuts. This is enough provided thatD0will be not increasing wrtD, i.e. we will not generate cuts with higher degrees. By inspection of all the transformations we will shown, it is easily seen that the degrees of the transformed cuts do not increase, and the degrees of newly generated cuts is either the same of the old ones or 0. This is established by routine calculations: we shall actually perform it just in the rst case we treate and in some other relevant ones. Note that these calculations are parametric wrt
F, hence F is actually an arbitrary uniform set of redex occurrences.
By Lemma 2.14 (iv) we can assume that Ddoes not contain ready cuts of shape (f) or (g).
We split the proof into two parts: in the rst one we lower the right rank of the considered cut, which is supposed to be > 1; in the second part we assume the right rank to be 1 and we lower the left rank supposed to be > 1. Since all transformations we do leave unchanged the left rank in part 1 an the right rank in part 2, this establishes the thesis.
Part 1:
right rank > 1.We distinguish various cases according to the shape of the last rule above the right premise of the cut. Note that Ax and ! cannot occur because the right rank is > 1. For the same reason cases of rules introducing type constructors to the right are impossible.
Case!L:
B;x : :;M : B0;u : :;N : B00:;P : B0;B00;v : ! :;N[vP=u] : !L B;B0;B00;v : ! :;M[N[vP=u]=x] : cut:
We can freely assume that u62FV (B;B00) and u62FV (M); hence we transform it into B;x : :;M : B0;u : :;N :
B;B0;u : :;M[N=x] : cut B00:;P : B;B0B00;v : ! :;M[N=x][vP=u] : !L.
Note that the new cut in the gure above is legal since u 62 FV (B;B00) and B;B0;B00 is a basis. Finally u62FV (M) implies that M[N[vP=u]=x]M[N=x][vP=u]. To verify the non-increasing property, suppose that the cut inference in the given derivationD is generating an F-redex (otherwise the thesis is trivially true); then the corresponding cut in the transformed derivationD0is generating anF-redex too. We have immediately that the degrees of the occurrences of the cut-type do not change. In fact the degrees of the occurrences of in B0;B00;v : ! :;N[vP=u] : and in B0;u : :;N : are clearly equal by de nition.
Case L ( 2f;8;9;^;_g):
B;x : :;M : Bi;y : i:;N : B0;y : 0:;N : L B;B0;y : 0:;M[N=x] : cut:
If y62FV (B), we transform it into
B;x : :;M : Bi;y : i:;N : B;Bi;y : i :;M[N=x] :
B;B0;y : 0:;M[N=x] : L.
cut
Here and in what follows we assume to have one or two cuts according to the value of the index i.
Otherwise B = B00;y : 0 for some B00, since B;B0;y : 0 is a basis. Let w be any fresh variable; de ne
Finally note that the last cut whose right premise is an axiom is ready and surely it does not create any redex, hence it has degree 0.
Case cut: in this case, by hypothesis, the upper cut is ready. We must distinguish subcases according to the shapes of Figure 2. We can assume that x62FV (B;B0;B00) and z;y;u62FV (B000).
Notice that M[N[uR=z][y:Q=u]=x] M[N=x][uR=z][y:Q=u] since we can assume that x 62FV (N) and u;z62FV (M).
Notice that M[N[Q=y]=x]M[N=x][Q=y] since we can assume y62FV (M).
(e): we are given a gure of the shape y62FV (M). We transform them into
B00;x : :;M : Bi[z=y];B0:;N[z=y] :
respectively. Notice that there is a deduction of Bi[z=y];B0:;N[z=y] : similar to the given deduction of Bi :;N : by Lemma 2.14 (i) and (ii). Moreover by the assumption y62FV (M) we have M[N[z=y]=x] M[N=x][z=y].
Part 2:
right rank = 1 and left rank > 1.In this case the deduction will have the shape:
Bi:;Mi: i
B;x : :;M : rule B0:;N : B;B0:;M[N=x] : cut:
In the conclusion of rule the cut type is either generated in that inference, or it has a father in one or both premises of rule. In the last case we shall assume that the statement x : occurs in both B1 and B2
(if i = 2), being the case in which it occurs just once similar and simpler.
We distinguish various cases according to the last rule above the left premise of the cut. Note that cases Ax and ! are impossible because the left rank is > 1.
Case!L: we are given either a gure of the shape
B;u : ;x : :;M : B0;x : :;P :
B;B0;B00:;M[N=x][zP[N=x]=u][N=z] : B;B0;B00;z : ! :;M[N=x][zP[N=x]=u] : !L B;B00;u : :;M[N=x] : cut B0;B00:;P[N=x] :
B;u : ;x : ! :;M : B00:;N : ! B0;x : ! :;P : B00:;N : ! cut B00:;N : ! cut respectively; observe that z is a fresh variable. Now this and u 62 FV (N) imply M[N=x][vP[N=x]=u] M[vP=u][N=x] and M[N=x][zP[N=x]=u][N=z]M[xP=u][N=x].
Case!R: B;x : ;y : :;M :
B;x : :;y:M : ! !R B0:;N : B;B0:;(y:M)[N=x] : ! cut Clearly we can assume y62FV (N) and y62FV (B0). The derivation transforms into
B;y : ;x : :;M : B0:;N : B;B0;y : :;M[N=x] :
B;B0:;y:M[N=x] : ! !R cut and, by the fact that y62FV (N), (y:M)[N=x]y:M[N=x].
Case L ( 2f;8;9;^;_g):
Bi;y : i;x : :;M :
B;y : 0;x : :;M : L B0:;N : B;B0;y : 0:;M[N=x] : cut If y62FB(B0), this derivation is transformed into
Bi;y : i;x : :;M : B0:;N : Bi;B0;y : i:;M[N=x] :
B;B0;y : 0:;M[N=x] : L cut
Otherwise we use the same renaming technique of the case L in part 1 of this proof.
Case R ( 2f;8;9;^;_g):
Bi;x : :;M : i
B;x : :;M : R B0:;N : B;B0:;M[N=x] : cut becomes Bi;x : :;M : i B0:;N :
Bi;B0:;M[N=x] : i
B;B0:;M[N=x] : R cut
Case cut: in this case by hypothesis the upper cut is ready. We must distinguish subcases according to the shapes of Figure 2. In the sequel there is no loss of generality in assuming that y62FV (N) and y62FV (B000).
(a):
B;x : ;z : :;M : B0;x : :;R :
B;B0;x : ;y : ! :;M[yR=z] : !L B00;x : ;u : :;Q : B00;x : :;u:Q : ! !R
B;B0;B00;x : :;M[yR=z][(u:Q)=y] : cut B000:;N : B;B0;B00;B000:;M[yR=z][(u:Q)=y][N=x] : cut is replaced by
B;B0;B000;y : ! :;DM[N=x][yR[N=x]=z] :
B00;u : ;x : :;Q : B000:;N : B00;B000;u : :;Q[N=x] :
B00;B000:;u:Q[N=x] : ! !R cut B;B;B ;B : M[N=x][yR[N=x]=z][(u:Q[N=x])=y] : cut
where the derivationDis given by
B;z : ;x : :;M : B000:;N :
B;B000;z : :;M[N=x] : cut B0;x : :;R : B000:;N : B0;B000:;R[N=x] : cut B;B0;B000;y : ! :;M[N=x][yR[N=x]=z] : !L
Notice that M[yR=z][(u:Q)=y][N=x]M[N=x][yR[N=x]=z][(u:Q[N=x])=y] since we can assume that z 62 FV (N).
(b), (c) and (d):
Bi;x : ;y : i:;M :
B;x : ;y : :;M : L Bj;x : :;P : j
B0;x : :;P : R
B;B0;x : :;M[P=y] : cut B00:;N :
B;B0;B00:;M[P=y][N=x] : cut
where 2f;8;9;^;_g, can be replaced by Bi;y : i;x : :;M : B00:;N :
Bi;B00;y : i :;M[N=x] : B;B00;y : :;M[N=x] : L
cut Bj;x : :;P : j B00:;N : Bj;B00:;P[N=x] : j
B0;B00:;P[N=x] : R cut B;B0;B00:;M[N=x][P[N=x]=y] : cut:
Again we have that M[P=y][N=x]M[N=x][P[N=x]=y] by the assumption about y.
(e): we are given a gure either of the shape Bi;x : :;M :
B;y : ;x : :;M : L B0;z : :;z : Ax
B;B0;z : ;x : :;M[z=y] : cut B00:;N : B;B0;B00;z : :;M[z=y][N=x] : cut or of the shape
Bi;x : :;M :
B;x : ;y : :;M : L B0;x : :;x : Ax
B;B0;x : :;M[x=y] : cut B00:;N : B;B0;B00:;M[x=y][N=x] : cut where is any type constructor. We transform them into
Bi[z=y];B0;x : :;M[z=y] : B00:;N : Bi[z=y];B0;B00:;M[z=y][N=x] : B;B0;B00;z : :;M[z=y][N=x] : L
cut and into Bi;B0;x : :;M : B00:;N :
Bi;B0;B00:;M[N=x] : B;B0;B00;y : :;M[N=x] : L
cut
B00:;N : B;B0;B00:;M[N=x][N=y] : cut
respectively. We observe that the newly generated cut is ready, since by hypothesis the right rank of the current cut was 1. Moreover the degree of this new cut is the degree of the lower cut of the original gure.
2
References
[1] R. Amadio. Recursion over realizability structures. Information and Computation, 91(1):55{85, 1991.
[2] F. Barbanera, M. Dezani-Ciancaglini, and U. de' Liguoro. Intersection and union types: syntax and semantics. Internal report, Universita di Torino, 1992.
[3] H. P. Barendregt. The Lambda Calculus. Its Syntax and Semantics. North-Holland, 1984.
[4] C. Bohm. The CUCH as a formal and description language. In T.B. Steel Jr., editor,Formal Language Description for Computer Programming, pages 179{197. North-Holland, 1966.
[5] C. Bohm and A. Berarducci. Automatic synthesis of typed -programs on term algebras. Theoretical Computer Science, 39:135{154, 1985.
[6] P. Canning, W. Cook, W. Hill, W. Oltho , and J.C. Mitchell. F-bounded quanti cation for object-oriented programming. In Proceedings Fourth International Conference on Functional Programming Languages and Computer Architecture, pages 273{280. IEEE, September 1989.
[7] L. Cardelli. Typeful programming. Research Report 45, DEC SRC, May 24, 1989.
[8] L. Cardelli and P. Wegner. On understanding types, data abstraction and polymorphism.ACM Com-puting Surveys, 17:471{522, 1985.
[9] F. Cardone. Recursive types for Fun. Theoretical Computer Science, 83:29{56, 1991.
[10] F. Cardone and M. Coppo. Type inference with recursive types. Syntax and Semantics. Information and Computation, 92(1):48{80, 1991.
[11] M. Coppo. A completeness theorem for recursively de ned types. In W. Brauer, editor,Proc. 12th Inter-national Colloquium on Automata, Languages and Programming, LNCS 194, pages 120{129. Springer, 1985.
[12] M. Coppo and M. Dezani-Ciancaglini. An extension of basic functionality theory for lambda-calculus.
Notre Dame Journal of Formal Logic, 21(4):685{693, 1980.
[13] M. Coppo and G.L. Ferrari. Type inference, abstract interpretation and strictness analysis. Internal report, Universita di Torino, 1992.
[14] T. Coquand and G. Huet. The calculus of constructions. Information and Computation, 76:95{120, 1988.
[15] T. Freeman and F. Pfenning. Re nement types for ML. InProceedings of the SIGPLAN '91 Symposium on Language Design and Implementation, Toronto, Ontario, pages 268{277. ACM Press, June 1991.
[16] D.E. Knuth. Examples of formal semantics. In E. Engeler, editor, Symposium on Semantics and Algorithmic Languages, LNM 188, pages 212{235. Springer, 1970.
[17] D. MacQueen, G.D. Plotkin, and R. Sethi. An ideal model for recursive polymorphic types. Information and Control, 71((1/2)):95{130, 1986.
[18] N.P. Mendler. Recursive types and type constraints in second order lambda calculus. In Proceedings Second Symposium on Logic in Computer Science, pages 30{36. IEEE, 1987.
[19] J.C. Mitchell and G.D. Plotkin. Abstract types have existential type. ACM Transactions on Program-ming Languages and Systems, 10:470{502, 1988.
[20] F. Pfenning. Intersection types for a logical framework. POP Report 92-006, School of Computer Science, Carnegie-Mellon University, December 1988.
[21] B. Pierce. Preliminary investigation of a calculus with intersection and union types. Internal report, Carnegie-Mellon University, 1990.
[22] G. Pottinger. A type assignment for the strongly normalizable -terms. In J.P. Seldin and R.J. Hindley, editors,To H.B. Curry: Essays in Combinatory Logic, Lambda Calculus and Formalism, pages 561{577.
Academic Press, 1980.
[23] D. Prawitz. Natural Deduction. Almqvist & Wiksell, 1965.
[24] J.C. Reynolds. Preliminary design of the programming language FORSYTHE. Technical Report CMU-CS-88-159, Carnegie-Mellon University, 1988.
[25] J.C. Reynolds. Syntactic control of interference. Part II. In G. Ausiello et al. editor, International Colloquium on Automata, Languages and Programming, LNCS 372, pages 704{722. Springer, 1989.
[26] D. Scott. Continuous lattices. In F.W. Lawvere, editor,Toposes, Algebraic Geometry and Logic, LNM 274, pages 97{136. Springer, 1972.
[27] M. Szabo. The Collected Papers of Gerhard Gentzen. North-Holland, 1969.