Calling Conventions

You may recall from the Grace Hopper reading in Assignment 0 that there was a time (very early on in the history of electronic computers) when programs did not call functions. Instead of writing a function call, you just copied and pasted the code for the function. This was a nightmare in terms of maintainability and code bloat — not to mention the question whether the code was copied correctly (since it all had to be done by hand).

These days, we can define a function once, and then call it repeatedly, passing in different arguments each time. But there is more variation than you might think in what it means to “pass arguments” in a function call.

Fortunately, there are only a handful of different approaches that are commonly used. By learning to recognize these approaches now, then when you learn new programming languages in the future (and you will!) it will be a matter of moments to identify the standard parameter-passing technique or techniques that are being used.

As a running example, we will assume a function with formal parameter p

    void f(int p) { ... }

that can be called with an actual argument a

    f(a)

So: what is the relationship between the argument a and the parameter p?

1. Call by Value

Call by value is the only parameter-passing method supported in C or Java, and is the default parameter-passing method in many other languages.

In call by value in a typical compiled language, each parameter is initialized with a copy of the value of the actual argument. Otherwise, function parameters are just like any of the function’s other local variables.

In the case of f, then, its parameter p is a local variable with its own space in memory (probably on the stack, since that’s the usual implementation for compiled local variables). If we call f(a), then the value of a is copied into that location before the function starts running. If we call f(3+z), then the value of expression 3+z is copied into the stack location for p before the code for f starts running, and so on.

Since p is its own variable, initialized with a copy of the argument, if we call f(a) and the code for the function f assigns to its local variable p, the assignment has no effect on a.

In a call by value language, a function cannot modify the values of its actual arguments. For example, we cannot write an increment function so that the call increment(x) would increase the value of variable x by one. The increment function would have access to a copy of the contents of variable x, but not to x itself.

On the other hand, if argument a is a pointer (the address of a data object in memory) and we pass a by value, then the parameter p will be a copy of a pointer, i.e., p will also contain the address of the same data object. We know that if f overwrites the pointer p with a different value, that will have no effect on the original pointer a. But if f modifies not p but the data at address p, that is the same as modifying the data where a points, and this change will persist when the function returns and pointer p disappears.

2. Call by Reference

Call by reference was the only parameter-passing method in traditional Fortran. It is optional in several modern languages, including C++ (if the parameter is declared with a & reference type) and C# (if the parameter is declared with the ref keyword).

In call by reference, the function parameter p is not an ordinary local variable with its own memory storage. Instead, in each function call the parameter p stands for (is an “alias” for) the original variable or value being passed.

So if we call f(a), then while f is running, the parameter p is just another name for the variable a. Every time the function changes p, that directly, immediately modifies the contents of variable a.

Call-by-reference functions have direct access to their actual arguments, so there’s no problem writing an increment function where the call increment(x) would increase the value of variable x.

If (still in call-by-reference) we call f(2), then while f is running, the parameter p is just another name for the place in memory where a copy of the value 2 is stored. (There are horror stories of old Fortran programs “modifying the value of 2 at run-time”, because someone called f(2) and then function f assigned a different value to its parameter p, overwriting the copy of 2 in memory with a different number. If the system was using that number 2 in memory for multiple purposes, overwriting it could lead to some very weird behavior.)

When a call-by-reference function writes to its parameter, the value of the argument passed by the caller imediately changes; there’s no delay, because the parameter is the same as the argument.

Now under the hood, call by reference is usually implemented using call by value and pointers. The function is given not a copy of the argument value, but a copy of the address of the argument value. The code for the function then knows that its parameter value is not the address it was given, but the value located at the given address.

A similar approach is used to simulate call by reference in the call by value language C. For example, this code doesn’t zero out variable a,

   void setToZero(int p) { 
      p = 0; 
   }
   
   int a = 42;
   setToZero(a);   // zeroing a copy of a does not change a.

but this code does:

   void setToZero(int* p) {   // argument is an address
      *p = 0;   // zero out memory at that address;
   }

   int a = 42;
   setToZero(&a);  // if we copy the address of a, the function can zero it.

However, if you’re not trying to simulate call by reference, but rather to use call by reference, then thinking about implementation details and pointers is more likely to be confusing that to be helpful! Just remember that in call by reference the formal parameter is an alias (alternate name) for the actual argument, and you will understand the behavior of code.

3. Call by Result

Call-by-result parameter passing only makes sense for “output only” parameters, where data is being transferred from the function back to the caller. No general-purpose programming language would use only call by result; because you wouldn’t be able to get any data into functions!

Like call by value (and unlike call by reference), the function parameter p is just a local variable in the function. Unlike call by value, when we call f(a) and the function f starts running, the value of the argument a is not copied into variable p. Depending on the details of the programming language, either p starts out uninitialized, or starts out with a default value like 0.

