School of Computing

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

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.

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 25/07/2012