Jensen's Device

From Rosetta Code
This page uses content from Wikipedia. The original article was at Jensen's Device. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)
Jensen's Device
You are encouraged to solve this task according to the task description, using any language you may know.

This task is an exercise in call by name.

Jensen's Device is a computer programming technique devised by Danish computer scientist Jørn Jensen after studying the ALGOL 60 Report.

The following program was proposed to illustrate the technique. It computes the 100th harmonic number:

   integer i;
   real procedure sum (i, lo, hi, term);
      value lo, hi;
      integer i, lo, hi;
      real term;
      comment term is passed by-name, and so is i;
      real temp;
      temp := 0;
      for i := lo step 1 until hi do
         temp := temp + term;
      sum := temp
   comment note the correspondence between the mathematical notation and the call to sum;
   print (sum (i, 1, 100, 1/i))

The above exploits call by name to produce the correct answer (5.187...). It depends on the assumption that an expression passed as an actual parameter to a procedure would be re-evaluated every time the corresponding formal parameter's value was required. If the last parameter to sum had been passed by value, and assuming the initial value of i were 1, the result would have been 100 × 1/1 = 100.

Moreover, the first parameter to sum, representing the "bound" variable of the summation, must also be passed by name, otherwise it would not be possible to compute the values to be added. (On the other hand, the global variable does not have to use the same identifier, in this case i, as the formal parameter.)

Donald Knuth later proposed the Man or Boy Test as a more rigorous exercise.


<lang ada>with Ada.Text_IO; use Ada.Text_IO;

