[<<][staapl][>>][..]

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'
concepts.

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
the variables:

   : 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
stack allocation.

[1] entry://../meta




[Reply][About]
[<<][staapl][>>][..]