226: Control Features

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-226@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

Abstract

Whenever an expression is evaluated during the run of a Scheme program, there is a continuation awaiting the values of the expression. It is a distinguishing property of the Scheme programming language to offer a procedure (named call/cc) that captures the current continuation as a procedure, which, when called, aborts the then current continuation and reinstates the captured one.

One can visualize a continuation as a list of (continuation) frames where a non-tail call adds a frame to the top of the list and where the return from a non-tail call removes the appropriate frame.

Moreover, each expression is evaluated in a dynamic environment that conceptually holds the values of parameters like the current output port and the dynamic-wind stack at the point of evaluation. As the dynamic environment is captured and reinstated along the continuation when the call/cc machinery is used, we can view it conceptually as part of the continuation.

The libraries defined in this SRFI are all concerned with continuations in a wider sense. More specifically, the topics are as follows:

Continuation Prompts: A continuation prompt is a special continuation frame, which is tagged with a so-called prompt tag. Procedures to install continuation prompts and to abort the current continuation and to escape back to a previously installed continuation prompt are provided. Moreover, continuation prompts are equipped with handlers that are invoked when a continuation is aborted to them.

Continuations: When continuations are captured, the list of captured continuation frames are always delimited by some continuation prompt. This extends the semantics of Scheme’s call-with-current-continuation. Moreover, a procedure to capture so-called composable continuations is provided. As opposed to continuations captured by call-with-current-continuation, invoking a composable continuation does not abort the then current continuation, so composable continuations behave like ordinary procedures. Together with continuation prompts, composable continuations allow one to implement the various proposed sets of control operators for delimited continuations. Finally, a primitive (call-in-continuation) is provided that allows calling a thunk in a given continuation instead of just delivering values to it.

Continuation Marks: Continuation marks are a provided feature that allows one to attach arbitrary information to continuation frames, which are captured and reinstated along the rest of the continuation. Conceptually, exception handlers and parameters are implemented in terms of continuation marks, but the syntax and procedures defined in this SRFI allow the user to use them in more general ways. Moreover, they reify the notion of a tail call, allowing, for example, to test for tail context.

Exceptions: The exception mechanism of R6RS and R7RS is reinterpreted with respect to the concepts introduced in this SRFI. Moreover, the with-exception-handler procedure and the guard syntax gain additional tail context guarantees.

Parameters: The parameter object mechanism of SRFI 39 and R7RS is reinterpreted with respect to the concepts introduced in this SRFI. Procedures to retrieve the current parameterization and to reinstall it later are provided. Moreover, the parameterize syntax gains an additional tail context guarantee.

Delayed evaluation: The syntax and procedures on delayed evaluation of R7RS are revisited and redefined to handle the following satisfactorily: the parameterization of the delayed expression being forced, the treatment of exceptions raised during forcing of delayed expressions, and iterative lazy algorithms. Moreover, their semantics are detailed with respect to the concepts introduced in this SRFI, and promises can naturally deliver an arbitrary number of values when being forced. Finally, the initial continuation of a delayed expression being forced is defined in a way that makes it interchangeably with the initial continuation of a thread.

Threads: The thread mechanism of SRFI 18 is detailed with respect to the concepts introduced in this SRFI. In particular, mutation of parameter objects in multithreaded applications is specified..

Large parts of this SRFI have been inspired by the control operators provided by Racket.

Issues

Rationale

The aim of this SRFI is to provide a consistent set of control operators and related syntax and procedures vastly extending the scope of the venerable pair of call/cc and dynamic-wind. The procedures and syntax in this SRFI can be provided as R6RS or as R7RS libraries. Although a portable implementation is not possible, it is demonstrated by the sample implementation that a small set of primitives, which can easily be provided by any Scheme implementation, suffices to implement the rich operators in this SRFI.

The theoretical concepts behind the operators described in this specification are well understood and not new. The author of this SRFI does not claim any originality for any idea presented here, but is lucky to be able to stand on the shoulders of giants. (See the various references in A Monadic Framework for Delimited Continuations, for example.)

Whenever this document refers to just R7RS, the small language is meant as the large language is still a work in progress as the time of writing of this SRFI.

Overview

In detail, the contributions of this SRFI are the following:

Continuations and Prompts

As explained in R6RS and R7RS, whenever a Scheme expression is evaluated, there is a continuation wanting the result of the expression. We can view a continuation as a sequence of active procedure calls. Evaluation steps alter the current continuation. Calls add an active procedure call to the current continuation, while returns remove an active procedure call.

Certain control operations can change the current continuation more radically. The Scheme procedure call/cc allows capturing the current continuation and reifies it into a procedure that, when later called, abandons the then-current continuation and replaces it with the captured one.

Conceptually, only an end segment of the current continuation is ever replaced. For example, when running a Scheme program, running a thread, or evaluating an expression at the REPL prompt, the old and the new current continuation always share an initial segment at least up to the point when the program was started, the thread was started, or the expression was sent to the REPL.

Therefore, call/cc never has to, nor actually does, capture the whole current continuation, but only an end segment. Reinstating the captured continuation means to replace the end segment of the then-current continuation.

With call/cc alone, the programmer has no control over the size of this end segment. This SRFI offers operators to do exactly this. With these operators, the programmer can install continuation prompts identified by prompt tags in the current continuation. When a continuation is later captured, it is delimited by the nearest continuation prompt with a given prompt tag. Default prompts are installed at the start of each program, the start of each thread, and when promises are forced.

The reason that continuation prompts are called prompts is that ​a continuation as we know from Scheme is usually delimited at the prompt of the REPL. In a strict sense, an undelimited continuation does not return by definition. But this is not true for an actual continuation returned by even the venerable call/cc. When it is invoked, it will deliver value at the REPL prompt. (And when the program may not have been running from a REPL, the prompt is that of the shell or some HALT instruction.) A prompt as defined by this document just extends this scenario.

Composable and Non-Composable Continuations

When a continuation captured with call-with-current-continuation is later invoked, the invocation never returns to this call's continuation. In this sense, such a continuation procedure is far from being a function in the mathematical sense, as it doesn't deliver any values. In particular, it cannot be composed. For that reason, continuations captured by call-with-current-continuation are also called non-composable continuations.

This SRFI offers an operator call-with-composable-continuation that also captures the current continuation, but reifies it into a different type of continuation, a composable continuation. Contrary to non-composable continuations, a composable continuation, when invoked, does not abort any active procedure call, but just extends the then-current continuation. In particular, it delivers values to the continuation of the call to it. A composable continuation therefore behaves like an ordinary procedure.

Continuation Marks

Continuation marks are a feature that allows attaching information in the form of key-value pairs to individual continuation frames, which are maximal segments of continuations of a number of active tail calls followed by at most one active non-tail call. The set of continuation marks of the continuation frames of a continuation belongs to this continuation and is thus also captured by call-with-current-continuation and call-with-composable-continuation.

Continuation marks can be used to implement exception handlers, parameter objects, and an implementation of delay and force of R5RS that supports iterative lazy algorithms.

A crucial feature of continuation marks is that they allow one to attach marks to the most recent continuation frame without creating active non-tail calls. This allows one to implement a parameterize form where the last expression in its body is in tail context when the parameterize form is in tail position. Similarly, it becomes possible to implement with-exception-handler in a way so that its thunk is called in tail context if the call to with-exception-handler is in tail context.

The latter is not guaranteed by R6RS and R7RS (but should have according to the author of this SRFI).

In fact, with continuation marks, the concept of tail calls becomes operationally observable.

Continuations and Threads

The concept of threads and the semantics of multithreaded programs are deeply linked with the concepts that are involved in this specification. For example, each thread possesses an initial continuation, containing a continuation prompt with a handler that has to be described. For that, this specification contains a specification of a thread system mostly API-compatible with SRFI 18 (and that exist alongside SRFI 18). This helps making the existence of multiple threads, continuations, continuation prompts, and parameterizations mutually compatible.

Parameter Objects

Parameter objects are a tool to provide dynamically-scoped variables to the Scheme language in a clean way. As a definition of parameter objects in terms of continuation marks is possible, and as an implementation in terms of them allows rich operations like capturing the current parameterization to later reinstall it, this SRFI provides both.

Moreover, this specification makes a decision on the behavior of mutable parameter objects with respect to multiple threads. If a parameter that is inherited by a newly created thread and has not been reparameterized is mutated by one of the threads, the mutation will also (eventually) be observed by the other thread. This is a clear semantics because this is the same behavior as implemented by lexical variables.

Thread locals

Although they have been proposed for this application, parameter objects are unsuited to provide thread-local cells. The main reason is that the current parameterization is part of the current continuation. As the current continuation can be captured and reinstated in any thread, the parametrization cannot be a per-thread entity.

Instead, this specification defines first-class thread locals akin to thread-specific storage in the C programming language and to thread-specific data keys in POSIX. In particular, the former can be efficiently implemented in terms of the latter.

Promises

