Combinators

Combinators are a type of mathematical function that was extensively investigated by Curry and Feys (1958), and then energetically considered as the basis for novel computer instruction sets in the early 1980s.

A string of space-separated symbols is treated as the name of a function and the list of arguments to which it is to be applied. Thus, the string "f x y z" could be considered as the equivalent of "f(x,y,z)" in a more conventional notation; and, using prefix notation for arithmetic expressions, "+ 1 4" would evaluate to "5".

One of the properties of combinator strings is that they bind from left to right, so that "f x y z" is equivalent to "(((f x) y) z)". This means that "+ 1 4" is equivalent to "((+ 1) 4)", and hence that "(+ 1)" can be considered to be a function in its own right. Combinators, therefore, are said to support "higher-order function" definitions. In effect, in this case, giving the combinator equivalent of the single-argument "Increment" function (though, in practice, it is rare that the intermediate functions are anything other than transient, and in no need of a name that can be recognised by a human reader).

However, most of the combinators, normally represented by letters of the alphabet, are for swapping arguments around in the string, and forming nested sub-strings. Being mathematical in origin, the most important combinator is the one that appears to do the least: the "Identity" combinator, I. This takes a single argument, and returns it unchanged as its result. This is shown in the first line of the following table:

The I combinator is not quite the combinator equivalent of the NOP instruction on a conventional computer, since it first has to wait (when implemented as a computer programming language) until its parameter, x, is available before it can be evaluated. The real NOP in the combinator world is I₀, which takes no arguments. By extension, the I_n combinator requires n arguments before it can be evaluated, leaving them all completely unchanged, and hence I₁ is the same as I.

Two-argument Combinators

In the following table, the combinators KI and CI represent what Curry and Feys would have called K* and C*. Since they have the effect of (K I) and (C I), respectively, it is more convenient to call them KI and CI.

At this point, it becomes evident that there are, in fact, and infinite number of possible combinators, and that these tables only list the most useful ones.

Three-argument Combinators

If x and y are functions, and are being passed to the combinator as its first and second arguments, then B arranges that the second, y, is applied to z; for example, "B sin cos 1" would evaluate to sin(cos(1)). C arranges that its first argument, x, is applied to z; and S arranges that both, x and y, are applied to z.

Four-argument Combinators

If w, x and y are functions, and are being passed to the combinator as its first, second and third arguments, then B' arranges that the third, y, is applied to z; C' arranges that its second, x, is applied to z; and S' (which Curry and Feys call Φ) arranges that both, x and y, are applied to z. Other combinations can be easily imagined.

Compilation from Programming Languages to Combinator Strings

The following line is written in a programming language called Sugar (Glaser, Hankin and Till, 1984), and defines a function, poly, that takes a single argument, x, and evaluates the result of multiplying that argument by itself and subtracting a constant from it.

Curry and Feys (1958) give a very simple algorithm for the compiler to use, to convert this function definition into a string involving S, K and I combinators:

Clarke et al (as described in Chambers, Duce and Jones, 1984)) give an even simpler algorithm, for the compiler to convert it into a string involving I, B', C', S' (and possibly K") combinators:

It is now that one of the most important properties of combinators is seen: they allow functions to be defined without the need for variables. Even in the trivial example given here, the combinator strings do without the internal variable, x.

The Curry and Feys algorithm shows that all functions can be described using just S, K and I. Furthermore, since "(S K K)" can be used to replace I, they showed that all functions, and all the other combinators, can be described using just S and K. One immediate concern with implementing a purely SK machine in hardware is the inbalance between the work of the S combinator, and the relatively trivial amount for the K combinator (even when taking the work of the partial-reference counting garbage collection mechanism into account). More importantly, though, such a minimalist design would be highly inefficient in terms of package communication times. So, moving in the other direction, it is noted that the I, B, C, W, B', C', S' and K" combinators are convenient for including in a practical instruction set, since they represent efficient ways of performing operations that high-level language compilers routinely handle.

Lastly, the Y combinator was mentioned at the start of this page. This is useful for implementing recursive function calls within a function.

Manipulating Compound Data Structures

It is no coincidence that combinator expressions bear a strong resemblance to the computer programming language, Lisp. The K and KI combinators turn out to be very similar to the CAR and CDR operators (HD and TL, or HEAD and TAIL) when manipulating lists. This might be helped by use of the P, pair constructor, combinator to code the structural information in the list itself.

Meanwhile, given a list of n elements, the Select_i combinator will delete all of them except the i^th element. It is equivalent to K^i-1 K^n-i, where this notation is explained later on this page.

K and KI also turn out to be good representations of TRUE and FALSE, as the result to be returned by conditional expressions. In this way, "(> x 9) y z" would evaluate y if x is greater than 9, and would evaluate z otherwise.

KI also turns out to be a good representation for ZERO, or Z₀, in Peano notation, with "S B" as the SUCCESSOR operator to generate the other integers. In this way:

This is just for the mathematician, though. No computer engineer would think of using Peano notation, instead of the far more convenient binary representation for integers (except in a few limited cases, such as using a bit circulating in a shift register to organise the timing elsewhere in the circuit). However, it does complete the assertion above, that even the integers and arithmetic operators can be expressed in terms of S and K combinators.

Compounding Notation on Combinators

This last section needs to be treated with some caution. I noted the following relationships down when I read Curry and Feys, but never had cause to check it out in detail. There could well be riders and special cases, or dare I say errors in the transcription, that need to be ironed out. I offer it here, as is, just as a starting point for further work.

For example, setting n=2, combinators are obtained that do twice what the original combinator does, and setting n=3 obtains combinators do thrice what the original combinator does:

It turns out that:

The system of primes on combinators (B', C', S', K") can be defined by the following notation:

Next, the notation can be defined that was used earlier (noting that X_(n) is not the same as X_n):

This obtains combinators like: C_n that swaps over its n^th and (n+1)^th arguments; W_n that repeats its n^th argument; K_n that deletes its n^th argument; S_n that applies each of its (n+1) arguments to its (n+2)^th argument; S'_n that applies each of its (n+1) arguments, except the first, to its (n+2)^th argument; and, of course, I_n that does nothing to its n arguments.

Higher order functions

In functional languages, functions are first-class citizens. Just as names can be associated with constants of type "integer", "real", or "string", so they can with constants of type "function".

 G = 6.673e-11;
 earthmass = 5.972e24;
 welcome = "Hello, World.";
 fac = [n] (if n>0, n*fac(n-1), 1 )
 force = [coupling][q1][q2][r] (coupling*q1*q2/r^2)
 gravityfield = force( G, earthmass )

The "=" sign is used to emphasise that it is a naming, not an assignment operation, and "gravityfield" is a higher order function that takes two arguments, having been constructed on-the-fly by the compiler from a function that takes four arguments for which two of them have already been supplied.