# COMBINATORS II (solution of exercises)

From: Bruno Marchal <marchal.domain.name.hidden>
Date: Fri, 04 Feb 2005 15:16:48 +0100

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/
Received on Fri Feb 04 2005 - 09:16:17 PST

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:10 PST