diff options
| author | Cliff Click <cliffc@acm.org> | 2025-06-13 15:42:08 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2025-06-13 15:42:08 -0700 |
| commit | 0154c739b94d842898c36566c24e0f8b6d133951 (patch) | |
| tree | 8807e3fe457b5e8b7713cdb66ec538f9d9fde6a0 /chapter24 | |
| parent | ba789671e71d90c03cf7fa4246b7e3f7ea2bf48d (diff) | |
| download | Simple-0154c739b94d842898c36566c24e0f8b6d133951.tar.gz Simple-0154c739b94d842898c36566c24e0f8b6d133951.zip | |
Squashed commit of the following:
commit 2c31fa61d71fcbcf160edef5aba874913e63859a
Author: Cliff Click <cliffc@acm.org>
Date: Sat Jun 7 16:34:11 2025 -0700
README, comments
commit 8be23b15ad007509c9006a121328ce6615b912f6
Author: Cliff Click <cliffc@acm.org>
Date: Sat Jun 7 10:16:20 2025 -0700
Cleanup on sys ADT
BubbleSort looks cleaner
Cleanup recursive type handling
commit 145f977b53b3a9e89e984ae7af4bb3d8fd7768bb
Author: Cliff Click <cliffc@acm.org>
Date: Fri Jun 6 15:47:09 2025 -0700
More methods
Removing a Phi keeps mintype lifting until consumers no longer expect it. Load, Store, MemMerge all "peek" through mem Cast and MemMerge.
Bugfix, clone a constant near a required spill-use when passing constant stack arg.
Bugfix, missing dep when upgrading a type allows inlining.
Bugfix NegX86 is 2-adr
Bugfix, x86 cmp imm vs mem cannot swap args.
Bugfix, methods save/restore struct init values.
Bugfix, method vars can be set.
Repeat psudo-optimistic pass removing dead calls (tree shaking).
Add basic lib calls for Vectors for i64 and u8.
commit 04953c112a83de6127b6b2058a4bfbc344a3a02b
Author: Cliff Click <cliffc@acm.org>
Date: Tue Jun 3 15:58:03 2025 -0700
improve BubbleSort
Bugfix uctrlSkipEmpty did not stop at Calls.
Bugfix Phi skip mem alias uses 1 as default mem.
Bugfix cyclic install uses uniform walking method to catch all cases.
Drop % to mark static methods. Methods are static when not using the 'self' argument.
Encoding records when it inserts function header padding, so the ASMPrinter gets offsets right.
Encoding improve BB layout other things being equal.
commit f42903ff30c533a78adfdc43407da29711a83ad9
Author: Cliff Click <cliffc@acm.org>
Date: Mon Jun 2 09:31:09 2025 -0700
Methods
Block scoping now carries more Kind info, including constructor Type; fold Kind and lexSize info together.
Static calls need extra syntax `{% args ->body }`
Mem Phis more precise minType.
Mem Phi peeks through MemMerge.
TypeMem BOT/TOP alias is now#1 to match the Parsers notion of "all mem".
Missing dep.
Eval2 constant array bugfix.
commit aeb0a01e27e63ff6f8a2399523aa9f5922643d17
Author: Cliff Click <cliffc@acm.org>
Date: Sat May 31 14:55:11 2025 -0700
READMEs
commit dc1afb8d65a35e90b6495bd6dbaaf8d0d0149569
Author: Cliff Click <cliffc@acm.org>
Date: Sat May 31 11:43:09 2025 -0700
Cyclic types!
Handle cyclic types: thats that indirectly through a chain of types, point back to themselves. Make all type walkers cycle-aware. New cyclic-aware versions of hash and eq. In addition to hash-consing/interning types, also recycle allocated-but-interned types. Hash-consing has a 99.9% hit rate, so nearly all created types intern, and get recycles. This keeps the total count of types low (by 1000x) which keeps the type UID low, which keeps bit vectors for cyclic type walkers fast.
Move TypeStruct._con field into the normal array body field "[]".
Rename Field._type to Field._t to avoid shadowing prior _type field.
commit fc6f6277e18fcf30f3770698572c307fc0913132
Author: Cliff Click <cliffc@acm.org>
Date: Sun May 25 10:06:06 2025 -0700
Progress on cyclic types
Types can reset between tests.
Rename Phi _declaredType to _minType. Lifts to min type.
Broken CFG can have null idom
Field offsets by name only, can be delayed even more.
Bug dying FunNode looks "inProgress"
Move sys.smp to smp dir
commit d4544c2740f8effb2edd08293ca19382d4f0aa01
Author: Cliff Click <cliffc@acm.org>
Date: Sun May 25 09:57:51 2025 -0700
Move utils to a util directory
commit 9462acc2e8b200b499fe4308e3f6a3a6a2d8ac0b
Author: Cliff Click <cliffc@acm.org>
Date: Wed May 14 14:50:13 2025 -0700
Hitting self-recursive types
Changes for allowing locals to be non-const by default.
Changes to track `_one` single-ton fields that will get moved to a class.
Field offset constants; will become a real int constant once layout is determined, which waits until fields are decided to be in the class or instance; also if the field contents can be put in a smaller size.
commit a1f3a27146fa40cb85aef90934250cf5b77be736
Author: Cliff Click <cliffc@acm.org>
Date: Sun May 11 16:14:04 2025 -0700
Minor progress bug
commit f21ccb089f7963b76cae553ff948b8cc056b0b82
Author: Cliff Click <cliffc@acm.org>
Date: Sun May 11 15:28:35 2025 -0700
Ch 23 initial tests
commit 89131d2ffa145e6cdbba95abed9abb7989e6822f
Author: Cliff Click <cliffc@acm.org>
Date: Sun May 11 15:19:02 2025 -0700
First commit ch23
Diffstat (limited to 'chapter24')
| -rw-r--r-- | chapter24/README.md | 345 |
1 files changed, 345 insertions, 0 deletions
diff --git a/chapter24/README.md b/chapter24/README.md new file mode 100644 index 00000000..03056897 --- /dev/null +++ b/chapter24/README.md @@ -0,0 +1,345 @@ + + +## 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<str#; i++ ) + self = self.add(str[i]); + return self; + }; + + // Add an char to the string, possibly growing + val add = { u8 e -> + 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<len; i++ ) + v2[i] = [i]; + v2.len = len; + sys.libc.free(this); // Needs a better Mem Management solution + return v2; + }; + + val print { -> 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. +Add optimistic pass SCCP to `opto` +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 +} }; +``` |
