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/
Received on Tue Feb 08 2005 - 06:52:28 PST