[Haskell-cafe] ANN: data-fix-cse -- Common subexpression elimination for EDSLs

[Emil Axelsson]

2013-02-19 12:10, Anton Kholomiov skrev:
> I'm glad to announce the package for Commonsubexpression elimination [1].
> It's an implementation of the hashconsig algorithm as described in the
> paper
> 'Implementing Explicit and Finding Implicit Sharing in EDSLs' by Oleg
> Kiselyov.
>
> Main point of the library is to define this algorithm in the most
> generic way.
> You can define the AST for your DSL as fixpoint type[2]. And then all
> you need
> to use the library is to define the instance for type class `Traversable`.

One way to make the library even more useful would have been to base it 
on compdata instead of data-fix. Compdata has support for composable 
types and lots of extra functionality. On the other hand, it's easy 
enough to translate from compdata terms to your `Fix`...



> One side-note form my experience: Fixpoint types can be very flexible.
> It's easy to compose them. If suddenly we need to add some extra data
> to all cases from the example above we can easily do it with just another
> Functor:
>
> Imagine that we want to use a SampleRate value with all signals.
> Then we can do it like this:
>
> type E = Fix SampledExp
>
> data SampledExp a = SampledExp SampleRate (Exp a)
>
> then we should define an instance of the type class Traversable
> for our new type SampleRate. The Exp doesn't change.

Very useful indeed! A more principled way to extend data types in this 
way is Data Types à la Carte:

   http://dx.doi.org/10.1017/S0956796808006758

(Implemented in compdata.)

/ Emil