Search code examples
lispturing-complete

Really minimum lisp


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)


Solution

  • 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.