# joy combinator construction finder

## iepos@tunes.org — 2000-06-04 00:38:30

    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)

## Mark van Gulik — 2000-06-04 19:03:10

    [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.

## iepos@tunes.org — 2000-06-04 20:28:11

    > [technique of finding constructions of combinators by brute force]

    >

    > Interesting technique.  I saw this used in three places before:

    >  [... hashing to solve rubix cube]

    >

    > Just some ideas.

     Thanks... perhaps then there is some way to apply hashing to this

    problem also...

    - "iepos" (Brent Kerby)

## Mark van Gulik — 2000-06-07 03:09:18

    From: wtanksley@...

     > From: iepos@... [mailto:iepos@...]

    >>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

     Whoops, I think your definition of concat isn't right.  Wouldn't "7 [4 +]

    [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.

## Mark van Gulik — 2000-06-07 05:08:07

    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)

    >   [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).

## iepos@tunes.org — 2000-06-07 13:39:07

    > > 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)

    > >   [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).

     Good point. In Joy, this rewrite would indeed not always be valid.

    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)

## stevan apter — 2000-06-07 13:58:15

    >

    > But, in a way, I do sort of like the programs-as-lists metaphor ...

         joy>2 3 [+] first

        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

    >

    >

    >

    >