tiny-lisp
tiny-lisp is a small implementation of LISP, written in standard C11. It is intended to show how features such as macros, tail recursion and a copying garbage collector can be implemented in C.
Language features
- read-eval-print loop
- numbers, strings, symbols and lists
- functions and macros
- lexical scoping
- scheme-style dotted parameter lists
- scheme-style tail recursion
- copying garbage collector
Numeric operations
tiny-lisp supports the four arithmetic operations +, -, *, / as well as
the relational operations =, <, <=, >, >=:
(- 5) ; -5
(- 5 3.2 .6) ; 1.2
(< 2 4 6.8) ; t
(> 4 8) ; nil
List operations
(list ...) returns a list containing the supplied arguments:
(list) ; nil
(list 1 2 3) ; (1 2 3)
(list 1 2 (+ 1 2)) ; (1 2 3)
(cons x y) creates a new cons cell, the car of which is x and the cdr
of which is y:
(cons 1 2) ; (1 . 2)
(cons 1 '(2)) ; (1 2)
(car x), (cdr x) return the car and cdr of a list respectively:
(car '(1 2 3)) ; 1
(cdr '(1 2 3)) ; (2 3)
Predicates
(eq x y) returns t if x and y refer to the same object, or if they are
numbers with the same value, or if they are string objects with identical
content:
(eq 1 1) ; t
(eq 1 2) ; nil
(eq 'a 'a) ; t
(eq 'a 'b) ; nil
(eq "hello" "hello") ; t
(eq "hello" "world") ; nil
(eq '(1 2) '(1 2)) ; nil
(equal x y) returns t if x and y are objects of identical structure and
each of their elements satisfy the eq predicate, otherwise nil:
(equal '(1 2) '(1)) ; nil
(equal '(1 2) '(1 2)) ; t
(null x) returns t if x is nil, otherwise nil:
(null nil) ; t
(null 1) ; nil
(null "hello") ; nil
(null '(1 2)) ; nil
(atom x) returns t if x is not a cons cell, otherwise nil:
(atom nil) ; t
(atom 1) ; t
(atom "hello") ; t
(atom '(1 2)) ; nil
(consp x) returns t if x is a cons cell, otherwise nil:
(consp nil) ; nil
(consp 1) ; nil
(consp "hello") ; nil
(consp '(1 2)) ; t
(listp x) returns t if x is a cons cell or nil, otherwise nil:
(listp nil) ; t
(listp 1) ; nil
(listp "hello") ; nil
(listp '(1 2)) ; t
(zerop x) returns t if x is the number zero, otherwise nil:
(zerop 0) ; t
(zerop 1) ; nil
(zerop "hello") ; error: "hello" is not a number
Logical operations
(not x) returns t if x is nil, otherwise nil (not is therefore
identical to null, but is usually used in conjunction with boolean logic).
(and ...) evaluates its arguments one at a time from left to right. As soon
as any argument evaluates to nil, and returns nil without evaluating the
remaining arguments. Otherwise, it returns the value produced by evaluating
its last argument. If no arguments are supplied, and returns t:
(and) ; t
(and 1 2 3) ; 3
(and 1 nil 3) ; nil
(or ...) evaluates its arguments one at a time from left to right. As soon
as any argument does not evaluate to nil, or returns its value without
evaluating the remaining arguments. Otherwise, it returns nil:
(or) ; nil
(or 1 2 3) ; 1
(or nil nil 3) ; 3
Output operations
(princ x) prints x to the standard output:
(princ "Hello!\n") ; prints Hello! followed by a newline
(print x) is similar to princ but its output is preceded by a newline and
followed by a space. In addition, print differs in its handling of strings
which it outputs exactly the way they were entered, including reproducing
escape sequences:
(print "\"a\\b\"\n") ; prints "\"a\\b\"\n"
Conditionals
(if test then [else]) returns the result of evaluating then if test
does not evaluate to nil, otherwise returns the result of evaluating else
or nil:
(if 1 2 3) ; 2
(if nil 2 3) ; 3
(if nil 2) ; nil
(cond ...) takes zero or more clauses, each of the form (test [expr...]).
cond returns the result of evaluating expr... of the first clause for which
test does not evaluate to nil without evaluating the remaining clauses. If
a clause does not supply expr..., the result of evaluating test is returned
instead. If every test evaluates to nil, or no clauses are given, cond
returns nil:
(cond) ; nil
(cond (nil "hello")
(t "world")) ; "world"
(cond (nil "hello")
("world")) ; "world"
Defining variables
(setq name expr ...) binds the result of evaluating expr to the symbol
name. More than one name-expr pair can be given. setq returns the value
bound to the last symbol:
(setq a 1
b 2) ; 2
a ; 1
b ; 2
Defining functions
(lambda params expr...) creates an anonymous function with parameters
params and body expr.... params can be nil, a symbol, or a list of
symbols. If params is a symbol or a dotted list of symbols, the function will
accept a variable number of arguments:
((lambda nil
"hello")) ; "hello"
((lambda (a b)
(+ a b)) 1 2) ; 3
((lambda (a b . c)
c) 1 2 3 4 5) ; (3 4 5)
((lambda args
args) 1 2 3 4 5) ; (1 2 3 4 5)
(defun name params expr...) creates a function and binds it to the symbol
name:
(defun plus1 (x)
(+ x 1)) ; #<Lambda (x)>
(plus1 2) ; 3
Defining macros
(macro params expr...) creates an anonymous macro with parameters params
and body expr....
(defmacro name params expr...) creates a macro and binds it to the symbol
name.
Macros are different from functions in that they do not evaluate their arguments when called. Instead, we can think of them as taking expressions as input and returning a new expression as output.
Imagine we want to implement (when test expr...):
(setq x '(1 2 3)) ; (1 2 3)
(when (consp x)
(car x)) ; 1
(setq x "hello")
(when (consp x)
(car x)) ; nil
when, if implemented as a function, would not work correctly, since expr...
would be evaluated as soon as when is called:
(setq x "hello")
(when (consp x)
(car x)) ; error: "hello" is not a list
However, we can implement when as a macro that wraps expr... in a call to
if:
(defmacro when (test . expr)
(list 'if test (cons 'progn expr)))
(when (consp x) (car x)) would then produce the expression
(if (consp x) (progn (car x))) which yields the expected behaviour.