Start on Chapter 5

21 files changed, 1654 insertions, 0 deletions

diff --git a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
new file mode 100644
index 00000000..f73bfd3c
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -0,0 +1,199 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeControl;
+
+import java.util.*;
+
+/**
+ * Simple visualizer that outputs GraphViz dot format.
+ * The dot output must be saved to a file and run manually via dot to generate the SVG output.
+ * Currently, this is done manually.
+ */
+public class GraphVisualizer {
+
+    public String generateDotOutput(Parser parser) {
+
+        // Since the graph has cycles, we need to create a flat list of all the
+        // nodes in the graph.
+        Collection<Node> all = findAll(parser);
+        StringBuilder sb = new StringBuilder();
+        sb.append("digraph chapter04 {\n");
+        sb.append("/*\n");
+        sb.append(parser.src());
+        sb.append("\n*/\n");
+        
+        // To keep the Scopes below the graph and pointing up into the graph we
+        // need to group the Nodes in a subgraph cluster, and the scopes into a
+        // different subgraph cluster.  THEN we can draw edges between the
+        // scopes and nodes.  If we try to cross subgraph cluster borders while
+        // still making the subgraphs DOT gets confused.
+        sb.append("\trankdir=BT;\n"); // Force Nodes before Scopes
+        
+        // Just the Nodes first, in a cluster no edges
+        nodes(sb, all);
+        
+        // Now the scopes, in a cluster no edges
+        scopes(sb, parser._scope);
+
+        // Walk the Node edges
+        nodeEdges(sb, all);
+
+        // Walk the Scope edges
+        scopeEdges(sb, parser._scope);
+        
+        sb.append("}\n");
+        return sb.toString();
+    }
+
+
+    private void nodes(StringBuilder sb, Collection<Node> all) {
+        // Just the Nodes first, in a cluster no edges
+        sb.append("\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name
+        for( Node n : all ) {
+            if( n instanceof ProjNode )
+                continue; // Do not emit, rolled into MultiNode already
+            sb.append("\t\t").append(n.uniqueName()).append(" [ ");
+            String lab = n.label();
+            if( n instanceof MultiNode ) {
+                // Make a box with the MultiNode on top, and all the projections on the bottom
+                sb.append("shape=plaintext label=<\n");
+                sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"4\">\n");
+                sb.append("\t\t\t<TR><TD BGCOLOR=\"yellow\">").append(lab).append("</TD></TR>\n");
+                sb.append("\t\t\t<TR>");
+                boolean doProjTable = false;
+                for( Node use : n._outputs ) {
+                    if( use instanceof ProjNode proj ) {
+                        if (!doProjTable) {
+                            doProjTable = true;
+                            sb.append("<TD>").append("\n");
+                            sb.append("\t\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">").append("\n");
+                            sb.append("\t\t\t\t<TR>");
+                        }
+                        sb.append("<TD PORT=\"p").append(proj._idx).append("\"");
+                        if( proj._idx==0 ) sb.append(" BGCOLOR=\"yellow\"");
+                        sb.append(">").append(proj.label()).append("</TD>");
+                    }
+                }
+                if (doProjTable) {
+                    sb.append("</TR>").append("\n");
+                    sb.append("\t\t\t\t</TABLE>").append("\n");
+                    sb.append("\t\t\t</TD>");
+                }
+                sb.append("</TR>\n");
+                sb.append("\t\t\t</TABLE>>\n\t\t");
+                
+            } else {
+                // control nodes have box shape
+                // other nodes are ellipses, i.e. default shape
+                if( n instanceof Control )
+                    sb.append("shape=box style=filled fillcolor=yellow ");
+                sb.append("label=\"").append(lab).append("\" ");
+            }
+            sb.append("];\n");
+        }
+        sb.append("\t}\n");     // End Node cluster
+    }
+
+    private void scopes( StringBuilder sb, ScopeNode scopenode) {
+        sb.append("\tnode [shape=plaintext];\n");
+        int level=0;
+        for( HashMap<String,Integer> scope : scopenode._scopes ) {
+            sb.append("\tsubgraph cluster_").append(level).append(" {\n"); // Magic "cluster_" in the subgraph name
+            String scopeName = makeScopeName(level);
+            sb.append("\t\t").append(scopeName).append(" [label=<\n");
+            sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n");
+            // Add the scope level
+            sb.append("\t\t\t<TR><TD BGCOLOR=\"cyan\">").append(level).append("</TD>");
+            for( String name : scope.keySet() )
+                sb.append("<TD PORT=\"").append(makePortName(scopeName, name)).append("\">").append(name).append("</TD>");
+            sb.append("</TR>\n");
+            sb.append("\t\t\t</TABLE>>];\n");
+            level++;
+        }
+        // Scope clusters nest, so the graphics shows the nested scopes, so
+        // they are not closed as they are printed; so they just keep nesting.
+        // We close them all at once here.
+        sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters
+    }
+    
+    private String makeScopeName(int level) { return "scope" + level; }
+    private String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; }
+
+    private boolean isControlEdge(Node def) {
+        return def._type instanceof TypeControl;
+    }
+
+    // Walk the node edges
+    private void nodeEdges(StringBuilder sb, Collection<Node> all) {
+        for( Node n : all ) {
+            if( n instanceof ConstantNode || n instanceof ProjNode )
+                continue;       // Do not display the Constant->Start edge; ProjNodes handled by Multi
+            for( Node def : n._inputs )
+                if( def != null ) {
+                    sb.append('\t').append(n.uniqueName()).append(" -> ");
+                    if( def instanceof ProjNode proj ) {
+                        String mname = proj.ctrl().uniqueName();
+                        sb.append(mname).append(":p").append(proj._idx);
+                    } else sb.append(def.uniqueName());
+                    // Control edges are colored red
+                    if( isControlEdge(def) )
+                        sb.append(" [color=red]");
+                    sb.append(";\n");
+                }
+        }
+    }
+    
+    // Walk the scope edges
+    private void scopeEdges( StringBuilder sb, ScopeNode scopenode ) {
+        sb.append("\tedge [style=dashed color=cornflowerblue];\n");
+        int level=0;
+        for( HashMap<String,Integer> scope : scopenode._scopes ) {
+            String scopeName = makeScopeName(level);
+            for( String name : scope.keySet() ) {
+                Node def = scopenode.in(scope.get(name));
+                if( def==null ) continue;
+                sb.append("\t")
+                  .append(scopeName).append(":")
+                  .append('"').append(makePortName(scopeName, name)).append('"') // wrap port name with quotes because $ctrl is not valid unquoted
+                  .append(" -> ");
+                if( def instanceof ProjNode proj ) {
+                    String mname = proj.ctrl().uniqueName();
+                    sb.append(mname).append(":p").append(proj._idx);
+                } else sb.append(def.uniqueName());
+                sb.append(";\n");
+            }
+            level++;
+        }
+    }
+    
+    /**
+     * Finds all nodes in the graph.
+     */
+    private Collection<Node> findAll(Parser parser) {
+        final StartNode start = Parser.START;
+        final HashMap<Integer, Node> all = new HashMap<>();
+        for( Node n : start._outputs )
+            walk(all, n);
+        // Scan symbol tables
+        for( HashMap<String,Integer> scope : parser._scope._scopes )
+            for (Integer i : scope.values())
+                walk(all, parser._scope.in(i));
+        return all.values();
+    }
+
+    /**
+     * Walk a subgraph and populate distinct nodes in the all list.
+     */
+    private void walk(HashMap<Integer, Node> all, Node n) {
+        if(n == null ) return;
+        if (all.get(n._nid) != null) return; // Been there, done that
+        all.put(n._nid, n);
+        for (Node c : n._inputs)
+            if (c != null)
+                walk(all, c);
+        for (Node c : n._outputs)
+            if (c != null)
+                walk(all, c);
+    }
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
new file mode 100644
index 00000000..147515f6
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
@@ -0,0 +1,397 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
+
+import java.util.*;
+
+/**
+ * The Parser converts a Simple source program to the Sea of Nodes intermediate
+ * representation directly in one pass. There is no intermediate Abstract
+ * Syntax Tree structure.
+ * <p>
+ * This is a simple recursive descent parser. All lexical analysis is done here as well.
+ */
+public class Parser {
+
+    /**
+     * A Global Static, unique to each compilation.  This is a public, so we
+     * can make constants everywhere without having to thread the StartNode
+     * through the entire parser and optimizer.
+     * <p>
+     * To make the compiler multithreaded, this field will have to move into a TLS.
+     */
+    public static StartNode START;
+
+    private final Lexer _lexer;
+
+    /**
+     * Stack of lexical scopes, each scope is a symbol table that binds
+     * variable names to Nodes.  The top of this stack represents current scope.
+     */
+    public ScopeNode _scope;
+
+    public Parser(String source, TypeInteger arg) {
+        _lexer = new Lexer(source);
+        _scope = new ScopeNode();
+        Node.reset();
+        START = new StartNode(new Type[]{ Type.CONTROL, arg });
+        START.peephole();
+    }
+
+    public Parser(String source) {
+        this(source, TypeInteger.BOT);
+    }
+
+    String src() { return new String( _lexer._input ); }
+
+
+
+    public ReturnNode parse() {
+        _scope.push();
+        try {
+            _scope.define("$ctrl", new ProjNode(START, 0, "$ctrl").peephole());
+            _scope.define("arg"  , new ProjNode(START, 1, "arg"  ).peephole());
+            return (ReturnNode) parseBlock();
+        }
+        finally {
+            _scope.pop();
+        }
+    }
+
+    /**
+     * Parses a block
+     *
+     * <pre>
+     *     '{' statements '}'
+     * </pre>
+     */
+    private Node parseBlock() {
+        // Enter a new scope
+        _scope.push();
+        Node n = null;
+        while (!match("}") && !_lexer.isEOF()) {
+            Node n0 = parseStatement();
+            if (n0 != null) n = n0; // Allow null returns from eg showGraph
+        }
+        // Exit scope
+        _scope.pop();
+        return n;
+    }
+
+    /**
+     * Parses a statement
+     *
+     * <pre>
+     *     returnStatement | declStatement | blockStatement | expressionStatement
+     * </pre>
+     */
+    private Node parseStatement() {
+        if (match("return")) return parseReturn();
+        else if (match("int")) return parseDecl();
+        else if (match("{")) return parseBlock();
+        else if (match("#showGraph")) return showGraph();
+        else return parseExpressionStatement();
+    }
+
+    /**
+     * Parses a return statement; "return" already parsed.
+     * The $ctrl edge is killed.
+     *
+     * <pre>
+     *     'return' expr ;
+     * </pre>
+     */
+    private Node parseReturn() {
+        var expr = require(parseExpression(), ";");
+        Node ret = new ReturnNode(_scope.lookup("$ctrl"), expr);
+        _scope.update("$ctrl",null);
+        return ret;
+    }
+
+    /**
+     * Dumps out the node graph
+     */
+    private Node showGraph() {
+        require(";");
+        System.out.println(new GraphVisualizer().generateDotOutput(this));
+        return null;
+    }
+
+    /**
+     * Parses an expression statement
+     *
+     * <pre>
+     *     name '=' expression ';'
+     * </pre>
+     */
+    private Node parseExpressionStatement() {
+        var name = requireId();
+        require("=");
+        var expr = require(parseExpression(), ";");
+        if( _scope.update(name, expr)==null )
+            throw error("Undefined name '" + name + "'");
+        return expr;
+    }
+
+    /**
+     * Parses a declStatement
+     *
+     * <pre>
+     *     'int' name = expression ';'
+     * </pre>
+     */
+    private Node parseDecl() {
+        // Type is 'int' for now
+        var name = requireId();
+        require("=");
+        var expr = require(parseExpression(), ";");
+        if( _scope.define(name,expr) == null )
+            throw error("Redefining name '" + name + "'");
+        return expr;
+    }
+
+    /**
+     * Parse an expression of the form:
+     *
+     * <pre>
+     *     expr : additiveExpr
+     * </pre>
+     */
+    private Node parseExpression() { return parseComparison(); }
+
+    private Node parseComparison() {
+        var lhs = parseAddition();
+        if (match("==")) return new BoolNode.EQNode(lhs, parseComparison()).peephole();
+        if (match("!=")) return new BoolNode.NENode(lhs, parseComparison()).peephole();
+        if (match("<" )) return new BoolNode.LTNode(lhs, parseComparison()).peephole();
+        if (match("<=")) return new BoolNode.LENode(lhs, parseComparison()).peephole();
+        if (match(">" )) return new BoolNode.GTNode(lhs, parseComparison()).peephole();
+        if (match(">=")) return new BoolNode.GENode(lhs, parseComparison()).peephole();
+        return lhs;
+    }
+
+    /**
+     * Parse an additive expression
+     *
+     * <pre>
+     *     additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)*
+     * </pre>
+     */
+    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>
+     */
+    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>
+     */
+    private Node parseUnary() {
+        if (match("-")) return new MinusNode(parseUnary()).peephole();
+        return parsePrimary();
+    }
+
+    /**
+     * Parse a primary expression:
+     *
+     * <pre>
+     *     primaryExpr : integerLiteral | Identifier | '(' expression ')'
+     * </pre>
+     */
+    private Node parsePrimary() {
+        if (_lexer.isNumber()) return parseIntegerLiteral();
+        if (match("(")) return require(parseExpression(), ")");
+        String name = requireId();
+        Node id = _scope.lookup(name);
+        if( id==null )
+            throw error("Undefined name '" + name + "'");
+        return id.peephole();
+    }
+
+    /**
+     * Parse integer literal
+     *
+     * <pre>
+     *     integerLiteral: [1-9][0-9]* | [0]
+     * </pre>
+     */
+    private ConstantNode parseIntegerLiteral() {
+        return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole();
+    }
+
+    //////////////////////////////////
+    // Utilities for lexical analysis
+
+    // Return true and skip if "syntax" is next in the stream.
+    private boolean match(String syntax) { return _lexer.match(syntax); }
+
+    // Require and return an identifier
+    private String requireId() {
+        String id = _lexer.matchId();
+        if (id != null) return id;
+        throw error("identifier");
+    }
+
+    // Require an exact match
+    private void require(String syntax) { require(null, syntax); }
+    private Node require(Node n, String syntax) {
+        if (match(syntax)) return n;
+        throw errorSyntax(syntax);
+    }
+
+    RuntimeException errorSyntax(String syntax) {
+        return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken());
+    }
+
+    static RuntimeException error(String errorMessage) {
+        return new RuntimeException(errorMessage);
+    }
+
+    ////////////////////////////////////
+    // Lexer components
+
+    private static class Lexer {
+
+        // Input buffer; an array of text bytes read from a file or a string
+        private final byte[] _input;
+        // Tracks current position in input buffer
+        private int _position = 0;
+
+        /**
+         * Record the source text for lexing
+         */
+        public Lexer(String source) {
+            this(source.getBytes());
+        }
+
+        /**
+         * Direct from disk file source
+         */
+        public Lexer(byte[] buf) {
+            _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;
+        }
+
+        // Peek next character, or report EOF
+        private char peek() {
+            return isEOF() ? Character.MAX_VALUE   // Special value that causes parsing to terminate
+                    : (char) _input[_position];
+        }
+
+        private char nextChar() {
+            char ch = peek();
+            _position++;
+            return ch;
+        }
+
+        // True if a white space
+        private boolean isWhiteSpace() {
+            return peek() <= ' '; // Includes all the use space, tab, newline, CR
+        }
+
+        /**
+         * Return the next non-white-space character
+         */
+        private void skipWhiteSpace() {
+            while (isWhiteSpace()) _position++;
+        }
+
+
+        // Return true, if we find "syntax" after skipping white space; also
+        // then advance the cursor past syntax.
+        // Return false otherwise, and do not advance the cursor.
+        boolean match(String syntax) {
+            skipWhiteSpace();
+            int len = syntax.length();
+            if (_position + len > _input.length) return false;
+            for (int i = 0; i < len; i++)
+                if ((char) _input[_position + i] != syntax.charAt(i)) return false;
+            _position += len;
+            return true;
+        }
+
+        // Return an identifier or null
+        String matchId() {
+            skipWhiteSpace();
+            return isIdStart(peek()) ? parseId() : null;
+        }
+
+        // Used for errors
+        String getAnyNextToken() {
+            if (isEOF()) return "";
+            if (isIdStart(peek())) return parseId();
+            if (isPunctuation(peek())) return parsePunctuation();
+            return String.valueOf(peek());
+        }
+
+        boolean isNumber() {return isNumber(peek());}
+        boolean isNumber(char ch) {return Character.isDigit(ch);}
+
+        private Type parseNumber() {
+            int start = _position;
+            while (isNumber(nextChar())) ;
+            String snum = new String(_input, start, --_position - start);
+            if (snum.length() > 1 && snum.charAt(0) == '0')
+                throw error("Syntax error: integer values cannot start with '0'");
+            return TypeInteger.constant(Long.parseLong(snum));
+        }
+
+        // First letter of an identifier 
+        private boolean isIdStart(char ch) {
+            return Character.isAlphabetic(ch) || ch == '_';
+        }
+
+        // All characters of an identifier, e.g. "_x123"
+        private boolean isIdLetter(char ch) {
+            return Character.isLetterOrDigit(ch) || ch == '_';
+        }
+
+        private String parseId() {
+            int start = _position;
+            while (isIdLetter(nextChar())) ;
+            return new String(_input, start, --_position - start);
+        }
+
+        // 
+        private boolean isPunctuation(char ch) {
+            return "=;[]<>()+-/*".indexOf(ch) != -1;
+        }
+
+        private String parsePunctuation() {
+            int start = _position;
+            if (isPunctuation(nextChar())) ;
+            return new String(_input, start, --_position - start);
+        }
+    }
+
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java
new file mode 100644
index 00000000..8b157a9c
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -0,0 +1,72 @@
+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
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("("));
+        in(2)._print0(sb.append("+"));
+        return sb.append(")");
+    }
+  
+
+    @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 i0.meet(i1);
+        }
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize () {
+        Node lhs = in(1);
+        Node rhs = in(2);
+        Type t1 = lhs._type;
+        Type t2 = rhs._type;
+
+        // Add of 0.  We do not check for (0+x) because this will already
+        // canonicalize to (x+0)
+        if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 )
+            return lhs;
+        
+        // Move constants to RHS: con+arg becomes arg+con
+        if ( t1.isConstant() && !t2.isConstant() ) {
+            Node tmp = in(1);   // Swap inputs without letting either input go dead during the swap
+            _inputs.set(1,in(2));
+            _inputs.set(2,tmp);
+            return this;
+        }
+        
+        // Goal: a left-spine set of adds, with constants on the rhs (which then fold).
+        
+        // Do we have (x + con1) + con2 ?
+        // Rotate to   x +(con1  + con2)
+        // The constants will fold on the next peephole.
+        if (t2.isConstant() && lhs instanceof AddNode && lhs.in(2)._type.isConstant() )
+            return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole());
+
+        // Do we have  x + (y + con) ?
+        // Swap to    (x + y) + con
+        if (rhs instanceof AddNode add && add.in(2)._type.isConstant() )
+          return new AddNode(new AddNode(lhs,add.in(1)).peephole(), add.in(2));
+
+        // Add of same to a multiply by 2
+        if( lhs==rhs )
+            return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole());
+        
+        return null;
+    }
+        
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java
new file mode 100644
index 00000000..b0e0bf42
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -0,0 +1,53 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeBot;
+import com.seaofnodes.simple.type.TypeInteger;
+
+abstract public class BoolNode extends Node {
+
+    public BoolNode(Node lhs, Node rhs) {
+        super(null, lhs, rhs);
+    }
+
+    abstract String op();       // String opcode name
+    
+    @Override
+    public String label() { return op(); }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("("));
+        in(2)._print0(sb.append(op()));
+        return sb.append(")");
+    }
+
+    @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(doOp(i0.value(), i1.value()) ? 1 : 0);
+            return i0.meet(i1);
+        }
+        return TypeBot.BOTTOM;
+    }
+
+    abstract boolean doOp(long lhs, long rhs);
+
+    @Override
+    public Node idealize() {
+        // Compare of same 
+        if( in(1)==in(2) )
+            return new ConstantNode(TypeInteger.constant(doOp(3,3)?1:0));
+
+        return null;
+    }
+
+    public static class EQNode extends BoolNode { public EQNode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } }
+    public static class NENode extends BoolNode { public NENode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "!="; } boolean doOp(long lhs, long rhs) { return lhs != rhs; } }
+    public static class LTNode extends BoolNode { public LTNode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs <  rhs; } }
+    public static class LENode extends BoolNode { public LENode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } }
+    public static class GTNode extends BoolNode { public GTNode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return ">" ; } boolean doOp(long lhs, long rhs) { return lhs >  rhs; } }
+    public static class GENode extends BoolNode { public GENode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return ">="; } boolean doOp(long lhs, long rhs) { return lhs >= rhs; } }
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
new file mode 100644
index 00000000..ec85bf1f
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -0,0 +1,42 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.Type;
+
+/**
+ * A Constant node represents a constant value.  At present, the only constants
+ * that we allow are integer literals; therefore Constants contain an integer
+ * value. As we add other types of constants, we will refactor how we represent
+ * Constants.
+ * <p>
+ * Constants have no semantic inputs. However, we set Start as an input to
+ * Constants to enable a forward graph walk.  This edge carries no semantic
+ * meaning, and it is present <em>solely</em> to allow visitation.
+ * <p>
+ * The Constant's value is the value stored in it.
+ */
+public class ConstantNode extends Node {
+    Type _con;
+    public ConstantNode( Type type ) {
+        super(Parser.START);
+        _con = type;
+    }
+    
+    @Override
+    public String label() { return "#"+_con; }
+  
+    @Override
+    public String uniqueName() { return "Con_" + _nid; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        return _con._print(sb);
+    }
+    
+    @Override
+    public Type compute() { return _con; }
+
+    @Override
+    public Node idealize() { return null; }
+    
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/Control.java b/chapter05/src/main/java/com/seaofnodes/simple/node/Control.java
new file mode 100644
index 00000000..48cf2b7a
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/Control.java
@@ -0,0 +1,9 @@
+package com.seaofnodes.simple.node;
+
+
+/**
+ * Control interface is a marker interface to be implemented
+ * by Control nodes.
+ */
+public interface Control {
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java
new file mode 100644
index 00000000..22167a87
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -0,0 +1,38 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeBot;
+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
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("("));
+        in(2)._print0(sb.append("/"));
+        return sb.append(")");
+    }
+  
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0 &&
+            in(2)._type instanceof TypeInteger i1) {
+            if (i0.isConstant() && i1.isConstant()) {
+                if (i1.value() == 0)
+                    throw new IllegalArgumentException("Divide by zero");
+                return TypeInteger.constant(i0.value()/i1.value());
+            }
+            return i0.meet(i1);
+        }
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java
new file mode 100644
index 00000000..04084d0f
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -0,0 +1,30 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeBot;
+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
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("(-"));
+        return sb.append(")");
+    }
+  
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0)
+            return TypeInteger.constant(-i0.value());
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java
new file mode 100644
index 00000000..e3e83b38
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -0,0 +1,55 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeBot;
+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
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("("));
+        in(2)._print0(sb.append("*"));
+        return sb.append(")");
+    }
+
+    @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 i0.meet(i1);
+        }
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() {
+        Node lhs = in(1);
+        Node rhs = in(2);
+        Type t1 = lhs._type;
+        Type t2 = rhs._type;
+        
+        // Mul of 1.  We do not check for (1*x) because this will already
+        // canonicalize to (x*1)
+        if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==1 )
+            return lhs;
+        
+        // Move constants to RHS: con*arg becomes arg*con
+        if ( t1.isConstant() && !t2.isConstant() ) {
+            Node tmp = in(1);   // Swap inputs without letting either input go dead during the swap
+            _inputs.set(1,in(2));
+            _inputs.set(2,tmp);
+            return this;
+        }
+        
+        return null;
+    }
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java
new file mode 100644
index 00000000..e517c3d5
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java
@@ -0,0 +1,13 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+
+public abstract class MultiNode extends Node {
+    
+    public MultiNode(Node... inputs) {
+        super(inputs);
+    }
+    
+    // Return the ProjNode with the idx
+    abstract ProjNode proj(int idx);
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
new file mode 100644
index 00000000..8d698d1b
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -0,0 +1,343 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+
+import java.util.ArrayList;
+import java.util.Collections;
+
+/**
+ * All Nodes in the Sea of Nodes IR inherit from the Node class.
+ * The Node class provides common functionality used by all subtypes.
+ * Subtypes of Node specialize by overriding methods.
+ */
+public abstract class Node {
+
+    /**
+     * Each node has a unique dense Node ID within a compilation context
+     * The ID is useful for debugging, for using as an offset in a bitvector,
+     * as well as for computing equality of nodes (to be implemented later).
+     */
+    public final int _nid;
+
+    /**
+     * Inputs to the node. These are use-def references to Nodes.
+     * <p>
+     * Generally fixed length, ordered, nulls allowed, no unused trailing space.
+     * Ordering is required because e.g. "a/b" is different from "b/a".
+     * The first input (offset 0) is often a Control node.
+     * @see Control
+     */
+    public final ArrayList<Node> _inputs;
+
+    /**
+     * Outputs reference Nodes that are not null and have this Node as an
+     * input.  These nodes are users of this node, thus these are def-use
+     * references to Nodes.
+     * <p>
+     * Outputs directly match inputs, making a directed graph that can be
+     * walked in either direction.  These outputs are typically used for
+     * efficient optimizations but otherwise have no semantics meaning.
+     */
+    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.
+     * */
+    private static int UNIQUE_ID = 1;
+
+    protected Node(Node... inputs) {
+        _nid = UNIQUE_ID++; // allocate unique dense ID
+        _inputs = new ArrayList<>();
+        Collections.addAll(_inputs,inputs);
+        _outputs = new ArrayList<>();
+        for( Node n : _inputs )
+            if( n != null )
+                n._outputs.add( this );
+    }
+
+    public abstract String label();
+
+    public String uniqueName() { return label() + _nid; }
+
+    @Override
+    public final String toString() {
+        // TODO: This needs a lot of work
+        return print();
+    }
+
+    // This is a *deep* print.  This version will fail on cycles, which we will
+    // correct later when we can parse programs with loops.  We print with a
+    // tik-tok style; the common _print0 calls the per-Node _print1, which
+    // calls back to _print0;
+    public final String print() {
+        return _print0(new StringBuilder()).toString();
+    }
+    // This is the common print: check for DEAD and print "DEAD" else call the
+    // per-Node print1.
+    final StringBuilder _print0(StringBuilder sb) {
+        return isDead()
+            ? sb.append(uniqueName()).append(":DEAD")
+            : _print1(sb);
+    }
+    // Every Node implements this.
+    abstract StringBuilder _print1(StringBuilder sb);
+
+    
+    /**
+     * Gets the ith input node
+     * @param i Offset of the input node
+     * @return Input node or null
+     */
+    public Node in(int i) { return _inputs.get(i); }
+
+    public int nIns() { return _inputs.size(); }
+
+    /**
+     * Gets the ith output node
+     * @param i Offset of the output node
+     * @return Output node (not null)
+     */
+    public Node out(int i) { return _outputs.get(i); }
+
+    public int nOuts() { return _outputs.size(); }
+
+    public boolean isUnused() { return nOuts() == 0; }
+
+    /**
+     * We allow disabling peephole opt so that we can observe the
+     * full graph, vs the optimized graph.
+     */
+    public static boolean _disablePeephole = false;
+
+
+    /**
+     * 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.  The "better replacement"
+     * is things like {@code (1+2)} becomes {@code 3} and {@code (1+(x+2))} becomes
+     * {@code (x+(1+2))}.  By canonicalizing expressions we fold common addressing
+     * math constants, remove algebraic identities and generally simplify the
+     * code. </li>
+     * </ul>
+     */
+    public final Node peephole( ) {
+        // Compute initial or improved Type
+        Type type = _type = compute();
+        
+        if (_disablePeephole)
+            return this;        // Peephole optimizations turned off
+
+        // Replace constant computations from non-constants with a constant node
+        if (!(this instanceof ConstantNode) && type.isConstant())
+            return deadCodeElim(new ConstantNode(type).peephole());
+
+        // Future chapter: Global Value Numbering goes here
+        
+        // Ask each node for a better replacement
+        Node n = idealize();
+        if( n != null )         // Something changed
+            // Recursively optimize
+            return deadCodeElim(n.peephole());
+        
+        return this;            // No progress
+    }
+
+    // m is the new Node, self is the old.
+    // Return 'm', which may have zero uses but is alive nonetheless.
+    // If self has zero uses (and is not 'm'), {@link #kill} self.
+    private Node deadCodeElim(Node m) {
+        // If self is going dead and not being returned here (Nodes returned
+        // from peephole commonly have no uses (yet)), then kill self.
+        if( m != this && isUnused() ) {
+            // Killing self - and since self recursively kills self's inputs we
+            // might end up killing 'm', which we are returning as a live Node.
+            // So we add a bogus extra null output edge to stop kill().
+            m.addUse(null); // Add bogus null use to keep m alive
+            kill();            // Kill self because replacing with 'm'
+            m.delUse(null);    // Remove bogus null.
+        }
+        return m;
+    }
+
+    
+    /**
+     * 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}.
+     * <p>
+     
+     * This method is the normal path for altering a Node, because it does the
+     * proper default edge maintenance.  It also <em>immediately</em> kills
+     * Nodes that lose their last use; at times care must be taken to avoid
+     * killing Nodes that are being used without having an output Node.  This
+     * definitely happens in the middle of recursive {@link #peephole} calls.
+     *     
+     * @param idx which def to set
+     * @param new_def the new definition
+     * @return this for flow coding
+     */
+    Node set_def(int idx, Node new_def ) {
+        Node old_def = in(idx);
+        if( old_def == new_def ) return this; // No change
+        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);
+        // If new def is not null, add the corresponding def->use edge
+        if( new_def != null )
+            new_def._outputs.add(this);
+        // Return self for easy flow-coding
+        return this;
+    }
+
+    /**
+     * Add a new def to an existing Node.  Keep the edges correct by
+     * adding the corresponding <em>def->use</em> edge.
+     *
+     * @param new_def the new definition, appended to the end of existing definitions
+     * @return new_def for flow coding
+     */
+    Node add_def(Node new_def) {
+        // Add use->def edge
+        _inputs.add(new_def);
+        // If new def is not null, add the corresponding def->use edge
+        if( new_def != null )
+            new_def._outputs.add(this);
+        return new_def;
+    }
+
+    
+    // Breaks the edge invariants, used temporarily
+    private void addUse(Node 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.
+    private boolean delUse( Node use ) {
+        ArrayList<Node> outs = _outputs;
+        int lidx = outs.size()-1; // Last index            
+        // This 1-line hack compresses an element out of an ArrayList
+        // without having to copy the contents.  The last element is
+        // stuffed over the deleted element, and then the size is reduced.            
+        outs.set(outs.indexOf(use),outs.get(lidx));
+        outs.remove(lidx);  // Reduce ArrayList size without copying anything
+        return lidx==0;
+    }
+
+    // Shortcut for "popping" n nodes.  A "pop" is basically a
+    // set_def(last,null) followed by lowering the nIns() count.
+    void pop_n(int n) {
+        for( int i=0; i<n; i++ ) {
+            Node old_def = _inputs.remove(_inputs.size()-1);
+            if( old_def != null &&     // If it exists and
+                old_def.delUse(this) ) // If we removed the last use, the old def is now dead
+                old_def.kill();        // Kill old def
+        }
+    }
+  
+    /**
+     * 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 #pop_n}.
+     */
+    public void kill( ) {
+        assert isUnused();      // Has no uses, so it is dead
+        pop_n(nIns());          // Set all inputs to null, recursively killing unused Nodes
+        _type=null;             // Flag as dead
+        assert isDead();        // Really dead now
+    }
+
+    // Mostly used for asserts and printing.
+    boolean isDead() { return isUnused() && nIns()==0 && _type==null; }
+    
+    /**
+     * 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();
+
+    /**
+     * This function rewrites the current Node into a more "idealized" form.
+     * This is the bulk of our peephole rewrite rules, and we use this to
+     * e.g. turn arbitrary collections of adds and multiplies with mixed
+     * constants into a normal form that's easy for hardware to implement.
+     * Example: An array addressing expression:
+     * <pre>   ary[idx+1]</pre>
+     * might turn into Sea-of-Nodes IR:
+     * <pre>   (ary+12)+((idx+1) * 4)</pre>
+     * This expression can then be idealized into:
+     * <pre>   ary + ((idx*4) + (12 + (1*4)))</pre>
+     * And more folding:
+     * <pre>   ary + ((idx<<2) + 16)</pre>
+     * And during code-gen:
+     * <pre>   MOV4 Rary,Ridx,16 // or some such hardware-specific notation </pre>
+     * <p>
+     * {@link #idealize} has a very specific calling convention:
+     * <ul>
+     * <li>If NO change is made, return {@code null}
+     * <li>If ANY change is made, return not-null; this can be {@code this}
+     * <li>The returned Node does NOT call {@link #peephole} on itself; the {@link #peephole} call will recursively peephole it.
+     * <li>Any NEW nodes that are not directly returned DO call {@link #peephole}.
+     * </ul>
+     * <p>
+     * Examples:
+     * <table border="3">
+     * <tr><th>    before       </th><th>       after     </th><th>return </th><th>comment  </th></tr>
+     * <tr><td>{@code (x+5)    }</td><td>{@code   (x+5)  }</td><td>{@code null  }</td><td>No change</td></tr>
+     * <tr><td>{@code (5+x)    }</td><td>{@code   (x+5)  }</td><td>{@code this  }</td><td>Swapped arguments</td></tr>
+     * <tr><td>{@code ((x+1)+2)}</td><td>{@code (x+(1+2))}</td><td>{@code (x+_) }</td><td>Returns 2 new Nodes</td></tr>
+     * </table>
+     *
+     * The last entry deserves more discussion.  The new Node {@code (1+2)}
+     * created in {@link #idealize} calls {@link #peephole} (which then folds
+     * into a constant).  The other new Node {@code (x+3)} does not call
+     * peephole, because it is returned and peephole itself will recursively
+     * call peephole.
+     * <p>
+     * Since idealize calls peephole and peephole calls idealize, you must be
+     * careful that all idealizations are <em>monotonic</em>: all transforms remove
+     * some feature, so that the set of available transforms always shrinks.
+     * If you don't, you risk an infinite peephole loop!
+     *
+     * @return Either a new or changed node, or null for no changes.
+     */
+    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.
+     */
+    public static void reset() { UNIQUE_ID = 1; }
+  
+    /*
+     * hashCode and equals implementation to be added in later chapter.
+     */
+  
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java
new file mode 100644
index 00000000..be37c514
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -0,0 +1,39 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeBot;
+import com.seaofnodes.simple.type.TypeTuple;
+
+public class ProjNode extends Node {
+
+    // Which slice of the incoming multi-part value
+    public final int _idx;
+
+    // Debugging label
+    public final String _label;
+    
+    public ProjNode(MultiNode ctrl, int idx, String label) {
+        super(ctrl);
+        _idx = idx;
+        _label = label;
+    }
+
+    @Override
+    public String label() { return _label; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) { return sb.append("Proj_" +_nid); }
+
+    public MultiNode ctrl() { return (MultiNode)in(0); }
+
+    @Override
+    public Type compute() {
+        Type t = ctrl()._type;
+        return t instanceof TypeTuple tt ? tt._types[_idx] : TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() {
+        return null;
+    }
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
new file mode 100644
index 00000000..c94115bb
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -0,0 +1,40 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeBot;
+
+/**
+ * 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.
+ * <p>
+ * In this presentation, Return functions as a Stop node, since multiple <code>return</code> statements are not possible.
+ * The Stop node will be introduced in Chapter 6 when we implement <code>if</code> statements.
+ * <p>
+ * The Return's output is the value from the data node.
+ */
+public class ReturnNode extends Node implements Control {
+
+    public ReturnNode(Node ctrl, Node data) {
+        super(ctrl, data);
+    }
+
+    public Node ctrl() { return in(0); }
+    public Node expr() { return in(1); }
+  
+    @Override
+    public String label() { return "Return"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        return expr()._print0(sb.append("return ")).append(";");
+    }
+
+  
+    @Override
+    public Type compute() {
+        return expr().compute();
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
new file mode 100644
index 00000000..8bd81e82
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -0,0 +1,88 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.TypeBot;
+
+import java.util.*;
+
+/**
+ * The Scope node is a purely parser helper - it tracks names to nodes with a
+ * stack of scopes.
+ */
+public class ScopeNode extends Node {
+
+    /**
+     * Stack of lexical scopes, each scope is a symbol table
+     * that binds variable names to Nodes.
+     * The top of this stack represents current scope.
+     */
+    public final Stack<HashMap<String, Integer>> _scopes = new Stack<>();
+  
+    @Override
+    public String label() { return "Scope"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        for( HashMap<String,Integer> scope : _scopes ) {
+            sb.append("[");
+            boolean first=true;
+            for( String name : scope.keySet() ) {
+                if( !first ) sb.append(", ");
+                first=false;
+                sb.append(name).append(":");
+                Node n = in(scope.get(name));
+                if( n==null ) sb.append("null");
+                else n._print0(sb);
+            }
+            sb.append("]");
+        }
+        return sb;
+    }
+  
+    @Override
+    public TypeBot compute() { return TypeBot.BOTTOM; }
+
+    @Override
+    public Node idealize() { return null; }
+
+    // Add an empty lexical scope
+    public void push() {
+        _scopes.push(new HashMap<>());
+    }
+
+    // Remove the current lexical scope, killing all unused nodes.
+    public void pop() {
+        HashMap<String,Integer> scope = _scopes.pop();
+        pop_n(scope.size());
+    }
+
+    // Create a new name in the current scope
+    public Node define( String name, Node n ) {
+        HashMap<String,Integer> scope = _scopes.lastElement();
+        if( scope.put(name,nIns()) != null )
+            return null;        // Double define
+        return add_def(n);
+    }
+
+    // Lookup a name in all scopes
+    public Node lookup(String name) {
+        for (int i = _scopes.size() - 1; i >= 0; i--) {
+            var idx = _scopes.get(i).get(name);
+            if (idx != null) return in(idx);
+        }
+        return null;
+    }
+
+
+    // If the name is present in any scope, then redefine
+    public Node update(String name, Node n) {
+        for (int i = _scopes.size() - 1; i >= 0; i--) {
+            HashMap<String, Integer> scope = _scopes.get(i);
+            Integer idx = scope.get(name);
+            if (idx != null)           // Found prior def
+                return set_def(idx,n); // Update def in scope
+        }
+        return null;
+    }
+
+
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java
new file mode 100644
index 00000000..b59e3375
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -0,0 +1,46 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeBot;
+import com.seaofnodes.simple.type.TypeTuple;
+
+/**
+ * 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 MultiNode implements Control {
+
+    final TypeTuple _args;
+    
+    public StartNode(Type[] args) {
+        super();
+        _args = new TypeTuple(args);
+    }
+
+    @Override
+    public String label() { return "Start"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+      return sb.append(label());
+    }
+  
+    @Override
+    public TypeTuple compute() { return _args; }
+
+    @Override
+    public Node idealize() { return null; }
+
+    
+    @Override 
+    public ProjNode proj( int idx ) {
+        for( Node proj : _outputs )
+            if( ((ProjNode)proj)._idx==idx )
+                return (ProjNode)proj;
+        return null;
+    }
+  
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java
new file mode 100644
index 00000000..e5939e1b
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -0,0 +1,42 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeBot;
+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
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("("));
+        in(2)._print0(sb.append("-"));
+        return sb.append(")");
+    }
+  
+    @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 i0.meet(i1);
+        }
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() {
+        // Sub of same is 0
+        if( in(1)==in(2) )
+            return new ConstantNode(TypeInteger.constant(0));
+
+        return null;
+    }
+
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java
new file mode 100644
index 00000000..d9567dc8
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -0,0 +1,30 @@
+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 abstract class Type {
+
+    public static final TypeControl CONTROL = new TypeControl();
+
+    public boolean isConstant() { return false; }
+
+    public abstract StringBuilder _print(StringBuilder sb);
+
+    public Type meet(Type other) { return TypeBot.BOTTOM; }
+
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeBot.java b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeBot.java
new file mode 100644
index 00000000..a5709448
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeBot.java
@@ -0,0 +1,19 @@
+package com.seaofnodes.simple.type;
+
+import java.lang.StringBuilder;
+
+public class TypeBot extends Type {
+
+    public static final TypeBot BOTTOM = new TypeBot();
+  
+    @Override
+    public String toString() { return "Bottom"; }
+
+    @Override
+    public Type meet(Type other) {
+        return BOTTOM;
+    }
+
+    @Override
+    public StringBuilder _print(StringBuilder sb) { return sb.append(toString()); }
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeControl.java b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeControl.java
new file mode 100644
index 00000000..0130ffd0
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeControl.java
@@ -0,0 +1,16 @@
+package com.seaofnodes.simple.type;
+
+public class TypeControl extends Type {
+
+    public static final TypeControl CONTROL = new TypeControl();
+
+    @Override
+    public StringBuilder _print(StringBuilder sb) {
+        return sb.append(toString());
+    }
+
+    @Override
+    public String toString() {
+        return "Control";
+    }
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
new file mode 100644
index 00000000..e23840e0
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -0,0 +1,63 @@
+package com.seaofnodes.simple.type;
+
+/**
+ * Integer Type
+ */
+public class TypeInteger extends Type {
+
+    public final static TypeInteger TOP = new TypeInteger(false, 0);
+    public final static TypeInteger BOT = new TypeInteger(false, 1);
+
+    private final boolean _is_con;
+
+    /**
+     * The constant value or
+     * if not constant then 0=bottom, 1=top.
+     */
+    private final long _con;
+
+    public TypeInteger(boolean is_con, long con) { _is_con = is_con; _con = con; }
+
+    public static TypeInteger constant(long con) { return new TypeInteger(true, con); }
+
+    public boolean isTop() { return !_is_con && _con==0; }
+    public boolean isBot() { return !_is_con && _con==1; }
+
+    @Override
+    public String toString() {
+      return _print(new StringBuilder()).toString();
+    }
+
+    @Override 
+    public StringBuilder _print(StringBuilder sb) {
+        if (isTop()) return sb.append("IntTop");
+        if (isBot()) return sb.append("IntBot");
+        return sb.append(_con);
+    }
+
+    @Override
+    public boolean isConstant() { return _is_con; }
+
+    public long value() { return _con; }
+
+    @Override
+    public Type meet(Type other) {
+        if( this==other ) return this;
+        if (!(other instanceof TypeInteger i)) return super.meet(other);
+        // BOT wins
+        if (   isBot() ) return this;
+        if ( i.isBot() ) return i   ;
+        // TOP loses
+        if ( i.isTop() ) return this;
+        if (   isTop() ) return i   ;
+        assert isConstant() && i.isConstant();
+        return _con==i._con ? this : TypeInteger.BOT;
+    }
+
+    @Override
+    public boolean equals( Object o ) {
+        if( o==this ) return true;
+        if( !(o instanceof TypeInteger i) ) return false;
+        return _con==i._con && _is_con==i._is_con;
+    }
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
new file mode 100644
index 00000000..ef87a415
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
@@ -0,0 +1,20 @@
+package com.seaofnodes.simple.type;
+
+public class TypeTuple extends Type {
+
+    public final Type[] _types;
+
+    public TypeTuple(Type[] _types) {
+        this._types = _types;
+    }
+
+    @Override
+    public Type meet(Type other) {
+        throw new UnsupportedOperationException("Meet on Tuple Type not yet implemented");
+    }
+
+    @Override
+    public StringBuilder _print(StringBuilder sb) {
+        return sb;
+    }
+}