Jensen's device
Jensen's device is a computer programming technique devised by Danish computer scientist Jørn Jensen for the ALGOL 60 programming language, exploiting its call-by-name parameter passing mechanism to enable the repeated evaluation of expressions tied to a loop variable within a procedure.[1] The device allows for concise implementation of iterative computations, such as summing a series where each term depends on an external variable updated during iteration, without embedding the loop logic directly in the calling code. A classic example computes the 100th harmonic number (approximately 5.187) by calling a generic summation procedure with the bound variable i, the range 1 to 100, and the term 1/i, all passed by name except the fixed limits.[2]
In ALGOL 60, call-by-name treats the actual parameter as a textual substitute for the formal parameter, re-evaluating it each time the formal is referenced inside the procedure body, which effectively makes the term a function of the bound variable. This is demonstrated in the following ALGOL 60 code for the summation procedure:
real [procedure](/page/Procedure) sum(n, term); integer n; real term;
value n;
begin
integer i; real s;
s := 0;
for i := 1 step 1 until n do s := s + term;
sum := s
end
real [procedure](/page/Procedure) sum(n, term); integer n; real term;
value n;
begin
integer i; real s;
s := 0;
for i := 1 step 1 until n do s := s + term;
sum := s
end
When invoked as sum(100, 1/i), the expression 1/i is substituted and re-evaluated for each value of i from 1 to 100, yielding the correct harmonic sum. If the term were passed by value instead, it would evaluate only once using the uninitialized i from the caller, leading to undefined or erroneous results (such as division by zero or garbage values).[2]
Jensen's device, first documented around the development of early ALGOL 60 implementations, served as a benchmark for compiler correctness and highlighted the power—and potential inefficiency—of call-by-name, as each evaluation incurs overhead similar to macro expansion. It influenced discussions on parameter passing in subsequent languages, though call-by-name was largely abandoned in favor of call-by-value or call-by-reference due to performance concerns.[3] Modern emulations appear in languages like C++ using templates or lambdas to approximate the behavior.[2]
Background
Call-by-Name Parameter Passing
Call-by-name parameter passing is an evaluation strategy in which the argument expression provided to a function is not evaluated prior to the function call; instead, the actual parameter is textually substituted for each occurrence of the corresponding formal parameter within the function body, with evaluation occurring only when the substituted expression is needed during execution.[4] This substitution effectively delays the computation of the argument until its value is required, treating the parameter as a symbolic name that is resolved in the caller's context each time it is referenced.[5]
In contrast to call-by-value, where arguments are fully evaluated before the call and a copy of the resulting value is passed to the function—ensuring no side effects on the original arguments—call-by-name avoids premature evaluation, potentially leading to multiple computations of the same expression if the parameter is used more than once.[6] Unlike call-by-reference, which passes the memory address of the argument to allow direct modification of the original variable without re-evaluation, call-by-name performs fresh evaluations of the substituted expression in the caller's environment, which can introduce inconsistencies if the expression involves side effects or mutable state.[4]
A key feature of call-by-name is that it permits the argument expression to be re-evaluated each time the formal parameter is encountered, which can result in different values if the expression depends on changing variables or produces side effects, such as incrementing a counter or modifying global state.[5] This lazy evaluation mechanism is often implemented using thunks—unevaluated closures that capture the argument expression for deferred computation.[6]
To illustrate, consider a simple procedure defined as follows in pseudocode:
procedure double(x);
x := x * 2
end
procedure double(x);
x := x * 2
end
When called with double(a + b), the call-by-name strategy substitutes the expression a + b directly for x in the body, yielding the effective code (a + b) := (a + b) * 2. Here, a + b is evaluated twice—once for the right-hand side and once for the left-hand side assignment—potentially yielding different results if a or b changes between evaluations.[4]
Historical Context in ALGOL 60
ALGOL 60 emerged from an international collaborative effort in the late 1950s and early 1960s, spearheaded by the Association for Computing Machinery (ACM) in the United States and the Gesellschaft für Angewandte Mathematik und Mechanik (GAMM) in Europe, aimed at establishing a standardized language for expressing algorithms in a machine-independent manner. The project built upon the earlier International Algebraic Language (IAL) proposal from the 1958 Zurich conference, involving delegates from multiple countries who convened key meetings, including the pivotal Paris conference in January 1960, to refine the language's syntax and semantics.[7] This standardization drive addressed the proliferation of machine-specific programming languages, seeking to create a universal tool for scientific and mathematical computation.[8]
A deliberate design choice in ALGOL 60 was the inclusion of call-by-name parameter passing alongside call-by-value, selected to facilitate the direct translation of mathematical expressions into code and to enable forms of delayed or lazy evaluation, drawing conceptual inspiration from lambda calculus principles of substitution. This mechanism allowed procedures to treat formal parameters as textual substitutes for actual arguments, promoting expressiveness in algorithmic descriptions without premature evaluation, though it introduced complexities in implementation.[9] The feature was formalized during the Paris revisions to resolve ambiguities in parameter handling from the IAL draft, ensuring compatibility with recursive and block-structured programming.[7]
Peter Naur, a Danish computer scientist, served as the editor of the seminal ALGOL 60 Report, published in May 1960 in Communications of the ACM, which provided a rigorous, formal definition of the language using his refined Backus-Naur Form (BNF) notation.[10] Early implementations followed swiftly, including the GIER ALGOL compiler developed by Regnecentralen in Copenhagen for the GIER computer, released in 1962 and notable for its faithful handling of ALGOL 60's advanced features like recursion and parameter passing.[11]
In the early 1960s, Danish programmer Jørn Jensen, working at Regnecentralen alongside Naur on the GIER compiler, began exploring innovative applications of call-by-name, leading to the devising of what would later be known as Jensen's device as a technique for efficient numerical computations through parameter substitution.[1] This work highlighted the practical potential of ALGOL 60's design choices in real-world programming challenges.[8]
Core Mechanism
Thunk-Based Evaluation
In the implementation of call-by-name parameter passing, a thunk serves as a delayed computation mechanism, essentially a subroutine or closure that encapsulates an unevaluated expression from the actual parameter. This structure allows the expression to be evaluated dynamically only when the corresponding formal parameter is referenced within the procedure body, capturing the current state of variables at each invocation. Thunks thus enable the re-evaluation of parameters on each use, distinguishing call-by-name from eager evaluation strategies like call-by-value.[12]
The process begins at procedure invocation, where each call-by-name argument is transformed into a thunk by the compiler or translator. This thunk is generated as an implicit subroutine that, upon activation, computes and returns the value of the original expression under the prevailing bindings. For instance, if the actual parameter is an expression involving variables that may change during execution, such as the local loop variable in a summation, the thunk ensures fresh computation each time, which can introduce side effects if the expression modifies shared state. In ALGOL 60 implementations, thunks are often represented as code blocks with entry and exit operations, such as block entry (BE) and end implicit subroutine (EIS), facilitating recursive activations without premature evaluation. In the classic Jensen's device, the thunk evaluates the term in the procedure's environment, resolving references like the local index variable.[12]
To illustrate, consider a procedure declaration like:
real [procedure](/page/Procedure) sum(low, high, expr);
value low, high;
[integer](/page/Integer) low, high;
real expr;
begin
[integer](/page/Integer) i; real s;
s := 0;
for i := low step 1 until high do
s := s + expr;
sum := s
end
real [procedure](/page/Procedure) sum(low, high, expr);
value low, high;
[integer](/page/Integer) low, high;
real expr;
begin
[integer](/page/Integer) i; real s;
s := 0;
for i := low step 1 until high do
s := s + expr;
sum := s
end
Here, expr is treated as a thunk. When the procedure body references expr inside the loop, the thunk is executed anew for each iteration, substituting the current value of the local i into the original expression (e.g., called as sum(1, 100, 1/i)). This substitution occurs at runtime, preserving the semantics of call-by-name.[12]
This thunk-based approach bears a close relation to the lambda calculus, where thunks function analogously to unevaluated lambda abstractions that bind free variables from the calling environment. Peter Landin's semantic mapping of ALGOL 60 constructs to Church's lambda notation highlights this correspondence, portraying call-by-name parameters as lambda expressions delayed until application, thereby providing a formal foundation for the delayed evaluation thunks implement.
Parameter Substitution and Side Effects
In Jensen's device, the core mechanism relies on call-by-name parameter passing, where the actual parameter expression is textually substituted into the procedure body each time the formal parameter is referenced, rather than being evaluated once at the call site. This substitution occurs dynamically during execution, allowing the procedure to treat the parameter as if it were inline code. For instance, consider a summation procedure defined as:
real [procedure](/page/Procedure) sum(n, [term](/page/Parameter));
value n;
integer n;
real [term](/page/Parameter);
begin
integer i; real s;
s := 0;
for i := 1 step 1 until n do s := s + [term](/page/Parameter);
sum := s
end
real [procedure](/page/Procedure) sum(n, [term](/page/Parameter));
value n;
integer n;
real [term](/page/Parameter);
begin
integer i; real s;
s := 0;
for i := 1 step 1 until n do s := s + [term](/page/Parameter);
sum := s
end
When invoked as sum(100, 1/i), the formal parameter term is replaced by 1/i in the procedure body. The for loop defines a local i iteratively, and each evaluation of term reflects the current value of i, effectively computing the sum \sum_{i=1}^{100} 1/i.[13]
The key innovation of this approach lies in its ability to enable the substituted expression term to depend on the local index variable i or other constructs within the procedure, which can itself contain conditional or nested computations that further alter state. This dynamic re-evaluation during the loop iterations allows for sophisticated behaviors, such as skipping terms or incorporating dependencies that would be cumbersome in call-by-value languages. Call-by-name is typically implemented using thunks—delayed computations that encapsulate the parameter expression—but the substitution model directly facilitates these modifications without requiring explicit passing of mutable references. A generalization passes the index by name (e.g., sum(k, 1, 100, a[k]) where k is a caller's variable), allowing non-local modification but introducing side effects on the caller.[13]
However, this substitution introduces significant side effects, as multiple evaluations of the parameter can unexpectedly alter external program state. For example, if term includes assignments or procedure calls that modify variables outside the summation loop, such as incrementing a global counter or changing array elements based on the current i, the overall computation may deviate from intuitive expectations, leading to non-deterministic or erroneous results depending on the order of evaluations. In full ALGOL 60, function designators and procedures permit such alterations to external variables, exacerbating these issues, whereas the language's SUBSET restricts side effects to promote predictability.[13]
Examples
Basic Array Summation
The canonical example of Jensen's device involves a procedure that computes the sum of array elements from a lower to an upper bound, leveraging call-by-name parameter passing to substitute and re-evaluate the index variable and term expression within the loop.[14]
In ALGOL 60, this is implemented as follows:
real procedure sum(i, low, high, expr);
value low, high;
integer i, low, high;
real expr;
begin
real s;
s := 0;
for i := low step 1 until high do
s := s + expr;
sum := s
end
real procedure sum(i, low, high, expr);
value low, high;
integer i, low, high;
real expr;
begin
real s;
s := 0;
for i := low step 1 until high do
s := s + expr;
sum := s
end
This procedure defines i and expr as call-by-name parameters, while low and high are passed by value; the loop increments i from low to high in steps of 1, accumulating the value of expr each time.[14] A call such as result := [sum](/page/Sum)(j, 1, n, a[j]) substitutes the caller's variable j for the formal i and the expression a[j] for expr, enabling the summation \sum_{k=1}^{n} a_k without the procedure directly accessing the array.[15]
During execution, call-by-name substitution replaces each occurrence of the formal parameters with their actual arguments in the caller's context, causing re-evaluation on every access. For the call result := sum(j, 1, 3, a[j]) with array a = [1, 2, 3] and assuming j is a local integer variable initialized appropriately:
- The loop first assigns
j := 1 (substituting for i := low), evaluates expr as a[1] (yielding 1), and adds it to s (now s = 1).
- It then increments
j to 2, re-evaluates expr as a[2] (yielding 2), and adds it (s = 3).
- Finally,
j becomes 3, expr evaluates to a[3] (yielding 3), adding it to give s = 6.
- The procedure returns 6, stored in
result.
This process demonstrates how the index j updates across iterations due to textual substitution, effectively summing the array elements.[14][15]
Nested or Double Summations
Jensen's device can be extended to compute nested or double summations, such as the sum \sum_{i=1}^{m} \sum_{j=1}^{n} a[i,j], where a is a two-dimensional array, by using recursive calls to the summation procedure with indices passed by name. This approach demonstrates the technique's composability for multi-dimensional computations without directly passing array data to a single procedure.[12]
The caller invokes nested summations, such as total := sum(i, 1, m, sum(j, 1, n, a[i,j])), where i and j are dummy integer variables, m and n define the bounds, and a[i,j] is the term to sum. The inner sum computes \sum_{j=1}^{n} a[i,j] for the current i, and the outer sum aggregates those over i from 1 to m.[15]
During execution, ALGOL 60's call-by-name semantics perform textual substitution of the actual parameters into the procedure bodies each time they are referenced. For a fixed i, the inner loop varies j from 1 to n, evaluating a[i,j] with the current bindings, while the outer loop updates i and re-evaluates the inner sum. Changes to j in the inner call do not affect the outer i, enabling correct nested computation equivalent to explicit double loops. This recursive structure highlights the power of call-by-name for composing iterations.[12]
General Problem Solver (GPS) Application
In the paper "ALGOL 60 Confidential," Donald E. Knuth and Jack N. Merner introduced a procedure called the General Problem Solver (GPS) as a demonstration of ALGOL 60's call-by-name parameter passing mechanism, which underpins Jensen's device.[16] This GPS procedure exploits the delayed evaluation of formal parameters to enable iterative computations with side effects within a compact framework, allowing it to solve diverse problems by repeatedly substituting and evaluating expressions passed by name.[16] Unlike straightforward numerical summations, GPS facilitates more intricate tasks by treating parameters as thunks—unevaluated expressions—that can be dynamically referenced during execution, effectively simulating search-like behaviors through side effects.[16]
The procedure is defined as follows:
real [procedure](/page/Procedure) GPS(I, N, Z, V);
real I, N, Z, V;
begin
for I := 1 step 1 until N do Z := V;
GPS := 1
end
real [procedure](/page/Procedure) GPS(I, N, Z, V);
real I, N, Z, V;
begin
for I := 1 step 1 until N do Z := V;
GPS := 1
end
Here, the parameters I, N, Z, and V are passed by name, meaning they are substituted as expressions into the procedure body each time referenced, allowing side effects in V to update state like Z or external variables over N iterations.[16] A key example is matrix multiplication, where GPS is nested to compute C = A \times B:
for I := 1 step 1 until p do
for J := 1 step 1 until q do
C[I,J] := GPS(I, 1, C[I,J], 0) × GPS(K, n, 1, A[I,K] × B[K,J])
for I := 1 step 1 until p do
for J := 1 step 1 until q do
C[I,J] := GPS(I, 1, C[I,J], 0) × GPS(K, n, 1, A[I,K] × B[K,J])
More complex applications include finding the m-th prime by nesting GPS calls in conditional expressions within parameters to increment a candidate until it satisfies primality, leveraging recursive evaluation to explore values efficiently. The outcome is a concise framework for stateful computations like prime generation or linear algebra in a single procedure style, demonstrating how call-by-name transforms iteration into goal-oriented problem-solving and influencing concepts like lazy evaluation.[16]
Implementations
Simulation in C Using Macros
Jensen's device, originally a feature of ALGOL 60's call-by-name parameter passing, can be emulated in C—a strictly call-by-value language—through the use of preprocessor macros that perform textual substitution of expressions. This approach approximates the deferred evaluation of call-by-name by expanding the macro body with the actual parameter text each time it is referenced, effectively re-evaluating the expression in context during compilation.
A common example is a macro for computing the sum of an array or range, mimicking the summation procedure central to Jensen's device. The macro substitutes the expression parameter directly into a loop, allowing flexible operations like dot products or reciprocals without passing functions or lambdas. Consider the following definition in C:
c
#define SUM(Expr, Term, Lbound, Ubound, Inc, Total) \
for (Total = 0, Term = Lbound; Term <= Ubound; Term += Inc) \
Total += (Expr)
#define SUM(Expr, Term, Lbound, Ubound, Inc, Total) \
for (Total = 0, Term = Lbound; Term <= Ubound; Term += Inc) \
Total += (Expr)
To compute the dot product of two arrays a and b of length 7, one would invoke SUM(a[X]*b[X], X, 0, 6, 1, T); where T holds the result. The preprocessor replaces Expr with a[X]*b[X] and Term with X, expanding to a loop that evaluates the multiplication for each index X from 0 to 6, simulating the textual substitution of ALGOL 60's name parameters. Similarly, for summing reciprocals, SUM(1.0/a[X], X, 0, 6, 1, T); substitutes and evaluates the division anew each iteration.
This macro-based simulation differs fundamentally from true thunks in ALGOL 60, as the C preprocessor performs static textual replacement without runtime mechanisms for lazy evaluation or automatic variable renaming to avoid name clashes. Consequently, it lacks native support for deferred computation, potentially leading to inefficient multiple evaluations of side-effecting expressions and compile-time errors from identifier conflicts, unlike the dynamic thunk resolution in the original implementation.
The technique gained popularity in the late 1970s and 1980s for pedagogical purposes in early C programming texts, where macros illustrated advanced concepts like generic programming despite C's limitations.[3]
Support in Functional Programming Languages
Functional programming languages, particularly those with built-in support for lazy evaluation, provide native mechanisms that emulate the deferred computation and repeated evaluation aspects of Jensen's device without relying on explicit call-by-name parameters. In Haskell, lazy evaluation is implemented via call-by-need semantics, where unevaluated expressions are represented as thunks—suspended computations that are shared and evaluated only upon demand, avoiding the inefficiencies of call-by-name's multiple evaluations. This approach allows for seamless integration of delayed computations in summations and other iterative constructs, achieving similar expressive power to Jensen's device while maintaining purity and efficiency.
A representative example in Haskell demonstrates this through higher-order functions, where the summation term is passed as a lambda expression that is lazily applied within a list comprehension. Consider the following definition:
haskell
sumTerm :: (Int -> [Double](/page/Double)) -> [Int](/page/INT) -> [Int](/page/INT) -> [Double](/page/Double)
sumTerm term low high = sum [term j | j <- [low .. high]]
-- Usage for [harmonic](/page/Harmonic) series approximation
[harmonic](/page/Harmonic) :: [Int](/page/INT) -> [Double](/page/Double)
[harmonic](/page/Harmonic) n = sumTerm (\j -> 1.0 / fromIntegral j) 1 n
sumTerm :: (Int -> [Double](/page/Double)) -> [Int](/page/INT) -> [Int](/page/INT) -> [Double](/page/Double)
sumTerm term low high = sum [term j | j <- [low .. high]]
-- Usage for [harmonic](/page/Harmonic) series approximation
[harmonic](/page/Harmonic) :: [Int](/page/INT) -> [Double](/page/Double)
[harmonic](/page/Harmonic) n = sumTerm (\j -> 1.0 / fromIntegral j) 1 n
Here, the lambda \j -> 1.0 / fromIntegral j acts as a thunk-like delayed computation, evaluated for each j in the range without textual substitution, mirroring the effect of substituting the term into the loop body in ALGOL 60.
In Lisp variants, such as Common Lisp, native call-by-name is absent, but macros enable simulation of Jensen's device by performing hygienic expansion that wraps the term in a lambda, effectively creating a closure for repeated evaluation. For instance, a macro can define a summation form where the term is substituted and lambdafied:
lisp
(defun %sum (lo hi func)
(loop for i from lo to hi sum (funcall func i)))
(defmacro sum (var lo hi term)
`(%sum ,lo ,hi (lambda (,var) ,term)))
(defun %sum (lo hi func)
(loop for i from lo to hi sum (funcall func i)))
(defmacro sum (var lo hi term)
`(%sum ,lo ,hi (lambda (,var) ,term)))
This expands to a call to %sum with a lambda that binds var and evaluates term in that context, then loops applying the function, akin to call-by-name, though it requires careful hygiene to avoid variable capture.
The influence of Jensen's device and call-by-name from ALGOL 60 extended to post-ALGOL functional languages, shaping the adoption of laziness in systems like Miranda, which introduced lazy evaluation in 1985 using graph reduction for efficient thunk handling, and subsequently Haskell in 1990, which refined this with polymorphic types and call-by-need to mitigate repeated computations.[17] In Scheme, a Lisp dialect, explicit delays via delay and force primitives allow programmer-controlled laziness for similar effects, though without default lazy semantics. These features enable functional languages to support Jensen's device-like patterns natively, prioritizing referential transparency over the unpredictable substitutions of call-by-name.
Criticism and Limitations
Unpredictable Side Effects
Jensen's device relies on call-by-name parameter passing, where actual parameters are re-evaluated each time the corresponding formal parameter is referenced within the procedure body. This mechanism, while enabling powerful abstractions like iterated summations, introduces significant risks when combined with imperative features such as assignments that produce side effects. Multiple evaluations of a by-name parameter can unexpectedly alter shared variables in the caller's environment, leading to non-intuitive program behavior. For instance, consider a summation procedure sum(e, i, low, high) that initializes i to low, increments it in a loop up to high, and accumulates the value of expression e each time. If called as result := sum(A[j], j, 1, 10), the expression A[j] is re-evaluated on each iteration; if the summation procedure modifies j (e.g., through an internal increment), subsequent evaluations access and potentially alter different array elements prematurely, distorting the intended computation.[18]
Debugging these issues is particularly challenging due to the textual substitution semantics underlying call-by-name, which effectively inlines the actual parameter's code at each use site without explicit indication in the source. This obscures the control flow, as the expanded code may interleave with the procedure's body in ways that are not apparent from the high-level structure, making it difficult to trace variable modifications or predict execution order. Programmers must mentally simulate multiple expansions to uncover hidden dependencies, often leading to subtle bugs that surface only under specific calling conditions.[19]
Call-by-name evaluation amplifies the complexity of imperative side effects, turning simple parameter passing into a source of errors.[18]
One primary efficiency drawback of Jensen's device stems from its reliance on call-by-name parameter passing, where the formal parameter is treated as an unevaluated thunk that is re-evaluated each time it is referenced within the procedure body. This repeated computation can lead to significant runtime overhead, particularly when the expression passed as the parameter involves complex or costly operations. For instance, in a summation procedure iterating n times, a simple expression like i * i is evaluated n times, but if the expression includes O(n-time computations—such as another inner loop or recursive call—the total time complexity can degrade to O(n²), as each of the n iterations triggers redundant work.[20]
Historical implementations of ALGOL 60, such as those on the Electrologica X1 and X8 computers, highlighted these costs through measured overheads. In one analysis, programs compiled for the X8 resulted in about 21% longer code compared to the X1, and showed significant reductions in instruction counts, such as 93% fewer instructions for a Runge-Kutta integration example. Implementations utilized techniques like execute instructions to handle thunks more efficiently, but re-evaluations still incurred notable performance penalties.[21]
In performance-critical applications, this inefficiency contrasts sharply with call-by-value semantics, where arguments are evaluated once before the procedure call and passed as constants, avoiding redundant computations and enabling better compiler optimizations like inlining. As a result, call-by-value became the preferred mechanism in subsequent languages like Pascal and C, prioritizing predictable and efficient execution over the flexibility of call-by-name.[20]