haskell - 打印带有变量名称的 AST

Question

我正在尝试在 Haskell 中实现 EDSL。我想用绑定(bind)的变量名称漂亮地打印 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。我曾考虑过遍历树的其余部分并用名称值元组替换绑定(bind)变量，但我不能 100% 确定这是否/如何工作。我也更愿意保留原始变量名称，但我想不出一种简单的方法来做到这一点。我更喜欢 haskell 中有一个相当轻量级的语法(类似于上面)。

我也很感激能教我如何最好地做这些事情的 Material 。我读过一些关于免费 monad 和 GADT 的内容，但我想我不知道如何将它们组合在一起。

Answer 1

根据您所拥有的结构，您无法在“纯”Haskell 代码中执行此操作，因为一旦编译了代码，您就无法区分 (Plus a b)来自(Plus (I 4) (I 3))并保持“引用透明度”——变量及其值的可互换性。

但是，存在不安全的黑客行为 - 即不保证有效 - 可以让你做这种事情。它们通常被称为“可观察共享”，并且基于使用 StableName 访问值如何表示的内部结构。 。本质上，这为您提供了一个指针相等操作，允许您区分对 a 的引用。以及值 (I 4) 的新副本.

有助于完成此功能的一个包是 data-reify .

源代码中使用的实际变量名称将在编译过程中不可挽回地丢失。在 Paradise我们使用预处理器来翻译 foo <~ bar进入foo <- withName "foo" $ bar在编译之前，但它很 hacky 并且会大大减慢构建速度。