Combinatory logic

Uses your system voice; voice and rate in settings.

Snapshot

≈ 16 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming languages. It is based on combinators, which were introduced by Schönfinkel in 1920 with the idea of providing an analogous way to build up functions — and to remove any mention of variables — particularly in predicate logic. A combinator is a higher-order function that uses only function application and earlier defined combinators to define a result from its arguments.

Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming languages. It is based on combinators, which were introduced by Schönfinkel in 1920 with the idea of providing an analogous way to build up functions — and to remove any mention of variables — particularly in predicate logic. A combinator is a higher-order function that uses only function application and earlier defined combinators to define a result from its arguments.

In mathematics

Combinatory logic was originally intended as a 'pre-logic' that would clarify the role of quantified variables in logic, essentially by eliminating them. Another way of eliminating quantified variables is Quine's predicate functor logic. While the expressive power of combinatory logic typically exceeds that of first-order logic, the expressive power of predicate functor logic is identical to that of first-order logic (Quine 1960, 1966, 1976).

The inventor of combinatory logic, Moses Schönfinkel, published nothing on combinatory logic after his original 19241 paper. Haskell Curry rediscovered the combinators while working as an instructor at Princeton University in late 1927. In the late 1930s, Alonzo Church and his students at Princeton invented a rival formalism for functional abstraction, the lambda calculus, which proved more popular than combinatory logic.

The upshot of these historical contingencies was that until theoretical computer science began taking an interest in combinatory logic in the 1960s and 1970s, nearly all work on the subject was by Haskell Curry and his students, or by Robert Feys in Belgium. Curry and Feys (1958), and Curry et al. (1972) survey the early history of combinatory logic. For a more modern treatment of combinatory logic and the lambda calculus together, see the book by Barendregt, which reviews the models Dana Scott devised for combinatory logic in the 1960s and 1970s.

In computing

In computer science, combinatory logic is used as a simplified model of computation, used in computability theory and proof theory. Despite its simplicity, combinatory logic captures many essential features of computation. Combinatory logic can be viewed as a variant of the lambda calculus, in which lambda expressions (representing functional abstraction) are replaced by a limited set of combinators, primitive functions without free variables.

It is easy to transform lambda expressions into combinator expressions, and combinator reduction is much simpler than lambda reduction. Hence combinatory logic has been used to model some non-strict functional programming languages and hardware. The purest form of this view is the programming language Unlambda, whose sole primitives are the S and K combinators augmented with character input/output. Although not a practical programming language, Unlambda is of some theoretical interest. Combinatory logic can be given a variety of interpretations.

Many early papers by Curry showed how to translate axiom sets for conventional logic into combinatory logic equations. Dana Scott in the 1960s and 1970s showed how to marry model theory and combinatory logic. The expression E[v := a] represents the result of taking the term E and replacing all free occurrences of v in it with a . Thus we write ((\lambda v.E)a) \Rightarrow E[v := a] By convention, we take (a b c) as shorthand for ((a b) c) (i.e., application is left associative).

The motivation for this definition of reduction is that it captures the essential behavior of all mathematical functions. For example, consider the function that computes the square of a number. We might write The square of x is x*x (Using " * " to indicate multiplication.) x here is the formal parameter of the function.

To evaluate the square for a particular argument, say 3, we insert it into the definition in place of the formal parameter: The square of 3 is 3*3 To evaluate the resulting expression 3*3 , we would have to resort to our knowledge of multiplication and the number 3. Since any computation is simply a composition of the evaluation of suitable functions on suitable primitive arguments, this simple substitution principle suffices to capture the essential mechanism of computation.

Moreover, in lambda calculus, notions such as '3' and ' * ' can be represented without any need for externally defined primitive operators or constants. It is possible to identify terms in lambda calculus, which, when suitably interpreted, behave like the number 3 and like the multiplication operator, q.v. Church encoding.

Lambda calculus is known to be computationally equivalent in power to many other plausible models for computation (including Turing machines); that is, any calculation that can be accomplished in any of these other models can be expressed in lambda calculus, and vice versa. According to the Church–Turing thesis, both models can express any possible computation.

It is perhaps surprising that lambda-calculus can represent any conceivable computation using only the simple notions of function abstraction and application based on simple textual substitution of terms for variables. But even more remarkable is that abstraction is not even required. Combinatory logic is a model of computation equivalent to lambda calculus, but without abstraction.

The advantage of this is that evaluating expressions in lambda calculus is quite complicated because the semantics of substitution must be specified with great care to avoid variable capture problems. In contrast, evaluating expressions in combinatory logic is much simpler, because there is no notion of substitution. (P\ x_1 \dots x_n) = E where E is a term mentioning only variables from the set \{x_1 \dots x_n\} . It is in this way that primitive combinators behave as functions. (I\ x) = x for all terms x .

