0xekez / lisp

A lisp JIT compiler and interpreter built with cranelift.

A little lisp compiler and interpereter. The compiler is just in time and written with Cranelift.

>> (import 'format)
>> (let say-hello (fn (name)
                      (printf "hello {}!" name)))
>> (say-hello "Lisp")
hello Lisp!

Performance Example

Consider everyone's favorite fib function in this lisp and in Python:

(let fib (fn (n)
	     (if (lt n 2)
		 n
	       (add (fib (sub n 2)) (fib (sub n 1))))))

def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

The JIT compiler can compute (fib 40) in 2.3 seconds. It takes Python 35 seconds.

Take this with a grain of salt because there are many things Python can do very elegantly that are still awkward in here and I'm sure there are places where python's C bindings give it a leg up. The point is that in this case both languages are very similar looking but one is much, much quicker.

The compiler also doesn't have a garbage collector yet but who really needs one if you can run everything faster than a gc cycle ;)

here are example programs.

lisp's Issues

Use Vec for enviroments instead of HashMap

Most environments are small. Vec is lighter than hash map.

Internal error assigning variable of same name in compiler

The program

(let cons cons)
(cons 1 2)

yields

error: internal error: use of undeclared variable (0_cons)

Add an import expression

Should evaluate a file and then merge its global symbol table with ours.

License

Is it ok to reuse this under the MIT license? I don't see a license file anywhere

Pay for what you use: varadic functions

Varadic functions require that we heap allocate function arguments. This is slow. Most existing Lust programs do not use varadic functions - in that situation we don't need to heap allocate arguments.

Trouble with doing this is that it adds a lot of code complexity (two implementations of function calls) and once there is a standard library which will use varadic functions most Lust programs are liable to use varadic functions.

Garbage Collection

We now have heap allocation wired up in lustc. This means that its time to start thinking about garbage collection. For now I have wrapped malloc in an alloc function. In 164 Hilfinger uses a similar method and I believe that later we ought to be able to add some machinery to alloc to track allocations and later garbage collect.

Add char parsing to tokenizer / parser

See docs/grammar.md for what this ought to look like.

Allow non list objects in the tail position of lists

>> (cons 1 1)
(cons 1 1)
^----
|  error: expected list, got 1
*--> repl:0:0

Currently errors but should not.

Type checks are inlined causing code bloat

Currently type checks are inlined for every primitive. This leads to a lot of code being generated. We should likely move this into a function.

Add unit testing for Lust programs

At the moment there is no way to test that errors are being displayed properly because they print to stdout and don't leave much of a trace. As time goes on and there is more need for this sort of thing we should consider adding some sort of btest like unit test framework so that we can compare the output of lust programs to a baseline.

Support new let expression semantics

Recently in lustc we modified let semantics and added a set expression. Docs here.

Strangeness when multiple expressions are on the same line in repl

lust> -'hello
=> (fn (& args) (fold (fn (a i) (sub a i)) (cdr args) (car args)))
=> hello

I guess this makes sense if we're letting multiple expressions be on a line in the repl but it's not the most straightforward thing.

Better support for `LUSTPATH` enviorment variable

• Add documentation
• Add way for it to be installed terminally by some variation of cargo install

Stop assuming that expressions are on a single line

Reasonably low priority but needs to be done before this can properly parse files and as a precursor for a decent REPL

Use Vec more appropriately when representing lists

Most operations on lists in Lust occur at the beginning. car, cdr, and cons all operate on the first item in the list. Meanwhile, Rust's vector class is designed for things to change at the end. As a result we're abusing the data structure when we're constantly popping and inserting data at the front.

One way to get around this would be to represent Lust lists as a reversed vector. Under the hood, lists would be represented by Vec still, but the first item in a Lust list would correspond to the last item in the corresponding vector. I believe this would be markedly more performant.

Last night I tried to see if this would be a simple change, but I don't think it will. There are quite a few places where indexing the complex with varadic functions and etc. It also makes code really ugly to be constantly using the reverse of the index you want. We'd probably be well served to wrap Vec in some sort of LustVec class and then use that instead of Vec.

This would be a good learning experience working with more complex data types in Lust as well.

Write a high level bytecode compiler

Here is a nice write up of roughly what I'd imagine. Doing this would serve two purposes:

1. It would allow us to emit better error messages because we could keep location information around while compiling expressions
2. It would be the first step in moving towards compiling Lust. Later a JIT might be happier compiling that byte code to machine code.

I think it would be fine to keep the byte code very high level. Environments could remain roughly how they are now and we could possibly avoid typing by still keeping things in an enum. The goal wouldn't be performance so much as it would be to lower the Lust code into a simpler form more for executing and catch some additional errors along the way.

Support compilation to object files

Having a JIT is nice and makes testing pretty easy but at the end of the day the ability to compile to native object files is very important to me because it opens up the possibility of writing a self hosting version of Lust (this is very far down the line though.)

A branch of the simple jit demo shows approximately how this is done. Based on this I don't believe that doing this will require too much additional work as the architecture seems to be similar enough.

Lustc expects compiled programs to return an immediate type

The following program panics because the return value (result of last expression compiled) is a closure:

(let printf (fn (list & args) 1))

Reference guide link broken

https://zmedley.com/lust

The link there to the reference guide gives me 404.

(Also does Lust work running in WASM?)

Handle blank lines in repl

Currently panics on the cleanup branch. Something to do with locations being one past the end I suspect. Not high priority right now.

Don't compile primitive functions that we don't need

Right now at the beginning of compilation we emit all of the primitive functions into the JIT. We don't need to do this. We should add a pass to the compiler that locates primitives that appear in non-head positions of lists and only compiles those ones.

Change `import` to `require`

Right now our import function is liable to get caught in a loop if files import each other. This isn't so good. I'd like to change import to require like Emacs Lisp. This way we could more clearly indicate that we're just requiring that the file is loaded. import gives the idea that you're actively evaluating the file when you import it.

Varadic functions in compiler

Parse negative numeric literals

Optionally we could use ~ to indicate negation, but that seems like a lot of confusion for a little bit of saved time on the tokenizer.

Add a quaziquote expression to Lust

Should follow along with Emacs:

https://www.gnu.org/software/emacs/manual/html_node/elisp/Backquote.html

Would make a lot of macros a lot easier and some that were impossible possible.

car and cdr have different behavior when called on empty list

In the interpreter (car ()) and (cdr ()) yield () whereas in the compiler both calls result in a type error.

Currently, my preference is for the compilers behavior. It seems like if you ask for the second item of an empty list that is indeed an error. Right now it can be a little confusing but once we get around to improving the compiler's error messages I suspect we can make that error more obvious.

Update string documentation

Changed strings so that they no longer need the quote in front of them