Pass-By-Name Parameter Passing

CMPT 383 Lecture Notes
Robert D. Cameron
March 6, 2002

Rather than using pass-by-reference for input/output parameters, Algol used the more powerful mechanism of pass-by-name.

In essence, you can pass in the symbolic "name"; of a variable, which allows it both to be accessed and updated.

For example, to double the value of C[j], you can pass its name (not its value) into the following procedure.

procedure double(x);
  real x;
begin
  x := x * 2
end;

In general, the effect of pass-by-name is to textually substitute the argument expressions in a procedure call for the corresponding parameters in the body of the procedure, e.g., double(C[j]) is interpreted as C[j] := C[j] * 2.

Technically, if any of the variables in the called procedure clash with the caller's variables, they must be renamed uniquely before substitution.

Implications of the pass-by-name mechanism:

1. The argument expression is re-evaluated each time the formal parameter is accessed.
2. The procedure can change the values of variables used in the argument expression and hence change the expression's value.

Pass-by-Name Elegance: Jensen's Device

Passing expressions into a routine so they can be repeatedly evaluated has some valuable applications.

Consider calculations of the form: "sum x_i × i for all i from 1 to n." How could a routine Sum be written so that we could express this as Sum(i, 1, n, x[i]*i)?

Using pass-by-reference or pass-by-value, we cannot do this because we would be passing in only a single value of x[i]*i, not an expression which can be repeatedly evaluated as "i" changes.

Using pass-by-name, the expression x[i]*i is passed in without evaluation.

real procedure Sum(j, lo, hi, Ej);
  value lo, hi;
  integer j, lo, hi; real Ej;
begin
  real S;
  S := 0;
  for j := lo step 1 until hi do
    S := S + Ej;
  Sum := S
end;

Pass-By-Name Security Problem (Severe)

1. A sample program:

   procedure swap (a, b);
   integer a, b, temp;
   begin
     temp := a;
     a := b;
     b:= temp
   end;
   

2. Effect of the call swap(x, y):

     temp := x;
     x := y;
     y := temp
   

3. Effect of the call swap(i, x[i]):

     temp := i;
     i := x[i];
     x[i] := temp
   

   It doesn't work! For example:

   Before call:	i = 2	x[2] = 5
   After call:	i = 5	x[2] = 5	x[5] = 2

   It is very difficult to write a correct swap procedure in Algol.

Evaluation of Pass-by-Name

1. It has a simple semantic model as textual substitution.
2. Modification and re-evaluation of argument expressions has useful applications, such as Jensen's device.
3. Argument expressions are not necessarily evaluated:

   boolean procedure and (x, y);
     boolean x, y;
   begin
     if x then return y else return false
   end;
   

   Here, y is not evaluated if x is false.

Disadvantages:

1. Repeated evaluation of arguments can be inefficient.
2. Pass-by-name can have unsafe semantic effects.
3. Pass-by-name is difficult to implement. Argument expressions must be compiled to special parameterless procedures called thunks. These thunks are passed into the called procedure and used whenever necessary to evaluate or re-evaluate the argument.

Thunks

Thunks are parameterless procedures used to implement pass-by-name.

Essentially a thunk is set up to return a pointer to the current location represented by a parameter.

Thunks can be simulated in (extended) Pascal using procedure types. For example, to simulate the argument expressions i and x[i] passed using pass-by-name, the following thunks can be set up.

TYPE IntVarAddress = ^ INTEGER;
     RealVarAddress = ^ REAL;
FUNCTION iThunk () : IntVarAddress;
BEGIN
  iThunk := ADDRESS(i)
END;

FUNCTION XiThunk () : RealVarAddress;
VAR expi : REAL;
BEGIN
  expi := x[i] * i;
  XiThunk := ADDRESS(expi)
END;

Notice that iThunk will always return the same memory location, but that XiThunk will return a memory location dependent on the current value of i.

Now, the Algol expression Sum(i, 1, n, x[i]) could be rewritten in (extended) Pascal as Sum(iThunk, lo, hi, XiThunk) where the Sum function is defined as follows.

FUNCTION Sum(jThunk : FUNCTION () : IntVarAddress;
             lo, hi : INTEGER;
             EjThunk : FUNCTION () : RealVarAddress);
  VAR S : REAL;
BEGIN
  S := 0;
  jThunk()^ := lo;
  WHILE jThunk()^ <= hi DO BEGIN
    S := S + EjThunk()^;
    jThunk()^ := jThunk()^ + 1
  END;
  Sum := S
END;