Another simple combinator is K , which manufactures constant functions: (K x) is the function which, for any argument, returns x , so we say ((K\ x)\ y) = x for all terms x and y . Or, following the convention for multiple application, (K\ x\ y) = x A third combinator is S , which is a generalized version of application: (S\ x\ y\ z) = (x\ z\ (y\ z)) S applies x to y after first substituting z into each of them. Or put another way, x is applied to y inside the environment z .

Given S and K , I itself is unnecessary, since it can be built from the other two: ((S\,K\,K)\,x) = (S\,K\,K)\,x = K\,x\,(K\,x) = x for any term x . Note that although ((S\,K\,K)\,x) = (I x) for any x , (S\,K\,K) itself is not equal to I . We say the terms are extensionally equal. Extensional equality captures the mathematical notion of the equality of functions: that two functions are considered equal if they always produce the same results for the same arguments.

In contrast, the terms themselves, together with the reduction of primitive combinators, capture the notion of intensional equality of functions: that two functions are considered equal only if they have identical implementations up to the expansion of primitive combinators. There are many ways to implement an identity function; (S\,K\,K) and I are among these ways. (S\,K\,S) is yet another. We will use the word equivalent to mean extensional equality.

A more interesting combinator is the fixed point combinator or Y combinator, which can be used to implement recursion. It is related to the process of bracket abstraction, which takes an expression E built from variables and application and produces a combinator expression [x]E in which the variable x is not free, such that [x]E x = E holds.

A very simple algorithm for bracket abstraction is defined by induction on the structure of expressions as follows: [x]y := K y [x]x := I [x](E E ) := S([x]E )([x]E ) Bracket abstraction induces a translation from lambda terms to combinator expressions, by interpreting lambda-abstractions using the bracket abstraction algorithm. = T λx.T λy.(y x) (by 5) = T[λx.(S T[λy.y] T[λy.x])] (by 6) = T[λx.(S I T[λy.x])] (by 4) = T[λx.(S I (K T[x]))] (by 3) = T[λx.(S I (K x))] (by 1) = (S T[λx.(S I)] T[λx.(K x)]) (by 6) = (S (K (S I)) T[λx.(K x)]) (by 3) = (S (K (S I)) (S T[λx.K] T[λx.x])) (by 6) = (S (K (S I)) (S (K K) T[λx.x])) (by 3) = (S (K (S I)) (S (K K) I)) (by 4) If we apply this combinatorial term to any two terms x and y (by feeding them in a queue-like fashion into the combinator 'from the right'), it reduces as follows: (S (K (S I)) (S (K K) I) x y) = (K (S I) x (S (K K) I x) y) = (S I (S (K K) I x) y) = (I y (S (K K) I x y)) = (y (S (K K) I x y)) = (y (K K x (I x) y)) = (y (K (I x) y)) = (y (I x)) = (y x) The combinatory representation, (S (K (S I)) (S (K K) I)) is much longer than the representation as a lambda term, λx.λy.(y x).

This is typical. In general, the T[ ] construction may expand a lambda term of length n to a combinatorial term of length Θ(n 3 ). λx.(E E ) is a function which takes an argument, say a, and substitutes it into the lambda term (E E ) in place of x, yielding (E E )[x : = a].

But substituting a into (E E ) in place of x is just the same as substituting it into both E and E , so (E E )[x := a] = (E [x := a] E [x := a]) (λx.(E E ) a) = ((λx.E a) (λx.E a)) = (S λx.E λx.E a) = ((S λx.E λx.E ) a) By extensional equality, λx.(E E ) = (S λx.E λx.E ) Therefore, to find a combinator equivalent to λx.(E E ), it is sufficient to find a combinator equivalent to (S λx.E λx.E ), and (S T[λx.E ] T[λx.E ]) evidently fits the bill.

E and E each contain strictly fewer applications than (E E ), so the recursion must terminate in a lambda term with no applications at all—either a variable, or a term of the form λx.E. T[λx.(E x)] = T[E] (if x is not free in E) λx.(E x) is the function which takes an argument, x, and applies the function E to it; this is extensionally equal to the function E itself. It is therefore sufficient to convert E to combinatorial form.

Taking this simplification into account, the example above becomes: T[λx.λy.(y x)] = ... = (S (K (S I)) T[λx.(K x)]) = (S (K (S I)) K) (by η-reduction) This combinator is equivalent to the earlier, longer one: (S (K (S I)) K x y) = (K (S I) x (K x) y) = (S I (K x) y) = (I y (K x y)) = (y (K x y)) = (y x) Similarly, the original version of the T[ ] transformation transformed the identity function λf.λx.(f x) into (S (S (K S) (S (K K) I)) (K I)). With the η-reduction rule, λf.λx.(f x) is transformed into I. X (X (X X)) = β K and X (X (X (X X))) = β S.

Since {K, S} is a basis, it follows that {X} is a basis too. The Iota programming language uses X as its sole combinator. Another simple example of a one-point basis is: X ≡ λx.(x K S K) with (X X) X = β K and X (X X) = β S The simplest known one-point basis is a slight modification of S: S ≡ λxλyλz. (x z) (y (λw. z))) with S (S S) (S (S S) S S S S S) = β K and S (S (S S (S S (S S))(S (S (S S (S S)))))) S S = β S. In fact, there exist infinitely many such bases.

