Category: Books

John Allen (1937-2022) and Anatomy of LISP

When I began researching the history of LISP in 2005 [1], one of the first people I got in touch with was John Allen. Not only had he helped create Stanford LISP 1.6, written an influential book on the LISP language and its implementation (Anatomy of LISP), but also he and his wife, Ruth Davis, had organized (and funded!) the 1980 LISP conference [2] and founded The LISP Company, which produced TLC Lisp for Intel 8080- and 8086-based microcomputers. By the time I got in touch with him he was busy preparing a talk for another LISP conference [3], but told me:

in 1964 i got interested in lisp and wrote to mit. tim hart responded, sending the distribution tape and wished my luck. i needed it because the mit tape was for a machine related, but not identical, to the one i had at work. so to make a long story short, i got the tape converted and running.

what i have is a november 1964 listing of the tape’s contents. that includes the source card-images for lisp 1.5 plus the initial lisp library written in lisp. that includes bunches of test cases, the compiled compiler and other random crap. the listing does have some of my comments related to the conversion, but the original text is quite clear.

i was planning to bring it along when i go to stanford june 19-22, and would be willing to let someone scan it if desired. i’ve got other crap around in random piles, boxes, and “archives.”

I gave a 5-minute pitch at the conference for my LISP history project, but did not catch up with John. I tried to stay in touch with periodic emails, and ran into John and Ruth in person at John McCarthy’s 2012 Stanford memorial. But somehow we could never coordinate to scan his listing and other items from his “archives”.

Then in 2022 Ruth contacted me with the sad news that John had died in March of that year. Remembering our long correspondence regarding John’s LISP materials, she invited me to help her sort through John’s papers:

I have come across a PDP-1 notebook with a THOR manual (I think), some tapes containing I know not what, some copies of handwritten lecture notes (I think) of Dana Scott and Georg Kreisel. And I haven’t made it to the closet yet. I am throwing out a lot, and I may not have the right sensibilities to know what may be of interest.

I jumped at the chance, and spent an afternoon with her, bringing home several boxes of materials including the 1964 LISP 1.5 listing. Also she told me she’d discovered the copyright release for John’s famous book Anatomy of LISP and would be happy for an electronic edition to be posted online. That suggested an opportunity: ACM had included Anatomy in their 2006 Classic Books collection, but at that time the copyright status was not clear and an electronic edition could be be included, as was possible for many of the books in the collection. John wrote the book using Larry Tesler’s PUB document compiler, and many drafts were preserved in Bruce Baumgart’s SAILDART archive. John’s original plan was to adapt PUB’s output to a phototypesetter to achieve “book quality” output, but that did not work out so the book was published from pages printed on a Xerox XGP printer, at a low 192 dots/inch. Bruce Baumgart very generously did some work to recreate a bitmap-based PDF from SAILDART files, but it was still at 192 dpi and the content didn’t quite match the published version. So Ruth and I offered a clean, scanned PDF to ACM, and after verifying the rights they added this PDF to the website. [4]

The Computer History Museum accepted Ruth’s donation of the LISP 1.5 listing, some Stanford PDP-1 timesharing system documents (TVEDIT, RAID, and THOR), John’s Alvine LISP editor manual, John’s 1971-1972 lecture notes for the E123A course he taught at UCLA, three early MDL/MUDDLE documents, some ECL documents from Harvard, some early theorem proving reports (John implemented a theorem prover with David Luckham [5]), reports by Christopher Stratchey, Dana Scott, and Peter Wegner, an early 1979 version (by Harold Abelson and Robert Fano) of Structure and Interpretation of Computer Programs, and the four magnetic tapes Ruth had mentioned. (Al Kossow has promised to digitize the tapes; I suspect one contains John’s theorem prover; two may contain other LISP code.)

John Allen was a passionate computer scientist and educator. He held programming or research positions at Burroughs Sierra Madre, UC Santa Barbara, and GE Research (Goleta) in the early 1960s and at HP Labs and Signetics in the 1970s, as well as programming and research positions at Stanford from 1965 to about 1975, interspersed with teaching assignments at UCLA, UC Santa Cruz, and San Jose State. He also periodically taught part-time at Santa Clara University from 1984 to 2005. I wish I could have gotten to know him better.

[1] Paul McJones. Archiving LISP History, Dusty Decks blog, 22 May 2005. https://mcjones.org/dustydecks/archives/2005/05/22/40/

[2] Ruth E. Davis and John R. Allen, co-organizers. Conference Record of the 1980 LISP Conference. Later reissued as: LFP ’80: Proceedings of the 1980 ACM conference on LISP and functional programming. https://dl.acm.org/doi/proceedings/10.1145/800087

