[stack] Re: Concatenative operators as functions over stacks.

--- In [email protected], "Don Groves" <dgroves@...> wrote:
>
> I've long been intrigued by Manfred's statement that Joy operators are
> best described as functions from stacks to stacks

If you just look at that on its own, it isn't enough. There's a
standard computer science result, that I don't have a reference to off
hand, that says that a PURE stack machine isn't Turing equivalent,
i.e. if you can only work within a limited depth of one stack at any
stage and the stack only holds simple values (roughly speaking). You
can get Turing equivalent if you have a two stack machine, or if you
have non-standard operators, e.g. like Forth's PICK and ROLL, or
non-functional stuff for memory peeking and poking like Forth's @ and !.

.
.
.
> So, here's the question -- can all required operations of a
> concatenative language be defined in terms of these two primitive
> stack operations and function composition?

No, not within the pure stack machine limit. When I look at my own
work with Furphy (mentioned in earlier threads), it turns out that all
operations in that take two stacks and return two stacks, but most
operations leave one - the return stack - essentially unchanged. So,
most operations can be thought of as taking and yielding a single
stack, but some need both; these are really higher order functions in
some sense (you can build PICK and ROLL using these and the simpler
operations). But you don't need to go beyond two stacks and end up
with a regress of stacks, a stack of stacks say.
.
.
.
> By adding additional notation for lists, sets, ..., this method seems
> able to account for any concatentative operation.

That's another way of expanding what you can do with one stack, enough
to make it Turing equivalent. And of course I provide that in Furphy
too - but it turns out, so far, that this is orthogonal to what Furphy
does with higher order, two stack using, operations. PML.