[stack] Re: Concatenative macros?

Billy and all,

Sorry for taking so long to respond to this. When I first read your 
email, the server hosting Chris Okasaki's paper was apparently down. 
And then for a couple weeks I forgot to come back and try it again. I 
must say -- What he's accomplished is pretty cool. 

> My question is: how does Okasaki's and Barker's work apply to this?
> Okay, actually, what I want to know is how to design a flat,
> two-combinator, concatenative language that's implemented using 
stacks
> and lists (like Joy).

I want to respond to your second question first; hopefully this will 
in turn shed some light on the relationship between flat 
concatenative systems and Okasaki's and Barker's work.

When I wrote that flaky old program that searches for optimal Joy 
constructions, I put in an option to search only for flat 
constructions (activated by uncommenting the line "//#define 
NOQUOTES" :-) ) but never really pursued the problem, although I 
agree it is an interesting one.

Let's try this. We're looking for a finite set of combinators from 
which we can construct any combinator by concatenation alone (no 
quotations). We'll say that such a set of combinators forms complete 
flat basis. To start, we observe that if "z" is any combinator  
forming a complete (non-flat) basis (for example, z == X\ zap [cake] 
[k] X, as we've seen), then {[], [z], unit, cat, i} forms a complete 
flat basis. Any concatenative combination of "z" can be decomposed 
into a flat one in terms of these combinators quite easily; For 
example, 

   [z [z z] z]
== [z] [[z z] z] cat
== [z] [[z z]] [z] cat cat
== [z] [z z] unit [z] cat cat
== [z] [z] [z] cat unit [z] cat cat

If the expression had contained a dequoted 'z', then we would have 
needed to use '[z] i' (or, if desired, we could have included 'z' in 
the basis instead of i); and if the expression had contained a null 
quotation, we would have had to use []. In this way, we can decompose 
any concatenative combination of "z", and hence any combinator 
whatsoever, into a flat expression in terms of {[], [z], unit, cat, 
i}.

Now, we can do better than that. You really want a basis in terms of 
just two combinators (not five). So let's think about what would have 
to be true about such a basis:

1. One of the two combinators must be able to execute on an empty 
stack; therefore it must do nothing but push a sequence of constant 
quotations onto the stack (This will necessarily be an improper 
combinator).

2. The other combinator must be a total dequoter, such as 'i' or 'k' 
(otherwise, roughly speaking, it's impossible to get down to an empty 
stack again once anything has been pushed onto it).

It might be possible to relax the first requirement if our system has 
a "bottomless stack", i.e., if we can assume infinitely many stack 
items are always available if needed, so that "[] dip" is considered 
equivalent to the empty program (analagous to the beta-eta-theory of 
classical combinatory logic, as opposed to the beta-theory). In any 
case, this won't be necessary, because it turns out there is a 
solution satisfying both requirements.

Also, intuitively, the empty quotation [] must be embedded somehow in 
the first combinator. My first attempts at a two-combinator flat 
basis were {[] [z], i}, {[z] [], i}, {[] [cake] [k], i}, {[cake] [k] 
[], i}, and so forth, before realizing that these are all doomed 
because it is impossible to construct "cat" from them. But I'll skip 
over my failed attempts and cut straight to one that works. To do 
this, first define a new combinator "q":

[B] [A] q == [[B]] [A B]

This combinator, along with k, forms a complete basis (in the 
ordinary, non-flat sense). This is interesting in itself, since "q" 
is a bit simpler than "cake" ({cake, k} formerly being the simplest 
known basis of two proper combinators). But, as you've mentioned, 
Billy, it's not exactly clear how to count the size of a combinator. 
In my search program, I've counted it as the total number of atoms 
plus the number of quotations (so "q" would be size 6, 3 atoms plus 3 
quotations, while "cake" would be size 8, 4 atoms plus 4 quotations); 
but other schemes may be equally valid.

Anyhow, here are the essential constructions from {q,k}:

zap  == [] k
i    == [] q k
unit == [] q zap
swat == q unit k     (where swat == X\ Y\ [X Y] == swap cat)
dip  == unit [unit] swat i swat i
dup  == [] q unit swat i

I'll give the verification of "dip", the most interesting of these:

[Y] [X] unit [unit] swat i swat i
== [Y] [[X]] [unit] swat i swat i
== [Y] [unit [X]] i swat i
== [Y] unit [X] swat i
== [[Y]] [X] swat i
== [X [Y]] i
== X [Y]

It's worth noting that 

  swat i == X\ Y\ X Y == dip i

This combinator simply executes the top two programs on the stack. It 
may be constructed simply as "q k". Using this makes the above 
constructions of "dip" and "dup" much more efficient (In fact, a 
computer search shows that they are then minimal, in terms of their 
size as combinations of the original base combinators "q" and "k").

Also, notice that the constructions of unit and swat (as well as zap, 
i, and dup) are flat in terms of [], q, and k. This will be useful to 
us in a moment. But I want to emphasize that I'm not claiming that 
{q, k} is a complete flat basis, because it certainly isn't. However, 
{q, k} is complete in the ordinary sense, and will be useful in 
building a flat basis:

All right, so for a two-combinator basis, define:

o == [] [q] [k]

Then {o,i} is a complete flat basis. To prove this, we just need to 
show how to construct each combinator in {[], [q], [k], swat, unit}, 
because this set, along with "i", clearly forms a complete flat 
basis, applying with minor adjustment the simple algorithm 
illustrated above for {[], [z], cat, unit, i}, noticing that "swat" 
will do just as well as "cat". 

So here we go. First, as an auxiliary step, we find that

oi == q 

and 

ooooqiiiiii == [][k]

(We might as well dispense with unnecessary spaces). Here's the 
verification:

oi
== [][q][k]i
== [][q]k
== q

ooooqiiiiii
== ooo[][q][k]qiiiiii
== ooo[][[q]][kq]iiiiii
== ooo[][[q]]kqiiiii
== ooo[q]qiiiii
== oo[][q][k][q]qiiiii
== oo[][q][[k]][qk]iiiii
== oo[][q][[k]]qkiiii
== oo[][[q]][[k]q]kiiii
== oo[][k]qiiii
== oo[[]][k[]]iiii
== oo[[]]k[]iiii
== oo[[]]kiii
== o[][q][k][[]]kiii
== o[][q][]iii
== o[][q]ii
== o[]qi
== [][q][k][]qi
== [][q][[k]][k]i
== [][q][[k]]k
== [][k]

From this we can get zap:

zap == [][k] i

The verification:

[A][][k]i
== [A][]k
==

Now we can construct []:

[] == [][k] zap

This was one of the five we wanted. So, one down, four to go. 
Actually, we're done with most of the hard work. Next construct [k]:

[k] == [][k] [] q i

The verification:

[][k][]qi
== [][[k]][k]i
== [][[k]]k
== [k]

Now take advantage of our original flat constructions of "unit" 
and "swat":

unit == [] q zap
swat == q unit k

Now it remains only to construct [q]. (Note we already 
constructed "q" at the very beginning, but in a flat system, this is 
not enough.): 

[q] == o zap unit k

The verification:

o zap unit k
== [][q][k] zap unit k
== [] [q] unit k
== [] [[q]] k
== [q]

So there we have it! We can write all this explicitly as

[]   == oooooiiiiiiioooooiiiiiiii
[k]  == oooooiiiiiiioooooiiiiiiioooooiiiiiiiioii
unit == oooooiiiiiiioooooiiiiiiiioioooooiiiiiiii
swat == 
oioooooiiiiiiioooooiiiiiiiioioooooiiiiiiiioooooiiiiiiioooooiiiiiiioooo
oiiiiiiiioiii
[q] == 
ooooooiiiiiiiioooooiiiiiiioooooiiiiiiiioioooooiiiiiiiioooooiiiiiiioooo
oiiiiiiioooooiiiiiiiioiii

Of course, these constructions could probably be improved; my poor 
little Joy searcher (among other restrictions) only works on a basis 
of proper combinators, which does not apply in this case. So I'm not 
able to determine what the minimal constructions might be. Also, it 
is certainly possible that a more clever choice of basis could lead 
to smaller constructions.

- Brent