漂亮的打印就是编译

DDD原创: 2024-11-01 04:21:02590浏览

Wadler 的 Prettier Printer 是一款经典的功能性珍珠。然而，无论是由于哈斯克尔的懒惰还是我自己的懒惰，我都在努力用其他语言（甚至在读完论文五分钟后用哈斯克尔）重新实现他的想法。值得庆幸的是，Lindig 认识到了这个问题，并在《🎜>Strictly Pretty中带火了大众。但即使这样对我来说还不够愚蠢。

但是在花了更多时间修改两篇论文中的想法之后，我想我终于明白了。

概述

正如标题所示，我们将漂亮打印视为以抽象“文档语言”编写的程序的

编译（和执行）过程。与大多数编程语言一样，这种文档语言——我们称之为
Doc——具有可以组合在一起的表达式；这使得人类很容易推理。我们会将 Doc 中的表达式编译为一种汇编语言 (ASM) 的指令。 ASM 中的指令更容易转换为字符串。

这是该过程的示意图：

Pretty-Printing is Compilation

作为一个具体示例，假设我们想要漂亮地打印嵌套列表：

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

这是一个用于执行此操作的文档程序：

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

我们很快就会见到团体、巢穴等。现在，对文档语言有一个大致的了解就足够了。

然后将该程序编译（设置某些“架构参数”）到 ASM 指令中：

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 ']'

然后被解释为字符串：

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

上面提到的一个重要功能是编译器有一个可配置的“架构参数”，它是

目标最大线宽。根据此参数的值，编译器将为同一个 Doc 程序发出不同的 ASM 指令。在上面的示例中，我们使用的目标宽度为 30。如果我们使用 20，则发出的汇编指令将会有所不同，生成的字符串也会有所不同：

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

如果我们使用 60，它将是：

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

打印机汇编语言

汇编语言很简单，所以我们先解决它。我们将 ASM 指令视为控制一个非常简单的打印设备，它只能做两件事：

因此 ASM 仅包含两条指令：

TEXT ，发出一串文本。
LINE ，将打印机前进到下一行，然后按缩进空格缩进。

ASM 程序通过依次执行指令来解释为字符串。作为示例，让我们跟踪程序的执行情况：

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

我们将使用 >指示正在执行的指令，并在下面显示当前输出。 ^ 字符将指示“打印机头”的当前位置。我们还将使用 _ 字符来表示空格，因为否则很难跟踪。

第一个 TEXT 指令导致发出字符串“hello”：

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

第 2 行前进到下一行并将头部缩进 2 个空格：

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 ']'

然后 TEXT 'indented' 会导致添加 'indented'：

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

后跟“world”，由于文本“world”：

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

LINE 0 将打印机前进到下一行（并且根本不缩进）：

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

最后，TEXT“再见”发出“再见”：

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

我们将 ASM 指令表示为“总和类型”：

TEXT 指令将由 Python strs 表示。
LINE 指令将用整数表示。

即：

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

== OUTPUT ==

hello
     ^

将 AsmInst 列表解释为它们代表的字符串只需迭代指令并“做正确的事情”：

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

== OUTPUT ==

hello
__
  ^

对于TEXT指令，解释器将文本附加到结果中；对于 LINE 指令，解释器会附加一个换行符 ('n')，后跟缩进空格。

我们可以使用上面示例中的 ASM 指令进行测试解释，并将其翻译成 Python：

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

== OUTPUT ==

hello
__indented
          ^

文档语言（预告片）

我们喜欢 ASM 因为它很容易解释。但使用起来很痛苦。这激发了更加人性化的 Doc 语言。 ASM 程序是指令的序列，而Doc程序是表达式的组合。这些表达式由以下语法总结：

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

== OUTPUT ==

hello
__indented world
                ^

例如：

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

== OUTPUT ==

hello
__indented world

^

是一个Doc表达式，如下：

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

== OUTPUT ==

hello
__indented world
goodbye
       ^

这些代表什么？

Python str 文字代表其自身。
br() 是可能的换行符。
Nest(indent, doc) 创建一个“嵌套”子表达式，该子表达式在视觉上通过缩进空格进行偏移。
group(doc) 分隔一个子表达式，其中所有 br() 要么被视为换行符，要么不被视为换行符。
结合了 Doc 表达式。
nil 充当“空”表达式。

所以，例如：

AsmInst = str | int

代表字符串：

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

第二个更复杂的表达式：

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

可以代表：

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

