What is “Call By Name”?

Question

I'm working on a homework assignment where we are asked to implement an evaluation strategy called "call by name" in a certain language that we developed (using Scheme).

We were given an example in Scala, but I don't understand how "call by name" works and how it is different to "call by need"?

Answer 1

Call by name is a a parameter passing scheme where the parameter is evaluated when it is used, not when the function is called. Here's an example in pseudo-C:

int i;
char array[3] = { 0, 1, 2 };

i = 0;
f(a[i]);

int f(int j)
{
    int k = j;    // k = 0
    i = 2;        // modify global i
    k = j;        // The argument expression (a[i]) is re-evaluated, giving 2.
}

The argument expression is lazily evaluated when accessed using the current values of the argument expression.

Answer 2

Call-by-need is a memoized version of call-by-name (see wikipedia).

In call-by-name, the argument is evaluated every time it is used, whereas in call-by-need, it is evaluated the first time it is used, and the value recorded so that subsequently it need not be re-evaluated.

Answer 3

Add this to the above answers:

Work through the SICP section on Streams. It gives a good explanation of both call-by-name and call-by-need. It also shows how to implement those in Scheme. BTW, if you are looking for a quick solution here is a basic call-by-need implemented in Scheme:

 ;; Returns a promise to execute a computation. (implements call-by-name)
 ;; Caches the result (memoization) of the computation on its first evaluation
 ;; and returns that value on subsequent calls. (implements call-by-need)
 (define-syntax delay
    (syntax-rules ()
      ((_ (expr ...))
       (let ((proc (lambda () (expr ...)))
             (already-evaluated #f)
             (result null))
         (lambda ()
           (if (not already-evaluated)
               (begin
                 (display "computing ...") (newline)
                 (set! result (proc))
                 (set! already-evaluated #t)))
           result)))))

 ;; Forces the evaluation of a delayed computation created by 'delay'.
 (define (my-force proc) (proc))

A sample run:

> (define lazy (delay (+ 3 4)))
> (force lazy) 
computing ... ;; Computes 3 + 4 and memoizes the result.
7
> (my-force lazy) 
7 ;; Returns the memoized value.