If I were asked to distil into a single word the essence of what I learned from Alain, it would have to be: beauty.
Even when computers were much less efficient than today, and hacking to gain speed appeared as a must, Alain aimed always at concise and elegant formulations, betting that efficiency would follow largely from the resulting clarity – and so it typically did.
Alain’s focus on beauty led him naturally to think in more general, more abstract terms than strictly required by the problem at hand. Thus, in his Grenoble University thesis dissertation on finding a program’s syntactic errors, his goal of doing so elegantly in a single pass led him to a very general solution solidly resting on precedence relations theory.
Next, during his military (so called) service at Université de Montreal as “Coopérant Scientifique” in the late 60’s, Alain solved an automatic translation problem by lifting it into the higher level framework of Q-systems, a formalism he developed for processing linguistic data through tree-rewriting rules. In his own words: “The experience gained using the Q-systems reinforced my feeling that to suitably solve a problem it was necessary to develop high level programming languages, even if their execution time would appear impracticably slow at that time.”
Just how formidably his bet on beauty over speed paid off even in practical terms is firstly attested to by the fact that the TAUM METEO system, created only a few years later using an industrial version of Q-systems, was the first industrial application of Machine Translation.
Secondly and most importantly, this approach led Alain to develop Prolog, once back in France as Head of the Groupe d’Intelligence Artificielle he created at Université d’Aix-Marseille II.
Curiously, his aim was not to produce a programming language, but rather a tool for enabling computer input of concepts described in French that could later be queried in French.
Constantly tacking between theory and practice, he interleaved working with Robert Pasero on a French analyser and conducting numerous experiments with Philippe Roussel and Jean Trudel on automated theorem proving methods. This led him to adopt a refinement of Alan Robinson’s resolution principle, SL-resolution, introduced by Bob Kowalski and Donald Kuehner. In the process, Prolog was born.
It soon became apparent that the new language, which integrates Alain’s Q-systems approach with SL-resolution and with Bob Kowalski’s procedural interpretation of Horn clauses, was nothing less than a revolution in scientific thinking about programming: it catapulted computing sciences from its old number-crunching, algorithm-focussed and mostly imperative paradigm into the new era of inferential engines. An era in which we no longer measure computation speed in terms of calculations per second, but in terms of inferences per second− a fantastic qualitative leap, with import well beyond the natural language processing uses for which it had been first conceived.
Prolog’s semantic underpinnings were captured by Maarten van Emden and Bob Kowalski. Improvements made it competitive as an AI language: Alain’s search space cut operation, his elegantly simple use of this operation for an implementation in two clauses of negation-as-failure (which Keith Clark then endowed with the first proper semantics), and techniques such as structure sharing (R. Boyer and J. Moore) and structure copying (Maurice Bruynooghe and Chris Mellish). When Prolog was chosen for the Fifth Generation Computing Project in Japan, it became famous worldwide.
Early implementations by Philippe Roussel, Gérard Battani and Henri Meloni and by David H.D. Warren, Fernando Pereira and Luis Pereira paved the way to Warren’s Abstract Machine, which became the standard for Prolog compilers.
Commercial applications mushroomed in areas such as expert systems, automated translators, interpreters and compilers, automatic design, deductive databases, and computer-aided instruction. Alain’s syntactic variant of Prolog for language processing− Metamorphosis Grammars, also known as Definite Clause Grammars− became a standard Prolog feature, as well as inspiring further logical variants of executable grammar.
In 1984, Alain founded a research company, PROLOGIA (still in operation), with colleagues Geneviève Bossu, Henri Garetta, Henri Kanoui, Robert Pasero, Jean-Francois Pique and Michel van Caneghem, for commercializing Prolog and developing practical software solutions to complex problems, still in operation.
It took uncompromising determination and strength of character for Alain to materialise his ideas into practical form in the face of generalised disbelief at the time when Prolog was being conceived. When he visited Stanford with Philippe Roussel and Robert Pasero in 1972 to present his ideas, they were met with scepticism and almost laughter. Yet Alain’s unwavering faith in his ideas and his happy and enterprising spirit kept him going. After history proved him right, John McCarthy himself showed up aboard the Queen Mary’s First Workshop on Logic Programming, trying to learn more about the new paradigm and seeking our help to introduce it at Stanford.
Those early days in the aptly named Luminy, where I had the privilege of studying under Alain’s supervision from 1975 to 1977, are indelibly imprinted in my mind as an improbable domain of peaceful and inspiring Mediterranean landscapes, relentless mistral, and meridional friendliness in Alain’s uniquely creative lab. I suspect Alain’s love of sailing in the blue waters dazzlingly framed in white calcareous rock provided him with additional source of inspiration.
Already in 1976, Alain felt constraints were the next giant leap needed in logic programming− a dream that spawned two most influential further contributions. The first was the move from unification to equations and inequations over infinite trees (late 70’s/early 80’s), which materialised in award-winning software and paved the way for many of the accomplishments in Constraint LP that flourished as from the mid-80’s.
Alain’s second crucial contribution to CP were his highly innovative extensions of constraint solving and its semantic underpinnings into richer domains: from Prolog II’s infinite trees and non-equality predicate − admirably implemented with Michel van Caneghem on a very primitive personal computer with floppy disk virtual memory−; to Prolog III’s extension to Boolean algebra and real numbers; to the beautiful formalization of interval reasoning and the unifying presentation of the heterogeneous solvers in Prolog IV; to generalising the idea of constraint solving by intervals narrowing into general constraints.
These two achievements influenced in particular Joxan Jaffar and Jean-Louis Lassez in developing the theory underlying CLP. The second influenced Pascal van Hentenryck to leverage the work of Jean-Louis Lauriere and Alan Mackworth to design CP over finite domains.
Alain’s subsequent achievements in CP involve a phenomenal ambition: solving non-restricted first-order formulae constraints in the theory of trees, as well as combining them with additive ordered rational numbers.
Remarkably, his most recent research was completed after he recovered from a severe stroke. It once more addresses an entirely different research field− the study of the complexity of universal programs− from a highly original and high level perspective. This was the formal notion of coefficient introspection, expressing the average number of instructions executed by a universal machine for simulating the execution of one of its own instructions.
As a supervisor, Alain was always available for chatting about research, and had a great sense of humour which made his students feel very comfortable around him. He provided them with the exact combination of guidance and independence needed. He inspired generations of students, as attested by the fifty-one theses he supervised over his career, and also by many other people he helped out with the same dedication as if they had been his own students. In David H.D. Warren’s words: “I still think of Alain as a young and vigorous and inspiring research leader. We had many interesting conversations, especially when I first visited Marseille. He gave me a lot of his time, considering I was just an inexperienced visiting PhD student.”
Alain’s inspiring creativity, his relentless pursuit of his ideas, his unassuming way of producing brilliant gems for our scientific culture, his generosity in sharing them, have all shaped the fields of Logic Programming, Natural Language Processing and Constraint Programming indelibly.
Personally, I feel very privileged and incredibly lucky to have known Alain, a being of so much light, genius, and open-minded humanity. I feel orphaned and at the same time very grateful for his presence all these years, and for all the good that came into my life from his having accepted me into his lab without knowing me, a student from distant Argentina who wrote to him out of the blue, with no connections to invoke.
My condolences to Colette and all of us, my everlasting gratitude to Alain, and my thought that his light is something we will always continue to share and also to spread, having had the luck to bask in it.
Veronica Dahl