Call By Need in Scheme

Question

I have this code knowing that parameters are passed using call by need:

(define fact-2
  (let ((foo (lambda (n f)
               (if (zero? n)
                   1
                   (f n f)))))
    (lambda (n)
      (let ((res 1))
        (foo n (begin 
                 (set! res (* res n)) 
                 (set! n (- n 1)) 
                 foo)) 
        res))))

I feel like I am missing something, but in the call by need calling foo with this object as f, it will calculate f once and then will never update res and n. Is this correct? Am I missing something?

Thank you.

Answer 1

You are correct. Only with call-by-name the begin expression will get evaluated on each call to f (except for the very first time) -- to find out what it is that we're calling, only if the call to f is indeed made.

With call-by-value the begin expression will be evaluated only once, before the very first call to foo.

With call-by-need it might get evaluated at most once, when and if at the end of the very first call to foo there's a need to call f again.

---

Let's look at how a call-by-name version could be simulated in the regular call-by-value Scheme:

(define fact2
  (let ((foo (lambda (n f)
               (if (zero? (n))       ;; (n)   NB
                   1
                   ((f) n f)))))     ;; (f)   NB
    (lambda (n)
      (let ((res 1))
        (foo (lambda () n)           ;; (lambda () ...)    NB
             (lambda ()              ;; (lambda () ...)    NB
               (begin 
                 (set! res (* res n)) 
                 (set! n (- n 1)) 
                 foo))) 
        res))))

Calling (fact2 5) produces 120 in Racket.

For call-by-value semantics your code needs no changes (to be interpreted in the regular call-by-value Scheme) and will of course loop, for the (fact-2 5) call (and indeed does so, in Racket).

And under the call-by-need semantics each lambda's body (of the two new lambda wrappers) will be evaluated only for the very first time it is called, whereupon it will save the calculated value and then return it; and for all the subsequent calls the saved value will be immediately returned, without evaluating the body. Thus the set! forms will be evaluated at most once, and the code, with the example test call (fact-2 5) will, again, loop.