LISPcraft

LISPcraft

nil

Robert Wilensky. LISPcraft. W.W. Norton. ISBN 0-393-95442-0. 1984.

Hard to know whether to include this as an introduction or collection of applications, since it runs all the way from basic uses to pattern-matching and associative retrieval, by way of the non-list data types in Lisp, and includes discussion of the symbol table and other internals that definitely fall into the “advanced” category.

However, this was my second introduction to Lisp (after SICP), so it has a fond place in my memory. The fact that it deals with language internals isn’t a bad thing, because it deals with the basics so well. It’s very much a traditional programming introduction focusing on the “needed” parts of the language. It pre-dates the Common Lisp standard and doesn’t touch on CLOS, which perhaps make it a less appropriate choice for newcomers these days than Practical Common Lisp.


There is also a second edition. I haven’t read it, but it seems that it addresses at least the concern about being non-standard:

Robert Wilensky. Common LISPcraft. W.W. Norton. ISBN 978-039395544-6. 1986.

The CONNIVER reference manual

The CONNIVER reference manual

Drew McDermott and Gerald Jay Sussman. The Conniver Reference Manual. Technical report AIM-259a. MIT AI Laboratory. 1974.

I think Conniver may have a claim to being the most influential language you’ve never heard of. It’s a mostly forgotten Lisp variant that was a laboratory for some radically different language design ideas, and a precursor to a surprising set of features – many of which are still uncommon in the mainstream.

Conniver was intended to manage knowledge databases. This does make the report slightly hard to read in places, as there are a lot of explicit references to planning techniques wrapped-up with language mechanisms that don’t really depend on them.

Conniver is (to the best of my knowledge) the first appearance of generators in a programming language. It is therefore a distant precursor of all the lazy functional languages and libraries, as well as the generators found in Python. Implementing generators within a language (rather than as a built-in part of one) requires control structures that can be exited and re-entered, and therefore needs more flexible frames for controlling executing code rather than conventional stack frames that are unwound destructively on return.

The obvious (for Lisp, anyway) next step is to make these “hairy” control structures visible within the language, to allow them to be re-arranged in interesting ways. It does this by exposing the structure of frames, consisting of:

  • the bound variables
  • the state of the ongoing computation within the frame (e.g., the program counter)
  • a link (the ALINK) to the frame within which free variables should be looked-up
  • a link (the CLINK) to the frame to which control should return on exit from the frame

This structure in turn mandates the use of spaghetti stack (or parent pointer trees) where frames are implemented using lists that can be combined in richer ways than actual, literal stacks. Thee are the underpinnings of several different common structures:

  • generators and continuations
  • closures
  • non-local transfers, like CATCH and THROW in Common Lisp, and therefore probably encompassing the entire condition system
  • functions with access to extra state (as with object methods, but in this case used as callbacks for database updates)
  • symbolic debuggers (not mentioned in the text)
  • lexical versus dynamic variable scope (not mentioned in the text, and I think it’s a binary choice between one or the other depending on the ALINK, rather than accommodating lexical and “special” variable classes as Common Lisp does)

So these features are constructed in Conniver from more basic mechanisms rather than being provided built-in. I’m fascinated by what other structures one might build when every frame has two independent super-frames (one for variable lookup,one for control return) instead of one, and both can be modified independently. This is radically different to most languages in which frames are hidden and their manipulation reserved for the compiler and run-time: it’s a set of ideas that re-surface at the object level in metaobject protocols.

Common Lisp: the language

Common Lisp: the language

nil

Guy Steele. Common Lisp: The Language. Digital Press. ISBN 1-55558-041-6. 1990.

The reference manual for Common Lisp, also available online in its entirety. This is very much a reference manual and not a tutorial, but having said that it’s a lot more accessible than many such documents.

It’s remarkable that Common Lisp’s standard has been stable for over thirty years, despite enormous advances in Lisp practices in that time. It shows the care that went into the original standardisation process, but also the effects of some detailed technical choices and (especially) the use of macros in preference to new core mechanisms.

However, it has to be said that the standard also fixed in place certain choices that now seem questionable. It’s a matter of opinion, of course, but personally I think the questionable set includes at least: multiple-value returns and binds, which are unnecessary when you can return lists and destructure them and that impinge on the minimalism of the core language; and allowing symbols to be bound simultaneously to values and functions, which unnecessarily treats the two differently (and for which reason it was removed from Scheme).

Structure and interpretation of computer programs

Structure and interpretation of computer programs

nil

Harold Abelson and Gerald Jay Sussman. Structure and Interpretation of Computer Programs. MIT Press. 1985.

A book once described (by me, actually) as “the only computer science book worth reading twice”, and which was the foundational text for teaching programming at MIT for decades.

There are many reasons that this book is so popular and long-lived. It’s resolutely an introductory text, but it treats topics that are uncommon in introductions, and does so to a depth that’s quite astonishing – although it has to be said that the authors avoid the more complex constructions like conditions and the complexities of macros, (They do deal with continuations, however, which are essential for good Scheme programming.)

But what other introduction to programming includes a complete meta-linguistic re-implementation of the language itself? – and in two different styles! It can do this because Scheme is so regular and so simple – homoiconic (one representation for programs and data), (although they don’t use that term).

Learn Common Lisp in Y minutes

Learn Common Lisp in Y minutes

https://learnxinyminutes.com/docs/common-lisp/

A one-web-page introduction to Common Lisp covering pretty much all the language in enough detail to at least start writing simple command-line programs (and understanding those of others). Includes macros and CLOS. Quite an achievement to make it all so readable.