luafun.github.io/under_the_hood.html at master · luafun/luafun.github.io · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223

<!DOCTYPE html>

<html lang="en">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />

    <title>Under the Hood &#8212; Lua Functional 0.1.3 documentation</title>
    <link rel="stylesheet" type="text/css" href="_static/pygments.css" />
    <link rel="stylesheet" type="text/css" href="_static/haiku.css" />
    <script data-url_root="./" id="documentation_options" src="_static/documentation_options.js"></script>
    <script src="_static/jquery.js"></script>
    <script src="_static/underscore.js"></script>
    <script src="_static/doctools.js"></script>
    <link rel="author" title="About these documents" href="about.html" />
    <link rel="index" title="Index" href="genindex.html" />
    <link rel="search" title="Search" href="search.html" />
    <link rel="next" title="About" href="about.html" />
    <link rel="prev" title="Operators" href="operators.html" />
  </head><body>
      <div class="header" role="banner"><img class="rightlogo" src="_static/logo.png" alt="Logo"/><h1 class="heading"><a href="index.html">
          <span>Lua Functional 0.1.3 documentation</span></a></h1>
        <h2 class="heading"><span>Under the Hood</span></h2>
      </div>
      <div class="topnav" role="navigation" aria-label="top navigation">

        <p>
        «&#160;&#160;<a href="operators.html">Operators</a>
        &#160;&#160;::&#160;&#160;
        <a class="uplink" href="index.html">Contents</a>
        &#160;&#160;::&#160;&#160;
        <a href="about.html">About</a>&#160;&#160;»
        </p>

      </div>
      <div class="content" role="main">


  <section id="under-the-hood">
