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: ...
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
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:
as can be verified by feeding the equation Axyz=xz(zy)
to the combinator-finder program
BCSI command-line option)
as well as by explicit computation: