Evaluating Function Calls

The previous chapter made functions into values. A function value is a closure: the parameter names, the body, and the environment where the function was written. This chapter is about what happens when a program calls one.

Here are two small functions. trace prints a label and then returns a number; sub subtracts:

fn trace(label: String, v: Int) -> Int {
    println(label);
    v
}

fn sub(a: Int, b: Int) -> Int = a - b;

sub(trace("a", 10), trace("b", 3))

The call’s value is 7. Getting there takes several steps, and at each one the language has to decide something:

• What is evaluated first? The interpreter evaluates sub to find its closure, and each argument to get its value. Because trace prints, the output shows the order: a then b, or b then a.
• When is an argument evaluated? Before the body starts, or only when the body uses the parameter — and so never, if the body never does.
• Where does the body run? The body looks up its parameters, and any other names it mentions, in some environment. The call has to build that environment.
• What if the body leaves early? A return in the body has to become the call’s value and go no further.

Languages in use today still answer the first two questions differently. The second divided Algol 60 and Lisp at the end of the 1950s, and the chapter begins there before giving Bridger’s answers as one inference rule, E-App.

Call by value, call by name

The Algol 60 report defined a procedure call by describing an edit to the program text. Its §4.7.3 lists the operations “on the program at the time of execution of the procedure statement”. A parameter listed in the procedure’s value part is called by value: the actual parameter is evaluated and its value assigned to a variable local to the body, as though in “an additional block embracing the procedure body”. Every other parameter is called by name:

Any formal parameter not quoted in the value list is replaced, throughout the procedure body, by the corresponding actual parameter, after enclosing this latter in parentheses wherever syntactically possible. Possible conflicts between identifiers inserted through this process and other identifiers already present within the procedure body will be avoided by suitable systematic changes of the formal or local identifiers involved.

“Finally the procedure body, modified as above, is inserted in place of the procedure statement and executed.” Under call by name an argument is an expression, pasted into the body wherever the parameter appears, and evaluated each time execution reaches one of those places — once, many times, or never. The renaming clauses keep the paste from changing what any name means: the body’s own identifiers are renamed away from those in the pasted expression, and, when the procedure is called from somewhere its nonlocal names are not in scope, the caller’s identifiers are renamed away from the body’s.

Call by name made possible a kind of procedure that call by value cannot express directly. A procedure could take an expression and a variable that appears in it, change the variable, and re-evaluate the expression:

real procedure sum(i, lo, hi, term);
    value lo, hi;
    integer i, lo, hi;  real term;
begin real s;
    s := 0;
    for i := lo step 1 until hi do s := s + term;
    sum := s
end

A call sum(k, 1, n, a[k] × b[k]) pastes a[k] × b[k] in for term and k in for i, so each turn of the loop assigns the next index to k and then evaluates the product at that index; the call computes an inner product. The technique came to be known as Jensen’s device.

A compiler cannot literally edit the program text at every call, so it has to produce the same effect another way. Peter Ingerman’s 1961 paper, titled simply “Thunks”, describes compiling each by-name argument into a small routine that computes the argument’s expression in the caller’s environment; the body runs that routine every time it uses the parameter. The paper’s title became the name for such a routine, and for any delayed computation packaged to run later.

Lisp took the other answer for every argument. McCarthy’s eval evaluates each argument of a function call first and hands the function the resulting values — call by value — so an argument is evaluated exactly once, before the body starts, whether or not the body uses it. C, ML, Java, Python, Rust, and Bridger all evaluate arguments the same way.

The rule for application

Bridger’s call is one rule. In the env-and-store judgment of Part IV:

