Going Stackless?

Levi Pearson levi at cold.org
Tue Feb 27 16:41:40 MST 2007


Steve <smorrey at gmail.com> writes:
> Hey there everyone,
> I've decided to roll my own scripting language from scratch.

Well, I guess I shouldn't be too surprised that you didn't listen to
my advice, since you didn't seem to listen to it any of the previous
times I offered it.  But I suppose you have your reasons.

> At present my VM executes fast and fine until it reaches a blocking
> call at which time the whole works will freeze until it's unlocked
> (for instance a long iterative loop).

A problem that has plagued MUD programmers, and writers of concurrent
programs in general (like time-sharing operating systems), for a very
long time.  There are also a lot of reasonable solutions.  Many, in
order to keep things deterministic in the face of concurrency, use a
cooperative concurrency model.  This is also, fortunately, the easiest
to implement.

In a cooperative system, a task executes until it decides to yield
control back to the scheduler.  This has the problem you observed that
if you aren't careful, a task can steal all the computing resources by
choosing not to yield.  The typical solution to this is to enforce
some sort of limit, after which a task is simply stopped and given a
'timeout' exception.  Means are provided for a task to see how much
processor time it has left to use before it's stopped so it can yield
before time runs out.

This works out pretty well, and keeps things fairly deterministic.
You still have to make sure you yield in safe spots, where you won't
leave anything in an inconsistent state.  You do have to be pretty
disciplined in your coding to ensure you yield when appropriate, but
not as disciplined as you have to be if your task could be preempted
at any moment.

> One solution I've come up with is to spawn a child VM, pass the child
> a reference to the parent, pass it a copy of the stack sections it's
> going to need, run the child in it's own thread, and have the child
> notify the parent when the process completes.
>
> This works ok, but there is a whole lot of overhead and extra code involved.

Indeed.  Probably not a good idea, especially considering your
scalability goal, unless you confine the size of the thread pool.  You
will also have to keep in mind proper locking of data structures in
your scripts.

>
> I've been reading a lot about language design and one thing that
> intrigues me is a stackless model.  It appears to be some sort of
> programming cure-all but I don't really understand what a stackless
> language involves, or how it is different from my stack model.

"Stackless" in this context is a bit of a misnomer.  What it really
means is that you are not using the C stack for your stack; instead,
you have a linked list or some other data structure containing
activation records.  Now, instead of being limited to one stack, you
can have as many as you want at the same time.  This is somewhat more
expensive than doing everything on the C stack, which has nice
assembly instructions to manipulate it, but far less expensive than
creating OS threads for everything.

> Anyways for anyone versed in language design, compiler theory etc.
> What am I missing here?  How exactly does a stackless language work?
> What are the pitfalls of a stackless language?

Many Scheme interpreters use a 'stackless' virtual machine, since it
makes the implementation of first-class continuations much easier than
it would if you were using the C stack.  It isn't the only way to do
it, though.  I'm currently reading a paper by Kent Dybvig about this:
http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

Lua, of course, already has coroutines built into the language.
Scheme has continuations.  Erlang has a lightweight, extremely
scalable concurrency model that can take advantage of multi-processor
systems now.  I think you really ought to use someone else's language,
because language design is a very difficult thing to get right; far
more difficult than a network server.

                --Levi



More information about the PLUG mailing list