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