COMBINATORS I was http://www.escribe.com/science/theory/m5913.html COMBINATORS II was http://www.escribe.com/science/theory/m5942.html
Resume:
Kxy = x Sxyz = xz(yz)
That's all. (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).
I recall the last exercises: Find combinators M, B, W, L, T and C such that Mx = xx (Hint: use your "subroutine" I, as a "macro" for SKK) Bxyz = x(yz) Wxy = xyy Lxy = x(yy) Txy = yx Cxyz = xzy (I add this one)
I solve the two firsts one: M and B: I recall we have already program the identity combinator I, which is such that Ix = x for any combinators x. it is I = SKK, and we can use it as a "subroutine".
1) We want find a combinator M such that Mx = xx.
We reason again by inverse-execution. We must transform xx in a way such that it matches the right part of the dynamic of K or S. The simplest way is by using I. Indeed xx = Ix(Ix), and this match the S rule.
Thus Mx = Ix(Ix) = SIIx
and thus M = SII= S(SKK)(SKK).
2) We want to find a combinator B such that Bxyz = x(yz)
We need to find an expression equal (by the dynamic rule) to something matching the right part of the S dynamic. We can use I, M or K and S. Here K and S will be enough. Indeed
Bxyz = x(yz) = (Kxz)(yz) because x = Kxz = S(Kx)yz verify with all the parentheses if you don't see it. = KSx(Kx)yz because S = (KSx) = S(KS)Kxyz
Thus B = S(KS)K All right?
Note to understand what will follow it is not really necessary to develop skills in the art of finding those programs, but you should be able to verify them if you want to have the needed passive knowledge. Let us verify B on any x y z:
Bxyz = S(KS)Kxyz = KSx(Kx)yz = S(Kx)yz = Kxz(yz) =x(yz). OK?
Nevertheless I give you time (for the fun) to try to find W, L, T and C. Could you find a combinator called INFINITY which is perpetually unstable? That is INFINITY gives INFINITY, which gives INFINITY etc. (by the K S dynamical rule).
To sum up our work:
I = SKK M = SII = S(SKK)(SKK) B = S(KS)K
Try to find W, with Wxy = xyy, L, with Lxy = x(yy), T with Txy = yx, C with Cxyz = xzy, and INFINITY, with INFINITY dynamically transform into INFINITY itself. No question? Soon (that is after we solve the last problems) we will have enough to make precise some nuances between "mind" and "matter". Already!
Bruno
http://iridia.ulb.ac.be/~marchal/