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

[Anton Kholomiov]

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>

> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130219/b3d614db/attachment.htm>