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
- x + y * 2 with x = 3 and y = 4 is 11, and the precedence of the parser is what makes it 11 and not 14.
- The parentheses give 15, which is the same tree rule again.
- Left that names it.
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.
-
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.
-
Where does the environment live?
Answer
As an argument of eval
A parameter keeps eval pure and testable, like the Reader lesson.
-
What does an unknown variable give?
Answer
A Left that names it
The lookup returns Nothing and eval turns it into the message.
-
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.
-
Which token type holds a name?
Answer
TIdent StringThe identifier branch of the lexer produces TIdent with its text.
-
What does this program print?
module Main (main) where main :: IO () main = print (14 :: Int)Answer
14
The number is printed as it is.
-
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.
-
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.
-
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.
-
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