或：

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 ']'

取决于提供给编译器的目标最大线宽“架构参数”的值。因此 br 表达式可能被视为换行符或常规文本，在这种情况下使用它们的文本值（如果未提供文本参数则使用 ''）。

我们将使用 strs 和 Python 类来表示 Doc 表达式。特别是：

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

DocExpr DocExpr 怎么样？我们将使用额外的 Concat 类来代表那些：

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

我们希望支持使用组合表达式，因此我们需要在每个变体类上实现 __add__ 和 __radd__ 。使用 just 构造两个 Doc 表达式来添加两个 Doc 表达式。手动执行此操作很容易，例如：

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

但是我们可以通过定义一个装饰器来为我们节省一些打字时间：

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

变体类现在看起来像：

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

== OUTPUT ==

hello
     ^

我们现在的任务是编写一个编译器，在给定一些目标最大行宽的情况下，将 Doc 语言中的表达式翻译为等效的 ASM 指令：

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

== OUTPUT ==

hello
__
  ^

然而，事实证明，首先将 Doc 表达式“降级”为 中间表示 (IR) 语言中的表达式，然后将 IR 表达式编译为 ASM 会更简单。引入这个额外的“pass”让每一步都更加清晰。

中间表示

所以我们描述漂亮打印过程的示意图有点过于简单化了。完整图片如下：

Pretty-Printing is Compilation

IR 表达式在很多方面类似于 Doc 表达式：

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

== OUTPUT ==

hello
__indented
          ^

关键的区别是我们不再有和 nil 表达式：这些在降低过程中被转换为 IR 表达式列表。实际上，这就是所有降低过程的作用：

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

== OUTPUT ==

hello
__indented world
                ^

我们首先需要定义 IrExprs。
这看起来应该很熟悉：

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

== OUTPUT ==

hello
__indented world

^

所有 lower 所做的都是用空列表 ([]) 替换 Nil() 实例，并通过附加降低 car 和 cdr 表达式的结果来替换 Concat(car, cdr) 实例。同样的处理也适用于 Nest 和 Group 中的子表达式。这无非是一个递归的“展平”操作。

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

== OUTPUT ==

hello
__indented world
goodbye
       ^

使用上面的示例 Doc 表达式之一来测试 lower：

AsmInst = str | int

这正是我们所期望的。

编译器（最后）

现在到最后一步：编译。该函数将 IR 表达式转换为 ASM 指令，同时考虑目标最大线宽：

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

这是算法的大致思路：

编译器维护一些“状态”信息：
- 当前（水平）线位置。
- 当前的缩进量。
- brs 是否应该被视为换行符或呈现“扁平”。
我们迭代表达式，发出一些 ASM 指令并适当更新行位置。

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

过程就是奇迹发生的地方：

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

简而言之：

对于文本表达式，我们发出一条 TEXT 指令，并将位置 (pos) 前进文本的长度。
br 表达式的处理取决于 flat 的值：
- 如果 flat 为 True，则将它们视为文本。
- 否则，发出具有当前缩进级别的 INDENT 指令，并将位置重置为此值。
对于嵌套表达式，我们处理所有子表达式，但当前缩进级别会增加嵌套表达式的缩进值。
最后，对于组表达式，我们首先检查整个组是否可以在不超过剩余空间的情况下渲染为平坦。这决定了所有分组子表达式的 flat 值，进而决定 brs 是否呈现为换行符（或文本）。

fits_flat 是如何工作的？它只是简单地遍历组中的说明，将 brs 视为文本，并在出现以下情况时停止：

我们已经用完了空间（宽度
我们已经处理了所有子表达式，在这种情况下，组可以呈现为扁平的。

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 ']'

将所有内容放在一起

我们终于可以将各个部分组合在一起了：

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

漂亮打印机接口唯一剩下的部分是文档表达式构造函数：

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

让我们尝试一下简介中的示例：

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

请在此处查看完整源代码。

如何在文档中“编程”

？正在建设中？

常见模式。
br、巢穴和群体如何互动。

花哨的东西

？正在建设中？

添加折叠参数组以强制折叠。

以上是漂亮的打印就是编译的详细内容。更多信息请关注PHP中文网其他相关文章！

Python print String define if for try break using class Length Interface finally nil function this location display position transform idea kind

声明：

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：How to Merge DataFrames by Index in Python?下一篇：Why does `(1 in [1,0] == True)` evaluate to `False` in Python?

查看更多