Write, preferably in a functional language like ML, an interpreter for the a language with the following syntax:
Prog ::= Def* Expr Def ::= id id* = Expr Expr ::= int | id | Expr '+' Expr | Expr '*' Expr | id Expr* | if Expr then Expr else ExprA program is a sequence of definitions followed by an expression evaluation. A definition binds an identifier (optionally followed by parameters, in the case of functions) to an expression. An expression is an integer, an arithmetic expression (sum or product), a previously defined identifier, a function application (identifier followed by argument expressions) or a conditional expression (the 'then' branch is taken if the condition is nonzero). Function definitions may be recursive.
For an alternate (possibly simpler) definition, you may consider functions with only one argument. The simplifications to the grammar are then: Def ::= id = Expr | id = 'fun' id Expr. Scoping is assumed to be static, i.e. the definition of an identifier is determined syntactically. It extends to the end of the program, or its next redefinition; a function declaration creates an inner scope for its parameters. Examples:
x = 5 (* definition *) x (* evaluation, 5) f x = x + 3 (* definition of f *) f 4 (* 7, argument is 4; x = 5 in outer scope*) x (* evaluation, 5 as before *) g y = x + y (* x is bound to 5 *) g 1 (* 6 *) x = 3 (* redefinition *) g 3 (* 8, x was bound to 5 at the definition of g *)You will need to evaluate expressions in the appropriate environment, i.e. retain for each expression the environment that defines its free variables (for functions, this is called a closure). Note that when evaluating a function in environment env you must evaluate its argument(s) in env but evaluate the function body (specifically, its free variables) in the environment of the function definition. The PLAI book has an in-depth discussion (sec. II-IV) of building an interpreter. Here's an example of an ML interpreter (with more features) from a course at Cornell.