I appreciate this as someone learning lisp for the first time!
While I'm here I'll ask: does anybody have a recommendation for resources on learning lisp that focus on how the interpreter/compiler works? Here's what I tried so far: 1) Started Practical Common Lisp, but I found it lacking in the specifics. Then I 2) tried going to the specification but that was way too much. Then I 3) tried Common Lisp The Language and, while I liked the precise definitions a lot, it was a lot to keep in mind at the same time as learning the fundamentals. Right now I'm 4) back at Practical Common Lisp, skipping most of the text and reading surrounding paragraphs whenever if I find a piece of code I don't understand.
I wanted something that will not explain the standard library; I'd rather read the documentation for that. I wanted to know more precisely what happens throughout the program's life: Like, is behavior when running a script in "interpreter" mode guaranteed to be the same as when running in "native compiled code"? At what point does the compiler create an intermediate representation? Why does SBCL not use LLVM? At what point are #-starting words(read macros?) evaluated and how is that different from interpreting to compiling. How do I control the amount of optimization the compiler will do? Will the interpreter ever try to optimize? Is garbage collection implementation-defined? How will implementations change in behavior?
My first suggestion would be Norvig's text "Artificial Intelligence Programming" (note: not Russel and Norvig's "Modern Approach" but the "Case Studies" one with the teal and orange cover), start with chapter 3 for a straightforward description of the core set of routines (more than a minimal impl but not everything you'd see described in CL) and choose a few from any of the other chapters as a demo program that you can use as a first target for your implementation. Yeah it's GOFAI and might feel dated but it worked well for me to get a stronger grasp of Lisp implementations.
This won't hold your hand through implementing Lisp within another language like C or Rust, but it does show the representation of Lisp within Lisp (and a few chapters on implementing a logic programming language in Lisp as well). Most of the task of transpiling into another language reduces to how you represent functions and function results, and the extent to which your compiler reduces specific built-ins. There's a range of implementation here that you can find covered in PL research papers, but you may be better off looking through compiler books and articles for that.
This book also has a couple chapters on efficiency concerns for implementations of Lisp, chapters 9 and 10, which look at both dev-side and compiler-side approaches to more efficient Lisps.
Despite the focus on GOFAI, I think the lessons apply to good Lisp programs in general from a practitioner's PoV. If you want a more abstract vantage then I'd say the classic "Structure and Interpretation of Computer Programs" by Abelson & Sussman should be mentioned. It includes a lot of diagrams of CONS structures to keep things focused but it doesn't have the kind of full case study applications of the Norvig text.
It's funny how all the good books on Lisp implementations assume that first you start with a Lisp. I wonder if this goes back to there being Lisp machines on which the language was already deeply situated.
This is the half-page of code that Alan Kay famously described as "the Maxwell's equations of software."
Common Lisp and MACLISP before it and Lisp 1.5 before that worked by providing a running program that implements the functions given in that half page and applies them and their effects iteratively to their own environment.
In other words, the basic model is that Lisp is a running program that you modify interactively by feeding expressions to it one after another.
Common Lisp's model still works like that: when you give it a source file it reads one expression after another from the file, evaluating the expressions as it goes, and altering the running environment to reflect any changes that they make, such as adding new definitions, updating data structures, and so on.
The Lisp reads the next well-formed expression, converting it into Lisp data structures. It then evaluates the resulting data structure, yielding some number of values and updating the environment at the same time. (In Common Lisp even pure functions have side effects if evaluated by the read-eval-print loop because the standard defines a globally-accessible variable named * that contains the value returned by the most recently-evaluated expression).
Common Lisp's design reflects this basic model, and much of its standard library is concerned with making it convenient to work this way. The ANSI standard likewise reflects this basic model of computation, including features specifically designed to support this style of interactive programming.
The process of evaluation allows, but does not require, compilation. Common Lisp interpreters (usually called "evaluators") do exist, but most practical implementations provide compilers that compile each expression in order to evaluate it. Some implementations are "compiler only": that is, every expression is always compiled in order to be evaluated, whether it's in a source file or typed at a repl prompt.
To answer some of your specific questions more directly:
> is behavior when running a script in "interpreter" mode guaranteed to
> be the same as when running in "native compiled code"?
"Guaranteed" is a strong word. ANSI specifies the behavior, and it's generally the same whether code is interpreted or compiled. That may be hard to achieve for some expressions, but if you find an example of different behavior, that's most likely a bug in ANSI compliance.
(I should allow for the possibility that the ANSI spec has some corner somewhere that allows for a difference, but I can't think of any off the top of my head. Of course, the spec is large and my memory is imperfect.)
> At what point does the compiler create an intermediate representation?
Depends on what you mean. Under some interpretations and in some implementations there may not be an intermediate form.
The normal lifecycle of an evaluation is:
- read: ingest text and convert it to Lisp data
- macroexpand: rewrite any macro expressions in the data
- eval: use eval and apply on the data to yield some result values
- print: convert the result values to text in a standard format and print it to *standard-output*
You might regard the result of the read function as an intermediate form, but I would say that what read produces is Lisp source code. In my view, the original text is not Lisp source code; it's a serialization of Lisp source code. Read converts the text into Lisp source code.
ANSI does not specify in detail exactly what eval has to do in order to yield results. It specifies abstractly what each function, macro, and special form ...
I suggest “Lisp in Small Pieces” as a great introduction to implementing a Lisp. It focuses on Scheme rather than CL, but all of the knowledge is transferable. In the book, you go through multiple basic implementations, each successively more sophisticated, starting with basic interpretation and moving through more optimizations toward a compiler.
> While I'm here I'll ask: does anybody have a recommendation for resources on learning lisp that focus on how the interpreter/compiler works?
Yes: Lisp in Small Pieces, by Christian Queinnec.
I've read a fair number of books on Lisp, including Paul Graham's On Lisp and ANSI Common Lisp, and IMO Lisp in Small Pieces is the best for understanding how to implement a Lisp. LiSP covers interpreters and compilers, and it covers how to implement call/cc. Like Paul Graham's books on Lisp, LiSP is highly enjoyable -- these are books I read for fun.
> Like, is behavior when running a script in "interpreter" mode guaranteed to be the same as when running in "native compiled code"?
The ANSI Common Lisp standard applies to all compliant implementation, regardless of whether they interpret or compile the language. In earlier Lisps there might have been a difference, in Common Lisp that would be a bug.
> At what point does the compiler create an intermediate representation?
??? Are you referring to macro-expansion time?
> Why does SBCL not use LLVM?
Other than for historic reasons, why would it?
> At what point are #-starting words(read macros?) evaluated and how is that different from interpreting to compiling
You're answering your own question. Read macros are evaluated at read time.
I'm not sure whether those questions are really all that relevant to someone just starting to learn the language.
Practical Common Lisp is a fine starting point and Common Lisp The Language (2nd edition) will keep you busy for a looong time.
I am in a similar situation as you, but in a lot of ways you're asking more sophisticated questions than me. FWIW, I've been building a little toy lisp-scheme like scripting language as a learning tool: https://github.com/zeraholladay/lispm/tree/main. It's been a lot of fun and I've really enjoyed exploring parts of CS that my career hasn't really taken me to.
This book was an important part in my learning of Lisp, along with Common Lisp the Language 2ed. It did leave me with a few biases that took a while to overcome though, like biases against CLOS and verbose names.
I consider this book to be almost like a forerunner of the style of book that JavaScript: the Good Bits is, in that it is advocating one's use of a language to a particular subset rather being an impartial description of the whole language.
These notes may appear to be overly critical or an extremely pedantic reading but they're pretty good, and it's bit like like having the teacher across from you while you're reading. But some notes are a little excessive and the teacher comes off as overbearing. For example, the emphasis on the function style is itself pedagogical, hence the avoidance of `loop` and the preference for recursion over iteration. Some are more excessive than that, like Chapter 2 page 18 (the author shouldn't use ~S if it hasn't been properly introduced yet, so sticking with ~A is actually the right choice.). Overall it's a great guide to reading, especially as it gives the student a sense for the higher-order stylistic considerations when writing a more malleable language like lisp.
These are very good notes. Here's a few of my notes on these notes:
> Naming: Like Unix, Graham likes short names, often to the point of crypticness. See my notes on naming for a better way.
Eh, you should see Haskell, where conventions are to use `x` for an object of some type and `xs` for a list of `x`, for example. And not just x/xs, but h/hs, etc. Once you get used to thinking of polymorphic functions as mathematical functions then this starts seeming ideal rather than cryptic.
> Loops: Graham avoids loop, because it is so easily misused and different from the functional programming style. Sometimes, however, loop is the clearest simplest way to write something.
I agree, but this is probably didactic. Many Lisp teachers insist on students learning to think of recursion as a natural way to do iteration. I'm not sure I agree with that viewpoint, but I don't think it's unreasonable. The issue I have is that one really has to learn how to recognize tail recursion instantly, even mutual tail recursion, and then also how to recognize when non-tail recursion (especially mutual non-tail recursion) gets optimized by the compiler into a loop with an explicit stack (if at all).
> Preference for recursion over iteration, even if it might lead to code that causes stack overflows on very long lists.
Yes, well, see above. I agree that starting Lisp programmers will take some time to learn how to use tail recursion, but it's not a problem for a) an experienced Lisp programmer, b) a Lisp teacher who is trying to drive this point home.
> Backtraces are incredibly useful for debugging. Be aware though that tail-call elimination may have removed some function calls from the stack.
This is true in many languages. I've seen this in C. You have to get used to it because tail call optimization is so important.
> bfs is a terrible name, because it says how it works, not what it does.
Sometimes "how it works" has to bleed into the naming somehow. Generally (i.e., not just in Lisp) this function could be `search` (which is what TFA wants) in some namespace/package/whatever that where the function implements [part of] an interface and the provider's name denotes that this is a breadth-first search, but it's very important to understand the trade-offs of depth-first and breadth-first searching and which you get needs to be observable somewhere.
20 comments
[ 3.9 ms ] story [ 58.3 ms ] threadWhile I'm here I'll ask: does anybody have a recommendation for resources on learning lisp that focus on how the interpreter/compiler works? Here's what I tried so far: 1) Started Practical Common Lisp, but I found it lacking in the specifics. Then I 2) tried going to the specification but that was way too much. Then I 3) tried Common Lisp The Language and, while I liked the precise definitions a lot, it was a lot to keep in mind at the same time as learning the fundamentals. Right now I'm 4) back at Practical Common Lisp, skipping most of the text and reading surrounding paragraphs whenever if I find a piece of code I don't understand.
I wanted something that will not explain the standard library; I'd rather read the documentation for that. I wanted to know more precisely what happens throughout the program's life: Like, is behavior when running a script in "interpreter" mode guaranteed to be the same as when running in "native compiled code"? At what point does the compiler create an intermediate representation? Why does SBCL not use LLVM? At what point are #-starting words(read macros?) evaluated and how is that different from interpreting to compiling. How do I control the amount of optimization the compiler will do? Will the interpreter ever try to optimize? Is garbage collection implementation-defined? How will implementations change in behavior?
On QuickLisp, use Ultralisp, as an updated mcclim with an up to date clx it's like night and day on speed.
If you use Portacle, just run:
(ql-dist:install-dist "http://dist.ultralisp.org/" :prompt nil)
Otherwise, install Ultralisp and then eval that function to get an updated QL base).
Recommended book: https://www.cs.cmu.edu/~dst/LispBook/
Portacle which bundles Emacs + SBCL: https://portacle.github.io/
"Lambda: The Ultimate Goto"
( https://en.wikisource.org/wiki/Lambda:_The_Ultimate_GOTO )
as they go into how the Lisp-y abstractions can correspond to machine code (as in interpreters and compilers).
This won't hold your hand through implementing Lisp within another language like C or Rust, but it does show the representation of Lisp within Lisp (and a few chapters on implementing a logic programming language in Lisp as well). Most of the task of transpiling into another language reduces to how you represent functions and function results, and the extent to which your compiler reduces specific built-ins. There's a range of implementation here that you can find covered in PL research papers, but you may be better off looking through compiler books and articles for that.
This book also has a couple chapters on efficiency concerns for implementations of Lisp, chapters 9 and 10, which look at both dev-side and compiler-side approaches to more efficient Lisps.
https://www.goodreads.com/book/show/15534706
Despite the focus on GOFAI, I think the lessons apply to good Lisp programs in general from a practitioner's PoV. If you want a more abstract vantage then I'd say the classic "Structure and Interpretation of Computer Programs" by Abelson & Sussman should be mentioned. It includes a lot of diagrams of CONS structures to keep things focused but it doesn't have the kind of full case study applications of the Norvig text.
https://www.goodreads.com/book/show/43713
It's funny how all the good books on Lisp implementations assume that first you start with a Lisp. I wonder if this goes back to there being Lisp machines on which the language was already deeply situated.
https://michaelnielsen.org/ddi/wp-content/uploads/2012/04/Li...
This is the half-page of code that Alan Kay famously described as "the Maxwell's equations of software."
Common Lisp and MACLISP before it and Lisp 1.5 before that worked by providing a running program that implements the functions given in that half page and applies them and their effects iteratively to their own environment.
In other words, the basic model is that Lisp is a running program that you modify interactively by feeding expressions to it one after another.
Common Lisp's model still works like that: when you give it a source file it reads one expression after another from the file, evaluating the expressions as it goes, and altering the running environment to reflect any changes that they make, such as adding new definitions, updating data structures, and so on.
The Lisp reads the next well-formed expression, converting it into Lisp data structures. It then evaluates the resulting data structure, yielding some number of values and updating the environment at the same time. (In Common Lisp even pure functions have side effects if evaluated by the read-eval-print loop because the standard defines a globally-accessible variable named * that contains the value returned by the most recently-evaluated expression).
Common Lisp's design reflects this basic model, and much of its standard library is concerned with making it convenient to work this way. The ANSI standard likewise reflects this basic model of computation, including features specifically designed to support this style of interactive programming.
The process of evaluation allows, but does not require, compilation. Common Lisp interpreters (usually called "evaluators") do exist, but most practical implementations provide compilers that compile each expression in order to evaluate it. Some implementations are "compiler only": that is, every expression is always compiled in order to be evaluated, whether it's in a source file or typed at a repl prompt.
To answer some of your specific questions more directly:
> is behavior when running a script in "interpreter" mode guaranteed to > be the same as when running in "native compiled code"?
"Guaranteed" is a strong word. ANSI specifies the behavior, and it's generally the same whether code is interpreted or compiled. That may be hard to achieve for some expressions, but if you find an example of different behavior, that's most likely a bug in ANSI compliance.
(I should allow for the possibility that the ANSI spec has some corner somewhere that allows for a difference, but I can't think of any off the top of my head. Of course, the spec is large and my memory is imperfect.)
> At what point does the compiler create an intermediate representation?
Depends on what you mean. Under some interpretations and in some implementations there may not be an intermediate form.
The normal lifecycle of an evaluation is:
- read: ingest text and convert it to Lisp data
- macroexpand: rewrite any macro expressions in the data
- eval: use eval and apply on the data to yield some result values
- print: convert the result values to text in a standard format and print it to *standard-output*
You might regard the result of the read function as an intermediate form, but I would say that what read produces is Lisp source code. In my view, the original text is not Lisp source code; it's a serialization of Lisp source code. Read converts the text into Lisp source code.
ANSI does not specify in detail exactly what eval has to do in order to yield results. It specifies abstractly what each function, macro, and special form ...
Also the rest of his blog is worthy of at least a skim.
Yes: Lisp in Small Pieces, by Christian Queinnec.
I've read a fair number of books on Lisp, including Paul Graham's On Lisp and ANSI Common Lisp, and IMO Lisp in Small Pieces is the best for understanding how to implement a Lisp. LiSP covers interpreters and compilers, and it covers how to implement call/cc. Like Paul Graham's books on Lisp, LiSP is highly enjoyable -- these are books I read for fun.
The ANSI Common Lisp standard applies to all compliant implementation, regardless of whether they interpret or compile the language. In earlier Lisps there might have been a difference, in Common Lisp that would be a bug.
> At what point does the compiler create an intermediate representation?
??? Are you referring to macro-expansion time?
> Why does SBCL not use LLVM?
Other than for historic reasons, why would it?
> At what point are #-starting words(read macros?) evaluated and how is that different from interpreting to compiling
You're answering your own question. Read macros are evaluated at read time.
I'm not sure whether those questions are really all that relevant to someone just starting to learn the language.
Practical Common Lisp is a fine starting point and Common Lisp The Language (2nd edition) will keep you busy for a looong time.
This is the subject of the classic book "Structure and interpretation of computer programs"
Why doesn't GCC use LLVM? Why is Zig writing their own backend?
https://www.cs.cmu.edu/~dst/LispBook/
A no brainer setup:
https://portacle.github.io/
happy hacking.
I consider this book to be almost like a forerunner of the style of book that JavaScript: the Good Bits is, in that it is advocating one's use of a language to a particular subset rather being an impartial description of the whole language.
> Naming: Like Unix, Graham likes short names, often to the point of crypticness. See my notes on naming for a better way.
Eh, you should see Haskell, where conventions are to use `x` for an object of some type and `xs` for a list of `x`, for example. And not just x/xs, but h/hs, etc. Once you get used to thinking of polymorphic functions as mathematical functions then this starts seeming ideal rather than cryptic.
> Loops: Graham avoids loop, because it is so easily misused and different from the functional programming style. Sometimes, however, loop is the clearest simplest way to write something.
I agree, but this is probably didactic. Many Lisp teachers insist on students learning to think of recursion as a natural way to do iteration. I'm not sure I agree with that viewpoint, but I don't think it's unreasonable. The issue I have is that one really has to learn how to recognize tail recursion instantly, even mutual tail recursion, and then also how to recognize when non-tail recursion (especially mutual non-tail recursion) gets optimized by the compiler into a loop with an explicit stack (if at all).
> Preference for recursion over iteration, even if it might lead to code that causes stack overflows on very long lists.
Yes, well, see above. I agree that starting Lisp programmers will take some time to learn how to use tail recursion, but it's not a problem for a) an experienced Lisp programmer, b) a Lisp teacher who is trying to drive this point home.
> Backtraces are incredibly useful for debugging. Be aware though that tail-call elimination may have removed some function calls from the stack.
This is true in many languages. I've seen this in C. You have to get used to it because tail call optimization is so important.
> bfs is a terrible name, because it says how it works, not what it does.
Sometimes "how it works" has to bleed into the naming somehow. Generally (i.e., not just in Lisp) this function could be `search` (which is what TFA wants) in some namespace/package/whatever that where the function implements [part of] an interface and the provider's name denotes that this is a breadth-first search, but it's very important to understand the trade-offs of depth-first and breadth-first searching and which you get needs to be observable somewhere.