The University of Kent, Canterbury, Kent, CT2 7NZ, T +44 (0)1227 764000
Efficient simple pretty printing combinatorsA pretty printer converts tree structured data, for example the syntax tree of a program or an XML document, into nicely formatted text with a given line width limit. A pretty printing library provides the functionality common to a large class of pretty printers, thus enabling a programmer to easily implement a specific pretty printer. A pretty printing library enables the programmer to compositionally describe alternative layouts for components of the data to be printed. The pretty printing algorithm then chooses an optimal layout from this set of layouts. There is a trade-off between the available choice of alternative layouts, the optimality criterion and the efficiency of the pretty printing algorithm.
Oppen published in 1980 an imperative pretty printer that allows the description of nice layouts, adequate for many purposes, and that is very efficient. The algorithm takes time linear in the size of the input, independent of the lie-width limit. Furthermore, the algorithm is bounded, that is, it produces parts of the output already after having processed only limited parts of its input. Oppen's work inspired numerous pretty printing libraries, in particular several Haskell libraries by John Hughes and Phil Wadler, but these use backtracking and hence are less efficient.
I developed the first purely functional pretty printing library that has all the nice properties of Oppen's implementation. My first implementation was still hard to understand, using two intricately linked double ended queues, but later I improved it obtaining an implementation that is both efficient and simple. It is a nice application of delimited continuations. It does not even require laziness, but an eager implementation might want to avoid the construction of the intermediate document.
- Linear, bounded, functional pretty-printing. S. Doaitse Swierstra and Olaf Chitil. Journal of Functional Programming, 19(01):1-16, January 2009.
- Pretty printing with delimited continuations. Olaf Chitil. Technical report 4-06, Computing Laboratory, University of Kent, June 2006.
- Pretty printing with lazy dequeues. Olaf Chitil. Transactions on Programming Languages and Systems (TOPLAS), 27(1):163-184, January 2005.
- Pretty printing with lazy dequeues. Olaf Chitil. In Ralf Hinze, editor, Preliminary Proceedings of the 2001 ACM SIGPLAN Haskell Workshop, pages 183-201, Firenze, Italy, September 2001. Universiteit Utrecht UU-CS-2001-23. Final Proceedings to appear in ENTCS 59(2).