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)

1	Disabling Tail Recursion
2	Tail-Recursive Continuations
3	Generalized Continuation Marks