A micro-manual for Lisp: Not the whole truth

A micro-manual for Lisp: Not the whole truth

John McCarthy. A Micro-Manual for Lisp: Not the Whole Truth. ACM SIGPLAN Notices 13, pp.215–216. 1978.

A “manual” in the sense of providing a complete implementation of Lisp – in Lisp itself.

Is that useful? A semantics expert would say “no”, since such a model has no real explanatory power: the recursion doesn’t bottom-out to define the concepts. However, a programming language expert might disagree and observe that this is meta-linguistic abstraction, the use of one high-level language to capture the definition of another. The “host” language provides a higher level of abstraction than is usual when writing interpreters and compilers, so it becomes easier to experiment with different forms of “target” language as there’s less low-level work to do. This benefit exists even when host and target are the same: essentially the target is bootstrapped and can then be adjusted while running within an earlier version of itself.

As far as I know this is the first example of meta-linguistic abstraction in the computer science literature. The idea was popularised by SICP (using Scheme), and forms the basis for a lot of modern bootstrapped compilers.

The Lisp machine

The Lisp machine

Richard Greenblatt. The Lisp Machine. Working paper 79. MIT AI Laboratory. 1974.

A description of the architecture later built and sold by LMI.

A visionary description of a machine to run Lisp at a “non-prohibitive cost” of $70,000 per system. (The web tells me that this is the equivalent of $440,000 in 2024.) A completely integrated system based on a Cons processor and using a PDP-11 as a console. A relocating, compacting, garbage collector with invisible forwarding pointers. Non-linear spaghetti stacks to support advanced programming constructs.

One of the many notable facets of this design is one of its proposals (the “frame pushdown list”) to avoid excessive conses and garbage collection overhead by maintaining lists of blocks of particular sizes. It uses this approach to manage the creation of call stack frames; modern Python implementations use this scheme throughout to avoid heap fragmentation through allocating and re-allocating blocks of different sizes. (Lisp has this feature generally, of course, with its use of fixed-size cons cells.)

It’s also fascinating to see that, even at this early stage, hardware design was being seen as an exercise in refinement to maintain software-level abstractions even as features were being pushed into hardware – while still providing optimised implementations that were invisible to the programmer.

Lisp for the web

Lisp for the web

nil

Adam Tornhill. Lisp for the Web. Leanpub. 2015.

A short, practical guide to build a dynamic web site entirely using Common Lisp. Makes extensive use of several libraries, including the intriguingly-named hunchentoot web server (named after a never-staged musical written by Frank Zappa), the CL-WHO HTML generator, and – perhaps most interesting – the Parenscript Lisp to Javascript compiler.

One gain from using Lisp is the ability to wrap-up standard constructions like page templates as macros. Other than this, it’s hard to assess whether the gains are all that significant. One interesting point is that the whole development occurs in Lisp, so there’s no cognitive dissonance between writing the back-end and the front-end: essentially the same argument for using node.js as a back-end framework. While Parenscript isn’t a fully-featured Lisp-in-the-browser it again can benefit from macros and other features. There’s a throwaway comment about linking it to jQuery, although that isn’t demonstrated in practice: it feels intriguing, though, especially if there’s a way to represent jQuery functionality idiomatically in Lisp.

List processing

List processing

J.M. Foster. List Processing. Macdonald and Co. 1967.

A slim volume discussing list processing with reference to Lisp and to other list processing systems of the time (including some libraries embedded into Fortran).

The most fascinating part of the book is its bibliography, which references a lot of papers that have disappeared from the collective memory of computer science, but whose implications were profound.

Recursive functions of symbolic expressions and their computation by machine, Part I

Recursive functions of symbolic expressions and their computation by machine, Part I

John McCarthy. Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Communications of the ACM 3, pp.184–195. 1960.

The original Lisp paper from 1960, which opens:

A programming system called LISP (for LISt Processor) has been developed for the IBM 704 computer…

The paper then proceeds to lay out everything that’s since been built on: the basic constructs, the use of cons cells (pairs) as a data representation, the world’s first garbage collection algorithm, an equational semantics, and ideas for interpretation and compilation. It’s awesome, and humbling to read it and realise its age and the vision of computing it developed.

(Despite this paper being labelled Part I, incidentally, there isn’t a part II.)