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. Implement the nonrecursive case first.
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 *) f x = x + 3 (* definition of f *) g y = x + y (* x is bound to 5 *) 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. 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.
You do not need to write an expression parser. It suffices if your interpreter processes an ML term representing a list of declarations/expressions.
The PLAI book has an in-depth discussion (sec. II-IV) of building an interpreter. Here's an example of an SML interpreter (with more features) from a course at Cornell. For help with ML basics see this introduction to OCaml (Scott Smith, Johns Hopkins University)