procedure Jensen_Device is

  function Sum
           (  I : not null access Float;
              Lo, Hi : Float;
              F : access function return Float
           )  return Float is
     Temp : Float := 0.0;
     I.all := Lo;
     while I.all <= Hi loop
        Temp := Temp + F.all;
        I.all := I.all + 1.0;
     end loop;
     return Temp;
  end Sum;
  I : aliased Float;
  function Inv_I return Float is
     return 1.0 / I;
  end Inv_I;


  Put_Line (Float'Image (Sum (I'Access, 1.0, 100.0, Inv_I'Access)));

end Jensen_Device;</lang>



Translation of: ALGOL 60

<lang algol68>BEGIN

  INT i;
  PROC sum  = (REF INT i, INT lo, hi, PROC REAL term)REAL:
     COMMENT term is passed by-name, and so is i COMMENT
     REAL temp := 0;
     i := lo;
     WHILE i <= hi DO           # ALGOL 68 has a "for" loop but it creates a distinct #
        temp +:= term;          # variable which would not be shared with the passed "i" #
        i +:= 1                 # Here the actual passed "i" is incremented. #
  COMMENT note the correspondence between the mathematical notation and the call to sum COMMENT
  print (sum (i, 1, 100, REAL: 1/i))

END</lang> Output: +5.18737751763962e +0


<lang AppleScript>set i to 0

on jsum(i, lo, hi, term) set {temp, i's contents} to {0, lo} repeat while i's contents ≤ hi set {temp, i's contents} to {temp + (term's f(i)), (i's contents) + 1} end repeat return temp end jsum

script term_func on f(i) return 1 / i end f end script

return jsum(a reference to i, 1, 100, term_func)</lang> Output: 5.18737751764


<lang c>#include <stdio.h>

int i; double sum(int *i, int lo, int hi, double (*term)()) {

   double temp = 0;
   for (*i = lo; *i <= hi; (*i)++)
       temp += term();
   return temp;


double term_func() { return 1.0 / i; }

int main () {

   printf("%f\n", sum(&i, 1, 100, term_func));
   return 0;

}</lang> Output: 5.18738

Works with: gcc

Alternatively, C's macros provide a closer imitation of ALGOL's call-by-name semantics: <lang c>#include <stdio.h>

int i;

  1. define sum(i, lo_byname, hi_byname, term) \
 ({                                            \
 int lo = lo_byname;                           \
 int hi = hi_byname;                           \
 double temp = 0;                              \
 for (i = lo; i <= hi; ++i)                    \
   temp += term;                               \
 temp;                                         \

int main () {

   printf("%f\n", sum(i, 1, 100, 1.0 / i));
   return 0;

}</lang> Output: 5.187378


Can be simulated via lambda expressions: <lang csharp>using System;

class JensensDevice {

   public static double Sum(ref int i, int lo, int hi, Func<double> term)
       double temp = 0.0;
       for (i = lo; i <= hi; i++)
           temp += term();
       return temp;
   static void Main()
       int i = 0;
       Console.WriteLine(Sum(ref i, 1, 100, () => 1.0 / i));


Common Lisp

Common Lisp does not have call-by-name for functions; however, it can be directly simulated by a macro wrapping selected parameters in lambdas.

<lang lisp>(declaim (inline %sum))

(defun %sum (lo hi func)

 (loop for i from lo to hi sum (funcall func i)))

(defmacro sum (i lo hi term)

 `(%sum ,lo ,hi (lambda (,i) ,term)))</lang>

<lang lisp>CL-USER> (sum i 1 100 (/ 1 i)) 14466636279520351160221518043104131447711/2788815009188499086581352357412492142272 CL-USER> (float (sum i 1 100 (/ 1 i))) 5.1873775</lang>


There are better ways to do this in D, but this is closer to the original Algol version: <lang d>import std.stdio: writeln;

double sum(ref int i, int lo, int hi, lazy double term) {

   double result = 0.0;
   for (i = lo; i <= hi; i++)
       result += term();
   return result;


void main() {

   int i;
   writeln(sum(i, 1, 100, 1.0/i));

}</lang> Output: 5.18738


<lang cpp>#include <iostream>

int i; double sum(int &i, int lo, int hi, double (*term)()) {

   double temp = 0;
   for (i = lo; i <= hi; i++)
       temp += term();
   return temp;


double term_func() { return 1.0 / i; }

int main () {

   std::cout << sum(i, 1, 100, term_func) << std::endl;
   return 0;

}</lang> Output: 5.18738


In E, the distinct mutable locations behind assignable variables can be reified as Slot objects. The E language allows a variable name (noun) to be bound to a particular slot, and the slot of an already-bound noun to be extracted, using the & operator.

(The definition of the outer i has been moved down to emphasize that it is unrelated to the i inside of sum.)

<lang e>pragma.enable("one-method-object") # "def _.get" is experimental shorthand def sum(&i, lo, hi, &term) { # bind i and term to passed slots

   var temp := 0
   i := lo
   while (i <= hi) {          # E has numeric-range iteration but it creates a distinct
       temp += term           # variable which would not be shared with the passed i
       i += 1
   return temp

} {

   var i := null
   sum(&i, 1, 100, def _.get() { return 1/i })


1/i is not a noun, so there is no slot associated with it; so we use def _.get() { return 1/i } to define a slot object which does the computation when it is read as a slot.

The value returned by the above program (expression) is 5.187377517639621.

This emulation of the original call-by-name is of course unidiomatic; a natural version of the same computation would be:

<lang e>def sum(lo, hi, f) {

   var temp := 0
   for i in lo..hi { temp += f(i) }
   return temp

} sum(1, 100, fn i { 1/i })</lang>


<lang forth>: s>f s>d d>f ;

sum 0 s>f 1+ swap ?do i over execute f+ loop drop ;
noname s>f 1 s>f fswap f/ ; 1 100 sum f.</lang>

Output: 5.18737751763962


<lang haskell>import Control.Monad import Control.Monad.ST import Data.STRef

sum' ref_i lo hi term =

 return sum `ap`
        mapM (\i -> writeSTRef ref_i i >> term) [lo..hi]

foo = runST $ do

       i <- newSTRef undefined -- initial value doesn't matter
       sum' i 1 100 $ return recip `ap` readSTRef i

main = print foo</lang> Output: 5.187377517639621

Icon and Unicon

Traditional call by name and reference are not features of Icon/Unicon. Procedures parameters are passed by value (immutable types) and reference (mutable types). However, a similar effect may be accomplished by means of co-expressions. The example below was selected for cleanliness of calling.


<lang Icon>record mutable(value) # record wrapper to provide mutable access to immutable types

procedure main()

   A := mutable()      
   write( sum(A, 1, 100, create 1.0/A.value) )


procedure sum(A, lo, hi, term)

   temp := 0
   every A.value := lo to hi do
       temp +:= @^term
   return temp


Refreshing the co-expression above is more expensive to process but to avoid it requires unary alternation in the call. <lang Icon> write( sum(A, 1, 100, create |1.0/A.value) ) ...

       temp +:= @term</lang>

Alternately, we can use a programmer defined control operator (PDCO) approach that passes every argument as a co-expression. Again the refresh co-expression/unary iteration trade-off can be made. The call is cleaner looking but the procedure code is less clear. Additionally all the parameters are passed as individual co-expressions. <lang Icon> write( sum{A.value, 1, 100, 1.0/A.value} ) ... procedure sum(X) ...

   every @X[1] := @X[2] to @X[3] do
       temp +:= @^X[4]</lang>


This Icon solution works in Unicon.


Solution: <lang j>jensen=: monad define

 'name lo hi expression'=. y
 temp=. 0
 for_n. lo+i.1+hi-lo do.
   (name)=. n
   temp=. temp + ".expression

)</lang> Example: <lang j> jensen 'i';1;100;'1%i'


Note, however, that in J it is reasonably likely that the expression (or an obvious variation on the expression) can deal with the looping itself. And in typical use this often simplifies to entering the expression and data directly on the command line.

And another obvious variation here would be turning the expression into a named entity (if it has some lasting usefulness).


Translation of: C

Uses an object o instead of integer pointer i, as the C example does.

<lang javascript>var obj;

function sum(o, lo, hi, term) {

 var tmp = 0;
 for (o.val = lo; o.val <= hi; o.val++)
   tmp += term();
 return tmp;


obj = {val: 0}; alert(sum(obj, 1, 100, function() {return 1 / obj.val}));</lang> The alert shows us '5.187377517639621'.


<lang lua> function sum(var, a, b, str)

 local ret = 0
 for i = a, b do
   ret = ret + setfenv(loadstring("return "..str), {[var] = i})()
 return ret

end print(sum("i", 1, 100, "1/i")) </lang>


<lang M4>define(`for',








<lang ocaml>let i = ref 42 (* initial value doesn't matter *)

let sum' i lo hi term =

 let result = ref 0. in
   i := lo;
   while !i <= hi do
     result := !result +. term ();
     incr i

let () =

 Printf.printf "%f\n" (sum' i 1 100 (fun () -> 1. /. float !i))</lang>

Output: 5.187378


Translation using mutable references and an anonymous function: <lang oz>declare

 fun {Sum I Lo Hi Term}
    Temp = {NewCell 0.0}
    I := Lo
    for while:@I =< Hi do
       Temp := @Temp + {Term}
       I := @I + 1
 I = {NewCell unit}


 {Show {Sum I 1 100 fun {$} 1.0 / {Int.toFloat @I} end}}</lang>

Idiomatic code: <lang oz>declare

 fun {Sum Lo Hi F}
    {FoldL {Map {List.number Lo Hi 1} F} Number.'+' 0.0}


 {Show {Sum 1 100 fun {$ I} 1.0/{Int.toFloat I} end}}</lang>


<lang perl>my $i; sub sum {

   my ($i, $lo, $hi, $term) = @_; 
   my $temp = 0;
   for ($$i = $lo; $$i <= $hi; $$i++) {
       $temp += $term->();
   return $temp;


print sum(\$i, 1, 100, sub { 1 / $i }), "\n";</lang> Output: 5.18737751763962

Or you can take advantage of the fact that elements of the @_ are aliases of the original: <lang perl>my $i; sub sum {

   my (undef, $lo, $hi, $term) = @_; 
   my $temp = 0;
   for ($_[0] = $lo; $_[0] <= $hi; $_[0]++) {
       $temp += $term->();
   return $temp;


print sum($i, 1, 100, sub { 1 / $i }), "\n";</lang> Output: 5.18737751763962

Perl 6

Rather than playing tricks like Perl 5 does, the declarations of the formal parameters are quite straightforward in Perl 6: <lang perl6>sub sum($i is rw, $lo, $hi, &term) {

   my $temp = 0;
   loop ($i = $lo; $i <= $hi; $i++) {
       $temp += term;
   return $temp;


my $i; say sum $i, 1, 100, { 1 / $i };</lang> Note that the C-style "for" loop is pronounced "loop" in Perl 6, and is the only loop statement that actually requires parens.


<lang php>$i; function sum (&$i, $lo, $hi, $term) {

   $temp = 0;
   for ($i = $lo; $i <= $hi; $i++) {
       $temp += $term();
   return $temp;


echo sum($i, 1, 100, create_function(, 'global $i; return 1 / $i;')), "\n"; //Output: 5.18737751764 (5.1873775176396)

function sum ($lo,$hi) {

$temp = 0;
for ($i = $lo; $i <= $hi; $i++)
 $temp += (1 / $i);
return $temp;

} echo sum(1,100);

//Output: 5.1873775176396 </lang>


<lang PicoLisp>(scl 6)

(de jensen (I Lo Hi Term)

  (let Temp 0
     (set I Lo)
     (while (>= Hi (val I))
        (inc 'Temp (Term))
        (inc I) )
     Temp ) )

(let I (box) # Create indirect reference

     (jensen I 1 100 '(() (*/ 1.0 (val I))))
     *Scl ) )</lang>


-> "5.187383"


<lang python>class Ref(object):

   def __init__(self, value=None):
       self.value = value

def harmonic_sum(i, lo, hi, term):

   # term is passed by-name, and so is i
   temp = 0
   i.value = lo
   while i.value <= hi:  # Python "for" loop creates a distinct which
       temp += term() # would not be shared with the passed "i"
       i.value += 1   # Here the actual passed "i" is incremented.
   return temp

i = Ref()

  1. note the correspondence between the mathematical notation and the
  2. call to sum it's almost as good as sum(1/i for i in range(1,101))

print harmonic_sum(i, 1, 100, lambda: 1.0/i.value)</lang> Output: 5.18737751764


R uses a call by need evaluation strategy where function inputs are lazily evaluated and then cached; functions can implement nonstandard evaluation such as call-by-name by using the "substitute" primitive to access the parse tree of the unevaluated input. There are some proposed conventions to do this in a way that is less confusing to the user of a function. The following ignores any conventions to mimic the effect of the original ALGOL where "i" is truly assigned in the calling context.

<lang R> sum <- function(var, lo, hi, term) {

 s <-  0
 for (i in lo:hi) {
   eval.parent(substitute(x <- i, list(x=substitute(var), i=i)))
   s <- s + eval.parent(substitute(term))


print(sum(i, 1, 100, 1/i)) </lang>


Here, setting the variable and evaluating the term are truly executed in the "outer" context: <lang ruby>def sum(var, lo, hi, term, context)

 sum = 0.0
 lo.upto(hi) do |n|
   sum += eval "#{var} = #{n}; #{term}", context

end p sum "i", 1, 100, "1.0 / i", binding # => 5.18737751763962</lang>

But here is the Ruby way to do it: <lang ruby>def sum2(lo, hi)

 lo.upto(hi).inject(0.0) {|sum, n| sum += yield n}

end p sum2(1, 100) {|i| 1.0/i} # => 5.18737751763962</lang>


Actually, the i parameter needs to be passed by reference, as done in so many examples here, so that changes made to it reflect on the parameter that was passed. Scala supports passing parameters by name, but not by reference, which means it can't change the value of any parameter passed. The code below gets around that by creating a mutable integer class, which is effectively the same as passing by reference.

<lang scala>class MyInt { var i: Int = _ } val i = new MyInt def sum(i: MyInt, lo: Int, hi: Int, term: => Double) = {

 var temp = 0.0
 i.i = lo
 while(i.i <= hi) {
   temp = temp + term
   i.i += 1

} sum(i, 1, 100, 1.0 / i.i)</lang>


res2: Double = 5.187377517639621

Standard ML

<lang sml>val i = ref 42 (* initial value doesn't matter *)

fun sum' (i, lo, hi, term) = let

 val result = ref 0.0


 i := lo;
 while !i <= hi do (
   result := !result + term ();
   i := !i + 1


val () =

 print (Real.toString (sum' (i, 1, 100, fn () => 1.0 / real (!i))) ^ "\n")</lang>

Output: 5.18737751764


Here, we set the value of the passed variable in the caller's frame. We then evaluate the passed term there too. <lang tcl>proc sum {var lo hi term} {

   upvar 1 $var x
   set sum 0.0
   for {set x $lo} {$x < $hi} {incr x} {
       set sum [expr {$sum + [uplevel 1 [list expr $term]]}]
   return $sum

} puts [sum i 1 100 {1.0/$i}] ;# 5.177377517639621</lang> However, the solution is expressed more simply like this <lang tcl>proc sum2 {lo hi lambda} {

   set sum 0.0
   for {set n $lo} {$n < $hi} {incr n} {
       set sum [expr {$sum + [apply $lambda $n]}]
   return $sum

} puts [sum2 1 100 {i {expr {1.0/$i}}}] ;# 5.177377517639621</lang>