Pretty-Printing is Compilation

DDD
Release: 2024-11-01 04:21:02
Original
530 people have browsed it

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:

Pretty-Printing is Compilation

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

['onions', ['carrots', 'celery'], 'turnips']
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login

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()
    + ']'
)
Copy after login
Copy after login
Copy after login
Copy after login

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 ']'
Copy after login
Copy after login
Copy after login
Copy after login

which are then interpreted as a string:

[
    'onions',
    ['carrots', 'celery'],
    'turnips'
]
Copy after login
Copy after login
Copy after login
Copy after login

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'
]
Copy after login
Copy after login
Copy after login
Copy after login

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

['onions', ['carrots', 'celery'], 'turnips']
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login

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']
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login

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()
    + ']'
)
Copy after login
Copy after login
Copy after login
Copy after login

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 ']'
Copy after login
Copy after login
Copy after login
Copy after login

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

[
    'onions',
    ['carrots', 'celery'],
    'turnips'
]
Copy after login
Copy after login
Copy after login
Copy after login

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

[
    'onions',
    [
        'carrots',
        'celery'
    ],
    'turnips'
]
Copy after login
Copy after login
Copy after login
Copy after login

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

['onions', ['carrots', 'celery'], 'turnips']
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login

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

TEXT 'hello'
LINE 2
TEXT 'indented'
TEXT ' world'
LINE 0
TEXT 'goodbye'
Copy after login
Copy after login

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
     ^
Copy after login
Copy after login

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
__
  ^
Copy after login
Copy after login

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
          ^
Copy after login
Copy after login

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
                ^
Copy after login
Copy after login

For example:

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

== OUTPUT ==

hello
__indented world

^
Copy after login
Copy after login

is a Doc expression, as is:

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

== OUTPUT ==

hello
__indented world
goodbye
       ^
Copy after login
Copy after login

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
Copy after login
Copy after login

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
Copy after login
Copy after login

The second, more complex expression:

['onions', ['carrots', 'celery'], 'turnips']
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login

may represent either:

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

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 ']'
Copy after login
Copy after login
Copy after login
Copy after login

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'
]
Copy after login
Copy after login
Copy after login
Copy after login

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

[
    'onions',
    [
        'carrots',
        'celery'
    ],
    'turnips'
]
Copy after login
Copy after login
Copy after login
Copy after login

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']
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login

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'
Copy after login
Copy after login

The variant classes now look like:

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

== OUTPUT ==

hello
     ^
Copy after login
Copy after login

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
__
  ^
Copy after login
Copy after login

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:

Pretty-Printing is Compilation

IR expressions resemble Doc expressions in many ways:

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

== OUTPUT ==

hello
__indented
          ^
Copy after login
Copy after login

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
                ^
Copy after login
Copy after login

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

^
Copy after login
Copy after login

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
       ^
Copy after login
Copy after login

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

AsmInst = str | int
Copy after login
Copy after login

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
Copy after login
Copy after login

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']
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login

process is where the magic happens:

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

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 ']'
Copy after login
Copy after login
Copy after login
Copy after login

Putting it all Together

We can finally click the pieces together:

[
    'onions',
    ['carrots', 'celery'],
    'turnips'
]
Copy after login
Copy after login
Copy after login
Copy after login

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

[
    'onions',
    [
        'carrots',
        'celery'
    ],
    'turnips'
]
Copy after login
Copy after login
Copy after login
Copy after login

Let's try the example from the introduction:

['onions', ['carrots', 'celery'], 'turnips']
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login
Copy after login

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!

source:dev.to
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!