漂亮的列印就是編譯
- DDD原創
- 2024-11-01 04:21:02511瀏覽
Wadler 的 Prettier Printer 是一款經典的功能性珍珠。然而，無論是由於哈斯克爾的懶惰還是我自己的懶惰，我都在努力用其他語言（甚至在讀完論文五分鐘後用哈斯克爾）重新實現他的想法。值得慶幸的是，Lindig 認識到了這個問題，並在《🎜>Strictly Pretty中帶火了大眾。但即使這樣對我來說還不夠愚蠢。
但是在花了更多時間修改兩篇論文中的想法之後，我想我終於明白了。概述
如標題所示，我們將漂亮列印視為以抽象「文檔語言」編寫的程式的
編譯（和執行）過程。與大多數程式語言一樣，這種文檔語言—我們稱之為
Doc——具有可以組合在一起的表達式；這使得人類很容易推理。我們會將 Doc 中的表達式編譯為一種組合語言 (ASM) 的指令。 ASM 中的指令更容易轉換為字串。
['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 指令視為控制一個非常簡單的列印設備，它只能做兩件事：
- 發出一串文字。
- 前進到下一行，並縮排一定量。
-
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 會更簡單。引入這個額外的“通過”讓每一步都更加清晰。
中間表示
所以我們描述漂亮列印過程的示意圖有點過於簡化了。完整圖片如下：
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中文網其他相關文章！