A monadic DSP language.

Main idea: the non-monadic abstract interpretation approach in ../ai/
has a major drawback: in Haskell code it is not possible to directly
capture node sharing (memoization) by abstract evaluation of the
function only.

While it is possible to recover input->output dependency information
for Haskell functions of the Num class through abstract interpretation
by defining a Num instance that constructs expression trees for
arithmetic operations, it is impossible to recover _internal_ sharing
information from a Haskell program by observing just the input->output
behaviour of that program.  Here "sharing" refers to bindings defined
by `let' and `where' forms that have more than one reference, thus
producing a dependency graph instead of a tree.

More concretely, the structure of `let' or `where' is a property of
the program text used to specify the function, but _not_ of the
behaviour itself.

The reason for this is that Haskell respects referential
transparency[1]:

  An expression e is referentially transparent if and only if e can be
  replaced with its evaluated result without affecting the behavior of
  the program.

If the sharing structure of a Haskell program would be part of the
behaviour of a functions, then shared bindings clearly would not be
referentially transparent as the replacement operation mentioned above
would change the sharing structure, bleeding through to observable
behaviour.

In short: values are just values do not encode who they are used by.
They are not (observable as) graph nodes.  In fact, the compiler is
free to move around internal binding structure as long as the
observable behaviour of the function remains the same.

In the presence of sharing, the output of an abstract interpretation
over expression trees will be a tree with duplicate nodes.  Note that
this duplication might very well be _implemented_ by sharing nodes in
the data structure, but the fact that it is or isn't is not
observable.

With careful input prepration, external input nodes can be unified
using equality in a straightforward way, but internal nodes need to be
"scanned" based only on structural equivalence of their dependency
graph that traces back to the input nodes.  This is really just common
subexpression elimination and has not much to do with the original
structure.

While it is convenient to not have to use a monadic approach when
specifying algorithms, it is probably not a good idea to use it as a
basic approach.  Sometimes explicit specification of sharing structure
might be necessary.  It seems better to build the inferred structure
on top of the explicitly specified structure.

The monad used is the code in this directory is modeled after the
state-continuation monad from [2].


[1] http://en.wikipedia.org/wiki/Referential_transparency_(computer_science)
[2] http://www.cs.rice.edu/~taha/publications/conference/pepm06.pdf


Entry: Structural elements
Date: Sun Dec 23 20:21:19 EST 2012

Core insights:

* Provide R S <-> S R commutation: representation of structures to/fro
  structures of representations.  This allows true lambda to be used
  for representing multi-arg functions.

* DAG-building requires a monad.  (e.g. variable names + references to
  share structure)

* A lexical front-end is probably needed to introduce "side-effecting"
  code ordering just like in Scheme.  To stick to haskell do-notation
  is probably too annoying.  What about making this Scheme?  It would
  allow a simple alternative implementation.