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.

Robert L. Patrick on eMuseums

Bob Patrick is a friend of mine who entered the computer field in 1951, and whose hands-on experience running programs on an IBM 701 led him to conceive of the architecture for the General Motors/North American Monitor for the IBM 704 computer. (Bob described this work in a 1987 National Computer Conference paper. Other aspects of his extensive career are discussed in his recent Annals of the History of Computing paper and in a 2006 Oral History.)

For a number of years Bob has been involved in volunteer activities at the Computer History Museum, and recently he organized his thoughts on how museums can use the web to present technology, in the form of this article: “Museums in the Computer Age: meeting the challenge of technology“. Bob invites comments on the article via email at bobpatrick@mac.com.

SDC: Q-32 Lisp, Lisp 2, and three more; Lisp 1.5 Primer

Lisp’s birth and infancy was at MIT, but it began spreading to other places when John McCarthy went to Stanford and other project members graduated and moved on. At about this time, a project began to develop a new language, Lisp 2, that would extend Lisp to include ALGOL-like syntax, type-checking, and numeric, string, and array data types. The project was a joint development of two “think tanks”, Information International, Inc. (III) System Development Corporation (SDC) in Santa Monica, California.

The host computer for the Lisp 2 project was the AN/FSQ-32/V, a one-of-a-kind prototype built by IBM for the Air Force as a potential replacements for the SAGE AN/FSQ-7. Before the Lisp 2 project began, an innovative compiler-only implementation of Lisp 1.5 on the Q-32 was done by Robert Saunders and his colleagues.

Through the kindness of Jeff Barnett, who was one of central contributors at SDC, the History of LISP web site now includes scanned copies of the Lisp 2 source code (with annotations by Jeff) and a number of documents, including the complete TM-3417 series documenting a planned (but not completed) port to the IBM System/360. A few other early memos were previously available online as MIT Project Mac memos. Additional memos will be soon be available via the Stoyan collection.

After the Lisp 2 project was terminated, the Q-32 at SDC was replaced with an IBM System/360. The researchers still wanted to use Lisp, so Jeff Barnett and Bob Long implemented a Lisp 1.5 for the System/360. Again, Jeff loaned a copy of the original manual and also wrote new notes.

Speech understanding was a major research area for many people at SDC, including Jeff. As building blocks for the speech research, he worked on two more Lisp or Lisp-like systems:

  1. A small Lisp for the Raytheon 704 used for speech capture and low-level processing.
  2. The Crisp Lisp 2-like system for the IBM System/370.

Jeff has provided modern notes for both, and for Crisp both the original documentation as well as slides from a recent talk he gave.

Finally, another offshoot of the Lisp 2 project is the book LISP 1.5 Primer by Clark Weissman. It began as a tutorial to help SDC researchers learn Lisp, and in 1967 was published as a book by Dickenson Publishing Company, Inc., of Belmont, California. The book has long been out of print and the copyright reverted to Clark; he has given his permission for a PDF of the book to be posted on the History of LISP web site.

Update 11/26/2010: Updated URLs to reflect reorganization of http://www.softwarepreservation.org/projects/LISP/.

Herbert Stoyan’s Lisp collection at CHM

Last winter Herbert Stoyan very generously donated to the Computer History Museum the extensive collection of Lisp and AI materials he assembled in the course of his extensive study of Lisp and its history: manuals, technical reports, papers, books, listings, magnetic media, and even two Scheme chips.

Stoyan has been involved with Lisp for four decades. In the early 1970s he implemented Lisp using only Berkeley and Bobrow as a reference, and this system became the basis for all artificial intelligence work in his native East Germany. In the late 1970s he became interested in the history of Lisp, and published the book LISP – Anwendungsgebiete, Grundbegriffe, Geschichte (Akademie-Verlag, Berlin, 1980) about Lisp and its history. In 1981 he emigrated to West Germany and began a career as a university professor; by 1990 he became Professor of Artificial Intelligence of the Friedrich-Alexander-Universität Erlangen-Nürnberg. He also wrote the two-volume Programmiermethoden der Künstlichen Intelligenz (Springer, 1988) about artificial intelligence programming. (For more details, see his speaker biography from the 2007 International Lisp Conference.)

In addition to his first book, Stoyan has published a number of papers on the early history of Lisp, including:

The Herbert Stoyan Collection on LISP Programming (Lot X5687.2010) is quite large (105 linear feet, 160 boxes), and the Museum is currently in the throws of construction for the major new exhibit Revolution: The First 2000 Years of Computing. But through the combined efforts of staff and volunteers, the collection will be organized and made accessible, with portions scanned and available online. To get a taste of the depth and breadth of the collection, see Stoyan’s LISP Bibliography and searchable LISP-Museum. [Update 2015/01/10: the searchable version is no longer available.]

