Combinatory Reduction Systems
Jan Willem Klop

Abstract:
*Title of this thesis*
In the present work we are exclusively concerned with the study of syntactical properties of λ—calculus (λ, for short), Combinatory Logic  (CL), Recursive Program Schemes, and in general, Term Rewriting Systems with bound variables; especially those syntactical properties which concern reductions. Hence the title of this thesis; Combinatory Reduction Systems  (CRS's)  is the name by which we refer to Term Rewriting Systems plus bound variables. The word 'combinatory' seems justified to us since it captures the essential feature of these reduction systems: subterms in a CRS-term are manipulated in a 'combinatory way'.

*Motivation*
There is ample motivation for the  (in our case syntactical)  investigation of CRS's. The importance of the paradigms of CRS's, λ and CL, is well—known in Mathematical Logic  (see also our historical remarks below). Moreover, λ and CL play an important role in the semantics of programming languages; we refer to the work of Scott. One can consider λ-calculus as the prototype of a programming language; see MORRIS [68]. Furthermore, in theoretical Computer Science, certain simple CRS's, Recursive Program Schemes, and more general, CRS's without substitution known as Term Rewriting Systems are studied. Then there is the AUTOMATH-project of de Bruijn, at the border—line of Computer Science and Foundations of Mathematics, which has as one of its aims the computer verification of mathematical proofs. Here λ-calculus plays an important role, too; we refer to the recent work of VAN DAALEN [80].
In Proof Theory one is often interested in certain extensions of (typed)  λ-calculus, such as λ^\tau ⊕ recursor R, iterator J, Pairing operators, etc. All these extensions are covered by the concept of a CRS. It is interesting that one encounters in Proof Theory also CRS's which have a variable-binding mechanism other than the usual one in λ-calculus: namely, in the normalization of Natural Deduction proofs. Finally, let us mention that there are recent foundational studies by Feferman in which certain syntactical properties of extensions of λ-calculus are relevant.
We conclude that CRS's arise in a variety of fields and that the study of their syntactical properties is worth-wile.

*Restriction to syntax*
Our restriction to syntactical investigations, as opposed to semantical considerations, is born solely from limitation and is not by principle. Recently, D. Scott, G. Plotkin and others have originated a model theory for the  λ-calculus and extensions thereof;  by means of this one can obtain in a fast and elegant way some results which require much labour in a syntactical treatment. E.g. the consistency of λη ⊕ Surjective Pairing.
We do not feel however that the availability of the powerful modeltheoretic methods lessens the usefullness of Church—Rosser proofs and related syntactical theorems. The reason is the well-known fact that the  (sometimes) tedious work of syntactical investigations yields longer proofs, but also more information. We mention a typical example above: model theory yields a beautiful proof of the consistency of λη ⊕ S.P., but the much longer proof which will appear in DE VRIJER [80]  yields not only consistency, but also conservativity of λη ⊕ S.P. over λη.  (Another reason is that the models of Plotkin and Scott, only bear on extensions of λ-calculus and not on several other Combinatory Reduction Systems.)
Although we have occasionally allowed ourselves a digression for completeness sake, this thesis certainly does not aim to give a survey of the syntax of λ—calculus and extensions. For such a survey we refer to Barendregt's forthcoming monograph 'The lambda calculus, its syntax and semantics'.

*Some history*
We will now give a short sketch of the history of the subject; for a more extensive historical introduction we refer to the introduction in BARENDREGT [80], to the short historical survey in SCOTT [79] and to the many historical comments in CURRY-FEYS [58].
Combinatory Logic starts in 1924 with SCHÖNFINKEL [24]:  'Uber die Bausteine der Mathematischen Logik'. Schönfinkel tries to reduce the number of primitive concepts in  (higher order predicate)  logic; in particular, his aim is to eliminate bound variables. His motivation: asserting e.g. ∀p,q ¬p ∨ (p∨q) for propositions, does not say anything about p,q but only about ¬ and ∨. To obtain his aim he introduces 'combinators' I,K,S,B,C, 'defined' by Ix = x, Kxy = x, Sxyz = xz(yz), Cxyz = xzy and Bxyz = x(yz). (S and K alone are sufficient, as Schönfinkel remarks.)  Schönfinkel then proves in an informal way that every formula A(x1,...,xn), with free variables ⊆{x1,...,xn}, in higher order predicate logic  (where quantification over predicates and over predicates of predicates, and so on, is allowed) can be rewritten as a term Mxl...xn where M is built by application from the combinators and an 'incompatibility predicate' U defined by UPQ ≡ ∀x(¬P(x)∨¬Q(x)).
Example: Let P(g,y,f) be the formula ∀xT(¬fx⋀gxy). Then P(g,y,f) = UF(Cgg) = CU(Cgy)f = BCU(Cg)yf = B(B(CU))Cgyf. Hence every closed formula A can-be rewritten as a term M built from combinators and U; it can even be written as a term NU where N contains only combinators (not U). So, omitting U, every sentence in Schönfinkel's higher order predicate logic can be represented by a term built from the basic combinators alone.
Around 1928 the combinators were rediscovered by H.B. Curry, who tried by means of a 'Combinatory Logic' to investigate the foundations of mathematics. The aim of Curry's program is to use CL to give an analysis of substitution and the use of variables; and to attack the paradoxes like the one of Russell. CL in Curry's program is also referred to as Illative Combinatory Logic, where the word 'illative' denotes the presence of inference rules as in predicate logic. Curry's program does meet certain obstacles; Schönfinkel's naive system was inconsistent (as demonstrated by 'Curry's paradox'), and some later proposed alternative systems also suffered from inconsistency. The foundational claims of Curry's program are not undisputed, cf. SCOTT [79].
With a different motivation, a variant of CL was developed at about the time of Curry's rediscovery of CL, namely 'λ-calculus', by Church, Kleene, Rosser. Kleene was led by the study of λ-terms to his First Recursion Theorem and other fundamental recursion theoretic results;  λ—definability of functions was studied and discovered to be equivalent to various other definitions of 'effective computable' functions  (e.g. the one via Turing machines).  (See Kleene's eye—witness account of this period in CROSLEY [75].)  Rosser demonstrated the close connection between λ-calculus and CL, and established, together with Church, the consistency of λ-Calculus and CL by a syntactical argument.  (The Church-Rosser Theorem for λ-calculus and CL.)
The Church-Rosser theorem yields the existence of term models of λ-calculus and CL. Term models of several versions of λ and CL were studied in BARENDREGT [71]. In the last ten years there has been a break-through in the 'model theory' of λ-calculus and CL, starting with the models D∞ and Pω of Scott and Plotkin. These models are of great importance in the semantics of programming languages.

*Main results*
As the main results of this thesis we consider
(I) the introduction of the concept CR5 and the development of the basic syntactical theorems for CRS's; notably the Church-Rosser theorem (CR), the Lemma of Parallel Moves (PM) and the theorem of Finite Developments (FD), and
(II) simultaneously, the generalization of a method due to R. Nederpelt which enables one to reduce Strong Normalization proofs for certain CRS's to Weak Normalization proofs. This device is not only interesting in itself, but enabled us also to obtain the theorems FD, CR, etc.;
(III)  the negative result that CR fails for certain non—left—linear CRS's, e.g.
λη ⊕ Surjective Pairing ⊭ CR
λ,CL ⊕ DMM -> M ⊭ CR
    { if ⊤ then X else Y -> X }
λ ⊕ { if ⊥ then X else Y -> Y } ⊭ CR
    { if Z then X else X -> X }
on the other hand, the positive result that e.g.
CL ⊕ D(M,M) -> M ⊭ CR
CL ⊕ if-then-else- as above ⊧ CR
(In the positive result, CL can be replaced by an arbitrary non-ambiguous and left—linear TRS;  not so in the negative one.)

*Summary*
The first part of Chapter I  (λβ—calculus and definable extensions, which include Recursive Program Schemes) is mainly devoted to the basic syntactical theorems of λ—calculus: the Lemma of Parallel Moves, the Theorem of Finite DeveloPments and as a consequence, the Church-Rosser Theorem. In the proofs of these well-known theorems we make a systematic use of labels, and of reduction diagrams. Since it is convenient for some applications later on, as well as interesting for its own sake, we not only prove the fore-mentioned theorems for λβ-calculus but for a wider class of 'reduction systems', which we have called definable extensions of λβ-calculus. The results also hold for substructures of such extensions; e.g. Combinatory Logic is a substructure of a definable extension of λβ—calculus.
The method of proof of 'Finite Developments' was first used in BARENDREGT, BERGSTRA, KLOP, VOLKEN [76]; it lends itself easily to prove FD for other extensions of λ-calculus  (see also BARENDREGT [80]). The use of reduction diagrams is new; it was independently proposed in HINDLEY [78"]. The treatment via reduction diagrams is only a slight refinement of that in LEVY [78]; it pays off especially in Chapter IV, where λβη-calculus is considered.
Before proving the Church-Rosser theorem, we have collected in section 1.5 several facts, mostly well—known, which hold for 'Abstract Reduction Systems' and which we need later on. Typical examples are the Lemma of Hindley—Rosen and (as we call it) Newman's Lemma. Also a preparation is made for a part of Chapter II, in the form of Nederpelt's Lemma and related propositions.
In 1.7 we proceed to prove another classical λ—calculus theorem, which we have called 'Church's Theorem'. It plays a key role in a new proof  (in 1.8)  of Strong Normalization for typed λ—calculus and some more general labeled λ—calculi, such as  'Lévy's λ—calculus'. Again the theorem is proved not only for λI-calculus, but for 'definable extensions of λI'.
Sections 1.9 — I.10 contain two new proofs of the well-known Standardization Theorem. Compared to the known proofs (see e.g. MITSCHKE [79]) these new proofs yield a simpler algorithm to standardize a reduction. The first proof is used in Chapter IV to obtain as a new result standardization for βη—reductions, and the second proof is used at the end of Chapter II to obtain Standardization for some generalizations of the reduction systems in Chapter I  (e.g. for λ ⊕ recursor R, if one uses the  'left—normal' version of R). Of all these results the strong versions are proved, in the sense of (Lévy-) equivalence ≂_L of reductions.  (E.g. for every finite reduction R, there is a unique standard reduction R_st which is equivalent to R. This strong version of the Standardization Theorem is due to J.J. Lévy.)  Our second proof of the Standardization Theorem casts some light on the relation between standard reductions and equivalence of reductions. As a digression, using the concept 'meta—reduction' of reductions as in this second proof, we prove in I.10 some facts about equivalence classes of finite reductions. (E.g. in λI the cardinality of the equivalence class { R' | R ≂_L R' } can be any n >= 1, but not be infinite.)
Chapter I is concluded by deriving in 1.11 the well—known Normalization Theorem for λβ (and definable extensions thereof)  and by considering in I.12 'cofinal' reductions; the main theorem about such reductions was proved independently by S. Micali and M. O'Donnell.
Chapter II introduces a very general kind of reduction systems, ranging from Term Rewriting Systems in Computer Science to Normalization procedures in Proof Theory. These reduction systems can be called 'Term Rewriting Systems with bound variables'; we refer to them as Combinatory Reduction Systems. In Chapter II we pose a severe restriction on such reduction systems: they have to satisfy the well-known conditions of being 'non-ambiguous and left—linear', a phrase which we will abbreviate by 'regular'. For such CRS's we have proved in Chapter II the main syntactical theorems, such as the ones mentioned above in the summary of Chapter I.  (Normalization and Standardization only for a restricted class of regular CRS's, though.)  Since the behaviour w.r.t. substitution of CRS's can be arbitrarily complicated (as contrasted to that of λβ), it turned out to be non—trivial to prove the theorem of Finite Developments, a Strong Normalization result. This obstacle is overcome by a device of Nederpelt for the reduction of SN-proofs for regular CRS's to WN-proofs. Not only for that reason, but also since this method seems to have independent merits, we have generalized Nederpelt's method to the class of all regular CRS's. This is done by introducing 'reductions with memory'; nothing is  'thrown away' in such reductions; they are non-erasing, like AI—calculus is. In II.5 we generalize Church's Theorem for AI to all regular non—erasing CRS's. Section II.6 contains a generalization of the Strong Normalization theorem for λ^L, λ^\tau, λβ^HW in Chapter 1.8, to regular CRS's for which a 'decreasing labeling' can be found (like the types in a typed λ-calculus are decreasing labels). This generalization enables us in turn to extend Lévy's method of labeling to all regular CRS's, and to prove the corresponding SN-result (this is only executed for TRS's, i.e. CRS's without substitution, though). As a corollary we obtain Standardization and Normalization for some 'left—normal' regular CRS's.

Whereas in Chapter I and II we considered only regular CRS's, we deal in Chapter III with some irregular ones, namely with some non—left—linear CRS's; i.e. in a reduction rule some metavariable in the LHS of a reduction rule occurs twice, as in DXX + X.  (Except for the case of 'Surjective Pairing' we do not consider ambiguous rules;  for results about ambiguous TRS's we refer to HUET [78] and HUET-OPPEN [80].)
Non-left—linearity  (we will omit the word 'left' sometimes) of the reduction rules turns out to be an obstacle to the CRrproperty: in a non-linear CRS which is 'strong enough’, the CR-property fails. This is proved for some non—linear extensions of λ-calculus  (or Combinatory Logic), thus answering some questions of C. Mann, R. Hindley and J. Staples negatively. Although the intuition behind these CR—counterexamples is easily grasped, the proof that they are indeed so requires several technicalities. In an Intermezzo we expand this intuition using the well-known 'Böhm-trees', a kind of infinite normal forms for terms.
In III.3 we have considered for these non—linear systems for which CR fails, other properties  (which are otherwise corollaries of CR)  such as Unicity of Normal forms  (UN), Consistency, etc. Even though CR fails, UN does hold for the systems considered.
In III.4,5 we prove CR for some restricted classes of non—linear CRS's. Most notable is a positive answer to a question suggested in O'DONNELL [77] : Does CR hold when the non-linear trio of rules (*)
if true then X else Y -> x
if false then X else Y -> Y
if X then Y else Y->Y
is added to a regular TRS?
This is seemingly in contradiction with our earlier CR-counterexample for CL ⊕ B where B is a constant representing the branching operation above, having the rules
B⊤XY->X, B⊥XY->Y, BXYY->Y.
The explanation is that CL⊕B ⊭ CR, but CL⊕B(—,-,—) ⊧ CR, where the notation B(—,—,-) means that B has to have three arguments (i.e. 3 cannot occur alone). In the formulation of (*)  as above this is similar, and so O'Donnell's question can be answered positively.
Chapter IV, finally, is not related to Chapters II, III, but considers λβη-calculus. Via a new concept of 'residual'  for βη—reductions  (for which the lemma of Parallel Moves holds, in contrast to the case of the ordinary residuals)  we prove the Standardization and Normalization theorem for  ABn, thus solving some questions of Hindley. Here we profit from the concept of 'reduction diagram' and from our first proof of the Standardization Theorem for A8 in 1.9. Also an extension of the result in I.12 about cofinal reductions is given.