What is "pass-by-name" and how does it work exactly?

Question

I've check wikipedia, and googled but I still can't wrap my mind around how pass-by-name works in ALGOL 60.

Thanks!

Answer 1

I found a good explanation at Pass-By-Name Parameter Passing. Essentially, the body of a function is interpreted at call time after textually substituting the actual parameters into the function body. In this sense the evaluation method is similar to that of C preprocessor macros.

By substituting the actual parameters into the function body, the function body can both read and write the given parameters. In this sense the evaluation method is similar to pass-by-reference. The difference is that since with pass-by-name the parameter is evaluated inside the function, a parameter such as a[i] depends on the current value of i inside the function, rather than referring to the value at a[i] before the function was called.

The page I linked above has some more examples of where pass-by-name is both useful, and dangerous. The techniques made possible by the pass-by-name are largely superseded today by other, safer techniques such as pass-by-reference and lambda functions.

Answer 2

For those in the future:

Concepts in Programming Languages by John C. Mitchell was also helpful.

Pass-by-Name. Perhaps the strangest feature of Algol 60, in retrospect, is the use of pass-by-name. In pass-by-name, the result of a procedure call is the same as if the formal parameter were substituted into the body of the procedure. This rule for defining the result of a procedure call by copying the procedure and substituting for the formal parameters is called the Algol 60 copy rule. Although the copy rule works well for pure functional programs, as illustrated by β reduction in lambda calculus, the interaction with side effects to the formal parameter are a bit strange. Here is an example program showing a technique referred to as Jensen's device: passing an expression and a variable it contains to a procedure so that the procedure can use one parameter to change the location referred to by the other:

---

 begin integer i;
        integer procedure sum(i, j);
            integer i, j;
                comment parameters passed by name;
            begin integer sm; sm := 0;
                for i := 1 step 1 until 100 do sm := sm + j;
                sum := sm
            end;
        print(sum(i, i*10 ))

end

In this program, the procedure sum(i,j) adds up the values of j as i goes from 1 to 100. If you look at the code, you will realize that the procedure makes no sense unless changes to i cause some change in the value of j; otherwise, the procedure just computes 100*j. In the call sum(i, i*10) shown here, the for loop in the body of procedure sum adds up the value of i*10 as i goes from 1 to 100.

Answer 3

Flatlander has an illuminating example of how it works in Scala here. Suppose you wanted to implement while:

def mywhile(condition: => Boolean)(body: => Unit): Unit =
  if (condition) {
    body
    mywhile(condition)(body)
  }

We can call this as follows:

var i = 0
mywhile (i < 10) {
  println(i)
  i += 1
}

Scala is not Algol 60, but maybe it sheds some light.

Answer 4

I'm assuming you mean call-by-name in ALGOL 60.

Call-by-name similar to call-by-reference in that you can change the value of the passed in parameter. It differs from call-by-reference in that the parameter is not evaluated before the procedure is called but is instead evaluated lazily. That is, it is evaluated when and only when the parameter is actually used.

For example, suppose we have a procedure f(x, y) and we pass it i and i/2 where i is initially equal to 10. If f sets x to 42 and then evaluates y it will see the value 21 (whereas with call by reference or call by value it would still see 5). This is because the expression "i/2" isn't evaluated until y is evaluated.

In many ways this appears to behave like a literal text-substitution of the parameters (with renaming to avoid name conflicts). In practice, however, this is implemented using "thunks" (basically closures) for the passed in expressions.

The Wikipedia article on Jensen's Device shows an interesting example of using call by name. In particular, pay attention to how the "term" parameter is used.