The arrival of this collection at CHM fulfills a dream that began for me in 2005 as I began work on History of LISP and first contacted Herbert Stoyan to timidly suggest he might contribute scans of selected items from his collection to CHM. His response — that he would be retiring in 3 years and needed to think about a permanent home for his collection — encouraged me to think that CHM might be the recipient. To get here from there, many people played important roles. At the risk of forgetting someone, I would like to thank Alex Bochannek, Grady Booch, Elizabeth Borchardt, Richard Gabriel, William Harnack, John Hollar, Paul Jabloner, Al Kossow, Karen Kroslowitz, Sara Lott, Bernard Peuto, Len Shustek, Dag Spicer, Herbert Stoyan, Kirsten Tashev, and JonL White. In addition, CHM volunteers John Dobyns and Randall Neff have labored to survey, pack, and catalog portions of the collection. (Additional volunteers would be welcome!) [Update 2015/01/10: Cataloging of the collection was completed in 2011.]

Update 2015/01/10: Stale links to Stoyan’s web sites replaced with Internet Archive Wayback Machine versions. Added link to finding aid for the Stoyan collection.

Whetstone ALGOL

Part of my motivation for starting on an ALGOL project was that Brian Randell recently obtained permission from the copyright holder to post an online copy of ALGOL 60 Implementation at CHM. This book, which he and Lawford Russell published in 1964, provides a detailed description of the ALGOL 60 compiler (known as Whetstone ALGOL) they developed for the English Electric KDF9 Computer. In January, Brian gave a talk “Reminiscences of Whetstone ALGOL” at a joint meeting of the BCS Advanced Programming Group and the Computer Conservation Society recognizing the 50th anniversary of ALGOL 60; see here for more on Whetstone. In particular, the Whetstone Algol resurrection team notes: “We now have the Walgol Translator re-keyed from a dog-eared listing, in the main, by Brian Wichmann, Graham Toal and Roderick McLeod. David Holdsworth has written an assembler and a rough-and-ready emulator. Bill Findlay is in the process of implementing a properly-enginered emulator.”

Update 7/11/2012: corrected URLs for ALGOL 60 Implementation at Software Preservation Group website and “Reminiscences of Whetstone ALGOL” at ncl.ac.uk.

Update 9/22/2010: corrected URL for Whetstone at Software Preservation Group website.


I recently created an ALGOL section at the Computer History Museum‘s Software Preservation Group web site, covering the language standardization efforts — for ALGOL 58 (also known as the International Algebraic Language), ALGOL 60, and ALGOL 68 — and also covering many implementations, dialects, and offshoots, complete with source code, manuals, and papers for many of these. The history of ALGOL has attracted many writers, and the final section of the web site links to many of their papers.

The ALGOL 58/60 implementations for which I’ve been able to find source code for include:

  • Burroughs 205 (Knuth)
  • Burroughs 220 (Erdwinn et al.)
  • Burroughs B-5500
  • DEC PDP-10 (Habermann et al.)
  • Electrologica X1 (Dijkstra and Zonneveld – Mathematisch Centrum)
  • Electrologica X8 (Kruseman Aretz – Mathematisch Centrum)
  • Electrologica X8 (Bron et al. – Technische Hogeschool Eindhoven)
  • Elliot 803 (Hoare et al.)
  • English Electric Whetstone (Randell and Russell)
  • G.E.C. process control computer (Higman)
  • Regnecentralen GIER (Naur et al.)
  • Stantec Zebra (van der Mey – Netherlands PTT)

The appendices to Maurice Halstead’s book Machine-Independent Programming (Spartan Books, 1962) contain compiler source listings of Neliac (an ALGOL 58 dialect) for the UNIVAC M-460, IBM 704, and CDC 1604.

I also found compiler source code and listings for several versions of ALGOL W.

I’ve just gotten started looking for ALGOL 68 implementations.

I welcome your comments, corrections, and suggestions for the ALGOL web site.

Don Chamberlin and the origin of SQL

Tonight Don Chamberlin will receive a 2009 Fellow Award of the Computer History Museum “for his fundamental work on structured query language (SQL) and database architectures”. The other awardees for 2009 are Robert R. Everett (M.I.T. Whirlwind and SAGE) and Federico Faggin, Marcian (Ted) Hoff, Stanley Mazor and Masatoshi Shima (Intel 4004).

