COMBINATORS I was

http://www.escribe.com/science/theory/m5913.html

I recall all you need to know:

Kxy = x Sxyz = xz(yz)

That's all! (Well you are supposed to remember also that abc is an abbreviation of ((ab)c), and a(bc) is an abbreviation for (a(bc)).

`I recall the exercices taken from "My First Everything Theory" Primary school Year 2127 :)`

Solution are below.

Evaluate:

Solution are below.

Evaluate:

(SS)KKK = KKK(SS) = ? (KK)(KK)(KK) = ? (KKK)(KKK)(KKK) = ?

Evaluate:

K KK KKK KKKK KKKKK KKKKKK KKKKKKK KKKKKKKK KKKKKKKKK KKKKKKKKKK

`A little more advanced exercices: is there a molecule, let us called it I, having`

the following dynamic: (X refers to any molecule).

the following dynamic: (X refers to any molecule).

IX = X I = ?

`(Note I will use in this context the words molecules, birds, combinators, programs`

as synonymous).

================================

SOLUTIONS:

as synonymous).

================================

SOLUTIONS:

(SS)KKK = SK(KK)K = KK(KKK) = K KKK(SS) = K(SS) (KK)(KK)(KK) = KK(KK)(KK) = K(KK) (KKK)(KKK)(KKK) = KKK = K

Note that the passage (KK)(KK)(KK) = KK(KK)(KK) comes just from a use of the parentheses abbreviation rule which help to see the match with the dynamic of K : Kxy = x, and indeed KK(KK), when occuring at a beginning, matches Kxy with x = K and y = (KK) = KK.

K = K KK = KK KKK = K KKKK = KK KKKKK = K KKKKKK = KK KKKKKKK = K KKKKKKKK = KK KKKKKKKKK = K KKKKKKKKKK = KK

ok? (this was easy! if you have not succeed it means you are imagining difficulties). The next exercise is slightly less easy, we are to program some identity operatort.

Ix = x I = ?

We must find a program (that is a combinator, that is a combination of K and S) which applied on any X gives that X. We want for example that

I(KK) = (KK) I(SSS) = SSS etc.

So we want that for all x Ix = x. But only Kxy is able to give x so x = Kx? and we want Kx? matching the rule for S (we have only this one), it is easy because whatever ? represents, Kx? gives x. So we can take ? = (K x) or (S x) or etc. This gives x = Kx(Kx) (or x = Kx(Sx) ) so that the rule S can be applied so that

x = Kx(Kx) = SKKx (or x = Kx(Sx) = SKS)

Thus SKKx = x, and so a solution is

I = SKK

It is our first program! Another one is I = SKS (actually SK<anything stable> would work).

Let us verify. i.e. let us test SKK and SKS on KK:

SKK(KK) = K(KK)(K(KK)) = KK SKS(KK) = K(KK)(S(KK)) = KK

more general verification: SKKx = Kx(Kx) = x

Any problem? You see that programming is really inverse-executing.

=============================== New programming exercises:

Find combinators M, B, W, L, T such that

Mx = xx (Hint: use your "subroutine" I, as a "macro" for SKK)

Bxyz = x(yz)

Wxy = xyy

Lxy = x(yy)

Txy = yx

Bruno

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