Found in 15 comments on Hacker News
braythwayt · 2019-12-18 · Original thread
"Do you know enough lisp to write a self hosting interpreter in it?"

Short answer: Yes.

Long answer: No!

I learned Lisp and TI-Scheme in the early 80s, and somewhere around then we did some SICP-like stuff in undergrad CS.

I later came upon SICP and worked my way through it, having the usual "Aha!" moments. I thought I knew something about Lisp and Scheme at that point. I built some self-hosted interpreters using the following pattern:

1. Write an interpreter for a minimal subset of Scheme in a host language.

2. Write an interpreter for a more full-featured Scheme in the subset of Scheme.

At some point, I read LiSP,[0] and I discovered that what I thought was enlightenment was actually but a hint of the delights to come. The entire book is about teaching programming through the device of building interpreters and compilers.

So my next pattern was something like:

1. Write a minimal Scheme interpreter in a host language.

2. Write a Scheme compiler in Scheme.

3. Bootstrap the compiler by running in in the interpreted Scheme.

4. Now you have a compiled Scheme implementation written in Scheme.

5. Build out more features.

And now, this approach is one of my go-to tools. A few years ago, I was playing with Turing Machines, and I used a "constructive proof" approach: If we want to demonstrate that a Turing machine with tape that has one end is just as powerful as a Turing Machine with a tape that stretches to infinity in both directions, write a compiler from one kind of Turing Machine to the other. And so on and so forth to prove that being able to write an infinite number of different symbols is no more powerful than writing 0s and 1s. Or that a multi-dimensional Langdon's Ant is no more powerful than a Turing Machine...

Interpreters and Compilers are very powerful tools for constructive reasoning.

But the point of the discussion around Scheme for this purpose is how easy it makes writing Interpreters and Compilers. On the one hand... Shrug... Since we can write interpreters and compilers in any language.

On the other hand, a tool that removes a lot of the accidental complexity in writing interpreters and compilers changes the way we think about writing interpreters and compilers, much as parsing text using a language built around pattern matching (like SNOBOL and its descendants) changes the way we think about parsing text.

So... We are probably in deep agreement about the value of SICP in Scheme, and the value of Lisp in general, not just as a language, but as a way of changing the way we approach solving problems.

And as for knowing enough... The truth is, every time I sit down with certain programming ideas, I learn more and realize that what I thought I knew was incomplete.

So in a very real sense, I suspect that no, I don't know nearly as much as I think I know.

---

[0]: Lisp in Small Pieces: https://www.amazon.ca/Lisp-Small-Pieces-Christian-Queinnec/d...

tumba · 2019-11-21 · Original thread
APL is not so much a model of computation as a new notation for semantics which already exist. The real semantic explanation of APL is set theory and traditional mathematics.

Probably the best deep ground-level explanation of APL is Iverson’s paper “Notation as a tool of thought.” [0]

The bootstrapping explanation you describe sounds a lot like what Paul Graham did in “On Lisp” [1] and in a much more complex fashion, Queinnec in “Lisp in Small Pieces” [2], both highly recommended.

[0] https://www.jsoftware.com/papers/tot.htm

[1] http://www.paulgraham.com/onlisptext.html

[2] https://www.amazon.com/dp/0521545668

pjmlp · 2016-12-16 · Original thread
Yes, this quite good book, "Lisp in Small Pieces"

https://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/...

segmondy · 2015-10-30 · Original thread
if you really want to learn to build lisp, please lookup "lisp in small pieces" http://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/d...
chollida1 · 2015-03-23 · Original thread
Would highly recommend this book, with the caveat of only if you are a common lisp user with a fair bit of experience using common lisp.

This book goes into some of the more advanced uses of macros and I don't believe most carries over to other "lisps".

I really loved the section on reader macros!! That's a topic that doesn't get enough attention from people coming to common lisp.

I don't believe clojure, for example, supports user defined reader macros, atleast I can't remember it having them the last time I used it(circa 2011).

EDIT, it looks like clojure does have reader macros now. Clojure just keeps getting better:)

http://en.wikibooks.org/wiki/Learning_Clojure/Reader_Macros

In addition to Let over Lambda, my common lisp reading list includes:

http://www.amazon.ca/Lisp-Small-Pieces-Christian-Queinnec-eb...

http://www.amazon.ca/Compiling-Continuations-Andrew-W-Appel-...

and http://www.amazon.ca/Paradigms-Artificial-Intelligence-Progr...

I'd love to hear if anyone else has book recommendations in a similar vein. I'm in the middle of a month off to read books and research papers so this is pretty timely for me:)

webnrrd2k · 2015-02-28 · Original thread
Excellent -- a much gentler version of Lisp In Small Pieces. (http://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/d...)
fredyr · 2014-05-19 · Original thread
Richard Bird, Philip Wadler - Introduction to Functional Programming http://www.amazon.com/Introduction-Functional-Programming-In...

Richard Bird - Pearls of Functional Algorithm Design http://www.amazon.com/Pearls-Functional-Algorithm-Design-Ric...

Christian Queinnec - Lisp in Small Pieces http://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/d...

pdelgallego · 2013-07-23 · Original thread
You might enjoy Lisp in Small Pieces. Is one of my favorite books

The book is in two parts. The first starts from a simple evaluation function and enriches it with multiple name spaces, continuations and side-effects with commented variants, while at the same time the language used to define these features is reduced to a simple lambda-calculus.

The second part focuses more on implementation techniques and discusses precompilation for fast interpretation: threaded code or bytecode; compilation towards C. Some extensions are also described such as dynamic evaluation, reflection, macros and objects.

http://www.amazon.com/books/dp/0521545668

raganwald · 2012-03-26 · Original thread
My (pricey) favourite is Lisp In Small Pieces: http://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/d...

Note that Peter Norvig gives it a five-star review.

(The affiliate link benefits DuckDuckGo.)

sb · 2011-06-26 · Original thread
larsberg has already given several suggestions, however, since nobody else mentioned it yet, you might want to complete your view of functional programming language implementation by taking a look at "Lisp in Small Pieces" by Christian Queinnec (http://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/d...).
pdelgallego · 2011-05-06 · Original thread
The best lisp project is a lisp interpreter/compiler in Lisp.

Take a look to Lisp in Small Pieces[1] if you are interested in something beyond the metacircular evaluator from SICP.

Read the code of Racket, you will learn a lot from it.

[1] http://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/d...

hvs · 2010-11-29 · Original thread
If you're interested in getting into the details of implementing a Lisp/Scheme interpreter and compiler, I highly recommend Lisp in Small Pieces: http://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/d...
Shooter · 2007-09-24 · Original thread
Everyone beat me to the punch, but my starting list for Common Lisp is:

1. A Gentle Introduction to Symbolic Computation. http://www.cs.cmu.edu/~dst/LispBook/index.html

2. Practical Common Lisp http://www.gigamonkeys.com/book/

3. ANSI Common Lisp http://www.paulgraham.com/acl.html

4. On Lisp http://www.paulgraham.com/onlisptext.html

5. Paradigms of Artifical Intelligence Programming http://norvig.com/paip.html

6. Lisp in Small Pieces http://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/d...

SICP is also amazing...and there are at least three sets of videos to go with the book (Abelson/Sussman and HP/MIT, ArsDigita, and UC-Berkeley.)

Fresh book recommendations delivered straight to your inbox every Thursday.