Re: [stack] Syntax for combinators

On 4/5/07 6:15 PM, "Manfred Von Thun" <[email protected]> wrote:

> So the ifte combinator can be defined in tems of nullary and dip. Presumably
> the nullary combinator will evoke the same wide variety of reactions from
> programmers as the ifte combinator. By way of contrast, the dip combinator
> has never evoked such a variety. But what is surprising is that nullary need
> not be a primitive combinator, it can be defined in terms of dip or in terms
> of infra. I cannot remember the two definitions right now. But I¹ll look
> them up at home and post them next week.
> 
Here we are:

First, two older versions:

nullary == [stack] dip infra first
nullary == [stack] dip dip cons unstack

My current favourites, using just one combinator (infra or dip):

nullary == stack rest swap infra first
nullary == stack rest swap dip cons unstack

With the wisdom of hindsight this should not really be a surprise.
Given any stack, the stack operator will produce essentially two
identical lists: the original stack and a copy (in the form of a list).
Put a quotation on top, and then the dip operator and the infra operator
can use the quotation to change the original or the copy.
So there exists some kind of symmetry between dip and infra.
If I had understood this earlier, I might have chosen two more
symmetric names for the two combinators.

I have not succeeded to define dip in terms of infra, or to
define infra in terms of dip. I don¹t know whether this is just
failure of the imagination or whether this is just impossible.
And this raises another question: Is there some technique by
which one can show that it is impossible to define one thing
in terms of a given set of others? I only have the vaguest
recollection of seeing a proof that ³not² cannot be defined
in terms of ³and² and ³or². Obvious, yes. But is there a
general technique?

  - Manfred





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