Pretty-Printing is Compilation

Wadler's A Prettier Printer is a classic functional pearl. However—whether due to Haskell's laziness or my own—I struggled to reimplement his ideas in other languages (or even in Haskell, five minutes after reading the paper). Thankfully, Lindig recognized this problem and brought fire to the masses in Strictly Pretty. Yet even that wasn't dumbed-down enough for me.

But after spending some more time tinkering with the ideas from both papers, I think I finally get the idea.

Overview

As the title suggests, we'll think of pretty-printing as a process of compilation (and execution) of programs written in an abstract "document language". Like most programming languages, this document language—which we'll call
Doc—features expressions that can be composed together; this makes it easy for humans to reason about. We'll compile expressions in Doc to instructions in a kind of assembly language (ASM). Instructions in ASM are much easier to transform into strings.

Here's a schematic view of the process:

As a concrete example, suppose we want to pretty-print the nested list:

['onions', ['carrots', 'celery'], 'turnips']

Here's a Doc program for doing so:

group(
    '['
    + nest(
        4,
        br()
        + "'onions'"
        + ','
        + br(' ')
        + group(
            '['
            + nest(4, br() + "'carrots'" + ',' + br(' ') + "'celery'")
            + br()
            + ']'
        )
        + ','
        + br(' ')
        + "'turnips'"
    )
    + br()
    + ']'
)

We'll meet group, nest, etc. shortly. For now it's enough to get a general feel for the document language.

This program is then compiled (with certain "architectural parameters" set) into the ASM instructions:

TEXT '['
LINE 4
TEXT "'onions'"
TEXT ','
LINE 4
TEXT '['
TEXT ''
TEXT "'carrots'"
TEXT ','
TEXT ' '
TEXT "'celery'"
TEXT ''
TEXT ']'
TEXT ','
LINE 4
TEXT "'turnips'"
LINE 0
TEXT ']'

which are then interpreted as a string:

[
    'onions',
    ['carrots', 'celery'],
    'turnips'
]

One important feature alluded to above is that the compiler has a configurable "architectural parameter", which is a target maximum line width. Depending on the value of this parameter, the compiler will emit different ASM instructions for the same Doc program. In the example above we used a target width of 30. If we'd used 20 instead, the emitted assembly instructions would be different, as would the resulting string:

[
    'onions',
    [
        'carrots',
        'celery'
    ],
    'turnips'
]

And if we'd used 60, it would be:

['onions', ['carrots', 'celery'], 'turnips']

Printer Assembly Language

The assembly language is straightforward, so we'll tackle it first. We'll think of ASM instructions as controlling a really simple printing device that's only capable of doing two things:

1. Emitting a string of text.
2. Advancing to the next line, and indenting by a certain amount.

Hence ASM consists of only two instructions:

1. TEXT , which emits a string of text.
2. LINE , which advances the printer to the next line, and then indents by indent spaces.

ASM programs are interpreted as strings by executing their instructions, one after the other. As an example, let's trace the execution of the program:

['onions', ['carrots', 'celery'], 'turnips']

We'll use a > to indicate the instruction being executed, and display the current output below. The ^ character will indicate the current location of the "printer head". We'll also use _ characters to indicate spaces, since these are otherwise difficult to track.

The first TEXT instruction causes the string 'hello' to be emitted:

group(
    '['
    + nest(
        4,
        br()
        + "'onions'"
        + ','
        + br(' ')
        + group(
            '['
            + nest(4, br() + "'carrots'" + ',' + br(' ') + "'celery'")
            + br()
            + ']'
        )
        + ','
        + br(' ')
        + "'turnips'"
    )
    + br()
    + ']'
)

LINE 2 then advances to the next line and indents the head by 2 spaces:

TEXT '['
LINE 4
TEXT "'onions'"
TEXT ','
LINE 4
TEXT '['
TEXT ''
TEXT "'carrots'"
TEXT ','
TEXT ' '
TEXT "'celery'"
TEXT ''
TEXT ']'
TEXT ','
LINE 4
TEXT "'turnips'"
LINE 0
TEXT ']'

Then TEXT 'indented' causes 'indented' to be added:

[
    'onions',
    ['carrots', 'celery'],
    'turnips'
]

Followed by ' world', due to TEXT ' world':

[
    'onions',
    [
        'carrots',
        'celery'
    ],
    'turnips'
]