A naive implementation of delay and force does not support iterative lazy algorithms as was observed, for example, in SRFI 45. That SRFI and R7RS solve the problem by providing another primitive, delay-force (called lazy in SRFI 45). When continuation marks are available, however, such an irksome primitive is not needed; see SRFI 155. Consequently, this specification defines promises in a way that makes delay-force superfluous.

Moreover, this specification amends R7RS in a way that defines the continuation in which the values of promises are forced in such a way that it has the same semantics as executing a thread. This makes the overall system pleasantly coherent. The sample implementation shows how everything can be implemented efficiently.

Finally, promises as defined in this specification can deliver multiple values when forced, an extension too natural to ignore, and it is clearly specified what happens when an exception is raised during the forcing of a promise.

Relation to Other Standards

This specification is meant to be applicable to both standards, R6RS and R7RS. The former standard allows the use of square brackets synonymous with parentheses in the syntax. In its non-normative appendix C, advice is given in which places in the syntactic forms specified in the report they should be used. In order to document in which places square brackets should be used in the syntactic forms described in this specification, this document uses them in the appropriate places. When this specification is applied to R7RS, the square brackets should be read as parentheses.

Some of the procedures and syntax defined in this specification have the same names as procedures and syntax of R6RS and R7RS. In case a definition of such a procedure or syntax here does not conflict with the corresponding definition in a Scheme report, the procedure or syntax should be the same whether exported by the relevant standard libraries or one of the libraries described below.

Relation to Other SRFIs

This SRFI supersedes SRFI 34, SRFI 39, SRFI 154, SRFI 155, and SRFI 157.

The programming model defined by SRFI 18 is extended.

Why this Proposal should be Incorporated as a Standard Feature in Scheme Implementations

Implementation

The accompanying sample implementation does not implement the libraries defined in this specification, but it demonstrates how they can be as soon as a small set of easily implementable primitives are provided by the Scheme implementation.

The sample implementation provides versions of all procedures and syntax described in this specification and allows playing with them. A runnable test suite is also provided.

The sample implementation is written in the Scheme dialect of R6RS because it is supposed to be run on Chez Scheme, an implementation of that Scheme dialect. However, the code should be easily adaptable to any other Scheme dialect. In fact, the goal of the sample implementation is to enable Scheme implementers to add the procedures and syntax defined in this SRFI to their Scheme implementations with little effort.

Specification

Libraries

The syntax and procedures defined below are provided by sublibraries within (srfi :226 control) (see SRFI 97).

The (srfi :226) and (srfi :226 control) library is a composite of the sublibraries described in this specification.

In an implementation of R7RS, the composite library is named (srfi 226) instead, and the sublibraries are sublibraries within (srfi 226) instead of (srfi 226 :control). Moreover, the library name parts are singularized.

It is expected that a future Scheme standard building on the procedures and syntax defined in this document will choose a different packaging into libraries, possibly fewer ones.

Entry format

The following naming conventions imply type restrictions:

obj, key
any objects
name
symbol
list
list
thunk, pre-thunk, post-thunk
zero-argument procedures
cont
continuation
prompt-tag
prompt tag
mark-set
continuation mark set or #f
parameterization
parameterization
promise
promise
handler
procedure or #f
k
undelimited continuation
tl
thread local
timeout
real number or #f
thread
thread
owner-thread
thread or #f
mutex
mutex
condition-variable
condition variable

Iterators

An iterator for a list in the sense of this specification is a zero-argument procedure that returns two values on each invocation. An iterator for the empty list returns #f and an iterator for the empty list. An iterator for a non-empty list returns the head of the list and an iterator for its tail. Note that this iterator protocol is unsuitable for lists that potentially contain #f.

Safety

The libraries described by this SRFI are safe libraries in the sense of R6RS. In particular, in the presence of multiple threads, concurrent reading and writing to a location must not threaten system integrity in ways that might result in execution that is inconsistent with the semantics described in the Scheme reports and in this document. All modifications to single locations in the store must appear atomic to each thread.

Continuation Prompts

This section describes the (srfi :226 control prompts) library.

Conditions

Note: If this SRFI is implemented in a system that does not support the condition system of R6RS, the respective parts of this specification should be applied mutatis mutandis. We follow the presentation style of R6RS for the condition types defined in this and the other libraries.

&continuationcondition-type
(make-continuation-violation obj)
(continuation-violation? obj)
(continuation-violation-prompt-tag condition)

This condition type could be defined by

(define-condition-type &continuation &violation
  make-continuation-violation continuation-violation?
  (prompt-tag continuation-violation-prompt-tag))

This condition type describes violations that occurred during non-local control operations. Prompt-tag should be the tag of the delimiting prompt.

Prompt Tags

Continuation prompts are tagged with prompt tags, which are opaque values. A distinguished prompt tag is the default prompt tag.

(make-continuation-prompt-tag)
(make-continuation-prompt-tag name)

Returns a prompt tag that is not equal? to any prior or future results from make-continuation-prompt-tag or default-continuation-prompt-tag.

The optional name argument may be used by the implementation for printing the prompt tag.

(default-continuation-prompt-tag)

Returns the default prompt tag.

(continuation-prompt-tag? obj)

Returns #t if obj is a prompt tag, and #f otherwise.

(continuation-prompt-tag? (default-continuation-prompt-tag))#t
(eq? (default-continuation-prompt-tag) (default-continuation-prompt-tag))#t
(continuation-prompt-tag? (make-continuation-prompt-tag))#t
(equal? (make-continuation-prompt-tag) (default-continuation-prompt-tag))#f
(equal? (make-continuation-prompt-tag) (make-continuation-prompt-tag))#f

Continuation Prompts

We identify a continuation with a sequence of active procedure calls, beginning with the most recent call. A continuation can be uniquely partitioned into continuation frames, which are maximal subsequences of active procedure calls containing an arbitrary number of active tail calls followed by at most one active non-tail call.

A continuation prompt is a type of continuation frame such that when values are delivered to a continuation extended by such a continuation frame, the values are effectively delivered to the non-extended continuation. Moreover, each continuation prompt is tagged with a prompt tag and records a prompt handler, which is a procedure.

A continuation prompt with a given prompt tag is available in a continuation if a continuation prompt with the given tag is contained in the continuation's sequence of continuation frames.

(call-with-continuation-prompt thunk)
(call-with-continuation-prompt thunk prompt-tag)
(call-with-continuation-prompt thunk prompt-tag handler)

If not supplied, prompt-tag defaults to the default prompt tag, and handler defaults to #f.

The call-with-continuation-prompt procedure instates a continuation prompt that is tagged with prompt-tag and records handler in the continuation to its call. Finally, thunk is called with no arguments in the resulting continuation.

If handler is #f, the default handler is used instead. The default handler is a procedure that takes a single argument thunk. When the default handler is called, it reinstates the continuation prompt and calls thunk with no arguments in the resulting continuation.

The calls to the thunks are never in tail context.

(abort-current-continuation prompt-tag obj …)

The abort-current-continuation procedure aborts all active procedure calls in the current continuation until a continuation prompt tagged with prompt-tag is aborted and replaces them with a call to the handler recorded with the prompt tag with the arguments objs.

When a continuation prompt tagged with prompt-tag is not available in the continuation processed by abort-current-continuation, an exception with condition type &continuation is raised.

Note: Even if a continuation prompt tagged with prompt-tag is available in the current continuation when abort-current-continuation is called, due to the presence of dynamic-wind winders (see below) it can still happen during the aborting process that it becomes no longer available.

(let ([tag (make-continuation-prompt-tag)])
  (call-with-continuation-prompt
    (lambda ()
      (+ 1
         (abort-current-continuation tag 'foo 'bar)
         2))
    tag
    list))(foo bar)

The following example demonstrates that the prompt is reinstalled by the default handler.

