# Re: More on Joy completeness (tack and take)

## Brent L Kerby — 2002-03-29 10:07:39

    > > [dig, bury, peek, poke]

    >

    > Joy already has some of these operators (well... sort of). dig2 is

    > called rolldown and bury2 is called rollup. dig3 could be implemented

    > as rolldownd swap and bury3 as swap rollup.

    >

    > [...]

    >

    > Ivan

     Good point. And you're also right in pointing out that programs that use deep

    stack manipulation tools like these usually can be written in a simpler way

    (i.e., by cutting back on the total number of stack items, so that these

    heavy-duty tools become unneccessary).

    Nevertheless, I see great value in studying these very interesting series of

    combinators. I've been thinking a bit about "reverse" the last while, and how to

    construct it. The most obvious way to me initially seemed to use this (using the

    4 case as an example):

      reverse4  ==  dig1 dig2 dig3

                ==  [] cons dip [] cons cons dip [] cons cons cons dip

    which works like this:

       [d] [c] [b] [a] dig1 dig2 dig3

    == [d] [c] [a] [b] dig2 dig3

    == [d] [a] [b] [c] dig3

    == [a] [b] [c] [d]

    However, this is kind of a poor construction, since if we express things in

    terms of "cons" and "dip", the size of each "reverse" grows quadratically.

    But, I was playing with my old brute-force searcher (yes, it has pretty

    messed-up functionality, and i cannot modify because I wrote it about 2 years

    ago and it has no comments :-) but it works well for this problem), and I found

    this cool other way of constructing "reverse". But to do so, first it will be

    handy to define a new combinator:

    [b] [a] tack == [b[a]]

    The idea is that "tack" tacks on "a" inside the program "b", leaving "b"

    unchanged except that it will leave a constant "a" on top of the stack. You can

    see "tack" as a kind of an analogue of "cons". Here are three possible ways of

    constructing tack:

    tack == unit cat

         == [[i] dip] cons cons

         == swap [dip] cons cons

    This "tack" is quite a powerful little combinator; with it we could construct

    "dip" and "unit":

    dip  == swap tack i

    unit == [] swap tack

    Anyways, I've run off on a tangent with "tack" (but finding something like

    "tack" was precisely what I hoped would happen in searching for a construction

    of "reverse"). So here's "reverse":

    reverse4 == [] swap tack swap tack swap tack swap tack i

             == unit swap tack swap tack dip

    It works like this:

       [d] [c] [b] [a] [] swap tack swap tack swap tack swap tack i

    == [d] [c] [b] [] [a] tack swap tack swap tack swap tack i

    == [d] [c] [b] [[a]] swap tack swap tack swap tack i

    == [d] [c] [[a]] [b] tack swap tack swap tack i

    == [d] [c] [[a] [b]] swap tack swap tack i

    == [d] [[a] [b]] [c] tack swap tack i

    == [d] [[a] [b] [c]] swap tack i

    == [[a] [b] [c]] [d] tack i

    == [[a] [b] [c] [d]] i

    == [a] [b] [c] [d]

    In retrospect, it would have been more handy to define "swap tack" as the new

    primitive, rather than "tack". Let's then define

    [b] [a] take == [a[b]]

    The idea is that "a" takes in the "b". This is rather nicely constructed:

    take == [dip] cons cons

    This makes "take" look actually more fundamental than "tack" perhaps, even

    though it has a reordering effect, whereas "tack" does not. And of course it

    then admits the nice construction:

    reverse4 == [] take take take take i

             == unit take take dip

    And of course this generalizes:

    reverse5 == unit take take take dip

    reverse6 == unit take take take take dip

    etc.

    Isn't that nifty?

    By the way, {take, cat, i} is a base that gives linear completeness, like {cons,

    dip, i} (currently I know of no base giving linear completeness with less than 3

    combinators). It isn't too hard to show that {take, cat, i} is complete. All we

    have to do is construct "cons" and "dip". "dip" is easy:

    dip == take i

    For "cons", we'll first want to construct "swap":

    swap == [] take take i

    And then:

    cons == swap [] take swap cat

         == [] take take i [] take [] take take i cat

    Isn't that neat? Well, there's probably really a neater construction of "cons"

    from this base ...

    (all this stuff will have to be put into the forthcoming article)

    - Brent

