Category: ALGOL

Remembering Maarten van Emden

Maarten van Emden died on January 4, 2023, at the age of 85.[1] He was a pioneer of logic programming, a field he explored for much of his career. I was not in his field, and only got to know him starting in 2010, so this is a personal, but not professional, remembrance of a very dear friend.

Maarten van Emden, 26 February 2011

His life

Maarten was born in Velp, the Netherlands, but his family soon moved to the Dutch East Indies, where his botanist father was working on improving tea plants. In 1942 the Japanese invaded. Maarten’s father escaped to join the resistance, but Maarten, his younger sister, and his mother were sent to a detention camp. As the war came to a close, his father was able to rescue and reunite the family. Over the next few years they returned to the Netherlands, with a brief return to the newly-formed Indonesia, followed by boarding school in Australia for Maarten. They were finally reunited in the Netherlands in 1954, where Maarten began his final year of high school. After graduating in 1955, he went to national flight school (Rijksluchtvaartschool). He did a year of military service, including flight training, and then joined KLM Royal Dutch Airlines. But KLM was adopting DC-8 jets for transatlantic service, whose speed, capacity, and ease of operation led to the need for fewer pilots. Maarten took advantage of a company program to enroll part-time in an engineering curriculum at the University of Delph. Later he was laid off by KLM and finished a master’s degree as a full-time student. He then enrolled in the PhD program administered by the University of Amsterdam with research at the Mathematisch Centrum (now CWI), and also made several visits to the University of Edinburgh. His 1971 dissertation was An Analysis of Complexity and his advisor was Adriaan van Wijngaarden. Maarten was awarded a post-doctoral fellowship by IBM, which he spent at the Thomas J. Watson Research Center in Yorktown Heights, NY during the 1971-1972 academic year, before returning to Edinburgh for a research position under Donald Michie in the Department of Machine Intelligence.  In 1975 he accepted a professorship at the University of Waterloo, and in 1987 he moved to the University of Victoria.

Programming

Maarten was one of 15 individuals recognized as Founders of Logic Programming by the Association for Logic Programming.[2] His work began with an early collaboration with Bob Kowalski[3] and continued throughout his career with collaborations and individual projects to explore many aspects of the field. Underlying his interest in logic programming was a fascination with programming and programming languages of all sorts.[4] His first language was Algol 60, which he taught himself using McCracken’s new book[5] when his university suddenly switched from Marchant calculators to a Telefunken TR-4 computer for the numerical methods course.[6] Moving on to the MC he was surrounded by ALGOL experts (his advisor van Wijngaarden was a member of the ALGOL 60 Committee and the instigator of the infamous ALGOL 68). Maarten was originally attracted to Edinburgh after hearing about the POP-2 timesharing system of Burstall and Popplestone; it was only later that he realized he’d initially used POP-2 as if it was ALGOL rather than a rich functional programming language. During his post-doc at IBM he learned APL and Lisp. Fred Blair was implementing a statically-scoped Lisp for the SCRATCHPAD computer algebra group.[7] And William Burge, who had worked with Burstall and Landin, was spreading the gospel of functional programming.[8] Ensconced in Edinburgh in 1972, he became an early convert to Kowalski’s logic programming, which he noted could be traced back as early as Cordell Green’s paper at the 4th Machine Intelligence workshop.[9] But Maarten’s first impression of Preliminary Prolog was not positive — the frequent control annotations seemed to detract from the logic. Nevertheless, he and Kowalksi began writing short programs to explore the ideas. And when David Warren returned from a visit to Marseille with a box of cards containing Final Prolog as well as his short but powerful WARPLAN program, things changed. The language no longer needed the control annotations, and Warren quickly ported its Fortran-coded lowest layer to the local DEC-10. WARPLAN served as a tutorial for all sorts of programs in the new language. Maarten was surprised that his friend Alan Robinson, the inventor of resolution logic, wouldn’t give up Lisp for logic programming.[10] At Waterloo, he advised Grant Roberts, who built Waterloo Prolog for the IBM System /370, and another series of students who built  several Prologs for Unix. At Victoria, he wrote a first-year textbook for science and engineering students based on C:

