Re: [stack] Re: Concatenative Hardware

On 11/2/07, pml060912 <[email protected]> wrote:
> --- In [email protected], "Christopher Diggins"
> <cdiggins@...> wrote:
> >
> > So I've been thinking about concatenative hardware lately. Here is a
> > single-stack
> > machine instruction set:
> >
> > 0: JZ (val fxn -> ) // jump to fxn if value is below zero
> > 1: CALL (fxn) // push return address and jump to fxn
> > 2: LTEQ (val val -> bool) // compare values
> > 3: AND (val val -> val) // perform bitwise and
> > 4: XOR (val val -> val) // perform XOR operation
> > 5: SHL (val val -> val) // shift-left
> > 6: DUP (a -> a a) // duplicate top-value
> > 7: QTE (val -> fxn) // create a thunk
> > 8: COMP (fxn fxn -> fxn) // compose two functions (append their
> contents)
> > 9: POP (a -> ) // pop value from stack
> > 10: DIP (a fxn -> a) // applies function to below top of stack
> > 11: SWP (a b -> b a) // swap top two items
> >
> > So essentially we can use the data stack also as a return address
> > stack.
>
> Maybe I'm missing a layer of sophistication hidden within the
> capabilities of one of these instructions (COMP, maybe?), but doesn't
> that restrict the virtual machine to the capabilities of a pure single
> stack machine?

QTE and COMP allows you to treat function like stacks, by adding data
to them, which you can accesss later by calling CALL. So
computationally it is a multi-stack machine.

> As I mentioned the other day, those aren't Turing
> equivalent - I had a quick look at the wikipedia entry on stack
> machines to confirm it - although you get that with two stack machines
> and machines with more generalised instructions like PICK or ROLL or
> data structuring/accessing instructions (ignoring finite physical
> restrictions for the moment).
>
> This is a zero operand instruction set, so it is very compact
> > and can be implemented efficiently, but it takes a lot of instructions
> > to do simple things (e.g. accessing items deep in the stack).
>
> For what it's worth, I contributed the original versions of the high
> level PICK and ROLL used in Ting's Eforth. They work using recursion
> and the return stack for temporary storage. That approach doesn't use
> many instructions in the code or many different opcodes, but it does
> use a lot of cycles to get very deep.

What are the stack effects of PICK and ROLL? (I don't really know
FORTH that well).

I wonder if PICK and ROLL would be a better choice than DIP, QTE, COMP, etc.

- Christopher