Midterm Exam 2

CSE 428
Fall 2000

Midterm #2
Test Form B

8 November 2000

Assume a program containing two global procedures P and Q. Local to P are two procedures R and S. Consider the state of the run-time stack after the following sequence of procedure calls: Q calls P, then P calls R, then R calls S. The static link in S's activation record is
- [(A)] the same as P's static link
- [(B)] the same as R's static link
- [(C)] the same as S's dynamic link
- [(D)] a pointer to Q's activation record
- [(E)] none of the above
If a language prohibits nesting of procedures inside of procedures, then an implementation of this language does not need
- [(A)] any static or dynamic links
- [(B)] any dynamic links
- [(C)] any static links
- [(D)] any static links to recursive procedures
- [(E)] any dynamic links to recursive procedures
If the language uses call-by-reference parameter passing, then the Caller will
- [(A)] push the value of the actual parameter onto the stack because the Callee will know to reference this stack location
- [(B)] push the address of the actual parameter onto the stack
- [(C)] push the value and address of the actual parameter onto the stack
- [(D)] all of the above
- [(E)] none of the above
If a function is tail-recursive then a compiler can implement this by
1. [(A)] avoiding the use of activation records
2. [(B)] creating a new activation record only when the function uses local variables
3. [(C)] reusing the same activation record for all recursive calls to the function
4. [(D)] all of the above
5. [(E)] non of the above

An efficient implementation of dynamic storage allocation using displays requires

[(A)] initializing all the display registers upon procedure entry
[(B)] saving and updating only one display register upon procedure entry
[(C)] computing static links at procedure call time
[(D)] computing static links at compile time
[(E)] traversing static links to find non-local variables

The next five questions use the following declarations:

datatype 'a mtree = Empty | Node of ('a mtree) * 'a * int * ('a mtree)

fun s(Empty) = 0
   |s(Node(t1,x,n,t2)) = n + s(t1) + s(t2);
fun fl(Empty) = Empty
   |fl(Node(t1,n,k,t2)) = Node(fl(t1), n,k, fl(t2));
