Observing tail calls

Take a simple tail-recursive function:

(define (f n acc)
  (if (zero? n)
      acc
      (f (sub1 n) (+ n acc))))

How can we demonstrate the control behavior of such a procedure? With continuation marks! If we wrap every reference to f with code that saves the current arguments in a continuation mark:

(with-continuation-mark 'snapshot (list n acc)
  (f (sub1 n) (+ n acc)))

then as long as the reference to f is in tail position, this should overwrite the previous mark. Otherwise, it will build a stack of marks, each representing the current arguments at one of the invocations. We can save this control snapshot for posterity so that after the computation finishes, we can check its most recent value:

(define (f n acc)
  (set! snapshot (current-continuation-marks))
  ...)

Here's a macro that abstracts out this transformation:

(define-syntax (control-snapshot stx)
  (syntax-case stx ()
    [(_ f e ...)
     (identifier? #'f)
     (with-syntax ([(x ...) (generate-temporaries #'(e ...))])
       #'(let ([original f]
               [snapshot #f]
               [label (gensym)])
           (fluid-let ([f (lambda (x ...)
                            (set! snapshot (current-continuation-marks))
                            (with-continuation-mark label (list x ...)
                              (original x ...)))])
             (f e ...)
             (continuation-mark-set->list snapshot label))))]))

If we take a control snapshot of an invocation of the tail-recursive f, we get

> (control-snapshot f 10 0)
((1 54))

If we define a non-tail-recursive version like so:

(define (g n acc)
  (if (zero? n)
      acc
      (let ([result (g (sub1 n) (+ n acc))])
        result)))

we get a full stack history:

> (control-snapshot g 10 0)
((1 54) (2 52) (3 49) (4 45) (5 40) (6 34) (7 27) (8 19) (9 10) (10 0))

You can use continuation marks in this manner to write test cases that ensure that something you've written is using bounded control.