[Haskell-cafe] AST Rewriting
Emil Axelsson
emax at chalmers.se
Wed Nov 21 14:56:36 CET 2012
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
>
More information about the Haskell-Cafe
mailing list