Parameter passing modes and access links

Why it exists

When procedure p(x, y) is called as p(a, b), the meaning of the link between the formal parameters x, y and the actual parameters a, b is not fixed by the idea of a procedure. Whether p can change the caller's a, whether x and y can be the same variable, how often an actual parameter expression is evaluated: all of this depends on the parameter-passing mode, and the same program prints different results in different modes. This is a classical GATE topic, usually asked as "what is printed".

Prerequisites

You need the run-time stack and activation records (activation records). Two words: an l-value of an expression is the location it denotes (i, a[2]), an r-value is its value (3).

Precise definitions

The actual parameters are the expressions in the call; the formal parameters are the names in the procedure header.

Call by value. The caller evaluates each actual parameter to an r-value and the callee receives a copy in its own activation record. Assignments to the formal parameter change only the copy; the caller's variable is unchanged. (C passes everything by value; passing a pointer by value lets the callee change what the pointer points to.) Cheap and safe for small values, costly for big objects.

Call by reference. The caller passes the address (l-value) of the actual parameter; the formal parameter becomes an alias of it. Every read or write of the formal is a read or write of the caller's variable, immediately. If the actual parameter is an expression with no l-value (such as x + 1) the compiler evaluates it into a temporary and passes the address of that. The location of a[i] is computed once, at the call, using the value of i at that time. Two formals can be aliases of the same variable (p(a, a)). Fortran passes by reference; C++ references and C pointers give the same effect.

Copy-restore (value-result, copy-in copy-out). The value is copied in at the call like call by value, the callee works on its local copy, and when the procedure returns the final value of the formal is copied back into the actual parameter's location (computed at the time of the call). Unlike call by reference, the caller does not see changes until the return, and aliasing is not seen inside the callee. If two formals are bound to the same actual variable, the result depends on the order in which they are copied back; the usual order is left to right, so the last copy-back wins.

Call by name. The actual parameter is substituted textually for every occurrence of the formal in the body (with the free variables of the actual interpreted in the caller's environment, i.e. renaming conflicting names). Implementation: the compiler passes a thunk, a small procedure (with the caller's environment) that re-evaluates the actual parameter every time the formal is used. Reading x evaluates the thunk; assigning to x assigns to whatever l-value the thunk denotes at that moment, which can be a different location from the one at the call if a variable in the expression has changed. Call by name was used in Algol 60; its descendant, lazy evaluation with sharing (call by need), is used in Haskell.

Summary.

Access links and the display (static scoping). A nested procedure reaches the variables of the procedures that enclose it by the access links of the activation records, one hop per level of nesting: the lookup of a variable declared $k$ levels out follows $k$ links. A display keeps, in an array indexed by nesting depth, a pointer to the latest record of each depth, so the record of any enclosing level is found in constant time; the price is that a call and a return must update the display. A procedure parameter that is itself a procedure needs, besides the code address, the access link of its definition (a closure). Details and the figures are on the activation records page.

How it works

One program, four modes. Main has i = 1 and the array a = [5, 2, 7]; the call is swap(i, a[i]) where swap(x, y) does t = x; x = y; y = t. The effect depends on the mode.

By value nothing changes: swap exchanges its own copies.

1var i = 1;
2var a = [5, 2, 7];
3proc swap(x, y) {
4  var t = 0;
5  t = x;
6  x = y;
7  y = t;
8}
9swap(i, a[i]);
10print i;
11print a[0];
12print a[1];
13print a[2];

By reference x is an alias of i and y of a[1] (the location was computed at the call, when i was 1). The swap works: i becomes 2 and a[1] becomes 1.

1var i = 1;
2var a = [5, 2, 7];
3proc swap(ref x, ref y) {
4  var t = 0;
5  t = x;
6  x = y;
7  y = t;
8}
9swap(i, a[i]);
10print i;
11print a[0];
12print a[1];
13print a[2];

By copy-restore the swap is done on local copies and copied back at the return: the same final result as by reference here, but the changes become visible only at the return.

1var i = 1;
2var a = [5, 2, 7];
3proc swap(copy-restore x, copy-restore y) {
4  var t = 0;
5  t = x;
6  x = y;
7  y = t;
8}
9swap(i, a[i]);
10print i;
11print a[0];
12print a[1];
13print a[2];

By name the thunk of y is the expression a[i], re-evaluated at every use. After x = y has changed i to 2, the assignment y = t stores into a[2], not into a[1]: the swap fails in a surprising way (i = 2, a = [5, 2, 1]).

1var i = 1;
2var a = [5, 2, 7];
3proc swap(name x, name y) {
4  var t = 0;
5  t = x;
6  x = y;
7  y = t;
8}
9swap(i, a[i]);
10print i;
11print a[0];
12print a[1];
13print a[2];

Next, aliasing: p(a, a) with a = 3, where p(x, y) does x = x + 1; y = y * 2; print x + y and the caller prints a afterwards. By reference x and y are the same variable: after the two assignments a = 8, x + y = 16.

1var a = 3;
2proc p(ref x, ref y) {
3  x = x + 1;
4  y = y * 2;
5  print x + y;
6}
7p(a, a);
8print a;

By copy-restore x and y are separate local copies: x = 4, y = 6, x + y = 10, and at the return a receives x and then y, so a ends as 6 (the last copy-back wins).

1var a = 3;
2proc p(copy-restore x, copy-restore y) {
3  x = x + 1;
4  y = y * 2;
5  print x + y;
6}
7p(a, a);
8print a;

Finally Jensen's device, the standard use of call by name. sum(k, e, n) assigns 1 to k and adds the value of e for each k up to n. Called as sum(i, i * i, 3), the formal k stands for the variable i and the formal e for the expression i * i, re-evaluated each time with the current i: the loop computes $1 + 4 + 9 = 14$ and leaves i = 4. With any other mode this would not work, since e would be computed once.

1var i = 0;
2var s = 0;
3proc sum(name k, name e, n) {
4  s = 0;
5  k = 1;
6  while (k < (n + 1)) {
7    s = s + e;
8    k = k + 1;
9  }
10}
11sum(i, i * i, 3);
12print s;
13print i;

The same effect as call by reference can be had in C with pointers. The program below shows by value (nothing changes) and by pointer (the swap works, with the address &a[i] computed at the call while i is still 1):

#include <stdio.h>
 
static void swap_value(int x, int y) {
    int t = x;
    x = y;
    y = t;
}
 
static void swap_pointer(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}
 
static void show(const char *how, int i, const int a[3]) {
    printf("%-9s i=%d a=[%d, %d, %d]\n", how, i, a[0], a[1], a[2]);
}
 
int main(void) {
    int i = 1;
    int a[3] = {5, 2, 7};
    swap_value(i, a[i]);
    show("value", i, a);
    swap_pointer(&i, &a[i]); /* &a[i] is computed once, at the call, while i is still 1 */
    show("pointers", i, a);
    return 0;
}

value     i=1 a=[5, 2, 7]
pointers  i=2 a=[5, 1, 7]

Worked examples

Cheat box

Traps and GATE patterns

Connections

The records into which parameters are placed are described in activation records. In C the corresponding facts are in functions and parameter passing and pointers. The compile-time side of the same question (type checking of arguments, evaluation order) belongs to semantic analysis (phases of a compiler).

PYQs

Self-check

Revision card

References