From 664761624f4b0e3d6d1593b99e576854beec5949 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 6 May 2025 13:44:10 -0700 Subject: Chapter 23: Methods and Revisiting Types --- docs/chapter23/README.md | 458 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 458 insertions(+) create mode 100644 docs/chapter23/README.md (limited to 'docs/chapter23/README.md') diff --git a/docs/chapter23/README.md b/docs/chapter23/README.md new file mode 100644 index 00000000..946853f7 --- /dev/null +++ b/docs/chapter23/README.md @@ -0,0 +1,458 @@ +# Chapter 23: Methods and Revisiting Types + +In this chapter add *methods*, functions defined in structs which take a +hiddent `self` argument and can access the struct fields. Here is an +`indexOf` method in a String-like class: + +```java +// A String-like class, with methods +struct String { + u8[~] buf; // Buffer of read-only characters + + // Return the index of the first character 'c' or -1 + val indexOf = { u8 c -> // Hidden 'self' argument + for( int i=0; i int } indexOf; }` + +It is the type named `String` with a field `u8[~] buf` and a final assigned +constant field `indexOf`, itself with type `{ String self, u8 c -> int }`. +i.e., the type of `String` has a reference to itself, nested inside the type of +`indexOf`.... i.e. `String`'s type is *cyclic*. + + +## Less Cyclic Types + +This problem of cyclic types has been around for a long time, and there a +number of tried and true methods for dealing with them. One easy one is to +have a type *definition* and a separate type *reference*. The reference refers +to the type by doing some kind of lookup; an easy one is via the type name and +the parsers' symbol table i.e., some kind of hash table lookup. + +In this model the cycle is effectively avoided; all "back edges" in the cycle +are really done by the reference edge (itself possibly a hash table lookup). + +So why not go down this route? + +Because all type references lead back to the same type definition - which +means any specialization of type information is lost, because *all* type +references lead back to the same definition and you end up taking the MEET +over *all* paths. + +Here's example, a Linked List with a Java `Object` or a C `void*` payload: + +```java +struct List { + List next; + Object payload; // equivalently: void* +} +// Then walk a collection of ints and build a List: +List nums = null; +for( int x : ary_ints ) + nums = new List{next=nums; payload=x; } + +// Again for strings: +List strs = null; +for( String x : ary_strs ) + strs = new List{next=strs; payload=x; } +``` + +What is the type of `nums`? It's `*List`... which is: + +``` +struct List { List *next; Object payload } +``` + +No sharpening of `Object` to `int` nor `String` because every List object +has a payload of `Object` and `Object` MEET `int` is back to `Object`. + +It we allow truely cyclic types then in these kinds of places we can discover +(or infer) a sharper type: `*List { *List next, int payload }` +basically building up *generics* in the optimizer. This is not generics in the +language nor type-variables per-se, but it goes a long way towards them. + + +## Handling cyclic types + +In this Chapter Simple handles cyclic types directly. This means we have +`Type` objects whose child types can point back to the original - and that +means +[*recursive descent*](https://en.wikipedia.org/wiki/Recursive_descent_parser) +no longer works on Types. + +Up till now we've used recursive descent when building up Types: child types +are built first, then interned, then the interned children are used to build up +the next layer. Because each layer is interned and because recursive descent +stops at interned Types we avoid repeating work at shared Types. This makes +operations on the current Types linear in the *delta* between the old and new +Types, i.e. incremental and fast. + +With the new cyclic types we now run into the problem that we cannot intern a +cycle until we see the whole cycle. Also hash tables require an equality +check and we cannot use recursive descent to compare a cycle for equality. + +The standard way to deal with cycles in a graph is with some kind of *visited* +notion, a "I have been here before" indicator. We will use a hashtable keyed +from a unique type ID; "visited" just means your unique ID is a key in the +table. Every Type thus picks up a unique ID from a global counter. Since we +will be interning Types we only need as many unique IDs as we have unique Types +(plus a few spare to build and intern cycles). From prior history I know this +number is typically maxes out in the low thousands so a small integer will do. + +Another thing - we want to keep as much of the our existing infrastructure as +we can, so we are going to keep all our existing recursive descent visitations +with some small modifications. + +`TypeStructs` exist in every Type cycle (except pure function type cycles, +where a function takes *itself* as an argument, which are weird and we kinda +don't care how they get handled). So in the core part of every `TypeStruct` +generator we'll set an element in a global `VISIT` hashtable to signal the +start of a cyclic Type creation - and we'll check for those elements to stop +cycling. + + + + +Time for an example! + +Lets go with a linked list, where we might have cycles of unrelated payloads +(but here only strings). Might you, linked-list is almost always the wrong +structure for any given job (being wildly inefficent compared to easy +alternatives) but it is a great tutorial data structure. + + +```java +struct List { + List? !next; // Next pointer or null + str !name; // Payload +}; +``` + +And the type of this struct matches its declaration: + +`struct List { List*? next, str !name };` + +We can use this to build up a list of strings: + +```java +var list = new List{ name="Hello"; }; +list = new List { list, name="World"; }; +``` + + +### Checking a cyclic type for Read-Only / Final + +Suppose at some point we want to make a read-only immutable version: +```java +val hello = list; // Make a read-only version +print(hello); // Pass along the read-only version +``` + +What is the type of `hello`? It is the read-only type of `List`... and `List` is +a cyclic type. Lets look at `Type.makeRO`: + +```java +public final Type makeRO() { + if( isFinal() ) return this; // First check if already read-only + return recurOpen()._makeRO().recurClose(); +} +``` + +and `isFinal()`: + +```java +// Are all reachable struct Fields are final? +public final boolean isFinal() { return recurClose(recurOpen()._isFinal()); } +boolean _isFinal() { assert _type < TCYCLIC; return true; } +``` + +We call `recurOpen()` to start/open the recursive walk, do the recursion +calling `_isFinal()` and end/close the recursive walk, and return a boolean +answer. `_isFinal()` is NOT Java final, and is overridden in the Type subclasses. +Most subclasses just forward the problem along: + +`@Override boolean _isFinal() { return _obj._isFinal(); }` + +until we hit `TypeStruct`: + +```java +@Override boolean _isFinal() { + if( _open ) return false; // May have more more non-final fields + if( VISIT.containsKey(_uid) ) // Test: been here before? + return true; // Cycles assume final + VISIT.put(_uid,this); // Set: dont do this again + for( Field fld : _fields ) + if( !fld._isFinal() ) + return false; + return true; +} +``` + +Here we see a common pattern in dealing with cycles: the **test-and-set**. We +check for any hard and fast answers (open structs are never read-only; they are +only partially defined and as-yet-unparsed non-final fields may appear), then +we **test** if we have been here before, and if so stop the recursion and +return some kind of answer. For "isFinal" the returned answer is "yes final" +as long as everything else in the cycle is also final. + +If we have not already checked this Type, we **set** the "visit" bit indicating +we've been here before, and then proceed to do normal recursive-descent on the +fields asking the same question recursively. + +For our example, we open the recursion (set a sentinel in `VISIT`), call +`makeRO` on `struct List`, which then calls `_isFinal` which then checks +the `_open` flag (not open), checks the `VISIT` (not visited), sets the +UID in `VISIT`and starts walking the fields. Fields check: + +`@Override boolean _isFinal() { return _final && _t._isFinal(); }` + +The first field is `List*? !next`, which is not-final, so immediately returns +`false`, which stops `_isFinal` on `List` and the whole `isFinal()` call returns +`false`, and ends/closes the recursion (clears `VISIT`). + + +### Making a cyclic type for Read-Only / Final + +To make the build-then-intern more obvious, lets put unique IDs on all our +Types. Here is the Type of `List` with sample UIDs following each unique type. +Fields are also just types so also get UIDs. + +``` +struct List#2 { // struct List has UID#2 + List#2*?#3 !next#4, // Field next has UID#3, type ptr-or-null#3 to List#2 + str#1 !name#5 // Field name has UID#5, type str#1 +}; +``` + +You can see from the repeated UIDs that `List#2` happens twice... because List +is cyclic. + +Now we do really need to make a cyclic type, and so our `makeRO()` call falls +into the next line: + +`return recurOpen()._makeRO().recurClose();`. + +Once again `recurOpen` starts/opens our recursive walk, and then we call +`_makeRO()` which is overridden in every child Type class. Lets look at +`TypeStruct`s version: + +```java +// Make a read-only version +@Override TypeStruct _makeRO() { + // Check for already visited + TypeStruct ts = (TypeStruct)VISIT.get(_name); + if( ts!=null ) return ts; // Already visited + ts = recurPre(_name,_open); // Make a new type with blank fields + Field[] flds = ts._fields; + for( Field fld : flds ) fld._final = true; + + // Now start the recursion + for( int i=0; iB` should be equal to cycle `B<->A`. This +means they both need the same hashcode, and this means we cannot use +order-varying hashes! + +E.g. Suppose A has static hash value 1 (plus something recursively from B's +hash), and vice-versa B has static hash value 3 (and something recursive from +A), and we compute hashes as `parent.hash*7 + child.hash`. If we compute A's +hash as `A.hash * 7 + B.hash` we get `1 * 7 + 3 == 10`, and then later we start +from B we get: `B.hash * 7 + A.hash` and which then becomes `3 * 7 + 1 == +22`... and their hashes differ so the hash table might miss the equivalence. +Also, if we simply use recursive descent in the cycle we'll +recurse until stack overflow and crash. + +We fix this by having `TypeStruct.hash()` *not* recurse - thus its hash +function is somewhat weak, depending only on the field names and aliases. + +*Cyclic-equals* is triggered by the `VISIT` table being not-empty, and uses +another unrelated *visit* table, the `CEQUALS` table, to seperate concerns from +`VISIT`. The cycle-equals check proceeds like the normal `eq` with recursive +descent on the parts, and some up-front hard-and-fast static checks - and the +ubiquitous **test-and-set** pattern before the recursion. + +If we ever compare the same two types for cycle-equals again, we assume they +will be cycle-equals (all other things being equals). + + + +## Methods and Final Fields and Classes + +Methods are simply function values (final fields) declared inside a struct that +take an implicit `self` argument. + +Final fields declared in the original struct definition are *values* and cannot +change; they are the same for all instances. They get moved out of the +struct's memory footprint and into a *class* - a collection of values from the +final fields. Classes are just plain namespaces and have no concrete +implementation; they are not reified. + +```java +struct vecInt { + u32 !len; // Actual number of elements + int[] !buf; // Array of integers. + + // Since "add" is declared with `val` in the original struct definition, + // it is a final field and is moved out of here to the class. + + // Method: Add an element to a vector, possibly returning a new larger vector. + val add = { int e -> + if( len >= buf# ) _grow(buf#*2) + buf[len++] = e; + self; + }; + + // Method: Internal: copy buf to a new size + val _grow = { int sz -> + val buf2 = new int[sz]; + for( int i=0; i