9

我正在尝试在 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 中有一个相当轻量级的语法（如上所述）。

我也很感激那些教我如何最好地做这些事情的材料的指针。我已经阅读了一些关于免费单子和 GADT 的内容，但我想我想念如何将它们放在一起。

4

2 回答 2

5

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

然而，有一些不安全的技巧——即不能保证有效——可以让你做这种事情。它们通常以“可观察共享”的名称命名，并且基于使用StableName访问值如何表示的内部结构。本质上，这为您提供了一个指针相等操作，允许您区分a对 value 的引用和新副本(I 4)。

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

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

于 2013-02-16T00:30:25.353 回答
4

我是根据@Gabriel Gonzales 的链接回答得出的。基本思想是在 Expr 类型中引入一个新的变量构造函数，并在解释树时为它们分配一个唯一的 id。这和清理代码有点给出：

import Control.Monad.Free
import Data.Map

newtype VInt = VInt Int

data Expr = IntL Int
          | IntV VInt
          | Plus Expr Expr

instance Show Expr where
  show (IntL i)        = show i
  show (IntV (VInt i)) = "var" ++ show i
  show (Plus e1 e2)    = show e1 ++ " + " ++ show e2

data StackProgF next = Pop  (VInt -> next)
                     | Push Expr next

instance Functor StackProgF where
  fmap f (Pop    k) = Pop (f.k)
  fmap f (Push e x) = Push e (f x)

type StackProg = Free StackProgF
type Stack = [Expr]

push :: Expr -> StackProg ()
push e = liftF $ Push e ()

pop :: StackProg Expr
pop = liftF $ Pop IntV

prog3 :: StackProg Expr
prog3 = do
  push (IntL 3)
  push (IntL 4)
  a <- pop
  b <- pop
  return (Plus a b)

showSP :: StackProg Expr -> String
showSP prg = go 0 prg []
  where
    go i (Pure a)          _     = show a
    go i (Free (Pop n))    (h:t) = "var" ++ show i ++ " <- pop " ++ show (h:t) ++ "\n" ++ 
                                   go (i+1) (n (VInt i)) t
    go i (Free (Pop _))    []    = "error: pop on empty stack\n"
    go i (Free (Push e n)) stk   = "push " ++ show e ++ ", " ++ show stk ++ "\n" ++ go i n (e:stk)

type Env = Map Int Expr

evalExpr :: Expr -> Env -> Int
evalExpr (IntL i)        _   = i
evalExpr (IntV (VInt k)) env = evalExpr (env ! k) env
evalExpr (Plus e1 e2)    env = evalExpr e1 env + evalExpr e2 env

evalSP :: StackProg Expr -> Int
evalSP prg = go 0 prg [] empty
  where
    go i (Free (Pop _))    []    env = error "pop on empty stack\n"    
    go i (Free (Pop n))    (h:t) env = go (i+1) (n (VInt i)) t       (insert i h env)
    go i (Free (Push e n)) stk   env = go i     n            (e:stk) env
    go i (Pure a)          _stk  env = evalExpr a env

漂亮的打印和运行：

*Main> putStrLn $ showSP prog3
push 3, []
push 4, [3]
var0 <- pop [4,3]
var1 <- pop [3]
var0 + var1
*Main> evalSP prog3
7
于 2013-02-17T14:23:10.330 回答