My apologies to the many people (I hope) reading this list and hoping
for something useful. This stuff is a LONG way from usefulness. I hope
that it will sharpen our understanding of what it means to be
concatenative; I hope that after I understand this I'll be better
equipped to explain the potential benefits.

For now, just treat this as a puzzle: to be solved if it entertains,
and skipped otherwise.

iepos <bkerby@...> wrote:
> Also, it
> is certainly possible that a more clever choice of basis could lead
> to smaller constructions.

I chose a different basis which results in shorter constructions for
the primitives we're producing. I think it's universally shorter; my
reason for suspecting that is that your 'o' and 'i' operations have
very asymmetric stack effects, so in general you have to execute a LOT
of 'i's for every 'o'. I also personally found it to be much simpler
to derive results for.

Let
0 = [] [q] [k]
1 = k

In this experiment, I didn't change the sequence of the 'o'
combinator. One interesting (to me) implication is that 'k' is very
exposed -- it's the last operation in both combinators. The other
simple choice would be to define 0 as [] [k] [q]; doing that seems to
result in slightly more complex forms for some primitives, but might
make others much simpler. (I need to work that out in full.) The other
permutations should be interesting as well, but now we're talking
computer work, not human work.

I originally chose 'k' so that the VM only needs to define 2
operations, q and k (rather than having to define q, k, and i). I also
suspect that it'll reduce faster, since there's less asymmetry between
'0' producing stack items and '1' consuming them.

Construct 'k':
1 =
k

Construct 'zap':
01 =
[] [q] [k] k =
[] k =
zap

(A simple 'zap' is very useful. It allows me to easily get at the
functions contained in '0'. It also promises a nice peephole
optimizer, since I have meanings for both "1" and "01"!)

Construct 'q':
0011 =
0 01 1 =
[] [q] [k] zap k =
[] [q] k =
q

Construct '[]':
00101 =
0 01 01 =
0 zap zap =
[] [q] [k] zap zap =
[]

Construct 'i':
00101 0011 1 =
[] q k =
i

Construct 'unit':
00101 0011 01 =
[] q zap =
unit

Construct 'nip':
00101001101 1 =
unit k =
nip

Construct 'swat':
0011 001010011011 =
q nip

> [] == oooooiiiiiiioooooiiiiiiii

[] = 00101

> [k] == oooooiiiiiiioooooiiiiiiioooooiiiiiiiioii

[k] = 0 nip nip ==
0 001010011011 001010011011

(That's 26 bits for the k system, versus 41 when using 'i'. This is
the closest thing to a tie.)

> unit == oooooiiiiiiioooooiiiiiiiioioooooiiiiiiii

unit == 00101001101

> swat ==
> oioooooiiiiiiioooooiiiiiiiioioooooiiiiiiiioooooiiiiiiioooooiiiiiiioooo
> oiiiiiiiioiii

swat == 0011001010011011

> [q] ==
> ooooooiiiiiiiioooooiiiiiiioooooiiiiiiiioioooooiiiiiiiioooooiiiiiiioooo
> oiiiiiiioooooiiiiiiiioiii

[q] = 0 zap nip ==
0 01 001010011011

Seems like I had a good intuition. Balance them combinators!

I still need to explore the effect of using cake instead of q. I also
need to (just as an exercise) express 'dip' and 'swap' in this system.
So far I haven't (I've tried...).

> - Brent

-Billy