Oppimateriaalin copyright © 2007 Arto Wikla. Tämän oppimateriaalin käyttö on sallittu vain yksityishenkilöille opiskelutarkoituksissa. Materiaalin käyttö muihin tarkoituksiin, kuten kaupallisilla tai muilla kursseilla, on kielletty.
(Muutettu viimeksi 14.2.2007)

Call-by-name & Jensen's Device

[Selitys Scottin kirjan vanhasta painoksesta (kiitos Pietu Pohjalaisen):]

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 o be prohibitive, and call by name was dropped in Algol 68.



Takaisin sisältösivulle.