A simple interpreter written in Haskell stores the output to the end, and not when it encounters a print expression.

Question

The following is my attempt at a very simple interpreter that translates from the Java version of the program described in Chapter 1, "Modern Implementation of the Java Compiler," by Andrew w. Appel, and runs directly on the tree that represents the language.

Basically, my problem is that it keeps all the output to the end before anything is printed at all. I'm just looking for advice on how to restructure it so that printed statements are printed when 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 tiv = (i,v):t tableLookup :: Table -> Id -> Value tableLookup ((x,v):t) i | x == i = v tableLookup ((x,v):t) i | x /= i = tableLookup ti -------------------------------------------------------------------- execute :: Stm -> IO() execute s = putStr ((\(o,_)->o) (interpStm s ("",[]))) interpStm :: Stm -> (Output, Table) -> (Output, Table) interpStm (CompoundStm lr) ot = interpStm r (interpStm l ot) interpStm (PrintStm el) (o,t) = (interpExpList el ot) interpStm (AssignStm ie) (o,t) = fi (interpExp e (o,t)) where fi (v,o,t) = (o, tableUpdate tiv) interpExp :: Exp -> (Output, Table) -> (Value, Output, Table) interpExp (IdExp i) (o,t) = (tableLookup ti, o, t) interpExp (NumExp v) (o,t) = (v, o, t) interpExp (EseqExp se) 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 = gv 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) ot = f (interpExp e (o,t)) where f (v, o, t) = (o ++ (show v) ++ "\n", t) interpExpList (PairExpList e el) ot = f (interpExp e (o,t)) where f (v, o, t) = interpExpList el (o ++ (show v) ++ " ") t 

Answer 1

Your use of the battery makes the conclusion unnecessarily strict. Batteries are good in strict languages ​​because they allow tail recursion; in lazy languages ​​they are not needed (and often bad). I rewrote your code below so as not to use it.

 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 tiv = (i,v):t tableLookup :: Table -> Id -> Value tableLookup ((x,v):t) i | x == i = v tableLookup ((x,v):t) i | x /= i = tableLookup ti -------------------------------------------------------------------- execute :: Stm -> IO() execute s = putStr ((\(o,_)->o) (interpStm s [])) interpStm :: Stm -> Table -> (Output, Table) interpStm (CompoundStm lr) t = let (o, t') = interpStm lt in let (o', t'') = interpStm rt' in (o ++ o', t'') interpStm (PrintStm el) t = interpExpList el t interpStm (AssignStm ie) t = let (v, o, t') = interpExp et in (o, tableUpdate t' iv) interpExp :: Exp -> Table -> (Value, Output, Table) interpExp (IdExp i) t = (tableLookup ti, "", t) interpExp (NumExp v) t = (v, "", t) interpExp (EseqExp se) t = let (o, t') = interpStm st in let (v, o', t'') = interpExp et' in (v, o ++ o', t'') interpExp (OpExp l op r) t = let (v, o, t') = interpExp lt in let (v', o', t'') = interpExp rt' in (gv 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 et in (o ++ show v ++ "\n", t') interpExpList (PairExpList e el) t = let (v, o, t') = interpExp et in let (o', t'') = interpExpList el t' in (o ++ show v ++ " " ++ o', t') 

With this change, the conclusion is lazy.

You will notice that a lot of repeating form code let (value, newTable) = f oldTable in ... and a lot of repeating form code let (output, value) = exp; (moreOutput, value) = exp2 in (output ++ moreOutput, exp3) let (output, value) = exp; (moreOutput, value) = exp2 in (output ++ moreOutput, exp3) . There are a couple of monads who write this code for you! Here is an example of using the 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 iv = 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 lr) = interpStm l >> interpStm r interpStm (PrintStm el) = interpExpList el interpStm (AssignStm ie) = interpExp e >>= tableUpdate i interpExp :: Exp -> InterpreterM Value interpExp (IdExp i) = tableLookup i interpExp (NumExp v) = return v interpExp (EseqExp se) = 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 many other changes that can be proposed here, but I hope you agree that this final form is much more pleasant to read than the previous one.

Answer 2

To print the output on the fly, the interpreter functions interpStm , interpExp and interpExpList must print the output instead of saving it. You will need to convert these functions to run in the IO monad, which includes many changes, but the process is simple. Since the output is not saved, new functions will not have the Output parameter or return value.

The actual print call occurs in interpExpList . print v; return t statements print v; return t says that the value of v will be printed before any subsequent statement reads store t . For a reasonable definition of other functions, this will lead to the desired execution. If you want to more clearly indicate the requirement that "v" be printed before the next statement is executed, you can convert the code to CPS.

 interpExpList (LastExpList e) t = do (v, t) <- interpExp et print v return t -- Code for PairExpList is similar 

As a side note, ExpList is isomorphic to [Exp] minus an empty list. Consider [Exp] instead of ExpList .

Answer 3

This question has been closed for a while, but I recently solved this problem and thought that people might want to see how I solved it.

By doing this, the print statements are actually printed on the screen as soon as the list of expressions coming from it is completed:

 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 tiv = (i,v):t tableLookup :: Table -> Id -> Value tableLookup ((x,v):t) i | x == i = v tableLookup ((x,v):t) i | x /= i = tableLookup ti ------------------------------------------------------------------------------- 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 ie) t = do (v, t') <- interpExp et return $ tableUpdate t' iv 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 ti, t) interpExp (EseqExp se) t = do t' <- interpStm st interpExp et' interpExp (OpExp e1 o e2) t = do (v1, t') <- interpExp e1 t (v2, t'') <- interpExp e2 t' return (fo 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 et (s, t'') <- interpExpList es t' return $ (show v ++ " " ++ s, t'')