L. Peter Deutsch’s PIVOT program verification system

L. Peter Deutsch in his office at Xerox PARC, around 1972.PIVOT, the program verification system written in BBN-Lisp by L. Peter Deutsch and described in his PhD thesis, “An interactive program verifier” is a recent addition to the Software Preservation Group web site.

Deutsch is a computer scientist who made important contributions to interactive implementations of Lisp and Smalltalk. While he was in high school, he implemented the first interactive Lisp interpreter, running on a DEC PDP-1 computer. While still in high school, he worked with Calvin Mooers on the design of TRAC, and implemented the language on a PDP-1 at BBN. Then Deutsch enrolled at the University of California at Berkeley, where he soon joined Project Genie, one of the earliest timesharing systems. Meanwhile, at BBN, Deutsch’s original PDP-1 Lisp became the “conceptual predecessor” of BBN-Lisp, running first on the PDP-1, then the SDS-940 (running the Project Genie timesharing system), and finally the PDP-10 running BBN’s own TENEX. After several of the BBN-Lisp creators, including Deutsch, moved to Xerox PARC, BBN-Lisp became INTERLISP. By this time, Deutsch had received his bachelor’s degree at Berkeley, and with other Project Genie alumni had co-founded Berkeley Computer Corporation, which built a large timeshared computer (the BCC-500) but then went bankrupt. While working at PARC, Deutsch also attended graduate school at Berkeley, carrying out the research on program verification that produced the PIVOT system.

Deutsch was kind enough to donate his only source listing of PIVOT to the Computer History Museum (Lot number X7485.2015), and to allow scans of the listing and his thesis to be posted on the SPG web site.

Xerox Alto file server archive

In 1980, Paul McJones used this Alto to develop portions of the Xerox Star operating system.

It’s been almost a year since I posted to this blog, but I haven’t been completely inactive. This week, as part of its Software Gems: The Computer History Museum Historical Source Code Series, the Computer History Museum released a set of files archived in the 1970s and early 1980s from the Xerox Alto file servers at Xerox PARC. The files include source code, executables, documents, fonts, and other files.

This release has been a long time in the making. The files were originally archived to 9-track magnetic tape, but around 1991 they were transferred to 8mm tape cartridges. Around 2003, before he joined the Computer History Museum, Al Kossow, working under a Nondisclosure Agreement with PARC, transferred the 8mm tapes to DVDs, and sifted through the entire archive looking for files specifically related to the Alto — the archive had included files from many other projects over several decades. After many years of discussion, and the involvement of a number of people inside and outside of PARC, an agreement with CHM was finally signed in February 2011, and a CD with the Alto files that Al had located was given to CHM.

In August of 2013, I asked Len Shustek what had become of the files, and he suggested I write a blog post about them. So I talked to Al (now CHM software curator), who gave me a copy of the files. It turns out they were images of the tape records written by a Cedar Mesa program called the Archivist. Luckily, when the 9-track tapes were transferred to 8mm tapes, a file called rosetta.tar containing the Archivist source code plus some documentation was included on each tape. Once I obtained a copy of rosetta.tar I was able to write a program that “dearchived” the tape records, recreating a set of file directories. To make the files easier to view over the web, I added code to create a static web site allowing the files to be browsed, including translations from Bravo format to HTML and Press format to PDF. (Bravo was the first WYSIWYG word processor, and Press was a device-independent print-file format.)

There are 14680 files in all, of which 8598 are distinct. They include the Alto operating system; BCPL, Mesa, and (portions of the) Smalltalk programming environments; applications such as Bravo, Draw, and the Laurel email client; fonts and printing software (PARC had the first laser printers); and server software (including the IFS file server and the Grapevine distributed mail and name server).

Although not many people ever used an Alto, it had a huge influence on the hardware and software we use today, so I am very pleased that this software is now available for study.

The blog post Len invited me to write is here. The archive itself is here, but I recommend starting with this walk-through of the archive describing what is there and who wrote the various programs. More detail about the archive (provenance, naming conventions, file types, etc.) is available here.

Remembering Jim Gray

