Re: [stack] Concatenative Hardware

On 11/2/07, William Tanksley, Jr <[email protected]> wrote:
> 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).

Yes, this is where I am stuck.

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

Whoops some mistakes. Especially the missing ADD.

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

Great, I'll look into it.

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

4 bits is my goal.

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

I'm looking for alternatives, I don't like the idea of CONS cells. I'm
thinking of a linked list of mini-stacks, but this is just a vague
notion at this point.

> This implies that there's one per cell.
>  That's MAJORLY inefficient in every way, needless to say.

Yep.

> It's obvious
>  that one optimization would be to pack multiple instructions into a
>  single CONS cell,

I'm thinking of 32 bit stack, which can contain 8 4 bit instructions.

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

Interesting idea.

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

Good point. Besides I need those slots for ADD, a PUSH, and possibly a NOOP.

>  > 15: open for suggestions
>
>  YES! 4 bits! (Assuming you don't want math or conditionals...)

JZ was the conditional (which I am thinking of combining with LTEQ, to
make JLE (Jump if less than or equal)  when do we use LTEQ outside of
a branch anyway, if we need a true LTEQ we can say: JLE

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

That is a good point.

> Much
>  better to let users implement DIP the way they need it.

Its just that when I generate Cat from C code algorithmically it
generates a ton of DIPs.

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

Not neccessarily, if we use lists with tail pointers. However, that is ugly.

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

Good idea.

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

Great point. Thank you for mentioning it.

Thanks a lot for sharing your ideas!

- Christopher