writing a lua interpreter

October 8th, 2013

I've been doing a bunch of reading around languages and interpreters lately, but I want to convert that insight into the kind of knowledge that only comes from the experience of implementation. I feel woefully unprepared for this, but on the other hand you can never prepare sufficiently for anything in life with research alone. I expect to hit many stumbling blocks, but that's kind of the point - without hitting them I wouldn't learn much.

Why lua?

Lua as a language has some interesting and unusual properties:

  • Designed to be small.
  • Designed to be portable.
  • Designed to be embeddable.

This is not just aspirational, lua really delivers on these promises.

How small?

  • the grammar has 21 keywords and a small set of productions,
  • 8 types: nil, boolean, number (double precision float), string, function, userdata, thread, and table,
  • a single kind of data structure: tables (associative arrays),
  • no type declarations (dynamically typed),
  • no manual memory management (garbage collected),
  • no object system,
  • no exceptions.

How portable? The lua interpreter is written in ANSI C. The implementors have consistently snubbed platform-specific services so that it builds just about anywhere, and from a single Makefile at that. That's right, no autotools. Try that with gcc.

How embeddable? In a word: very. The interpreter is only 15k sloc. The binary takes all of 6 seconds to build on my platform (linux x86, lua 5.2.2) and is 211kb. Lua is used more in embedded form that standalone and it's embedded in an enormous amount of software. Being small and portable makes it a great language to embed, because it's easy to learn and easy to use.

What's luna?

It's a little known fact that Lua, who is Brazilian, has an Italian sister called Luna. It's not hard to see why that would be - Luna has very little in common with her sister. She doesn't like to travel (not portable) and she doesn't like crowds (not embeddable). Luna has none of the qualities that make Lua so popular.

Not only that, Luna is very careless. When she's doing a task she doesn't care how long she takes, because life is good, so why hurry?

Of course, Python is no language to write an interpreter in. You should be using RPython or C. But it's the perfect language to prototype designs in when you're not really sure what you're doing yet.

Roadmap (tentative)

  • 0.0.1 - An interpreter that can execute a basic block. At this stage a program can consist of: assignment, expressions, function calls.
    • A parser and AST that cover all expressions and a small subset of statements.
    • A bytecode compiler.
    • A single stack frame virtual machine (stack based) with a single global environment.
  • 0.0.2 - Blocks and control flow: if, for, while, repeat.
    • A vm with multiple environments that understands lexical scope.
  • 0.0.3 - Function definitions.
    • A vm with multiple stack frames.

References

  1. Lua 5.1 Reference Manual
  2. The Implementation of Lua 5.0
  3. Where Lua Is Used
:: random entries in this category ::