Thursday, August 06, 2009

Selectively disabling tail recursion

The anti-tail-recursion crowd often complains about loss of information in stack traces. In DrScheme, if you raise an exception after a sequence of tail calls:
(define (fact-iter n acc)
(if (zero? n)
(error 'fact "stop!")
(fact-iter (sub1 n) (* n acc))))
(fact-iter 3 1)
the stack trace you get back has very little information in it.

One argument you'll sometimes hear from people like me is that in a properly tail calling language, you can always turn a tail position into a non-tail-position, whereas the reverse is impossible. But in practice, when you want broadly better diagnostics, manually converting lots of individual function calls throughout a program is too hard to be practical, and you then have to go and undo it afterward.

So in the spirit of linguistic tools for diagnostics, I've discovered a dirt-simple trick for improving the information in stack traces while debugging.

PLT Scheme lets you hijack the normal meaning of function application by rebinding the #%app macro. So I defined a utility called trace-app that wraps its function application in (roughly) the identity function, forcing the given function call out of tail position. Then all you have to do is add to the top of a module:
(require (planet dherman/tail:4))
(define-syntax #%app trace-app)
and suddenly, all function applications that occur syntactically within the current module body are non-tail calls, and voilà:


Update: I've posted a new version of the package, which exports trace-app in a slightly different way. The initial version had a hazard that client modules which used
(provide (all-defined-out))
would inadvertently re-provide #%app, which would then disable tail recursion for its client modules.

The new way to use it is
(require (rename-in (planet dherman/tail:5) [trace-app #%app]))
or
(require (only-in (planet dherman/tail:5) [trace-app #%app]))

No comments: