Greetings, concatenative combinator friends ...
Recently, I made a little program that searches for constructions of
combinators within restricted bases. It is written in C and is not
the most elegant thing, but it has a respectable speed I think
and might have some uses. Anyway, it can be found at:
http://tunes.org/~iepos/joysearch-0.3.tar.gz
On my machine it is currently tackling the "dip" problem mentioned
earlier: is "dip" constructable from {call, drop, dup, swap, cons}?
So far it has found no results, which is no surprise. If it is
constructable, it must take more than 10 words (where quotation counts
as an extra word). Of course, the program can never give a definitive
"no" answer, although a human maybe could by working out a clever
general proof.
However, there are a few interesting constructions it has found,
for instance:
[dup] dip == [] cons cons dup call drop swap call
This shows that even if "dip" can not itself be constructed, an
interesting application of it can ... here is how it works:
[x] [y] [] cons cons dup call drop swap call
[x] [[y]] cons dup call drop swap call (cons)
[[x] [y]] dup call drop swap call (cons)
[[x] [y]] [[x] [y]] call drop swap call (dup)
[[x] [y]] [x] [y] drop swap call (call)
[[x] [y]] [x] swap call (drop)
[x] [[x] [y]] call (swap)
[x] [x] [y] (call)
Sort of weird ...
Anyway, the program is sort of annoying in some ways; for instance,
changing the base requires modifying the source file :-)
(by default, it uses all nine primitive combinators it knows about
as bases). But, in case anyone else wants to use it, here is an example
of how:
joysearch 3 [s]bs[s]b
The first parameter is the number of parameters that the goal combinator
takes, and must be specified. The second parameter is the goal combinator,
written using one letter per combinator; here is the key:
i == call
w == dup
k == pop
s == swap
b == dip
p == sip
u == unit
t == cat
c == cons
For instance, in the example above, "[s]bs[s]b" means
[swap] dip swap [swap] dip
This is a combinator that reverses the order of the top three parameters.
Running the program this way will give:
goal combinator: [2][1][0]
(size 1)
(size 2)
(size 3)
(size 4)
* sucb
(size 5)
* usutb
* s[]ccb
* [s]ccb
* ubucb
* [s]cbs
* s[s]bs
(size 6)
...
The program found the smaller construction of "sucb", or in other words
swap unit cons dip
which works like this:
[x] [y] [z] swap unit cons dip
[x] [z] [y] unit cons dip (swap)
[x] [z] [[y]] cons dip (unit)
[x] [[z] [y]] dip (cons)
[z] [y] [x] (dip)
- "iepos" (Brent Kerby)
[Searching for non-primitive construction of dip]
Interesting technique. I saw this used in three places before:
1. A superoptimizer for code generation. Basically, all short sequences
of machine code (excluding jumps and traps) are generated and tested with a
few sample inputs for which the outputs are known. Those sequences that
pass the initial tests are then tested more thoroughly with boundary cases.
This tends to find the shortest (and often the fastest) machine code
sequences for certain small-scale idioms on arbitrary hardware. For
example, multiplication by a constant in the abscence of a hardware multiply
instruction (consider: x*59 = (x<<6)-(x<<2)-x).
2. A search for chess endgames with a small number of pieces (e.g., at
most how many moves before a knight and bishop can defeat a king?). This
search is usually done backwards from all checkmate positions, until all
allowable starting positions have been encountered.
3. An exhaustive search of minimal solution paths for Rubix cubes.
The third solution used some kind of hashing function on the cube state,
combined with dynamic programming, to exhaustively examine all cube states.
I believe it also used a backwards search, like the chess problem searches.
You may want to "summarize" a program as a canonical sequence of integers
that describes its net effect on the stack. This sequence of integers can
be hashed and stored (along with the first such program encountered that
produced this "summary") in a hash table.
The search algorithm would then be to store the "no-effect" canonical
encoding in the hash table, then loop through (a copy of) the table,
appending each possible symbol to each program encountered, and adding the
resulting entries to the table if an equivalent program has not yet been
encountered (i.e., with fewer tokens). If the last token is a quotation,
you should also try appending a token to that quotation (recursively if
necessary). This will should allow an efficient, complete breadth-first
search by number of tokens.
A further analysis on the subsequences it the hash table will indicate which
operators don't serve to compress code, and which *potential* operators
would assist greatly in compressing code. Of course, actual use of the
language will skew these values (as opposed to considering all possible uses
of the language equally likely).
Just some ideas.
> [technique of finding constructions of combinators by brute force]Thanks... perhaps then there is some way to apply hashing to this
>
> Interesting technique. I saw this used in three places before:
> [... hashing to solve rubix cube]
>
> Just some ideas.
problem also...
- "iepos" (Brent Kerby)
From: wtanksley@...
> From: iepos@... [mailto:iepos@...]Whoops, I think your definition of concat isn't right. Wouldn't "7 [4 +]
>>On my machine it is currently tackling the "dip" problem mentioned
>>earlier: is "dip" constructable from {call, drop, dup, swap, cons}?
>
> Since you're allowing cons you must at least allow the unit list. I assume,
> of course, that you're using 'call' to mean 'i'.
>
> enquote == [] cons;
> concat == [] cons cons;
> dip == enquote concat call.
>
> We're removing the first and second item from the stack, and using them to
> build a program which when executed will execute the second item, then will
> place the first item back on the stack. We then execute the program.
> Example:
>
> 7 [4 +] 3 enquote -> 7 [4 +] [3]
> 7 [4 +] [3] concat -> 7 [4 + 3]
> 7 [4 + 3] call -> 11 3
[3] concat" produce "7 [[4 +][3]]"? If you consider lists to be
suffix-sharing (something that cons doesn't break up), then it's impossible
to go from [4 +] something to [4 + 3]. The suffixes don't work out.
From: iepos@...
>^^^
>> concat == [] cons cons;
>
> This is incorrect, I believe. Say that you have the lists "[1 2]" and
> "[3 4]" on the stack, this will just give you
>
> [1 2] [3 4] [] cons cons
> [1 2] [[3 4]] cons
> [[1 2] [3 4]]
>
> We have not concatenated the two lists, but only wrapped the two lists
> unchanged into a new list. However, by modifying the technique a bit,
> you could construct "concat" correctly as
>
> concat == [[call] dip call] cons cons
>
> With the example above we get
>
> [1 2] [3 4] [[call] dip call] cons cons
> [1 2] [[3 4] [call] dip call] cons (cons)
> [[1 2] [3 4] [call] dip call] (cons)
> [[1 2] call [3 4] call] (dip)I don't think it's acceptable to replace the dip (or the subsequent "call"s)
> [1 2 [3 4] call] (call)
> [1 2 3 4] (call)
within a quotation. Replacement rules may only be applied outside
quotations, otherwise [1 2 +] and [3] might be considered equal lists (which
they most certainly are not).
> > We have not concatenated the two lists, but only wrapped the two listsGood point. In Joy, this rewrite would indeed not always be valid.
> > unchanged into a new list. However, by modifying the technique a bit,
> > you could construct "concat" correctly as
> >
> > concat == [[call] dip call] cons cons
> >
> > With the example above we get
> >
> > [1 2] [3 4] [[call] dip call] cons cons
> > [1 2] [[3 4] [call] dip call] cons (cons)
> > [[1 2] [3 4] [call] dip call] (cons)
> ^^^
> > [[1 2] call [3 4] call] (dip)
> > [1 2 [3 4] call] (call)
> > [1 2 3 4] (call)
>
> I don't think it's acceptable to replace the dip (or the subsequent "call"s)
> within a quotation. Replacement rules may only be applied outside
> quotations, otherwise [1 2 +] and [3] might be considered equal lists (which
> they most certainly are not).
I suppose I'm thinking of a system where quotations did
not serve a dual purpose as lists, where they were only used as
potential programs to be run, and where they could not directly be
introspected.
In such a system, it should be acceptable to make this sort of
replacement. [1 2 +] could be rewritten as [3], also, since both
programs would have the same effect if run.
The disadvantage of doing it this way is that we must have
new primitives for the empty list and a list-concatenater,
since we cannot reuse "[]" and "concat". This is not that
big of a deal, though, I think.
But, in a way, I do sort of like the programs-as-lists metaphor ...
- "iepos" (Brent Kerby)
>joy>2 3 [+] first
> But, in a way, I do sort of like the programs-as-lists metaphor ...
2 3 +
joy>i
5
vs.
joy>2 3 [+] first
5
>
> - "iepos" (Brent Kerby)
>
> ------------------------------------------------------------------------
> Remember four years of good friends, bad clothes, explosive chemistry
> experiments.
> http://click.egroups.com/1/4051/6/_/_/_/960385149/
> ------------------------------------------------------------------------
>
> To unsubscribe from this group, send an email to:
> concatenative-unsubscribe@egroups.com
>
>
>
>