Semantics of DELAY

[Marc Feeley <feeley@chaos.cs.brandeis.edu>]

In the R3.99RS report, the DELAY special form and the FORCE procedure
are defined through the following implementation:

(define-macro (DELAY form) `(make-promise (lambda () ,form)))

(define (make-promise thunk)
  (let ((computed? #f) (result #f))
    (lambda ()
      (if (not computed?)
        (begin
          (set! result (thunk))
          (set! computed? #t)))
      result)))

(define (FORCE promise) (promise))

I don't find this definition very appealing because it contradicts my
intuition about DELAY (and also the definition in the text).  For one
thing, it is specified (in the text) that the body of the DELAY is
evaluated (at most) once.  Also it is stated that the value returned
by forcing a given promise will always be the same value.  These
properties are not respected if call/cc is used to return several
times from the body of the DELAY.  Even if we don't use call/cc we can
still run into the same problem, for example:

(define (test)
  (let ((x #f) (y 1))
    (set! x (DELAY (begin
                     (set! y (* y 2))
                     (if (< y 10)
                       (+ (FORCE x) 1) ;;; this FORCE will run this body again
                       y))))
    (FORCE x))) ;;; returns 19

Note that in this code, every (FORCE x) returns a different value (first 16,
then 17, 18 and 19).

I think it would make sense to prevent the body from returning more than
once (i.e. such a thing would be an error).  Also it might be a good idea
to signal an error if the body is entered more than once.  The implementation
of make-promise could be easily extended to detect these errors:

(define (make-promise thunk)
  (let ((state 'NOT-ENTERED) (result #f))
    (lambda ()
      (case state
        ((NOT-ENTERED)
         (set! state 'COMPUTATION-STARTED)
         (let ((val (thunk)))
           (if (eq? state 'COMPUTATION-STARTED)
             (begin
               (set! state 'COMPUTATION-DONE)
               (set! result val)
               val)
             (error "body exited more than once"))))
        ((COMPUTATION-STARTED)
         (error "body entered more than once"))
        (else
         result)))))

Does anyone have reservations about such a definition?  Is there an even more
restrictive definition that would be coherent with the purpose of DELAY?

[Note: one of the reasons why I am asking this question is that in Gambit,
promise objects are represented as special objects (placeholders) that are
spliced out at GC time when they have a "value".  If DELAY forms can be
returned from multiple times, this optimization does not hold anymore.]

Marc -- feeley@cs.brandeis.edu