(let ([tag (make-continuation-prompt-tag)])
  (call-with-continuation-prompt
   (lambda ()
     (abort-current-continuation tag
       (lambda ()
         (abort-current-continuation tag
           (lambda ()
             27)))))
   tag
   #f))27

Continuations

This section describes the (srfi :226 control continuations) library. This library, in addition to the procedures described here, also exports the condition types described in the previous section on continuation prompts.

Each continuation (procedure) is a procedure.

(call-with-non-composable-continuation proc prompt-tag)
(call-with-non-composable-continuation proc)
(call-with-current-continuation proc)
(call/cc proc)

If not supplied, prompt-tag defaults to the default prompt tag.

It is an error if proc does not accept one argument.

The procedure call-with-non-composable-continuation packages all active procedure calls in the current continuation up to but not including a continuation prompt tagged with prompt-tag as a continuation (“escape”) procedure and passes it as an argument to proc. The continuation procedure is a Scheme procedure such that, if it is later called, aborts all active procedure calls in the then-current continuation up to but not including a continuation prompt with prompt-tag or up to but not including an active procedure call shared by the current and captured continuations, whichever comes first. Finally, the active procedure calls in the unshared portion of the captured continuation are reinstated and the arguments supplied to the call to the continuation procedure become the result values for the new current continuation.

We say that the continuation procedure is delimited by prompt-tag.

If a call to call-with-non-composable-continuation occurs in a tail context, the call to proc is also in a tail context.

If a continuation prompt tagged with prompt-tag is not available in the current continuation, an exception with condition type &continuation is raised.

If a continuation prompt tagged with prompt-tag is not available in the current continuation when the continuation procedure is called, an exception with condition type &continuation is raised.

The identifier call/cc is an alias for call-with-current-continuation, which does not take a prompt-tag argument.

Note: As a continuation prompt tagged with the default prompt tag is available in the initial continuation of each thread, including the primordial thread, the call-with-non-composable-continuation defined here is a conservative extension of the call-with-non-composable-continuation of earlier Scheme reports.

The following example shows how continuation prompts delimit the captured continuation and the continuation to be replaced.

(let ([tag (make-continuation-prompt-tag)])
  (* 2
   (call-with-continuation-prompt
    (lambda ()
      (* 3
         (call-with-non-composable-continuation
          (lambda (k)
            (* 5
               (call-with-continuation-prompt
                (lambda ()
                  (* 7 (k 11)))
                tag)))
         tag)))
    tag)))990

When the continuation is captured in this example, all active procedure calls up to nearest (dynamically) enclosing prompt (tagged with the value of tag) are captured. Effectively, multiplication by 3 is captured. When the continuation is invoked in this example, its active procedure calls are reinstated after the current continuation has been cut back to the nearest enclosing prompt at the point of invoking the captured continuation. Effectively, the multiplication by 7 is removed and replaced by the captured multiplication by 3. In effect, this yields the value of (* 2 (* 3 (* 5 (* 3 11)))), which is 990.

(call-with-composable-continuation proc)
(call-with-composable-continuation proc prompt-tag)

If not supplied, prompt-tag defaults to the default prompt tag.

It is an error if proc does not accept one argument.

The procedure call-with-composable-continuation packages all active procedure calls in the current continuation up to but not including a continuation prompt tagged with prompt-tag as a continuation (“escape”) procedure and passes it as an argument to proc. The continuation procedure is a Scheme procedure such that, if it is later called, the active procedure calls in the captured continuation are reinstated and the arguments supplied to the call to the continuation procedure become the result values for the new current continuation.

We say that the continuation procedure is delimited by prompt-tag.

If a call to call-with-composable-continuation occurs in a tail context, the call to proc is also in a tail context.

If a continuation prompt tagged with prompt-tag is not available in the current continuation, an exception with condition type &continuation is raised.

Note: The difference between the continuation procedure returned by call-with-non-composable-continuation and call-with-composable-continuation is that the former removes portions of the then-current continuation, while the latter does not. The former continuation procedures are called non-composable continuations, while the latter are called composable continuations. The latter usually return values to the continuation in which they are called, while the former never do.

The following example is similar to the previous one except that the call to call-with-non-composable-continuation is replaced with a call to call-with-composable-continuation. Accordingly, invoking the captured continuation does not remove any active procedure calls and so the result of the second example is 7 times the value of the first.

(let ([tag (make-continuation-prompt-tag)])
  (* 2
   (call-with-continuation-prompt
    (lambda ()
      (* 3
         (call-with-composable-continuation
          (lambda (k)
            (* 5
               (call-with-continuation-prompt
                (lambda ()
                  (* 7 (k 11)))
                tag)))
         tag)))
    tag)))6930

This concept of composable continuations together with the facility to install and abort to continuation prompts is rich enough to support the known delimited control operators. For example, the control operators reset and shift from Abstracting Control can be implemented as follows:

(define-syntax reset
  (syntax-rules ()
    [(reset e1 e2 ...)
     (call-with-continuation-prompt
      (lambda ()
        e1 e2 ...))]))

(define-syntax shift
  (syntax-rules ()
    [(shift k e1 e2 ...)
     (call-with-composable-continuation
       (lambda (k)
         (abort-current-continuation (default-continuation-prompt-tag)
           (lambda ()
             e1 e2 ...))))]))

(+ 1 (reset 3)) 4
(+ 1 (reset (* 2 (shift k 4)))) 5
(+ 1 (reset (* 2 (shift k (k 4))))) 9
(+ 1 (reset (* 2 (shift k (k (k 4))))))17
(+ 1 (reset (* 2 (shift k1 (* 3 (shift k2 (k1 (k2 4))))))))25

Another possible pair of control operators is made by prompt and control. The difference with reset/shift is that control does not reinstate the prompt.

(define-syntax prompt
  (syntax-rules ()
    [(prompt e1 e2 ...)
     (call-with-continuation-prompt
      (lambda ()
	e1 e2 ...)
      (default-continuation-prompt-tag)
      (lambda (thunk)
	(thunk)))]))

(define-syntax control
  (syntax-rules ()
    [(control k e1 e2 ...)
     (call-with-composable-continuation
      (lambda (k)
	(abort-current-continuation (default-continuation-prompt-tag)
	  (lambda ()
	    e1 e2 ...))))]))

(prompt (+ 2 (control k (k 5)))) 7
(prompt (+ 2 (control k 5))) 5
(prompt (+ 5 (prompt (+ 2 (control k1 (+ 1 (control k2 (k2 6))))))))12
(prompt (+ 5 (prompt (+ 2 (control k1 (+ 1 (control k2 (k1 6)))))))) 8
(prompt
  (+ 12 (prompt (+ 5 (prompt (+ 2 (control k1 (control k2 (control k3 (k3 6))))))))))
18
(continuation? obj)

Returns #t if obj is a continuation procedure, and #f otherwise.

(continuation? (call/cc values))#t
(continuation? (call-with-composable-continuation values))#t
(call-in-continuation cont thunk)

Aborts and reinstates active procedure calls as if the continuation procedure cont were applied, but instead of delivering values to then-current continuation, the procedure thunk is called with no arguments in this continuation.

The call-in-continuation procedure can be used to implement the guard syntax concisely:

(define-syntax/who guard
  (lambda (stx)
    (syntax-case stx ()
      [(_ (id c1 c2 ...) e1 e2 ...)
       (identifier? #'id)
       #`(call-with-current-continuation
	  (lambda (guard-k)
	    (with-exception-handler
		(lambda (c)
		  (call-with-current-continuation
		   (lambda (handler-k)
		     (call-in-continuation guard-k
		       (lambda ()
			 (let ([id c])
			   #,(let f ([c1 #'c1] [c2* #'(c2 ...)])
			       (syntax-case c2* ()
				 [()
				  (with-syntax
				      ([rest
					#'(call-in-continuation handler-k
					    (lambda ()
					      (raise-continuable c)))])
				    (syntax-case c1 (else =>)
				      [(else e1 e2 ...)
				       #'(begin e1 e2 ...)]
				      [(e0) #'e0]
				      [(e0 => e1)
				       #'(let ([t e0]) (if t (e1 t) rest))]
				      [(e0 e1 e2 ...)
				       #'(if e0
					     (begin e1 e2 ...)
					     rest)]))]
				 [(c2 c3 ...)
				  (with-syntax ([rest (f #'c2 #'(c3 ...))])
				    (syntax-case c1 (=>)
				      [(e0) #'(let ([t e0]) (if t t rest))]
				      [(e0 => e1)
				       #'(let ([t e0]) (if t (e1 t) rest))]
				      [(e0 e1 e2 ...)
				       #'(if e0
					     (begin e1 e2 ...)
					     rest)]))]))))))))
		(lambda ()
		  e1 e2 ...))))]
      [_
       (syntax-violation who "invalid syntax" stx)])))

Invoking a continuation k on values obj … can be defined in terms of call-in-continuation:

(let ([tmp obj] …)
  (call-in-continuation k (lambda () (values tmp …))))

On the other hand, it is not possible to define call-in-continuation in terms of invoking a continuation, so the former is the more primitive notion.

Remark: That a primitive like call-in-continuation is needed, was already noted in A better API for first-class continuations. In that paper, it is called continuation-graft. (The two accompanying procedures continuation-capture and continuation-return in that paper are just call/cc and apply in the context of this SRFI, which treats continuations as procedures for compatiblity reasons.)

(call-with-continuation-barrier thunk)

The call-with-continuation-barrier procedure instates an otherwise inaccessible continuation prompt in the current continuation and marks it as a continuation barrier. Finally, thunk is called with no arguments in the resulting continuation.

When applying a non-composable continuation would reinstate a continuation barrier, an exception with condition type &continuation is raised.

If a continuation barrier is captured during a call to call-with-composable-continuation, an exception with condition type &continuation is raised.

This extends the semantics of call-with-non-composable-continuation and call-with-composable-continuation.

The calls to the thunks are never in tail context.

Note: As calling a composable continuation never aborts active procedure calls, a continuation barrier would be reinstated if and only if the captured continuation included a continuation barrier.

A continuation barrier prevents jumps into more deeply nested active procedure calls:

((call-with-continuation-barrier
  (lambda ()
    (call/cc values))))&continuation-violation exception

On the other hand, escaping jumps are not prohibited:

(call/cc
  (lambda (k)
    (call-with-continuation-barrier
      (lambda ()
        (k 'ok)))))ok
(continuation-prompt-available? prompt-tag)
(continuation-prompt-available? prompt-tag cont)

The first form is operationally equivalent to (continuation-prompt-available? prompt-tag (call/cc values)).

Returns #t if a continuation prompt tagged with prompt-tag is available in the continuation packaged in cont or if cont is a non-composable continuation delimited by prompt-tag, and #f otherwise.

(define tag (make-continuation-prompt-tag))
(call-with-continuation-prompt-tag
  (lambda ()
    (continuation-prompt-tag-available? tag
      (call-with-non-composable-continuation values))))#t
(call-with-continuation-prompt-tag
  (lambda ()
    (continuation-prompt-tag-available? tag
      (call-with-non-composable-continuation values tag))))#t
(call-with-continuation-prompt-tag
  (lambda ()
    (continuation-prompt-tag-available? tag
      (call-with-composable-continuation values tag))))#f
(dynamic-wind pre-thunk thunk post-thunk)

The dynamic-wind procedure calls pre-thunk with no arguments in a continuation that calls thunk with no arguments in a continuation that calls post-thunk in a continuation with no arguments that finally delivers the results of the call to thunk to the continuation of the call to dynamic-wind.

Moreover, when the active call to thunk is aborted (either due to a prompt abort or a continuation procedure invocation), post-thunk is called with no arguments, and when the active call to thunk is reinstated (due to a continuation procedure invocation), pre-thunk is called with no arguments.

Each call to pre-thunk and post-thunk belongs to the dynamic extent of the original call to dynamic-wind.

Note: When a call to pre-thunk or post-thunk returns during a prompt abort or a continuation procedure invocation, the sequence of active procedure calls that still have to be aborted and the sequence of active procedure calls that still have to be reinstated may have changed due to the application of composable continuations captured in pre-thunk or post-thunks.

This extends the semantics of abort-current-continuation, call-with-non-composable-continuation, and call-with-composable-continuation.

The calls to the thunks are never in tail context.

The following example comes form R6RS and demonstrates jumping out of the post-thunk.

(let ([n 0])
  (call/cc
    (lambda (k)
      (dynamic-wind
          values
          (lambda ()
            (dynamic-wind
                values
                (lambda ()
                  (set! n (+ n 1))
                  (k))
                (lambda ()
                  (set! n (+ n 2))
                  (k))))
         (lambda ()
           (set! n (+ n 4))))))
  n)7

Continuation Marks

This section describes the (srfi :226 control continuation-marks) library. This library, in addition to the procedures described here, also exports the condition types described in the section on continuation prompts.

Continuation Marks

Continuation frames can be annotated with continuation marks. Each continuation mark maps a key, which can be an arbitrary object, to a value, which can also be an arbitrary object. If a continuation frame is annotated with a continuation mark for a key for which the continuation frame has already been annotated with a mark, the most recent annotation prevails.

Remark: In A better API for first-class continuations, the idea of a portable debugger using a procedure named continuation-next to walk up a continuation was presented. With continuation marks this can be easily achieved when frames are explicitly marked. The advantage of an explicit marking is that the debugger can then be instructed to automatically skip over frames installed by standard library procedures, for example. A Scheme system could offer a debug mode, in which every frame is automatically marked in a specific way that is understood by the debugger.

(with-continuation-mark key-expr val-expr expression)

Syntax: Key-expr, val-expr, and expression are expressions.

Semantics: Key-expr and val-expr are evaluated in an unspecified order to obtain a key and a value, respectively. The most recent continuation frame in the continuation of the with-continuation-mark expression is then dynamically annotated with a continuation mark mapping the key to the value, and expression is evaluated in the continuation of the with-continuation-mark expression.

If a with-continuation-mark expression is in tail context, expression is in tail context as well.

Note: That with-continuation-mark is a special form and not modeled as a procedure calling a thunk goes back to the paper Modeling an Algebraic Stepper, which introduced continuation marks. In fact, it makes optimization for a Scheme compiler easier, and with-continuation-mark needs to be efficient given its typical use cases.

(with-continuation-marks ([key-expr val-expr] …) body)

Syntax: The key-exprs and the val-exprs are be expressions, and body is be a body.

Semantics: The key-exprs and the val-exprs are evaluated in an unspecified order to obtain a list of keys and a list of corresponding values, respectively. The most recent continuation frame in the continuation of the with-continuation-marks expression is then dynamically annotated with a continuation mark mapping the keys to the values, and body is evaluated in the continuation of the with-continuation-marks expression.

It is unspecified which value prevails if two of the keys are the same.

If a with-continuation-marks expression is in tail context, the last expression of body is in tail context as well.

(call-with-immediate-continuation-mark key proc)
(call-with-immediate-continuation-mark key proc obj)

If not supplied, obj defaults to #f.

If the most recent continuation frame in the continuation of the call to call-with-immediate-continuation-mark is annotated with a continuation mark mapping key to a value, proc is applied to the value, and to obj otherwise.

If a call to call-with-immediate-continuation-mark occurs in a tail context, the call to proc is also in a tail context.

(with-continuation-mark 'key 'mark
  (call-with-immediate-continuation-mark 'key values))mark

(let ([tag (make-continuation-prompt-tag)])
  (with-continuation-mark 'key 'mark
    (call-with-continuation-prompt
      (lambda ()
        (call-with-immediate-continuation-mark 'key values 'default))
      tag)))default

In the second example, we installed a continuation prompt with some unrelated tag to make sure that the call to call-with-immediate-continuation-mark is not in tail context with respect to the with-continuation-mark expression.

(continuation-marks cont)
(continuation-marks cont prompt-tag)

If not supplied, prompt-tag defaults to the default prompt tag.

Returns a continuation mark set capturing the continuation marks of the continuation frames in the continuation cont up to the continuation prompt prompt-tag.

If no continuation prompt tagged with prompt-tag is available in cont and the continuation cont is not delimited by prompt-tag, an exception with condition type &continuation is raised.

(current-continuation-marks)
(current-continuation-marks prompt-tag)

If not supplied, prompt-tag defaults to the default prompt tag.

Operationally equivalent to (continuation-marks (call/cc values prompt-tag) prompt-tag).

(continuation-mark-set? obj)

Returns #t if obj is a continuation mark set, and #f otherwise.

(continuation-mark-set? (current-continuation-marks))#t
(continuation-mark-set->list mark-set key)
(continuation-mark-set->list mark-set key prompt-tag)

If not supplied, prompt-tag defaults to the default prompt tag.

Returns a newly allocated list containing the values of the continuation marks for key captured in mark-set up to where the corresponding continuation frames were separated by a continuation prompt tagged prompt-tag, if at all. The list elements correspond to the continuation frames that contained a continuation mark for key, with the most recent continuation frame coming first.

If mark-set is #f, the mark set that would be returned by (current-continuation-marks prompt-tag) is used instead.

(continuation-mark-set->list* mark-set list)
(continuation-mark-set->list* mark-set list obj)
(continuation-mark-set->list* mark-set list obj prompt-tag)

If not supplied, obj defaults to #f.

If not supplied, prompt-tag defaults to the default prompt tag.

Returns a newly allocated list containing newly allocated vectors. The vectors contain the values of the continuation marks for the keys in list captured in mark-set up to where the corresponding continuation frames were separated by a continuation prompts tagged prompt-tag, if at all, as follows: Each vector contains the continuation marks of a single continuation frame for the keys contained in list. If such a continuation frame has no mark for some key in list, the values obj is used. The vectors in the newly allocated list correspond to the continuation frames that contain a continuation mark for at least one key in list with the most recent continuation frames coming first.

If mark-set is #f, the mark set that would be returned by (current-continuation-marks prompt-tag) is used instead.

(define tag (make-continuation-prompt-tag))
(define key (make-continuation-mark-key))
(define key1 (make-continuation-mark-key))
(define key2 (make-continuation-mark-key))

(with-continuation-mark key 'mark1
  (with-continuation-mark key 'mark2
    (call-with-continuation-prompt
      (lambda ()
        (with-continuation-mark key 'mark3
          (continuation-mark-set->list #f key))))))(mark3 mark2)

(with-continuation-mark key1 'mark1
  (with-continuation-mark key2 'mark2
    (call-with-continuation-prompt
     (lambda ()
       (with-continuation-mark key1 'mark3
         (continuation-mark-set->list* #f (list key1 key2) 'default)))
     tag))(#(mark3 default) #(mark1 mark2))
(continuation-mark-set->iterator mark-set list)
(continuation-mark-set->iterator mark-set list obj)
(continuation-mark-set->iterator mark-set list obj prompt-tag)

If not supplied, obj defaults to #f.

If not supplied, prompt-tag defaults to the default prompt tag.

Returns an iterator for the list that would be constructed by continuation-mark-set->list when applied to the same arguments.

Note: Some recent SRFIs that have been included into early editions of R7RS Large or are to be included in its forthcoming editions feature the use of generators (see SRFI 158) to process lists (or objects of other sequence types). As generators are fundamentally non-pure, we believe that their use should be limited in otherwise functional code. The iterator concept used here, on the other hand, is fully functional. It does have to be modified for lists that may potentially contain #f, which cannot happen here.

If mark-set is #f, the mark set that would be returned by (current-continuation-marks prompt-tag) is used instead.

A correct but possibly inefficient implementation of continuation-mark-set->iterator is given as follows:

(define continuation-mark-set->iterator
  (lambda arg*
    (let f ([ls (apply continuation-mark-set->list arg*)])
      (lambda ()
        (if (null? ls)
          (values #f (f '()))
          (values (car ls) (f (cdr ls))))))))
(continuation-mark-set-first mark-set key)
(continuation-mark-set-first mark-set key obj)
(continuation-mark-set-first mark-set key obj prompt-tag)

If not supplied, obj defaults to #f.

If not supplied, prompt-tag defaults to the default prompt tag.

Returns the first element for the list that would be constructed by continuation-mark-set->list when applied to the same arguments, or obj if the result would be the empty list.

If mark-set is #f, the mark set that would be returned by (current-continuation-marks prompt-tag) is used instead.

(let ([tag (make-continuation-prompt-tag)]
      [key (make-continuation-mark-key)])
  (with-continuation-mark key 'mark1
    (call-with-continuation-prompt
     (lambda ()
       (with-continuation-mark key 'mark2
         (continuation-mark-set-first #f key)))
     tag)))mark2

Mark Keys

Mark keys can be used as opaque keys for continuation marks.

(make-continuation-mark-key)
(make-continuation-mark-key name)

Returns a mark key that is not equal? to any prior or future results from make-continuation-mark-key.

The optional name argument may be used by the implementation for printing the mark key.

(continuation-mark-key? obj)

Returns #t if obj is a mark key, and #f otherwise.

(continuation-mark-key? (make-continuation-mark-key))#t
(equal? (make-continuation-mark-key) (make-continuation-mark-key))#f

Parameter Objects

This section describes the (srfi :226 control parameters) library.

Each parameter object is a procedure.

A parameterization is an opaque mapping of parameter objects to cells that hold a value.

Conceptually, each continuation contains at least one otherwise inaccessible parameterization continuation mark, whose value is a parameterization. The parameterization of a continuation is the value of the most recent parameterization continuation mark in the continuation. The parameterization of the current continuation is the current parameterization.

The parameterization of the initial continuation of a top-level program maps each current and future parameter object to a cell holding its initial value.

(make-parameter obj)
(make-parameter obj proc)

Invokes proc on obj in the dynamic environment of the call to make-parameterto obtain a value and returns a newly allocated parameter object, which is a procedure accepting zero or one argument and whose initial value is the value and whose conversion procedure is proc.

When a parameter object is invoked with zero arguments, the content of the cell of the parameter object in the parameterization of the invocation is returned.

When a parameter object is invoked with one argument, its conversion function is applied to it in the dynamic environment of the call to the parameter object to obtain a new value. The previous value contained in the cell of the parameter object in the parameterization of the invocation is then replaced with the new value. The result of the invocation is unspecified.

(parameterize ([param-expr expression] …) body)

Syntax: The param-exprs and the expressions are expressions, and body is a body.

Semantics: Evaluates the param-exprs and expressions in an arbitrary order to obtain parameter objects and arbitrary objects, respectively. An assertion violation is raised if one of the obtained parameter objects is not actually a parameter object. The objects are then mapped to respective values by invoking the conversion procedures of the corresponding parameter objects in the dynamic environment of the parameterize expression on them. For each parameter object, a newly allocated cell is then constructed that holds the obtained corresponding value. A new parameterization that differs from the parameterization of the continuation of the parameterize expression in mapping the obtained parameter objects to the respectively newly allocated cells is then constructed. Finally, the most recent continuation frame in the continuation of the parameterize expression is annotated with a parameterization continuation mark whose value is the new parameterization and the body is evaluated in this continuation.

It is unspecified which value prevails if two of the parameter objects are the same.

If a parameterize expression is in tail context, the last expression in body is in tail context as well.

(current-parameterization)

Returns the current parameterization.

(parameterization? obj)

Returns #t if obj is a parameterization, and #f otherwise.

(call-with-parameterization parameterization thunk)

Annotates the most recent continuation frame in the current continuation with a parameterization continuation mark whose value is parameterization, and invokes proc in this continuation.

In particular, if a call to call-with-current-parameterization occurs in a tail context. the call to proc is also in a tail context.

While the following example demonstrates many features of parameter objects, it should not be considered to illustrate good programming style. Usually, the conversion procedure should be idempotent.

(define p (make-parameter 10 (lambda (x) (* x x))))
(define ps #f)

(p)100

(p 12)
(p)144

(parameterize ([p (p)])
  (set! ps (current-parameterization))
  (p))20736
(p)144

(parameterization? ps)#t

(call-with-parameterization ps
  (lambda ()
    (let ([x (p)])
      (p 0)
      (list x (p)))))(20736 0)

(p)144

The following example shows how continuation marks can be used to test that the last expression in a parameterize body is in tail context if the parameterize expression itself is:

(with-continuation-mark 'in-tail-context? #t
  (parameterize ([(make-parameter 0) 1])
    (call-with-immediate-continuation-mark 'in-tail-context? values)))#t

Note: The parameter objects defined in this specification are fully compatible with the parameter objects of SRFI 39 and R7RS but add the requirement that the last expression in the body of a parameterize expression in tail context is in tail context as well. With respect to multiple threads, this specification differs from Racket in that the cells associated with parameter objects are not “thread-local” in this specification. As has already been observed by Marc Feeley during the discussion period of SRFI 39, this is the cleaner, faster, and more expressive semantics. Finally, the parameter objects defined here are not fully compatible with the parameters of Chez Scheme. While these offer some features over the parameter objects in SRFI 39 and R7RS, they would be incompatible with the tail-context guarantee of the parameterize form.

Initial Continuations

This section describes the (srfi :226 control call-in-initial-continuation) library. The library, in addition to the procedures and syntax described here, also exports the &uncaught-exception condition type and associated procedures from (srfi :226 control threads).

An initial continuation is one that consists of a single continuation prompt tagged with the default prompt tag and with the default handler. Moreover, a single initial exception handler is installed in an initial continuation that, when invoked on a &serious condition or on a non-condition object, aborts to the most recent continuation prompt tagged with the default prompt tag and calls its handler with a thunk that, when evaluated, raises an exception whose condition is the object. When invoked on a non-&serious condition object, the initial handler returns with unspecified values instead.

Note: There is usually more than one initial continuation. The primordial thread starts in an initial continuation, but new initial continuations are created when new threads or new promises are created or when the procedure call-in-initial-continuation is invoked (see below).

Executing a top-level program starts with the initial continuation. When values are delivered in the initial continuation, the program exits normally. When an exception is raised in the dynamic extent of the handler of the initial continuation prompt, the program may exit or may provide a choice of other options. It is expected that the initial exception handler reports that an exception has been raised, and displays information about the condition object that was provided.

This extends the semantics of raise.

(call-in-initial-continuation thunk)procedure

Calls thunk in an initial continuation. The parameterization of the initial continuation is the same as the parameterization of the continuation of the call to call-in-initial-continuation. When values are delivered to the initial continuation, the values are delivered to the continuation of the call to call-in-initial-continuation. When an exception is raised in the dynamic extent of the handler of the continuation prompt of the initial continuation, an &uncaught-exception-error condition whose reason is the raised object is raised in the continuation of the call to call-in-initial-continuation.

This extends the semantics of raise.

(let ([tag (make-continuation-prompt-tag)]
      [p (make-parameter 0)])
  (parameterize ([p 1])
    (call-in-initial-continuation
      (lambda ()
        (list (continuation-prompt-available? (call/cc values))
              (p))))))(#f 1)

(guard (c
        [(uncaught-exception-error? c) (uncaught-exception-error-reason c)])
  (call-in-initial-continuation
    (lambda ()
      (raise 42))))42

Promises

This section describes the (srfi :226 control promises) library. The library, in addition to the procedures and syntax described here, also exports the &uncaught-exception condition type and associated procedures from (srfi :226 control threads).

Promises are objects that can be forced to deliver values or raise exceptions.

(delay body)

Syntax: Body is a body.

Semantics: Evaluates to a promise that behaves as follows when forced in a continuation k: If the promise already has delivered values, the same values are delivered again, and if the promise already has raised an exception, the same exception is raised again in the continuation k. Otherwise, body is evaluated in an initial continuation. The parameterization of the initial continuation is the same as the parameterization of the continuation of the original delay expression. When values are delivered to the initial continuation and the promise still hasn't delivered values or has raised an exception, the values are delivered to the continuation in which the promise was forced. Otherwise, the already delivered values are delivered again, or the already raised exception is raised again in the continuation k. When an exception is raised in the dynamic extent of the handler of the continuation prompt of the initial continuation and the promise still hasn't delivered values or has raised an exception, an &uncaught-exception-error condition whose reason is the object is raised in the continuation k. Otherwise, the already delivered values are delivered again, or the already raised exception is raised again in the continuation k.

If a call to force occurs in tail context during the evaluation of body, it is effectively a tail call.

All operations involved in forcing except for the evaluation of the body are required to be atomic.

Note: The extra requirement about calls to force in tail contexts makes the extra delay-force syntax of R7RS (see also SRFI 45, where it is called lazy) unnecessary.

(make-promise obj …)

Returns a promise that, when forced in a continuation, delivers the values obj … to the continuation.

Note: R7RS includes the description of a one-argument procedure also named make-promise that behaves as the make-promise procedure defined here when applied to a single non-promise object. As the semantics of make-promise in R7RS makes it mostly useless and does not allow the obvious generalization to multiple values, we have decided to break compatibility for the better.

(promise? obj)

Returns #t if obj is a promise, and #f otherwise.

(force promise)

The force procedure forces promise in the continuation of the call to force.

Note: R7RS includes the unfortunate requirement that the body of a delay form has to be evaluated in the dynamic environment of the call to force. This makes the result of forcing a promise dependent on the time when the promise is forced even in purely functional code. As has already been observed Marc Feeley during the discussion period of SRFI 39, the more consistent semantics would have been to evaluate the body of a delay form in the parameterization of that form. The delay syntax defined in this specification has the more consistent semantics and is breaking compatibility with R7RS for what we think is the better. The semantics defined here also work well in the presence of capturing and applying continuations. In fact, with regard to the dynamic environment, the semantics of promises are now equivalent to that of threads.

(promise? (make-promise 1 2))#t
(promise? (delay 3))#t
(promise? (force (make-promise (make-promise 4))))#t

(call-with-values
    (lambda ()
      (force
       (delay
         (define x 1)
         (values x 2))))
  list)(1 2)

(let* ([p (make-parameter 3)]
       [q (parameterize
              ([p 5])
            (delay (p)))])
  (force q))5

(let* ([x 0]
       (q (delay
            (set! x (+ x 1))
            (raise #t))))
  (guard (c [(uncaught-exception-error? c)])
    (force q)
    (set! x (+ x 2)))
  (guard (c [(uncaught-exception-error? c)])
    (force q)
    (set! x (+ x 4)))
  x)1

Exceptions

This section describes the (srfi :226 control exceptions) library.

Conceptually, each continuation contains at least one otherwise inaccessible exception handler stack continuation mark, whose value is a list of exception handlers, which are one-argument procedures. The exception handler stack of a continuation is the value of the most recent exception handler stack continuation mark in the continuation. The exception handler stack of the current continuation is the current exception handler stack. The current exception handler is the first element of the current exception handler stack. An exception handler (procedure) is installed in a continuation by recording the exception handler stack of the continuation, constructing a new exception handler stack by prepending the exception handler to be installed to the recorded exception handler stack, and annotating the continuation with an exception handler stack continuation mark whose value is the new exception handler stack. The most recent exception handler is removed in a continuation by recording the exception handler stack of the continuation, constructing a new exception handler stack by removing the first element of the recorded exception handler stack, and annotating the continuation with an exception handler stack continuation mark whose value is the new exception handler stack.

(with-exception-handler handler thunk)

It is an assertion violation if handler is not a procedure or does not accept one argument.

Installs handler in the continuation to the call to with-exception-handler, calls thunk with no arguments, and delivers the resulting values to the continuation of the call to with-exception-handler.

If a call to with-exception-handler occurs in a tail context, the call to thunk is also in a tail context.

Note: The tail context requirement is neither in R6RS nor in R7RS.

(exception-handler-stack)

Returns a newly allocated list containing the handlers of the current exception handler stack, with the most recently installed handlers coming first.

(current-exception-handler)

Returns the current exception handler.

(raise obj)

Raises a non-continuable exception as follows: The current exception handler is recorded and then the most recent exception handler is removed in the continuation to the call to raise. The recorded exception handler is then invoked on obj. If this invocation returns, a non-continuable exception with condition type &non-continuable is raised in the continuation of the call to raise.

If there is no current exception handler because the current exception handler stack is empty, the current continuation is instead aborted to the most recent continuation prompt tagged with the default continuation prompt tag, and its handler invoked on a thunk that, when called, raises obj.

Note: The current exception handler stack becomes empty if the initial exception handler returns after having been invoked on a non-&serious condition, which causes a &non-continuable condition to be raised.

(raise-continuable obj)

Raises a continuable exception as follows: The most recent continuation frame in the continuation to the call to raise-continuable is annotated with an exception handler stack continuation mark whose value is the current handler stack with the first element removed. The previously first element is then invoked on obj, and its values are returned.

If there is no current exception handler because the current exception handler stack is empty, the current continuation is instead aborted to the most recent continuation prompt tagged with the default continuation prompt, and its handler invoked on a thunk that, when called, raises obj.

If a call to raise-continuable occurs in a tail context, the call to the current exception handler is also in a tail context.

Note: The tail context requirement is neither in R6RS, nor in R7RS. It is in SRFI 18, whose raise corresponds to raise-continuable in R6RS and R7RS.

(guard (variable cond clause1 cond clause2) body)
=>auxiliary syntax
elseauxiliary syntax

Syntax: Each cond clause is as in the specification of cond. Variable is an identifier and body a body.

Semantics: Installs an exception handler as described below in the continuation of the guard expression, and evaluates body. The installed exception handler captures and records the current continuation delimited by the default prompt tag. It then aborts to the continuation of the guard expression or to the most recent continuation prompt tagged with the default prompt tag, whatever comes first. It then binds the raised object to variable and, within the scope of that binding, evaluates the clauses as if they were the clauses of a cond expression. If every cond clause evaluates to #f and there is no else clause, the recorded continuation is reinstated with the most recent exception handler removed and a continuable exception with the same object originally raised is raised in the resulting continuation. Otherwise, the resulting values of the equivalent cond expression are delivered to the aborted continuation (the one captured and recorded).

If a guard expression is in tail context, the last expression in body is in tail context as well. The final expression in a cond clause is in a tail context if the guard expression itself is.

Note: The tail context requirement on the body of a guard expression is neither in R6RS, nor in R7RS.

(guard (c [(eqv? c 42) c])
  (+ 1
     (call-with-continuation-prompt
       (lambda ()
         (raise 42)))))43

Threads

This section describes the (srfi :226 control threads) library. The library is compatible and mostly API-compatible with SRFI 18. For detailed examples and a detailed rational, please see that SRFI. The author of this document does not claim any additional major contributions; in fact, a lot of text from SRFI 18 was copied verbatim or mostly verbatim.

The concepts of a thread, a mutex, and a condition variable are described in the corresponding subsections below. As in SRFI 18, we do not require specific fairness constraints from implementations of this SRFI. Please see SRFI 18 for more comments on fairness.

The API described in this sections differs from the API provided by SRFI 18 in the following points:

A timeout is represented either by a real number (object) or by #f. If it is a real number, a relative time in a number of seconds given by the real number is represented (negative numbers the represented time is in the past relative to the current time). If it is #f, an absolute time lying infinitely far in the future is represented (meaning effectively no timeout). A missing optional timeout value defaults to #f.

Conditions

&threadcondition-type
(make-thread-error obj)
(thread-error? obj)

This condition type could be defined by

(define-condition-type &thread &error
  make-thread-error thread-error?)

This is a supertype for a set of more specific thread errors.

&uncaught-exceptioncondition-type
(make-uncaught-exception-error obj)
(uncaught-exception-error? obj)
(uncaught-exception-error-reason condition)

This condition type could be defined by

(define-condition-type &uncaught-exception &thread
  make-uncaught-exception-error uncaught-exception-error?
  (reason uncaught-exception-reason))

Both uncaught-exception-error? and uncaught-exception-error-reason are the same as uncaught-exception and uncaught-exception-reason in SRFI 18.

Note: The names defined in this specification are more in line with the naming conventions in R6RS.

&thread-already-terminatedcondition-type
(make-thread-already-terminated-error obj)
(thread-already-terminated-error? obj)

This condition type could be defined by

(define-condition-type &thread-already-terminated &thread
  make-thread-already-terminated-error thread-already-terminated-error?)

The procedure thread-already-terminated-error? is the same as terminated-thread-exception? in SRFI 18.

&thread-timeoutcondition-type
(make-thread-timeout-error obj)
(thread-timeout-error? obj)

This condition type could be defined by

(define-condition-type &thread-timeout &thread
  make-thread-timeout-error thread-timeout-error?)

The procedure thread-timeout-error? is the same as join-timeout-exception? in SRFI 18.

&thread-abandoned-mutexcondition-type
(make-thread-abandoned-mutex-error obj)
(thread-abandoned-mutex-error? obj)

This condition type could be defined by

(define-condition-type &thread-abandoned-mutex &thread
  make-thread-abandoned-mutex-error thread-abandoned-mutex-error?)

The procedure thread-abandoned-mutex-error? is the same as abandoned-mutex-exception? in SRFI 18.

&concurrent-modificationcondition-type
(make-concurrent-modification-violation)
(concurrent-modification-violation? obj)

This condition type could be defined by

(define-condition-type &concurrent-modification-violation &assertion
	  make-concurrent-modification-violation concurrent-modification-violation?)

A &concurrent-modification violation is raised when a concurrent modification of a non-thread safe data structure is detected.

The following example gives an implementation of list->vector utilizing &concurrent-modification:

(define list->vector
  (lambda (ls)
    (define-syntax safe
      (syntax-rules ()
        [(safe expr)
         (guard (exc [(assertion-violation? exc)
                      (raise
                        (condition
                          (make-who-condition 'list->vector)
                          (make-message-condition "argument concurrently modified")
                          (make-irritants-condition (list ls))
                          (make-concurrent-modification-violation)))])
           expr)]))
    (let ([n (length ls)])
      (do ([v (make-vector n)]
           [i 0 (fx+ i 1)]
           [ls ls (safe (cdr ls))])
          ((fx=? i n) v)
        (vector-set! v i (safe (car ls)))))))

Threads

A thread is a Scheme value of a specific type, representing a virtual processor which shares object space with all other threads.

A running thread is a thread that is currently executing. There can be more than one running thread on a multiprocessor machine. A runnable thread is a thread that is ready to execute or running. A thread is blocked if it is waiting for a mutex to become unlocked, an I/O operation to become possible, the end of a sleep period, etc. A new thread is a thread that has not yet become runnable. A new thread becomes runnable when it is started. A terminated thread is a thread that can no longer become runnable (but "deadlocked" threads are not considered terminated).

The only valid transitions between the thread states are from new to runnable, between runnable and blocked, and from any state to terminated. Any attempt to cause an invalid transition raises an assertion violation.

(make-thread thunk)procedure

Returns a new thread. This thread is not automatically made runnable (the procedure thread-start! must be used for this).

The thread's execution consists of a call to thunk in an initial continuation as defined above. The parameterization of the initial continuation is the same as the parameterization of the continuation of the invocation of make-thread. When an exception e is raised in the dynamic extent of the handler of the initial continuation prompt, an &uncaught-exception error object is recorded to be raised for this thread and the thread finally terminated. The reason field of the &uncaught-exception error object is populated with the exception e. When values are delivered to the initial continuation, the values are recorded to be delivered for this thread and the thread is finally terminated.

When a thread is finally terminated, all mutexes it owns are abandoned.

This extends the semantics of raise.

(thread body)syntax

Syntax: Body is a body.

Semantics: Operationally equivalent to evaluating (make-thread (lambda () body)).

Note: As threads inherit the parameterization of when they are created, a thread expression conveys the meaning better than a call to make-thread.

(thread? obj)procedure

Returns #t if obj is a thread, and #f otherwise.

(current-thread)procedure

Returns the current thread.

(thread-start! thread)procedure

Makes thread runnable and returns it. The thread thread must be a new thread.

Note: It is useful to separate thread creation and thread activation to avoid the race condition that would occur if the created thread tries to examine a table in which the current thread stores the created thread.

(thread-yield!)procedure

The current thread exits the running state. Returns unspecified values.

(thread-sleep! timeout)procedure

The current thread waits until the timeout timeout is reached. This blocks the thread only if timeout represents a point in the future. The procedure thread-sleep! returns unspecified values.

An assertion violation is raised if timeout is #f.

(thread-terminate! thread)procedure

Schedules an abnormal termination of thread. When the termination is due and if the thread is not already terminated, all mutexes owned by the thread become unlocked/abandoned and a &thread-already-terminated error object to be raised is recorded for this thread.

If thread is the current thread, thread-terminate! does not return. Otherwise, the current thread waits until the termination of thread has occurred. Afterward, thread-terminate! returns unspecified values.

If a thread is scheduled for (abnormal) termination and is blocked, the termination is due and the thread terminated before it would be unblocked.

Note: This operation must be used carefully because it terminates a thread abruptly and it is impossible for that thread to perform any kind of cleanup. This may be a problem if the thread is in the middle of a critical section where some structure has been put in an inconsistent state. However, another thread attempting to enter this critical section will raise an &thread-abandoned-mutex violation because the mutex is unlocked/abandoned. This helps avoid observing an inconsistent state.

(thread-join! thread timeout)procedure
(thread-join! thread)procedure

The current thread waits until thread terminates (normally or not) or until the timeout timeout is reached. If the timeout is reached, a &thread-timeout error is raised. Otherwise, if an error object to be raised is recorded for this thread, it is raised. Otherwise, the result values to be delivered that are recorded for this thread are delivered.

(thread body)syntax

Syntax: Body is a body.

Semantics: Operationally equivalent to evaluating (make-thread (lambda () body)). The initial continuation is an initial continuation as defined above. The parameterization of the initial continuation is the same as the parameterization of the continuation of the thread expression. When an exception is raised in the dynamic extent of the handler of the initial continuation prompts, a condition with type &uncaught-exception and the raised object as its reason is stored in the end-exception of the thread before the thread is finally terminated. When values are delivered to the initial continuation, the values are stored in the end-result of the thread before the thread is finally terminated.

This extends the semantics of raise.

Note: This also defines the initial continuation of a thread created by invoking the make-thread procedure in SRFI 18.

Note: As threads inherit the parameterization of when they are created, a thread expression conveys the meaning better than a call to make-thread.

(let ([p (make-parameter 0)])
(parameterize ([p 1])
  (let ([y
         (thread-join!
          (thread-start!
           (thread
             (let ([x (p)])
               (p 2)
               x))))])
    (list y (p)))))(1 2)
(let [(l '())]
  (define out!
    (lambda (x)
      (set! l (cons x l))))
  (define get
    (lambda ()
      (reverse l)))
  (thread-join!
   (thread-start!
    (thread
      (dynamic-wind
          (lambda ()
            (out! 'in))
          (lambda ()
            (call/cc
             (lambda (k)
               (thread-join!
                (thread-start!
                 (thread
                   (out! 'thread)
                   (k)))))))
          (lambda ()
            (out! 'out))))))
  (get))(in thread in out out)

Mutexes

A mutex is a Scheme value of a specific type, representing a mutual exclusion device, also known as a lock and binary semaphore.

A mutex can be in one of four states: locked (either owned or not owned) and unlocked (either abandoned or not abandoned). An attempt to lock a mutex only succeeds if the mutex is in an unlocked state, otherwise the current thread must wait. A mutex in the locked/owned state has an associated owner thread, which by convention is the thread that is responsible for unlocking the mutex (this case is typical of critical sections implemented as "lock mutex, perform operation, unlock mutex"). A mutex in the locked/not-owned state is not linked to a particular thread. A mutex becomes locked when a thread locks it using the mutex-lock! primitive. A mutex becomes unlocked/abandoned when the owner of a locked/owned mutex terminates. A mutex becomes unlocked/not-abandoned when a thread unlocks it using the mutex-unlock! primitive. The mutex primitives specified in this SRFI do not implement recursive mutex semantics; an attempt to lock a mutex that is locked implies that the current thread must wait even if the mutex is owned by the current thread (this can lead to a deadlock if no other thread unlocks the mutex).

(make-mutex)procedure

Returns a new mutex in the unlocked/not-abandoned state.

(mutex? obj)procedure

Returns #t if obj is a mutex, and #f otherwise.

(mutex-owner mutex)procedure

Returns the owner thread of mutex if mutex is in the locked/owned state, and #f otherwise.

(mutex-state mutex)procedure

Returns one of the symbols owned, not-owned, abandoned, not-abandoned, reflecting the state of mutex.

Note: To simplify the type of mutex-state, this procedure differs from the procedure with the same name in SRFI 18. Use mutex-owner to access a mutex's owner.

(mutex-lock! mutex timeout owner-thread)procedure
(mutex-lock! mutex timeout)procedure
(mutex-lock! mutex)procedure

If owner-thread is not given, it defaults to #f.

If mutex is currently locked, the current thread waits until it is unlocked or until the timeout is reached. If the timeout is reached, #f is returned. Otherwise, mutex becomes locked with owner-thread as the owner unless owner-thread is terminated, in which case mutex becomes unlocked/abandoned.

After changing the state of the mutex, an &abandoned-mutex error is raised if the mutex was unlocked/abandoned before the state change, otherwise mutex-lock! returns #t.

Note: It is not an error if the mutex is owned by the current thread (but the current thread will have to wait).

(mutex-unlock! mutex condition-variable)procedure
(mutex-unlock! mutex)procedure

Unlocks the mutex by making it unlocked/not-abandoned. If condition-variable is supplied, the current thread is blocked and added to the condition-variable before unlocking mutex; the thread can unblock at any time but no later than when an appropriate call to condition-variable-signal! or condition-variable-broadcast! is performed (see below), and no later than the timeout. If there are threads waiting to lock this mutex, the scheduler selects a thread, the mutex becomes locked/owned or locked/not-owned, and the thread is unblocked. mutex-unlock! returns #f when the timeout is reached, otherwise it returns #t.

Note: It is not an error to unlock an unlocked mutex and a mutex that is owned by any thread.

Note: The reason the thread can unblock at any time (when condition-variable is supplied) is to allow extending this SRFI with primitives that force a specific blocked thread to become runnable. For example a primitive to interrupt a thread so that it performs a certain operation, whether the thread is blocked or not, may be useful to handle the case where the scheduler has detected a serious problem (such as a deadlock) and it must unblock one of the threads (such as the primordial thread) so that it can perform some appropriate action. After a thread blocked on a condition-variable has handled such an interrupt it would be wrong for the scheduler to return the thread to the blocked state, because any calls to condition-variable-broadcast! during the interrupt will have gone unnoticed. It is necessary for the thread to remain runnable and return from the call to mutex-unlock! with a result of #t.

Note: mutex-unlock! is related to the wait operation on condition variables available in other thread systems. The main difference is that wait automatically locks the mutex just after the thread is unblocked. This operation is not performed by mutex-unlock! and so must be done by an explicit call to mutex-lock!. This has the advantages that a different timeout and exception handler can be specified on the mutex-lock! and mutex-unlock! operations and the location of all the mutex operations is clearly apparent.

Condition variables

A condition variable is a Scheme value of a specific type, representing a set of blocked threads.

The blocked threads represented by a condition variable are waiting for a certain condition to become true. When a thread modifies some program state that might make the condition true, the thread unblocks some number of threads (one or all depending on the primitive used) so they can check the value of the condition. This allows complex forms of interthread synchronization to be expressed more conveniently than with mutexes alone.

(make-condition-variable)procedure

Returns a new empty condition variable.

(condition-variable? obj)procedure

Returns #t if obj is a condition variable, and #f otherwise.

(condition-variable-signal! condition-variable)procedure

If there are threads blocked on condition-variable, the scheduler selects a thread and unblocks it. The procedure condition-variable-signal! returns unspecified values.

Note: As their are no fairness constraints imposed on the scheduler by this SRFI, the scheduler may always select the same thread to unblock it. If in doubt, use condition-variable-broadcast! instead.

(condition-variable-broadcast! condition-variable)procedure

Unblocks all the threads blocked on condition-variable. The procedure condition-variable-broadcast! returns an unspecified values.

Thread locals

The procedures in this subsection are also exported by the (srfi :226 control thread-locals) library.

Thread locals are opaque values used to identify thread-specific locations.

The thread-specific storage is an opaque table associating to each current and future thread and to each thread local a cell that holds a value.

(make-thread-local obj)procedure

Returns a thread local that is not equal? to any prior or future results from make-thread-local. The object obj is stored the cells associated to the thread local in the thread-specific storage.

(thread-local? obj)procedure

Returns #t if obj is a thread local, and #f otherwise.

(tlref tl)procedure

Returns the value of the cell associated to the current thread and to tl in the thread-specific storage.

(tlset! tl obj)procedure

Sets the value of the cell associated to the current thread and to tl in the thread-specific storage to obj.

Implementation

Portability

Implementing the control operators presented in this SRFI solely in terms of the facilities provided in R6RS or R7RS is not possible.

Sample Implementation

The sample implementation accompanying this SRFI demonstrates how the control operators can be implemented on top of a small set of primitives. If in doubt, it favors simplicity and clarity over speed.

The small set of primitives that have to be provided are as follows:

(%call-with-current-continuation proc)

It is an error if proc is not a procedure taking a single argument.

Calls proc with the current undelimited continuation.

If a call to %call/cc occurs in a tail context, the call to proc is also in a tail context.

An undelimited continuation is represented by a procedure k that, when it is later called, abandons whatever undelimited continuation is in effect at that later time and instead reinstates the continuation that is represented by it.

Note: The primitive %call-with-current-continuation neither supports dynamic-wind nor continuation barriers. It can thus be viewed as the R4RS procedure with the name call-with-current-continuation.

(%call-in-continuation k thunk)

Abandons whatever undelimited continuation is in effect, and calls thunk with the undelimited continuation represented by k as the continuation of the call.

(%continuation=? k1 k2)

Returns #t if the undelimited continuation represented by k1 is the same as the undelimited continuation represented by k2, and #f otherwise.

Note: Procedure equivalence with respect to the standard predicates eq?, eqv?, and equal? is unspecified at least in some versions of the Scheme programming language.

(%case-lambda-box expression [formals body] ...)

Syntax: Expression is an expression, the formalss are a formal parameter list and the bodys are bodies.

Semantics: When a %case-lambda-box expression is evaluated, it first evaluates expression, stores the resulting value in a new location, and then returns a procedure that when later called with some arguments behaves as if the procedure were created by evaluating (case-lambda [formals body] ...) and that is tagged with the new location.

(%case-lambda-box-ref proc obj)

If proc is a procedure tagged with a location, the %lambda-box-ref procedure returns the value stored in this location, and obj otherwise.

Other Implementations

A lot of the control operators of this SRFI are natively implemented in Racket. A high-performance implementation of continuation marks is described in Compiler and runtime support for continuation marks.

Acknowledgements

This SRFI borrows heavily from Racket's collection of control operators.

The sample implementation builds upon the ideas presented in A Monadic Framework for Delimited Continuations and found in Racket's CS implementation.

Thanks go to Lassi Kortela for pointing out Marc Feeley's A better API for first-class continuations to me, and to John Cowan and Vladimir Nikishkin for very careful readings of the first draft and providing me with a lot of helpful comments.

This document uses text copied verbatim from SRFI 18.

Finally, I would like to thank Arthur A. Gleckler for encouraging me to write a SRFI covering delimited continuations.

References

  1. Chez Scheme.

  2. John Clements, Matthew Flatt, Matthias Felleisen: Modeling an Algebraic Stepper, ESOP 2001: Programming Languages and Systems, pp. 320–334

  3. William Clinger, Jonathan Rees: Revised4 Report on the Algorithmic Language Scheme.

  4. Olivier Danvy, Andrzej Filinski: Abstracting control, LFP '90: Proceedings of the 1990 ACM conference on LISP and functional programming, May 1990, pp. 151–160. DOI: 10.1145/91556.91622.

  5. R. Kent Dybvig, Simon Peyton Jones, and Amr Sabry: A monadic framework for delimited continuations, Journal of Functional Programming, Volume 17, Issue 6, November 2007, pp. 687-730. DOI: 10.1017/S0956796807006259.

  6. Marc Feeley: SRFI 18: Multithreading support.

  7. Marc Feeley: SRFI 39: Parameter objects.

  8. Marc Feeley: A better API for first-class continuations, Scheme and Functional Programming Workshop (SFPW'01), pages 1-3, September 2001.

  9. Andrzej Filinski: Representing monads, POPL '94: Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, February 1994, pp. 446-457. DOI: 10.1145/174675.178047.

  10. Matthew Flatt, R. Kent Dybvig: Compiler and runtime support for continuation marks, PLDI 2020: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, June 2020, pp. 45-58. DOI: 10.1145/3385412.3385981.

  11. Martin Gasbichler, Michael Sperber: Final shift for call/cc:: direct implementation of shift and reset, ACM SIGPLAN Notices, Volume 37, Issue 9, September 2002, pp. 271–282. DOI: 10.1145/583852.581504.

  12. ISO/IEC 9899:2018 Information technology — Programming languages — C

  13. Shiro Kawai, John Cowan, Thomas Gilray: SRFI 158: Generators and Accumulators.

  14. Richard Kelsey, William Clinger, Jonathan Rees (eds.): Revised5 Report on the Algorithmic Language Scheme, ACM SIGPLAN Notices, Volume 33, Issue 9, Sept. 1, 1998, pp. 26–76. DOI: 10.1145/290229.290234.

  15. Richard Kelsey, Michael Sperber: SRFI 34: Exception Handling for Programs.

  16. Oleg Kiselyov: An argument against call/cc.

  17. Marc Nieper-Wißkirchen: SRFI 154: First-class dynamic extents.

  18. Marc Nieper-Wißkirchen: SRFI 155: Promises.

  19. Marc Nieper-Wißkirchen: SRFI 157: Continuation marks.

  20. Portable Operating System Interface (IEEE 1003)

  21. R7RS Home Page.

  22. Racket.

  23. Alex Shinn, John Cowan, Arthur A. Gleckler: Revised7 Report on the Algorithmic Language Scheme.

  24. Michael Sperber, R. Kent Dybvig, Matthew Flatt, Anton van Straaten, Robby Findler, and Jacob Matthews: Revised6 Report on the Algorithmic Language Scheme. Journal of Functional Programming, Volume 19, Supplement S1, August 2009, pp. 1-301. DOI: 10.1017/S0956796809990074.

  25. David van Horn: SRFI 97: SRFI Libraries.

  26. André van Tonder: SRFI 45: Primitives for Expressing Iterative Lazy Algorithms.

© 2021 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.


Editor: Arthur A. Gleckler