THE EARLY YEARS OF LOGIC PROGRAMMING

1 ARTICLES. THE EARLY YEARS OF LOGIC . PROGRAMMING . This firsthand recollection of those EARLY days of LOGIC PROGRAMMING traces the shared influences and inspirations that connected Edinburgh, Scotland, and Marseilles, France. ROBERT A. KOWALSKI. The name Prolog is ambiguous. It was originally in- clauses and deduction is performed by backwards rea- tended as the name for the PROGRAMMING language de- soning embedded in resolution [29]. But LOGIC program- veloped by Alain Colmerauer and Phillipe Roussel ming can also be understood more generally, for exam- in the summer of 1972.

2 The name was suggested by ple, to include negation by failure [3], set construction Roussel's wife, Jacqueline, as an abbreviation for pro- [4, 321, or goal-directed reasoning with equations. The grammation en logique. In time, however, this abbrevia- advantage of the more liberal notion of LOGIC program- tion has been used to refer to the concept of LOGIC pro- ming is that it points the way for further developments gramming in general. It is a confusing notion, as claims to encompass richer fragments of LOGIC and give a com- made for the general concept of LOGIC PROGRAMMING do putational interpretation to a greater variety of proof not always hold for the PROGRAMMING language, Prolog, procedures.]

3 And vice versa. In an attempt to minimize such confu- The liberal notion of LOGIC PROGRAMMING do'es not in- sion, I shall reserve the term Prolog to refer to the clude a number of related uses of LOGIC in PROGRAMMING . PROGRAMMING language alone. It excludes, for example, systems of constructive LOGIC This is not the place for an extensive discussion of in which proofs are interpreted as programs, and it ex- what should or should not be regarded as LOGIC program- cludes uses of LOGIC in which computation is construed ming, a term that is equally ambiguous.

4 However, with- model-theoretically as evaluating a formula in an inter- out wanting to stir further controversy, let me hazard pretation. the following rough characterization: LOGIC program- This article is a personal account of some of the EARLY ming shares with mechanical theorem proving the use history of LOGIC PROGRAMMING , ending with my move of LOGIC to represent knowledge and the use of deduc- from Edinburgh to London in December 1974. The tion to solve problems by deriving logical conse- chronicle is unavoidably biased toward my own recol- quences.

5 However, it differs from mechanical theorem lection of events at the University of Edinburgh. I am proving in two distinct but complementary ways: (1) It especially conscious that it does not do justice to re- exploits the fact that LOGIC can be used to express defi- lated activities that took place during that time at the nitions of computable functions and procedures; and Universite d'Aix Marseilles. (2) it exploits the use of proof procedures that perform deductions in a goal-directed manner, to run such defi- THE EDINBURGH-MARSEILLES CONNEC'I'ION.

6 Nitions as programs. My first contact with the Marseilles group was a three A consequence of using LOGIC to represent knowledge or four day visit in the summer of 1971 at the invitation is that such knowledge can be understood declaratively. of Colmerauer, who was then head of the artificial in- A consequence of using deduction to derive conse- telligence (AI) team at the university. The group, which quences in a computational manner is that the same consisted of Bob Pasero, Roussel, and Colmerauer, was knowledge can also be understood procedurally.

7 Thus, developing a natural language question-answlering sys- LOGIC PROGRAMMING allows us to view the same knowl- tem. Roussel and Jean Trudel, a colleague visiting from edge both declaratively and procedurally. the University of Montreal, had read [21], which de- The most straightforward case of LOGIC PROGRAMMING scribes the SL-resolution theorem prover, and Roussel is when information is expressed by means of Horn was interested in using it for the deductive component of the question-answering system. 01988 ACMOOOl-0782/88/0100-0038 $ Most of my visit consisted of intensive discussions 38 Comnunications of the ACM ]anuary 1988 Volume 31 Number I.

8 Articles with Colmerauer about using LOGIC to represent gram- which still exists today, may reflect the difference be- mar and using resolution to parse sentences. Earlier, I tween our EARLY contributions to the subject. had devised an inefficient representation of grammars, From Marseilles I wrote to Bernard Meltzer at the with explicit axioms of associativity for string conca- University of Edinburgh to explain the new ideas. In tenation. Colmerauer saw how to improve the repre- his reply, Meltzer wrote that my letter generated a lot sentation significantly, avoiding associativity by formal- of discussions.

9 Pat Hayes, in particular, argued that I. izing the graph representation of strings used in his seemed to be taking credit for the thesis that computa- Q-Grammars [5]. We observed that the bottom-up be- tion is controlled deduction, which he had been advo- havior of his Q-system parser could be obtained by cating in Edinburgh before me. using hyperresolution. SL-resolution behaved as a top- Indeed, Hayes had argued that computation and de- down parser. It is because of this work that 1971 is duction were similar some time before my second visit sometimes given as the year Prolog was born.

10 To Marselles. In particular, he argued that inference My short visit was very productive, and we planned with equations imitated computation in Lisp and that to continue our collaboration. Our plans were realized Robert Boyer and J Moore's new structure-sharing in the spring of 1972 during my second visit to Marseilles. method of implementing resolution [l] gave similar My trip was again at Colmerauer's invitation. This time run-time structures to the Bobrow and Wegbreit spa- I was accompanied by doctoral student, Ed Wilson. ghetti stack mechanism.