For your amusement here is a fun programming puzzle:

Define a while loop that takes a loop body and termination predicate
in Joy using only the following combinators:

"ifte","cat","swap","dup","pop","i","dip" and "unit"

Cheers,
Christopher

Joshua Shinavier — 2007-05-17 00:18:40

Well, this seems to work:

DEFINE mywhile ==
swap [dup] dip swap
[[dup dip] dip mywhile] cons cons
[]
ifte.

E.g.

1 [2 *] [dup 100 <] mywhile.

yields 128. However, it uses cons, which is not in your list. I think I
should be able to construct cons like so:

DEFINE cons == [unit] dip concat.

...if only knew how to construct unit :-)

Josh

On 5/16/07, Christopher Diggins <cdiggins@...> wrote:
>
> For your amusement here is a fun programming puzzle:
>
> Define a while loop that takes a loop body and termination predicate
> in Joy using only the following combinators:
>
> "ifte","cat","swap","dup","pop","i","dip" and "unit"
>
> Cheers,
> Christopher
>
>

[Non-text portions of this message have been removed]

Christopher Diggins — 2007-05-17 00:43:13

Well done!

I made a mistake with my Joy words: "cat" is supposed to be "concat".

I did include "unit" in my list, so the construction is valid according to
the rules I set out.
I also believe in Joy you can define unit as "[] concat", am I correct?

Second puzzle: do the same without using the name of the function in the
definition.

Does any know of smaller constructions?

- Christopher

On 5/16/07, Joshua Shinavier <parcour@...> wrote:
>
> Well, this seems to work:
>
> DEFINE mywhile ==
> swap [dup] dip swap
> [[dup dip] dip mywhile] cons cons
> []
> ifte.
>
> E.g.
>
> 1 [2 *] [dup 100 <] mywhile.
>
> yields 128. However, it uses cons, which is not in your list. I think I
> should be able to construct cons like so:
>
> DEFINE cons == [unit] dip concat.
>
> ...if only knew how to construct unit :-)
>
> Josh
>
> On 5/16/07, Christopher Diggins <cdiggins@... <cdiggins%40gmail.com>>
> wrote:
> >
> > For your amusement here is a fun programming puzzle:
> >
> > Define a while loop that takes a loop body and termination predicate
> > in Joy using only the following combinators:
> >
> > "ifte","cat","swap","dup","pop","i","dip" and "unit"
> >
> > Cheers,
> > Christopher
> >
> >
>
> [Non-text portions of this message have been removed]
>
>
>

[Non-text portions of this message have been removed]

Ivan Tomac — 2007-05-17 00:45:34

--- In concatenative@yahoogroups.com, "Christopher Diggins"
<cdiggins@...> wrote:

> Define a while loop that takes a loop body and termination predicate
> in Joy using only the following combinators:
>
> "ifte","cat","swap","dup","pop","i","dip" and "unit"
>

LIBRA

(* Joy doesn't appear to have unit and cat combinators - unit == [] cons
? *)

unit == [] cons ;
cat == concat ;

(* first thing's first - define cons *)

cons == [unit] dip cat ;

make-recursive == [dip dup i] cons ;
fix-predicate == [dip swap ] cons ;

construct-loop == [[pop] ifte] cons cons ;

recurse == dup i ;

while == [fix-predicate] dip make-recursive construct-loop recurse .

10 [0 >] [dup put 1 -] while .

> Cheers,
> Christopher
>

Ivan

[Non-text portions of this message have been removed]

Christopher Diggins — 2007-05-17 00:59:48

Very nice!

I particularly like the use of intelligible names, something I too often
fail to do.
Unless, I am mistaken I believe "dup i" or "recurse" is the classical Y
combinator.
Notice the second occurence of "dup i" hidden in the definition of
"make-recursive",
which makes sense given the name. ;-)

I am going to have to throw some harder puzzles at this gang ;-)

- Christopher

On 5/16/07, Ivan Tomac <e1_t@...> wrote:
>
> --- In concatenative@yahoogroups.com <concatenative%40yahoogroups.com>,
> "Christopher Diggins"
> <cdiggins@...> wrote:
> > Define a while loop that takes a loop body and termination predicate
> > in Joy using only the following combinators:
> >
> > "ifte","cat","swap","dup","pop","i","dip" and "unit"
> >
>
> LIBRA
>
> (* Joy doesn't appear to have unit and cat combinators - unit == [] cons
> ? *)
>
> unit == [] cons ;
> cat == concat ;
>
> (* first thing's first - define cons *)
>
> cons == [unit] dip cat ;
>
> make-recursive == [dip dup i] cons ;
> fix-predicate == [dip swap ] cons ;
>
> construct-loop == [[pop] ifte] cons cons ;
>
> recurse == dup i ;
>
> while == [fix-predicate] dip make-recursive construct-loop recurse .
>
> 10 [0 >] [dup put 1 -] while .
>
> > Cheers,
> > Christopher
> >
>
> Ivan
>
> [Non-text portions of this message have been removed]
>
>
>

[Non-text portions of this message have been removed]

Brent L Kerby — 2007-05-19 05:06:59

> 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

Christopher Diggins — 2007-05-19 05:22:46

On 5/18/07, Brent L Kerby <bkerby@...> wrote:

>
> > 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.

Ah yes! Thank you for the correction.

> 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")

I notice he calls "M" "x".

> 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.

As always I enjoy your posts and insights Brent.

- Christopher

William Tanksley, Jr — 2007-05-19 16:33:37

Brent L Kerby <bkerby@...> wrote:

> Observing that every valid program begins with a 0, not a 1,

An interesting point. I had to think about that... Of course you mean
every valid program for an initially empty stack. If you allow the
stack to contain initiial input, 1 is an acceptable start.

> - Brent

-Billy

> An interesting point. I had to think about that... Of course you mean
> every valid program for an initially empty stack. If you allow the
> stack to contain initiial input, 1 is an acceptable start.

Right, good point.

> -Billy

- Brent

Programming Puzzle

Christopher Diggins — 2007-05-16 22:46:06