248: Minimal delimited continuations248: Minimal delimited continuationsby Marc Nieper-Wißkirchen
This SRFI is currently in draft status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-248@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.
Scheme's exception system is extended so that exception handlers
gain access to the delimited continuation representing the rest
of the computation of the call of the thunk guarded by the
handler. Algebraic effect handlers can be directly expressed in
this extended exception system. The system directly implements
the shift0/reset0 delimited control
operators. It is well known that other delimited control
operators like prompt0/control0 or
reset/shift are expressible
in shift0/reset0 (and vice versa).
None at present.
Scheme was the first programming language with first-class continuations. Since their invention, it has become increasingly clear that they do not provide the right abstraction in many use cases, but should be supplemented by delimited continuations, which only represent a portion of the rest of the computation. While delimited continuations are becoming popular in other programming languages, they still have to find their way into a Scheme standard.
SRFI
226 is an extensive proposal to add many control structures,
including delimited continuations, in a coherent way to Scheme.
SRFI 226 also contains a rationale for delimited continuations
and provides many links to existing literature. Due to its size
and far-reaching consequences, it does, however, place a burden
not be underestimated on implementers of Scheme. For a future
standard comparable in size with R6RS or
R7RS, a minimal API supporting delimited
continuations might be more appropriate. This SRFI proposes
such an API. It integrates smoothly into the existing
facilities by hooking into Scheme's exception system, and only
comes with one essential primitive procedure (and extends the
existing guard convenience syntax).
This SRFI dispenses with the idea of prompt tags as in other
systems for delimited continuation (but it is possible to
implement a delimited continuation system with prompt tags with
it). If it were not for call/cc, the system could
dispense with dynamic-wind.
In the following examples, we use the guard
syntax, which is a convenient syntactic abstraction over the
primitive with-unwind-handler procedure. Both
are defined in the specification
section.
The following is a version
of SRFI
158's make-coroutine-generator that
prevents the space leaks inherent to the sample implementation
of SRFI 158, which uses call/cc. This version, which uses delimited
continuations, is also easier to understand.
(define make-coroutine-generator
(lambda (proc)
(define-condition-type &yield &condition
make-yield-condition yield-condition?
(value condition-value))
(define yield
(lambda (val)
(raise-continuable (make-yield-condition val))))
(define thunk
(lambda ()
(guard (c k
[(yield-condition? c)
(set! thunk k)
(condition-value c)])
(proc yield)
(eof-object))))
(lambda ()
(thunk))))
The next example shows how delimited continuations and the API
of this SRFI in particular can be used to transform a procedure
with for-each-like semantics describing an abstract
list into a procedure with fold-like semantics
describing the same abstract list. Notably, the implementation
does not use state, which would be incompatible with the existence
of call/cc.
(define for-each->fold
(lambda (for-each)
(define-condition-type &yield &condition
make-yield-condition yield-condition?
(value condition-value))
(lambda (proc nil)
((guard (c k
[(yield-condition? c)
(lambda (s)
((k) (proc s (condition-value c))))])
(for-each
(lambda (x)
(raise-continuable (make-yield-condition x))))
values)
nil)))
(define string-fold
(lambda (proc seed s)
(define for-each-s (lambda (proc) (string-for-each proc s)))
(define fold-s (for-each->fold for-each-s))
(fold-s proc seed))))
More examples can be found in the bundled test cases.
The following syntax and procedures are provided by the (srfi
:248 exceptions) and (srfi :248) libraries
(R6RS) and by the (srfi 248) library
(R7RS).
(with-unwind-handler handler thunk)
Handler must be a procedure and should accept two
arguments. Thunk must be a procedure that accepts
zero arguments. The with-unwind-handler procedure
returns the results of invoking thunk. An anonymous
handler is installed as the current exception handler for the
dynamic extent (as defined in R6RS) of the invocation
of thunk.
When the anonymous handler is invoked on an
object obj as a result of a call
to raise or raise-continuable, it
packages the portion of the current continuation up to and
including the call to with-unwind-handler that
installed the anonymous handler in a “delimited
continuation procedure” k. It then
applies handler on obj and k in
the continuation and dynamic environment of the call
to with-unwind-handler.
Implementation responsibilities (R6RS): The
implementation must check the restrictions on handler
to the extent performed by applying it as described when it is
called as a result of a call to raise
or raise-continuable. An implementation may check
whether handler is an appropriate argument before
applying it.
(empty-continuation? k)
The argument k should be a delimited continuation
procedure. The empty-continuation? predicate
returns #t if k represents the empty
delimited continuation, that is, if k is the
delimited continuation argument of a handler invoked as a result
of a call to raise-continuable that occurs in tail
context of the thunk of the with-unwind-handler
expression that installed the handler. If k does not
represent the empty delimited continuation, #f is
returned.
Example:
(with-unwind-handler
(lambda (obj k)
(empty-continuation? k))
(lambda ()
(raise-continuable 42))) ; ⇒ #t
(with-unwind-handler
(lambda (obj k)
(empty-continuation? k))
(lambda ()
(not (raise-continuable 42)))) ; ⇒ #t
(with-exception-handler handler thunk)
This procedure is the same as in R6RS and R7RS.
(raise obj)
This procedure is the same as in R6RS and R7RS.
(raise-continuable obj)
This procedure is the same as in R6RS and R7RS.
(guard (⟨variable⟩ ⟨continuation variable⟩
⟨cond clause1⟩
⟨cond clause1⟩
…)
⟨body⟩)
=>
else
Syntax: ⟨Cond clause⟩ is as in the
specification of cond. =>
and else are the same as in R6RS and
R7RS.
Semantics: Evaluating a guard form evaluates
⟨body⟩ with an anonymous exception handler that
packages the portion of the current continuation up to and
including the evaluation of the guard form in a
delimited continuation procedure. It then binds the raised
object to ⟨variable⟩ and the captured delimited
continuation procedure to ⟨continuation variable⟩,
and within the scope of those bindings evaluates the clauses as
if they were the clauses of a cond expression. The
implicit cond expression is evaluated within the
continuation and dynamic environment of the guard
expression. If every ⟨cond clause⟩'s
⟨test⟩ evaluates to #f and there is
no else clause, then raise-continuable
is invoked on the raised object, and the captured delimited
continuation procedure is applied to the values returned by the
call to raise-continuable.
The final expression in a ⟨cond clause⟩
is in a tail context if the guard expression itself is.
If a call to raise-continuable occurs in tail
context of the body, the delimited continuation
procedure bound to ⟨continuation variable⟩
represents the empty continuation.
(guard (⟨variable⟩
⟨cond clause1⟩
⟨cond clause1⟩
…)
⟨body⟩)
This syntactic form is the same as in R6RS (with errata applied) and R7RS (with the tail context specification as in R6RS).
A portable implementation of delimited continuations (which
uses call/cc and global state) is only possible by
at least replacing the user-visible call/cc.
This is analogous to the fact that dynamic-wind can be
implemented by using call/cc and global state, but
only by replacing the user-visible call/cc.
This SRFI is implementable in any Scheme that supports any form
of delimited continuations compatible with call/cc
and dynamic-wind and where one can test for
equality of continuation procedures. We provide a
a sample implementation for
Guile, which is only missing
the empty-continuation? predicate.
Thanks to the members of the SRFI discussion group.
© 2023 Marc Nieper-Wißkirchen.
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 (including the next paragraph) 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.