Jensen's Device & Thunks

Named after Jørn Jensen (Regnecentralen, Copenhagen), Jensen's device exploits call by name to pass an *expression* and the *variable it depends on*:

16.1 Jensen's device

Named after Jørn Jensen (Regnecentralen, Copenhagen), Jensen's device exploits call by name to pass an *expression* and the *variable it depends on*:

Each time sum executes s := s + term, the actual expression (1 / k, a[k] * b[k], ...) is evaluated with the current value of k, which the for statement inside sum is changing through the by-name formal i.

'begin'
    'integer' k;
    'real' 'array' a, b[1:3];

    'real' 'procedure' sum(i, lo, hi, term);
        'value' lo, hi; 'integer' i, lo, hi; 'real' term;
    'begin'
        'real' s;
        s := 0;
        'for' i := lo 'step' 1 'until' hi 'do' s := s + term;
        sum := s
    'end';

    a[1] := 1; a[2] := 2; a[3] := 3;
    b[1] := 4; b[2] := 5; b[3] := 6;

    outreal(1, sum(k, 1, 100, 1 / k));          'comment' harmonic number H(100);
    outstring(1, "\n");
    outreal(1, sum(k, 1, 3, a[k] * b[k]));      'comment' inner product = 32;
    outstring(1, "\n");
    outreal(1, sum(k, 1, 10, k * k))            'comment' 385;
'end'

16.2 Double sums

'comment' sum over i and j of m[i, j];
total := sum(i, 1, n, sum(j, 1, n, m[i, j]));

16.3 Thunks: how call by name is implemented

Peter Ingerman (1961) named the technique: for each by-name actual parameter the compiler generates a thunk — a parameterless routine that evaluates the actual expression (or computes the address of the actual variable) in the caller's environment. The formal parameter is represented by a pair *(code pointer, environment pointer)*.

In C-like pseudocode, the call sum(k, 1, 100, 1 / k) compiles roughly into:

MARST does exactly this when translating ALGOL 60 to C: look at the generated .c file to see the thunks.

/* thunk for "i": returns the address of k in the caller's frame */
int *thunk_i(Frame *env) { return &env->k; }
/* thunk for "term": evaluates 1/k in the caller's frame */
double thunk_term(Frame *env) { return 1.0 / env->k; }

double sum(Thunk_addr i, int lo, int hi, Thunk_val term) {
    double s = 0;
    for (*i.fn(i.env) = lo; *i.fn(i.env) <= hi; *i.fn(i.env) += 1)
        s += term.fn(term.env);
    return s;
}

16.4 Thunks today

Lazy evaluation in Haskell is call by *need* — call by name plus memoization of the thunk's result.

Closures / lambdas passed explicitly (() => expr) recreate call by name in modern languages; Scala has by-name parameters (x: => Int).

Macro systems and "lazy" arguments (e.g., logging macros) use the same idea.