用变量名称打印AST [英] Printing an AST with variable names
问题描述
这是我有一个简单的例子有多远：
import Control.Monad.State
data免费fa = Roll（f（Free fa））
|纯一个
实例Functor f => Monad（Free f）其中
return = Pure
（Pure a）>> = f = fa
（Roll f）>> = g = Roll $ fmap（> > = g）f
data Expr a = I a
| （显示）
数据StackProgram a next = Pop（a - >下一个）
|推下一个
实例Functor（StackProgram a）其中
fmap f（Pop k）= Pop（fk）
fmap f（Push ix）= Push i（fx）
liftF :: Functor f => f a - >免费f a
liftF l = Roll $ fmap返回l
push :: a - > Free（StackProgram a）（）
push i = liftF $ Push i（）
pop :: Free（StackProgram a）a
pop = liftF $ Pop id
prog3 :: Free（StackProgram（Expr Int））（Expr Int）
prog3 = do
push（I 3）
push（I 4）
a < ; - pop
b< - pop
return（Plus ab）
showSP'::（Show a，Show b）=> Free（StackProgram a）b - > [a] - > State Int String
showSP'（Pure a）_ = return $return++ show a
showSP'（Roll（Pop f））（a：stack）= do
i< - get
put（i + 1）
rest< - showSP'（fa）stack
return $var++ show i ++< - pop++ show （a：stack）++\\\
++ rest
showSP'（Roll（Push in））stack = do
rest< - showSP'n（i：stack）
返回$push++ show ++ ++++ +++ show ++ ++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Free（StackProgram a）b - > [a] - >字符串
showSP prg stk = fst $ runState（showSP'prg stk）0
给出：
* Main> putStrLn $ showSP prog3 []
push I 3 []
push I 4 [I 3]
var0 < - pop [I 4，I 3]
var1 < - pop [I 3]
return Plus（I 4）（I 3）
我想要用 Plus var0 var1 替换 Plus（I 4）（I 3）。我曾考虑过遍历树的其余部分，并用名称值元组替换绑定的变量，但我不能100％确定该/如何工作。我也希望保留原始的变量名称，但我想不出一个简单的方法来做到这一点。我宁愿在haskell中使用相当轻量级的语法（类型如上）。
我也很欣赏指向材料的指针，它告诉我如何最好地做到这些种类的东西。我已经阅读了一些免费的monads和GADT，但我想我错过了如何把它放在一起。
所以你不能在纯粹的Haskell代码中这样做，因为一旦你的代码被编译完成，你就无法区分（Plus ab）从（Plus（I 4）（I 3））并保留参照透明度 - 变量及其值的可交换性
<但是有不安全的黑客 - 即不能保证工作 - 可以让你做这种事情。他们通常使用可观察分享的名称，并基于获取价值如何表达的内部机制，使用 StableName 。从本质上讲，它给了你一个指针相等操作，它允许你区分对 a 的引用和值（I 4） code>。
有助于结束此功能的一个包是 data-reify 。
源代码中使用的实际变量名称在编译期间将不可挽回地丢失。在 Paradise 中，我们使用预处理器来翻译 foo <〜 bar 到 foo< - withNamefoo$ bar 编译之前，但它很不方便，并且会减慢编译的速度。
I am trying to implement an EDSL in Haskell. I would like to pretty print the AST with the variable names that are bound (if I can't get the real names then some generated names would do).
This is how far I have got with a simple example:
import Control.Monad.State
data Free f a = Roll (f (Free f a))
| Pure a
instance Functor f => Monad (Free f) where
return = Pure
(Pure a) >>= f = f a
(Roll f) >>= g = Roll $ fmap (>>= g) f
data Expr a = I a
| Plus (Expr a) (Expr a)
deriving (Show)
data StackProgram a next = Pop (a -> next)
| Push a next
instance Functor (StackProgram a) where
fmap f (Pop k) = Pop (f.k)
fmap f (Push i x) = Push i (f x)
liftF :: Functor f => f a -> Free f a
liftF l = Roll $ fmap return l
push :: a -> Free (StackProgram a) ()
push i = liftF $ Push i ()
pop :: Free (StackProgram a) a
pop = liftF $ Pop id
prog3 :: Free (StackProgram (Expr Int)) (Expr Int)
prog3 = do
push (I 3)
push (I 4)
a <- pop
b <- pop
return (Plus a b)
showSP' :: (Show a, Show b) => Free (StackProgram a) b -> [a] -> State Int String
showSP' (Pure a) _ = return $ "return " ++ show a
showSP' (Roll (Pop f)) (a:stack) = do
i <- get
put (i+1)
rest <- showSP' (f a) stack
return $ "var" ++ show i ++ " <- pop " ++ show (a:stack) ++ "\n" ++ rest
showSP' (Roll (Push i n)) stack = do
rest <- showSP' n (i:stack)
return $ "push " ++ show i ++ " " ++ show stack ++ "\n" ++ rest
showSP :: (Show a, Show b) => Free (StackProgram a) b -> [a] -> String
showSP prg stk = fst $ runState (showSP' prg stk) 0
Running this gives:
*Main> putStrLn $ showSP prog3 []
push I 3 []
push I 4 [I 3]
var0 <- pop [I 4,I 3]
var1 <- pop [I 3]
return Plus (I 4) (I 3)
So what I want is to replace Plus (I 4) (I 3) with Plus var0 var1. I have thought about walking through the rest of the tree and replacing the bound variables with name-value tuples, but I am not 100% sure if/how that would work. I'd also prefer to keep the original variable names, but I can't think of an easy way of doing this. I would prefer to have a fairly light-weight syntax in haskell (kind of as above).
I would also appreciate pointers to material that teaches me how to best do these kinds of things. I have read a bit on free monads and GADTs, but I guess I am missing how to put it all together.
With the structure you have, you can't do this in "pure" Haskell code, because once your code is compiled, you can't distinguish (Plus a b) from (Plus (I 4) (I 3)) and keep "referential transparency" - the interchangeability of variables and their values.
However there are unsafe hacks - i.e. not guaranteed to work - that can let you do this kind of thing. They generally go under the name "observable sharing" and are based on getting access to the internals of how values are represented, using StableName. Essentially that gives you a pointer equality operation that allows you to distinguish between the reference to a and a new copy of the value (I 4).
One package that helps wrap up this functionality is data-reify.
The actual variable names used in your source will be irretrievably lost during compilation. In Paradise we use a preprocessor to translate foo <~ bar into foo <- withName "foo" $ bar before compilation, but it's hacky and it slows down builds quite a bit.
这篇关于用变量名称打印AST的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
