4 ms·

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 progra

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/prettier.pdf https://homepages.inf.ed.ac.uk/wadler/papers/prettier/pretti... [1] https://jyp.github.io/pdf/Prettiest.pdf https://jyp.github.io/pdf/Prettiest.pdf [2] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.2200 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.2... [3] https://hexdocs.pm/elixir/Inspect.Algebra.html https://hexdocs.pm/elixir/Inspect.Algebra.html

westoncb 7y ago
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.
- QuinnWilton 7y ago
  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 http://www.cse.chalmers.se/~rjmh/Papers/pretty.html
  - westoncb 7y ago
    This looks great—thanks!
    - QuinnWilton 7y ago
      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/ http://elementsofprogramming.com/
  - harpocrates 7y ago
- amykyta 7y ago
  Here is an interesting use https://www.lexifi.com/instrumentbox/ 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’.
choeger 7y ago
The actual first true generic pretty printing algorithm comes from Derek Oppen and is referenced in that paper, btw.

westoncb 7y ago

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.

QuinnWilton 7y ago
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 http://www.cse.chalmers.se/~rjmh/Papers/pretty.html
- westoncb 7y ago
  This looks great—thanks!
  - QuinnWilton 7y ago
    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/ http://elementsofprogramming.com/
- harpocrates 7y ago
amykyta 7y ago
Here is an interesting use https://www.lexifi.com/instrumentbox/ 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’.

choeger 7y ago

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