This SRFI is currently in withdrawn 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.
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.
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.
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.
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.
(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.
(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.
(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).
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.
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.
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.