Subprograms I: parameter passing methods

This week’s topic, parameter passing methods, is one of the most “mechanical” topics on the exam and one of the biggest point winners. The question template is always the same: a small procedure, a call, “what happens to the variables under each method?” Recipe: for each method write what the formal parameter receives (a value, an address, an expression) and when it writes back, then trace line by line.

Golden rules:

1. Value: a copy. Reference: an address. One does not change the outside, the other changes it immediately.
2. Value-result changes the outside only at return, and the result may depend on the copy order.
3. Name: re-evaluate the expression on every use. If the index variable changes, you go to a different element.
4. If the same variable is passed to two parameters, or as parameter + global, there is an alias. Most questions come from here.
5. In Java everything is pass-by-value, including references.

Basic concepts

A subprogram definition consists of a header (name, parameters) and a body. The parameters in the definition are formal parameters, the expressions in the call are actual parameters.

• Positional: actuals are matched in order. Short, but causes mistakes in long lists.
• Keyword: area(width = 3, height = 5) (Python, Ada). The order is free, but the formal names must be known.
• Default: the value used if no actual is given.

function f(a, b = a * 2) { return a + b; }
console.log(f(3), f(3, 1));

9 4

Subprograms are divided into functions, which return a value, and procedures, which do not. Local variables are usually stack-dynamic (recursion is possible); in C they can be made static with static (they remember history).

Semantic models: in, out, inout

Implementation is done in two ways: physically copying the value (value, result, value-result) or transferring an access path (address) (reference).

Five methods

Pass-by-value

The actual’s value initializes the formal, and the formal behaves like a local variable. No effect on the outside. Cost: large objects are copied.

Pass-by-result

The input value is not transferred. The formal is initialized in the callee, and its value is copied to the actual on return. Problems: in calls like g(a, a), which copy will win (actual parameter collision), and whether the address of the actual is computed at the call or at the return.

void g(out int x, out int y) { x = 5; y = 7; }
g(a, a);          copy left to right: a = 5, then a = 7  → 7

Pass-by-value-result

Value + result: copy in at entry, copy out at return. Similar to reference but alias effects are not visible until the return.

Pass-by-reference

The address of the actual is transferred, and the formal becomes its alias. No copy, fast. But aliases lower readability and reliability; every access needs an indirection.

Pass-by-name

Every use of the formal behaves as if it were replaced by the text of the actual, and is evaluated at that moment in the caller’s environment. It exists in ALGOL 60 and is rarely used today. Its implementation: a thunk for each parameter (a small function that computes the address or value when called). When a simple variable is passed it behaves like reference; the difference appears when an array element or an expression is passed.

Worked example 1: the same variable twice

void f(int x, int y) { x = x + 1; y = y * x; }
a = 2;  f(a, a);

Worked example 2: alias with a global

int g = 3;
void fun(int x) { x = x * 2; g = g + 1; }
fun(g);

value:         x = 3 → 6 (local)       g = 3 + 1          → 4
reference:     x ≡ g: g = 6            g = 6 + 1          → 7
value-result:  x = 3 → 6 (local)       g = 4; on return g = x → 6
name:          x ≡ g (simple variable)                     → 7

Worked example 3: array element and a changing index

int i = 0;  int A[3] = {1, 2, 3};
void h(int x) { i = i + 1; x = x + 10; }
h(A[i]);

value:      the array does not change                 {1, 2, 3}
reference:  address at the call: x ≡ A[0]             {11, 2, 3}
            the change of i is irrelevant
name:       x is A[i] on every use; i is now 1        {1, 12, 3}
            x = x + 10  →  A[1] = A[1] + 10

With value-result you also get {11, 2, 3}, because the return address is computed at call time. In some definitions the address is computed at return; then it would be {1, 11, 3}. If the question does not specify it on the exam, assume call time and write that down.

Worked example 4: the classic swap(i, A[i])

void swap(int x, int y) { int t = x; x = y; y = t; }
i = 1;  A = {5, 0, 7};
swap(i, A[i]);

reference (addresses at the call: x ≡ i, y ≡ A[1]):
  t = i = 1;  i = A[1] = 0;  A[1] = t = 1      → i = 0, A = {5, 1, 7}   correct swap

name (re-evaluate on every use):
  t = i            → 1
  i = A[i]         → i = A[1] = 0
  A[i] = t         → A[0] = 1      ← i is now 0
                                    → i = 0, A = {1, 0, 7}   swap BROKEN

A general swap that works correctly cannot be written with pass-by-name. One of the reasons this method was abandoned.

PITFALL · thinking name and reference are the same. When a simple variable (a) is passed, the two give the same result. When an array element is passed and the index changes in the body, they differ: reference writes to the old element, name writes to the new element.

The situation in languages

static void swap(int a, int b) { int t = a; a = b; b = t; }
static void change(int[] arr) { arr[0] = 99; arr = new int[]{7, 7}; arr[1] = 55; }
static void grow(StringBuilder sb) { sb.append("!"); sb = new StringBuilder("new"); sb.append("?"); }

int x = 1, y = 2; swap(x, y);
System.out.println(x + " " + y);
int[] a = {1, 2}; change(a);
System.out.println(a[0] + " " + a[1]);
StringBuilder s = new StringBuilder("hi"); grow(s);
System.out.println(s);

1 2
99 2
hi!

Rule: a method can change the inside of an object (because it points to the same object), but cannot point the caller’s variable at a different object.

Closures and other topics

A closure is the combination of a subprogram and the referencing environment where it was defined. If a function can be returned as a value and called elsewhere, the lifetime of the variables it captured must be extended (unlimited extent).

function makeCounter() { let c = 0; return () => ++c; }
const c1 = makeCounter(), c2 = makeCounter();
console.log(c1(), c1(), c2(), c1());
const fs = []; for (var i = 0; i < 3; i++) fs.push(() => i);
console.log(fs.map((g) => g()).join(","));
const gs = []; for (let j = 0; j < 3; j++) gs.push(() => j);
console.log(gs.map((g) => g()).join(","));

1 2 1 3
3,3,3
0,1,2

• Overloaded subprogram: the same name, different parameter profiles (Java, C++). Which one is called is determined at compile time.
• Generic subprogram: a single definition that works with different types (Java generics, C++ templates). Parametric polymorphism.
• Variable number of parameters: Java int... xs, C printf.

Common mistakes

void f(int x, int y) {
    x = x + 1;
    y = y * x;
}

void swap(int x, int y) {
    int t = x;
    x = y;
    y = t;
}

t = i          t = 1
i = A[i]       i = A[1] = 0
A[i] = t       A[0] = 1     (i is now 0!)

void h(int x) {
    i = i + 1;
    x = x + 10;
}

void fun(int x) {
    x = x * 2;
    g = g + 1;
}

static void swap(int a, int b) { int t = a; a = b; b = t; }
// in main:
int x = 1, y = 2;
swap(x, y);
System.out.println(x + " " + y);

static void change(int[] arr) {
    arr[0] = 99;
    arr = new int[]{7, 7};
    arr[1] = 55;
}
// in main:
int[] a = {1, 2};
change(a);
System.out.println(a[0] + " " + a[1]);

function makeCounter() { let c = 0; return () => ++c; }
const c1 = makeCounter(), c2 = makeCounter();
console.log(c1(), c1(), c2(), c1());

function f(a, b = a * 2) { return a + b; }
console.log(f(3), f(3, 1));

const fs = [];
for (var i = 0; i < 3; i++) fs.push(() => i);
console.log(fs.map(g => g()).join(","));