slisp

README

slisp

This repository contains slisp (either named for "Steve's Lisp Compiler", or "Simple Lisp Compiler"), which is a compiler reading Lisp programs as input, generating standalone assembly representations for Linux/AMD64 as output.

Lisp is traditionally used in an interactive way, via a REPL. By contrast this repository allows you to turn a lisp program into a compiled executable which will run non-interactively.

But note that I did write a Lisp Interpreter, complete with a REPL, which you can see described below in the INCEPTION section.

Quick links:

• INTRODUCTION.md
  • Brief high-level overview of the facilities.
• PRIMITIVES.md
  • Detailed list of all available functions and special-forms.

Example

This is a minimal, standalone, example of what a program might look like:

    (defun fact (n)
      "Calculate, and return, the value of N!"
      (if (<= n 1) 1 (* n (fact (- n 1)))))

    ;; entry-point
    (defun main (args)
      "Command line arguments are available in the list ARGS."
      (println "factorial demonstration, 10!:" (fact 10))

      ;; exit code - use "(exit 0)" if you prefer
      0)

You can find bigger examples beneath examples/, and our test/ directory contains a large number of programs which are used for testing purposes (they are compiled and executed, and their output compared to known-good results stored alongside them).

• Notable examples

  • examples/brainfuck.lisp contains a useful/working brainfuck interpreter.
  • examples/example.lisp has other misc. snippets.
  • examples/life.lisp - Game of Life.
  • examples/packages.lisp demonstrates how our packaging system works - more details in INTRODUCTION.md.
  • examples/globals.lisp - Explicit demonstration of scopes, showing that local variables always take precedence over global ones.
  • examples/nqueens.lisp is a solver for the N Queens problem, defaults to solving the 8x8 grid but you may specify different sizes via a CLI argument.
  • examples/wc.lisp is a clone of the standard wc utility, which demonstrates our included argument-parser packages/.

• Notable tests:

  • test/entries.lisp - Read all the files in a directory, filter them, sort them, and print their names.
  • Standard programs: test/factorial.lisp, test/fibonacci.lisp, test/fizzbuzz.lisp.
  • File I/O: test/fread.lisp and test/fwrite.lisp.
  • test/sort3.lisp - A mergesort implementation.
  • test/vararg.lisp - Demonstration of a function accepting a variable number of arguments.

It should be noted that we prepend a standard library of functions to all user programs unless -stdlib=false is added to the command line. That library itself is a useful reference/demonstration of functionality:

• stdlib.slisp - Our standard library, written in slisp itself.
  • Has a good print definition which handles known types appropriately.
  • Has map, length and similar general-purpose functions.

Features

• Support for bindings, functions, floating-point numbers, integers, strings, lambdas, lists, etc.
  • The lambdas have support for closures.
  • Run-time type detection via functions such as int?, and cons?.
• A rough and ready bump-allocator used for heap-allocated cons-cells.
• Mathematical operations +, -, *, and /.
  • These work against integers, floating point numbers, or combination of the two.
• File I/O operations:
  • fopen, fclose, fread, and fwrite.
• Filesystem primitive:
  • dir?, entries, exists?, file?, mkdir, mkdirs, rmdir, stat, unlink and which.
• Comparison operations:
  • =, <, <=, >=, >, and ! to invert a result.
• Special forms (only some of which are valid at the top-level, those are marked with *):
  • (alias! ..) - * - Alias/overwrite a function.
  • (cond ..)
  • (defun ..) - * - declare a function.
  • (defconst ..) - * - declare a global constant.
  • (defvar ..)- * - declare a global variable.
  • (do ..)
  • (if ..)
  • (lambda ..)
  • (let ..)
  • (list ..)
  • (require ..) - * - Include other source files.
  • (package ..) - * - Declare a package-scope.
  • (set! ..)
  • (while ..)

You can see a complete list of our primitives, and their details in PRIMITIVES.md - documenting both the built-in special-forms, and the parts of the standard library which are implemented in assembly, or slisp itself.

Anti-features:

• No garbage collection.
• No macros.
  • It wouldn't be impossible to add them, but without quote, quasiquote, etc, it's a lot of work.
• No quote
  • Only really useful if you can call eval and as a compiler? That's not going to happen easily.
• We don't have "symbols" exposed to the language, but if you prefix a variable with ":" it will become visually distinct, and this is useful when working with alists, or plists.
  • Internally that is actually translated to a stringified version of the variable name (So (print :name) becomes (print "name") - that might seem weird but it works for alist/plist usage, etc.)
• Packages are bespoke, and not like lisp/common-lisp/scheme.

Usage

