Many Lisp functions can be defined in terms of other Lisp functions.

For example, CAAR can be defined in terms of CAR as

(defun caar (list) (car (car list)))

It is then natural to ask whether there is a "minimal" or smallest set

of primitives necessary to implement the language.

There is no single "best" minimal set of primitives; it all depends on

the implementation. For example, even something as basic as numbers

need not be primitive, and can be represented as lists. One possible

set of primitives might include CAR, CDR, and CONS for manipulation of

S-expressions, READ and PRINT for the input/output of S-expressions

and APPLY and EVAL for the guts of an interpreter. But then you might

want to add LAMBDA for functions, EQ for equality, COND for

conditionals, SET for assignment, and DEFUN for definitions. QUOTE

might come in handy as well. If you add more specialized datatypes,

such as integers, floats, arrays, characters, and structures, you'll

need to add primitives to construct and access each.

AWKLisp is a Lisp interpreter written in awk, available by anonymous

ftp from ftp.cs.cmu.edu:/user/ai/lang/lisp/impl/awk/. It has thirteen

built-in functions: CAR, CDR, CONS, EQ, ATOM, SET, EVAL, ERROR, QUOTE,

COND, AND, OR, LIST.

A more practical notion of a "minimal" set of primitives might be to

look at the implementation of Scheme. While many Scheme functions can

be derived from others, the language is much smaller than Common Lisp.

See Dybvig's PhD thesis,

R. Kent Dybvig, "Three Implementation Models for Scheme", Department

of Computer Science Technical Report #87-011, University of North

Carolina at Chapel Hill, Chapel Hill, North Carolina, April 1987.

for a justification of a particularly practical minimal set of

primitives for Scheme.

In a language like Common Lisp, however, there are a lot of low-level

primitive functions that cannot be written in terms of the others,

such as GET-UNIVERSAL-TIME, READ-CHAR, WRITE-CHAR, OPEN, and CLOSE,

for starters. Moreover, real Common Lisp implementations are often

built upon primitives that aren't part of the language, per se, and

certainly not intended to be user-accessible, such as SYS:%POINTER-REF.

Beside the references listed in [1-4], some other relevant references

include:

McCarthy, John, "Recursive Functions of Symbolic Expressions and

their Computation by Machine, Part I", CACM 3(4):185-195, April 1960.

[Defines five elementary functions on s-expressions.]

McCarthy, John, "A Micro-Manual for Lisp -- not the whole Truth",

ACM SIGPLAN Notices, 13(8):215-216, August 1978.

[Defines the Lisp programming language in 10 rules and gives

a small interpreter (eval) written in this Lisp.]

McCarthy, John, et al., "LISP 1.5 Programmer's Manual", 2nd edition,

MIT Press, 1965, ISBN 0-262-13011-4 (paperback).

[Gives five basic functions, CAR, CDR, CONS, EQ, and ATOM.

Using composition, conditional expressions (COND), and

recursion, LAMBDA, and QUOTE, these basic functions may be used

to construct the entire class of computable functions of

S-expressions. Gives the functions EVAL and APPLY in

M-expression syntax.]