## ANN: data-fix-cse -- Common subexpression elimination for EDSLs

2013-02-19 11:10:43 GMT

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`.

This idea is inspired by `data-reify` [3] package which you can use to transform

your ASTs to DAGs too. But it relies on inspection of the references for values

when `data-fix-cse` doesn't sacrifices the purity.

A short example:

Let's define a tiny DSL for signals

import Data.Fix

type Name = String

type E = Fix Exp

data Exp a = Const Double | ReadPort Name | Tfm Name [a] | Mix a a

deriving (Show, Eq, Ord)

We can make constant signals, read them from some ports and transform them

(apply some named function to the list of signals) and mix two signals.

Let's define an instance of the Traversable (hence for the Functor and Foldable)

import Control.Applicative

import Data.Monoid

import Data.Traversable

import Data.Foldable

instance Functor Exp where

fmap f x = case x of

Const d -> Const d

ReadPort n -> ReadPort n

Mix a b -> Mix (f a) (f b)

Tfm n as -> Tfm n $ fmap f as

instance Foldable Exp where

foldMap f x = case x of

Mix a b -> f a <> f b

Tfm n as -> mconcat $ fmap f as

_ -> mempty

instance Traversable Exp where

traverse f x = case x of

Mix a b -> Mix <$> f a <*> f b

Tfm n as -> Tfm n <$> traverse f as

a -> pure a

Now we can use the functio `cse`

cse :: (Eq (f Int), Ord (f Int), Traversable f) => Fix f -> Dag f

to transform our AST to DAG. DAG is already sorted.

Later we can define a handy wrapper to hide the details from the client

newtype Sig = Sig { unSig :: E }

You can find examples in the package archive

Extra-Source-Files: test/Exp.hs test/Impl.hs

test/Expl.hsIf you want to see a real world example of usage you can find it

in the csound-expression[4]. An edsl for the Csound language.

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.

[1] http://hackage.haskell.org/package/data-fix-cse-0.0.1

[2] http://hackage.haskell.org/package/data-fix-0.0.1

[3] http://hackage.haskell.org/package/data-reify

[4] http://hackage.haskell.org/package/csound-expression

Anton

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe <at> haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe