views:

256

answers:

5

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)

+2  A: 

http://en.wikipedia.org/wiki/Unlambda

Andrey
I'm not sure I agree that Unlambda is a LISP-variant.
Skeptic
i mentioned it just for fun, and it is functional
Andrey
+9  A: 

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

Michael Donohue
+1  A: 

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

The Roots of Lisp.

The code.

Nick D
+3  A: 

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.

ire_and_curses
Reading said FAQ, it appears he used those five functions along with the special forms CONS, LAMBDA and QUOTE.
Zak
A: 

Depends if by LISP-variant you include some kind of "set", if it is the case, you have more work to do (i.e. the interpreter needs to support environments, see SICP).

Skeptic