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