Re: Re: [stack] Re: Programming Puzzle

> Unless, I am mistaken I believe "dup i" or "recurse" is the classical Y
combinator.

"dup i" is indeed a useful component in building the y combinator, although they are not the same. The difference is this:

[P] dup i == [P] P
[P] y == [[P] y] P

"dup i" is the concatenative equivalent of the classical combinator M (= \f. ff), the combinator which applies its operand to itself. The classical construction of Y in terms of M is BM(CBM), which works like so:

Yf == BM(CBM)f
== M(CBMf)
== M(BfM)
== BfM(BfM)
== f(M(BfM))
== f(Yf)

This corresponds to the concatenative construction

y == [[m] [b] c] [m] b

or, written in terms of more familiar combinators (using b == [cons] dip i, c == [swap] dip i)

y == [[dup i] [b] c] [dup i] b
== [[dup i] swap b] cons dup i
== [[dup i] swap [cons] dip i] cons dup i

which works like so:

[P] y == [P] [[dup i] swap [cons] dip i] cons dup i
== [[P] [dup i] swap [cons] dip i] dup i
== [[dup i] [P] [cons] dip i] dup i
== [[dup i] cons [P] i] dup i
== [[dup i] cons P] dup i
== [[dup i] cons P] [dup i] cons P
== [[[dup i] cons P] dup i] P
== [[P] y] P

Manfred has offered a simpler concatenative "y" combinator (at http://www.latrobe.edu.au/philosophy/phimvt/joy/j05cmp.html, in the section "The fixpoint theorem and the y combinator")

y == [dup cons] swap concat dup cons i
== [dup cons] swap concat dup i

which works like so:

[P] y == [P] [dup cons] swap concat dup i
== [dup cons] [P] concat dup i
== [dup cons P] dup i
== [dup cons P] dup cons P
== [[dup cons P] dup cons P] P
== [[P] y] P

With the "y" combinator, making a "while" loop is quite straightforward:

[Pred] [Body] while == [[Pred] [[Body] dip i] [pop] ifte] y

or, abstracting out Pred and Body,

while == [dip i] cons [[pop] ifte] cons cons y

Actually, we can accomplish this task even without using "ifte" as a primitive, if you are willing to identify true and false with the following combinators:

true == zap i
false == dip zap

These choose the first or second program on the stack to execute, respectively, i.e.

[P] [Q] true == P
[P] [Q] false == Q

Then we can construct "ifte" simply as

ifte == dig i

so that

[true] [P] [Q] ifte
== [true] [P] [Q] dig i
== [P] [Q] [true] i
== [P] [Q] true
== P

whereas

[false] [P] [Q] ifte == Q

(However, this does not reproduce the peculiar stack saving and restoring behavior of Joy's "ifte".)

This example is an illustration of the well-known fact that you can build essentially any control flow construct you want from combinators alone. In fact, there is a very simple two-combinator basis {q, k} for concatenative combinators, as Billy and I were discussing a few months ago:

[B] [A] q == [[B]] [A B]
[B] [A] k == A

Their constructions in terms of familiar combinators would be

q == swap dup [concat] dip unit swap
k == dip pop == swap pop i

So just from these two combinators alone you can build loops, conditionals, logical and numeric operators, and essentially anything else you want. Perhaps even more surprising is that from two (improper) combinators "o" and "k" (where o == [] [q] [k]), it is possible, _even without the use of quotation_, to build any concatenative combinator whatsoever (see the thread "Flat concatenative basis" from early February). Billy likes to call these combinators "0" and "1", since this suggests an obvious encoding of any concatenative program as an integer represented in binary. For example,

i == 0010100111
unit == 00101001101

Observing that every valid program begins with a 0, not a 1, I guess it might be preferable to interchange the roles of 0 and 1, so that as this encoding would be one-to-one (otherwise we have, for example, 0011 and 011 encoding the same integer, although they represent different combinators). Alternatively, we could keep 0 and 1 as they are, but read them as little-endian, the last bit being most significant; this would also work, since no power is lost by requiring every program to end in a 1. I would tend to favor the former option, if nothing else for esthetic reasons -- k, given its more destructive nature, relative to "o", would more aptly be represented by 0 ...

Sorry, I've gone off on a bit of a tangent; I just think this is quite an interesting result that's worth mentioning again.

- Brent