Geek Answers Handbook

Really minimum lisp

What is the minimum set of primitives needed to make the language complete, and the lisp variant?

It seems that the car, cdr and some flow control, and something for REPL is enough. Well, if there is such a list.

Suppose there are only 3 data types, integers, characters, and lists. (e.g. in picolisp)

+7
lisp turing-complete
source share
5 answers

A good discussion of this question in Lisp FAQs . It depends on your choice of primitives. McCarthy's original “LISP 1.5 Programmer Manual” did this with five functions: CAR, CDR, CONS, EQ, and ATOM.

+5
source share

lambda calculus is complete. He has one primitive - lambda. Translation of this lisp syntax is pretty trivial.

+12
source share

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

The roots of Lisp .

Code .

+5
source share

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

+3
source share

The best way to find out for sure is to implement it. I used 3 summers to create Zozotez , which is the McCarty-ish LISP working on Brainfuck .

I tried to figure out what I needed, and on the forum you will find a thread that says you only need lambda. That way you can do the whole LISP in lambda calculus if you want. It seemed interesting to me, but it is unlikely to succeed if you want something that ultimately has side effects and works in the real world.

For a complete LISP Turing, I used Paul Graham's explanation of McCarthy's article , and all you really need:

  • rating symbol
  • special form quote
  • special form if (or cond)
  • special form lambda (similar to quote)
  • Eq function
  • function atom
  • cons function
  • function machine
  • Cdr function
  • send function (mainly used, but not actually exposed to the system, so it processes a list where the first element is a function)

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

  • reading function
  • write function

Thats 12. In my Zozotez, I did set and flambda (anonymous macros, like lambda). I could equip the library with the implementation of any dynamic LISP binding (Elisp, picoLisp), except for file I / O (because the underlying BF does not support it except stdin / stdout).

I recommend everyone to implement the LISP1 interpreter in LISP and (not LISP) in order to fully understand how the language is implemented. LISP has a very simple syntax, so it is a good starting point. For all other programming languages, how you implement the interpreter is very similar. For example. in SICP video, wizards make an interpreter for a logical language, but the structure and methods of its implementation are very similar to the LISP interpreter, although this language is completely different from Lisp.

+1
source share

More articles:


All Articles