fun rnk(Empty,z) = (Empty,z)
   |rnk(Node(t1,n,k,t2),z) = let val (t1',z1) = rnk(t1,z+1);
			         val (t2',z2) = rnk(t2,z1 )
			     in (Node(t1',n,z,t2'),z2) end;
fun ins(0) = Empty
   |ins(n) = Node(ins(n-1), n,n, ins(n-1));

What is the most general type of the function s:
- [(A)] 'a mtree * int -> int
- [(B)] int
- [(C)] 'a mtree -> int
- [(D)] int mtree -> int mtree
- [(E)] int mtree * int -> int mtree
What is the most general type of the function fl:
- [(A)] 'a mtree -> 'a mtree
- [(B)] 'a mtree * 'a * int * 'a mtree -> 'a mtree
- [(C)] ('a mtree * 'a * int * 'a mtree) -> ('a mtree * 'a * int * 'a mtree)
- [(D)] int mtree -> int mtree
- [(E)] int mtree * int mtree
Which of the following statements is true:
- [(A)] fl(t) = t, for any mtree t
- [(B)] fl(fl(t)) = t, for any mtree t
- [(C)] fl(fl(t)) = fl(t), for any mtree t
- [(D)] fl(rnk(t,0)) = t, for any mtree t
- [(E)] rnk(t) = t, for any mtree t
For any tree t, what does the expression rnk(t,0) return:
- [(A)] a tree identical t
- [(B)] a tree similar to t, but with every internal node labeled by 0.
- [(C)] a tree similar to t, but with every internal node labeled according to a preorder traversal of the tree
- [(D)] a tree similar to t, but with every internal node labeled according to an inorder traversal of the tree
- [(E)] a tree similar to t, but with every internal node labeled with its depth in the tree
What is the value of the expression s(ins(2)):
- [(A)] 0
- [(B)] 1
- [(C)] 2
- [(D)] 3
- [(E)] 4
The next five questions refer to the compiler and abstract machine presented in class, including declarations
```
datatype Exp = ...
datatype Instr = ...
type Code = Instr list
type State = (Code * int list * int list)
```
and functions
```
 comp : Exp * string list -> Code
 exec : State -> int
 execute: Code -> int
```
The compiler (function comp) uses its second argument (of type string list) to
- [(A)] perform typechecking
- [(B)] ensure that all variable references are in scope
- [(C)] generate unique variable names when necessary
- [(D)] count the number of variables used in the program
- [(E)] convert identifier names to integer offsets
The definition of exec contains one base (non-recursive) case that produces the return value when the code component of the machine state is empty:
```
fun exec(nil, v::S, env) = v
   | ...
```
Suppose we delete this rule and insert the following rule after {\it all} the other cases in the definition of exec:
```
   |exec(C,S,E) = (C,S,E)
```
Which of the following statements is true about this new definition of exec
- [(A)] the new function and the original function will terminate (without exception) on exactly the same inputs.
- [(B)] the new function returns only when the code list is empty
- [(C)] the new function can return a machine state in which the first instruction in the code list cannot be executed because the stack or the environment is not in the required form
- [(D)] the new function can execute a program in fewer machine steps than the original function would have taken
- [(E)] the new function may execute a program in more machine steps than the original function might require
Assuming the same change to exec as described above, which of the following definitions of execute provides behavior identical to the original definition of the machine:
- [(A)] fun execute cd = exec(cd,nil,nil);
- [(B)] fun execute cd = let val (C,v::S,E) = exec(cd,nil,nil) in v end;
- [(C)] fun execute cd = let val (nil,v::S,E) = exec(cd,nil,nil) in v end;
- [(D)] fun execute cd = exec(cd,S,E);
- [(E)] fun execute cd = let val v = exec(cd,nil,nil) in v end;
Extending the compiler to handle local function declarations and function calls {\bf requires}
- [(A)] maintaining a list of function names during compilation
- [(B)] extending the list of variable names with the names of formal parameters before compiling the body of a function
- [(C)] generating code for pushing and popping argument values from the machine's E environment
- [(D)] both A and B, but not C
- [(E)] A, B, and C
Extending the abstract machine to handle local function declarations and function calls {\bf requires}
- [(A)] maintaining a machine-state component consisting of a list of code for functions currently in scope
- [(B)] extending the machine language with instructions for pushing and popping code for functions
- [(C)] pushing and popping all of a function's arguments using just one instruction
- [(D)] both A and B, but not C
- [(E)] A, B, and C
The next five questions refer to the typechecker and evaluator presented in class.
```
datatype Exp = ...
datatype Ty =  BoolTy | IntTy | NoTy;
datatype Val = ...
type Context = (Id * Ty) list
type Env = (Id * Val) list
```
and functions
```
tc : Exp * Context -> Ty
typecheck : Exp -> Ty
ev : Exp * Env -> Val
eval : Exp -> Val
```
The typecheck function tc generates an exception whenever it determines that an expression is not well-typed. Suppose we modify the function to simply return NoTy in these cases. Making this change:
- [(A)] would require other changes be made in the definition of tc
- [(B)] is not possible
- [(C)] would make the function tc more efficient
- [(D)] would require changes to the definition of typecheck
- [(E)] would not be able to detect all possible type errors
Typechecking function declarations and function calls
- [(A)] Requires computing the type of the function body knowing the type of the function parameter
- [(B)] Requires checking that the type of the argument (in a function call) is equal to the type of the function's parameter
- [(C)] Requires ensuring that functions are called only within their scope
- [(D)] both A and B, but not C
- [(E)] A, B, and C
Evaluating function declarations and function calls
- [(A)] Requires evaluating arguments (in a function call) prior to evaluating the body of the function
- [(B)] Requires looking up the function's name in the environment
- [(C)] Requires extending an environment with a binding for the function's formal parameter
- [(D)] both A and B, but not C
- [(E)] A, B, and C
The function ev
- [(A)] uses its environment to look up values for variables
- [(B)] checks the types of values to make sure all operations are performed properly
- [(C)] will never raise an exception, regardless of its input expression
- [(D)] A and B, but not C
- [(E)] A and C, but not B

In the function ev, the case for Let expressions is

 |  ev( Let(x, e1, e2), venv ) =
      let val v1 = ev( e1, venv );
          val v2 = ev( e2, extend(venv, x, v1 ))
      in v2 end

An equivalent definition is

[(A)]

 |  ev( Let(x, e1, e2), venv ) =
      let val v2 = ev( e2, extend(venv, x, e1))
      in v2 end

[(B)]

 |  ev( Let(x, e1, e2), venv ) =
      let val v2 = ev( e2, extend(venv, x, ev( e1, venv)))
      in v2 end

[(C)]

 |  ev( Let(x, e1, e2), venv ) =
       ev( e2, extend(venv, x, ev( e1, venv)))

[(D)] A, B, and C
[(E)] B and C, but not A

The next five questions refer to the following program

program main
  x: integer;
  
  procedure p(a:integer)
    x := a+x
  end p;

  procedure q(b:integer)
    x : integer;
    x := b+2;
    p(x);
    b := b+1
  end q;

  x:=1;  (* main begins here *)
  q(x);
  write(x)
end main;

What is the value written out assuming static scoping and call-by-value parameter passing? (A) 1 (B) 2 (C) 3 (D) 4 (E) 5
What is the value written out assuming static scoping and call-by-reference parameter passing? (A) 1 (B) 2 (C) 3 (D) 4 (E) 5
What is the value written out assuming static scoping and call-by-value-result parameter passing? (A) 1 (B) 2 (C) 3 (D) 4 (E) 5
What is the value written out assuming dynamic scoping and call-by-value parameter passing? (A) 1 (B) 2 (C) 3 (D) 4 (E) 5
What is the value written out assuming dynamic typing, static scoping and call-by-value parameter passing? (A) 1 (B) 2 (C) 3 (D) 4 (E) 5