Re: [stack] Properties of Concatenative langauges and Forth

In Fri, Jan 2, 2009 at 11:50 AM, William Tanksley, Jr
<[email protected]> wrote:
> Christopher Diggins <[email protected]> wrote:
>> In a concatenative language, I believe evaluation order should be
>> unimportant.
>> For example:
>> f g h <=> (f g) h <=> f (g h)
>
> This is the associative property. You need to be careful calling it
> "evaluation order", though; evaluation order matters with respect to
> dataflow

Not necessarily. It depends on what the evaluation mechanism is.
Talking about data-flow in the context of Joy is incorrect. A Joy
program has no data, only functions. You'll see what I mean below.

>  -- you can't fully evaluate an expression whose parameters
> aren't all known at evaluation time.

This is the difference between applicative and concatenative
languages. An applicative language applies a function to a value to
yield values. This continues until no more application is required and
we are left with a final *value*. In a concatenative language (or at
least in Joy and Cat) every program, subprogram, and expression is a
function from stack to stack. Evaluation of a program consists of
composing functions created by the terms to yield a final *function*
on stacks.

In a program "1 2 +", "1" and "2" are not parameters to a function
"+". Manfred calls this out quite clearly in his essays. This is why
he says Joy is not a postfix language. You are not applying the
function "+" to values "1" and "2". To understand why this is, we have
to resort to a formal exploration of the semantics in terms of the
mathematical meanings of a Joy (or Cat) program.

I'll use Cat, because I am afraid of making a mistake with the Joy
syntax. Consider the Cat program "p":

define p { 1 2 + }

In Cat (like Joy) the program "p" is a function on stacks, that is
created by composing the stack functions represented by "1", "2", and
"+". The semantics (the meaning) of a valid program is a function on
stacks. I represent this formally below using the symbol "::==" to
mean "has the meaning of". The left side is a term in Cat, and the
right side is the function on stacks. The notation [R, a, b] -> [R,
a+b] means "the function which maps a stack containing two values on
top and any number of values below, to a new stack containing which is
a copy of the original stack with the top two values replaced with
their sum".

1 ::== [R] -> [R, 1]
2 ::== [R] -> [R, 2]
+ ::== [R, a, b] -> [R, a+b]

We know intuitively that the meaning of "p" is:

p ::== [R] -> [R, 3]

Which is equivalent to the program:

3 ::== [R] -> [R, 3]

Hence we can say that the evaluation of "p" is "3", because it has the
same effect as the program 3. To get the function from a program (in
other words to evaluate a program), we have to compose all of the
functions corresponding to individual terms in the program. Formally:

1 2 + ::== ([R] -> [R, 1]) . ([R] -> [R, 2]) . ([R, a, b] -> [R, a+b])

To evaluate the expression "1 2 +", we compose the functions which
result from performing the composition of the sub-terms. We can do it
right to left:

1 2 + ::== ([R] -> [R, 1]) . (([R] -> [R, 2]) . ([R, a, b] -> [R, a+b]))
1 2 + ::== ([R] -> [R, 1]) . ([R, a] -> [R, a+2])
1 2 + ::== ([R] -> [R, 3])

Or left to right (obviously because composition is applicative):

1 2 + ::== (([R] -> [R, 1]) . (([R] -> [R, 2])) . ([R, a, b] -> [R, a+b])
1 2 + ::== ([R] -> [R, 1, 2]) . ([R, a, b] -> [R, a+b])
1 2 + ::== ([R] -> [R, 3])

So my statement about evaluation order is correct.

The execution model of a Cat program may vary. Formally the stack
function created by composing terms is applied to an input stack to
yield an output stack. A naive implementation may apply terms
sequentially to the input stack. While this is a helpful mental model
for understanding a common implementation technique for executing Cat
or Joy programs, it says nothing useful about the formal semantics.

For those interested in semantics, the following books provide a good
foundation in the study of the semantics of programming languages.

* "Programming Languages Applications and Interpretation" (a,k.a.
PLAI) by Shriram Krishnamurthi ( full text online at
http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/plai-2007-04-26.pdf
)
* "Structure and Interpretation of Programs" (a.k.a. SICP) by Ableman,
Sussman, and Sussman. (full text online at
http://mitpress.mit.edu/sicp/full-text/book/book.html )
* "Types and Programming Languages" (a.k.a. TAPL) by Benjamin Pierce,
unfortunately not free

- Christopher