This SRFI is currently in withdrawn status. Here
is an
explanation of each status that a SRFI can hold. To provide
input on this SRFI, please send email
to srfi-157@nospamsrfi.schemers.org.
To subscribe to the list,
follow these
instructions. You can access previous messages via the
mailing
list archive.
Continuation marks are a programming language feature that
allows one to attach information to and retrieve information
from continuations, generalizing stack inspection.
Conceptually, a continuation consists of a number of frames
where each frame stands for an active procedure call that is not
a tail call. A continuation mark is then a key-value pair
associated with a frame, with keys compared
using eq?.
At most one mark for a given key can be attached to a single frame.
Besides stack inspection, continuation marks can be used to implement dynamic scope, delimited continuations, or delayed evaluation that is able to handle iterative lazy algorithms.
This SRFI proposes to add continuation marks to the Scheme programming language. The interface defined here is modelled after Racket's continuation marks. It does not include all forms and procedures provided by Racket but provides a compatible subset.
One of the defining properties of the Scheme programming
language is that it is properly tail-recursive. The R7RS defines
that an implementation is properly tail-recursive if it
supports an unbounded number of active tail calls
, and goes on
to define which procedure calls occur in tail context
(see R7RS, section 3.5).
Being properly tail-recursive or, for a procedure call, to occur in tail context with respect to a lambda expression, is, however, a non-observable property. A non-properly tail recursive implementation of Scheme may be observably indistinguishable from a proper implementation as long as storage space is sufficient. (This is the same argument which is used in the implementation section of SRFI 124, where it is argued that there are no guarantees that a garbage collection is run at all, or even exists.)
Continuation marks are a programming language feature that, in particular, reifies the notion of proper tail calls. More generally, continuation marks allow one to attach values to the control stack (or, in Scheme terms, to the current continuation), and to retrieve these values later, and in such a way that it does not interfere with Scheme's tail-calling requirement.
Continuation marks can be used to implement stack inspection
useful for debuggers. They can also be used to implement dynamic
scope in the form of parameter objects as in the R7RS. Whereas
the reference implementation in the R7RS, which relies
on dynamic-wind instead, does not have the
desirable feature that the last expression within the body of
a parameterize expression occurs in tail context, a
simple implementation using continuation marks having this
feature is possible. Another use case of continuation marks is
the proper implementation of delayed evaluation in a strict
programming language that allows for iterative lazy algorithms
without the need of the special delay-force form of
the R7RS; see SRFI
155: Promises.
In order to demonstrate the application range of continuations and in order to introduce the syntactic forms and procedures defined by this SRFI below, we start with a number of examples.
Continuation marks can be attached with
with-continuation-mark and retrieved
with current-continuation-marks and the
accessors continuation-mark-set->list, continuation-mark-set->list*
and continuation-mark-set-first.
(let ((key (vector 'key)))
(with-continuation-mark key 1
(continuation-mark-set->list (current-continuation-marks) key))) ; ⇒ (1)
(let ((key (vector 'key)))
(with-continuation-mark key 1
(cons 'foo
(with-continuation-mark key 2
(continuation-mark-set->list (current-continuation-marks) key))))) ; ⇒ (foo 2 1)
We use the invocation of cons to ensure that the
inner with-continuation-mark form does not occur in
tail context with respect to the outer with-continuation-mark form.
Without, we would get:
(let ((key (vector 'key)))
(with-continuation-mark key 1
(with-continuation-mark key 2
(continuation-mark-set->list (current-continuation-marks) key)))) ; ⇒ (2)
Consider the following two definitions of a factorial procedure:
(define (fact1 n)
(let loop ((n n))
(if (zero? n)
1
(* n (loop (- n 1))))))
(define (fact2 n)
(let loop ((n n) (a 1))
(if (zero? n)
a
(loop (- n 1) (* n a)))))
The first version is recursive. The second version is iterative. Using continuation marks, we can observe this behaviour:
(define %key (vector 'key))
(define (ccm)
(continuation-mark-set->list (current-continuation-marks) %key))
(define (fact1 n)
(let loop ((n n))
(if (zero? n)
(begin
(display (ccm))
(newline)
1)
(with-continuation-mark %key n (* n (loop (- n 1)))))))
(define (fact2 n)
(let loop ((n n) (a 1))
(if (zero? n)
(begin
(display (ccm))
(newline)
a)
(with-continuation-mark %key n (loop (- n 1) (* n a))))))
Calling (fact1 3) outputs (1 2 3) on
the console, while calling (fact2 3)
outputs (1) on the console.
A version of parameterize, in which the last
expression of its body is in tail context, and which is thus
usable for iterative algorithms and thus in the spirit of the
Scheme programming language, can be obtained using
continuation marks as follows:
(define %param-key (vector 'param-key))
(define %param-convert (vector 'param-convert))
(define make-parameter
(case-lambda
((init)
(make-parameter init values))
((init converter)
(let ((key (vector 'key))
(value (converter init)))
(case-lambda
(()
(let ((boxed-value (continuation-mark-set-first (current-continuation-marks)
key)))
(if boxed-value
(vector-ref boxed-value 0)
value)))
((secret)
(cond
((eq? %param-convert secret)
converter)
((eq? %param-key secret)
key))))))))
(define-syntax parameterize
(syntax-rules ()
((parameterize
((param init) ...) . body)
(%parameterize ((param init) ...) () body))))
(define-syntax %parameterize
(syntax-rules ()
((_ () ((param init tmp) ...) body)
(let* ((tmp ((param %param-convert) init)) ...)
(%parameterize ((param tmp) ...) body)))
((_ ((param1 init1) . rest) ((param2 init2 tmp2) ...) body)
(%parameterize rest ((param2 init2 tmp2) ... (param1 init1 tmp1)) body))
((%parameterize () body)
(let () . body))
((%parameterize ((param tmp) . rest) body)
(with-continuation-mark (param %param-key) (vector tmp)
(%parameterize rest body)))))
Some Scheme procedures are required to call certain procedures in tail position, and some Scheme forms are required to have certain expressions in tail context.
With only the primitives as defined by the R7RS, unit tests (using the SRFI 64 framework, for example) cannot check whether procedure calls actually happen in tail position. With continuation marks, it is possible to implement such tests.
(define-syntax test-tail-position
(syntax-rules
((test-tail-position tail expression)
(test-assert
(call-with-current-continuation
(lambda (c)
(let ((key (vector 'key)))
(let-syntax
((tail
(syntax-rules ()
((tail) (lambda args
(call-with-immediate-continuation-mark key c))))))
(with-continuation-mark key #t expression)
#f))))))))
(test-tail-position tail
(apply (tail) 1 2))
The last test should succeed for a correct implementation
of apply.
Note: Using the syntax parameters
of SRFI
139 and defining tail as a syntax parameter would
eliminate the need for the unpleasant passing of the tail
datum to the test-tail-position macro.
We view a continuation as a list of frames where each frame represents an active procedure call that is not a tail call. Each non-tail call of a procedure adds a frame to the head of the list of frames of the current continuation, while tail-calling a procedure conceptually reuses the top (or first) frame.
Continuation marks associate values to keys to frames. There
can be at most one value for a given frame and key. Keys and
values can be arbitrary Scheme objects. Keys are compared
using eq?.
The continuation marks for a given key in a continuation conceptually form a list of all values associated with the given key in the frames of the continuation, ordered by the ordering of frames.
An R7RS system that supports this SRFI shall make the identifiers
defined below available in the (srfi 157) library.
On any such system, the last expression within the body of
a parameterize expression shall occur in a tail context.
(with-continuation-mark <key> <value>
<expression>)
The <key> expression is evaluated to obtain
a key, the <value> expression is evaluated to
obtain a value, the key is mapped to the value as a continuation
mark in the current continuation's initial continuation (if the
frame already has a mark for the key, the mark is replaced), and,
finally, the <expression> is evaluated. The
continuation for evaluating <expression> is the
continuation of the with-continuation-mark expression
(so the result of the <expression> is the
result of the with-continuation-mark expression, and
the <expression> is in tail context if
the with-continuation-mark expression is).
In the descriptions of the following
procedures, default stands for an optional
argument that defaults to #f if it is not provided.
(current-continuation-marks)
Returns an object called a set of continuations
marks, which at some point in the future can be asked (by
the continuation-mark-set->list,
continuation-mark-set->list*
and continuation-mark-set-first procedures) to
deliver the set of continuation marks of the continuation of the
call to current-continuation-marks for a given key.
(continuation-marks? obj)
Returns #t if obj is a set
of continuation marks, and #f otherwise. Note that
sets of continuation marks are not necessarily disjoint from other
Scheme types such as lists.
(continuation-mark-set->list marks key)
Returns a newly allocated list containing the marks for
the key in the continuation mark
set marks.
(continuation-mark-set->list* marks list)
(continuation-mark-set->list* marks list default)
Returns a newly allocated list containing vectors of marks in
the continuation mark set marks. The length
of each vector in the result list is the same as the length of the
key list, and a value in a particular vector
position is the value for the corresponding key
in list. Values for multiple keys appear in
a single vector only when the marks are for the same continuation
frame in the continuation mark set marks.
The object default is used for vector elements to indicate
the lack of a value.
(continuation-mark-set-first marks key)
(continuation-mark-set-first marks key default)
Returns the first element of the list that would be returned
by (continuation-mark-set->list marks key),
or default if the result would be the empty list.
Semantically equivalent to, but may be more efficient than:
(let ((lst (continuation-mark-set->list marks key))
(if (not (null? lst))
(car lst)
default)))
(call-with-immediate-continuation-mark key proc)
(call-with-immediate-continuation-mark key proc
default)
Tail-calls proc with the value associated
with key in the first frame of the current
continuation (i.e., a value that would be replaced in the
set of current continuation marks if the call
to call-with-immediate-continuation-mark were
replaced with a with-continuation-mark form
using key as the key expression). If no
such value exists in the first frame, default is passed
to proc.
Semantically equivalent to, but may be more efficient than:
(let ((secret-key (vector #f)))
(with-continuation-mark secret-key #f
(let ((marks
(continuation-mark-set->list* (current-continuation-marks)
(list key secret-key)
default))
(proc (vector-ref (car marks) 0)))))
An implementation of continuation marks as a portable R7RS library is not possible.
This SRFI provides an implementation in
the form of a meta-circular interpreter written in R7RS
dubbed Inferior Scheme. Inferior Scheme is a REPL for
the Scheme IEEE 1178-1990 standard. Outside of the standard
syntax and procedures, Inferior Scheme provides the syntax and
the procedures of this SRFI, and the load procedure
of the R4RS.
A mature implementation of continuation marks is available in Racket.
The author of Chibi Scheme expressed plans to support continuation marks in his implementation.
A simple way for an implementation of Scheme to provide
continuation marks is to pass two implicit parameters
called flag and marks in each call. The
parameter flag is #t in a call if the call
is a tail call that occurs in tail context with respect to the
form with-continuation-mark, and #f
otherwise. The parameter marks holds the current
continuation marks. The Inferior Scheme implementation bundled
with this SRFI uses this approach. It is detailed in
R. Germane's master's thesis (see acknowledgements).
An implementation of Scheme that employs a global CPS-transform
to model continuations can implement continuation marks more
efficiently as follows: The current continuation marks are
stored in a thread-local mutable cell, which corresponds to the
implicit marks parameter from above. The
form with-continuation-marks invokes
its expression with a specific special
continuation procedure C*. The presence of that
specific continuation procedure as the current continuation
corresponds to the flag parameter from above
being #t. (In order for
the with-continuation-marks form to be able to
return to its continuation, it has to push its continuation onto
the current continuation marks so that C* can access it
when it is invoked and pass control to it.)
A similar strategy is possible for Scheme implementations that are stack-based. Passing the special continuation procedure from above is replaced by leaving a specific special return value on the stack.
I would like to thank John Clements and Matthew Flatt for inventing continuation marks. See Modeling an Algebraic Stepper (PDF) and Portable and high-level access to the stack with Continuation Marks (PDF).
Also, thank you to the PLT team for making continuation marks popular. Parts of the wording of this specification have been taken over from the Racket documentation.
I also want to acknowledge Kimball R. Germane's master's thesis, where a simple global source code transformation for implementing continuation marks in pure lambda calculus is described in great detail.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.