Fri Jun 14 10:06:26 EDT 2013

Composing state machines

Note these are synchronous state machines, which are a bit simpler
than event-based ones.  The basic model I use for the audio DSP work
is the state space model (SSM) or state space representation, which
has nice properties if it is linear:


Goal: represent a stream operator in Haskell in an abstract way, but
allow for C code generation from the description.

A stream operator consists of an initial state value and update
function with types:

(s,i) -> (s,o)

Ignoring the explicit state, the straightforward way to represent a
stream operator as a pure function is something like this:

    data S a = S a (S a)
    S i -> S o

However, the state info is lost here.  So the SSM rep can be mapped to
the stream rep, but not vice versa.

When composing two SSMs (ignoring the initial state) you get something

   ( (s1,a) -> (s1,b) ) ->
   ( (s2,b) -> (s2,c) ) ->
   ((s1,s2),a) -> ((s1,s2), c)

This is troublesome, because the state "grows".

The whole thing is here:

The composition would fit neatly in the Arrow abstraction except for
that dangling state vector.

It is possible to use existential types to hide the states.
The trouble with that is they become quite inaccessible.

In the end, after composition, I really want a type (s,i) -> (s,o)
where s is a large composition of per-SSM state vectors, because that
information is used to generate C code.  I also want this to fit in
the Arrow abstraction, so it integrates better into Haskell.

For code generation, the SSM idea is combined with the "final tagless"
representation trick to perform abstract interpretation.  See:


All this +- works.  To work out how exactly to use the existential
types, I did some type directed programming to just see where the
types lead me, but in the end I got confused.  It all seems a bit

I took that idea and went back to Scheme (Racket) to do what I wanted
to do in the first place; to build a tool that I can use effectively
to write audio DSP code (*).  This is the result up to now:

Doing it in Scheme allowed me to "emulate" types and type classes.  An
interesting exercise in itself, but still, in Haskell it would be a
lot simpler.

Now that I know that the basic idea works, I'd like find a good way to
port it back to Haskell, probably on top of Feldspar.