docs/sphinx_docs/_build/html/notebooks/Derivatives_of_Regular_Expressions.html

   1
   2 <!DOCTYPE html>
   3
   4 <html>
   5   <head>
   6     <meta charset="utf-8" />
   7     <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />
   8
   9     <title>∂RE &#8212; Thun 0.4.1 documentation</title>
  10     <link rel="stylesheet" type="text/css" href="../_static/pygments.css" />
  11     <link rel="stylesheet" type="text/css" href="../_static/alabaster.css" />
  12     <script data-url_root="../" id="documentation_options" src="../_static/documentation_options.js"></script>
  13     <script src="../_static/jquery.js"></script>
  14     <script src="../_static/underscore.js"></script>
  15     <script src="../_static/doctools.js"></script>
  16     <link rel="index" title="Index" href="../genindex.html" />
  17     <link rel="search" title="Search" href="../search.html" />
  18     <link rel="prev" title="The Four Fundamental Operations of Definite Action" href="The_Four_Operations.html" />
  19
  20   <link rel="stylesheet" href="../_static/custom.css" type="text/css" />
  21
  22
  23   <meta name="viewport" content="width=device-width, initial-scale=0.9, maximum-scale=0.9" />
  24
  25   </head><body>
  26
  27
  28     <div class="document">
  29       <div class="documentwrapper">
  30         <div class="bodywrapper">
  31
  32
  33           <div class="body" role="main">
  34
  35   <section id="re">
  36 <h1>∂RE<a class="headerlink" href="#re" title="Permalink to this headline">¶</a></h1>
  37 <section id="brzozowskis-derivatives-of-regular-expressions">
  38 <h2>Brzozowski’s Derivatives of Regular Expressions<a class="headerlink" href="#brzozowskis-derivatives-of-regular-expressions" title="Permalink to this headline">¶</a></h2>
  39 <p>Legend:</p>
  40 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>∧ intersection
  41 ∨ union
  42 ∘ concatenation (see below)
  43 ¬ complement
  44 ϕ empty set (aka ∅)
  45 λ singleton set containing just the empty string
  46 I set of all letters in alphabet
  47 </pre></div>
  48 </div>
  49 <p>Derivative of a set <code class="docutils literal notranslate"><span class="pre">R</span></code> of strings and a string <code class="docutils literal notranslate"><span class="pre">a</span></code>:</p>
  50 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>∂a(R)
  51
  52 ∂a(a) → λ
  53 ∂a(λ) → ϕ
  54 ∂a(ϕ) → ϕ
  55 ∂a(¬a) → ϕ
  56 ∂a(R*) → ∂a(R)∘R*
  57 ∂a(¬R) → ¬∂a(R)
  58 ∂a(R∘S) → ∂a(R)∘S ∨ δ(R)∘∂a(S)
  59 ∂a(R ∧ S) → ∂a(R) ∧ ∂a(S)
  60 ∂a(R ∨ S) → ∂a(R) ∨ ∂a(S)
  61
  62 ∂ab(R) = ∂b(∂a(R))
  63 </pre></div>
  64 </div>
  65 <p>Auxiliary predicate function <code class="docutils literal notranslate"><span class="pre">δ</span></code> (I call it <code class="docutils literal notranslate"><span class="pre">nully</span></code>) returns either
  66 <code class="docutils literal notranslate"><span class="pre">λ</span></code> if <code class="docutils literal notranslate"><span class="pre">λ</span> <span class="pre">⊆</span> <span class="pre">R</span></code> or <code class="docutils literal notranslate"><span class="pre">ϕ</span></code> otherwise:</p>
  67 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>δ(a) → ϕ
  68 δ(λ) → λ
  69 δ(ϕ) → ϕ
  70 δ(R*) → λ
  71 δ(¬R) δ(R)≟ϕ → λ
  72 δ(¬R) δ(R)≟λ → ϕ
  73 δ(R∘S) → δ(R) ∧ δ(S)
  74 δ(R ∧ S) → δ(R) ∧ δ(S)
  75 δ(R ∨ S) → δ(R) ∨ δ(S)
  76 </pre></div>
  77 </div>
  78 <p>Some rules we will use later for “compaction”:</p>
  79 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>R ∧ ϕ = ϕ ∧ R = ϕ
  80
  81 R ∧ I = I ∧ R = R
  82
  83 R ∨ ϕ = ϕ ∨ R = R
  84
  85 R ∨ I = I ∨ R = I
  86
  87 R∘ϕ = ϕ∘R = ϕ
  88
  89 R∘λ = λ∘R = R
  90 </pre></div>
  91 </div>
  92 <p>Concatination of sets: for two sets A and B the set A∘B is defined as:</p>
  93 <p>{a∘b for a in A for b in B}</p>
  94 <p>E.g.:</p>
  95 <p>{‘a’, ‘b’}∘{‘c’, ‘d’} → {‘ac’, ‘ad’, ‘bc’, ‘bd’}</p>
  96 </section>
  97 <section id="implementation">
  98 <h2>Implementation<a class="headerlink" href="#implementation" title="Permalink to this headline">¶</a></h2>
  99 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">functools</span> <span class="kn">import</span> <span class="n">partial</span> <span class="k">as</span> <span class="n">curry</span>
 100 <span class="kn">from</span> <span class="nn">itertools</span> <span class="kn">import</span> <span class="n">product</span>
 101 </pre></div>
 102 </div>
 103 <section id="and">
 104 <h3><code class="docutils literal notranslate"><span class="pre">ϕ</span></code> and <code class="docutils literal notranslate"><span class="pre">λ</span></code><a class="headerlink" href="#and" title="Permalink to this headline">¶</a></h3>
 105 <p>The empty set and the set of just the empty string.</p>
 106 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">phi</span> <span class="o">=</span> <span class="nb">frozenset</span><span class="p">()</span>   <span class="c1"># ϕ</span>
 107 <span class="n">y</span> <span class="o">=</span> <span class="nb">frozenset</span><span class="p">({</span><span class="s1">&#39;&#39;</span><span class="p">})</span> <span class="c1"># λ</span>
 108 </pre></div>
 109 </div>
 110 </section>
 111 <section id="two-letter-alphabet">
 112 <h3>Two-letter Alphabet<a class="headerlink" href="#two-letter-alphabet" title="Permalink to this headline">¶</a></h3>
 113 <p>I’m only going to use two symbols (at first) becaase this is enough to
 114 illustrate the algorithm and because you can represent any other
 115 alphabet with two symbols (if you had to.)</p>
 116 <p>I chose the names <code class="docutils literal notranslate"><span class="pre">O</span></code> and <code class="docutils literal notranslate"><span class="pre">l</span></code> (uppercase “o” and lowercase “L”) to
 117 look like <code class="docutils literal notranslate"><span class="pre">0</span></code> and <code class="docutils literal notranslate"><span class="pre">1</span></code> (zero and one) respectively.</p>
 118 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">syms</span> <span class="o">=</span> <span class="n">O</span><span class="p">,</span> <span class="n">l</span> <span class="o">=</span> <span class="nb">frozenset</span><span class="p">({</span><span class="s1">&#39;0&#39;</span><span class="p">}),</span> <span class="nb">frozenset</span><span class="p">({</span><span class="s1">&#39;1&#39;</span><span class="p">})</span>
 119 </pre></div>
 120 </div>
 121 </section>
 122 <section id="representing-regular-expressions">
 123 <h3>Representing Regular Expressions<a class="headerlink" href="#representing-regular-expressions" title="Permalink to this headline">¶</a></h3>
 124 <p>To represent REs in Python I’m going to use tagged tuples. A <em>regular
 125 expression</em> is one of:</p>
 126 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">O</span>
 127 <span class="n">l</span>
 128 <span class="p">(</span><span class="n">KSTAR</span><span class="p">,</span> <span class="n">R</span><span class="p">)</span>
 129 <span class="p">(</span><span class="n">NOT</span><span class="p">,</span> <span class="n">R</span><span class="p">)</span>
 130 <span class="p">(</span><span class="n">AND</span><span class="p">,</span> <span class="n">R</span><span class="p">,</span> <span class="n">S</span><span class="p">)</span>
 131 <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">R</span><span class="p">,</span> <span class="n">S</span><span class="p">)</span>
 132 <span class="p">(</span><span class="n">OR</span><span class="p">,</span> <span class="n">R</span><span class="p">,</span> <span class="n">S</span><span class="p">)</span>
 133 </pre></div>
 134 </div>
 135 <p>Where <code class="docutils literal notranslate"><span class="pre">R</span></code> and <code class="docutils literal notranslate"><span class="pre">S</span></code> stand for <em>regular expressions</em>.</p>
 136 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">AND</span><span class="p">,</span> <span class="n">CONS</span><span class="p">,</span> <span class="n">KSTAR</span><span class="p">,</span> <span class="n">NOT</span><span class="p">,</span> <span class="n">OR</span> <span class="o">=</span> <span class="s1">&#39;and cons * not or&#39;</span><span class="o">.</span><span class="n">split</span><span class="p">()</span>  <span class="c1"># Tags are just strings.</span>
 137 </pre></div>
 138 </div>
 139 <p>Because they are formed of <code class="docutils literal notranslate"><span class="pre">frozenset</span></code>, <code class="docutils literal notranslate"><span class="pre">tuple</span></code> and <code class="docutils literal notranslate"><span class="pre">str</span></code> objects
 140 only, these datastructures are immutable.</p>
 141 </section>
 142 <section id="string-representation-of-re-datastructures">
 143 <h3>String Representation of RE Datastructures<a class="headerlink" href="#string-representation-of-re-datastructures" title="Permalink to this headline">¶</a></h3>
 144 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">stringy</span><span class="p">(</span><span class="n">re</span><span class="p">):</span>
 145     <span class="sd">&#39;&#39;&#39;</span>
 146 <span class="sd">    Return a nice string repr for a regular expression datastructure.</span>
 147 <span class="sd">    &#39;&#39;&#39;</span>
 148     <span class="k">if</span> <span class="n">re</span> <span class="o">==</span> <span class="n">I</span><span class="p">:</span> <span class="k">return</span> <span class="s1">&#39;.&#39;</span>
 149     <span class="k">if</span> <span class="n">re</span> <span class="ow">in</span> <span class="n">syms</span><span class="p">:</span> <span class="k">return</span> <span class="nb">next</span><span class="p">(</span><span class="nb">iter</span><span class="p">(</span><span class="n">re</span><span class="p">))</span>
 150     <span class="k">if</span> <span class="n">re</span> <span class="o">==</span> <span class="n">y</span><span class="p">:</span> <span class="k">return</span> <span class="s1">&#39;^&#39;</span>
 151     <span class="k">if</span> <span class="n">re</span> <span class="o">==</span> <span class="n">phi</span><span class="p">:</span> <span class="k">return</span> <span class="s1">&#39;X&#39;</span>
 152
 153     <span class="k">assert</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">re</span><span class="p">,</span> <span class="nb">tuple</span><span class="p">),</span> <span class="nb">repr</span><span class="p">(</span><span class="n">re</span><span class="p">)</span>
 154     <span class="n">tag</span> <span class="o">=</span> <span class="n">re</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
 155
 156     <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">KSTAR</span><span class="p">:</span>
 157         <span class="n">body</span> <span class="o">=</span> <span class="n">stringy</span><span class="p">(</span><span class="n">re</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span>
 158         <span class="k">if</span> <span class="ow">not</span> <span class="n">body</span><span class="p">:</span> <span class="k">return</span> <span class="n">body</span>
 159         <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">body</span><span class="p">)</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">:</span> <span class="k">return</span> <span class="s1">&#39;(&#39;</span> <span class="o">+</span> <span class="n">body</span> <span class="o">+</span> <span class="s2">&quot;)*&quot;</span>
 160         <span class="k">return</span> <span class="n">body</span> <span class="o">+</span> <span class="s1">&#39;*&#39;</span>
 161
 162     <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">NOT</span><span class="p">:</span>
 163         <span class="n">body</span> <span class="o">=</span> <span class="n">stringy</span><span class="p">(</span><span class="n">re</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span>
 164         <span class="k">if</span> <span class="ow">not</span> <span class="n">body</span><span class="p">:</span> <span class="k">return</span> <span class="n">body</span>
 165         <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">body</span><span class="p">)</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">:</span> <span class="k">return</span> <span class="s1">&#39;(&#39;</span> <span class="o">+</span> <span class="n">body</span> <span class="o">+</span> <span class="s2">&quot;)&#39;&quot;</span>
 166         <span class="k">return</span> <span class="n">body</span> <span class="o">+</span> <span class="s2">&quot;&#39;&quot;</span>
 167
 168     <span class="n">r</span><span class="p">,</span> <span class="n">s</span> <span class="o">=</span> <span class="n">stringy</span><span class="p">(</span><span class="n">re</span><span class="p">[</span><span class="mi">1</span><span class="p">]),</span> <span class="n">stringy</span><span class="p">(</span><span class="n">re</span><span class="p">[</span><span class="mi">2</span><span class="p">])</span>
 169     <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">CONS</span><span class="p">:</span> <span class="k">return</span> <span class="n">r</span> <span class="o">+</span> <span class="n">s</span>
 170     <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">OR</span><span class="p">:</span>   <span class="k">return</span> <span class="s1">&#39;</span><span class="si">%s</span><span class="s1"> | </span><span class="si">%s</span><span class="s1">&#39;</span> <span class="o">%</span> <span class="p">(</span><span class="n">r</span><span class="p">,</span> <span class="n">s</span><span class="p">)</span>
 171     <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">AND</span><span class="p">:</span>  <span class="k">return</span> <span class="s1">&#39;(</span><span class="si">%s</span><span class="s1">) &amp; (</span><span class="si">%s</span><span class="s1">)&#39;</span> <span class="o">%</span> <span class="p">(</span><span class="n">r</span><span class="p">,</span> <span class="n">s</span><span class="p">)</span>
 172
 173     <span class="k">raise</span> <span class="ne">ValueError</span>
 174 </pre></div>
 175 </div>
 176 </section>
 177 <section id="i">
 178 <h3><code class="docutils literal notranslate"><span class="pre">I</span></code><a class="headerlink" href="#i" title="Permalink to this headline">¶</a></h3>
 179 <p>Match anything. Often spelled “.”</p>
 180 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">I</span> <span class="o">=</span> <span class="p">(</span><span class="mi">0</span><span class="o">|</span><span class="mi">1</span><span class="p">)</span><span class="o">*</span>
 181 </pre></div>
 182 </div>
 183 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">I</span> <span class="o">=</span> <span class="p">(</span><span class="n">KSTAR</span><span class="p">,</span> <span class="p">(</span><span class="n">OR</span><span class="p">,</span> <span class="n">O</span><span class="p">,</span> <span class="n">l</span><span class="p">))</span>
 184 </pre></div>
 185 </div>
 186 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="nb">print</span> <span class="n">stringy</span><span class="p">(</span><span class="n">I</span><span class="p">)</span>
 187 </pre></div>
 188 </div>
 189 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">.</span>
 190 </pre></div>
 191 </div>
 192 </section>
 193 <section id="id1">
 194 <h3><code class="docutils literal notranslate"><span class="pre">(.111.)</span> <span class="pre">&amp;</span> <span class="pre">(.01</span> <span class="pre">+</span> <span class="pre">11*)'</span></code><a class="headerlink" href="#id1" title="Permalink to this headline">¶</a></h3>
 195 <p>The example expression from Brzozowski:</p>
 196 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">(</span><span class="o">.</span><span class="mf">111.</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">+</span> <span class="mi">11</span><span class="o">*</span><span class="p">)</span><span class="s1">&#39;</span>
 197    <span class="n">a</span>    <span class="o">&amp;</span>  <span class="p">(</span><span class="n">b</span>  <span class="o">+</span>  <span class="n">c</span><span class="p">)</span><span class="s1">&#39;</span>
 198 </pre></div>
 199 </div>
 200 <p>Note that it contains one of everything.</p>
 201 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">a</span> <span class="o">=</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">I</span><span class="p">,</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="n">I</span><span class="p">))))</span>
 202 <span class="n">b</span> <span class="o">=</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">I</span><span class="p">,</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">O</span><span class="p">,</span> <span class="n">l</span><span class="p">))</span>
 203 <span class="n">c</span> <span class="o">=</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="p">(</span><span class="n">KSTAR</span><span class="p">,</span> <span class="n">l</span><span class="p">))</span>
 204 <span class="n">it</span> <span class="o">=</span> <span class="p">(</span><span class="n">AND</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="p">(</span><span class="n">NOT</span><span class="p">,</span> <span class="p">(</span><span class="n">OR</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span><span class="p">)))</span>
 205 </pre></div>
 206 </div>
 207 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="nb">print</span> <span class="n">stringy</span><span class="p">(</span><span class="n">it</span><span class="p">)</span>
 208 </pre></div>
 209 </div>
 210 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">(</span><span class="o">.</span><span class="mf">111.</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">11</span><span class="o">*</span><span class="p">)</span><span class="s1">&#39;)</span>
 211 </pre></div>
 212 </div>
 213 </section>
 214 <section id="nully">
 215 <h3><code class="docutils literal notranslate"><span class="pre">nully()</span></code><a class="headerlink" href="#nully" title="Permalink to this headline">¶</a></h3>
 216 <p>Let’s get that auxiliary predicate function <code class="docutils literal notranslate"><span class="pre">δ</span></code> out of the way.</p>
 217 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">nully</span><span class="p">(</span><span class="n">R</span><span class="p">):</span>
 218     <span class="sd">&#39;&#39;&#39;</span>
 219 <span class="sd">    δ - Return λ if λ ⊆ R otherwise ϕ.</span>
 220 <span class="sd">    &#39;&#39;&#39;</span>
 221
 222     <span class="c1"># δ(a) → ϕ</span>
 223     <span class="c1"># δ(ϕ) → ϕ</span>
 224     <span class="k">if</span> <span class="n">R</span> <span class="ow">in</span> <span class="n">syms</span> <span class="ow">or</span> <span class="n">R</span> <span class="o">==</span> <span class="n">phi</span><span class="p">:</span>
 225         <span class="k">return</span> <span class="n">phi</span>
 226
 227     <span class="c1"># δ(λ) → λ</span>
 228     <span class="k">if</span> <span class="n">R</span> <span class="o">==</span> <span class="n">y</span><span class="p">:</span>
 229         <span class="k">return</span> <span class="n">y</span>
 230
 231     <span class="n">tag</span> <span class="o">=</span> <span class="n">R</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
 232
 233     <span class="c1"># δ(R*) → λ</span>
 234     <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">KSTAR</span><span class="p">:</span>
 235         <span class="k">return</span> <span class="n">y</span>
 236
 237     <span class="c1"># δ(¬R) δ(R)≟ϕ → λ</span>
 238     <span class="c1"># δ(¬R) δ(R)≟λ → ϕ</span>
 239     <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">NOT</span><span class="p">:</span>
 240         <span class="k">return</span> <span class="n">phi</span> <span class="k">if</span> <span class="n">nully</span><span class="p">(</span><span class="n">R</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span> <span class="k">else</span> <span class="n">y</span>
 241
 242     <span class="c1"># δ(R∘S) → δ(R) ∧ δ(S)</span>
 243     <span class="c1"># δ(R ∧ S) → δ(R) ∧ δ(S)</span>
 244     <span class="c1"># δ(R ∨ S) → δ(R) ∨ δ(S)</span>
 245     <span class="n">r</span><span class="p">,</span> <span class="n">s</span> <span class="o">=</span> <span class="n">nully</span><span class="p">(</span><span class="n">R</span><span class="p">[</span><span class="mi">1</span><span class="p">]),</span> <span class="n">nully</span><span class="p">(</span><span class="n">R</span><span class="p">[</span><span class="mi">2</span><span class="p">])</span>
 246     <span class="k">return</span> <span class="n">r</span> <span class="o">&amp;</span> <span class="n">s</span> <span class="k">if</span> <span class="n">tag</span> <span class="ow">in</span> <span class="p">{</span><span class="n">AND</span><span class="p">,</span> <span class="n">CONS</span><span class="p">}</span> <span class="k">else</span> <span class="n">r</span> <span class="o">|</span> <span class="n">s</span>
 247 </pre></div>
 248 </div>
 249 </section>
 250 <section id="no-compaction">
 251 <h3>No “Compaction”<a class="headerlink" href="#no-compaction" title="Permalink to this headline">¶</a></h3>
 252 <p>This is the straightforward version with no “compaction”. It works fine,
 253 but does waaaay too much work because the expressions grow each
 254 derivation.</p>
 255 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">D</span><span class="p">(</span><span class="n">symbol</span><span class="p">):</span>
 256
 257     <span class="k">def</span> <span class="nf">derv</span><span class="p">(</span><span class="n">R</span><span class="p">):</span>
 258
 259         <span class="c1"># ∂a(a) → λ</span>
 260         <span class="k">if</span> <span class="n">R</span> <span class="o">==</span> <span class="p">{</span><span class="n">symbol</span><span class="p">}:</span>
 261             <span class="k">return</span> <span class="n">y</span>
 262
 263         <span class="c1"># ∂a(λ) → ϕ</span>
 264         <span class="c1"># ∂a(ϕ) → ϕ</span>
 265         <span class="c1"># ∂a(¬a) → ϕ</span>
 266         <span class="k">if</span> <span class="n">R</span> <span class="o">==</span> <span class="n">y</span> <span class="ow">or</span> <span class="n">R</span> <span class="o">==</span> <span class="n">phi</span> <span class="ow">or</span> <span class="n">R</span> <span class="ow">in</span> <span class="n">syms</span><span class="p">:</span>
 267             <span class="k">return</span> <span class="n">phi</span>
 268
 269         <span class="n">tag</span> <span class="o">=</span> <span class="n">R</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
 270
 271         <span class="c1"># ∂a(R*) → ∂a(R)∘R*</span>
 272         <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">KSTAR</span><span class="p">:</span>
 273             <span class="k">return</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">derv</span><span class="p">(</span><span class="n">R</span><span class="p">[</span><span class="mi">1</span><span class="p">]),</span> <span class="n">R</span><span class="p">)</span>
 274
 275         <span class="c1"># ∂a(¬R) → ¬∂a(R)</span>
 276         <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">NOT</span><span class="p">:</span>
 277             <span class="k">return</span> <span class="p">(</span><span class="n">NOT</span><span class="p">,</span> <span class="n">derv</span><span class="p">(</span><span class="n">R</span><span class="p">[</span><span class="mi">1</span><span class="p">]))</span>
 278
 279         <span class="n">r</span><span class="p">,</span> <span class="n">s</span> <span class="o">=</span> <span class="n">R</span><span class="p">[</span><span class="mi">1</span><span class="p">:]</span>
 280
 281         <span class="c1"># ∂a(R∘S) → ∂a(R)∘S ∨ δ(R)∘∂a(S)</span>
 282         <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">CONS</span><span class="p">:</span>
 283             <span class="n">A</span> <span class="o">=</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">derv</span><span class="p">(</span><span class="n">r</span><span class="p">),</span> <span class="n">s</span><span class="p">)</span>  <span class="c1"># A = ∂a(R)∘S</span>
 284             <span class="c1"># A ∨ δ(R) ∘ ∂a(S)</span>
 285             <span class="c1"># A ∨  λ   ∘ ∂a(S) → A ∨ ∂a(S)</span>
 286             <span class="c1"># A ∨  ϕ   ∘ ∂a(S) → A ∨ ϕ → A</span>
 287             <span class="k">return</span> <span class="p">(</span><span class="n">OR</span><span class="p">,</span> <span class="n">A</span><span class="p">,</span> <span class="n">derv</span><span class="p">(</span><span class="n">s</span><span class="p">))</span> <span class="k">if</span> <span class="n">nully</span><span class="p">(</span><span class="n">r</span><span class="p">)</span> <span class="k">else</span> <span class="n">A</span>
 288
 289         <span class="c1"># ∂a(R ∧ S) → ∂a(R) ∧ ∂a(S)</span>
 290         <span class="c1"># ∂a(R ∨ S) → ∂a(R) ∨ ∂a(S)</span>
 291         <span class="k">return</span> <span class="p">(</span><span class="n">tag</span><span class="p">,</span> <span class="n">derv</span><span class="p">(</span><span class="n">r</span><span class="p">),</span> <span class="n">derv</span><span class="p">(</span><span class="n">s</span><span class="p">))</span>
 292
 293     <span class="k">return</span> <span class="n">derv</span>
 294 </pre></div>
 295 </div>
 296 </section>
 297 <section id="compaction-rules">
 298 <h3>Compaction Rules<a class="headerlink" href="#compaction-rules" title="Permalink to this headline">¶</a></h3>
 299 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">_compaction_rule</span><span class="p">(</span><span class="n">relation</span><span class="p">,</span> <span class="n">one</span><span class="p">,</span> <span class="n">zero</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">):</span>
 300     <span class="k">return</span> <span class="p">(</span>
 301         <span class="n">b</span> <span class="k">if</span> <span class="n">a</span> <span class="o">==</span> <span class="n">one</span> <span class="k">else</span>  <span class="c1"># R*1 = 1*R = R</span>
 302         <span class="n">a</span> <span class="k">if</span> <span class="n">b</span> <span class="o">==</span> <span class="n">one</span> <span class="k">else</span>
 303         <span class="n">zero</span> <span class="k">if</span> <span class="n">a</span> <span class="o">==</span> <span class="n">zero</span> <span class="ow">or</span> <span class="n">b</span> <span class="o">==</span> <span class="n">zero</span> <span class="k">else</span>  <span class="c1"># R*0 = 0*R = 0</span>
 304         <span class="p">(</span><span class="n">relation</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">)</span>
 305         <span class="p">)</span>
 306 </pre></div>
 307 </div>
 308 <p>An elegant symmetry.</p>
 309 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="c1"># R ∧ I = I ∧ R = R</span>
 310 <span class="c1"># R ∧ ϕ = ϕ ∧ R = ϕ</span>
 311 <span class="n">_and</span> <span class="o">=</span> <span class="n">curry</span><span class="p">(</span><span class="n">_compaction_rule</span><span class="p">,</span> <span class="n">AND</span><span class="p">,</span> <span class="n">I</span><span class="p">,</span> <span class="n">phi</span><span class="p">)</span>
 312
 313 <span class="c1"># R ∨ ϕ = ϕ ∨ R = R</span>
 314 <span class="c1"># R ∨ I = I ∨ R = I</span>
 315 <span class="n">_or</span> <span class="o">=</span> <span class="n">curry</span><span class="p">(</span><span class="n">_compaction_rule</span><span class="p">,</span> <span class="n">OR</span><span class="p">,</span> <span class="n">phi</span><span class="p">,</span> <span class="n">I</span><span class="p">)</span>
 316
 317 <span class="c1"># R∘λ = λ∘R = R</span>
 318 <span class="c1"># R∘ϕ = ϕ∘R = ϕ</span>
 319 <span class="n">_cons</span> <span class="o">=</span> <span class="n">curry</span><span class="p">(</span><span class="n">_compaction_rule</span><span class="p">,</span> <span class="n">CONS</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">phi</span><span class="p">)</span>
 320 </pre></div>
 321 </div>
 322 </section>
 323 <section id="memoizing">
 324 <h3>Memoizing<a class="headerlink" href="#memoizing" title="Permalink to this headline">¶</a></h3>
 325 <p>We can save re-processing by remembering results we have already
 326 computed. RE datastructures are immutable and the <code class="docutils literal notranslate"><span class="pre">derv()</span></code> functions
 327 are <em>pure</em> so this is fine.</p>
 328 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="k">class</span> <span class="nc">Memo</span><span class="p">(</span><span class="nb">object</span><span class="p">):</span>
 329
 330     <span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">f</span><span class="p">):</span>
 331         <span class="bp">self</span><span class="o">.</span><span class="n">f</span> <span class="o">=</span> <span class="n">f</span>
 332         <span class="bp">self</span><span class="o">.</span><span class="n">calls</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">hits</span> <span class="o">=</span> <span class="mi">0</span>
 333         <span class="bp">self</span><span class="o">.</span><span class="n">mem</span> <span class="o">=</span> <span class="p">{}</span>
 334
 335     <span class="k">def</span> <span class="fm">__call__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
 336         <span class="bp">self</span><span class="o">.</span><span class="n">calls</span> <span class="o">+=</span> <span class="mi">1</span>
 337         <span class="k">try</span><span class="p">:</span>
 338             <span class="n">result</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">mem</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>
 339             <span class="bp">self</span><span class="o">.</span><span class="n">hits</span> <span class="o">+=</span> <span class="mi">1</span>
 340         <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
 341             <span class="n">result</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">mem</span><span class="p">[</span><span class="n">key</span><span class="p">]</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">f</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>
 342         <span class="k">return</span> <span class="n">result</span>
 343 </pre></div>
 344 </div>
 345 </section>
 346 <section id="with-compaction">
 347 <h3>With “Compaction”<a class="headerlink" href="#with-compaction" title="Permalink to this headline">¶</a></h3>
 348 <p>This version uses the rules above to perform compaction. It keeps the
 349 expressions from growing too large.</p>
 350 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">D_compaction</span><span class="p">(</span><span class="n">symbol</span><span class="p">):</span>
 351
 352     <span class="nd">@Memo</span>
 353     <span class="k">def</span> <span class="nf">derv</span><span class="p">(</span><span class="n">R</span><span class="p">):</span>
 354
 355         <span class="c1"># ∂a(a) → λ</span>
 356         <span class="k">if</span> <span class="n">R</span> <span class="o">==</span> <span class="p">{</span><span class="n">symbol</span><span class="p">}:</span>
 357             <span class="k">return</span> <span class="n">y</span>
 358
 359         <span class="c1"># ∂a(λ) → ϕ</span>
 360         <span class="c1"># ∂a(ϕ) → ϕ</span>
 361         <span class="c1"># ∂a(¬a) → ϕ</span>
 362         <span class="k">if</span> <span class="n">R</span> <span class="o">==</span> <span class="n">y</span> <span class="ow">or</span> <span class="n">R</span> <span class="o">==</span> <span class="n">phi</span> <span class="ow">or</span> <span class="n">R</span> <span class="ow">in</span> <span class="n">syms</span><span class="p">:</span>
 363             <span class="k">return</span> <span class="n">phi</span>
 364
 365         <span class="n">tag</span> <span class="o">=</span> <span class="n">R</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
 366
 367         <span class="c1"># ∂a(R*) → ∂a(R)∘R*</span>
 368         <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">KSTAR</span><span class="p">:</span>
 369             <span class="k">return</span> <span class="n">_cons</span><span class="p">(</span><span class="n">derv</span><span class="p">(</span><span class="n">R</span><span class="p">[</span><span class="mi">1</span><span class="p">]),</span> <span class="n">R</span><span class="p">)</span>
 370
 371         <span class="c1"># ∂a(¬R) → ¬∂a(R)</span>
 372         <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">NOT</span><span class="p">:</span>
 373             <span class="k">return</span> <span class="p">(</span><span class="n">NOT</span><span class="p">,</span> <span class="n">derv</span><span class="p">(</span><span class="n">R</span><span class="p">[</span><span class="mi">1</span><span class="p">]))</span>
 374
 375         <span class="n">r</span><span class="p">,</span> <span class="n">s</span> <span class="o">=</span> <span class="n">R</span><span class="p">[</span><span class="mi">1</span><span class="p">:]</span>
 376
 377         <span class="c1"># ∂a(R∘S) → ∂a(R)∘S ∨ δ(R)∘∂a(S)</span>
 378         <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">CONS</span><span class="p">:</span>
 379             <span class="n">A</span> <span class="o">=</span> <span class="n">_cons</span><span class="p">(</span><span class="n">derv</span><span class="p">(</span><span class="n">r</span><span class="p">),</span> <span class="n">s</span><span class="p">)</span>  <span class="c1"># A = ∂a(r)∘s</span>
 380             <span class="c1"># A ∨ δ(R) ∘ ∂a(S)</span>
 381             <span class="c1"># A ∨  λ   ∘ ∂a(S) → A ∨ ∂a(S)</span>
 382             <span class="c1"># A ∨  ϕ   ∘ ∂a(S) → A ∨ ϕ → A</span>
 383             <span class="k">return</span> <span class="n">_or</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">derv</span><span class="p">(</span><span class="n">s</span><span class="p">))</span> <span class="k">if</span> <span class="n">nully</span><span class="p">(</span><span class="n">r</span><span class="p">)</span> <span class="k">else</span> <span class="n">A</span>
 384
 385         <span class="c1"># ∂a(R ∧ S) → ∂a(R) ∧ ∂a(S)</span>
 386         <span class="c1"># ∂a(R ∨ S) → ∂a(R) ∨ ∂a(S)</span>
 387         <span class="n">dr</span><span class="p">,</span> <span class="n">ds</span> <span class="o">=</span> <span class="n">derv</span><span class="p">(</span><span class="n">r</span><span class="p">),</span> <span class="n">derv</span><span class="p">(</span><span class="n">s</span><span class="p">)</span>
 388         <span class="k">return</span> <span class="n">_and</span><span class="p">(</span><span class="n">dr</span><span class="p">,</span> <span class="n">ds</span><span class="p">)</span> <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">AND</span> <span class="k">else</span> <span class="n">_or</span><span class="p">(</span><span class="n">dr</span><span class="p">,</span> <span class="n">ds</span><span class="p">)</span>
 389
 390     <span class="k">return</span> <span class="n">derv</span>
 391 </pre></div>
 392 </div>
 393 </section>
 394 </section>
 395 <section id="lets-try-it-out">
 396 <h2>Let’s try it out…<a class="headerlink" href="#lets-try-it-out" title="Permalink to this headline">¶</a></h2>
 397 <p>(FIXME: redo.)</p>
 398 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">o</span><span class="p">,</span> <span class="n">z</span> <span class="o">=</span> <span class="n">D_compaction</span><span class="p">(</span><span class="s1">&#39;0&#39;</span><span class="p">),</span> <span class="n">D_compaction</span><span class="p">(</span><span class="s1">&#39;1&#39;</span><span class="p">)</span>
 399 <span class="n">REs</span> <span class="o">=</span> <span class="nb">set</span><span class="p">()</span>
 400 <span class="n">N</span> <span class="o">=</span> <span class="mi">5</span>
 401 <span class="n">names</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">product</span><span class="p">(</span><span class="o">*</span><span class="p">(</span><span class="n">N</span> <span class="o">*</span> <span class="p">[(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">)])))</span>
 402 <span class="n">dervs</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">product</span><span class="p">(</span><span class="o">*</span><span class="p">(</span><span class="n">N</span> <span class="o">*</span> <span class="p">[(</span><span class="n">o</span><span class="p">,</span> <span class="n">z</span><span class="p">)])))</span>
 403 <span class="k">for</span> <span class="n">name</span><span class="p">,</span> <span class="n">ds</span> <span class="ow">in</span> <span class="nb">zip</span><span class="p">(</span><span class="n">names</span><span class="p">,</span> <span class="n">dervs</span><span class="p">):</span>
 404     <span class="n">R</span> <span class="o">=</span> <span class="n">it</span>
 405     <span class="n">ds</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">ds</span><span class="p">)</span>
 406     <span class="k">while</span> <span class="n">ds</span><span class="p">:</span>
 407         <span class="n">R</span> <span class="o">=</span> <span class="n">ds</span><span class="o">.</span><span class="n">pop</span><span class="p">()(</span><span class="n">R</span><span class="p">)</span>
 408         <span class="k">if</span> <span class="n">R</span> <span class="o">==</span> <span class="n">phi</span> <span class="ow">or</span> <span class="n">R</span> <span class="o">==</span> <span class="n">I</span><span class="p">:</span>
 409             <span class="k">break</span>
 410         <span class="n">REs</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">R</span><span class="p">)</span>
 411
 412 <span class="nb">print</span> <span class="n">stringy</span><span class="p">(</span><span class="n">it</span><span class="p">)</span> <span class="p">;</span> <span class="nb">print</span>
 413 <span class="nb">print</span> <span class="n">o</span><span class="o">.</span><span class="n">hits</span><span class="p">,</span> <span class="s1">&#39;/&#39;</span><span class="p">,</span> <span class="n">o</span><span class="o">.</span><span class="n">calls</span>
 414 <span class="nb">print</span> <span class="n">z</span><span class="o">.</span><span class="n">hits</span><span class="p">,</span> <span class="s1">&#39;/&#39;</span><span class="p">,</span> <span class="n">z</span><span class="o">.</span><span class="n">calls</span>
 415 <span class="nb">print</span>
 416 <span class="k">for</span> <span class="n">s</span> <span class="ow">in</span> <span class="nb">sorted</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="n">stringy</span><span class="p">,</span> <span class="n">REs</span><span class="p">),</span> <span class="n">key</span><span class="o">=</span><span class="k">lambda</span> <span class="n">n</span><span class="p">:</span> <span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">n</span><span class="p">),</span> <span class="n">n</span><span class="p">)):</span>
 417     <span class="nb">print</span> <span class="n">s</span>
 418 </pre></div>
 419 </div>
 420 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">(</span><span class="o">.</span><span class="mf">111.</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">11</span><span class="o">*</span><span class="p">)</span><span class="s1">&#39;)</span>
 421
 422 <span class="mi">92</span> <span class="o">/</span> <span class="mi">122</span>
 423 <span class="mi">92</span> <span class="o">/</span> <span class="mi">122</span>
 424
 425 <span class="p">(</span><span class="o">.</span><span class="mi">01</span><span class="p">)</span><span class="s1">&#39;</span>
 426 <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="p">)</span><span class="s1">&#39;</span>
 427 <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="o">^</span><span class="p">)</span><span class="s1">&#39;</span>
 428 <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">&#39;</span>
 429 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="p">)</span><span class="s1">&#39;)</span>
 430 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="o">^</span><span class="p">)</span><span class="s1">&#39;)</span>
 431 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span> <span class="o">|</span> <span class="mf">1.</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span><span class="p">)</span><span class="s1">&#39;)</span>
 432 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">&#39;)</span>
 433 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span> <span class="o">|</span> <span class="mf">1.</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">&#39;)</span>
 434 </pre></div>
 435 </div>
 436 <p>Should match:</p>
 437 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">(</span><span class="o">.</span><span class="mf">111.</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">11</span><span class="o">*</span><span class="p">)</span><span class="s1">&#39;)</span>
 438
 439 <span class="mi">92</span> <span class="o">/</span> <span class="mi">122</span>
 440 <span class="mi">92</span> <span class="o">/</span> <span class="mi">122</span>
 441
 442 <span class="p">(</span><span class="o">.</span><span class="mi">01</span>     <span class="p">)</span><span class="s1">&#39;</span>
 443 <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span> <span class="p">)</span><span class="s1">&#39;</span>
 444 <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="o">^</span> <span class="p">)</span><span class="s1">&#39;</span>
 445 <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">&#39;</span>
 446 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span><span class="p">)</span>            <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span> <span class="p">)</span><span class="s1">&#39;)</span>
 447 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span><span class="p">)</span>      <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="o">^</span> <span class="p">)</span><span class="s1">&#39;)</span>
 448 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span><span class="p">)</span>      <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">&#39;)</span>
 449 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span> <span class="o">|</span> <span class="mf">1.</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span>     <span class="p">)</span><span class="s1">&#39;)</span>
 450 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span> <span class="o">|</span> <span class="mf">1.</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">&#39;)</span>
 451 </pre></div>
 452 </div>
 453 </section>
 454 <section id="larger-alphabets">
 455 <h2>Larger Alphabets<a class="headerlink" href="#larger-alphabets" title="Permalink to this headline">¶</a></h2>
 456 <p>We could parse larger alphabets by defining patterns for e.g. each byte
 457 of the ASCII code. Or we can generalize this code. If you study the code
 458 above you’ll see that we never use the “set-ness” of the symbols <code class="docutils literal notranslate"><span class="pre">O</span></code>
 459 and <code class="docutils literal notranslate"><span class="pre">l</span></code>. The only time Python set operators (<code class="docutils literal notranslate"><span class="pre">&amp;</span></code> and <code class="docutils literal notranslate"><span class="pre">|</span></code>) appear
 460 is in the <code class="docutils literal notranslate"><span class="pre">nully()</span></code> function, and there they operate on (recursively
 461 computed) outputs of that function, never <code class="docutils literal notranslate"><span class="pre">O</span></code> and <code class="docutils literal notranslate"><span class="pre">l</span></code>.</p>
 462 <p>What if we try:</p>
 463 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>(OR, O, l)
 464
 465 ∂1((OR, O, l))
 466                             ∂a(R ∨ S) → ∂a(R) ∨ ∂a(S)
 467 ∂1(O) ∨ ∂1(l)
 468                             ∂a(¬a) → ϕ
 469 ϕ ∨ ∂1(l)
 470                             ∂a(a) → λ
 471 ϕ ∨ λ
 472                             ϕ ∨ R = R
 473 λ
 474 </pre></div>
 475 </div>
 476 <p>And compare it to:</p>
 477 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>{&#39;0&#39;, &#39;1&#39;)
 478
 479 ∂1({&#39;0&#39;, &#39;1&#39;))
 480                             ∂a(R ∨ S) → ∂a(R) ∨ ∂a(S)
 481 ∂1({&#39;0&#39;)) ∨ ∂1({&#39;1&#39;))
 482                             ∂a(¬a) → ϕ
 483 ϕ ∨ ∂1({&#39;1&#39;))
 484                             ∂a(a) → λ
 485 ϕ ∨ λ
 486                             ϕ ∨ R = R
 487 λ
 488 </pre></div>
 489 </div>
 490 <p>This suggests that we should be able to alter the functions above to
 491 detect sets and deal with them appropriately. Exercise for the Reader
 492 for now.</p>
 493 </section>
 494 <section id="state-machine">
 495 <h2>State Machine<a class="headerlink" href="#state-machine" title="Permalink to this headline">¶</a></h2>
 496 <p>We can drive the regular expressions to flesh out the underlying state
 497 machine transition table.</p>
 498 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">.</span><span class="mf">111.</span> <span class="o">&amp;</span> <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">+</span> <span class="mi">11</span><span class="o">*</span><span class="p">)</span><span class="s1">&#39;</span>
 499 </pre></div>
 500 </div>
 501 <p>Says, “Three or more 1’s and not ending in 01 nor composed of all 1’s.”</p>
 502 <figure class="align-default" id="id2">
 503 <img alt="State Machine Graph" src="../_images/omg.svg" /><figcaption>
 504 <p><span class="caption-text">State Machine Graph</span><a class="headerlink" href="#id2" title="Permalink to this image">¶</a></p>
 505 </figcaption>
 506 </figure>
 507 <p>Start at <code class="docutils literal notranslate"><span class="pre">a</span></code> and follow the transition arrows according to their
 508 labels. Accepting states have a double outline. (Graphic generated with
 509 <a class="reference external" href="http://www.graphviz.org/">Dot from Graphviz</a>.) You’ll see that only
 510 paths that lead to one of the accepting states will match the regular
 511 expression. All other paths will terminate at one of the non-accepting
 512 states.</p>
 513 <p>There’s a happy path to <code class="docutils literal notranslate"><span class="pre">g</span></code> along 111:</p>
 514 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>a→c→e→g
 515 </pre></div>
 516 </div>
 517 <p>After you reach <code class="docutils literal notranslate"><span class="pre">g</span></code> you’re stuck there eating 1’s until you see a 0,
 518 which takes you to the <code class="docutils literal notranslate"><span class="pre">i→j→i|i→j→h→i</span></code> “trap”. You can’t reach any
 519 other states from those two loops.</p>
 520 <p>If you see a 0 before you see 111 you will reach <code class="docutils literal notranslate"><span class="pre">b</span></code>, which forms
 521 another “trap” with <code class="docutils literal notranslate"><span class="pre">d</span></code> and <code class="docutils literal notranslate"><span class="pre">f</span></code>. The only way out is another happy
 522 path along 111 to <code class="docutils literal notranslate"><span class="pre">h</span></code>:</p>
 523 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>b→d→f→h
 524 </pre></div>
 525 </div>
 526 <p>Once you have reached <code class="docutils literal notranslate"><span class="pre">h</span></code> you can see as many 1’s or as many 0’ in a
 527 row and still be either still at <code class="docutils literal notranslate"><span class="pre">h</span></code> (for 1’s) or move to <code class="docutils literal notranslate"><span class="pre">i</span></code> (for
 528 0’s). If you find yourself at <code class="docutils literal notranslate"><span class="pre">i</span></code> you can see as many 0’s, or
 529 repetitions of 10, as there are, but if you see just a 1 you move to
 530 <code class="docutils literal notranslate"><span class="pre">j</span></code>.</p>
 531 <section id="re-to-fsm">
 532 <h3>RE to FSM<a class="headerlink" href="#re-to-fsm" title="Permalink to this headline">¶</a></h3>
 533 <p>So how do we get the state machine from the regular expression?</p>
 534 <p>It turns out that each RE is effectively a state, and each arrow points
 535 to the derivative RE in respect to the arrow’s symbol.</p>
 536 <p>If we label the initial RE <code class="docutils literal notranslate"><span class="pre">a</span></code>, we can say:</p>
 537 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>a --0--&gt; ∂0(a)
 538 a --1--&gt; ∂1(a)
 539 </pre></div>
 540 </div>
 541 <p>And so on, each new unique RE is a new state in the FSM table.</p>
 542 <p>Here are the derived REs at each state:</p>
 543 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">a</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mf">111.</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">11</span><span class="o">*</span><span class="p">)</span><span class="s1">&#39;)</span>
 544 <span class="n">b</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mf">111.</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="p">)</span><span class="s1">&#39;)</span>
 545 <span class="n">c</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">&#39;)</span>
 546 <span class="n">d</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="o">^</span><span class="p">)</span><span class="s1">&#39;)</span>
 547 <span class="n">e</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span> <span class="o">|</span> <span class="mf">1.</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">&#39;)</span>
 548 <span class="n">f</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span> <span class="o">|</span> <span class="mf">1.</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span><span class="p">)</span><span class="s1">&#39;)</span>
 549 <span class="n">g</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">&#39;</span>
 550 <span class="n">h</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mi">01</span><span class="p">)</span><span class="s1">&#39;</span>
 551 <span class="n">i</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="p">)</span><span class="s1">&#39;</span>
 552 <span class="n">j</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="o">^</span><span class="p">)</span><span class="s1">&#39;</span>
 553 </pre></div>
 554 </div>
 555 <p>You can see the one-way nature of the <code class="docutils literal notranslate"><span class="pre">g</span></code> state and the <code class="docutils literal notranslate"><span class="pre">hij</span></code> “trap”
 556 in the way that the <code class="docutils literal notranslate"><span class="pre">.111.</span></code> on the left-hand side of the <code class="docutils literal notranslate"><span class="pre">&amp;</span></code>
 557 disappears once it has been matched.</p>
 558 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">collections</span> <span class="kn">import</span> <span class="n">defaultdict</span>
 559 <span class="kn">from</span> <span class="nn">pprint</span> <span class="kn">import</span> <span class="n">pprint</span>
 560 <span class="kn">from</span> <span class="nn">string</span> <span class="kn">import</span> <span class="n">ascii_lowercase</span>
 561 </pre></div>
 562 </div>
 563 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">d0</span><span class="p">,</span> <span class="n">d1</span> <span class="o">=</span> <span class="n">D_compaction</span><span class="p">(</span><span class="s1">&#39;0&#39;</span><span class="p">),</span> <span class="n">D_compaction</span><span class="p">(</span><span class="s1">&#39;1&#39;</span><span class="p">)</span>
 564 </pre></div>
 565 </div>
 566 </section>
 567 <section id="explore">
 568 <h3><code class="docutils literal notranslate"><span class="pre">explore()</span></code><a class="headerlink" href="#explore" title="Permalink to this headline">¶</a></h3>
 569 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">explore</span><span class="p">(</span><span class="n">re</span><span class="p">):</span>
 570
 571     <span class="c1"># Don&#39;t have more than 26 states...</span>
 572     <span class="n">names</span> <span class="o">=</span> <span class="n">defaultdict</span><span class="p">(</span><span class="nb">iter</span><span class="p">(</span><span class="n">ascii_lowercase</span><span class="p">)</span><span class="o">.</span><span class="n">next</span><span class="p">)</span>
 573
 574     <span class="n">table</span><span class="p">,</span> <span class="n">accepting</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">(),</span> <span class="nb">set</span><span class="p">()</span>
 575
 576     <span class="n">to_check</span> <span class="o">=</span> <span class="p">{</span><span class="n">re</span><span class="p">}</span>
 577     <span class="k">while</span> <span class="n">to_check</span><span class="p">:</span>
 578
 579         <span class="n">re</span> <span class="o">=</span> <span class="n">to_check</span><span class="o">.</span><span class="n">pop</span><span class="p">()</span>
 580         <span class="n">state_name</span> <span class="o">=</span> <span class="n">names</span><span class="p">[</span><span class="n">re</span><span class="p">]</span>
 581
 582         <span class="k">if</span> <span class="p">(</span><span class="n">state_name</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span> <span class="ow">in</span> <span class="n">table</span><span class="p">:</span>
 583             <span class="k">continue</span>
 584
 585         <span class="k">if</span> <span class="n">nully</span><span class="p">(</span><span class="n">re</span><span class="p">):</span>
 586             <span class="n">accepting</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">state_name</span><span class="p">)</span>
 587
 588         <span class="n">o</span><span class="p">,</span> <span class="n">i</span> <span class="o">=</span> <span class="n">d0</span><span class="p">(</span><span class="n">re</span><span class="p">),</span> <span class="n">d1</span><span class="p">(</span><span class="n">re</span><span class="p">)</span>
 589         <span class="n">table</span><span class="p">[</span><span class="n">state_name</span><span class="p">,</span> <span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">names</span><span class="p">[</span><span class="n">o</span><span class="p">]</span> <span class="p">;</span> <span class="n">to_check</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">o</span><span class="p">)</span>
 590         <span class="n">table</span><span class="p">[</span><span class="n">state_name</span><span class="p">,</span> <span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="n">names</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="p">;</span> <span class="n">to_check</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">i</span><span class="p">)</span>
 591
 592     <span class="k">return</span> <span class="n">table</span><span class="p">,</span> <span class="n">accepting</span>
 593 </pre></div>
 594 </div>
 595 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">table</span><span class="p">,</span> <span class="n">accepting</span> <span class="o">=</span> <span class="n">explore</span><span class="p">(</span><span class="n">it</span><span class="p">)</span>
 596 <span class="n">table</span>
 597 </pre></div>
 598 </div>
 599 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">{(</span><span class="s1">&#39;a&#39;</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">&#39;b&#39;</span><span class="p">,</span>
 600  <span class="p">(</span><span class="s1">&#39;a&#39;</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">&#39;c&#39;</span><span class="p">,</span>
 601  <span class="p">(</span><span class="s1">&#39;b&#39;</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">&#39;b&#39;</span><span class="p">,</span>
 602  <span class="p">(</span><span class="s1">&#39;b&#39;</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">&#39;d&#39;</span><span class="p">,</span>
 603  <span class="p">(</span><span class="s1">&#39;c&#39;</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">&#39;b&#39;</span><span class="p">,</span>
 604  <span class="p">(</span><span class="s1">&#39;c&#39;</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">&#39;e&#39;</span><span class="p">,</span>
 605  <span class="p">(</span><span class="s1">&#39;d&#39;</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">&#39;b&#39;</span><span class="p">,</span>
 606  <span class="p">(</span><span class="s1">&#39;d&#39;</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">&#39;f&#39;</span><span class="p">,</span>
 607  <span class="p">(</span><span class="s1">&#39;e&#39;</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">&#39;b&#39;</span><span class="p">,</span>
 608  <span class="p">(</span><span class="s1">&#39;e&#39;</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">&#39;g&#39;</span><span class="p">,</span>
 609  <span class="p">(</span><span class="s1">&#39;f&#39;</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">&#39;b&#39;</span><span class="p">,</span>
 610  <span class="p">(</span><span class="s1">&#39;f&#39;</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">&#39;h&#39;</span><span class="p">,</span>
 611  <span class="p">(</span><span class="s1">&#39;g&#39;</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">&#39;i&#39;</span><span class="p">,</span>
 612  <span class="p">(</span><span class="s1">&#39;g&#39;</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">&#39;g&#39;</span><span class="p">,</span>
 613  <span class="p">(</span><span class="s1">&#39;h&#39;</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">&#39;i&#39;</span><span class="p">,</span>
 614  <span class="p">(</span><span class="s1">&#39;h&#39;</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">&#39;h&#39;</span><span class="p">,</span>
 615  <span class="p">(</span><span class="s1">&#39;i&#39;</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">&#39;i&#39;</span><span class="p">,</span>
 616  <span class="p">(</span><span class="s1">&#39;i&#39;</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">&#39;j&#39;</span><span class="p">,</span>
 617  <span class="p">(</span><span class="s1">&#39;j&#39;</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">&#39;i&#39;</span><span class="p">,</span>
 618  <span class="p">(</span><span class="s1">&#39;j&#39;</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">&#39;h&#39;</span><span class="p">}</span>
 619 </pre></div>
 620 </div>
 621 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">accepting</span>
 622 </pre></div>
 623 </div>
 624 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">{</span><span class="s1">&#39;h&#39;</span><span class="p">,</span> <span class="s1">&#39;i&#39;</span><span class="p">}</span>
 625 </pre></div>
 626 </div>
 627 </section>
 628 <section id="generate-diagram">
 629 <h3>Generate Diagram<a class="headerlink" href="#generate-diagram" title="Permalink to this headline">¶</a></h3>
 630 <p>Once we have the FSM table and the set of accepting states we can
 631 generate the diagram above.</p>
 632 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">_template</span> <span class="o">=</span> <span class="s1">&#39;&#39;&#39;</span><span class="se">\</span>
 633 <span class="s1">digraph finite_state_machine {</span>
 634 <span class="s1">  rankdir=LR;</span>
 635 <span class="s1">  size=&quot;8,5&quot;</span>
 636 <span class="s1">  node [shape = doublecircle]; </span><span class="si">%s</span><span class="s1">;</span>
 637 <span class="s1">  node [shape = circle];</span>
 638 <span class="si">%s</span><span class="s1"></span>
 639 <span class="s1">}</span>
 640 <span class="s1">&#39;&#39;&#39;</span>
 641
 642 <span class="k">def</span> <span class="nf">link</span><span class="p">(</span><span class="n">fr</span><span class="p">,</span> <span class="n">nm</span><span class="p">,</span> <span class="n">label</span><span class="p">):</span>
 643     <span class="k">return</span> <span class="s1">&#39;  </span><span class="si">%s</span><span class="s1"> -&gt; </span><span class="si">%s</span><span class="s1"> [ label = &quot;</span><span class="si">%s</span><span class="s1">&quot; ];&#39;</span> <span class="o">%</span> <span class="p">(</span><span class="n">fr</span><span class="p">,</span> <span class="n">nm</span><span class="p">,</span> <span class="n">label</span><span class="p">)</span>
 644
 645
 646 <span class="k">def</span> <span class="nf">make_graph</span><span class="p">(</span><span class="n">table</span><span class="p">,</span> <span class="n">accepting</span><span class="p">):</span>
 647     <span class="k">return</span> <span class="n">_template</span> <span class="o">%</span> <span class="p">(</span>
 648         <span class="s1">&#39; &#39;</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="n">accepting</span><span class="p">),</span>
 649         <span class="s1">&#39;</span><span class="se">\n</span><span class="s1">&#39;</span><span class="o">.</span><span class="n">join</span><span class="p">(</span>
 650           <span class="n">link</span><span class="p">(</span><span class="n">from_</span><span class="p">,</span> <span class="n">to</span><span class="p">,</span> <span class="n">char</span><span class="p">)</span>
 651           <span class="k">for</span> <span class="p">(</span><span class="n">from_</span><span class="p">,</span> <span class="n">char</span><span class="p">),</span> <span class="p">(</span><span class="n">to</span><span class="p">)</span> <span class="ow">in</span> <span class="nb">sorted</span><span class="p">(</span><span class="n">table</span><span class="o">.</span><span class="n">iteritems</span><span class="p">())</span>
 652           <span class="p">)</span>
 653         <span class="p">)</span>
 654 </pre></div>
 655 </div>
 656 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="nb">print</span> <span class="n">make_graph</span><span class="p">(</span><span class="n">table</span><span class="p">,</span> <span class="n">accepting</span><span class="p">)</span>
 657 </pre></div>
 658 </div>
 659 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">digraph</span> <span class="n">finite_state_machine</span> <span class="p">{</span>
 660   <span class="n">rankdir</span><span class="o">=</span><span class="n">LR</span><span class="p">;</span>
 661   <span class="n">size</span><span class="o">=</span><span class="s2">&quot;8,5&quot;</span>
 662   <span class="n">node</span> <span class="p">[</span><span class="n">shape</span> <span class="o">=</span> <span class="n">doublecircle</span><span class="p">];</span> <span class="n">i</span> <span class="n">h</span><span class="p">;</span>
 663   <span class="n">node</span> <span class="p">[</span><span class="n">shape</span> <span class="o">=</span> <span class="n">circle</span><span class="p">];</span>
 664   <span class="n">a</span> <span class="o">-&gt;</span> <span class="n">b</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;0&quot;</span> <span class="p">];</span>
 665   <span class="n">a</span> <span class="o">-&gt;</span> <span class="n">c</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;1&quot;</span> <span class="p">];</span>
 666   <span class="n">b</span> <span class="o">-&gt;</span> <span class="n">b</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;0&quot;</span> <span class="p">];</span>
 667   <span class="n">b</span> <span class="o">-&gt;</span> <span class="n">d</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;1&quot;</span> <span class="p">];</span>
 668   <span class="n">c</span> <span class="o">-&gt;</span> <span class="n">b</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;0&quot;</span> <span class="p">];</span>
 669   <span class="n">c</span> <span class="o">-&gt;</span> <span class="n">e</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;1&quot;</span> <span class="p">];</span>
 670   <span class="n">d</span> <span class="o">-&gt;</span> <span class="n">b</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;0&quot;</span> <span class="p">];</span>
 671   <span class="n">d</span> <span class="o">-&gt;</span> <span class="n">f</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;1&quot;</span> <span class="p">];</span>
 672   <span class="n">e</span> <span class="o">-&gt;</span> <span class="n">b</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;0&quot;</span> <span class="p">];</span>
 673   <span class="n">e</span> <span class="o">-&gt;</span> <span class="n">g</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;1&quot;</span> <span class="p">];</span>
 674   <span class="n">f</span> <span class="o">-&gt;</span> <span class="n">b</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;0&quot;</span> <span class="p">];</span>
 675   <span class="n">f</span> <span class="o">-&gt;</span> <span class="n">h</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;1&quot;</span> <span class="p">];</span>
 676   <span class="n">g</span> <span class="o">-&gt;</span> <span class="n">i</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;0&quot;</span> <span class="p">];</span>
 677   <span class="n">g</span> <span class="o">-&gt;</span> <span class="n">g</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;1&quot;</span> <span class="p">];</span>
 678   <span class="n">h</span> <span class="o">-&gt;</span> <span class="n">i</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;0&quot;</span> <span class="p">];</span>
 679   <span class="n">h</span> <span class="o">-&gt;</span> <span class="n">h</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;1&quot;</span> <span class="p">];</span>
 680   <span class="n">i</span> <span class="o">-&gt;</span> <span class="n">i</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;0&quot;</span> <span class="p">];</span>
 681   <span class="n">i</span> <span class="o">-&gt;</span> <span class="n">j</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;1&quot;</span> <span class="p">];</span>
 682   <span class="n">j</span> <span class="o">-&gt;</span> <span class="n">i</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;0&quot;</span> <span class="p">];</span>
 683   <span class="n">j</span> <span class="o">-&gt;</span> <span class="n">h</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">&quot;1&quot;</span> <span class="p">];</span>
 684 <span class="p">}</span>
 685 </pre></div>
 686 </div>
 687 </section>
 688 <section id="drive-a-fsm">
 689 <h3>Drive a FSM<a class="headerlink" href="#drive-a-fsm" title="Permalink to this headline">¶</a></h3>
 690 <p>There are <em>lots</em> of FSM libraries already. Once you have the state
 691 transition table they should all be straightforward to use. State
 692 Machine code is very simple. Just for fun, here is an implementation in
 693 Python that imitates what “compiled” FSM code might look like in an
 694 “unrolled” form. Most FSM code uses a little driver loop and a table
 695 datastructure, the code below instead acts like JMP instructions
 696 (“jump”, or GOTO in higher-level-but-still-low-level languages) to
 697 hard-code the information in the table into a little patch of branches.</p>
 698 <section id="trampoline-function">
 699 <h4>Trampoline Function<a class="headerlink" href="#trampoline-function" title="Permalink to this headline">¶</a></h4>
 700 <p>Python has no GOTO statement but we can fake it with a “trampoline”
 701 function.</p>
 702 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">trampoline</span><span class="p">(</span><span class="n">input_</span><span class="p">,</span> <span class="n">jump_from</span><span class="p">,</span> <span class="n">accepting</span><span class="p">):</span>
 703     <span class="n">I</span> <span class="o">=</span> <span class="nb">iter</span><span class="p">(</span><span class="n">input_</span><span class="p">)</span>
 704     <span class="k">while</span> <span class="kc">True</span><span class="p">:</span>
 705         <span class="k">try</span><span class="p">:</span>
 706             <span class="n">bounce_to</span> <span class="o">=</span> <span class="n">jump_from</span><span class="p">(</span><span class="n">I</span><span class="p">)</span>
 707         <span class="k">except</span> <span class="ne">StopIteration</span><span class="p">:</span>
 708             <span class="k">return</span> <span class="n">jump_from</span> <span class="ow">in</span> <span class="n">accepting</span>
 709         <span class="n">jump_from</span> <span class="o">=</span> <span class="n">bounce_to</span>
 710 </pre></div>
 711 </div>
 712 </section>
 713 <section id="stream-functions">
 714 <h4>Stream Functions<a class="headerlink" href="#stream-functions" title="Permalink to this headline">¶</a></h4>
 715 <p>Little helpers to process the iterator of our data (a “stream” of “1”
 716 and “0” characters, not bits.)</p>
 717 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">getch</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="nb">int</span><span class="p">(</span><span class="nb">next</span><span class="p">(</span><span class="n">I</span><span class="p">))</span>
 718
 719
 720 <span class="k">def</span> <span class="nf">_1</span><span class="p">(</span><span class="n">I</span><span class="p">):</span>
 721     <span class="sd">&#39;&#39;&#39;Loop on ones.&#39;&#39;&#39;</span>
 722     <span class="k">while</span> <span class="n">getch</span><span class="p">(</span><span class="n">I</span><span class="p">):</span> <span class="k">pass</span>
 723
 724
 725 <span class="k">def</span> <span class="nf">_0</span><span class="p">(</span><span class="n">I</span><span class="p">):</span>
 726     <span class="sd">&#39;&#39;&#39;Loop on zeros.&#39;&#39;&#39;</span>
 727     <span class="k">while</span> <span class="ow">not</span> <span class="n">getch</span><span class="p">(</span><span class="n">I</span><span class="p">):</span> <span class="k">pass</span>
 728 </pre></div>
 729 </div>
 730 </section>
 731 <section id="a-finite-state-machine">
 732 <h4>A Finite State Machine<a class="headerlink" href="#a-finite-state-machine" title="Permalink to this headline">¶</a></h4>
 733 <p>With those preliminaries out of the way, from the state table of
 734 <code class="docutils literal notranslate"><span class="pre">.111.</span> <span class="pre">&amp;</span> <span class="pre">(.01</span> <span class="pre">+</span> <span class="pre">11*)'</span></code> we can immediately write down state machine
 735 code. (You have to imagine that these are GOTO statements in C or
 736 branches in assembly and that the state names are branch destination
 737 labels.)</p>
 738 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">a</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">c</span> <span class="k">if</span> <span class="n">getch</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="k">else</span> <span class="n">b</span>
 739 <span class="n">b</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">_0</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="ow">or</span> <span class="n">d</span>
 740 <span class="n">c</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">e</span> <span class="k">if</span> <span class="n">getch</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="k">else</span> <span class="n">b</span>
 741 <span class="n">d</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">f</span> <span class="k">if</span> <span class="n">getch</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="k">else</span> <span class="n">b</span>
 742 <span class="n">e</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">g</span> <span class="k">if</span> <span class="n">getch</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="k">else</span> <span class="n">b</span>
 743 <span class="n">f</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">h</span> <span class="k">if</span> <span class="n">getch</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="k">else</span> <span class="n">b</span>
 744 <span class="n">g</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">_1</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="ow">or</span> <span class="n">i</span>
 745 <span class="n">h</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">_1</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="ow">or</span> <span class="n">i</span>
 746 <span class="n">i</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">_0</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="ow">or</span> <span class="n">j</span>
 747 <span class="n">j</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">h</span> <span class="k">if</span> <span class="n">getch</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="k">else</span> <span class="n">i</span>
 748 </pre></div>
 749 </div>
 750 <p>Note that the implementations of <code class="docutils literal notranslate"><span class="pre">h</span></code> and <code class="docutils literal notranslate"><span class="pre">g</span></code> are identical ergo
 751 <code class="docutils literal notranslate"><span class="pre">h</span> <span class="pre">=</span> <span class="pre">g</span></code> and we could eliminate one in the code but <code class="docutils literal notranslate"><span class="pre">h</span></code> is an
 752 accepting state and <code class="docutils literal notranslate"><span class="pre">g</span></code> isn’t.</p>
 753 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">acceptable</span><span class="p">(</span><span class="n">input_</span><span class="p">):</span>
 754     <span class="k">return</span> <span class="n">trampoline</span><span class="p">(</span><span class="n">input_</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="p">{</span><span class="n">h</span><span class="p">,</span> <span class="n">i</span><span class="p">})</span>
 755 </pre></div>
 756 </div>
 757 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="k">for</span> <span class="n">n</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">2</span><span class="o">**</span><span class="mi">5</span><span class="p">):</span>
 758     <span class="n">s</span> <span class="o">=</span> <span class="nb">bin</span><span class="p">(</span><span class="n">n</span><span class="p">)[</span><span class="mi">2</span><span class="p">:]</span>
 759     <span class="nb">print</span> <span class="s1">&#39;</span><span class="si">%05s</span><span class="s1">&#39;</span> <span class="o">%</span> <span class="n">s</span><span class="p">,</span> <span class="n">acceptable</span><span class="p">(</span><span class="n">s</span><span class="p">)</span>
 760 </pre></div>
 761 </div>
 762 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>    <span class="mi">0</span> <span class="kc">False</span>
 763     <span class="mi">1</span> <span class="kc">False</span>
 764    <span class="mi">10</span> <span class="kc">False</span>
 765    <span class="mi">11</span> <span class="kc">False</span>
 766   <span class="mi">100</span> <span class="kc">False</span>
 767   <span class="mi">101</span> <span class="kc">False</span>
 768   <span class="mi">110</span> <span class="kc">False</span>
 769   <span class="mi">111</span> <span class="kc">False</span>
 770  <span class="mi">1000</span> <span class="kc">False</span>
 771  <span class="mi">1001</span> <span class="kc">False</span>
 772  <span class="mi">1010</span> <span class="kc">False</span>
 773  <span class="mi">1011</span> <span class="kc">False</span>
 774  <span class="mi">1100</span> <span class="kc">False</span>
 775  <span class="mi">1101</span> <span class="kc">False</span>
 776  <span class="mi">1110</span> <span class="kc">True</span>
 777  <span class="mi">1111</span> <span class="kc">False</span>
 778 <span class="mi">10000</span> <span class="kc">False</span>
 779 <span class="mi">10001</span> <span class="kc">False</span>
 780 <span class="mi">10010</span> <span class="kc">False</span>
 781 <span class="mi">10011</span> <span class="kc">False</span>
 782 <span class="mi">10100</span> <span class="kc">False</span>
 783 <span class="mi">10101</span> <span class="kc">False</span>
 784 <span class="mi">10110</span> <span class="kc">False</span>
 785 <span class="mi">10111</span> <span class="kc">True</span>
 786 <span class="mi">11000</span> <span class="kc">False</span>
 787 <span class="mi">11001</span> <span class="kc">False</span>
 788 <span class="mi">11010</span> <span class="kc">False</span>
 789 <span class="mi">11011</span> <span class="kc">False</span>
 790 <span class="mi">11100</span> <span class="kc">True</span>
 791 <span class="mi">11101</span> <span class="kc">False</span>
 792 <span class="mi">11110</span> <span class="kc">True</span>
 793 <span class="mi">11111</span> <span class="kc">False</span>
 794 </pre></div>
 795 </div>
 796 </section>
 797 </section>
 798 </section>
 799 <section id="reversing-the-derivatives-to-generate-matching-strings">
 800 <h2>Reversing the Derivatives to Generate Matching Strings<a class="headerlink" href="#reversing-the-derivatives-to-generate-matching-strings" title="Permalink to this headline">¶</a></h2>
 801 <p>(UNFINISHED) Brzozowski also shewed how to go from the state machine to
 802 strings and expressions…</p>
 803 <p>Each of these states is just a name for a Brzozowskian RE, and so, other
 804 than the initial state <code class="docutils literal notranslate"><span class="pre">a</span></code>, they can can be described in terms of the
 805 derivative-with-respect-to-N of some other state/RE:</p>
 806 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">c</span> <span class="o">=</span> <span class="n">d1</span><span class="p">(</span><span class="n">a</span><span class="p">)</span>
 807 <span class="n">b</span> <span class="o">=</span> <span class="n">d0</span><span class="p">(</span><span class="n">a</span><span class="p">)</span>
 808 <span class="n">b</span> <span class="o">=</span> <span class="n">d0</span><span class="p">(</span><span class="n">c</span><span class="p">)</span>
 809 <span class="o">...</span>
 810 <span class="n">i</span> <span class="o">=</span> <span class="n">d0</span><span class="p">(</span><span class="n">j</span><span class="p">)</span>
 811 <span class="n">j</span> <span class="o">=</span> <span class="n">d1</span><span class="p">(</span><span class="n">i</span><span class="p">)</span>
 812 </pre></div>
 813 </div>
 814 <p>Consider:</p>
 815 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">c</span> <span class="o">=</span> <span class="n">d1</span><span class="p">(</span><span class="n">a</span><span class="p">)</span>
 816 <span class="n">b</span> <span class="o">=</span> <span class="n">d0</span><span class="p">(</span><span class="n">c</span><span class="p">)</span>
 817 </pre></div>
 818 </div>
 819 <p>Substituting:</p>
 820 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">b</span> <span class="o">=</span> <span class="n">d0</span><span class="p">(</span><span class="n">d1</span><span class="p">(</span><span class="n">a</span><span class="p">))</span>
 821 </pre></div>
 822 </div>
 823 <p>Unwrapping:</p>
 824 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">b</span> <span class="o">=</span> <span class="n">d10</span><span class="p">(</span><span class="n">a</span><span class="p">)</span>
 825 </pre></div>
 826 </div>
 827 <p>’’’</p>
 828 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">j</span> <span class="o">=</span> <span class="n">d1</span><span class="p">(</span><span class="n">d0</span><span class="p">(</span><span class="n">j</span><span class="p">))</span>
 829 </pre></div>
 830 </div>
 831 <p>Unwrapping:</p>
 832 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">j</span> <span class="o">=</span> <span class="n">d1</span><span class="p">(</span><span class="n">d0</span><span class="p">(</span><span class="n">j</span><span class="p">))</span> <span class="o">=</span> <span class="n">d01</span><span class="p">(</span><span class="n">j</span><span class="p">)</span>
 833 </pre></div>
 834 </div>
 835 <p>We have a loop or “fixed point”.</p>
 836 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">j</span> <span class="o">=</span> <span class="n">d01</span><span class="p">(</span><span class="n">j</span><span class="p">)</span> <span class="o">=</span> <span class="n">d0101</span><span class="p">(</span><span class="n">j</span><span class="p">)</span> <span class="o">=</span> <span class="n">d010101</span><span class="p">(</span><span class="n">j</span><span class="p">)</span> <span class="o">=</span> <span class="o">...</span>
 837 </pre></div>
 838 </div>
 839 <p>hmm…</p>
 840 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">j</span> <span class="o">=</span> <span class="p">(</span><span class="mi">01</span><span class="p">)</span><span class="o">*</span>
 841 </pre></div>
 842 </div>
 843 </section>
 844 </section>
 845
 846
 847           </div>
 848
 849         </div>
 850       </div>
 851       <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
 852         <div class="sphinxsidebarwrapper">
 853 <h1 class="logo"><a href="../index.html">Thun</a></h1>
 854
 855
 856
 857
 858
 859
 860
 861
 862 <h3>Navigation</h3>
 863 <ul class="current">
 864 <li class="toctree-l1"><a class="reference internal" href="Intro.html">Thun: Joy in Python</a></li>
 865 <li class="toctree-l1"><a class="reference internal" href="../joy.html">Joy Interpreter</a></li>
 866 <li class="toctree-l1"><a class="reference internal" href="../stack.html">Stack or Quote or Sequence or List…</a></li>
 867 <li class="toctree-l1"><a class="reference internal" href="../parser.html">Parsing Text into Joy Expressions</a></li>
 868 <li class="toctree-l1"><a class="reference internal" href="../pretty.html">Tracing Joy Execution</a></li>
 869 <li class="toctree-l1"><a class="reference internal" href="../library.html">Function Reference</a></li>
 870 <li class="toctree-l1"><a class="reference internal" href="../lib.html">Functions Grouped by, er, Function with Examples</a></li>
 871 <li class="toctree-l1"><a class="reference internal" href="../types.html">Type Inference of Joy Expressions</a></li>
 872 <li class="toctree-l1 current"><a class="reference internal" href="index.html">Essays about Programming in Joy</a><ul class="current">
 873 <li class="toctree-l2"><a class="reference internal" href="Developing.html">Developing a Program in Joy</a></li>
 874 <li class="toctree-l2"><a class="reference internal" href="Quadratic.html">Quadratic formula</a></li>
 875 <li class="toctree-l2"><a class="reference internal" href="Replacing.html">Replacing Functions in the Dictionary</a></li>
 876 <li class="toctree-l2"><a class="reference internal" href="Recursion_Combinators.html">Recursion Combinators</a></li>
 877 <li class="toctree-l2"><a class="reference internal" href="Ordered_Binary_Trees.html">Treating Trees I: Ordered Binary Trees</a></li>
 878 <li class="toctree-l2"><a class="reference internal" href="Treestep.html">Treating Trees II: <code class="docutils literal notranslate"><span class="pre">treestep</span></code></a></li>
 879 <li class="toctree-l2"><a class="reference internal" href="Generator_Programs.html">Using <code class="docutils literal notranslate"><span class="pre">x</span></code> to Generate Values</a></li>
 880 <li class="toctree-l2"><a class="reference internal" href="Newton-Raphson.html">Newton’s method</a></li>
 881 <li class="toctree-l2"><a class="reference internal" href="Square_Spiral.html">Square Spiral Example Joy Code</a></li>
 882 <li class="toctree-l2"><a class="reference internal" href="Zipper.html">Traversing Datastructures with Zippers</a></li>
 883 <li class="toctree-l2"><a class="reference internal" href="Types.html">The Blissful Elegance of Typing Joy</a></li>
 884 <li class="toctree-l2"><a class="reference internal" href="TypeChecking.html">Type Checking</a></li>
 885 <li class="toctree-l2"><a class="reference internal" href="NoUpdates.html">No Updates</a></li>
 886 <li class="toctree-l2"><a class="reference internal" href="Categorical.html">Categorical Programming</a></li>
 887 <li class="toctree-l2"><a class="reference internal" href="The_Four_Operations.html">The Four Fundamental Operations of Definite Action</a></li>
 888 <li class="toctree-l2 current"><a class="current reference internal" href="#">∂RE</a></li>
 889 </ul>
 890 </li>
 891 </ul>
 892
 893 <div class="relations">
 894 <h3>Related Topics</h3>
 895 <ul>
 896   <li><a href="../index.html">Documentation overview</a><ul>
 897   <li><a href="index.html">Essays about Programming in Joy</a><ul>
 898       <li>Previous: <a href="The_Four_Operations.html" title="previous chapter">The Four Fundamental Operations of Definite Action</a></li>
 899   </ul></li>
 900   </ul></li>
 901 </ul>
 902 </div>
 903 <div id="searchbox" style="display: none" role="search">
 904   <h3 id="searchlabel">Quick search</h3>
 905     <div class="searchformwrapper">
 906     <form class="search" action="../search.html" method="get">
 907       <input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
 908       <input type="submit" value="Go" />
 909     </form>
 910     </div>
 911 </div>
 912 <script>$('#searchbox').show(0);</script>
 913
 914
 915
 916
 917
 918
 919
 920
 921         </div>
 922       </div>
 923       <div class="clearer"></div>
 924     </div>
 925     <div class="footer" role="contentinfo">
 926 <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">
 927 <img alt="Creative Commons License" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png" />
 928 </a>
 929 <br />
 930 <span xmlns:dct="http://purl.org/dc/terms/" property="dct:title">Thun Documentation</span> by <a xmlns:cc="http://creativecommons.org/ns#" href="https://joypy.osdn.io/" property="cc:attributionName" rel="cc:attributionURL">Simon Forman</a> is licensed under a <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License</a>.<br />Based on a work at <a xmlns:dct="http://purl.org/dc/terms/" href="https://osdn.net/projects/joypy/" rel="dct:source">https://osdn.net/projects/joypy/</a>.
 931       Created using <a href="http://sphinx-doc.org/">Sphinx</a> 4.3.0.
 932     </div>
 933
 934   </body>
 935 </html>