Friday, May 28, 2010

Getting started with Kahlua2

This post contains some words and acronyms that are good to know about.
  • J2SE - Java 2 Standard Edition - is the Java version that is available on desktops. Kahlua core depends on J2SE 1.4 or higher, while the J2SE extensions require J2SE 1.5 or higher.
  • CLDC - Connected Limited Device Configuration - is a slimmed down version of Java, with many features removed. Kahlua requires CLDC 1.1 or higher to work.
  • Midlet - Application for mobile devices using CLDC (and MIDP, but let's not go too deep).

Kahlua2 is built with a modular design.
This means you can configure your system the way you want it but it also means that there are some basic things that need to be set up to get started.

The platform
First of all, you need a Platform.

The core of Kahlua2 has some dependencies that are platform specific. For instance, Kahlua2 needs to be able to create tables, and the table implementations are different for J2SE and CLDC 1.1. They are backed by ConcurrentHashMap and Hashtable respectively.
For that reason, Platform has the method:
KahluaTable newTable();

Fortunately for you, getting hold of a platform is easy!
Just call J2SEPlatform.getInstance() or CLDC11Platform.getInstance().
These platform implementations are immutable, so don't worry about sharing the platform with others.

Typically you want to use CLDC11Platform for writing midlets and J2SEPlatform for everything else. If for some reason, neither of these platforms suit your purposes, you can simply create your own.

An environment
The global scope in Kahlua (as well as in Lua) is just a regular table. The compiler makes sure to translate any variable that isn't declared as a local to a lookup in the environment table.

If the environment is just a regular table, can we simply create one by calling platform.newTable()? Yes! That works perfectly well.

However, this environment will be empty, so you can't find the standard library functions in it, and most of the scripts you want to run probably needs a couple
of standard functions to do anything interesting.

An alternative way of creating an environment is to call platform.newEnvironment(); This creates a new table, but also populates it with useful stuff. J2SEPlatform for instance loads the environment with BaseLib, MathLib, RandomLib, StringLib, CoroutineLib, OsLib, TableLib and the compiler.

If you're curious, take a look inside J2SEPlatform, it should be easy to follow.

Compiling scripts
Having an environment is not very exciting in itself, you probably also want to run some scripts! Kahlua has two ways of creating closures (or functions) for these scripts. The easiest and best way is to use one of the static methods in LuaCompiler; use loadstring if you have the input as a string, and loadis if you have an inputstream or reader. All closures needs environments, so you need to pass in your environment as the last parameter (or another environment if you prefer).

Note that the compiler will throw a KahluaException (which is a RuntimeException) if the script is malformed. You should be prepared to handle it.

The other option is to load the bytecode directly. This is mostly useful on devices where you dont want to bundle the full compiler, such as limited mobile devices. The solution is to compile the scripts offline, either with the standard luac bundled with Lua, or with Kahluas own Java class called LuaC. The resulting binary file can then be loaded with KahluaUtil.loadByteCodeFromResource.

The thread
With a platform, an environment and some closures, you're almost set to start running your scripts, but there is one more thing needed - a thread to run them in.
KahluaThread t = new KahluaThread(platform, env)

is all you need to create a thread.

Kahlua is concurrent in the way that you can create multiple threads that reference the same environment, but don't try to run scripts on the same KahluaThread from different Java threads! Things would blow up in mysterious and unexpected ways.

The most basic way of invoking your closure is by using, args...). However, if the closure invocation should throw an error, a RuntimeException will propagate out to the Java code. A safer option is to use thread.pcall(closure, args...) which traps all Lua errors and returns the error information as part of the return values.

For J2SE, there are few more ways of invoking closures, but more on that in a later post.

Java functions
Most applications that use an embedded script engine have a need for the scripts to access domain specific functions. If I were to write a game engine, then my AI scripts might need a way to execute orders. So the opposite of Java invoking Lua scripts is needed; we need to be able to call Java methods from Lua.

There are several ways of doing this in Kahlua, but they all boil down to this core functionality:

