docs/sphinx_docs/_build/html/notebooks/The_Four_Operations.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>The Four Fundamental Operations of Definite Action &#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="next" title="∂RE" href="Derivatives_of_Regular_Expressions.html" />
  19     <link rel="prev" title="Categorical Programming" href="Categorical.html" />
  20
  21   <link rel="stylesheet" href="../_static/custom.css" type="text/css" />
  22
  23
  24   <meta name="viewport" content="width=device-width, initial-scale=0.9, maximum-scale=0.9" />
  25
  26   </head><body>
  27
  28
  29     <div class="document">
  30       <div class="documentwrapper">
  31         <div class="bodywrapper">
  32
  33
  34           <div class="body" role="main">
  35
  36   <section id="the-four-fundamental-operations-of-definite-action">
  37 <h1>The Four Fundamental Operations of Definite Action<a class="headerlink" href="#the-four-fundamental-operations-of-definite-action" title="Permalink to this headline">¶</a></h1>
  38 <p>All definite actions (computer program) can be defined by four
  39 fundamental patterns of combination:</p>
  40 <ol class="arabic simple">
  41 <li><p>Sequence</p></li>
  42 <li><p>Branch</p></li>
  43 <li><p>Loop</p></li>
  44 <li><p>Parallel</p></li>
  45 </ol>
  46 <section id="sequence">
  47 <h2>Sequence<a class="headerlink" href="#sequence" title="Permalink to this headline">¶</a></h2>
  48 <p>Do one thing after another. In joy this is represented by putting two
  49 symbols together, juxtaposition:</p>
  50 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">foo</span> <span class="n">bar</span>
  51 </pre></div>
  52 </div>
  53 <p>Operations have inputs and outputs. The outputs of <code class="docutils literal notranslate"><span class="pre">foo</span></code> must be
  54 compatible in “arity”, type, and shape with the inputs of <code class="docutils literal notranslate"><span class="pre">bar</span></code>.</p>
  55 </section>
  56 <section id="branch">
  57 <h2>Branch<a class="headerlink" href="#branch" title="Permalink to this headline">¶</a></h2>
  58 <p>Do one thing or another.</p>
  59 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">boolean</span> <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="n">branch</span>
  60
  61
  62    <span class="n">t</span> <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="n">branch</span>
  63 <span class="o">----------------------</span>
  64           <span class="n">T</span>
  65
  66
  67    <span class="n">f</span> <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="n">branch</span>
  68 <span class="o">----------------------</span>
  69       <span class="n">F</span>
  70
  71
  72 <span class="n">branch</span> <span class="o">==</span> <span class="n">unit</span> <span class="n">cons</span> <span class="n">swap</span> <span class="n">pick</span> <span class="n">i</span>
  73
  74 <span class="n">boolean</span> <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="n">branch</span>
  75 <span class="n">boolean</span> <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="n">unit</span> <span class="n">cons</span> <span class="n">swap</span> <span class="n">pick</span> <span class="n">i</span>
  76 <span class="n">boolean</span> <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="p">[[</span><span class="n">T</span><span class="p">]]</span> <span class="n">cons</span> <span class="n">swap</span> <span class="n">pick</span> <span class="n">i</span>
  77 <span class="n">boolean</span> <span class="p">[[</span><span class="n">F</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="p">]]</span> <span class="n">swap</span> <span class="n">pick</span> <span class="n">i</span>
  78 <span class="p">[[</span><span class="n">F</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="p">]]</span> <span class="n">boolean</span> <span class="n">pick</span> <span class="n">i</span>
  79 <span class="p">[</span><span class="n">F</span><span class="o">-</span><span class="ow">or</span><span class="o">-</span><span class="n">T</span><span class="p">]</span> <span class="n">i</span>
  80 </pre></div>
  81 </div>
  82 <p>Given some branch function <code class="docutils literal notranslate"><span class="pre">G</span></code>:</p>
  83 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">G</span> <span class="o">==</span> <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="n">branch</span>
  84 </pre></div>
  85 </div>
  86 <p>Used in a sequence like so:</p>
  87 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">foo</span> <span class="n">G</span> <span class="n">bar</span>
  88 </pre></div>
  89 </div>
  90 <p>The inputs and outputs of <code class="docutils literal notranslate"><span class="pre">F</span></code> and <code class="docutils literal notranslate"><span class="pre">T</span></code> must be compatible with the
  91 outputs for <code class="docutils literal notranslate"><span class="pre">foo</span></code> and the inputs of <code class="docutils literal notranslate"><span class="pre">bar</span></code>, respectively.</p>
  92 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">foo</span> <span class="n">F</span> <span class="n">bar</span>
  93
  94 <span class="n">foo</span> <span class="n">T</span> <span class="n">bar</span>
  95 </pre></div>
  96 </div>
  97 <section id="ifte">
  98 <h3><code class="docutils literal notranslate"><span class="pre">ifte</span></code><a class="headerlink" href="#ifte" title="Permalink to this headline">¶</a></h3>
  99 <p>Often it will be easier on the programmer to write branching code with
 100 the predicate specified in a quote. The <code class="docutils literal notranslate"><span class="pre">ifte</span></code> combinator provides
 101 this (<code class="docutils literal notranslate"><span class="pre">T</span></code> for “then” and <code class="docutils literal notranslate"><span class="pre">E</span></code> for “else”):</p>
 102 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="p">[</span><span class="n">E</span><span class="p">]</span> <span class="n">ifte</span>
 103 </pre></div>
 104 </div>
 105 <p>Defined in terms of <code class="docutils literal notranslate"><span class="pre">branch</span></code>:</p>
 106 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">ifte</span> <span class="o">==</span> <span class="p">[</span><span class="n">nullary</span> <span class="ow">not</span><span class="p">]</span> <span class="n">dip</span> <span class="n">branch</span>
 107 </pre></div>
 108 </div>
 109 <p>In this case, <code class="docutils literal notranslate"><span class="pre">P</span></code> must be compatible with the stack and return a
 110 Boolean value, and <code class="docutils literal notranslate"><span class="pre">T</span></code> and <code class="docutils literal notranslate"><span class="pre">E</span></code> both must be compatible with the
 111 preceeding and following functions, as described above for <code class="docutils literal notranslate"><span class="pre">F</span></code> and
 112 <code class="docutils literal notranslate"><span class="pre">T</span></code>. (Note that in the current implementation we are depending on
 113 Python for the underlying semantics, so the Boolean value doesn’t <em>have</em>
 114 to be Boolean because Python’s rules for “truthiness” will be used to
 115 evaluate it. I reflect this in the structure of the stack effect comment
 116 of <code class="docutils literal notranslate"><span class="pre">branch</span></code>, it will only accept Boolean values, and in the definition
 117 of <code class="docutils literal notranslate"><span class="pre">ifte</span></code> above by including <code class="docutils literal notranslate"><span class="pre">not</span></code> in the quote, which also has the
 118 effect that the subject quotes are in the proper order for <code class="docutils literal notranslate"><span class="pre">branch</span></code>.)</p>
 119 </section>
 120 </section>
 121 <section id="loop">
 122 <h2>Loop<a class="headerlink" href="#loop" title="Permalink to this headline">¶</a></h2>
 123 <p>Do one thing zero or more times.</p>
 124 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">boolean</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">loop</span>
 125
 126
 127    <span class="n">t</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">loop</span>
 128 <span class="o">----------------</span>
 129    <span class="n">Q</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">loop</span>
 130
 131
 132    <span class="o">...</span> <span class="n">f</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">loop</span>
 133 <span class="o">--------------------</span>
 134    <span class="o">...</span>
 135 </pre></div>
 136 </div>
 137 <p>The <code class="docutils literal notranslate"><span class="pre">loop</span></code> combinator generates a copy of itself in the true branch.
 138 This is the hallmark of recursive defintions. In Thun there is no
 139 equivalent to conventional loops. (There is, however, the <code class="docutils literal notranslate"><span class="pre">x</span></code>
 140 combinator, defined as <code class="docutils literal notranslate"><span class="pre">x</span> <span class="pre">==</span> <span class="pre">dup</span> <span class="pre">i</span></code>, which permits recursive
 141 constructs that do not need to be directly self-referential, unlike
 142 <code class="docutils literal notranslate"><span class="pre">loop</span></code> and <code class="docutils literal notranslate"><span class="pre">genrec</span></code>.)</p>
 143 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">loop</span> <span class="o">==</span> <span class="p">[]</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="n">dip</span> <span class="n">loop</span><span class="p">]</span> <span class="n">cons</span> <span class="n">branch</span>
 144
 145 <span class="n">boolean</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">loop</span>
 146 <span class="n">boolean</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="p">[]</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="n">dip</span> <span class="n">loop</span><span class="p">]</span> <span class="n">cons</span> <span class="n">branch</span>
 147 <span class="n">boolean</span> <span class="p">[]</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="p">[</span><span class="n">dup</span> <span class="n">dip</span> <span class="n">loop</span><span class="p">]</span> <span class="n">cons</span> <span class="n">branch</span>
 148 <span class="n">boolean</span> <span class="p">[]</span> <span class="p">[[</span><span class="n">Q</span><span class="p">]</span> <span class="n">dup</span> <span class="n">dip</span> <span class="n">loop</span><span class="p">]</span> <span class="n">branch</span>
 149 </pre></div>
 150 </div>
 151 <p>In action the false branch does nothing while the true branch does:</p>
 152 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">t</span> <span class="p">[]</span> <span class="p">[[</span><span class="n">Q</span><span class="p">]</span> <span class="n">dup</span> <span class="n">dip</span> <span class="n">loop</span><span class="p">]</span> <span class="n">branch</span>
 153       <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">dup</span> <span class="n">dip</span> <span class="n">loop</span>
 154       <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">dip</span> <span class="n">loop</span>
 155       <span class="n">Q</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">loop</span>
 156 </pre></div>
 157 </div>
 158 <p>Because <code class="docutils literal notranslate"><span class="pre">loop</span></code> expects and consumes a Boolean value, the <code class="docutils literal notranslate"><span class="pre">Q</span></code>
 159 function must be compatible with the previous stack <em>and itself</em> with a
 160 boolean flag for the next iteration:</p>
 161 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Q</span> <span class="o">==</span> <span class="n">G</span> <span class="n">b</span>
 162
 163 <span class="n">Q</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">loop</span>
 164 <span class="n">G</span> <span class="n">b</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">loop</span>
 165 <span class="n">G</span> <span class="n">Q</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">loop</span>
 166 <span class="n">G</span> <span class="n">G</span> <span class="n">b</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">loop</span>
 167 <span class="n">G</span> <span class="n">G</span> <span class="n">Q</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">loop</span>
 168 <span class="n">G</span> <span class="n">G</span> <span class="n">G</span> <span class="n">b</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">loop</span>
 169 <span class="n">G</span> <span class="n">G</span> <span class="n">G</span>
 170 </pre></div>
 171 </div>
 172 <section id="while">
 173 <h3><code class="docutils literal notranslate"><span class="pre">while</span></code><a class="headerlink" href="#while" title="Permalink to this headline">¶</a></h3>
 174 <p>Keep doing <code class="docutils literal notranslate"><span class="pre">B</span></code> <em>while</em> some predicate <code class="docutils literal notranslate"><span class="pre">P</span></code> is true. This is
 175 convenient as the predicate function is made nullary automatically and
 176 the body function can be designed without regard to leaving a Boolean
 177 flag for the next iteration:</p>
 178 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>            <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="k">while</span>
 179 <span class="o">--------------------------------------</span>
 180    <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="n">nullary</span> <span class="p">[</span><span class="n">B</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="n">nullary</span><span class="p">]</span> <span class="n">loop</span>
 181
 182
 183 <span class="k">while</span> <span class="o">==</span> <span class="n">swap</span> <span class="p">[</span><span class="n">nullary</span><span class="p">]</span> <span class="n">cons</span> <span class="n">dup</span> <span class="n">dipd</span> <span class="n">concat</span> <span class="n">loop</span>
 184
 185
 186 <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="k">while</span>
 187 <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="n">swap</span> <span class="p">[</span><span class="n">nullary</span><span class="p">]</span> <span class="n">cons</span> <span class="n">dup</span> <span class="n">dipd</span> <span class="n">concat</span> <span class="n">loop</span>
 188 <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">nullary</span><span class="p">]</span> <span class="n">cons</span> <span class="n">dup</span> <span class="n">dipd</span> <span class="n">concat</span> <span class="n">loop</span>
 189 <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[[</span><span class="n">P</span><span class="p">]</span> <span class="n">nullary</span><span class="p">]</span> <span class="n">dup</span> <span class="n">dipd</span> <span class="n">concat</span> <span class="n">loop</span>
 190 <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[[</span><span class="n">P</span><span class="p">]</span> <span class="n">nullary</span><span class="p">]</span> <span class="p">[[</span><span class="n">P</span><span class="p">]</span> <span class="n">nullary</span><span class="p">]</span> <span class="n">dipd</span> <span class="n">concat</span> <span class="n">loop</span>
 191 <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="n">nullary</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[[</span><span class="n">P</span><span class="p">]</span> <span class="n">nullary</span><span class="p">]</span> <span class="n">concat</span> <span class="n">loop</span>
 192 <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="n">nullary</span> <span class="p">[</span><span class="n">B</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="n">nullary</span><span class="p">]</span> <span class="n">loop</span>
 193 </pre></div>
 194 </div>
 195 </section>
 196 </section>
 197 <section id="parallel">
 198 <h2>Parallel<a class="headerlink" href="#parallel" title="Permalink to this headline">¶</a></h2>
 199 <p>The <em>parallel</em> operation indicates that two (or more) functions <em>do not
 200 interfere</em> with each other and so can run in parallel. The main
 201 difficulty in this sort of thing is orchestrating the recombining
 202 (“join” or “wait”) of the results of the functions after they finish.</p>
 203 <p>The current implementaions and the following definitions <em>are not
 204 actually parallel</em> (yet), but there is no reason they couldn’t be
 205 reimplemented in terms of e.g. Python threads. I am not concerned with
 206 performance of the system just yet, only the elegance of the code it
 207 allows us to write.</p>
 208 <section id="cleave">
 209 <h3><code class="docutils literal notranslate"><span class="pre">cleave</span></code><a class="headerlink" href="#cleave" title="Permalink to this headline">¶</a></h3>
 210 <p>Joy has a few parallel combinators, the main one being <code class="docutils literal notranslate"><span class="pre">cleave</span></code>:</p>
 211 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>               <span class="o">...</span> <span class="n">x</span> <span class="p">[</span><span class="n">A</span><span class="p">]</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="n">cleave</span>
 212 <span class="o">---------------------------------------------------------</span>
 213    <span class="o">...</span> <span class="p">[</span><span class="n">x</span> <span class="o">...</span><span class="p">]</span> <span class="p">[</span><span class="n">A</span><span class="p">]</span> <span class="n">infra</span> <span class="n">first</span> <span class="p">[</span><span class="n">x</span> <span class="o">...</span><span class="p">]</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="n">infra</span> <span class="n">first</span>
 214 <span class="o">---------------------------------------------------------</span>
 215                    <span class="o">...</span> <span class="n">a</span> <span class="n">b</span>
 216 </pre></div>
 217 </div>
 218 <p>The <code class="docutils literal notranslate"><span class="pre">cleave</span></code> combinator expects a value and two quotes and it executes
 219 each quote in “separate universes” such that neither can affect the
 220 other, then it takes the first item from the stack in each universe and
 221 replaces the value and quotes with their respective results.</p>
 222 <p>(I think this corresponds to the “fork” operator, the little
 223 upward-pointed triangle, that takes two functions <code class="docutils literal notranslate"><span class="pre">A</span> <span class="pre">::</span> <span class="pre">x</span> <span class="pre">-&gt;</span> <span class="pre">a</span></code> and
 224 <code class="docutils literal notranslate"><span class="pre">B</span> <span class="pre">::</span> <span class="pre">x</span> <span class="pre">-&gt;</span> <span class="pre">b</span></code> and returns a function <code class="docutils literal notranslate"><span class="pre">F</span> <span class="pre">::</span> <span class="pre">x</span> <span class="pre">-&gt;</span> <span class="pre">(a,</span> <span class="pre">b)</span></code>, in Conal
 225 Elliott’s “Compiling to Categories” paper, et. al.)</p>
 226 <p>Just a thought, if you <code class="docutils literal notranslate"><span class="pre">cleave</span></code> two jobs and one requires more time to
 227 finish than the other you’d like to be able to assign resources
 228 accordingly so that they both finish at the same time.</p>
 229 </section>
 230 <section id="apply-functions">
 231 <h3>“Apply” Functions<a class="headerlink" href="#apply-functions" title="Permalink to this headline">¶</a></h3>
 232 <p>There are also <code class="docutils literal notranslate"><span class="pre">app2</span></code> and <code class="docutils literal notranslate"><span class="pre">app3</span></code> which run a single quote on more
 233 than one value:</p>
 234 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>                <span class="o">...</span> <span class="n">y</span> <span class="n">x</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">app2</span>
 235 <span class="o">---------------------------------------------------------</span>
 236    <span class="o">...</span> <span class="p">[</span><span class="n">y</span> <span class="o">...</span><span class="p">]</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">infra</span> <span class="n">first</span> <span class="p">[</span><span class="n">x</span> <span class="o">...</span><span class="p">]</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">infra</span> <span class="n">first</span>
 237
 238
 239        <span class="o">...</span> <span class="n">z</span> <span class="n">y</span> <span class="n">x</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">app3</span>
 240 <span class="o">---------------------------------</span>
 241    <span class="o">...</span> <span class="p">[</span><span class="n">z</span> <span class="o">...</span><span class="p">]</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">infra</span> <span class="n">first</span>
 242        <span class="p">[</span><span class="n">y</span> <span class="o">...</span><span class="p">]</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">infra</span> <span class="n">first</span>
 243        <span class="p">[</span><span class="n">x</span> <span class="o">...</span><span class="p">]</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">infra</span> <span class="n">first</span>
 244 </pre></div>
 245 </div>
 246 <p>Because the quoted program can be <code class="docutils literal notranslate"><span class="pre">i</span></code> we can define <code class="docutils literal notranslate"><span class="pre">cleave</span></code> in
 247 terms of <code class="docutils literal notranslate"><span class="pre">app2</span></code>:</p>
 248 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">cleave</span> <span class="o">==</span> <span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="n">app2</span> <span class="p">[</span><span class="n">popd</span><span class="p">]</span> <span class="n">dip</span>
 249 </pre></div>
 250 </div>
 251 <p>(I’m not sure why <code class="docutils literal notranslate"><span class="pre">cleave</span></code> was specified to take that value, I may
 252 make a combinator that does the same thing but without expecting a
 253 value.)</p>
 254 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">clv</span> <span class="o">==</span> <span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="n">app2</span>
 255
 256    <span class="p">[</span><span class="n">A</span><span class="p">]</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="n">clv</span>
 257 <span class="o">------------------</span>
 258      <span class="n">a</span> <span class="n">b</span>
 259 </pre></div>
 260 </div>
 261 </section>
 262 <section id="map">
 263 <h3><code class="docutils literal notranslate"><span class="pre">map</span></code><a class="headerlink" href="#map" title="Permalink to this headline">¶</a></h3>
 264 <p>The common <code class="docutils literal notranslate"><span class="pre">map</span></code> function in Joy should also be though of as a
 265 <em>parallel</em> operator:</p>
 266 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">a</span> <span class="n">b</span> <span class="n">c</span> <span class="o">...</span><span class="p">]</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="nb">map</span>
 267 </pre></div>
 268 </div>
 269 <p>There is no reason why the implementation of <code class="docutils literal notranslate"><span class="pre">map</span></code> couldn’t distribute
 270 the <code class="docutils literal notranslate"><span class="pre">Q</span></code> function over e.g. a pool of worker CPUs.</p>
 271 </section>
 272 <section id="pam">
 273 <h3><code class="docutils literal notranslate"><span class="pre">pam</span></code><a class="headerlink" href="#pam" title="Permalink to this headline">¶</a></h3>
 274 <p>One of my favorite combinators, the <code class="docutils literal notranslate"><span class="pre">pam</span></code> combinator is just:</p>
 275 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">pam</span> <span class="o">==</span> <span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="nb">map</span>
 276 </pre></div>
 277 </div>
 278 <p>This can be used to run any number of programs separately on the current
 279 stack and combine their (first) outputs in a result list.</p>
 280 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="p">[[</span><span class="n">A</span><span class="p">]</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="o">...</span><span class="p">]</span> <span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="nb">map</span>
 281 <span class="o">-------------------------------</span>
 282    <span class="p">[</span> <span class="n">a</span>   <span class="n">b</span>   <span class="n">c</span>  <span class="o">...</span><span class="p">]</span>
 283 </pre></div>
 284 </div>
 285 </section>
 286 <section id="handling-other-kinds-of-join">
 287 <h3>Handling Other Kinds of Join<a class="headerlink" href="#handling-other-kinds-of-join" title="Permalink to this headline">¶</a></h3>
 288 <p>The <code class="docutils literal notranslate"><span class="pre">cleave</span></code> operators and others all have pretty brutal join
 289 semantics: everything works and we always wait for every
 290 sub-computation. We can imagine a few different potentially useful
 291 patterns of “joining” results from parallel combinators.</p>
 292 <section id="first-to-finish">
 293 <h4>first-to-finish<a class="headerlink" href="#first-to-finish" title="Permalink to this headline">¶</a></h4>
 294 <p>Thinking about variations of <code class="docutils literal notranslate"><span class="pre">pam</span></code> there could be one that only
 295 returns the first result of the first-to-finish sub-program, or the
 296 stack could be replaced by its output stack.</p>
 297 <p>The other sub-programs would be cancelled.</p>
 298 </section>
 299 <section id="fulminators">
 300 <h4>“Fulminators”<a class="headerlink" href="#fulminators" title="Permalink to this headline">¶</a></h4>
 301 <p>Also known as “Futures” or “Promises” (by <em>everybody</em> else. “Fulinators”
 302 is what I was going to call them when I was thinking about implementing
 303 them in Thun.)</p>
 304 <p>The runtime could be amended to permit “thunks” representing the results
 305 of in-progress computations to be left on the stack and picked up by
 306 subsequent functions. These would themselves be able to leave behind
 307 more “thunks”, the values of which depend on the eventual resolution of
 308 the values of the previous thunks.</p>
 309 <p>In this way you can create “chains” (and more complex shapes) out of
 310 normal-looking code that consist of a kind of call-graph interspersed
 311 with “asyncronous” … events?</p>
 312 <p>In any case, until I can find a rigorous theory that shows that this
 313 sort of thing works perfectly in Joy code I’m not going to worry about
 314 it. (And I think the Categories can deal with it anyhow? Incremental
 315 evaluation, yeah?)</p>
 316 </section>
 317 </section>
 318 </section>
 319 </section>
 320
 321
 322           </div>
 323
 324         </div>
 325       </div>
 326       <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
 327         <div class="sphinxsidebarwrapper">
 328 <h1 class="logo"><a href="../index.html">Thun</a></h1>
 329
 330
 331
 332
 333
 334
 335
 336
 337 <h3>Navigation</h3>
 338 <ul class="current">
 339 <li class="toctree-l1"><a class="reference internal" href="Intro.html">Thun: Joy in Python</a></li>
 340 <li class="toctree-l1"><a class="reference internal" href="../joy.html">Joy Interpreter</a></li>
 341 <li class="toctree-l1"><a class="reference internal" href="../stack.html">Stack or Quote or Sequence or List…</a></li>
 342 <li class="toctree-l1"><a class="reference internal" href="../parser.html">Parsing Text into Joy Expressions</a></li>
 343 <li class="toctree-l1"><a class="reference internal" href="../pretty.html">Tracing Joy Execution</a></li>
 344 <li class="toctree-l1"><a class="reference internal" href="../library.html">Function Reference</a></li>
 345 <li class="toctree-l1"><a class="reference internal" href="../lib.html">Functions Grouped by, er, Function with Examples</a></li>
 346 <li class="toctree-l1"><a class="reference internal" href="../types.html">Type Inference of Joy Expressions</a></li>
 347 <li class="toctree-l1 current"><a class="reference internal" href="index.html">Essays about Programming in Joy</a><ul class="current">
 348 <li class="toctree-l2"><a class="reference internal" href="Developing.html">Developing a Program in Joy</a></li>
 349 <li class="toctree-l2"><a class="reference internal" href="Quadratic.html">Quadratic formula</a></li>
 350 <li class="toctree-l2"><a class="reference internal" href="Replacing.html">Replacing Functions in the Dictionary</a></li>
 351 <li class="toctree-l2"><a class="reference internal" href="Recursion_Combinators.html">Recursion Combinators</a></li>
 352 <li class="toctree-l2"><a class="reference internal" href="Ordered_Binary_Trees.html">Treating Trees I: Ordered Binary Trees</a></li>
 353 <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>
 354 <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>
 355 <li class="toctree-l2"><a class="reference internal" href="Newton-Raphson.html">Newton’s method</a></li>
 356 <li class="toctree-l2"><a class="reference internal" href="Square_Spiral.html">Square Spiral Example Joy Code</a></li>
 357 <li class="toctree-l2"><a class="reference internal" href="Zipper.html">Traversing Datastructures with Zippers</a></li>
 358 <li class="toctree-l2"><a class="reference internal" href="Types.html">The Blissful Elegance of Typing Joy</a></li>
 359 <li class="toctree-l2"><a class="reference internal" href="TypeChecking.html">Type Checking</a></li>
 360 <li class="toctree-l2"><a class="reference internal" href="NoUpdates.html">No Updates</a></li>
 361 <li class="toctree-l2"><a class="reference internal" href="Categorical.html">Categorical Programming</a></li>
 362 <li class="toctree-l2 current"><a class="current reference internal" href="#">The Four Fundamental Operations of Definite Action</a></li>
 363 <li class="toctree-l2"><a class="reference internal" href="Derivatives_of_Regular_Expressions.html">∂RE</a></li>
 364 </ul>
 365 </li>
 366 </ul>
 367
 368 <div class="relations">
 369 <h3>Related Topics</h3>
 370 <ul>
 371   <li><a href="../index.html">Documentation overview</a><ul>
 372   <li><a href="index.html">Essays about Programming in Joy</a><ul>
 373       <li>Previous: <a href="Categorical.html" title="previous chapter">Categorical Programming</a></li>
 374       <li>Next: <a href="Derivatives_of_Regular_Expressions.html" title="next chapter">∂RE</a></li>
 375   </ul></li>
 376   </ul></li>
 377 </ul>
 378 </div>
 379 <div id="searchbox" style="display: none" role="search">
 380   <h3 id="searchlabel">Quick search</h3>
 381     <div class="searchformwrapper">
 382     <form class="search" action="../search.html" method="get">
 383       <input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
 384       <input type="submit" value="Go" />
 385     </form>
 386     </div>
 387 </div>
 388 <script>$('#searchbox').show(0);</script>
 389
 390
 391
 392
 393
 394
 395
 396
 397         </div>
 398       </div>
 399       <div class="clearer"></div>
 400     </div>
 401     <div class="footer" role="contentinfo">
 402 <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">
 403 <img alt="Creative Commons License" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png" />
 404 </a>
 405 <br />
 406 <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>.
 407       Created using <a href="http://sphinx-doc.org/">Sphinx</a> 4.3.0.
 408     </div>
 409
 410   </body>
 411 </html>