Applicative languages are functional, and applicative is often used as a synonym for functional.

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.

incoming concatenative