Friday, May 21, 2010

The history of Kahlua

In 2007, there was really only one alternative if you wanted to run Lua on Java.
LuaJava implements a native binding from Java to the real Lua,
which requires you to bundle a platform specific library with your Java application.

This meant that the integration with Java wasn't as easy to use as it could have been - the memory spaces were completely separated, just like the memory space of regular Lua is separated from C.
It also meant that Lua on J2ME devices was complete out of the questions - you're not allowed to bundle native libraries in J2ME applications, and even if you did,
they would probably be much too large.

So I thought it would be a fun idea to implement a pure Java implementation of Lua to see how similar it would be. I figured that it wouldn't be too much work, since several data types in Lua would be easily mapped by existing classes in Java:
  • strings, numbers and booleans in Lua could be implemented by the String class, Double class and Boolean class respectively in Java. These types are immutable in both languages and have the same behaviour, which
    makes it a good fit.
  • the special value nil was trivially mapped to null in Java.
  • tables can be implemented as a plain Java class.
  • java functions (a Java object implementing a specific interface).

Regular Lua implements sophisticated memory management with garbage collection. This is completely avoided in Java by just using the same memory space and taking advantage of the built in garbage collector in the JVM.

Error handling in Lua were adapted similarly, by simply mapping Lua errors to Java RuntimeException.

Kahlua was originally written with the goal of implementing the basic virtual machine for running Lua bytecode. There were no plans for having a compiler or supporting advanced features such as coroutines. It was aimed at both J2ME and J2SE, and thus only supported the common subset between the two - CLDC 1.1.
Since the project goals were fairly modest, and the actual virtual machine can be written fairly simple and straightforward, it didn't take long until Kahlua could load bytecode compiled from the regular Lua and run it with a limited implementation of the base library.

After the success of having the toy project actually work, I set out to implement more of the advanced features of Lua - Upvalues, coroutines, weak metatables and the complete string library. Getting all this to work took some time, but it ended up quite compatible with Lua.

Soon after that, I started working on a hobby J2SE game project, and thought it would be fun to start using Kahlua as a scripting language there. Kahlua worked nicely there, but it relied on external compilation so we had to either precompile scripts with the commandline luac or make a JNI binding to the lua library. We started with the precompiling, but once we realized that we needed hot reloads,
doing the second approach was unavoidable.

Within the next couple of years after the initial release of Kahlua, several other pure Lua implementations emerged.
First after Kahlua, I think, was Mochalua which was also aimed at J2ME and had more core functionality for directly interacting with MIDP instead of just CLDC, which unfortunately made it harder to use in J2SE. Mochalua was more of a direct port of the original C code than a reimplementation but just like Kahlua, it lacked a compiler.

Not long after Mochalua, LuaJ appeared, which also was based on a port of Lua.
LuaJ had however also implemented/ported a compiler and had a coroutine implementation based on Java threads. This was a quite sophisticated project, with a very modular design. It had a clever solution for supporting both J2ME and J2SE based on a platform interface that both J2ME and J2SE implemented, which I ended up getting inspiration from later on.

It also turned out that LuaJ's compiler could, with a little bit of refactoring, be adapted to fit in with Kahlua, so I forked it and put it into Kahlua and seemingly over night, Kahlua had its own compiler and the JNI solution could be dropped. Thanks LuaJ!

A while after this project, yet another Lua project in Java appeared. JILL, or Java Implementation of the Lua Language wasn't really a new project - Nokia had funded it and it had just recently been open sourced. I haven't really looked into it much, but it seemed to use a similar approach as Kahlua, adapting the implementation to Java instead of doing a straight port.

Now, back to the game project!

We were writing our entire UI system in Lua, with gui and game logic methods implemented in Java and made available to Kahlua. Creating the raw JavaFunction's needed for Kahlua required a lot of low level operations, such as verifying correct number of arguments and the types of the arguments as well as pushing return values, so we decided to implement an easier mechanism for exposing methods.

This ended up as a contrib-library in Kahlua that supported exposing Java classes annotated with @LuaMethod. It handled all of the problems above, which made our lives much easier. In time, this library grew to also include conversion between Lua and Java types. Since Lua only used Double as a numeric type, we needed conversions from the other numeric types in Java. Lists and Maps in Java were converted to KahluaTable.

This was pretty much the last real development for Kahlua, but I started getting other ideas for the further development of Kahlua.

The birth of Kahlua2
I started getting a lot of ideas for how to modernize Kahlua which meant departing from many of the original design decisions, and introducing big incompatibilities with the original Kahlua. So, Kahlua2 was born, this time on github instead of Google Code. The reason for this was unrelated to the actual development of Kahlua - I just wanted to learn git, and investigate if its workflow and features had any real life benefits over Subversion.

I've identified three main categories of design changes.

Modularity
Kahlua didn't differentiate the versions for J2SE and J2ME, which meant that J2SE had to suffer a bit (not much, but a bit). The most significant effect was that most of the math operations were implemented in software, which is both slower and less precise than the built in operations in J2SE.

The solution in Kahlua2 was to introduce a platform interface implemented for both J2SE and J2ME, and creating two separate math libraries, similar to the solution used in LuaJ.

Compatibility
Keeping compatibility with Lua was one of the original goals of Kahlua, and it reached pretty far. Tables in Kahlua had the same behaviour as tables in Lua.
This was done with a complete low level implementation of tables and special handling of doubles (0 and -0 are the same key in lua tables, but in Java they are distinct). The low level implementation was required to achieve a reasonably fast implementation of next().

I meant for Kahlua to be primarily a way of extending Java with a good script language and thus compatibility with Java is more important than compatibility with Lua. Also, keeping the code simple and efficient should have a high priority.
The handcoded table implementation in Kahlua is likely not as a good as the built in maps in Java, so Kahlua2 simply drops compatibility on table keys, removes the next function, and removes support for weak tables. I hope no one will miss these features too much.

Concurrency
Kahlua, and all other Lua implementations I knew of were inheritly single threaded.
Each lua state could only be run by one thread at a time, and states couldn't really share data.
With the loosening of compatibility, Kahlua2 can instead implement tables as a simple facade to either Hashtable (for J2ME) or ConcurrentHashMap (for J2SE),
which means that Kahlua2 suddenly becomes concurrent.

All native datatypes in Kahlua (and Lua) are immutable except for tables, upvalues and the stack itself. The stack concurrency is solved by not letting multiple Java threads use the same KahluaThread at the same time. Upvalues are solved by simply making the set and get-methods be synchronized.

Unlike Kahlua, Kahlua2 separates the script environment and thread. Multiple KahluaThreads can share the same environment, which is the key to concurrency.
The threads are not to be confused with Coroutines, which still work just like in Lua.
Many KahluaThreads can share Coroutines, but only one thread can run a coroutine at a time.

Present day
You can currently find Kahlua2 on github and it's still evolving, although the core ideas for Kahlua2 described above are already implemented. The changes at the point in time mostly consist of bug fixes, refactoring of the compiler (it's still mostly a C port, which fits badly with Java).

That's it for now!
Stay tuned for The History of Kahlua part 2, expected somewhere around 2013 perhaps.

Relevant links:
LuaJava
Mochalua
LuaJ
JILL

Kahlua
Kahlua2

The hobby game, with working title Spaced