[stack] Re: Flat concatenative basis (was: Concatenative macros?)

Billy & all,

I hacked at my old Joy searcher for a while and was at last able to 
persuade it to deal with improper combinators; so I've been able to 
determine some minimal constructions for the basis we're looking at, 
i.e., {o,k} where

  o == [] [q] [k]

and 

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

So, it turns out most of the constructions you gave are minimal. An 
improvement was possible only for [q] (from 15 to 8 bits) and [k] 
(from 25 to 18 bits). Here are all minimal constructions for q, [], 
i, unit, nip, swat, [q], and [k]:

q   == ookk         ( == o zap k, same as your construction)
[]  == ookok        ( == o zap zap, same as your construction)
i   == ookokookkk   ( == [] q k, same as your construction)
    == ookoookkkk 
unit== ookokookkok  ( == [] q zap, same as your construction)
    == ookoookkkok
nip == ookokookkokk ( == unit k, same as your construction)
    == ookoookkkokk  
swat== ookkookokookkokk (== q nip, same as your construction)
    == ookkookoookkkokk 
[q] == oookkokk     ( == o q zap k)
[k] == oookokookkookkokkk  ( == o [] q q zap k k)
    == oookoookkkookkokkk 
    
The varients are all due to the equivalence

  okookk == oookkk == zap q

The improvements on [q] and [k] are actually interesting. The 
original construction for [q] was

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

Notice that in the construction 

  unit == [] q zap

the empty program is only used as a junk element; any other element 
works just as well:

[A] [junk] q zap 
== [[A]] [junk A] zap
== [[A]]

So, in the construction for [q], we might as well leave [k] alone 
and use it as our junk element, rather than zapping it and pushing 
[]. Therefore, we can delete "zap []" from the construction. Compare:

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

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

Now let's look at [k]. The original construction was

[k] == o nip nip
    == o unit k unit k

Notice that "unit unit k k" also works as an implementation of "nip 
nip":

[C] [B] [A] unit unit k k
== [C] [B] [[A]] unit k k
== [C] [B] [[[A]]] k k
== [C] [[A]] k
== [A]

So we have

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

And once again we can delete the unneeded "zap []" (for the same 
reason as with [q]) to get

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

which is the minimal construction.

I've tried searching for minimal constructions of "dip" and "swap" 
but without success; I can say that "dip" has size at least 33 
and "swap" has size at least 35. But I would guess that the minimal 
constructions are much larger than this, so it's probably useless to 
continue searching in a brute-force manner (although technically 
it's not quite brute-force; I did implement a sort of backtracking 
algorithm for flat constructions, which helps speed things up a bit).

I also did some experimenting with different bases. Remarkably, all 
five other bases obtained from {o,k} by changing the order of the 
three quotations in "o" are flat complete. Here are the 
constructions (for the sake of conciseness, I'll just choose one 
representative when there are multiple minimal constructions):

o := [] [k] [q]
[]  == oookkokkk
[q] == ookokokkokkkk 
[k] == ookkokokk
i   == okk
unit== okoookkokkkk
swat== ookokkkokookkokokkk

o := [q] [] [k]
[]  == oookkoookkokkk
[q] == ooookkookkokkk
[k] == ooookkokkookkk
i   == oookkokkk
unit== ookoookkookkkk
swat== ookkoookokookkkk

o := [k] [] [q]
[]  == ooookokookkkkkokk
[q] == ooookokkkkokk
[k] == ooookokookkkkkk 
    == ooookokkokkokkk
i   == oookkokkk
unit== oookokkkk
swat== oookokkokokkkk

o := [q] [k] []
[]  == ooookkookkkokkk
[q] == ok
[k] == ooookkkoookkkkk
i   == oookkkoookkkokkkk
unit== oookkoookokkokkookkkkk
swat== okokkookkookoookkkkkk

o := [k] [q] []
[]  == ooookkkookkokkk
[q] == oookkokk
[k] == ok
i   == oookkkoookkookkkkkk
unit== okooookkkookkkk 
swat== ookkoookkkokk

Also, it turns out that my original base {o,i} isn't as bad as it 
first appeared; here are the minimal constructions over it:

[]  == oooiiioooiiiiii 
[q] == ooioooiioiioiiii
[k] == oooiioiii 
unit== ooiioooiiiii 
swat== oiooiioooiioiioiiii

And the basis {[k] [q] [],i} also turns out to be complete and has 
fairly simple constructions:

o := [k] [q] []
[]  == ooiiioiii
[q] == ooioiiiiiiii 
[k] == ooiiii
unit== oiiooiiioiiioiiii 
swat== oooiioiiioiiooiioiii 

The other four bases obtained from {o, i} by changing the order of 
the quotations in "o" appear to be incomplete, although I'm not 
certain except in the case {[q] [] [k], i}, which is definitely 
incomplete since "oi" is the empty program.

A couple other interesting bases arise from a new combinator, call 
it "h", defined

[B] [A] h == [[A B]] [B]

which forms a complete (non-flat) basis with "k", as evidenced by 
the constructions

i    == [] h k
unit == [] h [] k
swat == h h k
dup  == [] h unit swat i

Then {[] [h] [k], k} and {[] [k] [h], k} are complete flat bases:

o := [] [h] [k]
[]   == ookok
[h]  == ookookkookkk
[k]  == ooookkkokoookkkokkk
i    == oookkkk
unit == oookkkok
swat == ookkookkk

o := [] [k] [h]
[]   == ookkokokkk
[h]  == ookookokkkokookokkkkk 
[k]  == ookkokkokk
i    == okk
unit == okookokkk 
swat == ookookokkkkkookokkkokk 

In the end, from what I can see, none of these alternative bases 
offer significant improvement over your {o,k}, which is one of the 
best in terms of yielding small constructions of the combinators 
we're looking at. It looks like your intuition served you well 
indeed! 

- Brent