What's great about Lua?

Lua is an amazing programming language implementation. I say implementation because it is not just the language itself but how it is implemented that is particularly impressive.

As a programming language, Lua can be characterised as a small but powerful language. The power comes from clever use of a few core meta-mechanisms as Lua authors like to put it. A nice introduction to some of these are in the recent talk by Roberto Lerusalimschy at the Lua Workshop 2016.

I used to think that Lua is a simple language; but appearances are deceptive. I now think of Lua as 'small' and 'powerful' language rather than a 'simple' language.

The language design is clever, but the implementation is what makes it great.

Firstly it is a very compact implementation, just a few C source files, and that's it. No dependencies other than an ANSI C compiler.

Secondly, despite the compact implementation, it features:

• A byte-code compiler and Virtual Machine.
• An incremental garbage collector.
• Extremely fast parser and code generator.
• And the language is delivered as a library with an extremely well designed C API, that makes it easy to embed Lua as well as extend it.

It is this combination of economical design and beautiful implementation that makes Lua great.

Lua 5.3 Bytecode Reference

Lua bytecodes are not officially documented as they are considered to be an implementation detail. The best attempt to document Lua bytecodes is the A No-Frills Introduction to Lua 5.1 VM Instructions by Kein-Hong Man. However this document is quite old now and does not reflect the changes made since Lua 5.2.

Some time ago I started an attempt to bring this document up-to-date for Lua 5.3. I recently managed to spend a few hours updating the new Lua 5.3 bytecode reference. This is still not complete but the most important bytecodes are covered.

I want to eventually produce a version that is like a specification, i.e., one that allows independent implementations to replicate the bytecode generation. My interest in this is due to my desire to create a new parser and code generator for Lua. 

I love the new Microsoft!

I have always been a Java person ... until now. With the new cross platform open source CLR (.Net) platform from Microsoft, I am doing exciting new work in C#!

I also love the Linux subsystem on Windows 10 - which I installed today. I was able to build my Lua derived scripting language Ravi using Linux tools right within Windows. I did not enable LLVM but that is next on my list to try. If this really works, then I can decommission my Linux Virtual Machine.

I also love that Microsoft's made the Visual Studio Community edition free - and this is the full version and not a cut-down version. And the new Visual Studio Code editor is great - checkout my Lua/Ravi 5.3 debugger extension for it!

All in all - great stuff, Microsoft!  

Lua Workshop 2015

I presented Ravi at the Lua Workshop 2015 held at Stockholm. You see see the slides of my presentation here.

An LLVM binding for Lua

I announced the development of Ravi back in January 2015. It started as an experiment - I was not certain whether Ravi could achieve the performance levels of LuaJIT, the reigning monarch for Lua JIT compilation.

I am pleased to report that Ravi is able to match LuaJIT's performance for a few selected benchmarks. More details are available here. While this is positive news, there is still much to do to make Ravi competitive in a variety of situations.

LuaJIT offers a powerful FFI interface for interfacing with external libraries and like. This is very convenient for sure, but the approach taken is not compatible with Lua. After some thought I decided that rather than creating an FFI interface for Ravi, a more general capability would be to allow both Lua and Ravi users to write JIT code using LLVM. Work on this has just started so there is not much to show yet, but I hope to make progress fairly quickly.

LLVM is a very low level api - lower level than C. This has its pluses and minuses. On the plus side the LLVM binding will allow Lua and Ravi users to exploit the full power of LLVM. On the minus side even writing trivial functions can be quite some effort.

Memory bugs and finding them

I am working on creating a JIT compiler for Lua and Ravi. Ravi is a Lua derived language with some enhancements to help improve performance. The JIT compilation is being implemented using LLVM.

As I implement more parts of the Lua language I am able to run more of the standard Lua test suites in JIT mode. A few days ago I encountered a nasty bug - one of the test cases failed on Windows with a run-time exception that seemed to imply an invalid or misaligned stack. Now this is a particularly hard bug to find as at runtime there is a mix of code compiled by the MSVC compiler (the Lua C code) and the code generated by LLVM. The LLVM generated code has no debugging information right now as I haven't yet implemented the required metadata. So the problem is how to investigate the issue if the fault is in LLVM generated code.

Confusingly the error only occurred on Windows - but not on Linux, so I was initially led to believe that the error may be due to some issue with how LLVM was using the stack on Windows.

The problem with memory errors is that they are Heisenbugs. Any change you do to investigate the issue such as adding a debug print may help the bug to hide. So investigation is particularly hard.

My initial attempt at finding the root cause was to run the tests under Valgrind. Valgrind reported some possible memory leaks but not in my code - the reported potential leaks were in LLVM code. There were no reports of buffer overflow or memory overwrites.

I guess that if the problem is some portion of the stack being overwritten then Valgrind cannot find it as it is more a tool for analyzing issues with heap allocation.

