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

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.

  1. Why does eval return Either 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.

  2. What does (+) <$> eval a <*> eval b do?

    Answer

    Adds the two results and stops at the first Left

    The Either Applicative combines the values and short-circuits on Left.

  3. 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.

  4. 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.

  5. What is the value of (1+2)*3?

    Answer

    9

    The sum is 3 and the product is 9.

  6. What does this program print? ``module Main (main) where main :: IO () main = print (10 div 4 :: Int)``

    Answer

    2

    Integer division truncates, so ten over four is two.

  7. 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.

  8. 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.

  9. 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.

  10. 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

Banner image