How many primitives does it take to build a LISP machine? Ten, seven or five?

Question

On this site they say there are 10 LISP primitives. The primitives are: atom, quote, eq, car, cdr, cons, cond, lambda, label, apply.

http://hyperpolyglot.wikidot.com/lisp#ten-primitives

Stevey reckons there are seven (or five):

Its part of the purity of the idea of LISP: you only need the seven (or is it five?) primitives to build the full machine. http://steve-yegge.blogspot.com/2006/04/lisp-is-not-acceptable-lisp.html

What is the minimum number of primitives to build a LISP machine (ie something that can run an eval/value function on LISP code)? (And which ones are they?)

(I can understand you could live without atom, label and apply)

Answer 1

Basic Predicates/F-functions

McCarthy's Elementary S-functions and Predicates were:

1. atom

   Which was necessary because car and cdr are defined for lists only, which means you cannot count on any sort of answer to indicate what was happening if you gave car an atom.

2. eq

   For testing equality between atoms.

3. car

   For returning the first half (address) of the cons cell. (Contents of address register).

4. cdr

   For returning the second half (decrement) of the cons cell. (Contents of decrement register).

5. cons

   For making a new cons cell, with the address half containing the first argument to cons, and the decrement half containing the second argument.

Tying it together: S-Functions

He then went on to add to his basic notation, to enable writing what he called S-functions:

1. quote

   To represent an expression without evaluating it.

2. cond

   The basic conditional to be used with the previously described predicates.

3. lambda

   To denote a function.

4. label

   Though he didn't need this for recursion, he might not have known about the Y-Combinator (according to Paul Graham), he added this for convenience and to enable easy recursion.

---

So you can see he actually defined 9 basic "operators" for his Lisp machine. In a previous answer to another one of your questions, I explained how you could represent and operate on numbers with this system.

But the answer to this question really depends on what you want out of your Lisp machine. You could implement one without the label function, as you could simply functionally compose everything, and obtain recursion through applying the Y-Combinator.

atom could be discarded if you defined the car operation on atoms to return NIL.

You could essentially have McCarthy's LISP machine with 7 of these 9 defined primitives, but you could ostensibly define a more concise version depending on how much inconvenience you'd want to inflict on yourself. I like his machine quite fine, or the many primitives in the newer languages like Clojure.

Answer 2

The best way to actually know this for sure is if you implement it. I used 3 summers to create Zozotez which is a McCarty-ish LISP running on Brainfuck.

I tried to find out what I needed and on a forum you'll find a thread that says You only need lambda. Thus, you can make a whole LISP in lambda calculus I you'd like. I found it interesting, but it's hardly the way to go if you want something that eventually has side effects and works in the real world.

For a Turing complete LISP I used Paul Grahams explanation of McCarthy's paper and all you really need is:

• symbol-evaluation
• special form quote
• special form if (or cond)
• special form lambda (similar to quote)
• function eq
• function atom
• function cons
• function car
• function cdr
• function-dispatch (list-lambda)

Thats 10. In addition to this, to have a implementation that you can test and not just on a drawing board:

• function read
• function write

Thats 12. In my Zozotez I implemeted set and flambda (anonymous macroes, like lambda) as well. I could feed it a library implementing any dynamic bound lisp (Elisp, picoLisp) with the exception of file I/O (because the underlying BF does not support it other than stdin/stdout).

I recommend anyone to implement a LISP1-interpreter in both LISP and (not LISP) to fully understand how a language is implemented. LISP has a very simple syntax so it's a good starting point for a parser. I'm currently working on a scheme compiler written in scheme with different targets (like Stalin is for target C), hopefully BF as one of them.

Answer 3

McCarthy used seven operators to define the original Lisp: quote, atom, eq, car, cdr, cons and cond. This article retraces his steps.

Answer 4

This faq states:

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.

That comes from the School of Computer Science, Carnegie Melon website.

Answer 5

You just need an x86 MOV instruction.

"The M/o/Vfuscator (short 'o', sounds like "mobfuscator") compiles programs into "mov" instructions, and only "mov" instructions. Arithmetic, comparisons, jumps, function calls, and everything else a program needs are all performed through mov operations; there is no self-modifying code, no transport-triggered calculation, and no other form of non-mov cheating."

Seriously though, these primitives will not implement a Lisp Machine. A machine needs facilities like I/O, and garbage collection. Not to mention a function calling mechanism! Okay, you have seven primitives which are functions. How does the machine call a function?

The proper understanding of what these primitives make possible is that they expose the instruction set of a Universal Turing Machine. Because those instructions are "Lispy", by a slip of the tongue (speaking with a Lisp) we sneakily call this a "Lisp Machine". "Universal" means that the machine is programmable: with some combination instructions applied to the Universal Turing Machine, we can instantiate any Turing Machine. But so far, all of that is purely a mathematical construct.

To actually simulate this UTM—realize it physically in order to explore it on a computer, we need a machine which provides for a way to us to actually input those forms which create Turing Machines from combinations of those seven Lisp instructions. And we also need some form of output; the machine as to at least be able to tell us "yes", "no", or "Wait, I'm still running".

In other words, the only way those seven instructions can practically work is if they are hosted in a larger machine which provides the environment.

Also note that Graham's seven primitives have no explicit support for numbers, so you would have to build them out of functions ("Church numerals" technique). No production Lisp implementation does such a crazy thing.

Answer 6

Paul Graham implements eval using seven.

In McCarthy's Micro Manual for LISP he implements eval using ten.