[1-5] What is the "minimal" set of primitives needed for a Lisp interpreter?

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.] 

    Abelson and Sussman's SICP, especially chapters 4 and 5 on the
    implementation of meta-circular and explicit-control evaluators.

    Steele and Gabriel's "The Evolution of LISP".
Go Back Up

Go To Previous

Go To Next