CPSC 425 Spring 2008
HW 12: The Runtime Stack, Part II

1. In a language with static scoping, a reference to a non-local variable x refers to the definition of x in ______________ (fill in the blank).

2. In a language with dynamic scoping, a reference to a non-local variable x refers to the definition of x in ______________ (fill in the blank).

3. Consider the runtime stack below. For each activation record, only the name of the function and the nesting link are shown.

   
              -----------
      --------|   f5    |
      |       |         |
      |       -----------
      |  ---- |   f4    |
      | |     |         |
      | |     -----------
      |  ---> |   f3    |
      |  ---- |         |
      | |     -----------
      | |  -- |   f2    |
      | | |   |         |
      | | |   -----------
      | |  -> |   f1    |
      | ----> |         |
      |   --  |         | 
      |  |    -----------
      |  |    | outer   |
      |  ---> | env     |
      ------> |         |
          
   
   

   Assume the language uses static scoping in answering the questions below.
   1. From the stack you can tell some things about the nesting levels of the functions. What do you know about the relationship (be as specific as possible) between
      1. level(f1) and level(f2)
      2. level(f1) and level(f3)
      3. level(f1) and level(f4)
      4. level(f1) and level(f5)

   2. Some of these functions could have been passed as parameters. Given the nesting links shown, did any of them have to be passed as a parameter? Explain.

   3. Write a program in ML that would produce this stack at some point during its execution. The program need not be meaningful (e.g., each function can just call another function without "doing" anything).