Combinatory Completeness in Joy

[btanksley@hifn.com]

From: iepos@tunes.org [mailto:iepos@tunes.org]

>A while back we discussed how it is possible from
>the four primitives "swap", "dup", "pop", and "dip" to form
>all stack-manipulators of a certain kind... among those that
>could be formed:

>These kinds of combinators I will call the "regular combinators"
>of Joy (because they correspond to the regular combinators of
>applicative systems); unlike "dip", "cons", and "concat", 
>regular combinators do not have any quoting or unquoting effects.

Did you know that applicative system do not have ANY combinators without
'quoting or unquoting' effects?  So technically, your terminology is
backwards.

>Anyway, irregular combinators are quite important too, and should
>not be neglected... As yet, I haven't said much about them, or
>how they can be constructed from one another. It turns out
>that the above four combinators, along with "i" and "cons", are enough
>to form all combinators (regular and irregular); moreover,
>"swap" is not necessary, as it can be constructed from the others as

>  [] cons dip

>All right, now to show how it is that "dup", "pop", "dip", 
>"cons", and "i"
>form a complete base...

First, get rid of i.  dip takes care of it:

  i == dup dip pop;

So dup, dip, pop, and cons form our combinators.  uncons, IMO, is also
important (although it has no equivalent I can think of with applicative
systems).

>Anyway, this whole thing illustrates that lambda-like things are
>not a characteristic of just applicative systems; they can be
>used naturally in concatenative systems too (but, they can also be
>eliminated in both applicative systems and concatenative systems).

Absolutely.  They're useful in proofs, too.  I've seen many people who are
addicted to them, thanks to bad prior experience with non-combinatorial
applicative languages; in Forth, the closest equivalent is "local
variables".

>  The combinators in the base are sufficient to eliminate all
>  lambdas. Moreover, all combinators can be formed (using
>  concatenation and quotation) from the combinators in the base.

Excellent statement.

>The second statement is almost a direct consequence of the first;

And vice versa -- but most people are less versed in combinators than they
are in lambda.  Sad.  :-)

>Okay, this is the end now...

>- "iepos" (Brent Kerby)

-Billy