Jensen's Device
| 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) |
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:
begin
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;
begin
real temp;
temp := 0;
for i := lo step 1 until hi do
temp := temp + term;
sum := temp
end;
comment note the correspondence between the mathematical notation and the call to sum;
print (sum (i, 1, 100, 1/i))
end
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.
Ada
<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;
begin
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
begin
return 1.0 / I;
end Inv_I;
begin
Put_Line (Float'Image (Sum (I'Access, 1.0, 100.0, Inv_I'Access)));
end Jensen_Device; </lang>
5.18738E+00
ALGOL 68
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
BEGIN
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. #
OD;
temp
END;
COMMENT note the correspondence between the mathematical notation and the call to sum COMMENT
print (sum (i, 1, 100, REAL: 1/i))
END
Output: +5.18737751763962e +0
C
<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
Alternatively, C's macros provide a closer imitation of ALGOL's call-by-name semantics: <lang c>#include <stdio.h>
int i;
- 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
D
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
C++
<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
E
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.)
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:
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 })
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
Output: 5.187377517639621
OCaml
<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
done;
!result
let () =
Printf.printf "%f\n" (sum' i 1 100 (fun () -> 1. /. float !i))</lang>
Output: 5.187378
Perl
<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
PHP
<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";</lang> Output: 5.18737751764
Python
<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()
- note the correspondence between the mathematical notation and the
- 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
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
in
i := lo; while !i <= hi do ( result := !result + term (); i := !i + 1 ); !result
end
val () =
print (Real.toString (sum' (i, 1, 100, fn () => 1.0 / real (!i))) ^ "\n")</lang>
Output: 5.18737751764