Haskell Project Small Interpreter
An interpreter is a program that runs another small language. This interpreter evaluates arithmetic expressions with variables, using only base libraries.
Literals and arithmetic evaluate to a number
The expression adds 2 to 3 times 4. Multiplication is evaluated before the addition.
data Expr = Lit Int | Add Expr Expr | Mul Expr Expr | Var String
eval :: [(String, Int)] -> Expr -> Maybe Int
eval _ (Lit n) = Just n
eval env (Add x y) = (+) <$> eval env x <*> eval env y
eval env (Mul x y) = (*) <$> eval env x <*> eval env y
eval env (Var name) = lookup name env
main :: IO ()
main = print (eval [] (Add (Lit 2) (Mul (Lit 3) (Lit 4))))Variables are looked up in the environment
The first lookup finds x with value 7. The second lookup runs in an empty environment, so it fails.
data Expr = Lit Int | Add Expr Expr | Mul Expr Expr | Var String
eval :: [(String, Int)] -> Expr -> Maybe Int
eval _ (Lit n) = Just n
eval env (Add x y) = (+) <$> eval env x <*> eval env y
eval env (Mul x y) = (*) <$> eval env x <*> eval env y
eval env (Var name) = lookup name env
main :: IO ()
main = do
print (eval [("x", 7)] (Add (Var "x") (Lit 1)))
print (eval [] (Var "x"))A list of expressions maps to a list of results
Each expression is evaluated with x set to 3. The unknown variable gives Nothing in the last position.
data Expr = Lit Int | Add Expr Expr | Mul Expr Expr | Var String
eval :: [(String, Int)] -> Expr -> Maybe Int
eval _ (Lit n) = Just n
eval env (Add x y) = (+) <$> eval env x <*> eval env y
eval env (Mul x y) = (*) <$> eval env x <*> eval env y
eval env (Var name) = lookup name env
main :: IO ()
main = print (map (eval [("x", 3)]) [Lit 5, Add (Var "x") (Lit 6), Var "y"])Example
data Expr = Lit Int | Add Expr Expr | Mul Expr Expr | Var String | Let String Expr Expr
eval :: [(String, Int)] -> Expr -> Maybe Int
eval _ (Lit n) = Just n
eval env (Add x y) = (+) <$> eval env x <*> eval env y
eval env (Mul x y) = (*) <$> eval env x <*> eval env y
eval env (Var name) = lookup name env
eval env (Let name value body) = case eval env value of
Just v -> eval ((name, v) : env) body
Nothing -> Nothing
main :: IO ()
main = do
print (eval [] (Let "x" (Lit 6) (Mul (Var "x") (Lit 7))))
print (eval [] (Let "x" (Lit 4) (Let "y" (Lit 5) (Add (Var "x") (Var "y")))))Key points
- Interpreter: a program that runs another small language.
- Expression: a tree built from literals, arithmetic, and variables.
- Environment: a list of name and value pairs used to look up variables.
- Literal: a plain number written directly in the expression.
- Evaluation: walking the expression tree and computing its value.
In this example, the program first evaluates a let that binds x to 6 and multiplies it by 7, then evaluates nested lets that bind x to 4 and y to 5 and add them.
Note
a missing variable gives Nothing instead of crashing, because lookup may fail.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Haskell Playground
Exercise
What does eval [] (Var "x") return in this interpreter?