18

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

I am curious. What is the most minimal LISP, upon which all further features could be built? Ignore efficiency -- the question comes simply from a place of elegance.

If you awoke on an alien planet and were instructed to build the most minimal LISP that you could later build upon to implement any feature you liked, what would you include?

Edit: Clarification. My intent here is not to start a debate, rather I am considering implementing a minimal LISP and I want to understand how minimal I can go while still allowing the language I implement to be Turing complete, etc. If this turns out to be controversial I am sure I will learn what I wanted to learn from observing the controversy. :). Thanks!

Community
  • 1
  • 1
MikeC8
  • 3,783
  • 4
  • 27
  • 33
  • How is this subjective? It might be a duplicate (I think I saw a similar question once, will go searching now). –  Jan 03 '11 at 23:36
  • 2
    Found it: [How many primitives does it take to build a LISP machine? Ten, seven or five?](http://stackoverflow.com/questions/3482389/how-many-primitives-does-it-take-to-build-a-lisp-machine-ten-seven-or-five) (Also has a link to another question that touches this subject as well). –  Jan 03 '11 at 23:43
  • Do you want the minimal number of operations for the language to be turing complete or to be able to define all language features found e.g. in common lisp? – sepp2k Jan 03 '11 at 23:56
  • 3
    Might want to read `Lisp In Small Pieces`. – Wodin Jan 04 '11 at 00:33

2 Answers2

16

Courtesy of Paul Graham, here's a Common Lisp implementation of John McCarthy's original LISP:

It assumes quote, atom, eq, cons, car, cdr, and cond, and defines null, and, not, append, list, pair, assoc, eval, evcon and evlis.

grifaton
  • 3,986
  • 4
  • 30
  • 42
  • It also assume that you have a lisp machine capable of interpreting lisp –  Jul 12 '21 at 18:09
6

Peter Norvig implemented a LISP interpreter in 90 lines of Python, and his subsequent article discusses in detail what you're asking. Well worth the read, IMHO.

http://norvig.com/lispy.html

I've got a feeling that his "sequencing" special form could be dropped if only function calls could take an arbitrary number of parameters.

(defun last (lst)
  (if (cdr lst) 
      (last (cdr lst))
      (car lst)))

(defun begin (:rest y) (last y))

But this would complicate function application.

Jander
  • 5,359
  • 1
  • 22
  • 21
  • If function applications are curried to create partial applicable with some lambda context then your idea wouldn't be so difficult! Good thinking. – Joshua Hedges May 15 '18 at 17:37