Drucken eines AST mit Variablennamen

Question

Ich versuche, eine EDSL in Haskell zu implementieren. Ich würde gerne den AST mit den Variablennamen, die gebunden sind, ausdrucken (wenn ich die echten Namen nicht bekommen kann, würden einige generierte Namen genügen).

Dieses, wie weit ich mit einem einfachen Beispiel bekam:

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 

Laufen ergibt dies:

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

Also, was ich will ist Plus (I 4) (I 3) mit Plus var0 var1 zu ersetzen. Ich habe darüber nachgedacht, durch den Rest des Baums zu gehen und die gebundenen Variablen durch Namen-Wert-Tupel zu ersetzen, aber ich bin mir nicht 100% sicher, ob/wie das funktionieren würde. Ich würde es auch vorziehen, die ursprünglichen Variablennamen zu behalten, aber ich kann mir keine einfache Möglichkeit vorstellen, dies zu tun. Ich hätte lieber eine ziemlich leichte Syntax in Haskell (so wie oben).

Ich würde auch gerne Hinweise auf Material, das mich lehrt, wie man diese Art von Dingen zu tun. Ich habe ein bisschen über freie Monaden und GADTs gelesen, aber ich denke, ich vermisse es, alles zusammen zu setzen.

Answer 1

Mit der Struktur, die Sie haben, können Sie dies nicht tun, in „reinen“ Haskell Code, denn sobald der Code kompiliert wird, Sie nicht (Plus a b) von (Plus (I 4) (I 3)) unterscheiden kann und halten „referentielle Transparenz“ - die Austauschbarkeit von Variablen und ihre Werte.

Jedoch gibt es unsichere Hacks - d. H. Nicht garantiert zu arbeiten - die können Sie diese Art von Sache machen lassen. Sie werden in der Regel unter dem Namen "Observable Sharing" geführt und basieren auf dem Zugriff auf die Interna der Darstellung von Werten unter Verwendung von StableName. Im Wesentlichen erhalten Sie eine Zeigergleichheitsoperation, mit der Sie zwischen dem Verweis auf a und einer neuen Kopie des Werts (I 4) unterscheiden können.

Ein Paket, das hilft, diese Funktionalität zu schließen, ist .

Die tatsächlichen Variablennamen, die in Ihrer Quelle verwendet werden, gehen beim Kompilieren unwiderruflich verloren. In Paradise verwenden wir einen Preprozessor, um foo <~ bar in foo <- withName "foo" $ bar vor der Kompilierung zu übersetzen, aber es ist hacky und es verlangsamt ziemlich baut.

Answer 2

Ich fand dies basierend auf @Gabriel Gonzales 'linked answer. Die Grundidee ist, einen neuen Variablen -Konstruktor im Expr-Typ einzuführen, und Sie weisen diesen eine eindeutige ID zu, wenn Sie den Baum interpretieren. Das und die Säuberung der Code etwas gibt:

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 

Hübscher Druck und läuft:

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