Re: [stack] Properties of Concatenative langauges and Forth

Christopher Diggins <[email protected]> wrote:
> 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're thinking of "values" as a syntactic element: Joy (and
concatenative languages in general) do not have a special syntactic
element for values. A value is nothing more than a function that takes
no input and generates a single, constant output; not worth making a
special syntactic category for.

Data, on the other hand, is what programs consume and produce.

Obviously, you can't evaluate a '+' if you don't know what 2 data
items are on top of the stack. In that sense evaluation order is
important.

>>  -- 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.

I totally agree right up to the last sentence -- building a program
works that way, but evaluating it (i.e. running it) still requires
data. Once you've built it, you can analyze it, refactor it, optimize
it... But you can only evaluate the parts for which you have actual
data.

> In a program "1 2 +", "1" and "2" are not parameters to a function
> "+". Manfred calls this out quite clearly in his essays.

You're right; it took until now to see my mistake. I misspoke of
parameters to a function, when as you explain, functions do not attach
in any way to parameters, or anything else aside from other functions.

I could have more accurately spoken of "data" applied to a "program".
If "data" doesn't work for you, try "unknowns". You can't evaluate a
program until all the unknowns are provided; you can't evaluate a
portion of a program until all of the unknowns it depends upon have
been computed or provided, and often that means you have to evaluate
the leftmost part of a program earlier than the rightmost part. That's
a rule of thumb, not a law; there are transformations that can
rearrange program text; but it's a strong rule of thumb nonetheless.

> 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:

Evaluating a program does not result in "getting the function from"
it. Evaluating a program, given the data you wish to evaluate it at,
produces the program's output for that data (if any, and if the
program halts within your patience).

> 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:

You're actually simplifying "1 2 +" rather than evaluating it -- since
it's a constant, the simplification is the same as the evaluation.

> Or left to right (obviously because composition is applicative):
> So my statement about evaluation order is correct.

It's true that you can simplify in any order; and it's true that this
is one of the big points in favor of concatenative languages. They
beat even referentially transparent applicative languages, since
applicative languages can only simplify a valid parse.

> - Christopher

-Wm