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