From: mmcg@cs.monash.edu.au (Mike  Mc Gaughey)
Subject: Re: Distributed lpmud
Organization: Computer Science, Monash University, Australia
Date: Thu, 17 Dec 1992 12:24:13 GMT

oreillym@tartarus.uwa.edu.au (Michael O'Reilly) writes:

>Mike  Mc Gaughey (mmcg@cs.monash.edu.au) wrote:

>: No - otherwise, how do you guarantee that your destructors
>: are called on values in the main stack?  Easier to have one stack,
>: and an `exception jump address'.  The neat thing is, this

>Where do you store this exception jump address? Or do you keep track
>of what can produce what exception?

The `current' jump address is a per-thread global; nearly all exception handlers
are all passed through in the normal course of code execution, so each
can pop the prior one off the C stack.  As it turns out, insisting that
your destructors be called properly means that the exception address
changes rapidly - but, in general, there needs to be only one per (C or
interpreted) function, because jumping to an exception address implies
executing all subsequent exception handlers until the return point.

This is easy to see for the interpreted code if you think about the
`linear, block scoped' semantics of C - an exception means finding an
appropriate exception handler, but all `exception handlers' (and I'm
using the term loosely here) which (syntactically) appear between the
point the exception occurred and the handler that intercepts that
exception have to be queried, because they might do important things -
like destruct values which are leaving scope (can't do this at the end
of the function because you wouldn't be able to re-use stack slots, and
you wouldn't know which had been initialised before the exception
occurred).

This means that each exception handler in a function will *know* the
address of the subsequent one, so can jump directly to it - no need to
use a stack for the addresses within a single function.  In fact, in
many cases there's no need to have explicit jumps at all - you can have
four opcodes - start/end exception handling and enter/leave subscope.
When an exception occurs, you can linearly scan the opcodes between the
exception point and the end of the function, turning processing on when you
see one at an equal or outer scope.  (Scoping is because you don't want
to "capture" the destructors, and break, continue, return, etc handlers
from subscopes; I don't know whether this would produce more compact
M-code.  Of course, if you want to do any sort of code motion, you may
need occasional spurious jump addresses - but I doubt any of us bothers
much with code motion :)

>'continuation-based C code'. So thats what it's called. :) Any
>pointers on nicer ways to write this sort of stuff other than zillions
>of little state machines???

Heh.  I wrote myself a macro package in M4 which translates a combination
of macro calls and inline C into C functions which (effectively) implement
a pushdown automaton (and typechecks under GCC :) by splitting each function
in two at every call/return point.  It's ugly to program in -
feels a bit like assembler - but it's better than doing it by hand, and
it ensures that each of the split-up components of a C function share the
same type definitions for parameters, locals, and return value address,
and that they all get a little "current exception check" header.

In any case, although there are a lot of things that have to be
implemented this way, the bulk of the code in the driver is _known_ to
be nonblocking; things like hash table lookups hardly need to be
written this way, and the C message passing code is all implemented
nonblocking (it awakens the intended receiver by raising its priority;
only stream endpoints need to be started this way).  The things that
_are_ written this way are anything that could block; this includes
_some_ efuns, the opcode dispatcher itself, scheduler, and so on.

>you mention destructors above. here is a cute little problem. How do
>you write a call your m-code destructor in continuation-based C code?

You don't!  Them that creates the value - or the space for it -
destroys it when it goes out of scope.  If they want a value (of a
particular type) returned, they create a spot for it and initialise
with a `nil' value, and expect you to fill it in (hell, how else do you
do assignment? :).  A proof that this works (heh) can be found in
Jaques Girard's `paper' (actually an entire journal's worth) on linear
logic (uhh, "J. Theoretical Comp Sci", within the last 2 years.  Don't
have it at the moment, and never want to see it again :).  A useful
application (an extroadinarily useful one) can be found in Wadler:
Comprehending Monads, in which he uses `monad comprehensions' to
implement updateable stores in a pure functional language (the idea
being that you only have one reference, at any time, to an instance of
an updateable array, so you can destructively update it).  If you think
about it, you can only have one reference to a stack variable (though
*it* might refer to a shared heap variable - e.g. a list or string -
with a ref count).

>How to you cope with a call to your m-code at the very lowest level of
>C code???? I.e. any call to pop_stack() might result in a  call to an
>m-code routine.

pop_stack?  Not relevant - only m-code will do that, and it's
interpreted by a (suspendable) thread.  Other things go through the
function call interface which is (must be!) a continuation entry
point.  The lowest level of C code that can call an m-code hook of any
description (or block) is implemented as continuations.  But that
lowest level can be implemented surprisingly high :)

>Does this mean you have to check each and every call
>to pop_stack() in case it didn't actually run, and needs to be
>re-tried? This means you EVERY routine that calls any other routine
>needs to declare a static variable to indicate where it got up to
>before some operation failed. ARGH!!!

But our `exception jump address' requires that anyway, within a
function - and are pushed on the stack during function calls.  And,
yes, you *do* need a per-thread `current exception' value, so that
each of your handlers know whether they're supposed to handle it.
Note that we've been talking about catch/throw exception handling
throughout - signal handling is a different matter (one I haven't
worried about yet).

Mike, who's supposed to be working.
--
Mike McGaughey			AARNET:	mmcg@bruce.cs.monash.edu.au

"Head stompin', ass kickin', finger licking nastiness"