|Home page||Services||Past achievements||Contact||Site
|Page d'accueil||Services||Réalisations précédentes||Contact|
|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.
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.
|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.
|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.
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.
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|
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.
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|
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|
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|
Next, the notation can be defined that was used earlier (noting that X(n) is not the same as Xn):
|noting, too, that Bm X(n)||==>||X(m+n)|
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.