# A One Combinator Basis for Cat!

## Christopher Diggins — 2007-01-09 08:46:46

    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 }

    From this you can build K and S

    def K { [X] [X] X }

    def S { [[X] X] X }

    I figured it with help from http://en.wikipedia.org/wiki/Combinatory_logic

    A flat one-combinator concatenative language would probably require a

    quoting operation like:

    A B q == [[A] B]

    BTW it turns out that Brent Kerby's paper is right on the money

    despite my earlier posts disputing it. I am only now just starting to

    formally understand the difference between application and composition

    and the implications for concatenative languages.

    --

    http://www.cdiggins.com

## William Tanksley, Jr — 2007-01-09 16:21:39

    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