ISS

N 0

249-

6399

ap por t de r ech er ch e

INSTITUT NATIONAL DE RECHERCHE EN INFORMATIQUE ET EN AUTOMATIQUE

An explicit Eta rewrite rule

Daniel BRIAUD

N˚ 2417Novembre 1994

PROGRAMME 2

An explicit Eta rewrite ruleDaniel BRIAUDProgramme 2 | Calcul symbolique, programmation et g�enie logicielProjet EurecaRapport de recherche n�2417 | Novembre 1994 | 20 pagesAbstract: In this report, we extend �-calculi of explicit substitutions by an Eta rule. We do this in theframework of ��, a �-calculus of explicit substitutions introduced by Lescanne (1994) and thoroughly studiedby Lescanne and Rouyer-Degli (1994). The main feature of such a calculus is that the classical �-contractionis expressed by a �rst-order term rewriting system. Our main result is the explicitation of the �-contraction bymeans of an unconditional, generic Eta rewrite rule and of an extension of the substitution calculus, �. Previousde�nitions of Eta are due to Hardin (1992) and R��os (1993) in the framework of ��-calculi. The principaldi�erence between �� and ��-calculi concerns con uence and strong normalization: �� is ground con uent andits simply typed version is terminating, whenever ��*-calculus is con uent on open terms but non terminatingon typed terms. In their work, Hardin and R��os present Eta rule as an extension of �-contraction. Theirextension is a conditional rewrite rule and does not stick fully to the philosophy of explicit substitutions. In ourapproach, the Eta-rule is a �rst order rewrite rule which uses an explicit substitution calculus. For that, oneneeds to introduce a new constant ? that denotes an unspeci�ed term. Its behaviour is described by a rewriterule. This report shows, in the one hand, how the Eta-rule associated with �� and the rule for ? provides acorrect implementation of the �-reduction and studies other properties of the ���-calculus namely con uenceon ground terms and strong normalisation on typed terms. On the other hand, this explicit Eta leads to �0 avery general alternative to the classical �. Indeed, we prove that �0 allows con uent contractions which are notcaptured by classical �.Key-words: �-calculus, explicit substitutions, �-reduction (R�esum�e : tsvp)Unite de recherche INRIA Lorraine

Technopole de Nancy-Brabois, Campus scientifique,615 rue de Jardin Botanique, BP 101, 54600 VILLERS LES NANCY (France)

Telephone : (33) 83 59 30 30 – Telecopie : (33) 83 27 83 19Antenne de Metz, technopole de Metz 2000, 4 rue Marconi, 55070 METZ

Telephone : (33) 87 20 35 00 – Telecopie : (33) 87 76 39 77

Une r�egle de r�e�ecriture Eta expliciteR�esum�e : Dans ce rapport, nous �etendons les �-calculs �a subsitutions explicites avec une r�egle Eta. Nousl'e�ectuons dans le cadre de ��, un �-calcul �a substitution explicite introduit par Lescanne (1994) et �etudi�een d�etail par Lescanne et Rouyer-Degli (1994). La caract�eristique essentielle d'un tel calcul est l'expressionde la �-contraction classique �a l'aide d'un syst�eme de r�e�ecriture de termes du premier ordre. Notre r�esultatprincipal consiste en l'explicitation de la �-contraction au moyen d'une r�egle de r�e�ecriture Eta non-conditionnelle,g�en�erique et d'une extension du calcul de substitution �. Les pr�ec�edentes d�e�nitions de Eta sont dues �a Hardin(1992) et R��os (1993) dans le cadre des ��-calculs. La principale di��erence entre les calculs �� et �� concerne lacon uence et la forte normalisation : �� est con uent sur les termes clos et sa version simplement typ�ee termine,alors que ��*est con uent sur les termes ouverts mais ne termine pas sur les termes typ�es. Dans leurs travaux,Hardin et R��os d�e�nissent la r�egle Eta comme une extension de la �-contraction. Leur extension est une r�egleconditionnelle et ne respecte pas totalement la philosophie des substitutions explicites. Dans notre approche,la r�egle Eta est une r�egle de r�e�ecriture du premier ordre qui emploie un calcul de subsitutions explicites. Pourcela, on introduit une nouvelle constante ? qui d�enote un terme non-sp�eci��e. Son comportement est d�ecrit parune r�egle de r�e�ecriture. Ce rapport montre, d'une part, comment Eta associ�ee �� et �a la r�egle de ? fournit uneimpl�ementation correcte de la �-r�eduction, puis �etudie des propri�et�es du ���-calcul, c'est-�a-dire, la con uencesur les termes clos et la forte normalisation des termes typ�es. D'autre part, cette Eta explicite conduit �a �0, unealternative �a � qui se r�ev�ele plus g�en�erale. En e�et, nous prouvons que �0 autorise des contractions con uentesqui ne sont pas captur�ees par la � classique.Mots-cl�e : �-calcul, substitutions explicites, �-r�eduction

An explicit Eta rewrite rule 3IntroductionThe main feature of a �-calculus of explicit substitutions is that the classical �-contraction is expressed by a�rst-order term rewriting system. In this way, such �-calculi concur to achieve Curry's program (Cf appen-dix A). Indeed, one aim was to �nd a fully formalized prelogic, constituted of a theory of substitution (not ametatheory) and a theory of types. Upon Curry, there are two forms of such a prelogic : Combinatory Logicwhich is ultimate and �-conversion which is intermediate. We think �-calculus of explicit substitutions is asultimate as Combinatory Logic, but more intuitive. Historically, explicit substitutions were �rst designed by DeBruijn [dB78] but with a crude terminology. They have been made popular more recently by Abadi, Cardelli,Curien and L�evy [ACCL91].These authors present ��, a �-calculus of explicit substitutions which is a result of an almost decade researchwork. The starting point is CCL, categorical combinator logic [Cur83, Cur86b, Cur86a], a combinatory logicmore intuitive than the classical one. Indeed, it is based on �-calculus with cartesian products and keeps itsstructure. Hardin [Har87, Har89] studied con uence on open terms of this calculus. An important contributiontoward explicit substitutions is the ��-calculus, [Cur86b] suited for weak reduction. It has been extended to�� [ACCL91]. Hardin and Levy designed ��* [HL89], thus achieving an important goal : con uence on openterms. Guided by implementation grounds, this family of calculi rests from the beginning on the concept ofcomposition of substitutions.In this paper, we will work in ��, a recent �-calculus of explicit substitutions introduced in [Les94] and tho-roughly studied in [LRD94a]. What characterizes this calculus is that the substitution calculus � is an orthogonalrewriting system which does not manage composition of substitutions. Like most �-calculi of explicit substi-tutions, �� uses De Bruijn indices for terms [dB72], beginning at 1. We recall the syntax of �-terms with DeBruijn indexes :De�nition 1 (�) The set � is the set generated by :Terms a ::= n j aa j �aNaturals n ::= n+ 1 j 1:Terms of � are called pure terms.How does �� break the �-contraction ? First, the rule Beta creates a substitution stored in a closure denotedby [ ] : Beta (�a)b ! a[b=]Then, rules of � (Cf �gure 1) distribute this substitution and apply it to indexes. The rules fBetag [ � arede�ned on the following set of terms ��:Terms a ::= n j aa j �a j a[s]Substitutions s ::= a= j * (s) j "Naturals n ::= n+ 1 j 1:For example, (�x:�y:xy)z, denoted (�(�2 1 ))1 in De Bruijn notation, is contracted by � as follows :RR n�2417

