CSE 340 HW 3
Due Monday, Feb 23th

Environment-based interpreters, Dynamic binding and Recursive functions

Added 2/20/2004: Having trouble with the Makefile on unix machines? Try this version.

Added 2/16/2004:  A new version of eoplLexer.mll that corrects the 0 problem.

The archive hw3.tar contains the ML implementation of an
environment-based interpreter, similar to that defined in Sections
3.1-3.6 of EOPL.

The concrete language is not Mini-Scheme, but a variant with fewer
parentheses. However, each parenthesis in this language is significant so you will
have to be very careful when you design examples for testing. The BNF
for this language is scattered through out  chapter 3, so I've reprinted it
below. In the notation below, "{<exp>}," is any number of expressions
separated by commas ( {<var>}, is a  similar notation for variables).

prim ::= + | - | * | add1 | sub1 | and | or | not

exp ::= <number>
        | <var>
        | <prim> ( {<exp>}, )
        | if <exp> then <exp> else <exp>
        | let { <var> = <exp> } in <exp>
        | proc ( {<var>}, ) <exp>
        | ( <exp> {<exp>} )

The following problems ask you to make five changes to the program in
eval.ml. When you test your program, you probably do not want to make
all five changes at once. However, you should submit a modified version
of eval.ml with all of the changes made,  each change marked in the comments. You
should not need to change any other file in the assignment.

1. Modify eval.ml to extend the evaluator with the following new primitives. These
   primitives have already been added to the concrete and abstract
   syntax.
    

   Concrete Syntax	Abstract Syntax	Description
   zero?	Zero	Tests if number is zero
   <	LT	Tests if one number is less than another
   >	GT	Tests if one number is greater than another
   =	Equal	Test if two numbers are equal

   
   

2. EOPL 3.14 Booleans
   
   Currently the interpreter uses the number 0 to represent false and any
   other value to represent true. This is kind of silly since ML has
   booleans that could be used instead.  Change the interpreter to use the
   value variant "Bool of bool" as the interpretation of booleans. Your interpreter
   should signal an error if anything other than a "Bool" is used as a boolean value.
   
   This change will affect the semantics of the language because before
   "if 5 then 1 else 2" returns "1"  (because any non-zero value is true)
   whereas after the change it should produce a run-time error.
   
   
3. EOPL 3.20 Function application
   
   Modify the evaluator so that an error is signaled if a function is
   applied to the wrong number of arguments. Currently, the error is signaled only
   when a parameter is accessed, in the case of two few arguments, and not at
   all if there are too many.
   
   
EOPL 3.30 (and 3.33) Static and dynamic binding

Dynamic binding is an alternative design for procedures, where the
procedure body is evaluated in an environment obtained by extending
the environment at the point of call.

For example:


let a = 2 
in let p = proc (x) +(x,a)
       a = 5
   in *(a,(p 2))

Evaluates to 5 under dynamic scoping, not 3.

Your job is to:

a) Modify the interpreter in eval.ml to use dynamic
binding.

b) Determine the result of evaluation under static and dynamic binding
for the following expressions:


let a = 3
    p = proc () a
in let f = proc (x) (p)
       a = 5
   in (f 2)
   
let a = 3
    p = proc () a
in let f = proc (a) (p)
       a = 5
   in (f 2)

(Put the answer to this question in the comments at the end of the file.)

 

5. Because the values stored in the environments in this implementation are
   stored in arrays, and arrays are mutable in ML, we can implement
   recursive definitions as shown in Figure 3.12, without using the
   special variant "ExtendRec" of the env datatype.
   
   The basic idea is that when we extend the environment, we first make a
   dummy vector of values with "place-holders" for all of the recursive
   functions. Then we can create those closures (pointing to the extended
   environment) and fill in the vector with the closures.
   
   Redefine extend_env_rec to be like Figure 3.12.
   
   (Note, operations on arrays in ML are found in the Array module.)