3 ms·

> The Starling does parenthesising, reordering, and duplication. Applied to three combinators, it applies each of the first two combinators to the last, then ap

by scubbo 4y ago

> The Starling does parenthesising, reordering, and duplication. Applied to three combinators, it applies each of the first two combinators to the last, then applies the first result of that to the second: Can someone help me understand this leap? Thus far, the birds (functions) have been applied to shapes (perhaps "letters", if we are calling parenthesized-sequences of shapes "words"), but now this bird is being applied to combinators (presumably, another word for functions). How should I map from the set {yellow-triangle, red diamond, green circle} to the set {Mockingbird, Kestrel, Thrush, Bluebird, Warbler, ...}?

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.
Jtsummers 4y ago
The colored shapes are arbitrary symbols, variables like in algebra. They could be other combinators or anything in the system. Kx, for instance, always produces whatever x, a variable, happens to be when applied to something else. So KKI will produce K. KIS produces I. So there is no one for one mapping. Any of those birds/combinators or some parenthesized expression of them can be put in place of the colored shapes.

by scubbo 4y ago

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.

Jtsummers 4y ago

The colored shapes are arbitrary symbols, variables like in algebra. They could be other combinators or anything in the system. Kx, for instance, always produces whatever x, a variable, happens to be when applied to something else. So KKI will produce K. KIS produces I. So there is no one for one mapping. Any of those birds/combinators or some parenthesized expression of them can be put in place of the colored shapes.