COMBINATORS I is http://www.escribe.com/science/theory/m5913.html COMBINATORS II is http://www.escribe.com/science/theory/m5942.html COMBINATORS III is http://www.escribe.com/science/theory/m5946.html

Resume:

Kxy = x Sxyz = xz(yz)

`You are supposed to remember also that`

abc is an abbreviation of ((ab)c), and a(bc) is an abbreviation for (a(bc)), so

Kxy is put for ((K x) y), and Sxyz is put for (((S x) y) z), and xz(yz) is put for

((x z)(y z)). We just don't write the left parentheses).

abc is an abbreviation of ((ab)c), and a(bc) is an abbreviation for (a(bc)), so

Kxy is put for ((K x) y), and Sxyz is put for (((S x) y) z), and xz(yz) is put for

((x z)(y z)). We just don't write the left parentheses).

We have seen:

Ix = x, a solution for I is I = SKK Mx = xx, a solution for M is M = SII = S(SKK)(SKK) Bxyz = x(yz), a solution for B is B = S(KS)K

I recall the last exercises: Find combinators W, L, T, C and INFINITY such that

Wxy = xyy Lxy = x(yy) Txy = yx Cxyz = xzy INFINITY gives INFINITY (by the dynamical rules for K and S).

SOLUTIONS:

1) Wxy = xyy = (xy)y because xyy abbreviates xyy = (xy)(Iy) because y = Iy = SxIy dynamics of S = (SxI)y abbrev. = Sx(KIx)y because I = KIx = (Sx(KIx))y abbrev. = (SS(KI)x)y dynamics of S = SS(KI)xy abbrev.

Thus W = SS(KI) = SS(K(SKK))

2) Lxy = x(yy) = x(My) because My = yy (Mx = xx). = BxMy dynamics of B = Bx(KMx)y 'cause KMx = M = SB(KM)xy dyn. of S, on ((Bx)((KM)x)

Thus L = SB(KM) = S(S(KS)K)(KS(SKK)(SKK))

`Od course SB(KM) is a better presentation, giving that we know already B and M.`

But I give the (abbreviated) combinator (in term of S and K) to be sure you see it is

indeed a combinator (a combination of S and K).

But I give the (abbreviated) combinator (in term of S and K) to be sure you see it is

indeed a combinator (a combination of S and K).

`3) Txy = yx`

= y(Kxy) 'cause x = Kxy

= (Iy)(Kxy) 'cause y = (Iy)

= SI(Kx)y dyn. of S (which explain the transformation just above btw)

= B(SI)Kxy dyn. of B

= y(Kxy) 'cause x = Kxy

= (Iy)(Kxy) 'cause y = (Iy)

= SI(Kx)y dyn. of S (which explain the transformation just above btw)

= B(SI)Kxy dyn. of B

Thus T = B(SI)K = S(KS)K(S(SKK))K

4) Cxyz = xzy = xz(Kyz) = Sx(Ky)z = B(Sx)Kyz = BBSxKyz = BBSx(KKx)yz = (BBS)x(KKx)yz = S(BBS)(KK)xyz

Thus C = S(BBS)(KK) = S((S(KS)K)(S(KS)K)S)(KK) cf B = S(KS)K

5) INFINITY Well this one is easy!

Mx = xx, thus MM gives MM which gives MM, etc.

Thus INFINITY = MM = SII(SII) = S(SKK)(SKK)(S(SKK)(SKK))

It is a simple example of a perpetually unstable molecule.

All right so far? To find those programs, the heuristic has been to use K and I to change some combination of variables (like xzy) into a form such that a known dynamic can be used (in general the one of S, or of B). B, for example, is useful to shift parentheses on the left. Such exercises need a bit of training and a taste for programming or puzzles. I hope that you are able to verify (at least) a solution. Let us verify that L admits another solution based on the use of C:

L = CBM (by which I mean CBM behaves like it is aked for L to behave, i.e. Lxy = x(yy)

Indeed CBMxy = BxMy (because Cabc=acb, or Cxyz = xzy) = x(My) = x(yy).

Such a sequence of application of the dynamical rules will be what I mean by the term "computation". This will be justify when we will see that the combinators are Turing-equivalent. Any program can be matched by a combinator.

Note also this. We see that SB(KM) and CBM are two different programs computing L. But SB(KM), that is S(S(KS)K)(KS(SKK)(SKK)), and CBM, that is S((S(KS)K)(S(KS)K)S)(KK)(S(KS)K)(S(SKK)(SKK)) are different combinators doing the same things. We will use the (extensionality) rule which identifies the combinators which have the same behavior. When two combinators are syntactically identical, we will use the expression "strictly identical" (written ==). A (more simple) example is:

I = SKK = SKS = SK(KK) = ....

`They all give an identity combinator. But none can be obtained from this`

other by a reduction, i.e. an application of the dynamical rule from left to right (like

in a computation).

other by a reduction, i.e. an application of the dynamical rule from left to right (like

in a computation).

Finally, because the combinators we have met so far will play some persisting role in the sequel, they deserve names. I give you the (birdy) terminology of Smullyan:

`K is the kestrel. It is "the" eliminator. K(KK)(SSS) eliminates (SSS) for example.`

S is the starling. S does many things at once: it duplicates, composes, and permutates

its arguments: Sxyz = xz(yz). Look carefully.

T is the trush. It is a crude permutator. It permutates its arguments: Txy = yx.

M is the mocking bird itself! It is just a crude duplicator: Mx = xx.

C is the cardinal. C is called the elementary or regular permutator.

It is less crude than the trush. Much more easy to use, like in general the regular

combinators, which by definition are those combinators which leaves unchanged they

first argument. All combinators seen so far are regular except the trush.

W is the warbler. It is the elementary duplicator (less crude thanb the mocking bird!).

B is the elementary compositor. Bxyz = x(yz). Suppose that f = log, and g = sin,

then Bfgx = log(sin x), so that Bfg gives f ° g. That is the composition of the functions

f and g. I forget to say that B is called the blue bird.

L is the lark: it is an hybrid of a warbler or a mocking bird and a compositor.

S is the starling. S does many things at once: it duplicates, composes, and permutates

its arguments: Sxyz = xz(yz). Look carefully.

T is the trush. It is a crude permutator. It permutates its arguments: Txy = yx.

M is the mocking bird itself! It is just a crude duplicator: Mx = xx.

C is the cardinal. C is called the elementary or regular permutator.

It is less crude than the trush. Much more easy to use, like in general the regular

combinators, which by definition are those combinators which leaves unchanged they

first argument. All combinators seen so far are regular except the trush.

W is the warbler. It is the elementary duplicator (less crude thanb the mocking bird!).

B is the elementary compositor. Bxyz = x(yz). Suppose that f = log, and g = sin,

then Bfgx = log(sin x), so that Bfg gives f ° g. That is the composition of the functions

f and g. I forget to say that B is called the blue bird.

L is the lark: it is an hybrid of a warbler or a mocking bird and a compositor.

`Exercise:`

We have seen how to program the blue bird B, the cardinal C and the Warbler W

with the kestrel K and the starling S. Could you define the starling S from B, W and C?

I give you the first line: Sxyz = xz(yz)

= Cx(yz)z

= ...

We have seen how to program the blue bird B, the cardinal C and the Warbler W

with the kestrel K and the starling S. Could you define the starling S from B, W and C?

I give you the first line: Sxyz = xz(yz)

= Cx(yz)z

= ...

Bruno

http://iridia.ulb.ac.be/~marchal/