4 Daniel BRIAUD(Beta) (�a)b ! a[b=](App) (ab)[s] ! a[s]b[s](Lambda) (�a)[s] ! �(a[*(s)])(FVar) 1 [a=] ! a(RVar) n+ 1[a=] ! n(FVarLift) 1[*(s)] ! 1(RVarLift) n+ 1 [*(s)] ! n [s]["](VarShift) n ["] ! n+ 1Figure 1: The rewrite system ��(�(�2 1 ))1 �!Beta (�2 1 )[1 =]�!� �((2 1 )[* (1 =)]) rule Lambda�!� �(2 [* (1 =)] 1 [* (1 =)]) rule App+�!� �(1 [1 =]["]) 1 ) rules RVarLift, FVarLift�!� �(1 ["]) 1 ) rule FVar�!� �(2 1 ) rule VarShiftIts �-normal form, namely �(2 1 ), is equivalent to �y:z y. We may �-reduce it to z. Indeed, the practical reasonfor de�ning �-reduction comes from the natural equality (�x:fx)a =� fa if x has no free occurences in f . Itcomes from the wish to make equal two functions which behave the same, that is which return the same resultwhen applied to the same parameter (extensional equality). This is the role of �-contraction :(�x:fx) �!� f if x has no free occurences in f .Accordingly, we would like to �-reduce �(2 1 ) to 1 . We observe that in De Bruijn notation, �-contraction is notas trivial as in the classical formalism: there is some work to do to compute the �-reduct. Our aim is now to �nda �rst order rewrite rule which explicits the substitution process involved in the �-contraction and hidden at themeta-level in all the other approaches [Har92, R��o93]. In the following, we explicit the �-reduction by means ofan unconditional Eta rewrite rule and of an extension of the substitution calculus, �. We show that the rewritingsystem obtained, denoted by ���, provides a correct implementation of the �-contraction. Moreover, Eta leadsto a new de�nition of the classical �-contraction. We especially study consequences of this new de�nition w.r.t.ground con uence. Next, we prove some properties of the ���-calculus namely con uence on ground terms1and strong normalisation on typed terms. Finally, we compare our Eta rule to previous approaches.1 De�nition of � and EtaWe now work in De Bruijn notation. R��os [R��o93] gives an operational de�nition of � on the set � of pure terms.Indeed, he proves : �(a 1) �!� a1 if a1 is de�ned,with the partial function an, de�ned at the meta-level :(ab)n = anbn(�a)n = �an+1 mn =8<: m� 1 if m > nundefined if m = nm if m < nLemma 1 (R��os) � is the rewrite extension on � of �(a 1) �!� a1 if a1 is de�ned.1In the following, we write con uent instead of ground con uent INRIA

