Assignment 2 (Functional Interpreter)

Due Date: April 10, 2000 before class

Here is the abstract syntax of the language to be interpreted specified as a collection of ML datatypes. For your convenience, I have included several examples of programs in that language, written in abstract syntax, that you can directly evaluate. If you want to test your interpreter on more examples, you will have to write in abstract syntax yourself, or write a parser. We will explain the informal semantics of the constructs in class. But you can also find this information in the EOPL book.

datatype prim = Plus | Min | Div | Mul | And | Or | Not | Eq

datatype exp = 
    Num of int
  | Bool of bool
  | Var of string
  | Prim of prim
  | Fun of string list * exp
  | App of exp * exp list
  | Cond of exp * exp * exp 
  | Let of (string * exp) list * exp
  | Ref of exp
  | Deref of exp
  | Assign of exp * exp 
  | Letrec of (string * exp) list * exp

val e1 = Num 3

val e2 = Prim Plus

val e3 = Bool true

val e4 = Cond (Cond (Bool true, 
                     Bool false, 
                     Bool true), 
               Num 33, 
               Num 99)

val e5 = App (Prim Plus, 
              [Num 2, 
               App (Prim Mul, [Num 4, Num 2])])

val e6 = App (Prim Eq, [Num 4, Num 5])

val e7 = Cond (App (Prim Eq, [Num 4, Num 5]), 
               App (Prim Plus, [Num 2, Num 1]), 
               App (Prim Min, [Num 2, Num 1]))

val e8 = Let ([("x", Ref (Num 3))],
              Let ([("f", Fun ([], Deref (Var "x"))),
                    ("g", Fun ([], Assign (Var "x", Num 10)))],
                   Let ([("d", App (Var "g", []))],
                        App (Var "f", []))))

val e9 = Letrec ([("fact", 
                   Fun (["n"],
                        Cond (App (Prim Eq, [Var "n", Num 0]),
                              Num 1, 
                              App (Prim Mul,
                                   [Var "n", 
                                    App (Var "fact",
                                         [App (Prim Min, 
                                               [Var "n", Num 1])])]))))],
                 App (Var "fact", [Num 5]))