Lecture 11

Subroutines


Abstraction: associate a name with potentially complicated program fragment
 - control abstraction -> subroutines
 - data abstraction -> object oriented 

subroutines
 - function
 - procedure

Local variables

 - created on function entry and destroyed on function exit
 - function calls in last-in-first-out order 

   Two functions f and g, their run-time relationship can be
   either non-overlap or nested. 
   Therefore, local variables can be handled by using stack (of frames).

   Stack grows downwards (from high address to low address). 
   Inside a frame, in addition to local variables, there are 
   control access that contains links to previous stack frame.

In each stack frame:

1. local variables
2. misc temps
3. control link
   dynamic link  points back to the prev frame: who's calling you
4. access link
   static link   points to where the current function was defined
5. return address




Calling sequences

Into a subroutine:

  - passing parameters
  - saving return address
  - changing program counter
  - changing stack counter
  - saving registers (including the frame pointer)
  - changing the frame pointer to refer to the new frame
  - executing initialization for any objects in the new frame

At a return

  - passing return parameters or function values
  - executing finalization code for any local objects that require it
  - deallocating the stack frame (restoring the stack pointer)
  - restoring the program counter

Note: - most tasks can be done by either caller or callee.
      - save space if callee does as much work as possible.


e.g., (in C-like syntax)

  void f (int x) 
  {
       int y = 5;
       g (x + y);
       g( x + y + 1);
  }

  void g (int x)
  {
       int y = 10;
       int z = 20;
       print (x+y+z);
  }





                            |
    ______________________  |
    | |  control          |-|
    |f|  return addr      |
    |---------------------|<-|
    |  x = 7              |  |
    |  y = 5              |  |
    ----------------------   |
                             |
                             |
    ______________________   |
    | |  control          |--|
    |g|  return addr = L1 |
    |---------------------|
    |  x = 12             |
    |  y = 10             | 
    |  z = 20             |
    ----------------------



   Note: Control link (also called dynamic link) is the saved value of 
         the frame pointer, which tells where the parent frame starts 
         and therefore can restore it once this frame is poped off 
         the stack.
         Return Address: When function f calls function g, eventually 
         g must return. It needs to know where to go back to. If the call 
         instraction within f is at address a, then (usually) the right 
         place to return to is a + 1, the next instruction in g. This is 
         called return address. 
         



  f (int x) 
  {
      g(int y)
      {
        ...
        ... x+y ...     /* access to the local variables of function f where */
                        /* this function g is defined.                       */
        ... g(...) ..   /* function g is recursively defined.                */
      }
  }


     ^                     ^
     |                     |
     |  |---------------|  |
     |--| |    c        |--
  |---->|f|-------------|<-|
  |  |->| |    a        |  |
  |  |  |---------------|  |
  |  |  |    x = 3      |  |
  |  |  ----------------   |
  |  |                     |
  |  |                     | 
  |  |                     |
  |  |  |---------------|  |
  |  |--| |    c        |--
  |     |g|-------------|<-|
  |     | |    a        |  |
  |     |---------------|  |
  |     |    y = 5      |  |
  |     ----------------   |
  |                        | 
  |                        | 
  |     |---------------|  |
  |     | |    c        |--
  |     |g|-------------|
  |-----| |    a        |
        |---------------|
        |    y = 7      |
        ----------------

  Note: Access link (also called static link) is a reference to the frame of 
        the lexically surrounding subroutine. Access link is a way to implement 
        recursive call in lexical scope language.

  Given the current frame there is no fixed offset we can access variable x 
  in the parent function. That's why we need access link to point to x.


  f (int x )                              /* level 1 */
  {
       g (int y)
       h (int z)                          /* level 2 */
            i (int w)
               ... x + z + w ...          /* level 3 */


     ^                     ^
     |                     |
     |  |---------------|  |
     |--| |    c        |--
  |---->|f|-------------|<-|
  |  |->| |    a        |  |
  |  |  |---------------|  |
  |  |  |    x = 3      |  |
  |  |  ----------------   |
  |  |                     |
  |  |                     | 
  |  |                     |
  |  |  |---------------|  |
  |  |--| |    c        |--
  |     |h|-------------|<-|
  |  |->| |    a        |  |
  |  |  |---------------|  |
  |  |  |    z = 5      |  |
  |  |  ----------------   |
  |  |                     | 
  |  |  |---------------|  |
  |  |  | |    c        |--
  |  |  |i|-------------|<-|
  |  |--| |    a        |  |
  |     |---------------|  |
  |     |    w = 12     |  |
  |     ----------------   |
  |                        | 
  |                        | 
  |     |---------------|  |
  |     | |    c        |--
  |     |g|-------------|
  |-----| |    a        |
        |---------------|
        |               |
         ---------------

Compiler needs to track which level a variable is defined and at 
which level it is called in order to decide how many access 
links to jump. 

Calculating access link:
   - level of current function
   - level of funcion be called
   - copy access link from callee fn's level to caller fn's level.

Note that function f can not call function i for i is local to 
function h so f does not know i exist. If caller is parent of callee,
then set access to current frame (caller).

Note: access link is for implementing lexical scoping and you have 
nested functions.  For dynamic scoping, however, it is not just to 
throw away access link. We need to add extra info. Lookup first in 
local frame, if not found, then follow dynamic link up to the prev 
frame, and so on and so forth, until found. 
(Refer to the textbook for Display, an alternative to access link)


For lexical scope, compiler always knows an offset for accessing a variable.

For dynamic scope, the layout of previous stack where you need to lookup
a variable is unknown (until run-time).
So compiler need to generate (in target code) a table listing all 
the info (about a function's local variables and the layout) for run-time
lookup. Therefore, for compiler, lexical scoping is easier to 
implement (this is in contrast to interpreter).