Sat Feb 20 14:13:51 CET 2010

Embedding Faust in Haskell

Let's look at Faust[1].

Faust's basic data type are data stream operators representing block
diagrams.  It supports the following operators (block diagrams)
compositions (precedence):

f ~  g   recursive (4)
f ,  g   parallel (3)
f :  g   sequential (2)
f <: g   split (1)
f :> g   merge (1)

The combinators seem strange at first sight.  It seems that
wire-crossings are not so simple to express.

The graphic representations in [3] are most illustrative.

* The : operator is not the same as function composition: it operates
  on a stack of signals.  (Faust is a stack language??)

* The , combinator is like : with the stack replaced by a queue.

* The <: and :> operators are fan-out and (summed) fan-in.

* The ~ operator is the y combinator with a delay in the loop.

* The _ and ! operators are identity and cut (sink).

To embed these combinators in the Ai.hs structure, one needs the
concept of "delay", i.e. polynomials.  I.e. a data flow network can
contain outputs that are fed back as inputs.

Then the Faust operators (the block diagram algebra defined in [3])
can probably be built on top of that by allowing a representation of
"busses" and operations on them.

Let's look closer at the algebra.  The operators <: and :> seem
ad-hoc.  They could use some explicit fanout / fanin operations.  Atm
they seem to be fixed at duplicate / sum.  (It would be more
interesting if this were an equality constraint ;)

I do like the stack and queue operators : and , but these could be
augmented with some more general wire-shuffling routing combinators.

The paper[3] mentions (2.9) the Stefanescu Algebra of Flownomials
(AoF) to be related.  AoF is an extension of Kleene's calculus of
regular expressions.  See pubs in [5].

                              * * *

Apparently Claude is/was working on something similar[4].  Looks like
he gave up after finding some type level tricks that lead to
exponential compilation times.

If I understand correctly, the problem seems to be that Faust's
combinators can easily be embedded as operations on lists of streams
(busses).  However, to make it possible to determine bus size at
compile time, some other machinery is necesary.  This rings several
faint bells related to stack languages and typing.  I believe the Cat
language's type system might be of use here.

In Cat[6] the main trick seems to be that operations are polymorphic
over the rest of the stack.

[1] http://faust.grame.fr/
[2] http://www.grame.fr/Ressources/pub/faust-chapter.pdf
[3] http://www.grame.fr/Ressources/pub/faust-soft-computing.pdf
[4] http://claudiusmaximus.goto10.org/cm/2009-12-06_heist_busted.html
[5] http://www.comp.nus.edu.sg/~gheorghe/papers/selPub.html
[6] http://www.cat-language.com/Cat-TR-2008-001.pdf