CS314, Fall 2007
Homework 5: Dynamic and Lexical Scoping --PROLEM 3 FIXED
Due: Thurs, Oct 18th, 2007

#1. Scott text, problem 3.9, just answer the question about how much 
variable storage is necessary for execution of this program. 
How would you manage the necessary storage during execution?

#2. Scott text, problem  3.13

(The problem with the original #3 was that there was an 
infinite loop of mutually recursive routines because variable
b was never reset to false.  See below in function Q() as to where
this now happens, so there will only be 2 invocations of Q() 
in the longest chain of calls shown below:

main calls P(assign2) calls R calls Q(assign3) calls P(assign2)
 calls R calls Q(assign 3) 

and eventually assign 1 will be executed two times in R as
the recursion returns through each of two invocations of R.)

#3. Consider the following program in a block structured language.

Program main
{Var g, y;
 Var b=true;    
     procedure P
     {Var x;
          Procedure R
          {Var y;
            y = Q();
            g = y;    /* Assign 1 */
            return y;
          }--end R
      y = 2;          /* Assign 2 */
      x = R();
      return x;
      }--end P

     procedure Q
     {Var y;
       if b then {
         y = 3;       /* Assign 3 */
         b = false;
         g = P();
         return y; }
       else
         return 6;
     }--end Q
      
   y = 1;
   g = P();
}--end main

a) Draw what the runtime stack would look like at each of the points
listed below.  Show the stack frames including lexical and dynamic
chain links and local variables. 

i) The first time you reach Assign 3.
ii) The second time you reach Assign 2.
iii) The second time you reach Assign 1.

b) Repeat the above, but use a display (as shown in class).