[stack] Re: Concatenative Hardware

--- 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? 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.

> 
> The "dip" instruction is so important I'm tempted to include variants:
> 
> 12: DIP2 : (a b fxn -> a b)
> 13: DIP3 : (a b c fxn -> a b c)
> 14: DIP4 : (a b c d fxn -> a b c d)
> 15: open for suggestions
> 
> Of course "DIP" can be implemented as "SWP QTE COMP CALL", but I'm
> concerned about performance. The "DIP" is one of the most frequent
> instructions in my code.
> 
> Anyway, hopefully this makes sense to my fellow concatenators. I'd
> love to hear thoughts and suggestions. I'm pretty naive when it comes
> to hardware.
> 
> - Christopher
>