From 863a6ed0ad723e06c76f392d4fb3a5f6bd22863c Mon Sep 17 00:00:00 2001 From: Jun Kawasaki Date: Tue, 6 Oct 2026 13:01:11 +0900 Subject: docs: add Japanese translations for all chapters --- chapter23/README.ja.md | 343 ++++++++++++++++++++++++++++++++++++++++ chapter23/README.md | 2 + chapter23/docs/18-grammar.ja.md | 138 ++++++++++++++++ chapter23/docs/18-grammar.md | 2 + 4 files changed, 485 insertions(+) create mode 100644 chapter23/README.ja.md create mode 100644 chapter23/docs/18-grammar.ja.md (limited to 'chapter23') diff --git a/chapter23/README.ja.md b/chapter23/README.ja.md new file mode 100644 index 00000000..b83b0914 --- /dev/null +++ b/chapter23/README.ja.md @@ -0,0 +1,343 @@ +# 第23章: メソッドと型の再検討 + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第22章](../chapter22/README.ja.md) | +[次の章: 第24章](../chapter24/README.ja.md) + +この章では *メソッド* を追加します。構造体内で定義し、隠れた `self` 引数を取り、構造体のフィールドへアクセスできる関数です。文字列のようなクラスの `indexOf` メソッドを示します。 + +```java +// A String-like class, with methods +struct String { + u8[~] buf; // Buffer of read-only characters + + // Return the index of the first character 'c' or -1 + val indexOf = { u8 c -> // Hidden 'self' argument + for( int i=0; i int } indexOf; }` + +これは `String` という名前の型で、フィールド `u8[~] buf` と、final で代入済みの定数フィールド `indexOf` を持ちます。後者自身の型は `{ !String !self, u8 c -> int }` です。つまり `String` の型は、`indexOf` の型の内側に自分自身への参照を持ちます。`String` の型は *循環* しています。 + +## 循環の少ない型 + +循環する型の問題は古くからあり、対処のための実績ある方法がいくつもあります。簡単なものの1つは、型の *定義* と、それとは別の型の *参照* を持つ方法です。参照は何らかの検索で型を参照します。たとえば型名とパーサーのシンボル表を使う、ハッシュ表検索です。 + +このモデルでは循環を実質的に回避します。型の循環内の「後退辺」は、すべて参照辺、場合によってはハッシュ表検索で実現します。 + +では、なぜこの方法を採用しないのでしょうか。 + +すべての型参照が同じ型定義へ戻るためです。型情報を特化しても失われます。*すべての* 参照が同じ定義へ戻るため、*すべての* 経路の MEET を取ることになるのです。 + +Java の `Object`、または C の `void*` をデータとして持つ連結リストの例を示します。 + +```java +struct List { + !List !next; + Object payload; // equivalently for C: void* +} +// Then walk a collection of ints and build a List: +List nums = null; +for( int x : ary_ints ) + nums = new List{next=nums; payload=x; } + +// Again for strings: +List strs = null; +for( String x : ary_strs ) + strs = new List{next=strs; payload=x; } +``` + +`nums` の型は何でしょうか。`*List`、つまり次の型です。 + +``` +struct List { List *next; Object payload } +``` + +`Object` を `int` や `String` に精密化できません。すべての List オブジェクトのデータ型は `Object` で、`Object` MEET `int` は `Object` に戻るためです。 + +真に循環する型を許せば、このような場面で `*List { *List next, int payload }` という精密な型を発見、あるいは推論できます。基本的に最適化器内で *ジェネリクス* を構築するのです。言語のジェネリクスや型変数そのものではありませんが、それにかなり近づきます。 + +## 循環する型の扱い + +この章で Simple は循環する型を直接扱います。子の型が元の型へ戻る `Type` オブジェクトを持つため、型に対して [*再帰下降*](https://en.wikipedia.org/wiki/Recursive_descent_parser) がそのままでは使えなくなります。 + +これまでは型構築に再帰下降を使ってきました。子の型を先に作ってインターンし、インターン済みの子で次の階層を構築します。各階層がインターンされ、再帰下降がインターン済みの型で止まるので、共有する型での重複作業を避けられます。このため現在の型に対する演算は、旧型と新型の *差分* に対して線形となり、増分的で高速です。 + +新たな循環する型では、循環全体を見るまでインターンできない問題に直面します。またハッシュ表は等値検査を必要としますが、循環を等値比較するのに通常の再帰下降は使えません。 + +グラフの循環を扱う標準的な方法は、「以前ここに来た」ことを示す *訪問済み* の概念です。一意な型 ID をキーにするハッシュ表を使います。「訪問済み」は、一意な ID が表のキーにあるという意味です。各 Type は大域カウンタから一意な ID を得ます。型をインターンするので、必要な一意 ID 数は一意な型の数と、循環を構築・インターンするためのわずかな予備だけです。過去の経験では通常数千程度が最大なので、小さな整数で十分です。 + +もう1つ、既存の基盤をできる限り残したいので、既存の再帰下降による巡回を少しだけ修正してすべて保持します。 + +すべての型循環には `TypeStruct` が存在します。ただし関数が *自身* を引数に取る純粋な関数型の循環は例外です。それは奇妙なので、どう扱うかはそれほど気にしません。各 `TypeStruct` 生成器の中核で大域 `VISIT` ハッシュ表に要素を設定し、循環型作成の開始を示します。そしてその要素を検査し、循環を止めます。 + +例を見ましょう。 + +異なるデータ型の循環を持つかもしれない連結リストを使います。ただし、ここでは文字列だけです。連結リストは、簡単な代替と比べてひどく非効率なので、ほぼどんな仕事でも間違った構造であることが多いのですが、教材用のデータ構造としては優れています。 + +```java +struct List { + !List? !next; // Next pointer or null + str !name; // Payload +}; +``` + +この構造体の型は宣言に一致します。 + +`struct List { List*? next, str !name };` + +これで文字列リストを構築できます。 + +```java +var list = new List{ name="Hello"; }; +list = new List { list, name="World"; }; +``` + +### 循環する型の読み取り専用／final の検査 + +どこかで読み取り専用の不変な版を作りたいとします。 + +```java +val hello = list; // Make a read-only version +print(hello); // Pass along the read-only version +``` + +`hello` の型は何でしょうか。`List` の読み取り専用型です。しかし `List` は循環する型です。`Type.makeRO` を見ましょう。 + +> 訳注：原文では上の `val hello = list` を読み取り専用版の作成と説明しています。一方、第17b章では `val` は束縛を固定し、初期化式のアクセス権限を保持すると説明しています。この訳では、原文の例と説明を保持しています。 + +```java +public final Type makeRO() { + if( isFinal() ) return this; // First check if already read-only + return recurOpen()._makeRO().recurClose(); +} +``` + +そして `isFinal()`: + +```java +// Are all reachable struct Fields are final? +public final boolean isFinal() { return recurClose(recurOpen()._isFinal()); } +boolean _isFinal() { assert _type < TCYCLIC; return true; } +``` + +`recurOpen()` を呼んで再帰走査を開始／開き、`_isFinal()` を呼びながら再帰し、走査を終了／閉じて、真偽値を返します。`_isFinal()` は Java の final ではなく、Type のサブクラスでオーバーライドします。大半のサブクラスは単に問題を転送します。 + +`@Override boolean _isFinal() { return _obj._isFinal(); }` + +そして `TypeStruct` に到達します。 + +```java +@Override boolean _isFinal() { + if( _open ) return false; // May have more non-final fields + if( VISIT.containsKey(_uid) ) // Test: been here before? + return true; // Cycles assume final + VISIT.put(_uid,this); // Set: don't do this again + for( Field fld : _fields ) + if( !fld._isFinal() ) + return false; + return true; +} +``` + +ここには循環処理の共通パターン、**test-and-set** があります。まず確定できる答えを調べます。開いた構造体は部分的にしか定義されず、未解析の non-final フィールドが現れる可能性があるので、決して読み取り専用ではありません。次に以前訪問したかを **検査** し、そうなら再帰を止めて何らかの答えを返します。`isFinal` では、循環のほかのものもすべて final なら「final である」を返します。 + +まだこの型を調べていなければ、ここを訪れたことを示す訪問ビットを **設定** し、通常の再帰下降でフィールドに同じ質問をします。 + +この例では、`VISIT` に番兵を置いて再帰を開き、`struct List` に `makeRO` を呼びます。それが `_isFinal` を呼び、`_open`（開いていない）、`VISIT`（未訪問）を確認し、UID を `VISIT` に設定してフィールドを走査します。フィールドの検査は次のとおりです。 + +`@Override boolean _isFinal() { return _final && _t._isFinal(); }` + +最初のフィールド `List*? !next` は non-final なので、すぐ `false` を返します。これで `List` の `_isFinal` が止まり、`isFinal()` 全体が `false` を返して再帰を終了／閉じます。`VISIT` もクリアします。 + +### 循環する読み取り専用／final 型の作成 + +構築してからインターンする手順を明確にするため、すべての型に一意 ID を付けましょう。一意な型の後ろに UID の例を付けた `List` 型を示します。フィールドも型なので UID を持ちます。 + +``` +struct List#2 { // struct List has UID#2 + List#2*?#3 !next#4, // Field next has UID#3, type ptr-or-null#3 to List#2 + str#1 !name#5 // Field name has UID#5, type str#1 +}; +``` + +同じ UID が繰り返されることから、`List#2` が2回現れています。List が循環しているためです。 + +今度は実際に循環する型を作る必要があり、`makeRO()` は次の行に進みます。 + +`return recurOpen()._makeRO().recurClose();`. + +再び `recurOpen` が再帰走査を開始／開き、それから子の Type クラスそれぞれでオーバーライドする `_makeRO()` を呼びます。`TypeStruct` 版を見ます。 + +```java +// Make a read-only version +@Override TypeStruct _makeRO() { + // Check for already visited + TypeStruct ts = (TypeStruct)VISIT.get(_name); + if( ts!=null ) return ts; // Already visited + ts = recurPre(_name,_open); // Make a new type with blank fields + Field[] flds = ts._fields; + for( Field fld : flds ) fld._final = true; + + // Now start the recursion + for( int i=0; i 訳注：原文の「all !fields !attached」は、続く説明と図に合わせて、フィールドの型が未設定である状態として訳しています。 + +``` +struct List#12 { + ____ next#14, + ____ name#15 +} +``` + +最後にすべてのフィールド型で `_makeRO` を再帰呼び出しし、設定します。`TypeMemPtr` に `_fields[i]._t._makeRO()` を呼ぶと、再帰する `List` の `_makeRO()` を呼んだ後に、新しい TMP を作ります。 + +この再帰は `TypeStruct._makeRO()` へ戻り、同じ型名で `VISIT` 表にヒットします。最初のフィールド設定を巻き戻すと、次になります。 + +``` +struct List#12 { + List#12 *? #13 next#14, // Recursive next field makes a cycle + ____ name#15 +} +``` + +すべての型が新しい UID になっていることに注目してください。まだインターンできないので、以前の型にはできません。2番目のフィールド `str name` はすでに存在するため、次になります。 + +``` +struct List#12 { + List#12 *? #13 next#14, // Recursive next field makes a cycle + str#2 name#15 // Reuse the interned type str#2 +} +``` + +ここで再帰を巻き戻し、複雑な `Type.recurClose()` に入ります。いくつかの例でコードを1ステップずつ実行してみるとよいでしょう。`TypeTest.testList` がこれらの型を構築します。高水準での概要は次のとおりです。 + +管理を容易にするため、訪問したすべての型を `VISIT` からコピーします。すでにインターン済みのものを発見したら後続の処理から除去しますが、HashMap 内にない方が簡単です。 + +**走査 #1:** 循環に属さない既存のインターン済み部分を探し、置き換えます。新しい型循環から古いインターン済み型へポインタが出ているのに、そのコピーを作ってしまっている場合があります。この段階の後も新しい循環は残りますが、出力辺は可能なら以前の型を指します。置き換えた型は、遅延した `FREES` リストへ入ります。 + +**走査 #2:** すべての型は *双対* を事前計算して直接使えるようにしています。ここで再帰的な循環する双対を作ります。 + +**走査 #3:** 新しい型を登録します。新しくインターンされた型への共通ポインタをここで発見する *可能性がある* ので、進みながら再び検査・置換し、使わない型を再度遅延 `FREES` リストへ入れます。この段階はハッシュ表検索を必要とし、それには循環ハッシュと循環 equals が必要です。 + +**走査 #4:** 遅延解放するすべての型をここで解放し、将来の型生成で再利用します。 + +最終的に、新しい `List` の循環型は完全にインターンされます。読み書き可能版 `List#2` は同じ読み書き可能版 `List#2` を指し、読み取り専用版 `List#12` は同じ読み取り専用版 `List#12` を指します。 + +### 循環する HashCode と Equals + +循環する `hashCode` と `equals` はさらに説明が必要です。2つの循環を等価比較するとき、比較の開始位置に関係なく等価であってほしいのです。つまり循環 `A<->B` は循環 `B<->A` と等しいべきです。両方のハッシュコードは同じでなければならず、順序で変化するハッシュは使えません。 + +たとえば A の静的ハッシュ値が1で、さらに B のハッシュから再帰的な成分があり、逆に B の静的値が3で A からの再帰成分があるとします。`parent.hash*7 + child.hash` で計算すると、A からは `A.hash * 7 + B.hash`、つまり `1 * 7 + 3 == 10` です。後で B から始めると `B.hash * 7 + A.hash`、つまり `3 * 7 + 1 == 22` になります。ハッシュが異なるため、ハッシュ表が等価性を見逃す可能性があります。また循環で単純に再帰下降すれば、スタックオーバーフローまで再帰してクラッシュします。 + +`TypeStruct.hash()` が再帰しないようにして解決します。そのためハッシュ関数はやや弱く、フィールド名とエイリアスだけに依存します。 + +*循環 equals* は `VISIT` 表が空でないことにより発動し、`VISIT` と関心を分離するため、別の訪問表 `CEQUALS` を使います。循環 equals 検査は通常の `eq` と同様、構成部分を再帰下降し、最初に確定的な静的検査を行い、再帰前にはおなじみの **test-and-set** を使います。 + +同じ2型を再び循環 equals で比較したら、ほかがすべて等しい限り、循環についても等しいと仮定します。 + +## メソッド、final フィールド、クラス + +メソッドは、構造体内で宣言され、暗黙の `self` 引数を取る、単なる関数値（final フィールド）です。 + +元の構造体定義で宣言した final フィールドは *値* であり、変化できません。すべてのインスタンスで同じです。構造体のメモリ占有部分から、final フィールドの値の集まりである *クラス* へ移動します。クラスは単なる名前空間で具体的な実装を持たず、実体化されません。 + +```java +struct vecInt { + u32 !len; // Actual number of elements + int[] !buf; // Array of integers. + + // Since "add" is declared with `val` in the original struct definition, + // it is a final field and is moved out of here to the class. + + // Method: Internal: copy buf to a new size + val _grow = { int sz -> + var buf2 = new int[sz]; + for( int i=0; i + if( len >= buf# ) _grow(buf#*2); + buf[len++] = e; + return self; + }; + + +}; + +val primes = new vecInt{buf = new int[4];}.add(2).add(3).add(5).add(7).add(11); +``` + +ここで `val add` フィールドは、定数関数値である *値* フィールドです。基本的な `vecInt` オブジェクトから `vecInt` の *クラス* へ移り、オブジェクト内で記憶領域を占めません。`_grow` も同様です。そのため `vecInt` インスタンスのサイズは、`u32` の長さと配列ポインタに、配置調整のパディングを加えたものです。配列ヘッダと要素は別の割り当てを占めます。拡張後の古いバッファの回収は、この例の範囲外です。`return primes.len*100+primes.buf[4];` を追加すると、RISC-V と ARM の両方で511になります。 + +## RegAlloc の改良: 多数の使用のグループ化 + +第22章では色の優先度と安いスピルの順序を改善しました。この章では、使用が互換性のないレジスタを要求する、よく使う値を分割する方法を追加します。たとえば複数のシフトが同じカウントレジスタを必要とし、別の使用が異なるレジスタを必要とする場合です。互換グループごとに1コピーを共有すると、使用ごとに別のコピーを挿入するのを避けられます。 + +割り当て器は、空のレジスタマスクと、2つより多い固定レジスタ使用を持つ、単一定義の区間にこれを適用します。重なる使用マスクの共通部分を取り、グループ化します。グループを狭めても以前の使用と互換なので、1走査で十分です。交わらないマスクは別グループにします。入力を接続し直す前に異なる使用側のスナップショットを取り、スケジューリング専用辺は無視し、値が複数引数を供給しても呼び出しを1回だけ数えます。 + +複数の呼び出しで使う値は、レジスタ破壊が共有コピーの利点を打ち消しがちなので、グループ化しません。すべての使用のループ深さが同じ場合に既存コピーを分割することも含め、通常のループ境界分割を代替として保持します。低頻度側を先にするループ分割は第24章、面積／コストのスピル順位付けは第25章に残します。 + +第21章の隣接コピー転送も引き継ぎます。彩色後、次の命令に唯一の使用がある場合、オペランドマスクが許し、2アドレスの結び付きを壊さなければコピー元レジスタを読めます。以下の表は、この整理と遅延メモリの前方移植を含みます。第22章の群には、以前の監査後に追加した移動0の C 戻り値 ABI 確認2件も含むようになりました（24ではなく26項目）。 + +このディレクトリで `make spill-stats` を実行してください。以下の全行は **この章のコンパイラ**、シード123、各群の固定されたソース／対象の組み合わせを使います。Windows 実行は x86 SystemV/Win64 と RISC-V/ARM SystemV を合わせます。診断マシングラフは別に確認し、数には寄与しません。 + +| プログラム群 | コンパイル数 | 残存する移動 | ループ重み付き移動 | +|---|---:|---:|---:| +| 第20章 | 39 | 323 | 442 | +| 第21章 | 52 | 433 | 965 | +| 第22章 | 26 | 67 | 67 | +| 第23章 | 30 | 78 | 225 | +| **合計** | **147** | **901** | **1,699** | + +`_spills` はレジスタ移動を含む残存 SplitNode を数え、`_spillScaled` は `8^loopDepth` で重み付けします。生成移動のコンパイラによる推定であり、実行時メモリアクセスではありません。報告器は個々のコンパイルと CPU/ABI 合計を表示し、スピル期待値や実行確認が失敗すれば、依然として失敗を報告します。 + +以前の監査では、隣接コピー転送前にグループ化を無効にしても、**同じ933移動／1,745重み付き移動** でした。元のグループ化コードも同じ合計です。したがってこのスイートには、グループ化によるスピル改善は見られません。縮小したマシングラフの回帰テストは、旧実装の null マスクによるクラッシュも含め、互換性と呼び出しの規則を検証します。もっともらしい割り当て器のヒューリスティックであっても、効果を主張するには、それが実際に適用される処理対象での測定が必要です。 + +以前の群だけでは、第22章コンパイラは838移動／1,496重み付き移動で、このコンパイラは849／1,514でした。この比較は割り当て以外の変更を含みます。特に第20章の固定した String 入力は、ここでは最適化後も残り16重み付き移動を要しますが、第22章はこのシードで除去しました。その差をグループ化に帰するのは誤解を招きます。 + +元の64ビット `person21` とガード付き `stringHash21` 入力は、第21章の群を維持します。改訂した String 入力とこの章で有効にした2つのエンコーディングテストは第23章の群に属します。群を固定することで、言語とテストが成長しても、以後の比較に意味が保たれます。 diff --git a/chapter23/README.md b/chapter23/README.md index ee17f9f2..1f073c6b 100644 --- a/chapter23/README.md +++ b/chapter23/README.md @@ -1,5 +1,7 @@ # Chapter 23: Methods and Revisiting Types +English | [日本語](README.ja.md) + [Previous: Chapter 22](../chapter22/README.md) | [Next: Chapter 24](../chapter24/README.md) diff --git a/chapter23/docs/18-grammar.ja.md b/chapter23/docs/18-grammar.ja.md new file mode 100644 index 00000000..c2b37f67 --- /dev/null +++ b/chapter23/docs/18-grammar.ja.md @@ -0,0 +1,138 @@ +# 第23章の文法 + +[English](18-grammar.md) | 日本語 + +この文書は [原文](18-grammar.md) の日本語訳です。 + +> 訳注: 原文の見出しは「Grammar for Chapter 16」です。この日本語版では、配置されている第23章に合わせた見出しにしています。 + +[第23章に戻る](../README.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program : block EOF ; + +block : statement+ ; + + +statement + : '{' block '}' + | returnStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatement + | structDeclaration + | expressionStatement + ; + + +returnStatement : 'return' expression ';' ; + +ifStatement : 'if' '(' expression ')' statement ('else' statement)? ; + +whileStatement : 'while' '(' expression ')' statement ; + +breakStatement : 'break' ';' ; + +continueStatement : 'continue' ';' ; + + +structDeclaration : 'struct' IDENTIFIER '{' block '}' ; + +expressionStatement + : type IDENTIFIER ';' + | type IDENTIFIER '=' expression ';' + | IDENTIFIER '=' expression ';' + | expression + ; + +PRIMTYPE + : 'int' + | 'i8' + | 'i16' + | 'i32' + | 'i64' + | 'u8' + | 'u16' + | 'u32' + | 'flt' + | 'f32' + | 'f64' + | 'bool' + ; + +type + : PRIMTYPE + | typeName '?'? + | typeName nestedArray+ + ; + +nestedArray : '?'? '[]'* ; + +typeName : IDENTIFIER ; + + +expression : bitWiseExpression ; + +bitWiseExpression + : comparisonExpression ( '&' | '|' | '^' ) comparisonExpression)* + ; + +comparisonExpression + : shiftExpression (('==' | '!='| '>'| '<'| '>='| '<=') shiftExpression)* + ; + +shiftExpression + : additiveExpression ( '<<' | '>>>' | '>>' ) additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | '!' unaryExpression + | primaryExpression postAssign + ; + +primaryExpression + : INTEGER_LITERAL + | FLOAT_LITERAL + | '(' expression ')' + | 'true' + | 'false' + | 'null' + | newExpression + | IDENTIFIER + ; + +newExpression + : 'new' IDENTIFIER [ '{' block '}' ] + | 'new' IDENTIFIER '[' expression ']' + ; + +postAssign : postFix [ '=' expression ] | [ '#' ]; + +postFix + : '.' IDENTIFIER postFix + | '[' expression ']' postFix + ; + + +IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ; + +INTEGER_LITERAL + : [1-9]DIGIT* + | [0] + ; + +NON_DIGIT: [a-zA-Z_]; +DIGIT: [0-9]; +``` diff --git a/chapter23/docs/18-grammar.md b/chapter23/docs/18-grammar.md index 7da725e9..51539d0b 100644 --- a/chapter23/docs/18-grammar.md +++ b/chapter23/docs/18-grammar.md @@ -1,5 +1,7 @@ # Grammar for Chapter 16 +English | [日本語](18-grammar.ja.md) + ```antlrv4 grammar SimpleLanguage; -- cgit v1.2.3