(This is in part a continuation of the post
https://srfi-email.schemers.org/srfi-155/msg/6070271.)

In this post I describe a backward-compatible superior semantics for
delayed evaluation that makes ‘delay-force‘ unnecessary. Despite the
length of this post, I would like to get some feedback from users of
delayed evaluation in Scheme and from implementers.

Since the R5RS, delayed evaluation has become part of a Scheme standard.
The primitives defined by the R5RS are ‘delay’ and ‘force‘. At least
since SRFI 45 it was known that the obvious implementation of ‘delay’
and ‘force‘ is not sufficient for expressing iterative lazy algorithms.
The solution of SRFI 45 was to add a third primitive, later named
‘delay-force’ in the R7RS. The observable behavior of ‘(delay-force
<expression>)’ is the same as of ‘(delay (force <expression>))’ except
that the former allows an unbounded number of active delay-force
expressions in tail position.

From a user's perspective, the need for this third primitive is not
optimal, and one may think that a Scheme system properly supporting
delayed evaluation should handle ‘(delay (force <expression>))' as
gracefully as it does handle calls in tail position (as described in 3.5
of the R7RS).

It was suggested by Alex Shinn that ‘delay‘ should be redefined along
the following lines:

(define-syntax delay
  (syntax-rules (force)
   ((delay (force expression))
    (delay-force expression)
   ((delay expression)
    ...)))

With this definition, during expansion of ‘delay’ the system statically
detects whether the expression to be delayed is of the form ‘(force
<expression>)’. This means that ‘delay-force’ does not have to be
exposed anymore and that a Scheme user can write ‘(delay (force
<expression>))’ instead of ‘(delay-force <expression>)‘.

Besides probably being more user-friendly, this redefinition of ‘delay’
makes the delayed evaluation model also more composable, hence more
powerful: Consider the following example code (using SRFI 111):

(define-syntax lazy-box
  (syntax-rules ()
    ((lazy-box expression)
     (box (delay expression)))))

(define-syntax lazy-unbox
  (syntax-rules ()
   ((lazy-unbox box)
    (force (unbox box)))))

The lazy boxes defined by these two keywords wrap a promise in a box.
The pair of ‘lazy-box’ and ‘lazy-unbox’ provides the same primitives for
lazy boxes as do ‘delay’ and ‘force’ for non-boxed promises. Using the
suggested semantics that ‘(delay (force <expression>))’ is equivalent to
‘(delay-force <expression>)’, the composition ‘(lazy-box (lazy-unbox
<expression>))’ reduces correctly and makes expressing iterative lazy
algorithms with lazy boxes possible.

This is also the reason why ‘lazy-unbox’ has to be defined as syntax and
not as a procedure. Had we defined ‘lazy-unbox’ as a procedure, the call
to ‘force’ in tail position would have remained hidden from the syntax
expander.

While the automatic syntactic reduction of ‘(delay (force
<expression>))’ to ‘(delay-force <expression>)’ is, as this example
shows, better than exposing ‘delay-force’ directly, this necessity of
having to define ‘lazy-unbox’ as syntax also shows that the proposed
semantics is still a suboptimal choice.

From a user's perspective, this handling of ‘(delay (force
<expression>))’ is still not as graceful as it should be. The problem is
that the previous solution is based on detecting the presence of ‘force’
syntactically. Semantically, however, it is more correct, to reduce
‘(delay <expression>)’ to a ‘delay-force’-expression at execution time,
namely whenever a call to ‘force’ happens in ‘<expression>’ in tail
position.

This desirable semantics can be achieved with continuation marks that
are yet not part of the Scheme language, but viable candidates for (in
particular because they make proper tail recursion observable). Racket
is a dialect of Scheme that already exposes continuation marks to the
user. With the primitives for continuations provided by Racket and
otherwise portable R5RS code, the primitives of delayed evaluation of
the R7RS library ‘(scheme lazy)’ can be coded as follows:

#lang racket

;;; Internal definitions

(define %promise (vector 'promise))

(define (%make-promise done? value)
  (vector %promise (vector done? value)))

(define (%promise-content promise)
  (vector-ref promise 1))

(define (%promise-set-content! promise content)
  (vector-set! promise 1 content))

(define (%promise-done? promise)
  (vector-ref (%promise-content promise) 0))

(define (%promise-value promise)
  (vector-ref (%promise-content promise) 1))

(define (%promise-set-done?! promise done?)
  (vector-set! (%promise-content promise) 0 done?))

(define (%promise-set-value! promise value)
  (vector-set! (%promise-content promise) 1 value))

(define (%promise-update! new old)
  (%promise-set-done?! old (%promise-done? new))
  (%promise-set-value! old (%promise-value new))
  (%promise-set-content! new (%promise-content old)))

;;; Exported syntax

(define-syntax delay
  (syntax-rules ()
    ((delay expr)
     (%make-promise #f (lambda () expr)))))

(define-syntax delay-force
  (syntax-rules ()
    ((delay-force promise)
     (delay (force promise)))))

;;; Exported procedures

(define (promise? obj)
  (and (vector? obj)
       (> (vector-length obj) 0)
       (eq? %promise (vector-ref obj 0))))

(define (make-promise obj)
  (%make-promise #t obj))

(define (force promise)
  (if (%promise-done? promise)
      (%promise-value promise)
      (call-with-immediate-continuation-mark
       %promise
       (lambda (c)
         (if c
             (c promise)
             (let ((promise*
                    (call-with-current-continuation
                     (lambda (c)
                       (make-promise
                        (with-continuation-mark %promise c
                          ((%promise-value promise))))))))
               (unless (%promise-done? promise)
                 (%promise-update! promise* promise))
               (force promise)))))))

This implementation passes all tests of SRFI 45. That it has the desired
semantics can be seen from the definition of ’delay-force’. (For
simplicity, it ignores questions of dynamic extent as addressed by this
SRFI.)

This SRFI 155 wants to get the promises of the R7RS "right". So far, it
only requires from implementations to syntactically rewrite ‘(delay
(force <expression>))’ into ‘(delay-force <expression>)’. It does not
yet require to detect calls to ‘force‘ in tail position. By the
discussion from above, however, this would mean that SRFI 155 would get
the promises of the R7RS only "sort of right".

Thus I am inclined to make the optimal semantics from above a must-have
for implementations of this SRFI. In particular, ‘delay-force’ would
have outlived its usefulness. From a user's perspective, this is
certainly the way to go. From an implementer's perspective, this new
requirement may force him or her to add a few new primitives for
inspection of continuations or the stack (like continuation marks, which
are interesting on their own).

In order to make the sample implementation of this post more
self-contained, I am also considering to write a SRFI providing the
notion of continuation marks and the necessary primitives.

--

Marc