Fri Jan 14 15:13:41 EST 2011

DSP code gen

Conclusions up to now:

  - Use instances of the Num class to perform code analysis.  This has
    the huge advantage that pure functions in the problem remain pure
    in the modeling/specification, and we don't need to carry around a
    pile of scaffolding.  It also allows maximum code reuse.

  - For representing dynamics, update equations are the way to go.  I
    am currently in dispute about using either:

     * the forward state-space form:
       x_{k+1} = f (x_k)

       This is conceptually more straightforward as it isolates
       shift/memory operators from pure functions.  This facilitates
       analysis of the RHS update functions themselves.

     * backward time delays (old approach):
       x_k = f(x_{k-1}, x_(k-2}, ...)

      This needs a delay operator intermingled with the the function
      specification.  The only advantage seems to be that for
      implementation this is quite straightforward.  Delays are just
      indexed state memory references.

    Putting it this way makes it fairly clear: choose state-space form
    to preserve purity.

    Note also that in many problems, the state space formulation is
    more natural than a multiplied-out multiple delay form.  For lack
    of being able to make that more precise, I can mention that at
    least for low-frequency dynamics the state space formulation has
    superior numerical performance due to the large magnitude
    difference between coefficients in the multiplied-out form.

  - Sharing.  The expressions for the update equations f might contain
    shared subexpressions.  It is important to respect the
    programmer's effort to write (keep!) a problem in memoized form.

    Due to referential transparency, implementation details like value
    sharing are not observable for Haskell functions, so this needs a
    special treatment.  There seem to be two options, of which the
    first one seems most appropriate:

      * Sharing monad[1].  All code that uses data sharing needs to be
        written in monadic form.

      * Sharing recovery through common subexpression elimination.

[1] http://www.cas.mcmaster.ca/~carette/publications/scp_metamonads.pdf

[1] entry://20100219-131604