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

Representing failure

I'm working on an algorithm that uses backtracking implemented with exceptions and handlers (rather than, say, explicit continuations). I just noticed that, for debugging, it's nice to represent the failure exceptions as records that contain not just the data about the operation that failed but also an optional list of other failure exceptions. In the disjunction cases, I can save the intermediate failures and, if they all fail, include them in the resulting failure record. This provides me with a nice data structure representing the control flow of the failed search tree. It only required modifying about 3 lines of code and the resulting data structure is easier to analyze than a manual debugging sequence. (I hate working with debuggers, even good ones.)

Debugger as library

The great thing about printf-debugging is that it's got about as low a barrier to entry as possible (unless you're using Haskell--don't get me started). You have implicit access to the program's control flow and I/O and the function is essentially always there. When you want to use a debugger, you usually have to search for a good one, download and install it, learn how it works, figure out how to set breakpoints, learn the language of breakpoint conditions, figure out how to inspect locals and evaluate expressions, etc. etc.

What if debugging was just available as a library? What power would you need? I think PLT Scheme is uniquely suited to making this extremely practical. It's easy to implement a programmatic breakpoint: just call/cc and raise an exception with the captured continuation. You immediately have access to a nice language of boolean predicates for determining breakpoint conditions (Scheme), as well as a language to evaluate expressions with access to the locals (also Scheme). But PLT Scheme also provides continuation marks, which allow you to leave little bread-crumbs through the control flow of a program. What I'd really love to do is use this to allow the programmer to annotate interesting points in the control and connect this up to the DrScheme GUI libraries so that the programmer can do something like:

> (define bp (debug <expression>))
> bp
#<breakpoint>
> (show-control bp)

and have a window pop open that displays a stack trace of the suspended program.

I'm working on a PLaneT library to make this just about as low-tech and seamless as printf-debugging. You'll just need to throw in one extra line somewhere in the module:

(require (planet dherman/debug))

and this will allow you to throw in breakpoints and debug programs much like you could with a full debugging IDE, only with the directness and intra-linguistic style of printf.

Crazy debugging feature idea

Here's a crazy idea. Closures are like objects with private fields, right? Specifically, outside of the function body, you're not allowed to refer to the variables in the closed environment. But one of the most annoying things that happen when I'm debugging is that I want to call some local function, but it's not available from the REPL:

(define (foo x y)
  (define (helper z)
    ... x ... y ...)
  ...)

What if, at the REPL (i.e., in debug mode only), closures were openable? You could use dot-notation to refer to them, and all you'd have to do is somehow provide the extra bindings needed to fill in their environment. Keyword arguments, maybe?

> ((close foo.helper [#:x 42] [#:y 'blah]) "value of z")
'result-value-ftw!