Re: [stack] Concatenative Hardware

Christopher Diggins <[email protected]> wrote:
> William Tanksley, Jr <[email protected]> wrote:
> >  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.

I'm picturing a multiprocessor model based on Baker's model, with one
dedicated memory processor (hooks up to external memory) and a bunch
of general purpose processors, each with a decent amount (TBD) of
internal memory.

The memory processor will handle synchronizing all the internal
memories with the external shared memory, and will also continuously
compact external memory.

(Of course, this can also be done in software as a VM, in which case
the "memory processor" will simply be a compactor task.)

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

The "missing comparison" claim was my mistake -- I didn't notice JZ. My bad.

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

Whoops, I did see that later; should have corrected my
misapprehension. 4 bits is great.

Another thing to consider is that control flow instructions are
special and rarely used; if you're packing multiple instructions in a
single memory word, it makes sense to define those instructions as
valid only at the last instruction in the word, which leaves those
opcodes open for other uses in the other instruction slots. If you do
this, you can has room for all the arithmetical opcodes.

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

That's equivalent to what I was thinking of as a linked list of
arrays, so we're on the same page.

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

Ah, I see. Yes, that's just fine.

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

It would be like the RPC-4000
(http://catb.org/jargon/html/story-of-mel.html, highly recommended
programming literature) -- every instruction word would include its
own implicit GOTO.

I guess you'd bitpack a bit more and use the last instruction slot to
choose between JUMP, BRANCH, and CALL behavior (so only 2 bits; I
guess we'd invent a CALLBRANCH instruction to use all the bits, and
we'd encode a few extra instructions in the 2 remaining bits, so every
32-bit word would have 3 full instructions, 1 short instruction, and 1
call instruction).

Now, because the instruction stream isn't on the stack, it might be
possible to load it from a linked list in shared memory (canonical
form) into a array form in-processor, thus making it much more
compact. I have no idea what would work better. (There will not be any
issues with cache locality, so it may be better to simply store the
on-chip form as a linked list -- in fact the first software model
should do that.)

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

NOOP is very handy when dealing with slotted instructions... Sometimes
you just don't have 4 instructions to fill a word with.

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

Sure, but this processor isn't Cat; a decent generator for it will
generate different code than a decent one would for Cat.

To be fair, if we can do DIP in vaguely similar time to the other
instructions I've got no beef with it.

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

Oh, yes, you could tail-CONS the dipped value on, if that's what you
meant. But tail pointers would be really, really nasty... I'm pretty
sure they wouldn't work in general (EVERY node of a list would have to
maintain a tail pointer, right?).

There's got to be a cleaner solution...

I definitely would prefer using CONS as the machine primitive; CONCAT
is (as I mentioned) linear time, and that's just not good in hardware.

> Thanks a lot for sharing your ideas!

Hard to stop me, isn't it. ;-)

> - Christopher

-Billy