llisp

A Lisp interpreter implemented in LLVM IR.

Inspiration

Peter Norvig’s lis.py both inspired me
to attempt this project and guided my implementation of it. The reader
algorithm in llisp is a simplified implementation of that described
in the
Reader Algorithm
section (2.2) of the Common Lisp HyperSpec.

Building

Run make to build it; run make test to run the test suite. You
will need LLVM installed.

For fun, run make count to count the number of source lines in the
project (excluding tests).

Using

After building it, run ./llisp to get an interactive REPL, or
./llisp somefile.llisp to execute the code in a file.

The language

llisp implements an extremely limited lisp-like language (maybe a
proto-lisp?), the goal of which is to explore an extremely simple
implementation of a lisp in an implementation language (LLVM IR) which
makes any “hidden” complexities painfully obvious.

As such, there isn’t much to it, but you can perform
computations with it.

false | nil | ()

The simplest value is (), which is an empty list, and is often
spelled nil. false is also defined as an alias for nil.

true

The symbol true evaluates to the token true, which, since it is
not nil, is “true” in the boolean sense of the word.

define

You can define a symbol using define, which adds the symbol to the
global namespace:

(define my-truth true)

if

You can conditionally evaluate expressions using if. The first
expression is always evaluated. If it evaluates to non-nil, the second
expression will be evaluated. If it evaluates to nil, the third
expression will be evaluated. The third expressions is optional, in
which case nil will be returned when the condition evaluates to
nil.

(if cond then else)

Example:

llisp> (if true false true)
nil

lambda

You can define an anonymous function using lambda. The first
form should be a list naming parameters, and the second form will be
evaluated when the function is invoked, and its return value will be
the return value of the invocation.

You invoke a function by making it the first argument to a list.

(lambda (params) body)

Example:

llisp> ((lambda (x) (if x false true)) nil)
true

You can name functions using define:

llisp> (define not (lambda (x) (if x false true)))
nil
llisp> (not true)
nil
llisp> (not false)
true

quote

quote is a special form which returns its body without it being
evaluated.

(quote body)

Example:

llisp> (quote foo)
foo

You can save a lot of typing with quote:

llisp> (cons true (cons true (cons true true)))
(true true true true)
llisp> (quote (true true true true))
(true true true true)

cons

cons returns a new list in which the first argument is the first
element of the list, and the second argument is the rest of the
list. For convenience, if the second argument is not a list, cons
will create a list of one element using the second argument.

(cons first rest)

Example:

llisp> (cons true nil)
(true)
llisp> (cons true true)
(true true)
llisp> (cons true (cons nil (cons true nil)))
(true nil true)

first

first returns the first element of a list.

(first a-list)

Example:

llisp> (first (cons true true))
true

rest

rest returns a list containing all the elements of the list except
the first element.

(rest a-list)

Example:

llisp> (rest (cons true true))
(true)
llisp> (rest (cons true nil))
nil

print

print prints its argument to standard out, followed by a newline,
and returns nil.

(print someval)

Example:

llisp> (print (cons true true))
(true true)
nil

eval

You can evaluate data as code using eval. The code is evaluated in
the current execution context, with any previously defined names
being available to it.

(eval code)

Example:

llisp> (define f (lambda (a b) (cons a b)))
nil
llisp> (eval (quote (f true true)))
(true true)