# More on Joy completeness

## Brent L Kerby — 2002-03-20 19:58:39

    I just noticed something interesting a minute ago: that {cons, dip} alone

    (almost) gives linear completeness, because of the construction

      i  ==  [[]] dip dip dip

    This construction has a bit of a caveat though, in that the program you are

    executing with "i" must leave at least one item on the stack for it to function

    right. It operates like this

        [a] [[]] dip dip dip

     == [] [a] dip dip

     == a [] dip

     ~= a

    At the end, "[] dip" will have no effect, but it must have a stack item to dip

    under.

    Anyway, this is kind of a mutant construction again, but I was hoping to could

    stimulate some thinking. Here's also something I realized. Take a look at the

    rule for "dip" and "cons":

       [a] [b] dip   ==  b [a]

       [a] [b] cons  ==  [[a] b]

    From this you can see that there is no way to give a real construction of "i"

    from just "dip" and "cons", because "dip" and "cons" always end up leaving you

    with a quotation on the stack, but with "i" you can start out with a single

    quotation (say "[]"), and are able to get rid of a quotation entirely simply by

    running "i".

    Thus "i" is not constructable from "dip" and "cons", because "dip" and "cons"

    cannot wipe out a sole empty quotation "[]", but "i" can.

    We can generalize the principle and say that a base can only be complete if it

    contains at least one combinator which has no quotations on the right side of

    its rewrite rule ("pop", "i", and "k" are examples of this type of combinator).

    This means a complete base has to have at least two combinators, since the base

    must also include a combinator with a "cons"-ing effect (i.e., a combinator

    which produces a double quotation), otherwise there would be no way to build

    quotations up (and construct "cons"). And no single combinator can satsify both

    properties (i.e., containing a double quotation on the right-hand-side and

    containing no quotations on the right-hand-side).

    However, I need to quantify the statement that a one-combinator-base cannot be

    complete. This is true if we are talking about a real combinator, one with a

    real rewrite rule (i.e., given a certain number of stack items, will always

    yield a combination of them, using concatenation and quotation). However, things

    might change if we permit "pseudo-combinators" in the base. By

    pseudo-combinator, I mean something like "dup [dip]", which does not have a true

    rewrite rule, because no matter how many stack items there are, the "[dip]" will

    still have to stay there at the end of the right-hand-side; thus the

    right-hand-side could not be a pure combination of left-hand-side terms.

    I am betting that there is a complete one-pseudo-combinator base. I'm guessing

    this only because such a thing happens in the applicative system: We know that

    {S, K} is complete, but did you know that if you have a U, with

      U ==  PKS  ==  x\ xKS  == C(CIK)S

    that U alone gives you completeness, because

      UUU    ==  UKSU == KKSSU ==  KSU  == S

      US     ==  SKS  == I

      U(SII) ==  SIIKS ==  IK(IK)S == KKS == K

    Thus you can get an S and a K out of this combinator, which gives you

    completeness. But still, U is only a pseudo-combinator, since no matter how many

    parameters we apply, the best rewrite rule we get is

      Uxyz  ==  xSKyz

    Applying more letters after "y" and "z" does nothing to make the impure "S" and

    "K" dissapear.

    - Brent Kerby

## Manfred von Thun — 2002-03-25 07:00:03

    On -1 xxx -1, Brent L Kerby wrote:

    [... lots of good things about combinatory completeness for Joy ]

    > - Brent Kerby

    I think that what you have here is far too important to get buried

    in diverse messages to the concatenative group. The same is true of

    your earlier discussions, mainly with Billy Tanksley. It is also

    true of you discussions, again with Billy, on the TUNES group.

    Could you and/or Billy be persuaded to write up all this in a single

    discussion paper for the files section of the concatenative group?

    I could then plant a link to that in the Joy main page. I know it

    would entail quite a lot of work by you, but it would be worthwhile.

    On the topic of planting links, I am seeking your permission to

    refer to your home page with the exposition of the SK(I) combinatory

    calculus. It cleared up a few things for me.

      - Manfred

