Backport lazy memory splits to ch10, split into ch10a and bch10ab

1 files changed, 100 insertions, 83 deletions

diff --git a/chapter10a/README.md b/chapter10a/README.md
index 64600fa0..2f25f681 100644
--- a/chapter10a/README.md
+++ b/chapter10a/README.md
@@ -10,10 +10,11 @@ same in 10a and 10b; the next chapter improves the memory representation.
 
 ## One memory value
 
-Arithmetic nodes depend on the values they use. A load also depends on when it
-observes memory. In this chapter every store consumes the preceding memory
-state and produces the next one. A load consumes memory without changing it.
-This makes the source program's effect ordering explicit in the graph.
+Arithmetic nodes depend on the values they use, similarly a load also depends
+on when it observes memory.  In this chapter every store consumes the preceding
+memory state and produces the next one, and a load consumes memory without
+changing it.  This makes the source program's memory ordering explicit in the
+graph.
 
 ```java
 struct Point { int x; int y; }
@@ -30,27 +31,23 @@ different fields are independent. Chapter 10b will remove it.
 
 ![One chain orders stores and loads](docs/example1.svg)
 
-These diagrams are schematic dependency graphs: arrows run from uses to their
-definitions. Pointer and value inputs are omitted where they do not explain ordering.
-
-| Node | Inputs | Result |
-|---|---|---|
-| `New` | Control and a struct type | A fresh, non-null object pointer |
-| `Store` | Memory, pointer, field name, value | The updated whole-memory state |
-| `Load` | Memory, pointer, field name | The value of the field |
-| `Start` | External entry | Control, initial memory, and `arg` |
+| Node     | Inputs | Result |
+|----------|---|---|
+| `New`    | Control and a struct type | A fresh, non-null object pointer |
+| `Store`  | Memory, pointer, field name, value | The updated whole-memory state |
+| `Load`   | Memory, pointer, field name | The value of the field |
+| `Start`  | External entry | Control, initial memory, and `arg` |
 | `Return` | Control, result, memory | Completion with all preceding effects retained |
 
-The memory edge is a dependency token, not a copy of the heap. In the evaluator,
-objects contain mutable field arrays; executing a Store changes an array entry.
-The graph determines the legal execution order.
+The memory edge is a dependency, not a copy of the heap.  The graph determines
+the legal execution order.  In hardware, a Store updates physical memory
+directly.  In the evaluator, a Store updates an objects' attached memory array.
 
 ## Memory is an SSA variable
 
 The parser keeps one hidden binding named `$mem`. Source identifiers cannot
 contain `$`, so user code cannot name it.  Reading and updating memory uses the
-same `ScopeNode` lookup and update operations as a local variable.  Start has a
-fixed tuple: control at index 0, memory at index 1, and `arg` at index 2.
+same `ScopeNode` lookup and update operations as a local variable.
 
 For an `if`, the two branches can finish with different memory values. An
 ordinary Phi selects the memory from the branch that executed:
@@ -88,69 +85,88 @@ optimization, not a correctness problem; it motivates the next chapter.
 
 The Type Lattice for Simple has a major revision in this chapter.
 
-![Graph1](./docs/lattice.svg)
-
-Within the Type Lattice, we now have the following type domains:
-
-* <font style="background-color:yellow">Control type</font> - represents control flow
-* <font style="background-color:lightblue">Integer type</font> - Integer values, with a Top, Bottom and constants
-* <font style="background-color:green" color="white">Pointer type</font> (new) - Represents a pointer to a struct type
-  * We use the prefix `*` to mean pointer-to.  Thus `*S1` means pointer to
-    `S1`, `*$TOP` means pointer to `$TOP`.
-  * `?` suffix represents the union of a pointer to some type and `null`.
-  * The pointer lattice has only 2 entries: null or not-null.  In both cases a struct lattice element is
-    included, and can be any member of the struct lattice.
-  * `null` is a pointer to non-existent memory object, i.e. `*$TOP?`, and is a
-    nullable.  Notice that the null part of the type is low in the lattice,
-    while the struct part is the highest struct.
-  * `*void` is a synonym for `*$BOT` - i.e. it represents a non-null pointer to
-    all possible struct types, akin to `void *` in C except not null.  It is
-    the inverse or *dual* of `null`, and the null part is high in the pointer
-    lattice, while the struct part is the lowest struct.
-  * `null` pointer evaluates to False and non-null pointers evaluate to True, as in C.
-
-* <font style="background-color:lightgreen">Struct type</font> (new) -
-  Represents user defined struct types, a struct type is allowed to have
-  members of Integer type only in this chapter, later chapters will expand
-  this.
-  * `⊤:struct` represents local Top for struct type; all we know about the type
-    is that it is a struct but, we do not know if it is a specific struct, or
-    all possible structs.  In the code, we use a struct with no fields named `$TOP`.
-  * `⊥:struct` represents local Bottom for struct type; we definitely know the
-    value can take all possible struct types.  In the code, we uise a struct
-    with no fields named `$BOT`.
-* <font style="background-color:blue" color="white">Memory type</font> (new) - Represents the whole-memory token
-  * `⊤:mem` is `TypeMem.TOP`, the high end of the memory domain.
-  * `⊥:mem` is `TypeMem.BOT`, our conservative type for the whole-memory state.
-  * Neither token describes the values stored in individual fields.
-* <font style="background-color:pink">Tuple type</font> - when a Node results in a collection of values
-
-We make use of following operations on the lattice.
-
-* The `meet` operation takes two types and computes the greatest lower bound
-  type.  While not true for all lattices, in the our lattice this can be
-  thought of as set union (ORing) of its input types (as sets).
-  * Example, meet of `*S1` and `*S2` results in `*void` - there is no lattice
-    element for exactly both `{*S1,*S2}`, so we drop down to the nearest
-    element containing both (and maybe more), which is `*void`.
-  * Meet of `*S1` and pointer `null` results in `*S1?`
-  * Meet of `*void` and `null` results in `*$BOT?`; bear in mind that `*void` is a synonym for `*$BOT`.
-  * Meet of `1` and `2` results in `Int Bot`.
-* The `dual` operation is symmetric across the lattice centerline.  Types directly on the centerline are their own dual.
-  * Find the corresponding node of the lattice after inverting the lattice.
-    * Thus, dual of `Top` is `Bot`.
-    * The dual of `*$TOP` is `*$BOT?`.
-  * For structs, the dual is obtained by computing the dual of each struct
-    member. Thus, dual of `*S1` is not `*S1?`, it is some `*S1?` with dualed
-    fields.
-
-* The `join` operation takes two types and computes the least upper bound type.
-  Similar to `meet` this can thought of as set intersection (ANDing) of its input types.
-  Because our lattice structure is symmetric and complete, we compute `join` with a well known identity:
-  `JOIN(x,y) === MEET(x.dual,y.dual).dual`
-  * Example, join of `*S1` and `*S2` results in `*$TOP`.
-  * Join of `1` and `2` results in `Int Top`.
-  * Join of `*void` and `Null` results in `*$TOP`.
+![Type lattice with six domains and parallel named struct alternatives](./docs/lattice.svg)
+
+The diagram uses `⊤` for **top** and `⊥` for **bottom**. A suffix names the
+domain: `⊤:struct` is *struct top*, while the bare `⊤` is global top. In the
+prose we use those words; in code examples we use the actual Java constants.
+The implementation's `$TOP` and `$BOT` names need not appear in the diagram:
+
+| Diagram | Prose | Java constant | Internal struct name |
+|---|---|---|---|
+| `⊤:struct` | struct top | `TypeStruct.TOP` | `$TOP` |
+| `⊥:struct` | struct bottom | `TypeStruct.BOT` | `$BOT` |
+
+Edges in this diagram show lattice order, with top above bottom. They are not
+the use-to-definition edges of the program graphs elsewhere in the chapter.
+Boxes containing an ellipsis abbreviate further parallel alternatives; they
+are not extra union types. Field and tuple-element type lattices are elided.
+
+Within the type lattice, we now have the following domains:
+
+* ![Control](docs/type-control.svg) represents control flow: unreachable control
+  at control top, and reachable control at control bottom.
+* ![Integer](docs/type-integer.svg) has integer top, integer bottom, and parallel
+  constants between them. The ellipses stand for the other integer constants.
+* ![Pointer](docs/type-pointer.svg) (new) combines a struct type with nullability.
+  * The prefix `*` means pointer-to: `*Person` is a non-null pointer to a Person.
+    The suffix `?` includes null, so `*Person?` permits a Person pointer or null.
+  * The pointer domain contains the whole struct lattice twice, once without
+    null and once with it. The diagram expands named alternatives in both
+    copies. It is not just two individual pointer types.
+  * `null` combines struct top with the nullable flag: it has no non-null
+    object alternative. The diagram labels it `*⊤:struct?` as well as `null`.
+  * A pointer to struct bottom can point to any struct. The diagram shows the
+    non-null form as `*⊥:struct` and the nullable form as `*⊥:struct?`.
+    The latter is pointer bottom; pointer top is `*⊤:struct`.
+  * Null evaluates to false; non-null pointers evaluate to true.
+
+  > C analogy: the non-null pointer to struct bottom is akin to `void *`, except
+  > that C's `void *` may also be null. Simple names this constant
+  > `TypeMemPtr.VOIDPTR` and prints it as `*void`. Struct bottom itself is the
+  > common lower bound of struct types, not C's `void` type.
+
+* ![Struct](docs/type-struct.svg) (new) represents user-defined named structs.
+  Fields have integer types in this chapter.
+  * Struct top lies above every named struct; struct bottom lies below every
+    named struct. Top is the high/empty struct alternative, while bottom
+    conservatively includes any struct name.
+  * `Person`, `s1`, `s2`, and further names are parallel alternatives. There is
+    no inheritance, so different named structs do not nest beneath one another,
+    even if they have identical fields.
+  * There is no fixed bound on the names a program can declare. The diagram's
+    ellipsis stands for more named alternatives, not a distinguished unnamed
+    struct. Each named box abbreviates its own field-type lattice.
+* ![Memory](docs/type-memory.svg) (new) represents the whole-memory token.
+  Memory top and memory bottom are `TypeMem.TOP` and `TypeMem.BOT`. Neither
+  records the values stored in individual fields.
+* ![Tuple](docs/type-tuple.svg) represents a collection of results from one node,
+  such as Start's control, memory, and argument. The displayed shapes abbreviate
+  tuples of different lengths and their element-type lattices.
+
+We use the following operations on the lattice:
+
+* **Meet** computes the greatest lower bound. For these examples, think of
+  combining the alternatives represented by its inputs.
+  * The meet of `Person` and `s1` is struct bottom. There is no separate type
+    representing exactly those two names.
+  * The meet of `*Person` and `*s1` is the non-null pointer to struct bottom.
+  * The meet of `*Person` and `null` is `*Person?`.
+  * The meet of the non-null pointer to struct bottom and `null` is pointer bottom.
+  * The meet of `1` and `2` is integer bottom.
+* **Dual** reflects the lattice about its centerline: top and bottom exchange
+  places, and applying dual twice returns the original type.
+  * Struct top and struct bottom are duals.
+  * `null` and the non-null pointer to struct bottom are duals.
+  * A pointer's dual also duals its struct's fields and flips nullability. Thus
+    the dual of `*Person` is not generally the original `*Person?`: the field
+    types must be dualed too. Those field details are omitted in the diagram.
+* **Join** computes the least upper bound. It is defined through meet and dual:
+  `JOIN(x,y) = MEET(x.dual(),y.dual()).dual()`.
+  * The join of `Person` and `s1` is struct top.
+  * The join of `*Person` and `*s1` is pointer top.
+  * The join of the non-null pointer to struct bottom and `null` is pointer top.
+  * The join of `1` and `2` is integer top.
 
 As we construct the Sea of Nodes graph, we ensure that values stay inside the
 domain they are created in - that is ptr fields will never contain ints
@@ -221,8 +237,9 @@ To enable this behaviour, we make following enhancements.
   predicate is a ptr value.  The up-cast removes the null possibility on the
   true branch making it legal to use the pointer.
 
-* The up-cast is done using a `Cast` op with the type `*void`.  This does a
-  lattice JOIN of the original type and `*void`.  This JOIN operation preserves
+* The up-cast uses a `Cast` with the non-null pointer to struct bottom
+  (`TypeMemPtr.VOIDPTR`). It joins the original pointer type with that type,
+  corresponding to `*⊥:struct` in the diagram. This JOIN operation preserves
   everything we already know about ptr, and also adds the new knowledge that
   the ptr is not-null.