Capstone B: adding a feature

Adding a feature

The extension of the capstone is a variable: an identifier is a token, a name is a node of the tree, and the evaluator looks it up in an environment. The table of the previous lesson grows by one row per case, and the change is visible in three places: the lexer, the tree and the evaluator.

data Token = TNum Int | TIdent String | TPlus | TStar | TLParen | TRParen | TBad Char data Expr = Num Int | Var String | Add Expr Expr | Mul Expr Expr type Env = Map.Map String Int eval env (Var name) = case Map.lookup name env of Nothing -> Left ("unknown variable " ++ name) Just value -> Right value

An unknown name is a Left like a division by zero, so the REPL of the previous lesson would keep running. The environment is a parameter of eval and not a global, which is the same decision the Reader lesson made for a configuration.

The program

module Main (main) where import Data.Char (isAlpha, isDigit) import qualified Data.Map.Strict as Map data Token = TNum Int | TIdent String | TPlus | TStar | TLParen | TRParen | TBad Char 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 | isAlpha c = let (name, rest) = span isAlpha (c : cs) in TIdent name : lexer rest | otherwise = TBad c : lexer cs where symbol '+' = TPlus symbol '*' = TStar symbol '(' = TLParen symbol ')' = TRParen symbol other = TBad other data Expr = Num Int | Var String | Add Expr Expr | Mul Expr Expr deriving (Show, Eq) 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 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 rest = Right (left, rest) parseFactor :: [Token] -> Either String (Expr, [Token]) parseFactor (TNum n : rest) = Right (Num n, rest) parseFactor (TIdent name : rest) = Right (Var name, 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" type Env = Map.Map String Int eval :: Env -> Expr -> Either String Int eval _ (Num n) = Right n eval env (Var name) = case Map.lookup name env of Nothing -> Left ("unknown variable " ++ name) Just value -> Right value eval env (Add a b) = (+) <$> eval env a <*> eval env b eval env (Mul a b) = (*) <$> eval env a <*> eval env b run :: Env -> String -> Either String Int run env input = parseAll input >>= eval env main :: IO () main = do let env = Map.fromList [("x", 3), ("y", 4)] print (run env "x + y * 2") print (run env "x * (y + 1)") print (run env "x + z")

ghc -Wall -O1 -o vars vars.hs
./vars

Right 11
Right 15
Left "unknown variable z"

Reading the output

This is the end of Capstone B and of the lessons written so far: the third capstone, a concurrent job runner, and the three article groups come in the later rounds.

Questions

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

  1. What does the extension add to the tree?

    Answer

    A Var node that names a variable

    Var is one more constructor and the evaluator has one more equation.

  2. Where does the environment live?

    Answer

    As an argument of eval

    A parameter keeps eval pure and testable, like the Reader lesson.

  3. What does an unknown variable give?

    Answer

    A Left that names it

    The lookup returns Nothing and eval turns it into the message.

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

    Answer

    11

    The product is 8 and the sum is 11.

  5. Which token type holds a name?

    Answer

    TIdent String

    The identifier branch of the lexer produces TIdent with its text.

  6. What does this program print? module Main (main) where main :: IO () main = print (14 :: Int)

    Answer

    14

    The number is printed as it is.

  7. How many places change for the feature?

    Answer

    The lexer, the tree and the evaluator

    A token, a constructor and an equation, which the lesson lists.

  8. What does this program print? module Main (main) where import qualified Data.Map.Strict as Map main :: IO () main = print (Map.lookup "x" (Map.fromList [("x", 1 :: Int)]))

    Answer

    Just 1

    The key is present and lookup returns its value in Just.

  9. Why is the unknown name not a parse error?

    Answer

    The grammar accepts a name; only the evaluation knows the environment

    The syntax is right and the meaning is what fails.

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

    Answer

    14

    The sum is 7 and the product is 14.

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