Lua To Cee

wiki

Description

This utility converts a given Lua source file into an equivalent C source file written in terms of Lua C API calls. At least, this works for a large subset of the Lua language (see limitations below).

The compiler is written entirely in Lua, and no build/install is needed. This project reuses Metalua's gg/mlp parser to convert Lua source to a Metalua-style[1] AST over which the compiler then operates. lua2c does not require Metalua itself though since gg/mlp is bundled in the distribution (patched metalua-0.4.1-rc1) and is written in pure Lua.

Usage

Example usage:

lua lua2c.lua test/bisect.lua

which generates a C file similar to as shown here: [bisect.c].

You may also use the shell script "clua" to compile Lua->C->machine code and execute all in one step. However, you may need to edit the variables in the file to match your system since this utility invokes the C compiler.

./clua test/bisect.lua

lua2c can even compile itself! (Note: the -c option compiles only without running.)

./clua -c lua2c.lua               # compile lua2c binary

./lua2c examples-lua/bisect.lua   # test

Related Work

• luac2c - This related effort by Hisham Muhammad[2] converts Lua bytecodes to C source, whereas this project converts Lua source to C source. luac2c runs into a few similar limitations as given below. luac2c has remained experimental but superseded Luiz Henrique De Figueiredo's very basic but similarly named lua2c for Lua 4.0[3].

• luagen++[4] uses C++ expression templates to translate Lua-like C++ statements to C API calls. Some of the code generation structure is actually fairly similar to lua2c.

• Python Pyrex[5] does something similar in Python but has the added goal of lowering the boundary between C and Python code. Something like that could be done with lua2c, especially since lua2c uses the extensible gg parser.

• Clue by David Given[6] does the opposite: convert C source to Lua source.

• luac + BinToCee[10] allow compilation of Lua source to bytecodes and/or embedding in a C file.

• LuaInterpreterInLua[12] - is the Lua interpreter (lua.c) reimplemented in Lua. It can be compiled to C via lua2c (e.g. for scaffolding).

Potential Uses

I think this project not only is theoretically nice to have but has a number of potential uses:

• Provide another approach of compiling Lua to machine code (rather than luac + BinToCee).
• Streamline the interface between C and Lua code and allow efficient access to C datatypes from Lua (see Pyrex above).
• Compile Lua to optimized C. For example, by statically determining that certain variables are used in a restricted way (e.g. by decorating the Lua source file with pragmas or determining this implicitly by inference), certain code constructs might be simplified to use plain C rather that the Lua C API. This could allow certain Lua code written with sufficient care to run at native speeds. Since it compiles to C, it will even work on CPUs where LuaJIT is not available.

Limitations

WARNING: This code passes much of the Lua 5.1 test suite[7] and can compile itself, but the code is new and there can still be errors. In particular, a few language features (e.g. coroutines) are not implemented. See comments in lua2c.lua for details. Please report bugs/patches on the wiki.

lua2c does not currently support coroutines, functions that normally reject C functions (e.g. setfenv), and possibly tail call optimizations. Not all of these have the exact analogue in C. Coroutines might not ever be supported. However, some solutions might be explored[8][9], including possibly generating code that maintains the coroutine context in Lua tables.

Closures and upvalues are implemented, but creating and accessing upvalues is somewhat slow.

Now that the code is fairly complete/robust, more attention can be given to optimizing the code generation. Performance was 25%-75% of regular Lua when running a few tests[11], but hopefully future optimizations will improve that.

Download

• Latest development source (recommended): http://github.com/davidm/lua2c/ . From here you can browse the source, download a tar/zip snapshot, or checkout with git by running "git clone git://github.com/davidm/lua2c.git".
• Last release distribution: [lua2c-0.2.1-20080802.tar.gz]; Older versions: [achive]

Project Page

The project page is currently http://lua-users.org/wiki/LuaToCee .

Licensing

(c) 2008 DavidManura. Licensed under the same terms as Lua (MIT license). See included LICENSE file for full licensing details. Please post any patches/improvements.

Implementation Notes

Some implementation notes will likely go here.

Important topics include

• Implementing closures with upvalues in C. The current approach is to store local variables that are used as upvalues in a Lua table scoped to the block (lc_newclosuretable). Utility functions lc_getupvalue/lc_setupvalue access it.
• Supporting vararg (...) functions. Mainly, this just requires allowing the stack to be shifted by an arbitrary amount (lc_nextra).
• The transformation process: Lua code string -> Lua AST -> C AST -> C code string
• Implementation of utility functions not in the Lua C API (e.g. arithmetic metamethod handlers, such as lc_add to implement __add to add two numbers while handling metamethods).
• Keeping track of lexical scope (currentscope table)
• Keeping track of the stack (idxtop)
• Handling expressions that evaluate to 0, 1, or multiple return values
• Handling expressions not on the top of the stack (where is 'onstack' v.s. 'anywhere')
• Constant folding
• Possible optimization tricks (not yet implemented):
  • Removing metamethods calls when it can be inferred they won't be triggered.
  • Other code elimination.
  • Using internal interfaces rather than the C API?
  • Building constant tables?
  • Inlining?

Future Work

This project could be significantly helped by the addition of a global (per-file) code optimizer. Most importantly, some type of interprocedural data flow analysis[1] could infer the basic data types of many expressions in code (e.g. this value is a number, has no metatable, is a constant with a certain value, or is positive), especially when that code makes extensive use of local (lexical) variables. If the AST is decorated with this information, the code generator could replace generic code with more specific code. For example, the Lua code "a+b" normally translates to values a and b on the Lua stack, with __add metamethod lookups. However, if a and b are known to be numbers, this can be translated directly to the C code "a+b" where a and b are C doubles on the C stack. There is no reason we shouldn't be able to achieve this type of transformation:

-- Lua code
local function f(n)
  local sum = 0
  for i=1,n do sum = sum + i end
  -- note: sum and n are obviously always numbers.
  return sum
end
print(f(5))

// C code
double sum = 0;  // C datatype
for(int i=1; i<=5; i++) { sum = sum + i; }  // no overhead!
lua_getfield(L,LUA_ENVIRONINDEX,"print");
lua_pushnumber(L,sum);
lua_call(L,1,0);

Global optimization of Lua code is an interesting problem, and I'm learning some about data flow theory in my spare time. If anyone else has more experience in this area and is motivated to work on the optimizer, you're more than welcome to. There may be some overlap with LuaJIT and other projects here[2].

Some syntax for embedding C expressions in-line to Lua code should also be high on the to-do list (as in Pyrex).

References

• [1] Metalua AST - http://metalua.luaforge.net/manual006.html#toc17
• [2] luac2c (previously named luatoc) - LuaList:2006-07/msg00144.html
• [3] LHF's lua2c for Lua 4.0 - LuaList:2002-01/msg00296.html
• [4] luagen++ - LuaGenPlusPlus
• [5] Pyrex - http://www.cosc.canterbury.ac.nz/greg.ewing/python/Pyrex/
• [6] Clue - http://cluecc.sourceforge.net/
• [7] Lua 5.1 test suite - http://www.inf.puc-rio.br/~roberto/lua/lua5.1-tests.tar.gz
• [8] [Wikipedia:Coroutine - Implementations for C]
• [9] [Coco] - True C coroutine semantics (used in LuaJIT)
• [10] BinToCee
• [11] [The Computer Language Benchmarks Game]
• [12] LuaInterpreterInLua - Lua interpreter (lua.c) reimplemented in Lua.