archives

Scheme language conundrum regarding delay and force.

The following is a question originally posed by Alan Manuel Gloria to the Scheme Standardization list. I think that it is a particularly good question, so I thought I'd share it.

(define x 0)
(define p
  (delay
    (if (= x 5)
      x
      (begin
        (set! x (+ x 1))
        (force p)
        (set! x (+ x 1))
        x))))

(force p) => ??
x => ??

Delay and force have their usual (for PL theory discussions) meanings; the questions are about promises that force themselves in the course of their forcing (ie, forms for which 'force' causes a recursive invocation of 'force' on the same promise). The question becomes interesting when, as in the above case, the recursion is nontail. Some current implementations return 5 for p and 10 for x and some throw an exception reporting a reentrant promise. Some implementors claim that 5 for p and 5 for x ought to be allowed since the delayed form returns at the point of forcing and no further computation ought to be done on it, whereas others say that x is visible outside the scope of the delayed computation and therefore the computation of the delayed form must be completed for its side effect on x, even after the force has taken place. FWIW, I agree with the latter point of view. The questions, roughly, are these:
  1. Ought the above be legal with specified results, legal with undefined results, or is it an error?
  2. If it is an error, must an implementation detect and report the error via the exception mechanism, or may the dread curse of nasal demons be invoked?
  3. If it is legal, with specified meaning, then what specific meaning ought it to have?
  4. If it is legal, then may force return while the remainder of the computation caused by the force completes in another thread (making x subject to a possible race condition)?
  5. If it is made legal, is there any legitimate use for it? (ie, is there any useful purpose the language would fail to serve if it were banned)?
It complicates the discussion somewhat that this language "feature" may interact with reified winding continuations. So, bearing in mind that the committee is under no obligation to listen to or agree with this forum should a consensus be reached here, what do you think this code should do?