Christopher Diggins <
cdiggins@...> wrote:
> I finally figured out the one combinator basis for Cat
> def aba { [dup] dip swap }
> def fcons { [quote] dip compose }
> def K { [pop] dip eval }
> def S { [aba] dip [[fcons] dip] dip eval }
> def X { [K] swap [S] swap [K] swap eval }
That's the Rosser X combinator. The Fokker X combinator is something like:
def Xf { [nip nip i] [S] rot i }
(I hope I got the Cat right.)
> From this you can build K and S
> def K { [X] [X] X }
> def S { [[X] X] X }
The same functions can be defined using the Fokker X combinator as:
def K { [Xf] Xf }
def S { [[Xf] Xf] Xf }
Fokker's goal was to make the simplest possible construction, and this
"wins" by having a shorter K definition.
The Barker X combinator (as used in the Jot, Iota, and Zot languages)
is simpler by another definition -- it uses a much simpler lambda
definition.
Here's my first attempt to derive a stack definition for the Barker X
combinator:
Xb =
^f.fS(^x^y.x) =
^f.f(S(^x^y.x)) =
\f [[\x\y x] S] f =
[[\x\y x] S] swap i =
[[nip] S] swap i
I'll stop there. It's simpler all right (assuming I've done my
derivation right). I'm not going to check it for now, but Barker says
the definition of K in terms of his X is 4 combinators long, while S
takes 5 of his combinators. This explains why Fokker didn't derive it
-- Fokker was looking for the simplest way to express S and K, while
Barker was looking for the simplest lambda expression, regardless of
how complex S or K turned out to be.
> I figured it with help from http://en.wikipedia.org/wiki/Combinatory_logic
Yes, that helped me immensely. Also useful was Fokker's paper, at
<
http://citeseer.ist.psu.edu/fokker97systematic.html>.
I still have two puzzles.
First, how do I use any of these Xes to create a flat language
according to the style of Okasaki:
http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp03
As a side issue to that question, I'd of course want to implement that
language using bitstrings (or even long integers). I think I can solve
this puzzle.
And second, how do I express any of these Xes as a
non-"pseudo-combinator" (to use Kerby's term for a combinator that has
some other explicit combinators stuck inside it)? Kerby seems to
believe that all real combinators can be expressed purely as a
rearrangement of inputs. I don't think I can solve this puzzle; it's
what's stopped me from writing up the work I've done so far.
> A flat one-combinator concatenative language would probably require a
> quoting operation like:
Of course, there can't formally be a flat one-combinator language;
you'd need two combinators, one based on X and the other one based on
the quoting operation (Okasaki proved this). But two combinators is
just what I want; it allows me to interpret bitstrings as programs.
This is exactly what one would want for a genetic program, by the way
-- a flat bitstring, so that programs can be cut, mutated, and
recombined at any point without concern for syntax.
-Billy