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/

The Year of Prolog (1972-2022)

Prolog 50 1972-2022

50 years ago Alain Colmerauer and his colleagues were working on Prolog 0:

“A draconian decision was made: at the cost of incompleteness, we chose linear resolution with unification only between the heads of clauses. Without knowing it, we had discovered the strategy that is complete when only Horn clauses are used.”

[Colmerauer and Roussel, 2006]

With this system, and the idea of “metamorphosis grammars” (a generalization of what later became known as “definite clause grammars”), the team was able to implement a natural language man-machine communication system. The following year, the team released Prolog 1, the classic Marseille Prolog that quickly spread to Edinburgh, Leuven, Warsaw, Budapest, London, Waterloo, and beyond.

Now the friends of Alain Colmerauer are calling for 2022 to be “The Year of Prolog”. They’re marking the 50th anniversary with:

  1. An Alain COLMERAUER Prize awarded by an international jury for the most significant achievement in Prolog technology.
  2. A “Prolog School Bus” that will travel to reintroduce declarative programming concepts to the younger generation. This is a long-term initiative that will be initiated during the year. The purpose of this “Tour de France” (and elsewhere) will be to familiarize schoolchildren with Prolog, as they are already familiar with the Scratch language. At the end of this school caravan, a prize will be awarded to the ‘nicest’ Prolog program written by a student.

For more information, see:

A documentary about Alain Colmerauer

Alain Colmerauer – photo from his web site http://alain.colmerauer.free.fr

It’s called An idea crazy enough…..Artificial Intelligence and it’s being developed by Colmerauer‘s friends at Prolog Heritage via a crowd-funded project at Ulele.

Colmerauer died 12 May 2017; the hoped-for tribute this fall has evolved:

The project is a film to portray Alain Colmerauer’s life and work – his contribution to Logic Programming and Constraints Logic Programming – all brought to life through interviews with some of the key participants of his time, complemented by images and documents from the archives. In fact that was the best solution to invite witnesses in this period of sanitary difficulties.

Alain Colmerauer documentary, Ulule

A 20 Euro contribution gets you an invitation to an exclusive preview of the film online; a 50 Euro contribution gets you the invitation, your name in the credits as a donor, and a digital version of the documentary.

Colmerauer’s web site: http://alain.colmerauer.free.fr

Prolog Heritage: http://www.prolog-heritage.org

Prolog and Logic Programming Historical Sources Archive: http://www.softwarepreservation.org/projects/prolog/

Preserving (more of) the history of logic programming and Prolog

This is a preview of an article that later appeared in the Newsletter of the Association for Logic Programming. I posted it here first because of the infrequent publication schedule of that newsletter and my desire to announce a new website: Prolog and Logic Programming Historical Sources Archive.

Logic programming has a long and interesting history with a rich literature comprising newsletters, journals, monographs, and workshop and conference proceedings. Much of that literature is accessible online, at least to people with the appropriate subscriptions. And there are a number of logic programming systems being actively developed, many of which are released as open source software.

Unfortunately, the early years of logic programming are not as consistently preserved. For example, according to dblp.org, the proceedings of the first two International Logic Programming Conferences are not available online, and according to worldcat.org, the closest library copies of the two are 1236 km. and 8850 km. away from my home in Silicon Valley. Early workshop proceedings and many technical reports are similarly hard to find (but see [1, 2]!). And the source code of the early systems, although at one time freely distributed from university to university, is now even more difficult to find.

As noted by people like Donald Knuth [3], Len Shustek [4], and Roberto Di Cosmo [5], software is a form of literature, and deserves to be preserved and studied in its original form: source code. Publications can provide overviews and algorithms, but ultimately the details are in the source code. About a year ago I began a project to collect and preserve primary and secondary source materials (including specifications, source code, manuals, and papers discussing design and implementation) from the history of logic programming, beginning with Marseille Prolog. This article is intended to bring awareness of the project to a larger circle than the few dozen people I’ve contacted so far. A web site with the materials I’ve found is available [6]. I would appreciate suggestions for additional material [7], especially for the early years (say up through the mid 1980s). The web site is hosted by the Computer History Museum [8], which welcomes donations of historic physical and digital artifacts. It’s also worth noting the Software Heritage Acquisition Process [9], a process designed by Software Heritage [5] in collaboration with the University of Pisa to curate and archive historic software source code.

Maarten van Emden provided the initial artifacts and introductions enabling me to begin this project. Luís Moniz Pereira provided enthusiastic support, scanned literature from the early 1980s [1, 2], and encouraged me to write this article. And a number of other people have generously contributed time and artifacts; they are listed in the Acknowledgements section of [6] as well as in individual entries of that web site.

References

  1. Luís Moniz Pereira, editor. Logic Programming Newsletter, Universidade Nova de Lisboa, Departamento de Informática. Issues #1-#5, 1981-1984. [Note that this newsletter was typeset, galley-proofed, and printed in color.] http://www.softwarepreservation.org/projects/prolog/lisbon/lpn/
  2. Luís Moniz Pereira, António Porto, Luís Monteiro, and Miguel Figueiras, editors. Proceedings of Logic Programming Workshop’83. Praia da Falésia, Algarve / PORTUGAL, 26 June – 1 July, 1983. Núcleo de Intelligência Artificial, Universidade Nova de Lisboa. http://www.softwarepreservation.org/projects/prolog/lisbon/lpw83/ and https://dblp.org/db/conf/iclp/lpw1983.html
  3. Donald Knuth. Let’s not dumb down the history of computer science. Kailath Lecture, Stanford University, May 7, 2014. https://engineering.stanford.edu/donald-knuth-2014-kailath-lecture
  4. Len Shustek. What Should We Collect to Preserve the History of Software? IEEE Annals of the History of Computing, Vol. 28, No. 4, October-December 2006. https://doi.ieeecomputersociety.org/10.1109/MAHC.2006.78
  5. Roberto Di Cosmo, founder and CEO. Software Heritage. https://www.softwareheritage.org
  6. Paul McJones, editor. Prolog and Logic Programming Historical Sources Archive. http://www.softwarepreservation.org/projects/prolog/
  7. Do you have a card deck or listing of the original Marseille interpreter? Or the source code for NIM IGÜSZI PROLOG, IC-Prolog, EMAS Prolog, or LogLisp, just to name a few?
  8. Computer History Museum. Mountain View, California. https://computerhistory.org
  9. The Software Heritage Acquisition Process (SWHAP). https://www.softwareheritage.org/swhap/

Update 1/21/2021: added the link to the article as published in the ALP Newsletter.

Update 5/5/2024: updated the link to the ALP Newsletter.