MCS-287 Notes for EOPL Section 6.5 (Spring 2000)

Although call-by-name is best-known for its use in Algol 60 (a very influential language), you should understand this is something of a historical dead-end. Later successor languages derived from Algol 60, such as Pascal and Algol 68, abandoned call-by-name. Even within the Algol 60 committee, the original plan had been for call-by-reference and call-by-value to be the two options, rather than call-by-name and call-by-value. To the very end, some members of the committee preferred call-by-reference, but they were having difficulty formulating a simple, correct specification of it. Other committee members put forward a specification of call-by-name as an alternative, on the last day of the committee meeting. It isn't clear whether everyone understood that what was being suggested was a different parameter passing mechanism, rather than just a different specification of call-by-reference. The proposal was adopted, in the last hour of the last day, but according to Peter Naur, "it seemingly was understood in a coherent manner only by one member, Alan Perlis." ("The European Side of the Last Phase of the Development of Algol 60," in History of Programming Languages, Richard L. Wexelblat, ed., Academic Press, 1991, pp. 111-112.)

On the other hand, although call-by-name is now dead in imperative languages (those employing effects, such as variable assignment, data structure mutation, and direct I/O), it is alive and well in purely functional languages, such as Haskell. Actually these languages typically use call-by-need, but given the purely functional context, this is just an optimization: there is no way to distinguish call-by-name and call-by-need, except by speed. (In the presence of effects, this isn't true.) In the functional programming community, some alternative nomenclature is frequently used: call-by-value is called "eager evaluation," call-by-name is called "lazy evaluation," and call-by-need is called "fully lazy evaluation."

Regarding the etymology of the term "thunk":

There are a couple of onomatopoeic myths circulating about the origin of this term. The most common is that it is the sound made by data hitting the stack; another holds that the sound is that of the data hitting an accumulator. Yet another suggests that it is the sound of the expression being unfrozen at argument-evaluation time. In fact, according to the inventors, it was coined after they realized (in the wee hours after hours of discussion) that the type of an argument in Algol-60 could be figured out in advance with a little compile-time thought, simplifying the evaluation machinery. In other words, it had "already been thought of"; thus it was christened a "thunk", which is "the past tense of `think' at two in the morning".
(Eric Raymond, The New Hacker's Dictionary, The MIT Press, 1991, p. 350. See also the Jargon File on the web.)

On page 202 the Array Element type makes a reappearance from Section 6.2, and just like there, we can eliminate it since we have an Array ADT that supports the array-cell operation. We can simply equate

L-value = Cell(Expressed Value)

The expression type local is similar to let except that it remains "call-by-value" even when let is changed to call-by-name. (Since let is defined in terms of procedure application, it follows the prevailing parameter passing mechanism.) Incidentally, local would also be handy with Section 6.2's call-by-reference interpreter, for the same reason. For a somewhat contrived example,

local x = 3
 in let y = x
     in begin
          y := +(y, 1);
          *(x, y)
evaluates to 16 under call-by-reference or call-by-name, since y is an alias for or thunk for x, so y := +(y,  1) increments x. If we instead write
local x = 3
 in local y = x
     in begin
          y := +(y, 1);
          *(x, y)
then we get 12 regardless of the parameter passing mechanism, because y is a new variable. (The outer local could be a let in the case of call-by-reference or call-by-need, without the values changing any. However, in the case of call-by-name, the version with the outer and inner blocks both being let evaluates to 9, due to the subtlety described in the next paragraph.)

The call-by-name interpreter described in EOPL does something very counter-intuitive if you assign to a formal parameter when the actual parameter wasn't a variable. For example, consider

let p = proc(x)
           x := 5;
 in p(3)
This evaluates to 3, not 5. Each of the two places where x is used in the procedure body is replaced by a new cell containing 3. The first cell is updated to 5, but the second cell still contains 3. In Algol 60, this program would simply be illegal: it isn't allowed to pass in a non-variable argument if the formal parameter is assigned to in the procedure body. But under EOPL's rules, this program is legal, just surprising. Another surprising program would be the one shown in Exercise 6.5.2 at the bottom of page 205. Notice that this issue affects let as well, since let is just a shorthand for procedure application. That leads to the surprising value of 9 in the previous example of
let x = 3
 in let y = x
     in begin
          y := +(y, 1);
          *(x, y)
Also, note that this has a serious consequence for the implementation of letrec or letrecproc. Expanding either of these out into a let of the names to some dummy values and then in the body assigning the names new values won't work. Instead, you will need to expand letrec or letrecproc into a local

To understand the interpreter implementation in this section, it helps to know that only the indirect array model is considered.

For Figure 6.5.2, page 204, we can use the following replacements:

Exercise 6.5.4, page 206, introduces Jensen's device in the context of approximating definite integrals, but it can be simplified to just summing a function over a range, e.g., the sum for k from 1 to 10 of k2. In Scheme we would write

(define from-to-sum
  (lambda (low high f)
    (if (> low high)
        (+ (f low)
           (from-to-sum (+ low 1) high f)))))

(from-to-sum 1 10 (lambda (k) (* k k)))
We could translate this directly into Ted, using proc in place of lambda, getting
fromToSum(1, 10, proc(k) *(k, k))
But Jensen's device tells us that in the call-by-name variant of Ted (or, originally, in Algol 60), we can dispense with the proc and write
forFromToSum(k, 1, 10, *(k, k))
with a suitable definition of forFromToSum, which repeatedly evaluates its fourth argument (here *(k, k)), with its first argument (here k) set to each value in the range specified by the second and third arguments. As I mentioned earlier, this is a historical curiosity.

Finally, note that Section 6.5's discussion of call-by-name and call-by-need assumes that when any primitive procedure is applied, the argument denoted values (thunks or memos) are first converted to expressed values. (This is done in apply-proc, which still remains unchanged from Figure 6.1.2, page 182.) This policy is known as having strict primitive procedures.

We can usefully change cons to be non-strict, so that it builds a pair of denoted values (thunks or memos) instead of a pair of expressed values. We can then change car and cdr to convert the denoted values to expressed values when they are accessed. (This particularly is viable, from an efficiency standpoint, if call-by-need memos are used rather than call-by-name thunks.)

By making this simple change, it becomes possible to make infinitely large data structures, so long as we only ever look at finitely much of them. For example, the following expression make an infinitely long list of all the positive integers, and then selects the third element of that list (3).

letrec intsFrom = proc(low) cons(low, intsFrom(+(low, 1)))
  in local positiveIntegers = intsFrom(1)
       in car(cdr(cdr(positiveIntegers)))
This would make a fun project, if you are looking for an extra challenge.