Under the Hood¶
The section sheds some light on the internal library structure and working principles.
Iterators¶
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! 1.
The simplest iterators are (surprise!) the pairs() and ipairs()
Lua functions. Have you ever tried calling, say, the ipairs() function
without using it inside a for loop? Try to do that on any Lua
implementation:
> =ipairs({'a', 'b', 'c'})
function: builtin#6 table: 0x40f80e38 0
The function returned three strange values which look useless without a for
loop. We call these values an iterator triplet.
Let’s see what each value is used for:
gen– first valueA generating function that can produce a next value on each iteration. Usually returns a new
stateand iteration values (multireturn).param– second valueA 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
ipairscase.state– third valueA some transient state of an iterator that is changed after each iteration. For example, the array index in the
ipairscase.
Try calling the gen function manually:
> gen, param, state = ipairs({'a', 'b', 'c'}) > =gen(param, state) 1 a
The gen function returned a new state 1 and the next iteration
value a. The second call to gen with the new state will return the next
state and the next iteration value. When the iterator gets to the end
the nil value is returned instead of the next state.
Please do not panic! You do not have to use these values directly.
It is just a nice trick to get for .. in loops working in Lua.
Iterations¶
What happens when you type the following code into a Lua console:
for _it, x in ipairs({'a', 'b', 'c'}) do print(x) end
According to Lua reference manual 2 the code above is equivalent to:
do
-- Initialize the iterator
local gen, param, state = ipairs({'a', 'b', 'c'})
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
What does it mean for us?
An iterator can be used together with
for .. into generate a loopAn iterator is fully defined by the
gen,paramandstateiterator tripletThe
nilstate marks the end of an iterationAn iterator can return an arbitrary number of values (multireturn)
It is possible to make some wrapping functions to take an iterator and return a new modified iterator
The library provides a set of iterators that can be used like pairs
and ipairs.
Iterator Types¶
Pure functional iterators¶
Iterators can be either purely functional or have some side effects and return different values for the same initial conditions 3. An iterator is purely functional if it meets the following criteria:
genfunction always returns the same values for the sameparamandstatevalues (idempotence property)paramandstatevalues are not modified during thegencall and a newstateobject is returned instead (referential transparency property).
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.
Finite iterators¶
Iterators can be finite (sooner or later end up) or infinite (never end). Since there is no way to determine automatically if an iterator is finite or not 4 the library function can not automatically resolve infinite loops. It is your obligation not to pass infinite iterators to reducing functions.
Tracing JIT¶
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.
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 trace. 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 5.
Why is tracing JIT important for us? The LuaJIT tracing compiler can detect tail-, up- and down-recursion 6, unroll compositions of functions and inline high-order functions 7. All of these concepts make the foundation for functional programming.