CIS 425 Homework V

Functions; Parameter-Passing; Activation Records; due 11/9

Background

First make sure you are familiar with the interpreters presented in class for call-by-name (static and dynamic scope versions) and call-by-value (static scope version and the extensions with first class functions and references, and the version managing activation records explicitly). Read the entire chapter 5!

To Do

There are two parts to this homework and an extra credit problem.

Part I

Write an interpreter for the following language:

datatype bop = Plus | Min | Mul | Div

datatype exp = 
    Num of int 
  | Bin of exp * bop * exp 
  | Dec of string * exp * exp 
  | Var of string 
  | Function of string * exp
  | Call of exp * exp
  | NewArray of exp * exp
  | ArrayIndex of exp * exp
  | ArrayAssign of exp * exp * exp

All parameters should be passed by value. Like Java, there are two kinds of values: primitive values like integers and reference values which point to "objects" in the heap. There are two kinds of heap-allocated objects: functions and arrays. Here are some examples:

(*
 f = fn (x) array(x,0)  // take an x and 
                        // create an array of size x initialized to zeroes
 a1 = f(10)  // a1 is an array of size 10 initialized to zeroes
 a2 = f(20)  // a1 is an array of size 20 initialized to zeroes
 x = (a2[5] = 1000) // update array a2 at index 5 with value 1000; x = 1000
 y = a1[5] 
 return y // should return 0
*)

val e1 = Dec("f", Function("x", NewArray(Var("x"), Num(0))),
         Dec("a1", Call(Var("f"), Num(10)),
         Dec("a2", Call(Var("f"), Num(20)),
         Dec("x", ArrayAssign(Var("a2"), Num(5), Num(1000)),
         Dec("y", ArrayIndex(Var("a1"), Num(5)),
         Var("y"))))))

(* 
  f = fn (x) (fn (y) x+y)
  f(10)(20) // should return 30
*)

val e2 = Dec("f", Function("x", Function("y", Bin(Var("x"), Plus, Var("y")))),
         Call(Call(Var("f"),Num(10)),Num(20)))

(*
  f = fn (g) { 
        x = 1
        g(x)
      }
  x = 3
  f (fn(y) x+y) // should return 4
*)

val e3 = Dec("f", Function("g", Dec("x",Num(1),Call(Var("g"),Var("x")))),
         Dec("x", Num(3),
         Call(Var("f"), Function("y",Bin(Var("x"),Plus,Var("y"))))))

Part II

The questions refer to the following program in some Pascal dialect similar to what is discussed in the book:

program Main
  let var flag := 1
      var x1 := 1
      function P (y1:int) : int = 
        let var x2 := 2
            function Q (y2:int) : int = 
              let var x3 := 3
                  function R (y3:int) : int = 
                          if flag
                          then (flag := 0; P(x1) + y2)
                          else y2
              in y1 + R(x3)
              end
        in x1 + Q(y1) end
  in P(9) end
end

At run time, the program performs the following sequence of calls: Main, P, Q, R, P, Q, R . Assuming that the general shape of an activation record is as in the following figure:

Show the contents of the stack after the second call to R. Your figure should include all activation records on the stack, the values (and names for clarity) of each variable on the stack, and the location each static link points to.
Write an expression that describes how to access the following variables from R's frame: y3 , y2 and flag . A typical expression would look like: *(*(*(FP+4)+4)-8) where FP is the frame pointer and *p fetches the contents of pointer p as in the C language.

Extra Credit

Answer one or both of the following questions:

Using the C preprocessor, write a macro that illustrates dynamic scope in action.
Modify your interpreter from Part I to pass parameters using call-by-value-result. Give a program fragment that produces different results when using the new interpreter.

Visited

times since September 21, 1999 (or the last crash).

sabry@cs.uoregon.edu