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:
(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).
IX = X I = ?
(Note I will use in this context the words molecules, birds, combinators, programs
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/
