4 ms·
Think of the "birds" (combinators) acting on a combined set of both the birds and the shapes. Don't forget that parenthesized blocks of birds and shapes are con
by kamray23 4y ago
Think of the "birds" (combinators) acting on a combined set of both the birds and the shapes. Don't forget that parenthesized blocks of birds and shapes are considered a single "letter" for manipulation. For an example of these in action, take this application to SS(SK), equivalent to W, with three inputs a, b, and c:
-- reminder of the definitions
Sxyz → xz(yz)
Kxy → x
-- always expanding the leftmost combinator
SS(SK)abc
→ Sa(SKa)bc
→ ab(SKab)c
→ ab(Kb(ab))c
→ abbc
The biggest leap to make is the first to the second line. S here is the x, a is the z, and (SK) is the y. Then with a little imagination you should be able to see that the expression morphed into xz(yz) with whatever wasn't touched, in this case bc, just kind of stuck on the end.
This also shows that the definition of the W-combinator given in the article
Wxyz → xyyz
is a little overenthusiastic in having three arguments. The last one is actually never touched with the SK-definition!
Wxy → xyy
would actually be enough, and it's the canonical definition for it when working with combinatory logic in a more serious context.