Backport some of the code refactoring to previous chapters (#50)

* #44 Revise docs and comments

* #44 Add starting scope to xScopes

* #44 back some of the code refactoring port to previous chapters

* #44 add_def should not be public

* #44 add_def should not be public. Rename method names so that they are camelcase

12 files changed, 295 insertions, 171 deletions

diff --git a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java
index b505c2c5..8daaed73 100644
--- a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java
@@ -14,11 +14,6 @@ import java.util.*;
  */
 public class Parser {
 
-    /**
-     * The control is a name that binds to the currently active control
-     * node in the graph
-     */
-    public static final String CTRL = "$ctrl";
   
     /**
      * A Global Static, unique to each compilation.  This is a public, so we
@@ -33,7 +28,7 @@ public class Parser {
     private final Lexer _lexer;
 
     /**
-     * Stack of lexical scopes, each scope is a symbol table that binds
+     * A ScopeNode contains a 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;
@@ -48,8 +43,8 @@ public class Parser {
 
 
     public Parser(String source, TypeInteger arg) {
-        _lexer = new Lexer(source);
         Node.reset();
+        _lexer = new Lexer(source);
         _scope = new ScopeNode();
         START = new StartNode(new Type[]{ Type.CONTROL, arg });
         START.peephole();
@@ -59,26 +54,29 @@ public class Parser {
         this(source, TypeInteger.BOT);
     }
 
+    @Override
+    public String toString() { return _lexer.toString(); }
+  
     String src() { return new String( _lexer._input ); }
 
+    // Debugging utility to find a Node by index
+    public static Node find(int nid) { return START.find(nid); }
+    
     private Node ctrl() { return _scope.ctrl(); }
 
     private Node ctrl(Node n) { return _scope.ctrl(n); }
 
     public ReturnNode parse() { return parse(false); }
     public ReturnNode parse(boolean show) {
+        // Enter a new scope for the initial control and arguments
         _scope.push();
-        try {
-            _scope.define(CTRL , new ProjNode(START, 0, CTRL ).peephole());
-            _scope.define("arg", new ProjNode(START, 1, "arg").peephole());
-            var ret = (ReturnNode) parseBlock();
-            if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
-            return ret;
-        }
-        finally {
-            _scope.pop();
-            if( show ) showGraph();
-        }
+        _scope.define(ScopeNode.CTRL, new ProjNode(START, 0, ScopeNode.CTRL).peephole());
+        _scope.define(ScopeNode.ARG0, new ProjNode(START, 1, ScopeNode.ARG0).peephole());
+        var ret = (ReturnNode) parseBlock();
+        _scope.pop();
+        if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
+        if( show ) showGraph();
+        return ret;
     }
 
     /**
@@ -199,12 +197,12 @@ public class Parser {
      */
     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();
+        if (match("==")) return new BoolNode.EQ(lhs, parseComparison()).peephole();
+        if (match("!=")) return new NotNode(new BoolNode.EQ(lhs, parseComparison()).peephole()).peephole();
+        if (match("<" )) return new BoolNode.LT(lhs, parseComparison()).peephole();
+        if (match("<=")) return new BoolNode.LE(lhs, parseComparison()).peephole();
+        if (match(">" )) return new BoolNode.LT(parseComparison(), lhs).peephole();
+        if (match(">=")) return new BoolNode.LE(parseComparison(), lhs).peephole();
         return lhs;
     }
 
@@ -450,5 +448,4 @@ public class Parser {
             return new String(_input, start, 1);
         }
     }
-
 }
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/Utils.java b/chapter04/src/main/java/com/seaofnodes/simple/Utils.java
new file mode 100644
index 00000000..4d663c25
--- /dev/null
+++ b/chapter04/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;
+    }
+}
\ No newline at end of file
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java
index 06be0b75..be3ee46c 100644
--- a/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -46,10 +46,7 @@ abstract public class BoolNode extends Node {
         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; } }
