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 =
  | 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