> Now wouldn't it be nice to have a brute force search for the most powerful
> base.
>
> John Carter
Yes ... I was thinking about your idea here, and I think it is quite
interesting.
With a bit of programming work, I bet you could actually formalize the idea
of the "power" of a base, in a Joy combinator context, in such a way that
the power of particular bases could even be (approximately) computed by some
brute force.
To me, the most simple way that comes to mind to test the power of a base is
this: given a base, construct every possible combinator up to a certain
size, using the smallest possible construction, and then find the average
length of the constructions (the length of a construction should take into
account that in a larger base each term will take slightly more bits to
represent). This average would tell how powerful the base was, a smaller
number indicating a more powerful base.
This approach could be modified by just doing a random sampling of
combinators to construct (rather than trying every single one), which could
allow the computation to finish much quicker, and thus allow you to go up to
a higher size of combinators to check.
The automation could be carried one step further, and you could have the
program automatically move on from base to base, checking every possible
base, in search of the best one; however, I'm guessing the computations here
are going to be expensive enough that it would only be wise to check bases
which seem like reasonable candidates to be powerful (if this automation was
used, I think it would be a practical neccessity to include some preliminary
tests to weed out worthless bases before wasting long times doing the
in-depth check; perhaps a preliminary test could be the same as the
full-fledged check, though, except up to a much smaller size of combinator)
One subtle question to ask in considering how to carry on this search is
this: how exactly are the goal combinators to be expressed? Put another way,
what exactly is meant by "construct every possible combinator up to a
certain _size_"? How do we rate the size of a combinator except by reference
to some base?
To answer that question ... at first, I was thinking that in the search, the
goal combinators would be expressed in lambda form. However, it would also
be possible to represent the goal combinators in terms of some other base
(for example, {i, cons, dip, dup, zap}), and that would give the resulting
"power" a bit of a different meaning, since it would be relative to the base
that the goal combinators were expressed in.
But, anyway, assuming the search uses the lambda approach, the first few
goal combinators that we'd be trying to construct would look something like
this (the number one the left, before each colon, represents the arity of a
given goal combinator; i.e., how many parameters it takes ... the numbers on
the right symbolize the results that will happen, "0" symbolizing an
execution (i.e., unquoting) of the first parameter, "1" symbolizing an
execution of the second parameter, etc.):
(size 1:)
1: (search for the program that takes 1 parameter and leaves nothing;
i.e., "zap")
(size 2:)
1: 0 (search for a program that takes 1 parameter and executes it; i.e.,
"i")
2: (search for a program that takes 2 parameters and leaves nothing)
(size 3:)
1: 00 (search for a program that takes 1 parameter and executes it twice,
i.e., "rep2")
1: [0] (search for a program that does nothing, except check for one item;
i.e., "[] dip")
2: 0 (search for "k")
2: 1 (search for "swap k", aka "zap i")
3: (drop three parameters)
(size 4:)
1: 000 ("rep3")
1: 0[0]
1: [0]0
1: [00]
2: 00
2: 01
2: 10
(...)
There is some flexibility as to how exactly this is defined. For example, a
quotation could reasonably be defined to be of either size 1 or size 2 (2
because it may implemented as a start "[" and terminator "]", or 1 because
it may be implemented with just a single-byte prefix telling the length).
Also, above I did not include combinators containing "[]"'s in them, even
though they could be considered true combinators (after some thought about
what Louis has said, I think I realize there is some significance to a
formalism excluding empty quotations, also).
Anyway, if someone feels up to programming something like this, that'd be
really cool (maybe in a while I'd be up to it, but not right now anyway, at
least until after I've written that article Manfred suggested). I might give
just one hint, from the experience of writing two brute-force Joy searchers
that really stink, efficiency-wise: in your brute-force search of the
construction, incrementally try your construction, starting from the
beginning, and adding one term at a time, and backtracking when either an
error occurs or when the maximum size is reached. In this way, huge masses
of search space are cut out, by backtracking on errors (by error, I'm
talking about the basic "empty stack error", but also about cases where
executions of the candidate program do not match up with the goal; e.g., if
your goal is "0[2][1]" (dip2), and your candidate program begins by
executing parameter "1" or "2", then you know it is safe to backtrack,
because nothing that happens after an execution of "1" or "2" can ever make
the combinator match the goal). I did not use that incremental approach, by
the way, which is why my searchers are so slow.
An extension to that approach, which would also help a ton, is to postpone
filling in quotations until after their context is clear. In other words,
actually have the body of quotations stored at the end of the expression.
The reason for this is that, when you're about to push a quotation, any
quotation seems valid, and so there's a huge search space; but, if you wait
until later when the quotation is executed, you'll be able to cut back
big-time on the search space using the backtracking technique.
Well, this sounds fun ... any takers?
- Brent