Page 186

Location: Chapter 19, final Exercise

Exercise (after the Appendix)

In terms of B, C, S, and I, find a combinator A satisfying the condition Axyz=xz(zy). The problem should be divided into three parts: ...

Solution

A = C(BBS)(CI)

Short explanation

As suggested by the text, and according to the algorithm given in the Appendix, the solution proceeds in three steps:

First, a distinguished z-eliminate A_1 of the expression X=xz(zy) must be found. By Rule 3a, this in turn requires to find:

  • a distinguished z-eliminate of xz, which is x (Rule 2);
  • a distinguished z-eliminate of zy, which by Rule 3c is CIy.

Hence it is A_1=Sx(CIy).

The second step consists of finding a distinguished y-eliminate A_2 of A_1: by Rule 3b (and Rule 2), one has immediately

A_2 = B(Sx)(CI)\;.

Finally, one needs a distinguished x-eliminate A of A_2: again according to Rule 3c, to find it one must have a distinguished x-eliminate of B(Sx). This latter term is BBS (applying Rule 3b).

Application of Rule 3c then yields:

A = C(BBS)(CI)\;,

as can be verified by feeding the equation Axyz=xz(zy) to the combinator-finder program (with the BCSI command-line option) as well as by explicit computation:

\begin{align} Axyz =~& C(BBS)(CI)xyz=BBSx(CI)yz=B(Sx)(CI)yz=\\ =~& Sx(CIy)z=xz(CIyz)=xz(Izy)=xz(zy)\;. \end{align}