Pretty-Printing is Compilation

Wadler's A Prettier Printer is a classic functional pearl. Someday I hope to understand it. 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 picture.

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 <text>, which emits a string of text.
2. LINE <indent>, 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:

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

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:

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

== OUTPUT ==

hello
     ^

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

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

== OUTPUT ==

hello
__
  ^

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

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

== OUTPUT ==

hello
__indented
          ^

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

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

== OUTPUT ==

hello
__indented world
                ^

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

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

== OUTPUT ==

hello
__indented world

^

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

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

== OUTPUT ==

hello
__indented world
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:

AsmInst = str | int

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

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

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:

insts = ["hello", 2, "indented", " world", 0, "goodbye"]

print(interpret(insts))
# hello
#   indented world
# goodbye

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:

DocExpr = nil
        | DocExpr + DocExpr
        | str
        | br(str?)
        | nest(int, DocExpr)
        | group(DocExpr)

For example:

'test' + br() + 'ing' + br(' ') + 'this'

is a Doc expression, as is:

group(nest(2, 'test' + br() + 'ing' + br(' ') + 'this'))

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:

'test' + br() + 'ing' + br(' ') + 'this

represents the string:

testing this

The second, more complex expression:

group(nest(2, 'test' + br() + 'ing' + br(' ') + 'this'))

may represent either:

testing this

or:

__test
__ing
__this

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:

from __future__ import annotations
from dataclasses import dataclass

@dataclass
class Nil:
    pass

@dataclass
class Br:
    text: str = ""

@dataclass
class Nest:
    indent: int
    doc: DocExpr

@dataclass
class Group:
    doc: DocExpr

DocExpr = Nil | Concat | str | Br | Nest | Group

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

@dataclass
class Concat:
    car: DocExpr
    cdr: DocExpr

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.:

@dataclass
class Nil:
    def __add__(self: DocExpr, other: DocExpr) -> DocExpr:
        return Concat(self, other)

    def __radd__(self: DocExpr, other: DocExpr) -> DocExpr:
        return Concat(other, self)

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

def with_add(cls):
    """Add suitable __add__ and __radd__ methods to cls so that instances of it
    can be concatenated using "+".
    """

    def add(self: DocExpr, other: DocExpr) -> DocExpr:
        return Concat(self, other)

    def radd(self: DocExpr, other: DocExpr) -> DocExpr:
        return Concat(other, self)

    setattr(cls, "__add__", add)
    setattr(cls, "__radd__", radd)

    return cls

The variant classes now look like:

@with_add
@dataclass
class Nil:
    pass

@with_add
@dataclass
class Concat:
    car: DocExpr
    cdr: DocExpr

@with_add
@dataclass
class Br:
    text: str = ""

@with_add
@dataclass
class Nest:
    indent: int
    doc: DocExpr

@with_add
@dataclass
class Group:
    doc: DocExpr

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:

def compile(expr: DocExpr, max_len: int) -> list[AsmInst]:
    """Compile a Doc expression to a sequence of ASM instructions."""
    pass

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:

IrExpr = str
       | br(str?)
       | nest(int, list[IrExpr])
       | group(list[IrExpr])

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:

def lower(expr: DocExpr) -> list[IrExpr]:
    pass

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

@dataclass
class BR:
    text: str

@dataclass
class NEST:
    indent: int
    insts: list[IrExpr]

@dataclass
class GROUP:
    insts: list[IrExpr]

IrExpr = str | BR | NEST | GROUP

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.

def lower(expr: DocExpr) -> list[IrExpr]:
    """Lower a Doc expression to an equivalent sequence of IR expressions."""
    match expr:
        case Nil():
            return []
        case Concat(car, cdr):
            return lower(car) + lower(cdr)
        case text if isinstance(text, str):
            return [text]
        case Br(text):
            return [BR(text)]
        case Nest(indent, expr):
            return [NEST(indent, lower(expr))]
        case Group(expr):
            return [GROUP(lower(expr))]
        case _:
            raise ValueError("expected a doc")

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

doc = Group(Nest(2, "test" + Br() + "ing" + Br(" ") + "this"))
print(lower(doc))

# [GROUP(insts=[NEST(indent=2, insts=['test', BR(text=''), 'ing', BR(text=' '), 'this'])])]

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 compile(exprs: list[IrExpr], max_len: int) -> list[AsmInst]:
    """Compile a sequence of IR expressions into a list of ASM instructions."""
    pass

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.

def compile(exprs: list[IrExpr], max_len: int) -> list[AsmInst]:
    """Compile a sequence of IR expressions into a list of ASM instructions."""
    pos = 0
    asm = []

    def process(expr, indent=0, flat=True):
        nonlocal pos, asm
        match expr:
            # Append ASM instructions for expr to asm, and update pos.
            # ...

    for expr in exprs:
        process(expr)

    return asm

process is where the magic happens:

def process(expr, indent=0, flat=True):
    nonlocal pos, asm
    match expr:
        case text if isinstance(text, str):
            asm.append(text)
            pos += len(text)
        case BR(text):
            if flat:
                asm.append(text)
                pos += len(text)
            else:
                asm.append(indent)
                pos = indent
        case NEST(nest_indent, nest_exprs):
            for nest_expr in nest_exprs:
                process(nest_expr, indent=indent + nest_indent, flat=flat)
        case GROUP(group_exprs):
            flat = fits_flat(group_exprs, max_len - pos)
            for group_expr in group_exprs:
                process(group_expr, indent=indent, flat=flat)

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.

def fits_flat(exprs: list[IrExpr], width: int) -> bool:
    """Can the list of IR expressions can be laid out flat without exceeding
    the provided width?"""
    if width < 0:
        return False
    elif not exprs:
        return True

    first, *rest = exprs
    match first:
        case text if isinstance(text, str):
            return fits_flat(rest, width - len(text))
        case BR(text):
            return fits_flat(rest, width - len(text))
        case NEST(_, nest_exprs):
            return fits_flat(nest_exprs + rest, width)
        case GROUP(group_exprs):
            return fits_flat(group_exprs + rest, width)

Putting it all Together

We can finally click the pieces together:

def layout(doc: DocExpr, max_len: int) -> str:
    """Transform a Doc expression into a string it represents, trying not to
    exceed a line width of max_len.
    """
    ir = lower(doc)
    asm = compile(ir, max_len)
    return interpret(asm)

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

nil = Nil()
br = Br
nest = Nest
group = Group

Let's try the example from the introduction:

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

print(layout(doc, 60))
# ['onions', ['carrots', 'celery'], 'turnips']

print(layout(doc, 30))
# [
#     'onions',
#     ['carrots', 'celery'],
#     'turnips'
# ]

print(layout(doc, 20))
# [
#     '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.