使用变量名打印AST

Question

我正在尝试在Haskell中实现EDSL.我想用绑定的变量名来打印AST(如果我不能得到真实的名字,那么一些生成的名称会这样做).

这是我用一个简单的例子得到的:

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

运行这个给出:

*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 (I 4) (I 3)用Plus var0 var1.我已经考虑过遍在树的其余部分并用名称值元组替换绑定变量,但我不是100%确定是否/如何工作.我也更喜欢保留原始变量名称,但我想不出这样做的简单方法.我更喜欢在haskell中使用相当轻量级的语法(如上所述).

我也非常感谢能够教会我如何最好地完成这些事情的材料.我已经阅读了一些关于免费monad和GADT的内容,但我想我错过了如何将它们放在一起.

Answer 1

你所拥有的结构,你不能在"纯" Haskell代码做到这一点,因为一旦你的代码编译,你不能区分(Plus a b)从(Plus (I 4) (I 3))有保有压"引用透明" -的变量及其值的互换性.

然而,有些不安全的黑客 - 即无法保证工作 - 可以让你做这种事情.它们通常以"可观察共享"的名称命名,并基于使用StableName访问值的表示方式.本质上,它为您提供了一个指针相等操作,允许您区a分值的引用和新副本(I 4).

一个有助于结束此功能的软件包是数据验证.

在编译期间,源中使用的实际变量名称将无法挽回地丢失.在天堂,我们使用一个预处理翻译foo <~ bar成foo <- withName "foo" $ bar编译之前,但它是哈克,它会减慢建立了不少.