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

[Emil Axelsson]

Fully understandable! Compdata would be quite a heavy dependency for 
your library.

I'm just generally fond of the idea of collecting all DSL implementation 
tricks under one umbrella. That requires using the same term representation.

/ Emil

2013-02-19 14:12, Anton Kholomiov skrev:
> There are several packages that already define fixpoints (another one is
> about unification), but all packages that I'm aware of define a lot of
> functionality
> that I don't need (and actually don't understand, packages with fixpoint
> types
> tend to be rather dense with math). I'd like it to be simple and
> lightweight.
> Just fixpoints, just folds and unfolds.
>
>
> 2013/2/19 Emil Axelsson <emax at chalmers.se <mailto:emax at chalmers.se>>
>
>     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
>     <http://dx.doi.org/10.1017/S0956796808006758>
>
>     (Implemented in compdata.)
>
>     / Emil
>
>