In a recent oral history I conducted for the Computer History Museum, Don put into context his work designing SQL in collaboration with Ray Boyce. Don described the pre-relational database management systems, Ted Codd’s development of the relational model, various implementation projects at IBM culminating in System R, which was the first RDBMS to support SQL. Don went on to describe other pioneering relational systems, including Ingres and Oracle. He also described his subsequent work on text processing, DB/2, and XQuery.

For further historical information about Don and his work, see:

Bob Taylor recognized by The University of Texas

Last month, Bob Taylor (the subject of a recent oral history) was recognized by The University of Texas. Bob received the Graduate School Outstanding Alumnus Award, a $100,000 Presidential Endowed Fellowship was established in his name, and he gave the first in a series of lectures in the UT Graduate School’s Centential celebration. Since this is also the 40th anniversary of the first tests of the ARPAnet, it was a fitting time for Bob’s achievements to be honored.

The lecture was in the form of an interview by New York Times technology reporter John Markoff, who noted:

The Internet has many fathers, but few deserve the label more than Robert W. Taylor.

Authors M. Mitchell Waldrop (The Dream Machine) and Michael A. Hiltzik (Dealers of Lightning: Xerox PARC and the Dawn of the Computer Age) shared their views as well. J Strother Moore and Gary Chapman (who each worked with Bob in the past and now have UT positions) served as masters of ceremony.

The announcement for the lecture includes links to news stories about Bob, as well as the famous 1968 paper by Licklider and Taylor, “The Computer as a Communication Device”. The recap of the lecture includes links to a video and photographs.

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.

Oral history of Robert W. Taylor

Robert W. Taylor directed external research at NASA, where he funded early work by Douglas Engelbart, and at the ARPA IPTO, where he initiated the ARPANET project. He also founded the Xerox PARC Computer Science Laboratory and later the DEC Systems Research Center. Last fall I interviewed him for the Computer History Museum‘s Oral History Collection. The transcript, based on two afternoons of interviewing captured on six videotapes, has been edited and is now online: catalog entry; transcript (PDF).

Here are summaries of the contents (corresponding to the six videotapes):

  1. Taylor’s childhood, education, military service in the US Navy during the Korean War, and his first positions after graduating from college: teaching at a prep school in Florida, and systems engineering at The Martin Company in Orlando, Florida; managing research at NASA and at ARPA IPTO.
  2. The ARPANET project, the founding of the graphics work at the University of Utah; his own brief stay at the University of Utah; the founding and early history of the Xerox PARC Computer Science Laboratory (CSL); Xerox’s purchase of Scientific Data Systems (SDS), and CSL’s MAXC, Alto, and EARS projects.
  3. More on the Alto system and what it influenced (including TCP/IP); the Future Day held by PARC for Xerox executives; the Dorado project.
  4. His departure from Xerox; the founding of the DEC Systems Research Center (SRC); the Firefly, Alpha Demonstration Unit, Autonet, AN2, and Petal projects; the founding of the DEC Paris Research Laboratory and its collaboration with SRC; the nearby DEC Western Research Laboratory (WRL) and its Titan project; a recap of the commercialization of Ethernet.
  5. Wes Clark, his TX-2 work, his LINC work, and his suggestion of decentralizing control for the ARPANET via a small computer (IMP) at every host; Taylor’s work in Vietnam at the end of his ARPA tenure; his approach to research management, including recruiting, interviewing, and performance appraisals.
  6. More on research management: informal celebrations, and the importance of a college intern program; reminiscences about people who worked at Xerox PARC CSL or DEC SRC or both.

Lisp’s 50th Birthday Celebration

A celebration of the 50th anniversary of Lisp is taking place in October at OOPSLA 2008. John McCarthy will give a talk about the early history of Lisp. Also Guy Steele and Richard Gabriel will repeat their 1992 HOPL-II talk about the Evolution of Lisp.

Faithful readers of this blog know that a good way to prepare for this event is to visit the History of Lisp web site at the Computer History Museum, which contains source code, manuals, and hyperlinks for many versions of Lisp starting with McCarthy’s Lisp 1.5.

Update 5 (7/10/2012): I updated the URLs for www.lisp50.org to use www.archive.org since the domain name seems to fallen into the hands of Japanese search engine optimizers, and I updated the hyperlink for JonL White because his ACM Author page now gives a 404 error.

Update 4: It was necessary to revise the schedule because of severe health issues preventing John McCarthy from attending in person. Pascal Costanza says McCarthy will be able to participate via live telephone interview.

Update 3: Now www.lisp50.org lists the Invited Speakers but notes “Title, abstracts, biographies and schedule will be announced here and at the Lisp50 blog in the coming days and weeks.”

Update 2: www.lisp50.org seems to be the URL for Lisp50@OOPSLA, but the Invited Speakers section still says “to be announced”.

