From c54580d2b2685829dab0976ed8c2bcae59322f69 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Wed, 17 Jul 2024 18:11:56 +0100 Subject: Chapter 12: References MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Dibyendu Majumdar Co-authored-by: Thalia Archibald Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Robert Obkircher Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- docs/chapter12/12-grammar.ja.md | 136 ++++++++++++++++++++++++++++++++++++ docs/chapter12/12-grammar.md | 132 +++++++++++++++++++++++++++++++++++ docs/chapter12/Makefile | 12 ++++ docs/chapter12/README.ja.md | 101 +++++++++++++++++++++++++++ docs/chapter12/README.md | 150 ++++++++++++++++++++++++++++++++++++++++ 5 files changed, 531 insertions(+) create mode 100644 docs/chapter12/12-grammar.ja.md create mode 100644 docs/chapter12/12-grammar.md create mode 100644 docs/chapter12/Makefile create mode 100644 docs/chapter12/README.ja.md create mode 100644 docs/chapter12/README.md (limited to 'docs/chapter12') diff --git a/docs/chapter12/12-grammar.ja.md b/docs/chapter12/12-grammar.ja.md new file mode 100644 index 00000000..827e7478 --- /dev/null +++ b/docs/chapter12/12-grammar.ja.md @@ -0,0 +1,136 @@ +# 第12章の文法 + +[English](12-grammar.md) | 日本語 + +この文書は [原文](12-grammar.md) の日本語訳です。 + +[第12章に戻る](README.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | structDeclaration + | declStatement + | blockStatement + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatement + ; + +PRIMTYPE + : 'int' + ; + +field + : PRIMTYPE IDENTIFIER ';' + | structName ('?')? IDENTIFIER ';' + ; + +fields + : field+ + ; + +structDeclaration + : 'struct' IDENTIFIER '{' fields '}' + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + | fieldExpression '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +structName + : IDENTIFIER + ; + +declStatement + : PRIMTYPE IDENTIFIER '=' expression ';' + | structName ('?')? IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | '!' unaryExpression + | primaryExpression + ; + +newExpression + : 'new' IDENTIFIER + ; + +fieldExpression + : primaryExpression '.' IDENTIFIER + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | 'null' + | newExpression + | '(' expression ')' + | fieldExpression + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DEC_DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter12/12-grammar.md b/docs/chapter12/12-grammar.md new file mode 100644 index 00000000..41a7e24e --- /dev/null +++ b/docs/chapter12/12-grammar.md @@ -0,0 +1,132 @@ +# Grammar for Chapter 12 + +English | [日本語](12-grammar.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | structDeclaration + | declStatement + | blockStatement + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatement + ; + +PRIMTYPE + : 'int' + ; + +field + : PRIMTYPE IDENTIFIER ';' + | structName ('?')? IDENTIFIER ';' + ; + +fields + : field+ + ; + +structDeclaration + : 'struct' IDENTIFIER '{' fields '}' + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + | fieldExpression '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +structName + : IDENTIFIER + ; + +declStatement + : PRIMTYPE IDENTIFIER '=' expression ';' + | structName ('?')? IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | '!' unaryExpression + | primaryExpression + ; + +newExpression + : 'new' IDENTIFIER + ; + +fieldExpression + : primaryExpression '.' IDENTIFIER + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | 'null' + | newExpression + | '(' expression ')' + | fieldExpression + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DEC_DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter12/Makefile b/docs/chapter12/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter12/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/docs/chapter12/README.ja.md b/docs/chapter12/README.ja.md new file mode 100644 index 00000000..2b0f19dc --- /dev/null +++ b/docs/chapter12/README.ja.md @@ -0,0 +1,101 @@ +# 第12章: 参照 + +[English](README.md) | 日本語 + +[前: 第11章](../chapter11/README.ja.md) | +[次: 第13章](../chapter13/README.ja.md) + +この文書は [原文](README.md) の日本語訳です。 + +第10章と第11章では、構造体に整数フィールドを追加し、そのメモリへの作用を SSA で表しました。この章では、まだ定義が現れていない構造体も含め、フィールドにほかの構造体への参照を格納できるようにします。メモリグラフを変更せずに、連結リストや互いを参照するオブジェクトを扱えます。 + +線形の Git 履歴で[この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter12)を読むことや、[第11章との差分](https://github.com/SeaOfNodes/Simple/compare/linear-chapter11...linear-chapter12)を見ることもできます。 + +## 型付きフィールドと前方参照 + +```java +struct Person { + int age; + FamilyTree? tree; +} +struct FamilyTree { + Person? father; + Person? mother; +} +``` + +パーサーの `TYPES` テーブルは名前を型に対応付けます。初期状態では `int`（およびほかのプリミティブ型。後の章でさらに登場します）が入っています。`type()` が未知の名前を使う宣言を認識すると、`_fields == null` の、名前だけの `TypeStruct` を登録します。これは構造体名だけがわかっていて、ほかの情報はない構造体です。その構造体へのポインタがあれば、参照フィールドを記述するには十分で、`?` によってポインタが null であることを許容します。 + +`parseStruct()` は、すべてのフィールドを収集してから完全な構造体を `TYPES` に登録します。テーブルのエントリを置き換えるのであって、古い型を変更したり、フィールドリストの途中までを順次公開したりはしません。フィールドのエイリアスは、これまでと同じく宣言が完成した時点で割り当てます。 + +[パーサー](../../src/main/java/com/seaofnodes/simple/Parser.java)、特に `type()`、`parseField()`、`parseStruct()` と、[文法](12-grammar.ja.md)を参照してください。 + +## 再帰構造体: `L0` と `L1` + +```java +struct LLI { LLI? next; int i; } +``` + +コンパイラが実際に何を構築するかを覚えておくには、次の2つの記述が役立ちます。 + +```text +L0 = TypeStruct("LLI", fields = null) +L1 = TypeStruct("LLI", fields = { next: pointer-to-L0?, i: int }) +TYPES["LLI"] = L1 +``` + +`L0` は `LLI? next` フィールドをパースするときに作られます。閉じ波括弧の後で、名前テーブル内の `L0` を `L1` が置き換えます。`L1` 内の `next` フィールドは引き続き `L0` を指します。`L1` に戻るように書き換えません。 + +この設計は、**不変で浅い参照を、必要に応じて名前で解決する**ものです。実行時のオブジェクトはサイクルを形成しても、コンパイラの型記述は有限で非循環のままです。これは、**再帰的な型の展開を止める**意図的な決定です。すべての参照に完成した定義を再帰的に代入すると、無限に展開するか、循環する型のインターン化、等価性、ハッシュ、束の操作が必要になります（実際に、束を扱う章で登場します）。 + +[`TypeStruct`](../../src/main/java/com/seaofnodes/simple/type/TypeStruct.java) は、代わりに名前だけの記述で止めます。`dual()` と `glb()` はその記述をそのままにします。同じ構造体の完全な記述と名前だけの記述の meet は、名前だけの記述になります。これによってフィールドの詳細は失われますが、構造体の識別情報は失われません。`L0` をますます深い `L1`、`L2` などの列へと展開しようとするパスはありません。 + +## 浅い参照の解決 + +`head.next` のパース時、`parsePostfix()` はポインタの構造体名を取り出し、`TYPES` で現在の宣言を検索します。ポインタ自身の型にまだ `L0` が含まれていても、その宣言からフィールドの配置とエイリアスを得ます。`head.next.next.i` のような連鎖には、次のフィールドアクセスでも検索を繰り返せば十分です。 + +局所宣言や代入では、`parseExpressionStatement()` も、代入の互換性を確認する前に名前だけのポインタを解決します。この「深める」処理はチェックに使う一時的な型を変更するだけで、式ノードの型を書き換えたり、グラフ内の古い参照をすべて置き換えたりはしません。 + +```java +struct LLI { LLI? next; int i; } +LLI? head = null; +while (arg) { + LLI x = new LLI; + x.next = head; + x.i = arg; + head = x; + arg = arg - 1; +} +if (!head) return 0; +LLI? next = head.next; +if (next == null) return 1; +return next.i; +``` + +null チェックは、生き残る制御経路でポインタの型を絞り込みます。特に、明示的な `else` がなくても、`if` の false 経路はその絞り込みを記録しなければなりません。名前の解決はフィールドの定義を与えますが、ポインタが null でないことを証明するわけではありません。 + +## 初期化と不完全な定義 + +`newStruct()` は、各フィールドをその型の `makeInit()` で初期化します。整数はゼロ、参照は null です。Load と Store は第11章と同じエイリアスとメモリ最適化を使います。したがって、初期化 Store からの Load は null に畳み込めます。 + +使われない前方参照は、最後まで定義する必要がありません。 + +```java +struct Holder { Missing? ref; } +Holder h = new Holder; +return h.ref; // null; no definition of Missing is needed +``` + +ここでは、完全な定義なしに null でない `Missing` を構築する方法はありません。`new Missing` は拒否されます。そのフィールドにアクセスするにも、null でないポインタに加えて定義が必要です。null を許容する参照型に言及するだけでは、プログラムの終わりまでに定義する義務は生じません。 + +この章には、初期化に関する一時的な許容事項が1つあります。 + +```java +struct N { N next; int i; } +N n = new N; +return n.next; // null, despite the non-null field declaration +``` + +初期化 Store は、null を許容しない参照フィールドにも null を書き込めます。通常の `n.next = null` は拒否されます。第16章ではコンストラクタを追加して初期化をチェックします。この章では、この区別を [`StoreNode`](../../src/main/java/com/seaofnodes/simple/node/StoreNode.java) に明示的に保持します。 + +[参照のテスト](../../src/test/java/com/seaofnodes/simple/Chapter12Test.java)は、連結リスト、相互参照、null チェック、不完全な型を検証します。`make tests` で実行でき、`make view` は同じ未スケジュールのグラフを表示します。これで第13章には、ロード/ストアの反依存も含めた大域的コード移動の導入に必要な、メモリと参照の意味論がそろいました。 diff --git a/docs/chapter12/README.md b/docs/chapter12/README.md new file mode 100644 index 00000000..5087ee21 --- /dev/null +++ b/docs/chapter12/README.md @@ -0,0 +1,150 @@ +# Chapter 12: References + +English | [日本語](README.ja.md) + +[Previous: Chapter 11](../chapter11/README.md) | +[Next: Chapter 13](../chapter13/README.md) + +Chapters 10 and 11 gave structs integer fields and represented their memory +effects in SSA. This chapter lets fields contain references to other structs, +including structs whose definitions have not yet appeared. Linked lists and +mutually referring objects become possible without changing the memory graph. + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter12) +in the linear Git history and [compare it with Chapter 11](https://github.com/SeaOfNodes/Simple/compare/linear-chapter11...linear-chapter12). + +## Typed fields and forward references + +```java +struct Person { + int age; + FamilyTree? tree; +} +struct FamilyTree { + Person? father; + Person? mother; +} +``` + +The parser's `TYPES` table maps names to types. It initially contains `int` +(and any other primitive types, more are showing up in later chapters). When +`type()` recognizes a declaration using an unknown name, it installs a +name-only `TypeStruct`, with `_fields == null` - this a struct where we only +know the struct name, and no other information. A pointer to that struct is +enough to describe a reference field,`?` allows the pointer to be null. + +`parseStruct()` collects all fields before installing the complete struct in +`TYPES`. It replaces the table entry; it does not mutate the old type or +publish successive prefixes of the field list. Field aliases are allocated +with the completed declaration, as before. + +See [the parser](../../src/main/java/com/seaofnodes/simple/Parser.java), particularly +`type()`, `parseField()`, and `parseStruct()`, and the +[grammar](12-grammar.md). + +## Recursive structs: `L0` and `L1` + +```java +struct LLI { LLI? next; int i; } +``` + +Two descriptions are useful for remembering what the compiler actually builds: + +```text +L0 = TypeStruct("LLI", fields = null) +L1 = TypeStruct("LLI", fields = { next: pointer-to-L0?, i: int }) +TYPES["LLI"] = L1 +``` + +`L0` is created when parsing the `LLI? next` field. After the closing brace, +`L1` replaces it in the name table. The `next` field inside `L1` still points +to `L0`; it is not patched to point back to `L1`. + +The design is **immutable shallow references, resolved by name when needed**. +The runtime objects may form a cycle; their compiler type descriptions remain +finite and acyclic. This is an intentional decision to **stop recursive type +expansion**. Recursively substituting the completed definition into every +reference would either expand forever or require cyclic type interning, +equality, hashing, and lattice operations (which indeed show up in a lattice +chapter). + +[`TypeStruct`](../../src/main/java/com/seaofnodes/simple/type/TypeStruct.java) +instead stops at the name-only description. Its `dual()` and `glb()` leave that +description alone. Meeting a complete description with a name-only description +of the same struct yields the name-only description. That loses field detail +without losing the struct's identity. There is no pass trying to expand `L0` +into an ever deeper sequence of `L1`, `L2`, and so on. + +## Resolving a shallow reference + +When parsing `head.next`, `parsePostfix()` takes the pointer's struct name and +looks up the current declaration in `TYPES`. It gets the field layout and alias +from that declaration, even if the pointer's own type still contains `L0`. +Doing the lookup again for the next field access is sufficient for a chain +such as `head.next.next.i`. + +For a local declaration or assignment, `parseExpressionStatement()` also +resolves a name-only pointer before checking assignment compatibility. This +"deepening" changes the temporary type used for the check; it does not rewrite +the expression node's type or replace all old references in the graph. + +```java +struct LLI { LLI? next; int i; } +LLI? head = null; +while (arg) { + LLI x = new LLI; + x.next = head; + x.i = arg; + head = x; + arg = arg - 1; +} +if (!head) return 0; +LLI? next = head.next; +if (next == null) return 1; +return next.i; +``` + +The null checks refine the pointer on the surviving control path. In +particular, the false path of an `if` must record its refinement even when +there is no explicit `else`. Resolving a name supplies the field definition; +it does not prove that the pointer is non-null. + +## Initialization and incomplete definitions + +`newStruct()` initializes each field using its type's `makeInit()`: zero for +integers and null for references. Loads and Stores use the same aliases and +memory optimizations as Chapter 11. A Load from an initializing Store can +therefore fold to null. + +An unused forward reference need not ever be defined: + +```java +struct Holder { Missing? ref; } +Holder h = new Holder; +return h.ref; // null; no definition of Missing is needed +``` + +There is no way here to construct a non-null `Missing` without its complete +definition: `new Missing` is rejected. Accessing one of its fields also needs +a definition, as well as a non-null pointer. Simply mentioning a nullable +reference type does not impose a requirement to define it before the end of +the program. + +There is one temporary initialization allowance in this chapter: + +```java +struct N { N next; int i; } +N n = new N; +return n.next; // null, despite the non-null field declaration +``` + +The initializing Store may write null even into a non-null reference field. +An ordinary `n.next = null` is rejected. Chapter 16 adds constructors and +checks initialization; this chapter keeps the distinction explicit in +[`StoreNode`](../../src/main/java/com/seaofnodes/simple/node/StoreNode.java). + +The [reference tests](../../src/test/java/com/seaofnodes/simple/Chapter12Test.java) +exercise linked lists, mutual references, null checks, and incomplete types. +Run them with `make tests`; `make view` displays the same unscheduled graph. +Chapter 13 now has the memory and reference semantics it needs to introduce +global code motion, including load/store anti-dependencies. -- cgit v1.2.3