## Assignment #3: A Programming Language with Loops and Variables

(Modified from Prof. Greenberg’s Homework #3).

In this homework we’ll be experimenting with our first interpreter for a true programming language. We’ll need two concepts throughout: variable names (which will just be strings) and stores (a/k/a heaps, where we keep the contents of the variables of our language). All of our variables will store integers.

```
type VarName = String
type Store = Map VarName Int
```

Here is a new version of the `ArithExp`

datatype from our previous assignment, augmented to support variables:

```
data ArithExp =
Var VarName
| Num Int
| Plus ArithExp ArithExp
| Times ArithExp ArithExp
| Neg ArithExp
deriving (Show, Eq, Ord)
```

Write an interpreter for these arithmetic expressions. When evaluating variables, you should return 0 if they’re not in the store (such variables are called *unbound* or *undefined*). Because

`evalA :: Store -> ArithExp -> Int`

`evalA _ _ = undefined`

We can define boolean expressions similarly. Rather than concretely specifying which arithmetic expressions they’re defined over, we just take in a parameter.

```
data BoolExp a =
Bool Bool
| Equal a a
| Lt a a
| Not (BoolExp a)
| Or (BoolExp a) (BoolExp a)
| And (BoolExp a) (BoolExp a)
deriving (Show, Eq, Ord)
```

Write an interpreter for boolean expressions over our prior arithmetic expressions.

`evalB :: Store -> BoolExp ArithExp -> Bool`

`evalB _ _ = undefined`

Finally, we’ll define a simple programming language supporting the familiar features of sequencing, conditionals, and loops. Its abstract syntax tree (AST) takes two type parameters: one identifying the arithmetic expressions we’ll use, one identifying the boolean expressions we’ll use.

```
data Stmt a b =
Skip
| Assign VarName a
| Seq (Stmt a b) (Stmt a b)
| If (b a) (Stmt a b) (Stmt a b)
| While (b a) (Stmt a b)
deriving (Show, Eq, Ord)
```

Write an interpreter for this language.

`eval :: Store -> Stmt ArithExp BoolExp -> Store`

`eval _ _ = undefined`