Yep, there is a complete two-combinator Joy base, namely {z, k} where

[D] [C] [B] [A] z == [[D] C] A [D] B
[B] [A] k == A

I don't plan to permanently reserve the name "z" for this combinator, seeing as
it is so weird :-)

Essentially, "z" is a modified "s" combinator, where

[C] [B] [A] s == [[C] B] [C] A

In fact, "s" can be constructed simply as

s == [] z

This was a main point in the design of "z". Because, having "s" and "k" allows
us to construct a huge amount of combinators; in fact it allows us to construct
all applicative combinators. I should define "applicative combinator" formally,
but instead, I'll just say that we can construct, for example, all these fun
combinators, "i", "b", "c", "w":

[A] i == A
[C] [B] [A] b == [[C] B] A
[C] [B] [A] c == [B] [C] A
[B] [A] w == [B] [B] A

These are constructed the classic way from applicative combinatory logic (I
should give more detail on this ...):

i == [][k]s
b == [k][[s]k]s
c == [[k]k][[s][b]b]s
w == [[i]k][s]s

Having "b", "c", "w", and "k" gives us the ability to construct "cons", "swap",
"dup", and "zap":

cons == [] b == [[]k]s
swap == [] c == [k][[[]s]k]s
dup == [] w == [i][]s
zap == [] k

To be on the safe side, I'll verify these by hand for you:

(first, here's cons:)
[B] [A] [[] k] s
== [[B] A] [B] [] k (by s)
== [[B] A] (by k)

(now, swap:)
[B] [A] [k] [[[] s] k] s
== [B] [[A] k] [A] [[] s] k (by s)
== [B] [[A] k] [] s (by k)
== [[B] [A] k] [B] (by s)
== [A] [B]

(now, dup:)

[A] [i] [] s
== [[A] i] [A] (by s)
== [A] [A] (by i)

Obviously, these constructions (particularly, of swap and dup) rely on the
transparency of quotation; but this is quite acceptable, I think.

Anyway, this gives us "i", "cons", "dup", and "zap". All we're lacking for
completeness now is "dip". And this is where the fun comes in! :-)

To get "dip", we have to use "z", because "dip" is not constructible from just
"s" and "k". Fortunately, "z" is specially designed to allow us to get "dip" out
of it.

dip == [] swap [] swap [k] cons z

It works like this:

[B] [A] [] swap [] swap [k] cons z
== [B] [] [A] [] swap [k] cons z (by swap)
== [B] [] [] [A] [k] cons z (by swap)
== [B] [] [] [[A] k] z (by cons)
== [[B]] [A] k [B] (by z)
== A [B] (by k)

Or, I'll give you the brute-searcher's construction of dip in terms of just "z"
and "k" (I was surprised to find that a construction even as simple as this
exists):

dip == [k] [[] [[]]] [] z z z

Here's how it works: ( :-) )

[B] [A] [k] [[] [[]]] [] z z z
== [B] [[A] k] [A] [] [[]] z z (by z)
== [B] [[[A] k] A] [] [[A] k] z (by z)
== [[B] [[A] k] A] [A] k [B] (by z)
== A [B] (by k)

To summarize, here are the constructions "i", "cons", "dip", "dup", and "zap" in
terms of just "z" and "k"

i == [] [k] [] z
cons == [[] k] [] z
dip == [k] [[] [[]]] [] z z z
dup == [[] [k] [] z] [] [] z
zap == [] k

Just for fun, here's "sip", too (as found by the searcher):

sip == [k] [] [[] [[]] z k] z

Here's how it works:

[B] [A] [k] [] [[] [[]] z k] z
== [B] [[A] k] [] [[]] z k [A] (by z)
== [[B] [A] k] [] [B] k [A] (by z)
== [A] [] [B] k [A] (by k)
== [A] B [A] (by k)

Wow, isn't this interesting!

Now, the question is: is there a simpler two-combinator base? (maybe a base in
which the combinators take at most three parameters, or maybe only two).

A word of warning to those who might be trying to use my searcher ... it has a
little bug somewhere that I can't explain. It causes the program to be
unsuccessful in many cases at finding constructions of "cons", or combinators
similar to it, even when a simple construction is right there.

(all these results really do need to go into an article, as Manfred suggested; I
think I'm about ready to start on it, for real, especially now that this
particular question, about the existence of a two-combinator base, is solved)

- Brent

Two-combinator base !

Brent L Kerby — 2002-04-04 21:52:25