Re: [stack] Concatenative Hardware

Christopher Diggins <[email protected]> wrote:
> So I've been thinking about concatenative hardware lately. Here is a
> single-stack machine instruction set:

Interesting. I've played a lot with stack hardware (designed a
complete processor for a HW class), so your twist on the subject is
very thought-provoking.

> 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

Very high-level... You'll need more detailed semantics for that to
work at all (memory management will be a BEAR for you). Of course,
you're entirely missing ADD and such. Oh, and I see you've got a
comparison instruction, but no conditional call or branch. I assume
you intended to imply those, of course.

You might want to look at Henry Baker's papers on a similar topic.
Check out his paper on O(1) instructions which could implement a VERY
flexible VM that doesn't require GC;
http://home.pipeline.com/~hbaker1/LinearLisp.html. "Hash cons"ing is
very important, and might even fit into hardware.

Once you get memory management a bit more simple, you need to
determine the implications of your instruction encoding. You don't
explain your encoding, which leads me to suspect that each instruction
is encoded as a byte. Needless to say, bit packing is a LOT nicer,
even when you're doing a VM.

The worst implication of your instruction encoding -- and this isn't
something you've made explicit -- is that your instructions _appear_
to be stored in CONS cells. This implies that there's one per cell.
That's MAJORLY inefficient in every way, needless to say. It's obvious
that one optimization would be to pack multiple instructions into a
single CONS cell, but that could well give you worse problems, as then
you have to decide how to handle CALLs. Perhaps the answer should be
that a CALL is always the CDR of a CONS pair...

> So essentially we can use the data stack also as a return address
> stack. 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).

"Doctor, it hurts when I do this." ;-)

It's possible that you shouldn't consider "accessing items deep in the
stack" to be a "simple thing".

> 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)

The DIP instruction is so complex, high-overhead, and dependent on
precise details of user needs that I'm tempted to not include it.

> 15: open for suggestions

YES! 4 bits! (Assuming you don't want math or conditionals...)

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

It seems to me that DIP is inherently complex -- you don't want to
stretch your clock cycle to accommodate a single instruction. Much
better to let users implement DIP the way they need it.

Although I just noticed you use CONCAT instead of CONS. Hmm. That's
another inherently complex instruction (it takes linear time).

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

Think about this carefully... Generally speaking, the minimal
requirement for hardware is that all instructions should be O(1). I've
seen that requirement skipped... Chuck Moore's processors use cycle
times so fast that there's isn't time for the carry flag to propagate
on addition, so when you do addition you have to allow the stack to
settle in the ALU before you read the result of the addition (it's
simpler in practice than it sounds). Most CISCs have varying
instruction times. But in general it makes things messy.

Whatever you do, you do NOT want any single instruction to NOT take
constant time.

> - Christopher

-Billy