Assignments 1 and 2

CS 152
both due March 10, 1999
100 points each

For Assignment 1, do the problem described below in C++. For Assignment 2, do it in C (without using any C++ constructions).

The problem is to simulate a simple environment system that supports the environment operations given below. Environments are represented as linked stacks of frames. You should be able to implement both static scoping and dynamic scoping.

  1. push a given frame onto the environment
  2. pop a given frame from the environment
  3. return the filler for a given slot for an identifier specified by name (using dynamic scoping)
  4. return the filler for a given slot for an identifier specified by an offset pair (using static scoping)
Here, frames consist of at least (1) a set of sets of bindings, one set of bindings for each identifier, (2) a dynamic link, and (3) a static link. A binding consists of a slot (or attribute) and a filler. Note that in this context we don't use value as a synonym for filler, since value is the name of an important attribute. You needn't worry about updating the filler for a given slot.

To avoid type conflicts (which wouldn't occur in an implementation in a low-level language), you may assume that slot names are of an enumerated type (or of string type). You may assume that all legal fillers are nonnegative integers.

You are to use at least the test cases of the function test in the file a1test.cpp (for Assignment 1), and in the file a2test.c (for Assignment 2). Both files are obtainable from the class web site The test function is written under the assumption that a single environment class (or type) is used for both static and dynamic scoping; if you are using two different classes or types you may modify the test code to change the name environment to whichever of static_environment or dynamic_environment is appropriate.

Note that these test cases assume explicit types/classes frame, identifier_list (with function add_identifier), and binding_list (with function add_binding), in addition to environment. The functions used in Assignment 2 are documented in the file a2functs.h (available from the class web site), which you may add to. The corresponding member functions are used in Assignment 1. You may use additional types (in C) and classes (in C++), and additional functions (member functions in C++).

You may assume that the program will not run out of memory (i.e., that neither malloc nor new will fail). However, you should reclaim storage. Although the only calls to free or delete in the test cases take environment pointers as arguments, you may reclaim storage incrementally.

Some documentation of the source of the test cases is given in the file a1_doc.txt, also obtainable from the class web site.

Techniques for eliminating some of the sequential search in implementing environments, and for computing offsets and initial values of static links will be discussed briefly in class.