Lua stacks in Lua

Preamble

In case you didn’t know, Lua (http://lua.org) is a very simplistic open source scripting language. Its simplicity is also a reason for its incredible flexibility and hence a perfect candidate for embedding in anything ranging from tiny (like http://www.nodemcu.com/ microcontrollers) to huge desktop applications like Adobe Lightroom.

However the base concept of Lua is both curse and blessing at the same time and it’s imperative to understand how it works to use this language: stacks.

Disclaimer: What I’m telling you here might not be entirely accurate in terms of the real implementation but it should help understanding what’s going on behind the scenes.

The concept of a stack

In essence a stack is nothing more than information piled on top of each other. Each piece of information has a position called the index, its usually counted from the bottom of the of the stack, however the top of the stack is much more interesting (more about this in a little bit) so Lua supports the concept of a negative index to also count from the top.

The three main operations one can do on a stack are called:

• push: Put a new piece of information on the stack
• pop: Remove pieces of information from the top of the stack
• peek: Look at information on the stack without modifying it

Note: Push and pop officially exist in lua lingo while peek does not but of course is available through various functions. However it is important to understand which function applies which of base operations to the stack to keep everything sane.

In Lua everything is a stack

Expect for a few integral types really everything in Lua is expressed as a stack and maintained as a stack: You declare a variable – it goes on a stack, you append something to a list – it goes on a stack, you call a function – the arguments go on a stack …

Most of the stackiness is luckily hidden when just looking at the Lua scripting language itself, however once you’d like to use it with some other language, you’d better be stack-proficient or you’ll drown.

A simple table example

Let’s try a very basic example and see where stacks might be involved:

a = {"one", "two", "three"}
for i, v in ipairs (a) do
        print (i, v)
end

So all starts with an array or table which is declared by the {"one", "two", "three"}. What this does is:

• Creates a new table type (i.e. a stack of type table) on the current stack
• Pushes a 1 on the stack, for the index of the first string “one”
• Pushes the string “one” onto the stack
• Resets the stack pointer to the table type
• Pushes a 2 on the stack, for the index of the second string “two”
• Pushes the string “two” onto the stack
• Resets the stack pointer to the table type
• Pushes a 3 on the stack, for the index of the third string “three”
• Pushes the string “three” onto the stack
• Resets the stack pointer to the table type

The next part is the a = ..., this one retrieves the table representing the global symbol table, and either replaces the value of the entry with the key “a” or inserts a new key “a” and sets the value to the value on top of the stack – our just generated table.

If we did not assign the new table anywhere the garbage collector would detect that and free the used memory.

ipairs (a) is a function call which is implemented in Lua as follows:

• The value of ipairs is looked up in the symbol table. in this case it should be found in the global symbols table and have the value of a functions which gets pushed on the stack
• Every parameter to the function is resolved (i.e. either looked up or turned into a Lua value) and pushed onto the stack as well, in this case it’ll find the “a” in the global symbols table and push the value of the table we’ve created just before on the stack
• Then it’ll call the function pushed on the stack which will pop the amount of parameters specified in the function signature from the stack and bind the values to the symbols
• The called function will compute a result and push any number of return values back on the stack

So now we have two values on the stack which will be consumed by the for loop, for i, v in ipairs (a) do will call the ipairs function to receive an iterator function and an initialiser argument which the for will be calling as long as the iterator function does not push nil on the stack. If no nil is pushed on the stack the i, v will pop the two values on the stack and assign their values to the symbols “i” and “v”.

The remainder of operation should be clear now, print (i, v) looks up the “print” symbol from the symbol tables and pushes its value on the stack, then “i” and “v” are looked up and their values pushed onto the stack. The function will be called with the function itself popped from the stack and whatever it might return will be ignored by the caller.

In closing

As you can see, even in the simple context we examined earlier and taking many shortcuts, a stack is a fundamental concept in Lua and everything directly tied to the manipulation of stacks. Where other imperative programming languages utilize a (typically size constraint) stack only for limited operations like function calling and temporary variable storage, stacks in Lua are only limited to the available amount of memory and nothing would be possible without them.

More about Lua and stacks to follow soon, then we’ll also see why knowledge about stacks are essential when leaving the safe home of the Lua interpreter.