<span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">Hi Everyone,</span><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
<br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">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.</div>
<div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)"><br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
My AST is defined using GADTs as follows:</div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)"><br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
class (ReflectDescriptor a, Typeable a, Wire a) => ProtoBuf a </div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)"><br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
<div>data Expression a b where</div><div> OpenTable :: (ProtoBuf b) => Int -> Table -> Expression () b</div><div> OpenFile :: (ProtoBuf b) => Int -> String -> Expression () b</div></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
<div> WriteFile :: (Typeable a, ProtoBuf b) => Int -> String -> Expression a b -> Expression b ()</div><div> WriteTable :: (Typeable a, ProtoBuf b) => Int -> Table -> Expression a b -> Expression b ()</div>
</div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)"> Map :: (ProtoBuf a, ProtoBuf b, ProtoBuf c) => Int -> (a -> b) -> Expression c a -> Expression a b</div>
<div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)"> LocalMerge :: (ProtoBuf a) => Int -> [Expression c a] -> Expression c a</div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
<br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">The user can create code inside a Monad Transformer like so:</div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
<br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">q <- query $ do</div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
table <- openTable myTable</div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)"> transform <- map someFunc table</div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
writeTable otherTable transform</div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)"><br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
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. </div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
<br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">So uniplate cannot work over GADTs if I recall correctly.</div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
<br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">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.</div>
<div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)"><br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
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.</div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
<br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">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. </div>
<div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)"><br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
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.</div>
<div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)"><br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
Has anyone developed something similar? What recommendations do you have?</div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)"><br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
Thanks.</div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)"><br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
Steve</div>