Common Lisp: Are all functions built from the core functions, CAR, CDR, CONS, etc?

Question

True or False?

Common Lisp has a mountain of functions. All of those functions are built (or could be built) using this small set of core functions: CAR, CDR, CONS, ATOM, EQ, QUOTE, COND, LAMBDA, LABEL, NULL.

If the answer is False, can you provide an example of a function that cannot be implemented using the core functions? Perhaps the list of core functions is incomplete, and another or two additional core functions are required?

Common Lisp has some special forms. Otherwise I think it's pretty much up to the implementation how it chooses to implement the standard functions/macros. — jkiiski
Thanks. I am looking right now at The LISP Interpreter in the LISP 1.5 Programmers Manual (appendix B). It appears that I am correct, albeit a few more functions are part of the core set. — Roger Costello

Daniel Jour Daniel Jour · Accepted Answer · 2016-02-27T20:09:13

[..] All of those functions are built (or could be built) using [..]

The important part is the could, which you already figured out yourself. That (almost*) all of (a) Lisp could be built using that small set of core functions (forms) is part of the beauty of Lisp. In practice, though, the set of functions (forms) not implemented in Lisp is a lot larger.

Why do implementations then bother to implement that much, when they only could implement that minimal core? As a small example, think of this expression:

(+ 1 2)

You could implement a Lisp that uses only the small set of core functions and it would be able (given an appropriate parser for the numbers) to evaluate this expression. But it would be painfully slow! The systems (CPUs) that are available to us mostly provide a lot of different instructions which Lisp implementations (especially the compiling ones) try to leverage as much as possible in order to allow fast execution of Lisp programs. And, to get back to the example, that also means that one wouldn't do actual calculations using peano arithmetic but rather use the "boolean logic arithmetic" implemented in hardware.

If the answer is False, can you provide an example of a function that cannot be implemented using the core functions?

That's easy, how'd you implement format? Anything that's not part of the "algorithmic" nature of a programming language, i.e. the stuff interfacing with the "outside world", is often not implemented in itself but - being dependent on the underlying system - most often in C or assembly.

Common Lisp: Are all functions built from the core functions, CAR, CDR, CONS, etc?

2 Answers