I'll deviate a bit from your given code and indicate how you might start to write a monadic interpreter which encodes the evaluation semantics for an toy imperative language, much like the one you specified. You'll need a frontend AST like you have:
import Control.Monad.State
import qualified Data.Map as Map
data Expr = Var Var
| App Expr Expr
| Fun Var Expr
| Lit Ground
| If Expr Expr Expr
-- Fill in the rest
deriving (Show, Eq, Ord)
data Ground = LInt Integer
| LBool Bool
deriving (Show, Eq, Ord)
We will evaluate via a function eval
into concrete Value
types.
data Value = VInt Integer
| VBool Bool
| VUnit
| VAddress Int
| VClosure String Expr TermEnv
type TermEnv = Map.Map String Value
type Memory = [Value]
type Interpreter t = State Memory t
eval :: TermEnv -> Expr -> State Memory Value
eval _ (Lit (LInt k)) = return $ VInt k
eval _ (Lit (LBool k)) = return $ VBool k
eval env (Fun x body) = return (VClosure x body env)
eval env (App fun arg) = do
VClosure x body clo <- eval env fun
res <- eval env fun
args <- eval env arg
let nenv = Map.insert x args clo
eval nenv body
eval env (Var x) = case (Map.lookup x env) of
Just v -> return v
Nothing -> error "prevent this statically!"
eval env (If cond tr fl) = do
VBool br <- eval env cond
if br == True
then eval env tr
else eval env fl
-- Finish with the rest of your syntax.
programs will return the resulting state after the program executes
To run the interpreter we need to feed it two values: the binding environment of variables and the values on the heap. This will return a tuple of the resulting value and the memory state which you can then feed back to the function itself if building a REPL-like loop.
runInterpreter :: TermEnv -> Memory -> Expr -> (Value, [Value])
runInterpreter env mem x = runState (eval env x) mem
initMem = []
initTermEnv = Map.empty
Since you're writing an imperative language likely you'll want to add state and references, so you can create new AST nodes working allocating and mutating Refs
. Left for you to do is to add the logic for allocating an Array
as a sequence of Ref
s and using pointer arithmetic when indexing and assigning into it.
data Expr = -- Same as above
| Ref Expr
| Access Expr
| Assign Expr Expr
eval :: TermEnv -> Expr -> State Memory Value
...
eval env (Ref e) = do
ev <- eval env e
alloc ev
eval env (Access a) = do
VAddress i <- eval env a
readAddr i
eval env (Assign a e) = do
VAddress i <- eval env a
ev <- eval env e
updateAddr ev i
With this we'll need some helper functions for dealing with the values on the heap which are just thin wrappers around the State monad functions.
access :: Int -> Memory -> Value
access i mem = mem !! i
update :: Int -> Value -> Memory -> Memory
update addr val mem = a ++ [val] ++ b
where
(a, _:b) = splitAt addr mem
alloc :: Value -> Interpreter Value
alloc val = do
mem <- get
put $ mem ++ [val]
return $ VAddress (length mem)
readAddr :: Int -> Interpreter Value
readAddr i = do
mem <- get
return $ access i mem
updateAddr :: Value -> Int -> Interpreter Value
updateAddr val i = do
mem <- get
put $ update i val mem
return VUnit
Hope that helps get you started.