Jensen's device
Jensen's device is a computing technique which exploits quirks of call-by-name
(ALGOL 60 style, not the other one, see
call-by-name vs. call-by-name
for more details) and internal side-effects (see
on impurity (and Haskell) for details).
The following is pseudo ALGOL 60 (assume that all arguments are passed by
name):
real procedure Sum(int id_var, int from, int to, real expr)
begin
real s := 0;
for id_var := from step 1 until to do
s := s + expr;
Sum := s;
end;
Sum(i, 1, 100, V[i]);
We can evaluate the function call by replacing each occurrence of the
arguments in the body by the appropriate input. Indeed, call-by-name behaves
just like call-by-macro in the above (this is not the case in
general; see call-by-macro vs. call-by-name
for details).
real procedure Sum(id_var = i, from = 1, to = 100, expr = V[i])
begin
real s := 0;
for id_var i := from 1 step 1 until to 100 do
s := s + expr V[i];
Sum := s;
end;
The core of the trick is that expr can reference
id_var (and that id_var is
treated as a variable name and not as a value).
Notes:
-
There is no good reason for passing from and
to by name here; ALGOL 60 is the main language
that implements call-by-name, but it also supports call-by-value (a
single function could have both some passed-by-value and some
passed-by-name arguments, although the former is the default)
-
Building more complex functions is easy, e.g.:
-
Sum(i, 0, m, Sum(j, 0, n, A[i,j])): summation of 2D arrays
-
Sum(i, 0, m, i*i): sum of consecutive squares
-
In modern languages, lambdas can do similar tricks in a more principled
manner