Wed Jan 11 10:59:17 EST 2012
State machines & register allocation
I've been playing with Haskell a bit lately, writing a state machine
compiler (essentially SSA form of code without recursion: original
form is only letrec-style mutual tail recursion).
This makes me think about a certain disconnect between the approach
used in Staapl (stacks = local variables) and a state machine approach
that's so useful for embedded systems. There isn't really a good way
in Staapl to make this kind of thing work well due to lack of
structure namespaces., i.e. separating the 'instance' and 'member'
All the talk of protocol-oriented programming does seem to have
something underlying it (minimise state in data processing by focusing
on streams), but in practice it happens that data structures are
buffer-oriented, not stream-oriented, probably due to a bias of the C
programming language. Stream-oriented work requires protocol design.
If the protocol is fixed the minimal memory usage is limited by
(ad-hoc) protocol decisions and random data dependencies.
Concretely: i'd like to solve the USB protocol parser problem in a
smart way but this really requires either buffering and structure
(namespace) support, or a botched stream-oriented approach that tries
to work with the limitations of the protocol.
I was thinking that *if* the intention is to compile down to a bunch
of global variables, then it's possible to just use a modifed kind of
macro. The Staapl macros have lambda and I bet this isn't so hard to
then turn into global memory references in an instantiation phase:
- function abstraction: name binding only: associate each argument
with a "var @" macro.
- function calls: pop arguments from stack and store them into the
associated macros. requires knowledge of arity, but could be
included at definition time.
This requires a "lazy argument" macro, where each argument is
interpreted as an inline function instead of a literal value.
A macro like :
: foo-macro a b c | ... ;
would be instantiated to a function foo' by binding its arguments to
: foo-code [ v1 @ ] [ v2 @ ] [ v3 @ ] foo-macro
and each call to 'foo' would be implemented as a macro or function
: foo v3 ! v2 ! v1 ! foo' ;
The purpose of this approach is then to isolate naming (just lamba
arguments) from storage allocation.
This technique is probably useful in general to allow "flattening" of