© University of Kent - Contact | Feedback | Legal | FOI | Cookies
Efficient simple pretty printing combinators
A 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.
Apparently the pretty printing combinator algorithms have been transferred to Scala, Curry and OCaml. I'd be interested to here about other programming languages.
Papers
- 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).
Software
FPretty is a Haskell library for pretty printing. The library has the same interface as that of Wadler. It is very efficient, in contrast to Wadler's library and the one by John Hughes and Simon Peyton Jones the pretty printer only takes time linear in the size of the printed document; it does not do any backtracking. This version is based on the latest papers by Doaitse Swierstra and me but provides additional combinators following PPrint by Daan Leijen.- Text.PrettyPrint.FPretty is on Hackage. It comes with Haddock documentation and uses the standard Data.Sequence instead of its own Dequeue implementation.
- Previous version:
- FPretty.hs
- Dequeue.hs (imported by FPretty)