docs/sphinx_docs/_build/html/notebooks/The_Four_Operations.html

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