Search code examples
macrosschemelazy-evaluation

a question about memorized lazy eval macro in scheme language

Currently, i have been reading the book the scheme programming language written by Kent Dybvig.

In section 5.7, it implements memorized lazy eval in scheme using the scheme macro system.

The source code as

(define-syntax delay
  (syntax-rules ()
    [(_ expr) (make-promise (lambda () expr))]))

(define make-promise
  (lambda (p)
    (let ([val #f] [set? #f])
      (lambda ()
        (unless set?
          (let ([x (p)])
            (unless set?
              (set! val x)
                (set! set? #t))))
        val))))

(define force
  (lambda (promise)
    (promise)))

But i can not understand why the variable set? need to be tested twice in the procedure make-promise. This is the reason from the book

The second test of the variable set? in make-promise is necessary in the event that, as a result of applying p, the promise is recursively forced. Since a promise must always return the same value, the result of the first application of p to complete is returned.

which i can not understand

Could anyone explain it to me? Thanks!

Solution

  • The key is that force may reenter itself. Maybe an example can help you understand this:

    (define x 5)

(letrec ([f (delay
              (if (zero? x)
                  0
                  (begin
                    (set! x (- x 1))
                    (+ (force f) 1))))])
  (force f))

    The result will be 0, because the inner force call returns 0.

    If without the second test, the result will be 5. In this situation, every (force f) returns different values.