Jim Gray’s professional contributions to the theory and practice of transactions, databases, and scientific applications of large databases, coupled with his teaching, mentoring, and warm friendships made a tremendous impact on the world. When he failed to return from sailing his 40-foot sloop Tenacious around the Farallon Islands on January 28, 2007, it was a devastating blow to family, friends, and colleagues alike. Despite a series of extremely thorough searches by the Coast Guard, by his friends, and by his family, no trace of him or his boat were ever found, which meant he could not be declared legally dead at that time. The ambiguous loss suffered by his wife and family meant his disappearance was especially difficult to recover from. After the legally-mandated five-year waiting period, a court recently granted a petition by his wife Donna Carnes to have Jim declared dead as of January 28, 2012. As Donna indicates in this NY Times interview, the waiting followed by the court order have led to a sense of closure for her.

I recently wrote a summary of Jim’s life and career for the updated ACM Turing Award web site; it includes links to related articles from the 2008 Tribute held for him at U.C. Berkeley and also photographs supplied by Donna.

Jim Gray with former colleagues of the CAL Timesharing project at U.C. Berkeley, Golden Gate Park, April 1974

Here I’ll note a few of my personal memories of working with Jim, who I met at the University of California in the the late 1960s, when he was a computer science graduate student, and I was an engineering undergraduate and part-time employee of the campus computer center. Jim served as an informal advisor to me on course work, and he was also my manager for a time on the CAL Timesharing System project. Jim was a knowledgeable, patient and enthusiastic advisor. There were few boundaries between Jim’s professional and social life. I will never forget going walnut picking with Jim, who stood on the roof of his VW bus to reach the walnuts, and then easily repaired the dent in the roof by pushing upward from below.

Franco Putzolu, Jim Gray, and Irv Traiger at IBM San Jose Research, circa 1977

Jim and I worked together again a few years later at IBM San Jose Research (now IBM Almaden). After working with John Backus (whom Jim had introduced me to) on functional programming for about 15 months, I joined Jim on the System R team. By then Jim was well into his work on the transaction abstraction — creating a unified approach to the interrelated problems of concurrency control and crash recovery — which led to his 1998 ACM Turing Award. I took over some of the transaction management code, designed the crash recovery component, and wrote a multiprocess debugger which we used to test and debug the lock manager. As always, Jim was an enthusiastic and generous collaborator; I’m very proud of being a coauthor with him and six of our System R colleagues of the paper “The Recovery Manager of the System R Database Manager”.

I don’t suppose I’ll ever stop encountering subjects causing me to say to myself, “If only I could talk to Jim about this.”

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.

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:

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.

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).

Remembering John Backus

As an undergraduate at the University of California at Berkeley in the late 1960s, I first learned of John Backus and his work on Fortran, BNF, and Algol. Around 1972 or 1973 I attended a talk John gave on “variable-free programming” at Berkeley. I was fascinated by programming languages (having worked on implementations of Snobol4, APL, and Lisp by that time), so I obtained and read a copy of his report “Reduction Languages and Variable-Free Programming”. In mid 1973 he mailed out a preprint of his POPL paper “Programming Language Semantics and Closed Applicative Languages“, whose margins I filled with notes.

In early 1974 I was looking for a job. My friend Jim Gray, who was then working at IBM Research in San Jose, introduced me to John, who was looking for someone to work with him on the design of his Red language and to implement an interpreter. We seemed to hit it off, and in March I accepted his employment offer. John mostly worked out of his home in San Franscisco. We discussed the possibility of locating my office in IBM’s Palo Alto Science Center, but I wound up joining the staff of IBM Research in San Jose, which was then located in the triangular Building 28 of the IBM Cottle Road Campus. John began driving down to San Jose once or twice a week in his diesel Mercedes. The only place in the area he could refuel was a truck stop in North San Jose. IBM colleagues told me I’d had an immediate positive impact: they now saw John much more than before.

For the next 15 months or so, I worked with John, discussing language features, writing various prototypes in Lisp and McG (an ISWIM-like language by W.H. Burge), reading papers on programming language semantics, and writing a report “A Church-Rosser Property of Closed Applicative Languages” that showed the operational semantics for Backus’s Red language was well-defined.

