2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
3 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
5 <html xmlns="http://www.w3.org/1999/xhtml">
7 <meta http-equiv="X-UA-Compatible" content="IE=Edge" />
8 <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
9 <title>Using x to Generate Values — 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="Newton’s method" href="Newton-Raphson.html" />
20 <link rel="prev" title="Treating Trees II: treestep" href="Treestep.html" />
22 <link rel="stylesheet" href="../_static/custom.css" type="text/css" />
25 <meta name="viewport" content="width=device-width, initial-scale=0.9, maximum-scale=0.9" />
30 <div class="document">
31 <div class="documentwrapper">
32 <div class="bodywrapper">
33 <div class="body" role="main">
35 <div class="section" id="using-x-to-generate-values">
36 <h1>Using <code class="docutils literal notranslate"><span class="pre">x</span></code> to Generate Values<a class="headerlink" href="#using-x-to-generate-values" title="Permalink to this headline">¶</a></h1>
37 <p>Cf. jp-reprod.html</p>
38 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">notebook_preamble</span> <span class="k">import</span> <span class="n">J</span><span class="p">,</span> <span class="n">V</span><span class="p">,</span> <span class="n">define</span>
41 <p>Consider the <code class="docutils literal notranslate"><span class="pre">x</span></code> combinator:</p>
42 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">x</span> <span class="o">==</span> <span class="n">dup</span> <span class="n">i</span>
45 <p>We can apply it to a quoted program consisting of some value <code class="docutils literal notranslate"><span class="pre">a</span></code> and
46 some function <code class="docutils literal notranslate"><span class="pre">B</span></code>:</p>
47 <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="p">]</span> <span class="n">x</span>
48 <span class="p">[</span><span class="n">a</span> <span class="n">B</span><span class="p">]</span> <span class="n">a</span> <span class="n">B</span>
51 <p>Let <code class="docutils literal notranslate"><span class="pre">B</span></code> function <code class="docutils literal notranslate"><span class="pre">swap</span></code> the <code class="docutils literal notranslate"><span class="pre">a</span></code> with the quote and run some
52 function <code class="docutils literal notranslate"><span class="pre">C</span></code> on it to generate a new value <code class="docutils literal notranslate"><span class="pre">b</span></code>:</p>
53 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">B</span> <span class="o">==</span> <span class="n">swap</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="n">dip</span>
55 <span class="p">[</span><span class="n">a</span> <span class="n">B</span><span class="p">]</span> <span class="n">a</span> <span class="n">B</span>
56 <span class="p">[</span><span class="n">a</span> <span class="n">B</span><span class="p">]</span> <span class="n">a</span> <span class="n">swap</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="n">dip</span>
57 <span class="n">a</span> <span class="p">[</span><span class="n">a</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="n">dip</span>
58 <span class="n">a</span> <span class="n">C</span> <span class="p">[</span><span class="n">a</span> <span class="n">B</span><span class="p">]</span>
59 <span class="n">b</span> <span class="p">[</span><span class="n">a</span> <span class="n">B</span><span class="p">]</span>
62 <p>Now discard the quoted <code class="docutils literal notranslate"><span class="pre">a</span></code> with <code class="docutils literal notranslate"><span class="pre">rest</span></code> then <code class="docutils literal notranslate"><span class="pre">cons</span></code> <code class="docutils literal notranslate"><span class="pre">b</span></code>:</p>
63 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">b</span> <span class="p">[</span><span class="n">a</span> <span class="n">B</span><span class="p">]</span> <span class="n">rest</span> <span class="n">cons</span>
64 <span class="n">b</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="n">cons</span>
65 <span class="p">[</span><span class="n">b</span> <span class="n">B</span><span class="p">]</span>
68 <p>Altogether, this is the definition of <code class="docutils literal notranslate"><span class="pre">B</span></code>:</p>
69 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">B</span> <span class="o">==</span> <span class="n">swap</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span>
72 <p>We can make a generator for the Natural numbers (0, 1, 2, …) by using
73 <code class="docutils literal notranslate"><span class="pre">0</span></code> for <code class="docutils literal notranslate"><span class="pre">a</span></code> and <code class="docutils literal notranslate"><span class="pre">[dup</span> <span class="pre">++]</span></code> for <code class="docutils literal notranslate"><span class="pre">[C]</span></code>:</p>
74 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span><span class="p">]</span>
78 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">V</span><span class="p">(</span><span class="s1">'[0 swap [dup ++] dip rest cons] x'</span><span class="p">)</span>
81 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span> <span class="o">.</span> <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span><span class="p">]</span> <span class="n">x</span>
82 <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span><span class="p">]</span> <span class="o">.</span> <span class="n">x</span>
83 <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span><span class="p">]</span> <span class="o">.</span> <span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span>
84 <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span><span class="p">]</span> <span class="mi">0</span> <span class="o">.</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span>
85 <span class="mi">0</span> <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span><span class="p">]</span> <span class="o">.</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span>
86 <span class="mi">0</span> <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span><span class="p">]</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="o">.</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span>
87 <span class="mi">0</span> <span class="o">.</span> <span class="n">dup</span> <span class="o">++</span> <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span><span class="p">]</span> <span class="n">rest</span> <span class="n">cons</span>
88 <span class="mi">0</span> <span class="mi">0</span> <span class="o">.</span> <span class="o">++</span> <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span><span class="p">]</span> <span class="n">rest</span> <span class="n">cons</span>
89 <span class="mi">0</span> <span class="mi">1</span> <span class="o">.</span> <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span><span class="p">]</span> <span class="n">rest</span> <span class="n">cons</span>
90 <span class="mi">0</span> <span class="mi">1</span> <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span><span class="p">]</span> <span class="o">.</span> <span class="n">rest</span> <span class="n">cons</span>
91 <span class="mi">0</span> <span class="mi">1</span> <span class="p">[</span><span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span><span class="p">]</span> <span class="o">.</span> <span class="n">cons</span>
92 <span class="mi">0</span> <span class="p">[</span><span class="mi">1</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span><span class="p">]</span> <span class="o">.</span>
95 <p>After one application of <code class="docutils literal notranslate"><span class="pre">x</span></code> the quoted program contains <code class="docutils literal notranslate"><span class="pre">1</span></code> and
96 <code class="docutils literal notranslate"><span class="pre">0</span></code> is below it on the stack.</p>
97 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[0 swap [dup ++] dip rest cons] x x x x x pop'</span><span class="p">)</span>
100 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">0</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">4</span>
103 <div class="section" id="direco">
104 <h2><code class="docutils literal notranslate"><span class="pre">direco</span></code><a class="headerlink" href="#direco" title="Permalink to this headline">¶</a></h2>
105 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'direco == dip rest cons'</span><span class="p">)</span>
108 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">V</span><span class="p">(</span><span class="s1">'[0 swap [dup ++] direco] x'</span><span class="p">)</span>
111 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span> <span class="o">.</span> <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span> <span class="n">x</span>
112 <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span> <span class="o">.</span> <span class="n">x</span>
113 <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span> <span class="o">.</span> <span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span>
114 <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span> <span class="mi">0</span> <span class="o">.</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span>
115 <span class="mi">0</span> <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span> <span class="o">.</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span>
116 <span class="mi">0</span> <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="o">.</span> <span class="n">direco</span>
117 <span class="mi">0</span> <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="o">.</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span>
118 <span class="mi">0</span> <span class="o">.</span> <span class="n">dup</span> <span class="o">++</span> <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span> <span class="n">rest</span> <span class="n">cons</span>
119 <span class="mi">0</span> <span class="mi">0</span> <span class="o">.</span> <span class="o">++</span> <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span> <span class="n">rest</span> <span class="n">cons</span>
120 <span class="mi">0</span> <span class="mi">1</span> <span class="o">.</span> <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span> <span class="n">rest</span> <span class="n">cons</span>
121 <span class="mi">0</span> <span class="mi">1</span> <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span> <span class="o">.</span> <span class="n">rest</span> <span class="n">cons</span>
122 <span class="mi">0</span> <span class="mi">1</span> <span class="p">[</span><span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span> <span class="o">.</span> <span class="n">cons</span>
123 <span class="mi">0</span> <span class="p">[</span><span class="mi">1</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span> <span class="o">.</span>
127 <div class="section" id="making-generators">
128 <h2>Making Generators<a class="headerlink" href="#making-generators" title="Permalink to this headline">¶</a></h2>
129 <p>We want to define a function that accepts <code class="docutils literal notranslate"><span class="pre">a</span></code> and <code class="docutils literal notranslate"><span class="pre">[C]</span></code> and builds
130 our quoted program:</p>
131 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span> <span class="n">a</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="n">G</span>
132 <span class="o">-------------------------</span>
133 <span class="p">[</span><span class="n">a</span> <span class="n">swap</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span>
136 <p>Working in reverse:</p>
137 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">a</span> <span class="n">swap</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span> <span class="n">cons</span>
138 <span class="n">a</span> <span class="p">[</span><span class="n">swap</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span> <span class="n">concat</span>
139 <span class="n">a</span> <span class="p">[</span><span class="n">swap</span><span class="p">]</span> <span class="p">[[</span><span class="n">C</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span> <span class="n">swap</span>
140 <span class="n">a</span> <span class="p">[[</span><span class="n">C</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span> <span class="p">[</span><span class="n">swap</span><span class="p">]</span>
141 <span class="n">a</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="p">[</span><span class="n">direco</span><span class="p">]</span> <span class="n">cons</span> <span class="p">[</span><span class="n">swap</span><span class="p">]</span>
144 <p>Reading from the bottom up:</p>
145 <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">direco</span><span class="p">]</span> <span class="n">cons</span> <span class="p">[</span><span class="n">swap</span><span class="p">]</span> <span class="n">swap</span> <span class="n">concat</span> <span class="n">cons</span>
146 <span class="n">G</span> <span class="o">==</span> <span class="p">[</span><span class="n">direco</span><span class="p">]</span> <span class="n">cons</span> <span class="p">[</span><span class="n">swap</span><span class="p">]</span> <span class="n">swoncat</span> <span class="n">cons</span>
149 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'G == [direco] cons [swap] swoncat cons'</span><span class="p">)</span>
152 <p>Let’s try it out:</p>
153 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'0 [dup ++] G'</span><span class="p">)</span>
156 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span>
159 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'0 [dup ++] G x x x pop'</span><span class="p">)</span>
162 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">0</span> <span class="mi">1</span> <span class="mi">2</span>
165 <div class="section" id="powers-of-2">
166 <h3>Powers of 2<a class="headerlink" href="#powers-of-2" title="Permalink to this headline">¶</a></h3>
167 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'1 [dup 1 <<] G x x x x x x x x x pop'</span><span class="p">)</span>
170 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">1</span> <span class="mi">2</span> <span class="mi">4</span> <span class="mi">8</span> <span class="mi">16</span> <span class="mi">32</span> <span class="mi">64</span> <span class="mi">128</span> <span class="mi">256</span>
174 <div class="section" id="x-times">
175 <h3><code class="docutils literal notranslate"><span class="pre">[x]</span> <span class="pre">times</span></code><a class="headerlink" href="#x-times" title="Permalink to this headline">¶</a></h3>
176 <p>If we have one of these quoted programs we can drive it using <code class="docutils literal notranslate"><span class="pre">times</span></code>
177 with the <code class="docutils literal notranslate"><span class="pre">x</span></code> combinator.</p>
178 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'23 [dup ++] G 5 [x] times'</span><span class="p">)</span>
181 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">23</span> <span class="mi">24</span> <span class="mi">25</span> <span class="mi">26</span> <span class="mi">27</span> <span class="p">[</span><span class="mi">28</span> <span class="n">swap</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span>
186 <div class="section" id="generating-multiples-of-three-and-five">
187 <h2>Generating Multiples of Three and Five<a class="headerlink" href="#generating-multiples-of-three-and-five" title="Permalink to this headline">¶</a></h2>
188 <p>Look at the treatment of the Project Euler Problem One in the
189 “Developing a Program” notebook and you’ll see that we might be
190 interested in generating an endless cycle of:</p>
191 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span>
194 <p>To do this we want to encode the numbers as pairs of bits in a single
196 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span>
197 <span class="mi">0</span><span class="n">b</span> <span class="mi">11</span> <span class="mi">10</span> <span class="mi">01</span> <span class="mi">11</span> <span class="mi">01</span> <span class="mi">10</span> <span class="mi">11</span> <span class="o">==</span> <span class="mi">14811</span>
200 <p>And pick them off by masking with 3 (binary 11) and then shifting the
201 int right two bits.</p>
202 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'PE1.1 == dup [3 &] dip 2 >>'</span><span class="p">)</span>
205 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">V</span><span class="p">(</span><span class="s1">'14811 PE1.1'</span><span class="p">)</span>
208 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span> <span class="o">.</span> <span class="mi">14811</span> <span class="n">PE1</span><span class="o">.</span><span class="mi">1</span>
209 <span class="mi">14811</span> <span class="o">.</span> <span class="n">PE1</span><span class="o">.</span><span class="mi">1</span>
210 <span class="mi">14811</span> <span class="o">.</span> <span class="n">dup</span> <span class="p">[</span><span class="mi">3</span> <span class="o">&</span><span class="p">]</span> <span class="n">dip</span> <span class="mi">2</span> <span class="o">>></span>
211 <span class="mi">14811</span> <span class="mi">14811</span> <span class="o">.</span> <span class="p">[</span><span class="mi">3</span> <span class="o">&</span><span class="p">]</span> <span class="n">dip</span> <span class="mi">2</span> <span class="o">>></span>
212 <span class="mi">14811</span> <span class="mi">14811</span> <span class="p">[</span><span class="mi">3</span> <span class="o">&</span><span class="p">]</span> <span class="o">.</span> <span class="n">dip</span> <span class="mi">2</span> <span class="o">>></span>
213 <span class="mi">14811</span> <span class="o">.</span> <span class="mi">3</span> <span class="o">&</span> <span class="mi">14811</span> <span class="mi">2</span> <span class="o">>></span>
214 <span class="mi">14811</span> <span class="mi">3</span> <span class="o">.</span> <span class="o">&</span> <span class="mi">14811</span> <span class="mi">2</span> <span class="o">>></span>
215 <span class="mi">3</span> <span class="o">.</span> <span class="mi">14811</span> <span class="mi">2</span> <span class="o">>></span>
216 <span class="mi">3</span> <span class="mi">14811</span> <span class="o">.</span> <span class="mi">2</span> <span class="o">>></span>
217 <span class="mi">3</span> <span class="mi">14811</span> <span class="mi">2</span> <span class="o">.</span> <span class="o">>></span>
218 <span class="mi">3</span> <span class="mi">3702</span> <span class="o">.</span>
221 <p>If we plug <code class="docutils literal notranslate"><span class="pre">14811</span></code> and <code class="docutils literal notranslate"><span class="pre">[PE1.1]</span></code> into our generator form…</p>
222 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'14811 [PE1.1] G'</span><span class="p">)</span>
225 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">14811</span> <span class="n">swap</span> <span class="p">[</span><span class="n">PE1</span><span class="o">.</span><span class="mi">1</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span>
228 <p>…we get a generator that works for seven cycles before it reaches zero:</p>
229 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[14811 swap [PE1.1] direco] 7 [x] times'</span><span class="p">)</span>
232 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">PE1</span><span class="o">.</span><span class="mi">1</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span>
235 <div class="section" id="reset-at-zero">
236 <h3>Reset at Zero<a class="headerlink" href="#reset-at-zero" title="Permalink to this headline">¶</a></h3>
237 <p>We need a function that checks if the int has reached zero and resets it
239 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'PE1.1.check == dup [pop 14811] [] branch'</span><span class="p">)</span>
242 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'14811 [PE1.1.check PE1.1] G'</span><span class="p">)</span>
245 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">14811</span> <span class="n">swap</span> <span class="p">[</span><span class="n">PE1</span><span class="o">.</span><span class="mf">1.</span><span class="n">check</span> <span class="n">PE1</span><span class="o">.</span><span class="mi">1</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span>
248 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[14811 swap [PE1.1.check PE1.1] direco] 21 [x] times'</span><span class="p">)</span>
251 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="p">[</span><span class="mi">0</span> <span class="n">swap</span> <span class="p">[</span><span class="n">PE1</span><span class="o">.</span><span class="mf">1.</span><span class="n">check</span> <span class="n">PE1</span><span class="o">.</span><span class="mi">1</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span>
254 <p>(It would be more efficient to reset the int every seven cycles but
255 that’s a little beyond the scope of this article. This solution does
256 extra work, but not much, and we’re not using it “in production” as they
259 <div class="section" id="run-466-times">
260 <h3>Run 466 times<a class="headerlink" href="#run-466-times" title="Permalink to this headline">¶</a></h3>
261 <p>In the PE1 problem we are asked to sum all the multiples of three and
262 five less than 1000. It’s worked out that we need to use all seven
263 numbers sixty-six times and then four more.</p>
264 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'7 66 * 4 +'</span><span class="p">)</span>
267 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">466</span>
270 <p>If we drive our generator 466 times and sum the stack we get 999.</p>
271 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[14811 swap [PE1.1.check PE1.1] direco] 466 [x] times'</span><span class="p">)</span>
274 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">3</span> <span class="p">[</span><span class="mi">57</span> <span class="n">swap</span> <span class="p">[</span><span class="n">PE1</span><span class="o">.</span><span class="mf">1.</span><span class="n">check</span> <span class="n">PE1</span><span class="o">.</span><span class="mi">1</span><span class="p">]</span> <span class="n">direco</span><span class="p">]</span>
277 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[14811 swap [PE1.1.check PE1.1] direco] 466 [x] times pop enstacken sum'</span><span class="p">)</span>
280 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">999</span>
285 <div class="section" id="project-euler-problem-one">
286 <h2>Project Euler Problem One<a class="headerlink" href="#project-euler-problem-one" title="Permalink to this headline">¶</a></h2>
287 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'PE1.2 == + dup [+] dip'</span><span class="p">)</span>
290 <p>Now we can add <code class="docutils literal notranslate"><span class="pre">PE1.2</span></code> to the quoted program given to <code class="docutils literal notranslate"><span class="pre">G</span></code>.</p>
291 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'0 0 0 [PE1.1.check PE1.1] G 466 [x [PE1.2] dip] times popop'</span><span class="p">)</span>
294 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">233168</span>
298 <div class="section" id="a-generator-for-the-fibonacci-sequence">
299 <h2>A generator for the Fibonacci Sequence.<a class="headerlink" href="#a-generator-for-the-fibonacci-sequence" title="Permalink to this headline">¶</a></h2>
301 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">b</span> <span class="n">a</span> <span class="n">F</span><span class="p">]</span> <span class="n">x</span>
302 <span class="p">[</span><span class="n">b</span> <span class="n">a</span> <span class="n">F</span><span class="p">]</span> <span class="n">b</span> <span class="n">a</span> <span class="n">F</span>
305 <p>The obvious first thing to do is just add <code class="docutils literal notranslate"><span class="pre">b</span></code> and <code class="docutils literal notranslate"><span class="pre">a</span></code>:</p>
306 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">b</span> <span class="n">a</span> <span class="n">F</span><span class="p">]</span> <span class="n">b</span> <span class="n">a</span> <span class="o">+</span>
307 <span class="p">[</span><span class="n">b</span> <span class="n">a</span> <span class="n">F</span><span class="p">]</span> <span class="n">b</span><span class="o">+</span><span class="n">a</span>
310 <p>From here we want to arrive at:</p>
311 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">b</span> <span class="p">[</span><span class="n">b</span><span class="o">+</span><span class="n">a</span> <span class="n">b</span> <span class="n">F</span><span class="p">]</span>
314 <p>Let’s start with <code class="docutils literal notranslate"><span class="pre">swons</span></code>:</p>
315 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">b</span> <span class="n">a</span> <span class="n">F</span><span class="p">]</span> <span class="n">b</span><span class="o">+</span><span class="n">a</span> <span class="n">swons</span>
316 <span class="p">[</span><span class="n">b</span><span class="o">+</span><span class="n">a</span> <span class="n">b</span> <span class="n">a</span> <span class="n">F</span><span class="p">]</span>
319 <p>Considering this quote as a stack:</p>
320 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">F</span> <span class="n">a</span> <span class="n">b</span> <span class="n">b</span><span class="o">+</span><span class="n">a</span>
323 <p>We want to get it to:</p>
324 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">F</span> <span class="n">b</span> <span class="n">b</span><span class="o">+</span><span class="n">a</span> <span class="n">b</span>
328 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">F</span> <span class="n">a</span> <span class="n">b</span> <span class="n">b</span><span class="o">+</span><span class="n">a</span> <span class="n">popdd</span> <span class="n">over</span>
329 <span class="n">F</span> <span class="n">b</span> <span class="n">b</span><span class="o">+</span><span class="n">a</span> <span class="n">b</span>
332 <p>And therefore:</p>
333 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">b</span><span class="o">+</span><span class="n">a</span> <span class="n">b</span> <span class="n">a</span> <span class="n">F</span><span class="p">]</span> <span class="p">[</span><span class="n">popdd</span> <span class="n">over</span><span class="p">]</span> <span class="n">infra</span>
334 <span class="p">[</span><span class="n">b</span> <span class="n">b</span><span class="o">+</span><span class="n">a</span> <span class="n">b</span> <span class="n">F</span><span class="p">]</span>
337 <p>But we can just use <code class="docutils literal notranslate"><span class="pre">cons</span></code> to carry <code class="docutils literal notranslate"><span class="pre">b+a</span></code> into the quote:</p>
338 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">b</span> <span class="n">a</span> <span class="n">F</span><span class="p">]</span> <span class="n">b</span><span class="o">+</span><span class="n">a</span> <span class="p">[</span><span class="n">popdd</span> <span class="n">over</span><span class="p">]</span> <span class="n">cons</span> <span class="n">infra</span>
339 <span class="p">[</span><span class="n">b</span> <span class="n">a</span> <span class="n">F</span><span class="p">]</span> <span class="p">[</span><span class="n">b</span><span class="o">+</span><span class="n">a</span> <span class="n">popdd</span> <span class="n">over</span><span class="p">]</span> <span class="n">infra</span>
340 <span class="p">[</span><span class="n">b</span> <span class="n">b</span><span class="o">+</span><span class="n">a</span> <span class="n">b</span> <span class="n">F</span><span class="p">]</span>
344 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">b</span> <span class="n">b</span><span class="o">+</span><span class="n">a</span> <span class="n">b</span> <span class="n">F</span><span class="p">]</span> <span class="n">uncons</span>
345 <span class="n">b</span> <span class="p">[</span><span class="n">b</span><span class="o">+</span><span class="n">a</span> <span class="n">b</span> <span class="n">F</span><span class="p">]</span>
348 <p>Putting it all together:</p>
349 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">F</span> <span class="o">==</span> <span class="o">+</span> <span class="p">[</span><span class="n">popdd</span> <span class="n">over</span><span class="p">]</span> <span class="n">cons</span> <span class="n">infra</span> <span class="n">uncons</span>
350 <span class="n">fib_gen</span> <span class="o">==</span> <span class="p">[</span><span class="mi">1</span> <span class="mi">1</span> <span class="n">F</span><span class="p">]</span>
353 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'fib == + [popdd over] cons infra uncons'</span><span class="p">)</span>
356 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'fib_gen == [1 1 fib]'</span><span class="p">)</span>
359 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'fib_gen 10 [x] times'</span><span class="p">)</span>
362 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">5</span> <span class="mi">8</span> <span class="mi">13</span> <span class="mi">21</span> <span class="mi">34</span> <span class="mi">55</span> <span class="mi">89</span> <span class="p">[</span><span class="mi">144</span> <span class="mi">89</span> <span class="n">fib</span><span class="p">]</span>
366 <div class="section" id="project-euler-problem-two">
367 <h2>Project Euler Problem Two<a class="headerlink" href="#project-euler-problem-two" title="Permalink to this headline">¶</a></h2>
369 <div>By considering the terms in the Fibonacci sequence whose values do
370 not exceed four million, find the sum of the even-valued terms.</div></blockquote>
371 <p>Now that we have a generator for the Fibonacci sequence, we need a
372 function that adds a term in the sequence to a sum if it is even, and
373 <code class="docutils literal notranslate"><span class="pre">pop</span></code>s it otherwise.</p>
374 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'PE2.1 == dup 2 % [+] [pop] branch'</span><span class="p">)</span>
377 <p>And a predicate function that detects when the terms in the series
378 “exceed four million”.</p>
379 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'>4M == 4000000 >'</span><span class="p">)</span>
382 <p>Now it’s straightforward to define <code class="docutils literal notranslate"><span class="pre">PE2</span></code> as a recursive function that
383 generates terms in the Fibonacci sequence until they exceed four million
384 and sums the even ones.</p>
385 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'PE2 == 0 fib_gen x [pop >4M] [popop] [[PE2.1] dip x] primrec'</span><span class="p">)</span>
388 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'PE2'</span><span class="p">)</span>
391 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">4613732</span>
394 <p>Here’s the collected program definitions:</p>
395 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">fib</span> <span class="o">==</span> <span class="o">+</span> <span class="n">swons</span> <span class="p">[</span><span class="n">popdd</span> <span class="n">over</span><span class="p">]</span> <span class="n">infra</span> <span class="n">uncons</span>
396 <span class="n">fib_gen</span> <span class="o">==</span> <span class="p">[</span><span class="mi">1</span> <span class="mi">1</span> <span class="n">fib</span><span class="p">]</span>
398 <span class="n">even</span> <span class="o">==</span> <span class="n">dup</span> <span class="mi">2</span> <span class="o">%</span>
399 <span class="o">></span><span class="mi">4</span><span class="n">M</span> <span class="o">==</span> <span class="mi">4000000</span> <span class="o">></span>
401 <span class="n">PE2</span><span class="o">.</span><span class="mi">1</span> <span class="o">==</span> <span class="n">even</span> <span class="p">[</span><span class="o">+</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span><span class="p">]</span> <span class="n">branch</span>
402 <span class="n">PE2</span> <span class="o">==</span> <span class="mi">0</span> <span class="n">fib_gen</span> <span class="n">x</span> <span class="p">[</span><span class="n">pop</span> <span class="o">></span><span class="mi">4</span><span class="n">M</span><span class="p">]</span> <span class="p">[</span><span class="n">popop</span><span class="p">]</span> <span class="p">[[</span><span class="n">PE2</span><span class="o">.</span><span class="mi">1</span><span class="p">]</span> <span class="n">dip</span> <span class="n">x</span><span class="p">]</span> <span class="n">primrec</span>
405 <div class="section" id="even-valued-fibonacci-terms">
406 <h3>Even-valued Fibonacci Terms<a class="headerlink" href="#even-valued-fibonacci-terms" title="Permalink to this headline">¶</a></h3>
407 <p>Using <code class="docutils literal notranslate"><span class="pre">o</span></code> for odd and <code class="docutils literal notranslate"><span class="pre">e</span></code> for even:</p>
408 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">o</span> <span class="o">+</span> <span class="n">o</span> <span class="o">=</span> <span class="n">e</span>
409 <span class="n">e</span> <span class="o">+</span> <span class="n">e</span> <span class="o">=</span> <span class="n">e</span>
410 <span class="n">o</span> <span class="o">+</span> <span class="n">e</span> <span class="o">=</span> <span class="n">o</span>
413 <p>So the Fibonacci sequence considered in terms of just parity would be:</p>
414 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">o</span> <span class="n">o</span> <span class="n">e</span> <span class="n">o</span> <span class="n">o</span> <span class="n">e</span> <span class="n">o</span> <span class="n">o</span> <span class="n">e</span> <span class="n">o</span> <span class="n">o</span> <span class="n">e</span> <span class="n">o</span> <span class="n">o</span> <span class="n">e</span> <span class="n">o</span> <span class="n">o</span> <span class="n">e</span>
415 <span class="mi">1</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">5</span> <span class="mi">8</span> <span class="o">.</span> <span class="o">.</span> <span class="o">.</span>
418 <p>Every third term is even.</p>
419 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[1 0 fib] x x x'</span><span class="p">)</span> <span class="c1"># To start the sequence with 1 1 2 3 instead of 1 2 3.</span>
422 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">1</span> <span class="mi">1</span> <span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">2</span> <span class="n">fib</span><span class="p">]</span>
425 <p>Drive the generator three times and <code class="docutils literal notranslate"><span class="pre">popop</span></code> the two odd terms.</p>
426 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[1 0 fib] x x x [popop] dipd'</span><span class="p">)</span>
429 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">2</span> <span class="n">fib</span><span class="p">]</span>
432 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'PE2.2 == x x x [popop] dipd'</span><span class="p">)</span>
435 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[1 0 fib] 10 [PE2.2] times'</span><span class="p">)</span>
438 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">2</span> <span class="mi">8</span> <span class="mi">34</span> <span class="mi">144</span> <span class="mi">610</span> <span class="mi">2584</span> <span class="mi">10946</span> <span class="mi">46368</span> <span class="mi">196418</span> <span class="mi">832040</span> <span class="p">[</span><span class="mi">1346269</span> <span class="mi">832040</span> <span class="n">fib</span><span class="p">]</span>
441 <p>Replace <code class="docutils literal notranslate"><span class="pre">x</span></code> with our new driver function <code class="docutils literal notranslate"><span class="pre">PE2.2</span></code> and start our
442 <code class="docutils literal notranslate"><span class="pre">fib</span></code> generator at <code class="docutils literal notranslate"><span class="pre">1</span> <span class="pre">0</span></code>.</p>
443 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'0 [1 0 fib] PE2.2 [pop >4M] [popop] [[PE2.1] dip PE2.2] primrec'</span><span class="p">)</span>
446 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">4613732</span>
451 <div class="section" id="how-to-compile-these">
452 <h2>How to compile these?<a class="headerlink" href="#how-to-compile-these" title="Permalink to this headline">¶</a></h2>
453 <p>You would probably start with a special version of <code class="docutils literal notranslate"><span class="pre">G</span></code>, and perhaps
454 modifications to the default <code class="docutils literal notranslate"><span class="pre">x</span></code>?</p>
456 <div class="section" id="an-interesting-variation">
457 <h2>An Interesting Variation<a class="headerlink" href="#an-interesting-variation" title="Permalink to this headline">¶</a></h2>
458 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'codireco == cons dip rest cons'</span><span class="p">)</span>
461 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">V</span><span class="p">(</span><span class="s1">'[0 [dup ++] codireco] x'</span><span class="p">)</span>
464 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span> <span class="o">.</span> <span class="p">[</span><span class="mi">0</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">codireco</span><span class="p">]</span> <span class="n">x</span>
465 <span class="p">[</span><span class="mi">0</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">codireco</span><span class="p">]</span> <span class="o">.</span> <span class="n">x</span>
466 <span class="p">[</span><span class="mi">0</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">codireco</span><span class="p">]</span> <span class="o">.</span> <span class="mi">0</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">codireco</span>
467 <span class="p">[</span><span class="mi">0</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">codireco</span><span class="p">]</span> <span class="mi">0</span> <span class="o">.</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">codireco</span>
468 <span class="p">[</span><span class="mi">0</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">codireco</span><span class="p">]</span> <span class="mi">0</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="o">.</span> <span class="n">codireco</span>
469 <span class="p">[</span><span class="mi">0</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">codireco</span><span class="p">]</span> <span class="mi">0</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="o">.</span> <span class="n">cons</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span>
470 <span class="p">[</span><span class="mi">0</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">codireco</span><span class="p">]</span> <span class="p">[</span><span class="mi">0</span> <span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="o">.</span> <span class="n">dip</span> <span class="n">rest</span> <span class="n">cons</span>
471 <span class="o">.</span> <span class="mi">0</span> <span class="n">dup</span> <span class="o">++</span> <span class="p">[</span><span class="mi">0</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">codireco</span><span class="p">]</span> <span class="n">rest</span> <span class="n">cons</span>
472 <span class="mi">0</span> <span class="o">.</span> <span class="n">dup</span> <span class="o">++</span> <span class="p">[</span><span class="mi">0</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">codireco</span><span class="p">]</span> <span class="n">rest</span> <span class="n">cons</span>
473 <span class="mi">0</span> <span class="mi">0</span> <span class="o">.</span> <span class="o">++</span> <span class="p">[</span><span class="mi">0</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">codireco</span><span class="p">]</span> <span class="n">rest</span> <span class="n">cons</span>
474 <span class="mi">0</span> <span class="mi">1</span> <span class="o">.</span> <span class="p">[</span><span class="mi">0</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">codireco</span><span class="p">]</span> <span class="n">rest</span> <span class="n">cons</span>
475 <span class="mi">0</span> <span class="mi">1</span> <span class="p">[</span><span class="mi">0</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">codireco</span><span class="p">]</span> <span class="o">.</span> <span class="n">rest</span> <span class="n">cons</span>
476 <span class="mi">0</span> <span class="mi">1</span> <span class="p">[[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">codireco</span><span class="p">]</span> <span class="o">.</span> <span class="n">cons</span>
477 <span class="mi">0</span> <span class="p">[</span><span class="mi">1</span> <span class="p">[</span><span class="n">dup</span> <span class="o">++</span><span class="p">]</span> <span class="n">codireco</span><span class="p">]</span> <span class="o">.</span>
480 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'G == [codireco] cons cons'</span><span class="p">)</span>
483 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'230 [dup ++] G 5 [x] times pop'</span><span class="p">)</span>
486 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">230</span> <span class="mi">231</span> <span class="mi">232</span> <span class="mi">233</span> <span class="mi">234</span>
496 <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
497 <div class="sphinxsidebarwrapper">
498 <h3><a href="../index.html">Table Of Contents</a></h3>
500 <li><a class="reference internal" href="#">Using <code class="docutils literal notranslate"><span class="pre">x</span></code> to Generate Values</a><ul>
501 <li><a class="reference internal" href="#direco"><code class="docutils literal notranslate"><span class="pre">direco</span></code></a></li>
502 <li><a class="reference internal" href="#making-generators">Making Generators</a><ul>
503 <li><a class="reference internal" href="#powers-of-2">Powers of 2</a></li>
504 <li><a class="reference internal" href="#x-times"><code class="docutils literal notranslate"><span class="pre">[x]</span> <span class="pre">times</span></code></a></li>
507 <li><a class="reference internal" href="#generating-multiples-of-three-and-five">Generating Multiples of Three and Five</a><ul>
508 <li><a class="reference internal" href="#reset-at-zero">Reset at Zero</a></li>
509 <li><a class="reference internal" href="#run-466-times">Run 466 times</a></li>
512 <li><a class="reference internal" href="#project-euler-problem-one">Project Euler Problem One</a></li>
513 <li><a class="reference internal" href="#a-generator-for-the-fibonacci-sequence">A generator for the Fibonacci Sequence.</a></li>
514 <li><a class="reference internal" href="#project-euler-problem-two">Project Euler Problem Two</a><ul>
515 <li><a class="reference internal" href="#even-valued-fibonacci-terms">Even-valued Fibonacci Terms</a></li>
518 <li><a class="reference internal" href="#how-to-compile-these">How to compile these?</a></li>
519 <li><a class="reference internal" href="#an-interesting-variation">An Interesting Variation</a></li>
523 <div class="relations">
524 <h3>Related Topics</h3>
526 <li><a href="../index.html">Documentation overview</a><ul>
527 <li><a href="index.html">Essays about Programming in Joy</a><ul>
528 <li>Previous: <a href="Treestep.html" title="previous chapter">Treating Trees II: <code class="docutils literal notranslate"><span class="pre">treestep</span></code></a></li>
529 <li>Next: <a href="Newton-Raphson.html" title="next chapter">Newton’s method</a></li>
534 <div role="note" aria-label="source link">
536 <ul class="this-page-menu">
537 <li><a href="../_sources/notebooks/Generator_Programs.rst.txt"
538 rel="nofollow">Show Source</a></li>
541 <div id="searchbox" style="display: none" role="search">
542 <h3>Quick search</h3>
543 <div class="searchformwrapper">
544 <form class="search" action="../search.html" method="get">
545 <input type="text" name="q" />
546 <input type="submit" value="Go" />
547 <input type="hidden" name="check_keywords" value="yes" />
548 <input type="hidden" name="area" value="default" />
552 <script type="text/javascript">$('#searchbox').show(0);</script>
555 <div class="clearer"></div>
557 <div class="footer" role="contentinfo">
558 <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">
559 <img alt="Creative Commons License" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png" />
562 <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>.
563 Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.7.3.