[Haskell-cafe] AST Rewriting

[Steve Severance]

Hi Everyone,

I am trying to build a function to rewrite and AST. I have and AST which is
designed to represent a computation graph. I will present a simplified
version here designed to illustrate the problem. I have tried numerous ways
of rewriting it including uniplate, recursion and Edward Kmett's
implementation of plate in his lens package.

My AST is defined using GADTs as follows:

class (ReflectDescriptor a, Typeable a, Wire a) => ProtoBuf a

data Expression a b where
  OpenTable :: (ProtoBuf b) => Int -> Table -> Expression () b
  OpenFile :: (ProtoBuf b) => Int -> String -> Expression () b
  WriteFile :: (Typeable a, ProtoBuf b) => Int -> String -> Expression a b
-> Expression b ()
  WriteTable :: (Typeable a, ProtoBuf b) => Int -> Table -> Expression a b
-> Expression b ()
  Map :: (ProtoBuf a, ProtoBuf b, ProtoBuf c) => Int -> (a -> b) ->
Expression c a -> Expression a b
  LocalMerge :: (ProtoBuf a) => Int -> [Expression c a] -> Expression c a

The user can create code inside a Monad Transformer like so:

q <- query $ do
         table <- openTable myTable
         transform <- map someFunc table
         writeTable otherTable transform

As part of this language the compiler I am building would need to for
instance transform OpenTable into a series OpenFile nodes with a LocalMerge
to merge the results together.

So uniplate cannot work over GADTs if I recall correctly.

I exchanged emails with Edward and he explained that for the lens case I
would need something like an indexed lens family from his indexed package
which is not implemented yet but which may be in the future.

The issue with recursion is that as you recurse through the AST the a b on
the Expression change and GHC cannot compile it because it wants the a b to
be the same on each recursive call.

My question to the Haskell community is how might one develop AST rewriting
functionality. One possible solution is stripping the types away from GHC
and doing all the type checking myself. That doesn't seem very good.

Another possibility that I have looked at was using hoopl. It seems very
compatible given that it is built for describing and optimizing data flow
which I am doing however the learning curve looks quite steep. I have been
reluctant so far to invest the time in it.

Has anyone developed something similar? What recommendations do you have?

Thanks.

Steve
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20121120/fb7ee397/attachment.htm>