Combinators

After it became widely known in the 1910s that Nand could be used to build up any expression in basic logic (see page 1173) Moses Schönfinkel introduced combinators 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 (see page 898). Given the combinator rules

crules = {s[x_][y_][z_]  x[z][y[z]], k[x_][y_]  x}

the setup was that any function f would be written as some combination of s and k—which Schönfinkel referred to respectively as "fusion" and "constancy"—and then the result of applying the function to an argument x would be given by f[x] //. crules. (Multiple arguments were handled for example as f[x][y][z] in what became known as "currying".) A very simple example of a combinator is id = s[k][k], which corresponds to the identity function, since id[x] //. crules yields x for any x. (In general any combinator of the form s[k][_] will also work.) Another example of a combinator is b = s[k[s]][k], for which b[x][y][z] //.crules yields x[y[z]].

With the development of lambda calculus in the early 1930s it became clear that given any expression expr such as x[y[x][z]] with a list of variables vars such as {x, y, z} one can always find a combinator equivalent to a lambda function such as Function[x, Function[y, Function[z, x[y[x][z]]]]], and it turns out that this can be done simply using

ToC[expr_, vars_] := Fold[rm, expr, Reverse[vars]]

rm[v_, v_] = id

rm[f_[v_], v_] /; FreeQ[f, v] = f

rm[h_, v_] /; FreeQ[h, v] = k[h]

rm[f_[g_], v_] := s[rm[f, v]][rm[g, v]]

So this shows that any lambda function can in effect be written in terms of combinators, without anything analogous to variables ever explicitly having to be introduced. And based on the result that lambda functions can represent recursive functions, which can in turn represent Turing machines (see note above), it has been known since the mid-1930s that combinators are universal. The rule 110 combinator on page 713 provides however a much more direct proof of this.

The usual approach to working with combinators involves building up arithmetic constructs from them. This typically begins by using so-called Church numerals (based on work by Alonzo Church on lambda calculus), and defining a combinator e_n to correspond to an integer n if e_n[a][b]//.crules yields Nest[a, b, n]. (The ℯ on page 103 can thus be considered a Church numeral for 2 since e[a][b] is a[a[b]].) This can be achieved by taking e_n to be Nest[inc, zero, n] where

zero = s[k]

inc = s[s[k[s]][k]]

With this setup one then finds

plus = s[k[s]][s[k[s[k[s]]]][s[k[k]]]]

times = s[k[s]][k]

power = s[k[s[s[k][k]]]][k]

(Note that power[x][y]//.crules is y[x], and that by analogy x[x[y]] corresponds to y^x2, x[y[x]] to x^{x y}, x[y][x] to x^yx, and so on.)

Another approach involves representing integers directly as combinator expressions. As an example, one can take n to be represented just by Nest[s, k, n]. And one can then convert any Church numeral x to this representation by applying s[s[s[k][k]][k[s]]][k[k]]. To go the other way, one uses the result that for all Church numerals x and y, Nest[s, k, n][x][y] is also a Church numeral—as can be seen recursively by noting its equality to Nest[s, k, n - 1][y][x[y]], where as above x[y] is power[y][x]. And from this it follows that Nest[s, k, n] can be converted to the Church numeral for n by applying

s[s[s[s[s[k][k]][k[s[s[k[s]][k]][s[k][k]]]]][
k[s[s[k[s]][k]][s[s[k[s]][k]][s[k][k]]]]]][s[s[k[s]][
s[s[k[s]][s[k[s[s[s[s[s[s[s[k][k]][k[s]]][k[k]]][k[s[s[
k[s]][k]][s[k][k]]]]][k[s[s[k[s]][k]][s[s[k[s]][k]][s[k][
k]]]]]][k[s[s[s[s[k][k]][k[s[s[k[s]][s[k[s[s[k][k]]]][s[
k[k]][s[k[s[s[k[s]][k]]]][s[s[k][k]][k[k]]]]]]][s[k[k]][s[
s[k][k]][k[k]]]]]]][k[s[s[s[k][k]][k[s[k]]]][k[s[k]]]]]][
k[s[k]]]]]]]][s[k[k]][s[s[s[k][k]][k[s[s[k[s]][k]][s[k][
k]]]]][k[s[s[k[s]][k]][s[s[k[s]][k]][s[k][k]]]]]]]]][
k[s[k[k]][s[s[k[s]][k]]]]]]][k[s[k][k]]]]][k[s[k]]]

Using this one can find from the corresponding results for Church numerals combinator expressions for plus, times and power—with sizes 377, 378 and 382 respectively. It seems certain that vastly simpler combinator expressions will also work, but searches indicate that if inc has size less than 4, plus must have size at least 8. (Searches based on other representations for integers have also not yielded much. With n represented by Nest[k, s[k][k], n], however, s[s[s[s]][k]][k] serves as a decrement function, and with n represented by Nest[s[s],s[k], n], s[s[s][k]][k[k[s[s]]]] serves as a doubling function.