Capstone B: evaluation
Evaluation and the error in the type
The evaluator walks the tree and returns Either String Int: the arithmetic cannot fail, and the division can. A failure is a Left with a message, so the caller decides whether to print it, exit or continue, which is what the REPL of two lessons later does.
eval :: Expr -> Either String Int
eval (Num n) = Right n
eval (Add a b) = (+) <$> eval a <*> eval b
eval (Div a b) = do
x <- eval a
y <- eval b
if y == 0 then Left "division by zero" else Right (x `div` y)
The <*> of the Applicative lesson combine two results and stop at the first Left, and the do block is the same short circuit for the division, where the second operand has to be checked before the operator can run.
The program
module Main (main) where
import Data.Char (isDigit)
data Token
= TNum Int
| TPlus
| TMinus
| TStar
| TSlash
| TLParen
| TRParen
deriving (Show, Eq)
data Expr
= Num Int
| Add Expr Expr
| Sub Expr Expr
| Mul Expr Expr
| Div Expr Expr
deriving (Show, Eq)
lexer :: String -> [Token]
lexer [] = []
lexer (c : cs)
| c == ' ' = lexer cs
| c `elem` "+-*/()" = symbol c : lexer cs
| isDigit c =
let (digits, rest) = span isDigit (c : cs)
in TNum (read digits) : lexer rest
| otherwise = error ("bad character: " ++ [c])
where
symbol '+' = TPlus
symbol '-' = TMinus
symbol '*' = TStar
symbol '/' = TSlash
symbol '(' = TLParen
symbol ')' = TRParen
symbol other = error ("bad symbol: " ++ [other])
parseExpr :: [Token] -> Either String (Expr, [Token])
parseExpr tokens = do
(left, rest) <- parseTerm tokens
restExpr left rest
where
restExpr left (TPlus : rest) = do
(right, rest') <- parseTerm rest
restExpr (Add left right) rest'
restExpr left (TMinus : rest) = do
(right, rest') <- parseTerm rest
restExpr (Sub left right) rest'
restExpr left rest = Right (left, rest)
parseTerm :: [Token] -> Either String (Expr, [Token])
parseTerm tokens = do
(left, rest) <- parseFactor tokens
restTerm left rest
where
restTerm left (TStar : rest) = do
(right, rest') <- parseFactor rest
restTerm (Mul left right) rest'
restTerm left (TSlash : rest) = do
(right, rest') <- parseFactor rest
restTerm (Div left right) rest'
restTerm left rest = Right (left, rest)
parseFactor :: [Token] -> Either String (Expr, [Token])
parseFactor (TNum n : rest) = Right (Num n, rest)
parseFactor (TLParen : rest) = do
(expr, rest') <- parseExpr rest
case rest' of
TRParen : rest'' -> Right (expr, rest'')
_ -> Left "expected )"
parseFactor [] = Left "unexpected end of input"
parseFactor (token : _) = Left ("unexpected token " ++ show token)
parseAll :: String -> Either String Expr
parseAll input = do
(expr, rest) <- parseExpr (lexer input)
case rest of
[] -> Right expr
_ -> Left "unexpected input after the expression"
eval :: Expr -> Either String Int
eval (Num n) = Right n
eval (Add a b) = (+) <$> eval a <*> eval b
eval (Sub a b) = (-) <$> eval a <*> eval b
eval (Mul a b) = (*) <$> eval a <*> eval b
eval (Div a b) = do
x <- eval a
y <- eval b
if y == 0 then Left "division by zero" else Right (x `div` y)
main :: IO ()
main = do
print (parseAll "1+2*3" >>= eval)
print (parseAll "(1+2)*3" >>= eval)
print (parseAll "8/2" >>= eval)
print (parseAll "1/0" >>= eval)
ghc -Wall -O1 -o eval eval.hs
./eval
Right 7
Right 9
Right 4
Left "division by zero"
Reading the four lines
- Left and not an exception: the program continues, and a caller could print the error and read the next line.
The next lesson turns the messages into errors a user can read, with the position of the problem and an exit status for a script.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Why does
evalreturnEither String Int?Answer
The division can fail and the failure is in the type
Either carries the message of a failure the caller must handle.
-
What does
(+) <$> eval a <*> eval bdo?Answer
Adds the two results and stops at the first Left
The Either Applicative combines the values and short-circuits on Left.
-
What does
eval (Div (Num 1) (Num 0))return?Answer
Left "division by zero"
The divisor is checked before the division and the result is a Left.
-
What does this program print?
module Main (main) where main :: IO () main = print (2 * 3 + 4 :: Int)Answer
10
The product is 6 and the sum is 10.
-
What is the value of
(1+2)*3?Answer
9
The sum is 3 and the product is 9.
-
What does this program print? ``
module Main (main) where main :: IO () main = print (10div4 :: Int)``Answer
2
Integer division truncates, so ten over four is two.
-
Why does the evaluator not throw on a division by zero?
Answer
The failure is a value the caller can report and continue from
The Either keeps the REPL alive after one bad expression.
-
What does this program print?
module Main (main) where main :: IO () main = print (length [1, 2, 3, 4 :: Int])Answer
4
The list has four elements.
-
What does the do block in the division return when the divisor is zero?
Answer
The Left from the if branch
The branch returns Left and the do block propagates it.
-
What does this program print?
module Main (main) where main :: IO () main = print (1 + 2 * 3 :: Int)Answer
7
The product is 6 and the sum is 7.
The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev