`\n` はどこから来たのか？

(rodarmor.com)

1 ポイント投稿者 GN⁺ 2024-10-07 | 1件のコメント | WhatsAppで共有

just foo は justfile の "\n" を処理して、bar ファイルに 単一バイト 0x0A を書き込み、この記事はこの値がどこから来たのかを段階的にたどる
just の Rust パーサーは \n エスケープに出会うと、Rust の文字エスケープ '\n' の値を文字列に入れるよう実装されている
現在の rustc も Rust で書かれているため、追跡は再び rustc の lexer へと続くが、self-hosted 以前の OCaml 実装 により直接的な手がかりがある
初期の OCaml 版 rustc は文字エスケープ n を Char.code '\n' として処理し、OCaml lexer はこれを '\010' と定義している
0x0A は 10 なので、justfile の \n は Rust コンパイラの世代を超えて受け継がれてきた値であり、その出発点は OCaml コンパイラが '\010' を評価して初期 rustc バイナリに入れたバイトへと行き着く

`justfile` の `\n` が `0x0A` になるまで

just foo を実行すると、次の justfile は bar ファイルに 単一バイト 0x0A を書き込む

x := "\n"
foo:
printf '{{x}}' > bar

just は Rust で書かれており、パーサーの cook_string 関数がエスケープシーケンスを含む just の文字列トークンを UTF-8 文字列へ変換する
バックスラッシュの後に n が来ると、この関数は cooked.push('\n') を実行する

State::Backslash => {
    match c {
        'n' => cooked.push('\n'),
        …
    }
}

この段階で just は、Rust の文字エスケープ '\n' の評価結果を文字列に入れる処理を rustc に委ねている

`rustc` と OCaml までさかのぼる経路

rustc のエスケープ処理は lexer の scan_escape 関数にあり、n に出会うと再び Rust の文字エスケープ '\n' として処理する

let res: char = match chars.next().ok_or(EscapeError::LoneSlash)? {
    …
    'n' => '\n',
    …
};

現在の rustc は Rust で書かれ、自分自身をコンパイルするため、'\n' の意味を探す過程は rustc から再び rustc へ と続いていく
ただし、rustc は最初から Rust で書かれていたわけではなく、self-hosted 以前の初期バージョンは OCaml で書かれていた
OCaml 版 rustc の lexer は文字エスケープ n を次のように処理していた

| 'n' { end_char (Char.code '\n') lexbuf }

ここでも OCaml の文字エスケープ '\n' が使われているが、OCaml lexer にはさらに直接的な定義がある

let char_for_backslash = function
  'n' -> '\010'

OCaml コンパイラが \n を見ると、10進の文字エスケープ '\010' の評価結果を入れ、0x0A は 10 なので求めていたバイト値と一致する
したがって justfile の \n は、just バイナリ内のある形の 0x0A バイトへとつながり、そのバイトは rustc が入れ、さらに以前の rustc たちが世代を超えて同じ値を受け渡してきた流れとして見られる
現在の rustc は 1.81.0 であり、rustc 1.0 以降だけを見てもこの過程は少なくとも 81 回起きており、1.0 以前まで含めればさらに多かった可能性がある
追跡の出発点は、OCaml コンパイラが 10進の文字エスケープ '\010' を評価して初期 rustc バイナリに 0x0A バイトを入れた地点である

1件のコメント

GN⁺ 2024-10-07

Hacker News のコメント

このアイデアを最初に読んだのは、一般的な trusting trust ではなく改行文字に関する内容で、https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compile... の42日目だった
文字列リテラル内の "\n" を実際の改行文字として解釈するには、ソースコードにはその ASCII コード情報がなく、コンパイラをコンパイルした以前のコンパイラから受け継がれる、という点が興味深い
結局、そのコンパイラの改行文字は、それ自身をコンパイルした GCC までさかのぼれる
- GCC も '\n' の値を自分のコンパイラに任せる方式だと期待していたが、実際にはエスケープの数値をハードコードしており[1]、ASCII と EBCDIC システム用の選択肢だけを用意しているようだった
  [1] https://github.com/gcc-mirror/gcc/blob/8a4a967a77cb937a2df45...
筆者が思い浮かべていた原典は、Ken Thompson のチューリング賞講演 Reflections on Trusting Trust である可能性が高そう
- その講演でも、この技法がより一般的には**クワイン（quine）**で使われることに触れている
  クワインに関する研究、論文、解説はかなり多いので、筆者はそうした文章を読んだのかもしれない
  https://en.wikipedia.org/wiki/Quine_(computing)
- 2009年に出た、この短くて優れたウェブ記事も読む価値がある
  https://www.teamten.com/lawrence/writings/coding-machines/
- それではないと思う
  自分も数年前に Rust の '\n' についてまったく同じトリビア記事を見た記憶があるが、今では出典を見つけられない