It is indeed true that object-oriented programming represents a great advance. It is also true that polymorphism in object-oriented programming does away with many if-statements and switch statements; that iterators replace or simplify many loops. But experience has shown that introducing objects first does not lead to a first course that produces better programmers; on the contrary. It is as much necessary as in the old days to make sure that students master variables, functions, branches, loops, arrays, and structures.

[11], page xi

In the acknowledgements of the book, he wrote:

I had the good fortune to grow up in three distinctive programming cultures: the Mathematical Centre in Amsterdam, the Lisp group in the IBM T.J. Watson Research Center, and the Department of Machine Intelligence in the University of Edinburgh. Though all of these entities have ceased to exist, I trust I am not the only surviving beneficiary.

If this book is better than others, it is due to my choice of those who were, often without knowing it, my teachers: H. Abelson, J. Bentley, W. Burge, R. Burstall, M. Cheng, A. Colmerauer, T. Dekker, E. Dijkstra, D. Gries, C. Hoare, D. Hoffman, N. Horspool, B. Kernighan, D. Knuth, R. O’Keefe, P. Plauger, R. Popplestone, F. Roberts, G. Sussman, A. van Wijngaarden, N. Wirth.

[11], page xi

Getting to know Maarten

As different as we were, Maarten and I had a few things in common: fathers who piloted B-24 bombers in WWII, a charismatic mutual friend named Jim Gray, attendance at the 1973 NATO Summer School on Structured Programming, books named Elements of Programming, and a fascination with the early development of programming languages. Jim Gray had been an informal mentor for me at UC Berkeley as I worked on CAL Snobol and Cal TSS. Then he left Berkeley for IBM Research in Yorktown, and made friends with Maarten. Jim soon decided he couldn’t tolerate life on the east coast, but before leaving he encouraged Maarten and his wife Jos to drive across the country and visit him in California, where he would show them around. They took him up on the offer, and during a brief stay in fall 1972 at Jim’s home in Berkeley I met Maarten, but didn’t make much of an impression on him (although he later told me Jim had mentioned the “great programmers on Cal TSS”). The next summer both Maarten and I attended the NATO Summer School on Structured Programming at Marktoberdorf, but neither of us remembered encountering the other. Maarten mentioned the summer school in his remembrance of Dijkstra.[12]

In 1974 I caught up with Jim Gray again, joining IBM Research in San Jose (before Almaden). The next summer Maarten visited Jim, although I didn’t learn of it until much later:

“After I returned to Europe Jim and I kept writing letters. In the summer of 1975 I was in a workshop in Santa Cruz and Jim came up in a beautiful old Porsche.  I was at the height of my logic programming infatuation. Jim was rather dismissive of it. Nothing of what he told me about System R  turned me on; the relationship died with that meeting. How I wish I could talk to him now about the mathematics of RDBs, which I started working on recently.”

[Maarten van Emden, personal communication, September 3, 2010]

Maarten left three technical reports with Jim, who passed them along to me.[13] [14] [15] I looked at them, and then put them aside for the next 35 years. In the fall of 2010 I had retired and was spending more time on software history projects. I’d been following Maarten’s blog; a recent pair of articles about the Fifth Generation Computer System project and the languages Prolog and Lisp[16] [17] prompted me to contact him about a project I was contemplating: an historical archive of implementations of Prolog.[18] That began a friendship carried out mostly through some 2000 emails and almost 400 weekly video calls, plus one in-person visit when Maarten visited the Bay Area in early 2011. I will always remember his charming manners, gentle humor, wide-ranging interests, and intriguing stories.

Acknowledgements

Thanks to Maarten’s daughter Eva van Emden for information about his life.

For more of his writing, see:

Update 1 January 2024

Shortly after I wrote my post, Maarten’s colleagues wrote this article for the Association of Logic Programming: In Memoriam: Maarten van Emden.

Maarten’s web site at UVic has moved to http://maarten.vanemden.com/

References