John was an inspiring person to work for and with. Despite his accomplishments (inventor of Fortran and BNF; Algol contributor; IBM Fellow) and the age difference (he started work at IBM the year after I was born), he treated me like he treated everyone: as a respected colleague. I had many suggestions for changing and extending Red, and John gave them all his complete attention. At that time, John was interested in pure functional programming, with no side-effects on storage or the external world. I advocated extending the language to allow writing complete interactive applications. John conceded the importance of this, and came up with a scheme in which one would write a function to express the complete transformation of an application on the global state. I struggled with John’s variable free style, and suggested we allow lambda variables when defining a new functional form (higher-order function), but he stuck to his guns. Gradually, I came to the conclusion that it was still too early to build a full implementation of Red, and I began spending more time talking to the System R team down the hall, who were designing one of the first relational database managers, and inventing the SQL query language and formalizing atomic transactions along the way.

John rarely wanted to talk about himself, but when asked he had interesting stories to tell. When he first joined IBM, he programmed the Selective Sequence Electronic Calculator (SSEC), a huge electromechanical machine whose programs and data were punched into a paper tape the width of regular 80-column punched cards, but many feet long. By gluing a data tape into a loop, it could be traversed multiple times. John recalled having to debug a program that would go through cycles of correct and incorrect behavior. Eventually they realized that the tape had a half-twist when it was glued into a loop, converting it into a one-sided Möbius strip.

John’s 25th service anniversary at IBM was in 1975. A recognition luncheon was planned in San Jose (at the IBM Country Club, or customer conference center), and John was asked who he’d like to attend. He named several of his current San Jose colleagues (I was honored to be included), as well as his old colleagues from the 1950s, including people from the Fortran project. The person arranging the event said, “But these people are in New York…”, and then came up with the travel expenses.

Cordial relations with John were not restricted to working hours. He and his wife Barbara invited my wife and me to dinner at their home, which turned out to be near the base of the Sutro Tower, with a beautiful view looking north from the Golden Gate bridge to the east bay. John said the only disadvantage of the location was RF interference to his stereo from the television transmitters. To combat this, he’d designed a Faraday cage by lining his equipment closet with aluminum foil. We invited John and Barbara back to our modest rental in San Jose, and they graciously accepted.

When I started at IBM, Nixon was still in office. John’s distaste for Nixon was no secret to his friends at the time. He learned he was one of seven people singled out to receive a “Presidential Prize for Innovation”, but then the plans were dropped. John later wrote that he “had been secretly planning to use the occasion to denounce Nixon and the Vietnam war. … I guess now my plan was not a gentlemanly scheme, but anyway I was relieved when the plan fell through.”

I stayed at IBM until November 1976, working on the System R recovery manager with Jim Gray, and then moved on to another job. A while later, I ran into John waiting in line for one of the West Coast Computer Faires — probably the first one, in 1977 in San Francisco. John told me he’d sent a deposit on an interesting computer called the MicroMind, from an outfit in Cambridge, MA, called ECD Corp. He was beginning to be skeptical that he would ever get a computer or his money back. I recently heard from Olin Sibert that ECD couldn’t build the machines cheaply enough, and returned all the deposits.

In 1977 John received the ACM Turing Award for “profound, influential, and lasting contributions to the design of practical high-level programming systems, notably through his work on Fortran, and for seminal publication of formal procedures for the specifications of programming languages.” John’s Turing Lecture, “Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs” was devoted to his functional programming work, and had a large impact on the growth of a branch of academic computer science studying functional programming languages. John continued to work on functional programming until he retired in 1991.

I fell out of touch with John for many years. But in 2003, an effort I became involved with at the Computer History Museum to collect and preserve historic source code led me to get in touch with John regarding the original Fortran compiler. John was still living in the same house in San Francisco, and seemed pleased to hear from me. He didn’t have any source code, but did make several suggestions; eventually I found several versions of the IBM 704 FORTRAN II compiler source code.

