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
- Precedence and grouping are both right, because the two expressions of the same numbers give different values.
- A division by zero is a Left and not a crash.
- A truncated expression is a Left, so the error path is tested too.
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.
-
What does
run input = parseAll input >>= evaldo?Answer
Parses and evaluates in one step, carrying the error
The bind of Either stops at the first Left of the two stages.
-
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.
-
What does a passing run exit with?
Answer
0
exitSuccess leaves status 0 for the build tool.
-
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.
-
Which case covers the division by zero?
Answer
1/0with a LeftThe evaluator returns the Left for the zero divisor.
-
What does this program print? ``
module Main (main) where main :: IO () main = print (10div2 :: Int)``Answer
5
Ten divided by two is five.
-
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.
-
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.
-
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.
-
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