[1] Eva van Emden. Maarten van Emden Obituary. The Times Colonist, January 10, 2023. https://www.legacy.com/ca/obituaries/timescolonist/name/maarten-van-emden-obituary?pid=203621344
[2] ALP Awards. Association for Logic Programming. https://www.cs.nmsu.edu/ALP/the-association-for-logic-programming/alp-awards/
[3] M. H. van Emden and R. A. Kowalski. The Semantics of Predicate Logic as a Programming Language. Journal of the ACM, Vol. 23, No. 4, 1976, pp. 733-742. https://www.doc.ic.ac.uk/~rak/papers/kowalski-van_emden.pdf
[4] Maarten van Emden. The Early Days of Logic Programming: A Personal Perspective. Association for Logic Programming Newsletter, August 2006. https://dtai.cs.kuleuven.be/projects/ALP/newsletter/aug06/nav/articles/article4/article.html
[5] Daniel McCracken. A Guide to ALGOL Programming. John Wiley and Sons, 1962. https://archive.org/details/mccracken1962guide
[6] Maarten van Emden. On Finding a Discarded Copy of “A guide to Algol Programming.” 1993 email to Frank Ruskey. https://web.archive.org/web/20050906222954/http://csr.uvic.ca:80/~vanemden/other/guideAlgol.html
[7] J. H. Griesmer and R. D. Jenks. SCRATCHPAD/1: An interactive facility for symbolic mathematics. In Proceedings of the second ACM symposium on Symbolic and algebraic manipulation (SYMSAC ’71). Association for Computing Machinery, New York, NY, USA, 42–58. https://doi.org/10.1145/800204.806266
[8] William Burge. Recursive Programming Techniques. Addison-Wesley 1975. https://archive.org/details/recursiveprogram0000burg
[9] Cordell Green. Theorem-Proving by Resolution as a Basis for Question-Answering Systems. Machine Intelligence 4, Bernard Meltzer and Donald Michie, editors, Edinburgh University Press, Edinburgh, Scotland, 1969, pages 183–205. https://www.kestrel.edu/people/green/publications/theorem-proving.pdf
[10] Maarten van Emden. Interview with Alan Robinson, inventor of resolution logic. June 8, 2010. https://vanemden.wordpress.com/2010/06/08/interview-with-alan-robinson-inventor-of-resolution-logic/
[11] M. H. van Emden. Elements of Programming. Andromeda Research Associates, Ltd. Third edition, 2009, page ix. https://abazu.vanemden.com/4EOP/EOP.html
[12] Maarten van Emden. I remember Edsger Dijkstra (1930 – 2002). August 2008. https://vanemden.wordpress.com/2008/05/06/i-remember-edsger-dijkstra-1930-2002/
[13] Robert Kowalski. Predicate Logic as Programming Language. Department of Computational Logic, University of Edinburgh, Memo No. 70, November 1973. https://www.doc.ic.ac.uk/~rak/papers/IFIP74.pdf
[14] M. H. van Emden and R. A. Kowalski. The semantics of predicate logic as a programming language. School of Artificial Intelligence, University of Edinburgh, MIP-R-103, February 1974. https://www.doc.ic.ac.uk/~rak/papers/kowalski-van_emden.pdf
[15] M. H. van Emden. First-order predicate logic as a high-level program language. School of Artificial Intelligence, University of Edinburgh, MIP-R-106, May 1974. http://webhome.cs.uvic.ca/~vanemden/Publications/FOPLasHLPL.pdf
[16] Maarten van Emden. Who Killed Prolog? A Programmer’s Place blog, August 21, 2010. https://vanemden.wordpress.com/2010/08/21/who-killed-prolog/
[17] Maarten van Emden. The Fatal Choice. A Programmer’s Place blog, August 31, 2010. https://vanemden.wordpress.com/2010/08/31/the-fatal-choice/
[18] Paul McJones, editor. Prolog and Logic Programming Historical Sources Archive. https://www.softwarepreservation.org/projects/prolog/

Dr. John E. L. Peck, 1918-2013

Dr. John E. L. Peck (1918-2013)
Dr. John E. L. Peck (1918-2013)
Dr. John E. L. Peck, whose work on ALGOL 68 was described in a recent post, passed away on November 6, 2013. His family has provided this obituary:

John, born August 14, 1918 in Pietermaritzburg, South Africa, passed away peacefully with his family by his side on November 6, 2013. He is predeceased by his wife Dornacilla of 61 years, and lovingly remembered by his sons, Edward (Phyllis) and Nigel (Susan); his twin daughters Lenny (George) and Gwenda; his sister Gwenyth; grandchildren Justin (Kristina), Linstead (Randi), Shannon, Tanya and Vernon; great-grandson Isaac; nieces and nephews, Elizabeth, Brian, Richard, Louise, Deborah, Sheryl, Ross, Janene, Randa, Dahl and Fraser; relatives, good friends and colleagues from around the world. John was the first Head of the University of Calgary Mathematics Dept. and founded UBC’s Department of Computer Science – his contributions to computer science were significant internationally. He was a key member of the international community that pioneered the field of Computer Science beginning in the early 60s. He was an avid outdoorsman who enjoyed alpine climbing, skiing and cycle touring. He also had a strong love of music playing pipe organ, piano and classical recorder. He enjoyed a full and rich life and will be greatly missed. A Celebration of his Life will be held Saturday, December 7, 2013 at 10:00am at Victory Memorial Park Funeral Centre, 14831 28th Avenue, Surrey, BC. In lieu of flowers, please consider making a donation to the charity of your choice.

Condolences may be offered at www.victoryfuneralcentre.ca

ALGOL 68: Implementation and more

John E. L. Peck joined the ALGOL 68 design project in 1966, was a coauthor of the report, edited the proceedings of the 1970 Munich implementation conference, hosted meetings that laid the foundations for the revised report, and chaired IFIP Working Group 2.1 from 1975 to 1978. Recently his son Edward Peck contacted me to say that he had come across a set of ALGOL 68-related documents in his father’s papers, and wondered if they would be appropriate for the ALGOL 68 section of the History of ALGOL web site. That led to some valuable additions:

I’d like to thank Edward Peck very much for making these documents available and for careful work scanning them.

Update 2024/05/08: Updated URLs for IFIP WG 2.1 and the conference at CWI.

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.

Update 2024/05/8: Updated link for Neville Dempsey.

More ALGOL history papers

As the ALGOL programming language enters its sixth decade, its interest to historians seems to be increasing. I’ve recently added additional citations to the “Papers on the history of ALGOL” section of the History of ALGOL web site:

  • Edgar G. Daylight. From Mathematical Logic to Programming-Language Semantics — a Discussion with Tony Hoare. Journal of Logic and Computation (to appear).

    Section 2.3 covers Hoare’s Algol work at Elliot.

  • Edgar G. Daylight. Pluralism in Software Engineering: Turing Award Winner Peter Naur Explains. CONVERSATIONS. Issue 1, Volume 2011, Lonely Scholar, 2011.

    Part I of this wide-ranging interview covers Naur’s work on Algol 60, including the DASK and GIER implementations. He also makes a few remarks about Algol 68.

  • Pierre Mounier-Kuhn. From universal project to sunken culture : Algol in France. SHOT / SIGCIS Workshop 2011, Cultures and Communities in the History of Computing, Cleveland (OH), 6th November 2011. PDF

Edgar Daylight on Dijkstra

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

E. W. Dijkstra and Paul McJones at Marktoberdorf Summer School, 1973

Gordon Bell: “Out of a Closet: The Early Years of The Computer [History] Museum”

Update 1/1/2016: Gordon Bell has made an archive of materials from The Computer Museum available at https://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.

Update 2024/05/08: Updated various URLs.

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 200/11/26: Updated URLs to reflect reorganization of http://www.softwarepreservation.org/projects/LISP/.

Update 2024/05/08: Corrected some URLs to match History of LISP reorganization.

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 2010/9/22: corrected URL for Whetstone at Software Preservation Group website.

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

Update 2020/3/10: Bill Findlay contacted me to say: “You might be interested to know that the emulator mentioned [above] is in good working order. Not only does it run the Whetstone system, it now also runs the Kidsgrove optimising compiler for KDF9 Algol as well. The latter was restored by a team including one of its original authors, David Huxtable.  See:  http://www.findlayw.plus.com/KDF9/.

Also corrected (again) links to ncl.ac.uk.

Update 2024/05/08: Corrected link for Brian Randell and for Whetstone Algol Resurrection.

ALGOL

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.