How the embeddability of Lua impacted its design (2011)

There's a collection of c-exposed values called the api stack (not to be confused with the function stack). The stack keeps them from being collected, so there's no need for ref counting. OP writes about this.

OP doesn't write much about the GC itself, but I can tell you a little from my dayjob-using-lua experience. It's mark'n'sweep, but (i) it's narrowly tailored for lua tables, not general purpose allocations, and (ii) it's incremental, so you can cap individual pause times and amortise (imp for games).

  > I'm missing the crucial design bits which would influence
  > embeddability:

Your points are crucial but mundane. For people who have done extension and embedding with other languages like Perl, Python, Tcl, etc, what really matters for productivity and maintenance are the more subtle details.

For example, in Lua you can create _instances_ of a wrapped C function that has upvalues, which are analogous to closed-over variable slots. In other words, you can implement C callbacks as closures, a more functional-oriented approach which also generally more performant than many alternatives. In many languages to associate instance data with wrapped functions (as opposed to wrapped methods where you're always passed an instance object) you're stuck using some sort of global registry or other coarse mechanism. Lua supports many such alternatives, as well, including some novel alternatives. But the upvalue mechanism is particularly elegant and useful.

Another useful feature, which is discussed by that paper, is how Lua designed coroutines--the semantics, the implementation, and the public C API. Languages like JavaScript, Perl, and Python don't support stackful coroutines (i.e. being table to yield a coroutine from any arbitrary function, not simply the function initially invoked/resumed). They neither support them within the language nor outside the language for use by C, and with exception (a brilliantly complex Perl XS module comes to mind) you can't even begin to fake this. This is because implementations of those languages conflate the host C stack with the logical call stack of the language. And because you can neither grow the C stack nor easily yield and resume, these languages simply eschew stackful coroutines altogether. The implementation restricts the semantics they can implement at the language level.

Lua not only supports stackful coroutines, but it provides a mechanism and API for resuming and yielding a Lua/C function, all in strict ISO C. This was more limited in Lua 5.1, and made more powerful in Lua 5.2. In any event, this mechanism makes it easy to, among other things, write asynchronous I/O frameworks in Lua that behave like green threading. You don't need to pepper your code with async/await everywhere, nor do you need to create trampolines in your FFI binding code to get yield semantics from the C callback, which results in messy and complex modules.

Lua is awesome as both an extension and embedding language because it was built from the ground keeping those requirements and constraints in mind. The only serious concession most languages make for integration with C is either to avoid moving pointers, or providing a special type to wrap objects visible in C. All the rest occurs as an after thought, and while the results are often acceptable, they're just not remotely as convenient or seamless.

The biggest exception to my points above are Tcl. I find Lua more elegant and powerful, both the language and the C APIs, but Tcl deserves its due.

Pointers do not ever 'move'. You also should never store variables (to userdata, memory chunks, strings, etc.) by pointers or anything like that according to documentation because they might be collected at any time. To stuff like tables or values you never ever get a pointer and having a pointer to a "Lua value" would make no sense because it's a small struct with just the type number (in case of nil that's all that matters actually) and then either an inline value (light userdata, bool, number, etc.) or a pointer to the actual GC object (thread, string, table, function, internal data structures, etc.). Lack of exposing internal data structures (there is Buffer in luaL but it's the only one I can think of and it's so simple and just to collect few results together it doesn't matter) is probably the reasons why LuaJIT is ABI and API compatible with Lua 5.1 despite implementing stuff very differently internally (like values in NaN tagged doubles to keep them in a 64 bit boundary instead of just placing fields normally in structs and letting compiler figure it out like stock Lua does).

There is a feature in luaL part of the C API called 'refs' but that's basically storing stuff in a table array and addressing it by ints and it's done all using the C API itself, it's not a VM or language feature.

There is also a weak reference system (where table can be marked to have key, value or both be 'weak' and allow collection if there are no 'strong' references anywhere to these objects) and that is part of the VM itself (GC specifically, the table processing code) and has some caveats with stuff like strings (they are interned in Lua) and it doesn't remove intelligently form tables serving as arrays.

To call a function from C you push it and its arguments onto the stack (of the main thread or the coroutine) and execute it with one of API functions (depending on what you're trying to do)[1], to call it in Lua you 'just' call it or pass it to pcall or a when making a coroutine.

A C function exposed to Lua like that must implement its 'protocol'[2] which is getting and returning arguments by interacting with the lua state pointer so it's an extra effort to wrap them or you can use a third party library (there are some, especially C++ ones which use templates to automatically wrap stuff, but I don't use any myself).

C and Lua functions are indistinguishable in most cases, they are called the same way, etc. but sometimes they differ, i.e. Lua functions can be dumped with string.dump.

There is no FFI (as there is in C#, JNI, etc.) as such. LuaJIT has an FFI that parses C declarations and it's quite nice IMO. There are also third party FFI libs but I know nothing about them. Using that also loses you all the nice to haves that Lua has like multiple return values (it's customary to return false or nil and an error message string on errors from many functions and it's impossible to write an iterator without multiple return values), interacting with lua state in the function, arg type check calls with automatic errors, etc.

The GC is a mark and sweep one, in 5.0 it was a stop the world one - two color, from 5.1 onwards it's incremental tri color with forward and back write barriers(see [0] for an explanation of what that means and how it works). In 5.2 there was also (off by default) generational one. I have no idea how that one worked and it was removed in 5.3. LuaJIT also uses mark and sweep from 5.1 but with improvements and for 3.0 there was supposed to be a quad color one. You of course have full control over it (stop, start, adjust speed, force a full cycle or a single step, etc.) to complete right now) from Lua and C via the right function. It does nothing fancy like compaction or copying/moving.

You are also responsible for the memory allocation (in 64 bit LuaJIT it's taken over and attempting to do that is an error) and the default alloc is just a malloc wrapper[3]. From 5.2 onwards you also get told during initial (i.e. not the resize) allocation what kind of Lua object is being allocated (it doesn't tell you about internal structures though, only the user visible Lua types) so that might help you make some decisions in the allocator. Lua VM never allocs memory or touches the system on its own in any way either.

If you want you can remove all the standard libs like os, io, etc. and not use any of luaL functions (they all are implemented using Lua C API only so they are 'userspace' and optional, not part of VM, they do not use internals of the VM itself). Even the require mechanism for importing libs is all userspace implemented (unlike like Python where it's part of the language, I think). It's also possible to recompile Lua and change what type the number is (double so 64 bit by default, plus 64 bit int in 5.3, there is convenient macro to force both to 32 bit in 5.3, for LuaJIT I'm not sure, it uses NaN tagging in a double and a handwritten asm to get its speed and compactness and I'm not familiar with its codebase like I am with the vanilla Lua), add a bit of extra space in front of the VM for direct instant access from C (space for 1 pointer by default in 5.3, no space before that) and a bunch of other configurable things. The codebase of PUC-Rio Lua (i.e. not some third party implementation like LuaJIT or Havok Script[4] - which I think they don't even sell but that Google still indexes and they have a testimony on the front page for...) is also easy to jump into if you know C and very small (c.a. 10k lines if you ignore the lexer+parser+compiler part, std libs and standalone lua and luac program sources).

Feel free to ask about anything if I was unclear. I am knee deep in Lua by now and I've even written about Lua internals for my engineer's thesis (in Polish) so I'd say I'm quite up there with my knowledge of its working and history and such compared to average Lua knowing person. I thought about recycling my notes to write an article about that but I don't really see a point because I'd largely be rahashing between source code itself (very readable!) and various resources like no frills intro to vm instructions[5], articles from the three Brazilian devs themselves, mailing lists, details on LuaJIT page, etc. If someone is interested about such an article then you can drop me an email( my email address is visible once you're logged in at https://github.com/FRex/ ) and if I get a few I might do it.

[0] - http://wiki.luajit.org/New-Garbage-Collector#introduction [1] - http://www.lua.org/manual/5.3/manual.html#lua_call [2] - http://www.lua.org/manual/5.3/manual.html#lua_CFunction [3] - http://www.lua.org/manual/5.3/manual.html#lua_Allo [4] - https://www.havok.com/wp-content/uploads/Havok_Brochures/Hav... [5] - http://luaforge.net/docman/83/98/ANoFrillsIntroToLua51VMInst...