4 ms·

This makes me vocalize something Ive wondered about... Whats the smallest subset of lisp which you need to implement in order to bootstrap the language? So, g

by gord 17y ago

This makes me vocalize something Ive wondered about... Whats the smallest subset of lisp which you need to implement in order to bootstrap the language? So, given this small subset, one can implement the rest of say scheme or common lisp or arc on top of. I vaguely recall Sussman or Ebelson implementing car and cadr in terms of lambdas, for example. It seems this should be quite modular, given so many implementations of lisp [ in javascript, PHP, etc now Ruby ]. So that new lisps might be easily brought up over this kernel.

mdemare 17y ago
According to pg, seven: (quote, atom, eq, car, cdr, cons, and cond) Eighth paragraph: http://www.paulgraham.com/ilc03.html http://www.paulgraham.com/ilc03.html
- onewland 17y ago
  Quote as a predefined macro could be important though, in a Lisp, if you expect to be doing a lot of macro magic, and I don't see it here. This is cool, though, and very readable; I know what all the code is doing with a quick glance. Cheers to the author.
- jmatt 17y ago
  Ya that should be the minimum required to bootstrap. I always thought the definitive minimum code for lisp was here: http://lib.store.yahoo.net/lib/paulgraham/jmc.lisp http://lib.store.yahoo.net/lib/paulgraham/jmc.lisp Or at least from a historic perspective.
procrastitron 17y ago
Well, lambda calculus is Turing complete, so you could just stick with a call-by-value version of that. However, you'd want to add macros if you wanted to extend the syntax of the language. Since you mentioned car and cdr in lambdas, they'd be defined like this: 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)))
twilightsentry 17y ago
Well, you can define pairs like this (as long as you've got lexical scope): (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))) That only uses 'setq, 'lambda, 'if, 'eq, and quoted symbols. That pretty much gives you the untyped lambda calculus, plus some side effects. Throw in the appropriate macros and you've got the core of Scheme and Arc, without any I/O or efficient data representations. 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.
- mahmud 17y ago
  Under which lisp implementation do those forms work? 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)
  - mquander 17y ago
    Those look correct to me. The function returned by cons is just a switch that holds two values in a closure, and interprets what you pass it as a signal to determine which to retrieve. You could just as easily rewrite it to pass it 0 or 1 instead of car and cdr. If you evaluate (car (cons 1 2)) and (cdr (cons 1 2)) on paper using substitution, you'll see how it works.
    - dkersten 17y ago
      Exactly. SICP shows some similar code, though I don't remember which part..
  - twilightsentry 17y ago
fadmmatt 17y ago
The lambda calculus is Turing-complete, so the following language is sufficient to encode any computable function: exp ::= var | (lambda (var) exp) | (exp exp) Check out http://matt.might.net/articles/church-encodings-demo-in-scheme/ 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-fixed-point-y-combinator-in-javascript-for-memoization/ http://matt.might.net/articles/implementation-of-recursive-f...
jacquesm 17y ago
hehe, I had this open two tabs to the left of HN :) http://www.faqs.org/faqs/lisp-faq/part1/section-6.html http://www.faqs.org/faqs/lisp-faq/part1/section-6.html
- gord 17y ago
  Nice link. 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 http://www.ee.ryerson.ca/~elf/pub/misc/micromanualLISP.pdf
  - jacquesm 17y ago
    thank you, I'd been looking for that one :)
silentbicycle 17y ago
http://www.c2.com/cgi/wiki?ImplementingLisp http://www.c2.com/cgi/wiki?ImplementingLisp 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.
sb 17y ago
Since nobody mentioned it, there is a very interesting paper among what are know the "lambda papers": http://library.readscheme.org/page1.html 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-453.pdf 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.

by gord 17y ago

mdemare 17y ago

According to pg, seven: (quote, atom, eq, car, cdr, cons, and cond) Eighth paragraph: http://www.paulgraham.com/ilc03.html http://www.paulgraham.com/ilc03.html

onewland 17y ago
Quote as a predefined macro could be important though, in a Lisp, if you expect to be doing a lot of macro magic, and I don't see it here. This is cool, though, and very readable; I know what all the code is doing with a quick glance. Cheers to the author.
jmatt 17y ago
Ya that should be the minimum required to bootstrap. I always thought the definitive minimum code for lisp was here: http://lib.store.yahoo.net/lib/paulgraham/jmc.lisp http://lib.store.yahoo.net/lib/paulgraham/jmc.lisp Or at least from a historic perspective.

procrastitron 17y ago

Well, lambda calculus is Turing complete, so you could just stick with a call-by-value version of that. However, you'd want to add macros if you wanted to extend the syntax of the language. Since you mentioned car and cdr in lambdas, they'd be defined like this: 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)))

twilightsentry 17y ago

Well, you can define pairs like this (as long as you've got lexical scope): (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))) That only uses 'setq, 'lambda, 'if, 'eq, and quoted symbols. That pretty much gives you the untyped lambda calculus, plus some side effects. Throw in the appropriate macros and you've got the core of Scheme and Arc, without any I/O or efficient data representations. 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.

mahmud 17y ago
Under which lisp implementation do those forms work? 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)
- mquander 17y ago
  Those look correct to me. The function returned by cons is just a switch that holds two values in a closure, and interprets what you pass it as a signal to determine which to retrieve. You could just as easily rewrite it to pass it 0 or 1 instead of car and cdr. If you evaluate (car (cons 1 2)) and (cdr (cons 1 2)) on paper using substitution, you'll see how it works.
  - dkersten 17y ago
    Exactly. SICP shows some similar code, though I don't remember which part..
- twilightsentry 17y ago

fadmmatt 17y ago

The lambda calculus is Turing-complete, so the following language is sufficient to encode any computable function: exp ::= var | (lambda (var) exp) | (exp exp) Check out http://matt.might.net/articles/church-encodings-demo-in-scheme/ 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-fixed-point-y-combinator-in-javascript-for-memoization/ http://matt.might.net/articles/implementation-of-recursive-f...

jacquesm 17y ago

hehe, I had this open two tabs to the left of HN :) http://www.faqs.org/faqs/lisp-faq/part1/section-6.html http://www.faqs.org/faqs/lisp-faq/part1/section-6.html

gord 17y ago
Nice link. 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 http://www.ee.ryerson.ca/~elf/pub/misc/micromanualLISP.pdf
- jacquesm 17y ago
  thank you, I'd been looking for that one :)

silentbicycle 17y ago

http://www.c2.com/cgi/wiki?ImplementingLisp http://www.c2.com/cgi/wiki?ImplementingLisp 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.

sb 17y ago

Since nobody mentioned it, there is a very interesting paper among what are know the "lambda papers": http://library.readscheme.org/page1.html 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-453.pdf 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.