1 Disabling Tail Recursion
trace-begin
trace-app
2 Tail-Recursive Continuations
let-tail-continuation
let/ tc
3 Generalized Continuation Marks
with-continuation-mark*

Tail Recursion Utilities

by Dave Herman (dherman at ccs dot neu dot edu)

This library provides utilities for tail recursion.

 (require (planet dherman/tail:5:0))

    1 Disabling Tail Recursion

    2 Tail-Recursive Continuations

    3 Generalized Continuation Marks

1 Disabling Tail Recursion

(trace-begin body-expr ...+)
A syntax for evaluating a sequence of expressions, like begin, but without preserving tail position. In particular, the last of the body-expr expressions is not in tail position.

(trace-app expr ...+)
A syntactic form that behaves like the #%app of scheme/base, but without evaluating the procedure application in tail position. To disable tail recursion in an entire module, add the following line to the beginning of the module:

  (require (rename-in (planet dherman/tail:5:0) [trace-app #%app]))

Subsequent function applications appearing within the body of the module are then translated to non-tail calls.

2 Tail-Recursive Continuations

(let-tail-continuation k-id body-expr ...+)
(let/tc k-id body-expr ...+)
Syntactic forms for capturing a continuation and binding a special form that always invokes the continuation in tail position.

The identifier k-id is bound to a special form that invokes the captured continuation in tail position with respect to the entire let/tc expression.

Examples:

  > (define (down n)
      (with-continuation-mark 'down n
        (let/ec return
          (if (zero? n)
              (return (current-continuation-marks-list 'down))
              (return (down (sub1 n)))))))
  > (down 10)

  (0 1 2 3 4 5 6 7 8 9 10)

  > (define (down* n)
      (with-continuation-mark 'down* n
        (let/tc return
          (if (zero? n)
              (return (current-continuation-marks-list 'down*))
              (return (down* (sub1 n)))))))
  > (down* 10)

  (0)

To achieve proper tail recursion, the argument to k-id is evaluated in the hole of the captured continuation, i.e., after abandoning the current continuation. Note that this behavior is significant when the argument expression performs side effects.

Examples:

  > (with-continuation-mark 'jump 'after
      (let/cc k
        (with-continuation-mark 'jump 'before
          (k (current-continuation-marks-list 'jump)))))

  (before)

  > (with-continuation-mark 'jump 'after
      (let/tc k
        (with-continuation-mark 'jump 'before
          (k (current-continuation-marks-list 'jump)))))

  (after)

  > (with-handlers ([exn? (lambda (exn) 'uncaught)])
      (let/ec k
        (with-handlers ([exn? (lambda (exn) 'caught)])
          (k (error 'stop)))))

  caught

  > (with-handlers ([exn? (lambda (exn) 'uncaught)])
      (let/tc k
        (with-handlers ([exn? (lambda (exn) 'caught)])
          (k (error 'stop)))))

  uncaught

The captured continuation k-id can only be applied to exactly one argument. (If control returns normally, i.e., without explicitly invoking k-id, it may return any number of values.)

Examples:

  > (let/tc k
      (k 1 2 3))

  eval:11:0: k: bad syntax in: (k 1 2 3)

  > (let/tc k
      (values 1 2 3))

  1

  2

  3

3 Generalized Continuation Marks

(with-continuation-mark* key-expr val-expr update-expr body-expr ...+)
Like with-continuation-mark, but instead of automatically overwriting existing marks, applies procedure obtained from update-expr to the existing value.

Example:

  > (let down ([n 10])
      (if (zero? n)
          (current-continuation-marks-list 'down)
          (with-continuation-mark* 'down 0 add1 (down (sub1 n)))))

  (9)