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]))

Linguistic tools for diagnostics

I've written before about how the stack gets misunderstood as a history thanks to non-tail-recursive languages. Of course, stack traces are indispensable: they're essential for debugging, and they're also useful for reporting crash information from live applications.

But this conflates two very different language requirements in one feature: the need for nested (unbounded, if your language isn't broken) function application, and the need for diagnostics of dynamic errors.

The first is what continuations and stacks are all about, of course: functions can't call each other function calls can't be nested in compound expressions without the language runtime keeping track of the work it has left to do. But the second is an independent need: there's all sorts of diagnostic information that's potentially useful, and the stack just happens to be one source of information that's already there.

Now, as it turns out, it's a pretty useful source of information. And if you happen not to have proper tail recursion, it's even more useful, since it provides a path through the function call graph. But I've been finding stack traces in Scheme less informative, because with proper tail calls, there's less function-call history in the continuation.

I recognize that sometimes the "complexity budget" in language design necessitates using one feature to satisfy multiple requirements. But I'd like to see more investigation of linguistic diagnostics designed independently of existing language features. For example, it might be useful to provide configurable tracing facilities that record program history during runtime, where the tuning of how much gets recorded is completely independent of the space semantics of the evaluator. So you have a properly tail recursive semantics with a flexible tracing facility grafted on top.

What classifies a language feature as "purely diagnostic" might be that it is designed not to change the observable behavior of the program, but merely to report some additional information. Contracts-as-projections is an example.

Update: rephrased my rookie characterization of continuations.

Continuation marks in exceptions

Rethrowing caught exceptions is an important idiom. In particular, there are lots of cases where it's important to conditionally handle an exception by handling it and then rethrowing it. In ML, I believe it's the actual definition of pattern matching on particular exception types: the pattern matching is syntactic sugar for inspecting the caught exception and conditionally rethrowing it. In standard JavaScript it's the only way to catch particular exception types, because there is no standard conditional handling form.

But a useful feature of some exception systems, like in Java, is the association of a stack trace with an exception. But when you rethrow an exception, this involves a choice: do you want a stack trace to be associated with the original continuation that threw the exception, or the one that rethrew it? There are genuine use cases for both. But in Java, the implementers have to choose one or the other for you.

PLT Scheme gives you the flexibility to choose for yourself. Exceptions are not special values in Scheme; there's an orthogonal way of reifying the control state. The PLT runtime stores stack trace information in a special continuation mark, so if you grab the current continuation mark set, you've got your hands on a value that provides DrScheme's IDE with all the information it needs to visualize the continuation.

The standard exception types in PLT Scheme are records with a field for the current continuation mark set. So when you conditionally rethrow an exception, you can either keep its version of the continuation marks, or functionally update it with the current continuation marks and throw that instead.

Afterthought: I think Java might have chosen something like a policy where an exception value saves its stack trace at the point where it's created. This gives you the ability to do both by either rethrowing the same exception (to keep the original stack trace) or wrapping the exception with a new one (to use the new stack trace). I still prefer the PLT Scheme approach, which makes the stack trace a first-class value and consequently more explicit.