Build the compiler:

go build .

Then use it to compile and link a program:

./slisp -compile example.lisp

That will create "example.asm", and "example.o", before creating "example". If you prefer to run the commands manually you can do it this way:

./slisp example.lisp  > example.s
nasm -f elf64 example.s
ld -o example example.o

Finally you may execute your compiled program:

./example

Testing

There are some functional test programs beneath test/, which compile fixed programs and compare their output to known-good results. You can run these tests by executing:

cd test && make test

Running make clean at the top-level will remove the test artifacts, and compiled programs.

In addition to the functional tests there are also golang tests of the internal implementation packages, these can be executed in the standard fashion:

$ go test ./...
ok      github.com/skx/slisp	0.004s
ok      github.com/skx/slisp/compiler	0.009s
ok      github.com/skx/slisp/env	(cached)
ok      github.com/skx/slisp/lexer	0.008s
ok      github.com/skx/slisp/parser	0.006s

There is also support for the fuzz-testing that golang provides, you can run five minutes of fuzz-testing by executing the following (remove the -fuzztime=300s to run forever, and remove -parallel=1 to run more than a single instance at a time):

$ go test -fuzztime=300s -parallel=1 -fuzz=FuzzProject -v

Inception

As noted this is a compiler which means that for a given lisp program we produce an executable, there is no REPL.

But I thought it might be fun to prove that my slisp is a real lisp, and so I implemented a lisp interpreter which can read lisp source code from files and execute it, and which also implements a REPL.

Build the compiler, and build the interpreter:

go build .
cd examples/
make

Now you should find, amongst other binaries, you have the executable inception which is an interpreter. Fire it up:

$ ./inception --repl
Welcome to lisp in slisp!
Enter :quit to exit.

> (defun square (x) (* x x))
(symbol square)
> square
(closure (x) (((symbol *) (symbol x) (symbol x))) <nil>)
> (square 3)
9
> (square (square (square 3) ) )
6561
> :quit

In addition to having a REPL you can also load files (and then optionally have the REPL start). So here's running the self-contained example:

$ ./inception inception.in
Loading .. inception.in
100
Squaring some numbers: (16 25 400 900 1600)
LAMBDA X 1*1: -> 1
LAMBDA X 2*2: -> 4
LAMBDA X 3*3: -> 9
LAMBDA X 4*4: -> 16
LAMBDA X 5*5: -> 25
This is what a function looks like: (closure (x) (((symbol +) (symbol x) (symbol n))) ((n 10)))
Adder (+10) result for  5:15
..

And here is loading an existing test - which will define the function main and launching that via the REPL:

$ ./inception ../test/closure2.lisp  --repl
Loading .. ../test/closure2.lisp
Welcome to lisp in slisp!
Enter :quit to exit.

> (main)   ; loading "closure2.lisp" will produce a (defun main) now we call it.
25
35
5
10
22
40

So what are the differences between our compiler and our interpreter? Well in some ways the interpreter is more advanced as it has support for (quote), it has a symbol-type, and you can get references to functions using them. The lambdas/defuns are real standalone objects which are treated largely interchangeably and which you can print. But the biggest difference is that the compiler has a significantly larger standard-library.

The compiler prepends stdlib.slisp to all programs, so you always have map, filter, etc, available. By contrast the interpreter has a very small standard library - it exposes print, println, cons, list and the special forms. It understands strings, integers, and floating-point numbers but it doesn't have a character-type.

That said, and as demonstrated above, the interpreter can run many of the same programs that the compiler can. The main omissions are mutating captured variables inside closures, and the need to enter functions all on one line if you're using the REPL.

Motivation

I've spent a few weeks writing a compiler for a home-made language, s-lang. Initially that language only used integers, but later I added floats/strings/pointers with appropriate type-markers in the lower bits of the values.

I found the overhead of dealing with typing and syntax a bit complex, and kinda backed myself into a corner with it - I wrote a reasonably complete standard-library with File I/O, getenv, and other things.

However adding more types, and dynamic things felt like it would be too complex as it would involve ripping out so much of what I'd done. The compiler, the standard library, and the interface between the two.

So this repository was born:

• Implement a compiler.
• With proper typing from the ground-up. Using macros for readability and to minimize the chances of making mistakes.
• Use the well-known SysV ABI, rather than my home-grown alternative.
• Use lisp because the syntax is trivial to parse.
  • And I've written interpreters for it in the past so there are dragons, but somewhat friendly ones.

Already this compiler is more "real" and "usable", although it lacks the quality, standard-library, test-cases, and creativity of s-lang. I guess at the end of the day both are toys, and both are here for my own personal learning.