From 2475516bee0ca64ffb1bff184e671db9b69bd617 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 21 Apr 2025 14:18:23 -0700 Subject: Chapter 22: A Hello, World! MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: godalming123 <68993177+godalming123@users.noreply.github.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> 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/chapter22/22-grammar.ja.md | 149 +++++++ docs/chapter22/22-grammar.md | 149 +++++++ docs/chapter22/Makefile | 12 + docs/chapter22/README.ja.md | 163 ++++++++ docs/chapter22/README.md | 220 ++++++++++ docs/chapter22/examples/A_helloWorld.smp | 3 + docs/chapter22/examples/BubbleSort.smp | 109 +++++ docs/chapter22/font-awesome-4.7.0.zip | Bin 0 -> 669808 bytes docs/chapter22/ifg_trim.pdf | Bin 0 -> 155190 bytes docs/chapter22/lattice.gv | 203 +++++++++ docs/chapter22/lattice.svg | 691 +++++++++++++++++++++++++++++++ docs/chapter22/lattice2.gv | 85 ++++ docs/chapter22/lattice2.svg | 260 ++++++++++++ docs/chapter22/pardoe.docx | Bin 0 -> 22583 bytes docs/chapter22/webtcp.min.js | 65 +++ 15 files changed, 2109 insertions(+) create mode 100644 docs/chapter22/22-grammar.ja.md create mode 100644 docs/chapter22/22-grammar.md create mode 100644 docs/chapter22/Makefile create mode 100644 docs/chapter22/README.ja.md create mode 100644 docs/chapter22/README.md create mode 100644 docs/chapter22/examples/A_helloWorld.smp create mode 100644 docs/chapter22/examples/BubbleSort.smp create mode 100644 docs/chapter22/font-awesome-4.7.0.zip create mode 100644 docs/chapter22/ifg_trim.pdf create mode 100644 docs/chapter22/lattice.gv create mode 100644 docs/chapter22/lattice.svg create mode 100644 docs/chapter22/lattice2.gv create mode 100644 docs/chapter22/lattice2.svg create mode 100644 docs/chapter22/pardoe.docx create mode 100644 docs/chapter22/webtcp.min.js (limited to 'docs') diff --git a/docs/chapter22/22-grammar.ja.md b/docs/chapter22/22-grammar.ja.md new file mode 100644 index 00000000..1813539f --- /dev/null +++ b/docs/chapter22/22-grammar.ja.md @@ -0,0 +1,149 @@ +# 第22章の文法 + +[English](22-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. +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 block ';' ; + +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. 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 : bitwiseExpression ('?' assignment (':' assignment)?)? ; + +bitwiseExpression + : comparisonExpression (('&' | '|' | '^') comparisonExpression)* + ; + +comparisonExpression + : 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 ; + +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)* ','? ; + +// Struct initialization uses a block; array allocation supplies a length. +newExpression : 'new' type ('[' assignment ']' | block)? ; + +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/chapter22/22-grammar.md b/docs/chapter22/22-grammar.md new file mode 100644 index 00000000..dfee11bd --- /dev/null +++ b/docs/chapter22/22-grammar.md @@ -0,0 +1,149 @@ +# Grammar for Chapter 22 + +English | [日本語](22-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. +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 block ';' ; + +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. 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 : bitwiseExpression ('?' assignment (':' assignment)?)? ; + +bitwiseExpression + : comparisonExpression (('&' | '|' | '^') comparisonExpression)* + ; + +comparisonExpression + : 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 ; + +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)* ','? ; + +// Struct initialization uses a block; array allocation supplies a length. +newExpression : 'new' type ('[' assignment ']' | block)? ; + +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/chapter22/Makefile b/docs/chapter22/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter22/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/chapter22/README.ja.md b/docs/chapter22/README.ja.md new file mode 100644 index 00000000..4ad6fae4 --- /dev/null +++ b/docs/chapter22/README.ja.md @@ -0,0 +1,163 @@ +# 第22章: Hello, World! + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第21章](../chapter21/README.ja.md) | +[次の章: 第23章](../chapter23/README.ja.md) + +そろそろ文字列と表示を扱う頃です。この章では基本的な文字列を作るために何が必要かを見ます。本格的な String クラスは、別の章まで待ちます。 + +```java +sys.io.p("Hello, World!"); +``` + +できました。1行の `Hello, World` です。この例は `examples/A_helloWorld.smp` にあります。 + +分解して見てみましょう。 + +- `sys`: 単なる変数名です。ほかの変数と同様、現在のスコープで検索します。そのスコープは完全に空に見えますが、今ではすべての Simple プログラムがスコープ内に `sys` 変数を持って始まります。`sys` 自体は普通の `struct` で、`src/main/smp/sys.smp` に定義されています。 +- `sys.io.p`: `sys` 構造体で `io` フィールドを検索すると `sys.io` 構造体が得られ、そこで `p`（print の略）を検索します。これによって関数を返します。 +- `p("Hello, World!")`: `p` フィールドからロードしたばかりの関数を、文字列引数 `"Hello, World!"` で呼び出します。 +- `"Hello, World!"`: `u8`（文字）の定数配列を生成する新しい構文です。それ以外は通常の範囲検査付き配列で、先頭に長さフィールド `#` があります。配列の実体データは、最終的に *定数プール*、そして ELF ファイルの RODATA セクションに入ります。 + +第11章の遅延メモリ分割はここでも続きます。パーサーは1つの `$mem` を保持し、BulkMemPhi/MemPhi が最適化中にフィールドのエイリアスを発見します。割り当ては部分的な MemMerge を消費し、`{ptr, $mem}` を生成します。Call はメモリ全体を運びます。ループ内の Load 検索はメモリマージのすべての枝をたどるので、BrainFuck の不変のプログラム長は主ループの外へ畳み込まれます。 + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチ上の直線的な Git リビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter22) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter21...linear-chapter22) することもできます。 + +この章の[完全な言語文法](22-grammar.ja.md)はこちらです。 + +## 入れ子の型と静的フィールド + +Simple は入れ子の型をサポートします。これは名前空間だけの変更で、新しい意味規則はなく、型定義を入れ子にできるだけです。 + +```java +struct Outer { + struct Inner { + int in; + flt pi = 3.14; + }; + int out; +}; +``` + +コンストラクタではなく宣言内で設定した final フィールドは、自動的に「静的」フィールドになります。すべてのインスタンスで final なので、各インスタンスに保存する必要がありません。代わりに大域領域に1つだけ保持し、そこからロードします。まだ本当の *クラス* オブジェクトではありません。 + +この例では: + +- `Outer` 構造体のインスタンスは、単一の `int` フィールド `out` を持ちます。 +- `Inner` 構造体のインスタンスは、単一の `int` フィールド `in` を持ちます。 +- 大域領域には、値 `3.14` の `Outer.Inner.pi` フィールドが存在します。 + +`sys` 構造体も、少なくとも入れ子の `libc` と `io` 構造体を持つ例です。これらの構造体のフィールドはすべて final なので静的です。 + +## FFI と I/O 呼び出し + +外部／FFI 関数を呼び出せるようになりました。ほかの変数と同様に宣言しますが、`"C"` を代入します。libc の `write` 呼び出しの束縛は次のとおりです。 + +`{ i32 fd, i64 buf, u32 len -> u32 } write = "C";` + +`"C"` を代入された final 変数は、外部で定義されたとみなします。同じ `"C"` 文字列の代入との曖昧さを避けるため、構文は少し変わるかもしれません。 + +正しいシグネチャや名前空間を取得するリンカのサポートはありません。リンク時に名前 `write` が一意である必要があります。 + +## 自動インポートと「sys.」名前空間 + +`sys` 構造体には `libc` 束縛と、表示やコレクションなどの既定ライブラリコードを含みます。この章の時点では、最小限の libc 束縛と簡単な表示があります。以下の抜粋は、上で使った部分を示します。 + +```java +// top-level default import +struct sys { + // libc bindings + /** https://www.man7.org/linux/man-pages/man2/.2.html */ + struct libc { + // fd buf len -> len + { i32 i64 u32 -> u32 } write = "C"; + // addr len prot flags fd off -> void* + { i64 i64 i32 i32 i32 i32 -> i64 } mmap = "C"; + // mmap flags + i32 PROT_EXEC = 4; + i32 PROT_READ = 1; + i32 PROT_WRITE= 2; + i32 PROT_NONE = 0; + i32 MAP_PRIVATE = 2; + i32 MAP_ANON = 32; + }; + struct io { + val p = { u8[~] str -> + i64 ptr = str; // cast array base to i64 + return sys.libc.write(1,ptr,str#); + }; + }; +}; +``` + +`sys` インポート自体は、ほかと同じ単なる `struct` です。内部にフィールド、代入、型を宣言します。これらの代入はすべて final で構造体宣言内にあるため、すべて *静的* フィールドであることに注意してください。 + +## ポインタから `i64` へのキャスト + +ポインタを i64 にキャストできるようになりました。ただし逆方向はできません。 +`i64 ptr = str; // cast array base to i64` + +配列の場合、長さフィールド `#` を飛ばした配列の *先頭* へのキャストであり、外部の「C」呼び出しへ渡すのに適しています。構造体の場合は単に構造体の先頭です。上の `sys.io.p` 関数では、長さ検査付き Simple 配列を libc の `write` 呼び出しへ渡すために使います。 + +## 定数の配列と定数配列 + +Simple の型システムは「定数配列」、すなわち固定された定数の配列をサポートします。ELF ファイルの RODATA セクションに保存します。現在、パーサーのレベルでは文字列だけをサポートします。`"Hello, World!"` は13個の ASCII バイトを含む `u8[13]` 配列を作ります。すべての配列と同様に長さがあり、どこかで範囲検査を受けます。 + +非定数配列の定数版は `u8[~]` 構文で代入できます。 + +```java +// Make a mutable array of ints +int N=4; +i32[] is = new i32[N]; +// Mutate the array +for( int i=0; i // Notice the [~] signature marking nums as immutable + int sum = 0; + for( int i=0; i u32 } write = "C";` + +Any final variable assigned as "C" will be considered defined externally. The +syntax of this might change slightly to avoid ambiguity with assigning the same +"C" string. + +There is no linker support for getting the correct signature or namespace; the +name `write` has to be unique when linking. + + +## Auto-Import and the "sys." namespace + +The `sys` struct includes `libc` bindings, and any default library code +including e.g. printing support and collections. As of this chapter it +includes minimal libc bindings and an easy print. This excerpt shows the +parts used above: + +```java +// top-level default import +struct sys { + // libc bindings + /** https://www.man7.org/linux/man-pages/man2/.2.html */ + struct libc { + // fd buf len -> len + { i32 i64 u32 -> u32 } write = "C"; + // addr len prot flags fd off -> void* + { i64 i64 i32 i32 i32 i32 -> i64 } mmap = "C"; + // mmap flags + i32 PROT_EXEC = 4; + i32 PROT_READ = 1; + i32 PROT_WRITE= 2; + i32 PROT_NONE = 0; + i32 MAP_PRIVATE = 2; + i32 MAP_ANON = 32; + }; + struct io { + val p = { u8[~] str -> + i64 ptr = str; // cast array base to i64 + return sys.libc.write(1,ptr,str#); + }; + }; +}; +``` + +The `sys` import itself is Just Another `struct` like any other struct; it has +fields and assignments and types declared internally. Note that these +assignments are all final and in the struct declaration, hence these are all +*static* fields. + + +## Casting a Pointer to an `i64` + +You can now cast a pointer to an i64, although not the other way around. +`i64 ptr = str; // cast array base to i64` + +For arrays, this cast is to the array *base* skipping the `#` length field, and +is suitable for passing to external "C" calls. For structs, this is just the +struct base. This is used to pass a length-checked Simple array to the libc +`write` call in the above `sys.io.p` function. + + +## Arrays of Constants and Constant Arrays + +The Simple type system now supports the notion of a "constant array" - an array +of fixed constants, stored in the ELF file in the RODATA section. Currently we +only support strings at the parser level: `"Hello, World!"` makes a `u8[13]` +array containing 13 ASCII bytes; like all arrays it has a length and will be +range-checked at some point. + +A constant version of a non-constant array can be assigned using the `u8[~]` +syntax. + +```java +// Make a mutable array of ints +int N=4; +i32[] is = new i32[N]; +// Mutate the array +for( int i=0; i // Notice the [~] signature marking nums as immutable + int sum = 0; + for( int i=0; i +| Test cohort | Cases D / X | Ch 20: Ops / RA / X | Ch 21: Ops / RA / X | Ch 22: Ops / RA / X | +|---|---:|---:|---:|---:| +| Ch 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | 58,751 / 9,099 / 175 | +| Ch 21 | 20 / 18 | | 6,207 / 261 / 461 | 6,324 / 379 / 475 | +| Ch 22 | 14 / 8 | | | 198 / 60 / 7 | + diff --git a/docs/chapter22/examples/A_helloWorld.smp b/docs/chapter22/examples/A_helloWorld.smp new file mode 100644 index 00000000..07ff935f --- /dev/null +++ b/docs/chapter22/examples/A_helloWorld.smp @@ -0,0 +1,3 @@ +// -*- mode: java; -*- +sys.io.p("Hello, World!"); +return 0; diff --git a/docs/chapter22/examples/BubbleSort.smp b/docs/chapter22/examples/BubbleSort.smp new file mode 100644 index 00000000..a491bd82 --- /dev/null +++ b/docs/chapter22/examples/BubbleSort.smp @@ -0,0 +1,109 @@ +// -*- mode: java; -*- + +// An implementation of +// https://sampleprograms.io/projects/bubble-sort/ +// +// Bubble sort, with reading (parsing) and writing (formatting) the data. + + +val _exit = { u8[~] msg -> + sys.io.p(msg); + sys.libc._exit(1); +}; + +val usage = { -> _exit("stdin must look like [4, 3, 2, 1]"); }; + +// Scanner +struct Scan { + int !x; + u8[~] buf; +}; + +// Skip whitespace +val skip = { !Scan s -> + while( s.buf[s.x] <= ' ' ) + s.x++; +}; + + +// Require specific syntax or usage +val require = { !Scan !s, u8 c -> + skip(s); + if( s.buf[s.x++] != c ) + usage(); +}; + +val peek = { !Scan !s, u8 c -> + skip(s); + if( s.buf[s.x] != c ) return false; + s.x++; + return true; +}; + +val number = { !Scan s -> + skip(s); + i32 n = 0; + while( '0' <= s.buf[s.x] & s.buf[s.x] <= '9' ) + n = n*10 + (s.buf[s.x++] - '0'); + return n; +}; + +val sort = { int[] ns, int len -> + var done = false; + while( !done ) { + done = true; + for( var i = 0; i < len-1; i++ ) + if( ns[i] > ns[i+1] ) { + int tmp = ns[i]; + ns[i] = ns[i+1]; + ns[i+1] = tmp; // Swap + done = false; + } + } +}; + +// Read from stdin a line of the form "[ 4, 3, 2, 1]" and print it sorted. +val main = { -> + !Scan !s = new Scan{ buf = sys.io.stdin(); }; + require(s,'['); + // Array of parsed results + int[] !ns = new int[16]; + i32 len = 0; + // Parse a list of numbers + if( !peek(s,']') ) { // Handle the empty list + // Parse "123, " until a something else + while( s.x < s.buf# ) { + int n = number(s); + ns[len++] = n; + if( !peek(s,',') ) + break; + }; + require(s,']'); // Close the list + } + + // Bubble sort array of integers + sort(ns,len); + + // Print a list of numbers + sys.io.p("[ "); + u8[] !junk = new u8[1]; + for( int i=0; i⊤>, 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/chapter22/lattice.svg b/docs/chapter22/lattice.svg new file mode 100644 index 00000000..e72b473b --- /dev/null +++ b/docs/chapter22/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/chapter22/lattice2.gv b/docs/chapter22/lattice2.gv new file mode 100644 index 00000000..6aa37fa0 --- /dev/null +++ b/docs/chapter22/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/chapter22/lattice2.svg b/docs/chapter22/lattice2.svg new file mode 100644 index 00000000..8b682aa7 --- /dev/null +++ b/docs/chapter22/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/chapter22/pardoe.docx b/docs/chapter22/pardoe.docx new file mode 100644 index 00000000..24fde921 Binary files /dev/null and b/docs/chapter22/pardoe.docx differ diff --git a/docs/chapter22/webtcp.min.js b/docs/chapter22/webtcp.min.js new file mode 100644 index 00000000..bf23ee5a --- /dev/null +++ b/docs/chapter22/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