Re: [stack] SK language
Billy and Melissa — 2002-03-19 02:00:40
From: "John Carter" <
john.carter@...>
> Yet another language to add to the set....
> http://www.cwi.nl/~tromp/cl/cl.html
> ...well not quite, it seems to be prefix'ish.
It's worse than that -- it's applicative, and explicitly designed to be so.
> I suspect he could drop all the ()'s if he did it postfix.
I suspect not; I think we'd still need quotation operators.
This is a very minimal language -- S, K, application, and grouping.
Question: could an equally minimal language be made using composition as the
default operation, instead of application? Would that minimal language be
concatenative?
> John Carter Phone : (64)(3) 358 6639
-Billy
Manfred von Thun — 2002-03-19 05:28:14
On Mon, 18 Mar 2002, Billy and Melissa wrote:
> From: "John Carter" <john.carter@...>
> > Yet another language to add to the set....
> > http://www.cwi.nl/~tromp/cl/cl.html
> > ...well not quite, it seems to be prefix'ish.
>
> It's worse than that -- it's applicative, and explicitly designed to be so.
Yes, it is essentially Schoenfinkel's (1924) Combinatory Calculus,
or lambda calculus minus lambda abstraction (if that isn't a
contradiction). Joy is lambda calculus minus lambda abstraction
minus application plus quotation plus concatenation.
> > I suspect he could drop all the ()'s if he did it postfix.
> I suspect not; I think we'd still need quotation operators.
Yes, the parentheses are essential - an SK program is a binary tree,
with application as the binary "glue". One could very well write
application in the reverse order, but even then it would not be
concatenative because application just isn't associative.
However, even then the parentheses or brackets would not be
Joy-like quotation.
> This is a very minimal language -- S, K, application, and grouping.
> Question: could an equally minimal language be made using composition as the
> default operation, instead of application? Would that minimal language be
> concatenative?
My immediate reaction was: yes, a minimal concatenative language would
be possible, but it would need quotation of some form for combinators.
I am no longer sure that this is the case.
Suppose (as is likely) that we need dip and at least two others,
say foo and bar. Suppose further that foo and bar are sometimes needed in
quotes form, say as [foo bar] to be used by dip. Then we could equally
write [foo] dip [bar] dip, which is equivalent.
Now, in that case we could have as primitives foo' and bar'
so that
foo' dip bar' dip == [foo] dip [bar] dip == [foo bar] dip
Just a thought. If the number of primitives is small, then
the extra primitives due to having primed versions would not
be execessive. (I don't have my Peyton-Jones here, but a similar
device was used by Turner to enable efficient compilation to
SK+++ combinators. Joy's dip combinator is a generalisation.
The Haskell people will know that Turner's device is (or was)
used in Haskell implementations.)
A starting point for a minimal concatenative language might well
be the SK applicative language translated into a subset of Joy.
In the "Rationale for Joy" paper, in the last section or so,
there is something along these lines.It may well be that it can
be compressed further.
> > John Carter Phone : (64)(3) 358 6639
>
> -Billy
- Manfred
Brent L Kerby — 2002-03-19 22:08:46
A long time ago Billy and I discussed this topic bit in the TUNES archives March
2000 (see post Combinatory Completeness in Joy).
The main result is that {dup, pop, cons, dip, i} forms a complete base for Joy.
This base is sort of cool because {cons, dip, i} alone gives you linear
completeness (i.e., completeness provided you don't need duplications or
destructions), and then "dup" and "pop" are added to give you non-linear power.
And as Billy pointed out, the base can be reduced to {dup, pop, cons, dip},
since "i" can be constructed as:
i == dup dip pop
or, without "dup" as
i == [] swap dip pop
or,
i == [[]] dip dip pop
As you can see, there are many joyous ways of constructing "i" from more complex
primitives, even though this ought to be considered a perversion of nature :-)
Alternatively, the base {sip, pop, cons, i} is complete, where
[b] [a] sip == [b] a [b]
It is unknown to me whether there exists a complete base with less than four
combinators. This is an interesting question. You might try experimenting with
these combinators:
[c] [b] [a] s == [[c] b] [c] a
[b] [a] k == a
These are analogues of the S and K in applicative systems. With them alone you
can construct many combinators, such as
i == [] [k] s
pop == [] k
However, "s" and "k" leave only the right-most program unquoted, so there is no
way to construct "dip" with them by themselves ...
A long time ago I used to have a program that would do a brute-force search for
constructions of combinators from a resticted base, which would be helpful here,
except that it was kind of a pain to use; maybe I'll make a new version, because
the question of whether a two-combinator or at least three-combinator base
exists really has me now ... even though {dup, pop, cons, dip, i} is probably
the ultimate base anyway, as far as elegance is concerned. Actually, there are
probably cool bases that use "unit", "swap", and/or "cat" (replacing cons and/or
dip), but in any case, a two-combinator base is probably not going to be very
elegant, if it exists, although I'm still curious to know if it exists!
- Brent
Manfred von Thun — 2002-03-20 05:35:55
On -1 xxx -1, Brent L Kerby wrote:
> A long time ago Billy and I discussed this topic bit in the TUNES archives March
> 2000 (see post Combinatory Completeness in Joy).
I am most impressed - and embarassed because I had not noticed it
before. What you have there makes what I have written on it rather
simplistic. Congratulations.
- Manfred