$$\frac{\begin{array}{c}\rho ⊢⟨e_0,{\sigma }_0⟩\Downarrow ⟨⟨\lambda \vec{x}.e_b,{\rho }^{\prime }⟩,{\sigma }_0^{\prime }⟩\\ \rho ⊢⟨e_i,{\sigma }_{i-1}^{\prime }⟩\Downarrow ⟨v_i,{\sigma }_i^{\prime }⟩(1\le i\le n)\\ {\rho }^{\prime }[\vec{x}\mapsto \vec{v}]⊢⟨e_b,{\sigma }_n^{\prime }⟩\Downarrow ⟨r,{\sigma }^{\prime }⟩\end{array}}{\rho ⊢⟨e_0(e_1,\dots ,e_n),{\sigma }_0⟩\Downarrow ⟨\mathsf{Val}(\mathrm{unwrap}r),{\sigma }^{\prime }⟩}(\text{E-App})$$

Read top to bottom, the premises are the order the interpreter works in.

The first premise evaluates the operator $e_0$, in the caller’s environment $\rho$, and requires the result to be a closure $⟨\lambda \vec{x}.e_b,{\rho }^{\prime }⟩$: parameters $\vec{x}$, body $e_b$, and the environment ${\rho }^{\prime }$ that E-Lam recorded when the closure was made. The operator is an expression like any other. It is usually a name — sub, which E-Var looks up — but pick(true)(10) and (deref cell)(7) are calls too.

The second line evaluates the arguments $e_1$ through $e_n$, also in $\rho$, one after another. The store threads through them in index order — $e_1$ starts from the store the operator left, ${\sigma }_0^{\prime }$, and each later argument starts from the store the one before it left — which fixes the order at left to right, exactly as the threaded store fixed the order of +’s operands in mutation. Each $v_i$ is a value by the time the body starts. That makes the rule call by value, and the call from the start of the chapter prints a and then b before sub’s body subtracts.

The third premise runs the body. Its environment is ${\rho }^{\prime }[\vec{x}\mapsto \vec{v}]$: the closure’s captured environment, extended with each parameter $x_i$ bound to its argument $v_i$. The caller’s environment $\rho$ appears in the first two premises and not in the third. Whatever the caller has bound, the body sees only what was in scope where the function was written, plus its own parameters:

let scale = 10;

fn scaled(x: Int) -> Int = x * scale;

fn main() {
    let scale = 2;
    let x = 99;
    println(scaled(4));               // 40
}

scaled’s closure captured the program environment, where scale is 10; extending it with x ↦ 4 shadows nothing the caller holds, because the caller’s x and scale are not in it. This is the lexical scope that Part III committed Bridger to, now at work on code that runs away from where it was written. What the other choice — looking free names up in the caller’s environment — would do to programs like this one is the subject of static and dynamic scope.

The bindings the body extends are new. A call does not change the closure’s environment ${\rho }^{\prime }$; it builds a child of it for the length of the body, the same way a block builds a child scope. Two calls of the same function, or a function that calls itself, each get their own parameter bindings on top of the same captured environment.

The conclusion writes out both outcomes of evaluation, which the rules since E-Return have left implicit. The body’s result $r$ is either an ordinary $\mathsf{Val}v$ or the returning outcome $\mathsf{Ret}v$ that return produces, and

$$\mathrm{unwrap}(\mathsf{Val}v)=\mathrm{unwrap}(\mathsf{Ret}v)=v$$

turns either into the call’s value, marked $\mathsf{Val}$ again. Under the convention that a premise yielding $\mathsf{Ret}$ makes its rule yield $\mathsf{Ret}$, a return travels outward through the loops and blocks around it; E-App is where it stops. The call is the function boundary that conditionals and loops described without having one:

fn first_negative(xs: [Int]) -> Int {
    for x in xs {
        if x < 0 { return x; }
    }
    0
}

first_negative([3, -4, 5, -6]) + 100    // 96

The return x abandons the rest of the loop and the trailing 0; the call to first_negative catches it and yields -4, and the + 100 around the call proceeds as it would for any value.

When a call is stuck