10時間たっても EBCDIC に言及したスレッドがないのは興味深い
初期の C コンパイラは、\n の「改行（line feed）」を10進数の10にマッピングしない非 ASCII システムにも存在したので、ここで交わされているすべての理論はその事実を説明する必要がある
https://en.wikipedia.org/wiki/EBCDIC
さらに EBCDIC には、明示的な NextLine 文字と LineFeed 文字の両方があった
ASCII では for (c = 'A'; c <= 'Z'; ++c) putchar(c); が A から Z までを出力するが、EBCDIC では文字の間に空き領域があるため、未割り当ての文字まで含めて41文字を出力してしまう
EBCDIC の照合順序では小文字が大文字より前にあり、文字が数字より前にあるので、ASCII とは正反対だった
C 標準が文字エンコーディングについて保証していたのは、数字 '0'〜'9' が連続した昇順にマッピングされることだけだった
理論上は単純な C プログラムなら ASCII でも EBCDIC でも同じソースからコンパイルされ、同じ出力を出すべきだったが、実際には落とし穴が多かった
- EBCDIC には改行／次行文字 NEL があるにはあるが、多くの EBCDIC システムではあまり目にしない
  初期の EBCDIC システム（MVS、VM/CMS、OS/400、DOS/VSE など）は、テキストをバイトストリームファイルとして保存するのではなく、レコード指向ファイルとして保存しており、各行は固定長または可変長のレコードだった
  固定長レコードでは、ファイル作成時に 80 や 132 といったレコード長を宣言し、短い行は通常 EBCDIC の空白文字 0x40 で埋められ、長い行は切り詰められるか継続文字を使った
  可変長レコードは長さを含むレコード記述ワード（RDW）を先頭に付けていたが、テキストファイルやソースコードではまれで、固定長レコードが一般的だった
  そのため NEL が存在しても、ディスクファイルでは通常使われなかった
  NEL のような改行文字は行／レコード境界を示す帯域内シグナルだが、レコード指向ファイルシステムはその境界を帯域外で表現していたからだ
  EBCDIC C コンパイラのランタイムライブラリで stdio が正確にどう実装されていたのかは分からないが、内部的には \n を NEL にマッピングしたうえで stdio 層がそれをレコード区切りとして扱い、各レコードを別々のシステムコールで書き込み、必要ならパディングしていたのだと思う
  その後、こうした OS の大半は POSIX 互換サブシステムを得て、主流システムのようなバイトストリームファイルも持つようになった
  IBM システムはファイルにコードページタグを付ける機能を一般的にサポートしているため、ファイルが EBCDIC と ASCII を混在して持つことができ、OS が入出力層で変換してくれる
  そのおかげで、ランタイムで EBCDIC を使うアプリケーションでも、ASCII ファイルを別途の変換 API 呼び出しや明示的な指定なしに EBCDIC のように読める
  新しいアプリケーションは POSIX ベースのファイルシステムをますます使うようになっているが、古いアプリケーションはデータ、テキストファイル、ソースコードまでも、今なお古典的なレコード指向ファイルシステムに保存していることが多い
  実環境で EBCDIC NEL を最もよく見かけた場所は、IBM 2741 や IBM 3767 のようなハードコピー端末のラインモード端末接続だったと理解している
本当に興味深い記事だ
私には文芸的プログラミングと詩が混ざったもののように読める
just foo を実行したときに出てくる、まさにその 0x0A バイトが、もしかすると何百回ものコード生成サイクルを経てきたのだ、という考えを説明しようとしている記事だ
大昔に誰かがこの情報を何らかの形で OCaml コンパイラにエンコードし、何年も後に私のコンピュータの 0x0A 情報がその歴史のおかげで保存されている、というわけだ
そしてこの現象は実際のコードで説明されている
もちろんそのコード自体が要点ではないし、誰かがこの特定のコードを実行したりコンパイルしたりするとも思えないが、人が議論を追えるように置かれたコードなのだ
clang も同じ性質を持つのか気になったが、lib/Lex/LiteralSupport.cppで明示的に10にハードコードされている
ProcessCharEscapeが標準 C のエスケープシーケンスをパースし、case 'n': ResultChar = 10; break;のように処理する
- GCC も同様にgcc/libcpp/charset.ccでハードコードされており、ASCII または EBCDICのどちらかを選ぶ
  \a \b \e \f \n \r \t \vの値をcharconsts配列に入れ、ASCII なら{ 7, 8, 27, 12, 10, 13, 9, 11 }、EBCDIC なら{ 47, 22, 39, 12, 21, 13, 5, 11 }を使ったうえで、case 'n': c = charconsts[4]; break;として処理する
