# Two combinator linear-complete base!

## Brent L Kerby — 2002-03-30 17:55:48

    Hello!

    Well it turns out there is indeed a two-combinator base with linear

    completeness, namely {cons, dipi} where

    [B] [A] cons == [[B]A]

    [B] [A] dipi == A B

    The name for "dipi" I got simply because it can be constructed as "dip i".

    Manfred mentions this combinator in his "Mathematical Foundations" paper; it

    turns out to be rather significant, I think.

    Anyway, now to demonstrate the completeness, we just have to construct "dip" and

    "i" (since along with "cons" these three are known to give a complete base):

      i == [] dipi

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

    The "i" is rather self-explanatory. And here's how the "dip" works:

       [B] [A] [] cons [[] cons] dipi dipi

    == [B] [[A]] [[] cons] dipi dipi

    == [B] [] cons [A] dipi

    == [[B]] [A] dipi

    == A [B]

    I'm rather happy about this base. What's particularly interesting to note here

    is that, in an applicative system, a two-combinator base with this kind of

    completeness does not exist, to my knowledge (although I can't verify this).

    However, if duplications (but not destructions) are permitted, there is the

    applicative base {I, J} where

    Ia    == a

    Jabcd == ab(adc)

    Now, the remaining question is: does a similar kind of two-combinator base (with

    duplication but not destruction allowed) exist in a concatenative system?

    - Brent

## Louis Madon — 2002-03-31 01:27:37

    Hi Brent,

    I'm afraid you haven't quite achieved a 2-combinator base yet.

    What you have is a three combinator base { cons, dipi, [] }.

    That is you can't ignore [] since it is not derivable (in any way I can

    see) from cons and dipi.

    I might post more thoughts later ...

    [ BTW, there seems to be something up with the date-stamp on your

    postings.  They're all dated 1st March and I have to scroll my inbox a

    long way up to get to them. ]

    Louis.

     On Friday, March 1, 2002, at 12:00 PM, Brent L Kerby wrote:

    > Hello!

    >

    > Well it turns out there is indeed a two-combinator base with linear

    > completeness, namely {cons, dipi} where

    >

    > [B] [A] cons == [[B]A]

    > [B] [A] dipi == A B

    ...

    [Non-text portions of this message have been removed]

## Brent L Kerby — 2002-03-31 02:15:43

    > I'm afraid you haven't quite achieved a 2-combinator base yet.

    > What you have is a three combinator base { cons, dipi, [] }.

    >

    > That is you can't ignore [] since it is not derivable (in any way I can

    > see) from cons and dipi.

     Well, it's true that "[]" is neccessary in order to form all combinators using

    "cons" and "dip". However, I don't see "[]" as a primitive that needs to be in

    the base. The fact that we're using a concatenative system allows us to use

    quotations to aid in constructions; in fact, quotations are a fundamental way of

    buliding expressions up, along with concatenation.

    To me, "[]" really is just a special case of quotation, with an empty body. My

    system (i.e., the joy searcher) treats "[]" the same way as  any other

    quotation; it's just a quotation with a zero length. Thus there is no need to

    include "[]" in the base. This makes sense to me.

    Granted, there is a way you could formally define concatenation and quotation

    that would exclude "[]" from being a valid expression, but to me that would

    seem unnatural. It makes sense to allow "" (i.e.,

    that blank program, the concatenation of zero things) to be a valid program, and

    thus "[]" would then be valid too. Of course, this rejects concatenation as a

    binary construct, treating it a bit differently; but it seems good to me.

     > [ BTW, there seems to be something up with the date-stamp on your

    > postings.  They're all dated 1st March and I have to scroll my inbox a

    > long way up to get to them. ]

     Hmm.. not sure if there's anything I can do about this. My email address only

    works through a web interface.

     > Louis.

     - Brent

## Louis Madon — 2002-03-31 04:26:34

    On Friday, March 1, 2002, at 12:00 PM, Brent L Kerby wrote:

     > > I'm afraid you haven't quite achieved a 2-combinator base yet.

    > > What you have is a three combinator base { cons, dipi, [] }.

    > >

    > > That is you can't ignore [] since it is not derivable (in any way I

    > can

    > > see) from cons and dipi.

    >

    > Well, it's true that "[]" is neccessary in order to form all

    > combinators using

    > "cons" and "dip". However, I don't see "[]" as a primitive that needs

    > to be in

    > the base. The fact that we're using a concatenative system allows us to

    > use

    > quotations to aid in constructions; in fact, quotations are a

    > fundamental way of

    > buliding expressions up, along with concatenation.

     You seem to be confusing the notion of empty quotation with the act of

    pushing one onto the stack.  The latter is a primitive.

    To put it another way, on one hand [] is just a value that can sit on

    the stack (which can be swap'ed, pop'ed etc). But on the other, [] is

    also the name of a program that pushes the empty quotation onto the

    stack.

    More generally, a quotation of any size should be constructable as an

    expression involving only the base combinators.  It certainly wouldn't

    be a Joy-like language without that.

     >

    > To me, "[]" really is just a special case of quotation, with an empty

    > body. My

    > system (i.e., the joy searcher) treats "[]" the same way as  any other

    > quotation; it's just a quotation with a zero length. Thus there is no

    > need to

    > include "[]" in the base. This makes sense to me.

     But how did this zero length quotation come into being? How did it

    appear on the stack? - with only cons and dipi - there is no way to say

    "push the empty quotation here".

     >

    > Granted, there is a way you could formally define concatenation and

    > quotation

    > that would exclude "[]" from being a valid expression, but to me that

    > would

    > seem unnatural.

     Indeed, it would be unnatural, and I'm certainly not suggesting that.

     >  It makes sense to allow "" (i.e.,

    > that blank program, the concatenation of zero things) to be a valid

    > program, and

    > thus "[]" would then be valid too.

     Yes, but this program can't ever be built unless we provide a primitive

    for returning it.

     >  Of course, this rejects concatenation as a

    > binary construct, treating it a bit differently; but it seems good to

    > me.

     Sorry, I didn't follow this ...

    Louis.

    [Non-text portions of this message have been removed]

