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]