(C f g x) = ((f x) g) (B f g x) = (f (g x)) He also explains how they in turn can be expressed using only S and K: B = (S (K S) K) C = (S (S (K (S (K S) K)) S) (K K)) These combinators are extremely useful when translating predicate logic or lambda calculus into combinator expressions. They were also used by Curry, and much later by David Turner, whose name has been associated with their computational use.

Using them, we can extend the rules for the transformation as follows: (if x is not free in E) (if x is free in E) (if x is free in both E and E ) (if x is free in E but not E ) (if x is free in E but not E ) Using B and C combinators, the transformation of λx.λy.(y x) looks like this: (by rule 7) (η-reduction) = \mathsf{C}_{*} (traditional canonical notation: \mathsf{X}_{*} = \mathsf{X I} ) = \mathsf{I}' (traditional canonical notation: \mathsf{X}' = \mathsf{C X} ) And indeed, (C I x y) does reduce to (y x): (C I x y) = (I y x) = (y x) The motivation here is that B and C are limited versions of S, with B x y = S (K x) y and C x y = S x (K y).

Whereas S x y z = (x z) (y z) takes a value (z) and substitutes it into both the applicand (x) and its argument (y) before performing the application, C performs the substitution only in the applicand ((x z) y), and B only in the argument (x (y z)). The modern names for the combinators come from Haskell Curry's doctoral thesis of 1930 (see B, C, K, W System). In Schönfinkel's original paper, what we now call S, K, I, B and C were called S, C, I, Z, and T respectively.

The reduction in combinator size that results from the new transformation rules can also be achieved without introducing B and C, as demonstrated in Section 3.2 of . (§12) defines two minimal combinators for λ I calculus: I = λa.a and J = λabcd.ab(adc). He also proposes alternative primitive sets of combinators, B, C, W, I (where W = λab.abb is the same as used today), or B, T, U, I (where T = JII = λab.ba = CI, and U = λa.aa = WI which he calls D).

L[I] = λx.x L[K] = λx.λy.x L[C] = λx.λy.λz.(x z y) L[B] = λx.λy.λz.(x (y z)) L[S] = λx.λy.λz.(x z (y z)) L[(E E )] = (L[E ] L[E ]) Note, however, that this transformation is not the inverse transformation of any of the versions of T[ ] that we have seen. The undecidable problems above (equivalence, existence of normal form, etc.) take as input syntactic representations of terms under a suitable encoding (e.g., Church encoding).

One may also consider a toy trivial computation model where we "compute" properties of terms by means of combinators applied directly to the terms themselves as arguments, rather than to their syntactic representations. More precisely, let a predicate be a combinator that, when applied, returns either T or F (where T and F represent the conventional Church encodings of true and false, λx.λy.x and λx.λy.y, transformed into combinatory logic; the combinatory versions have and ).

A predicate N is nontrivial if there are two arguments A and B such that N A = T and N B = F. A combinator N is complete if NM has a normal form for every argument M. An analogue of Rice's theorem for this toy model then says that every complete predicate is trivial. The proof of this theorem is rather simple. From this undefinability theorem it immediately follows that there is no complete predicate that can discriminate between terms that have a normal form and terms that do not have a normal form.

It also follows that there is no complete predicate, say EQUAL, such that: (EQUAL A B) = T if A = B and (EQUAL A B) = F if A ≠ B. If EQUAL would exist, then for all A, λx.(EQUAL x A) would have to be a complete non trivial predicate. However, note that it also immediately follows from this undefinability theorem that many properties of terms that are obviously decidable are not definable by complete predicates either: e.g., there is no predicate that could tell whether the first primitive function letter occurring in a term is a K.

This shows that definability by predicates is a not a reasonable model of decidability.

See also

Applicative computing systems B, C, K, W system Categorical abstract machine Combinatory categorial grammar Explicit substitution Fixed point combinator Graph reduction machine Lambda calculus and Cylindric algebra, other approaches to modelling quantification and eliminating variables SKI combinator calculus Supercombinator To Mock a Mockingbird

Literature

(eBook: )

External links

Stanford Encyclopedia of Philosophy: "Combinatory Logic" by Katalin Bimbó. 1920–1931 Curry's block notes. Keenan, David C. (2001) "To Dissect a Mockingbird: A Graphical Notation for the Lambda Calculus with Animated Reduction." Rathman, Chris, "Combinator Birds." A table distilling much of the essence of Smullyan (1985). Drag 'n' Drop Combinators. (Java Applet) Binary Lambda Calculus and Combinatory Logic. Combinatory logic reduction web server

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378677590 under CC BY-SA 4.0; modifications have been made.

References

  1. ↩Wikipedia “Combinatory logic” revision 1378677590 · retrieved 2026-10-20 publication date (×1) · confidence 0.95 revision URL