VAR logo English
Home page Services Past achievements Contact Site
map
Page d'accueil Services Réalisations précédentes Contact
Français


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:

I x==>x
Y x==>x (Y x)

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 I0, which takes no arguments. By extension, the In combinator requires n arguments before it can be evaluated, leaving them all completely unchanged, and hence I1 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.

I2 x y==>x y
K x y==>x
KI x y==>y
CI x y==>y x
W x y==>x y y

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

I3 x y z==>x y z
K' x y z==>x y
B x y z==>x (y z)
C x y z==>x z y
S x y z==>x z (y z)
P x y z==>z x y
JI x y z==>x (z y)

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

I4 w x y z==>w x y z
K" w x y z==>w x y
B' w x y z==>w x (y z)
C' w x y z==>w (x z) y
S' w x y z==>w (x z) (y z)
Ψ w x y z==>w (x y) (x z)
J w x y z==>w x (w z y)

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.

poly = [x] x*x – 9;

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:

S (S (K –) (S * I)) (K 9)

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:

C' – (S' * I I) 9

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.

However, 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 Selecti combinator will delete all of them except the ith element. It is equivalent to Ki-1 Kn-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 Z0, in Peano notation, with "S B" as the SUCCESSOR operator to generate the other integers. In this way:

S B Zn-1==>Zn
S' B Zm Zn==>Zm+n
B Zm Zn==>Zmn
Zm Zn==>Znm

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.

Xn==>B X Xn-1
where X0==>I

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:

W2 x y==>x y y y
K2 x y z==>x
C2 x y z==>x y z
B2 w x y z==>w (x y z)

It turns out that:

B Xm Xn==>Xm+n
hence B Xn X-n==>I
(Xm)n==>Xmn
(BX)n==>B Xn

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

X(n)==>B (B X(n-1)) B
where X(0)==>X

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

X(n)==>B X(n-1)
where X(0)==>X
noting, too, that Bm X(n)==>X(m+n)
Xn==>X(n-1)

This obtains combinators like: Cn that swaps over its nth and (n+1)th arguments; Wn that repeats its nth argument; Kn that deletes its nth argument; Sn 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, In that does nothing to its n arguments.

Top of this page Home page Services Past achievements Contact Site
map
Page d'accueil Services Réalisations précédentes Contact
© Malcolm Shute, Valley d'Aigues Research, 2006-2015