LINE 0 advances the printer to the next line (and doesn't indent at all):

['onions', ['carrots', 'celery'], 'turnips']

And finally, TEXT 'goodbye' emits 'goodbye':

TEXT 'hello'
LINE 2
TEXT 'indented'
TEXT ' world'
LINE 0
TEXT 'goodbye'

We'll represent ASM instructions as a "sum type":

• TEXT instructions will be represented by Python strs.
• LINE instructions will be represented by ints.

That is:

> TEXT 'hello'
  LINE 2
  TEXT 'indented'
  TEXT ' world'
  LINE 0
  TEXT 'goodbye'

== OUTPUT ==

hello
     ^

Interpreting a list of AsmInsts into the string they represent is just a matter of iterating over the instructions and "doing the right thing":

  TEXT 'hello'
> LINE 2
  TEXT 'indented'
  TEXT ' world'
  LINE 0
  TEXT 'goodbye'

== OUTPUT ==

hello
__
  ^

For TEXT instructions, the interpreter appends the text to the result; for LINE instructions, the interpreter appends a newline ('n') followed by indent spaces.

We can test interpret with the ASM instructions from the example above, translated into Python:

  TEXT 'hello'
  LINE 2
> TEXT 'indented'
  TEXT ' world'
  LINE 0
  TEXT 'goodbye'

== OUTPUT ==

hello
__indented
          ^

The Doc Language (Teaser)

We like ASM because it's easy to interpret. But it's a pain to use. This motivates the more human-friendly Doc language. Whereas ASM programs are sequences of instructions, Doc programs are compositions of expressions. These expressions are summed up by the following grammar:

  TEXT 'hello'
  LINE 2
  TEXT 'indented'
> TEXT ' world'
  LINE 0
  TEXT 'goodbye'

== OUTPUT ==

hello
__indented world
                ^

For example:

  TEXT 'hello'
  LINE 2
  TEXT 'indented'
  TEXT ' world'
> LINE 0
  TEXT 'goodbye'

== OUTPUT ==

hello
__indented world

^

is a Doc expression, as is:

  TEXT 'hello'
  LINE 2
  TEXT 'indented'
  TEXT ' world'
  LINE 0
> TEXT 'goodbye'

== OUTPUT ==

hello
__indented world
goodbye
       ^

What do these represent?

• A Python str literal represents itself.
• br() is a possible line break.
• nest(indent, doc) creates a "nested" subexpression that's visually offset by indent spaces.
• group(doc) delimits a subexpression in which all br()s are either treated as line breaks or not.
• combines Doc expressions.
• nil acts as an "empty" expression.

So, for instance:

AsmInst = str | int

represents the string:

def interpret(insts: list[AsmInst]) -> str:
    """Interpret the ASM instructions as a string."""
    result = ""
    for inst in insts:
        match inst:
            case text if isinstance(text, str):
                result += inst
            case indent if isinstance(indent, int):
                result += f"\n{' ' * indent}"
    return result

The second, more complex expression:

['onions', ['carrots', 'celery'], 'turnips']

may represent either:

group(
    '['
    + nest(
        4,
        br()
        + "'onions'"
        + ','
        + br(' ')
        + group(
            '['
            + nest(4, br() + "'carrots'" + ',' + br(' ') + "'celery'")
            + br()
            + ']'
        )
        + ','
        + br(' ')
        + "'turnips'"
    )
    + br()
    + ']'
)

or:

TEXT '['
LINE 4
TEXT "'onions'"
TEXT ','
LINE 4
TEXT '['
TEXT ''
TEXT "'carrots'"
TEXT ','
TEXT ' '
TEXT "'celery'"
TEXT ''
TEXT ']'
TEXT ','
LINE 4
TEXT "'turnips'"
LINE 0
TEXT ']'

depending on the value of the target maximum line width "architectural parameter" provided to the compiler. So br expressions might either be treated as line breaks or regular text, in which case their text value is used (or '' if no text argument was provided).

We'll represent Doc expressions using strs and Python classes. In particular:

[
    'onions',
    ['carrots', 'celery'],
    'turnips'
]

What about DocExpr DocExpr? We'll represent those using an additional Concat class:

[
    'onions',
    [
        'carrots',
        'celery'
    ],
    'turnips'
]

We want to support using to combine expressions, so we need to implement __add__ and __radd__ on each of the variant classes. Adding two Doc expressions using just constructs a Concat of the two. It's easy enough to do this manually, e.g.:

['onions', ['carrots', 'celery'], 'turnips']

But we can save ourselves some typing by defining a decorator to do it for us:

TEXT 'hello'
LINE 2
TEXT 'indented'
TEXT ' world'
LINE 0
TEXT 'goodbye'

The variant classes now look like:

> TEXT 'hello'
  LINE 2
  TEXT 'indented'
  TEXT ' world'
  LINE 0
  TEXT 'goodbye'

== OUTPUT ==

hello
     ^

Our task now is to write a compiler that translates expressions in the Doc language into the equivalent ASM instructions, given some target maximum line width:

  TEXT 'hello'
> LINE 2
  TEXT 'indented'
  TEXT ' world'
  LINE 0
  TEXT 'goodbye'

== OUTPUT ==

hello
__
  ^

However, it turns out to be simpler to first "lower" Doc expressions into expressions in an Intermediate Representation (IR) language, and then compile the IR expressions into ASM. Introduces this additional "pass" makes each step clearer.

An Intermediate Representation

So our schematic describing the pretty-printing process was a tad oversimplified. Here's the full picture:

IR expressions resemble Doc expressions in many ways:

  TEXT 'hello'
  LINE 2
> TEXT 'indented'
  TEXT ' world'
  LINE 0
  TEXT 'goodbye'

== OUTPUT ==

hello
__indented
          ^

The key difference is that we no longer have and nil expressions: these are converted to lists of IR expressions in the lowering process. Actually, that's all the lowering pass does:

  TEXT 'hello'
  LINE 2
  TEXT 'indented'
> TEXT ' world'
  LINE 0
  TEXT 'goodbye'

== OUTPUT ==

hello
__indented world
                ^

We first need to define IrExprs.
This ought to look familiar:

  TEXT 'hello'
  LINE 2
  TEXT 'indented'
  TEXT ' world'
> LINE 0
  TEXT 'goodbye'

== OUTPUT ==

hello
__indented world

^

All lower does is replace Nil() instances with an empty list ([]), and Concat(car, cdr) instances by appending the results of lowering the car and cdr expressions. The same treatment is applied to the subexpressions in Nest and Group. This is nothing more than a recursive "flattening" operation.

  TEXT 'hello'
  LINE 2
  TEXT 'indented'
  TEXT ' world'
  LINE 0
> TEXT 'goodbye'

== OUTPUT ==

hello
__indented world
goodbye
       ^

Testing lower with one of our example Doc expressions from above:

AsmInst = str | int

which is exactly what we expect.

The Compiler (Finally)

Now to the final step: compile. This function transforms IR expressions into ASM instructions, taking into account the target maximum line width:

def interpret(insts: list[AsmInst]) -> str:
    """Interpret the ASM instructions as a string."""
    result = ""
    for inst in insts:
        match inst:
            case text if isinstance(text, str):
                result += inst
            case indent if isinstance(indent, int):
                result += f"\n{' ' * indent}"
    return result

Here's the rough idea of the algorithm:

• The compiler maintains some "state" information:
  • The current (horizontal) line position.
  • The current indentation amount.
  • Whether or not brs should be treated as line breaks or rendered "flat".
• We iterate over the expressions, emitting some ASM instructions and updating the line position appropriately.

['onions', ['carrots', 'celery'], 'turnips']

process is where the magic happens:

group(
    '['
    + nest(
        4,
        br()
        + "'onions'"
        + ','
        + br(' ')
        + group(
            '['
            + nest(4, br() + "'carrots'" + ',' + br(' ') + "'celery'")
            + br()
            + ']'
        )
        + ','
        + br(' ')
        + "'turnips'"
    )
    + br()
    + ']'
)

In short:

• For text expressions, we emit a TEXT instruction and advance the position (pos) by the length of the text.
• br expressions are handled depending on the value of flat:
  • If flat is True, treat them as text.
  • Otherwise, emit an INDENT instruction with the current indentation level, and reset the position to this value.
• For nest expressions, we process all of the subexpressions, but with the current indentation level increased by the nest expression's indentation value.
• Finally, for group expressions we first check if the entire group can be rendered flat without exceeding the remaining space. This determines the value of flat for all of the grouped subexpressions, which in turn decides whether brs are rendered as line breaks (or as text).

How does fits_flat work? It simply walks through the instructions in the group, treating brs as text, and stopping when either:

• We've run out of space (width < 0), in which case the grouped subexpressions can't be rendered flat.
• We've processed all subexpressions, in which case the group can be rendered flat.

TEXT '['
LINE 4
TEXT "'onions'"
TEXT ','
LINE 4
TEXT '['
TEXT ''
TEXT "'carrots'"
TEXT ','
TEXT ' '
TEXT "'celery'"
TEXT ''
TEXT ']'
TEXT ','
LINE 4
TEXT "'turnips'"
LINE 0
TEXT ']'

Putting it all Together

We can finally click the pieces together:

[
    'onions',
    ['carrots', 'celery'],
    'turnips'
]

The only remaining pieces of the pretty-printer interface are the document expression constructors:

[
    'onions',
    [
        'carrots',
        'celery'
    ],
    'turnips'
]

Let's try the example from the introduction:

['onions', ['carrots', 'celery'], 'turnips']

See the full source here.

How to "Program" in Doc

? Under Construction ?

• Common patterns.
• How br, nest, and group interact.

Bells and Whistles

? Under Construction ?

• Adding a fold parameter group to force folding.

The above is the detailed content of Pretty-Printing is Compilation. For more information, please follow other related articles on the PHP Chinese website!