## Brent L Kerby — 2002-03-25 09:24:51

    > Could you and/or Billy be persuaded to write up all this in a single

    > discussion paper for the files section of the concatenative group?

     That sounds like a great idea. I think that sometime soon I'd be up to that. If

    Billy wants to write something up too, that'd be great, as two perspectives are

    better than one, and it could be a while until I do it.

    Actually, I've been working on a brute-force Joy searcher, but it's not

    functional yet. I think I'd like to finish it first; with it, we could probably

    quickly answer the question regarding the possible completeness of a

    two-combinator or three-combinator base (at least, if such a base exists, I bet

    we could quickly find it, although if they don't exist, it could take some more

    work to show why).

     > On the topic of planting links, I am seeking your permission to

    > refer to your home page with the exposition of the SK(I) combinatory

    > calculus. It cleared up a few things for me.

     Sure. In fact, I'll refer to it here: http://tunes.org/~iepos/. Just skip past

    the blurb on supposed innate talent and juggling (or don't skip past it, if

    you'd rather not :-)).

    I think over the last while I've started to see that the true relation between

    the applicative combinatory system and the concatenative one is much more

    beautiful and rich than I had previously supposed. While it's true that either

    system can be easily simulated in the other system (in fact, either system may

    be seen as a generalization of the other), this does not mean that the two

    systems are trivial modifications of each other. It seems that the Joy is

    elegantly based on combinators that take just one or two parameters, whereas in

    applicative the basic combinators tend to need three parameters. However, in Joy

    we perhaps seem to need more base combinators to get completeness, whereas in

    applicative we needed only two bases. This seems to be a fundamental difference

    between the two systems.

    - Brent

## Manfred von Thun — 2002-03-28 01:13:59

    On -1 xxx -1, Brent L Kerby wrote:

     > > Could you and/or Billy be persuaded to write up all this in a single

    > > discussion paper for the files section of the concatenative group?

    >

    > That sounds like a great idea. I think that sometime soon I'd be up to that. If

    > Billy wants to write something up too, that'd be great, as two perspectives are

    > better than one, and it could be a while until I do it.

     Please do, please do.

     > Actually, I've been working on a brute-force Joy searcher, but it's not

    > functional yet. I think I'd like to finish it first; with it, we could

    > probably quickly answer the question regarding the possible completeness

    > of a two-combinator or three-combinator base (at least, if such a base

    > exists, I bet we could quickly find it, although if they don't exist, it

    > could take some more work to show why).

     I look forward to seeing that. What language are you using for this

    brute ?

     > > On the topic of planting links, I am seeking your permission to

    > > refer to your home page with the exposition of the SK(I) combinatory

    > > calculus. It cleared up a few things for me.

    >

    > Sure. In fact, I'll refer to it here: http://tunes.org/~iepos/. Just skip past

    > the blurb on supposed innate talent and juggling (or don't skip past it, if

    > you'd rather not :-)).

     Alternatively I could either

       1) make the link http://tunes.org/~iepos/introduction-to-logic/

    or 2) make four separate links to the four combinator papers.

    Do you have any preferences?

    [... more interesting anticipations...]

     > - Brent

     - Manfred

