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