[Haskell-cafe] AST Rewriting

[Emil Axelsson]

This is one of the problem Syntactic aims to solve, but it requires you 
to use a different representation of expressions (for good or bad). If 
you want to keep your existing representation, then you have to use a 
generic programming library that supports GADTs. I know at least the 
Spine approach supports GADTs, but the library on Hackage seems too 
incomplete to be useful:

   http://hackage.haskell.org/package/spine

I don't know if there are other libraries that support GADTs.

You can also have a look at CompData:

   http://hackage.haskell.org/package/compdata

It is similar to Syntactic (i.e. requires a different representation), 
but it has a richer library of generic traversals.

/ Emil


2012-11-21 04:20, Alexander Solla skrev:
> Have you read "Data types a la carte"?  The 'syntactic' package
> implements the ideas, but it was a little dense for my purposes when I
> looked (I just wanted data types, a la carte; it focuses on manipulating
> ASTs defined a la carte).  It might be what you need, or you can roll
> your own based on the paper.
>
>
> On Tue, Nov 20, 2012 at 3:21 PM, Steve Severance
> <sseverance at alphaheavy.com <mailto:sseverance at alphaheavy.com>> wrote:
>
>     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
>
>     _______________________________________________
>     Haskell-Cafe mailing list
>     Haskell-Cafe at haskell.org <mailto:Haskell-Cafe at haskell.org>
>     http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>