INTERVIEW QUESTIONS PROGRAMMING LANGUAGES LISP PROGRAMMING DETAILS

Question: What is the "minimal" set of primitives needed for a Lisp interpreter?

Answer: 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.

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.
Source: CoolInterview.com

If you have the better answer, then send it to us. We will display your answer after the approval.

Rules to Post Answers in CoolInterview.com:-

• There should not be any Spelling Mistakes.
• There should not be any Gramatical Errors.
• Answers must not contain any bad words.
• Answers should not be the repeat of same answer, already approved.
• Answer should be complete in itself.

Name :*
Email Id :*
Answer :*
Verification Code	Not readable? Load New Code
Enter the above shown code: *
	Inform me about updated answers to this question