248: Minimal delimited continuations

by Marc Nieper-Wißkirchen

Status

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.

Received: 2023-10-27
60-day deadline: 2023-12-28
Draft #1 published: 2023-10-29
Draft #2 published: 2023-10-31

Abstract

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

Issues

None at present.

Rationale

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. 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 R⁶RS or R⁷RS, 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 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.

Examples

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.

Specification

The following syntax and procedures are provided by the (srfi :248 exceptions) and (srfi :248) libraries (R⁶RS) and by the (srfi 248) library (R⁷RS).

Procedures

(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 determined by dynamic-wind) 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 (R⁶RS): 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.

(with-exception-handler handler thunk)

This procedure is the same as in R⁶RS and R⁷RS.

(raise obj)

This procedure is the same as in R⁶RS and R⁷RS.

(raise-continuable obj)

This procedure is the same as in R⁶RS and R⁷RS.

Syntax

(guard (⟨variable⟩ ⟨continuation variable⟩ ⟨cond clause₁⟩ ⟨cond clause₁⟩ …) ⟨body⟩)
=>
else

Syntax: ⟨Cond clause⟩ is as in the specification of cond. => and else are the same as in R⁶RS and R⁷RS.

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 exception to ⟨variable⟩ and the captured delimited continuation procedure to ⟨continuation variable⟩, and within the scope of that 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.

(guard (⟨variable⟩ ⟨cond clause₁⟩ ⟨cond clause₁⟩ …) ⟨body⟩)

This syntactic form is the same as in R⁶RS (with errata applied) and R⁷RS (with the tail context specification as in R⁶RS).

Implementation

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. We provide a a sample implementation for Guile.

Acknowledgements

Thanks to the members of the SRFI discussion group.

Copyright

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.

Editor: Arthur A. Gleckler