An explicit Eta rewrite rule 5Starting from this and unlike R��os, we try to de�ne a primitive Eta rule. Our reasoning is based on two facts.First, an is an e�ective partial function and should be computed by a rewrite system. Second, the function anshould look like a = substitution according to the following similarities.an+1 leaves unchanged the indexes from 1 to n, decreases the indexes after n+ 2 and rules out n+ 1.a[*n(b=)] leaves unchanged the indexes from 1 to n, decreases the indexes after n + 2 and replaces n + 1 byb["n].We see that an+1 and a[*n(b=)] have the same e�ect if the term a does not contain the index n+ 1. If acontains n + 1, its presence is remembered by a special term, namely ?.Let us de�ne the set of terms ��?.De�nition 2 The set ��? is the set generated by :Terms a ::= n j aa j �a j a[s] j ?Subst s ::= a= j * (s) j "Naturals n ::= n+ 1 j 1:Now, we are able to de�ne a rule on ��? which we call Eta :De�nition 3 Let a; b 2 ��?. Eta is the rewrite extension on ��? of :�(a 1) �!Eta a[?=]As ? is a constant, we add the rule :De�nition 4 �? is : � [ f?[s] !?g.In appendix B, we extend the properties of �� proved in [LRD94a] to a ��-calculus with a �nite set of constants.Lemmas 16 and 17 prove that a[*n(?=)] has the expected behaviour :Lemma 2 Let m � 1 and n � 0.1. m [*n(?=)] ��!� m if 1 � m � n2. n + 1 [*n(?=)] ��!� ?["n] ��!�? ?3. m [*n(?=)] ��!� m � 1 if m � n+ 2.We show that Eta is correct on pure terms w.r.t. �, that is to say, an Eta-rewrite followed by �-normalisationis equivalent to an �-contraction. We introduce another relation �0 de�ned on � and we prove this relation isactually � :De�nition 5 Let a 2 �. �(a 1) �!�0 b i� �(a 1) �!Eta a[?=] and �(a[?=]) = b 2 �. We extend �0 by rewriteextension on �.Lemma 3 Let a 2 �, an+1 is de�ned if and only if �(a[*n(?=)]) 2 � and in that casean+1 = �(a[*n(?=)]).Proof :1. Let a 2 � and suppose that an+1 is de�ned. We proceed by structural induction on a :(a) a = mBy hypothesis, an+1 exists, so a = m 6= n+ 1.i. m > n+ 1, mn+1 = m � 1By lemma 2, �(m [*n(?=)]) = m � 1 2 �;= mn+1ii. m < n+ 1;mn+1 = mBy lemma 2, �(m [*n(?=)]) = m 2 �;= mn+1RR n�2417

6 Daniel BRIAUD(b) a = �bAs an+1 is de�ned and an+1 = (�b)n+1 = �bn+2, bn+2 is de�ned. Then, by inductionhypothesis, �(b[*n+1(?=)]) 2 � and equals bn+2.a[* n(?=)] = (�b)[* n(?=)]�!� �(b[* n+1(?=)])��!� �(bn+2)2 �= (�b)n+1= an+1(c) a = bcImmediate by application of the induction hypothesis to b and c.2. Let a 2 � and suppose �(a[*n(?=)]) 2 �. an+1 is de�ned. Indeed, by structural induction on a :(a) a = mSuppose an+1 is not de�ned. Therefore a = n+ 1 and by lemma 2, �(n + 1 [*n(?=)]) =?["n] 62 �. This contradicts the hypothesis, so an+1 is de�ned.(b) a = �b�((�b)[* n(?=)]) = ��(b[* n+1(?=)]) 2 �. So �(b[* n+1(?=)]) 2 �, and by inductionhypothesis, bn+2 is de�ned. As an+1 = (�b)n+1 = �bn+2, an+1 is de�ned.(c) a = bcImmediate by application of the induction hypothesis to b and c.2We now prove equivalence of � and �0 contractions for redexes located at the head of terms :Lemma 4 Let a 2 �, �(a 1) �!� a1 if and only if �(a 1) �!�0 �(a[?=]) = a1.Proof :1. Suppose �(a 1) �!� a1. By previous lemma, as a1 is de�ned, we know : �(a[?=]) = a1 2 �. So�(a 1) �!Eta a[?=] ��!� a1. That is to say, �(a 1) �!�0 �(a[?=]) = a1 2 �.2. Suppose �(a1) �!�0 �(a[?=]) 2 �. By previous lemma, a1 is de�ned and equals �(a[?=]). So,�(a 1) �!� �(a[?=]).2More generally, by rewrite extension on �, we get the following proposition :Eta followed by the �-normalisation2correctly implements the classical �-reduction.Proposition 1 (Correction) Let a; b 2 �, a �!� b if and only if a �!�0 b.So we achieve our aim: we compute the �-reduct by a �rst order term rewriting system, as this computation isexpressed through explicit substitutions.Beta is now extended to ��? :De�nition 6 Let a; b 2 ��?. Beta is the rewrite extension on ��? of : (�a)b �!Beta a[b=]The de�nition of �0 w.r.t. [LRD94a] is unchanged :De�nition 7 Let a; b 2 �. �0 is the rewrite extension on � of : (�a)b �!�0 �(a[b=])�0 is correct w.r.t. �, as already proved in [LRD94a].2We do not need the constant rule ?[s] ! ? INRIA

An explicit Eta rewrite rule 72 Con uence of ��0The Eta rule leads us to a new view of the classical �-contraction, i.e. � expressed in classical formalism (withoutDe Bruijn notation). Indeed, we de�ne a new �-contraction in the classical �-calculus, denoted by �0 as :�x:(a x) �!�0 af?=xgNotice that �0 is unconditional. As shown by correction, this rule coincides with classical � in the case x isnot a free variable of a. In the other case, classical � is not allowed, but �0 is. In some cases, it makes sense toforget the precondition on the application of classical �. The following examples show that some �0-contractions,classically forbidden, can in fact be allowed and keep the whole calculus con uent.1. (�xy:x)(�x:x)(�x:x x) �!�0 (�xy:x)(�x:x)? ��!� (�x:x)(�xy:x)(�x:x)(�x:x x) ��!� (�x:x)2. �x:((�y:z)x x) �!�0 (�y:z)? �!� z�x:((�y:z)x x) �!� �x:(z x) �!�0 z3. (�u:(�x:uxx))(�y:z) �!�0 (�u:u?)(�y:z) �!� (�y:z)? �!� z(�u:(�x:uxx))(�y:z) �!� (�x:(�y:z)xx) �!� (�x:zx) �!�0 zThe rest of this section is devoted to the study of this unconditional �0. To be consistent with our older de�-nitions, we go back to De Bruijn notation, but the following statements hold in classical �-calculus. First, weextend � to �?, the set of pure terms that may contain ? constant occurences. We de�ne unconditional �0 onthis set. Next, we look for a set �m on which the relation ��0 is con uent. To prove this con uence, we �rstshow the postponement of �0-steps w.r.t. �-steps.We de�ne �0 and �0 on the set �? :De�nition 8 (�?) The set �? is the set generated by :Terms a ::= n j aa j �a j ?Naturals n ::= n+ 1 j 1:De�nition 9 Let a; b 2 �?.1. �0 is the rewrite extension on �? of : (�a)b �!�0 �?(a[b=])2. �0 is the rewrite extension on �? of : �(a 1) �!�0 �?(a[?=])In appendix B, we show that �0 and classical � coincide on the set �?, as ? is a constant. So we will write �for both.��0 is clearly not con uent on �?, i.e. on the set of terms containing ? occurences, as shown by the criti-cal pair between � and �0 : ab ��0 (�(a 1))b �!�0 a[?=]bIn �?, we have the counter-example : 1 1 ��0 (�(1 1)) 1 �!�0 ? 1But by restricting �0 to a reasonably large subset of �?, we can make ��0 con uent. This set is �m :De�nition 10 �m = fa 2 �?j9b 2 � : a ��!��0 bgThis set is larger than � and than the set used by Hardin and R��os in the sense that �0 contains more reductionsand �m contains terms with occurences of ? (See �g. 2). For example, the terms (�(1 1)) 1 and 1 1 belong to�m, but ? 1 does not.As already noticed, an �0-contraction does not necessarily coincide with a classical �-contraction. We qua-lify such an �0-contraction as biased. In the following, we show that on the set �m, we can either postpone aRR n�2417

8 Daniel BRIAUDη’

Λ m

Λ ⊥Figure 2: Relations between �m and �?biased �0-contraction and so transform it in a classical � one, or eliminate it. This way, con uence of ��0 followsimmediately. Consider the reduction : a �!�0 b �!� cWe successively prove :1. the below case : when the �0-redex is strictly contained in the �-redex, it can be postponed and may beduplicated (or eliminated).2. the upon case : when the �0-redex strictly contains the �-redex, it can be postponed.3. the critical case : when there is a critical pair, the �0-contraction can be eliminated.The �rst two cases hold in �?, the last one holds only in �m. Due to potential duplication, there is a technicalityfor the below case.First, we show the below case. To treat it formally and according to the philosophy of explicit substitution,we need what is called projection lemmas. In the case of Eta, this lemma says that an Eta-rewrite betweenterms of ��? translates in a �0-reduction between their �?-normal forms. If the Eta-rewrite takes place insidea closure [ ] we call it internal, if it takes place outside each closure, we call it external. External and internalare abbreviated by the superscripts ext and int.Lemma 5 (Projection lemmas on �?)1. If a; b 2 ��? such that a �!Etaext b then �?(a) �!�0 �?(b). INRIA

An explicit Eta rewrite rule 92. If a; b 2 ��? such that a �!Etaint b then �?(a) ��!�0 �?(b)The proof of this lemma is in appendix C. The Beta projection lemma is similar, its proof extends the one givenin [LRD94a] (Cf appendix B).Lemma 6 (The case �0 below �) Let a; b; c 2 �.1. If (�a)b �!�0 (�c)b �!� �?(c[b=]) then (�a)b �!� �?(a[b=]) �!�0 �?(c[b=]).2. If (�b)a �!�0 (�b)c �!� �?(b[c=]) then (�b)a �!� �?(b[a=]) ��!�0 �?(b[c=]).The proof comes directly from the projection lemma 5.Proof :1. We suppose : (��(a 1))b �!�0 (��?(a[?=]))b �!� �?(�?(a[?=][b=])) = �?(a[?=][b=])We observe : (��(a 1))b �!Betaext (�(a 1))[b=] �!Etaext a[?=][b=]By external projection lemmas, we get :(��(a 1))b �!� �?((�(a 1))[b=]) �!�0 �?(a[?=][b=])The key part, i.e. Barendregt style substitution lemma [Bar84], is inside the projection lemma:a[*(b=)][?=] � !�? a[*(b=)][?[b=]=] � !�? a[?=][b=]2. We suppose :(�b)(�(a 1)) �!�0 (�b)(�?(a[?=])) �!� �?(b[�?(a[?=])=]) = �?(b[a[?=]=])We observes : (�b)(�(a 1)) �!Betaext b[(�(a 1))=] �!Etaint b[a[?=]=]By external and internal projection lemmas, we get :(�b)(�(a 1)) �!� �?(b[(�(a 1))=]) ��!�0 �?(b[a[?=]=])2Lemma 7 (The case �0 above �) Let a; c 2 �?. If �(a 1) �!�0 �?(a[?=]) �!� c then there exists d 2 �? suchthat �(a 1) �!� d �!�0 c.Proof : We translate the hypothesis�(a 1) �!�0 �?(a[?=]) �!� cinto a �-reduction : (� a)? �!� �?(a[?=]) �!� cSince ? is not an abstraction, the �rst �-contraction does not create a �-redex in �?(a[?=]). So, thestructure of the �-redex in �?(a[?=]) is already in a. Hence, there exists a d 2 �? such that :a �!� dAs we have : (� a)? �!� �?(a[?=]) �!� c(� a)? �!� (� d)? �!� �?(d[?=])RR n�2417

10 Daniel BRIAUDBy the substitution lemma for � [HS86], we get :c = �?(d[?=])Back to �0-contraction, we get the postponement :�(a 1) �!� �(d 1) �!�0 �?(d[?=]) = c2The previous lemmas imply :Lemma 8 Let a; b; c 2 �?. If a ��!�0 b ��!� c when �0 is below or above � then there exists d 2 �? such that :a ��!� d ��!�0 b.The proof is by a double induction on, �rst, the length of the �0-reduction, and, second, the length of the�-reduction.The following lemma shows what becomes of the classical commutation of classical � and �.Lemma 9 (The critical case) LetM;N 2 �?. If (�(M 1))N �!�0 (�?(M [?=]))N ��!� P 2 � then (�(M 1))N ��!� P .Proof : We prove it with the classical formalism. Here, we treat ? as a free variable and we rename? by >, a fresh variable, in M and N :N 0 � N [>=?] and N 0 � N [>=?]. We have :(�x:M 0 x)N 0 �!�0 (M 0[?=x])N 0 ��!� P 2 �By stability of � (or substitution lemma [HS86]) :((M 0[?=x])N 0)[N 0=?] ��!� P [N 0=?]As ? =2 FV (N 0P ), P [N 0=?] = P and N 0[N 0=?] = N 0.(M 0[?=x][N 0=?])N 0 ��!� PAnd M 0[?=x][N 0=?] = M 0[N 0=x], (M 0[N 0=x])N 0 ��!� PBy �-expansion : (�x:M 0 x)N 0 ��!� PBy renaming, as > =2 FV (MN ), (�x:M x)N ��!� P2Lemma 10 (Postponement of �0-contractions) Let a 2 �m and c 2 � such that : a ��!��0 c. Then there existsd 2 � : a ��!� d ��!� c.Proof : We proceed by induction on the number of �0-steps. We consider the last �0 step. If there isno �0-step, we get the result. If this step is a critical case, by lemma 9, we eliminate it. If this step isan upon or below case, by lemma 8, it is postponed and may be duplicated (or eliminated). As only�-steps eliminate ? occurences, �nal �0-steps are in fact classical �-steps : a ��!��0 b ��!� c and b 2 �, sothat we apply the induction hypothesis on a ��!��0 b. 2Theorem 1 ��0 is con uent on �m. INRIA

An explicit Eta rewrite rule 11Proof : Let a; b; c 2 �m such that a ��!��0 b and a ��!��0 c. As b; c 2 �m, there exists b0; c0 2 � such thatb ��!��0 b0 and c ��!��0 c0. So : a ��!��0 b0 a ��!��0 c0By previous lemma, we associate to these two reductions two classical ones :a ��!�� b0 a ��!�� c0As classical �� is con uent on � plus a constant, there exists d 2 � (d 62 �? because �-steps arecorrect and b0; c0 2 �) : b0 ��!�� d c0 ��!�� dBy correction, �0 can simulate � : b0 ��!��0 d c0 ��!��0 d2The de�nition of �m is very general and we do not know a syntactic characterization for it (we conjecture thereis none). If one wants to implements an �0 reduction strategy, one may wish to know if one stays in �m. Theabsence of a syntactic characterization seems to prevent providing such a criterion. Even a smaller set, like,fa 2 �?j9b 2 � : a ��!� bgis of no more help. Nevertheless, �0 sheds more light on the relation between � and �.3 Con uence and strong normalization of ���In this section, we study two properties of ���, the rewrite system fBeta;Etag [ �?, namely con uence andstrong normalization. The proof of these properties are straightforward extension of �� ones, so we just sketchthem.3.1 Con uence of ���We prove con uence of ���, the theory �� augmented with the rule Eta on a smaller and handy set :De�nition 11 ��� = fa 2 ��?j9b 2 �� : a ��!� bgWe prove the con uence of ��� by the interpretation method [HL89]. We review it for our particular case.Consider the relation ��� de�ned on the set ��� and such that :1. ��� = R [ �? with R = fBeta;Etag2. �? is convergent, that is to say con uent and strongly normalizing, on the set � of �?-normal forms of���.3. �� � (���)�If 1. �� is de�ned on the set � of �?-normal forms of ���, and2. the projection lemmas on � hold : a Beta (resp. Eta) contraction between terms of ��� translates in a �(resp. �) reduction between their �?-normal forms.then �� is con uent on � if and only if ��� is con uent on ���.So the con uence of ��� on ��� relies on the projection lemmas of Beta and Eta on �. In a �rst step, we recallthe projection lemmas concerning terms of ��? :RR n�2417

12 Daniel BRIAUDLemma 11 (Projection lemmas on �?) If a; b 2 ��? such that a �!Beta b (resp. a �!Eta b) then �?(a) ��!� �?(b)(resp. �?(a) ��!�0 �?(b)).As a subcase, as �?(b) 2 � for b 2 ���, we get :Corollary 1 (Projection lemmas on �) If a; b 2 ��� such that a �!Beta b (resp. a �!Eta b) then �?(a) ��!� �?(b)(resp. �?(a) ��!�0 �?(b)) and �?(a); �?(b) 2 �.Theorem 2 The reduction ��� is con uent on ���.So, we prove the ground con uence of ��� on a set equivalent to, on the one hand, the classical one, on theother hand, the Hardin ground one. Unlike Hardin, we can not achieve a stronger result, i.e. con uence on termscontaining variables of type Term or Substitution. Indeed, there is a counter-example to such a con uence,which is already present in �� :a[b=][s] �Beta ((�a)b)[s] +�!� (�a[*(s)])(b[s]) �!Beta a[*(s)][b[s]=]If we consider a, b and s as variables, we get two distinct �-normal forms. But for each ground instance of a, band s, we have (Cf appendix B) : a[b=][s] � !� a[*(s)][b[s]=]That is to say, it is a theorem of the inductive theory, not of the equational theory of �. On the contrary, ��*-calculus is con uent on open terms [HL89]. As a counterpart, typed �� is strongly normalizing, an interestingproperty which does not hold in ��*, nor in �� [Mel95].3.2 Strong normalization of typed ���We now look at the preservation of strong normalisation of ��� on ��? terms. Then, we deduce strong norma-lisation of ��� on simply typed terms.We adapt the �� strong normalization preservation proof [LRD94a] and comment it. The main ideas are : usethe strong normalization of ��0 and the fact that b= substitutions, with b 6= ?, come from Beta rewrites. Weemphasize the fact that this last property of � is essential to this proof of strong normalization of �� and ���.The following lemma formalizes this property.Lemma 12 Let a0 2 �? such that a0 ��!��� an � Cfd[*i(c=)]g with c 6= ?. Then there exists ai, 0 � i � n suchthat : ai � Df(�e)bg and b ��!��� c.The proof can be found in [BBLRD94]. This lemma does not hold in the � calculus because of the rule(a � s) � t ! a[t] � (s � t). Indeed, one observes that it creates a closure [ ] and so it may create [b � id],the equivalent in �� of [b=] [Mel95].We now state the second key point of this normalization proof : this lemma isolates the sources of the potentiallyin�nite derivations in closures [ ].Lemma 13 Let a 2 ��? such that �?(a) is strongly normalizing. In a ��� derivation starting from a, thereexists a rank N such that each ���-step following N is internal.That property, proved in [LRD94a], depends only on �, not on Beta, ? or Eta. It is not shared by the �substitution calculus [ACCL91] because of the same rule. Indeed, in the �-derivation :1 [(a � s) � t] !int 1 [a[t] � (s � t)] !ext a[t]the external redex 1 [ � ] produced by the internal �-rewrite (a � s) � t ! a[t] � (s � t) can not be pushed up.By the two previous lemmas, we get :Theorem 3 Let a 2 ��? such that �?(a) is ��0-strongly normalizing. Then, a is ��?-strongly normalizing.INRIA

An explicit Eta rewrite rule 13The proof follows closely the �� case, described in [BBLRD94]. It is based on a minimal counter-example, moreprecisely a minimal ���-derivation.So ��� preserves strong normalization. As a consequence, we derive strong normalization of a simply typedversion of ��� on ��?. For this, �rst, we need a typing system, second, we have to show ��0 is strongly norma-lizing on simply typed pure terms.Thus, we enlarge �� simply typed terms [LRD94a] to ��� ones. This part heavily relies on the simply typedversion of ��-calculus described in [LRD94a]. To introduce a typed Eta rule, we have to type terms of ��?.For this, instead of a single constant ?, we need, for each simple type A, a typed constant ?A and a rule?A[s] ! ?A. We just add an axiom scheme to the typing system of �� in order to type ?A and termscontaining occurences of ?A.The grammar of the pseudo-terms is:Type A ::= A1 j : : : j An j A) BNaturals n ::= 1 j n+ 1Terms a ::= n j ab j �A:a j a[s] j ?ASubstitutions s ::= a= j " j *(s)Context � ::= [ ] j A � �where A1 : : :An is a family of atomic types. The set of ���-simply typed terms is noted ��!? and is producedby the typing system :Terms � ` ?A : A� ` a : A) B � ` b : A� ` ab : B A � � ` a : B� ` �A:a : A) B� ` a : A � ` s : �� ` a[s] : A A � � ` 1 : A � ` n : AB � � ` n+ 1 : ASubstitutions � ` a : A� ` a= : A � � A � � ` ": � � ` s : �A � � ` *(s) : A ��We de�ne a typed Eta rule accordingly :Lemma 14 (Subject reduction theorem) Let a 2 ��?. The rewrite extension on ��? of �A:(a 1) �!Eta a[?A=],that is to say typed Eta, preserves types.Proof :A � � ` a : A) B A � � ` 1 : AA � � ` a 1 : B� ` �A:(a 1) : A) B A � � ` a : A) B � ` ?A : A� ` ?A= : A � �� ` a[?A=] : A) B2So, having de�ned simply typed terms, it remains to show ��0 strong normalization on simply typed pure terms.We note the set of simply typed pure terms �!? ; it is a subset of ��!? .Lemma 15 Let a 2 �!? , a is ��0-strongly normalizing.The adaptation of the �� case [HS86] is quite straightforward. It relies on an easy "reverse" substitution lemma:let M;L be pure terms and x; y be variables. if Mfy=xg�!��0 L then there is a pure term N such that : M�!��0 Nand L � Nfy=xg.The conditions of the preservation theorem 3 are ful�lled , so :Corollary 2 Let a 2 ��!? , a is ���-strongly normalizing.RR n�2417

14 Daniel BRIAUDConclusionHardin and R��os de�nition3 of Eta [Har92, R��o93] in the framework of ��, is:�(a 1) �!Eta b if �(a) = �(b["]) (HR)which raises few comments. That rule does not make the �-reduct computation explicit since it uses an�-matching [JK91] instead of our �?-normalization. More precisely, imagine Eta applied on a term �(a 1).To apply rule (HR), one must solve, modulo the theory �, the equation a =� b["] where b, the Eta-reduct, isthe unknown (the variable to instantiate). This computation is what we call �-matching. Clearly, �-matching ismore complex than �?-normalization: we do not even know whether �-matching is decidable or not and since�-matching may produce several solutions, rule (HR) may produce several reducts for the same Eta-redex,among them the classical �-reduct. Consequently, rule (HR) is less operational than our Eta rule.Moreover, our Eta rule is generic. Indeed, in this report we apply our de�nition to ��. But all we need inorder to de�ne Eta is a term rewriting system that computes �-contraction; for instance we do not use re-naming operators like ". Hence, Eta can be adapted to every �-calculus of explicit substitution, with explicitnames or not. For instance, in ��* [HL89], we would write :�(a 1) �!Eta a[? � id]and in �� [LRD94b] : �xi:(a xi) �!Eta a[?=xi]0Last, our rule is unconditional. We have seen that this lead to a very general alternative of the classical �,namely �0 which does not require De Bruijn notation. The condition of application of the classical � rule is toostrong and as we have shown, there are other con uent reductions which are not captured by this rule. Thisexampli�es our conviction that explicit substitutions help to a deeper understanding of �-calculus, not only ofits �-reduction aspect but also of other aspects like �-reduction. In that manner, according to Curry [CF58],explicit substitutions concur to precise the fundamentals of logic.Acknowledgments. We would like to thank Pierre Lescanne and Jocelyne Rouyer-Degli for their constantsupport, and Philippe de Groote and Roberto Amadio for their remarks.3To be consistent with our notations, we take R��os syntax. INRIA

An explicit Eta rewrite rule 15References[ACCL91] M. Abadi, L. Cardelli, P.-L. Curien, and J.-J. L�evy. Explicit substitutions. Journal of FunctionalProgramming, 1(4):375{416, 1991.[Bar84] H. P. Barendregt. The Lambda-Calculus, its syntax and semantics. Studies in Logic and theFoundation of Mathematics. Elsevier Science Publishers B. V. (North-Holland), Amsterdam, 1984.Second edition.[BBLRD94] Z. Benaissa, D. Briaud, P. Lescanne, and J. Rouyer-Degli. ��, a calculus of explicit substitutionswhich preserves strong normalisation. Submitted, December 1994.[CF58] H. B. Curry and Feys. Combinatory Logic, volume 1. Elsevier Science Publishers B. V. (North-Holland), Amsterdam, 1958.[Cur83] P.-L. Curien. Combinateurs cat�egoriques, algorithmes s�equentiels et programmation applicative.Th�ese de Doctorat d'Etat, Universit�e Paris 7, 1983.[Cur86a] P.-L. Curien. Categorical combinators. Information and Control, 69:188{254, 1986.[Cur86b] P.-L. Curien. Categorical Combinators, Sequential Algorithms and Functional Programming. Pit-man, 1986.[dB72] N. G. de Bruijn. Lambda calculus with nameless dummies, a tool for automatic formula mani-pulation, with application to the Church-Rosser theorem. Proc. Koninkl. Nederl. Akademie vanWetenschappen, 75(5):381{392, 1972.[dB78] N. G. de Bruijn. A namefree lambda calculus with facilities for internal de�nition of expressions andsegments. TH-Report 78-WSK-03, Technological University Eindhoven, Netherlands, Departmentof Mathematics, 1978.[Har87] Th. Hardin. R�esultats de con uence pour les r�egles fortes de la logique combinatoire cat�egorique etliens avec les lambda-calculs. Th�ese de Doctorat d'Etat, Universit�e Paris 7, 1987.[Har89] Th. Hardin. Con uence results for the pure strong categorical combinatory logic CCL: �-calculi assubsystems of CCL. Theoretical Computer Science, 65:291{342, 1989.[Har92] Th. Hardin. Eta-conversion for the languages of explicit substitutions. In 3rd ALP, LNCS 632,Volterra, Italy, 1992.[HL89] Th. Hardin and J.-J. L�evy. A con uent calculus of substitutions. In France-Japan Arti�cialIntelligence and Computer Science Symposium, Izu, 1989.[HS86] J. Roger Hindley and Johnathan P. Seldin. Introduction to Combinators and Lambda-calculus.Cambridge University, 1986.[JK91] J.-P. Jouannaud and Claude Kirchner. Solving equations in abstract algebras: a rule-based surveyof uni�cation. In Jean-Louis Lassez and G. Plotkin, editors, Computational Logic. Essays in honorof Alan Robinson, chapter 8, pages 257{321. The MIT press, Cambridge (MA, USA), 1991.[Les94] P. Lescanne. From �� to ��, a journey through calculi of explicit substitutions. In Hans Boehm,editor, Proceedings of the 21st Annual ACM Symposium on Principles Of Programming Languages,Portland (Or., USA), pages 60{69. ACM, 1994.[LRD94a] P. Lescanne and J. Rouyer-Degli. The calculus of explicit substitutions ��. Technical ReportRR-2222, INRIA-Lorraine, January 1994.[LRD94b] P. Lescanne and J. Rouyer-Degli. Explicit substitutions with de Bruijn's levels, August 1994.[Mel95] P.-A. Melli�es. Typed �-calculi with explicit substitutions may not terminate. In M. Dezani, editor,Int. Conf. on Typed Lambda Calculus and Applications, 1995.[R��o93] A. R��os. Contributions �a l'�etude des �-calculs avec des substitutions explicites. Th�ese de Doctoratd'Universit�e, U. Paris VII, 1993.RR n�2417

16 Daniel BRIAUDA Quotation from Curry and FeysWe quote Curry and Feys [CF58] : `Combinatory logic is a branch of mathematical logic which concerns itselfwith the ultimate foundations. Its purpose is the analysis of certain notions of such basic character that theyare ordinarily taken for granted. These include the processes of substitution usually indicated by the use ofvariables; and also the classi�cation of entities constructed by these processes into types or categories, whichin many systems has to be done intuitively before the theory can be applied. It has been observed that thesenotions, although generally presupposed are not simple; they constitute a prelogic, so to speak, whose analysisis by no means trivial. [...] It is the synthetic theory4 which gives the ultimate analysis of substitution interms of a system of extreme simplicity. The theory of lambda-conversion is intermediate in character betweenthe synthetic theory and ordinary logics. Although its analysis is in some ways less profound - many of thecomplexities in regard to variables are still unanalysed there - yet it is none the less signi�cant; and it has theadvantage of departing less radically from our intuitions.'B Properties of applied ��-calculusWe add a �nite set of constants to ��, forming ��c, and their associated constant rules c[s] ! c to �, thenTheorem 4 (Convergence of �c)1. �c terminates.2. �c is orthogonal, therefore con uent.Remark 1 (well-foundedness of (�!�c [ =)+) The termination of �c is proved with a simpli�cation ordering,>. So it contains = and �!�c , and therefore the transitive closure of their union.Remark 2 (application and abstraction structure is preserved) As no left hand side of �c rules is anapplication or an abstraction, for a; b 2 �c,1. �c(ab) = �c(a)�c(b)2. �c(�a) = ��c(a)Remark 3 (Church-Rosser consequence) As �c is Church-Rosser, for a; s 2 �c, �c(a[s]) = �c(�c(a)[�c(s)])Lemma 16 For n � 1 and i � 0, n [*n+i(s)] ��!�c n.Lemma 17 For n � 1 and i � 0, n + i [*i(s)] ��!�c n[s]["i].Corollary 3 (Barendregt style Substitution Lemma) a[b=][s] � !�c a[*(s)][b[s]=]:Theorem 51. the projection lemma for Beta holds : a Beta-rewrite between terms of ��c translates in a �-reductionbetween their �?-normal forms.2. Beta is con uent on ��c, by previous item.C Eta projection lemma on �?In the next lemma, we prove that an external (in the term part) Eta-rewrite corresponds to exactly one �0-reduction. In particular, an external Eta-redex structure does not tamper with �?-normalization. (basic case :4 b)Lemma 18 (External Projection Lemma) Let a; b 2 ��?,if a �!Eta extb then �?(a) �!�0 �?(b).4what we now call combinatory logic INRIA

An explicit Eta rewrite rule 17Proof : By noetherian induction with the well-founded order �!�? .1. a = �(c 1) : by Remark 2 and Remark 3, �?(a) = �?(�(c 1)) = �(�?(a) 1) �!�0 �?(�?(a)[?=]) =�?(a[?=]) = �?(b)2. a = �c �!Eta ext�c0As c �!Eta extc0, by induction hypothesis : �?(c) �!�0 �?(c0).By compatibility of �0 : ��?(c) �!�0 ��?(c0).And �?-normalisation left unchanged the abstraction structure, so : �?(�c) �!�0 �?(�c0).3. a = cd : as previous case.4. a = c[s] �!Eta extc0[s]. We can not apply the same reasoning, because � is not de�ned on ��?, sowe have not the compatibility step. We must look at the structure of c :(a) a = de[s] �!Eta extd0e[s] = b. We have :a = de[s] �!� d[s]e[s]By compatility of Eta on ��?, d[s]e[s] �!Eta d0[s]e[s]By induction hypothesis, �?(d[s]e[s]) �!�0 �?(d0[s]e[s])And �?-normalisation left unchanged the application structure, so :�?(de[s]) �!�0 �?(d0e[s])�?(a) �!�0 �?(b)(b) a = �(d 1)[s] �!Eta e[s] = b�?(a) = �?((�(d 1))[s]) = �?(�(d[* (s)] 1 [* (s)])= �(�?(d[* (s)]) 1)�!�0 �?(�?(d[* (s)])[?=])= �?(d[* (s)][?=])= �?(d[* (s)][?[s]=])= �?(d[?=][s]) = �?(b)(c) a = (� d)[s] �!Eta (� e)[s] = b and d �!Eta eWe have : (� d)[s] �!�? �(d[* (s)]) so (� d)[s] >(�!�? =) �(d[* (s)]) By compatibility of Eta,�(d[* (s)]) �!Eta �(e[* (s)])By induction hypothesis, �?(�(d[* (s)]) �!�0 �?(�(e[* (s)]))�?((� d)[s])) �!�0 �?((� e)[s])�?(a) �!�0 �?(b)(d) a = d[t][s] �!Eta exte[t][s] = b and d �!Eta e.d[t] is a subterm of d[t][s], so we can apply the induction hypothesis on it :�?(d[t]) �!�0 �?(e[t])By de�nition of �0 there exists g such that :�?(d[t]) �!Eta g �!�? �?(e[t])RR n�2417

18 Daniel BRIAUDBy compatibility of Eta on �? :�?(d[t])[s] �!Eta g[s] �!�? �?(e[t])[s]As a closure is not in �?-nf, �?(d[t])[s] <(�!�? =) d[t][s], so we can apply the inductionhypothesis : �?(�?(d[t])[s]) �!�0 �?(�?(e[t])[s])And by convergence of �? : �?(d[t][s]) �!�0 �?(e[t][s])�?(a) �!�0 �?(b)2In the following lemma, we prove that an internal Eta-rewrite corresponds to zero, one or several �-contractions.We point out where the Eta-redexes are eliminated or duplicated.Lemma 19 Let a,b 2 ��?, if a �!Eta intb then �?(a) ��!�0 �?(b).Proof : By noetherian induction with the well-founded order (�!�? =).1. a = �c �!Eta int�c = b. By induction hypothesis on c and compatibility of � on �.2. a = cd. Idem.3. a = c[s](a) c[s] �!Eta intc[t]. By next `lemma'.(b) c[s] �!Eta intd[s].As c �!Eta intd, by induction hypothesis :�?(c) ��!�0 �?(d)By correction, Eta simulates �0 on pure terms,�?(c) �!Etaext c0 �!�? �?(c0) : : : �?(d)The Eta-rewrite are external because pure terms contain no closure. By compatibility ofEta and �? : �?(c)[s] �!Etaext c0[s] �!�? �?(c0)[s] : : : �?(d)[s]By zero or more applications of the external projection lemma,�?(�?(c)[s]) �!�0 �?(c0[s]) = �?(�?(c0)[s]) : : : �?(�?(d)[s])By remark 3, �?(c[s]) ��!�0 �?(d[s])2We extract a particular case of the previous proof :Lemma 20 Let a,b 2 ��?,if a[s] �!Eta inta[t] then �?(a) ��!�0 �?(b).Proof : We suppose : s �!Eta t INRIA

An explicit Eta rewrite rule 191. a = bc and (bc)[s] �!Eta (bc)[t]bc[s] �!�? b[s]c[s] = c[s] so bc[s] >(�!�? =) b[s]As b[s] �!Eta b[t]by induction hypothesis : �?(b[s]) ��!�0 �?(b[t])Similarly, �?(c[s]) ��!� �?(c[t])By compatibility of �, �?(b[s])�?(c[s]) ��!�0 �?(b[t])�?(c[s])�?(b[t])�?(c[s]) ��!�0 �?(b[t])�?(c[t])By transitivity of �, �?(b[s])�?(c[s]) ��!�0 �?(b[t])�?(c[t])By remark 2, �?(bc[s]) ��!�0 �?(bc[t])Here, the Eta-redex is duplicated. (We use twice the induction hypothesis.)2. a = �c and (�c)[s] �!Eta (�c)[t](�c)[s] �!�? �(c[* (s)]) so (�c)[s] >(�!�? =) �(c[* (s)])By compatibility of Eta on ��? : �(c[* (s)]) �!Eta �(c[* (t)])By induction hypothesis on �(c[* (s)]),�?(�(c[* (s)])) ��!�0 �?(�(c[* (t)])By remark 2, �?((�c)[s]) ��!�0 �?((�c)[t])3. a = c[u] and c[u][s] �!Eta c[u][t]c[u][s] +�!�? �?(c[u])[s] so c[u][s] >(�!�? =) �?(c[u])[s]By compatibility of Eta on ��? : �?(c[u])[s] �!Eta �?(c[u])[t]By induction hypothesis on �?(c[u])[s],�?(�?(c[u])[s]) ��!�0 �?(�?(c[u])[t])By remark 3, �?(c[u][s]) ��!�0 �?(c[u][t])4. a = m and n [s] �!Eta m [t]. The form of s is necessarily : * i(c=). So, we suppose :n [* i(c=)] �!Eta n [*i(d=)] with c �!Eta d.RR n�2417

20 Daniel BRIAUD(a) m = 1; i = 0 and 1 [c=] �!Eta 1 [d=]1 [c=] �!�? 1 so 1 [c=] >(�!�? =) 1i. c �!Eta intd. By induction hypothesis :�?(c) ��!�0 �?(d)ii. c �!Eta extd. By external projection lemma:�?(c) ��!�0 �?(d)As �?(1 [c=]) = �?(c), �?(1 [c=]) ��!�0 �?(1 [d=])�?(m [s]) ��!�0 �?(m [t])Notice that we need the external projection lemma to prove the internal one (but notconversely).(b) m = n+ 1; i = 0 and n+ 1 [c=] �!Eta n+ 1 [d=]As, �?(n+ 1 [c=]) = n = �?(n+ 1 [d=]), trivially :�?(n + 1 [c=]) ��!�0 �?(n + 1 [d=])�?(m [s]) ��!�0 �?(m [t])Here, we see that a Eta-redex is eliminated by the rule RV ar(c) m = 1; i = j + 1 and 1[*(* j(c=))] �!Eta 1[* (* j(d=))]As, �?(1[*(* j(c=))]) = 1 = �?(1[* (* j(d=))]), trivially :�?(1[* (* j(d=))]) ��!�0 �?(1[* (* j(d=))])�?(m [s]) ��!�0 �?(m [t])Here, we see that a Eta-redex is eliminated by the rule FV arLift(d) m = n+ 1; i = j + 1 and n+ 1 [*(* j(c=))] �!Eta n + 1 [* (* j(d=))]By compatibility of Eta on ��?,n [* j(c=)]["] �!Eta intn [* j(d=)]["]n+ 1 [*(* j(c=))] �!�? n [* j(c=)]["] so n+ 1 [*(* j(c=))] >(�!�? =) n [* j(c=)]["]By induction hypothesis : �?(n [* j(c=)]["]) ��!�0 �?(n [* j(d=)]["])As �?(n [* j(c=)]["]) = �?(n + 1 [*(* j(c=))]),�?(n + 1 [*(* j(c=))]) ��!�0 �?(n + 1 [*(* j(d=))])�?(m [s]) ��!�0 �?(m [t])2 INRIA

Unite de recherche INRIA Lorraine, Technopole de Nancy-Brabois, Campus scientifique,615 rue du Jardin Botanique, BP 101, 54600 VILLERS LES NANCY

Unite de recherche INRIA Rennes, Irisa, Campus universitaire de Beaulieu, 35042 RENNES CedexUnite de recherche INRIA Rhone-Alpes, 46 avenue Felix Viallet, 38031 GRENOBLE Cedex 1

Unite de recherche INRIA Rocquencourt, Domaine de Voluceau, Rocquencourt, BP 105, 78153 LE CHESNAY CedexUnite de recherche INRIA Sophia-Antipolis, 2004 route des Lucioles, BP 93, 06902 SOPHIA-ANTIPOLIS Cedex

EditeurINRIA, Domaine de Voluceau, Rocquencourt, BP 105, 78153 LE CHESNAY Cedex (France)

ISSN 0249-6399