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.

After the first call to `foo`, `foo` calls itself in an infinite loop. Since `foo` is just calling itself, the numeric argument `n` is never decremented, so never reaches zero to terminate the loop. — clartaq, Feb 15 '21 at 22:54
Well, based on my teacher you are wrong, it somehow supposed to keep updating n in the (begin ... ) but I do not understand why since in call by need it should do it once — Maya Saias, Feb 16 '21 at 10:54
You can show it easily by adding a little output. Add a line like `(display "Enter foo: n: ")(display n)(newline)` as the first line in `foo`. Then invoke `(fact-2 5)`. You will see an unending stream of output where `foo` is called with an argument of 4. — clartaq, Feb 16 '21 at 13:32
@clartaq -- _call by need_ is a lazy evaluation model, and Scheme eagerly evaluates arguments in function calls. You can't just run this code in a Scheme REPL to reason about its behavior under a call by need model. — ad absurdum, Feb 18 '21 at 09:15

Will Ness · Answer 1 · 2021-02-21T05:41:05.300

2

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.

edited Feb 21 '21 at 05:41

answered Feb 18 '21 at 15:09

Will Ness

70,110
9
98
181

Could you explain some more? I only see `fact-2` calling `foo` with the arguments `n` and `foo`. And `foo` only calls `foo` with the arguments `n` and `foo`. Nowhere does `foo` decrement `n`. And I don't see any memoization or other mechanics for laziness being set up. – clartaq Feb 18 '21 at 18:31
@clartaq explain specifically what? there's three statements in my answer. are you asking about call by need? what exactly, specifically, is your question please? – Will Ness Feb 18 '21 at 19:14
Yes, about "call by need" (or any other parameter passing convention). I just don't see how any call to `fact-2` can succeed if there is no visible way to stop `foo` from recursing. Otherwise, I'll repeat the O.P.s question. "Am I missing something?" Thank you for persisting. – clartaq Feb 18 '21 at 19:38
@clartaq I've edited the answer. :) under call-by-value the OP code needs no changes and will of course loop, for the `(fact-2 5)` call. – Will Ness Feb 18 '21 at 20:13
Thank you. And I thought continuations were mind-bending. – clartaq Feb 18 '21 at 20:23
that's mutation for you. :) interestingly, I only had the lambda wrapping for the `foo` argument, at first. I thought, `n` is a plain numeric value, it needs no wrapping. can you guess what happened when I tried it? :) (and thanks for the discussion!) – Will Ness Feb 18 '21 at 20:25
Wouldn't even venture a guess. – clartaq Feb 18 '21 at 20:28
why it looped of course. can you see why? (I couldn't, at first) ...... 1.6K miles above Mars, yay! – Will Ness Feb 18 '21 at 20:30
It isn't obvious to me. Stepped away to watch Perseverance touchdown too. – clartaq Feb 18 '21 at 21:17
it's about _____scope_____. one `n` was being mutated, another one was being tested in the `if`. but with the lambda it's the same `n`, so it works. – Will Ness Feb 18 '21 at 21:22
load it up in Racket, hit Debug. :) cheers. – Will Ness Feb 18 '21 at 21:24
"_Under the call-by-value semantics your code needs no changes and will of course loop, for the `(fact-2 5)` call._" -- Maybe I misunderstand your meaning, but under call-by-value semantics the `begin` form will be evaluated when `foo` is first called (evaluating to `foo`), so on subsequent `(foo n foo)` calls, there will be no calls to `set!`, no decrement of `n`, and non-terminating looping. – ad absurdum Feb 19 '21 at 14:17
1

@adabsurdum "... and there will occur non-terminating looping." yes, that's it. what I meant was, we had to make some changes to represent the call-by-name interpretation of OP's code, to represent it by a code to be run inside Racket's call-by-value system; so there's no need for any changes to represent its call-by-value interpretation, as Racket is already that. – Will Ness Feb 19 '21 at 14:40

Call By Need in Scheme

1 Answers1