Two things can prevent E-App from applying. The operator may evaluate to something other than a closure — 5(1), or a name bound to a list — and then the first premise cannot hold. Or the number of arguments may differ from the number of parameters, and then ${\rho }^{\prime }[\vec{x}\mapsto \vec{v}]$, which pairs the $i$-th parameter with the $i$-th value, has no meaning. The Algol 60 report stated the second condition in as many words: the actual parameter list “must have the same number of entries as the formal parameter list” of the declaration.

The premises also say when each is detected. A non-function operator is stuck at the first premise, before any argument has run; a wrong count is stuck only once the arguments have all been evaluated, since the rule compares the values with the parameters. In 5(trace("a", 1)) nothing is printed; in sub(trace("a", 1)) the a is printed and then evaluation is stuck.

Both are runtime errors in the interpreter built so far. With the type checker of Part VI, a call’s operator and its argument count are known before the program runs, and both become static errors.

Building it

A call is Expr::Call, holding the operator, the argument expressions, and the span of the whole call:

Expr::Call(Box<Expr>, Vec<Expr>, Span)

Everything the Call arm needs beyond eval_expr itself is provided. The closure it finds is the Closure enum from the previous chapter; the environment for the body is built with Env::extend, which returns a child scope and leaves its receiver untouched; the stuck cases have their own RuntimeError variants; and two methods on Interpreter keep count of how deep the calls are nested:

impl Env {
    pub fn extend(&self, x: Name, v: Value) -> Env;
}

RuntimeError::NotAFunction { found: Ty, span: Span }
RuntimeError::ArityMismatch { expected: usize, found: usize, span: Span }

impl Interpreter {
    fn enter_call(&mut self, span: Span) -> Result<(), RuntimeError>;
    fn leave_call(&mut self);
    fn eval_prelude(&mut self, id: BuiltinId, args: Vec<Value>, span: Span)
        -> Result<Value, RuntimeError>;
}

The arm follows E-App’s premises in order. It evaluates the operator; a value that is not a Value::Closure is NotAFunction, with found filled from the value’s runtime type, before any argument is touched. It evaluates the arguments left to right into a vector of values. What happens next depends on which kind of closure it holds. A Closure::Native is a prelude primitive, and eval_prelude runs it on the argument values. A Closure::Bridger checks the argument count against its parameters (ArityMismatch if they differ), extends its own captured env with one binding per parameter, and evaluates the body in that environment.

A Bridger body is bracketed by enter_call before it and leave_call after it, whatever the body’s outcome. The pair counts frames: a program that recurses without end is stopped at a fixed depth with a StackOverflow error, where the Rust stack running eval_expr would otherwise overflow and abort the whole interpreter.

The body’s outcome is the last thing the arm looks at. Evaluation hands it back as the Control channel: a value, a Control::Return, or a Control::Raise. The Call arm is the one place in the evaluator that inspects Control::Return instead of passing it on — it takes the returned value as the call’s value, which is $\mathrm{unwrap}$ — while a Raise continues outward as it does everywhere else.

In Part VII, the operator of a call may also evaluate to a relation, and the Call arm gains one more case.

The design space

Other languages have answered E-App’s questions differently, most visibly the order in which a call’s parts are evaluated and when an argument is evaluated at all.

Evaluation order

Bridger fixes the order: operator, then arguments left to right. Java fixes the same order for arguments — the Java Language Specification has a section titled “Argument Lists are Evaluated Left-to-Right”. Scheme leaves it open: the R7RS (§4.1.3) says only that the operator and operands of a procedure call are evaluated in an unspecified order. C goes further. Under the C11 standard (§6.5) the side effects of a call’s arguments are unsequenced relative to one another, and if two of them modify the same object, as in f(i++, i++), the program’s behaviour is undefined: the standard places no requirement on what it does.

Leaving the order open lets a compiler evaluate the arguments in whatever order suits the machine: pushing them onto a stack from right to left, or computing the one that needs the most registers first. The cost falls on programs whose arguments have effects. A call such as printf("%d %d\n", next(), next()), where next advances a counter, prints its two numbers in either order, and the order can change with the compiler, its version, or its optimization level. A program that happens to rely on one order works until it is rebuilt somewhere else. A fixed order costs the compiler that freedom and gives every call with effects a single meaning; in the semantics it costs nothing, since threading the store left to right is already an order.

