Title

Promises

Author

Marc Nieper-Wißkirchen

Status

This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-155@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

Abstract

Scheme, like ML, is a programming language with strict evaluation while others, like Haskell, use lazy evaluation. Scheme, however, possesses the primitives delay and force that make it possible to express lazy algorithms.

Lazy evaluation does not go well in conjunction with imperative, non-functional, side-effecting code. It should, however, be applicable in a purely functional setting. This is the case for the delayed evaluation model as described in the R7RS as long as no dynamically bound variables, also known as parameter objects, are present. It is the purpose of this SRFI to rework the specification in the R7RS so that lazy evaluation works with purely functional code that makes use of dynamic environments or, more generally, the dynamic extent. This is done by remembering the dynamic extent in effect when the delay expression is evaluated.

Another perceived misfeature of the R7RS model of delayed evaluation is the apparent need of the delay-force special form to express iterative lazy algorithms. It is shown that the delay-force special form is unneeded and that the implementation can (and should) handle iterative lazy algorithms without space leaks.

Rationale

Promises and the dynamic extent

In ticket #397 of the Scheme Working Group 1, the question was raised how promises shall interact with the dynamic extent, namely whether force shall evaluate a promise in the dynamic extent of the call to force which first requested its value. An opposing choice would be that force shall evaluate a promise in the dynamic extent of the site where the promise was created.

The ticket was resolved apparently without any ballot or public discussion, and the former semantics was chosen for the R7RS. Accordingly, the description of force in the R7RS says: Consequently, a delayed expression is evaluated using the parameter values and exception handler of the call to force which first requested its value.

It is the main thesis of this SRFI that the choice made by the editors of the R7RS was the wrong one, so this SRFI proposes a correction to the (scheme lazy) library in form of the (scheme promise) library.

Lazy algorithms should work well together with purely functional code. The use of parameter objects (for example functioning as implicit arguments to procedure calls), or more generally calls to dynamic-wind with a pair of before and after thunks that, abstractly, has a clear functional semantics is orthogonal to the question of whether code is purely functional or not. However, with the semantics of force as currently in the R7RS, the order of evaluation of arguments in otherwise purely functional code suddenly matters:

  (let ()
    (define x (make-parameter 1))
    (define p (delay (x)))
    (define (g p) (parameterize ((x 2)) (force p)))
    (+ (force p) (g p)))

Depending on the order of evaluation, this expression either evaluates to 2 or 4. Obviously, we don't expect that purely functional code exhibits such a behaviour. (Folks from the Haskell camp would have good reasons to shake their heads in astonishment.) Reasoning about such code would be very hard.

A more realistic example could be provided by a combination of an object system together with some lazy algorithm. Such an object system may want to refer to the current instance by this. One choice would be to explicitly thread this in the code (as Python does with explicitly mentioning self at each method definition) or to realize this as a syntax parameter (see SRFI 139, a way C++ and Java chose.) A third way, more along Python's semantics but without explicitly mentioning this (or self) at every method definition site would be to define this as a parameter object (in the sense of the R7RS), which is parameterized at each call site of a method. Now, if the lazy algorithm references this, most certainly the parameter value of this when initially referred to and not when firstly forced is the correct one.

Unfortunately, the semantics of R7RS would get it wrong. Does this sound familiar? Of course! ECMAScript's functions suffer from the same problem, namely that the value of this is not remembered as part of the closure. (In ECMAScript 2015 this problem was remedied in form of “arrow functions”.)