interface JavaFunction {
int call(LuaCallFrame callFrame, int nArguments);

Kahlua can call any object that implements this interface. This is how all of the standard library in Kahlua is implemented. This is also the only way to do it in CLDC 1.1, due to lack of a reflection API.

The parameters to call is a callframe, which contain the arguments passed to the function, and the number of arguments. The return value of call should be the number of return values, since Lua supports multiple return values. The return values themselves need to be pushed on the Kahlua stack, and there are convenience methods for that in the LuaCallFrame object.

Here is a simple example a JavaFunction implementation intended to be used like this:

local x, y = GetUnitLocation("The unit name")

public class GetUnitLocation implements JavaFunction {
public int call(LuaCallFrame callFrame, int nArguments) {
if (nArguments < 1) {
throw new IllegalArgumentException("Expected at least one argument");
Object arg = callFrame.get(0);
if (arg == null || !(arg instanceof String)) {
throw new IllegalArgumentException("Expected a string argument but got " + arg);
String s = (String) arg;
Unit unit = unitService.getUnit(s);
return 2;

Due to the dynamic nature of Kahlua, there needs to be a lot of boilerplate error checking, but the rest of the implementation is straight forward.

Exposing things
Just having a JavaFunction implementation is not enough - it needs to reach the lua scripts in order to be useful. This can be done in several ways. The first, and most obvious, is to put it in the environment:

environment.rawset("GetUnitLocation", new GetUnitLocation());

The lua script can then call it by just doing:
GetUnitLocation("the unit name")

The lua script can also copy it somewhere, redefine it - "GetUnitLocation" is just a key in a table, and can be manipulated like any other object, so you can do things like this:
fun = GetUnitLocation
fun("the unit name")

local oldfun = GetUnitLocation
function GetUnitLocation(s)
print("calling GetUnitLocation here")
return oldfun(s)

That's all you need to know to get started with Kahlua. It may seem like there was a lot of steps involved, but each step is really very simple.

For mobile platform targets, there isn't much more to add but for J2SE users there are additional goodies available, which I'll go over some time in the near future.

Tuesday, May 25, 2010

Half baked objects

A half baked object is an object that after construction is still not ready to use.
Using it will either just silently behave badly (that's bad) or throw a usage exception (that's less bad).

This is a really irritating code smell, because it makes it much too easy to introduce bugs. The best APIs I've used have made it impossible (or atleast very difficult) to use it incorrectly because once they've given me an object to work with, they've guaranteed that they're set up properly and are ready for action.

There are some generic rules you can use to avoid having half baked objects:
  1. Set up everything in the constructor. This is not always possible, but when it is, do it.
  2. Use final fields - they enforce you set up everything in the constructor, which reduces the risk for bugs. Note that final fields in itself doesn't make the object immutable, you can still have final lists, maps and sets in your object, which themselves are mutable.
  3. Use builders - and don't allow creating the real object until the builder has all the necessary requirements.
  4. Be suspicious of methods named things like "init", "postconstruct", "setup" or similar. They could be indicators of a half baked object.
However, I have found one case of needing half baked objects, and I currently don't have any workaround for it.
This is a new feature in Mockachino, where I want to create an alias for a combination of a mock object and a method signature.
Since I can't pass a method signature as a parameter in Java (without using icky reflection) my only choice is to capture the method invocation and record it in the Alias.

interface Foo {
foo(int n);

Foo mock = mock(Foo.class);;

SimpleAlias alias = newAlias(); // alias is half baked here - it's not bound to any mock

alias.bind(mock).foo(anyInt()); // now alias is fully setup


This is one of few cases where half baked objects is hard to avoid, but if anyone has any clever suggestions, I'm all ears.

Temporal testable code

A lot of code is time dependent. Code either needs to wait or timeout for a specific amount of time, or it needs to fetch the current system time for some reason.

If the code uses Thread.sleep(), System.currentTimeMillis(), new Date(), or anything like that, it has a hidden and implicit dependency. This can be a problem when you're trying to write tests for such code.

The tests usually end up with a lot of:

Thread.sleep(1000); // wait for code to finish doing its job.

This will make your test suite unnecessarily slow to run, and you want your tests to finish almost instantly.

The solution is to convert this implicit dependency to an explicit!
This is done by creating the following interface:

public interface TimeProvider {
long now(); // Replaces System.currentTimeMillis();
sleep(long timeInMilliSeconds) throws InterruptedException; // Replaces Thread.sleep

All the code that is time dependent in any way should inject an object of this interface.
Now, you need two implementations of this interface, one for real usage and one for testing. Fortunately, these are trivial to write:

public class SystemTimeProvider implements TimeProvider {
public long now() {
return System.currentTimeMillis();

public void sleep(long timeInMilliSeconds) throws InterruptedException {

public class MockTimeProvider implements TimeProvider {

private long now;

public void setNow(long now) { = now;

public void advanceTime(long amountInMillis) {
now += amountInMillis;

public long now() {
return now;

public void sleep(long timeInMilliSeconds) {
now += timeInMilliSeconds;

For the real application, everything will behave the same.
For testing purposes, just inject the MockTimeProvider instead, and manually manipulate the time.

Here's simple example to illustrate how this works in practice.
Basically we want to ensure that when we generate UUIDs, a specific part of the UUID remains the same if two UUIDs are generated close enough temporally, but different if there's a small time difference:

public class UUIDTest {
private final MockTimeProvider mockTimeProvider = new MockTimeProvider();
private final UUIDFactory factory = new UUIDFactoryImpl(mockTimeProvider, new SecureRandom());

public void combTest() throws InterruptedException {

UUID firstUuid = factory.combUUID();
UUID secondUuid = factory.combUUID();

long combPart1 = getCombPart(firstUuid);
long combPart2 = getCombPart(secondUuid);
assertEquals(combPart1, combPart2);


UUID thirdUuid = factory.combUUID();
long combPart3 = getCombPart(thirdUuid);
assertFalse(combPart1 == combPart3);


private long getCombPart(UUID uuid) {
String combString = "0x" + uuid.toString().substring(24, 36);
return Long.decode(combString);
Stop using static ways of using time in your code!
Using an injected TimeProvider works almost identically if it's a SystemTimeProvider, so the only cost is a slightly more costly method invocation since it's through an additional abstraction layer.
But the benefits are huge! Your code will be more testable, and the dependency on time is no longer hidden.

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.

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.

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.

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:


The hobby game, with working title Spaced

Tuesday, May 18, 2010

What's up with String.format

I noticed a while back that Javas own String.format() is slower than I expected it to be. I compared it to the handbuilt version in Kahlua which is built with a naive approach using only Java 1.4 features.

To follow up on this, I wrote a benchmark to see if I can really be sure that it is in fact slower. Writing benchmarks is always tricky and is easy to get wrong. Here's my approach of writing a test.

public class StringFormatTest {
static interface Runner {
String run(String format, Double x, Double y);
String name();

static class JavaRunner implements Runner {

public String run(String format, Double x, Double y) {
return String.format(format, x, y);

public String name() {
return "Java String.format";

static class LuaRunner implements Runner {
private final KahluaThread thread;
private final LuaClosure closure;

public LuaRunner(KahluaThread thread, LuaClosure closure) {
this.thread = thread;
this.closure = closure;

public String run(String format, Double x, Double y) {
return (String), format, x, y);

public String name() {
return "Lua string.format";

public void testFormat() throws IOException {
String format = "Hello %3.2f world %13.2f";
Double x = 123.0;
Double y = 456.0;

Platform platform = new J2SEPlatform();
KahluaTable env = platform.newEnvironment();
KahluaThread thread = new KahluaThread(platform, env);
LuaClosure closure1 = LuaCompiler.loadstring("" +
"local stringformat = string.format;" +
"return function(format, x, y)" +
"return stringformat(format, x, y)" +
"end", null, env);
LuaClosure closure = (LuaClosure), null, null, null);

Runner luaRunner = new LuaRunner(thread, closure);
Runner javaRunner = new JavaRunner();

List<Runner> list = new ArrayList<Runner>();
for (int i = 0; i < 20; i++) {

for (Runner runner : list) {
int count = 0;
long t1 = System.currentTimeMillis();
long t2;

while (true) {
t2 = System.currentTimeMillis();
if (t2 - t1 > 1000) {
}, x, y);
double performance = (double) count / (t2 - t1);
"%30s %10.2f invocations/ms",,

I've done my best to make this test be fair. The obvious first thing to do is to run each test many times, to ensure that cache misses, JIT optimizations, warmups, et.c. are all taken into account. The second obvious thing is to shuffle the ordering of tests to avoid introducing accumulating interference.
For instance, if I were to run the tests as A, B, A, B, ... then any garbage being produced at the end of A would punish B when it ran its garbage collector.

Having run this test suite for a bit, I consistently get these results:

Lua string.format 232.71 invocations/ms
Java String.format 170.07 invocations/ms
Lua string.format 231.61 invocations/ms
Java String.format 170.34 invocations/ms
Lua string.format 232.73 invocations/ms
Java String.format 170.10 invocations/ms
Java String.format 170.11 invocations/ms
Java String.format 171.23 invocations/ms

Why is the Lua version faster? It should be much slower considering:
  1. The Lua version has to go into its interpreter loop as additional overhead.
  2. The Lua implementation of string.format is a naive and short implementation, and not built by the elite development team of Sun.
Perhaps the difference is that the default Java implementation handles a lot of additional use cases such as locale, but that still doesn't really explain it.

Does anyone have any ideas why Javas String.format is slow?

Monday, May 17, 2010

TDD - levels of insight

Test Driven Development (or Design) is a method of developing code where you first write small tests that express the requirements, it can either be requirements from the customer or product owner, or requirements the developers themselves deduce are needed of the product.

The idea is that by writing the tests first, the design of the code improves, because it will automatically become modular (writing tests for code that's not modular is much harder, if not impossible). The tests also increase your development speed, since running your suite of tests takes a much shorter time than starting up the application and manually testing everything. If you make a mistake somewhere when refactoring the code or writing a new feature, it will become obvious directly, since the tests will expose it, if it breaks any of the requirements.

But let's not go into the details of TDD, there are plenty of other sources that describe TDD much better than I ever could.

Instead, this blog post will be about a hypothesis I have.
I don't believe you can really study TDD and just get it. You have to try it out for yourself and become convinced by experiencing the benefits. You will notice that you can keep maintaining a project without losing speed and your code will be extendable.

So what is the hypothesis? Glad you asked!
Every developer will go through a series of levels of insight, with each level being closer to being a TDD master.

And here are the levels I've identified, based on anecdotal evidence consisting of my personal experience, and what I've observed in others.

#1 Obliviousness
As a fresh developer, it's obvious that at some point in your life, you didn't know about TDD. I'd also take a guess that it's common to start programming before starting to write tests. From the various educations I've been to and talked to others about, testing is not something that's introduced early in programming training.

Obliviousness simply means that you're unaware of TDD is a practice and its usefulness. I was unfortunately in this category for much too long, which I suspect is true for a lot of developers.

#2 Disregard
The next step is hearing about TDD and getting the initial thought: "Writing tests first? That sounds backwards!". Not only that, you may also think that is seems like a waste of time to spend a lot of time writing tests that will soon be obsolete anyway, or tests for things that have obvious failures "I'll obviously notice immediately when starting up if this breaks".

#3 Awareness
Level 3 is being aware of TDD and that it can be a useful tool, and not just a stupid overhead designed as support for bad developers.

The easiest way to get past level 2 onto level 3 is to work with someone who's already past it, who seems to be using it successfully.

"Hmm, that guy produces clean code and doesn't seem to introduce as many bugs as I do, I wonder why..." Deeper investigation may lead to the introduction of TDD.

This may inspire you to try out writing tests first (or just writing tests at all), but since you're unfamiliar with TDD to begin with, your code will be hard to test, and it will be a pain to write the tests. You'll spend a long time to write the test, and you'll become irritated. "Do I really gain anything from spending so much time writing tests instead of producing code? QA will find any bugs I produce anyway, better to spend the time later to bugfix it instead."

Unfortunately, this is a typical setback that some people fail to get past.

#4 Empirical
Level 4 is when you've tried TDD for such a long time that you're really convinced that it's the best way to develop.
To reach this level, you need to really have used for such a long time that you have started to reap the benefits.

You have may have done a simple refactoring or introduced a new feature when one of your oldest tests break, and you look into it. "Aha, of course I needed to consider that before I did this, no wonder it broke!".

This is when you'll start building up the confidence in your code. If you introduce some code change that will break something, your tests will catch it.

Writing good tests, and writing them before the code is hard, as is writing clean and modular code. Becoming good at TDD takes time and effort, but it also makes you a better developer and better designer. Suddenly all your code will have at least two use cases - the test code and the runtime code.

#5 Mastery
After having been in level 4 long enough, TDD will become second nature to you.
You would use TDD for all development with the insight that it drives good design and saves time. No aspect of code is too hard to write test driven for a master, not even the typical daunting tasks intimidates the TDD master: UI, database, network, et.c.

I personally am stuck in level 4 at the moment. Perhaps I'll stay there forever, but even so it's probably a good idea to keep striving to reach level 5. I do this by trying to embrace TDD in my development as much as I can, but how can I be sure that's enough? Perhaps some other insight is needed to step up to the next level.

If I find any answers to that, You can expect a follow up post.