# EWD 28: Djikstra's sort-of-concatenative language

## kuwabatake — 2007-07-30 23:33:24

    I find Djikstra's writings very interesting, and I stumbled on this:

    http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD28.html

    In the (short) paper, Djikstra describes a stack-based arithmetic

    language. At first, he has two types of ``words'' that can be

    concatenated: number words and operator words. When a number word is

    encountered, the number is pushed onto the stack; when an operator

    word is encountered, the operation is performed on the top of the

    stack and the result pushed. So far, so good; we could think of this

    language in the Joy-like way by reframing all words as functions stack

    -> stack.

    The really interesting part comes in the middle of the paper: Djikstra

    proposes to make operator words behave just like number words, simply

    pushing the operator onto the stack. He then introduces the special

    word `E'(for evaluate) which, if there is an operator on top of the

    stack, makes the operator perform its action. In this language,

    pushing 1 2 + would give the stack

    1 2 +

    but then pushing an E would give the stack

    3

    The result is that operators can sit on the stack just like numbers

    and `literals'. Djikstra goes on to introduce an environment of bound

    variables, but that doesn't interest me as much. To me, the

    introduction of E is a really significant idea. In Joy, popping + out

    of a list with

    [+] first

    is sort of messy; a meaningless token is now floating on the stack,

    needing a new quotation to be part of before it can be used in a

    meaningful way and muddying the expression-oriented way of looking at

    Joy. If Joy's + was instead defined as

    + == '+ i

    where '+ is primitive, then the single symbol '+ could be treated as a

    quotation, executable by combinators. The ambiguous symbol + is now

    just an ordinary definition. A language whose primitives are all like

    this would be somewhat Floy-like, where '+ replaces [+] (sort of...

    the analogy is a little complicated.)

    In short: how about a language in which every word puts itself onto

    the stack, except for the `special' word i, which executes the

    function on top of the stack?

    Whew, long post. Thoughts?

    ~Daniel

## Manfred Von Thun — 2007-08-07 07:28:14

    On 31/7/07 9:33 AM, "kuwabatake" <kuwabatake@...> wrote:

     >

    > I find Djikstra's writings very interesting, and I stumbled on this:

    >

    > http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD28.html

    >

    > In the (short) paper, Djikstra describes a stack-based arithmetic

    > language. [..]

    >

     A fascinating paper indeed. Thank you for sharing it with us. And to think

    that the concatenative world only discovered it now! We should have

    stumbled upon it much earlier.

     >

    > [..]

    > In short: how about a language in which every word puts itself onto

    > the stack, except for the `special' word i, which executes the

    > function on top of the stack?

    >

     I have toyed with this idea several times. We have also discussed it on

    the group  can anybody remember when? But I have never been

    convinced of its utility, except for theoretical purposes. However,

    Stephan Apter has used it in one of his languages, see his previous

    post.

    Only distantly related, the language of foyers that I invented trying

    (but failing) to persuade Billy that flatness is in the eye of the beholder.

    That was about 6 (?) months ago. There I had a stack of queues;

    input (like 2 3 +) from the scanner was appended to the top queue;

    the contents of the top queue could be executed by a final period.

     >

     Thanks for that

      - Manfred

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