Update 1: JonL White notes that the Association of Lisp Users is holding its “celebratory 50th Anniversary” conference at MIT in the spring of 2009, with Guy Steele as Program Chair and Dan Weinreb as General Chair; Dan sent out an “extremely unofficial pre-announcement” in February.

VLISP documents; LISP Bulletin #2 and #3

Jérôme Chailloux recently told me about the wonderful ArtInfo-MusInfo web site, which contains a variety of documents produced by a group of “painters, musicians, psychologists, pedagogues, linguists, mathematicians, poets, architects and computer scientists gathered within the Computer Science Department of the University of Vincennes” during the period 1969-1980. Although there are many fascinating documents, I was especially interested in two collections:

  • VLISP manuals and papers, including dissertations by Patrick Greussay and Jérôme Chailloux. VLISP was the precursor of Le_Lisp, and served as a testbed for some of the implementation techniques of Le_Lisp.
  • LISP Bulletin #2 and #3, edited by Patrick Greussay & Joachim Laubsch. Danny Bobrow launched the LISP Bulletin with a first issue published in the September 1969 issue of SIGPLAN Notices, but no issues followed until Greussay and Laubsch took over.

I’ve updated the VLISP and LISP Bulletin sections of the CHM LISP web site with links to these documents.

Updated 11/26/2010: Updated URLs to reflect reorganization of http://www.softwarepreservation.org/projects/LISP/.

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.

The Revised MacLisp Manual goes online

MIT’s MacLisp played a key role in Lisp history, but its documentation often lagged the system as developers concentrated on adding features and improving performance. Around the time that Lisp machine development eclipsed PDP-10 MacLisp, this final MacLisp document was published:

  • Kent M. Pitman. The Revised MacLisp Manual. “Saturday Morning Edition”, M.I.T. Laboratory for Computer Science Technical Report MIT-LCS-TR-295, June 1, 1983.

This has been out of print for many years, but Kent just made available an updated, hypertext “Sunday Morning Edition”.

If you are interested in more MacLisp history, including earlier manuals, source code, and more, see the MacLisp area of the Lisp website at the Computer History Museum.

BBC Radio observes Fortran’s 50th birthday

This week’s episode of BBC Radio’s Digital Planet show includes a short segment on the 50th anniversary of Fortran. The presenter, Gareth Mitchell, interviewed me last week and about 4 minutes of that interview are included.

If you’re interested, the show will be broadcast at various times December 18 and 19 (today and tomorrow); local schedules are available at this web page:

For one week only, starting today, an MP3 of the entire half-hour show can be downloaded from this web page:

The Fortran segment starts at about 19m38s into the show.

Update 2: With the permission of BBC Radio, I’ve added the audio of the Fortran segment to the Memoirs and user stories section of the CHM Fortran web site:

  • Gareth Mitchell, presenter. Fortran is 50. Digital Planet programme, BBC Radio World Service, December 18, 2007, 6′:40″. MP3 (7.6 megabytes)

    Mitchell interviews Paul McJones on the occasion of the 50th birthday of Fortran; additional commentary by Bill Thompson; produced by Helena Selby.

Update: A BBC reorganization removed the download link from the page above; in a comment below, Derek Mahar notes the episode download site is now http://www.bbc.co.uk/radio/podcasts/digitalp/ and this download itself is http://downloads.bbc.co.uk/podcasts/worldservice/digitalp/digitalp_20071218-1232.mp3

Computer History Museum videos coming to YouTube

The Computer History Museum has just launched a partnership with YouTube to provide a ComputerHistory “channel”. Right now it has 23 videos from various events and lectures at the museum; if you subscribe (via the orange button), you’ll be notified when more are uploaded. In the mean time, the museum maintains a calendar of past events with links to video, where available.

C++ Historical Sources Archive

Observant audience members at Bjarne Stroustrup’s HOPL-III C++ talk this past weekend may have noticed on the last slide a mention of the C++ Historical Sources Archive at the Computer History Museum. This is a project Bjarne and I have been working on in the background for a year or two. Bjarne convinced the appropriate authorities at AT&T to approve releasing the Cfront source code, and then dug up listings, documentation, and/or machine-readable source for Cfront releases E, 2.0, and 3.0. Willem Wakker kindly supplied a copy of release 1.0. We have also tracked down some early libraries including libg++, COOL, LEDA, Array_Alg, STL, InterViews, ET++, and more. We would be very interested also in early applications written in C++ (especially pre-1990).

By the way, what was previously called the Software Collection Committee at the Computer History Museum has a new name (the Software Preservation Group), a new domain name (www.softwarepreservation.org) and a new chairman (Al Kossow, the Museum’s Software Curator and the creator of www.bitsavers.org).