[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Semantics of DELAY



[I removed the distribution to scheme-standard@wheaties.ai.mit.edu
because DELAY and FORCE aren't in the IEEE/ANSI standard, precisely
because they were poorly specified in R3.99RS, and I removed the
distribution to scheme@mc.lcs.mit.edu because I haven't the least
idea who that/they is/are and his/her/its/their connection to the
R*RS.]

Very interesting.  We knew that DELAY and FORCE were
vaguely specified, but I didn't realize that even the
vague specification was unrealizable.

Because of recursion, I don't see how to implement
DELAY and FORCE in such a way that the body of the
DELAY is evaluated at most once.  The following will,
however, ensure that the value obtained by forcing a
given promise is always the same:

(define (make-promise proc)
  (let ((already-run? #f)
        (result #f))
    (lambda ()
      (cond (already-run? result)
            (else (let ((x (proc)))
                    (if (not already-run?)
                        (set! result x)))
                  (set! already-run? #t)
                  result)))))

Feeley suggests that we should consider repairing the
specification by adopting one or both of:

  (1)  It is an error for the body to return
       more than once.
  (2)  It is an error if the body is entered
       more than once.

As motivation, Feeley cites an implementation in
which promises are spliced out at GC time and complains
that this isn't a legal implementation technique if
DELAY forms can be returned from multiple times.  Well,
that isn't true.  The implementation technique remains
legal so long as the value obtained by forcing a promise
is constant.

I therefore suggest that we should require all uses
of FORCE on any given promise to return the same value,
while relaxing the requirement that the body of a
promise be entered at most once.  If this is considered
unreasonable, I would agree with a proposal in which all
uses of FORCE on any given promise must return the same
value, but it is an error for the body of a promise to
be entered more than once.

I see no particular problem with allowing the body to
return more than once provided all FORCEs return the
same value.  All other expression bodies in Scheme can
return more than once, so why should the bodies of DELAY
expressions be different?

Will

Appendix:  Implementations that actually signal errors
(1) and (2), respectively.

(define (make-promise proc)
  (let ((already-run? #f)
        (result #f))
    (lambda ()
      (cond (already-run? result)
            (else (let ((x (proc)))
                    (if already-run?
                        (error "Promise returned more than once")
                        (begin (set! already-run? #t)
                               (set! result x))))                    
                  result)))))

(define (make-promise proc)
  (let ((running? #f)
        (already-run? #f)
        (result #f))
    (lambda ()
      (cond (already-run? result)
            (running? (error "Nested FORCE on a single promise"))
            (else (set! running? #t)
                  (let ((x (proc)))
                    (if (not already-run?)
                        (set! result x)))
                  (set! already-run? #t)
                  result)))))

You may combine these two if you want to signal both
(1) and (2).