Печать AST с именами переменных

Question

Я пытаюсь реализовать EDSL в Haskell. Я хотел бы напечатать 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, но, думаю, мне не хватает того, как все это собрать.

Answer 1

Имея структуру, которую вы имеете, вы не можете сделать это в "чистом" коде на Haskell, потому что, как только ваш код скомпилирован, вы не сможете различить (Plus a b) от (Plus (I 4) (I 3)) и сохранить "ссылочную прозрачность" - взаимозаменяемость переменных и их значений.

Однако существуют небезопасные хаки - то есть не гарантированные работы - которые могут позволить вам делать такие вещи. Они обычно идут под названием "наблюдаемый обмен" и основаны на получении доступа к внутренним элементам представления значений с помощью StableName. По сути, это дает вам операцию равенства указателей, которая позволяет вам различать ссылку на a и новая копия значения (I 4),

Одним из пакетов, который помогает обернуть эту функцию, является reify данных.

Фактические имена переменных, используемые в вашем источнике, будут безвозвратно потеряны во время компиляции. В раю мы используем препроцессор для перевода foo <~ bar в foo <- withName "foo" $ bar до компиляции, но он хакерский и сильно тормозит сборки.

Answer 2

Я понял это, основываясь на связанном ответе@Gabriel Gonzales. Основная идея состоит в том, чтобы ввести новый конструктор переменных в типе Expr, и вы присваиваете им уникальный идентификатор при интерпретации дерева. Это и очистка кода немного дает:

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