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

Question

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

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

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

Call-by-name is 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 some interesting examples of using call by name. Here is one of them:

real procedure Sum(k, l, u, ak)
     value l, u;
     integer k, l, u;
     real ak;
     comment k and ak are passed by name;
 begin
     real s;
     s := 0;
     for k := l step 1 until u do
         s := s + ak;
     Sum := s
 end;

In the procedure, the index variable k and summation term ak are passed by name. Call by name enables the procedure to change the value of the index variable during execution of the for loop. Call by name also causes the ak argument to be reevaluated during each iteration of the loop. Typically, ak will depend upon the changing (side-effected) k.

For example, code to compute the sum of the first 100 terms of a real array V[] would be:

Sum(i, 1, 100, V[i]).

Answer 3

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 4

Actually, call-by-name, is not just a historical curiosity. You can do call-by-name in Windows batch files (and myriad of other scripting languages). Knowing how it works, and how to use it effectively in programming can open up neat solutions to problems. I know it is only passing strings through for later expansion, but it can be manipulated to have similar effects as call-by-name.

call :assign x 1
exit /b
:assign
setlocal enabledelayedexpansion
(endlocal
:: Argument 1 is the name of the variable
set %1=%2
)
exit /b

Answer 5

ALGOL was designed for mathematical algorithms. I like the summation function as an example of call by name.

Sorry my ALGOL is a bit rusty the syntax is probably not right.

.FUNCTION SUM(var,from,to,function)
.BEGIN
  .REAL sum =0;
  .FOR var = from .TO to .DO sum = sum + function;
  return sum;
.END

You could than use sum like

  Y = sum(x,1,4,sum(y,3,8,x+y));

In the above the inner sum(y,3,8,x+y) would generate an unnamed function to pass to the outer sum call. The variables x and y are not passed by value but by name. In the case of variables call by name is equivalent to call by address reference in C. It gets a bit confusing when recursion is involved.

Borrows made ALGOL machines. They had 48 bit word memory with 3 flag bits. The flag bits implemented the cal by name of ALGOL. it was a stack machine so when function was loaded onto the stack the call by name fag would cause it to be called. The compiler would generate unnamed functions when expressions were used as arguments. A variable would be a simple indirect reference. An error would occur writing to a function.

Answer 6

I know I'm joining late to the club and this is not necessarily an answer, but I did want to add one thing that could help clarify a little. I've always thought of the Algol pass-by-name as a similar process to when the C++ preprocessor directives (macros, specifically) replaces the name of some function/variable with the the actual piece of code during compile time. The pass-by-name essentially replaces the name of the formal parameter with the actual parameter, and executes. I've never written in Algol, but I hear that pass-by-name will have the same result as C++'s pass-by-reference.

Answer 7

You can pass "name" in the symbolic form of a variable which allows it to be both updated and accessed simultaneously. As an example lets say you want to triple a variable x which is of type int :

start double(x);
real x;
begin
x : = x * 3
end;

Answer 8

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.