Re: [stack] Monads in a Stack-Based Language

Christopher Diggins <[email protected]> wrote:
> William Tanksley, Jr <[email protected]> wrote:
> > It would be nice to have a theory that explains local variables inside
> > a concatenative language, if such a thing is possible.

> I may not understand precisly what you are saying, but I thought Brent
> Kerby did a pretty good job on the subject of local variables. You can
> convert any form with named variables to one without quite easily.

Perhaps you're right, and his work could lead to a semantic
understanding of local variables in a concatenative context.

> In
> Cat (well to be precise an extension to Cat called Big Cat) I now
> support named variables in both definitions and quotation.

Yeah, so do most "concatenative" languages (scare quotes, just for
fun). Locals are conceptually a bit risky for me; I feel like they're
foreign to the language. We're all trained in imperative applicative
languages so locals look natural -- but most of us don't even have a
precise model for how locals work in _applicative_ languages. (Look
how hard the authors of SICP have to work to teach the concept.)

> What I am looking for is an elegant mapping from a stack-based
> language with global variables to a referentially transparent
> stack-based language. I believe I have found one, but the theory
> behind it still eludes me.

That's good quarry to hunt! Once you stalk it down, you'll also help
explain how word meanings can be dynamically redefined in the system
dictionary.

In typical stack-based concatenative languages, the order of execution
is completely specified (by the monad of the stack), so "side effects"
become perfectly predictable. Side effects only become a problem when
you add in the ability to reorder execution. Gut feeling: I suspect
that you can only reorder execution when you have a concept of partial
ordering of dataflow, as we discussed in our other thread today.

Thus, a formalization of global variables will depend on a
formalization of reordering execution, which in turn depends on a
formalization of partial ordering. All the problems fade away in the
trivial degenerate case where no reordering is allowed because the
data is totally ordered.

> Christopher

-Billy