Re: [stack] Concatenative macros?

Hi Billy & all,

It's been a while! Sorry this post is a little belated. I tried 
sending it last week, but something was wrong with my account (my 
concatenative membership had expired, apparently; or maybe the list 
was unmoderated back when I used to use it). In any case, Yahoo ate 
my post up, so I had to rewrite it ...

> A doubt begins to stir in my mind. Is the Fokker X combinator 
actually
> a pseudo-combinator? If so, is that a problem with the Fokker X
> combinator, or is it a problem with Kerby's ideas about
> pseudo-combinators? 

Yes. The Fokker X combinator would be a "pseudo-combinator". But 
that was a bad choice of terminology on my part. Under the standard 
definition, it is a combinator. The restricted objects I was calling 
combinators are what Curry called "proper combinators". So we ought 
to say that the Fokker X combinator is an improper combinator, but a 
combinator nonetheless. To recap, here are the standard definitions 
which I should have used:

Proper combinator: Any closed lambda-form in which all lambdas occur 
at the head (i.e., at the far left).

Combinator: Any closed lambda-form whatsoever (or, equivalently: any 
combination of proper combinators)

This applies to both applicative and concatenative systems (although 
the interpretation of "lambda" and "combination" of course depends 
on which system we're dealing with). Another way of putting it is 
that proper combinators are ones that can be expressed by a rewrite 
rule; i.e., in an applicative system, Z is a proper combinator if 
you can state a rule

  Zxyz == (some applicative combination of x, y, and z)

or the like, with as many variables as needed; the standard 
combinators S, K, I, B, C, W, T, etc. are all proper, while the 
Fokker X combinator and, for example, Y, the "paradoxical" or fixed-
point combinator, are not. 

Likewise, in a concatenative system, Z is a proper combinator if you 
can state a rule

  [z] [y] [x] Z == (some concatenative combination of x, y, and z)

or the like, with as many variables as needed. The standard 
combinators i, cons, dip, cat, swap, dup, zap, k, and cat are all 
proper.

Now, since the Fokker X combinator is improper, the question 
naturally arises: Is there a complete basis (in applicative 
combinatory logic) consisting of a single _proper_ combinator? The 
answer is no. The standard proof (due to William Craig) goes roughly 
like this: Every basis of proper combinators must contain a 
selector, i.e., a combinator like I or K, that takes some parameters 
(in a curried fashion, of course) and returns a certain one of them 
untouched, ignoring the rest. This is because selectors cannot be 
constructed out of other proper combinators; this can been seen by 
looking at the rewriting process: An expression Fxyz, for example, 
where F is written as some combination of proper combinators A, B, 
C, ..., none of which is a selector, can never reduce to just the 
the single variable 'x' by applying rewrite rules, because the 
rewrite rules for A, B, C, ... each have a right-hand-side 
consisting of something more than just a single variable. There is a 
combinator F (namely, the selector \xyz.x) for which Fxyz would 
reduce to x; but it is impossible to construct this F, or likewise, 
any selector, from a basis of non-selectors. Therefore, in a basis 
consisting of a single proper combinator, this combinator must be a 
selector. But selectors have no duplicative effect; therefore, it 
would be impossible to construct "W" or "S", for example. So a 
complete basis consisting of a single proper combinator does not 
exist.

So in a complete basis of proper combinators, we need at least two. 
And of course it turns out that two is enough, since {S, K} is a 
complete basis. But if you allow improper combinators, then one is 
enough, as the Fokker X combinator shows, for instance.

Now, what about in a concatenative system? Well, using an argument 
similar to the one above, we can show that a basis consisting of a 
single proper combinator is again impossible. This is because any 
basis of proper combinators must contain what I'll call a "total 
dequoter", i.e., a combinator whose right-hand-side contains no 
quotations; total dequoters simply execute some of their parameters 
(possibly multiple times, or none at all) in a certain order;  
examples would be i, k, zap, 'cat i', and

  X\ Y\ Z\ W\ Y X W X

A total dequoter is needed, because if every combinator in the basis 
had a quotation on the right-hand-side, then it would never be 
possible to get down to an empty stack, once a quotation was on it; 
specifically, the expression [] F, where F is written as some 
combination of proper combinators A, B, C, ..., none of which is a 
total dequoter, could never reduce to the empty program, which shows 
that 'i' could not be constructed, since 'i' would be an F that 
works. Therefore, in a basis consisting of a single proper 
combinator, this combinator must be a total dequoter. But from a 
total dequoter alone, it is clearly impossible to construct cons, or 
even swap, dup, dip, or cat. So a basis consisting of a single 
proper combinator again does not exist.

So the best we could hope for would be a two-combinator basis of 
proper combinators, or a one-combinator basis consisting of an 
improper combinator. We know that a basis of two proper combinators 
is possible; for example, {cake, k} works.

So what about a one-combinator basis? This is an interesting 
question. It will not work to simply take the concatenative version 
of the Fokker X combinator (or the Rosser, or any other applicative 
one-combinator complete basis).  This would be equivalent to the 
basis {s, k}, which is _not_ complete in a concatenative system. 
From {s, k}, we can construct all applicative combinators (i, b, c, 
etc.) and even many others (swap, cons, dup, zap), but it would be 
impossible to construct dip (or cat). You can see this by looking at 
the rewrite rules for 's' and 'k':

[Z] [Y] [X] s  ==  [[Z] Y] [Z] X
    [Y] [X] k  ==  X

Note that on the right-hand-side of both rules, there is nothing to 
the right of the only dequoted term X. In reducing the 
expression '[B] [A] F', where F is some (concatenative) combination 
of 's' and 'k', every step of the reduction preserves the property 
that no subexpression contains a (dequoted) A followed by anything 
containing B; therefore, it could never reduce to 'A [B]'. So it is 
impossible to construct dip from {s, k}.

But after some fiddling, I was able to find a one-combinator base 
that does work. The idea is to make a combinator with 'cake' and 'k' 
somehow embedded in it, built in such a way that, with a little 
manipulation, we can extract them back out. Let

z == X\ zap [cake] [k] X

or, in other words,

z == [zap [cake] [k]] dip i

Then

[] [] z z
== [] zap [cake] [k] z
== [cake] [k] z
== [cake] zap [cake] [k] k
== [cake] [k] k
== k

So we can construct k. And

[] [] [zap k] z 
== [] [] zap [cake] [k] zap k
== [] [cake] [k] zap k
== [] [cake] k
== cake

So we can construct cake. Explicitly, we can write them

k    == [] [] z z
cake == [] [] [[] [] [] z z [] [] z z] z

So this {z} forms a complete basis. Incidentally, this construction 
doesn't depend specifically on 'cake'; you could replace 'cake' with 
any combinator that, along with 'k', forms a complete basis.

- Brent