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

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

1

http://en.wikipedia.org/wiki/Turtles_all_the_way_down

2

http://www.lua.org/manual/5.2/manual.html#3.3.5

3

http://en.wikipedia.org/wiki/Pure_function

4

Proved by Turing

5

http://en.wikipedia.org/wiki/Tracing_just-in-time_compilation

6

http://lambda-the-ultimate.org/node/3851#comment-57679

7

http://wiki.luajit.org/Optimizations