Re: [stack] Combining Combinators

On 15/6/07 11:40 PM, "William Tanksley, Jr" <[email protected]> wrote:
> 
> Manfred Von Thun <[email protected] <mailto:m.vonthun%40latrobe.edu.au>
> > wrote:
> 
>> > Years ago I sometimes wondered whether there could be
>> > any higher order combinators.
> 
> I don't see how there couldn't be. Joy functions are higher-order, so
> wouldn't Joy's combinators also be higher-order?

My understanding is that the usual terminology is this:
At level zero there are numbers, chars, truth values, lists...
At level one there are functions successor, +, and ...
At level two there are combinators, functions which take functions
as arguments (or as values): map, fold, and many more.
I was looking for something at level three: functions which
take combinators as arguments, but which are distinct from
combinators themselves. I never found any that are distinct
from the existing bunch of Joy combinators. But there are
plenty of ways in which a combinator D can take a quoted
combinator [C] as argument, as in [C] D. The note I wrote
only examined 8 of the 64 combinations that I hinted at.
There are even more combinations once we allow combinators
that take more than one quotation, or once we allow more
complex constructions. A trivial example is

5 [dup *] [i] [i] [i] [i] [i] i  => 25

where all the [i] quotations and the final i are the same i.
The whole area of combining combinators in this way is
a strange new world to me. But it has not led to any combinator
N (for Œnew¹) such that [C] N is meaningful for a combinator [C]
but [Q] N is not meaningful for a non-combinator Q. This
is what I meant by a higher order combinator. But I do not have
a proof that there cannot be such a beast.

  - Manfred



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