The impossible parser

5 August 2004

In Scheme, the Lisp variant that MIT nerds learn in 6.001, implementations must be properly tail-recursive. What does this mean? Suppose you have a the following two Scheme functions (cribbed shamelessly from the 6.001 textbook:

 (define (factorial n)   (fact-iter 1 1 n))  (define (fact-iter product counter max-count)   (if (> counter max-count)       product       (fact-iter (* counter product)                  (+ counter 1)                  max-count)))

If you ask for (factorial 6), the factorial function will call (fact-iter 1 1 6), which will call (fact-iter 1 2 6), and so on up to (fact-iter 720 7 6). In a non-tail-recursive language, (fact-iter 720 7 6) will return 720 to its caller, (fact-iter 120 6 6), which will return the same value to its caller, and all the way back down.

A proper Scheme implementation, however, can tell from the structure of the code that all these intermediate function returns are unnecessary, so that (fact-iter 720 7 6) can deliver its return value directly to whatever function called (factorial 6) in the first place. No matter how large n is, a Scheme interpreter can evaluate (factorial n) without growing the stack. Where programmers in other languages would use for, while, and other special iterative forms, Scheme programmers just write a recursive procedures like fact-iter.

According to Scheme fans, tail recursion is one example of how Scheme doesn’t force programmers to clutter up their code with useless syntax. According to Scheme foes, tail recursion is one example of how Scheme omits perfectly useful features for the sake of some cult-like ideal of purity. Based on my experiences with a recent Java project, I would like to put in a good word for the fans.

I had to write an application that interpreted files in a certain XML format. I chose SAX for the job, since it was the fastest free pure-Java XML parser that I knew of. SAX works by setting up a sort of tennis game between two interfaces. The SAX distribution provides an implementation of XMLReader, which parses the incoming XML. Every time it sees an “event”, such as an opening XML tag, it calls a method on an implementation of ContentHandler, which you, the programmer using SAX, have to write.

My XML application had two notable features. For my first pass through the document, I wanted to look for some information in the opening tag of the root element, and I didn’t care about processing the rest of the document. The XML format also had a looping construct, so my content handler had to be able to recognize the beginning and end of the loop, and it had to store up all the events in the middle to be replayed.

One catch: The interface for ContentHandler doesn’t give the content handler any way to communicate with the XML reader that’s sending the events. The only way to tell the reader “I know you’re not done with this document, but stop parsing, I don’t want to see any more” is to throw an exception. If you want one content handler to hand off its responsibility to another, the rest of the application has to provide the content handler with a reference to the XML reader, so you can call the appropriate method. Worst of all, if you’re trying to collect all of the events within a balanced pair of tags, the content handler has to keep track of how deeply nested the tags are—even though the XML reader has to keep track of the same information.

It would be a nice thing, I thought, if SAX provided another interface, one that let you write a content handler in continuation passing style. In this XML processor of my imagination, every CPS-content-handler method would take an extra argument, a proxy for the XML reader itself. When the method finished its work and wanted the parse to continue, it could just call reader.continueParsing(this). If it wanted to hand off work to another CPS-content-handler, it would call reader.continueParsing(otherHandler). If it needed information about how deeply nested the current element was, it could call reader.getDepth(); other methods could provide other useful information about the context of the event being processed, such as the names of enclosing tags. And if a CPS-content-handler method wanted to stop parsing, it would simply exit without calling reader.continueParsing().

(The Java servlet filter API uses this strategy. If a filter wants to pass control to the next filter in the filter chain, it calls chain.doFilter(); if it wants to block further request processing, it doesn’t call that method.)

But alas! Even though one of the architects of Scheme has spent the last ten years working for Sun, Java is not guaranteed to be properly tail-recursive. Therefore, all these calls from the XML reader to the CPS-content-handler and back would add two stack frames for every parsing event, until the whole parse was completed—or, more likely, until the stack overflowed and a fatal exception stopped the whole application.

Perhaps I can convince the Powers that Be at my employer to write their next multi-million-dollar ERP application in Scheme, instead of Java. I’m not exactly holding my breath.

technology