Continuation marks


Marc Nieper-Wißkirchen


This SRFI is currently in final 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.

Some simple 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)

Recursive versus iterative algorithms

Consider the following two definitions of a factorial procedure:

  (define (fact1 n)
    (let loop ((n n))
      (if (zero? n)
          (* n (loop (- n 1))))))

  (define (fact2 n)
    (let loop ((n n) (a 1))
      (if (zero? n)
          (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)
            (display (ccm))
          (with-continuation-mark %key n (* n (loop (- n 1)))))))

  (define (fact2 n)
    (let loop ((n n) (a 1))
      (if (zero? n)
            (display (ccm))
          (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.

Parameter objects

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
       (make-parameter init values))
      ((init converter)
       (let ((key (vector 'key))
             (value (converter init)))
            (let ((boxed-value (continuation-mark-set-first (current-continuation-marks)
             (if boxed-value
                 (vector-ref boxed-value 0)
              ((eq? %param-convert secret)
              ((eq? %param-key secret)

  (define-syntax parameterize
    (syntax-rules ()
           ((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)))))

Test for tail position

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
      ((test-tail-position tail expression)
          (lambda (c)
            (let ((key (vector 'key)))
                   (syntax-rules ()
                     ((tail) (lambda args
                               (call-with-immediate-continuation-mark key c))))))
                (with-continuation-mark key #t expression)

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


Continuation marks

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.


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)

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

Implementation hints

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.


Copyright (C) Marc Nieper-Wißkirchen (2017). All Rights Reserved.

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.


Editor: Arthur A. Gleckler