exp ::= var | (lambda (var) exp) | (exp exp)

Check out

http://matt.might.net/articles/church-encodings-demo-in-sche...

To see how to build numbers, booleans, lists, conditionals and recursion out of pure lambdas.

Even cooler is that these tricks work in languages like JavaScript too:

http://matt.might.net/articles/implementation-of-recursive-f...

  (setq cons (lambda (x xs)
               (lambda (msg)
                 (if (eq msg 'car) x xs)))

  (setq car (lambda (xs) (xs 'car)))
  (setq cdr (lambda (xs) (xs 'cdr)))

You can take this pretty far. Essentially, you just need 'lambda and application. You could use church numerals for numbers, monads for side effects, the y-combinator for recursion, etc.

The definitions for CAR and CDR are identical and they don't make much sense (set the symbol 'car to the value of a function that takes angument xs, which is a function, and applies that to the symbol 'car)

And the definition for CONS is equally opaque.

How would you use those functions, CONS, CAR and CDR?

Since you pretty much nailed the uses of church numerals, monads and the y-combinator, I know you know what you're talking about, it just that Lisp's semantics is confusing me (it has common lisp keyword SETQ but none of its behavior)

If mquander's explanation isn't enough, you might look at it using terms from the OO world: CAR takes a pair object and calls its 'car method.

I thought what you wrote was supposed to be a primitive implementation of the functions.

Imagine encoding the pair ('hello . 'world) into a function. You might say:

  (lambda (msg)
    (if (eq msg 'car) 'hello 'world))

  (lambda (car-value cdr-value)
    (lambda (msg)
      (if (eq msg 'car) car-value cdr-value)))

If you evaluate (car (cons 1 2)) and (cdr (cons 1 2)) on paper using substitution, you'll see how it works.

Pair-structured memory, a (very simple) recursive-descent parser, eval, apply, read, print, a few mathematical primitives, not too much else. Once you have the bare bones, _The Art of the Interpreter_ provides a good skeleton. Don't worry about a garbage collector yet - either use a language with one (Scheme, Python, Lua, Ruby, OCaml, etc.) or just let it leak memory for now. (Garbage collectors aren't deep magic either, but one thing at a time, you know?)

Implementing a toy Lisp is absolutely worthwhile. It shouldn't take too long* , and it will teach you several deep things. Don't worry about making it efficient until you have it together enough to be useful. (If you want a mini language that's mature, just use Lua.) This is about discovery. Many interpreters for mini-languages don't need to be efficient, anyway. Who writes 20,k-long files in a DSL?

* Though if you've never done an interpreter at all, a half-assed Forth is even simpler. Either way, implementing half-assed Lisps, Prologs, Js, etc. is a great way to feel out a language. Worrying about getting it efficient upfront can be a red herring.

Eighth paragraph: http://www.paulgraham.com/ilc03.html

http://lib.store.yahoo.net/lib/paulgraham/jmc.lisp

Or at least from a historic perspective.

This is cool, though, and very readable; I know what all the code is doing with a quick glance. Cheers to the author.

NIL = (lambda (x) (lambda (y) y))

CONS = (lambda (ar) (lambda (dr) (lambda (op) (op ar dr))))

CAR = (lambda (expr) (expr (lambda (ar dr) ar)))

CDR = (lambda (expr) (expr (lambda (ar dr) dr)))

http://library.readscheme.org/page1.html

What you are looking for is answered in "The Art of the Interpreter, the Modularity Complex (Part Zero, One, and Two)", Steele and Sussman, MIT AI Lab Memo 453, May 1978.

http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-...

More LISP details can be obtained by the book "LISP in Small Pieces" by Christian Queinnec (1996), and an excellent description of the eval/apply functions can be found in "The Architecture of Symbolic Computers" by Peter M. Kogge, 1990.

Btw: to satisfy my more or less latent pedantism: The second SICP author is called Abelson not Ebelson.

http://www.faqs.org/faqs/lisp-faq/part1/section-6.html

Frustrating to have to login to ACM to read McCarthys - 'A micro-manual for LISP - not the whole truth'

Thankfully, found this hidden away at [pdf d/l link] : http://www.ee.ryerson.ca/~elf/pub/misc/micromanualLISP.pdf