Capstone B: the syntax tree
The syntax tree as a value
The tree of the previous lesson is an ordinary data type, and a
data Expr
= Num Int
| Add Expr Expr
| Sub Expr Expr
| Mul Expr Expr
| Div Expr Expr
instance Show Expr where
show (Num n) = show n
show (Add a b) = "(" ++ show a ++ " + " ++ show b ++ ")"
show (Sub a b) = "(" ++ show a ++ " - " ++ show b ++ ")"
show (Mul a b) = "(" ++ show a ++ " * " ++ show b ++ ")"
show (Div a b) = "(" ++ show a ++ " / " ++ show b ++ ")"
Every operation is parenthesised, which is more brackets than a reader needs and exactly what a parser can read back without precedence questions.
The program
module Main (main) where
data Expr
= Num Int
| Add Expr Expr
| Sub Expr Expr
| Mul Expr Expr
| Div Expr Expr
instance Show Expr where
show (Num n) = show n
show (Add a b) = "(" ++ show a ++ " + " ++ show b ++ ")"
show (Sub a b) = "(" ++ show a ++ " - " ++ show b ++ ")"
show (Mul a b) = "(" ++ show a ++ " * " ++ show b ++ ")"
show (Div a b) = "(" ++ show a ++ " / " ++ show b ++ ")"
size :: Expr -> Int
size (Num _) = 1
size (Add a b) = 1 + size a + size b
size (Sub a b) = 1 + size a + size b
size (Mul a b) = 1 + size a + size b
size (Div a b) = 1 + size a + size b
sample :: Expr
sample = Add (Num 1) (Mul (Num 2) (Num 3))
main :: IO ()
main = do
print sample
print (size sample)
print (Sub (Num 10) (Div (Num 8) (Num 2)))
ghc -Wall -O1 -o ast ast.hs
./ast
(1 + (2 * 3))
5
(10 - (8 / 2))
Why a Show of your own
- The derived Add (Num 1) (Mul (Num 2) (Num 3)), which is the constructors and not the language.
- The parenthesised form is unambiguous, so it can be parsed back without a precedence table.
-
The next lesson evaluates the tree and returns an error for a division by
zero, which is the first place the capstone has to say no.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Why write a Show instance for Expr?
Answer
The derived one prints constructors, not an expression
The instance prints the language the tree represents.
-
Why are all operations parenthesised?
Answer
The printed form is unambiguous and parses back
Brackets remove every question about which side binds first.
-
What does
size (Num 4)return?Answer
1
One constructor is one node.
-
What does this program print?
module Main (main) where main :: IO () main = print (show (1 + 2 :: Int) ++ "!")Answer
3!
show 3 is the string 3 and the exclamation is appended.
-
What does
size (Add (Num 1) (Num 2))return?Answer
3
One node for the addition and one for each number.
-
What does this program print?
module Main (main) where main :: IO () main = print (length "(1 + 2)")Answer
7
The string has seven characters including spaces and brackets.
-
What is the difference between the tree and its printed form?
Answer
The tree is a value the program walks, the string is for a reader or a parser
The evaluator walks the tree and the parser produces one from text.
-
What does this program print?
module Main (main) where main :: IO () main = putStrLn (show (2 * 3 :: Int))Answer
6
putStrLn prints the shown number without quotes.
-
Why does the lesson count the constructors?
Answer
It is the first recursion over the tree and the model for eval
A recursion that returns a number is the simplest shape before the evaluator.
-
What does this program print?
module Main (main) where main :: IO () main = print (null [])Answer
True
The empty list is null.
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
-