Chapter 2 (#4)

* Start on Chapter 2.

* Start on Chapter 2.

* Refactor

* Refactor

* Initial attempt at peephole opt for add operation

* cleanup unused import

* Start on graph visualizer

* Start on graph visualizer

* Rework chapter 2

Add a short discourse on the Types, and provide a Bottom type.

Make a final toString; require each Node to specify its special printing via label().

Add a recursing printer called print(); toString is used by default in the debugger and so cannot be recursive.

Make the peephole rules based on a proper Type and idealize calls.
Big comments about the Type computations.

Every node picks up a _print, compute and idealize() call.

Rename long arith ops Divide, UnaryMinus, Multiply, Subtract into shorter uniform-length names.  Cleans up the parser where he does the precedence op parsing.

Rework Parser:
- Drop Token class, its all Strings except in the one place we know a number is coming
- Embed the Lexer as a field in the Parser, instead of trying to pass it around everywhere in the Parser
- StartNode becomes a read-only global, so we don't have to pass it around everywhere in the Parser AND optimizer.
- Lexer matches on strings and returns strings.  Match and consume *at the moment* instead of carrying around a current token/string and forcing the next-token after consuming the current one.
- All parse subexpressions shrink by 1/2 after these changes.

* Initial writeup of Chapter 2

* Initial writeup of Chapter 2

* Initial writeup of Chapter 2

* Initial writeup of Chapter 2

* Remove range

* progress Chapter 2

Drop integer ranges.
Broader lattice pic.
Lots of prose changes in the readme.
Fixed title in gviz dot generation.
Fixed bug with peephole making redundant constants.

* Implement compute for all the arithmetic node types
Add a flag to switch off peephole so we can see the full graph
Add post peephole graph to writeup

* Implement compute for all the arithmetic node types
Add a flag to switch off peephole so we can see the full graph
Add post peephole graph to writeup

* Fix bad path to the svg

* Update pre-peephole diagram

* Add dead code elimination

...and a set_def to proper update graph edges.

* Update README.md

* Cleanup the GraphVisualizer a bit.
Update the graphs.
Update the chapter list as chapter 3 deleted, and chapter 4 is now chapter 3.

---------

Co-authored-by: Cliff Click <cliffc@acm.org>

25 files changed, 1666 insertions, 0 deletions

diff --git a/chapter02/README.md b/chapter02/README.md
new file mode 100644
index 00000000..5b4c4958
--- /dev/null
+++ b/chapter02/README.md
@@ -0,0 +1,126 @@
+# Chapter 2
+
+In this chapter we extend the language grammar to include arithmetic operations such as addition, subtraction,
+multiplication, division, and unary minus. This allows us to write statements such as:
+
+```
+return 1 + 2 * 3 + -5;
+```
+
+Here is the [complete language grammar](docs/02-grammar.md) for this chapter. 
+
+## Extensions to Intermediate Representation
+
+In chapter 1 we introduced following nodes.
+
+| Node Name | Type    | Description                        | Inputs                                                           | Value                                                 |
+|-----------|---------|------------------------------------|------------------------------------------------------------------|-------------------------------------------------------|
+| Start     | Control | Start of function                  | None                                                             | None for now as we do not have function arguments yet |
+| Return    | Control | End of function                    | Predecessor control node, Data node value                        | Return value of the function                          |
+| Constant  | Data    | Constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant                                 |
+
+We extend the set of nodes by adding following additional node types.
+
+| Node Name  | Type | Description                   | Inputs                                                     | Value                       |
+|------------|------|-------------------------------|------------------------------------------------------------|-----------------------------|
+| Add        | Data | Add two values                | Two data nodes, values are added, order not important      | Result of the add operation |
+| Sub        | Data | Subtract a value from another | Two data nodes, values are subtracted, order matters       | Result of the subtract      |
+| Mul        | Data | Multiply two values           | Two data nodes, values are multiplied, order not important | Result of the multiply      |
+| Div        | Data | Divide a value by another     | Two data nodes, values are divided, order matters          | Result of the division      |
+| UnaryMinus | Data | Negate a value                | One data node, value is negated                            | Result of the unary minus   |
+
+## Peephole Optimizations
+
+Nodes in the graph can be peephole-optimized.  The graph is viewed through a
+"peephole", a small chunk of graph, and if a certain pattern is detected we
+locally rewrite the graph.
+
+During parsing, these peephole optimizations are particularly easy to check and
+apply: there are no uses (yet) of a just-created Node from a just-parsed piece
+of syntax, so there's no effort to the "rewrite" part of the problem. We just
+replace in-place before installing Nodes into the graph.
+
+This replacement might allow us to *kill* the unused inputs from the replaced
+Node, basically doing a modest Dead Code Elimination during parsing.
+
+E.g. Suppose we already parsed out a constant `1`, and a constant `2`; then when we
+parse an `Add(1,2)`, the peephole rule for constant math replaces the Add with a
+constant `3`.  At this point, we also *kill* the unused `Add`, which recursively
+may *kill* the unused constants `1` and `2`.
+
+
+
+## Constant Folding and Constant Propagation
+
+In this chapter and next we focus on a particular peephole optimization:
+constant folding and constant propagation.  Since we do not have variables
+until Chapter 3, the main feature we demonstrate now is constant folding.
+However, we introduce some additional ideas into the compiler at this stage, to
+set the scene for Chapter 3.
+
+It is useful for the compiler to know at various points of the program whether
+a node's value is a constant. The compiler can use this knowledge to perform various
+optimizations such as:
+
+* Evaluate expressions at compile time and replace an expression with a constant
+* The compiler may be able to identify regions of code that are dead and no
+  longer needed, such as when a conditional branch always take one of the
+  branches
+* Pointers may be known to be not-null, and a null check can be skipped.
+* Array indices may be known to be in-range, and a range check can be skipped
+* Many additional optimizations are possible when the compiler learns more
+  about the possible set of Node values
+
+In order to achieve above, we annotate Nodes with Types.
+
+The Type annotation serves two purposes:
+
+* it defines the set of operations allowed on the Node
+* it defines the set of values the Node takes on
+
+The type itself is identified by the Java class sub-typing relationship; all
+types are subtypes of the class `Type`.  For now, we only have the following
+hierarchy of types:
+
+```
+Type
++-- TypeInteger
+```
+
+It turns out that the set of values associated with a Type at a specific Node
+can be conveniently represented as a "lattice". Our lattice has the following
+structure:
+
+![Lattice](./docs/02-lattice.svg)
+
+Our lattice elements can be one of three types:
+
+* the highest element is "top", denoted by T.
+* The lowest is bottom, denoted by ⊥,
+* All elements in the middle are constants.
+
+Assigning ⊥ means that the Node's value is known to be not a compile time
+constant, whereas assigning T means that the Node's value may be some (as yet)
+undetermined constant.  The transition of the Node's type can occur from T to
+some constant to ⊥.
+
+In later chapters we will explore extending this lattice, as it frequently
+forms the heart of core optimizations we want our compiler to do.
+
+There are other important properties of the Lattice that we discuss in Chapter
+3, such as the "meet" operator and its rules.
+
+
+## Nodes Pre Peephole Optimization
+
+The following visual shows how the graph looks like pre-peephole optimization:
+
+![Example Visual](./docs/02-pre-peephole-ex1.svg)
+
+* Control nodes appear as square boxes
+* Control edges are in bold red
+* The edges from Start to Constants are shown in dotted lines as these are not true def-use edges
+
+## Post-peephole
+
+![Example Visual](./docs/02-post-peephole-ex1.svg)
\ No newline at end of file
diff --git a/chapter02/docs/02-grammar.md b/chapter02/docs/02-grammar.md
new file mode 100644
index 00000000..a4a79cea
--- /dev/null
+++ b/chapter02/docs/02-grammar.md
@@ -0,0 +1,39 @@
+# Grammar for Chapter 1
+
+```antlrv4
+grammar SimpleLanguage;
+
+program
+    : statement EOF
+    ;
+
+statement
+    : 'return' expression ';'
+    ;
+
+expression
+    : additiveExpression
+    ;
+    
+additiveExpression
+    : multiplicativeExpression (('+' | '-') multiplicativeExpression)*    
+    ;
+    
+multiplicativeExpression
+    : unaryExpression (('*' | '/') unaryExpression)*
+    ;
+
+unaryExpression
+    : ('-') unaryExpression
+    | primaryExpression
+    ;
+
+primaryExpression
+    : INTEGER_LITERAL
+    ;
+
+INTEGER_LITERAL
+    : [1-9][0-9]*
+    | [0]
+    ;    
+```
\ No newline at end of file
diff --git a/chapter02/docs/02-lattice.gv b/chapter02/docs/02-lattice.gv
new file mode 100644
index 00000000..57f14d77
--- /dev/null
+++ b/chapter02/docs/02-lattice.gv
@@ -0,0 +1,35 @@
+digraph Lattice {
+    // Define nodes
+    node [shape=circle, style=filled, fillcolor=lightblue];
+    Top [label="⊤"];
+    Bottom [label="⊥"];
+    
+    A [label="MIN_INT"];
+    B [label="..." shape=none style=none];
+    C [label="-1"];
+    D [label="0"];
+    E [label="1"];
+    F [label="..." shape=none style=none];
+    G [label="MAX_INT"];
+
+
+    // Define edges
+    Top -> A [arrowhead=none];
+    Top -> B [arrowhead=none];
+    Top -> C [arrowhead=none];
+    Top -> D [arrowhead=none];
+    Top -> E [arrowhead=none];
+    Top -> F [arrowhead=none];
+    Top -> G [arrowhead=none];
+    A -> Bottom [arrowhead=none];
+    B -> Bottom [arrowhead=none];
+    C -> Bottom [arrowhead=none];
+    D -> Bottom [arrowhead=none];
+    E -> Bottom [arrowhead=none];
+    F -> Bottom [arrowhead=none];
+    G -> Bottom [arrowhead=none];
+
+    // Additional customization
+    {rank=same; A; B; C; D; E; F; G; }
+    {rank=same; Bottom;}
+}
diff --git a/chapter02/docs/02-lattice.svg b/chapter02/docs/02-lattice.svg
new file mode 100644
index 00000000..218acc6a
--- /dev/null
+++ b/chapter02/docs/02-lattice.svg
@@ -0,0 +1,143 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
+        "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 2.43.0 (0)
+ -->
+<!-- Title: Lattice Pages: 1 -->
+<svg width="548pt" height="266pt"
+     viewBox="0.00 0.00 547.59 265.88" xmlns="http://www.w3.org/2000/svg">
+    <g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 261.88)">
+        <title>Lattice</title>
+        <polygon fill="white" stroke="transparent" points="-4,4 -4,-261.88 543.59,-261.88 543.59,4 -4,4"/>
+        <!-- Top -->
+        <g id="node1" class="node">
+            <title>Top</title>
+            <ellipse fill="lightblue" stroke="black" cx="269.65" cy="-238.39" rx="19.5" ry="19.5"/>
+            <text text-anchor="middle" x="269.65" y="-234.69" font-family="Times,serif" font-size="14.00">⊤</text>
+        </g>
+        <!-- A -->
+        <g id="node3" class="node">
+            <title>A</title>
+            <ellipse fill="lightblue" stroke="black" cx="52.65" cy="-128.94" rx="52.79" ry="52.79"/>
+            <text text-anchor="middle" x="52.65" y="-125.24" font-family="Times,serif" font-size="14.00">MIN_INT</text>
+        </g>
+        <!-- Top&#45;&gt;A -->
+        <g id="edge1" class="edge">
+            <title>Top&#45;&gt;A</title>
+            <path fill="none" stroke="black"
+                  d="M250.55,-233.09C220.3,-225.77 160.13,-209.08 114.65,-182.89 106.3,-178.08 98.02,-172.1 90.35,-165.89"/>
+        </g>
+        <!-- B -->
+        <g id="node4" class="node">
+            <title>B</title>
+            <text text-anchor="middle" x="150.65" y="-125.24" font-family="Times,serif" font-size="14.00">...</text>
+        </g>
+        <!-- Top&#45;&gt;B -->
+        <g id="edge2" class="edge">
+            <title>Top&#45;&gt;B</title>
+            <path fill="none" stroke="black"
+                  d="M252.34,-228.66C234.5,-219.09 206.55,-202.47 186.65,-182.89 175.87,-172.28 166.38,-158 159.86,-146.95"/>
+        </g>
+        <!-- C -->
+        <g id="node5" class="node">
+            <title>C</title>
+            <ellipse fill="lightblue" stroke="black" cx="214.65" cy="-128.94" rx="19.5" ry="19.5"/>
+            <text text-anchor="middle" x="214.65" y="-125.24" font-family="Times,serif" font-size="14.00">&#45;1</text>
+        </g>
+        <!-- Top&#45;&gt;C -->
+        <g id="edge3" class="edge">
+            <title>Top&#45;&gt;C</title>
+            <path fill="none" stroke="black" d="M261.05,-220.6C250.72,-200.41 233.48,-166.74 223.18,-146.61"/>
+        </g>
+        <!-- D -->
+        <g id="node6" class="node">
+            <title>D</title>
+            <ellipse fill="lightblue" stroke="black" cx="269.65" cy="-128.94" rx="18" ry="18"/>
+            <text text-anchor="middle" x="269.65" y="-125.24" font-family="Times,serif" font-size="14.00">0</text>
+        </g>
+        <!-- Top&#45;&gt;D -->
+        <g id="edge4" class="edge">
+            <title>Top&#45;&gt;D</title>
+            <path fill="none" stroke="black" d="M269.65,-218.67C269.65,-198.47 269.65,-166.57 269.65,-147.03"/>
+        </g>
+        <!-- E -->
+        <g id="node7" class="node">
+            <title>E</title>
+            <ellipse fill="lightblue" stroke="black" cx="323.65" cy="-128.94" rx="18" ry="18"/>
+            <text text-anchor="middle" x="323.65" y="-125.24" font-family="Times,serif" font-size="14.00">1</text>
+        </g>
+        <!-- Top&#45;&gt;E -->
+        <g id="edge5" class="edge">
+            <title>Top&#45;&gt;E</title>
+            <path fill="none" stroke="black" d="M278.08,-220.6C288.46,-199.94 305.94,-165.16 315.97,-145.22"/>
+        </g>
+        <!-- F -->
+        <g id="node8" class="node">
+            <title>F</title>
+            <text text-anchor="middle" x="386.65" y="-125.24" font-family="Times,serif" font-size="14.00">...</text>
+        </g>
+        <!-- Top&#45;&gt;F -->
+        <g id="edge6" class="edge">
+            <title>Top&#45;&gt;F</title>
+            <path fill="none" stroke="black"
+                  d="M286.52,-228.57C303.92,-218.93 331.18,-202.25 350.65,-182.89 361.2,-172.38 370.57,-158.37 377.1,-147.4"/>
+        </g>
+        <!-- G -->
+        <g id="node9" class="node">
+            <title>G</title>
+            <ellipse fill="lightblue" stroke="black" cx="485.65" cy="-128.94" rx="53.89" ry="53.89"/>
+            <text text-anchor="middle" x="485.65" y="-125.24" font-family="Times,serif" font-size="14.00">MAX_INT</text>
+        </g>
+        <!-- Top&#45;&gt;G -->
+        <g id="edge7" class="edge">
+            <title>Top&#45;&gt;G</title>
+            <path fill="none" stroke="black"
+                  d="M288.46,-233C318.29,-225.56 377.63,-208.69 422.65,-182.89 430.83,-178.2 438.98,-172.41 446.57,-166.39"/>
+        </g>
+        <!-- Bottom -->
+        <g id="node2" class="node">
+            <title>Bottom</title>
+            <ellipse fill="lightblue" stroke="black" cx="269.65" cy="-19.5" rx="19.5" ry="19.5"/>
+            <text text-anchor="middle" x="269.65" y="-15.8" font-family="Times,serif" font-size="14.00">⊥</text>
+        </g>
+        <!-- A&#45;&gt;Bottom -->
+        <g id="edge8" class="edge">
+            <title>A&#45;&gt;Bottom</title>
+            <path fill="none" stroke="black"
+                  d="M90.35,-91.99C98.02,-85.79 106.3,-79.8 114.65,-75 160.13,-48.81 220.3,-32.11 250.55,-24.79"/>
+        </g>
+        <!-- B&#45;&gt;Bottom -->
+        <g id="edge9" class="edge">
+            <title>B&#45;&gt;Bottom</title>
+            <path fill="none" stroke="black"
+                  d="M159.86,-110.94C166.38,-99.88 175.87,-85.6 186.65,-75 206.55,-55.41 234.5,-38.79 252.34,-29.22"/>
+        </g>
+        <!-- C&#45;&gt;Bottom -->
+        <g id="edge10" class="edge">
+            <title>C&#45;&gt;Bottom</title>
+            <path fill="none" stroke="black" d="M223.24,-111.15C233.57,-90.97 250.81,-57.3 261.11,-37.17"/>
+        </g>
+        <!-- D&#45;&gt;Bottom -->
+        <g id="edge11" class="edge">
+            <title>D&#45;&gt;Bottom</title>
+            <path fill="none" stroke="black" d="M269.65,-110.68C269.65,-91.1 269.65,-59.3 269.65,-39.16"/>
+        </g>
+        <!-- E&#45;&gt;Bottom -->
+        <g id="edge12" class="edge">
+            <title>E&#45;&gt;Bottom</title>
+            <path fill="none" stroke="black" d="M315.91,-112.55C305.88,-92.59 288.44,-57.9 278.08,-37.28"/>
+        </g>
+        <!-- F&#45;&gt;Bottom -->
+        <g id="edge13" class="edge">
+            <title>F&#45;&gt;Bottom</title>
+            <path fill="none" stroke="black"
+                  d="M377.1,-110.49C370.57,-99.52 361.2,-85.5 350.65,-75 331.18,-55.63 303.92,-38.95 286.52,-29.31"/>
+        </g>
+        <!-- G&#45;&gt;Bottom -->
+        <g id="edge14" class="edge">
+            <title>G&#45;&gt;Bottom</title>
+            <path fill="none" stroke="black"
+                  d="M446.57,-91.49C438.98,-85.48 430.83,-79.69 422.65,-75 377.63,-49.19 318.29,-32.33 288.46,-24.88"/>
+        </g>
+    </g>
+</svg>
diff --git a/chapter02/docs/02-post-peephole-ex1.gv b/chapter02/docs/02-post-peephole-ex1.gv
new file mode 100644
index 00000000..a39d602b
--- /dev/null
+++ b/chapter02/docs/02-post-peephole-ex1.gv
@@ -0,0 +1,10 @@
+digraph chapter02
+{
+	Start1 [shape=box,  label="Start"];
+	Con213 [ label="Con2"];
+	Start1 -> Con213 [style=dotted];
+	Return14 [shape=box,  label="Return"];
+	Con213 -> Return14;
+	edge [color=red];
+	Start1 -> Return14;
+}
\ No newline at end of file
diff --git a/chapter02/docs/02-post-peephole-ex1.svg b/chapter02/docs/02-post-peephole-ex1.svg
new file mode 100644
index 00000000..33aa5a95
--- /dev/null
+++ b/chapter02/docs/02-post-peephole-ex1.svg
@@ -0,0 +1,51 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
+        "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 2.43.0 (0)
+ -->
+<!-- Title: chapter02 Pages: 1 -->
+<svg width="106pt" height="188pt"
+     viewBox="0.00 0.00 106.45 188.00" xmlns="http://www.w3.org/2000/svg">
+    <g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 184)">
+        <title>chapter02</title>
+        <polygon fill="white" stroke="transparent" points="-4,4 -4,-184 102.45,-184 102.45,4 -4,4"/>
+        <!-- Start1 -->
+        <g id="node1" class="node">
+            <title>Start1</title>
+            <polygon fill="none" stroke="black" points="92.45,-180 38.45,-180 38.45,-144 92.45,-144 92.45,-180"/>
+            <text text-anchor="middle" x="65.45" y="-158.3" font-family="Times,serif" font-size="14.00">Start</text>
+        </g>
+        <!-- Con213 -->
+        <g id="node2" class="node">
+            <title>Con213</title>
+            <ellipse fill="none" stroke="black" cx="34.45" cy="-90" rx="34.39" ry="18"/>
+            <text text-anchor="middle" x="34.45" y="-86.3" font-family="Times,serif" font-size="14.00">Con2</text>
+        </g>
+        <!-- Start1&#45;&gt;Con213 -->
+        <g id="edge1" class="edge">
+            <title>Start1&#45;&gt;Con213</title>
+            <path fill="none" stroke="black" stroke-dasharray="1,5"
+                  d="M57.78,-143.7C54.2,-135.61 49.86,-125.81 45.9,-116.87"/>
+            <polygon fill="black" stroke="black" points="49.06,-115.35 41.81,-107.62 42.66,-118.18 49.06,-115.35"/>
+        </g>
+        <!-- Return14 -->
+        <g id="node3" class="node">
+            <title>Return14</title>
+            <polygon fill="none" stroke="black" points="98.45,-36 32.45,-36 32.45,0 98.45,0 98.45,-36"/>
+            <text text-anchor="middle" x="65.45" y="-14.3" font-family="Times,serif" font-size="14.00">Return</text>
+        </g>
+        <!-- Start1&#45;&gt;Return14 -->
+        <g id="edge3" class="edge">
+            <title>Start1&#45;&gt;Return14</title>
+            <path fill="none" stroke="red"
+                  d="M70.32,-143.98C73.01,-133.67 76.08,-120.19 77.45,-108 79.22,-92.1 79.22,-87.9 77.45,-72 76.49,-63.43 74.69,-54.22 72.76,-45.93"/>
+            <polygon fill="red" stroke="red" points="76.11,-44.89 70.32,-36.02 69.32,-46.57 76.11,-44.89"/>
+        </g>
+        <!-- Con213&#45;&gt;Return14 -->
+        <g id="edge2" class="edge">
+            <title>Con213&#45;&gt;Return14</title>
+            <path fill="none" stroke="black" d="M41.79,-72.41C45.32,-64.45 49.63,-54.72 53.6,-45.76"/>
+            <polygon fill="black" stroke="black" points="56.87,-47.01 57.72,-36.45 50.47,-44.17 56.87,-47.01"/>
+        </g>
+    </g>
+</svg>
diff --git a/chapter02/docs/02-pre-peephole-ex1.gv b/chapter02/docs/02-pre-peephole-ex1.gv
new file mode 100644
index 00000000..d5a16616
--- /dev/null
+++ b/chapter02/docs/02-pre-peephole-ex1.gv
@@ -0,0 +1,27 @@
+digraph chapter02
+{
+	Start1 [shape=box,  label="Start"];
+	Con12 [ label="Con1"];
+	Start1 -> Con12 [style=dotted];
+	Con23 [ label="Con2"];
+	Start1 -> Con23 [style=dotted];
+	Con34 [ label="Con3"];
+	Start1 -> Con34 [style=dotted];
+	Mul5 [ label="Mul"];
+	Con23 -> Mul5;
+	Con34 -> Mul5;
+	Con56 [ label="Con5"];
+	Start1 -> Con56 [style=dotted];
+	Minus7 [ label="Minus"];
+	Con56 -> Minus7;
+	Add8 [ label="Add"];
+	Mul5 -> Add8;
+	Minus7 -> Add8;
+	Add9 [ label="Add"];
+	Con12 -> Add9;
+	Add8 -> Add9;
+	Return10 [shape=box,  label="Return"];
+	Add9 -> Return10;
+	edge [color=red];
+	Start1 -> Return10;
+}
\ No newline at end of file
diff --git a/chapter02/docs/02-pre-peephole-ex1.svg b/chapter02/docs/02-pre-peephole-ex1.svg
new file mode 100644
index 00000000..dc33c7f5
--- /dev/null
+++ b/chapter02/docs/02-pre-peephole-ex1.svg
@@ -0,0 +1,156 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
+        "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 2.43.0 (0)
+ -->
+<!-- Title: chapter02 Pages: 1 -->
+<svg width="301pt" height="404pt"
+     viewBox="0.00 0.00 301.08 404.00" xmlns="http://www.w3.org/2000/svg">
+    <g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 400)">
+        <title>chapter02</title>
+        <polygon fill="white" stroke="transparent" points="-4,4 -4,-400 297.08,-400 297.08,4 -4,4"/>
+        <!-- Start1 -->
+        <g id="node1" class="node">
+            <title>Start1</title>
+            <polygon fill="none" stroke="black" points="169.34,-396 115.34,-396 115.34,-360 169.34,-360 169.34,-396"/>
+            <text text-anchor="middle" x="142.34" y="-374.3" font-family="Times,serif" font-size="14.00">Start</text>
+        </g>
+        <!-- Con12 -->
+        <g id="node2" class="node">
+            <title>Con12</title>
+            <ellipse fill="none" stroke="black" cx="46.34" cy="-162" rx="34.39" ry="18"/>
+            <text text-anchor="middle" x="46.34" y="-158.3" font-family="Times,serif" font-size="14.00">Con1</text>
+        </g>
+        <!-- Start1&#45;&gt;Con12 -->
+        <g id="edge1" class="edge">
+            <title>Start1&#45;&gt;Con12</title>
+            <path fill="none" stroke="black" stroke-dasharray="1,5"
+                  d="M115.19,-374.6C84.32,-370.26 35.25,-358.08 12.34,-324 -15.78,-282.17 11,-221.54 30.37,-187.88"/>
+            <polygon fill="black" stroke="black" points="33.47,-189.52 35.59,-179.14 27.46,-185.93 33.47,-189.52"/>
+        </g>
+        <!-- Con23 -->
+        <g id="node3" class="node">
+            <title>Con23</title>
+            <ellipse fill="none" stroke="black" cx="55.34" cy="-306" rx="34.39" ry="18"/>
+            <text text-anchor="middle" x="55.34" y="-302.3" font-family="Times,serif" font-size="14.00">Con2</text>
+        </g>
+        <!-- Start1&#45;&gt;Con23 -->
+        <g id="edge2" class="edge">
+            <title>Start1&#45;&gt;Con23</title>
+            <path fill="none" stroke="black" stroke-dasharray="1,5"
+                  d="M120.83,-359.7C108.86,-350.07 93.88,-338.01 81.26,-327.86"/>
+            <polygon fill="black" stroke="black" points="83.35,-325.05 73.37,-321.51 78.97,-330.5 83.35,-325.05"/>
+        </g>
+        <!-- Con34 -->
+        <g id="node4" class="node">
+            <title>Con34</title>
+            <ellipse fill="none" stroke="black" cx="142.34" cy="-306" rx="34.39" ry="18"/>
+            <text text-anchor="middle" x="142.34" y="-302.3" font-family="Times,serif" font-size="14.00">Con3</text>
+        </g>
+        <!-- Start1&#45;&gt;Con34 -->
+        <g id="edge3" class="edge">
+            <title>Start1&#45;&gt;Con34</title>
+            <path fill="none" stroke="black" stroke-dasharray="1,5"
+                  d="M142.34,-359.7C142.34,-351.98 142.34,-342.71 142.34,-334.11"/>
+            <polygon fill="black" stroke="black" points="145.84,-334.1 142.34,-324.1 138.84,-334.1 145.84,-334.1"/>
+        </g>
+        <!-- Con56 -->
+        <g id="node6" class="node">
+            <title>Con56</title>
+            <ellipse fill="none" stroke="black" cx="229.34" cy="-306" rx="34.39" ry="18"/>
+            <text text-anchor="middle" x="229.34" y="-302.3" font-family="Times,serif" font-size="14.00">Con5</text>
+        </g>
+        <!-- Start1&#45;&gt;Con56 -->
+        <g id="edge6" class="edge">
+            <title>Start1&#45;&gt;Con56</title>
+            <path fill="none" stroke="black" stroke-dasharray="1,5"
+                  d="M163.84,-359.7C175.81,-350.07 190.8,-338.01 203.41,-327.86"/>
+            <polygon fill="black" stroke="black" points="205.71,-330.5 211.31,-321.51 201.32,-325.05 205.71,-330.5"/>
+        </g>
+        <!-- Return10 -->
+        <g id="node10" class="node">
+            <title>Return10</title>
+            <polygon fill="none" stroke="black" points="268.34,-36 202.34,-36 202.34,0 268.34,0 268.34,-36"/>
+            <text text-anchor="middle" x="235.34" y="-14.3" font-family="Times,serif" font-size="14.00">Return</text>
+        </g>
+        <!-- Start1&#45;&gt;Return10 -->
+        <g id="edge13" class="edge">
+            <title>Start1&#45;&gt;Return10</title>
+            <path fill="none" stroke="red"
+                  d="M169.34,-373.51C199.13,-368.18 246.29,-355.12 272.34,-324 298.3,-292.99 291.34,-275.45 291.34,-235 291.34,-235 291.34,-235 291.34,-161 291.34,-117.91 268.74,-72.26 252.26,-44.7"/>
+            <polygon fill="red" stroke="red" points="255.17,-42.75 246.94,-36.07 249.21,-46.42 255.17,-42.75"/>
+        </g>
+        <!-- Add9 -->
+        <g id="node9" class="node">
+            <title>Add9</title>
+            <ellipse fill="none" stroke="black" cx="180.34" cy="-90" rx="28.7" ry="18"/>
+            <text text-anchor="middle" x="180.34" y="-86.3" font-family="Times,serif" font-size="14.00">Add</text>
+        </g>
+        <!-- Con12&#45;&gt;Add9 -->
+        <g id="edge10" class="edge">
+            <title>Con12&#45;&gt;Add9</title>
+            <path fill="none" stroke="black" d="M69.99,-148.65C92.27,-137 125.77,-119.5 150.02,-106.84"/>
+            <polygon fill="black" stroke="black" points="151.89,-109.81 159.13,-102.08 148.65,-103.61 151.89,-109.81"/>
+        </g>
+        <!-- Mul5 -->
+        <g id="node5" class="node">
+            <title>Mul5</title>
+            <ellipse fill="none" stroke="black" cx="137.34" cy="-234" rx="28.7" ry="18"/>
+            <text text-anchor="middle" x="137.34" y="-230.3" font-family="Times,serif" font-size="14.00">Mul</text>
+        </g>
+        <!-- Con23&#45;&gt;Mul5 -->
+        <g id="edge4" class="edge">
+            <title>Con23&#45;&gt;Mul5</title>
+            <path fill="none" stroke="black" d="M72.73,-290.15C84.56,-280.05 100.38,-266.55 113.4,-255.43"/>
+            <polygon fill="black" stroke="black" points="115.76,-258.03 121.09,-248.87 111.21,-252.7 115.76,-258.03"/>
+        </g>
+        <!-- Con34&#45;&gt;Mul5 -->
+        <g id="edge5" class="edge">
+            <title>Con34&#45;&gt;Mul5</title>
+            <path fill="none" stroke="black" d="M141.1,-287.7C140.55,-279.98 139.89,-270.71 139.27,-262.11"/>
+            <polygon fill="black" stroke="black" points="142.76,-261.83 138.56,-252.1 135.78,-262.33 142.76,-261.83"/>
+        </g>
+        <!-- Add8 -->
+        <g id="node8" class="node">
+            <title>Add8</title>
+            <ellipse fill="none" stroke="black" cx="180.34" cy="-162" rx="28.7" ry="18"/>
+            <text text-anchor="middle" x="180.34" y="-158.3" font-family="Times,serif" font-size="14.00">Add</text>
+        </g>
+        <!-- Mul5&#45;&gt;Add8 -->
+        <g id="edge8" class="edge">
+            <title>Mul5&#45;&gt;Add8</title>
+            <path fill="none" stroke="black" d="M147.31,-216.76C152.58,-208.19 159.15,-197.49 165.04,-187.9"/>
+            <polygon fill="black" stroke="black" points="168.17,-189.5 170.42,-179.15 162.2,-185.84 168.17,-189.5"/>
+        </g>
+        <!-- Minus7 -->
+        <g id="node7" class="node">
+            <title>Minus7</title>
+            <ellipse fill="none" stroke="black" cx="223.34" cy="-234" rx="39.79" ry="18"/>
+            <text text-anchor="middle" x="223.34" y="-230.3" font-family="Times,serif" font-size="14.00">Minus</text>
+        </g>
+        <!-- Con56&#45;&gt;Minus7 -->
+        <g id="edge7" class="edge">
+            <title>Con56&#45;&gt;Minus7</title>
+            <path fill="none" stroke="black" d="M227.85,-287.7C227.19,-279.98 226.4,-270.71 225.66,-262.11"/>
+            <polygon fill="black" stroke="black" points="229.15,-261.77 224.8,-252.1 222.17,-262.37 229.15,-261.77"/>
+        </g>
+        <!-- Minus7&#45;&gt;Add8 -->
+        <g id="edge9" class="edge">
+            <title>Minus7&#45;&gt;Add8</title>
+            <path fill="none" stroke="black" d="M213.15,-216.41C207.88,-207.83 201.34,-197.19 195.49,-187.67"/>
+            <polygon fill="black" stroke="black" points="198.38,-185.68 190.16,-178.99 192.41,-189.34 198.38,-185.68"/>
+        </g>
+        <!-- Add8&#45;&gt;Add9 -->
+        <g id="edge11" class="edge">
+            <title>Add8&#45;&gt;Add9</title>
+            <path fill="none" stroke="black" d="M180.34,-143.7C180.34,-135.98 180.34,-126.71 180.34,-118.11"/>
+            <polygon fill="black" stroke="black" points="183.84,-118.1 180.34,-108.1 176.84,-118.1 183.84,-118.1"/>
+        </g>
+        <!-- Add9&#45;&gt;Return10 -->
+        <g id="edge12" class="edge">
+            <title>Add9&#45;&gt;Return10</title>
+            <path fill="none" stroke="black" d="M192.54,-73.46C199.2,-64.99 207.61,-54.29 215.21,-44.61"/>
+            <polygon fill="black" stroke="black" points="218.19,-46.49 221.62,-36.46 212.69,-42.16 218.19,-46.49"/>
+        </g>
+    </g>
+</svg>
diff --git a/chapter02/pom.xml b/chapter02/pom.xml
new file mode 100644
index 00000000..5ced95c3
--- /dev/null
+++ b/chapter02/pom.xml
@@ -0,0 +1,14 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<project xmlns="http://maven.apache.org/POM/4.0.0"
+         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+    <modelVersion>4.0.0</modelVersion>
+    <parent>
+        <groupId>com.seaofnodes</groupId>
+        <artifactId>simple</artifactId>
+        <version>1.0</version>
+    </parent>
+    <artifactId>chapter02</artifactId>
+    <packaging>jar</packaging>
+    <name>Chapter 2</name>
+</project>
\ No newline at end of file
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
new file mode 100644
index 00000000..d2aa8179
--- /dev/null
+++ b/chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -0,0 +1,102 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.ConstantNode;
+import com.seaofnodes.simple.node.Control;
+import com.seaofnodes.simple.node.Node;
+import com.seaofnodes.simple.node.StartNode;
+
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * 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(StartNode start) {
+        // Since the graph has cycles, we need to create a flat list of all the
+        // nodes in the graph.
+        Collection<Node> all = findAll(start);
+        StringBuilder sb = new StringBuilder();
+        sb.append("digraph chapter02\n" +
+                "{\n");
+        for (Node n : all) {
+            sb.append('\t').append(n.uniqueName());
+            // control nodes have box shape
+            // other nodes are ellipses, i.e. default shape
+            if (n instanceof Control)
+                sb.append(" [shape=box, ");
+            else
+                sb.append(" [");
+            sb.append(" label=\"")
+                    .append(n.label())
+                    .append("\"];\n");
+            // Output the non control edges
+            walkIns(sb, n, false);
+        }
+        // Now output the control edges which must be in red
+        sb.append("\tedge [color=red];\n");
+        for (Node n : all) {
+            walkIns(sb, n, true);
+        }
+        sb.append("}\n");
+        return sb.toString();
+    }
+
+    /**
+     * Outputs edges. If doControlEdges is true then
+     * edges between control nodes are output. Else other edges
+     * output.
+     */
+    private void walkIns(StringBuilder sb, Node in, boolean doControlEdges) {
+        for (int i = 0; i < in.nIns(); i++) {
+            Node out = in.in(i);
+            if (out == null)
+                continue;
+            boolean isControlEdge = (out instanceof Control) && (in instanceof Control);
+            if (doControlEdges && !isControlEdge)
+                continue;
+            if (!doControlEdges && isControlEdge)
+                continue;
+            sb.append('\t')
+                    .append(out.uniqueName())
+                    .append(" -> ")
+                    .append(in.uniqueName());
+            // the edge from start node to constants is just for convenience so
+            // show it differently
+            if ((out instanceof StartNode) && (in instanceof ConstantNode))
+                sb.append(" [style=dotted]");
+            sb.append(";\n");
+        }
+    }
+
+    /**
+     * Walks the whole graph, starting from Start.
+     * Since Start is the input to all constants - we look at the outputs for
+     * Start, but for then subsequently we look at the inputs of each node.
+     */
+    private Collection<Node> findAll(StartNode start) {
+        Map<Integer, Node> all = new HashMap<>();
+        for (int i = 0; i < start.nOuts(); i++) {
+            Node n = start.out(i);
+            walk(all, n);
+        }
+        return all.values();
+    }
+
+    /**
+     * Walk a subgraph and populate distinct nodes in the _all list.
+     */
+    private void walk(Map<Integer, Node> all, Node n) {
+        if (all.get(n._nid) == null) {
+            // Not yet seen
+            all.put(n._nid, n);
+            for (Node c : n._inputs)
+                if (c != null)
+                    walk(all, c);
+        }
+    }
+}
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/Parser.java b/chapter02/src/main/java/com/seaofnodes/simple/Parser.java
new file mode 100644
index 00000000..27a7cffd
--- /dev/null
+++ b/chapter02/src/main/java/com/seaofnodes/simple/Parser.java
@@ -0,0 +1,269 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
+
+/**
+ * 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 {
+
+    private final Lexer _lexer;
+
+    /**
+     * 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;
+
+    public Parser( String source ) {
+        _lexer = new Lexer(source);
+        Node.reset();
+        START = new StartNode();
+    }
+    
+    public ReturnNode parse() {
+        return parseReturn();
+    }
+
+    /**
+     * Parses return statement.
+     *
+     * <pre>
+     *     return expr ;
+     * </pre>
+     */
+    private ReturnNode parseReturn() {
+        require("return");
+        var returnExpr = parseExpression();
+        require(";");
+        return new ReturnNode(START, returnExpr);
+    }
+
+    /**
+     * Parse an expression of the form:
+     *
+     * <pre>
+     *     expr : additiveExpr
+     * </pre>
+     */
+    private Node parseExpression() {
+        return parseAddition();
+    }
+
+    /**
+     * 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
+     * </pre>
+     */
+    private Node parsePrimary() {
+        if( _lexer.isNumber() )
+            return parseIntegerLiteral();
+        throw error("syntax error, expected integer literal");
+    }
+
+    /**
+     * Parse integer literal
+     *
+     * <pre>
+     *     integerLiteral: [1-9][0-9]* | [0]
+     * </pre>
+     */
+    private ConstantNode parseIntegerLiteral() {
+        return (ConstantNode)new ConstantNode(_lexer.parseNumber()).peephole();
+    }
+
+    static RuntimeException error(String errorMessage) {
+        return new RuntimeException(errorMessage);
+    }
+
+    //////////////////////////////////
+    // 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 an exact match
+    private void require(String syntax) {
+        if( match(syntax) ) return;
+        throw error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken());
+    }
+    
+    ////////////////////////////////////
+    // 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;
+        }
+
+        // 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;
+        }
+
+        // Used for errors
+        String getAnyNextToken() {
+            if( isEOF() ) return "";
+            if( isIdentifierStart(peek()) )
+                return parseIdentifier();
+            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 new TypeInteger(Long.parseLong(snum));
+        }
+
+        // First letter of an identifier 
+        private boolean isIdentifierStart(char ch) {
+            return Character.isAlphabetic(ch) || ch == '_';
+        }
+
+        // All characters of an identifier, e.g. "_x123"
+        private boolean isIdentifierLetter(char ch) {
+            return Character.isLetterOrDigit(ch) || ch == '_';
+        }
+
+        private String parseIdentifier() {
+            int start = _position;
+            while (isIdentifierLetter(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/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java
new file mode 100644
index 00000000..015779dc
--- /dev/null
+++ b/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -0,0 +1,35 @@
+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 _print(StringBuilder sb) {
+        in(1)._print(sb.append("("));
+        in(2)._print(sb.append("+"));
+        return sb.append(")");
+    }
+  
+
+    @Override
+    public Type compute() {
+        if( in(1)._type instanceof TypeInteger i0 &&
+            in(2)._type instanceof TypeInteger i1 )
+            return new TypeInteger(i0._con + i1._con);
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize () {
+        // TODO: add of 0
+        return null;
+    }
+        
+}
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
new file mode 100644
index 00000000..99ccf4b5
--- /dev/null
+++ b/chapter02/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -0,0 +1,39 @@
+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 {
+
+    public ConstantNode( Type type ) {
+        super(Parser.START);
+        _type = type;
+    }
+    
+    @Override
+    public String label() { return "Con" + _type; }
+
+    @Override
+    StringBuilder _print(StringBuilder sb) {
+        return _type._print(sb);
+    }
+    
+    @Override
+    public Type compute() { return _type; }
+
+    @Override
+    public Node idealize() { return null; }
+    
+}
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/Control.java b/chapter02/src/main/java/com/seaofnodes/simple/node/Control.java
new file mode 100644
index 00000000..48cf2b7a
--- /dev/null
+++ b/chapter02/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/chapter02/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/DivNode.java
new file mode 100644
index 00000000..bc129690
--- /dev/null
+++ b/chapter02/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -0,0 +1,35 @@
+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 _print(StringBuilder sb) {
+        in(1)._print(sb.append("("));
+        in(2)._print(sb.append("/"));
+        return sb.append(")");
+    }
+  
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0 &&
+                in(2)._type instanceof TypeInteger i1) {
+            if (i1._con == 0)
+                throw new IllegalArgumentException("Divide by zero");
+            return new TypeInteger(i0._con / i1._con);
+        }
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/MinusNode.java
new file mode 100644
index 00000000..7fab83b0
--- /dev/null
+++ b/chapter02/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 _print(StringBuilder sb) {
+        in(1)._print(sb.append("(-"));
+        return sb.append(")");
+    }
+  
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0)
+            return new TypeInteger(-i0._con);
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/MulNode.java
new file mode 100644
index 00000000..e1a26858
--- /dev/null
+++ b/chapter02/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -0,0 +1,32 @@
+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 _print(StringBuilder sb) {
+        in(1)._print(sb.append("("));
+        in(2)._print(sb.append("*"));
+        return sb.append(")");
+    }
+  
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0 &&
+                in(2)._type instanceof TypeInteger i1)
+            return new TypeInteger(i0._con * i1._con);
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter02/src/main/java/com/seaofnodes/simple/node/Node.java
new file mode 100644
index 00000000..43dea8e1
--- /dev/null
+++ b/chapter02/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -0,0 +1,213 @@
+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;
+
+    /**
+     * 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 );
+        // Do an initial type computation
+        _type = compute();
+    }
+
+    public abstract String label();
+
+    public String uniqueName() { return label() + _nid; }
+
+    @Override
+    public final String toString() {
+        // TODO: This needs a lot of work
+        return uniqueName();
+    }
+
+    // This is a *deep* print.  This version will fail on cycles, which we will
+    // correct later when we can parse programs with loops.
+    public final String print() {
+        return _print(new StringBuilder()).toString();
+    }
+    abstract StringBuilder _print(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(); }
+
+    /**
+     * 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 check and replace:
+     * <ul>
+     * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li>
+     * <li>in a future chapter we will look for a
+     * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a>
+     * to eliminate.</li>
+     * <li>we ask the Node for a better replacement (again, none enabled in this chapter)</li>
+     * </ul>
+     */
+    public final Node peephole( ) {
+        if (_disablePeephole)
+            return this;        // Peephole optimizations turned off
+
+        // Replace constant computations from non-constants with a constant node
+        Type type = compute();
+        if (!(this instanceof ConstantNode) && type.isConstant()) {
+            kill();             // Kill `this` because replacing with a Constant
+            return new ConstantNode(type);
+        }
+
+        // Future chapter: Global Value Numbering goes here
+        
+        // Ask each node for a replacement
+        Node n = idealize();
+        if( n != null ) return n;
+        
+        return this;            // No progress
+    }
+
+    /**
+     * 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 #set_def}.
+     */
+    void kill( ) {
+        assert nOuts()==0;    // Has no uses, so it is dead
+        for( int i=0; i<nIns(); i++ )
+            set_def(i,null);  // Set all inputs to null, recursively killing unused Nodes
+    }
+
+    /**
+     * Change a <em>def</em> into a Node.  Keeps the edges correct, by removing
+     * the corresponding <em>use->def</em> edge.  This may make the original
+     * <em>def</em> go dead.  This function is co-recursive with {@link #kill}.
+     *     
+     * @param idx which def to set
+     * @param new_def the new definition
+     */
+    void set_def(int idx, Node new_def ) {
+        Node old_def = in(idx);
+        if( old_def != null ) { // If the old def exists, remove a use->def edge
+            ArrayList<Node> outs = old_def._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(this),outs.get(lidx));
+            outs.remove(lidx);  // Reduce ArrayList size without copying anything
+            if( lidx == 0 )     // 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 use->def edge
+        if( new_def != null )
+            new_def._outputs.add(this);
+    }
+    
+  
+    /**
+     * Current computed type for this Node.  This value changes as the graph
+     * changes and more knowledge is gained about the program.
+     */
+    public Type _type;
+    
+    /**
+     * This function needs to be
+     * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a>
+     * as it is part of a Monotone Analysis Framework.
+     * <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">See for example this set of slides</a>.
+     * <p>
+     * For Chapter 2, all our Types are really integer constants, and so all
+     * the needed properties are trivially true, and we can ignore the high
+     * theory.  Much later on, this will become important and allow us to do
+     * many fancy complex optimizations trivially... because theory.
+     * <p>
+     * compute() needs to be stand-alone, and cannot recursively call compute
+     * on its inputs programs are cyclic (have loops!) and this will just
+     * infinitely recurse until stack overflow.  Instead, compute typically
+     * computes a new type from the {@link #_type} field of its inputs.
+     */
+    public abstract Type compute();
+
+    public abstract Node idealize();
+
+    /**
+     * Used to allow repeating tests in the same JVM.  This just resets the
+     * Node unique id generator, and is done as part of making a new Parser.
+     */
+    public static void reset() { UNIQUE_ID = 1; }
+  
+    /*
+     * hashCode and equals implementation to be added in later chapter.
+     */
+  
+}
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
new file mode 100644
index 00000000..c188ca79
--- /dev/null
+++ b/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -0,0 +1,39 @@
+package com.seaofnodes.simple.node;
+
+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 _print(StringBuilder sb) {
+        return expr()._print(sb.append("return ")).append(";");
+    }
+
+  
+    @Override
+    public TypeBot compute() {
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java
new file mode 100644
index 00000000..8d8031bb
--- /dev/null
+++ b/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -0,0 +1,31 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.TypeBot;
+
+/**
+ * The Start node represents the start of the function.  For now, we do not have any inputs to Start because our function does not
+ * yet accept parameters.  When we add parameters the value of Start will be a tuple, and will require Projections to extract the values.
+ * We discuss this in detail in Chapter 9: Functions and Calls.
+ */
+public class StartNode extends Node implements Control {
+
+    public StartNode(/*arguments go here*/) {
+        super();
+    }
+
+    @Override
+    public String label() { return "Start"; }
+
+    @Override
+    StringBuilder _print(StringBuilder sb) {
+      return sb.append(label());
+    }
+  
+    @Override
+    public TypeBot compute() {
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/SubNode.java
new file mode 100644
index 00000000..2d7db8d3
--- /dev/null
+++ b/chapter02/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -0,0 +1,33 @@
+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 _print(StringBuilder sb) {
+        in(1)._print(sb.append("("));
+        in(2)._print(sb.append("-"));
+        return sb.append(")");
+    }
+  
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0 &&
+                in(2)._type instanceof TypeInteger i1)
+            return new TypeInteger(i0._con - i1._con);
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+
+}
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java
new file mode 100644
index 00000000..872e453d
--- /dev/null
+++ b/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -0,0 +1,25 @@
+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 boolean isConstant() { return false; }
+
+    public abstract StringBuilder _print(StringBuilder sb);
+}
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/type/TypeBot.java b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeBot.java
new file mode 100644
index 00000000..5284884a
--- /dev/null
+++ b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeBot.java
@@ -0,0 +1,14 @@
+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 StringBuilder _print(StringBuilder sb) { return sb.append(toString()); }
+}
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
new file mode 100644
index 00000000..db3d4c46
--- /dev/null
+++ b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -0,0 +1,34 @@
+package com.seaofnodes.simple.type;
+
+/**
+ * Integer Type
+ */
+public class TypeInteger extends Type {
+
+    /**
+     * The constant value observed for this type
+     */
+    public final long _con;
+
+    public TypeInteger(long con) { _con = con; }
+
+    @Override
+    public String toString() {
+      return _print(new StringBuilder()).toString();
+    }
+
+    @Override 
+    public StringBuilder _print(StringBuilder sb) { return sb.append(_con); }
+
+    @Override
+    public boolean isConstant() { return true; }
+
+    public long getConstant() { return _con; }
+
+    @Override
+    public boolean equals( Object o ) {
+        if( o==this ) return true;
+        if( !(o instanceof TypeInteger i) ) return false;
+        return _con==i._con;
+    }
+}
diff --git a/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java
new file mode 100644
index 00000000..ba9ae448
--- /dev/null
+++ b/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java
@@ -0,0 +1,125 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.ConstantNode;
+import com.seaofnodes.simple.node.Node;
+import com.seaofnodes.simple.node.ReturnNode;
+import com.seaofnodes.simple.node.StartNode;
+import com.seaofnodes.simple.type.TypeInteger;
+import org.junit.Test;
+
+import static org.junit.Assert.*;
+
+public class Chapter02Test {
+
+    @Test
+    public void testChapter2ParseGrammar() {
+        Node._disablePeephole = true; // disable peephole so we can observe full graph
+        Parser parser = new Parser("return 1+2*3+-5;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return (1+((2*3)+(-5)));", ret.print());
+        GraphVisualizer gv = new GraphVisualizer();
+        System.out.println(gv.generateDotOutput(Parser.START));
+        Node._disablePeephole = false;
+    }
+
+    @Test
+    public void testChapter2AddPeephole() {
+        Parser parser = new Parser("return 1+2;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 3;", ret.print());
+    }
+
+    @Test
+    public void testChapter2SubPeephole() {
+        Parser parser = new Parser("return 1-2;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return -1;", ret.print());
+    }
+
+    @Test
+    public void testChapter2MulPeephole() {
+        Parser parser = new Parser("return 2*3;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 6;", ret.print());
+    }
+
+    @Test
+    public void testChapter2DivPeephole() {
+        Parser parser = new Parser("return 6/3;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 2;", ret.print());
+    }
+
+    @Test
+    public void testChapter2MinusPeephole() {
+        Parser parser = new Parser("return 6/-3;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return -2;", ret.print());
+    }
+
+    @Test
+    public void testChapter2Example() {
+        Parser parser = new Parser("return 1+2*3+-5;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 2;", ret.print());
+        GraphVisualizer gv = new GraphVisualizer();
+        System.out.println(gv.generateDotOutput(Parser.START));
+    }
+
+    @Test
+    public void testSimpleProgram() {
+        Parser parser = new Parser("return 1;");
+        ReturnNode ret = parser.parse();
+        StartNode start = Parser.START;
+        
+        assertEquals(start, ret.ctrl());
+        Node expr = ret.expr();
+        if( expr instanceof ConstantNode con ) {
+            assertEquals(start,con.in(0));
+            assertEquals(new TypeInteger(1), con._type);
+        } else {
+            fail();
+        }
+    }
+
+    @Test
+    public void testZero() {
+        Parser parser = new Parser("return 0;");
+        parser.parse();
+        StartNode start = Parser.START;
+        for( Node use : start._outputs )
+            if( use instanceof ConstantNode con )
+                assertEquals(new TypeInteger(0),con._type);
+    }
+
+    @Test
+    public void testBad1() {
+        try { new Parser("ret").parse(); }
+        catch( RuntimeException e ) { assertEquals("Syntax error, expected return: ret",e.getMessage()); }
+    }
+
+    @Test
+    public void testBad2() {
+        try { new Parser("return 0123;").parse(); }
+        catch( RuntimeException e ) { assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); }
+    }
+
+    @Test
+    public void testBad3() {
+        try { new Parser("return --12;").parse(); }
+        catch( RuntimeException e ) { assertEquals("Syntax error, expected integer literal: -",e.getMessage()); }
+    }
+
+    @Test
+    public void testBad4() {
+        try { new Parser("return 100").parse(); }
+        catch( RuntimeException e ) { assertTrue(e.getMessage().contains("Syntax error, expected ;:")); }
+    }
+
+    // Negative numbers require unary operator support that is not in scope
+    @Test
+    public void testBad5() {
+        try { new Parser("return -100;").parse(); }
+        catch( RuntimeException e ) { assertEquals("Syntax error, expected integer literal: -", e.getMessage()); }
+    }
+}