Hacker News Reader

Comment by QuinnWilton | Hacker News Reader

Philip Wadler has a seminal paper [0] on implementing pretty printers by modeling them using an algebra. There's implementations of the algorithm in most programming languages nowadays, and some state of the art advances that help with performance [1]

It's a very elegant algorithm, and is very pleasant to work. Elixir's formatter uses a variant of it [2], and it appears in the standard library [3]. I've personally made use of it to write a code formatter for GraphQL queries, and it was a very small amount of code for some powerful results.

Definitely take a look if you ever need to do something like this.

[0] https://homepages.inf.ed.ac.uk/wadler/papers/prettier/pretti...

[1] https://jyp.github.io/pdf/Prettiest.pdf

[2] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.2...

[3] https://hexdocs.pm/elixir/Inspect.Algebra.html

View on HN

I'm gonna take a look at Wadler's paper—but does anyone want to take a shot at a high-level description of how an algebra would be applicable to the problem of pretty printing?

Any more general comments on applying algebras to solving programming problems would also be appreciated.

My rough understanding of the benefits/rationale atm:

1) the algebra is a nice/minimal factoring of the problem

2) being able to formally classify it means we know a bunch of its properties, which tells us certain approaches are definitely (im)possible (and these properties are drawn from a fairly small set: e.g. associativity, distributivity, existence of inverses)

3) If the algebra is explicitly represented in code (maybe in a library), we can use that general structure to verify (and generate?) certain aspects of our particular problem solution.

Edit: The paper mentions "Over the years, Richard Bird and others have developed the algebra of programming to a fine art" —and I found Bird's book "Algebra of Programming". Seems like what I'm looking for maybe, but would be grateful to hear of any alternative resources as well.

You'd likely be more interested in the original paper [0] by John Hughes that Wadler built off of. It gets into a ton more detail about the algebraic structure of the documents they're defining:

> The question addressed in this paper is: how should libraries of combinators be designed? Our goal is to show how we can use formal specification of the combinators, and a study of their algebraic properties, to guide both the design and implementation of a combinator library. Our case study is a library for pretty-printing. But the methods we present are of wider applicability, and we also show how they can be used to develop a number of different monads.

Wadler's paper touches upon some of the same ideas, but the primary goal of his paper is to build a prettier printer, whereas Hughes aimed to demonstrate the power of algebraic properties.

[0] http://www.cse.chalmers.se/~rjmh/Papers/pretty.html

This looks great—thanks!

It's a little bit different from the other resources I've linked, but "Elements of Programming" [0] is another excellent (though incredibly challenging) read. It's written by Alexander Stepanov, and basically walks through the way he built STL by decomposing algorithms and data structures into abstract mathematical structures.

> Elements of Programming provides a different understanding of programming than is presented elsewhere. Its major premise is that practical programming, like other areas of science and engineering,must be based on a solid mathematical foundation. The book shows that algorithms implemented in a real programming language, such as C++, can operate in the most general mathematical setting. For example, the fast exponentiation algorithm is defined to work with any associative operation. Using abstract algorithms leads to efficient, reliable, secure, and economical software.

I revisit it every few years and get a little bit further every time before I start to struggle with the exercises.

[0] http://elementsofprogramming.com/

For anyone curious about the difference between the two: Hughes' pretty printer works really well for pretty-printing Haskell code, but Wadler's is more flexible for pretty-printing C-style languages where there is a dedented closing brace at the end of scopes.

It is 100% true that Hughes' paper is a better introduction to the idea of having algebraic document combinators. One can skim Hughes' and then feel at ease using a library that implements Wadler's printer - the bigger differences between the two libraries are tucked away in the layout algorithms and the APIs are similar.

> Hughes' pretty printer works really well for pretty-printing Haskell code, but Wadler's is more flexible for pretty-printing C-style languages where there is a dedented closing brace at the end of scopes.

That's very interesting! So far I've only used Wadler-Leijen-style prettyprinters.

Are Hughes-style pretty printers "better" in some way for Haskell-like documents? If so, why?

Here is an interesting use https://www.lexifi.com/instrumentbox/. Algebraic description of financial contracts that then gives all sorts of common features you want to analyze them ‘for free’.

The actual first true generic pretty printing algorithm comes from Derek Oppen and is referenced in that paper, btw.

Reply on news.ycombinator.com