Under the Hood

The section sheds some light on the internal library structure and working principles.


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 value

A generating function that can produce a next value on each iteration. Usually returns a new state and iteration values (multireturn).

param – second value

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 ipairs case.

state – third value

A some transient state of an iterator that is changed after each iteration. For example, the array index in the ipairs case.

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.


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:

    -- 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

What does it mean for us?

  • An iterator can be used together with for .. in to generate a loop

  • An iterator is fully defined by the gen, param and state iterator triplet

  • The nil state marks the end of an iteration

  • An 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:

  • gen function always returns the same values for the same param and state values (idempotence property)

  • param and state values are not modified during the gen call and a new state object 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.








Proved by Turing