CoolInterview.com - World's Largest Collection of Interview Questions & Answers, FAQs, queries, sample papers, exam papers, dumps, what, why, how, where, when questions
Our Services
Get 9,000 Interview Questions & Answers in an eBook.




Get it now !!
Send your Resume to 6000 Companies

Search Interview Questions

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.



Category Lisp Programming Interview Questions & Answers - Exam Mode / Learning Mode
Rating (0.3) By 5274 users
Added on 5/15/2014
Views 52775
Rate it!
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.
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.

Post your answer here

Inform me about updated answers to this question.
Related Questions
View Answer
Where can I learn about implementing Lisp interpreters and compilers?
View Answer
How can I improve my Lisp programming style and coding efficiency?
View Answer
Lisp books, introductions, documentation, periodicals, journals, and conference proceedings.
View Answer
What is the difference between Scheme and Common Lisp?
View Answer
What is the purpose of this newsgroup?
View Answer
How complex can I get?
View Answer
What if I get interrupted?
View Answer
How do I tell LG3 what I what?
View Answer
What is the ouput like?
View Answer
Can I save my programs to files?
View Answer
Why use LISP?
View Answer

Please Note: We keep on updating better answers to this site. In case you are looking for Jobs, Pls Click Here Vyoms.com - Best Freshers & Experienced Jobs Website.

View All Lisp Programming Interview Questions & Answers - Exam Mode / Learning Mode




India News Network
Latest 20 Questions
Payment of time- barred debt is: (a) Valid (b) Void (c) Illegal (d) Voidable
Consideration is defined in the Indian Contract Act,1872 in: (a) Section 2(f) (b) Section 2(e) (c) Section 2(g) (d) Section 2(d)
Which of the following is not an exception to the rule, "No consideration, No contract": (a) Natural love and affection (b) Compensation for involuntary services (c) Completed gift (d) Agency
Consideration must move at the desire of: (a) The promisor (b) The promisee (c) The promisor or any other party (d) Both the promisor and the promisee
An offer which is open for acceptance over a period of time is: (a) Cross Offer (b) Counter Offer (c) Standing Offer (d) Implied Offer
Specific offer can be communicated to__________ (a) All the parties of contract (b) General public in universe (c) Specific person (d) None of the above
_________ amounts to rejection of the original offer. (a) Cross offer (b) Special offer (c) Standing offer (d) Counter offer
A advertises to sell his old car by advertising in a newspaper. This offer is caleed: (a) General Offer (b) Special Offer (c) Continuing Offer (d) None of the above
In case a counter offer is made, the original offer stands: (a) Rejected (b) Accepted automatically (c) Accepted subject to certain modifications and variations (d) None of the above
In case of unenforceable contract having some technical defect, parties (a) Can sue upon it (b) Cannot sue upon it (c) Should consider it to be illegal (d) None of the above
If entire specified goods is perished before entering into contract of sale, the contract is (a) Valid (b) Void (c) Voidable (d) Cancelled
______________ contracts are also caled contracts with executed consideration. (a) Unilateral (b) Completed (c) Bilateral (d) Executory
A offers B to supply books @ Rs 100 each but B accepts the same with condition of 10% discount. This is a case of (a) Counter Offer (b) Cross Offer (c) Specific Offer (d) General Offer
_____________ is a game of chance. (a) Conditional Contract (b) Contingent Contract (c) Wagering Contract (d) Quasi Contract
There is no binding contract in case of _______ as one's offer cannot be constructed as acceptance (a) Cross Offer (b) Standing Offer (c) Counter Offer (d) Special Offer
An offer is made with an intention to have negotiation from other party. This type of offer is: (a) Invitation to offer (b) Valid offer (c) Voidable (d) None of the above
When an offer is made to the world at large, it is ____________ offer. (a) Counter (b) Special (c) General (d) None of the above
Implied contract even if not in writing or express words is perfectly _______________ if all the conditions are satisfied:- (a) Void (b) Voidable (c) Valid (d) Illegal
A specific offer can be accepted by ___________. (a) Any person (b) Any friend to offeror (c) The person to whom it is made (d) Any friend of offeree
An agreement toput a fire on a person's car is a ______: (a) Legal (b) Voidable (c) Valid (d) Illegal
Cache = 0.03125 Seconds