[3] John Allen. History, Mystery, and Ballast. International Lisp Conference, Stanford University, 2005. https://international-lisp-conference.org/2005/speakers.html#john_allen

[4] John Allen. Anatomy of LISP. McGraw-Hill, Inc., 1978. Part of ACM’s Classic Books Collection. ACM Digital Library (open access)

[5] John Allen and David Luckham. An interactive theorem proving program. In Machine Intelligence 5, B. Meltzer and D. Michie, Eds., Edinburgh. U. Press, Edinburgh, 1970, pp. 321- 336.

P.S. After some study of the Georg Kreisel notes that Ruth mentioned, I believe they correspond to this item:

57. Kreisel, G. Intuitionistic Mathematics. Lecture delivered at Stanford University, 1962?, 270 pp. [Mimeographed].

in this Kreisel bibliography:

Authors’ Edition of Elements of Programming

Cover of the book Elements of Programming by Alexander Stepanov and Paul McJones
Elements of Programming by Alexander Stepanov and Paul McJones

After almost 10 years in print, Addison-Wesley elected to stop reprinting Elements of Programming and has returned the rights to us. We are releasing an “Authors’ Edition” in two versions:

1. A free PDF (download from here)

2. A trade paperback from our imprint, Semigroup Press (purchase here or at Amazon – US$14.20 in either case).

The text is unchanged from the previous printing, except for corrections for all errata reported to us.

Update 5/15/2020: Lulu seems to have dropped their discount feature, so the price is the same everywhere.

Update 11/6/2019: Added Amazon link.

New Japanese edition of Elements of Programming

Second Japanese edition of Elements of Programming
Elements of Programming, second Japanese edition
The original Japanese translation of Elements of Programming went out of print. But Yoshiki Shibata, the translator, proposed to Tokyo Denki University Press that they publish a new edition, and they agreed. It is available via Amazon.jp, and joins the English, Russian, Chinese, and Korean editions.

We wrote a special preface for this edition:

To our Japanese readers:

We are very grateful to our publisher and our translator Yoshiki Shibata for this opportunity to address our Japanese readers.

This book is in the spirit of Japanese esthetics: it tries to say as much as possible in as few words as necessary. We could not reduce it to 17 sounds like a traditional haiku, but we were inspired with its minimalist approach. The book does not have much fat. We actually hope that it does not have any fat at all. We tried to make every word to matter.

We grew up when Japanese engineering was beginning to revolutionize the world with cars that did not break and television sets that never needed repairs. Our hope is that our approach to software will enable programmers to produce artifacts as solid as those products. Japanese engineers changed the experience of consumers from needing to know about cars, or, at least, knowing a good mechanic, to assuming that the vehicle always runs. We hope that the software industry will become as predictable as the automotive industry and software will be produced by competent engineers and not by inspired artist-programmers.

Our book is just a starting point; most work to industrialize software development is in the future. We hope that readers of this book will bring this future closer to reality.

We would like to thank Yoshiki Shibata not only for his very careful translation, but also for finding several mistakes in the original.

Korean edition of Elements of Programming

In addition to the English, Korean edition of Elements of Programming Japanese, Russian, and Chinese editions, Elements of Programming is now available in a Korean edition published by Pearson Education Korea and available from Kyobo Book Centre. Five editions, five scripts.

P.S. I can’t find a listing for the book at www.pearson.co.kr; I will update this post and our book website if I hear of one.

Algol 68: Informal Introduction and more

Cover of Informal Introduction to Algol 68Several years ago I began an archival collection for the Algol family of programming languages: Algol 58 (originally known as the International Algorithmic Language), Algol 60, and Algol 68. I began looking for implementations of Algol 58 and Algol 60. Since then I’ve also found information (including, in some cases, source code), for many Algol 68 implementations.

I’d like to announce the return of a very useful Algol 68 resource: a scanned copy of Informal Introduction to Algol 68, posted by permission of coauthor Charles H. Lindsey and copyright holder IFIP. This is the revised 1980 reprint of the second (“completely revised”) edition of 1977. For convenience, I’ve also posted separate files containing the large fold-out Table of Contents and the appendix of Syntax Charts.

This book, together with Marcel van der Veer’s modern Algol 68 Genie implementation and the extensive documentation accompanying it (including a hypertext version of the Revised Report) provide an excellent way to study Algol 68.

In addition to the above-mentioned, a number of other people have contributed to the overall Algol archive project. I’d like to single out Neville Dempsey for his dedication to spreading knowledge of and appreciation for Algol 68.

