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

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

More on Joy completeness