<h1>Under the Hood<a class="headerlink" href="#under-the-hood" title="Permalink to this headline">¶</a></h1>
<p>The section sheds some light on the internal library structure and working
principles.</p>
<section id="iterators">
<h2>Iterators<a class="headerlink" href="#iterators" title="Permalink to this headline">¶</a></h2>
<p>Another basic primitive of the library (after functions) is the iterator. Most functions
take an iterator and return a new iterator or several ones. Iterators all the way down!
<a class="footnote-reference brackets" href="#id8" id="id1">1</a>.</p>
<p>The simplest iterators are (surprise!) the <code class="xref py py-func docutils literal notranslate"><span class="pre">pairs()</span></code> and <code class="xref py py-func docutils literal notranslate"><span class="pre">ipairs()</span></code>
Lua functions. Have you ever tried calling, say, the <code class="xref py py-func docutils literal notranslate"><span class="pre">ipairs()</span></code> function
without using it inside a <code class="docutils literal notranslate"><span class="pre">for</span></code> loop? Try to do that on any Lua
implementation:</p>
<div class="highlight-bash notranslate" id="iterator-triplet"><div class="highlight"><pre><span></span>&gt;<span class="w"> </span><span class="o">=</span>ipairs<span class="o">({</span><span class="s1">&#39;a&#39;</span>,<span class="w"> </span><span class="s1">&#39;b&#39;</span>,<span class="w"> </span><span class="s1">&#39;c&#39;</span><span class="o">})</span>
<span class="k">function</span>:<span class="w"> </span>builtin#6<span class="w">     </span>table:<span class="w"> </span>0x40f80e38<span class="w">       </span><span class="m">0</span>
</pre></div>
</div>
<p>The function returned three strange values which look useless without a <code class="docutils literal notranslate"><span class="pre">for</span></code>
loop. We call these values an <strong>iterator triplet</strong>.
Let’s see what each value is used for:</p>
<dl class="simple">
<dt><code class="docutils literal notranslate"><span class="pre">gen</span></code> – first value</dt><dd><p>A generating function that can produce a next value on each iteration.
Usually returns a new <code class="docutils literal notranslate"><span class="pre">state</span></code> and iteration values (multireturn).</p>
</dd>
<dt><code class="docutils literal notranslate"><span class="pre">param</span></code> – second value</dt><dd><p>A permanent (constant) parameter of the generating function. It is used to create
a specific instance of the generating function. For example, the table itself
in the <code class="docutils literal notranslate"><span class="pre">ipairs</span></code> case.</p>
</dd>
<dt><code class="docutils literal notranslate"><span class="pre">state</span></code> – third value</dt><dd><p>A some transient state of an iterator that is changed after each iteration.
For example, the array index in the <code class="docutils literal notranslate"><span class="pre">ipairs</span></code> case.</p>
</dd>
</dl>
<p>Try calling the <code class="docutils literal notranslate"><span class="pre">gen</span></code> function manually:</p>
<blockquote>
<div><div class="highlight-lua notranslate"><div class="highlight"><pre><span></span><span class="o">&gt;</span> <span class="n">gen</span><span class="p">,</span> <span class="n">param</span><span class="p">,</span> <span class="n">state</span> <span class="o">=</span> <span class="nb">ipairs</span><span class="p">({</span><span class="s1">&#39;a&#39;</span><span class="p">,</span> <span class="s1">&#39;b&#39;</span><span class="p">,</span> <span class="s1">&#39;c&#39;</span><span class="p">})</span>
<span class="o">&gt;</span> <span class="o">=</span><span class="n">gen</span><span class="p">(</span><span class="n">param</span><span class="p">,</span> <span class="n">state</span><span class="p">)</span>
<span class="mi">1</span>       <span class="n">a</span>
</pre></div>
</div>
</div></blockquote>
<p>The <code class="docutils literal notranslate"><span class="pre">gen</span></code> function returned a new state <code class="docutils literal notranslate"><span class="pre">1</span></code> and the next iteration
value <code class="docutils literal notranslate"><span class="pre">a</span></code>. The second call to <code class="docutils literal notranslate"><span class="pre">gen</span></code> with the new state will return the next
state and the next iteration value. When the iterator gets to the end
the <code class="docutils literal notranslate"><span class="pre">nil</span></code> value is returned instead of the next state.</p>
<p><strong>Please do not panic!</strong> You do not have to use these values directly.
It is just a nice trick to get <code class="docutils literal notranslate"><span class="pre">for</span> <span class="pre">..</span> <span class="pre">in</span></code> loops working in Lua.</p>
</section>
<section id="iterations">
<h2>Iterations<a class="headerlink" href="#iterations" title="Permalink to this headline">¶</a></h2>
<p>What happens when you type the following code into a Lua console:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">for</span> <span class="n">_it</span><span class="p">,</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">ipairs</span><span class="p">({</span><span class="s1">&#39;a&#39;</span><span class="p">,</span> <span class="s1">&#39;b&#39;</span><span class="p">,</span> <span class="s1">&#39;c&#39;</span><span class="p">})</span> <span class="n">do</span> <span class="nb">print</span><span class="p">(</span><span class="n">x</span><span class="p">)</span> <span class="n">end</span>
</pre></div>
</div>
<p>According to Lua reference manual <a class="footnote-reference brackets" href="#lua-for" id="id2">2</a> the code above is equivalent to:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>do
    -- Initialize the iterator
    local gen, param, state = ipairs({&#39;a&#39;, &#39;b&#39;, &#39;c&#39;})
    while true do
        -- Next iteration
        local state, var_1, ···, var_n = gen(param, state)
        if state == nil then break end
        -- Assign values to our variables
        _it = state
        x = var_1
        -- Execute the code block
        print(x)
    end
end
</pre></div>
</div>
<p>What does it mean for us?</p>
<ul class="simple">
<li><p>An iterator can be used together with <code class="docutils literal notranslate"><span class="pre">for</span> <span class="pre">..</span> <span class="pre">in</span></code> to generate a loop</p></li>
<li><p>An iterator is fully defined by the <code class="docutils literal notranslate"><span class="pre">gen</span></code>, <code class="docutils literal notranslate"><span class="pre">param</span></code> and <code class="docutils literal notranslate"><span class="pre">state</span></code> iterator
triplet</p></li>
<li><p>The <code class="docutils literal notranslate"><span class="pre">nil</span></code> state marks the end of an iteration</p></li>
<li><p>An iterator can return an arbitrary number of values (multireturn)</p></li>
<li><p>It is possible to make some wrapping functions to take an iterator and
return a new modified iterator</p></li>
</ul>
<p><strong>The library provides a set of iterators</strong> that can be used like <code class="docutils literal notranslate"><span class="pre">pairs</span></code>
and <code class="docutils literal notranslate"><span class="pre">ipairs</span></code>.</p>
</section>
<section id="iterator-types">
<h2>Iterator Types<a class="headerlink" href="#iterator-types" title="Permalink to this headline">¶</a></h2>
<section id="pure-functional-iterators">
<h3>Pure functional iterators<a class="headerlink" href="#pure-functional-iterators" title="Permalink to this headline">¶</a></h3>
<p>Iterators can be either purely functional or have some side effects and return
different values for the same initial conditions <a class="footnote-reference brackets" href="#pure-function" id="id3">3</a>. An <strong>iterator is
purely functional</strong> if it meets the following criteria:</p>
<ul class="simple">
<li><p><code class="docutils literal notranslate"><span class="pre">gen</span></code> function always returns the same values for the same <code class="docutils literal notranslate"><span class="pre">param</span></code> and
<code class="docutils literal notranslate"><span class="pre">state</span></code> values (idempotence property)</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">param</span></code> and <code class="docutils literal notranslate"><span class="pre">state</span></code> values are not modified during the <code class="docutils literal notranslate"><span class="pre">gen</span></code> call and
a new <code class="docutils literal notranslate"><span class="pre">state</span></code> object is returned instead (referential transparency
property).</p></li>
</ul>
<p>Pure functional iterators are very important for us. Pure functional iterator
can be safety cloned or reapplied without creating side effects. Many library
function use these properties.</p>
</section>
<section id="finite-iterators">
<h3>Finite iterators<a class="headerlink" href="#finite-iterators" title="Permalink to this headline">¶</a></h3>
<p>Iterators can be <strong>finite</strong> (sooner or later end up) or <strong>infinite</strong>
(never end).
Since there is no way to determine automatically if an iterator is finite or
not <a class="footnote-reference brackets" href="#turing" id="id4">4</a> the library function can not automatically resolve infinite
loops. It is your obligation not to pass infinite iterators to reducing
functions.</p>
</section>
</section>
<section id="tracing-jit">
<h2>Tracing JIT<a class="headerlink" href="#tracing-jit" title="Permalink to this headline">¶</a></h2>
<p>Tracing just-in-time compilation is a technique used by virtual machines to
optimize the execution of a program at runtime. This is done by recording a
linear sequence of frequently executed operations, compiling them to native
machine code and executing them.</p>
<p>First profiling information for loops is collected. After a hot loop has been
identified, a special tracing mode is entered which records all executed
operations of that loop. This sequence of operations is called a <strong>trace</strong>.
The trace is then optimized and compiled to machine code. When this
loop is executed again the compiled trace is called instead of the program
counterpart <a class="footnote-reference brackets" href="#id9" id="id5">5</a>.</p>
<p>Why is tracing JIT important for us? The LuaJIT tracing compiler can detect
tail-, up- and down-recursion <a class="footnote-reference brackets" href="#luajit-recursion" id="id6">6</a>, unroll compositions of
functions and inline high-order functions <a class="footnote-reference brackets" href="#luajit-optimizations" id="id7">7</a>.
All of these concepts make the foundation for functional programming.</p>
<dl class="footnote brackets">
<dt class="label" id="id8"><span class="brackets"><a class="fn-backref" href="#id1">1</a></span></dt>
<dd><p><a class="reference external" href="http://en.wikipedia.org/wiki/Turtles_all_the_way_down">http://en.wikipedia.org/wiki/Turtles_all_the_way_down</a></p>
</dd>
<dt class="label" id="lua-for"><span class="brackets"><a class="fn-backref" href="#id2">2</a></span></dt>
<dd><p><a class="reference external" href="http://www.lua.org/manual/5.2/manual.html#3.3.5">http://www.lua.org/manual/5.2/manual.html#3.3.5</a></p>
</dd>
<dt class="label" id="pure-function"><span class="brackets"><a class="fn-backref" href="#id3">3</a></span></dt>
<dd><p><a class="reference external" href="http://en.wikipedia.org/wiki/Pure_function">http://en.wikipedia.org/wiki/Pure_function</a></p>
</dd>
<dt class="label" id="turing"><span class="brackets"><a class="fn-backref" href="#id4">4</a></span></dt>
<dd><p><a class="reference external" href="http://en.wikipedia.org/wiki/Halting_problem">Proved by Turing</a></p>
</dd>
<dt class="label" id="id9"><span class="brackets"><a class="fn-backref" href="#id5">5</a></span></dt>
<dd><p><a class="reference external" href="http://en.wikipedia.org/wiki/Tracing_just-in-time_compilation">http://en.wikipedia.org/wiki/Tracing_just-in-time_compilation</a></p>
</dd>
<dt class="label" id="luajit-recursion"><span class="brackets"><a class="fn-backref" href="#id6">6</a></span></dt>
<dd><p><a class="reference external" href="http://lambda-the-ultimate.org/node/3851#comment-57679">http://lambda-the-ultimate.org/node/3851#comment-57679</a></p>
</dd>
<dt class="label" id="luajit-optimizations"><span class="brackets"><a class="fn-backref" href="#id7">7</a></span></dt>
<dd><p><a class="reference external" href="http://wiki.luajit.org/Optimizations">http://wiki.luajit.org/Optimizations</a></p>
</dd>
</dl>
</section>
</section>


      </div>
      <div class="bottomnav" role="navigation" aria-label="bottom navigation">

        <p>
        «&#160;&#160;<a href="operators.html">Operators</a>
        &#160;&#160;::&#160;&#160;
        <a class="uplink" href="index.html">Contents</a>
        &#160;&#160;::&#160;&#160;
        <a href="about.html">About</a>&#160;&#160;»
        </p>

      </div>


    <div class="footer" role="contentinfo">
        &#169; Copyright 2013-2021, Roman Tsisyk.
      Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 4.4.0.
    </div>
    <script type="text/javascript">
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','https://www.google-analytics.com/analytics.js','ga');

ga('create', 'UA-45899190-2', 'auto');
ga('send', 'pageview');
    </script>

  </body>
</html>