Prolog

In 1970, Alain Colmerauer was not trying to invent a new programming language. This assistant professor of computer science at the University of Montreal was leading the TAUM project (Traduction Automatique de l’Université de Montréal) and simply wanted to advance his research on computational language processing. Two young 25-year-old instructors from the newly established Faculty of Science at Luminy, Robert Pasero and Philippe Roussel, joined him for two months. They discovered Q-systems, a language that Colmerauer had developed for his translation project.

Jean Trudel, a Canadian doctoral student under Colmerauer’s supervision, was working on automated theorem proving. He built upon Alan Robinson’s seminal paper on the resolution principle, published in 1965. He had the advantage of having taken a logic course with Martin Davis in New York and already mastered unification using a modern approach where all computations reduced to pointer manipulation.

In early 1971, the team reconvened in Marseille. Alain Colmerauer obtained a position as associate professor of computer science, and Jean Trudel accompanied him thanks to a two-year scholarship from Hydro-Québec. Their goal was to perform deductions from French texts. The work was divided such that Jean Trudel and Philippe Roussel tackled deductions, while Robert Pasero and Alain Colmerauer focused on natural language. Their working environment was luxurious by French standards of the time. Their department’s IBM 360-44 offered nearly 900 KB of internal memory, without virtual memory. Jean Trudel developed an interactive monitor, and they monopolized the machine at night.

In June 1971, the team invited Robert Kowalski, one of the inventors of SL-resolution. This meeting changed everything. For the first time, they engaged with a specialist capable of explaining the resolution principle, its variants, and its refinements. Kowalski discovered researchers passionate about his work and determined to apply it to natural language processing.

In February 1972, the Institut de Recherche d’Informatique et d’Automatique (IRIA) granted them 122,000 FF for 18 months. This funding allowed them to invest in a teletype terminal, a dedicated 300-baud connection to the IBM 360-67 in Grenoble, and the recruitment of Henry Kanoui.

The fall of 1972 saw the birth of the first Prolog system. Philippe Roussel developed it in Algol-W while Alain Colmerauer and Robert Pasero created in parallel the French-language human-machine communication system. The interaction between Philippe, who coded Prolog, and Alain and Robert, who programmed in a language under development, became permanent. It was Philippe’s wife who suggested the definitive name: Prolog, an abbreviation of “PROgrammation en LOGique” (Programming in Logic).

The first major program written in Prolog was the human-machine communication system. Its 610 clauses were distributed as follows: Alain wrote 334 for analysis, Robert Pasero 162 for the deductive part, and Henry Kanoui developed French morphology in 104 clauses. This morphology handled the relationships between singular and plural for all common nouns and all verbs, both regular and irregular, in the third person singular present tense.

Official recognition came in 1973. The CNRS established an “associated research team” named “Human-machine dialogue in natural language” and allocated 39,000 FF for the first year. Users of the preliminary version of Prolog had programmed enough for their experience to inform a second version, oriented toward a true programming language rather than merely an automated deductive system.

Between June and December 1973, three DEA students—Gérard Battani, Henry Méloni, and René Bazzoli—wrote the interpreter in FORTRAN and its supervisor in Prolog. This version introduced all the basic features of current Prologs. It was also during this period that the occur check disappeared, deemed too costly.

Dissemination truly began in 1974-1975. David Warren stayed in Marseille from January to March 1974 and used Prolog to write Warplan, his plan generation system. The interactive version of Prolog running in Grenoble via teletype generated numerous requests. Gérard Battani and Henry Méloni were overwhelmed with distributions. They shipped Prolog to Budapest, Warsaw, Toronto, Waterloo, and traveled to Edinburgh to help David Warren install it on a PDP 10. Hélène Le Gloan, a former student, installed it at the University of Montreal. Michel Van Caneghem did the same at IRIA in Paris before joining the team. Maurice Bruynooghe took Prolog to Louvain after three months in Marseille.

In 1975, the entire team participated in porting to a 16-bit minicomputer, Télémécanique’s T1600. The machine had only 64 KB and required a specific virtual memory management system. Pierre Basso tackled this task and won the competition for the shortest instruction sequence that achieves 32-bit addressing while testing for page faults. Each lab member then translated two pages of FORTRAN into machine language. The reassembled fragments worked. After five years, they finally had their own machine, and their Prolog ran—slowly, but it ran.

The story of Prolog’s birth ends in late 1975, but its influence endures. Alan Robinson’s January 1965 article, “A machine-oriented logic based on the resolution principle,” contained the seeds of the Prolog language. While this article gave rise to a significant body of work on automated theorem proving, the specific contribution of the Marseille team was transforming this theorem prover into a programming language. To achieve this, they did not hesitate to introduce purely computational mechanisms and restrictions that constituted heresies for the existing theoretical model. These modifications, often criticized, ensured Prolog’s viability and thus its success.

Robert Kowalski isolated the concept of “Horn clause,” legitimizing their main heresy: a linear demonstration strategy with backtracking and unifications only at clause heads. The Marseille team had ideal conditions for this creation. Colmerauer belonged to the first generation of French computer science PhDs, and his specialty was language theory. He had gained valuable experience creating Q-systems within the University of Montreal’s machine translation project. The meeting with Philippe Roussel and the particular circumstances in Marseille did the rest. The team benefited from freedom of action in a newly created scientific center and, without external pressures, could devote itself fully to its project.