# Re: [stack] joy combinator construction finder

## stevan apter — 2000-06-04 02:50:32

    ----- Original Message -----

    From: <iepos@...>

    To: <concatenative@egroups.com>

    Sent: Saturday, June 03, 2000 8:38 PM

    Subject: [stack] joy combinator construction finder

    >

    > However, there are a few interesting constructions it has found,

    > for instance:

    >

    >   [dup] dip   ==   [] cons cons dup call drop swap call

    this was driving me nuts until i figured out that your 'drop' is

    my 'pop'!

    i'll bet your c function is faster than my brute force k routine,

    but it's nice to know we get the same answers - ;-)

    \l joy

    Find:{[g;s;b]

     s:I s

     t:s E/I g

     n:#b:I b

     i:1

     while[1

      j:0

      do[_ n^i

       c:b(i#n)_vs j

       if[t~*|.[E/;(s;c);:];:`0:O@|c]

       j+:1]

      \i+:1]

    }

        Find["[dup]dip";"[1][2]";"[] cons dup i pop swap"]

    2

    3

    4

    5

    6

    7

    8

    [] cons cons cons i pop swap i

    --

    best

    sa

## iepos@tunes.org — 2000-06-04 04:35:43

    > > However, there are a few interesting constructions it has found,

    > > for instance:

    > >

    > >   [dup] dip   ==   [] cons cons dup call drop swap call

    >

    > this was driving me nuts until i figured out that your 'drop' is

    > my 'pop'!

     whoops. sorry :-)

     > i'll bet your c function is faster than my brute force k routine,

     maybe... it took my 133Mhz pentium 20 seconds. the k one could not have

    taken more than a couple hours, judging by how quickly you responded.

    the k one certainly appears way more compact.

    one trick used that significantly speeds things up is that the

    program never explores expressions with redexes in them; that is,

    you will never get a result involving something like "[foo] drop"

    or "[foo] call" or "[foo] dup" (where enough parameters are statically

    known that an reduction could occur), although admittedly you could get

    something involving "dup drop" or "[] dip".

     > but it's nice to know we get the same answers - ;-)

    >

    > [k code which i do not understand :-)]

    >

    >     Find["[dup]dip";"[1][2]";"[] cons dup i pop swap"]

     out of curiousity, is that list on the right the list of bases?

    why does "[]" need to be explicitly provided? does not the

    finder automatically use all kinds of quotations. if not, it seems

    like that would be a hole, as it then could not find constructions like

       [swap] dip swap [swap] dip  ==  swap [swap] dip swap

    because these contain non-empty quotations...

    but, speaking of holes, I discovered that my program has quite a

    large one: generally, it will fail to find results if the goal

    combinator has a cons'ing effect (like "cons" and "concat"). oops.

    but it is quite a deep flaw and am a bit confused and not sure

    what a good way is to fix it.

    but the whole thing needs a redesign anyway. currently, it operates

    by testing a possibility, and then incrementing it, and then testing

    and then incrementing, and so forth. it would be way faster (i think)

    if with each test, only the last word or so in the program usually

    changed (instead of the first word or so, as it currently is),

    and if the system did not do the whole test all over, but remembered

    shared results from the program so far...

    I'm guessing that a big speed increase could be gained that way.

    Although I'm not really sure what use any of this is ... :-)

    It could perhaps be of use when trying to make an optimizer that

    eliminates redundant stack-juggling, I suppose.

     > best

    >

    > sa

     - "iepos" (Brent Kerby)

## stevan apter — 2000-06-04 05:21:52

    ----- Original Message -----

    From: <iepos@...>

    To: <concatenative@egroups.com>

    Sent: Sunday, June 04, 2000 12:35 AM

    Subject: Re: [stack] joy combinator construction finder

    >

    > > i'll bet your c function is faster than my brute force k routine,

    >

    > maybe... it took my 133Mhz pentium 20 seconds. the k one could not have

    > taken more than a couple hours, judging by how quickly you responded.

    > the k one certainly appears way more compact.

    my 450 mhz machine took 39 seconds to test 392476 expressions -

    how odd.

    >

    > one trick used that significantly speeds things up is that the

    > program never explores expressions with redexes in them; that is,

    > you will never get a result involving something like "[foo] drop"

    > or "[foo] call" or "[foo] dup" (where enough parameters are statically

    > known that an reduction could occur), although admittedly you could get

    > something involving "dup drop" or "[] dip".

    do you have any feel for how this strategy cuts down the

    search space?  is it worth it?

    >

    > > but it's nice to know we get the same answers - ;-)

    > >

    > > [k code which i do not understand :-)]

    > >

    > >     Find["[dup]dip";"[1][2]";"[] cons dup i pop swap"]

    >

    > out of curiousity, is that list on the right the list of bases?

    > why does "[]" need to be explicitly provided? does not the

    > finder automatically use all kinds of quotations. if not, it seems

    > like that would be a hole, as it then could not find constructions like

    >

    >    [swap] dip swap [swap] dip  ==  swap [swap] dip swap

    >

    > because these contain non-empty quotations...

    oh yes, this is a big hole.  it should consider all possible

    constructions from the base.

    >

    > but, speaking of holes, I discovered that my program has quite a

    > large one: generally, it will fail to find results if the goal

    > combinator has a cons'ing effect (like "cons" and "concat"). oops.

    > but it is quite a deep flaw and am a bit confused and not sure

    > what a good way is to fix it.

    >

    > but the whole thing needs a redesign anyway. currently, it operates

    > by testing a possibility, and then incrementing it, and then testing

    > and then incrementing, and so forth. it would be way faster (i think)

    > if with each test, only the last word or so in the program usually

    > changed (instead of the first word or so, as it currently is),

    > and if the system did not do the whole test all over, but remembered

    > shared results from the program so far...

    >

    > I'm guessing that a big speed increase could be gained that way.

    > Although I'm not really sure what use any of this is ... :-)

    > It could perhaps be of use when trying to make an optimizer that

    > eliminates redundant stack-juggling, I suppose.

    there must be a theory lurking in all of this.  i wonder what

    it is?

    >

    > > best

    > >

    > > sa

    >

    > - "iepos" (Brent Kerby)

    >

    > ------------------------------------------------------------------------

    > Porsche Boxter. You and a friend. Nine dream days from

    > Napa Valley to Beverly Hills. Provided by CarsDirect.com.

    > Click to enter.

    > http://click.egroups.com/1/4882/6/_/_/_/960093345/

    > ------------------------------------------------------------------------

    >

    > To unsubscribe from this group, send an email to:

    > concatenative-unsubscribe@egroups.com

    >

    >

    >

    >

## iepos@tunes.org — 2000-06-04 18:44:23

    > > one trick used that significantly speeds things up is that the

    > > program never explores expressions with redexes in them; that is,

    > > you will never get a result involving something like "[foo] drop"

    > > or "[foo] call" or "[foo] dup" (where enough parameters are statically

    > > known that an reduction could occur), although admittedly you could get

    > > something involving "dup drop" or "[] dip".

    >

    > do you have any feel for how this strategy cuts down the

    > search space?  is it worth it?

     a very natural question to ask. Actually, before now I had never tried

    not using the trick. Now, here's what I get without the trick,

    when we have 5 bases:

      (size 1, total checked 0)

      (size 2, total checked 6)

      (size 3, total checked 48)

      (size 4, total checked 378)

      (size 5, total checked 3192)

      (size 6, total checked 28614)

      (size 7, total checked 268056)

      (size 8, total checked 2594490)

        * []ccwiksi

      (size 9, total checked 25745520)

      ...

    The number of expressions to search increases exponentially with size,

    as we'd expect, at about a factor of 10. Now, here's what we get with

    the trick:

      (size 1, total checked 0)

      (size 2, total checked 6)

      (size 3, total checked 45)

      (size 4, total checked 316)

      (size 5, total checked 2303)

      (size 6, total checked 17493)

      (size 7, total checked 137404)

      (size 8, total checked 1107784)

        * []ccwiksi

      (size 9, total checked 9115213)

    A significant improvement, although actually not as much as I would have

    expected. We are still exponential, but now at about a factor of 8.

    The five bases used here were {i, dup, drop, swap, cons}; the important

    thing is that 3 of the five are unary. The trick applies better the

    more combinators are unary, since then it will never at all attempt to use

    a quotation before a combinator (whereas with binary combinators,

    one quotation before is okay, although two is not). For instance,

    if we lie to the program and tell it that all five combinators are

    unary, then we get:

      (size 1, total checked 0)

      (size 2, total checked 6)

      (size 3, total checked 43)

      (size 4, total checked 278)

      (size 5, total checked 1817)

      (size 6, total checked 12209)

      (size 7, total checked 84476)

      (size 8, total checked 600950)

      (size 9, total checked 4384065)

      ...

    A further improvement, except when you consider that it missed the

    solution (because a quotation was needed before "cons") :-)

    Anyway, I would definitely say that the trick is worth it. The

    time it takes to do the check seems insignificant compared

    to all the time wasted doing other things (i haven't done a exact time

    check though; maybe I should, but I think really i'm just going

    to start over and make a new version; so many cycles are thrown

    away by using a basically bad algorithm that there is no point

    trying to fine-tune it in this way, I think).

     > there must be a theory lurking in all of this.  i wonder what it is?

     The theory of Joy combinators is similar to the theory of

    Combinatory Logic, pioneered in the 1930s by Haskell Curry and others.

    The combinators studied then were a bit different in that they were

    considered as functions that can be applied to each other using a

    function-application construct, whereas in Joy we concatenate

    combinators together and have quotations.

    The combinators W, K, and C, however, are strikingly similar to the

    "dup", "pop", and "swap" of Joy, respectively. For more information

    on combinatory logic, I might recommend Curry's book, "Combinatory Logic",

    and maybe Raymond Smullyan's "To Mock a Mockingbird". You might also find

    useful some old pages that I've written, available online at:

      http://tunes.org/~iepos

    Also, you might find interesting a long discussion between Billy and I

    on the TUNES list beginning January this year, under the subject

    "Joy, Lambdas, Combinators, Procedures":

      http://lists.tunes.org/list/tunes/0001/

    In this, I was mainly advocating making a new, pure applicative system

    based on combinators instead of named variables, while Billy was

    emphasizing how much better the concatenative approach is.

    Now I think I'm mostly won over to the Joy way of doing things,

    because it is closer to the way things work on real machines.

    However, the applicative approach is still quite curious; for one thing,

    with applicative combinators one can get a complete base with just

    two combinators (the so-called "S" and "K", with "I" usually added also,

    although not strictly necessary). With Joy, the smallest complete base I

    know of involves four combinators: "sip", "drop", "i", and "cons".

    Since "sip" is not standard Joy, I suppose I should define it to avoid

    being misunderstood again ... :

      [x] [f] sip  ==  [x] f [x]

    It is similar to "dip" in that it saves a parameter, runs a program,

    and restores the saved thing, except that "sip" also leaves a copy

    of the parameter for the program.

    - "iepos" (Brent Kerby)

## wtanksley@bigfoot.com — 2000-06-05 17:14:26

    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

     >- "iepos" (Brent Kerby)

     -Billy

## wtanksley@bigfoot.com — 2000-06-05 17:17:41

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

     >> this was driving me nuts until i figured out that your 'drop' is

    >> my 'pop'!

    >whoops. sorry :-)

     I always use 'drop' for that myself -- to me, 'pop' implies not discarding,

    but rather storing somewhere else (it's a word in common use in Forth).  In

    fact,

     pop == dup first

    As far as I'm concerned.

     >- "iepos" (Brent Kerby)

     -Billy

## iepos@tunes.org — 2000-06-05 19:51:32

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

     Yes, all kinds of quotations are allowed, with the unit list as

    a special case. For instance, expressions like

      [dup call] cons

    would be considered permissible to use in the construction.

     > I assume, of course, that you're using 'call' to mean 'i'.

     Right.

     > enquote == [] cons;

     Yes. This is the combinator I've called "unit". It takes an item off

    the stack and yields a quoted program that would push that item when run.

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

     > 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

     Yes, this is right ... except that the "dip" thus constructed takes the

    item to save first (i.e., it expects it as the top item on the stack),

    and then the program to run, which is backwards from Joy's standard

    "dip", which takes the program first. Just prepending a "swap" to the

    construction could fix this, of course.

     > >- "iepos" (Brent Kerby)

    >

    > -Billy

     - "iepos" (Brent Kerby)

## wtanksley@bigfoot.com — 2000-06-05 21:50:44

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

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

     Obviously, this isn't sufficient -- we can't define dip in terms of itself.

    In general, a true concat is inappropriate, since it implies a list

    unwrapping which cannot dequote.  Joy is deficient in this respect, IMO; it

    fails to correctly define the operation which 'first' actually performs on a

    quotation.

    Of course, I can make this work in spite of its illegality; I can't test it,

    since I don't have a joy-capable platform, but try this:

     sneakytrick == [call] first;

     concat == sneakytrick swap cons cons;

     dip == swap unit concat call.

    My first solution can also be modified to work in a more legitimate way:

     uncons == dup rest swap first;

     join == [] cons cons;

     dip == swap join uncons call first.

    However, both of these explicitly require at least 'first'; in other words,

    they have to be able to disassemble the lists they're allowed to create.  In

    a combinator spanning set one would probably want to include 'uncons' rather

    than 'first' and 'rest'.  By the way, you'll also want to remove 'swap' from

    your so-called basis set; swap == [] cons cons call.

    I believe that these will make the system complete by your terms.  This is

    an interesting kind of completeness, since it applies to runtime programs as

    well as compile-time ones; you can pass quotations (such as ones generated

    using loops) to functions using these, and they'll operate correctly on

    them.  The applicative completeness using only I and K can't handle runtime

    actions, probably because one of the crucial components is the applicative

    parser.

     >- "iepos" (Brent Kerby)

     -Billy