# CSCI 312 Assignment #3

## 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``