Pretty-Printing はコンピレーションです

Wadler の A Prettier Printer は、古典的な機能的な真珠です。しかし、Haskell の怠惰のためか、私自身の怠惰のためかはわかりませんが、私は彼のアイデアを他の言語で再実装するのに苦労しました (論文を読んだ 5 分後には、Haskell でさえ)。ありがたいことに、リンディグはこの問題を認識し、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'
]

上でほのめかした重要な機能の 1 つは、コンパイラには、ターゲットの最大線幅である構成可能な「アーキテクチャ パラメータ」があることです。このパラメータの値に応じて、コンパイラは同じ Doc プログラムに対して異なる ASM 命令を発行します。上の例では、ターゲット幅 30 を使用しました。代わりに 20 を使用した場合、生成されるアセンブリ命令と結果の文字列は異なります:

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

60 を使用した場合、次のようになります:

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

プリンターアセンブリ言語

アセンブリ言語は簡単なので、最初に取り組みます。 ASM 命令は、次の 2 つのことだけを実行できる非常に単純な印刷デバイスを制御するものと考えます。

1. テキスト文字列を出力します。
2. 次の行に進み、一定量インデントします。

したがって、ASM は 2 つの命令のみで構成されます。

1. TEXT : テキスト文字列を出力します。
2. 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()
    + ']'
)

LINE 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 'goodbye' は 'goodbye' を出力します:

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

ASM 命令を「合計タイプ」として表します。

• TEXT 命令は Python strs で表されます。
• LINE命令はintで表現されます。

つまり:

> 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() は 可能な改行です。
• net(indent, doc) は、インデント スペースによって視覚的にオフセットされた「ネストされた」部分式を作成します。
• group(doc) は、すべての br() が改行として扱われるかどうかの部分式を区切ります。
• ドキュメント式を結合します。
• 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

2 番目のより複雑な式:

['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 を使用して 2 つの Doc 式を追加すると、2 つの Concat が構築されます。これを手動で行うのは非常に簡単です。例:

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

^

下位の操作はすべて、Nil() インスタンスを空のリスト ([]) に置き換え、concat(car, cdr) インスタンスを car 式と cdr 式を下位にした結果を追加することです。同じ処理がネストとグループの部分式に適用されます。これは再帰的な「平坦化」操作にすぎません。

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

== OUTPUT ==

hello
__indented world
goodbye
       ^

上記の Doc 式の例の 1 つを使用して下位をテストします。

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、nest、グループがどのように相互作用するか。

ベルとホイッスル

?工事中?

• 折りたたみパラメータ グループを強制に追加します。

以上がPretty-Printing はコンピレーションですの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。