Wednesday, June 22, 2005

Observing tail calls

Take a simple tail-recursive function:
(define (f n acc)
(if (zero? n)
(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)
(let ([result (g (sub1 n) (+ n acc))])
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.


timmykeels said...

Hello I am so delighted I located your blog, I really located you by mistake, while I was watching on google for something else, Anyways I am here now and could just like to say thank for a tremendous post and a all round entertaining website.
Do check
Paypal Login
gemini login

jack peterson said...

You are doing a tremendous job. It is very enlightening and achieves what it desires. I will make sure that I read all of your blogs in future. It will definitively enhance my knowledge.
Do check
Telstra email login