From d32f97238c903765dec4e9a9f3cbfa5fd12cded6 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 10 Aug 2026 11:11:18 -0700 Subject: Chapter 25: Modules, Separate Compilation, and SSA Construction Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- docs/chapter25/25-grammar.ja.md | 175 ++++++++ docs/chapter25/25-grammar.md | 175 ++++++++ docs/chapter25/Makefile | 12 + docs/chapter25/README.ja.md | 123 ++++++ docs/chapter25/README.md | 213 ++++++++++ docs/chapter25/ROADMAP.ja.md | 451 ++++++++++++++++++++ docs/chapter25/ROADMAP.md | 464 +++++++++++++++++++++ docs/chapter25/examples/A_helloWorld.smp | 2 + docs/chapter25/examples/BubbleSort.smp | 36 ++ docs/chapter25/examples/Capitalize.smp | 22 + docs/chapter25/examples/Dijkstra.smp | 72 ++++ docs/chapter25/examples/FileIO.smp | 50 +++ docs/chapter25/font-awesome-4.7.0.zip | Bin 0 -> 669808 bytes docs/chapter25/ifg_trim.pdf | Bin 0 -> 155190 bytes docs/chapter25/initialization.md | 481 +++++++++++++++++++++ docs/chapter25/lattice.gv | 203 +++++++++ docs/chapter25/lattice.svg | 691 +++++++++++++++++++++++++++++++ docs/chapter25/lattice2.gv | 85 ++++ docs/chapter25/lattice2.svg | 260 ++++++++++++ docs/chapter25/pardoe.docx | Bin 0 -> 22583 bytes docs/chapter25/webtcp.min.js | 65 +++ 21 files changed, 3580 insertions(+) create mode 100644 docs/chapter25/25-grammar.ja.md create mode 100644 docs/chapter25/25-grammar.md create mode 100644 docs/chapter25/Makefile create mode 100644 docs/chapter25/README.ja.md create mode 100644 docs/chapter25/README.md create mode 100644 docs/chapter25/ROADMAP.ja.md create mode 100644 docs/chapter25/ROADMAP.md create mode 100644 docs/chapter25/examples/A_helloWorld.smp create mode 100644 docs/chapter25/examples/BubbleSort.smp create mode 100644 docs/chapter25/examples/Capitalize.smp create mode 100644 docs/chapter25/examples/Dijkstra.smp create mode 100644 docs/chapter25/examples/FileIO.smp create mode 100644 docs/chapter25/font-awesome-4.7.0.zip create mode 100644 docs/chapter25/ifg_trim.pdf create mode 100644 docs/chapter25/initialization.md create mode 100644 docs/chapter25/lattice.gv create mode 100644 docs/chapter25/lattice.svg create mode 100644 docs/chapter25/lattice2.gv create mode 100644 docs/chapter25/lattice2.svg create mode 100644 docs/chapter25/pardoe.docx create mode 100644 docs/chapter25/webtcp.min.js (limited to 'docs/chapter25') diff --git a/docs/chapter25/25-grammar.ja.md b/docs/chapter25/25-grammar.ja.md new file mode 100644 index 00000000..9e9fb820 --- /dev/null +++ b/docs/chapter25/25-grammar.ja.md @@ -0,0 +1,175 @@ +# 第25章の文法 + +[English](25-grammar.md) | 日本語 + +```antlrv4 +grammar SimpleLanguage; + +// Name lookup, assignable operands, type compatibility, and access permissions +// are checked by the compiler in addition to these syntax rules. +// A file is a compilation unit; its path supplies its namespace. +// Qualified names resolve nested types and other units without an import keyword. +program : statement* EOF ; + +block : '{' statement* '}' ; + +statement + : block + | returnStatement + | ifStatement + | whileStatement + | forStatement + | breakStatement + | continueStatement + | structDeclaration + | declaration ';' + | assignment ';' + | ';' + ; + +returnStatement : 'return' assignment ';' ; +ifStatement : 'if' '(' assignment ')' statement ('else' statement)? ; +whileStatement : 'while' '(' assignment ')' statement ; +breakStatement : 'break' ';' ; +continueStatement : 'continue' ';' ; + +forStatement + : 'for' '(' (declaration | assignment)? ';' assignment? ';' assignment? ')' statement + ; + +structDeclaration : 'struct' IDENTIFIER '{' structMember* '}' ';' ; +structMember : constructorDeclaration | methodDeclaration | statement ; + +// The constructor name must match the enclosing struct's name. +constructorDeclaration : 'new' IDENTIFIER '=' functionExpression ';' ; + +// A method is an ordinary fixed function binding in a struct definition. +// The compiler supplies self; it is not written in parameterList. +// Function types and expressions both receive their implicit receiver here. +methodDeclaration : 'val' bindingModifier? IDENTIFIER '=' functionExpression ';' ; + +declaration : declarationType binding (',' binding)* ; +declarationType : type | 'var' | 'val' ; +binding : bindingModifier? IDENTIFIER ('=' initializer)? ; +bindingModifier : '!' | '~' ; +// A declaration initializer consisting of the string "C" declares an extern +// symbol: a function, or explicit numeric native storage. Ordinary strings +// elsewhere are array-valued expressions. +initializer : assignment ; + +// The prefix qualifies the named struct reference, not an enclosing array. +// Each [] / [~] suffix qualifies its own array layer. ? requires a reference. +type + : functionType + | primitiveType typeSuffix* + | accessModifier? typeName typeSuffix* + ; +accessModifier : '!' | '~' ; +typeSuffix : '?' | '[]' | '[~]' ; +typeName : IDENTIFIER ('.' IDENTIFIER)* ; + +primitiveType + : 'int' | 'i8' | 'i16' | 'i32' | 'i64' + | 'u1' | 'u8' | 'u16' | 'u32' | 'byte' | 'bool' + | 'flt' | 'f32' | 'f64' + ; + +assignment : expression (assignmentOperator assignment)? ; +assignmentOperator + : '=' | '+=' | '-=' | '*=' | '/=' | '&=' | '|=' | '^=' + | '<<=' | '>>=' | '>>>=' + ; + +expression : logicalExpression ('?' assignment (':' assignment)?)? ; + +// Both logical operators short-circuit and associate to the right here. +logicalExpression : bitwiseExpression (('&&' | '||') logicalExpression)? ; + +bitwiseExpression + : equalityExpression (('&' | '|' | '^') equalityExpression)* + ; + +equalityExpression : comparisonExpression (('==' | '!=') comparisonExpression)* ; + +// Chained comparisons test adjacent operands and short-circuit. A chain must +// keep its direction; equality has lower precedence and does not join a chain. +comparisonExpression + : shiftExpression + ( (('<' | '<=') shiftExpression)+ | (('>' | '>=') shiftExpression)+ )? + ; + +shiftExpression + : additiveExpression (('<<' | '>>' | '>>>') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-' | '!') unaryExpression + | updateOperator IDENTIFIER + | postfixExpression + ; + +// Prefix updates require a local name; postfix updates also allow fields +// and array elements. All updates require an assignable operand. +updateOperator : '++' | '--' ; +postfixExpression : primaryExpression postfixSuffix* updateOperator? ; +postfixSuffix : '.' IDENTIFIER | '[' assignment ']' | '#' | callSuffix | methodCallSuffix ; + +// For a fixed function-valued member, object.name(args) passes object as self. +// This overlaps ordinary field selection followed by a call syntactically; +// name/type resolution determines which call form applies. +methodCallSuffix : '.' IDENTIFIER callSuffix ; + +primaryExpression + : INTEGER_LITERAL + | FLOAT_LITERAL + | STRING_LITERAL + | CHARACTER_LITERAL + | 'true' + | 'false' + | 'null' + | IDENTIFIER + | '(' assignment ')' + | newExpression + | functionExpression + ; + +// A function is an expression bound with an ordinary declaration. +// Its last statement supplies the implicit result; return can exit earlier. +functionExpression : '{' parameterList? '->' statement* '}' ; +parameterList : (parameter ','?)+ ; +parameter : type bindingModifier? IDENTIFIER ; + +// Function types have unnamed, space-separated argument types. +// {int} is the zero-argument type; its function expression still uses ->. +functionType + : '{' type+ '->' type '}' '?'? + | '{' type '}' '?'? + ; + +callSuffix : '(' argumentList? ')' ; +argumentList : assignment (',' assignment)* ','? ; + +// Allocation invokes the declared constructor; inline initializer blocks from +// earlier chapters are replaced by constructor arguments. +newExpression : 'new' type ('[' assignment ']' | callSuffix)? ; + +INTEGER_LITERAL : '0' | [1-9] DIGIT* ; +FLOAT_LITERAL : DIGIT+ ('.' DIGIT* ('e' DIGIT+)? | 'e' '-'? DIGIT+) ; +STRING_LITERAL : '"' (ESCAPE | ~["\\])* '"' ; +CHARACTER_LITERAL : '\'' (ESCAPE | ~['\\]) '\'' ; +fragment ESCAPE : '\\' [0ntr\\'"] ; +IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ; +fragment NON_DIGIT : [a-zA-Z_] ; +fragment DIGIT : [0-9] ; +WHITESPACE : [ \t\r\n]+ -> skip ; +LINE_COMMENT : '//' ~[\r\n]* -> skip ; +BLOCK_COMMENT : '/*' .*? '*/' -> skip ; +``` diff --git a/docs/chapter25/25-grammar.md b/docs/chapter25/25-grammar.md new file mode 100644 index 00000000..065cf051 --- /dev/null +++ b/docs/chapter25/25-grammar.md @@ -0,0 +1,175 @@ +# Grammar for Chapter 25 + +English | [日本語](25-grammar.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +// Name lookup, assignable operands, type compatibility, and access permissions +// are checked by the compiler in addition to these syntax rules. +// A file is a compilation unit; its path supplies its namespace. +// Qualified names resolve nested types and other units without an import keyword. +program : statement* EOF ; + +block : '{' statement* '}' ; + +statement + : block + | returnStatement + | ifStatement + | whileStatement + | forStatement + | breakStatement + | continueStatement + | structDeclaration + | declaration ';' + | assignment ';' + | ';' + ; + +returnStatement : 'return' assignment ';' ; +ifStatement : 'if' '(' assignment ')' statement ('else' statement)? ; +whileStatement : 'while' '(' assignment ')' statement ; +breakStatement : 'break' ';' ; +continueStatement : 'continue' ';' ; + +forStatement + : 'for' '(' (declaration | assignment)? ';' assignment? ';' assignment? ')' statement + ; + +structDeclaration : 'struct' IDENTIFIER '{' structMember* '}' ';' ; +structMember : constructorDeclaration | methodDeclaration | statement ; + +// The constructor name must match the enclosing struct's name. +constructorDeclaration : 'new' IDENTIFIER '=' functionExpression ';' ; + +// A method is an ordinary fixed function binding in a struct definition. +// The compiler supplies self; it is not written in parameterList. +// Function types and expressions both receive their implicit receiver here. +methodDeclaration : 'val' bindingModifier? IDENTIFIER '=' functionExpression ';' ; + +declaration : declarationType binding (',' binding)* ; +declarationType : type | 'var' | 'val' ; +binding : bindingModifier? IDENTIFIER ('=' initializer)? ; +bindingModifier : '!' | '~' ; +// A declaration initializer consisting of the string "C" declares an extern +// symbol: a function, or explicit numeric native storage. Ordinary strings +// elsewhere are array-valued expressions. +initializer : assignment ; + +// The prefix qualifies the named struct reference, not an enclosing array. +// Each [] / [~] suffix qualifies its own array layer. ? requires a reference. +type + : functionType + | primitiveType typeSuffix* + | accessModifier? typeName typeSuffix* + ; +accessModifier : '!' | '~' ; +typeSuffix : '?' | '[]' | '[~]' ; +typeName : IDENTIFIER ('.' IDENTIFIER)* ; + +primitiveType + : 'int' | 'i8' | 'i16' | 'i32' | 'i64' + | 'u1' | 'u8' | 'u16' | 'u32' | 'byte' | 'bool' + | 'flt' | 'f32' | 'f64' + ; + +assignment : expression (assignmentOperator assignment)? ; +assignmentOperator + : '=' | '+=' | '-=' | '*=' | '/=' | '&=' | '|=' | '^=' + | '<<=' | '>>=' | '>>>=' + ; + +expression : logicalExpression ('?' assignment (':' assignment)?)? ; + +// Both logical operators short-circuit and associate to the right here. +logicalExpression : bitwiseExpression (('&&' | '||') logicalExpression)? ; + +bitwiseExpression + : equalityExpression (('&' | '|' | '^') equalityExpression)* + ; + +equalityExpression : comparisonExpression (('==' | '!=') comparisonExpression)* ; + +// Chained comparisons test adjacent operands and short-circuit. A chain must +// keep its direction; equality has lower precedence and does not join a chain. +comparisonExpression + : shiftExpression + ( (('<' | '<=') shiftExpression)+ | (('>' | '>=') shiftExpression)+ )? + ; + +shiftExpression + : additiveExpression (('<<' | '>>' | '>>>') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-' | '!') unaryExpression + | updateOperator IDENTIFIER + | postfixExpression + ; + +// Prefix updates require a local name; postfix updates also allow fields +// and array elements. All updates require an assignable operand. +updateOperator : '++' | '--' ; +postfixExpression : primaryExpression postfixSuffix* updateOperator? ; +postfixSuffix : '.' IDENTIFIER | '[' assignment ']' | '#' | callSuffix | methodCallSuffix ; + +// For a fixed function-valued member, object.name(args) passes object as self. +// This overlaps ordinary field selection followed by a call syntactically; +// name/type resolution determines which call form applies. +methodCallSuffix : '.' IDENTIFIER callSuffix ; + +primaryExpression + : INTEGER_LITERAL + | FLOAT_LITERAL + | STRING_LITERAL + | CHARACTER_LITERAL + | 'true' + | 'false' + | 'null' + | IDENTIFIER + | '(' assignment ')' + | newExpression + | functionExpression + ; + +// A function is an expression bound with an ordinary declaration. +// Its last statement supplies the implicit result; return can exit earlier. +functionExpression : '{' parameterList? '->' statement* '}' ; +parameterList : (parameter ','?)+ ; +parameter : type bindingModifier? IDENTIFIER ; + +// Function types have unnamed, space-separated argument types. +// {int} is the zero-argument type; its function expression still uses ->. +functionType + : '{' type+ '->' type '}' '?'? + | '{' type '}' '?'? + ; + +callSuffix : '(' argumentList? ')' ; +argumentList : assignment (',' assignment)* ','? ; + +// Allocation invokes the declared constructor; inline initializer blocks from +// earlier chapters are replaced by constructor arguments. +newExpression : 'new' type ('[' assignment ']' | callSuffix)? ; + +INTEGER_LITERAL : '0' | [1-9] DIGIT* ; +FLOAT_LITERAL : DIGIT+ ('.' DIGIT* ('e' DIGIT+)? | 'e' '-'? DIGIT+) ; +STRING_LITERAL : '"' (ESCAPE | ~["\\])* '"' ; +CHARACTER_LITERAL : '\'' (ESCAPE | ~['\\]) '\'' ; +fragment ESCAPE : '\\' [0ntr\\'"] ; +IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ; +fragment NON_DIGIT : [a-zA-Z_] ; +fragment DIGIT : [0-9] ; +WHITESPACE : [ \t\r\n]+ -> skip ; +LINE_COMMENT : '//' ~[\r\n]* -> skip ; +BLOCK_COMMENT : '/*' .*? '*/' -> skip ; +``` diff --git a/docs/chapter25/Makefile b/docs/chapter25/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter25/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/chapter25/README.ja.md b/docs/chapter25/README.ja.md new file mode 100644 index 00000000..427fc1c7 --- /dev/null +++ b/docs/chapter25/README.ja.md @@ -0,0 +1,123 @@ +# 第25章: モジュール、分割コンパイル、SSA 構築 + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第24章](../chapter24/README.ja.md) | +[章の一覧](../../README.ja.md#各章) + +この章では Simple のソースファイルを再利用可能なオブジェクトファイルへコンパイルし、その型と理想 IR を後のコンパイルに読み込み、別に構築したシステムライブラリとネイティブプログラムをリンクします。また、不完全な情報を扱うため、パーサー、型、メモリ SSA を大幅に再設計します。 + +これらが現在のスナップショットの内容です。独立した正しさの修正を先に以前の章へ移します。大きな SSA 再設計を以前へ移すことや、この章の分割は延期します。[バックポート待ち一覧](../chapter-backports.md) を参照してください。 + +第21〜24章のメモリ処理はここにも引き継ぎます。Load 検索は読み取りをループ外へ移す前にマージの全枝を証明し、Phi の因数分解はメモリ破壊を確認し、スケジューリングはメモリ集合体を通じてエイリアスをたどります。検索は `EscapeNode` から非公開または公開メモリへ進み、未解決の Store エイリアスを待ちます。配列長の読み取りには要素の境界検査がなく、配列要素の読み取りは制御を保持します。整数値の Phi は、既存の型付き変換機構で、ループの拡大を通じてもロード幅を保持します。New は引き続き非公開のコンストラクタメモリを生成し、公開は Escape が扱います。以前の章の割り当て入力設計は、これを置き換えません。 + +[直線的な履歴](https://github.com/SeaOfNodes/Simple/tree/linear) で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter25) を読み、[第24章と比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter24...linear-chapter25) することもできます。 + +この章の[完全な言語文法](25-grammar.ja.md)はこちらです。 + +## コンパイル単位と名前 + +`CompUnit` はソースまたはオブジェクトファイルを表します。`ParseAll` は依存関係を発見し、必要なソースを解析し、以前コンパイルした単位を読み込みます。ソースツリーとビルドツリーは対応する相対パスを使い、クラス名はドット区切りのパスを使います。たとえば `a/b/foo.smp` は名前空間 `a.b.foo` を供給します。 + +各単位は Start/Stop ノードを持ちます。関数がコンパイル単位に所有されることと、未知の外部呼び出し側を表す辺とは別です。出力のためにコードを保持することが、任意の呼び出し側から到達できることを意味してはいけません。 + +ドライバは、プロジェクトルートの `--root`、出力の `-o`、外部 Simple オブジェクト検索パスの `-L` を受け付けます。検索パスにはオブジェクトファイルやディレクトリを指定できます。コンパイラはネイティブリンク用の外部 C シンボルも解決します。`_` で始まる名前は非公開性を制御し、公開到達性は外側の名前にも依存します。 + +明示的な数値型の C 宣言は、可変のネイティブ記憶領域へ直接束縛します。 + +```java +i32 counter = "C"; +counter += 1; +return counter; +``` + +ネイティブリンカが `counter` を解決します。読み書きはその C 変数にアクセスし、宣言はコピーも初期化もしません。繰り返した宣言とモジュールインポートは同じ記憶領域エイリアスを共有します。整数と浮動小数点データの束縛をサポートし、ポインタと集合体のデータ束縛はまだサポートしません。外部フィールドは記憶領域フラグを持ち、宣言元クラス内でバイトを占めません。配置はフィールドオフセットを `ExternOffset` シンボルへ解決し、命令選択はクラス先頭＋オフセットをネイティブシンボルアドレスへ置き換えます。ネイティブオブジェクト出力は既存の AMD64 ELF ライタを使い、ARM と RISC-V はメモリ内リンカを通じてこれらのアドレスをサポートします。スレッドローカル変数と C マクロにはアクセサ関数が必要です。システムライブラリは小さなネイティブランタイムアクセサを通じ、`libc.errno()` を公開します。 + +## オブジェクトファイルは理想 IR を含む + +ELF ライタは、ネイティブコードと、正規化された型、理想グラフノード、依存関係を含む `.simple` セクションを保存します。リーダはそのグラフを再構築し、インポートした関数をインライン化などの最適化に参加させます。インライン化せず残った呼び出しは、ネイティブリンクで解決します。 + +`GlobalBits` はファイルの同一性とファイルごとのインデックスを、エイリアス、関数対象、戻り位置の局所的な密なインデックスへ対応付けます。独立したコンパイルの等しい局所番号を、等しい同一性と取り違えてはいけません。読み込み後に型を閉じて更新し、単位をまたぐ循環参照も扱います。 + +シリアライズは、宣言型を精密化されたフロー型とは別に保持します。意味を持つすべてのノード／型のフィールドには、対応する読み書きサポートが必要です。ソースにある高コストなシリアライズの全単射検査は現在無効で、より大きな増分再ビルドテスト `testModule0` は無視されています。どちらも有効な検証保証ではありません。 + +外部フィールドのフラグと記号的オフセットは、シリアライズされた配置を変更します。マジックは `C0DE` のままで、独立した形式バージョンはまだありません。このコンパイラへインポートする前に、すべての Simple オブジェクトファイルを再ビルドしてください。 + +## 型が完成する前の SSA 構築 + +Simple は引き続き AST を介さず直接 SSA に解析します。前方参照により、解析時点では式の最終的な型が利用できない場合があります。そのため構文と解決済みの字句的束縛でトポロジーを選び、後から型でグラフを精密化、最適化、検証します。 + +- 算術ノードは整数モードか浮動小数点モードかの選択を延期し、SCCP 後の再帰的グラフ成分を通じた解決も扱います。 +- Call は呼び出し先の種類が決まる前に、構文上のレシーバスロットを保持します。記号的なフィールド情報は配置依存の判断を延期します。 +- Load と通常の Phi は、パーサーが供給した下限型を持たなくなります。 +- `TypeScalar` は整数、浮動小数点、メモリポインタ、関数ポインタ値を、大域的な制御／メモリのボトムと区別して表します。 +- `TypeStruct._open` は不完全なフィールド集合を記述し、`_fref` は権威ある定義の欠如を記録します。フィールドを発見したことは、型を定義したことではありません。 +- ガードは入力の種類がわかる前に、分岐が証明したゼロ／非ゼロの事実を運びます。`FunPtrNode` は関数の戻りグラフへの明示的な辺を保持します。 + +ドライバはシリアライズとマシン選択の前に、解析、悲観的反復、SCCP、最終型検査を行います。単純でないインライン化は、常に即時のピープホール最適化として行うのではなく、反復と調整します。 + +## メモリと構築 + +パーサーは通常のバルクメモリを保持します。最適化器は `MemMerge`、`MemPhi`、`BulkMemPhi` で正確なエイリアスを復元します。バルク Phi は、並列の正確な Phi で表す除外分以外のすべてのエイリアスを覆います。各スライスはちょうど1回だけ覆われなければなりません。 + +ユーザーコンストラクタは次のように宣言し、呼び出します。 + +```java +struct Box { + i64[] values; + new Box = { i64[] initial -> values = initial; }; +}; +return new Box(new i64[1]); +``` + +宣言で割り当て補助関数を生成します。これは割り当てを行い、隠れた `` とユーザーコンストラクタを順に呼び、`EscapeNode` を通じて初期化済みの非公開メモリを公開します。パーサーの `Var` メタデータは、早すぎるフィールド読み取りやコンストラクタ出口での未初期化を検出します。Store の幅は保存する値ではなく、対象の宣言から得ます。 + +ファイルレベルのコードは、インスタンス初期化とは異なるクラス初期化子（``）で表します。[遅延初期化の設計（英語）](initialization.md) は、一度だけ実行するためのチェック、モジュール間の非循環な依存関係、シリアライズの対応を提案しています。現在の実装すべてを記述する仕様ではありません。[ロードマップ](ROADMAP.ja.md) にも追加の提案があります。 + +## システムライブラリと例 + +以前の単一の `sys.smp` ライブラリは、libc 束縛、I/O、文字、スキャナ、配列、伸長可能なバッファ、ビット集合の単位に整理されました。ネイティブドライバは実際のプログラム引数をサポートします。`examples` の例には Bubble Sort、Capitalize、Dijkstra、FileIO があります。 + +`Chapter25Test` は、意図的にインライン化せず残す Hello World 呼び出しを含め、ライブラリ読み込みとネイティブリンクを検証します。そのテストは `sys.o` とリンクする前に、クライアントの外部シンボルを確認します。ほかのテストは前方コンストラクタ、呼び出し経由のフィールド更新、リテラルのエスケープ、縮小したコンパイラ失敗を検証します。独立した回帰テストは以前の章へ移す候補です。 + +## ビルドと確認 + +このディレクトリで `make lib` は Java テスト依存関係を用意し、`make tests` は章の生のスイート、独立スイート、システムテスト、ファザー回帰テストを実行します。`make release` はコンパイラ jar とネイティブライブラリ成果物を構築し、`make tags` はエディタ用タグを構築します。ネイティブツールと選択した CPU/ABI は環境と一致する必要があります。Makefile は現在、既定で x86-64/win64 を使います。 + +シリアライズ IR は `C0DE` ヘッダを使います。ポインタ型は独立した読み取り専用アクセスビットを含みます。形式にはまだバージョン番号がないため、形式を変更したらオブジェクトファイルを再ビルドしてください。現在、後方互換性は保証していません。 + +コンパイラ変更は `sys.o` のシリアライズ IR とネイティブコードの両方を無効にする場合があります。リンクしたプログラムのテスト結果を解釈する前に再ビルドしてください。ソースだけの部分集合は、この章の完全な `make tests` と同等ではありません。 + +## RegAlloc の改良: 生存区間の面積と分割コスト + +第24章はループ Phi の高頻度辺を分割する前に、低頻度のコピーを試しました。この章ではさらに、スピルがスケジュール済みコードのどれだけをレジスタ圧力から解放するかを推定し、新しいコピーの推定コストで割ります。callee-save 区間は関数全体を覆います。複製可能な定数は使用の近くで再構築できます。ループ内のコピーは高コストなので、`8^loopDepth` で重み付けします。特に多数の使用を持つ値については、低コストな近似です。 + +複数の固定レジスタ使用を直接分割する規則や、一部の複数定義区間をより深く分割する規則など、第25章のほかの衝突処理はここに残します。サイズのしきい値はヒューリスティックであり、最初の割り当て器へバックポートすべき一般的不変条件ではありません。共有される合法性修正は、引き続き最も早い該当章から始めます。最終監査は第20〜25章の固定隣接ノードの色バイアス、第20〜21章の狭いストアマスク、第21〜25章の ARM レジスタバンク／浮動小数点メモリエンコーディングを修正しました。 + +第21章の隣接コピー転送も引き継ぎます。次の命令だけで使うコピーは、オペランドがコピー元レジスタを受け入れ、命令の結果に結び付けられていなければ除去します。 + +以下は、必須の `cs` フィールドに明示的なコンストラクタを与えて保存済み String ソース3件を修正した後の、完全な2026-10-02再実行です。過去の212項目すべてが成功します。これはフィクスチャ調整と最近のコンパイラ修正後の新たな基準値を確立します。以前の監査との割り当て器だけの比較ではありません。[バックポート記録](../chapter-backports.md) に古い部分比較を残しています。 + +`make spill-stats` を実行してください。各行は **第25章のコンパイラ** を使います。最初の5行は以前の212のプログラム／対象項目を、この章の構文とライブラリ構成に適応して保持しています。[フィクスチャノート](../../src/test/java/com/seaofnodes/simple/spill/README.ja.md) にその調整と測定の制限を記載しています。最適化器のシードは123です。最後の行には、既存シードで記録した `Chapter25Test` の13割り当てと、ドライバのシード456での新規システムライブラリコンパイルを含みます。`sys.o` を再利用して、この大きな処理対象を測定から消してはいけません。この結果は Windows x86-64 のものです。以前の群には RISC-V/ARM SystemV と x86 SystemV も含みます。報告器は対象ごとの合計も表示します。 + +| プログラム群 | コンパイル数 | 分割／移動数 | ループ重み付き数 | +|---|---:|---:|---:| +| 第20章 | 39 | 375 | 606 | +| 第21章 | 52 | 479 | 1,172 | +| 第22章 | 24 | 103 | 103 | +| 第23章 | 30 | 129 | 353 | +| 第24章 | 67 | 696 | 1,410 | +| 第25章 | 14 | 786 | 1,815 | +| **合計** | **226** | **2,568** | **5,459** | + +`_spills` はレジスタ間移動を含む残存 SplitNode を数え、`_spillScaled` はループ重みを適用します。どちらもメモリアクセスだけを測るものではありません。古い群はレジスタ合法性確認を伴う割り当ての再実行で、ネイティブハーネスの再実行ではありません。`Chapter25Test` の23テストすべてが、ネイティブ／結果確認を含め、スピル期待値の失敗なしに成功します。継承したエミュレータテストを含む章全体には `make -j 4 tests` を使ってください。 + +### 測定についてのコメント + +以前の割り当て器監査では、一様な改善は見つかりませんでした。そのコンパイラのほかの部分を変えず、第24章の順位付けに置き換えると、221のクライアントコンパイルで5移動減りました（2,211／4,724に対し2,206／4,719）。しかしシステムライブラリを8ラウンド以内に割り当てられませんでした。したがって不完全な比較であり、有効なスイート全体の低い合計ではありません。既存の面積／コスト順位付けを保持し、ラウンド上限と正しさの確認も変えません。その監査でシステムライブラリ自体は386移動／855重み付き移動で、現在の再実行は373／828です。 + +複数使用を持つすべての複製可能定数を優先する試行は、それらのクライアントで以前の順位付けより1移動減りましたが、やはり新規ライブラリビルドに失敗し、却下されました。これが、集計統計と完全なコンパイル・実行確認の両方が重要な理由です。有利な小計だけでは変更を正当化できません。 + +その以前の監査では、過去の群の合計が第24章の1,332／2,956から、第25章の1,814／3,753へ増えました。第25章はクラス初期化子、モジュール所有権、異なる脱出解析、構文／ライブラリの調整を追加します。これらは異なるマシングラフなので、増加を割り当て器の品質だけに帰することはできません。章の表から結論を出す前に、1つのコンパイラと固定した入力集合でヒューリスティックを比較してください。 diff --git a/docs/chapter25/README.md b/docs/chapter25/README.md new file mode 100644 index 00000000..54f1a397 --- /dev/null +++ b/docs/chapter25/README.md @@ -0,0 +1,213 @@ +# Chapter 25: Modules, Separate Compilation, and SSA Construction + +English | [日本語](README.ja.md) + +[Previous: Chapter 24](../chapter24/README.md) | +[Chapter index](../../README.md#chapters) + +This chapter compiles Simple source files into reusable object files, loads +their types and ideal IR into later compilations, and links native programs +against a separately built system library. It also contains a substantial +parser, type, and memory-SSA redesign to support incomplete information. + +These are the contents of the current snapshot. Independent correctness fixes +will move to earlier chapters first; moving the larger SSA redesign backward, +or splitting this chapter, is deferred. See the [backport queue](../chapter-backports.md). + +The memory work from Chapters 21-24 carries forward here: Load search proves +all arms of a merge before moving a read out of a loop, Phi factoring checks +memory clobbers, and scheduling follows aliases through memory aggregates. +The search follows `EscapeNode` to private or public memory and waits for +unresolved Store aliases. Array-length reads have no element bounds check; +array-element reads retain control. Integer value Phis use the existing typed +conversion machinery to preserve the load's width across loop widening. +New still produces private constructor memory, with publication handled by +Escape; the earlier chapters' allocation-input design does not replace it. + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter25) +in the [linear history](https://github.com/SeaOfNodes/Simple/tree/linear) and +[compare it with Chapter 24](https://github.com/SeaOfNodes/Simple/compare/linear-chapter24...linear-chapter25). + +Here is the [complete language grammar](25-grammar.md) for this chapter. + +## Compilation units and names + +`CompUnit` represents a source or object file. `ParseAll` discovers dependencies, +parses needed sources, and loads previously compiled units. Source and build +trees use corresponding relative paths; class names use dotted paths. For +example, `a/b/foo.smp` supplies the namespace `a.b.foo`. + +Each unit has Start/Stop nodes. A function's ownership by a compilation unit is +distinct from an edge representing unknown external callers: retaining code +for emission must not imply that arbitrary callers can reach it. + +The driver accepts `--root` for the project root, `-o` for output, and `-L` for +external Simple object search paths, including an object file or a directory. +The compiler also resolves external C symbols for native linking. Names beginning +with `_` control privacy; public reachability depends on enclosing names too. + +Explicit numeric C declarations bind directly to mutable native storage: + +```java +i32 counter = "C"; +counter += 1; +return counter; +``` + +The native linker resolves `counter`. Reads and writes access that C variable; +the declaration neither copies nor initializes it. Repeated declarations and +module imports share the same storage alias. Integer and floating-point data +bindings are supported; pointer and aggregate data bindings are not yet supported. +External fields carry a storage flag and occupy no bytes in their declaring +class. Layout resolves their field offsets to `ExternOffset` symbols; instruction +selection replaces class-base-plus-offset with the native symbol address. +Native object output uses the existing AMD64 ELF writer; ARM and RISC-V support +these addresses through the in-memory linker. Thread-local variables and C macros +need accessor functions: the system library exposes `libc.errno()` through a small +native runtime accessor. + +## Object files contain ideal IR + +The ELF writer stores native code and a `.simple` section containing canonical +types, ideal graph nodes, and dependencies. The reader reconstructs that graph +so imported functions can participate in optimization, including inlining. +Calls that remain out of line are resolved by native linking. + +`GlobalBits` maps file identities and per-file indices to local dense indices +for aliases, function targets, and return points. Equal local numbers from +independent compilations must not be mistaken for equal identities. Types are +closed and upgraded after loading, including cross-unit cyclic references. + +Serialization preserves declaration types separately from sharpened flow types. +Every semantic node/type field needs matching read/write support. The source's +expensive serialization bijection check is currently disabled, and the larger +incremental-rebuild test `testModule0` is ignored. Neither is an active +validation guarantee. + +The external-field flag and symbolic offsets change the serialized layout. +The magic remains `C0DE`; there is no separate format version yet. Rebuild all +Simple object files before importing them with this compiler. + +## Constructing SSA before types are complete + +Simple still parses directly to SSA without an AST. Forward references mean an +expression's eventual type may be unavailable while parsing it. Syntax and +resolved lexical binding therefore choose topology; types subsequently refine, +optimize, and validate the graph. + +- Arithmetic nodes defer integer versus floating-point mode selection, including + resolution through recursive graph components after SCCP. +- Calls preserve their syntactic receiver slot before the callee kind is settled. + Symbolic field information defers layout-dependent decisions. +- Loads and ordinary Phis no longer carry parser-supplied lower-bound types. +- `TypeScalar` represents integer, float, memory-pointer, and function-pointer + values separately from global control/memory bottom. +- `TypeStruct._open` describes an incomplete field set; `_fref` records the + absence of an authoritative definition. Discovering fields does not define a type. +- Guards carry branch-proven zero/nonzero facts before the input family is known. + `FunPtrNode` retains an explicit edge to its function's return graph. + +The driver runs parsing, pessimistic iteration, SCCP, and final type checking +before serialization and machine selection. Nontrivial inlining is coordinated +with iteration instead of always occurring as an immediate peephole. + +## Memory and construction + +The parser carries ordinary bulk memory. The optimizer recovers precise aliases +using `MemMerge`, `MemPhi`, and `BulkMemPhi`. A bulk Phi covers all aliases +except its exclusions, represented by parallel precise Phis. Every slice must +be covered exactly once. + +User constructors are declared and called as follows: + +```java +struct Box { + i64[] values; + new Box = { i64[] initial -> values = initial; }; +}; +return new Box(new i64[1]); +``` + +An allocation helper is generated at the declaration. It allocates, calls the +hidden `` and then the user constructor, and publishes initialized private +memory through `EscapeNode`s. Parser `Var` metadata detects early field reads +and missing initialization on constructor exits. Store widths come from target +declarations, not from the values being stored. + +File-level code is represented by a class initializer (``), distinct +from instance initialization. The [lazy initialization design](initialization.md) +specifies proposed run-once checks, acyclic dependencies across modules, and +serialization support. It describes planned work, not all currently implemented +behavior. The [roadmap](ROADMAP.md) contains additional proposals. + +## System library and examples + +The former single `sys.smp` library is organized into units for libc bindings, +I/O, characters, scanners, arrays, growable buffers, and bitsets. The native +driver supports real program arguments. Examples in `examples` include +Bubble Sort, Capitalize, Dijkstra, and FileIO. + +`Chapter25Test` exercises library loading and native linking, including a Hello +World call deliberately kept out of line. That test checks the client's external +symbol before linking against `sys.o`. Other tests cover forward constructors, +field updates through calls, literal escapes, and reduced compiler failures. +Independent regressions are candidates for earlier chapters. + +## Building and checking + +From this directory, `make lib` supplies Java test dependencies and `make tests` +runs the raw chapter suites, standalone suites, system tests, and fuzzer +regressions. `make release` builds the compiler jar and native library artifacts; +`make tags` builds editor tags. Native tools and the selected CPU/ABI must match +the environment; the Makefile currently defaults to x86-64/win64. + +Serialized IR uses the `C0DE` header; pointer types include an independent +read-only access bit. The format is not versioned yet, so rebuild object files +after format changes. Backward compatibility is not currently supported. + +Compiler changes can invalidate both serialized IR and native code in `sys.o`. +Rebuild it before interpreting linked-program test results. A source-only subset +is not equivalent to this chapter's full `make tests`. + +## RegAlloc improvements: live-range area and split cost + +Chapter 24 tried cold copies before splitting a loop Phi's hot edges. This +chapter also estimates how much scheduled code a spill frees from register +pressure, divided by the estimated cost of the new copies. Callee-save ranges +cover a whole function. Cloneable constants can be rebuilt nearer their uses. +Copies inside loops cost more: the estimate weights them by `8^loopDepth`. +These are inexpensive approximations, especially for values with many uses. + +A single-use function address in the same block gets priority for +rematerialization when it is separated from its use. Moving that address +calculation next to the use adds no instruction and avoids preserving a +callee-save register merely to hold the constant. Adjacent uses and multi-use +addresses retain the area/cost ranking. + +Rows are fixed test cohorts; columns are compiler chapters. Each cell gives +**Ops / RA / X**: executed ARM+RISC-V instructions, the subset emitted for +allocator copies/rematerializations, and x86's loop-weighted split-move estimate. +**Cases D / X** counts measured dynamic program/target cases and x86 compilations; +membership and inputs stay fixed across columns. Native-library work is excluded. +Chapter 20 has no encoder, hence no dynamic counts. Lower is better within each +metric; see the [measurement details](../regalloc-spills.md) for coverage. + + +| Test cohort | Cases D / X | Ch 20: Ops / RA / X | Ch 21: Ops / RA / X | Ch 22: Ops / RA / X | Ch 23: Ops / RA / X | Ch 24: Ops / RA / X | Ch 25: Ops / RA / X | +|---|---:|---:|---:|---:|---:|---:|---:| +| Ch 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | 58,751 / 9,099 / 175 | 58,736 / 9,084 / 184 | 58,720 / 9,068 / 183 | 58,965 / 9,076 / 208 | +| Ch 21 | 20 / 18 | | 6,207 / 261 / 461 | 6,324 / 379 / 475 | 6,326 / 381 / 475 | 6,325 / 380 / 470 | 6,196 / 219 / 534 | +| Ch 22 | 14 / 8 | | | 198 / 60 / 7 | 194 / 56 / 7 | 194 / 56 / 7 | 252 / 92 / 11 | +| Ch 23 | 14 / 8 | | | | 630 / 160 / 36 | 630 / 160 / 36 | 864 / 358 / 36 | +| Ch 24 | 36 / 20 | | | | | 4,923 / 1,341 / 790 | 4,646 / 1,335 / 609 | +| Ch 25 | 2 / 12 | | | | | | 20 / 0 / 1,856 | + + + +Chapter25 introduces several features, which when run on the older tests +generate a lot more code, which in turn generates more spills. + +Class initialization, inlining, escape analysis, and library adaptations +all change the graphs. To help with this, we adjust the inlining +heursitics to try and get all the boilerplate to inline and optimize. + diff --git a/docs/chapter25/ROADMAP.ja.md b/docs/chapter25/ROADMAP.ja.md new file mode 100644 index 00000000..222f228a --- /dev/null +++ b/docs/chapter25/ROADMAP.ja.md @@ -0,0 +1,451 @@ +# ロードマップ + +[English](ROADMAP.md) | 日本語 + +この文書は [ROADMAP.md](ROADMAP.md) の日本語訳です。原文の設計案と未解決の問いを、そのまま設計案として記しています。 + +## 分割コンパイル + +未知の前方参照をどう扱うか？ H-M は使わないので、単一化も行わない。 +関数以外の前方参照を認めないことにする……関数なら、定義した時点ですぐにシグネチャを提供できる。 + +案 A：FRefNode を削除し、すべてのバグを直す。 +案 A の問題：相互再帰を使えるようにしたい。 +例：`val even = { int x -> x ? odd(x-1) : true; }; val odd = { int x -> x ? even(x-1) : false; };` + +案 B：型は順序どおりに定義する必要があるが、それ以外の関数には順序を要求しない。 +`new T` ならエラーにできるが、`fref.field`、`fref()`、`fref op fref`、`fref[]` ではできない。 + +あらゆる場所で Type.BOTTOM をパーサーの要件に合わせて「引き上げる」必要がある。 +FRef からフィールドをロードするには、FREF を FIELD のある TSTRUCT への TMP に引き上げる必要がある……。 +実際には、FREF が正しくなると局所的に仮定するだけだ。型は任意のコードから来るので、 +アクセスできず、引き上げられない。TMP は nullable かもしれない（後でエラーにすべき）。 +TSTRUCT は無名にでき、無名になるだろう。これは、すべての TSTRUCT を無名にすることを意味する。 + +問題は、未知・遠隔・外部・前方の参照にある。 + +FRef を*少しでも*認めると、すべての処理が FRef 型に遭遇することを考慮しなければならない。 +同じスコープの関数で認めると、上の odd/even の例が使える。 +同じスコープの構造体で認めると、相互再帰的な構造体が使える。 +スコープの外へ昇格させる際には外部の検索を試み、見つからなければ失敗する。 + +任意の使い方の例：`sys.fld`。`sys` の検索に失敗したら、次のどちらかを推測しなければならない。 +前方参照で問題なく、間もなく定義されるのか……それとも今すぐ外部を検索するのか。 +さらに、使い方によっては問題の発覚が遅れる。 +```java +// Extern or Future `sys` being returned. +val foo { -> return sys; } + +// foo() returns FRef, so Bottom, so the `.bar` has no type +// to do field lookups +val main { arg -> foo().bar } + +// HERE: Parser finds `sys` OR NOT?!?!?! +val sys??? = user_stuff....; + +``` + +行き着く先は、パーサーが一切エラーを出さず、盲目的な AST のように SSA を構築し、 +不適切な型だらけのグラフを結線するだけになることだ。 +必要なこと：パーサーを導く型をなくす！ 構文だけを使う！ + +（明らかな小さな問題：浮動小数点数へ拡張するかどうか。） +修正：たとえば整数演算を挿入する。両方の入力が isa-Int であり、isa-Float に引き上げられなくなるまでは、 +戻り値の型を Int と Float の MEET とする。 + +メソッド呼び出しで起こり得る問題： +`UNKNOWN_STRUCT_BOT.UNKNOWN_FIELD ( ARGS ); // Insert SELF OR NOT?` +— SELF を挿入するか？ +修正案：常に SELF 引数があると仮定し、静的と証明できる場合は null にする。 +最適化：定数パラメータをシグネチャから削除するか？ *定数*パラメータは、 +*パーサー*の時点で定数でなければならない。そうでなければ未知の呼び出し元がないことが必要になる +（したがって局所的な最適化になる）。 +修正案：SELF 引数を*最初*ではなく*最後*に置くと、不要になった場合に削除しやすいか？ + +Load は ConFldOff を捨て、名前を保持する。 +Load はスケーリング前の添字を保持し、添字入力を持つ。構造体ではこの入力は null。 +Ptr Base が*確定*した後で基底の配置を行い、添字の計算を畳み込める。 + +- `Load(ctrl, base, null );` — フィールド名は内部に持つ。 +- `Load(ctrl, base, index_math );` — フィールド名は `[]`。 +- `Store(ctrl, base, null , val);` + +問題：エイリアス情報がない！ + +案 C：直接呼び出し `odd()` と型では FRef を認める。それ以外はすべて*引き上げ*が必要。 + +## 構造体と配列の統合 + +構造体のフィールドは名前で索引付けされ、配列の要素は数値で索引付けされる。 +この2つの考え方は両立する、という発想です。 +C 言語では古くからこの考え方を使っています。通常の C の構造体の後に配列を続け、 +通常の配列構文で索引アクセスできます。 + +別の方法として、配列へのポインタをフィールドに保持すると、間接参照が1つ増える代わりに柔軟性が得られます。 +特に、配列を（通常はより大きな配列に）交換できます。 +これは、広く使われる汎用コンテナ `Vector` や `ArrayList` の基礎です。 + +```java +struct str { + int hash; // A cache of the strings hash code + u32 #; // The array length + u8 []; // Array of bytes +}; + +str X = "abc"; +print(X.hash); // Read the hash field +X[0]=='a'; // Read array element 0 +X#; // Length of the array + +``` + +ここでは、`#` というフィールドが配列の長さを保持し、`[]` というフィールドが実際の配列です。 +メモリ内では、この配列がほかのフィールドの直後に続きます。 +可変長配列の別の例を示します。 + +```java +struct vecInt { + u32 size; // Actual number of elements + u32 #; // The array length or capacity + int []; // Array of integers. +}; +``` + +明らかな制約として、配列のサイズを直接変更することはできません。 +先頭のフィールドと同じメモリブロックに実際に配置されているからです。 +このような `vecInt` を、より大きい新しい `vecInt` に*再割り当て*することはできますが、 +元の `vecInt` は解放されます。同じ `vecInt` の参照を永遠に使い続けることはできません。 + +名前付きフィールドはいくつあってもかまいません。 + +```java +struct Class { + !str !className; + !str !professor; + int time; + int credits; + !Class !prerequisite; + u16 #; // Limit of 65535 students per class + Student []; +}; +``` + +自己参照も使えます。 + +```java +struct NTree { + Some val; + u8 #; // Length is 0-255 + NTree []; // More NTrees +}; +``` + +構文規則は次のとおりです。 + +- 最後のフィールドの名前は `[]` で、どの型でもよい。 +- 最後から2番目のフィールドの名前は `#` で、配列の最大長を表す符号なし整数型でなければならない。 +- ` []` の前に空白が必要になるかもしれない。 + +### コンストラクタと配列 + +割り当てには配列の長さを含め、コンストラクタも含められます。 +`new NTree{val=17;}[2];` + +コンストラクタは省略できますが、配列の長さは省略できません。 + +配列を初期化するための任意の関数を使うと、一度だけ書き込む final 配列を作れます。 +`new u8[buffer#,{ u32 idx -> buffer[idx].toUpperCase() }]` + +### 配列の最大長の変更 + +範囲チェックのある小さな配列を大量に使う場合、配列の長さのために丸々4バイトを確保すると、 +配列のオーバーヘッドが大きく増えることが問題になります。 +Simple では最大長を小さくできます。ただし、最大長が異なる配列は別の型として扱います。 + +```java +struct x0 { u8 #; u8[]; }; // Array limited to 0-255 length +struct x1 { u16 #; u8[]; }; // Array limited to 0-65535 length +struct x2 { u32 #; u8[]; }; // +struct x3 { u64 #; u8[]; }; // + +x0 x = "abc"; // 4 bytes total: [3, 'a', 'b', 'c'] +x1 y = "def"; // 6 bytes total: [3, 0 , 'd', 'e', 'f', 0,]; 1 pad byte to acheieve 2-byte alignment +x = y; // ERROR, "x1 is not x0", no auto-widening +x += y; // OK, 7 bytes total: [6, 'a', 'b', 'c', 'd', 'e', 'f'] +y += x; // OK, 8 bytes total: [6, 0 , 'd', 'e', 'f', 'a', 'b', 'c'] + +x += "VeryLongString.... ....255_chars"; // Runtime RangeCheck + +// Explicit conversion to widen string +y = "" + x; +``` + +### 拡張可能な配列・文字列の2つの形：間接参照を増やすかどうか + +間接参照を1つ増やすと、Java の `ArrayList` や C++ の `Vector` のようになります。 + +増やさない場合、拡張可能な配列を伸ばす呼び出しは、新しいオブジェクトを返す可能性があります。 +拡張は必要な場合だけ行います。 + +```java +val vec1 = new vecInt[0].add(2); // len=1, capacity=1 +val vec2 = vec1.add(3); // NEW !vecInt !returned, only is deleted; len=2; capacity=2; +vec1[0]; // ERROR, vec1 has been freed by call to `vec1.add(3)` +vec2[0]; // OK +vec2[1]; // OK +vec2[2]; // Runtime error, AIOOBE +``` + +## 文字列の実装 + +既定の文字列は「str」「cstr」「ustr」などの名前を持ちます。 + +常に unicode8 を使い、u8 を明示的に操作します。 +Unicode の「文字」は、基礎となる実装の上に関数呼び出しとして提供します。 +おそらく別の文字列クラスで実装することになります。 + +## 既定の文字列 + +連結によって効率的に拡張でき、さまざまな IO/printf 関数をサポートします。 +明示的に要求すれば、基礎となる配列を可変な状態で共有できます。 +既定では常に、非共有時は可変、共有時は読み取り専用です。 + +```java +struct str { + + // Add a string to the string, possibly growing + val add = { str str -> + val self = this; + for( int i=0; i + if( len >= # ) return copy(# ? #*2 : 1).add(e); + [size++] = e; + return this; + }; + + // Copy 'this' to a new larger size + val copy = { int sz2 -> + val v2 = new str[sz2]; + for( int i=0; i sys.libc.write(1/*stdout*/,[]/*array base as argument to C*/,len); return this; } + + u32 len; // In-use size + u32 #; // Max length is 4Gig, although variants can request smaller lengths + u8 []; // Character data +}; +``` + +### Final な文字列 + +**不変**な文字列を意図しており、**安全な**文字列の基礎にも使えるかもしれません。 +一度に全体を作成する必要があり、おそらく防御的コピーも必要になります。 + +```java +struct sstr { + // Possible static call syntax; no references to "this" + val make { str str -> new sstr[str#,str.at] }; + + // Array contents are immutable. + // Still figuring out good syntax for this. + u8 #; + u8 [~]; // Middlin '~'? Makes primitive array contents *immutable* and requires constructor syntax +}; + +// Construction requires a function that produces the array contents. +// Here we are defining a defensive copy over `buf`. +sstr safe = new sstr[buf.len,{ int idx -> buf[idx]; }]; +sstr safe = sstr.make("abc"); // Defensive copy is made +``` + +### 拡張可能な文字列（StringBuilder または StringBuffer） + +この API は `StringBuilder` スタイルの代替としてそのまま使えることを意図しており、 +使うたびに間接参照が1つ増えます。 + +```java +struct xstr { + !str !_str; // The extra indirection is here + val add = { str str -> _str = str.add2(str); }; + val write = { int fd -> _str.write(fd); }; +}; +``` + +### Unicode 文字列 + +この API は、通常の `str` の上で Unicode の文字を操作できるようにすることを意図しています。 + +```java +struct ustr { + // Assuming idx is at the start of a character, return the character + // as a 32b integer. Returns junk integer if not at a character start. + // For all ASCII strings this will amount to a simple byte load. + // For bytes with high order bits set, this may read 1-4 characters. + val at = { int idx -> ... }; +}; +// Unicode character iterator +struct ucharator { +// Return successive unicode character codes +}; +``` + +### 「C」文字列 + +ゼロ終端の文字列ですが、長さを直接取得できる必要があります。 + +```java +struct cstr { + u8 #; // length including the trailing zero + u8[]; // always ends in a zero byte; suitable for direct passing to C string functions +}; +``` + +### 「german string」：レジスタに格納できる非常に短い文字列 + +メモリ内では、長さを表す1バイト（3ビット？）に続いて0〜7文字を格納し、最大8文字です。 +64ビットのレジスタに収まります。 + +```java +struct gstr { // aka germanString, or blend string and register "streg" + u3 #; // Size is 0-7 bytes??? + u8 []; // Up to 7 bytes +} +// Using inlined object (see below). All these strings are short and are +// represented as packed integers in a 64b register. +*gstr prize1 = "gold"; +*gstr prize2 = "silver"; +*gstr prize3 = "bronze"; + +``` + +### Main は `val main = { str[] args -> ...}` になる + +## 構造体のインライン化 + +構造体は通常、参照として扱いますが、「内容（contents of）」と読む `*` 演算子を使って +値として扱う形へ変換できます（この名前は、たとえば `inline` に変えるかもしれません）。 + +これは名前空間の変更だけです。内部の構造体の寿命を完全に消費しない限り、そのアドレスは取得できません。 +「外部への流出」は認めません。 + +```java +// 2 64-bit words, no other overheads +struct Complex { f64 x,y; val len = { ->Math.sqrt(x*x+y*y); }; }; + +// Current Simple rules: always by-reference +struct ByRef { + !Complex !c; // 4-byte pointer to a Complex +}; +print(new ByRef.c.y); // Lookup requires 1 extra memory load from ref to c + +// New behavior: by value (inlining a struct) +// The '*' syntax indicator can be something else, e.g. a keyword "inline" +// I am pronouncing '*' as "contents of" +struct ByValue { + *!Complex !c; // c is inlined, full 16 bytes into ByValue +}; +print(new ByValue.c.y); // x,y inlined into ByValue, no extra memory load + +// Mixing Refs and Struct Values. Basically, a ref can be converted +// to a value by taking the "contents of" the ref, and values cannot +// be *converted* to a ref, although they can be copied over a ref. +ref. c = val.c; // Error, mixing refs and values +ref.*c = val.c; // Allowed, whole structure copy. Does not allocate, requires ref.c not-null +val. c = ref.c; // Error, mixing refs and values +val. c = *ref.c; // Allowed, whole structure copy +ref. c = ref.c; // Allowed, pointer copy +val. c = val.c; // Allowed, whole structure copy. +val *c = val.c; // Error, cannot take "contents of" a value + +// Alternative syntax, to avoid the "contents of" being on LHS and field applying to being on RHS: +ref.c = val.*c; // Assign into ref.c the "contents of" val.c + +// Arrays of inlined structures +var ary = new *Complex[99]; // Array of 99 !Complex !objects, inlined + +// Calling methods has the same syntax +ref.c.len(); +val.c.len(); + +// Function arguments use the same typing, so can pass-by-value +val math.sin = { *Complex c -> ... }; // Passes a complex by value +math.sin(ref.*c); // Requires de-reference to pass by value +math.sin(val. c); // Pass by value + +``` + +## ほかの章のロードマップ + +`&&` と `||`。 +`int` を `i32` に縮小する。 +`TypeMemPtr` を4バイトに縮小する。`mmap` を使い、ヒープを下位4Gの領域に置く。 +パーサーの既定の for ループ構築、または部分的なループ剥離。 +`for( init; test; next ) body` は、次のようになる。 +```java +{ init; // Normal scope entry to bound lifetime of index variable +if( !test ) { // Zero-trip count test + do { + body; + next; + } while( test ); // Exit test at loop bottom by default +} }; +``` + +## `&&` と `||` + +論理演算子 &&（AND）と ||（OR）は短絡評価を行います。 +最初の条件だけで結果が決まるときは、第2の条件の評価を省略できます。 + +- `&&` は最初のオペランドが偽なら評価を止めます。 +- `||` は最初のオペランドが真なら評価を止めます。 + +これらは制御フローを読みやすくする糖衣構文であり、実行モデルに新しいノードを作りません。 + +`&&` と `||` の構文は、制御フローだけを変える単純な糖衣構文であり、新しいノードを導入しません。 + +次の例を考えます。 +```java +int a = 1; +int b = 0; + +if(a++ || b++ ) { + if(b == 0 && a == 2) { + sys.io.p("Or"); + } +} else{ + sys.io.p("And"); +} +return 0; +``` + +- `a++` は1（真）と評価されるので、`b++` は評価されません。 +- その結果、`b` は0のままで、`a` は2になり、「Or」が表示されます。 + +```java +int a = 1; +int b = 1; + +int x=1; +int y=1; +int z=0; + +int g = x++ && y++ && z++; +... +``` + +この例では、次のようになります。 + +- `x++` は真（1）なので、`y++` を評価します。それも真です。 +- 続いて `z++` を評価します。これは偽（0）です。 +- `&&` はすべての条件が真であることを要求するため、最終結果 `g` は0になります。 +- 偽になるオペランドまでのすべてのオペランドを評価するため、`x`、`y`、`z` はすべてインクリメントされます。 diff --git a/docs/chapter25/ROADMAP.md b/docs/chapter25/ROADMAP.md new file mode 100644 index 00000000..749a1614 --- /dev/null +++ b/docs/chapter25/ROADMAP.md @@ -0,0 +1,464 @@ +## Separate Compilation + +English | [日本語](ROADMAP.ja.md) + + +How to handle unknown forward ref? +No H-M, so no unification. +Demand no forward refs beyond functions... which will provide immediate signatures when def'd. + +Plan A: Remove FRefNode; fix all my bugs. +Fail A: I want mutual co-recurusion to work +Example: `val even = { int x -> x ? odd(x-1) : true; }; val odd = { int x -> x ? even(x-1) : false; };` + +Plan B: Require types ordered, but not any other fcn. `new T` can complain, +but not `fref.field` or `fref()` or `fref op fref` or `fref[]` + +Requires "lifting" Type.BOTTOM to the parser requirements everywhere. +So loading a field from an FRef requires: lift the FREF to a +TMP-to-TSTRUCT-with-FIELD... actually, just locally assume FREF will become +correct. Can't Lift it, no access, since type comes from random code. +TMP might be nullable (should error later). +TSTRUCT can/will be unnamed. Implies ALL TSTRUCT is unnamed. + +Issue is some unknown/remote/external/forward-ref. + +Allowing an FRef *at all* means everybody has to deal with seeing an FRef Type. +Allowing it for functions in same scope allow the above odd/even case . +Allowing it for structs in the same scope allows for co-recursive structs. +Promoting out-of-scope attempts the external lookup, then fails. + +Random junk usage: `sys.fld`. Looking up `sys` fails, now has to +guess: fref is ok, will be defined shortly... OR extern lookup now. +Then some usage delays trouble: +```java +// Extern or Future `sys` being returned. +val foo { -> return sys; } + +// foo() returns FRef, so Bottom, so the `.bar` has no type +// to do field lookups +val main { arg -> foo().bar } + +// HERE: Parser finds `sys` OR NOT?!?!?! +val sys??? = user_stuff....; + +``` + +Which gets to: parser never complains, builds SSA like a blind AST, +just wires up a graph with bad types all around. Requires: No Types +to guide parser! Just Syntax! + + (Obvious minor fail: widen floats- or-not) Fix: insert e.g. int-oper, return + type is MEET of Int,Float until both inputs are isa-Int and cannot lift to be + isa-Float + + Possible method call fail: + UNKNOWN_STRUCT_BOT.UNKNOWN_FIELD ( ARGS ); // Insert SELF OR NOT? + Possible fix: always assume a SELF arg, which is null for provable statics. + Optimization: constant parms get dropped from sig? *Constant* parms + must be constant from *Parser*, or else no unknown callers (so local opts). + Possible fix: SELF arg is *last* not *first*, easier to drop if dead? + + Load drops ConFldOff, keeps name. + Load keeps index unscaled, has index input, which is null for structs. + After Ptr Base is *closed*, base layout can happen, can fold index math. + - Load(ctrl, base, null ); // field name internal + - Load(ctrl, base, index_math ); // field name=='[]' + - Store(ctrl, base, null , val); + + FAIL: No Alias Info! + + +Plan C: + FRefs allowed for direct calls `odd()`, and for Types. + All other cases must *lift*. + + +## Unifying Structs and Arrays + +The idea is that structs have fields indexed by names, and arrays have fields +indexed by numbers, and these ideas are compatible with each other. This idea +has been used by the C language for a long time - an array can follow a normal +struct C and can index it with the usual array syntax. + +The alternative, using a field to hold a pointer to an array, exchanges some +flexibility for an extra indirection. The obvious flexibility allows swapping +the array out (generally for a larger one) and this is the basis of very common +`Vector` or `ArrayList` generic containers. + + +```java +struct str { + int hash; // A cache of the strings hash code + u32 #; // The array length + u8 []; // Array of bytes +}; + +str X = "abc"; +print(X.hash); // Read the hash field +X[0]=='a'; // Read array element 0 +X#; // Length of the array + +``` + +Here, the field named `#` holds the array length and the field named `[]` is +the actual array, which follows the other fields directly in memory. +Here is another example for variable length array: + +```java +struct vecInt { + u32 size; // Actual number of elements + u32 #; // The array length or capacity + int []; // Array of integers. +}; +``` + +The obvious limit here is that the array cannot be directly resized; it is +literally in the same memory block as the leading fields. Such a `vecInt` can +be *re-allocated* to a new larger `vecInt`, but the original `vecInt` will be +reclaimed - you cannot use the same `vecInt` reference forever. + +Any number of named fields are allowed: + +```java +struct Class { + !str !className; + !str !professor; + int time; + int credits; + !Class !prerequisite; + u16 #; // Limit of 65535 students per class + Student []; +}; +``` + +Or self-reference: + +```java +struct NTree { + Some val; + u8 #; // Length is 0-255 + NTree []; // More NTrees +}; +``` + +The syntax rules are: +- the last field is named `[]` and can be of any type. +- the second-to-last field is named `#` and must be some unsigned integer type + representing the maximum array length. +- may require a leading space in front of ` []` + + + +### Constructors and Arrays + +The allocation includes the array length, and can include a constructor: +`new NTree{val=17;}[2];` + +The constructor is optional, the array length is not. + +Optional function for initializing arrays, allows for write-once final arrays: +`new u8[buffer#,{ u32 idx -> buffer[idx].toUpperCase() }]` + + + +### Changing array max length + +An issue for large numbers of range-checked small arrays is that reserving a +full 4 bytes for array length can substantially increase the array overhead. +Simple allows for arrays to have smaller max lengths, although these are +treated as a different type than arrays with different max lengths. + +```java +struct x0 { u8 #; u8[]; }; // Array limited to 0-255 length +struct x1 { u16 #; u8[]; }; // Array limited to 0-65535 length +struct x2 { u32 #; u8[]; }; // +struct x3 { u64 #; u8[]; }; // + +x0 x = "abc"; // 4 bytes total: [3, 'a', 'b', 'c'] +x1 y = "def"; // 6 bytes total: [3, 0 , 'd', 'e', 'f', 0,]; 1 pad byte to acheieve 2-byte alignment +x = y; // ERROR, "x1 is not x0", no auto-widening +x += y; // OK, 7 bytes total: [6, 'a', 'b', 'c', 'd', 'e', 'f'] +y += x; // OK, 8 bytes total: [6, 0 , 'd', 'e', 'f', 'a', 'b', 'c'] + +x += "VeryLongString.... ....255_chars"; // Runtime RangeCheck + +// Explicit conversion to widen string +y = "" + x; +``` + + +### Two flavors of extendable arrays/strings: an extra indirection or not + +With an extra indirection you get e.g. Java `ArrayList` or C++ `Vector`. + +Without, then any call which extends the extendable array return a potentially +new object, only growing as needed. + +```java +val vec1 = new vecInt[0].add(2); // len=1, capacity=1 +val vec2 = vec1.add(3); // NEW !vecInt !returned, only is deleted; len=2; capacity=2; +vec1[0]; // ERROR, vec1 has been freed by call to `vec1.add(3)` +vec2[0]; // OK +vec2[1]; // OK +vec2[2]; // Runtime error, AIOOBE +``` + + +## A String Implementation + +Default strings have names like "str", "cstr", "ustr" or such. + +Always unicode8 with explicit u8 manipulations. Unicode "characters" will come +as function calls over the base implementation, probably in another string class. + +## Default string + +Efficiently growable via concantenation. Supports a variety of IO/printf functions. +The underlying array can be shared mutable if you ask for this. +The defaults will always be private mutable and read-only shared. + +```java +struct str { + + // Add a string to the string, possibly growing + val add = { str str -> + val self = this; + for( int i=0; i + if( len >= # ) return copy(# ? #*2 : 1).add(e); + [size++] = e; + return this; + }; + + // Copy 'this' to a new larger size + val copy = { int sz2 -> + val v2 = new str[sz2]; + for( int i=0; i sys.libc.write(1/*stdout*/,[]/*array base as argument to C*/,len); return this; } + + u32 len; // In-use size + u32 #; // Max length is 4Gig, although variants can request smaller lengths + u8 []; // Character data +}; +``` + + +### A Final String + +Intended to be a **immutable** string, possibly used as a base for a **secure** +string. This needs to be created all at once, and probably requires a +defensive copy. + +```java +struct sstr { + // Possible static call syntax; no references to "this" + val make { str str -> new sstr[str#,str.at] }; + + // Array contents are immutable. + // Still figuring out good syntax for this. + u8 #; + u8 [~]; // Middlin '~'? Makes primitive array contents *immutable* and requires constructor syntax +}; + +// Construction requires a function that produces the array contents. +// Here we are defining a defensive copy over `buf`. +sstr safe = new sstr[buf.len,{ int idx -> buf[idx]; }]; +sstr safe = sstr.make("abc"); // Defensive copy is made +``` + + +### A Extendable String (aka StringBuilder or StringBuffer) + +This API is intended to be a drop-in for a `StringBuilder` style, and takes an +extra indirection with each usage. + +```java +struct xstr { + !str !_str; // The extra indirection is here + val add = { str str -> _str = str.add2(str); }; + val write = { int fd -> _str.write(fd); }; +}; +``` + +### A Unicode String + +This API is intended to support unicode character manipulation over a plain `str` + +```java +struct ustr { + // Assuming idx is at the start of a character, return the character + // as a 32b integer. Returns junk integer if not at a character start. + // For all ASCII strings this will amount to a simple byte load. + // For bytes with high order bits set, this may read 1-4 characters. + val at = { int idx -> ... }; +}; +// Unicode character iterator +struct ucharator { +// Return successive unicode character codes +}; +``` + +### A "C" string + +A zero-terminated string, but the length has to be available directly + +```java +struct cstr { + u8 #; // length including the trailing zero + u8[]; // always ends in a zero byte; suitable for direct passing to C string functions +}; +``` + +### A "german string": a very short string that can exist in a register + +Length in memory is 1 byte (3 bits?) of length, then 0-7 chars; max 8 chars. +Fits in a 64 bit register. + +```java +struct gstr { // aka germanString, or blend string and register "streg" + u3 #; // Size is 0-7 bytes??? + u8 []; // Up to 7 bytes +} +// Using inlined object (see below). All these strings are short and are +// represented as packed integers in a 64b register. +*gstr prize1 = "gold"; +*gstr prize2 = "silver"; +*gstr prize3 = "bronze"; + +``` + +### Main becomes `val main = { str[] args -> ...}` + + +## Structs can be inlined + +Structs are normally by-reference, but can be converted to by-value by using +the `*` operator, pronounced "contents of" (this name might be changed to +e.g. `inline`). + +This is a name-space change only, you cannot take the address of the internal +struct without entirely consuming its lifetime. No "escaping". + +```java +// 2 64-bit words, no other overheads +struct Complex { f64 x,y; val len = { ->Math.sqrt(x*x+y*y); }; }; + +// Current Simple rules: always by-reference +struct ByRef { + !Complex !c; // 4-byte pointer to a Complex +}; +print(new ByRef.c.y); // Lookup requires 1 extra memory load from ref to c + +// New behavior: by value (inlining a struct) +// The '*' syntax indicator can be something else, e.g. a keyword "inline" +// I am pronouncing '*' as "contents of" +struct ByValue { + *!Complex !c; // c is inlined, full 16 bytes into ByValue +}; +print(new ByValue.c.y); // x,y inlined into ByValue, no extra memory load + +// Mixing Refs and Struct Values. Basically, a ref can be converted +// to a value by taking the "contents of" the ref, and values cannot +// be *converted* to a ref, although they can be copied over a ref. +ref. c = val.c; // Error, mixing refs and values +ref.*c = val.c; // Allowed, whole structure copy. Does not allocate, requires ref.c not-null +val. c = ref.c; // Error, mixing refs and values +val. c = *ref.c; // Allowed, whole structure copy +ref. c = ref.c; // Allowed, pointer copy +val. c = val.c; // Allowed, whole structure copy. +val *c = val.c; // Error, cannot take "contents of" a value + +// Alternative syntax, to avoid the "contents of" being on LHS and field applying to being on RHS: +ref.c = val.*c; // Assign into ref.c the "contents of" val.c + +// Arrays of inlined structures +var ary = new *Complex[99]; // Array of 99 !Complex !objects, inlined + +// Calling methods has the same syntax +ref.c.len(); +val.c.len(); + +// Function arguments use the same typing, so can pass-by-value +val math.sin = { *Complex c -> ... }; // Passes a complex by value +math.sin(ref.*c); // Requires de-reference to pass by value +math.sin(val. c); // Pass by value + +``` + + + +## RoadMap for other chapters + +`&&` and `||` +Drop `int` to `i32`. +Drop `TypeMemPtr` to 4 bytes; using `mmap` to make heap in low 4G. +Default parser for-loop construction, or partial peel. + `for( init; test; next ) body` +becomes: +```java +{ init; // Normal scope entry to bound lifetime of index variable +if( !test ) { // Zero-trip count test + do { + body; + next; + } while( test ); // Exit test at loop bottom by default +} }; +``` + +## `&&` and `||` + +The logical operators && (AND) and || (OR) are short-circuiting, meaning they may skip evaluating the second condition if the first one already determines the result: + +- `&&` stops if the first operand is false. +- `||` stops if the first operand is true. + +They are syntactic sugar—used for cleaner control flow—but they don't create new nodes in the execution model. + +The `&&` and `||` constructs are simple syntactic sugars that only modify the control flow and do not +introduce new nodes. + +Consider this example: +```java +int a = 1; +int b = 0; + +if(a++ || b++ ) { + if(b == 0 && a == 2) { + sys.io.p("Or"); + } +} else{ + sys.io.p("And"); +} +return 0; +``` +- `a++` evaluates to 1 (true), so `b++` is not evaluated. +- As a result, `b` stays 0, `a` becomes 2, and "Or" is printed. + +```java +int a = 1; +int b = 1; + +int x=1; +int y=1; +int z=0; + +int g = x++ && y++ && z++; +... +``` +Here: +- `x++` is true (1), so it evaluates `y++`, which is also true. +- Then it evaluates `z++`, which is false (0). +- Since `&&` requires all conditions to be true, the final result `g` is 0. +- All operands up to the false one are evaluated, so `x`, `y`, and `z` are all incremented. diff --git a/docs/chapter25/examples/A_helloWorld.smp b/docs/chapter25/examples/A_helloWorld.smp new file mode 100644 index 00000000..4ed6abdf --- /dev/null +++ b/docs/chapter25/examples/A_helloWorld.smp @@ -0,0 +1,2 @@ +sys.io.p("Hello, World!\n"); +return 0; diff --git a/docs/chapter25/examples/BubbleSort.smp b/docs/chapter25/examples/BubbleSort.smp new file mode 100644 index 00000000..ca6906b5 --- /dev/null +++ b/docs/chapter25/examples/BubbleSort.smp @@ -0,0 +1,36 @@ + +// An implementation of +// https://sampleprograms.io/projects/bubble-sort/ +// +// Bubble sort, with reading (parsing) and writing (formatting) the data. + +val sort = { !sys.aryi64 nums -> + sys.aryi64?! more = nums; + while( more ) { + more = null; + for( var i = 0; i < nums.len-1; i++ ) + if( nums.buf[i] > nums.buf[i+1] ) + more = nums.swap(i,i+1); + } +}; + +// Read one process argument of the form "[ 4, 3, 2, 1]" and print it sorted. +// args[0] is the executable name, as with native C argc/argv. +val main = { u8[~][] args -> + val usage = { -> + sys.io.p("Usage: please provide a list of at least two integers to sort in the format \"[1, 2, 3, 4, 5]\"\n"); + return 0; + }; + if( args# != 2 ) return usage(); + + var nums = sys.aryi64.parseAryI64(args[1]); + if( !nums ) return usage(); + if( nums.len < 2 ) return usage(); + + // Bubble sort array of integers + sort(nums); + + // Print the same bracketed array-list format accepted as input. + nums.str().add('\n').write(1); + return 0; +}; diff --git a/docs/chapter25/examples/Capitalize.smp b/docs/chapter25/examples/Capitalize.smp new file mode 100644 index 00000000..8e31c18f --- /dev/null +++ b/docs/chapter25/examples/Capitalize.smp @@ -0,0 +1,22 @@ + +// An implementation of +// https://sampleprograms.io/projects/capitalize/ + +val main = { u8[~][] args -> + if( args# > 2 ) { + sys.io.p("Use quotes around multiple strings.\n"); + return 0; + } + if( args# != 2 || args[1]# == 0 ) { + sys.io.p("Usage: please provide a string\n"); + return 0; + } + + u8[~] input = args[1]; + var output = new u8[input# + 1]; + sys.ary.copy(output,0,input,0,input#); + output[0] = sys.char.toupper(input[0]); + output[input#] = '\n'; + sys.io.p(output); + return 0; +}; diff --git a/docs/chapter25/examples/Dijkstra.smp b/docs/chapter25/examples/Dijkstra.smp new file mode 100644 index 00000000..fd595eb5 --- /dev/null +++ b/docs/chapter25/examples/Dijkstra.smp @@ -0,0 +1,72 @@ + +// An implementation of +// https://sampleprograms.io/projects/dijkstra/ + +val shortestPath = { !sys.aryi64 matrix, int nodes, int src, int dst -> + i64 infinity = (1 << 63)-1; + var dist = new i64[nodes]; + var visited = new sys.adt.bitset(); + // All nodes are infinitely far from each other + for( int i=0; i 0 && !visited.get(node) && best+weight < dist[node] ) + dist[node] = best+weight; + } + } + count++; + } + return result; +}; + +val usage = { -> + sys.io.p("Usage: please provide three inputs: a serialized matrix, a source node and a destination node\n"); + return 0; +}; + +val main = { u8[~][] args -> + // Exactly 3 args + if( args# != 4 ) return usage(); + // First is a serialized square matrix of positive numbers + var matrix = sys.aryi64.parseAryI64(args[1]); + if( !matrix ) return usage(); + if( !matrix.len ) return usage(); + // All numbers are positive + for( int i=0; i= nodes || dst < 0 || dst >= nodes ) + return usage(); // Source and destination land within the graph + + i64 cost = shortestPath(matrix,nodes,src,dst); + if( cost >= 0 ) { + new sys.aryu8().num(cost).add('\n').write(1); + return 0; + } + return usage(); +}; diff --git a/docs/chapter25/examples/FileIO.smp b/docs/chapter25/examples/FileIO.smp new file mode 100644 index 00000000..e48d435b --- /dev/null +++ b/docs/chapter25/examples/FileIO.smp @@ -0,0 +1,50 @@ + +// An implementation of +// https://sampleprograms.io/projects/file-input-output/ + +val FILE = "output.txt"; + +val main = { u8[~][] args -> + var str = new sys.aryu8(); + str.addAry("Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.\n"); + str.addAry("Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.\n"); + str.addAry("Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur.\n"); + str.addAry("Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.\n"); + + // Create + i32 fd = sys.io.create(FILE); + if( fd == -1 ) return _error(); + // Write + int wrote = sys.io.writeOff(fd,str.buf,0,str.len); + if( wrote == -1 ) return _error(); + if( wrote != str.len ) return _error2(-2); + // Close + if( sys.io.close(fd) != 0 ) return _error(); + + // Open + i32 fd2 = sys.io.open(FILE); + if( fd2 == -1 ) return _error(); + // Read + var got = sys.io.read(fd2); + if( got# != str.len ) return _error2(-3); + // Close + if( sys.io.close(fd2) != 0 ) return _error(); + + // Check contents are equal + if( sys.ary.cmp(got,0,str.buf,0,str.len) ) + return _error2(-4); + + // Remove + if( sys.io.remove(FILE) != 0 ) return _error(); + + sys.io.p("File I/O succeeded\n"); + return 0; +}; + +val _error2 = { i32 errno -> + sys.io.remove(FILE); + new sys.aryu8().addAry("Failed with error code ").num(errno).add('\n').write(sys.libc.STDERR); + sys.libc._exit(errno); +}; + +val _error = { -> _error2(sys.libc.errno()); }; diff --git a/docs/chapter25/font-awesome-4.7.0.zip b/docs/chapter25/font-awesome-4.7.0.zip new file mode 100644 index 00000000..b6bdb4bd Binary files /dev/null and b/docs/chapter25/font-awesome-4.7.0.zip differ diff --git a/docs/chapter25/ifg_trim.pdf b/docs/chapter25/ifg_trim.pdf new file mode 100644 index 00000000..d952fd4f Binary files /dev/null and b/docs/chapter25/ifg_trim.pdf differ diff --git a/docs/chapter25/initialization.md b/docs/chapter25/initialization.md new file mode 100644 index 00000000..d03c2eb7 --- /dev/null +++ b/docs/chapter25/initialization.md @@ -0,0 +1,481 @@ +# Lazy class initialization design + +Design proposal, 2026-10-08. This specifies the next implementation; the current +compiler does not yet enforce this protocol. Declared constant final fields +already have static-data lowering, but general lazy run-once initialization, +dependency validation, and initialization guards remain to be implemented. + +Initialization metadata belongs with class identity and compilation-unit +ownership, not solely on the `` FunNode. Represent active touches in +ideal IR, validate an acyclic graph across source and imported objects, and +lower remaining checks to a hidden flag in the class object and a conditional +call. The initializer itself owns the store that sets the flag. +Use one runtime bit in the first, single-threaded implementation. + +## Language rules + +- Dynamic class initialization runs once, on the first active touch. A class + never actively touched executes no initialization code. +- A dynamic parent completes before a dynamic child starts. There is no early + publication point or special tail-call escape from this rule. +- Outside the initializer's own checked initialization context, no code may + observe fields before their required initialization completes. +- Class identity exists before initialization. Taking a class reference, as + in `sys`'s `val io = io`, is passive and does not execute the child's body. + Storing a function identity is also distinct from invoking it. +- Proven static-data accesses require no dynamic work. This does not authorize + a called function to observe unfinished dynamic state in an ancestor or any + other class. +- Initialization requirements form a DAG across the complete linked program, + including module boundaries. Reject cycles, including potential cycles + behind runtime conditionals. Ordinary recursive functions are still legal. +- Initialization order follows actual execution and parent requirements, not + parser discovery order, worklist seed, or filesystem enumeration order. + +For example, A conditionally reading `B.foo`, with B initializing `foo` from +`A.bar`, is rejected. Neither an initial zero nor an early evaluation of +`A.bar` resolves that cycle. If B is A's child, the parent requirement already +provides the reverse dependency. + +An initializer may read its own previously initialized fields under the existing +definite-initialization rules. That is not an ordinary external active touch. +Do not infer permission for arbitrary callbacks or same-class helper calls from +the fact that their owner is currently being initialized. Such helpers need a +proof that they do not observe unfinished state; otherwise reject their use. + +## Ownership and identity + +Keep `CompUnit._deps` for source/object discovery and rebuild dependencies. +Do not reuse it as the initialization graph: passive references belong there, +and its elements are files rather than necessarily individual classes. + +Add a small `ClassInit` record owned by a CompUnit. The file class is available +as `CompUnit._init`; a canonical map in CodeGen resolves records by full class +name. Classes nested within a file do not each have a CompUnit today. They can +have records owned by that same unit, including records with no dynamic body. +This avoids treating an instance `` as a class ``. + +Suggested information, with names provisional: + +| Member | Meaning | +|---|---| +| `_name` | Stable, fully qualified class identity | +| `_owner` | Defining CompUnit; owns native data and initializer definitions | +| `_parent` | Enclosing class record, if any | +| `_body` | Optional current `` FunNode; absent for unloaded/static-only bodies | +| `_deps` | Lazily allocated, deduplicated direct initialization dependencies | +| `_complete` | All declarations, call effects, and dependency targets resolved | +| `_static` | Proven that this class's own initialization requires no execution | +| `_flagAlias` | Alias of the hidden `$init` field in this class object | + +An absent body is not proof of `_static`: it may simply not have been loaded. +Metadata flags describe compiler knowledge, not additional runtime states. +An explicitly defined namespace-only parent can have an empty initialization +record; a missing parent definition must not silently become such a record. +FunNodes can refer back to their initialization record; the record survives +inlining, dead-function elimination, and conversion of initialization to data. + +`addInitDep(target, reason)` adds a direct edge only once and invalidates the +cached graph validation/order. Retain a source location and, for indirect +dependencies, a call-site witness for diagnostics. Do not turn every dependency +addition into a scan of all initializer bodies. + +## Discovering and validating dependencies + +Use the convention `A -> B` to mean that initializing A may require B completed. +Topological output therefore places prerequisites before dependents. A dynamic +child has a structural dependency on its parent. An active touch of another +class during A's initializer contributes an edge; a passive reference does not. + +Record semantic touches before inlining and guard elimination. Collect direct +touches in ordinary function bodies too, and propagate their initialization +effects through the call graph with a worklist. Recursive function SCCs reach +a fixed point of finite dependency sets; they are not themselves initialization +cycles. Indirect calls contribute the union of all possible targets' effects. + +The initial policy is conservative: a runtime conditional contributes both +branches' possible requirements. Do not let inlining choices or random peephole +order decide whether a cycle is legal. Dependencies may be added as forward +references and call targets resolve. Before declaring a graph complete, every +reachable initialization-time call must have a complete effect summary. + +An unknown function-pointer target or native callback is not an empty summary. +Reject such a call during initialization unless an explicit trusted contract +establishes its initialization effects, including that it cannot call back into +unfinished Simple initialization. Ordinary native I/O can use such a contract; +this is independent of whether the call has memory or I/O effects. + +Proving a class entirely static is a separate, deterministic classification +step. Static object/reference cycles are legal and need no dynamic ordering. +Dropping a dynamic requirement requires proof that the relevant operation needs +no initialization, not merely that its guard or result optimized away. A real +cycle must not bootstrap its own static-ready proof. + +Validate the union of parent edges and active initialization requirements after +the source/import closure is resolved and again after loading or replacing +summaries. Report a cycle with class names and the source/call witnesses for +its edges. An incomplete library may retain explicitly unresolved obligations; +it cannot be certified as a complete runnable program. + +Use a stable name order to break ties in diagnostic/topological output. Cache +module-local results, but validate cross-module edges at final composition. +One module's list is not necessarily a contiguous block: `X.A -> Y.B -> X.C` +in prerequisite-first order requires interleaving X and Y. Retain edges as the +authority rather than serializing a local order as a global proof. + +The topological order validates permitted completion order; it is not a startup +schedule. If A conditionally uses independent B, B initializes only on the +taken path. A may start before B and finish after it. That is safe precisely +because B cannot directly or indirectly require unfinished A. Do not eagerly +initialize every possible dependency, or a prefix of the topological list. + +## Ideal IR and runtime protocol + +Introduce an effectful `CLInitNode` with a stable ClassInit identity: + +```text +CLInit(C, ctrl, memory) -> (ctrl, memory) +``` + +Control is input/output slot 0 and memory slot 1. Store the target class as +semantic metadata or a separate constant input, never in the control/memory +slots. Include target identity in equality, copying, printing, and serialization. +Its normal return guarantees the required initialization of C and its ancestors. +It can execute arbitrary initializer effects, so it is not a pure flag test. + +At dynamic class-field reads and writes, required instance creation, and calls +requiring initialized class state, consult parser flow facts first and insert +CLInitNode only if the required initialization is not already established. +Record the semantic requirement even when no check needs inserting. Passive +Simple class references remain subject to checks at their later field accesses. +Native escape of class references is a separate boundary described below. +Forward references must preserve the pending check until the target is known. + +For `ary.copy(args)`, check the class at the field access: + +```text +CLInit(ary) +f = load ary.copy +call f(args) +``` + +The ordinary function header, calling convention, and static function-pointer +field do not change. There is no per-function checked wrapper. Folding the +field load to a constant function pointer does not remove the preceding +initialization effect unless that effect is independently redundant. Once the +checked load yields `f`, it can be passed along and called without repeating +the check for `ary`. Materializing a function address in static data is not a +source-level field access. An initializer's raw body remains private compiler +machinery, not a callable reset operation. + +Keep CLInitNode in ideal IR so its peepholes can eliminate or simplify frequent +checks. Lower a remaining node to ordinary Load/If/Call/Region/Phi IR before +machine selection, using a shared class-initialization helper where an +out-of-line guard is useful. The checking code contains no flag store: + +```text +CLInit_C(ctrl, memory): + (ctrl, memory) = CLInit_parent_if_required(ctrl, memory) + if load(C.$init, memory): + return (ctrl, memory) + return call C.(ctrl, memory) + +C.(ctrl, memory): + memory = store(C.$init, true, memory) + ... original initializer body ... + return (ctrl, memory) +``` + +Entry to `` already means that its check took the not-initialized path. +Place the flag store in the initializer, naturally at its entry. This covers +all its normal exits without replicating a store in each CLInitNode expansion. +Inlining the body may of course copy its store, just as it copies other body +instructions. The body must not guard itself through ordinary method-entry +instrumentation. + +There is no requirement to schedule the store last. With a validated acyclic +initialization graph and one thread, no other user can observe this class's +flag while its initializer is running. A nonreturning initializer can leave +the bit set because no permitted observer can resume. The physical flag store +is not an early publication point: the class's initialization still completes +only when its body returns. Cycle validation and definite-initialization checks +must remain independent of that store and of optimizations which expose it. + +The first runtime contract is single-threaded initialization, with no recovery +and retry after initializer failure. The validated DAG rules out recursive +entry to an unfinished initializer. Thus no runtime `initializing` state is +needed. Concurrent first touches or recoverable initialization failures require +an extended protocol; the flag is not a synchronization mechanism. + +## Hidden flag and known completion + +Add a hidden boolean field `$init` to the ordinary `` class object. +There are few such objects, one per class; no separate allocation, symbol, or +special bit-packing scheme is needed. Use the existing small-integer field +representation and normal struct layout/offset machinery. It is a logical bit, +initially false for a dynamic body, stored true by that body, and inaccessible +to user writes. Separate importers share it through the existing `C.$class` +identity and its canonical field layout. + +Allocate/remap these aliases during class discovery, before the current +`freezePublicInterface()` boundary. Hidden flags are not source-visible fields, +but their memory effects must participate in call summaries and memory merging. +Keep CLInitNode's complete public-memory effect until a narrower summary is +proved; tracking only the flag would lose the initializer's field and I/O effects. + +There are two different facts: + +1. **Static body completion:** `_static` proves that C's own initial contents + are supplied by data and there are no remaining initializer effects. Its + `$init` field starts true, and its redundant body/store can disappear. +2. **Completion at a program point:** normal return from CLInitNode establishes + readiness in that control/memory state. At a permitted external touch, a + true flag branch proves completion of C's own body; its ancestors must also + be known complete before concluding that an ordinary active use is safe. + +Inside C's own initializer, the flag can already be true while fields are still +being initialized. Keep that lexical initialization context and its field-read +checks; a folded true flag does not grant access to unfinished fields. In +particular, it must not make a callback or cyclic initialization dependency +legal. Record and validate those dependencies before suppressing their checks. + +Neither fact means mutable fields remain constant. Do not refine their declared +types to their static initial values. Also, a static-only child with a dynamic +ancestor is not globally ready for every active use: ordinary ensures still +establish the ancestor. Passive references and proven initialization-independent +static accesses need no such ensure, including during the parent's initializer. + +## Parser flow and ideal peepholes + +CLInitNode will occur frequently. Avoid constructing obvious duplicates in the +parser, then use normal ideal optimization as more types, call effects, and +control-flow facts become available. A separate late must-analysis is optional, +not a prerequisite for removing straightforward redundant checks. + +Carry known-initialized class identities with parser control flow, for example +as a BitSet in ScopeNode keyed by compilation-local class IDs. These are path +facts, not mutable global properties of ClassInit or its declared TypeStruct: + +- On an active touch, record the dependency, then consult the facts. If C and + its required ancestors are known ready, omit the CLInitNode. +- Normal return from CLInit(C) adds C and its required ancestors. Do not add + every possible dependency: a conditional initializer may never touch one. +- Copy facts on a branch and intersect them at a reachable merge. An abrupt + or nonreturning path contributes no completion facts to a reachable merge. +- A loop's first iteration has only entry-path guarantees. Body/backedge facts + alone cannot suppress its first check or establish readiness after a + potentially zero-trip loop. Preserve pre-loop facts and refine only with a + proof covering all relevant incoming paths. +- A call cannot reset established facts. Add new ones only from a proven normal + return summary; do not seed arbitrary exported function entries with facts + learned at one caller. Checks at field-access sites establish their facts. + +Give CLInitNode ideal peepholes for these cases: + +| Proof | Rewrite | +|---|---| +| Fully static class / flag known true at a permitted touch | Remove the class's own check and call; retain any still-required ancestor initialization | +| Flag known false at this memory/control point | Replace the test with an unconditional initializer call; retain the call's effects and results | +| Earlier normally returning CLInit of the same class dominates | Forward control/memory through the redundant node | +| Dominating true flag test covers this path | Remove the covered check, as with redundant if-test reasoning | +| All reachable arms of a merge establish completion | Fold the repeated check after the merge | + +Known false must come from the memory reaching the node, not simply the false +byte in the original object image. Known true on one branch is not known true +after a merge with an unchecked branch. Match stable class identity and required +ancestors, not just a pointer-shaped value or a similar field name. + +Use the existing dependency/wakeup mechanism when a node consults a flag value, +memory state, or another node's proof, so later refinement revisits the check. +Retain control and whole-memory ordering through the conditional call: removing +a check must preserve preceding initialization effects, and hoisting a check +onto an untaken path would violate laziness. In particular, CLInitNode is not +freely speculatable or an ordinary pure expression suitable for unrestricted GVN. + +Parser omission must have an enduring IR justification: earlier effectful +CLInit/control edges, a proven caller precondition, or static metadata. +When bodies are inlined or deserialized, those proofs travel with the IR; +transient parser facts alone cannot justify an unchecked exported body. A +shared declared type must not be mutated to encode a path-local true flag. + +## Static data classification + +A class is fully static only when every required initial value is representable +in data/relocations and no runtime effect remains: no I/O, observable allocation, +potential failure, or required dynamic dependency. A missing/dead body alone +does not prove this, and startup arguments are not static inputs. + +Ignore the compiler-inserted `$init = true` bookkeeping store when checking +whether the original initializer is entirely static. Otherwise every inserted +store would prevent this optimization. Once the proof succeeds, emit `$init` +as true in the object image and eliminate the runtime store with the body. + +Mutable fields may have static initial values. Folding their initializing +stores must still preserve reads and escapes during the initializer. Merely +knowing the final value and that the body runs once is insufficient. Preserve +object identity and canonical layout separately from initial contents, and do +not collapse distinct class objects with equal bytes. + +This extends the current StaticData machinery; it does not change pointer +widths or require class objects to become read-only. An object with a dynamic +`$init` field stays writable even if its source fields are final. A fully static +object whose source fields are also immutable can later use read-only storage, +with its hidden field already true and no runtime writes to it. + +## Serialization and final composition + +Add a class-initialization directory to the `.simple` data that can be read +without materializing every function body. Serialize: + +- Stable class and parent names, defining-unit identity, and initializer symbols. +- Static/dynamic/unknown classification and summary-completeness information. +- Direct initialization requirements and function-effect summaries, including + unresolved obligations and useful cycle-diagnostic locations. +- The hidden `$init` field's type, alias identity, initial image value, and + canonical layout, alongside the other class fields. Remap aliases using file + identity and local order rather than copying process-local numbers. +- CLInitNode operations and the initializer's own flag Store in ideal IR, + including all semantic fields needed to rebuild them. + +Do not serialize transient node references, a cached global topo index, or the +runtime value of a dynamic flag as an unconditional type fact. A definition +and its imported declarations must resolve to the same ClassInit record. + +On load, register identities first, resolve parent/dependency edges second, +then resolve function summaries and IR. Check conflicting owners, missing +definitions, alias remapping, summary completeness, and combined cycles. +Loaded bodies must agree with their summaries; report newly found requirements +and revalidate rather than trusting an earlier module-local topo sort. + +Preserve these summaries before `unlinkImports()` removes imported bodies. +Serialize ideal CLInitNode operations before lowering to machine code. Native +objects retain checks at their class-field access sites even when a particular +importing compiler inlines and removes its local checks. Ordinary function +symbols and function-pointer constants are not replaced by checked wrappers. + +Do not serialize a parser's transient BitSet as unconditional entry knowledge. +Its local class IDs can change on reload; retained checks, control flow, and +explicit entry contracts must support any omitted checks. Recompute flow facts +for loaded graphs and verify hidden-field ownership/layout and that the flag +store belongs to ``, not to each checking caller. + +Final validation needs a Simple-aware executable/library composition step. +An ordinary native linker cannot validate dependencies stored only in `.simple`. +Enumerate the complete intended Simple object set, including exported entry +points that native code could invoke; loading only the source-discovered +references is insufficient. Validate that metadata set before handing objects +to GCC/the native linker. Dynamically loading additional Simple modules is +outside this first protocol and would require validation before activation. + +Keep the current unversioned `C0DE` convention and require rebuilding objects +when the serialized layout changes. Retain/validate summaries for the exact +objects being linked, not cached descriptions of older builds. + +## Program entry and other boundaries + +Program startup is another CLInitNode on the starting class. In a fresh runtime +image with a dynamic starting class, its `$init` is known false, so the check +folds to the initial `` call. The starting class sets its own bit just +like every other class; there is no adapter-specific flag store or protocol. +A proven fully static starting class needs no dynamic initialization call. + +The current file `` can receive `arg` and return a program/test result. +Preserve those arguments and the call result on the known-first-call startup +path. Ordinary class-use checks need only control and memory; they do not need +to cache or invent a result for the skip path. For fully static startup, the +program result must also be available as a constant or retained computation; +static object contents alone do not prove the entry computation unnecessary. +Existing tests executing file code with different arguments use independent +runtime images, not a reset of an already initialized class. The startup fact +must not be reused for an arbitrary native entry into a live image. + +Own-initializer helper calls and construction of a special instance during +class initialization need an explicit definite-initialization proof. Do not +carry forward the old module notes' unrestricted “golden instance” exception. +Initially reject cases that would publish or inspect unfinished class state. + +## Native handoff + +Native callers are not required to understand or explicitly run Simple class +initialization. The compiler/runtime must establish initialization before +exposing a supported value, or reject an unsupported handoff. + +For the first implementation, reject passing a class object or raw `` +function to native code, including through a class-to-address conversion. +Do not confuse these with an ordinary function pointer obtained by a checked +field access: loading `ary.copy` already initializes `ary`, so that value does +not need a new initialization wrapper when handed to native code, wherever the +ordinary FFI supports its signature. Initialization-time callbacks still need +the effect analysis described above; an uninitialized class cannot be hidden +behind a callback to evade cycle validation. + +Later, support a selected class value at the handoff point: + +```text +X = rand ? B : C // Passive class references +CLInit(selected class X) // Initialize the actual value being passed +libc.native(X) +``` + +Validate the initialization graph for all possible targets, B and C, including +their parents and transitive requirements, regardless of the selected value. +At runtime initialize only the selected target before the native call. This +can lower to checks on the corresponding control-flow arms, or dispatch on a +known target identity. The plan's initial CLInitNode has a fixed class identity; +this dynamic selection is a later extension, not an assumed existing facility. + +Initializing every possible target before handoff is an alternative policy, +but it runs effects for the unselected class. Prefer the selected-target form +to retain the rule that untouched classes run no code. Unknown target sets or +native traversal to further uninitialized class objects require additional +analysis; initializing just X is not a blanket proof for everything reachable +through X. Until supported, reject the handoff rather than transferring that +responsibility to native code. + +A native call directly to an exported symbol, without a preceding Simple +handoff, likewise needs compiler/runtime initialization support. Its eventual +export/startup mechanism is deferred; it must not require the native caller to +invoke ``. Existing native-linking tests are not evidence that this +future initialization guarantee is already implemented. + +## Implementation sequence and validation + +1. Add ClassInit identities and a distinct lazy dependency collection; preserve + passive class references. Add direct/function effect summaries and cycle + diagnostics, including unresolved external-call handling. +2. Serialize/load the directory and summaries. Validate combined graphs before + imported-body unlinking and at final composition. Preserve ordinary function + entries; establish startup handling and diagnostics for unsupported native + handoffs before claiming initialization coverage at the FFI boundary. +3. Add serializable CLInitNode IR, the hidden field in each class object, and + the flag Store in ``. Use the same node for ordinary checks and + startup. Add parser flow tracking and the basic constant/dominating-check + peepholes as part of this implementation, rather than relying on a later + cleanup pass to remove every repeated check. +4. Refine flow proofs and fully-static classification. Extend constant-memory + lowering only with the required observation/identity proofs. + +Validation should cover the actual boundaries, with a small number of focused +fixtures: parent-before-child order; an untouched branch performing no I/O; +two callers executing one initializer once; direct, indirect, sibling and +cross-module cycle rejection; passive/static reference cycles; a shared class +and flag reached through two separately compiled importers; a join/loop where +the first check cannot be removed; and rejection of unsupported native class +handoffs. Check function-pointer acquisition at the class field, with no new +ordinary function wrapper. Check parser omission and ideal elimination separately: a dominating +check, a true-test branch, an unchecked merge arm, and a zero-trip loop. Verify +one body-owned flag store before inlining, and that folding its early true +value cannot hide a cycle or bypass field initialization checks. Preserve entry +arguments/results and verify after serialization reload. +Run existing Chapter 25 suites and ARM/RISC/native execution checks for each +implementation frontier. No earlier-chapter backport is implied by this design. + +## Module goals retained from the old notes + +Keep one-line programs easy to compile/run, filesystem-based nested namespaces, +leading-underscore privacy, separate compilation without source include files, +and ordinary object-file/native-linker interoperability. Classes may be declared +within a file or supplied by nested files. Source and object builds must have +the same initialization semantics. The current CLI is documented in the +[chapter README](README.md); historical command examples and conflicting +initializer-order proposals are superseded by this design. diff --git a/docs/chapter25/lattice.gv b/docs/chapter25/lattice.gv new file mode 100644 index 00000000..8661082d --- /dev/null +++ b/docs/chapter25/lattice.gv @@ -0,0 +1,203 @@ +digraph Lattice { + compound = true; + // Define nodes + splines=false; + node [shape=circle, style=filled]; + nodesep=0.2; + ranksep=0.2; + + TOP [label=<⊤>, fillcolor=black, fontcolor=white]; + BOT [label=<⊥>, fillcolor=black, fontcolor=white]; + + // ---------------------- + // Control + XCTRL [label=<⊤:ctrl>, fillcolor=yellow, shape=oval]; + CTRL [label=<⊥:ctrl>, fillcolor=yellow, shape=oval]; + + TOP -> XCTRL; + XCTRL -> CTRL; + CTRL -> BOT; + + // ---------------------- + // Integers + INT_TOP [label=<⊤:int>, fillcolor=lightblue, shape=oval]; + INT_BOT [label=<⊥:int>, fillcolor=lightblue, shape=oval]; + + INT_HI [label="[min>max]" , fillcolor=lightblue, shape=oval]; + INT_XBOOL [label="[1...0]", fillcolor=lightblue, shape=oval]; + INT_CON [label="constants", fillcolor=lightblue, shape=oval]; + INT_CON0 [label="0", fillcolor=lightblue]; + INT_CON1 [label="1", fillcolor=lightblue]; + INT_BOOL [label="[0...1]", fillcolor=lightblue,shape=oval]; + INT_LO [label="[min INT_TOP; + INT_TOP -> INT_HI; + INT_HI -> INT_XBOOL; + INT_XBOOL -> INT_CON0; + INT_XBOOL -> INT_CON1; + INT_HI -> INT_CON; + INT_CON0 -> INT_BOOL; + INT_CON1 -> INT_BOOL; + INT_BOOL -> INT_LO; + INT_CON -> INT_LO; + INT_LO -> INT_BOT; + INT_BOT -> BOT; + + INT_CON0 -> INT_CON1 -> INT_CON [style=invis]; + + // ---------------------- + // Floats + FLT_TOP [label=<⊤:flt>, fillcolor=aqua, shape=oval]; + FLT_BOT [label=<⊥:flt>, fillcolor=aqua, shape=oval]; + + FLT_CON64 [label="64b consts\n[excludes\n32b consts]" , fillcolor=aqua, shape=oval]; + FLT_CON32 [label="32b consts", fillcolor=aqua, shape=oval]; + FLT_CONPI [label="3.14159...", fillcolor=aqua, shape=oval]; + FLT_X32 [label="~f32", fillcolor=aqua]; + FLT_CON0 [label="0." , fillcolor=aqua]; + FLT_32 [label="f32" , fillcolor=aqua]; + + TOP -> FLT_TOP; + FLT_TOP -> FLT_CON64 + FLT_TOP -> FLT_CONPI + FLT_CON64 -> FLT_BOT + FLT_CONPI -> FLT_BOT + + FLT_TOP -> FLT_X32; + FLT_X32 -> FLT_CON0; + FLT_X32 -> FLT_CON32; + FLT_CON0 -> FLT_32; + FLT_CON32 -> FLT_32; + FLT_32 -> FLT_BOT + + FLT_BOT -> BOT; + + FLT_CON0 -> FLT_CON32 -> FLT_CONPI -> FLT_CON64 [style=invis]; + + + // ---------------------- + // Pointers, just a boolean nil/not and a struct + PTR [shape=none, fillcolor=none, label=< + + + +
*ptr
struct
+ >]; + PTR0 [shape=none, fillcolor=none, label=< + + + +
*ptr?
struct
+ >]; + + TOP -> PTR; + PTR -> PTR0; + PTR0 -> BOT; + + // ---------------------- + // Structs + STRUCT_TOP [label=<⊤:struct>, fillcolor=lightgreen, shape=oval]; + STRUCT_BOT [label=<⊥:struct>, fillcolor=lightgreen, shape=oval]; + + STRUCT_S1 [shape=none, fillcolor=none, label=< + + +
fieldint/ptr
+ >]; + STRUCT_S2 [shape=none, fillcolor=none, label=< + + + +
fieldint/ptr
fieldint/ptr
+ >]; + STRUCT_SN [shape=none, fillcolor=none, label=< + + + + +
fieldint/ptr
... int/ptr
fieldint/ptr
+ >]; + + + TOP -> STRUCT_TOP; + STRUCT_TOP -> STRUCT_S1; + STRUCT_TOP -> STRUCT_S2; + STRUCT_TOP -> STRUCT_SN; + STRUCT_S1 -> STRUCT_BOT; + STRUCT_S2 -> STRUCT_BOT; + STRUCT_SN -> STRUCT_BOT; + STRUCT_BOT -> BOT; + + STRUCT_S1 -> STRUCT_S2 -> STRUCT_SN [style=invis]; + + // ---------------------- + // Memory + MEM_TOP [label=<⊤:mem>, fillcolor=blue, fontcolor=white, shape=oval]; + MEM_BOT [label=<⊥:mem>, fillcolor=blue, fontcolor=white, shape=oval]; + MEM_ALIAS1 [label="#1" , fillcolor=blue, fontcolor=white]; + MEM_ALIASDOTS [label="..." , fillcolor=blue, fontcolor=white, shape=oval]; + MEM_ALIASN [label="#n" , fillcolor=blue, fontcolor=white]; + + TOP -> MEM_TOP; + MEM_TOP -> MEM_ALIAS1; + MEM_TOP -> MEM_ALIASDOTS; + MEM_TOP -> MEM_ALIASN; + MEM_ALIAS1 -> MEM_BOT; + MEM_ALIASDOTS -> MEM_BOT; + MEM_ALIASN -> MEM_BOT; + MEM_BOT -> BOT; + + MEM_ALIAS1 -> MEM_ALIASDOTS -> MEM_ALIASN [style=invis]; + + // ---------------------- + // Tuples + + TUPLE_TOP [label=<⊤:tuple>, fillcolor=pink, shape=oval]; + TUPLE_BOT [label=<⊥:tuple>, fillcolor=pink, shape=oval]; + + TUPLE1 [shape=none, fillcolor=none, label=< + + + +
Tuple
type
+ >]; + TUPLE2 [shape=none, fillcolor=none, label=< + + + + +
Tuple
type
type
+ >]; + TUPLEN [shape=none, fillcolor=none, label=< + + + + + +
Tuple
type
...
type
+ >]; + + + TOP -> TUPLE_TOP; + TUPLE_TOP -> TUPLE1; + TUPLE_TOP -> TUPLE2; + TUPLE_TOP -> TUPLEN; + TUPLE1 -> TUPLE_BOT; + TUPLE2 -> TUPLE_BOT; + TUPLEN -> TUPLE_BOT; + TUPLE_BOT -> BOT; + + // ---------------------- + // Additional customization + {rank=same; TOP;} + {rank=same; INT_TOP; FLT_TOP; XCTRL; PTR; STRUCT_TOP; MEM_TOP; TUPLE_TOP} + {rank=same; INT_CON; INT_CON0; INT_CON1; + FLT_CON32; FLT_CON64; FLT_CON0; FLT_CONPI; + STRUCT_S1; STRUCT_S2; STRUCT_SN; + MEM_ALIAS1; MEM_ALIASDOTS; MEM_ALIASN; + TUPLE1; TUPLE2; TUPLEN; + } + {rank=same; INT_BOT; FLT_BOT; CTRL; PTR0; STRUCT_BOT; MEM_BOT; TUPLE_BOT} + {rank=same; BOT;} +} diff --git a/docs/chapter25/lattice.svg b/docs/chapter25/lattice.svg new file mode 100644 index 00000000..e72b473b --- /dev/null +++ b/docs/chapter25/lattice.svg @@ -0,0 +1,691 @@ + + + + + + +Lattice + + + +TOP + +⊤ + + + +XCTRL + +⊤ +:ctrl + + + +TOP->XCTRL + + + + + +INT_TOP + +⊤ +:int + + + +TOP->INT_TOP + + + + + +FLT_TOP + +⊤ +:flt + + + +TOP->FLT_TOP + + + + + +PTR + + + +*ptr + + +struct + + + +TOP->PTR + + + + + +STRUCT_TOP + +⊤ +:struct + + + +TOP->STRUCT_TOP + + + + + +MEM_TOP + +⊤ +:mem + + + +TOP->MEM_TOP + + + + + +TUPLE_TOP + +⊤ +:tuple + + + +TOP->TUPLE_TOP + + + + + +BOT + +⊥ + + + +CTRL + +⊥ +:ctrl + + + +XCTRL->CTRL + + + + + +CTRL->BOT + + + + + +INT_HI + +[min>max] + + + +INT_TOP->INT_HI + + + + + +INT_BOT + +⊥ +:int + + + +INT_BOT->BOT + + + + + +INT_XBOOL + +[1...0] + + + +INT_HI->INT_XBOOL + + + + + +INT_CON + +constants + + + +INT_HI->INT_CON + + + + + +INT_CON0 + +0 + + + +INT_XBOOL->INT_CON0 + + + + + +INT_CON1 + +1 + + + +INT_XBOOL->INT_CON1 + + + + + +INT_LO + +[min<max] + + + +INT_CON->INT_LO + + + + + + +INT_BOOL + +[0...1] + + + +INT_CON0->INT_BOOL + + + + + + +INT_CON1->INT_BOOL + + + + + +INT_BOOL->INT_LO + + + + + +INT_LO->INT_BOT + + + + + +FLT_CON64 + +64b consts +[excludes +32b consts] + + + +FLT_TOP->FLT_CON64 + + + + + +FLT_CONPI + +3.14159... + + + +FLT_TOP->FLT_CONPI + + + + + +FLT_X32 + +~f32 + + + +FLT_TOP->FLT_X32 + + + + + +FLT_BOT + +⊥ +:flt + + + +FLT_BOT->BOT + + + + + +FLT_CON64->FLT_BOT + + + + + +FLT_CON32 + +32b consts + + + + +FLT_32 + +f32 + + + +FLT_CON32->FLT_32 + + + + + +FLT_CONPI->FLT_BOT + + + + + + +FLT_X32->FLT_CON32 + + + + + +FLT_CON0 + +0. + + + +FLT_X32->FLT_CON0 + + + + + + +FLT_CON0->FLT_32 + + + + + +FLT_32->FLT_BOT + + + + + +PTR0 + + + +*ptr? + + +struct + + + +PTR->PTR0 + + + + + +PTR0->BOT + + + + + +STRUCT_S1 + + + +field + + + + + + + + +int/ptr + + + +STRUCT_TOP->STRUCT_S1 + + + + + +STRUCT_S2 + + + +field + + + + + + + + +int/ptr + + +field + + + + + + + + +int/ptr + + + +STRUCT_TOP->STRUCT_S2 + + + + + +STRUCT_SN + + + +field + + + + + + + + +int/ptr + + +...   + + + + + + + + +int/ptr + + +field + + + + + + + + +int/ptr + + + +STRUCT_TOP->STRUCT_SN + + + + + +STRUCT_BOT + +⊥ +:struct + + + +STRUCT_BOT->BOT + + + + + +STRUCT_S1->STRUCT_BOT + + + + + + +STRUCT_S2->STRUCT_BOT + + + + + + +STRUCT_SN->STRUCT_BOT + + + + + +MEM_ALIAS1 + +#1 + + + +MEM_TOP->MEM_ALIAS1 + + + + + +MEM_ALIASDOTS + +... + + + +MEM_TOP->MEM_ALIASDOTS + + + + + +MEM_ALIASN + +#n + + + +MEM_TOP->MEM_ALIASN + + + + + +MEM_BOT + +⊥ +:mem + + + +MEM_BOT->BOT + + + + + +MEM_ALIAS1->MEM_BOT + + + + + + +MEM_ALIASDOTS->MEM_BOT + + + + + + +MEM_ALIASN->MEM_BOT + + + + + +TUPLE1 + + + +Tuple + + +type + + + +TUPLE_TOP->TUPLE1 + + + + + +TUPLE2 + + + +Tuple + + +type + + +type + + + +TUPLE_TOP->TUPLE2 + + + + + +TUPLEN + + + +Tuple + + +type + + +... + + +type + + + +TUPLE_TOP->TUPLEN + + + + + +TUPLE_BOT + +⊥ +:tuple + + + +TUPLE_BOT->BOT + + + + + +TUPLE1->TUPLE_BOT + + + + + +TUPLE2->TUPLE_BOT + + + + + +TUPLEN->TUPLE_BOT + + + + + diff --git a/docs/chapter25/lattice2.gv b/docs/chapter25/lattice2.gv new file mode 100644 index 00000000..6aa37fa0 --- /dev/null +++ b/docs/chapter25/lattice2.gv @@ -0,0 +1,85 @@ +digraph Lattice { + compound = true; + // Define nodes + splines=false; + node [shape=oval, style=filled]; + nodesep=0.2; + ranksep=0.4; + + TOP [label="~scalar\n+int+tmp+0", fillcolor=black, fontcolor=white, group=center]; + + // ------------------------ + PTRHQ [label="~tmp\n+tmp+0", fillcolor=green, fontcolor=white, group=left]; + TOP -> PTRHQ + + VALH_ [label="~nscalar\n+int+tmp", fillcolor=white, group=center]; + TOP -> VALH_ + + INTHQ [label="~int\n+int+0", fillcolor=lightblue, group=right]; + TOP -> INTHQ + + LEFTHI [label="junk", style=invis, group=junkleft] + + + PTRHQ -> LEFTHI-> VALH_ -> INTHQ [style=invis]; + { rank=same; PTRHQ; LEFTHI; VALH_; INTHQ } + + // ------------------------ + PTRH_ [label="~ntmp\n+tmp", fillcolor=green, fontcolor=white, group=left]; + VALH_ -> PTRH_ + PTRHQ -> PTRH_ + + INTH_ [label="~nint\n+int", fillcolor=lightblue, group=right]; + VALH_ -> INTH_ + INTHQ -> INTH_ + { rank=same; PTRH_; INTH_ } + + // ------------------------ + NILX_ [label="~nil\n[int,tmp]+0", fillcolor=aqua, group=junkleft]; + INTHQ -> NILX_ + PTRHQ -> NILX_ + + NIL__ [label="nil\n[+int+tmp],0", fillcolor=pink]; + VALH_ -> NIL__; + + NILX_ -> NIL__ [style=invis]; + { rank=same; NIL__; NILX_ } + + // ------------------------ + PTRL_ [label="ntmp\ntmp", fillcolor=green, fontcolor=white, group=left]; + PTRH_ -> PTRL_ + + INTL_ [label="nint\nint", fillcolor=lightblue, group=right]; + INTH_ -> INTL_ + { rank=same; PTRL_; INTL_ } + + // ------------------------ + PTRL0 [label="tmp\ntmp,0", fillcolor=green, fontcolor=white, group=left]; + PTRL_ -> PTRL0 + NIL__ -> PTRL0 + + VALL_ [label="nscalar\nint,tmp", fillcolor=white, group=center]; + PTRL_ -> VALL_ + INTL_ -> VALL_ + NILX_ -> VALL_ + + INTL0 [label="int\nint,0", fillcolor=lightblue, group=right]; + INTL_ -> INTL0 + NIL__ -> INTL0 + + PTRL0 -> VALL_ -> INTL0 [style=invis]; + { rank=same; PTRL0; VALL_; INTL0 } + + // ------------------------ + BOT [label="scalar\nint,tmp,0", fillcolor=black, fontcolor=white, group=center]; + PTRL0 -> BOT + INTL0 -> BOT + VALL_ -> BOT + + // ------------------------ + // Verticle alignment + TOP -> VALH_ -> VALL_ -> BOT [style=invis]; + PTRHQ -> PTRH_ -> PTRL_ -> PTRL0 [style=invis]; + INTHQ -> INTH_ -> INTL_ -> INTL0 [style=invis]; + LEFTHI -> NILX_ [style=invis] +} diff --git a/docs/chapter25/lattice2.svg b/docs/chapter25/lattice2.svg new file mode 100644 index 00000000..8b682aa7 --- /dev/null +++ b/docs/chapter25/lattice2.svg @@ -0,0 +1,260 @@ + + + + + + +Lattice + + + +TOP + +~scalar ++int+tmp+0 + + + +PTRHQ + +~tmp ++tmp+0 + + + +TOP->PTRHQ + + + + + +VALH_ + +~nscalar ++int+tmp + + + +TOP->VALH_ + + + + + + +INTHQ + +~int ++int+0 + + + +TOP->INTHQ + + + + + + + +PTRH_ + +~ntmp ++tmp + + + +PTRHQ->PTRH_ + + + + + + +NILX_ + +~nil +[int,tmp]+0 + + + +PTRHQ->NILX_ + + + + + + +VALH_->PTRH_ + + + + + +INTH_ + +~nint ++int + + + +VALH_->INTH_ + + + + + +NIL__ + +nil +[+int+tmp],0 + + + +VALH_->NIL__ + + + + + +VALL_ + +nscalar +int,tmp + + + + +INTHQ->INTH_ + + + + + + +INTHQ->NILX_ + + + + + + + +PTRL_ + +ntmp +tmp + + + +PTRH_->PTRL_ + + + + + + +INTL_ + +nint +int + + + +INTH_->INTL_ + + + + + + + +NILX_->VALL_ + + + + + +PTRL0 + +tmp +tmp,0 + + + +NIL__->PTRL0 + + + + + +INTL0 + +int +int,0 + + + +NIL__->INTL0 + + + + + +PTRL_->PTRL0 + + + + + + +PTRL_->VALL_ + + + + + +INTL_->VALL_ + + + + + +INTL_->INTL0 + + + + + + + +BOT + +scalar +int,tmp,0 + + + +PTRL0->BOT + + + + + + +VALL_->BOT + + + + + + +INTL0->BOT + + + + + diff --git a/docs/chapter25/pardoe.docx b/docs/chapter25/pardoe.docx new file mode 100644 index 00000000..24fde921 Binary files /dev/null and b/docs/chapter25/pardoe.docx differ diff --git a/docs/chapter25/webtcp.min.js b/docs/chapter25/webtcp.min.js new file mode 100644 index 00000000..bf23ee5a --- /dev/null +++ b/docs/chapter25/webtcp.min.js @@ -0,0 +1,65 @@ +function Http(j){this.cID=Math.random().toString(36).substr(2);this.webtcp=j;this.webtcp.httpClients[this.cID]=this;this.createPacket=function(){return{cID:this.cID,type:"http",host:this.remoteAddress,port:this.remotePort,method:null,data:null}};this.ondata=function(){};this.get=function(g,c){this.on("data",c);this.rpc("httpGet",[g])};this.post=function(g,c,j){this.on("data",j);this.rpc("httpPost",[g,c])}}Http.prototype=new WebTCPIO;function Socket(j,g,c,p){this.sID=Math.random().toString(36).substr(2);this.webtcp=j;this.closed=this.ready=!1;this.options=p;this.sockOpts={_updating:!1};this.remoteAddress=g;this.remotePort=c;this.webtcp.sockets[this.sID]=this;this.createPacket=function(){return{id:Math.random().toString(36).substr(2),sID:this.sID,type:"tcp",options:this.options,host:this.remoteAddress,port:this.remotePort,data:null}};this.onconnect=function(){this.webtcp.sockets[sID].ready=!0;this.webtcp.sockets[sID].closed=!1}; +this.ondata=function(){};this.onend=function(){};this.ontimeout=function(){};this.ondrain=function(){};this.onclose=function(){this.webtcp.sockets[sID].ready=!1;this.webtcp.sockets[sID].closed=!0};this.getSockOpts=function(){this.sockOpts._updating=!0;this.rpc("getSockOpts")};this.onSockOptsRcv=function(c){this.sockOpts=c;this.sockOpts._updating=!1}}Socket.prototype=new WebTCPIO;var JSON;JSON||(JSON={}); +(function(){function j(c,p){var q,t,n,x,i=k,e,l=p[c];l&&"object"==typeof l&&"function"==typeof l.toJSON&&(l=l.toJSON(c));"function"==typeof r&&(l=r.call(p,c,l));switch(typeof l){case "string":return g(l);case "number":return isFinite(l)?String(l):"null";case "boolean":case "null":return String(l);case "object":if(!l)return"null";k+=v;e=[];if("[object Array]"===Object.prototype.toString.apply(l)){x=l.length;for(q=0;qc?"0"+c:c}"use strict";"function"!=typeof Date.prototype.toJSON&&(Date.prototype.toJSON=function(){return isFinite(this.valueOf())?this.getUTCFullYear()+"-"+c(this.getUTCMonth()+1)+"-"+c(this.getUTCDate())+"T"+c(this.getUTCHours())+":"+c(this.getUTCMinutes())+":"+c(this.getUTCSeconds())+"Z":null},String.prototype.toJSON=Number.prototype.toJSON=Boolean.prototype.toJSON=function(){return this.valueOf()});var p=/[\u0000\u00ad\u0600-\u0604\u070f\u17b4\u17b5\u200c-\u200f\u2028-\u202f\u2060-\u206f\ufeff\ufff0-\uffff]/g, +n=/[\\\"\x00-\x1f\x7f-\x9f\u00ad\u0600-\u0604\u070f\u17b4\u17b5\u200c-\u200f\u2028-\u202f\u2060-\u206f\ufeff\ufff0-\uffff]/g,k,v,D={"\b":"\\b","\t":"\\t","\n":"\\n","\f":"\\f","\r":"\\r",'"':'\\"',"\\":"\\\\"},r;"function"!=typeof JSON.stringify&&(JSON.stringify=function(c,g,p){var n;v=k="";if("number"==typeof p)for(n=0;n=a};c.countRTO=function(a){var b;return 100b;b++)d.push(String.fromCharCode(b));B=(r.lastIndex=0,d.join("").replace(r,function(a){return c[a]="\\u"+("0000"+a.charCodeAt(0).toString(16)).slice(-4),""}),r.lastIndex=0,c)}a=a.replace(r,function(a){return B[a]})}return a};var q="websocket xdr-streaming xhr-streaming iframe-eventsource iframe-htmlfile xdr-polling xhr-polling iframe-xhr-polling jsonp-polling".split(" "); +c.probeProtocols=function(){for(var a={},b=0;b