50th Anniversary of LISP 1.5 Programmer’s Manual

Cover of LISP 1.5 Programmer's Manual
I just noticed that August 17 was the 50th anniversary of the LISP 1.5 Programmer’s Manual by John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart, and Michael I. Levin. On that day in 1962 it was published as a bound report of the Computation Center and Research Laboratory of Electronics of the Massachusetts Institute of Technology. It was also published by MIT Press — perhaps simultaneously — and is still in print. A second edition was released in 1965; the only difference that I see comparing tables of contents is the addition of Appendix I: LISP for SHARE distribution.

This was of course the first book on LISP. It is a reference manual rather than a textbook, but many people managed to learn LISP from it, and a number of people managed to implement LISP from it. Today ACM’s Digital Library lists 327 citations for it, and Google lists about 23,900 hits. I’m pleased to say that #1 on Google is the authorized PDF at my History of LISP archive at the Computer History Museum.

Through the generosity of several people, the History of LISP archive includes not only the book but also several versions of the underlying source code:

If you’re resourceful and you’d like to actually run the system described in this book, you don’t need an IBM 7090 or a time machine; the SIMH simulator package and the files and information here are sufficient; scroll down until you find “Running Lisp 1.5 in the SIMH IBM 7094 emulator.”

Elements of Programming video

On November 3, 2010, we presented a lecture on Elements of Programming to the Department of Electrical Engineering Computer Systems Colloquium (EE380) at the Stanford University. While we both take responsibility for the contents, Alex Stepanov lectured. A video of the lecture is online at Stanford; eventually it will also be available via YouTube and iTunes.

Update 7/11/2012: The video made its way to YouTube and iTunes. By the way, the abstract (with a link to the slides) is here.

Elements of Programming

Elements of Programming, by Alexander Stepanov and Paul McJones, was published this month by Addison-Wesley Professional. From the preface:

This book applies the deductive method to programming by affiliating programs with the abstract mathematical theories that enable them to work. Specification of these theories, algorithms written in terms of these theories, and theorems and lemmas describing their properties are presented together. The implementation of the algorithms in a real programming language is central to the book. While the specifications, which are addressed to human beings, should, and even must, combine rigor with appropriate informality, the code, which is addressed to the computer, must be absolutely precise even while being general.

The roots of the book go back many years. In 1976 Alex had two important revelations: an essential part of programming is to find the most general form of each algorithmic component and, as he wrote a few years ago, “Our ability to restructure certain computations to be done in parallel depends on the algebraic properties of operations. For example, we can re-order a + (b + (c + d)) into (a + b) + (c + d) because addition is associative.” Much of his subsequent career, including his development of the C++ Standard Template Library, can be described as pursuing the consequences of these ideas.

I met Alex in early 2003, shortly after each of us joined Adobe Systems. As I mentioned in an earlier post, we discovered a common connection, to John Backus. Our first collaboration was co-chairing a company-wide internal engineering conference in 2004. After that I began attending the course on Foundations of Programming that Alex was teaching at Adobe. In 2005, I joined Alex in the Software Technology Lab, which was led by our colleague Sean Parent. In 2007, Alex invited me to work with him on converting his course notes into a book. We soon concluded that a fresh start was necessary. About two years later, Elements of Programming was complete.

The code in the book can be downloaded from the companion web site.

ACM Classic Books Series

Last summer, ACM posted PDF versions of some books in its Classic Books Series, which resulted from a poll of ACM members initiated by David Patterson, who was then ACM President. The books are accessible to anyone who creates a free ACM Web Account.

The available books include:

Update: I had neglected to include the book by Aho and Ullman..

Update: The URL above for the ACM Classic Books Series was updated to http://www.acm.org/classics.

Classic LISP books online

With the permission of The MIT Press, I have posted online copies of two classic LISP books on the History of Lisp website at the Computer History Museum:

  • John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart and Michael I. Levin. LISP 1.5 Programmer’s Manual. The M.I.T. Press, 1962, second edition. PDF
  • Berkeley and Bobrow, editors. The Programming Language LISP: Its Operation and Applications. Information International, Inc., March 1964 and The MIT Press, April 1966. PDF

In addition to these I have continued to track down information about more versions of LISP, so the web site keeps growing.

I also gave a brief announcement of this project at the recent International Lisp Conference 2005, and a number of people volunteered to help me track down more information.

If I’ve neglected your favorite version of LISP, please go through your closet or basement and find those manuals, listings, mag tapes, etc.

[Edited 10 May 2014: community.computerhistory.org/scc => www.softwarepreservation.org, etc.]