In fact, argument a is totally ignored until the very end of the function call, when f returns. At that point, we copy the final value of the parameter variable p back into the argument a.

Thus, call by result is the dual of call by value. In call by value, the argument a is assigned to (has its value copied into) the parameter variable p when the function starts running, and then a is ignored thereafter. In call by result, the argument a is ignored until the function completes, at which point the parameter p is assigned to (has its value copied back into) the argument a.

4. Call by Value-Result

Call by value-result is the union of call by value and call by result. Again, the function parameter p is an independent variable local to the function. When we make a call f(a), we start out as in call by value by copying the value of a into local variable p. Then we run the code for the function. When it is done, we finish as in call by result by copying the final value of p back into a.

Call by value-result and call by reference often have the same effects. In both cases, if we make the call f(a) and the function f modifies its parameter variable p, then when the call is over, the argument a has changed.

There is one difference though: in call by reference, when we call f(a) and f writes to its parameter p, the argument a changes immediately. (This change can be visible if, for example, a is a global variable that the function can access both as the global variable and as the function parameter.) In contrast, in call by value-result, when we call f(a) and f writes to its parameter p, the argument a doesn’t change until the function finally returns.

5. Call by Macro

In call by macro, a function call behaves as if we took the function’s code and used search-and-replace to replace uses of the parameter(s) with copies of the code for the argument(s). Such sorts of “functions” are the macros created with #define in C and C++ (really, the C Preprocessor).

Macros can have tricky or unexpected behavior. For example, if we have the function

    int g(int p) {
       int a = 7;
       int x = p;
       int y = p;
       return (x*y)*p;
    }

then the call g(1+h(a)) behaves exactly like

    {
       int a = 7;
       int x = 1+h(a);
       int y = 1+h(a);
       return (x*y)*1+h(a);
    }

First, the argument 1+h(a) gets recomputed each time the macro uses its parameter p; if function h has side-effects, these are repeated each time the parameter is used. (This is also true in call-by-name, below.)

Second, the argument 1+h(a) is substituted by copy-and-paste; whereas in any other calling convention the call 1+h(a) would refer to the value of variable a that was in scope at the call site, in call by macro we have the possibility of variables in the argument being captured by local variables in the macro. In this example, the function h is applied to 7 instead of the value of a around at the function call. Worse, because it’s textual copy and paste, the return value is not the argument multiplied by (x*y), but rather x*y added to h(7).

Note: This particular example, g(1+h(a)) will not compile with our calling-convention translator. Instead, we must use simple expressions as arguments to functions. Things like variables and the ++ operator should work, and can produce the effects that will be useful for testing.

6. Call by Name

Call by name originated in Algol 60, a language whose design (except for its parameter passing) has directly or indirectly influenced nearly every modern programming language.

Call by name is just like call by macro, but using “capture avoiding” substitution when we replace the parameter by the actual arguments. Local variables are automatically “renamed” out of the way, to make sure that they don’t interfere with the parameter values. Further, there are implicit parentheses inserted when substituting in arguments (or equivalently, the substitution is happening at the level of abstract syntax trees, as we did in our cbn interpreter).

So given the function g above, under call by name the call g(1+h(a)) is equivalent to

    {
       int local_a = 7;
       int x = (1+h(a));
       int y = (1+h(a));
       return x*y*(1+h(a));
    }

where we have automatically renamed a to local_a (any name would have worked, as long as we avoid the free variables of the arguments to this function call).

Otherwise, call by name is like call by macro in that the argument is re-evaluated every time it is used (possibly causing side-effects like assignments or I/O each time). For both, if the function doesn’t use the value of a parameter, then the corresponding argument is not computed even once.

Just as call by reference can be simulated in call by value by passing pointers (where the callee knows to follow the pointer when it needs the argument value), call by name can often be simulated in call by value by passing functions (where the callee knows to call the function every time it needs the argument value).

A few languages (including Scheme) offer “hygienic” macros that correctly rename local variables to avoid variable capture; this is another way to get call by name behavior. You have also seen call by name behavior in our $\lambda$-calculus interpreter.

7. Call by Need

Call by need is familiar from Haskell. It is like call by name in that parameters are only evaluated if/when they are used (and there are no weird variable captures like call by macro). But unlike call by name, call by need “memoizes” arguments; after the first time the argument is used (and evaluated), the result is saved. All future uses of the parameter reuse the saved value.

Languages that use call by need are almost always “purely functional”, meaning that evaluating expressions does not have side-effects. (Combining side-effects with implicitly memoized parameters gets weird very quickly.) If there are no side-effects, then there’s no way to tell whether the function argument is evaluated once or many times, because you get the same value. Therefore, in the absence of side-effects, call by name and call by need always produce the same result, with the only difference being how much time it takes to get that result.