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.