This is my attempt at making Rui Ueyama (rui314)'s MiniLisp more user friendly and powerful, while trying to keep the goal of simplicity and conciseness. Not being limited by the 1000 lines challenge, I've added a Read-Eval-Print-Loop (REPL) and a number of primitives to the original program to make it a comfortable Lisp implementation.
The whole program is 3000 lines of C and compiles to around 130 kb without debugging symbols. It should be able to run on low powered devices.
The original MiniLisp included the following:
- integers, symbols, cons cells
- global variables,
- lexically-scoped local variables,
- closures,
- if conditional,
- primitive functions, such as +, =, <, or list,
- user-defined functions,
- a macro system,
- and a copying garbage collector.
The added primitives of this version:
- cons, car, cdr
- strings, substrings, string comparisons and conversions
- floats and operators on floats
- vectors
- operators *, /, mod
- predicates >, >=, <=,
- special forms and, or, not,
- functions list, atom, length, reverse, progn, print, println, load, exit, gensym
- input and output: read-line, read-file, write-file, append-file, file-exists?, args
- tail call optimization
This added expressivity has the side effect of being much faster as well, since all these primitives are compiled C instead of being interpreted.
$ make
MiniLisp has been tested on Linux x86/x86-64 and 64 bit Mac OS. The code is not very architecture dependent, so you should be able to compile and run on other Unix-like operating systems.
MiniLisp comes with a comprehensive test suite. In order to run the tests, give "test" argument to make.
$ make test
The tests run twice, the second time with the environment variable
MINILISP_ALWAYS_GC=1, which makes the garbage collector run at every memory
allocation and makes the old heap inaccessible, so that any stale pointer
crashes immediately. MINILISP_DEBUG_GC=1 prints a line on the standard error
output at each collection. The heap starts at 4 MB (per semi-space) and doubles
when more than half of it is still in use after a collection, up to 1 GB.
Pass the source files f1, f2, ... as command arguments : ./minilisp f1 f2 ...
The files all share the same environment, so all the symbols, functions and macros defined in f1 can be reused in the following files. The REPL is started after execution, unless we pass the option -r to the command line, in which case the interpreter quits immediately at the end.
You can also pass a simple Lisp command as parameter: ./minilisp -x "(+ 1 1)"
The Lisp command will be evaluated and then the REPL is started. However we can quit immediately after execution with -r (or --no-repl).
The options, which can be given before or after the file names, are:
-x, --exec CODE evaluate the Lisp code CODE
-r, --no-repl don't enter the read-eval-print loop
-H, --no-history don't load nor save the history of the REPL
-m, --heap KB initial size of the heap, in KB (default 4096, minimum 32)
-M, --max-heap KB maximum size of the heap, in KB (default 1048576)
-h, --help print the help and exit
What follows -- on the command line is not read by minilisp: the Lisp program
gets it with (args).
When an expression fails, the error is reported on the standard error output
as file[line]: message and the evaluation goes on with the next expression.
The options -m (--heap) and -M (--max-heap) set the initial and the maximum
size of the heap, in KB. The minimum is 32 KB, which is enough to start the
interpreter and to load examples/library.lisp; a non tail recursion 1000 calls
deep needs about 100 KB. This makes MiniLisp usable on small machines, such as a
Raspberry Pi with little memory, and is a way to test the garbage collector with
a tiny heap.
./minilisp -m 256 -M 256 prog.lisp # a heap of fixed size: 256 KB
./minilisp -m 64 prog.lisp # starts with 64 KB, may grow up to 1 GB
./minilisp -M 1024 prog.lisp # a heap of 1 MB at most (it starts with 1 MB)
The collector copies the live objects from a semi-space to the other one, so the
memory used is twice the size of the heap (and up to four times during a growth).
A heap which cannot grow, because it has reached its maximum, ends with the error
"Memory exhausted" when the live data do not fit anymore. -m alone does not limit the
growth, -M does. If only -M is given, the heap starts at 4 MB or at the
maximum if that is smaller.
The Read-Eval-Print-Loop (REPL) is based on Justine Tunney (jart)'s bestline.
CTRL-Enter CONTINUE ON NEXT LINE
CTRL-E END
CTRL-A START
CTRL-B BACK
CTRL-F FORWARD
CTRL-L CLEAR
CTRL-H BACKSPACE
CTRL-D DELETE
CTRL-Y YANK
CTRL-D EOF (IF EMPTY)
CTRL-N NEXT HISTORY
CTRL-P PREVIOUS HISTORY
CTRL-R SEARCH HISTORY
CTRL-G CANCEL SEARCH
ALT-< BEGINNING OF HISTORY
ALT-> END OF HISTORY
ALT-F FORWARD WORD
ALT-B BACKWARD WORD
CTRL-ALT-F FORWARD EXPR
CTRL-ALT-B BACKWARD EXPR
ALT-RIGHT FORWARD EXPR
ALT-LEFT BACKWARD EXPR
CTRL-K KILL LINE FORWARDS
CTRL-U KILL LINE BACKWARDS
ALT-H KILL WORD BACKWARDS
CTRL-W KILL WORD BACKWARDS
CTRL-ALT-H KILL WORD BACKWARDS
ALT-D KILL WORD FORWARDS
ALT-Y ROTATE KILL RING AND YANK AGAIN
ALT-\ SQUEEZE ADJACENT WHITESPACE
CTRL-T TRANSPOSE
ALT-T TRANSPOSE WORD
ALT-U UPPERCASE WORD
ALT-L LOWERCASE WORD
ALT-C CAPITALIZE WORD
CTRL-C INTERRUPT PROCESS
CTRL-Z SUSPEND PROCESS
CTRL-\ QUIT PROCESS
CTRL-S PAUSE OUTPUT
CTRL-Q UNPAUSE OUTPUT (IF PAUSED)
CTRL-Q ESCAPED INSERT
CTRL-SPACE SET MARK
CTRL-X CTRL-X GOTO MARK
CTRL-Z SUSPEND PROCESS
CTRL-D on an empty line leaves the REPL. Lines starting with a slash are REPL commands:
/memory display the amount of memory used and the size of the heap
/help display a short help
The REPL also saves the history of commands in the file history.txt This file is loaded at startup, so one can recall previous commands (unless the option -H is given).
Known bugs and limitations:
- recall of multiline commands does not work as expected.
- a recursion which is not a tail call (such as
(+ 1 (f (- n 1)))) uses the C stack: deeper than about 25000 calls it stops with the error "Stack overflow: the recursion is too deep".
MiniLisp is a traditional Lisp interpreter. It reads one expression at a time
from a file, from the -x option or from the REPL, evaluates it, and then
prints out the return value of the expression. Here is an example of a valid
input.
(+ 1 2)
The above expression prints "3".
MiniLisp supports integer literals, float literals, string literals, vector literals, (), t, symbols, and
list literals.
- Integer literals are positive or negative 64 bit integers.
- Float literals are double precision numbers. They have a fractional part, an
exponent, or both:
1.5,-0.25,1e3,2.5E-4. A digit is required on both sides of the point, so1.and.5are not floats. - Vector literals are written between square brackets:
[1 2 3]. Contrary to the list literals, their elements are evaluated (see Vectors below). - String literals are written between double quotes. The escape sequences
\n,\t,\r,\"and\\are recognized. ()is the only false value. It also represents the empty list.tis a predefined variable evaluated to itself. It's a preferred way to represent a true value, while any non-()value is considered to be true.- Symbols are objects with unique name. They are used to represent identifiers.
- List literals are cons cells. It's either a regular list whose last element's
cdr is
()or an dotted list ending with any non-()value. A dotted list is written as(a . b).
cons takes two arguments and returns a new cons cell, making the first
argument the car, and the second the cdr.
(cons 'a 'b) ; -> (a . b)
(cons 'a '(b)) ; -> (a b)
car and cdr are accessors for cons cells. car returns the car, and cdr
returns the cdr.
(car '(a . b)) ; -> a
(cdr '(a . b)) ; -> b
setcar mutates a cons cell. setcar takes two arguments, assuming the first
argument is a cons cell. It sets the second argument's value to the cons cell's
car.
(define cell (cons 'a 'b))
cell ; -> (a . b)
(setcar cell 'x)
cell ; -> (x . b)
length and reverse operate either on their arguments, or a single list, string or vector.
reverse never modifies its arguments: it returns a new list, string or vector.
(length '(1 2 3)) ; -> 3
(length 1 2 t) ; -> 3
(length "1 2 3") ; -> 5
(reverse '(a b c)) ; -> (c b a)
(reverse 1 2 3) ; -> (3 2 1)
(reverse "1234") ; -> "4321"
(reverse [1 2 3]) ; -> [3 2 1]
(reverse '((a) b "c")) ; -> (c b (a))
Integers are 64 bit signed integers. The result of an operation that overflows wraps around. Floats are double precision numbers. Numeric operators accept integers and floats: when at least one argument is a float, the integers are converted and the result is a float, otherwise the result is an integer.
+ returns the sum of the arguments.
(+) ; -> 0
(+ 1) ; -> 1
(+ 1 2) ; -> 3
(+ 1 2 3) ; -> 6
* returns the product of the arguments.
(*) ; -> 1
(* 2 3 4) ; -> 24
- negates the value of the argument if only one argument is given.
(- 3) ; -> -3
(- -5) ; -> 5
If multiple arguments are given, - subtracts each argument from the first one.
(- 5 2) ; -> 3
(- 5 2 7) ; -> -4
/ divides the first argument by each of the following ones, and mod returns
the remainder of the same division. The division of integers is truncated
towards zero (the remainder has the sign of the dividend), the one of floats is
not. Dividing by zero is an error.
(/ 7 2) ; -> 3
(/ -7 2) ; -> -3
(mod 7 2) ; -> 1
(mod -7 2) ; -> -1
(/ 7 2.0) ; -> 3.5
(mod 7.5 2) ; -> 1.5
= takes two arguments and returns t if the two numbers are equal, whatever
their types.
(= 11 11) ; -> t
(= 11 6) ; -> ()
(= 1 1.0) ; -> t
< takes two arguments and returns t if the first argument is smaller than
the second.
(< 2 3) ; -> t
(< 3 3) ; -> ()
(< 4 3) ; -> ()
The other numerical predicates >, <=, >= work in a similar fashion.
(if cond then else ...) is the only conditional in the language. It first
evaluates cond. If the result is a true value, then is evaluated. Otherwise
the else expressions are evaluated in sequence, and the value of the last one
is returned (() if there is none).
(and expr ...) evaluates its expressions from left to right and stops at the first
one which is (), which is then the result. Otherwise the result is the value of the last
expression. (and) is t.
(or expr ...) evaluates its expressions from left to right and stops at the first
one which is not (), which is then the result. If there is none the result is ().
(and 1 2 3) ; -> 3
(and 1 () (car 1)) ; -> () the third expression is not evaluated
(or () 'a 'b) ; -> a
The last expression of and and or is in tail position.
(while cond expr ...) executes expr ... until cond is evaluated to
(). This is the only loop supported by MiniLisp.
If you are familiar with Scheme, you might be wondering if you could write a
loop by tail recursion in MiniLisp. The answer is yes: a call in tail position
does not consume any stack space. This is the case of the last expression of the
body of a function, of progn, of the branches of if, and of whatever a macro
expands to such an expression. So a loop can be written as a recursion with
an accumulator, and run for as long as needed:
(defun sum (n acc)
(if (= n 0)
acc
(sum (- n 1) (+ n acc)))) ; tail call
(sum 1000000 0) ; -> 500000500000
A recursion which is not a tail call, such as (+ 1 (f (- n 1))), still needs
a stack frame for each level and fails with the "Stack overflow" error after
about 25000 calls.
(progn expr expr ...) executes several expressions in sequence.
(progn (print "I own ")
(defun add (x y) (+ x y))
(print (add 3 7))
(println " cents")) ; -> prints "I own 10 cents"
A float is always printed with a point or an exponent (2.0, 1e+21), and with
as many digits as needed to read it back unchanged. Overflows give inf or
-inf.
float converts a number to a float. truncate (towards zero), floor and
round (to the nearest integer, halves away from zero) convert a number to an
integer, and are an error if the float does not fit in 64 bits.
(float 3) ; -> 3.0
(truncate -2.7) ; -> -2
(floor -2.7) ; -> -3
(round 2.5) ; -> 3
sqrt, exp, log, sin, cos and atan take one number and return a
float. (expt x y) returns x raised to the power y. sqrt of a negative
number and log of a number which is not positive are errors.
(sqrt 2) ; -> 1.4142135623730951
(expt 2 10) ; -> 1024.0
float? and integer? tell the type of a number.
(float? 1.5) ; -> t
(integer? 1.5) ; -> ()
A vector is a fixed size sequence of values, whose elements are reached in constant time, unlike those of a list. The first element has the index 0.
[a b c] is read as (vector a b c). The elements are evaluated, and each
evaluation makes a new vector, so a vector written in a function body is never
shared between two calls. To have symbols or lists in a vector, quote them.
[1 (+ 1 1) "three"] ; -> [1 2 three]
['a '(b c)] ; -> [a (b c)]
(vector 1 2) ; -> [1 2]
(make-vector n) makes a vector of n elements which are (), and
(make-vector n x) one whose elements are all x.
(make-vector 3 0) ; -> [0 0 0]
aref reads an element, aset stores a value in the vector and returns it.
An index out of range is an error.
(define v (make-vector 3 0))
(aset v 1 'x) ; -> x
(aref v 1) ; -> x
v ; -> [0 x 0]
length returns the number of elements, vector? tells whether an object is a
vector, and vector->list and list->vector convert between lists and vectors.
(length [1 2 3]) ; -> 3
(vector? [1]) ; -> t
(vector->list [1 2 3]) ; -> (1 2 3)
(list->vector '(a b)) ; -> [a b]
Note that '[a b] is the list (vector a b), not a vector of symbols: write
['a 'b] or (list->vector '(a b)). Two vectors are eq only if they are the
same object.
eq takes two arguments and returns t if the objects are the same. Integers
and floats are compared by value (but an integer is never eq to a float, as
opposed to =), and strings by content. For all the other objects eq does
a pointer comparison, so two lists that happened to have the same contents but
are actually different are considered to not be the same by eq.
(eq 1000 1000) ; -> t
(eq 'a 'a) ; -> t
(eq '(1) '(1)) ; -> ()
eq compares strings by content.
(eq "Hello" "Hello") ; -> t
(eq "Hello" "hello") ; -> ()
string-concat concatenates strings.
(string-concat) ; -> ""
(string-concat "A" "B" "C" "D") ; -> "ABCD"
symbol->string turns a symbol into a string.
(define sym 'hello) ; -> hello
(symbol->string sym) ; -> "hello"
string->symbol turns a string into a symbol of the same name.
(string->symbol "hello") ; -> hello
<, <=, > and >= (and =) also compare two strings, byte by byte.
(< "abc" "abd") ; -> t
A character is a string of length 1. Strings are made of bytes: MiniLisp
knows nothing about UTF-8, so length counts bytes and substring may cut a
multibyte character in two. length gives the length of a string.
substring returns the part of a string from the index start up to the index
end (excluded), or up to the end of the string when end is omitted. The
first index is 0. It is an error if the range is not inside the string.
(substring "hello" 1 3) ; -> "el"
(substring "hello" 2) ; -> "llo"
string-ref returns the character at an index, as a string of length 1.
(string-ref "hello" 1) ; -> "e"
string->number returns the integer or the float which is written in a string
(with an optional sign), or () if the string is anything else.
(string->number "42") ; -> 42
(string->number "-1.5e3") ; -> -1500.0
(string->number "4x") ; -> ()
list->string concatenates the strings and numbers of a list, like
string-concat does with its arguments. Building a long string by collecting
its parts in a list and calling list->string once is much faster than
calling string-concat for each part, because every call copies the whole
string.
(list->string (list "a" "b" 1)) ; -> "ab1"
The file examples/library.lisp defines more functions, written in Lisp on top
of these ones: number->string, string->list, string-search,
string-prefix?, string-suffix?, string-split, string-join and
string-trim.
(string-search "lo" "hello" 0) ; -> 3 (the index, or () if not found)
(string-split "a,b,c" ",") ; -> ("a" "b" "c")
(string-join (list "a" "b") ", ") ; -> "a, b"
(string-trim " hi \n") ; -> "hi"
print prints its arguments to the standard output, separated by a space.
Strings are printed without the quotes.
(print 3) ; -> "3"
(print '(hello world)) ; -> "(hello world)"
(print "hello" "world") ; -> "hello world"
println does the same, adding a return at the end. Without argument, it only
prints a return.
read-line reads a line of the standard input and returns it as a string,
without its end of line. It returns () at the end of the input, so that an
empty line ("") can be told from the end. The standard output is flushed
first, so that a prompt printed just before is displayed.
(define line (read-line))
(while line
(println "got: " line)
(setq line (read-line)))
read-file returns the whole content of a file as a string. write-file
replaces the content of a file (it creates it if needed) with a string, and
append-file adds a string at its end. Both return t. It is an error if the
file cannot be opened.
(write-file "notes.txt" "one\n") ; -> t
(append-file "notes.txt" "two\n") ; -> t
(read-file "notes.txt") ; -> "one\ntwo\n"
file-exists? tells whether a file exists. All the file names are relative to
the current directory (unlike load).
(file-exists? "notes.txt") ; -> t
Strings stop at the first null character, so a file which contains one is read up to it.
args returns the list of the arguments of the command line which follow --,
as strings. It is () when there are none.
$ ./minilisp -r script.lisp -- 12 hello
;; in script.lisp: (args) -> ("12" "hello")
To read a number: (string->number (car (args))).
MiniLisp supports variables and functions. They can be defined using define.
(define a (+ 1 2))
(+ a a) ; -> 6
There are two ways to define a function. One way is to use a special form
lambda. (lambda (args ...) expr ...) returns a function object which
you can assign to a variable using define.
(define double (lambda (x) (+ x x)))
(double 6) ; -> 12
((lambda (x) (+ x x)) 6) ; do the same thing without assignment
The other way is defun. (defun fn (args ...) expr ...) is short for
(define fn (lambda (args ...) expr ...)).
;; Define "double" using defun
(defun double (x) (+ x x))
You can write a function that takes variable number of arguments. If the parameter list is a dotted list, the remaining arguments are bound to the last parameter as a list.
(defun fn (expr . rest) rest)
(fn 1) ; -> ()
(fn 1 2 3) ; -> (2 3)
Variables are lexically scoped and have indefinite extent. References to "outer" variables remain valid even after the function that created the variables returns. Calling a function with more or fewer arguments than it has parameters is an error, unless the last parameter is a dotted one as above.
;; A countup function. We use lambda to introduce local variables because we
;; do not have "let" and the like. (The file examples/library.lisp defines
;; "let", "when", "and", "or" etc. as macros).
(define counter
((lambda (count)
(lambda ()
(setq count (+ count 1))
count))
0))
(counter) ; -> 1
(counter) ; -> 2
;; This will not return 12345 but 3. Variable "count" in counter function
;; is resolved based on its lexical context rather than dynamic context.
((lambda (count) (counter)) 12345) ; -> 3
setq sets a new value to an existing variable. It's an error if the variable
is not defined.
(define val (+ 3 5))
(setq val (+ val 1)) ; increment "val"
atom returns () if the argument is a cell, t otherwise.
(atom '(a b)) ; -> ()
(atom "") ; -> t
(atom ()) ; -> t
load loads a Lisp file and evaluates all its content, adding it to the environment.
(load "examples/nqueens.lisp") -> run the file and store its evaluated functions
and macros
A relative path is first looked up in the directory of the file that calls load,
then in the current directory. For instance, (load "./library.lisp") in
examples/hanoi.lisp loads examples/library.lisp, wherever minilisp is started from.
error stops the evaluation with an error message made of its arguments, which
are strings or numbers, like those of string-concat.
(error "Unknown function " 42) ; -> prints "Unknown function 42" as an error
exit quits the interpreter and returns the integer passed as parameter.
(exit 0) -> quit with success
Macros look similar to functions, but they are different that macros take an
expression as input and returns a new expression as output. (defmacro macro-name (args ...) body ...) defines a macro. Here is an example.
(defmacro unless (condition expr)
(list 'if condition () expr))
The above defmacro defines a new macro unless. unless is a new conditional
which evaluates expr unless condition is a true value. You cannot do the
same thing with a function because all the arguments would be evaluated before
the control is passed to the function.
(define x 0)
(unless (= x 0) '(x is not 0)) ; -> ()
(unless (= x 1) '(x is not 1)) ; -> (x is not 1)
macroexpand is a convenient special form to see the expanded form of a macro.
(macroexpand (unless (= x 1) '(x is not 1)))
;; -> (if (= x 1) () (quote (x is not 1)))
gensym creates a new symbol which will never be eq to any other symbol other
than itself. Useful for writing a macro that introduces new identifiers.
(gensym) ; -> a new symbol, such as G__0
As in the traditional Lisp syntax, ; (semicolon) starts a single line comment.
The comment continues to the end of line.