Chapter 2: Arithmetic

Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Yichen Yan <oraluben@outlook.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>

15 files changed, 524 insertions, 26 deletions

diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index c2ea3734..f59b0f25 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -1,6 +1,9 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.graph.GraphObserver;
+
 import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
 
 /**
  * The Parser converts a Simple source program to the Sea of Nodes intermediate
@@ -11,6 +14,9 @@ import com.seaofnodes.simple.node.*;
  */
 public class Parser {
 
+    // Current compilation context; the observer belongs to the parser.
+    public static Parser PARSER;
+    public GraphObserver<Node> _obs;
     public int pos() { return _lexer._position; }
 
 
@@ -29,10 +35,13 @@ public class Parser {
 
     public Parser(String source) {
         _lexer = new Lexer(source);
+        PARSER = this;
         Node.reset();
         START = new StartNode();
     }
 
+    String src() { return new String( _lexer._input ); }
+
     public ReturnNode parse() {
         var ret = (ReturnNode) parseStatement();
         if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
@@ -60,20 +69,61 @@ public class Parser {
      * </pre>
      * @return an expression {@link Node}, never {@code null}
      */
-    private ReturnNode parseReturn() {
+    private Node parseReturn() {
         var expr = require(parseExpression(), ";");
-        return new ReturnNode(START, expr);
+        return new ReturnNode(START, expr).peephole();
     }
 
     /**
      * Parse an expression of the form:
      *
      * <pre>
-     *     expr : primaryExpr
+     *     expr : additiveExpr
      * </pre>
      * @return an expression {@link Node}, never {@code null}
      */
-    private Node parseExpression() {
+    private Node parseExpression() { return parseAddition(); }
+
+    /**
+     * Parse an additive expression
+     *
+     * <pre>
+     *     additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)*
+     * </pre>
+     * @return an add expression {@link Node}, never {@code null}
+     */
+    private Node parseAddition() {
+        var lhs = parseMultiplication();
+        if (match("+")) return new AddNode(lhs, parseAddition()).peephole();
+        if (match("-")) return new SubNode(lhs, parseAddition()).peephole();
+        return lhs;
+    }
+
+    /**
+     * Parse an multiplicativeExpr expression
+     *
+     * <pre>
+     *     multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)*
+     * </pre>
+     * @return a multiply expression {@link Node}, never {@code null}
+     */
+    private Node parseMultiplication() {
+        var lhs = parseUnary();
+        if (match("*")) return new MulNode(lhs, parseMultiplication()).peephole();
+        if (match("/")) return new DivNode(lhs, parseMultiplication()).peephole();
+        return lhs;
+    }
+
+    /**
+     * Parse a unary minus expression.
+     *
+     * <pre>
+     *     unaryExpr : ('-') unaryExpr | primaryExpr
+     * </pre>
+     * @return a unary expression {@link Node}, never {@code null}
+     */
+    private Node parseUnary() {
+        if (match("-")) return new MinusNode(parseUnary()).peephole();
         return parsePrimary();
     }
 
@@ -81,14 +131,14 @@ public class Parser {
      * Parse a primary expression:
      *
      * <pre>
-     *     primaryExpr : integerLiteral
+     *     primaryExpr : integerLiteral | Identifier | '(' expression ')'
      * </pre>
+     * @return a primary {@link Node}, never {@code null}
      */
     private Node parsePrimary() {
-        _lexer.skipWhiteSpace();
-        if (_lexer.isNumber())
-            return parseIntegerLiteral();
-        throw error("Syntax error, expected integer literal");
+        if( _lexer.isNumber() ) return parseIntegerLiteral();
+        if( match("(") ) return require(parseExpression(), ")");
+        throw errorSyntax("integer literal");
     }
 
     /**
@@ -99,7 +149,7 @@ public class Parser {
      * </pre>
      */
     private ConstantNode parseIntegerLiteral() {
-        return new ConstantNode(_lexer.parseNumber());
+        return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole();
     }
 
     //////////////////////////////////
@@ -149,6 +199,12 @@ public class Parser {
             _input = buf;
         }
 
+        // Very handy in the debugger, shows the unparsed program
+        @Override
+        public String toString() {
+            return new String(_input, _position, _input.length - _position);
+        }
+
         // True if at EOF
         private boolean isEOF() {
             return _position >= _input.length;
@@ -212,11 +268,11 @@ public class Parser {
         boolean isNumber() {return isNumber(peek());}
         boolean isNumber(char ch) {return Character.isDigit(ch);}
 
-        private long parseNumber() {
+        private Type parseNumber() {
             String snum = parseNumberString();
             if (snum.length() > 1 && snum.charAt(0) == '0')
                 throw error("Syntax error: integer values cannot start with '0'");
-            return Long.parseLong(snum);
+            return TypeInteger.constant(Long.parseLong(snum));
         }
         private String parseNumberString() {
             int start = _position;
@@ -249,5 +305,4 @@ public class Parser {
             return new String(_input, start, 1);
         }
     }
-
 }
diff --git a/src/main/java/com/seaofnodes/simple/Utils.java b/src/main/java/com/seaofnodes/simple/Utils.java
new file mode 100644
index 00000000..45f15327
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/Utils.java
@@ -0,0 +1,39 @@
+package com.seaofnodes.simple;
+
+import java.util.ArrayList;
+
+public class Utils {
+    public static RuntimeException TODO() { return TODO("Not yet implemented"); }
+    public static RuntimeException TODO(String msg) { return new RuntimeException(msg); }
+
+    /**
+     *  Fast, constant-time, element removal.  Does not preserve order
+     *
+     *  @param array ArrayList to modify
+     *  @param i element to be removed
+     *  @return element removed
+     */
+    public static <E> E del(ArrayList<E> array, int i) {
+        if ( i >= 0 && i < array.size() ) {
+            E tmp = array.get(i);
+            E last = array.removeLast();
+            if (i < array.size()) array.set(i, last);
+            return tmp;
+        }
+        return null;
+    }
+
+    /**
+     * Search a list for an element by reference
+     *
+     * @param ary List to search in
+     * @param x Object to be searched
+     * @return >= 0 on success, -1 on failure
+     */
+    public static <E> int find( ArrayList<E> ary, E x ) {
+        for( int i=0; i<ary.size(); i++ )
+            if( ary.get(i)==x )
+                return i;
+        return -1;
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java
new file mode 100644
index 00000000..94aa4fbb
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -0,0 +1,30 @@
+package com.seaofnodes.simple.node;
+
+
+import com.seaofnodes.simple.type.*;
+
+public class AddNode extends Node {
+    public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Add"; }
+
+    @Override protected String format() { return "(%1+%2)"; }
+
+
+    @Override
+    public Type compute() {
+        if( in(1)._type instanceof TypeInteger i0 &&
+            in(2)._type instanceof TypeInteger i1 ) {
+            if (i0.isConstant() && i1.isConstant())
+                return TypeInteger.constant(i0.value()+i1.value());
+        }
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize () {
+        // TODO: add of 0, and many other peepholes added in Chaper04
+        return null;
+    }
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 01d9cbe1..cc1db452 100644
--- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -1,6 +1,9 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.print.ExprPrinter;
+
 import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.Type;
 
 /**
  * A Constant node represents a constant value.  At present, the only constants
@@ -15,15 +18,28 @@ import com.seaofnodes.simple.Parser;
  * The Constant's value is the value stored in it.
  */
 public class ConstantNode extends Node {
+    final Type _con;
+    public ConstantNode( Type type ) {
+        super(Parser.START);
+        _con = type;
+    }
 
-    @Override public String label() { return "Con"; }
-    @Override protected String format() { return Long.toString(_value); }
-    @Override protected String repeatName() { return null; }
+    @Override protected String repeatName() {
+        return _con==null || _con.toString().length()<=32 ? null : uniqueName();
+    }
 
-    public final long _value;
+    @Override
+    public String label() { return "Con"; }
 
-    public ConstantNode(long value) {
-        super(Parser.START);
-        _value = value;
+
+    @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) {
+        return p.p(_con);
     }
+
+    @Override
+    public Type compute() { return _con; }
+
+    @Override
+    public Node idealize() { return null; }
+
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java
new file mode 100644
index 00000000..d1a554bc
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -0,0 +1,28 @@
+package com.seaofnodes.simple.node;
+
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class DivNode extends Node {
+    public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Div"; }
+
+    @Override protected String format() { return "(%1/%2)"; }
+
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0 &&
+            in(2)._type instanceof TypeInteger i1) {
+            if (i0.isConstant() && i1.isConstant())
+                return i1.value() == 0
+                    ? TypeInteger.ZERO
+                    : TypeInteger.constant(i0.value()/i1.value());
+        }
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
new file mode 100644
index 00000000..11769935
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -0,0 +1,23 @@
+package com.seaofnodes.simple.node;
+
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class MinusNode extends Node {
+    public MinusNode(Node in) { super(null, in); }
+
+    @Override public String label() { return "Minus"; }
+
+    @Override protected String format() { return "(-%1)"; }
+
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0)
+            return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0;
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java
new file mode 100644
index 00000000..abae6925
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -0,0 +1,26 @@
+package com.seaofnodes.simple.node;
+
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class MulNode extends Node {
+    public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Mul"; }
+
+    @Override protected String format() { return "(%1*%2)"; }
+
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0 &&
+            in(2)._type instanceof TypeInteger i1) {
+            if (i0.isConstant() && i1.isConstant())
+                return TypeInteger.constant(i0.value()*i1.value());
+        }
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index ed88e86e..3c0c3905 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -2,6 +2,11 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.print.BaseNode;
 
+import com.seaofnodes.simple.Parser;
+
+import com.seaofnodes.simple.Utils;
+import com.seaofnodes.simple.type.Type;
+
 import java.util.*;
 
 /**
@@ -32,6 +37,12 @@ public abstract class Node extends BaseNode<Node> {
     public final ArrayList<Node> _outputs;
 
     /**
+     * Current computed type for this Node.  This value changes as the graph
+     * changes and more knowledge is gained about the program.
+     */
+    public Type _type;
+
+    /**
      * A private Global Static mutable counter, for unique node id generation.
      * To make the compiler multi-threaded, this field will have to move into a TLS.
      * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values.
@@ -45,9 +56,14 @@ public abstract class Node extends BaseNode<Node> {
         _outputs = new ArrayList<>();
         for( Node n : _inputs )
             if( n != null )
-                n._outputs.add( this );
+                n.addUse( this );
     }
 
+    // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ"
+    public abstract String label();
+
+    @Override public String typeName() { return _type==null ? null : _type.toString(); }
+
     /**
      * Gets the ith input node
      * @param i Offset of the input node
@@ -64,6 +80,119 @@ public abstract class Node extends BaseNode<Node> {
     public boolean isUnused() { return nOuts() == 0; }
 
     /**
+     * Change a <em>def</em> into a Node.  Keeps the edges correct, by removing
+     * the corresponding <em>use->def</em> edge.  This may make the original
+     * <em>def</em> go dead.  This function is co-recursive with {@link #kill}.
+     *
+     * @param idx which def to set
+     * @param new_def the new definition
+     * @return new_def for flow coding
+     */
+    Node setDef(int idx, Node new_def ) {
+        Node old_def = in(idx);
+        if( old_def == new_def ) return this; // No change
+        // If new def is not null, add the corresponding def->use edge
+        // This needs to happen before removing the old node's def->use edge as
+        // the new_def might get killed if the old node kills it recursively.
+        if( new_def != null )
+            new_def.addUse(this);
+        if( old_def != null &&  // If the old def exists, remove a def->use edge
+            old_def.delUse(this) ) // If we removed the last use, the old def is now dead
+            old_def.kill();     // Kill old def
+        // Set the new_def over the old (killed) edge
+        _inputs.set(idx,new_def);
+        // Return self for easy flow-coding
+        return new_def;
+    }
+
+    // Breaks the edge invariants, used temporarily
+    protected <N extends Node> void addUse(N n) { _outputs.add(n); }
+
+    // Remove node 'use' from 'def's (i.e. our) output list, by compressing the list in-place.
+    // Return true if the output list is empty afterward.
+    // Error is 'use' does not exist; ok for 'use' to be null.
+    protected boolean delUse( Node use ) {
+        Utils.del(_outputs, Utils.find(_outputs, use));
+        return _outputs.size() == 0;
+    }
+
+    /**
+     * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em>
+     * to null.  This may recursively kill more Nodes and is basically dead
+     * code elimination.  This function is co-recursive with {@link #setDef}.
+     */
+    public void kill( ) {
+        assert isUnused();      // Has no uses, so it is dead
+        for( int i=0; i<nIns(); i++ )
+            setDef(i,null);  // Set all inputs to null, recursively killing unused Nodes
+        _inputs.clear();
+        _type=null;             // Flag as dead
+        assert isDead();        // Really dead now
+    }
+
+    // Mostly used for asserts and printing.
+    public boolean isDead() { return isUnused() && nIns()==0 && _type==null; }
+    /**
+     * Try to peephole at this node and return a better replacement Node if
+     * possible.  We compute a {@link Type} and then check and replace:
+     * <ul>
+     * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li>
+     * <li>in a future chapter we will look for a
+     * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a>
+     * to eliminate.</li>
+     * <li>we ask the Node for a better replacement (again, none enabled in this chapter)</li>
+     * </ul>
+     */
+    public final Node peephole() {
+        var obs = Parser.PARSER == null ? null : Parser.PARSER._obs;
+        if( obs != null ) obs.before(this);
+        Type old = _type;
+        Node n = peepholeOpt();
+        Node rez = n == null ? this : n;
+        if( obs != null ) obs.after(this, n == null && old == _type ? null : rez, false);
+        return rez;
+    }
+
+    private Node peepholeOpt() {
+        // Compute initial or improved Type
+        Type type = _type = compute();
+
+        // Replace constant computations from non-constants with a constant node
+        if (!(this instanceof ConstantNode) && type.isConstant()) {
+            kill();             // Kill `this` because replacing with a Constant
+            return new ConstantNode(type).peephole();
+        }
+
+        // Future chapter: Global Value Numbering goes here
+
+        // Ask each node for a better replacement
+        Node n = idealize();
+        if( n != null ) return n;
+
+        return null;            // No progress
+        }
+
+    /**
+     * This function needs to be
+     * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a>
+     * as it is part of a Monotone Analysis Framework.
+     * <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">See for example this set of slides</a>.
+     * <p>
+     * For Chapter 2, all our Types are really integer constants, and so all
+     * the needed properties are trivially true, and we can ignore the high
+     * theory.  Much later on, this will become important and allow us to do
+     * many fancy complex optimizations trivially... because theory.
+     * <p>
+     * compute() needs to be stand-alone, and cannot recursively call compute
+     * on its inputs programs are cyclic (have loops!) and this will just
+     * infinitely recurse until stack overflow.  Instead, compute typically
+     * computes a new type from the {@link #_type} field of its inputs.
+     */
+    public abstract Type compute();
+
+    public abstract Node idealize();
+
+    /**
      * Used to allow repeating tests in the same JVM.  This just resets the
      * Node unique id generator, and is done as part of making a new Parser.
      */
diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index 85bbc83f..b48682ca 100644
--- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -1,5 +1,9 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.print.ExprPrinter;
+
+import com.seaofnodes.simple.type.*;
+
 /**
  * The Return node has two inputs.  The first input is a control node and the
  * second is the data node that supplies the return value.
@@ -18,6 +22,21 @@ public class ReturnNode extends Node {
     public Node ctrl() { return in(0); }
     public Node expr() { return in(1); }
 
+    @Override
+    public String label() { return "Return"; }
+
+    @Override
+    protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) {
+        return p.p("return ").n(expr()).p(";");
+    }
+
     @Override public boolean isCFG() { return true; }
 
+    @Override
+    public Type compute() {
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 04bd6bb4..12f35736 100644
--- a/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -1,9 +1,15 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.print.ExprPrinter;
+
+import com.seaofnodes.simple.type.Type;
+
 /**
- * The Start node represents the start of the function.  For now, we do not have any inputs to Start because our function does not
- * yet accept parameters.  When we add parameters the value of Start will be a tuple, and will require Projections to extract the values.
- * We discuss this in detail in Chapter 9: Functions and Calls.
+ * The Start node represents the start of the function.  For now, we do not
+ * have any inputs to Start because our function does not yet accept
+ * parameters.  When we add parameters the value of Start will be a tuple, and
+ * will require Projections to extract the values.  We discuss this in detail
+ * in Chapter 9: Functions and Calls.
  */
 public class StartNode extends Node {
 
@@ -11,6 +17,18 @@ public class StartNode extends Node {
         super();
     }
 
+    @Override
+    public String label() { return "Start"; }
+
+    @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) {
+        return p.p(label());
+    }
+
     @Override public boolean isCFG() { return true; }
 
+    @Override
+    public Type compute() { return Type.BOTTOM; }
+
+    @Override
+    public Node idealize() { return null; }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java
new file mode 100644
index 00000000..88106018
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -0,0 +1,27 @@
+package com.seaofnodes.simple.node;
+
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class SubNode extends Node {
+    public SubNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Sub"; }
+
+    @Override protected String format() { return "(%1-%2)"; }
+
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0 &&
+            in(2)._type instanceof TypeInteger i1) {
+            if (i0.isConstant() && i1.isConstant())
+                return TypeInteger.constant(i0.value()-i1.value());
+        }
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
index 20ee6aed..8f2f31ec 100644
--- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
+++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
@@ -5,7 +5,7 @@ import com.seaofnodes.graph.GraphSnapshot.*;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.node.Node;
 
-/** Chapter 1's view of the IR; browser, transport and layout are shared. */
+/** Chapter 2's view of the IR; browser, transport and layout are shared. */
 public class SimpleGraphAdapter extends GraphAdapter<Node> {
 
     @Override protected Kind kind(Node n) {
diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
index 1c78e4dd..a17bf796 100644
--- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
+++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
@@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node;
 import java.util.ArrayList;
 import java.io.IOException;
 
-/** Chapter 1's compilation context; capture and event bookkeeping are shared. */
+/** Chapter 2's compilation context; capture and event bookkeeping are shared. */
 public class SimpleGraphObserver extends GraphCapture<Node> {
     private Parser _parser;
     private Node _ret;
@@ -18,6 +18,7 @@ public class SimpleGraphObserver extends GraphCapture<Node> {
     }
     @Override protected void compile(String src) {
         _parser = new Parser(src);
+        _parser._obs = this;
         _phase = "Parse";
         _ret = _parser.parse();
         phase(_phase);
@@ -25,6 +26,7 @@ public class SimpleGraphObserver extends GraphCapture<Node> {
     @Override protected String phase() { return _phase; }
     @Override protected int pos() { return "Parse".equals(_phase) ? _parser.pos() : -1; }
     @Override protected void detach() {
+        if( _parser != null ) _parser._obs = null;
         _parser = null;
         _ret = null;
     }
diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java
new file mode 100644
index 00000000..b98ce6de
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -0,0 +1,45 @@
+package com.seaofnodes.simple.type;
+
+
+/**
+ * These types are part of a Monotone Analysis Framework,
+ * @see <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">see for example this set of slides</a>.
+ * <p>
+ * The types form a lattice; @see <a href="https://en.wikipedia.org/wiki/Lattice_(order)">a symmetric complete bounded (ranked) lattice.</a>
+ * <p>
+ * This wild lattice theory will be needed later to allow us to easily beef up
+ * the analysis and optimization of the Simple compiler... but we don't need it
+ * now, just know that it is coming along in a later Chapter.
+ * <p>g
+ * One of the fun things here is that while the theory is deep and subtle, the
+ * actual implementation is darn near trivial and is generally really obvious
+ * what we're doing with it.  Right now, it's just simple integer math to do
+ * simple constant folding e.g. 1+2 == 3 stuff.
+ */
+
+public class Type {
+
+    // ----------------------------------------------------------
+    // Simple types are implemented fully here.  "Simple" means: the code and
+    // type hierarchy are simple, not that the Type is conceptually simple.
+    static final byte TBOT    = 0; // Bottom (ALL)
+    static final byte TTOP    = 1; // Top    (ANY)
+    static final byte TSIMPLE = 2; // End of the Simple Types
+    static final byte TINT    = 3; // All Integers; see TypeInteger
+    public final byte _type;
+
+    public boolean is_simple() { return _type < TSIMPLE; }
+    private static final String[] STRS = new String[]{"Bot","Top"};
+    protected Type(byte type) { _type = type; }
+
+    public static final Type BOTTOM   = new Type( TBOT ); // ALL
+
+    public boolean isConstant() { return _type == TTOP; }
+
+    @Override
+    public String toString() {
+      return print(new StringBuilder()).toString();
+    }
+
+    public StringBuilder print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;}
+}
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
new file mode 100644
index 00000000..e0324da5
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -0,0 +1,41 @@
+package com.seaofnodes.simple.type;
+
+/**
+ * Integer Type
+ */
+public class TypeInteger extends Type {
+
+    public final static TypeInteger ZERO= new TypeInteger(0);
+
+    /**
+     * The constant value observed for this type
+     */
+    private final long _con;
+
+    public TypeInteger(long con) {
+        super(TINT);
+        _con = con;
+    }
+
+    public static TypeInteger constant(long con) { return new TypeInteger(con); }
+
+    @Override
+    public String toString() {
+      return print(new StringBuilder()).toString();
+    }
+
+    @Override
+    public StringBuilder print(StringBuilder sb) { return sb.append(_con); }
+
+    @Override
+    public boolean isConstant() { return true; }
+
+    public long value() { return _con; }
+
+    @Override
+    public boolean equals( Object o ) {
+        if( o==this ) return true;
+        if( !(o instanceof TypeInteger i) ) return false;
+        return _con==i._con;
+    }
+}