## Brent L Kerby — 2002-03-28 09:57:20

    > > [brute-force combinator-construction searcher]

    >

    > I look forward to seeing that. What language are you using for this

    > brute ?

     C. It's coming along, and really is pretty close to being done. It's really not

    too big ... it's just that parts of it get really confusing and give me a

    headache :-)

     > Alternatively I could either

    >    1) make the link http://tunes.org/~iepos/introduction-to-logic/

    > or 2) make four separate links to the four combinator papers.

    > Do you have any preferences?

     Oh, I'd forgotten how ambitious I was when I started writing these (planning to

    do make it into a whole book, practically) :-)

    It think your #2 idea of putting four separate links may be the best. This would

    keep the readers from being disappointed or confused by all the missing content

    on the main page. But, you're welcome to do it any way you like; I'm not

    planning on moving any of the pages.

    By the way, I was reading back on some of those old posts again, and I noticed

    some cool stuff that I'd totally forgotten about: namely some cool combinator

    series, say "dig", "bury", "peek" (was called "select" before), and "poke", for

    example (using the 3rd one of each of these):

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

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

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

    [e] [d] [c] [b] [a] poke3 ==   [a] [d] [c] [b]

    What gets really interesting is when we try to construct these combinators from

    primitives ... The "dig" and "bury" series can be constructed using just "dip"

    and "swap" (or, alternatively, "dip" and "cons"). The "peek" would naturally

    need a "dup", and "poke" would naturally need a "pop" somewhere. By the way, I

    think we should rename "pop" to be "zap" :-) "zap", more than "pop" or "drop",

    suggests that your data is truely being snuffed out of existence.

    A couple other interesting series include:

    [d] [c] [b] [a] dip3     ==  a [d] [c] [b]  (this is a familiar one)

                [a] rep3     ==  a a a

        [c] [b] [a] reverse3 ==  [a] [b] [c]

    Anyway, I think these series (and maybe some others I haven't thought of) could

    be enlightening to study; perhaps we'd find some handy simple combinators in the

    process. Maybe a discussion of this will be included in that future article.

    And, I wanted to take this chance now to thank Manfred for starting this whole

    wonderful Joy thing. Out of curiousity, could I ask what inspired you, or gave

    you the original idea?

    - Brent

## Joel Kelso — 2002-03-28 10:31:11

    > By the way, I was reading back on some of those old posts again, and I noticed

    > some cool stuff that I'd totally forgotten about: namely some cool combinator

    > series, say "dig", "bury", "peek" (was called "select" before), and "poke", for

    > example (using the 3rd one of each of these):

    >

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

    >     [d] [c] [b] [a] bury3 ==   [a] [d] [c] [b]

    >     [d] [c] [b] [a] peek3 ==   [d] [c] [b] [a] [d]

    > [e] [d] [c] [b] [a] poke3 ==   [a] [d] [c] [b]

     I like the names 'dig' and 'bury' (and 'peek' and 'poke' too).  Not

    having heard of names for these before I was calling them

       digN  == shuN   for "shift up"

       buryN == shdN   for "shift down"

       peekN == cpuN   for "copy up"

       pokeN == cpdN   for "copy down"

    but 'dig' and 'bury' are better; short and very descriptive.

    --

    chiral@...

    I used to live in denial, but that place got _way_ too crowded.

## e1_t — 2002-03-29 04:13:50

    --- In concatenative@y..., Brent L Kerby <bkerby@e...> wrote:

     > By the way, I was reading back on some of those old posts again,

     and I noticed

     > some cool stuff that I'd totally forgotten about: namely some cool

     combinator

     > series, say "dig", "bury", "peek" (was called "select" before),

     and "poke", for

     > example (using the 3rd one of each of these):

    >

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

    >     [d] [c] [b] [a] bury3 ==   [a] [d] [c] [b]

    >     [d] [c] [b] [a] peek3 ==   [d] [c] [b] [a] [d]

    > [e] [d] [c] [b] [a] poke3 ==   [a] [d] [c] [b]

    >

     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.

    And in fact Forth has almost all of those operators and they're

    generally frowned upon by hardcore Forthers as the code that utilizes

    such constructs can usually be rewritten in a simpler way. Such

    constructs also tend to be inefficient (that is especially true for

    non-optimizing Forth compilers and interpreters).

    dig2 = ROT

    dig3 = 3 ROLL

    bury2 = -ROT

    peek3 = 3 PICK

    Ivan

## e1_t — 2002-03-29 04:17:05

    --- In concatenative@y..., "e1_t" <e1_t@y...> wrote:

     >

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

     Correction - bury3 is swap rollupd

    Ivan

## Manfred von Thun — 2002-04-03 04:28:19

    On -1 xxx -1, Brent L Kerby wrote:

     > > Alternatively I could either

    > >    1) make the link http://tunes.org/~iepos/introduction-to-logic/

    > > or 2) make four separate links to the four combinator papers.

    > > Do you have any preferences?

     [...]

     >

    > It think your #2 idea of putting four separate links may be the best.

     OK, I'll do that. Thanks.

     - Manfred