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

John Nowak wrote: 
> William Tanksley wrote:
> > Technical point: Referential Transparency in a concatenative  
> > language is
> > different from the same concept in an applicative language. In one
> > sense, it's harder to use, since you can't simply move words from one
> > place to another (without rearranging the stack); in another sense  
> > it's
> > easier to use, since you can "factor out" a word without having to do
> > any work at all (cut and paste is sufficient). Unlike applicative
> > languages, you do NOT have to worry about functional state; the fact
> > that the stack acts as a monad means that the state is already
> > preserved; even I/O can be modelled properly.

> Not everyone agrees on this point. Take a look at this thread:
>     http://lambda-the-ultimate.org/node/3050

I think they're trying to discuss how not all concatenative languages
need to be functional and vice versa... A point I've made myself just
recently. But you're right to correct me when I use the technical term
"referential transparency" in an inappropriate way. Only purely
functional languages can be referentially transparent.

> Many would say Joy is not purely functional

I agree with them.

> and that the "monadic  
> stack" argument essentially amounts to hand-waving.

There's a lot more details to be worked out, but the essence is true --
linear logic with data items on a stack impose an order on computation.
Extracting that order is not a completely solved problem, and it's
always been an item of interest to me.

I'm often overly impatient about figuring it out -- that makes me say
things like "the stack is a monad, concatenative languages need nothing
else." I'm wrong to say that; it's more complicated than that. But a
naive concatenative language (i.e. one that executes strictly in order)
needs nothing else; and a sophisticated one needs only as much
sophistication as its out-of-order execution can handle.

> If you take this  
> view, then the question of Joy or Factor being "purely concatenative"  
> depends on if you require concatenative languages to be "purely  
> functional".

As you can see, I don't require that. My definition of "concatenative"
implies and requires associativity in syntax and semantics; it doesn't
mention functionality. A purely concatenative language may be highly
stateful, and thus not a functional language. It may be zeroeth order,
and therefore not a function-level language. It's still concatenative.

Joy is supposed to be somewhat functional -- if von Thun had intended it
to be purely functional he would have done something different with I/O.
Factor makes no claims as to functionality, just practicality, so the
"question" has never been raised.

> Joy isn't "pure enough" to allow evaluation via postfix term rewriting  
> in an arbitrary order. If you had a type system that could enforce  
> something similar to the I/O monad in Haskell, it would be. I  
> definitely think there's some use in distinguishing between the  
> relative purity of both approaches.

I entirely agree; that's why it's essential to maintain a distinction
between "purely functional" and "purely concatenative". You can have
both, neither, or either. There are benefits and prices for all
combinations.

> I feel that being able to evaluate in any order without worrying about  
> side effects is somehow "more concatenative" than having to evaluate  
> left to right. Rather than make a claim here, I tried to sidestep the  
> issue to avoid contention. I see I failed once again! :)

You'll not escape me! :)

I'd disagree that it's more concatenative to be able to evaluate in any
order. It is certainly more functional (or declarative), though. And
there IS value to it. The problem is that there's also a price to be
paid, and not every programmer wants to pay it.

In reality, the stack is not the only thing that gets passed to every
function. In every practical concatenative language so far invented
there's always something else -- sometimes a dictionary, sometimes an
I/O device... Often an entire virtual machine. There's value in
simplifying this machine (following a functional approach), and there's
value in clearly characterizing it (following a formal approach). One
need not do either.

For an example of how a more functional approach simplified a language,
consider Joy's introduction of 'dip', which entirely eliminated the need
for Forth's programmer-editable return stack. Of course, the return
stack or something like it is still hiding in the background; stevan's
XY language makes its replacement explicit, but in both cases it remains
a part of the global state, just like the data stack.

> - John

-Wm