When arguments are evaluated

Call by value evaluates each argument once, before the body starts. A function that ignores one of its arguments still pays for it — and if that argument is stuck, the call is stuck:

fn choose(c: Bool, a: Int, b: Int) -> Int = if c { a } else { b };

choose(true, 1, 1 / 0)            // stuck: division by zero

Call by name would have returned 1: b is never reached in the body, so 1 / 0 is never evaluated. The price is paid on the other side. A by-name argument is evaluated every time the body uses its parameter, so a parameter used inside a loop re-evaluates its argument on every turn, and an argument with an effect has that effect once per use. Jensen’s device relies on exactly this, and it is also why a reader of an Algol 60 procedure cannot tell, from the call alone, how many times each argument will run.

Call by need keeps call by name’s promise to evaluate an argument only if it is used, and adds a second promise: at most once. The first use evaluates the argument and records its value; every later use reads the record. Christopher Wadsworth’s 1971 Oxford thesis is usually credited with the technique, as a way of evaluating λ-calculus terms without repeating work. It is the evaluation strategy of lazy functional languages. The Haskell 2010 Report specifies “non-strict semantics” — a function may return a result without evaluating an argument it does not need — and leaves the mechanism to the implementation; the widely used Glasgow Haskell Compiler implements it with call by need.

Call by need makes the number of times an argument runs, and when, depend on how the body happens to use it. An argument that prints, or writes a cell, would print or write at a moment nobody chose. Haskell’s answer is to have no such arguments: an ordinary Haskell expression cannot perform an effect, and effects are sequenced by a separate mechanism in the types. A language with effects in ordinary expressions, Bridger among them, would have to choose between that restriction and effects whose timing a programmer cannot predict.

Bridger’s lambdas can simulate a by-name argument where one is wanted. A lambda with no parameters, written ||, is a thunk in Ingerman’s sense: it packages an expression to be evaluated later, in the environment where it was written, and a call with no arguments runs it:

fn choose_lazy(c: Bool, a: fn() -> Int, b: fn() -> Int) -> Int =
    if c { a() } else { b() };

choose_lazy(true, || 1, || 1 / 0)      // 1

The delay is written out at the call and the forcing in the body, so it is visible exactly where it happens. Call by need adds one more thing, the record of the first result; with a mutable cell to hold it, that too can be built by hand.

A fourth answer, where a procedure receives its argument’s location and assignments to the parameter write the caller’s variable, belongs to the same family. FORTRAN II passed arguments as locations, as the previous chapter showed, and Pascal’s var parameters make the choice per parameter. Bridger gets the same effect with an explicit value: a function that should update its caller’s state is passed a ref cell, and the cell’s location travels by value like any other.

Further reading

Parameter passing in Algol 60: the Revised Report on Algol 60 (1963) defines value assignment, name replacement, and body replacement in §4.7.3, in under a column. Ingerman’s “Thunks” (1961) describes how a compiler can carry out name replacement without editing the program.

Evaluation strategies and the λ-calculus: Gordon Plotkin’s “Call-by-name, call-by-value and the λ-calculus” (1975) gives each strategy its own calculus and proves how the two relate to evaluation in a machine; the argument is carried almost entirely in the formal development.

Laziness in practice: “A History of Haskell: Being Lazy with Class” (Hudak, Hughes, Peyton Jones, and Wadler, 2007) tells how the lazy functional languages came to share one design, and how laziness pushed Haskell toward purity and a type-based treatment of effects. John Hughes’s “Why Functional Programming Matters” (1989) uses lazy evaluation to separate a program that generates candidate answers from the one that decides how many to look at.

Concept checks

fn sum_until_negative(xs: [Int]) -> Int =
    fold(xs, 0, |acc: Int, x: Int| if x < 0 { return acc; } else { acc + x });