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

On Mar 2, 2009, at 3:19 PM, spir wrote:

> I intuitively understand "concatenative" as meaning "constructive"  
> in the sense of "brick programming". This is what I have always  
> looked for, probably. Still, I do not really get why some languages  
> may be so qualified; why most languages do not have this property.

The Wikipedia article was completely changed a few days ago and now  
gives a (mostly) good definition of what qualifies; I'd start there:
http://en.wikipedia.org/wiki/Concatenative_programming_language

> In stack based langugages,
> :W 1
> actually means "push 1 (whatever it actually is) on top of the stack".
> In a "real" OO language (based on messaged passing, such as usually  
> done in prototypes languages like Io), a reference to a data slot  
> actually calls a data accessor.
> Is this analog to "pushing on the stack" ?

I'm not sure what you mean exactly, but I think the answer is probably  
no. I don't think trying to understand concatenative languages in  
terms of message passing is likely to yield good results. The problem  
is that, unlike in Io, you don't really have a way of denoting the  
receiver of a given message. Especially in the higher order languages  
like Joy that have operations like 'dip', 'bi', etc, it's not clear  
how a message passing semantics would work. (That's not to say you  
couldn't make it work of course.)

The way to think about concatenative languages is in terms of function  
composition. Each term in the language represents a function that  
takes a stack as an argument and returns a new stack as a result. This  
is most clearly seen in Joy where stacks are first class and  
inexpensive to pass around freely. I'd try not to think about it in  
the Forth sort of mindset where there's a single stack (or pair of  
stacks) that all operations mutate.

> This leads me to wonder whether concatenation is related to  
> referential transparency.

In Joy, most functions are referentially transparent. Depending on how  
you look at it, you might even say that all functions are  
referentially transparent because the compositional nature of the code  
makes it possible to thread a single invisible state throughout the  
entire program. Some degree of hand-waving is required however.

> I have the impression that the language is concatenative iff we can  
> safely translate A & B to:
> ... Id est replace words with their definitions. This means that a  
> word's definition only relies on the definitions on the words it  
> references.

Correct.

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

Correct; things like local variables make a language non- 
concatenative. Factor offers locals but uses a compile-time transform  
to convert definitions that use them to purely concatenative code.

> What lets me uneasy with this point of view is that "concatenative"  
> is not supposed to be a synonym of "purely functional". Or what?

It depends on the language. For example, all data is persistent in  
Joy; only IO will cause a visible side effect. In a language like  
Factor, much data is not persistent.

> Are purely functional languages necessarily, logically, concatenative?

Not at all. Haskell is purely functional (i.e. there are *no* side  
effects), but not concatenative.

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

Many languages have the property that new words are treated equally to  
built-in words. What's unique about Io is that any function has access  
to the message sent to it before any expressions associated with that  
message are reduced. This is similar to the situation in Joy and XY  
where functions can manipulate the functions passed to them (called  
"quotations") as if they were lists. Factor offers a macro system that  
lets you do the same sort of things you do in Forth.

> 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

You may want to look at this page; it shows how concatenative  
languages can be turing complete with a very minimal combinator  
selection:
http://tunes.org/~iepos/joy.html

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

The simple grammar of concatenative languages makes it easy to do the  
sort of things you're talking about. It's not a property unique to  
concatenative languages however.

> I wonder about the practical usefulness of the concatenative  
> propertie(s).

They're useful. Tons of code is written in Forth. Factor has shown  
tremendous progress in a very short period of time. If you're  
interested in how such languages can be productive, I'd encourage you  
to download Factor and get to work.

Factor offers an OO system which may make you feel more at home,  
although it's based on multiple dispatch (I think) rather than message  
passing; the former makes more sense for a concatenative language. I  
don't know the system well enough to give you an example to your  
problem, although I'm sure asking on the #concatenative channel on  
Freenode would get you results; quite a few Factor programmers hang  
out there.

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

They're not incompatible. Many Forths have objects, Factor has  
objects, and I believe there was talk of adding a prototype-based  
object system to Cat at one point as well. If you want to reimplement  
Io in Factor, you'd be more than able to. I'd encourage you to try the  
existing system first though and see what you think.

- John