Tutorial notes for week 12


++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1. Parameter Passing

Consider the following program in an imperative language:

main() {
  int value = 1, list [2] = { 0, 0 };/* ie, list[0] = 0, list[1] = 0 */

  swap(value, list[0]);
  output(value, list[0], list[1]);

  swap(list[0], list[list[0]]);
  output(value, list[0], list[1]);
}

swap(int a, int b) {
  int temp;
  temp = a;
  a = b;
  b = temp;
}

Assume the "output" procedure prints the values of its parameters on a
new line each time it's called.

Give the output of the program, assuming the parameters are passed:

a) by value;
b) by value-result;
c) by reference;
d) by name.

**** Assume that for call-by-value-result in this language, the
**** location in which the final value of a formal is to be recorded
**** is determined at CALL TIME.  (Tell the students that they can 
     practice at home the case when the copy is done at RETURN TIME).


ANSWERS:

a) 1,0,0
   1,0,0

b) 0,1,0
   0,0,1

c) 0,1,0
   0,0,1

d) 0,1,0
   0,1,0

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2. Below is a program in a block structured language like Pascal.  In
each procedure, variables are declared first, then nested procedures
are declared, and then the actual procedure body appears.

There are many instances of the same name used multiple times (the
variables named A, B, C).  The correct association of the use of one of
these names to the right declaration depends on whether the language uses
static (lexical) or dynamic scope.

a) Assume the language uses static scope.  We can uniquely identify each
use of a name by writing it as <proc>.<name>, where <proc> is the name of
the procedure (or Main, for main program) in which this use of <name> is
declared.  For example, the variables used in the main program below have
been labeled Main.A, Main.B, and Main.C. 

Using this convention, fill in the blanks below to uniquely label all
other uses of variable names.

    Solutions have been written in the program below.


program
|  A,B,C: integer;
|  P:procedure
|   |  B, C: integer;
|   |  S:procedure
|   |   |  C,D: integer;
|   |   |  begin
|   |   |   /* some code */
|   |   |   output := A,B,C;  _main_.A    _P_.B    _S_.C  2)
|   |  end;-S
|   |  begin
|   |   /* some code */
|   |   call R;          
|   |   /* some code */
|   |   call S;          
|   |   /* some code */
|   |   output := A,B,C;  _main_.A    _P_.B    _P_.C      1)
|  end;-P
|  R:procedure
|   |  A: integer
|   |  begin
|   |   /* some code */                         
|   |   output := A,B,C;  _R_.A    _main_.B   _main_.C    3)
|  end;-R                                       
|  begin
|   /* some code */
|   call P;          
|   /* some code */
|   output := A,B,C;  Main.A  Main.B  Main.C               
end;-program

b) For the same program, assume the language uses dynamic scope. Using this
convention, fill in the blanks below to uniquely label all other uses of
names.

    Solutions have been written in the program below.

program
|  A,B,C: integer;
|  P:procedure
|   |  B, C: integer;
|   |  S:procedure
|   |   |  C,D: integer;
|   |   |  begin
|   |   |   /* some code */
|   |   |   output := A,B,C;  _main_.A    _P_.B    _S_.C   2)
|   |  end;-S
|   |  begin
|   |   output := A,B,C;  _main_.A    _P_.B    _P_.C       1)
|   |   /* some code */
|   |   call R;          
|   |   /* some code */
|   |   call S;          
|   |   /* some code */
|  end;-P
|  R:procedure
|   |  A: integer
|   |  begin
|   |   /* some code */                         
|   |   output := A,B,C;  _R_.A    _P_.B   _P_.C           3)
|  end;-R                                       
|  begin
|   /* some code */
|   call P;           Main.P
|   /* some code */
|   output := A,B,C;  Main.A  Main.B  Main.C
end;-program


3. For the previous program, draw the Run-Time Stack until the point 
marked with 3). Stop at each point 1), 2), 3) to show how to 
determine the scope of the variable using the access link for static scope, 
and the control link for the dynamic scope. You'll get exactly the result you
got at a) and b), respectively.

-----------------
S                 ---- point 3)
local vars:   C,D     Static:  Main.A P.B S.C
local procs:          Dynamic: Main.A P.B S.C
control link: P
access link:  P
-----------------
R                 / This is in the stack at point 2), and it
local vars:   A   / gets removed when moving to point 3)
local procs:      /   Static:  R.A Main.B Main.C
control link: P   /   Dynamic: R.A P.B    P.C
access link: Main /
-----------------
P                 --- point 1)
local vars:   B,C       Static:  Main.A P.B P.C
local procs:  S         Dynamic: Main.A P.B P.C
control link: Main
access link:  Main
------------------
Main
local vars:  A,B,C
local procs:  P,R
control link: RTS
access link:  null
------------------
   RTS
------------------