Really minimum lisp

Question

What is the minimum set of primitives required such that a language is Turing complete and a lisp variant?

Seems like car, cdr and some flow control and something for REPL is enough. It be nice if there is such list.

Assume there are only 3 types of data, integers, symbols and lists.(like in picolisp)

Note that integers are unnecessary, you can implement them from pure functions. — celtschk, Nov 09 '11 at 19:34

score 13 · Answer 1 · answered Apr 28 '10 at 17:10

13

The lambda calculus is turing complete. It has one primitive - the lambda. Translating that to a lisp syntax is pretty trivial.

answered Apr 28 '10 at 17:10

Michael Donohue

11,776
5
31
44

2

Actually it has *three* primitives: lambda expressions, function calls, and variable references. – Eli Barzilay Feb 29 '16 at 03:26

score 7 · Accepted Answer · answered Apr 28 '10 at 17:17

7

There's a good discussion of this in the Lisp FAQ. It depends on your choice of primitives. McCarthy's original "LISP 1.5 Programmer's Manual" did it with five functions: CAR, CDR, CONS, EQ, and ATOM.

answered Apr 28 '10 at 17:17

ire_and_curses

68,372
23
116
141

2

Reading said FAQ, it appears he used those five functions along with the special forms CONS, LAMBDA and QUOTE. – Zak Apr 30 '10 at 17:20

score 6 · Answer 3 · answered Apr 28 '10 at 17:17

6

I believe the minimum set is what John McCarthy published in the original paper.

The Roots of Lisp.

The code.

answered Apr 28 '10 at 17:17

Nick Dandoulakis

42,588
16
104
136

score 3 · Answer 4 · answered Feb 28 '16 at 17:52

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 if 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 (basically apply but not actually exposed to the system so it handles a list where first element is a function)

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 all other programming languages how you implement an interpreter is very similar. Eg. in the SICP videos the wizards make an interpreter for a logical language, but the structure and how to implement it is very similar to a lisp interpreter even though this language is completely different than Lisp.

Really minimum lisp

4 Answers4

Linked