{-# LANGUAGE GADTSyntax #-}
Write your team names here:
You may again choose whoever you want to start as the driver. Write your choice here:
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) arithExample2 :: Arith1 arithExample2 = Mul (Lit1 4) (Add (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 × 5) + 2 = 22, and arithExample2 evaluates to 4 × (5 + 2) = 28.
Arith1
Arith
Lit1
Add
Sub
Mul
arithExample
arithExample2
interpArith1
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, since by convention multiplication has higher precedence than addition. If we want concrete syntax to represent arithExample2, we have to use parentheses: "4*(5+2)".
"4*5+2"
"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.)
prettyArith1
"((4*5)+2)"
How might you go about altering your pretty printer to omit needless parentheses? Write down some ideas here.
If you have time and desire, you can try starting on this section. However, we will go over some things in class on Friday which will help a lot, so feel free to wait.
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 -- 4 * (5 + 2) expr1 :: Arith expr1 = Bin Times (Lit 4) (Bin Plus (Lit 5) (Lit 2)) -- 44 - 7 * (1 + 2) - 3 expr2 :: Arith expr2 = Bin Minus (Lit 44) (Bin Minus (Bin Times (Lit 7) (Bin Plus (Lit 1) (Lit 2))) (Lit 3))
First, write an interpreter interpArith for Arith expressions.
interpArith
Write functions assoc :: Op -> Associativity and prec :: 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, that is, ``stickier glue’’).
assoc :: Op -> Associativity
prec :: Op -> 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. Remember that parentheses are needed when (and only when):
prettyPrec :: Precedence -> Associativity -> Arith -> String
Write a function prettyArith :: Arith -> String which works by calling prettyPrec with appropriate starting arguments.
prettyArith :: Arith -> String
prettyPrec
Now go back and add an exponentiation operator to the language. Exponentiation is right-associative and has higher precedence than multiplication. Be sure to update both the interpreter and pretty-printer appropriately.