Around this same time, I learned that John’s idea of an algebra of programs had had a big impact on my colleague Alex Stepanov (although Alex figured out how to apply this idea while extending the “von Neumann style” in an important way). At the time, Alex and I were organizing an internal technical conference for our employer, and we invited John to give a keynote speech. Just after he graciously accepted, his wife Barbara died; understandably he canceled the speech. John decided to move to Ashland, Oregon, to be near one of his daughters. Another colleague of mine, Dick Sweet, lives in Ashland and introduced John to a new circle of friends for what turned out to be his final years.

Although many people contributed to the early development of programming languages, John Backus deserves credit for creating the first successful higher-level programming language, Fortran. Fortran provided data types (integer and floating-point numbers), a powerful data structure (the array), expressions, statements, and abstraction mechanisms (functions and subroutines). The Fortran compiler generated optimized code taking advantage of the then brand new index registers and floating-point hardware of the IBM 704. Finally, the Fortran system provided a linking loader, a subroutine library, and I/O routines. The scientific and engineering users adopted it instantly, and it became the standard against which future programming language designs were compared.

Why was John’s contribution so important? He invented a language allowing one to express numeric algorithms in a way that was abstracted from irrelevant details of particular computers but that was efficiently implementable on a broad class of computers: from the vacuum tube IBM 704 of 1954 to the fastest supercomputer of 2007 and beyond. That idea, allowing the essential details of algorithms and data structures to be expressed in an abstract and yet efficient way, is at the heart of what programming language designers have been trying to accomplish for the last 50 years. Only a handful of them have made the kind of progress John Backus and his team did.

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

A report and a request from Al Kossow

Many people know of Al Kossow through his work on bitsavers.org, which I mentioned in a previous post. I’m very pleased to mention here Al’s recent appointment as the Robert N. Miner Software Curator at the Computer History Museum. Al is off to a great start on a variety of efforts including reading old magnetic media, etc. He asked me to post this item about an important recent development:

In the spring of this year, the Computer History Museum was contacted by someone who had several SDS 900 series machines, and told us that he had the entire SDS software library from Honeywell in the early 80’s.

The donation arrived at CHM on Friday, and I’ve spent the past few days going through it. It does, in fact contain ALMOST the entire collection as it existed at Honeywell in March, 1982. Unfortunately, the 940 timesharing system software was already gone from the library by 1982. Two 940 archive tapes, a set of user programs and the off-line diagnostics have survived.

There is a very large collection of user’s manuals, program writeups, paper and magnetic tape. This is the largest software collection that has survived largely in one piece from a 60’s computer manufacturer that I’ve ever seen.

Scans of most of the program library listings are on line now at bitsavers under pdf/sds/9xx/programLibrary. I’m in the process of post-processing several dozen programming and other user’s manuals.

There are about 100 7-track tapes which will have to wait until I have a reliable way to read them. The smaller program library programs were written to 9-track tape in 1982, and those have been successfully read and a machine-readable index of their contents have been started.

Do you know anyone who may have worked for computer companies in the 60’s or 70’s that was a pack rat? The companies themselves have either disappeared or discarded this stuff literally decades ago!

This discovery has reinforced my opinion that there may still be large archives of 60’s and 70’s software in the hands of individuals, and that the most important thing to do is to get the word out that CHM is committed to the preservation of these archives, and has the facilities to recover these latent archives and keep them for posterity.

So if you are one of these people or you know one of them, please contact Al.

TENEX Interlisp

Tom Rindfleisch kindly supplied a set of TENEX Interlisp files from a system dump of the SUMEX-AIM <lisp> directory as of January 31, 1982. Tom notes:

This version of Interlisp should be both TENEX and TOPS20 compatible. It came at a time when lots of work was going on to port Interlisp to other environments, including the VAX and the new personal Lisp machines (Dolphins, etc.). This means little was changing in the TENEX/TOPS20 version.

There are links to these files here.

Speaking of TENEX Interlisp, TWENEX.ORG is offering free TENEX accounts on a simulated KL10B and they seem to have a version of Interlisp installed. I plan to investigate.

[Edited 10 May 2014: community.computerhistory.org/scc/projects/LISP/index.html#INTERLISP_ => www.softwarepreservation.org/projects/LISP/interlisp_family/#INTERLISP_.]