+    public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } }
+    public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs <  rhs; } }
+    public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } }
 }
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index ec85bf1f..ba6f55d7 100644
--- a/chapter04/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -23,7 +23,7 @@ public class ConstantNode extends Node {
     }
     
     @Override
-    public String label() { return "#"+_con; }
+    public String label() { return ""+_con; }
   
     @Override
     public String uniqueName() { return "Con_" + _nid; }
@@ -38,5 +38,4 @@ public class ConstantNode extends Node {
 
     @Override
     public Node idealize() { return null; }
-    
 }
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java
index fe3fddf8..81c90f68 100644
--- a/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java
+++ b/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java
@@ -1,7 +1,5 @@
 package com.seaofnodes.simple.node;
 
-import com.seaofnodes.simple.type.Type;
-
 public abstract class MultiNode extends Node {
     
     public MultiNode(Node... inputs) { super(inputs); }
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java
index b8a7bbd6..2b293193 100644
--- a/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
 
 import java.util.*;
@@ -70,7 +71,15 @@ public abstract class Node {
 
     // Graphical label, e.g. "+" or "Region" or "=="
     public String glabel() { return label(); }
+
+
+    // ------------------------------------------------------------------------
     
+    // Debugger Printing.
+    
+    // {@code toString} is what you get in the debugger.  It has to print 1
+    // line (because this is what a debugger typically displays by default) and
+    // has to be robust with broken graph/nodes.
     @Override
     public final String toString() {
         // TODO: This needs a lot of work
@@ -104,71 +113,14 @@ public abstract class Node {
 
     public int nIns() { return _inputs.size(); }
 
+    public Node out(int i) { return _outputs.get(i); }
+
     public int nOuts() { return _outputs.size(); }
 
     public boolean isUnused() { return nOuts() == 0; }
 
     public boolean isCFG() { return false; }
   
-    /**
-     * 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;
-    }
 
     
     /**
@@ -185,9 +137,9 @@ public abstract class Node {
      *     
      * @param idx which def to set
      * @param new_def the new definition
-     * @return this for flow coding
+     * @return new_def for flow coding
      */
-    Node set_def(int idx, Node new_def ) {
+    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
@@ -201,7 +153,7 @@ public abstract class Node {
         // Set the new_def over the old (killed) edge
         _inputs.set(idx,new_def);
         // Return self for easy flow-coding
-        return this;
+        return new_def;
     }
 
     /**
@@ -211,7 +163,7 @@ public abstract class Node {
      * @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) {
+    Node addDef(Node new_def) {
         // Add use->def edge
         _inputs.add(new_def);
         // If new def is not null, add the corresponding def->use edge
@@ -221,27 +173,21 @@ public abstract class Node {
     }
 
     // Breaks the edge invariants, used temporarily
-    private void addUse(Node n) { _outputs.add(n); }
+    protected <N extends Node> N addUse(Node n) { _outputs.add(n); return (N)this; }
 
     // 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 ) {
-        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;
+        Utils.del(_outputs, Utils.find(_outputs, use));
+        return _outputs.size() == 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) {
+    void popN(int n) {
         for( int i=0; i<n; i++ ) {
-            Node old_def = _inputs.remove(_inputs.size()-1);
+            Node old_def = _inputs.removeLast();
             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
@@ -251,17 +197,85 @@ public abstract class Node {
     /**
      * 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}.
+     * code elimination.  This function is co-recursive with {@link #popN}.
      */
     public void kill( ) {
         assert isUnused();      // Has no uses, so it is dead
-        pop_n(nIns());          // Set all inputs to null, recursively killing unused Nodes
+        popN(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; }
+
+    // Shortcuts to stop DCE mid-parse
+    // Add bogus null use to keep node alive
+    public <N extends Node> N keep() { return addUse(null); }
+    // Remove bogus null.
+    public <N extends Node> N unkeep() { delUse(null); return (N)this; }
+    // ------------------------------------------------------------------------
+    // Graph-based optimizations
+    
+    /**
+     * 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.keep();      // Keep m alive
+            kill();        // Kill self because replacing with 'm'
+            m.unkeep();    // Okay to peephole m
+        }
+        return m;
+    }
   
     /**
      * This function needs to be
@@ -329,7 +343,7 @@ public abstract class Node {
     public abstract Node idealize();
 
 
-    // -----------------------
+    // ------------------------------------------------------------------------
     // Peephole utilities
     
     // Swap inputs without letting either input go dead during the swap.
@@ -344,5 +358,25 @@ public abstract class Node {
      * 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; }
+    public static void reset() { UNIQUE_ID = 1; _disablePeephole=false; }
+
+    /**
+     * Debugging utility to find a Node by index
+     */
+    public Node find(int nid) { return _find(new BitSet(),nid); }
+    private Node _find(BitSet visit, int nid) {
+        if( _nid==nid ) return this;
+        if( visit.get(_nid) ) return null;
+        visit.set(_nid);
+        for( Node def : _inputs )
+            if( def!=null ) {
+                Node rez = def._find(visit,nid);
+                if( rez != null ) return rez;
+            }
+        for( Node use : _outputs ) {
+            Node rez = use._find(visit,nid);
+            if( rez != null ) return rez;
+        }
+        return null;
+    }
 }
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/NotNode.java
new file mode 100644
index 00000000..5dd6a86e
--- /dev/null
+++ b/chapter04/src/main/java/com/seaofnodes/simple/node/NotNode.java
@@ -0,0 +1,28 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class NotNode extends Node {
+    public NotNode(Node in) { super(null, in); }
+
+    @Override public String label() { return "Not"; }
+  
+    @Override public String glabel() { return "!"; }
+  
+    @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 i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0;
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index 6f36226b..5dd7a2f0 100644
--- a/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -30,10 +30,6 @@ public class ProjNode extends Node {
     @Override
     public Type compute() {
         Type t = ctrl()._type;
-        return getType(t);
-    }
-
-    private Type getType(Type t) {
         return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM;
     }
 
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index 73594d2a..d0d3eb06 100644
--- a/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -32,7 +32,7 @@ public class ReturnNode extends Node {
   
     @Override
     public Type compute() {
-      return new TypeTuple(Type.CONTROL,expr()._type);
+        return new TypeTuple(ctrl()._type,expr()._type);
     }
 
     @Override
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 17ea561a..c930fc65 100644
--- a/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -1,25 +1,34 @@
 package com.seaofnodes.simple.node;
 
-import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.type.Type;
 
 import java.util.*;
 
 /**
- * The Scope node is a purely parser helper - it tracks names to nodes with a
+ * The Scope node is purely a 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.
+     * The control is a name that binds to the currently active control
+     * node in the graph
      */
-    public final Stack<HashMap<String, Integer>> _scopes = new Stack<>();
+    public static final String CTRL = "$ctrl";
+    public static final String ARG0 = "arg";
 
-    // Reverse lookup for nicer graph printing
-    private final ArrayList<String> _rlabels = new ArrayList<>();
+    /**
+     * Names for every input edge
+     */
+    public final Stack<HashMap<String, Integer>> _scopes;
+
+
+    // A new ScopeNode
+    public ScopeNode() {
+        _scopes = new Stack<>();
+        _type = Type.BOTTOM;
+    }
+    
     
     @Override public String label() { return "Scope"; }
 
@@ -41,59 +50,85 @@ public class ScopeNode extends Node {
         }
         return sb;
     }
-  
-    @Override
-    public Type compute() { return Type.BOTTOM; }
-
-    @Override public Node idealize() { return null; }
 
-    // Add an empty lexical scope
-    public HashMap<String, Integer> push() {
-        return _scopes.push(new HashMap<>());
+    /**
+     * Recover the names for all variable bindings.
+     * The result is an array of names that is aligned with the
+     * inputs to the Node.
+     *
+     * This is an expensive operation.
+     */
+    public String[] reverseNames() {
+        String[] names = new String[nIns()];
+        for( HashMap<String,Integer> syms : _scopes )
+            for( String name : syms.keySet() )
+                names[syms.get(name)] = name;
+        return names;
     }
+    
+    @Override public Type compute() { return Type.BOTTOM; }
 
-    // Remove the current lexical scope, killing all unused nodes.
-    public void pop() {
-        HashMap<String,Integer> scope = _scopes.pop();
-        pop_n(scope.size());
-    }
+    @Override public Node idealize() { return null; }
 
-    // Create a new name in the current scope
+    public void push() { _scopes.push(new HashMap<>());  }
+    public void pop() { popN(_scopes.pop().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 )
+        HashMap<String,Integer> syms = _scopes.lastElement();
+        if( syms.put(name,nIns()) != null )
             return null;        // Double define
-        _rlabels.add(name);
-        return add_def(n);
+        return addDef(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;
+    /**
+     * Lookup a name in all scopes starting from most deeply nested.
+     *
+     * @param name Name to be looked up
+     * @see #update(String, Node, int)
+     */
+    public Node lookup( String name ) { return update(name,null,_scopes.size()-1);  }
+    /**
+     * If the name is present in any scope, then redefine else null
+     *
+     * @param name Name being redefined
+     * @param n    The node to bind to the name
+     */
+    public Node update( String name, Node n ) { return update(name,n,_scopes.size()-1); }
+    /**
+     * Both recursive lookup and update.
+     *
+     * A shared implementation allows us to create lazy phis both during
+     * lookups and updates; the lazy phi creation is part of chapter 8.
+     *
+     * @param name  Name whose binding is being updated or looked up
+     * @param n     If null, do a lookup, else update binding
+     * @param nestingLevel The starting nesting level
+     * @return node being looked up, or the one that was updated
+     */
+    private Node update( String name, Node n, int nestingLevel ) {
+        if( nestingLevel<0 ) return null;  // Missed in all scopes, not found
+        var syms = _scopes.get(nestingLevel); // Get the symbol table for nesting level
+        var idx = syms.get(name);
+        if( idx == null ) return update(name,n,nestingLevel-1); // Not found in this scope, recursively look in parent scope
+        Node old = in(idx);
+        // If n is null we are looking up rather than updating, hence return existing value
+        return n==null ? old : setDef(idx,n);
     }
 
-    public Node ctrl() { assert lookup(Parser.CTRL)==in(0); return in(0); }
-    
-    public Node ctrl(Node n) {
-        assert lookup(Parser.CTRL)==in(0);
-        set_def(0,n);
-        return n;
-    }
+    public Node ctrl() { return in(0); }
 
-  
-    // 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;
-    }
+    /**
+     * The ctrl of a ScopeNode is always bound to the currently active
+     * control node in the graph, via a special name '$ctrl' that is not
+     * a valid identifier in the language grammar and hence cannot be
+     * referenced in Simple code.
+     *
+     * @param n The node to be bound to '$ctrl'
+     *
+     * @return Node that was bound
+     */
+    public Node ctrl(Node n) { return setDef(0,n); }
 
 }
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 85c6cd34..e94c24e0 100644
--- a/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -17,6 +17,7 @@ public class StartNode extends MultiNode {
     public StartNode(Type[] args) {
         super();
         _args = new TypeTuple(args);
+        _type = _args;
     }
 
     @Override
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java
index a063e28e..170325f0 100644
--- a/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -32,7 +32,7 @@ public class Type {
     public final byte _type;
 
     public boolean is_simple() { return _type < TSIMPLE; }
-    private static final String[] STRS = new String[]{"BOTTOM","TOP","CONTROL"};
+    private static final String[] STRS = new String[]{"Bot","Top","Ctrl"};
     protected Type(byte type) { _type = type; }
 
     public static final Type BOTTOM   = new Type( TBOT   ); // ALL