However, there might be legitimate reasons to access the dynamic extent at the site of the first invocation to force, for example for debugging purposes. Therefore, this SRFI defines an optional procedure forcing-extent, which returns the dynamic extent (in the sense of SRFI 154) of the most recent call to force. The procedure is optional because its presence complicates the semantic model of lazy evaluation again. Using (forcing-extent) makes code as the following possible:

  (import (scheme base)
          (scheme write)
          (srfi 154)
          (srfi 155))
  (define current-logger (make-parameter #f))
  (define (log msg) ((current-logger) msg))
  (define (default-logger msg)
    (display msg (current-error-port))
    (newline (current-error-port)))
  (define-syntax logged-delay
    (syntax-rules ()
      ((delay/logged expression)
       (delay (begin (with-dynamic-environment (forcing-environment)
                      (lambda ()
                        (log "promised value calculated just now")))
                     expression)))))
  (let ((p (delay 1)))
    (parameterize ((current-logger default-logger))
      (display "The answer is: ")
      (display (+ (force p) 41))
      (newline)))

In particular, it is possible to implement the semantic model of the R7RS in terms of the model of this SRFI when the procedure forcing-environment is included.

Iterative lazy algorithms

The R5RS and the R7RS make no guarantee that expressing iterative lazy algorithms just with delay and force will run in bounded space. Instead, they provide a special form delay-force such that (delay-force <expression>) is equivalent to (delay (force <expression>)) except that forcing the resulting promise guarantees to evaluate (force <expression>) in tail position. The R7RS gives an example in form of the stream-filter procedure that makes use of the delay-force form.

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 section 3.5 of the R7RS).

As an improvement, it was suggested by Alex Shinn on the mailing list of this SRFI 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, for example, the following code (making use of SRFI 111: Boxes):

  (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.

In order to make this work, 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. Furthermore, the model breaks down in more complicated cases:

  (delay (if flag? (force x) (force y)))

Forcing the result of this expression won't guarantee that (force x) or (force y) is evaluated in a tail position although both calls appear in tail context inside the delay form.

So again, 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.

Instead, what is needed is the following: If evaluating <expression> results in a tail call of the form (force promise), forcing the result of (delay <expression>) will also result in a tail call to (force promise).

It is not possible to achieve this syntactically. It is, however, possible to implement this requirement using the continuation marks of SRFI 157, which is demonstrated by the sample implementation accompanying this SRFI.

Specification

We use the term dynamic extent for reified dynamic extents as in SRFI 154.

The mandatory identifiers defined by this specification are exported by the library (srfi 155). The optional identifiers are exported by the library (srfi 155 reflection). If an implementation provides the library (srfi 155 reflection), it has to provide all optional identifiers.

The author of this SRFI recommends that the interface described in this SRFI be made available under the namespace (scheme promise) (and (scheme promise reflection)) in future revisions of the Scheme programming language that build upon the R7RS. When this happens, (scheme lazy) might become deprecated and remain solely for backward-compatibility with the R7RS. It is further recommended that (scheme stream) of the R7RS-large uses the same semantics with respect to the dynamic extent as this SRFI.

Syntax

(delay <expression>)

(delay <expression>) returns an object called a promise which at some point in the future can be asked (by the force procedure) to evaluate <expression> in the dynamic extent in effect when the delay expression was evaluated, and deliver the resulting value. The effect of <expression> returning multiple values is unspecified.

If forcing the result of (delay <expression>) results in a tail call of the form (force promise), forcing of the result is required to also result in a tail call to (force promise).

Rationale: This makes iterative lazy algorithms without space leaks possible; see also SRFI 45.

(delay-force <expression>)

Equivalent to (delay (force <expression>)). This form is provided only for backward compatibility, and its use is deprecated.

Procedures

(force promise)

The force procedure forces the value of a promise created by delay, delay-force, or make-promise. If no value has been computed for the promise, the value is computed in the dynamic extent in effect when the delay, delay-force, or make-promise expression was evaluated, and returned. The value of the promise must be cached (or “memoized”) so that if it is forced a second time, the previously computed value is returned. If promise is not a promise, it may be returned unchanged.

(promise? obj)

The promise? procedure returns #t if its argument is a promise, and #f otherwise. Note that promises are not necessarily disjoint from other Scheme types such as procedures.

(make-promise obj)

The make-promise procedure returns a promise which, when forced, will return obj. It is similar to delay, but does not delay its argument; it is a procedure rather than syntax. If obj is already a promise, it is returned.

Optional procedures

(forcing-extent)

When the value of a promise (delay <expression>) is asked for the first time and <expression> is evaluated, an invocation of (forcing-extent) in the dynamic extent of that evaluation returns the dynamic extent (as defined by SRFI 154) of the call to force that initially forced the promise. If forcing a promise yields a chain of delay and force, the dynamic extent returned by (forcing-extent) is the dynamic extent of the outermost call to force in this chain. It is an error to invoke forcing-environment outside the dynamic extent of <expression>.

(dynamic-environment? obj)

Type predicate for dynamic extent as exported by (srfi 154).

Implementation

The provided sample implementation for an R7RS system builds upon the sample implementation of SRFI 154.

It is a faithful implementation if the presence of the library (srfi 157) of SRFI 157: Continuation marks is detected on the host system.

Otherwise, the requirement that (force (delay <expression>)) results in a tail call to (force promise) whenever evaluating <expression> results in a tail call to (force promise) is only met when <expression> expands into the form (force promise).

Their is also an interface to the implementation as a Racket module.

The sample implementation provides the optional procedures.

The portable R7RS implementation can cause unwanted space leaks because it does not use shallow keys for continuation marks (see the addendum to SRFI 157 in SRFI 154). A full implementation of this specification without any space leaks is provided in the form of a meta-circular interpreter written in R7RS dubbed Inferior Scheme, which is a REPL for the Scheme IEEE 1178-1990 standard. Outside of the standard syntax and procedures, Inferior Scheme provides the syntax and the procedures of SRFIs 154, 155, and 157, the load procedure of the R4RS, dynamic-wind of R5RS, and parameterize and make-parameter of R7RS.

Acknowledgements

Credit goes to the authors of the R7RS and to André van Tonder for his SRFI 45 from where most of this SRFI's description of promises and delayed evaluation was taken.

Credit also goes to Philip L. Bewig for his fantastic and standard setting SRFI 41, which provides an important use case for promises.

Special thanks go to Jim Rees for playing with and testing this proposed specification. Fruitful discussions with him led to the definition of shallow keys in SRFI 154 to prevent space leaks in implementations of this SRFI building upon SRFI 154.

Copyright

Copyright (C) Marc Nieper-Wißkirchen (2017). All Rights Reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.


Editor: Arthur A. Gleckler