Call by Name*
Explicit subroutine parameters are not the only language feature that
requires a closure to be passed as a parameter. In general, a language
implementation must pass a closure whenever the eventual use of the
parameter requires computation that depends on the actual parameter or
on the context in which it was passed (i.e., for which a compiler
cannot generate code that will work for all parameters). An interesting
example occurs in the call by name parameters of Algol 60 and
Simula.
When Algol 60 was defined, most programmers programmed in assembly
language (Fortran was only a few years old, and Lisp was even newer).
The assembly languages of the day made heavy use of macros, and it was
natural for the Algol designers to propose a parameter-passing
mechanism that mimicked the behavior of macros.
A call by name parameter is re-evaluated in the caller's referencing
environment every time it is used. The effect is as if the called
routine had been textually expanded at the point of call, with the
actual parameter (which may be a complicated expression) replacing
every occurence of the formal parameter. To avoid the usual problems
with macro parameters, the "expansion" is defined to include
parentheses around the replaced parameter wherever syntactically valid,
and to make "suitable systematic changes" to the names of any formal
parameters or local identifiers that share the same name, so that their
meanings never conflict [NBB+63, p. 12]. Call by name is the default in
Algol 60; call by value is available as an alternative. In Simula call
by value is the default; call by name is the alternative.
To implement call by name, Algol 60 implementations pass a hidden
subroutine that evaluates the actual parameter in the caller's
referencing environment. The hidden routine is usually called a
thunk.
In most cases thunks are trivial. If an actual parameter is a variable
name, for example, the thunk simply reads the variable from memory. In
some cases, however, a thunk can elaborate. Perhaps the most famous
occurs in what is known as Jensen's device, named after
Jørn
Jensen [Rut67]. The idea is to pass to a subroutine both a built-up
expression and one or more of the variables used in the expression.
Then by changing the values of the individual variable(s), the called
routine can deliberately and systematically change the value of the
built-up expression. This device can be used, for example, to write a
summation routine:
real procedure sum (expr, i, low, high);
value low, high;
comment low and high are
passed by value;
comment expr and i are passed
by name;
real expr;
integer i, low, high;
begin
real rtn;
rtn := 0;
for i := low step 1 until high do
rtn := rtn + expr;
comment the value of expr
depends on the value of i
sum := rtn
end sum
Now to evaluate the sum
y = ∑
3x² - 5x + 2
1≤x≤10
we can simply say
y := sum(3*x*x - 5*x + 2, x, 1, 10);
In practice, such clever uses of call by name are rather rare, and can
be imitated in other languages by use of formal subroutines. At the
same time, the cost of calling thunks on every use of a formal
parameter proved to be prohibitive, and call by name was dropped in
Algol 68.