[Haskell-cafe] ANN: data-fix-cse -- Common subexpression elimination for EDSLs
Emil Axelsson
emax at chalmers.se
Tue Feb 19 13:30:55 CET 2013
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
More information about the Haskell-Cafe
mailing list