Home

Awesome

lisp.c - A Lisp interpreter written in C

lisp.c is a Lisp interpreter experiment written entirely in C. It's core is a Lisp AST interpreter but is also contains a simple bytecode VM as well as a runtime bytecode compiler.

Contents:

Features

The Boehm-Demers-Weiser conservative garbage collector is used right now. Unfortunately the available time did not allow to write an own garbage collector.

Requirements

On an Debian based Linux system (e.g. Ubuntu Linux) the packages can be installed with the following command:

sudo apt-get install gcc make libgc1c2 libgc-dev

This has been tested on Ubuntu Linux 12.04.

Getting started

  1. Install the required packages (see above)
  2. Compile the interpreter and run tests:
  1. Run samples or use the interactive console

Using the lisp.c interpreter

The lisp.c interpreter can be run in different modes:

When in interactive mode each defined lambda is compiled to bytecode. In file mode the entire file is compiled into one begin statement and then executed.

The bytecode compiler can be disabled by using the -i option of the interpreter, e.g. ./lisp -i samples/fib.l will run the Fibonacci number calculation without the compiler. Alternatively the __compile_lambdas variable can be set to false to disable compilation of new lambdas: (set! __compile_lambdas false). Note that previously compiled lambdas still work. Only the bytecode compiler is disabled, not the interpreter.

The lisp.c interpreter can also be used for shell scripting via the hash bang line at the start of the file:

#!/home/steven/projects/lisp.c/lisp

The full path is required and the script needs execute permissions. samples/fac.l uses the hash-bang line but the path must be updated to your own location to the lisp binary.

Running the tests

Most parts of the interpreter, compiler and VM are covered by test cases. These can be explicitly run by changing into the tests directory and executing make.

The tests use a minimalistic test system, therefore the displayed number of tests is more or less equal to the asserts of normal test systems (assert already has a different meaning in C). An extra output stream and scanner hat to be written to make input and output testable.

The test cases contain large amount of code. Especially the bytecode interpreter and compiler test cases might be of interest.

Loading shared objects

A sample shared object can be found in mod_hello.c. It uses the init function to define a new builtin atom (named test) in the current execution environment. This new builtin just prints "test run".

The shared object can be compiled using make mod_hello. To load it into the interpreter:

$ ./lisp
> (mod_load "./mod_hello.so")
nil
> (test)
test run
nil

The "./" in the file name is important. Otherwise dlopen will search the system directories for the so file. With the "./" in front it searches only in the current directory.

Performance

To compare the performance between the AST and bytecode interpreter the Fibonacci number calculation sample was used. It calculates the 30th Fibonacci number. To measure the CPU time the time function of zsh was used (basically the same as the time program). The interpreter was compiled with -O2 settings for optimization.

The bytecode interpreter is about 1.7 times faster.

To get some perspective the same calculation was also implemented and run in PHP and Ruby:

Therefore the current lisp.c bytecode VM is about as fast as the old Ruby 1.8 AST interpreter which is still used for large amounts of Ruby code. However this is just one test case and one specific algorithm with strong emphasis on function calling overhead.

Known problems

General problems:

Source code:

Performance:

Bytecode VM:

Language reference

The lisp.c interpreter implements only a subset of Lisp. The following functions are supported.

Core functions:

Pair handling:

Arithmetic (only for number atoms):

Comparators (only for number atoms):

Misc:

Bytecode reference

Each bytecode instruction is 64 bits wide (56 bit with 8 bit padding) and consists of the following fields:

Depending on the instruction the second half is used as follows:

The instruction structure can be refactored into 32 bits without imposing to harsh limits. 2^16 lambda arguments and nested scopes are still more than enough. A jump range of 2^15 instructions (32k of code) up and down is also unlikely to cause problems, even for large amounts of generated Lisp code. However no more time was available for that refactoring.

Basic instructions:

Argument and local instructions:

Environment instructions:

Function generation and calling instructions:

Branching instructions:

Arithmetic and comparison instructions:

Pair handling instructions: