Archive for October, 2013

luna learns to crawl

October 12th, 2013

So, writing an interpreter. Where do we even start?

Why, with the essentials. While an interpreter is nothing more than a program that reads your program and runs it, that is a pretty complicated undertaking. You could conceivably write an interpreter that reads a program character by character and tries to execute it, but you would soon run into all kinds of problems, like: I need to know the value of this variable, but that's defined somewhere else in the program, and: I'm executing a function definition, which doesn't have any effect, but I need to remember that I've seen it in case anyone is calling the function later in the program.

In fact, this approach is not wrong, it's basically what your machine really does. But your machine is running machine code, and you're not, and therein lies the difference. People don't write programs in machine code anymore. It's too hard. We have high level languages that provide niceties like variables - define once, reference as often as you like. Like functions. Like modules. All of these abstractions amount to a program that is not a linear sequence of instructions, but a network of blocks of instruction sequences and various language specific structures like functions and classes that reference each other.

And yet, since many languages are compiled down to machine code, there must be a way to get from here to there? Well, compiler writers have decided that doing so in one step is needlessly complicated. And instead we do what we always do in software engineering when the problem is too hard: we split it into pieces. A compiler will run in multiple phases and break down the molecule into ever simpler compounds until it's completely flat and in the end you can execute it sequentially.

Interpreters start out the same way, but the goal is not machine code, it's execution of the program. So they bottom out in an analogous language to machine code: byte code. Byte code can be executed sequentially given a virtual machine (language specific) that runs on top of a physical machine (language agnostic) that knows a few extra things about the language it's running.


Parsing - Read the program text and build a structured representation (abstract syntax tree) out of it.

Compilation - Compile the AST to bytecode instructions that can be executed on a stack machine.

Interpretation - Pretend to be a machine and execute the bytecode.

The parser is the thing that will read the program text, but it needs to know the syntax of the programming language to recognize what it's reading. This is supplied in the form of a grammar. The parser also needs to know the structure of your abstract syntax for it to build those trees for you. And this is where it gets tricky, because the AST is one of the central data structures in an interpreter, and the way you design the AST will have a big impact on how awkward or convenient it will be to do anything meaningful with it. Even so, the AST much match the grammar very closely, otherwise it's going to be very hard to write that parser. So the optimal would be to design the AST first, then write a grammar that matches it to the letter (even better: you could generate the grammar from the AST). Well, there are decades of research that explain why this is hard. Long story short: the more powerful the parser the more leeway you have in the grammar and the easier it is to get the AST you want. Chances are you will not write the parser from scratch, you'll use a library.

The compiler is the thing that traverses an AST and spits out bytecode. It's constrained by two things: the structure of the AST, and the architecture of the vm (including the opcodes that make up your bytecode). Compilers really aren't generic - they need to know all the specifics of the machine they are compiling for. For virtual machines this means: is it a stack machine or a register machine? What are the opcodes? How does the vm supply constants and names at interpretation time? How does it implement scope and modules?

Finally, the interpreter is the thing that emulates a machine and executes the bytecode. It will read the bytecode sequentially and know what to do with each instruction. It's really the only part of the entire program that interacts with its environment extensively. It's the thing that produces output, opens sockets, creates file descriptors, executes processes etc, all on behalf of your program. In fact, it would be more correct to say that these things are contained in the standard libraries of the language, but the interpreter is what orders them to happen.

luna 0.0.1

It's out. An interpreter for basic blocks. All your code runs in a single stack frame, so you can only run expressions, assignments and function calls. There is an object model for lua values. There is a pretty barebones standard library. And there are tests (py.test is making life quite good so far).

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.


  1. Lua 5.1 Reference Manual
  2. The Implementation of Lua 5.0
  3. Where Lua Is Used