Informatics Educational Institutions & Programs

Jensen's device is a computer programming technique that exploits call by name. It was devised by Danish computer scientist Jørn Jensen, who worked with Peter Naur at Regnecentralen. They worked on the GIER ALGOL compiler, one of the earliest correct implementations of ALGOL 60. ALGOL 60 used call by name.^[1]^[2]^[3] During his Turing Award speech, Naur mentions his work with Jensen on GIER ALGOL.

Description

Jensen's device exploits call by name and side effects. Call by name is an argument passing convention that delays the evaluation of an argument until it is actually used in the procedure, which is a consequence of the copy rule for procedures. ALGOL introduced call by name.

A classic example of Jensen's device is a procedure that computes the sum of a series, $\textstyle \sum _{k=\ell }^{u}a_{k}$ :^[4]^[5]^[6]

 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]).

During the execution of Sum, the actual argument i will increment during each step of the for loop, and each of the procedure's evaluations of ak will use the current value of i to access the successive array elements V[i].

Jensen's device is general. A double summation can be done as:

 Sum(i, l, m, Sum(j, l, n, A[i,j]))

The Sum function can be employed for arbitrary functions merely by employing the appropriate expressions. If a sum of integers were desired the expression would be just Sum(i,1,100,i);, if a sum of squares of integers, then Sum(i,1,100,i*i);, and so on.^[7] A slight variation would be suitable for initiating a numerical integration of an expression by a method very similar to that of Sum.

The evaluation of ak is implemented with a thunk, which is essentially a subroutine with an environment. The thunk is a closure with no arguments. Each time a procedure needs the value of its formal argument, it simply calls the thunk. The thunk evaluates the actual argument in the scope of the calling code (not the scope of the procedure).

In the absence of this pass-by-name facility, it would be necessary to define functions embodying those expressions to be passed according to the protocols of the computer language, or to create a compendium function along with some arrangement to select the desired expression for each usage.

GPS

Another example is GPS (General Problem Solver), described in D. E. Knuth and J. N. Merner's ALGOL 60 confidential.^[8]

real 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;

Following is a single statement which finds m-th prime using GPS.

I := GPS(I, if I=0 then -1.0 else I, P, if I=1 then 1.0 else
   if GPS(A, I, Z, if A=1 then 1.0 else
      if entier(A)×(entier(I)÷entier(A))=entier(I) ∧ A<I
      then 0.0 else Z) = Z then
      (if P<m then P+1 else I×GPS(A, 1.0, I, -1.0)) else P)

(Note: In the original paper, the expression near the end is GPS(A, 1.0. I, 0.0), due to a corner case in the specification of the semantics of ALGOL 60's for statement.)

Criticism

Jensen's device relies on call by name, but call by name is subtle and has some problems. Consequently, call by name is not available in most languages. Knuth comments that ALGOL 60 cannot express an increment(n) procedure that increases its argument by one; the call increment(A[i]) does not do the expected action if i is a functional that changes with each access.^[9] Knuth says, "The use of 'macro' definition facilities to extend language, instead of relying solely on procedures for this purpose, results in a more satisfactory running program."

Others point out that a call by name procedure that swaps its argument can have subtle problems.^[10] An obvious swapping procedure is:

procedure swap(a, b)
  integer a, b;
  begin
    integer temp;
    temp := a;
    a := b;
    b := temp;
  end;

The procedure does the right thing for many arguments, but the invocation of swap(i,A[i]) is problematic. Using the Copy Rule leads to the assignments:

 temp := i;
 i := A[i];
 A[i] := temp;

The problem is the second assignment changes i, so the A[i] in the third assignment probably will not be the same array element as at the start. If on the other hand the procedure were to be coded the other way around (with b being saved to temp instead of a) then the desired action would result, unless it were invoked as swap(A[i],i)

References

^ Naur, Peter (2005). Peter Naur Lecture Video. ACM Awards. Denmark: Association for Computing Machinery. Retrieved 2020-09-11.
^ David (1 March 2006). "Software Pioneer Peter Naur Wins ACM's Turing Award". ACM Public Policy. Association for Computing Machinery. Retrieved 2020-09-11.
^ "ACM: Fellows: Peter Naur, Professor Emeritus, University of Copenhagen, Citation". 2005. Archived from the original on 2008-02-12. Retrieved 2020-09-21. Archived 2008-02-12 at the Wayback Machine
^ MacLennan, Bruce J. (1987). Principles of Programming Languages: Design, Evaluation, and Implementation (2nd ed.). Holt, Rinehart & Winston. pp. 141–2. ISBN 0-03-005163-0.
^ Dijkstra, E. W. (November 1961). "Defense of ALGOL 60 (Letter to the Editor)". Communications of the ACM. 4 (11): 502–503. doi:10.1145/366813.366844. S2CID 34185299.
^ Knuth, D. E. (October 1967). "The Remaining Troublespots in ALGOL 60". Communications of the ACM. 10 (10): 611–617. doi:10.1145/363717.363743. S2CID 10070608.
^ Sum requires a real argument for the term, so type conversion is assumed.
^ Knuth, Donald E.; Merner, Jack N. (June 1961). "ALGOL 60 confidential". Commun. ACM. 4 (6): 268–272. doi:10.1145/366573.366599. S2CID 22215746.
^ Knuth 1967, p. 613. For example, increment(A[increment(j)]) will increment j twice.
^ MacLennan 1987

External links

Standard, Storeless Semantics for ALGOL-Style Block Structure and Call-by-Name

[1] Naur, Peter (2005). Peter Naur Lecture Video. ACM Awards. Denmark: Association for Computing Machinery. Retrieved 2020-09-11.

[2] David (1 March 2006). "Software Pioneer Peter Naur Wins ACM's Turing Award". ACM Public Policy. Association for Computing Machinery. Retrieved 2020-09-11.

[3] "ACM: Fellows: Peter Naur, Professor Emeritus, University of Copenhagen, Citation". 2005. Archived from the original on 2008-02-12. Retrieved 2020-09-21. Archived 2008-02-12 at the Wayback Machine

[4] MacLennan, Bruce J. (1987). Principles of Programming Languages: Design, Evaluation, and Implementation (2nd ed.). Holt, Rinehart & Winston. pp. 141–2. ISBN 0-03-005163-0.

[5] Dijkstra, E. W. (November 1961). "Defense of ALGOL 60 (Letter to the Editor)". Communications of the ACM. 4 (11): 502–503. doi:10.1145/366813.366844. S2CID 34185299.

[6] Knuth, D. E. (October 1967). "The Remaining Troublespots in ALGOL 60". Communications of the ACM. 10 (10): 611–617. doi:10.1145/363717.363743. S2CID 10070608.

[7] Sum requires a real argument for the term, so type conversion is assumed.

[8] Knuth, Donald E.; Merner, Jack N. (June 1961). "ALGOL 60 confidential". Commun. ACM. 4 (6): 268–272. doi:10.1145/366573.366599. S2CID 22215746.

[9] Knuth 1967, p. 613. For example, increment(A[increment(j)]) will increment j twice.

[10] MacLennan 1987

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Informatics Educational Institutions & Programs

Description

GPS

Criticism

See also

References

External links