It is customary, in Lua, to register any new C type into the registry, using a type name as the index and the metatable as the value. As with any other registry index, we must choose a type name with care, to avoid clashes. . Any function declared here could be written as an application function./ #define lauxlibc #define LUALIB #include 'lua.h' #include 'lauxlib.h' #define FREELISTREF 0 /. free list of references./ /. convert a stack index to positive./ #define absindex (L, i) ((i) 0 (i) LUAREGISTRYINDEX? Lua is a script language frequently used in game development. Typically the game engine is written in C/C and the game itself is defined in Lua. Meaning setting up behaviour, placement of objects like powerups, doors, enemies etc is done in Lua. That way the game can be quickly tweaked without having to go through a time consuming re-compile.

In this article, I would like to share a C++/Lua programming technique that I enjoyed using in a past project. This technique allows you to define functions in a data-driven way using Lua scripts. These functions are converted into a domain-specific “bytecode” at initialization time, which can then be evaluated in C++ without using a Lua runtime. By evaluating functions as bytecode in C++, we can simplify and optimize Lua use by minimizing garbage collection and inter-language function calls.

This article is split into two main parts. In the first part, I describe the motivating use case that inspired me to use this technique. In the second part, I describe the details of how the technique was implemented for the aforementioned use case.

Several code samples are raised from a project on Github, which can be seen in full here: https://github.com/nlguillemot/robdd

The project where I used this technique was an implementation of the Binary Decision Diagram data structure. The input to the program is a Boolean function, and the output of the program is the number of possible solutions that make the Boolean function true. More specifically, I implemented the Multicore Binary Decision Diagram as described by Yuxiong He.

For this project, I wanted to specify the inputted Boolean functions through scripts, mainly because I thought it would be cute and fun. As a final result, I was able to specify Boolean functions as follows:

This script is broken down into four parts: The options, the inputs, the Boolean function itself, and its outputs.

The script begins by setting some options. The “title” is the name of the function, and “display = true” will display the binary function as a dot graph. Following these options, some inputs to the Boolean function are declared. Inputs are declared through the “index” table, and those inputs are assigned to variables with shorter names for convenience. After declaring the inputs, they are used in some Boolean operations. Here, the “+” operator means logical OR, and the “*” operator means logical AND. Finally, the results of these Boolean operations are marked as outputs, by putting them in the “output” table.

C Lua Metatable 2

The result of running the script is the following diagram, which shows all ways in which the outputs of the Boolean functions can either evaluate to false (0) or true (1). By tracing a path from the top of the diagram to the bottom, while following dotted lines when a variable is false, and following solid lines when a variable is true, you can see the result of the Boolean function for a specific assignment of values to its inputs.

By specifying the Boolean function as a Lua script, I was able to programmatically express various more complicated Boolean functions. For example, an n-bit ripple carry adder and the n-queens puzzle were programmatically specified with generic functions in terms of “n”. I was also able to make a general Lua function to generate Boolean functions for 3-colorings or 4-colorings of graphs, and I was able to conveniently import and reuse this function from other scripts to define Boolean functions for graph-colorings of the Petersen graph, the states of the United States, and the prefectures of Japan. Since I used Lua as a configuration language, I was able to easily create all these complicated Boolean functions, which wouldn’t be so conveniently possible if I was using JSON or XML as the input of my program.

If you’re curious about more details of my Binary Decision Diagram project, please consult this report pdf.

At a high-level, the implementation is split into two parts:

Running the Lua script to generate bytecode.
Executing the bytecode.

These two steps are described separately in this section.

Bytecode Generation

The generated bytecode has two main purposes: declaring new variables, and describing Boolean operations with them. Each instruction of this bytecode has an “opcode” that defines what type of instruction it is, and stores references to its inputs and outputs. The bytecode is built by appending an “instruction” to a std::vector every time an operation happens in the Lua script.

The following code sample shows the structure of the instructions used in the bytecode, and the std::vector that stores the instruction bytecode:

The inputs and outputs to each instruction are specified by Abstract Syntax Tree IDs (“AST IDs”). Initially, the IDs “0” and “1” are specially assigned to “false” and “true”, respectively. From there, monotonically increasing AST IDs are assigned to newly created variables, and to results of Boolean operations. Since a new AST ID is created for every intermediate result, the bytecode effectively represents a program where the result of every operation is immutable, even if the Lua code that created it might have syntactically reused a variable name.

The monotonically increasing AST ID numbers (and the specially reserved values for “false” and “true”) are represented by the following code:

Beside the AST IDs, a different type of monotonically increasing ID is used to uniquely identify input variables to the Boolean function specified by the script. These variable ID numbers are used to keep track of the inputs of the function (such as “input.a” and “input.b”), and they are used to record associations between AST IDs and input variables.

The monotonically increasing variable ID counter (starting at 0) is simply declared as follows:

The code that connects the Lua script to these C++ data structures is implemented mostly through Lua metatables. In particular, the metatable for the “input” table, and the metatable for each “ast” node of the computation. The implementation of these metatables will now be described.

The Input Table

The “input” table has two defined metamethods. The first one is “__newindex”, which is simply defined to forbid assignment to inputs. Obviously, inputs should only be read, not written. It is defined as follows:

The second metamethod, “__index”, is much more interesting:

When the “__index” metamethod is called, a new input variable is created. Each variable created with this method is given a monotonically increasing variable ID, and an AST node (with its own AST ID) is created to represent this variable in the computation. From there, a instruction that creates a new input is appended to the bytecode. This “new input” instruction stores the AST ID, the variable ID, and the name of the variable (for display purposes.)

The Lua API calls at the end of the function above do a few different things. First, it associates the “ast” metatable to a Lua object that contains the AST ID. After that, it uses “rawset” to insert the newly created Lua “ast” object to the “input” table. Finally, it returns the newly created “ast” object.

Note that the step with the “rawset” is crucial. The “__index” metamethod is called only if the key used to access the “input” table does not exist in the table itself. Therefore, inserting the object into the “input” table guarantees that each variable will only be created once. In other words, an expression like “input.a + input.a” will not create two duplicate variables or duplicate AST nodes.

AST Nodes

After a Lua object with the “ast” metatable is returned by accessing the “input” table, this object will be used in va

C++ Lua Metatable