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

On Mar 5, 2009, at 3:26 PM, William Tanksley wrote:

> John Nowak wrote:
>> John Cowan wrote:
>>> John Nowak scripsit:
>>>> In a concatenative language, one thing you can do as add the  
>>>> 'world'
>>>> to the top of the stack and have all operations work below it  
>>>> except
>>>> those that perform IO. This does let you sort of hand-wave and  
>>>> claim
>>>> the language is purely functional. The problem is that *everything*
>>>> now has a forced evaluation order, not just those things that  
>>>> perform
>>>> IO. In other words, even though your language is purely functional,
>>>> you're still essentially stuck with having to use eager evaluation.
>
> I don't see why this approach forces a totally fixed evaluation order.
> It seems to me that it forces a fixed order only for words which don't
> "work below the world" (I'm not certain precisely what you mean by
> that).

If you're threading the world around on the stack, and every operation  
works on a stack with the world on top (but perhaps does not read/ 
update it), you can't reduce any function until it gets access to the  
world. Sure, you can be smart and reduce functions that you know don't  
ultimately care about the world, but you can without passing any sort  
of world around anyway; simply only allow arbitrary-order reduction  
when no functions with side effects will be reduced.

The point of a "pure" language is that you never have to know which  
functions have side effects because *none* of them do. Adding a world  
and passing it to everything means side effects are *eliminated*, but  
you now have no flexibility when reducing programs. If, however, your  
language only passes the world to functions that need it, you still  
eliminate all side effects but have more flexibility in how you  
evaluate the program. It becomes completely unnecessary to worry about  
which functions are pure and which aren't because they're all pure. If  
their conditions are satisfied, you can reduce.

> A dumb optimizer has to assume that every operation changes the entire
> state; a smarter one knows to look at stack effects; a really smart  
> one
> knows to look for I/O effects.

Aye, and this is what I would do in a language with effect inference.  
The thing to be clear on here is that a language with effect inference  
is not pure because it still has effects. Things like "full" lazy  
evaluation are not generally possible. Languages with effect inference  
like Disciple Haskell are eager and impure.

> No, I wouldn't claim that; I just claim that concatenative languages
> _can_ be purely (or partially, or not at all) functional, and still
> retain full concatenativity. Of course, they lose OTHER advantages.

Agreed.

- John