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:
- Emitting a string of text.
- Advancing to the next line, and indenting by a certain amount.
Hence ASM consists of only two instructions:
-
TEXT <text>
, which emits a string of text. -
LINE <indent>
, which advances the printer to the next line, and then indents byindent
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 Pythonstr
s. -
LINE
instructions will be represented byint
s.
That is:
AsmInst = str | int
Interpreting a list of AsmInst
s 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 byindent
spaces. -
group(doc)
delimits a subexpression in which allbr()
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 str
s 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 IrExpr
s.
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
br
s 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 offlat
:- If
flat
isTrue
, treat them as text. - Otherwise, emit an
INDENT
instruction with the current indentation level, and reset the position to this value.
- If
- For
nest
expressions, we process all of the subexpressions, but with the current indentation level increased by thenest
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 offlat
for all of the grouped subexpressions, which in turn decides whetherbr
s are rendered as line breaks (or as text).
How does fits_flat
work? It simply walks through the instructions in the group, treating br
s 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
, andgroup
interact.
Bells and Whistles
🚧 Under Construction 🚧
- Adding a
fold
parametergroup
to force folding.
Top comments (0)