> {-# LANGUAGE GADTs #-}

Module 05: The Arith language: pretty-printing

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\).

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)".

Class discussion: precedence

A better pretty-printer

> 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