# 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