My next stop was to use Address Sanitizer. This is a tool created by Google engineers - it works by instrumenting the code using some compiler extensions. Fortunately this capability is available in GCC 4.8.2 which is the compiler I am using on Ubuntu. Just by adding a compiler option (-fsanitize=address) one can get instrumented C code. The tool not only checks heap allocations but also the stack for invalid reads/writes.

When I ran the test suite with the instrumented version asan reported an issue and aborted the program. Fortunately, you can just run the application under GDB, and break at the point where asan reports the error. And if the code has appropriate debug information, then GDB will tell you the line of code that caused the error.

To cut a long story short - I found that the memory error was being caused because I had not modified the Lua Debug API to work with JITed code. I had incorrectly assumed that the Debug API is only used if invoked explicitly. When an error is raised in Lua, the error routine uses the Debug API to obtain information about the code running at the time. This relies upon the 'savedpc' field which is not populated in JITed code - so any calls to the Debug API that relies on this can lead to unexpected memory access. The fix I implemented was to treat JITed functions as if they are C functions.

The reason for this post is however that I found Address Sanitizer to be an amazing tool. It is a life saver for C/C++ programmers.  

Ravi - an attempt to create optional typing for Lua

I am in love with Lua as blogged previously. While it is perfect little language, there is scope for improving the performance of Lua. Obviously great work in this area has already been done by Mike Pall who created Luajit. However, there are some issues with Luajit that are hard to overcome.

• Large parts of Luajit are written in assembler - which means that it would take significant investment of time and effort to understand how it works and fix issues or make enhancements to it.
• Mike Pall is undoubtedly a genius, but he is the sole developer of Luajit. The latest version 2.1 has not been released yet as Mike is presumably working on other things as reported on his sponsorship page. So the destiny of Luajit is pretty much tied up with how much effort Mike puts into Luajit.
• Luajit was based on Lua 5.1, and for good reasons it has stayed compatible with 5.1, avoiding ABI incompatible features in later versions. But this is increasingly going to be a problem as newer versions of Lua introduce new features.
• Luajit's FFI is great but not compatible with Lua, so any code exploiting FFI is not compatible with Lua. 

So my solution to above is to enhance core Lua to support optional typing so that the VM can use type specific bytecode. This will hopefully help the interpreter performance but more importantly it will enable simple JIT compilation of performance critical functions.

I am naming this new dialect of Lua as Ravi. Full details of the project can be found at the Ravi github site.

Lua is small and small is beautiful

Lua is a tiny language and like C has a tiny standard library. Like many other users of Lua, there are times when I wish it had some language feature (ability to specify types, for example) - but when I think about who Lua is meant for by its designers, I get the logic behind keeping it really small and simple.

Although Lua is powerful enough as a language that it can be used for many complex tasks - see DynASM for an assembler written in Lua - its primary design goal is to provide applications with an extension language. So for example you have a Spreadsheet application, and you wish to allow users to write their own functions they can use in the Spreadsheet. Or you have a Editor and you wish to allow users to customise the editor. And so on. In all these use cases, we cannot assume that the end user who is coding in Lua is a competent programmer. Hence Lua needs to be ultra-simple for such users. Having types in the language, for example, would immediately complicate the syntax of Lua.

That Lua fulfils the needs of its users is evident from the fact that a number of attempts have been made to create a Lua clone that is more powerful as a language - but none of these alternative improved Lua clones have any great following (Note that I exclude LuaJIT from this list as it is 100% faithful to Lua 5.1 so it is another implementation of Lua rather than a clone). I guess the question you have to ask is:

• Are you trying to create an extension language for ordinary users who are not programmers?

If not then perhaps Lua is not the language you need. 

Lua - A fabulous programming language

Last year I discovered Lua and LuaJIT.

These are both amazing implementations of the programming language Lua.

Ok now I need to explain why I think Lua is fabulous and these implementations are amazing.

Lua is a very small, dynamic, scripting language that is extremely easy to learn, and that can be used standalone as well as an embedded scripting language. The well documented and well crafted C API for extending the language is probably one of the best features of the Lua system.

It takes less that a minute to compile and build the Lua language and its basic libraries. Since the language is written in ANSI C, you can virtually build it on any platform.

LuaJIT is a JIT implementation of Lua created by a guy called Mike Pall who is without a doubt a programming wizard. LuaJIT features an interpreter that is hand-crafted in assembler, and has an amazing FFI library that allows easy extensions in C, including creating new data types. LuaJIT comes with an assembler called DynASM that is itself written in Lua.

Neither of these implementations depend on third-party libraries or tools ... which is an amazing thing in today's world (just look at the dependency list of Julia for comparison).

I hope to use Lua extensively in the future, so much so that I decided to learn assembler in order to be able to understand LuaJIT better.