## John Carter — 2002-04-02 22:26:26

    On Sun, 31 Mar 2002, Louis Madon wrote:

     > That is you can't ignore [] since it is not derivable (in any way I can

    > see) from cons and dipi.

    >

    > I might post more thoughts later ...

     Please do.

    I disturbs my repose that [blah blah blah] is remarkably infixish.

    Homework for today.

    Develop a quotation operator that fits completely neatly in with the

    postfixish concatenative paradigm.

    My gut feel is that quotation is a notational convenience which could be

    (at some cost of inconvenience) be replaced by something more in line with

    the paradigm. (Let's face it, base's aren't about convenience).

    John Carter                             Phone : (64)(3) 358 6639

    Tait Electronics                        Fax   : (64)(3) 359 4632

    PO Box 1645 Christchurch                Email : john.carter@...

    New Zealand

    Zeitgeist shutting down for corrective maintenance, please log off.

## Billy and Melissa — 2002-04-02 22:50:47

    From: "John Carter" <john.carter@...>

     > On Sun, 31 Mar 2002, Louis Madon wrote:

    > > That is you can't ignore [] since it is not derivable (in any way I can

    > > see) from cons and dipi.

    > > I might post more thoughts later ...

    > I disturbs my repose that [blah blah blah] is remarkably infixish.

     Always has for me.  I've never cared for it.

     > Homework for today.

    > Develop a quotation operator that fits completely neatly in with the

    > postfixish concatenative paradigm.

     Quotations are actually literals, like numbers and strings.  In fact, for

    some purposes strings can completely replace quotations.

     > My gut feel is that quotation is a notational convenience which could be

    > (at some cost of inconvenience) be replaced by something more in line with

    > the paradigm. (Let's face it, bases aren't about convenience).

     von Thun has suggested one way -- replacing quotations with quoted forms of

    the primitives.  Thus, in addition to "dipi" and "cons", you'd have "'dipi"

    and "'cons", which place quoted forms of their combinators on the stack.

    Okay, there are four elements in that "base", but it doesn't require

    quotation in the syntax.

     > John Carter                             Phone : (64)(3) 358 6639

     -Billy

## Brent L Kerby — 2002-04-03 01:36:37

    > von Thun has suggested one way -- replacing quotations with quoted forms of

    > the primitives.  Thus, in addition to "dipi" and "cons", you'd have "'dipi"

    > and "'cons", which place quoted forms of their combinators on the stack.

    > Okay, there are four elements in that "base", but it doesn't require

    > quotation in the syntax.

     Yes, this is a fascinating. At first it seems sort of like a hack, but I think

    maybe it has some significance. It be noted here, though, that "'dipi" and

    "'cons" alone cannot quite compensate for removing the quotation operator. At

    least, from these there is no way to construct the empty quotation "[]", so you

    might find it desirable to include "[]" as a primitive, unless you want to

    exclude "[]" from the system (it is sort of ironic here that I'm suggesting "[]"

    as a primitive after rejecting Louis's idea to do so; the difference is that

    here quotation is not a valid operator, and so "[]" is necessary as a primitive,

    whereas before when quotation was an operator, "[]" was unnecessary as a

    primitive because it came with quotation).

    There's a little subtlety going on here also. You might wonder how to could

    construct a compound quotation such as "[dipi cons]" using 'dipi and 'cons. It

    might look like we need to add a "concat" primitive, so that we can build

    quotations up from 'dipi and 'cons. However, in this particular base, "cons" can

    do the job:

      [cons dipi] == 'dipi 'cons 'dipi cons cons

    This construction might be considered a bit questionable, though, since it

    relies on the transparency of quotation (i.e., meaning it is only valid if you

    accept "[[foo] i]" to be the same as [foo], and such things). It works like

    this:

      'dipi 'cons 'dipi cons cons

    == [dipi] [cons] [dipi] cons cons

    == [[dipi] [cons] dipi]

    == [cons dipi]

    Similarly, you might wonder how to construct a compound quotation such as

    "[[dipi]]" from 'dipi and think that a "unit" primitive needs to be added. But

    again, cons can do the job, this time in a way that works even with opaque

    quotation:

      [[dipi]] == 'dipi [] cons

    But it does require the use of "[]" ... Anyway, this shows that {cons, dipi,

    'cons, 'dipi, []} can form all combinators using concatenation alone (i.e.,

    without quotation). Of course, the downside in terms of elegance is that 'cons

    and 'dipi are only pseudo-combinators.

    Hmm ... I wonder if a base exists containing only true combinators (no

    pseudo-combinators allowed) that nevertheless turns out to be complete even

    without quotation. I'm not sure if this is possible;

    I'll have to work on that.

     > -Billy

     - Brent