Capstone B: testing the evaluator

Testing the pipeline

The last step of the capstone tests the parser and the evaluator together: a table of an expression and the value it must give, a check that prints one line per case, and an exit status that a build tool reads. The cases cover precedence, grouping, a division and the two error paths.

run :: String -> Either String Int run input = parseAll input >>= eval cases = [ ("1+2*3", Right 7) , ("(1+2)*3", Right 9) , ("1/0", Left "division by zero") ]

run is the whole pipeline as one function, so the test does not have to know that a lexer and a parser exist. That is the value of a capstone: the parts are testable through the one function a user calls.

The program

module Main (main) where import Data.Char (isDigit) import System.Exit (exitFailure, exitSuccess) 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) run :: String -> Either String Int run input = parseAll input >>= eval check :: (String, Either String Int) -> IO Bool check (input, expected) = let actual = run input in do putStrLn ((if actual == expected then "ok " else "FAIL ") ++ input) pure (actual == expected) main :: IO () main = do results <- mapM check [ ("1+2*3", Right 7) , ("(1+2)*3", Right 9) , ("10/2", Right 5) , ("1/0", Left "division by zero") , ("1+", Left "unexpected end of input") ] if and results then exitSuccess else exitFailure

ghc -Wall -O1 -o tests tests.hs
./tests
echo "status: $?"

ok 1+2*3
ok (1+2)*3
ok 10/2
ok 1/0
ok 1+
status: 0

What the table proves

The next lesson extends the language with variables, which is the change the table makes cheap: one more case and one more row.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does run input = parseAll input >>= eval do?

    Answer

    Parses and evaluates in one step, carrying the error

    The bind of Either stops at the first Left of the two stages.

  2. Why does the table test precedence and grouping separately?

    Answer

    They give different values for the same numbers

    The two rows are the check that the parser groups the operations.

  3. What does a passing run exit with?

    Answer

    0

    exitSuccess leaves status 0 for the build tool.

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

  5. Which case covers the division by zero?

    Answer

    1/0 with a Left

    The evaluator returns the Left for the zero divisor.

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

    Answer

    5

    Ten divided by two is five.

  7. Why is the pipeline tested through one function?

    Answer

    The user calls one function, so the test should too

    run is the interface, and the table pins its behaviour.

  8. What does this program print? module Main (main) where main :: IO () main = print ((1 + 2) * 3 :: Int)

    Answer

    9

    The sum is 3 and the product is 9.

  9. What makes an extension cheap with this table?

    Answer

    One more case and one more row

    The table documents the behaviour and grows with the language.

  10. What does this program print? module Main (main) where main :: IO () main = print (null [1 :: Int])

    Answer

    False

    The list has an element.

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