Homework 2
CSE 130 (Summer 2004)
DUE Tuesday, July 27, in class
1. Write the scope tree for the following program treating it as a
PASCAL program:
program main;
var x,y,z: integer;
procedure A;
var i,j,x: integer;
procedure B;
var i,y: integer;
procedure C;
var j,k: integer;
begin (* C *)
write (i);
end; (* C *)
begin (* B *)
i := 10; i:= i*j; C
end; (* B *)
procedure C;
var j,k: integer;
begin (* C *)
j := 5; i := 10; B
end; (* C *)
begin (* A *)
j := 5; i := 10;
B ; j := 15; C
end; (* A *)
procedure B;
var i: integer;
begin (* B *)
i := 10; write (i)
end; (* B *)
begin (* main *)
A; B
end (* main *)
2. Write a tail-recursive factorial function f(n) in C and show the
run-time stack for the call f(3) (from start to completion).
3. Write an abstract data type for queues whose elements store
10-character names dynamically allocated from the heap. The queue
operations are enqueue, dequeue, isempty, and length.
4. Consider the McCarthy 91 function:
f(x) = if x > 100 then x-10
else f(f(x+11))
(a) Assuming innermost evaluation, evaluate f (101) (give all steps;
if it does not terminate leave it after 5 steps).
(b) Assuming innermost evaluation, evaluate f (102) (give all steps;
if it does not terminate leave it after 5 steps).
5. Discuss briefly the implementation of dynamic scope in a pure
functional language.