Re: [stack] Advantages of cat, joy ..?

Don Groves wrote:
> William Tanksley wrote:
> > The stack might possibly be the simplest concatenative datatype. It's
> > easy to add more complexity: A second stack, or a dictionary, or a
> > readable/writable terminal, or a queue to handle continuations, etc.
> > I've seen nothing that provides similar power to a stack, although I'd
> > like to.

> I really wish we could come up with a different name for the "stack"
> in these languages. The canonical stack only has two methods,
> push and pop, and they only operate on the top item in the stack.
> All other items are invisible. This data structure has several uses as
> it stands and shouldn't be corrupted, in my view.

This is a good point. Actually, it ties in with what I was saying:
concatenative languages don't really use _merely_ a stack; they all have
something more in addition.

In this case, you're pointing out that "stack" languages all have the
stack plus something more to allow shuffling. Most of the formal
languages use 'dip' as their model, which in turn can be implemented by
means of a second stack (Forth's return stack, or Factor's old retain
stack).

> Maybe we could call ours a "reorderable stack" (rstack) or a
> "shufflestack" (s-stack) or something that differentiates it from what
> is taught in Comp Sci 101.

I don't think there's really a need. "The stack" is different from "a
stack", and truly, the difference is merely that some words use
auxiliary data structures; this doesn't make the stack itself less of a
stack.

Of course, if we're truly going to understand concatenative languages at
a formal level, we must not gloss over these auxiliary data structures.
We have to explain what words use them, and which ones actually mutate
persistent structures versus which ones use only transient ones.
(Forth's >R and R> mutate a persistent structure; Joy's 'dip' creates a
transient one.)

> Granted, the additional stack operators we define can be defined
> in terms of push and pop, but that isn't the way we usually implement
> them and would be inefficient if we did (on register machines anyway).

I don't think implementations details matter that much to a formal
model.

> Maybe I'm too picky but I've seen too many other previously-defined
> names reused in ways that only cause confusion (mostly mine).

This is true. But the 'stack' in stack languages truly is a stack, I
think.

> don

-Wm