# Three combinator base!

## Brent L Kerby — 2002-03-30 04:59:13

    Hello folks! I finally finished the brute-force Joy searcher. After playing with

    it for just a few minutes, I discovered that there is a complete

    three-combinator Joy base, namely {sip, cons, k} where

    [B] [A] sip  == [B] A [B]

    [B] [A] cons == [[B] A]

    [B] [A] k    == A

    It's complete because you can construct

    dup  ==  [] sip

    zap  ==  [] k

    i    ==  [] sip k

    dip  ==  [k] cons sip

    This makes a complete base because {i, cons, dip, dup, zap} is complete. The

    construction of "dip" here, although simple, is quite sneaky and was actually

    found by the searcher. It works like this:

       [B] [A] [k] cons sip

    == [B] [[A] k] sip

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

    == A [B]

    How exciting! :-) It even is quite a pretty base, and provides fairly clean

    constructions of the other simple combinators.

    Of course, the question of a complete 2-combinator base, or even a 2-combinator

    base with linear completeness is unknown, although it probably won't take long

    to figure this out, I'm guessing.

    Anyhow, you all can get the searcher at <http://tunes.org/~iepos/joys.zip>. Join

    the fun! :-) There's a README in there explaining how to use it, but I'll

    duplicate it here for your convenience:

    ------- README -------

    This program uses a brute-force technique to search for constructions of

    concatenative combinators.

    It takes no command-line parameters. The settings are contolled by a file called

    "goal". The first line of this file describes the goal combinator (i.e., the

    combinator that the program will search for). The remaining lines describe

    combinators that the program will use as bases in the construction.

    The first character on each line should be a digit telling how many stack items

    the combinator will use. The next character should be a single letter giving a

    name for the combinator (except for the goal combinator, for which this name is

    omitted). The body of the combinator definition is best described by some

    examples. For "dip" you'd use

      0[1]

    For "cons" you'd use

      [[0]1]

    Basically, "0" refers to the top item on the stack, and higher numbers refer to

    successively deep items. For "zap" (aka "pop" or "drop"), just use a blank body,

    but be sure to let there be a "1" at the beginning of the line.

    Everything that is dumped to the screen is also recorded in the "log" file. So

    check the "log" file if a bunch of results came so fast that they scrolled off

    the screen (of course, the "log" file will be erased when the program is run

    again)

    The spinning baton rotates after every 65536 tests. It is normal for it to vary

    quite a bit in speed (because some tests take longer), but if it stops, that's a

    bad sign.

    There are a few settings that can be changed by editing some "#define"'s at the

    top of the program. See the source file, joys.c, for this.

    --------------

    Have fun!

    - Brent