A common trait of all dialects of LISP is the S-expression.

In Lisp, a pair of parentheses indicates one step of calculation, operations use the prefix notation. This page will document a portable, lexically scoped, purely functional subset of Lisp that compiles to the SECD virtual machine. I will use uppercase function names to indicate built-in functions, and lowercase for user-defined functions.

Typical Lisp Programmer


A number is a signed integer represented by a sequence of decimal digits, optionally preceded by a sign.


A symbol is word represented by a sequence of characters, it cannot begin with a number or a sign, although these may appear later in a symbol.


The (ATOM exp) procedure return the symbol T if the value of the expression is an atom or F otherwise.

(ATOM (QUOTE 12)) ; T
(ATOM (CONS (QUOTE 12) (QUOTE 34))) ; F


A pair joins two arbitrary values. The (CONS a d) procedure constructs pairs, the (CAR list) procedure extracts the first elements of the pair, and the (CDR list) procedure extracts the second.

(CONS (QUOTE foo) (QUOTE bar)) ; (foo.bar)
(CAR (CONS (QUOTE foo) (QUOTE bar))) ; foo
(CDR (CONS (QUOTE foo) (QUOTE bar))) ; bar

A list is a chain of pair that are cons-ed onto one another, ending with a nil.

			(QUOTE NIL)))) ; (a b c.NIL)


The (EQ a b) procedure results in a value either T or F provided that the values of the expressions being compared are both atoms, and either they are both the same number, or they are both the same symbol:

(EQ (QUOTE (a)) (QUOTE (a))) ; F
(EQ (QUOTE 42) (QUOTE foo)) ; F
(EQ (QUOTE 42) (QUOTE 42)) ; T
(EQ (QUOTE foo) (QUOTE foo)) ; T

Given three expressions, the (IF test exp2 exp3) returns the value of the second if the value of the expression test is T, otherwise returns the value of the third.

(IF (EQ (QUOTE 16) X)


Arithmetic operators follows the prefix notation:

(* (+ (QUOTE 3) (QUOTE 5)) (QUOTE 19)) ; 144


A (LAMBDA args exp) expression evaluates to a procedure. The environment which is in effect when a lambda expression is evaluated is enclosed in the newly created procedure, this is referred to as a closure. Given an expression, the (QUOTE exp) procedure returns that expression as a value.

(LAMBDA (X) (ADD X (QUOTE 2))) ; the procedure itself
((LAMBDA (X) (ADD X (QUOTE 2))) (QUOTE 14)) ; 16

The (LET exp [pairs]), and (LETREC exp [pairs]), expressions can associate pairs of values to an expression, given an expression with declarations returns its value. The main difference between let and letrec is that letrec's definitions are also visible in the expression itself.

(LETREC name
	(name LAMBDA (X Y)
		(ADD value1 value2)
	(value1 QUOTE 123)
	(value2 QUOTE 456)


A program is either a LET, LETREC or LAMBDA expression. The program is given an expression from the outside world, that we will call INPUT to make explicit that this is our program entry procedure.

From here forward, I will use the λ shorthand for LAMBDA, which is part of the extended Lispkit compiler.

The (WRITE exp) procedure sends an expression to be dispatched to a device, by default, it is printing the expression in the console. If the symbol "Machiavelli" is used as argument, the program will evaluate to the following output:

(λ (INPUT)
) ; "(Hello.Machiavelli)"

Prefixing the WRITE expression with the :cli symbol routes the expression to the Command Line Interface, which handles printing text. The #\Newline sybol gets converted to a linebreak during printing.

(LETREC main
	(main λ (INPUT)
		(print-line (fib INPUT))
	(fib λ (N)
		(IF (EQ N (QUOTE 0)) (QUOTE 0)
		(IF (EQ N (QUOTE 1)) (QUOTE 1)
				(fib (SUB N (QUOTE 1)))
				(fib (SUB N (QUOTE 2))))))
	(print-line λ (text)
			(CONS (QUOTE :cli)
			(CONS text
			(CONS (QUOTE #\Newline)
			(QUOTE NIL))))


Writing EVAL required inventing a notation representing Lisp functions as Lisp data, and such a notation was devised for the purposes of the paper with no thought that it would be used to express Lisp programs in practice.

Standard Functions

The following is a collection of implementations for standard functions in Pure Lisp. Predicate functions suffixed with ? are expressions that return either T or F.

(null? λ (x) (EQ x (QUOTE NIL)))
(true? λ (x) (IF x (QUOTE T) (QUOTE F)))
(not? λ (x) (IF x (QUOTE F) (QUOTE T)))
(or? λ (x y) (IF x (QUOTE T) (true? Y)))
(and? λ (x y) (IF x (true? y) (QUOTE F)))
(number? λ (n) (EQ n (+ n (QUOTE 0))))

List Processing Functions

Length is the number of components in the list ls.

(length λ (ls)
	(IF (ATOM ls)
		(QUOTE 1)
		(+ (QUOTE 1) (length (CDR ls)))

Member? returns T if the atom e is present in the list ls.

(member? λ (e ls)
	(IF (ATOM ls) (QUOTE F)
	(IF (EQ (CAR ls) e) (QUOTE T)
		(member? e (CDR ls))))

Filter is the list of those components for which the application of fn is T.

(filter λ (fn ls)
	(IF (ATOM ls)
		(IF (fn (CAR ls))
			(CONS (CAR ls) (filter fn (CDR ls)))
			(filter fn (CDR ls))

Map is the list whose components are obtained from those of ls by application of fn.

(map λ (fn ls)
	(IF (ATOM ls)
		(CONS (fn (CAR ls)) (map fn (CDR ls)))

Church Numerals are a representation of the natural numbers using lambda notation.

A kind of base1 arithmetic, in which numbers are represented by function nesting over an empty list, can be constructed in Pure Lisp using only very few primtives. This document will present Church Numerals through the lens of Lisp, alternatively one might prefer to read it coming from the Avian Numerals tutorial.

The following file contains the basic building blocks as an example:

(LETREC church
	(church LAMBDA (INPUT)
			(incr (incr (incr (incr nil))))
			(incr (incr (incr nil))))
	(#f QUOTE F)
	(#t QUOTE T)
	(incr LAMBDA (x)
		(CONS nil x))
	(decr LAMBDA (x)
		(CDR x))
	(zero? LAMBDA (x)
		(EQ x nil))
	(not LAMBDA (x)
		(IF x #f #t))
	(plus LAMBDA (x y)
		(IF (zero? x) y
			(plus (decr x) (incr y))))
	(minus LAMBDA (x y)
		(IF (zero? y) x
			(minus (decr x) (decr y))))
	(multiply LAMBDA (x y)
		(IF (zero? x) nil
			(plus y (multiply (decr x) y))))
	(equal? LAMBDA (x y)
		(IF (zero? x) (zero? y)
			(IF (zero? y) #f
				(equal? (decr x) (decr y)))))
	(greater? LAMBDA (x y)
		(IF (zero? x) #f
			(IF (zero? y) (not (zero? x))
				(greater? (decr x) (decr y)))))
	(lesser? LAMBDA (x y)
		(greater? y x))

Lispkit compiler

Lispkit compiles to SECD machine instructions, here is the source for the lispkit compiler capable of converting lispkit .lisp into .secd files.

lispkit lispkit.secd lispkit.lisp > bin/lispkit-bootstrap.secd view raw

You can use the compiler above with this minimal virtual machine, and a SECD-compatible version of that same compiler below:

lispkit lispkit.secd input.lisp > output.secd view raw

incoming ronin lain lisp library church encoding secd