Hackification.com

In the last three articles I covered the overall structure, lexer, and parser of a simple expression evaluator. This articles concludes by presenting the evaluator and main loop.

At this stage we are able to take a string, tokenize it, and then build a tree representing the expression. We now need to be able to reduce the tree down to a single value (or error).

Expression Reduction

reduce :: (MonadError ExprError m) => ExpressionTree -> m Int

We’re returning an Int, but as before, the context for this return value is an error state.

The reducer is a really simple recursive function. Leaf values in the tree (numbers) are their own value:

reduce (Node (NNumber _ v) _)
    = return v

Operator nodes recursively reduce their left and right child nodes, then apply the operator:

reduce (Node (NOperator p _ op) (lhs:rhs:[]))
    = do x <- reduce lhs
         y <- reduce rhs
         case op x y of
             Right v -> return v
             Left m  -> throwError $ ExprErrorAt m p

At this point we’re “collapsing” the error context. Previously we just defined it as any type that satisfied the ‘MonadError‘ interface. In this function, we force it to be the ‘Either‘ type by expecting the return value to be either ‘Right‘ (success) or ‘Left‘ (failure). Type inference sorts everything out nicely here.

Main Loop

Everything I’ve presented here has been ‘pure’ – free of side effects. That’s all well and good, and it lets us reason about the program, but ultimately we have to deal with the computer and the user, and that’s all about side-effects. The main function is the only bit of impure code in this whole example:

main = interact $ unlines . map (unlines . formatResult) . lines

The period operator is the function composition operator, so we read from right to left.

In other words: convert the input to a list of lines, process each one through ‘formatResult‘ (our function), concatenate our multi-line output, and concatenate again to produce a single string for output. The standard function ‘interact‘ handles all the messy business of reading and writing from the console streams.

Examples

2 + 3 * 4
14

(12+34)*(56+78)
6164

123 / (4 - 4)
** Error in expression:
**   123 / (4 - 4)
**       ^
** Reason: division by zero

123 +
** Error in expression:
**   123 +
**        ^
** Reason: expected a value