## Nick Forde — 2002-03-29 13:23:32

    Hi Brent,

    Brent L Kerby writes:

     ...

      > Nevertheless, I see great value in studying these very interesting series of

     > combinators. I've been thinking a bit about "reverse" the last while, and how to

     > construct it. The most obvious way to me initially seemed to use this (using the

     > 4 case as an example):

      ...

      > But, I was playing with my old brute-force searcher (yes, it has pretty

     > messed-up functionality, and i cannot modify because I wrote it about 2 years

     > ago and it has no comments :-) but it works well for this problem), and I found

     > this cool other way of constructing "reverse".

      ...

    How does your searcher work? Does it begin by assuming a base of

    {cons, dip, i} and let you extend to include others like "tack"? Do

    you intend to cover this in your article?

    I think it would be interesting to see the results of applying some

    simple linear optimisations by deconstructing and rebuilding

    expressions of Joy atoms using such a base. Where the rebuilding is

    being directed through perhaps random or prioritised alternatives.

    If the selection priority of atoms is specified by execution time this

    would be an easy means of applying some low level performance

    optimisations. Of course, this assumes that there are significant

    performance differences between the various linear combinators in Joy.

    If nothing else this might give some metrics on the relative

    importance/usefulness of particular combinators, beyond what

    programmers find most convenient.

    Nick.

## Brent L Kerby — 2002-03-29 18:22:10

    > How does your searcher work? Does it begin by assuming a base of

    > {cons, dip, i} and let you extend to include others like "tack"?

     My old searcher had 9 built-in possible bases (including "dup", "swap", "cons",

    "dip", "i", ...); it used to be configurable by a small hard-wired change in the

    code which of these were actually treated as bases, but I forget how this is

    done :-)

    Anyway, the searcher proceeds basically by trying each possible expression,

    first of size 1, then size 2, etc., and running each expression with a stack of

    appropriate size and then checking to see if the correct results happen (or if

    an error happens midway, then it just skips along to the next expression to

    try).

    If you'd like, the old searcher is available at

    tunes.org/~iepos/joysearch-0.3.tar.gz ... Anyway, the program takes two

    parameters: the first is the "arity" of the goal combinator you are looking for

    (i.e., how many stack items it requires), and the second is the goal combinator

    itself. The goal combinator, and also the results, are written in this

    one-letter code:

    i == i

    w == dup

    k == zap (pop)

    s == swap

    c == cons

    d == dip

    p == sip

    t == cat

    u == unit

    Joy's "[]"'s for quotation are used exactly the normal way. For example, when I

    was searching for a possible other construction of "swap [swap] dip swap" (this

    is reverse3), I did:

    joysearch 3 s[s]ds

    And you'll get an abundance of results, perhaps so many that you'll want to

    ctrl-brk and read "log" (log is a history of exactly what the program prints to

    the screen).

     > Do you intend to cover this in your article?

    >

    > [other interesting ideas  ...]

    > Nick.

     Well, I'm hoping to eventually finish the new searcher, and then yes, I would

    want to mention it in the article ...

    - Brent

## Brent L Kerby — 2002-03-29 18:27:15

    > How does your searcher work? Does it begin by assuming a base of

    > {cons, dip, i} and let you extend to include others like "tack"?

     My old searcher had 9 built-in possible bases (including "dup", "swap", "cons",

    "dip", "i", ...); it used to be configurable by a small hard-wired change in the

    code which of these were actually treated as bases, but I forget how this is

    done :-)

    Anyway, the searcher proceeds basically by trying each possible expression,

    first of size 1, then size 2, etc., and running each expression with a stack of

    appropriate size and then checking to see if the correct results happen (or if

    an error happens midway, then it just skips along to the next expression to

    try).

    If you'd like, the old searcher is available at

    tunes.org/~iepos/joysearch-0.3.tar.gz ... Anyway, the program takes two

    parameters: the first is the "arity" of the goal combinator you are looking for

    (i.e., how many stack items it requires), and the second is the goal combinator

    itself. The goal combinator, and also the results, are written in this

    one-letter code:

    i == i

    w == dup

    k == zap (pop)

    s == swap

    c == cons

    d == dip

    p == sip

    t == cat

    u == unit

    Joy's "[]"'s for quotation are used exactly the normal way. For example, when I

    was searching for a possible other construction of "swap [swap] dip swap" (this

    is reverse3), I did:

    joysearch 3 s[s]ds

    And you'll get an abundance of results, perhaps so many that you'll want to

    ctrl-brk and read "log" (log is a history of exactly what the program prints to

    the screen).

     > Do you intend to cover this in your article?

    >

    > [other interesting ideas  ...]

    > Nick.

     Well, I'm hoping to eventually finish the new searcher, and then yes, I would

    want to mention it in the article ...

    - Brent