Advanced Methods in Programming Languages (201-2-4411-01)
HW Assignment 4 - Fall 1996 - Michael Elhadad

Interpreters

Problems for Sun 29/12

For all the questions, the following BNF is to be used: 
<exp>         ::= <varref>                  varref (var)
               |  <number>                  lit (datum)
               |  (if <exp> <exp> <exp>)    if (test-exp then-exp else-exp)
               |  (proc ({<var>}*) <exp>)   proc (formals body)
               |  (<exp> {<exp>}*)          app (rator rands)
               |  (:= <var> <exp>)          varassign (var exp)
               |  (begin {<exp>}+)          begin (exps)
               |  (let <decls> <exp>)       let (decls body)
               |  (letrec <decls> <exp>)    letrec (decls body)
<decls> ::= ({<decl>}*)
<decl>  ::= (<var> <exp>)                   decl (var exp)
A parser/unparser for this BNF is provided in this file.

letmutable

Allow both mutable and immutable variable bindings in the interpreter: 
Denoted value = Cell(Expressed Value) + Expressed Value
Add the following clause to the BNF: 
<exp> ::= (letmutable <decls> <exp>)    letmutable (decls body)
Modify the parser and eval-exp procedure to account for letmutable.

Constant Optimization

Local variable binding need be mutable only if there is an assignment expression to the variable somewhere within its scope. Process the output of the parser to identify when each binding needs to be mutable and when it can be immutable, and modify the interpreter so that only bindings for variables that might change their values are mutable, while all the other bindings remain immutable.

Interpreter with Explicit Store

Write an interpreter with an explicit model of the store, that does not use assignment in the meta-language. Be sure to define your store-ADT appropriately, and include a new definition of the cell-ADT as needed.
Last modified Dec 15th, 1996 Michael Elhadad