Menu
Below is my attempt at a very simple interpreter which is translated from the Java version of the program described in Chapter 1 of "modern compiler implementation in Java" by Andrew w. Appel, and operates directly upon a tree which represents the language.
Basically, my problem is that it saves up all the output until the end before anything at all is printed. I'm really just looking for advice on how to restructure it so that the "print" statements are printed as they are interpreted.
module Interpreter where
--------------------------------------------------------------------
type Id = [Char]
type Output = [Char]
type Value = Int
type Table = [(Id, Value)]
data Stm = CompoundStm Stm Stm |
AssignStm Id Exp |
PrintStm ExpList deriving Show
data Exp = IdExp Id |
NumExp Value |
OpExp Exp Op Exp |
EseqExp Stm Exp deriving Show
data ExpList = PairExpList Exp ExpList |
LastExpList Exp deriving Show
data Op = Plus | Minus | Times | Div deriving Show
--------------------------------------------------------------------
example :: Stm
example = CompoundStm (AssignStm "a" (OpExp (NumExp 5) Plus (NumExp 3)))
(CompoundStm (AssignStm "b" (EseqExp (PrintStm (PairExpList (IdExp "a")
(LastExpList (OpExp (IdExp "a") Minus (NumExp 1))))) (OpExp (NumExp 10) Times
(IdExp "a")))) (PrintStm (LastExpList (IdExp "b"))))
--------------------------------------------------------------------
tableUpdate :: Table -> Id -> Value -> Table
tableUpdate t i v = (i,v):t
tableLookup :: Table -> Id -> Value
tableLookup ((x,v):t) i | x == i = v
tableLookup ((x,v):t) i | x /= i = tableLookup t i
--------------------------------------------------------------------
execute :: Stm -> IO()
execute s = putStr ((\(o,_)->o) (interpStm s ("",[])))
interpStm :: Stm -> (Output, Table) -> (Output, Table)
interpStm (CompoundStm l r) ot = interpStm r (interpStm l ot)
interpStm (PrintStm el) (o,t) = (interpExpList el o t)
interpStm (AssignStm i e) (o,t) = f i (interpExp e (o,t))
where
f i (v,o,t) = (o, tableUpdate t i v)
interpExp :: Exp -> (Output, Table) -> (Value, Output, Table)
interpExp (IdExp i) (o,t) = (tableLookup t i, o, t)
interpExp (NumExp v) (o,t) = (v, o, t)
interpExp (EseqExp s e) ot = interpExp e (interpStm s ot)
interpExp (OpExp l op r) (o,t) = f (interpExp l (o,t)) op r
where
f (v,o,t) op r = g v op (interpExp r (o,t))
g v1 Plus (v2,o,t) = (v1 + v2, o, t)
g v1 Minus (v2,o,t) = (v1 - v2, o, t)
g v1 Times (v2,o,t) = (v1 * v2, o, t)
g v1 Div (v2,o,t) = (v1 `div` v2, o, t)
interpExpList :: ExpList -> Output -> Table -> (Output, Table)
interpExpList (LastExpList e) o t = f (interpExp e (o,t))
where
f (v, o, t) = (o ++ (show v) ++ "\n", t)
interpExpList (PairExpList e el) o t = f (interpExp e (o,t))
where
f (v, o, t) = interpExpList el (o ++ (show v) ++ " ") t
631
Your use of an accumulator is making the output unnecessarily strict. Accumulators are good in strict languages because they allow tail recursion; in lazy languages, they are unnecessary (and often bad). I've rewritten your code below to not use one.
module Interpreter where
--------------------------------------------------------------------
type Id = [Char]
type Output = [Char]
type Value = Int
type Table = [(Id, Value)]
data Stm = CompoundStm Stm Stm |
AssignStm Id Exp |
PrintStm ExpList deriving Show
data Exp = IdExp Id |
NumExp Value |
OpExp Exp Op Exp |
EseqExp Stm Exp deriving Show
data ExpList = PairExpList Exp ExpList |
LastExpList Exp deriving Show
data Op = Plus | Minus | Times | Div deriving Show
example :: Stm
example = CompoundStm (AssignStm "a" (OpExp (NumExp 5) Plus (NumExp 3)))
(CompoundStm (AssignStm "b" (EseqExp (PrintStm (PairExpList (IdExp "a")
(LastExpList (OpExp (IdExp "a") Minus (NumExp 1))))) (OpExp (NumExp 10) Times
(IdExp "a")))) (PrintStm (LastExpList (IdExp "b"))))
--------------------------------------------------------------------
tableUpdate :: Table -> Id -> Value -> Table
tableUpdate t i v = (i,v):t
tableLookup :: Table -> Id -> Value
tableLookup ((x,v):t) i | x == i = v
tableLookup ((x,v):t) i | x /= i = tableLookup t i
--------------------------------------------------------------------
execute :: Stm -> IO()
execute s = putStr ((\(o,_)->o) (interpStm s []))
interpStm :: Stm -> Table -> (Output, Table)
interpStm (CompoundStm l r) t = let (o, t') = interpStm l t in
let (o', t'') = interpStm r t' in
(o ++ o', t'')
interpStm (PrintStm el) t = interpExpList el t
interpStm (AssignStm i e) t = let (v, o, t') = interpExp e t in
(o, tableUpdate t' i v)
interpExp :: Exp -> Table -> (Value, Output, Table)
interpExp (IdExp i) t = (tableLookup t i, "", t)
interpExp (NumExp v) t = (v, "", t)
interpExp (EseqExp s e) t = let (o, t') = interpStm s t in
let (v, o', t'') = interpExp e t' in
(v, o ++ o', t'')
interpExp (OpExp l op r) t = let (v, o, t') = interpExp l t in
let (v', o', t'') = interpExp r t' in
(g v op v', o++o', t'')
where
g v1 Plus v2 = v1 + v2
g v1 Minus v2 = v1 - v2
g v1 Times v2 = v1 * v2
g v1 Div v2 = v1 `div` v2
interpExpList :: ExpList -> Table -> (Output, Table)
interpExpList (LastExpList e) t = let (v, o, t') = interpExp e t in
(o ++ show v ++ "\n", t')
interpExpList (PairExpList e el) t = let (v, o, t') = interpExp e t in
let (o', t'') = interpExpList el t' in
(o ++ show v ++ " " ++ o', t')
With this change, the output comes properly lazily.
You'll notice that there's a lot of repeated code of the form let (value, newTable) = f oldTable in ..., and a lot of repeated code of the form let (output, value) = exp; (moreOutput, value) = exp2 in (output ++ moreOutput, exp3). There are a couple of monads that write this code for you! Here's an example using StateT Table (Writer Output):
module Interpreter where
import Control.Monad.Writer
import Control.Monad.State
import Data.Maybe
--------------------------------------------------------------------
type Id = [Char]
type Output = [Char]
type Value = Int
type Table = [(Id, Value)]
data Stm = CompoundStm Stm Stm |
AssignStm Id Exp |
PrintStm ExpList deriving Show
data Exp = IdExp Id |
NumExp Value |
OpExp Exp Op Exp |
EseqExp Stm Exp deriving Show
data ExpList = PairExpList Exp ExpList |
LastExpList Exp deriving Show
data Op = Plus | Minus | Times | Div deriving Show
type InterpreterM = StateT Table (Writer Output)
example :: Stm
example = CompoundStm (AssignStm "a" (OpExp (NumExp 5) Plus (NumExp 3)))
(CompoundStm (AssignStm "b" (EseqExp (PrintStm (PairExpList (IdExp "a")
(LastExpList (OpExp (IdExp "a") Minus (NumExp 1))))) (OpExp (NumExp 10) Times
(IdExp "a")))) (PrintStm (LastExpList (IdExp "b"))))
--------------------------------------------------------------------
tableUpdate :: Id -> Value -> InterpreterM ()
tableUpdate i v = modify ((i,v):)
tableLookup :: Id -> InterpreterM Value
tableLookup i = gets (fromJust . lookup i)
--------------------------------------------------------------------
execute :: Stm -> IO ()
execute s = putStr . execWriter $ evalStateT (interpStm s) []
interpStm :: Stm -> InterpreterM ()
interpStm (CompoundStm l r) = interpStm l >> interpStm r
interpStm (PrintStm el) = interpExpList el
interpStm (AssignStm i e) = interpExp e >>= tableUpdate i
interpExp :: Exp -> InterpreterM Value
interpExp (IdExp i) = tableLookup i
interpExp (NumExp v) = return v
interpExp (EseqExp s e) = interpStm s >> interpExp e
interpExp (OpExp l op r) = liftM2 (g op) (interpExp l) (interpExp r)
where
g Plus v1 v2 = v1 + v2
g Minus v1 v2 = v1 - v2
g Times v1 v2 = v1 * v2
g Div v1 v2 = v1 `div` v2
interpExpList :: ExpList -> InterpreterM ()
interpExpList (LastExpList e) = interpExp e >>= \v -> tell (show v ++ "\n")
interpExpList (PairExpList e el) = interpExp e >>= \v -> tell (show v ++ " ") >> interpExpList el
There are plenty of other changes that could be suggested from here, but hopefully you agree that this final form is much, much nicer to read than the previous one.
120
To print output on the fly, the interpreter functions interpStm, interpExp, and interpExpList should print output instead of saving it. You will have to convert those functions to run in the IO monad, which involves many changes but the process is straightforward. Since output isn't being saved, the new functions will not have an Output parameter or return value.
The actual call to print happens in interpExpList. The statements print v; return t says that the value v will be printed before any subsequent statement reads the store t. For a reasonable definition of the other functions, this will produce the execution order you want. If you want to be more explicit about the requirement that 'v' is printed before a subsequent statement executes, you can convert the code to CPS.
interpExpList (LastExpList e) t = do
(v, t) <- interpExp e t
print v
return t
-- Code for PairExpList is similar
As a side note, ExpList is isomorphic to [Exp] minus the empty list. Consider using [Exp] instead of ExpList.
43
This question has been closed for a while, but I recently solved this problem and thought people might wish to see how I ended up solving it.
Doing it this way, the print statements are actually printed to the screen as soon as the list of expressions descended from it are finished being evaluated:
module IOInterpreter where
import Data.Char
-------------------------------------------------------------------------------
type Id = [Char]
type Output = [Char]
type Value = Int
type Table = [(Id, Value)]
data Stm = CompoundStm Stm Stm |
AssignStm Id Exp |
PrintStm ExpList deriving Show
data Exp = IdExp Id |
NumExp Value |
OpExp Exp Op Exp |
EseqExp Stm Exp deriving Show
type ExpList = [Exp]
data Op = Plus | Minus | Times | Div deriving Show
-------------------------------------------------------------------------------
example :: Stm
example = CompoundStm (AssignStm "a" (OpExp (NumExp 5) Plus (NumExp 3)))
(CompoundStm (AssignStm "b" (EseqExp (PrintStm [IdExp "a",
OpExp (IdExp "a") Minus (NumExp 1)]) (OpExp (NumExp 10) Times
(IdExp "a")))) (PrintStm [IdExp "b"]))
-------------------------------------------------------------------------------
tableUpdate :: Table -> Id -> Value -> Table
tableUpdate t i v = (i,v):t
tableLookup :: Table -> Id -> Value
tableLookup ((x,v):t) i | x == i = v
tableLookup ((x,v):t) i | x /= i = tableLookup t i
-------------------------------------------------------------------------------
execute :: Stm -> IO()
execute s = do
interpStm s []
return ()
interpStm :: Stm -> Table -> IO Table
interpStm (CompoundStm s1 s2) t = do
t' <- interpStm s1 t
interpStm s2 t'
interpStm (AssignStm i e) t = do
(v, t') <- interpExp e t
return $ tableUpdate t' i v
interpStm (PrintStm es) t = do
(s, t') <- interpExpList es t
putStrLn s
return t'
interpExp :: Exp -> Table -> IO (Value, Table)
interpExp (NumExp v) t = return (v, t)
interpExp (IdExp i) t = return (tableLookup t i, t)
interpExp (EseqExp s e) t = do
t' <- interpStm s t
interpExp e t'
interpExp (OpExp e1 o e2) t = do
(v1, t') <- interpExp e1 t
(v2, t'') <- interpExp e2 t'
return (f o v1 v2, t'')
where
f Plus v1 v2 = v1 + v2
f Minus v1 v2 = v1 - v2
f Times v1 v2 = v1 * v2
f Div v1 v2 = v1 `div` v2
interpExpList :: ExpList -> Table -> IO (String, Table)
interpExpList [] t = return ("", t)
interpExpList (e:es) t = do
(v, t') <- interpExp e t
(s, t'') <- interpExpList es t'
return $ (show v ++ " " ++ s, t'')
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With