In một AST có tên biến

Question

Tôi đang cố triển khai EDSL trong Haskell. Tôi muốn in đẹp AST với tên biến bị ràng buộc (nếu tôi không thể có được tên thật thì một số tên được tạo ra sẽ làm).

Đây là cách nay tôi đã có với một ví dụ đơn giản:

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 

Chạy điều này mang lại:

*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) 

Vì vậy, những gì tôi muốn là để thay thế Plus (I 4) (I 3) với Plus var0 var1. Tôi đã nghĩ về việc đi qua phần còn lại của cây và thay thế các biến bị ràng buộc bằng các giá trị tên-giá trị, nhưng tôi không chắc chắn 100% nếu/làm thế nào có thể hoạt động. Tôi cũng muốn giữ tên biến ban đầu, nhưng tôi không thể nghĩ ra một cách dễ dàng để làm điều này. Tôi muốn có một cú pháp khá nhẹ trong haskell (loại như trên).

Tôi cũng đánh giá cao các chỉ dẫn cho tài liệu dạy tôi cách làm tốt nhất những thứ này. Tôi đã đọc một chút về monads miễn phí và GADT, nhưng tôi đoán tôi đang thiếu cách để đặt tất cả lại với nhau.

Answer 1

Với cấu trúc bạn có, bạn không thể làm điều này trong mã Haskell "thuần", bởi vì khi mã của bạn được biên dịch, bạn không thể phân biệt (Plus a b) từ (Plus (I 4) (I 3)) và giữ "tính minh bạch tham chiếu" - khả năng thay thế của các biến và giá trị của chúng.

Tuy nhiên, có các lỗi không an toàn - tức là không được bảo đảm để hoạt động - có thể cho phép bạn thực hiện loại điều này. Họ thường đi theo tên "chia sẻ quan sát" và được dựa trên việc tiếp cận với các bên trong cách các giá trị được biểu diễn, sử dụng StableName. Về cơ bản cung cấp cho bạn hoạt động bình đẳng bằng con trỏ cho phép bạn phân biệt giữa tham chiếu đến a và bản sao mới của giá trị (I 4).

Một gói giúp gói gọn chức năng này là data-reify.

Tên biến thực được sử dụng trong nguồn của bạn sẽ bị mất một cách không thể tin được trong quá trình biên dịch. Trong Paradise, chúng tôi sử dụng một bộ tiền xử lý để dịch foo <~ bar thành foo <- withName "foo" $ bar trước khi biên dịch, nhưng nó bị hack và chậm lại một chút.

Answer 2

Tôi đã tìm ra điều này dựa trên @Gabriel Gonzales 'linked answer. Ý tưởng cơ bản là giới thiệu một biến số biến mới trong loại Expr và bạn chỉ định một id duy nhất khi bạn diễn giải cây. Đó và dọn dẹp mã một chút cho:

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 

Khá in ấn và chạy:

*Main> putStrLn $ showSP prog3 
push 3, [] 
push 4, [3] 
var0 <- pop [4,3] 
var1 <- pop [3] 
var0 + var1 
*Main> evalSP prog3 
7