ある C コンパイラについての似た記事を覚えている
結局、0x10 という値が現れる唯一の場所はコンパイラのバイナリで、ソースコードには"\\n" -> "\n"のような形でしか入っていなかったことが分かった
自分の理解を超える話だ
なぜ\nが値 10 のバイトとしてエンコードされるのかを突き止めるために、こんな長い旅をしなければならないのか分からない
当たり前のことではないかと思うし、筆者もコメントも説明していないので、自分が馬鹿みたいに感じる
- 核心は、そのバイトを値 10 としてエンコードした「誰か」を問うことにある
  パーサを書いていて、改行をエスケープシーケンス\nとしてパースするなら、値 10 はどこから来たのか
  改行を整数リテラル10としてパースするなら、実際のバイナリ値1010はどこから来たのか
  この思考実験の究極の目的は、有名なReflections On Trusting Trustの講演のように、コンパイラに対する認識を変えることにある
  つまりコンパイラは単にプログラムを出力する何かではなく、プログラムの入力でもある
  コンパイラ自身もプログラムなので、そのコンパイラを作ったコンパイラが現在のコンパイラの入力であり、推移的に自分のプログラムの入力になる
  そしてこれはコンパイラのコンパイラのコンパイラ、さらにその上のコンパイラへと続いていく
- 面白いのは、値 10 が Rust のソースコード内で定義されているのではなく、コンパイラからコンパイラへと口伝のように受け継がれる点にある
- Rust コンパイラをゼロから再ビルドしなければならず、rustc のソースコードしか持っていない場合、ソースコードのどこにも'\n'が実際に何へマッピングされるのかを教えてくれる情報はない
  Ken Thompson のハックの興味深い現実例だ
- 核心は、なぜよりによって 10 なのかということだ
  なぜ 9 や 11 ではないのか
  コードは「改行文字列を見たら改行文字を出力せよ」と言っている
  ではコンパイラは、改行文字が何であるかをどうやって知るのか
  そのコンパイラのコードもまた「改行文字列を見たら改行文字として扱え」とだけ言っているにすぎない
  人間なら「C 文字列エスケープコード」を検索すればよいが、その表はコンパイラの中のどこにもない
  C 2025 が Start of Heading を\hと定義したら、'h' => cooked.push('\h')は魔法のように動き始めるのだろうか
  いったいどうやって分かるというのか
  どこかの時点で、誰かが'n' => 10のマッピングを手動でプログラムしたはずで、その場所はどこなのか、という問いだ
C のせいか、\0???は8進数エスケープだとずっと思っていた
なので自分の頭の中では、\012は\x0aまたは0x0aで、\010は0x08だ
だからこの記事はかなり混乱する
もしかすると OCaml には 8進数エスケープではなく 10進数エスケープがあり、\09がタブ文字なのかもしれない
確認はしていない
- その方向にもある程度合っている点はあるが、バックスラッシュエスケープとは関係ない
  バックスラッシュエスケープは象徴的／記憶補助的なもので、\nは「[Ne]wline」、\rは「carriage [R]eturn」、\tは「[T]ab」といった具合だ
  代わりに、^C（割り込み）、^G（ベル）、^M（キャリッジリターン）のような制御文字の慣例を見るとよい
  これらは C0 制御文字集合にあり、^Cは\0x3、^Gは\0x7、^Mは\0xDだ
  Unix 以前にさかのぼる巧妙な方式で、端末は見えない ASCII の C0 文字を表現するために、先頭に^文字を付け、その文字に AND-0x40 を適用して表示可能な範囲へ移して出力していた
  たどるには、https://www.asciitable.com のような ASCII 表を開くとよい
  各制御文字は、その表で2列隣の^文字にマッピングされる
  そのため、\0が不思議にも^@と表現されたり、Esc キーが^[になったりと、覚えにくい等価表現が生まれる
  これは Unix 作者たちの選択ではなく、ASCII の番号体系の産物だ
- 実際、OCaml は 10進数エスケープを使う: https://ocaml.org/manual/5.2/lex.html#char-literal
- バックスラッシュ＋10進数の文字エスケープは本当に珍しい
  私が知っている文字列構文では、OCaml、Lua、DNSくらいだ
誤った大文字表示のせいで、もしかして\nとは別の、ほとんど知られていないエスケープシーケンス**\N**があるのかと思った
改行以外の任意の文字にマッチするのかと思ったが、そうではなく、元記事のスモールキャップス表示のせいだった
- ソース表示をすると実際には\nなのだが、この CSS ルールのせいでそう表示されない
  .title { font-variant: small-caps; }
- 実際に\Nを使う場所はある
  多くのシステムが CSV や似た形式で、空文字列と区別するために\NをNULLとして使う
  だからこの記事もその話だと思った
- Python には\Nエスケープシーケンスがある
  名前で Unicode 文字を挿入する
  たとえば'\N{PILE OF POO}'は、うんち絵文字1つからなる Unicode 文字列だ
  \uや\Uで16進数シーケンスを書くより、ずっと自己説明的だ
- 私もそれでこの記事をクリックした
  それでも面白く読めた
この記事に着想を与えた「別の記事」は、おそらくこれだと思われます
https://research.swtch.com/nih
- ここで議論されたことがあります
  Running the "Reflections on Trusting Trust" Compiler - https://news.ycombinator.com/item?id=38020792 - 2023年10月、コメント67件

`\n` はどこから来たのか？

justfile の \n が 0x0A になるまで

rustc と OCaml までさかのぼる経路

関連記事

1件のコメント

Hacker News のコメント

`justfile` の `\n` が `0x0A` になるまで

`rustc` と OCaml までさかのぼる経路