Re: [stack] What does "concatenative" actually mean?

spir wrote:
> This leads me to wonder whether concatenation is related to
> referential transparency. Let us imagine a program which parse tree
> looks like this:
> I have the impression that the language is concatenative iff we can
> safely translate A & B to:

(Examples snipped.)

> Id est replace words with their definitions.

"A language is concatenative iff one can replace words with their
definitions." I think that's at least CLOSE. You might also have to be
able to replace a definition with the word as well -- it has to run both
ways. You also have to be "persnickety" that you're not allowed to
rename anything during the replacement (i.e. you're not allowed to do
beta reduction or alpha conversion).

Of course, this is not a complete way to evaluate a language; it doesn't
allow for recursion.

> This means that a word's definition only relies on the definitions on
> the words it references. So what makes most languages "unsafe" in this
> aspect? What kind of element in a definition breaks the scheme? My
> hypethesis is: definitions may use outer things like environment,
> state, variables... In the tree above, this translates to the fact
> that several occurrences of, say, z1 do not perform exactly the same
> action. For instance, it may not push the same value a stack: then, if
> z2 uses this value, it will not have the same result.

Not really. The problem with most languages is that the functions are
defined using local variables, so when you attempt to replace their name
with their definition, you have to FIRST change the definition by
replacing all the instances of each local variable with the value of the
actual parameter.

The fact that some things have state is a problem for lambda expansion,
but it's not even a question when you don't attempt to replace formal
parameters with actual parameters.

> What lets me uneasy with this point of view is that "concatenative" is
> not supposed to be a synonym of "purely functional". Or what? Are
> purely functional languages necessarily, logically, concatenative? But
> maybe there are other ways to achieve this property, meaning that
> concatenative is a superset of functional?

Nope, they're completely different properties.

A concatenative language is completely associative: you can group words
within it anyhow you'd like, and maintain the same semantics. A pure
functional language is referentially transparent: if two complete
expressions have the same semantics, they can be interchanged without
changing the program semantics. The functional language, however,
requires "complete expressions"; the concatenative language doesn't.

> Or am I totally wrong?
> Anyway, forth is not qualified as functional. Also, stack based
> languages can well use data external to a word definition (outside the
> stack). Are they then still concatenative?

Yes. But they're not functional languages -- just concatenative.

> -2- the self expression hypothesis ================
> Another unusual feature of Forth is its ability to compile itself.
> This is related I guess to the property that new words are equally
> treated as builtin words. Io has a similar feature and, as I
> understand it, a consequence is that it has no keyword in the usual
> sense of the term.
> To allow such a property, these languages' grammars map directly to a
> parse tree (like Lisp, too) without any structural transformation.

Io and Forth work for entirely different reasons. For Io, it has a
textual grammar that's a simple tree, and every message has full access
to the data-structure representation of that tree.

For Forth, the grammar is a flat list (not a tree), and because the
source code is already a flat list, giving functions access to their own
source is sufficient to allow them full access to the data-structure.

Most concatenative languages don't allow that, and even in Forth it's
discouraged. I don't have a good theory to account for what happens when
you let a word freely read and/or modify the source in which it appears;
you can do fun things, but you also lose all guarantees of concatenative
behavior. It makes more sense to me for a language to provide at most a
formal macro facility, so that source rewriting will follow clear rules
and be clearly delimited.

> Still, there must some primitives here or there, "under the hood",
> else such a language would really be a pure form and a program would
> execute without *doing* anything ;-) These primitives are not
> expressed in the language itself. There are operational primitives
> (such as IO), but also some minimal "meta-linguistic" ones such as in
> Forth:

Correct; a language consists of both syntax and semantics. The syntax of
a concatenative language consists only of a flat list; the semantics
says that the members of that list may be selected from a set of
functions called "basis functions".

Forth -- and any practical language -- has a huge set of basis
functions, and allows you to define your own functions that are used
just like basis functions.

See Kerby's paper for more mathematical detail.
http://tunes.org/~iepos/joy.html

IF YOU DARE. :)

> * A number token means "push this number (value) on the stack"
> * ':...;' means "parse and store this definition"
> * A word token means "recall this word's definiton"
> [Expressed with my own words that may not be accurate.]

Right -- Forth has an additional syntax (not purely concatenative) to
allow you to do real work. :-)

> Now, my question is: is there any relation between such self-defining
> properties and the notion of "concatenativity"?

Yes. Concatenative languages have fully listlike grammar, so every
element of a program can be defined in terms of what it should be
replaced with; in a language with more complex syntax some elements have
to serve syntactic function (the parens in Lisp and Io, the spaces in
Io).

> -3- human expressiveness ======================
> I wonder about the practical usefulness of the concatenative
> propertie(s). The ability of building a program by pure composition is
> great. But it seems to lead to great modelizing restrictions, too. I
> will illustrate my question with a simple example.
> Lets take the "mystery number" game. [Guess a number between eg 1 &
> 100. The "game master" answers "more" or "less" until found.] As I see
> it:
> * There are 2 actors.
> * They communicate: the player "guesses", the master "answers".
> * The master holds a "secret" data item; the player has current
> "lower" and "upper" bounds. 
> This example really well maps to OO semantics, sure, I didn't choose
> it randomly;-) But I really think, too, that it illustrates a kind of
> natural way to express most of non-scientific models. (I.e. models
> that are rather a system than a "problem" mapping to a (possibly
> tree-like) process.)

There's no reason NOT to use OO modeling in a concatenative language.
The only language type that's incompatible with that is immutable
functional languages.

> How would a model of this game expressed in a concatenative language
> look like? (I really ask: if ever some of you want to answer with
> source code...)

If we're restricted to the same model, it'd look the same way. If we can
choose a different model, it'd look different.

> I guess that in a functional language it would lead to conceptual
> distortion. Slight, manageable distortion, because the game is so
> simple. What I mean is that such langugages are often unable to allow
> a direct mapping from a model to source code expression. In other
> words: for me, a program should look like (be analog to) what it
> pretends to express.

That's only true if the model is OO. Not all models are OO. Don't forget
that OO modeling is also incompatible with relational modeling!

> This statement may only reflect a personal bias. Prototype based
> languges are, imo, the best metaphor / paradigm as of know, to allow
> direct, "natural", expression (In the OO world, most class-based
> languages yield on the contrary incredible and highly abstract
> complication -- and extreme dependencies!).

I know -- I really like Io for that.

> Is there a way to accord concatenation and basic OO? Or are these
> approaches -- as I suspect -- definitely incompatible?

Absolutely not incompatible. Factor has a complete OO system; it even
used to be based on prototypes (that was changed because the Factor
maintainers understood class based systems better and didn't want to
maintain a system they didn't understand; in particular they had buggy
delegation). It still has its prototype object system in a side library
(no longer in the core); perhaps a person knowledgeable in delegation
could fix it.

At any rate, there's no reason whatsoever for concatenative languages to
have any problem with object oriented modeling and/or programming.

> Denis

-Wm