Re: [stack] Concatenative Hardware

Chris,

This suggestion may be somewhat orthogonal to your memory management  
issue (or not), but it's something I've been interested in
for some time:  Could you build a machine with capability-based  
addressing?  That is, instead of building an MMU (not that you said  
you were going to) could you protect a process' memory from other  
processes with capabilities?

In this context, a "capability" is like a conventional pointer into  
memory, but it also includes other information, such as the size of  
the memory area it points to, some permission bits (read/write/ 
execute user code/execute system code), and an extra bit to indicate  
that this is a capability.

See Levy, "Capability-based Computing Systems" for a somewhat dated  
review, at http://www.cs.washington.edu/homes/levy/capabook/

So why do I suggest this for your Cat machine?  Cat has a real static  
type system (not just "types").  There's a very interesting  
interaction between capabilities and type systems:  if your machine  
had capabilities, the Cat type system might be able to handle memory  
management for you.  The suggestion below for LinearLisp is somewhat  
in this vein, but doesn't go as far as some current research in  
handling the problem.  For a start, have a look at Greg Morrisett,  
"Linear regions are all you need", and "Monadic regions", both  
available at his web page, http://www.eecs.harvard.edu/~greg/papers/ 
index.html.  Another site of interest is the Typed Assembly Language  
site at http://www.cs.cornell.edu/talc/

This way, you "pay" for memory management, and you get MMU-like  
process separation for free.  Or vice versa.

-Rod


On Nov 2, 2007, at 12:32 PM, Christopher Diggins wrote:

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



[Non-text portions of this message have been removed]