Wed Nov 9 10:15:18 EST 2011

Finite-state Machines (shallow coroutines) and extensible compiler state.

While it is often useful to work on a "thread" abstraction level where
each thread of control has a separate execution stack, on a low-RAM
uC this can be expensive because tasks have to be dimensioned for the
worst case stack usage.

In practice however, it is often possible to write a solution in terms
of a Finite-state Machine (FSM).  Doing this manually (without
language support) can be a bit of a drag, as it involves explicit
computation of a state variable on FSM exit, and dispatch on FSM

It is possible to remove this hassle by generating the state storage
and state dispatch code as part of a "yield" command, which has the
same meaning as a true coroutine yield, with the exception that it can
only be executed from the main thread of control, i.e. it's execution
stack is only 1 deep, hence the name "shallow coroutine" (SCR).

Implementing this in Staapl requires a (compile time) context that can
relate control points in the code to allocation of state IDs.  In
order to make this work, I've added an "ext" field to the compiler
state which contains a (functional) hash table.

The purpose of this field is to provide local state for macro
functionality, i,e, "begin-fsm ... end-fsm" in an extensible, modular
way, meaning that state from different modules will not clash.

An interesting observation is that once this mechanism works for a
1-SCR, it might be possible to extend it to support n-SCR, which would
be a coroutine with bounded stack depth.  If all the control points
are known at compile time it is possible to "flatten" the thread state
by enumerating it.