In addition to the English and Japanese editions, Elements of Programming is now available in a Russian edition translated by Konstantin Ptitsyn (Константин Птицын) and published by Williams Publishing House. The publisher’s web page has links to booksellers.
The latest addition to the “Papers on the history of ALGOL” section of the History of ALGOL web site is this paper about Dijkstra’s involvement in proposing and implementing the recursive procedure as an ALGOL 60 language construct:
- Edgar G. Daylight. Dijkstra’s Rallying Cry for Generalization: The Advent of the Recursive Procedure, Late 1950s–Early 1960s.
In a section on Future Work near the end of the paper, Daylight notes, “Research contributions of Gödel, Carnap, Turing and Tarski have been studied and documented over and over again by logicians and philosophers themselves. Computer scientists, by contrast, have yet to commence with similar work concerning the ideas of their fathers: Dijkstra, McCarthy, Hoare and others. This, in turn, explains my motivation to write this paper.” Daylight, who is a post-doctorate researcher in the history of computing, has set up the blog-style web site Dijkstra’s Rallying Cry for Generalization as a way to report on his ongoing research into Dijkstra’s writings, including the E. W. Dijkstra Archive at the University of Texas and additional materials Dijkstra’s family donated. Daylight is off to a good start. He welcomes suggestions for improving his blog, and notes he’ll be adding photographs of Dijkstra soon.
In that spirit, I offer the following photograph, taken at the 1973 Marktoberdorf Summer School, of instructor Dijkstra and student McJones. Dijkstra’s subsequent trip report (EWD385) mentions my friend Dave Redell (who took the photograph) and me because we served as “intelligent terminals” in an “interactive programming session”.
Update 1/1/2016: Gordon Bell has made an archive of materials from The Computer Museum available at http://tcm.computerhistory.org.
The institution now known as the Computer History Museum began in 1975 as a closet-sized exhibit in a Digital Equipment Corporation building, grew into The Computer Museum located on Boston’s Museum Wharf, and finally metamorphosed into its current form and location. In a fascinating technical report, Gordon Bell describes this long and interesting history, in which he and his wife Dr. Gwen Bell have played such important roles.
It was only recently, Bell notes, that “Software was finally added to list of things collected, such as the history of FORTRAN including original source code.” The FORTRAN collection to which Gordon refers is here; a catalog search of FORTRAN-related items in the museum’s archives is available here.
Bell gives a list of some two dozen “Mona Lisas” in the collection, all hardware artifacts. He concludes this section by saying “Regrettably, I omit that hard to see, hard to describe, essential software from COBOL, FORTRAN, and LISP, various Operating Systems, and on through Visicalc, and the Relational database.” I strongly agree with Bell about the importance of collecting and displaying such historic software. I’m glad to be able to point the previously-mentioned FORTRAN collection, and to similar collections for LISP, ALGOL, and C++. Others have assembled extensive collections on, for example, the Multics and Unix operating systems, PDP-10 systems and applications, and many more. Two of the earliest relational database management systems, Berkeley Ingres and IBM System R, have been preserved but are not yet easily accessible. For the most part, these collections are aimed at a more scholarly audience; I hope they will serve as source materials for future exhibits for a wider audience.
The History of LISP web site launched back in 2005 as a single web page running some 40 pages when printed; it covered many of the best known Lisp implementations. Over the years, the web site approximately doubled in size, leading several people to politely suggest breaking it up into smaller units. I’ve finally taken the time to do that. The organization roughly follows that used by Steele and Gabriel in their 1992 HOPL II talk, and I’m still making minor adjustments. It would be nice if a web site dedicated to historical archives would have stable URLs, but I think the new organization will be appreciated by people mostly interested in one or two specific implementations. I have not changed the URL of any “content” (PDF or archive file).
Thanks again to the many people down through the years who have patiently answered my questions, supplied copies of source code and documents, and allowed me to post copies.
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.
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 email@example.com.
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:
- A small Lisp for the Raytheon 704 used for speech capture and low-level processing.
- 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/.
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:
- LISP History. LISP Bulletin #3, December 1979, pages 44-55. PDF at www.artinfo-musinfo.org and ACM Digital Library
- Early LISP history (1956-1959). A version was published in: Proceedings of the 1984 ACM Symposium on LISP and functional programming, Austin, Texas, pages 299-310. ACM Digital Library
- The Influence of the Designer on the Design – J. McCarthy and Lisp. Originally published in: V. Lifschitz, editor. Artificial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy. Academic Press Professional, Inc., 1991.
- Lisp: Themes and History. Invited Lecture at International Lisp Conference 2007. MP3 at CHM
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.
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 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.
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:
- Burt Grad, Moderator. RDBMS Workshop: Technology Through 1983, Computer History Museum, June 12, 2007. http://www.computerhistory.org/collections/accession/102658267
- Donald D. Chamberlin, OH 329. Oral history interview by Philip L. Frana, 3 October 2001, San Jose, California. Charles Babbage Institute, University of Minnesota, Minneapolis. http://www.cbi.umn.edu/oh/display.phtml?id=317
- Paul McJones, editor. The 1995 SQL Reunion: People, Projects, and Politics. Technical Note 1997-018, Systems Research Center, Digital Equipment Corporation, August 1997.
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.
WIRED‘s THIS DAY IN TECH feature for tomorrow is
Oct. 15, 1956: Fortran Forever Changes Computing’s Fortunes.
The article links to the Software Preservation Group FORTRAN web site and uses a photograph of John Backus and John Cocke from a souvenir matchbook cover from Capt. Starn’s Restaurant and Bar in Atlantic City, New Jersey, year unknown:
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.
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):
- 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.
- 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.
- More on the Alto system and what it influenced (including TCP/IP); the Future Day held by PARC for Xerox executives; the Dorado project.
- 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.
- 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.
- 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.
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.