> {-# LANGUAGE GADTs #-}
Module 05: The Arith language: pretty-printing
Write your team names here:
You may again choose whoever you want to start as the driver. Write your choice here:
Arith syntax and semantics
The Arith language is represented by the following abstract syntax:
> data Arith1 where
> Lit1 :: Integer -> Arith1
> Add :: Arith1 -> Arith1 -> Arith1
> Sub :: Arith1 -> Arith1 -> Arith1
> Mul :: Arith1 -> Arith1 -> Arith1
> deriving (Show)
>
> arithExample :: Arith1
> arithExample = Add (Mul (Lit1 4) (Lit1 5)) (Lit1 2)
(We are using the name Arith1
to avoid a name clash, since later we will use a more refined version called Arith
.) The semantics of an Arith expression is an integer: Lit1
values represent themselves, Add
represents addition, Sub
subtraction, and Mul
multiplication. For example, arithExample
evaluates to \((4 \times 5) + 2 = 22\).
- Write an interpreter called
interpArith1
forArith1
expressions.
As concrete syntax for Arith, we use standard mathematical notation and standard conventions about operator precedence. For example, "4*5+2"
is concrete syntax for arithExample
. Notice that it does not represent Mul (Lit1 4) (Add (Lit1 5) (Lit1 2))
(which evaluates to 28), since by convention multiplication has higher precedence than addition. If we wanted the latter Arith1
value, we would have to write "4*(5+2)"
.
Write a pretty-printer
prettyArith1
which turns Arith abstract syntax into valid concrete syntax. At this point, you should try to make your pretty-printer as simple as possible rather than try to produce the best output possible. (Hint: something like"((4*5)+2)"
is just as valid concrete syntax as"4*5+2"
, even though it has unnecessary parentheses.)How might you go about altering your pretty printer to omit needless parentheses? Write down some ideas here.
Class discussion: precedence
![](../images/stop.gif)
A better pretty-printer
- ROTATE ROLES and write the name of the new driver here:
> data Op where
> Plus :: Op
> Minus :: Op
> Times :: Op
> deriving (Show, Eq)
>
> data Arith where
> Lit :: Integer -> Arith
> Bin :: Op -> Arith -> Arith -> Arith
> deriving (Show)
>
> data Associativity where
> L :: Associativity
> R :: Associativity
> deriving (Show, Eq)
>
> type Precedence = Int
First, write an interpreter
interpArith
forArith
expressions.Write functions
assoc :: Op -> Associativity
andprec :: Op -> Precedence
to return the associativity and precedence of each operator. Addition, multiplication, and subtraction are all left-associative by convention. Addition and subtraction should have the same precedence level, with multiplication at a higher level (typically larger numbers represent higher precedence).Now write a function
prettyPrec :: Precedence -> Associativity -> Arith -> String
. Given the precedence level of the parent operator and whether the current expression is a left or right child, it should print out a properly parenthesized version of the expression, with parentheses surrounding the entire expression only if they are needed.Finally, write a function
prettyArith :: Arith -> String
which works by callingprettyPrec
with appropriate starting arguments.