[Haskell-cafe] AST Rewriting

[Alexander Solla]

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>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
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20121120/8ee2195a/attachment-0001.htm>