Personal tools
You are here: Home Projects Prolog
Document Actions

Prolog and Logic Programming Historical Sources Archive

by Paul McJones last modified 2021-01-16 12:37

A collection of artifacts from logic programming languages beginning with Marseille Prolog.


Paul McJones, editor ( -
Software Preservation Group
Computer History Museum



The goal of this project is to preserve and present 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. Wherever possible, we hope to identify implementations that were either originally distributed in source form or have become open source. Comments, suggestions, and donations of additional materials are greatly appreciated.




Université d'Aix-Marseille

Alain Colmerauer's interest in parsing algorithms and natural language processing (e.g. automatic translation and question-answering) led to the development of the Prolog programming language. He receiving his Ph.D. for his work in precedence grammars from the University of Grenoble in 1967. Then he went to the Université de Montréal, where he designed a tree rewriting language called Q-systems that was used in the Automatic Translation Project to construct an automatic English-to-French translation system. Colmerauer considered the Q-systems to be the ancestor of Prolog. Other influences on Colmerauer and his team included Robert Floyd's paper "Nondeterministic Algorithms", J. Alan Robinson's work on resolution logic, and Robert Kowalski's work on SL-resolution. Kowalski visited the team in Marseille for a week in 1971 and two months in 1972.

This paper is the primary source for the creation of Prolog:

  • Alain Colmerauer and Philippe Roussel. The birth of Prolog. In History of programming languages---II, Thomas J. Bergin, Jr. and Richard G. Gibson, Jr. (Eds.). ACM, New York, NY, USA, 1996, pages 331-367. Draft at


Preliminary Prolog (Prolog 0), fall 1972\

In 1971 the team had constructed a "primitive natural-language communication system" using Q-systems for the natural language aspects and a theorem prover written in ALGOL-W. But in 1972 several ideas occured to them that led to the creation of a new programming language that could handle both kinds of computing:
  1. "Of all the resolution systems implemented by Philippe, the SL-resolution of R. Kowalski and D. Kuehner seemed to be the most interesting. Its stack-type operating mode was similar to the management of procedure calls in a standard programming language and was thus particularly well-suited to processing nondeterminism by backtracking à la Robert Floyd [1967] rather than by copying and saving the resolvents. SL-resolution then became the focus of Philippe's thesis on the processing of formal equality in automated theorem-proving [Roussel 1972]. Formal equality is less expressive than standard equality but it can be processed more efficiently. Philippe's thesis would lead to the introduction of the dif predicate (for ≠) into the very first version of Prolog."
  2. "After the departure of Robert, Alain ultimately found a way [which he called metamorphosis grammars] of developing powerful analyzers. He associated a binary predicate N(x,y) with each nonterminal symbol N of the grammar, signifying that x and y are terminal strings for which the string u defined by x = uy exists and can be derived from N. By representing x and y by lists, each grammar rule can then be encoded by a clause having exactly the same number of literals as occurrences of nonterminal symbols. It was thus possible to do without list concatenation. (This technique is now known as 'The difference lists technique.') Alain also introduced additional parameters into each nonterminal to propagate and compute information. As in Q-systems, the analyzer not only verified that the sentence was correct but also extracted a formula representing the information that it contained. Nothing now stood in the way of the creation of a man-machine communication system entirely in 'logic'."
  3. "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. Robert Kowalski demonstrated this point later and together with Maarten van Emden, he would go on to define the modern fixed point semantics of Horn clause programming."
[Colmerauer and Roussel 1996]

This first version of Prolog was implemented by Philippe Roussel in ALGOL-W on the IBM 360-67 machine (running the CP-CMS operating system) at the University of Grenoble computing center. This report describes the language Prolog and the man-machine communication system written in it:

  • Alain Colmerauer, Henry Kanoui, Robert Pasero and Philippe Roussel. Un système de communication en français.Rapport préliminaire de fin de contrat IRIA, Groupe Intelligence Artificielle, Faculté des Sciences de Luminy, Université Aix-Marseille II, France, Oct. 1972.
  • Alain Colmerauer, Henry Kanoui, Philippe Roussel and Robert Pasero. Un système de communication homme-machine en français. Rapport de recherche sur la contrat CRI no 72-18 de février 72 a juin 73. Groupe de recherche en Intelligence Artificielle, Faculté des Sciences de Luminy, 1973. PDF at

Here is Roussel's dissertation, which describes the immediate predecessor, OEDIPE:

  • Philippe Roussel. Définition et traitement de l'égalité formelle en démonstration automatique. Thèse de 3ème cycle, Groupe Intelligence Artificielle, Faculté des Sciences de Luminy, Université Aix-Marseille II, France, May 1972. PDF

For more information about the implementation of Prolog 0, see section 7.4 of [Colmerauer and Roussel 1996].


  • The man-machine communication system.
  • Robert Pasero. Représentation du français en logique du premier ordre en vue de dialoguer avec un ordinateur. Thèse de 3ème cycle, Groupe Intelligence Artificielle, Faculté des Sciences de Luminy, Université Aix-Marseille 11, France, May 1973.
  • A computer algebra system.
    • Marc Bergman and Henry Kanoui. Application of mechanical theorem proving to symbolic calculus. Third International Colloquium on Advanced Computing Methods in Theoretical Physics, Marseilles, France, June 1973.
    • Marc Bergman. Résolution par la démonstration automatique de quelques problèmes en integration symbolique sur calculateur. 3ème cycle thesis, Groupe Intelligence Artificielle, Faculté des Sciences de Luminy, Université Aix-Marseille II, France, Oct. 1973.
    • Henry Kanoui. Application de la demonstration automatique aux manipulations algébriques et à l'intégration formelle sur ordinateur. 3ème cycle thesis, Groupe Intelligence Artificielle, Faculté des Sciences de Luminy, Université Aix-Marscilie II, France, Oct. 1973.
  • Sugiton general problem-solving system.
    • Michel Joubert. Un système de résolution de problèmes à tendance naturelle. 3ème cycle thesis, Groupe Intelligence Artificielle, Faculté des Sciences de Luminy, Université Aix-Marseille ii, France, Feb. 1974.
  • A. Colmerauer. Les grammaires de metamorphose, Groupe d'Intelligence Artificielle, Université de Marseille-Luminy, November 1975. Appears as "Metamorphosis Grammars" in: L. Bole (Ed.), Natural Language Communication with Computers, Springer, Berlin, May 1978.


Final Prolog (Prolog 1), summer-fall 1973

"Between February and April 1973, at the invitation of Robert Kowalski, Philippe visited the School of Artificial Intelligence at the University of Edinburgh, which was within the Department of Computational Logic directed by Bernard Meltzer. Besides the many discussions with the latter and with David Warren, Philippe also met Roger Boyer and Jay Moore. They had constructed an implementation of resolution using an extremely ingenious method based on a structure-sharing technique to represent the logical formulae generated during a deduction. The result of this visit and the laboratory's need to acquire a true programming language prompted our decision to lay the foundations for a second Prolog. In May and June 1973, we laid out the main lines of the language, in particular the choice of syntax, basic primitives, and the interpreter's computing methods, all of which tended toward a simplification of the initial version. From June to the end of the year, Gérard Battani, Henri Meloni, and Rent Bazzoli, postgraduate students at the time, wrote the interpreter in FORTRAN and its supervisor in Prolog." [Colmerauer and Roussel 1996]

For more information about the implementation of Prolog 1, see section 7.5 of [Colmerauer and Roussel 1996] and [Kluźniak 1984].

Source code

There are no known surviving copies, but see Warsaw for a modification and port of the final Marseille interpreter to an ODRA computer.


  • Gérard Battani and Henri Meloni. Interpréter du langage de programmation PROLOG. Report de DEA, Groupe d'Intelligence Artificielle, Faculté des Sciences de Luminy, Université Aix-Marseille II, France, 1973. Online at
  • David H. D. Warren. Example to Illustrate How PROLOG Is Implemented. 1974. In a different hand, "The 3 slides that were the basis of the Hungarian PROLOG implementation (1975)" has been added. Courtesy of Tim Lindholm. PDF
  • Philippe Roussel. Prolog, manuel de référence et d'utilisation, Groupe de recherche en Intelligence Artificielle, Faculté des Sciences de Luminy, Université Aix-Marseille II, France, Sept. 1975. Online at
  • David H. D. Warren. Epilog: A User's Guide to DEC-10 PROLOG. Internal Memo. Department of Artificial Intelligence, Edinburgh, 1974. Cited in [Bundy 1975], [Coelho and Pereira 1979], and [Szeredi 2004].

    Was this strictly a port of the Battani-Meloni code to the PDP-10, or did it include Warren's compiler? Coelho and Perreira note this was a report stored in the [400,400] area (TOPS-10 project and programmer number) of the DEC-10 at the University of Edinburgh in August 1975.

  • Alan Bundy. Analysing Mathematical Proofs (or Reading between the Lines). Proceedings of the 4th International Joint Conference on Artificial Intelligence, 1975. Edinburgh Research Archive


"Gérard Battani and Henri Meloni were kept very busy with the distribution of Prolog. They sent it to Budapest, Warsaw, Toronto, and Waterloo (Canada) and traveled to Edinburgh to assist David Warren in installing it on a PDP 10. A former student, Hélène Le Gloan, installed it at the University of Montréal. Michel Van Caneghem did the same at the IRIA in Paris before coming to work with us. Finally, Maurice Bruynooghe took Prolog to Leuven (Belgium) after a three-month stay in Marseilles (October through December 1975). Indeed, as David Warren has pointed out, Prolog spread as much, or more, by people becoming interested and taking away copies either directly from Marseilles or from intermediaries such as Edinburgh. Thus, Prolog was not really distributed; rather it 'escaped' and 'multiplied.'" [Colmerauer and Roussel 1996]

"After my return [from Marseille] to Edinburgh Pietzrykowski contacted me for a possible visit to Waterloo. As the arrangements firmed up, he told me he hadn't managed to get a copy of Marseilles Prolog and could I bring one. And so it was that I arrived in Waterloo in January 1975 with two presents: a plastic bag with cuttings of the Papyrus plant and a box with a foot-long stack of punched cards. Sometime in the spring of 1975 two students of Pietrzykowski, Lewis Baxter (later to invent a fast unification algorithm) and Larry Rendell, got the Fortran of the interpreter translated to the local dialect. Thus was established the first Prolog installation in North America.

This was not the first propagation of Marseilles Prolog via Edinburgh. In December 1974 the mathematicians and logicians Hajnal Andreka and Istvan Nemeti obtained their foot-long box of cards and took it back with them to Budapest. Without much delay it got into the hands of Péter Szeredi." [van Emden 2006]


  • Marc Bergman and Henry Kanoui. SYCOPHANTE, système de calcul formel sur ordinateur, final report for a DRET contract (Direction des Recherches et Etudes Techniques), Groupe Intelligence Artificielle, Faculté des Sciences de Luminy, Université Aix-Marseille II, France, 1975
  • Henry Kanoui. Some aspects of symbolic integration via predicate logic programming. ACM SIGSAM Bulletin, 1976. ACM Digital Library
  • Gérard Battani et Henri Meloni. Mise en oeuvre des contraintes phonologiques, syntuxiques et sémantiques dans un systéme de compréhension automatique de la parole, 3ème cycle thesis, Groupe Intelligence Artificielle, Faculté des Sciences de Luminy, Université Aix-Marseille II, France, June 1975.
  • See [Warren 1974c].
  • See [Warren 197x].
  • Janusz S. Bień. Interactive sessions with Marseille Prolog, March 1974. Gift of Janusz S. Bień, who notes, "BTW, Warren was leaving Marseille on the day I arrived; I took over his dormitory room ...".
    • Marseille Prolog group. EPILOGUE. University of Marseille, 1973. EPILOGUE was a command file that automated some of the details of running the editor and the Prolog system. It ran on the IBM 360/67 machine (running the CP-CMS operating system) at the University of Grenoble computing center. PDF
    • Janusz Bień. IN. Program to test membership of an atom in a list. March 7,1974. Scanned teletype listing of entry and test of a simple program using Marseille Prolog on the IBM 360/67 at the University of Grenoble. PDF
    • SUPERCOL execution, March 14, 1974. Listing of a run by Janusz Bień applying SUPERCOL to several sentences, using Marseille Prolog on the IBM 360/67 at the University of Grenoble. PDF
    • Janusz S. Bień. IN2 editing and testing. March 29, 1974. Listing of a run by Janusz Bień editing and testing a predicate IN2 that tests whether one list is a sublist of another, using Marseille Prolog on the IBM 360/67 at the University of Grenoble. The test generated all subsequences of a given list, using backtracking. Bień comments: "You may note two file types (extensions): DONPROL (donné Prolog - the text) and ETAPROL (état Prolog - saved state of the interpreter with the program read in)." PDF
  • David H. D. Warren. PROLOG to DEC 10 Machine Code Compiler, 1975.
  • V. Dahl and R. Sambuc. Un système de banque de données en logique du premier ordre, en vue de sa consultation en langue naturelle. D.E.A. Report, Univ. Aix-Marseille, 1976. Copy courtesy of Veronica Dahl.  PDF

    Includes full source code.

  • V. Dahl. Un système deductif d'interrogation de banques de données en espagnol. Thèse Doctorat de Spécialité, Univ. Aix-Marseille, 1977.
  • H. Coelho and L. M. Pereira. GEOM: a Prolog geometry theorem prover. Memória No. 525, 70 pages, Laboratório Nacional de Engenharia Civil (LNEC), Lisbon, 1979. PDF at

    "A listing of the program GEOM written and a PROLOG user's guide will be sent upon request.

  • Helder Coelho and Luís Moniz Pereira. Automated reasoning in geometry theorem proving with Prolog. Journal of Automated Reasoning, December 1986, Volume 2, Issue 4, pages 329-390. SpringerLink

    "A listing of the program GEOM written in the Edinburgh standard notation will be sent upon request. However, along this paper we used the old syntax available with the Prolog written in FORTRAN IV developed at Marseille, where literals have '+' or '-' according to whether they are positive or negative. Infix operators are used, and variables are preceded by '*'."

  • Veronica Dahl. Translating Spanish into Logic through Logic. Computational Linguististics. Volume 7, Number 3 (July 1981), pages 149–164.


Prolog II, 1977-1982

"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 [Apple II) with floppy disk virtual memory ..."

[Dahl 2017]

* Prolog II included the dif/2 predicate, which had been part of Prolog 0 but not Prolog 1 or Edinburgh Prolog.

  • Verónica Dahl. In Memoriam: Alain Colmerauer (24 January 1941 - 12 May 2017). Association for Logic Programming Newsletter. Online at
  • PrologII+. Manuel de référence, PrologIA, Marseille. PDF at
  • A. Colmerauer, H. Kanoui, and M. Van Caneghem. Etude et réalisation d'un système Prolog. Internal report, Groupe d' Intelligence Artificielle, Universite Aix-Marseille II, May 1979.
  • Henry Kanoui and Michel van Caneghem. Implementing a very high level language on a very low cost machine. Rapport, Marseille: Group d'Intelligence Artificielle, University d'Aix-Marseille, Luminy, 1980.
  • A. Colmerauer, H. Kanoui, and M. Van Caneghem. Last steps towards an ultimate Prolog. In Proceedings of the 7th International Joint Conference on Artificial intelligence - Volume 2 (IJCAI’81). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 947–948, 1981. PDF at
  • Miguel Filgueiras. Un Interpreteur de Prolog. G.I.A., Marseille, 1982.
  • Alain Colmerauer. Prolog and Infinite Trees. In [Clark and Tärnlund 1982], pages 231-251. PDF
  • Alain Colmerauer. Equations and Inequations on Finite and Infinite Trees. Proceedings of the International Conference on Fifth Generation Computer Systems, 1984, ICOT. PDF at
  • Miguel Filgueiras. A Prolog Interpreter Working with Infinite Terms. In [Campbell 1984], pages 250-258.
  • Francis Giannesini, Henry Kanoui, Robert Pasero, Michel van Caneghem. Prolog. International Computer Science Series, Addison-Wesley, 1986. (Published in French, English, German, Spanish, and Italian editions.)
  • Alain Colmerauer. Theoretical model of Prolog II. In: [van Caneghem and Warren 1986], pages 3-31.
  • Alain Colmerauer. Prolog in 10 figures, Communications of the ACM, Volume 28, Number 12, pagers 1296-1310, December 1985. ACM Digital Library
  • Michel van Caneghem and David H. D. Warren, editors. Logic programming and its application, Ablex Publishing Corporation, 1986.
  • 1982: Prolog II a new theoretical model. Includes illustrations and downloads (manual and executable). Online at
    The download link for the program is broken, but this works: .zip via


Prolog III, 1983-1990, PrologIA as well as University of Marseille

"Prolog was initially designed to process natural languages. Its application in various problem solving areas has demonstrated its capabilities, but has also made clear its limitations. Some of these limitations have been overcome as a result of increasingly efficient implementations and ever richer environments. The fact remains, however, that the core of Prolog, namely, Alan Robinson's unification algorithm, has not changed fundamentally since the time of the first Prolog implementations. Moreover, it is becoming less and less significant compared to the ever-increasing number of external procedures as, for example, the procedures used for numerical processing. These external procedures are not easy to use. Their evocation requires that certain parameters be completely known, and this is not in line with the general Prolog philosophy that it should be possible anywhere and at any time to talk about an unknown object x.

In order to improve this state of affairs, we have fundamentally reshaped Prolog by integrating at the unification level: 1) a refined manipulation of trees, including infinite trees, together with a specific treatment of lists; 2) a complete treatment of two-valued Boolean algebra; 3) a treatment of the operations of addition, subtraction, multiplication by a constant and of the relations <, ≤, >, ≥ 4) the general processing of the relation ≠. By doing so, we replace the very concept of unification by the concept of constraint solving in a chosen mathematical structure. By mathematical structure, we mean here a domain equipped with operations and relations, the operations being not necessarily defined everywhere." [Colmerauer 1990]


Prolog IV, 1990-1996, PrologIA

"... 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. ..." [Dahl 2017]

"What is Prolog IV?

  • The leaves of a tree can be real numbers. The Boolean values are as simple as 0 and 1, which are integers, which are rational numbers, which are real numbers.
  • 120 evaluable predicates which generate constraints.
  • ISO-standard syntax. P. Deransart, A Ed-Dbali and L. Cervoni, Prolog: The Standard, Springer, 1996.
  • It utilizes mainly an algorithm of approximate resolution by computing a fixed point. This was the basis of BNR-Prolog."
[Colmerauer 2011]

  • Alain Colmerauer. Les bases de Prolog IV. Publication interne du LIM, Marseille, 1996. PDF at
  • F. Benhamou, P. Bouvier, A. Colmerauer, H. Garetta, B. Giletta, J.L. Massat, G.A. Narboni, S. NʼDong, R. Pasero, J.F. Pique, Touraïvane, M. Van Caneghem et E. Vétillard. Le manuel de Prolog IV. PrologIA, Marseille, June 1996. PDF at
  • Alain Colmerauer. From natural language processing to Prolog. Lecture slides, Academy of Mathematics and Systems Science, Beijing, April 8, 2011. PDF at
  • 1996: Prolog IV the approximation of non-linear constraints. Downloads (manual and executable). Online at


Université de Montréal



Before he went to Marseille, Alain Colmerauer led the TAUM (Traduction Automatique de l'Université de Montréal) project for automatic translation from English to French. He designed a tree rewriting language called Q-systems for use in this project.

"The Q-systems were written in ALGOL by Alain Colmerauer and were operational by October 1969. Michel van Caneghem and Franqois Stellin, then completing a master's degree, developed a FORTRAN version, and Gilles Steward developed an ultra-fast version in machine language for the CDC 6400 computer of the University of Montreal. These Q-systems were used by the entire TAUM project team to construct a complete chain of automatic English-French translations. The English morphology was written by Brian Harris, Richard Kittredge wrote a substantial grammar for the analysis of English, Gilles Stewart wrote the transfer phase, Jules Danserau wrote the grammar for the French synthesis, and Michel van Caneghem developed a complete French morphology [Taum 1971]. The Q-systems were also used a few years later to write the METEO system, a current industrial version of which produces daily translations of Canadian weather forecasts from English into French." [Colmerauer and Roussel 1996]

  • Alain Colmerauer. Les systèmes-q ou un formalisme pour analyser et synthétiser des phrases sur ordinateur. Internal publication no 43, Département d'Informatique, Université de Montréal, September 1970. Online at
  • TAUM 71, Annual report, Projet de Traduction Automatique de l'Université de Montréal, Jan. 1971.
  • Irena Findeisen-Bellert. Interactive session with TAUM translating a sentence from English to French, circa 1972. Gift of Janusz Bień. PDF
    Findeisen-Bellert joined McGill University in Montréal in 1972.


Marseille Prolog for Control Data 6000

"A former student, Hélène Le Gloan, installed [Marseille Prolog] at the University of Montreal." [Colmerauer and Roussel 1996]
  • Hélène Le Gloan. Implantation de PROLOG, Internal report, Université de Montréal, 1974.

"The first installation of Prolog in Warsaw was that of a version prepared by Le Gloan (1974) for the CDC6000 series. The principal difference with respect to the original version (Battani and Meloni, 1973) was the manner in which the interpreter's tables were accessed. The CDC machines were very fast, but had only up to 128K words of memory; each word had 60 bits, though, so the potential amount of data items - addresses in various linked data structures - was three times as large. Le Gloan replaced all array accesses with calls to simple packing/unpacking routines.

The loss in execution speed was considerable. This was compounded by the fact that the interpreter was not a Prolog interpreter really: it could only interpret the internal representation of a Prolog program in its tables. The 'real' Prolog interpreter (i.e. the program which could read and store Prolog clauses, read and write terms, and the like) was itself a Prolog program (Roussel, 1975) executed by the FORTRAN interpreter.

The effect was that our CDC CYBER 73, which ran at approximately 1.2 million instructions per second, read in Prolog programs at the average speed of 5 seconds per clause. As the machine was constantly labouring under a heavy load of multiprocessed jobs flowing in from a number of remote card-reader/printer terminals, it was impracticable to run Prolog for longer than a minute or so. In spite of all the packing, one needed to run in a low-priority storage class (we needed at least 72 000 (octal) words, as opposed to the standard of 54 000 (octal) for FORTRAN compilations, etc.), so a one-minute job used to hang in the input queue for up to 10 hours. Longer runs had to wait until the weekend.

Fortunately, the interpreter's internal state could be saved on a file between successive runs, so in spite of all this, Prolog was used for various small tasks, even by students. S. Szpakowicz even wrote his PhD program - a parser for a significant subset of Polish - in Prolog. With the low tum-around, reading in ten clauses at a time, it took him several months to get the program into the machine: spectacular evidence of Prolog's ability to captivate the mind!" [Kluźniak 1984]


University of Edinburgh

"One dark morning in October 1972 in Edinburgh, Bob Kowalski sat me down on the couch in his living room. `I'll show you something interesting. We call it programming in logic.'

I had flown in from California the day before to take up my appointment at the Department of Machine Intelligence under the direction of Donald Michie."


As a follow-up to our session on Bob's couch upon my arrival in Edinburgh in the fall of 1972, Bob arranged a few meetings as a sort of crash course for new arrivals in resolution and programming in predicate logic. These included David Warren and Austin Tate, two new students who were also to work under Michie.

David and I attended Bob's crash course. If there were any others, they couldn't have been more than one or two. By November it was clear that the fixpoint characterization applied to logic programs. In the spring of 1973 Bob and I made good progress with this work. I found it very exciting. I learned about the compactness theorem and we used it. Bob was not happy with it. He had the feeling it could be simpler. When we split for the summer, he suggested I leave it with him to see if he could find a more satisfactory exposition. By the time I returned, he had found the beautifully simple one-step inference characterization that can be found in our JACM paper.

In the course of 1973 Colmerauer and Roussel visited. They reported on their Prolog implementation, which had control annotations on the clauses. Our reaction was lukewarm: it seemed too far removed from logic.

I enjoyed programming in logic, though we couldn't run anything. We had learned how to append lists from the Marseilles people. When I told Bob my latest brainwave:

member(x,y) <- append(u,x.v,y)

he was gratifyingly surprised.


What little interest in Prolog there might have been that summer in Edinburgh continued to evaporate until David Warren returned from his visit to Marseilles in February 1974. He brought two things: a program and a foot-long box of cards. The program was WARPLAN, a one-page program that Bob, I, and others studied for years afterwards. The box contained the new Prolog. This was the second implementation, done in Fortran by Battani and Meloni.

The effect was electrifying. Actually being able to run programs (an opportunity obligingly arranged by David on the new PDP-10 computer in Edinburgh) made a huge difference, though it shouldn't have from a rational point of view. Moreover, the formerly ubiquitous control annotations had gone, being replaced by an occasional cut, which was much less obtrusive.


Some of the 1974 visitors were unreservedly interested not only in logic programming, but even in Prolog. These included Keith Clark from Queen Mary College, Luís Pereira from Lisbon, and Tomasz Pietrzykowski from the University of Waterloo in Canada."

[van Emden 2006]


Logic Programming

  • Robert Kowalski and Donald Kuehner. Linear Resolution with Selection Function In Artificial Intelligence, Vol. 2, 1971, pp. 227-60. Reprinted in: Anthology of Automated Theorem-Proving Papers, Vol. 2, Springer-Verlag, 1983, pp. 542-577. Online at
  • Robert Kowalski. Predicate Logic as Programming Language. In: Proceedings IFIP Congress, Stockholm, North Holland Publishing Co., 1974, pp. 569-574. Reprinted in Computers for Artificial Intelligence Applications, (eds. Wah, B. and Li, G.-J.), IEEE Computer Society Press, Los Angeles, 1986, pp. 68-73. Online at
  • Robert Kowalski. Logic for Problem Solving. Memo No. 75, Department of Computational Logic, School of Artificial Intelligence, University of Edinburgh, March 1974. PDF at

    An extended version of these lecture notes, first written for an advanced course at the Mathematics Center in Amsterdam, was published as:

  • David H. D. Warren. Warplan: A System for Generating Plans. Memo No. 76, Department of Computational Logic, School of Artificial Intelligence, University of Edinburgh, June 1974. Courtesy of Tim Lindholm. PDF
  • [David H. D. Warren.] The Car Assembly Problem. Handwritten slides, 7 pages, undated. Gift of Maarten van Emden. PDF
  • 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. Online at
  • Maarten van Emden. The Early Days of Logic Programming: A Personal Perspective. Assocation for Logic Programming Newsletter, Vol. 19 n. 3, August 2006. Online at


PROLOG to DEC 10 Machine Code Compiler, Version 13 Sep 1975.

This compiler was written in Marseille Prolog by David H. D. Warren. Computer History Museum Lot #X6167.2011, gift of Maarten van Emden. Posted here with permission of David H. D. Warren.

  • David H. D. Warren. Listing. PDF
  • David H. D. Warren. Example 1: Quicksort. Circa 1975. Example of generated code from PROLOG to DEC 10 Machine Code Compiler. PDF
  • David H. D. Warren. Example 2: Illustrates the improved scheme for indexing clauses. Circa 1975. Example of generated code from PROLOG to DEC 10 Machine Code Compiler. PDF


DECsystem-10 PROLOG

Source code

  • Bruce Baumgart, archivist. Stanford AI Lab W.A.I.T.S. backup tapes. The source files include versions modified to run on the Stanford system, as well as original versions.


  • Luís Moniz Pereira, Fernando C. N. Pereira, and David H. D. Warren. User's Guide to DECsystem-10 Prolog. Technical Report 03/13/5570, Laboratório Nacional De Engenharia Civil, Lisbon, September-October, 1978. Provisional version. Interpreter version 1.32 and compiler version 1.11. PDF at - ASCII at
  • Lawrence Byrd, Fernando Pereira, and David Warren. A Guide to Version 3 of DEC-10 Prolog. Department of Artificial Intelligence, University of Edinburgh, June 1980. ASCII at
  • Lawrence Byrd. Prolog Debugging Facilities. Technical note, Department of Artificial Intelligence, Edinburgh University, 1980. ASCII at
  • D. L. Bowen (editor), L. Byrd, F. C. N. Pereira, L. M. Pereira, and D. H. D. Warren. DECsystem-10 Prolog User's Manual. University of Edinburgh, Department of Artificial Intelligence, 10 November 1982. Prolog version 3.47. ASCII at CMU AI Repository
  • Ernie Davis and Udi Shapiro. A Prolog Tutorial Based on User's Guide to DECsystem-10 Prolog. December 1980. ASCII at
    Accompanying examples. ASCII at


  • [D. H. D. Warren,] L. M. Pereira and B. Meltzer. Implementation of an efficient predicate logic interpreter based on Earley deduction. Scientific proposal report for the SRC. April 1975.

    "A proposal for a new inference system was done by Warren (Pereira and Meltzer), on the implementation of an efficient predicate logic interpreter based on Earley deduction (ED). The ED is a top-down proof procedure, analogous to Earley's algorithm for parsing context-free languages, and it uses simple instantiation as a rule of inference in addition to resolution." [Coelho and Pereira 1979]

  • D. H. D. Warren, L. M. Pereira and F. Pereira. Prolog - the Language and its Implementation compared with Lisp, Proc. ACM Symposium on Artificial Intelligence and Programming Languages, Rochester, N.Y., 1977. ACM Digital Library PDF at
  • D. H. D. Warren, Implementing Prolog-Compiling Predicate Logic Programs. Research Reports 39 and 40, Department of Artificial Intelligence, University of Edinburgh, May 1977. Superseded by [Warren 1978]. Gift of Maarten van Emden.
    • Report 39. PDF
    • Report 40. PDF
  • David H. D. Warren. Applied logic : its use and implementation as a programming tool. Ph.D. thesis, University of Edinburgh, 1978. Online at - Online at
  • David H. D. Warren. PROLOG on the DECsystem-10. Pages 112-121 in [Michie 1979]. Discusses tail-recursion optimization. PDF
  • David H. D. Warren. An Improved PROLOG implementation which optimises tail recursion. Research Paper 156, Dept. of Artificial Intelligence, University of Edinburgh, Scotland, 1980; also published in [Tärnlund 1980]
  • D. H. D. Warren. Perpetual Processes - an Unexploited Prolog Technique. Logic Programming Newsletter, number 3, Universidade Nova de Lisboa, Summer 1982, page 2.
  • D. H. D. Warren. Higher-order extensions to PROLOG: are they needed? In Hayes, J. E., Michie, D., and Pao, Y.-H. (Eds.), Machine Intelligence 10, 1982. Ellis Horwood. Online at AAAI AITopics
  • David H. D. Warren. Optimizing Tail Recursion in Prolog. In: Michel van Caneghem and David H. D. Warren, eds. Logic Programming and its Application. Ablex, 1986.
  • Donald Michie, editor. Expert Systems in the Micro-Electronic Age. Edinburgh University Press, 1979.
  • Sten-Åke Tärnlund, editor. Proceedings of the 1980 Logic Programming Workshop, Debrecen, Hungary, 1980. Department of Computer Science, University of Stockholm, Sweden.


  • D. H. D. Warren. Generating conditional plans and programs. Procs. AISB Conf., p.34-354, Edinburgh. July 1976.
  • David H. D. Warren. Logic programming and compiler writing. Software: Practice and Experience, Vol. 10, February 1980, pages 97-125. Online at Online at
  • Fernando C. N. Pereira and David H. D. Warren. Definite clause grammars for language analysis — A survey of the formalism and a comparison with augmented transition networks. Artificial Intelligence, Vol. 13, Issue 3, May 1980, pages 231-278. ScienceDirect CiteSeerX

    "This formalism -- the main subject of our paper -- we call definite clause grammars (DCGs). DCGs are a special case of Colmerauer's (1975) "metamorphosis grammars", which are for Chomsky type-0 grammars what DCGs are for CFGs. Although metamorphosis grammars can be translated into definite clauses, the correspondence is not nearly so direct as that for DCGs."

  • David H. D. Warren. Efficient Processing of Interactive Relational Data Base Queries expressed in Logic. Procedings of 7th Very Large Data Bases Conference, September 9-11, 1981, Cannes, France, Proceedings, pages 272-281.
  • Fernando Carlos Neves Pereira. Logic for Natural Language Analysis. Ph.D. thesis, University of Edinburgh, 1982. era (Edinburgh Research Archive)

    A slightly revised version was published as Technical Note 275, AI Center, SRI International, January 1983. Online at

  • David H. D. Warren and Fernando C. N. Pereira. Chat-80 prototype natural language question answering system.
  • David H. D. Warren. Issues in Natural Language Access to Databases from a Logic Programming Perspective. Proceedings of the 20th annual meeting on Association for Computational Linguistics, 1982, pages 63-66. PDF at
  • Leon Sterling, Alan Bundy, Lawrence Byrd, Richard O'Keefe, and Bernard Silver. Symbolic reasoning with PRESS. In Computer Algebra (J. Calmet, ed.), Lecture Notes in Computer Science 144, Springer-Verlag, 1982. era (Edinburgh Research Archive)


PDP-11 Prolog

  • C. Mellish. Minimal documentation of the PDP-11 Prolog system. Dept. of Artificial Intelligence, University of Edinburgh, 1978. (Informal note.) Cited in [Warren 1979].
  • W. Clocksin and C. Mellish, The Unix Prolog System. Software Report 5, Department of Artificial Intelligence, University of Edinburg, 1979. Cited in Clocksin and Mellish, Programming in Prolog, first edition.
  • W. Clocksin, C. Mellish, and R. Fisher. The RT-11 Prolog System. Software Report 5a (revised), Department of Artificial Intelligence, University of Edinburgh, Edinburgh, Scotland, 1980. Cited in Clocksin and Mellish, Programming in Prolog, first edition.
  • C. S. Mellish. An Alternative to Structure Sharing in the Implementation of a PROLOG Interpreter. Research Paper 150, Department of Artificial Intelligence, University of Edinburgh, 1980.
  • C. S. Mellish. An Alternative to Structure Sharing in the Implementation of a PROLOG Interpreter. Pages 99-106 of: [Clark and Tärnlund 1982]. Condensed from [Mellish 1980].


EMAS Prolog

In 1980, Luís Damas wrote a Prolog in the IMP programing language for Edinburgh Multi-Access System (EMAS) running on ICL 2900 computers. [F. Pereira, C-Prolog, 1982]

  • Lawrence Byrd, editor. User's guide to EMAS Prolog. Occasional Paper 26, Department of Artificial Intelligence, University of Edinburgh, 1981.


  • James R. Cowls. Analysis of Descriptive Texts. ANLC '83 Proceedings of the first conference on Applied natural language processing. PDF at
    "The code for the system is written in PROLOG (Clocksin and Mellish, 1981) as implemented on the Edinburgh Multi Access System (Byrd, 1981). This is a standard implementation of the language, with the single enhancement of a second internal database which is accessed using a hashing algorithm rather than a linear search. This has been used to improve the efficiency of the dictionary search procedures."



C-Prolog was written by Fernando Pereira around 1982 in the EdCAAD project in the Department of Architecture at the University of Edinburgh. It was based on EMAS Prolog, written by Luís Damas. There were also contributions by Lawrence Byrd. [F. Pereira,, 1982]

"C-Prolog was designed for machines with a large, uniform, address space, and assumes a pointer cell 32 bits wide. At the time of writing, it has been tested on VAX machines under the UNIX and VAX/VMS operating systems, on the Sun workstation under 4.1/2 UNIX, and has been ported with minor changes to other MC68000-based workstations and to the Three Rivers PERQ." [F. Pereira 1984]

Source code


  • Fernando Pereira, editor. C-Prolog User's Manual Version 1.2. SRI International, September 4, 1984. Scan courtesy of Bart Demoen and Maurice Bruynooghe. PDF
  • Fernando Pereira, editor. C-Prolog User's Manual Version 1.2a. Edinburgh Computer Aided Architectural Design (EdCAAD), March 1983. Scan courtesy of Bart Demoen and Maurice Bruynooghe. PDF
  • Fernando Pereira, editor. C-Prolog User's Manual. Version 1.5, February 22, 1984. Online at
  • Richard O'Keefe. Portability of C-Prolog. AI-List Digest, Volume 2, Issue 25, March 6, 1984. Forwarded from Prolog Digest. Online at
    "The first thing to beware of is that there are two main versions of C-Prolog drifting around. The one most people have is the one distributed by EdCAAD (which is where Fernando Pereira wrote it), and while that runs under VAX/UNIX and VAX/VMS both, and is said to run on at least one 68000 box, V7 C compilers don't like it much. The other version is distributed by EdAI on a very informal basis, but it should be available from Silogic in a couple of weeks. The EdAI version has been ported to the Perq (running ICL's C-machine micro-code and their PaNiX port of V7 UNIX) and to another C-machine called the Orion (that compiler isn't a derivative of PCC). C-Prolog has something like one cast per line, the EdAI version has stronger type declarations so that the compiler produces no warning messages. Both versions are essentially the same, so EdAI cannot distribute their version to anyone who hasn't got a licence for the EdCAAD version."



"Prolog-X was designed just before I left Edinburgh in 1980. Workstations (such as the Apollo, Sun, etc) were the latest thing, and we (Lawrence Byrd, David Bowen, and I) wanted a workstation Prolog system compatible with DEC-10 Prolog. We reckoned there would be a ready market for such software. We were also envious of the Lisp Machine developments, and wanted to do the same thing for Prolog. Using pseudocode notes that we wrote, I wrote a 'reference' implementation in Pascal, and at about the same time I moved to Oxford to take up a research post in the Robot Welding Group to develop image processing algorithms for real-time control of a robot arc-welding system. I therefore had less time to work on Prolog-X. The reference implementation sort of worked, and the 'test' was to run Chat-80 on it (a program written by David Warren and Fernando Pereira) to answer questions in English about world geography, e.g. "What is the capital of Upper Volta?"), which I ran on a PDP-11/10 bought to control the robot welder. At Edinburgh, David Bowen had more time to work on a version of Prolog-X called NIP, so that made some progress.

Meanwhile, in Oxford I made contact with Tim [Robinson] from High Level Hardware, who had developed a microcoded workstation called the Orion (there is a good Wikipedia article on this machine). Tim wanted a Prolog system for the Orion, so I gave him the Prolog-X reference implementation. He microcoded it, and we reckoned it would have amazing performance because of that. However, several simultaneous events conspired to halt the microcoded Prolog on the Orion.

  1. I had by that time moved to Cambridge, where I was running an Orion, but had no time to make further development on the Prolog system. I used the Orion essentially as a very nice graphics workstation for my robotics research.
  2. Computer architecture had moved on; microcoding was no longer where the performance was. We found that running C-Prolog on a new 32-bit microprocessor chip (by Fairchild) was actually faster than the microcoded Prolog!
  3. At Cambridge I began collaborating with Acorn during its transition into ARM, and they had a workstation called the Archimedes using their own RISC chip on which I got Prolog-X running. However, this project folded as the transition to ARM matured and they decided not to offer consumer workstations."
[William Clocksin, personal communication, 11 June 2019]

Source code

  • William Clocksin. Prolog-X source code. 1983-1987? Written in C and Prolog. This version was modified by Tim Robinson to run as a (partially) microcoded virtual machine on the High Level Hardware ORION. The distribution includes two directories: prologX contains the C and Prolog source code; prologM contains the microcode. Courtesy of Tim Robinson. .tar.gz

    prologX/ describes the full bootstrap procedure, which uses an existing CProlog system to execute the "standalone compiler" ( on the three modules written in Prolog (,, and However prologX includes the compiled versions (with suffix .zap), so that step may be omitted. builds Clocksin's original C version; makefile builds Robinson's microcoded version, which depends on the microcode in the parallel prologM directory.

Documents and papers

  • W. F. Clocksin. The ZIP Virtual Machine. January 1983, with subsequent revisions. [By this time, Clocksin was at Oxford or Cambridge.] Courtesy of Tim Lindholm. PDF

    "Prolog-X is an implementation of Prolog which makes use of an abstract (virtual) machine called the ZIP Machine. The ZIP Machine is defined by a pointer format, 32 registers, the format of storage areas, an instruction set, and assumptions about the layout of data structures in memory."

  • David L. Bowen, Lawrence M. Byrd, and William F. Clocksin. A Portable Prolog Compiler. In Logic Programming Workshop'83, pages 74-83, Albufeira, Portugal, 1983. PDF
  • W. F. Clocksin. What is Prolog-X? Computer Laboratory [University of Cambridge], undated, but after August 1983. Andy Cheese’s Bibliography on Functional and Logic Programming tags it CLOCK84d. Courtesy of Tim Lindholm. PDF

    "Prolog-X is a portable design for a high-performance Prolog system intended for large-scale applications. … With the impending demise of the DEC-10, together with the wish to run big programs on machines such as the VAX and 68000, I set out to design a system based on Lawrence Byrd’s ZIP abstract instruction set … . Starting around March 1982 I implemented as much as I could, time permitting, in Pascal on a VAX under VMS. … The last release was Release 1.6 (August 1983)."

  • WFC [William F. Clocksin]. Executing Prolog at Ten Times DEC-10 Speed. [Computer Laboratory, University of Cambridge.], 28 November 1983. Courtesy of Tim Lindholm. PDF

    Proposes a benchmark of naive reverse of a 30-element list, which is said to take 53.7 milliseconds under DEC-10 Prolog.

  • W. F. Clocksin. Memory Representation Issues for Prolog Implementation. Computer Laboratory, University of Cambridge, undated, but 1983 or later. Courtesy of Tim Lindholm. PDF

    Proposes a conventional (uniform) heap memory with incremental garbage collector.

  • WFC [William F. Clocksin]. Notes on new Prologs. [Computer Laboratory, University of Cambridge,] 7/5/84 [7 May 1984?]. Courtesy of Tim Lindholm. PDF

    "I suggest the Cambridge implementation of Standard Lisp to be an ideal substrate from which to build a mixed language system. At the moment, I (with ROK [Richard O’Keefe] and ACN [Arthur C. Norman]) am investigating the feasibility of writing a Prolog compiler to be integrated with the Cambridge Lisp system."

  • W. F. Clocksin. Reference Summary of Prolog-X. Computer Laboratory, University of Cambridge, June 1984; revised 20 July 1984. Andy Cheese cites a 1986 version of this document. Courtesy of Tim Lindholm. PDF

    Mentions C as the "base language", and gives the address space (and integer values) as 2^28, so presumably this is a rewrite of the earlier Pascal-based "executable specification"?

  • William F. Clocksin. Design and Simulation of a Sequential Prolog Machine.
    • Technical report, Computer Laboratory, University of Cambridge, 1984. PDF
    • Journal of New Generation Computing (NGC), pages 101-120, vol. 3, no. 1, 1985. SpringerLink

    "In this paper we describe an abstract Prolog machine, called the ZIP machine, which is suitable for implementation in software, microcode, or hardware.


    The first version of the Prolog-X system was written in Pascal under VMS for the DEC VAX in 1982. It was then ported to the ICL 2980 under VME, and the bytecode emulator was subsequently translated into the VME systems programming language S3. The first version was also used as the basis of a separate Prolog implementation design study. The second (and current) version of Prolog-X is a translation of the first version into the C language. This version runs on the following machines: the ICL Perq under PNX (similar to System III Unix), the HLH Orion (made by High Level Hardware, Ltd.) under Berkeley Unix 4.1, the DEC VAX under Berkeley Unix 4.2, and the IBM 3081 (370 architecture) under MVS."

  • W. F. Clocksin. Implementation techniques for Prolog databases. Software—Practice and Experience, Volume 15, Number 7, pages 669-675, July 1985. Wiley Online Library
  • Lisa Robinson. High Level Hardware Orion. Informational web site, circa 2009. Online at


New Implementation of Prolog (NIP)

"At Edinburgh, David Bowen had more time to work on a version of Prolog-X called NIP, so that made some progress." [William Clocksin, personal communication, 11 June 2019]

"3.2.5 NIP (CYLK, AJL)

NIP, the New Implementation of Prolog from Edinburgh, is now complete. It has been distributed by RAL to 29 research groups for use on a large range of UNIX based systems. A range of utilities and tools developed on the DEC 10 at Edinburgh are distributed with NIP and are available independently over the networks for users of other Prologs.

Release 1.1 of NIP was received from AIAI at the end of January. This was unloaded onto the following machines:

  • SUN2: fileserver, richard and harold
  • VAX: rlvd
  • Pyramid: rlya
  • Atlas-10

The installation of NIP required a few alterations to a Makefile which determined where the NIP executable files were to be found after installation. Then they were compiled and linked (all with the supplied makefile). The compiled binaries were then copied to the destination directories for general access. All but the Pyramid were relatively straight forward; the Pyramid was most frustrating due to compiler problems. (Similar problems have prevented a Whitechapel installation).

There have been two new releases of NIP. Release 1.2 arrived at the beginning of February and was successfully installed on the SUNs, VAX and Atlas-10.

Release 1.3 arrived at the end of April (24th) and has been installed on the SUNs, Orion and VAX.

Release 1.3 manuals were received from AIAI and 10 copies of these were made and set to various Prolog users within the Division." [IKBS section, 1985-1986 Annual Report, Informatics Department, Rutherford Appleton Laboratory, Chilton]

  • David Bowen. Prolog Development Project. [Memo, Department of Artificial Intelligence, University of Edinburgh], 11 April 1983.

    Estimates totaling 50 man-months for short-term tasks to be completed on “PrologX (alias ZIP)”. Some tasks annotated “(if LB)” or “(if RO)”, indicating Lawrence Byrd or Richard O’Keefe.

  • [David Bowen or William F. Clocksin?]. Disjunction for Prolog-X. August 24, 1983. Filename of document was "zipor".

    “The point of this design is to extend the existing Prolog-X design so that a number of Prolog features supported by the Dec-10 interpreter (and in one case by a library routine) may be handled by the Prolog-X compiler and byte-code interpreter.” Includes disjunction (;), if-then-else, negation by finite failure (\+), iteration (forall). Adds new instructions Or, Alt, Goto, EndOr, Arrow, Slice, and TimidCut."

  • David Bowen. New Implementation of Prolog (NIP) : Progress Report. Department of Artificial Intelligence, University of Edinburgh, 30 August 1983.

    "Initially, it seems most sensible to attempt to collaborate in this endeavor with Lawrence Byrd and Bill Clocksin who were undertaking a new, portable Prolog implementation (Prolog-X) in their spare time."

  • A. M. J. Hutchings, editor and D. L. Bowen, L. Byrd, P. W. H. Chung, F. C. N. Pereira, L. M. Pereira, R. Rae, and D. H. D. Warren. Edinburg Prolog (The New Implementation) User's Manual - version 1.4. Department of Artificial Intelligence, University of Edinburgh, 1984.
  • Bert Hutchings. Dynamic op code frequencies in NIP. Programming Systems Group Note 16, AI Applications Institute, University of Edinburgh, AIAI/PSG16/84, November 14, 1984.
  • A. M. J. Hutchings, editor and D. L. Bowen, L. Byrd, P. W. H. Chung, F. C. N. Pereira, L. M. Pereira, R. Rae, and D. H. D. Warren. Edinburgh Prolog (The New Implementation) User's Manual. Report AIAI/PSGm1/86, AI Applications Institute, University of Edinburg, 1986.


Prolog Library

"The DEC-10 Prolog Library was an extraordinary and catholic collection of Prolog routines, largely written by research workers and students in Professor Alan Bundy's Mathematical Reasoning Group at the Department of Artificial Intelligence at the University of Edinburgh. In summer 1987 we sifted through the enormous amount of material in this library, grouping similar material together and converting some of the more used programs into Edinburgh Prolog." [Johnson and Rae 1987]


Katholieke Universiteit Leuven

"Finally, Maurice Bruynooghe took Prolog to Leuven (Belgium) after a three-month stay in Marseilles (October through December 1975)." [Colmerauer and Roussel 1996]

"In June 1975, Maurice Bruynooghe visited Robert Kowalski at Imperial College and came home with 2 boxes of punched cards containing the Fortran code of the Marseille Prolog interpreter (one card was missing, it got solved).

From October to December 1975, Maurice Bruynooghe visited Alain Colmerauer in Marseille." [Maurice Bruynooghe, Prolog at KULeuven]


Pascal Prolog and PDP-11 Prolog

"In the period 1975 -1977, Maurice Bruynooghe developed a space saving interpreter in Pascal. It used structure copying instead of structure sharing and also tail recursion optimization. A presentation 'A space saving implementation of Prolog' was given at the "logic Programming Meeting" organized by Robert Kowalski, Imperial College, May 24-28, 1976. See also [Bruynooghe 1976].

In the period 1980-1981, a new implementation in C was developed. Many tapes with a copy of the system have been distributed.

There has also been other implementation work: [Ballieu 1983]."
[Maurice Bruynooghe, Prolog at KULeuven]

  • Maurice Bruynooghe. An interpreter for predicate logic programs. Part I : Basic principles. Report CW 10, Applied Mathematics and Programming Division, K. U. Leuven, Leuven, Belgium, October 1976. Online at Lirias
  • Maurice. Bruynooghe. Intelligent backtracking for an interpreter of Horn clause logic programs. Report CW 16, Department of Computer Science, K. U. Leuven, Leuven, Belgium, September 1978. Online at Lirias
  • Maurice Bruynooghe. Naar een betere beheersing van de uitvoering van programma's in de logika der Horn-uitdrukkingen. (In Dutch) Doctoral Dissertation, Afdeling Toegepaste Wiskunde en Programmatie, K. U. Leuven, Belgium, May 1979. Online at Lirias
  • Maurice Bruynooghe. The memory management of PROLOG implementations. Report CW21, Applied Mathematics and Programming Division, K. U. Leuven, Leuven, Belgium, June 1980. Published in [Tärnlund 1980]. Online at Lirias
  • Maurice Bruynooghe. Some Reflexions on Implementation Issues of Prolog. In Logic Programming Workshop'83, pages 1-6, Albufeira, Portugal, 1983. PDF.
  • Gerard Ballieu. A Virtual Machine to Implement Prolog. In Logic Programming Workshop'83, pages 40-52, Albufeira, Portugal, 1983. PDF.
  • Maurice Bruynooghe and L. M. Pereira. Deduction revision by intelligent backtracking. In [Campbell 1984], pages 194-215. Online at Lirias


BIM-Prolog (with the BIM company)

"During the summer vacation of 1983, the ministry decided that teachers would no longer be paid for overtime, so I had to quit my teaching job: another colleague at school told me about his brother Raf Venken who worked in a small company (BIM) that was looking for collaborators for a new project. He gave me the telephone number of ... Maurice [Bruynooghe]: Maurice was in waiting for a permanent research job with the national FWO (kind of NSF), and in the mean time he got the manager of BIM (Michel Van den Bossche) interested in Prolog. They wrote up a project proposal which would - in collaboration with the university in Leuven - design and implement a commercial Prolog system: BIM-Prolog. At the phone Maurice asked me my qualifications and when he heard I had a masters in mathematics, I was hired. My PhD in theoretical physics was of no interest to him." [Demoen 2007]

BIM-Prolog internal reports and technical memoranda

A large set of BIM-Prolog documents from 1984 to 1988 were provided by Gerda Janssens and Bart Demoen and were scanned by Maurice Bruynooghe. They are available here:


University of Waterloo

"After my return to Edinburgh [Tomasz] Pietzrykowski contacted me for a possible visit to Waterloo. As the arrangements firmed up, he told me he hadn't managed to get a copy of Marseilles Prolog and could I bring one. And so it was that I arrived in Waterloo in January 1975 with two presents: a plastic bag with cuttings of the Papyrus plant and a box with a foot-long stack of punched cards. Sometime in the spring of 1975 two students of Pietrzykowski, Lewis Baxter (later to invent a fast unification algorithm*) and Larry Rendell, got the Fortran of the interpreter translated to the local dialect. Thus was established the first Prolog installation in North America." [van Emden 2006]

* See for example: Lewis Denver Baxter. A Practically Linear Unification Algorithm. Research Report CS-76-13, Department of Computer Science, University of Waterloo, February 1976. PDF at


Waterloo Prolog for IBM System/370

"In 1976 Grant Roberts, a Master's student, was looking for a project. If not writing a compiler, then at least implementing an interesting language. Prolog seemed suitable. As I was the only faculty member who was at least a user of Prolog, Grant was steered in my direction.

Grant was famous in Waterloo, because as an undergraduate he had been on the Waterloo team in the Putnam competition that had done very well in the year he was on it. Grant did not share the computer scientists' disdain of the IBM 370. In fact, he loved this machine. Not because he liked programming in Fortran, or in Cobol, or in PL/I. No, he programmed in assembler. At least that was all that an outsider could make out of his activities. What he actually programmed in was his own programming language, a macro processor.

There are very few people who can do this. There are even fewer who tell about it. One of the exceptions is Mark Halpern in his memoirs in the 1991 Annals of the History of Computing where he says something about his XPOP macroprocessor. But these few tend to perform incredible programming feats. In the case of Roberts the feat was to complete in 1977 a beautifully stable Prolog implementation, the fastest in the world." [van Emden 2006]

"The most completely engineered logic programming systems to date are the PROLOG systems (cf. P. Roussel [1975], G. Roberts [1977], D. Warren et al. [1977]), which are based on ideas of Kowalski, Colmerauer, Roussel, Hayes, and Boyer and Moore (cf. Kowalski [1974], p.573)." [Kenneth Bowen 1979]

[Roberts 1977] describes the language and its implementation, which uses the structure-sharing approach, following the Marseille interpreter.

  • Grant Maxwell Roberts. An Implementation of PROLOG. Master's thesis, University of Waterloo, Waterloo, Ontario, Canada, 1977. Posted with the permission of Grant Roberts. PDF
  • Anonymous. A Prolog Interpreter. Logic Programming Newsletter, Universidade Nova de Lisboa, Issue 2 (Autumn 1981), p. 11.

    "Grant Roberts' Prolog interpreter for IBM 370, 3031, 4341, and similar machines is now finally being distributed by the University of Waterloo. Note that this interpreter runs only under the VM /CMS operating system. A license for educational institutions costs Can$500 a year. Address enquiries to ..."

Source code

  • Grant Roberts. Waterloo Prolog source code assembly listing, version 1.2, 13 March 1982. PDF
  • Michigan Terminal System, Distribution 6.0, April 1988, contains some locally-produced documentation for Waterloo Prolog 1.7 from 1985, but, for licensing reasons, no Waterloo/Intralogic files. Online at

User manual

  • Grant Roberts. Waterloo Prolog User's Guide, version 1.4. With handwritten corrections by author. PDF - Grayscale PDF


Roberts later formed a company called Intralogic Inc. to develop and distribute Waterloo Prolog commercially. This was a sideline to Roberts' main business, which was an application software development firm. Intralogic developed another PROLOG implementation in C for Unix but that was not commercially successful. Roberts decided to focus on his primary business, scaling back Intralogic and just distributing the original IBM System/370 PROLOG with some enhancements. He recalls there were about 90 licensees worldwide at the peak in the 1980's, tapering off to a few licensees by the late 1990's when he terminated Intralogic. [Grant Roberts, personal communication, 17 April 2019]


  • Allen Hustler. Programming law in logic. Research Report CS-82-13, Department of Computer Science, University of Waterloo, Canada, 1982. PDF


Waterloo Unix Prologs

In the 1970s and 1980s, several students implemented versions of Prolog for Unix.
  • R.J. Ferguson, 1977.
    • R.J. Ferguson. An Implementation of Prolog in C. Master's Thesis, Department of Computer Science, University of Waterloo, 1977.
    • Maarten H. van Emden. An Algorithm for Interpreting PROLOG Programs. Technical Report CS-81-28, Department of Computer Science, University of Waterloo, September 1981. PDF at

      "Many thanks to Ron Ferguson for some very helpful discussions."

  • T. Y. Ng, 1982.
    • T. Y. Ng. Prolog Implementation. M. Math. Thesis, Department of Computer Science, University of Waterloo, 1982.
    • M. H. van Emden. An interpreting algorithm for Prolog programs. First International Logic Programming Conference, University of Marseille, 1982. Also published in: [Campbell 1984]. Posted by permission of Maarten van Emden. PDF

      "Many thanks to Ron Ferguson for some very helpful discussions and to Paul Ng for his willingness to use the algorithm in this form as basis for his implementation work."

    • J. A. Campbell, editor, Implementations of Prolog, Ellis Horwood, 1984.
  • Mantis Hoi Ming Cheng, 1984.
    • R. G. Goebel and M. H. M. Cheng. Waterloo Unix Prolog Reference Manual. Logic Programming Group, University of Waterloo, 1983.
    • M. H. M. Cheng and R. G. Goebel. Waterloo Unix Prolog Implementation Manual. Logic Programming Group, University of Waterloo, 1984.
    • M. H. van Emden and R. Goebel. Waterloo Unix Tutorial Version 1.2. Logic Programming Group, University of Waterloo, 1984
    • Mantis H. M. Cheng. Design and implementation of the Waterloo Unix Prolog environment. Master's thesis, Department of Computer Science, University of Waterloo, December 1984. PDF at
    • Mantis H. M. Cheng. Applications of Waterloo Unix Prolog.
      • Waterloo Unix Prolog and Lisp Environment (WUPL). A functional programming language based on LispKit Lisp and integrated into the Waterloo Unix Prolog interactive programming environment. Report with User Manual, Implementor Manual, and source code listing. PDF
      • FPL. A typed functional programming language supporting lazy evaluation, higher-order functions and universal polymorphism. Originally written for Waterloo Unix Prolog, but ported to ALS Prolog. Scanned listing includes manual, source code, and many example FPL definitions. August 1, 1988. PDF


Warsaw University

These projects were carried out at the Institute of Informatics, Warsaw University.

  • Stanisław Szpakowicz. The Prolog Team at Warsaw University. Logic Programming Newsletter, Universidade Nova de Lisboa, Issue 1 (Spring 1981), p. 8. PDF
  • Feliks Kluźniak. The `Marseille Interpreter' -- a personal perspective. In [Campbell 1984]. Posted by permission of Feliks Kluźniak. PDF


First installation of Marseille Prolog in Warsaw

Hélène Le Gloane's port of Marseille Prolog to the Control Data 6000 at the Université de Montréal was installed on a CDC CYBER 73 at Warsaw University; see Kluźniak's description here.


Port of Marseille Prolog to ODRA 1305 (ICL 1906-compatible)

"In 1978 we obtained funding for porting Prolog to an ODRA 1305 (essentially an ICL 1900). The machine was much slower, but it had 24-bit words, so there was no question of packing: we had high hopes that the result would be a faster interpreter (in the end it turned out to be twice as fast as on the CYBER). The memory was also only 128K, but we could have all of it, as the machine had only a very simple executive program and was operated in open shop." [Kluźniak 1984]

For a detailed description of this implementation, which is based on the Marseille interpreter, see [Kluźniak 1984].

Source code

  • Snapshot of ODRA Prolog. Gift of Janusz S. Bień. ZIP archive Unpacked Kluźniak [1984] notes: "The Prolog system was in the form of four decks of cards."
    • "There was the interpreter proper, which consisted of about 2000 FORTRAN cards." odra.3
    • "Another FORTRAN program - about 350 cards - was used to create a binary file with the interpreter's internal state. This program, which we called 'The Initiator', could only read in Prolog programs in a very low-level form - essentially a character representation of the internal form of Prolog clauses. The interpreter used Prefix Polish representation of trees, so we called this low-level language Prefix Prolog. To give an example of its distinctive flavour, here is the well-known procedure APPEND(*):
      (*) The first digit is the number of variables. Each functor is followed by its arity and variables are represented by integer offsets (not ambiguous, as numbers greater than 9 are not allowed)."
    • "The third deck - about 75 cards - started with a card defining the character set, followed by 17 cards of integer sequences defining the interpreter state's 'kernel' (the representation of NIL, etc.). Seven cards declared the non-character functors and predicates used in the Prefix Prolog program which followed, 'The Bootstrapper', which could read and execute programs written in what we called 'Prolog B'. This was rather primitive, but already similar to full Prolog ('Prolog C'). One could write:
                  +APPEND(.(*EL,*L), *L2, .(*EL,*L3)) -APPEND(*L,*L2,*L3)
      " odra.5
    • "The last deck consisted of about 400 cards in Prolog B, defining the full Prolog Monitor (interpreter with 'real' diagnostics, high-level input/output routines, etc.). The Monitor was written in a style apparently-designed to squeeze the last ounce of advantage from unification's ability to deal with multi-purpose arguments. Despite repeated attempts to read it, we could not at first understand more than small isolated fragments of this program, so for a long time we did it no harm apart from changing French diagnostic messages to Polish." odra.6



"After we finished with the ODRA, a Pascal interpreter was written for the CYBER [Kluźniak 1981]. This used no bootstrapping and a different program representation,* but otherwise -- on a conceptual level - the general design of Marseille Prolog. It was very successful: reading time was about 20 clauses per second and small programs could be run in 54 000 (octal) words -- the turn-around for our Prolog class was not worse than for FORTRAN. We used it quite extensively until the telephone line to the CYBER was cut off in December 1981.
> * Direct tree representation, but tightly-packed print-names." [Kluźniak 1984]


IIUW Prolog for SM-4

Feliks Kluźniak and Stanisław Szpakowicz wrote an implementation of Prolog for the SM-4, an Eastern-Bloc computer compatible with a DEC PDP-11/40. The upper layer, written in Prolog by Szpakowicz, performed parsing of full Marseille syntax Prolog and top-level executive control. The lower layer, written in CDL2 by Kluźniak, was the actual Prolog engine (unification, control, etc.). The basic operations for CDL2 such as integer addition, written in assembler, were provided by Piotr Carlson. Carlson also implemented a software-based paged virtual memory. The project took place in 1982 and 1983.


Toy Prolog

Toy is a "simple but fairly complete implementation of Prolog" whose implementation is described in Chapter 7 of [Kluźniak and Szpakowicz 1985]. It was written in Pascal on a PDP-11/40 look-alike (the SM-4) and a Mera 400 and later ported to 16-bit microcomputers. The source code was included as an appendix to the original edition of the book, then as a floppy disk included with the revised printing, and finally is now available online in C as well as Pascal.


  • Barbara Dunin-Kęplicz and Stanisław Szpakowicz. Język programowani PROLOG (Polish). Institute of Computer Science, Polish Academy of Science, 1979. Online at
  • Feliks Kluźniak and Stanisław Szpakowicz. Prolog (Polish). Wydawnictwa Naukowo-Techniczne (Warszawa), 1983. Online at
  • Feliks Kluźniak & Stanisław Szpakowicz, with a contribution by Janusz S. Bień. Prolog for Programmers. Academic Press Inc. (London), 1985 (corrected reprint 1987), ISBN 0-12-416521-4. Online

    Chapter 7 describe the implementation of Toy Prolog, whose source was included in an Appendix in the original printing and on an included floppy disk in the 1987 reprint. Source code for C and Pascal versions of Toy Prolog are now provided on the web site.





"Németi had research contacts in Edinburgh and visited Scotland several times. From there he brought the news and some papers about a theorem prover (?) called Prolog. I was quite taken aback by the fact that there was a theorem prover that could do something useful: calculate the factorial of a number! Németi brought the Marseille interpreter as a deck of cards from Edinburgh together with a brief description of built-ins (on a line printer listing) entitled Epilog[400,400] and copies of slides of David Warren's talk entitled 'What is Prolog?'.

Porting of the Marseille Fortran interpreter to the ICL 1903A computer of NIM IGÜSZI was included into our research contract for 1975. A member of Németi's group, Péter Tóth, who was given this task, encountered unexpected problems due to the different word and character size (ICL 1900 had 24 bit words and 6 bit characters). While he was struggling with the porting, I decided to try to write my own Prolog interpreter in CDL. I actually had never had a look at the Marseille Prolog itself, I based the implementation on the last three slides of David Warren's above mentioned talk, entitled 'Example to illustrate how Prolog is implemented'. This showed three snapshots in the execution of the (naive) rev(a.b.X, a.b.X) goal. The structure of the (single) stack was quite apparent from these slides, and this, together with my earlier encounter with a structure sharing unification algorithm was enough to get me started. CDL proved to be a very convenient implementation tool, especially suited for parsing, so the tokeniser and parser were written in CDL, rather than in Prolog (as was the case for the Marseille interpreter).

I succeeded in producing a working Prolog interpreter in a few weeks, just in time for the usual yearly out of town gathering of NIM IGÜSZI software developers where Prolog was the main topic that year. The availability of a working interpreter gave a big boost to that meeting. Several people got rather excited about Prolog, including Ferenc Darvas who worked on projects for drug-industry, Iván Futó, who worked in simulation, Zsuzsa Márkusz, an architect, Miklós Szõts, a civil engineer turned computer scientist. (Both Zsuzsa Márkusz and Miklós Szõts were students of Németi.) In a few weeks after the meeting Miklós Szõts produced the very first application of the Hungarian Prolog: a program for planning of a one level workshop building using prefabricated panels. Ferenc Darvas also came back with a number of application proposals, where he believed Prolog to be of good use, such as predicting drug interactions and various other programs in drug design." [Szeredi 2004]

[Santane-Toth and Szeredi 1982] list 16 installations of this PROLOG system by 1980, and a long list of applications, beginning with drug design and architecture.

  • P. Szeredi and I. Futó. PROLOG reference (Hungarian) SZAMOLOGEP, VII. No. 3-4. pp. 5-130, 1977.
  • P. Köves. BS2000 PROLOG Users' Reference Manual. V2.4. (Hungarian) SZKI report, 1978.
  • T. Laufer. DOS PROLOG Users' Reference Manual. (Hungarian) Technical High School report, Pecs (Hungary), 1979.
  • E. Santane-Toth and P. Szeredi. PROLOG Applications in Hungary. In [Clark and Tärnlund 1982], pages 19-31, 1982.
  • Péter Szeredi. The Early Days of Prolog in Hungary - a personal account. Association for Logic Programming Newsletter, Vol 17, No. 4, November, 2004. Online at
  • C. H. A. Koster. CDL - a compiler implementation language. Proceedings of Confeence on Methods of Algorithmic Language Implementation. In Lectures Notes in Computer Science, No. 47, Springer-Verlag, 1977. Springer



"Catching the last wave of big government grants for software, the development of a new Prolog implementation was started in 1978. This implementation, later called MProlog, was based on the three stack Warren model of 1977. It was written in CDL2, a successor to CDL.

The MProlog system offered two paths for program execution. During development, the Program Development SubSystem (PDSS) provided an interactive environment for writing and testing programs. For application delivery the Production System was offered, which used the traditional translate-link-execute model.


It was written in CDL2 and in addition to interpretation proper, it served as the run-time system (i.e. memory management, etc.) for the compiled code.

MProlog extended the usual Edinburgh Prolog language in a number of respects. It had a (name based) module concept, user-controlled multi-level indexing, exception handling, a rich set of built-ins, including the undoable ones inherited from the first Hungarian Prolog. For more details on MProlog, see [Far1994]." [Szeredi 2004]

  • J. Bendl, K. Varga, M. Kosa and K. Balogh. The Specification of an Interpreter of a Modular PROLOG. (Hungarian) NIM IGUSZI report. SOFTTECH D20, SZAMKI, 1979.
  • J. Bendl, J. Boda, G. Bogdanfy, M. Kosa, L. Naszvadi and J. Visnyovszky. A Users' Documentation of the MPROLOG System. (Hungarian) NIM IGUSZI report, 1979.
  • J. Bendl, P. Köves and P. Szeredi. The MPROLOG system. In [Tärnlund 1980], pp. 201-210, 1980.
  • J. Bendl, M. Kosa and P. Szeredi. A Rough System Description of the MPROLOG Compiler for IBM like Architectures. (Hungarian) NIM IGUSZI - SZKI report, 1980.
  • Alex Bykat. An evaluation of MProlog by Logicware. SIGART Bulletin 95 (January 1986), pages 31-33. ACM Digital Library
  • Zs. Farkas, P. Köves, and P. Szeredi. MProlog: an Implementation Overview. In Evan Tick and Giancarlo Succi (editors): Implementations of Logic Programming Systems. Kluwer Academic Publishers, 1994, pages 103-117. Springer


T-Prolog, CS-Prolog, CSO-Prolog, and CSR-Prolog

Iván Futó and his group.
  • I. Futó and J. Szeredi. T-Prolog: general information manual. Institute for Co-ordination of Computer Techniques, Budapest, 1980.
  • I. Futó and J. Szeredi. T-Prolog: A Very High Level Simulation System. Logic Programming Newsletter, Issue 2 (Autumn 1981), Universidade Nova de Lisboa, pages 8-9.
  • I. Futó. Prolog with Communicating Processes: From T-Prolog to CSR-Prolog (Invited paper). In: D. S. Warren (Ed.): Logic Programming, Proceedings of the Tenth International Conference on Logic Programming, MIT Press, pages 3-17, 1993.


Imperial College London and Logic Programming Associates (LPA)



  • K. L. Clark and F. McCabe. Programmers' Guide to IC-PROLOG. CCD Report 79/7, Imperial College, University of London, 1979.
  • Keith L. Clark and Frank McCabe. The control facilities of IC-Prolog. Pages 122-149 of: [Michie 1979]. PDF
  • Steve. Gregory. Towards the compilation of annotated logic programs. Research Report DOC 80/16, Imperial College, London, 1980. PDF at PDF at via
  • Keith L. Clark, Frank G. McCabe, and Steve Gregory. IC-PROLOG - language features. Pages 253-266 of: [Clark and Tärnlund 1982]. PDF
  • Keith L. Clark and Frank G. McCabe. IC-PROLOG - aspects of its implementation. In [Clark and Tärnlund 1982].
  • Keith L. Clark and Sten-Åke Tärnlund (eds). Logic programming. London: Academic Press, 1982.


LPA micro-PROLOG, LPA Mac Prolog

  • F. G. McCabe. Micro-PROLOG programmers reference manual. Logic Programming Associates Ltd, London, 1980.
  • Keith L. Clark and Frank G. McCabe. Micro-Prolog - programming in logic. Prentice Hall, 1984.
  • K. Clark, F. G. McCabe, N. Johns, C. Spenser. LPA MacPROLOG Reference Manual. Logic Programming Associates Ltd, London, 1987.
  • Manuals and decompiled executables. Online at


Abstract Prolog Machine (APM), Sigma Machine, LPA sigma-Prolog

  • F. G. McCabe. Abstract PROLOG machine -€” a specification. DOC 83/12, Department of Computing, Imperial College, May 1983. PDF
  • F. G. McCabe. The Sigma Machine -- a Specification. Internal report, Dept. of Computing, Imperial College, 1984. Computer History Museum Lot #X5687.2010, catalog #102719303.

    "The sigma machine is the abstract machine that is at the heart of IC-Prolog ][. It was designed based on the experience we had with the Abstract Prolog Machine. If I remember correctly, before it was called IC-Prolog ][, it was called Sigma-Prolog." [Francis McCabe, personal communication, 6 September 2019]

  • F. G. McCabe, K. L. Clark, B. D. Steel, and P. D. French. sigma-PROLOG 1.0 Programmer's Reference Manual. LPA Ltd., London, 1984.

    "sigma-PROLOG ... was written in C, and aimed at mini-computers such as the DEC-10, Sun Workstation, etc., for several operating systems but eventually concentrating on Unix systems.

    Its native syntax was based on that of micro-PROLOG, but its implementation was completely different, being a compiler-based architecture rather than a pure interpreter." [Brian Steel, personal communication, 9 July 2019]


Relational Language, PARLOG, and Parallel PARLOG

"Giles Kahn, in his 1977 IFIP paper with Dave McQueen on a stream communication model of parallel programming, set me and Frank McCabe on the track of exploring coroutining and pseudo parallelism, with incremental communication via shared variables, in IC-Prolog. It was our inability to see how we might efficiently implement IC- Prolog on a multi-processor that was the motivation to find an alternative approach. Then, on a semester visit in 1980 to Syracuse University, at the invitation of Alan Robinson, Steve Gregory and I decided to look at Hoare's CSP for inspiration. The concept of guards and committed choice non-determinism of that language (an idea previously proposed by Dijkstra for his guarded command language) seemed to us just the concept needed to allow efficient implementation of and-parallelism with stream communication in a logic programming language. This lead to the so called Relational Language, which merged the committed choice, communication only on committment, concept of CSP with the equally elegant stream communication model of Kahn and McQueen.

Because of our early work on concurrent LP languages, Steve Gregory and I were invited to ICOT in 1983. (I was pleased to hear in his Monday conference presentation, that Koichi Furukawa had read with interest our 1981 paper on the Relational Language and, even before the start of the FGCS project, had considered using a concurrent logic language rather than an or-parallel Prolog as the PIM kernel language.) Our 1983 visit coincided with the second ICOT visit of Ehud Shapiro, the originator of Concurrent Prolog, which was based on but significantly extended the Relational Language. I believe that between the three of us, we helped convince Koichi Furukawa and his colleagues that adopting a concurrent LP language as the PIM kernel language was a sound approach. During that visit Steve Gregory and I crystalized our views on the essential features of Parlog, our successor to the Relational Language." [Clark 1992]

"After 1984, the languages had stabilized and implementation efforts started in earnest. The size of the Parlog group (which was previously 1-2) increased and ICOT expanded even further. Some excellent, seriously usable, implementations of both Parlog and GHC were developed, especially Jim Crammond's Parallel Parlog system and ICOT's KLIC. Ironically, by the time that these implementations became available, there were few people to use them: interest in concurrent logic programming, and FGCS technology in general, had already started to fade." [Gregory 2007]

  • Keith L. Clark and Steve Gregory. A relational language for parallel programming. Proceedings of the 1981 conference on Functional programming languages and computer architecture, p. 171-178, October 18-22, 1981, Portsmouth, New Hampshire, United States. ACM Digital Library
  • K. L. Clark and S. Gregory. PARLOG: A parallel logic programming language. Res. rep. DOC 83/5, Dept. of Computing, Imperial College, London, May 1983. PDF at via
  • K. L. Clark and S. Gregory. Notes on systems programming in PARLOG. In Proceedings of the International Conference on Fifth Generation Computer Systems 1984, ICOT, pages 299-306. PDF at
  • K. L. Clark and S. Gregory. Notes on the implementation of PARLOG. J. Logic Program. 2, 1 (Apr. 1985), pages 17-42. ScienceDirect (open access)
  • Steven Gregory. Design, application and implementation of a paralled logic programming language. Ph.D. thesis, Department of Computing, Imperial College of Science and Technology, September 1985. Online at
  • Keith Clark and Steve Gregory. PARLOG: parallel programming in logic. ACM Trans. Program. Lang. Syst. 8, 1 (January 1986), pages 1-49. ACM Digital Library
  • I. Foster, S. Gregory, G. Ringwood, and K. Satoh. A Sequential Implementation of PARLOG. 3rd International Conference on Logic Programming, London, July 1986. SpringerLink
  • Keith L. Clark. PARLOG: the language and its applications. Pages 30-53 of: J. W. de Bakker, A. J. Nijman, and Philip C. Treleaven (eds). Proceedings of the conference on parallel architectures and languages europe (PARLE). Volume II: Parallel languages. Lecture Notes in Computer Science, vol. 259. Eindhoven, The Netherlands: Springer Verlag, 1987.
  • Ian Foster and Steve Gregory. Parallel Logic Programming Languages. Imperial College London. Undated slides; probably presented as tutorial at: Fourth IEEE Symposium on Logic Programming, San Francisco, August 31-September 4, 1987. Scan courtesy of Tim Lindholm; posted by permission of Foster and Gregory. PDF
  • David Gilbert. PARLOG: a tutorial introduction, Current trends in Parallel Processing and Supercomputing, organised by the Belgian Institute for Automatic Control. November 19-20, Antwerp, 1987. .ps.gz at
  • S. Gregory. Parallel Logic Programming in PARLOG: The Language and its Implementation, Addison-Wesley, 1987.
  • Ian Foster. Parlog As A System Programming Language. Ph.D. thesis, Research Report PAR 88/5, Department of Computing, Imperial College of Science and Technology, University of London, March 1988. PDF at
  • T. Conlon and S. Gregory. Hands on MacParlog 1.0. Parallel Logic Programming Limited, London, January 1989.
  • Windows Parlog. Parallel Logic Programming Ltd. (dissolved in October 2015). Online at

Parallel PARLOG

  • Jim A. Crammond. Scheduling and Variable Assignment in the Parallel PARLOG Implementation. In Logic Programming, Proceedings of the 1990 North American Conference, Austin, Texas, USA, October 29 - November 1, 1990, pages 642-657, 1990.
  • Jim A. Crammond. The Abstract Machine and Implementation of Parallel Parlog. New Generation Computing, Vol. 10, No. 4, pages 385-422, 1992. SpringerLink
  • Parlog Group. The Parallel Parlog User Manual V1.5.9. Department of Computing, Imperial College, London, 9 October 1989, revised 28 September 1993. PDF
  • Source code: see IC Prolog ][ below.

History of PARLOG

  • Steve Gregory. Concurrent Logic Programming before ICOT: A Personal Perspective. The ALP Newsletter, Vol. 20, No. 3/4, December 2007. Online at PDF


Logic and Objects

  • Francis Gregory McCabe. Logic and objects : language, application and implementation. Ph.D. thesis, Department of Computing, Imperial College of Science and Technology, April 17, 1989. Online at
  • Francis G. McCabe. Logic and Objects. Prentice Hall International, 1992.
  • Logic and Objects for MacProlog. Source code and documentatation. Requires LPA MacProlog 4.0 (running on Classic Mac OS). CMU AI Repository
  • Source code: see IC Prolog ][ below.
  • Zacharias Bobolakis. L&O on IC PROLOG ][ User's Guide DRAFT. Undated, but circa 1993. PDF


IC Prolog ][

"IC-Prolog ][ (ICP) is a multi-threaded Prolog system developed at Imperial College. Multiple threads allow queries to be executed concurrently. ICP also has an interface to Unix TCP/IP system calls and "mailboxes", a high level communication system. This interface together with multiple threads enables distributed applications (such as client/server systems) to be written in Prolog.

The package also includes a preprocessor for the Logic & Objects (L&O) object-oriented extension to Prolog. This gives a powerful structuring mechanism for Prolog programs as well as providing a logical interpretation of inheritance and other object-oriented features. (The sources for the L&O extension is also available to LPA MacProlog users in the subdirectory 'lo'.)

Parlog has been integrated with IC-Prolog ][ as a separate thread, so applications may be written in either language depending on which is more suitable. (Standalone versions of the Parlog system for Sun-3 and Sun-4 can be found in the parlog/ directory.)

The package also includes a simple expert system shell called Skilaki." [Chu et al. 1993]

  • See [McCabe 1984a].
  • Damian Chu. I.C. Prolog II: a Multithreaded Prolog System. Undated draft included in [Chu et al. 1993]. PDF
  • Damian Chu. I.C. Prolog II: a Language for Implementing Multi-Agent systems. Published in the Proceedings of the Special Interest Group on Cooperating Knowledge Based Systems, Keele, September 1992, and included in [Chu et al. 1993]. PDF
  • Yannis Cosmadopoulos and Damian Chu. IC Prolog II Reference Manual. Technical Report, Logic Programming Section, Department of Computing, Imperial College, Version 0.96, September 28, 1993. PDF HTML at via
  • Michael Lawley, Zacharias Bobolakis, and Yannis Cosmadopoulos. IC Prolog ][ and L&O. ALP Newsletter, Vol. 6, No. 1, February 1993. Online at
  • Chu et al. IC Prolog ][, Parallel Parlog, and Logic&Objects, version 0.96 for SUN 3 and SUN 4 (source, executables, documentation, examples), 1993. Provided by Frank G. McCabe. .zip archive


Universidade Nova de Lisboa


Logic Programming Newsletter



  • Luís Moniz Pereira, António Porto, Luís Monteiro, and Miguel Figueiras, editors. 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.
  • 2nd International Workshop on Non-Monotonic Reasoning. Lisbon, Portugal, June 28-30, 1993. Poster. PDF



  • 6th International Conference on Logic Programming. Lisbon, Portugal, 19-23 June 1989. Poster. PDF


Intelligent backtracking and logic control

  • Luís Moniz Pereira and António Porto. Intelligent backtracking and sidetracking in Horn clause programs - the theory. Report 2/79, Departmento de Informática, Universidade Nova de Lisboa, October 1979. Published in [Tärnlund 1980]. PDF at
  • Luís Moniz Pereira and António Porto. Intelligent backtracking and sidetracking in Horn clause programs - the implementation. Report 13/79, Departmento de Informática, Universidade Nova de Lisboa, December 1979. Published in [Tärnlund 1980]. PDF at

    Prolog source code: Appendix 1 is the intelligent backtracking interpreter; Appendix 2 is the specialized database interpreter; Appendix 3 is a database example; Appendix 4 is the sidetracking interpreter.

  • Luís Moniz Pereira and António Porto. An interpreter of logic programs using selective backtracking. Report 3/80, Departmento de Informática, Universidade Nova de Lisboa, July 1980. Published in [Tärnlund 1980]. PDF at
    Prolog source code: Appendix 1 is the selective backtracking interpreter; Appendix 2 is the specialized database interpreter; Appendix 3 is an additional module for the database example.
  • Luís Moniz Pereira and António Porto. Selective backtracking for logic programs. In Proceedings of the Fifth International Conference on Automated Deduction (CADE'80), pp. 306-317, Springer, 1980. PDF at
  • Luís Moniz Pereira and António Porto. Selective backtracking. In [Clark and 1982], pages 107-114.
  • L. M. Pereira. Logic Control with Logic. In Proceedings of the 1st. Conference on Logic Programming (ICLP'82), pp. 9-18, Marseilles, September 1982. Extended version published in [Campbell 1984], pp. 177-193. PDF at
  • See [Bruynooghe and Pereira, 1984].
  • L. M. Pereira and A. Porto. A Prolog Implementation of a Large System on a Small Machine. In [van Caneghem and Warren 1986], pages 152-160. PDF at
    Describes a natural language question-answering system implemented using a slightly modified version of Edinburgh PDP-11 Prolog for RT-11.
  • Luís Moniz Pereira. Rational Logic Programming Debugging. In: Proceedings of the 3rd Intl.Conf. on Logic Programming (ICLP'86), E.Shapiro (ed.), London, Springer LCNS 225, 1986. .ps.gz at


Source code

  • Luís Moniz Pereira and António Porto. Prolog source code accompanying Intelligent Backtracking papers: Selective backtracking interpreter (three versions); Intelligent Backtracking DataBase interpreter. .zip archive at
  • See also [Pereira 1982] above for detailed Prolog code to implement interpreters allowing various control regimes.
  • Luís Moniz Pereira. Prolog source code implementing Rational Logic Programming Debugging. (See [L. M. Pereira 1986].) .zip archive at


Distributed Logic

  • Luís Fernando Lopes Monteiro. Uma lógica para processos distribuídos. Ph.D. thesis,  Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa, 1983.
  • L. Monteiro. A proposal for distributed programming in logic. In [Campbell 1984], pages 329-340.
  • L. Monteiro. Distributed logic: a theory of distributed programming in logic. UNL, Computer Science Department, 1986.


Delta Prolog

"I developed Delta Prolog during a 3 month sabbatical at DEC in Marlborough, MA, 1983-84. Subsequently it gave rise to a number of papers developing it and a PhD thesis on distributed backtracking." [Luís Moniz Pereira, personal communication, 8 September 2019]

  • Luís Moniz Pereira and Roger Nasr. Delta Prolog: a distributed logic programming language. In Proceedings of the International Conference on Fifth Generation Computer Systems 1984, ICOT, November 1984. PDF at
  • Luís Moniz Pereira, Luís Monteiro, José Cunha, and Joaquim N. Aparício. Delta Prolog: A Distributed Backtracking Extension with Events. In: Procs. of the 3rd International Conference on Logic Programming (ICLP'86), pp. 69-83, E.Shapiro (ed.), London, Springer LCNS 225, 1986. PDF at
  • J. C. Cunha. Execução Concorrente de uma Linguagem de Programação em Lógica [Concurrent execution of a logic programming language] (in Portuguese). Doctoral dissertation, Dept. de Informática, Universidade Nova de Lisboa, September 1988.
  • L. M. Pereira, L. Monteiro, J. C. Cunha, and J. N. Aparício. Concurrency and communication in Delta-Prolog. Invited paper in: IEEE International Specialist Seminar: the design and application of parallel digital processors, pp. 94-104, 1988. PDF at
  • J. C. Cunha, M. C. Ferreira, and L. M. Pereira. Programming in Delta Prolog. In: Proceedings of the 6th International Conference on Logic Programming (ICLP'89), G. Levi, M. Martelli (eds.), MIT Press, Lisbon, Portugal, 1989. PDF at
  • J. C. Cunha, P. Medeiros, and L. M. Pereira. A distributed logic programming language and its implementation on transputer networks. In: Proceedings of Conf. OUG-12 (Occam User's Group), pp. 85-96, S. J. Turner (ed.), IOS Press, Amsterdam, 1990. PDF at
  • J. C. Cunha, P. Medeiros, M. B. Carvalhosa, and L. M. Pereira. Paralogism Progress Report. In: 3rd Esprit Parallel Computing Action Workshops, Bonn, Germany, 1991. .doc.gz at
  • José C. Cunha, P. Medeiros, M. Carvalhosa, and L. M. Pereira. Delta Prolog: a Distributed Logic Language and Its Implementation on Distributed-Memory Multiprocessors. In Implementations of Distributed Prolog, P. Kacsuk and M. Wise (Editors), John Wiley & Sons, ISBN 0-471-93116-0, pp 335-356, 1992.


Syracuse University



"I first encountered Lisp when John McCarthy rang my doorbell the day after we moved into a house in Menlo Park in the summer of 1965. I had published the Resolution paper a few months earlier and McCarthy had (in 2 hours!) written and run a Lisp program embodying the proof procedure, with, he said, minimal debugging. This seemed a miracle to me, who had for years been flailing about, first with assembly languages and then with Fortran. The gruff McCarthy, who was by then already well known, was also something of an astonishing revelation, but that is another story. I bought a copy of the Lisp 1.5 manual, and found it brilliant but with strangely clumsy but MIT-ishly bold and naïve blunders (involving QUOTE and functions as objects, FUNARGS and all that, eventually fixed years later in SCHEME but still there in Common Lisp)." [Interview with Alan Robinson, inventor of resolution logic, van Emden 2010]

"Some of the visitors [to Edinburgh in 1974] were not swept up in the anti-theorem proving campaign emanating from MIT. They believed that there was a lot of valuable potential in resolution theorem-proving. But when these people heard that we actually wanted to program in logic rather than in Lisp, the atmosphere would turn chilly. A prime example was Robinson himself. We thought he would be delighted to see resolution used to turn logic into an actual programming language complete with a beautiful fixpoint theory. He was not. His first and only love in programming was Lisp. Mechanize theorem-proving, by all means. But do it in Lisp. Later, Robinson was to give valuable support to logic programming in many ways, such as the founding of the [Journal of Logic Programming]. He was in favour of research in logic programming. But for him, programming was something you do in Lisp." [van Emden 2006]

"Our own early attempts (as devoted users of LISP) to use PROLOG convinced us that it would be worth the effort to create within LISP a faithful implementation of Kowalski's logic programming idea. We felt it would be very convenient to be able to set up a knowledge base of assertions inside a LISP workspace, and to compute the answers to queries simply by executing appropriate function calls. What seemed to be required was an extension of LISP consisting of a group of new primitives designed to support unification, LUSH resolution, and so on, as efficiently as possible. We set out to honor the principle of the separation of logic from control (no CUT, no preferred ordering of assertions within procedures nor of atomic sentences within hypotheses of assertions) by making the logic programming engine 'purely denotative'. Instead of the PROLOG method of generating the LUSH resolution proof tree one branch at a time by backtracking, we decided to generate all branches in quasi-parallel so that heuristic control techniques could be brought to bear on deciding which branch to develop at each step and so that our design would lend itself to multiprocessing at a later stage." [Robinson and Sibert 1982]

  • J. A. Robinson and E. E. Sibert. Logic Programming in LISP. Technical Report 8-80, E. E. School of Computer and Information Science, Syracuse University, November 1980. Also in Rome Air Deveopment Center Technical Report RADC 80-379, volume 1, 1980. Online at
  • J. A. Robinson and E. E. Sibert. LOGLISP Implementation Notes. Technical Report, School of Computer and Information Science, Syracuse University, December 1981.
  • J. A. Robinson and E. E. Sibert. The LOGLISP User's Manual. Describes version V2M3 of LOGLISP, December 1981. Accesion number 102720431, Herbert Stoyan collection on LISP programming, Computer History Museum. PDF
  • J. A. Robinson and E. E. Sibert. LOGLISP: an alternative to PROLOG. In: J.E. Hayes, Donald Michie, and Y-H. Pao, editors, Machine_Intelligence 10, Ellis Horwood Ltd., Chicester, England, 1982. Online at
  • J. A. Robinson and E. E. Sibert. LOGLISP: Motivation, design and implementation. In: [Clark and Tärnlund 1982], pages 299-313, 1982.
  • Robert C. Schrag. Notes on the Conversion of LogLisp from Rutgers/UCI-LISP to Interlisp. Rome Air Development Center, Final Technical Report RADC-TM-83-1, January 1983. PDF at
  • J. A. Robinson and E. E. Sibert. LOGLISP Implementation Notes. Technical Report, Logic Programming Research Group, Syracuse University, February, 1984.
  • Robert C. Schrag. Lisp Implementation Baseline Investigation. Rome Air Development Center, In House Report RADC-TR-84-151, June 1984. Online at
  • Robert C. Schrag. LogLisp Sequential Forms with Resolution Semantics. Rome Air Development Center, Final Technical Report RADC-TM-84-13, July 1984. Online at
  • Robert C. Schrag. Compilation and Environment Optimizations for LogLisp. Rome Air Development Center, Final Technical Report RADC-TM-84-14, July 1984. Online
  • J. A. Robinson, E. E. Sibert and K. J. Greene. The LOGLISP Programming System. Rome Air Development Center, Final Technical Report RADC-TR-85-89, May 1985. Online at
  • Sanjai Narain. Mycin: Implementing the Expert System in Loglisp. IEEE Software, Volume 2, Issue 3, May 1985. IEEE Xplore
  • James Carciofini, George Hadden, Timothy Colburn, and Aaron Larson. LOGLISP Programming System Users Manual. Final Technical Report, Honeywell Systems and Research Center, November 1987. Online at
  • J. A. Robinson. Beyond LOGLISP: combining functional and relational programming in a reduction setting. In: J. E. Hayes, Donald Michie, and J. Richards, editors. Machine Intelligence 11, Clarendon Press, 1988.
  • Maarten van Emden, interviewer. Interview with Alan Robinson, inventor of resolution logic. A Programmer's Place Blog, June 8, 2010. Online at


Syracuse/Argonne Prolog

"In the early 1980's, Kenneth Bowen and the Logic Programming Research Group at Syracuse University (Hamid Bacha, Kevin Buettner, Ilyas Cicekli, Keith Hughes, and Andrew Turk) were exploring meta-level extensions toLogic Programming systems, and to Prolog in particular. Desiring a Prolog implementation on which to experiment, they worked co-operatively with a group at Argonne National Laboratories (Tim Lindholm, Rusty Lusk, and Ross Overbeek), and initially developed a Prolog byte-code interpreter running on a Data General MV/8000, and later on a VAX 780. They found the system performance disappointing, and in late 1984, set out to develop a portable compiler-based system utilizing a byte-code interpreter for D. Warren's WAM design, implemented over C.

This came on line by fall, 1985. It contained a resident incremental compiler (from Prolog to WAM), and supported a module system, garbage compaction, and implemented assert/retract using on-the-fly compilation and decompilation techniques, the latter also utilized in a four-port debugger. The system performance was markedly better than the original byte-code interpreter. It was used as the starting point for two versions of a meta-prolog extension. ..." [See ALS Prolog below.] [Kenneth Bowen, personal communication, 11 June 2019]

  • Kenneth A. Bowen. Prolog. Proceedings of the 1979 annual conference (ACM '79), Arvid L. Martin and James L. Elshoff (Eds.). ACM, New York, NY, USA, 14-23. ACM Digital Library
  • Kenneth A. Bowen and Tobias Weinberg. A Meta-Level Extension of Prolog. Proceedings of the 1985 Symposium on Logic Programming, Boston, Massachusetts, USA, July 15-18, 1985, pages 48-53. Also: University of Syracuse, Electrical Engineering and Computer Science Technical Report 36. Online at
  • Kenneth A. Bowen, Kevin A. Buettner, Ilyas Cicekli, and Andrew Turk. The Design and Implementation of a High-Speed Incremental Portable Prolog Compiler. Proceedings of Third International Conference on Logic Programming, Imperial College of Science and Technology, London, United Kingdom, July 14-18, 1986, pages 650-656, SpringerLink. Also Technical Report. 35, Electrical Engineering and Computer Science, Syracuse University, 1985. Online at


Sussex University


Poplog Prolog

"During 1982, Chris Mellish and Steve Hardy devised a model for implementing Prolog, using Pop-11 closures to represent Prolog continuations, and Chris implemented a Prolog in Pop-11, while he was learning Pop-11. It worked, but was somewhat slow compared with high performance Prolog systems.

One reason for comparative slowness was that we decided that it was particularly useful to enable Prolog to share data-structures with Pop-11. This meant that it was not always possible to infer that because a Prolog program could no longer access some structures they were inaccessible. They might still be accessible if they had been handed to a Pop-11 program and stored somewhere for later use. This meant that structures that could be allocated using a stack in a stand-alone Prolog, had to be on a garbage collectable heap in Poplog. The use of garbage collections could slow things down, though the more memory was available the less this mattered, since having more memory reduced the frequency of garbage collections.

There were other inefficiencies in the original implementation, which led John Gibson to extend the Pop-11 virtual machine to provide additional mechanisms specifically to support Prolog. For example, instead of Prolog continuations being Pop-11 closures allocated on the heap (and therefore requiring garbage collections), they were allocated on a special stack reserved for Prolog continuations. Additional changes were made to speed up backtracking and unification.

It was as a result of such changes for Prolog that we started referring to the Poplog virtual machine rather than the Pop-11 virtual machine." [Sloman 1989]

Source code


Papers and implementation documentation

  • Chris Mellish and Steve Hardy. Integrating Prolog into the POPLOG environment. Proceedings of the Eighth International Joint Conference on Artificial Intelligence, Vol. 1, 1983. PDF at
    A slightly expanded version of this paper appears as Chapter 25 of Robin Popplestone's unfinished book. Chapter 26 of the book is a description of those datatypes and procedures built into POPLOG which are intended for the support of Prolog. Online at
  • C.S. Mellish. Some Global Optimizations for a PROLOG Compiler. Journal of Logic Programming, Volume 2 (1985), pp. 43-66. ScienceDirect (open access)
  • Aaron Sloman. The Evolution of POPLOG and Pop-11 at Sussex University. In: POP-11 Comes of Age: The Advancement of an AI Programming Language, Ed. J. A.D.W.Anderson, Ellis Horwood, pp 30-54, 1989. PDF and HTML at
  • R. Smith, A. Sloman and J. Gibson. POPLOG's two-level virtual machine support for interactive languages, In: D. Sleeman and N. Bernsen, editors. Research Directions in Cognitive Science Volume 5: Artificial Intelligence, Lawrence Erlbaum Associates, 1992, pages 203-231. Online at


SRI International and Stanford University

  • David H. D. Warren. A View Of The Fifth Generation and Its Impact.
  • See also [Pereira 1982].
  • Fernando C. N. Pereira. Can Drawing Be Liberated From The Von Neumann Style?, Technical Note 282. AI Center, SRI International, June 1983. Online at
  • David H. D. Warren Applied Logic--Its Use and Implementation As A Programming Tool, Technical Note 290. AI Center, SRI International, June 1983. Online at
  • Fernando C. N. Pereira and David H. D. Warren. Parsing As Deduction, Technical Note 295. AI Center, SRI International, June 1983. Online at


Warren Abstract Machine

  • David H. D. Warren. An Abstract Prolog Instruction Set. Technical Note 309, Artificial Intelligence Center, Computer Science and Technology Division, SRI International, October 1983. Online at
  • Evan Tick. An Overlapped Prolog Processor. Technical Note 308. AI Center, SRI International, October 1983. Online at
  • Evan Tick and David H. D. Warren. Towards a Pipelined Prolog Processor. New Generation Computing, Vol. 2, pages 323-345, 1984. Online at
  • E. Tick. Towards a Multiple Pipeline Prolog Processor. International Workshop on High-Level Computer Architecture, The University of Maryland, May 1984.
  • Evan Tick. 1984. Sequential Prolog machine: Image and host architectures. In Proceedings of the 17th annual workshop on Microprogramming (MICRO 17). IEEE Press, Piscataway, NJ, USA, 204-216. ACM Digital Library

About the WAM

  • John Gabriel, Tim Lindholm, E. L. Lusk, and R. A. Overbeek. A Tutorial on the Warren Abstract machine for Computational Logic. ANL-84-84, Mathematics and Computer Science Division, Argonne National Laboratory, June 1985. PDF
  • Hassan Aït-Kaci. Warren’s Abstract Machine: A Tutorial Reconstruction. MIT Press, 1991. Online at


Prolog technology theorem prover


Quintus Computer Systems, Inc.

Quintus Computer Systems was founded in February 1984 by David H. D. Warren, William Kornfeld, Lawrence Byrd, Fernando Pereira and Cuthbert Hurd, with the goal of selling a high-performance Prolog system for the emerging 32-bit processors (e.g., VAX, Motorola 68000, etc.) based on the Warren Abstract Machine.

Release 1.0 of Quintus Prolog was shipped in January 1985. Release 2.0 was shipped in 1987(???). Quintus was acquired by Intergraph Corporation in October 1989. Release 3.1 was shipped in February 1991.

In 1996 Quintus had refocussed on call center software called CustomerQ (written in Quintus Prolog). Quintus Prolog was sold to AI International Ltd. of Berkhamsted, UK. AI International later sold Quintus Prolog to the Swedish Institute of Computer Science (SICS), who continue to sell and support Release 3.5.

  • Patti Kahn et al. Quintus Prolog User's Guide. Release 1.0, 1985. Scan courtesy of Bart Demoen and Maurice Bruynooghe. PDF
  • David Bowen et al. Quintus Prolog Reference Manual. Release 1.0, 1985. Scan courtesy of Bart Demoen and Maurice Bruynooghe. PDF
  • Cuthbert C. Hurd Papers (CBI 95), Charles Babbage Institute, University of Minnesota, Minneapolis. Accessed November 19, 2019.

    "The collection contains correspondence, memoranda, and reports relating to Cuthbert Hurd's work with the Applied Science Department at IBM and minutes, memoranda, reports, and notes related to his chairmanship of Quintus Computer Systems. ... The Quintus records include business plans, agreements, stock and financial records, news releases, papers on the Prolog language, product planning and specifications memoranda, and board minutes."

  • Intelligent Systems Laboratory. Quintus Prolog User’s Manual. Release 3.5, Swedish Institute of Computer Science, December 2003. PDF at


University of Melbourne



MU-Prolog stands for Melbourne University Prolog.

"MU-Prolog is a structure-sharing interpreter. The original version (1.0) was written by John Lloyd in Pascal. Version 2.0 was written by Naish and completed in 1982." [Van Roy 1994]

"MU-Prolog (version 1) had a very short lifespan, no more than one year from beginning to end. Its only purpose was to actually run some programs to understand how Prolog worked. (I couldn't find a Prolog system that would run on the computers available to me at the time.) It was abandoned when Lee Naish began his PhD and soon built a completely new implementation that became widely used." [John Lloyd, personal communication, 7 November 2019]

"[The original version] doesn't really bear any relationship with v2.0 and later except for the name and was very slow (there was a misunderstanding of how Prolog implementations used structure sharing I think;  something along those lines anyway)." [Lee Naish, personal communication, 5 September 2019]

"MU-Prolog was implemented in the early 1980's. Its an interpreter written in C and was ported to many UNIX systems over the years. It is now more or less obsolete but may be of historical interest. It ran at about 1.5K LIPS on a VAX (remember them?), compared to about 2K LIPS for CProlog, which used similar implementation technology - a structure sharing interpreter.

In its day it was quite an innovative system.

  • It was the first system with flexible and easy to use facilities for coroutining without a major efficiency penalty. Wait declarations allow programmers to specify when calls to procedures should proceed or delay based on how instantiated they are. A tool was implemented to automatically generate these declarations and reorder code to improve termination and efficiency in many cases.
  • It had the best facilities for soundly implemented negation and the first "pure" all solutions predicate. Negated and conditional goals delay until they are ground and an inequality predicate supporting (implicit) universal quantification is supported.
  • It was one of the first Prolog systems which was connected to database systems. Provided with the system is code to implement disk-resident relations supporting partial match retrieval. It was used for one of the very early deductive database systems.
  • It was one of the first Prolog systems with a form of module system.
  • It was the first Prolog system to use "executable" saved states and many other UNIX-friendly features.
  • It was one of the first Prolog systems to support dynamic loading and linking of object files from C and other languages.

It was used as a vehicle for experimenting with many aspects of language design, implementation, program transformation, deductive databases and debugging. After the invention of the Warren Abstract Machine the time was right to move on. Development of MU-Prolog was stopped in the mid 1980's when NU-Prolog, a compiled Prolog system, was designed and implemented.

The most complete reference for MU-Prolog is my thesis." [Naish 1996]

  • J. W. Lloyd. MU-PROLOG Version 1 User Manual. University of Melbourne, March 1981. PDF
  • Lee Naish. An Introduction to MU-PROLOG. Technical Report 82/2, Department of Computer Science, University of Melbourne, Melbourne, Australia, March 1982 (revised July 1983). Scan courtesy of Bart Demoen and Maurice Bruynooghe. PDF
  • Lee Naish. MU-PROLOG 3.0 Reference Manual. Melbourne University, July 1983. Scan courtesy of Bart Demoen and Maurice Bruynooghe. PDF
  • Lee Naish. MU-Prolog implementation. Includes source code for version 3.2db from 1985. Web page, May 1996. Online at
  • Lee Naish. Negation and control in Prolog. PhD Thesis. Technical report 85/12, Department of Computer Science, University of Melbourne. Published in Lecture Notes in Computer Science Number 238, Springer-Verlag, 1986. Springer
  • Peter Van Roy. 1983-1993: The Wonder Years of Sequential Prolog Implementation.
    • Research Report PRL-RR-36, Paris Research Laboratory, Digital Equipment Corporation, December 1993. Online at
    • The Journal of Logic Programming, Volumes 19-20, Supplement 1, May-July 1994, Pages 385-441. ScienceDirect open access



"NU-Prolog is a WAM-based emulator written in C primarily by Jeff Schultz and completed in 1985. It is interesting for its pioneering implementation of logical negation, quantifiers, if-then-else, and inequality, through extensions to the WAM. The delay declarations ("when" declarations) are compiled into decision trees with multiple entry points. This avoids repeating already performed tests on resumption. It results in indexing on multiple arguments in practice. NU-Prolog was the basis for many implementation experiments, e.g., related to parallelism, databases, and programming environments." [Van Roy 1994]

  • Lee Naish. Negation and Quantifiers in NU-Prolog. In 3rd ICLP, Lectures Notes in Computer Science 225, Springer, New York, 1986, pp. 624-634.
  • Lee Naish. Parallelizing NU-Prolog. In: 5th ICSLP, MIT Press, Cambridge, MA, 1988, pp. 1546-1564. Also published as Technical Report 87/17, Department of Computer Science, University of Melbourne.
  • Lee Naish, P. W. Dart, and J. Zobel. The NU-Prolog Debugging Environment. In: 6th ICLP, MIT Press, Cambridge, MA, 1989, pp. 521-536. Online at
  • James A. Thom and Justin Zobel, editors. NU-Prolog Reference Manual, Version 1.5.24. Technical Report 86/10, Machine Intelligence Project, Department of Computer Science, University of Melbourne. Revised November 1990. PDF at
  • Lee Naish. NU-Prolog implementation. Includes source code for versions 1.6.5 and 1.6.9 from 1994. Web page, 1995. Online at
More logic programming software by Lee Naish:


University of Uppsala

See also this list of early Computer Science Department reports.

UPMAIL stands for Uppsala Programming Methodology and Artificial Intelligence Laboratory.



  • Martin Nilsson. FOOLOG--A Small and Efficient Prolog Interpreter. Report 20, June 1983.
  • Martin Nilsson. FOOLOG Prolog. AIList Digest, Volume 1, Issue 47, 24 Aug 1983. Reprinted from the PROLOG Digest by Ken%MIT-OZ%MIT-MC [Kenneth Kahn]. Includes sample run and source code. AI.V1[BB,DOC] at
  • M. Nilsson. The world's shortest Prolog interpreter? Pages 87-92 in [Campbell 1984].


YAQ (Yet Another QLOG)

Source code

Papers about YAQ

  • M. Carlsson. (Re)Implementing PROLOG in LISP or YAQ - Yet another QLOG. UPMAIL 81/1, Box 2059, S-75002, Uppsala, Sweden, 1981.
  • T. Risch. A Data Base Extension of Prolog and its Implementation. UPMAIL, Dept. of Computer Science, Uppsala University, Sweden, 1982. PDF at



"LM-Prolog is an implementation of Prolog for the MIT family of Lisp Machines. The Prolog dialect differs quite a bit from the Edinburgh Prolog family of dialects both in terms of syntax and built-in predicates. The bulk of the code was written in 1983, when the authors were at Uppsala University. The work was supported by the Swedish National Board for Technical Development (STU).

Ken Kahn wrote two precursors to the present implementation, one in Pure Lisp and one based on flavors and message passing and implemented libraries of built-in predicates and demo programs. The present implementation compiles Prolog predicates to Lisp functions, using success continuations to emulate the Prolog control structure. Mats Carlsson implemented the compiler and runtime support including microcode extensions for LMI CADRs and Lambdas." [Ken Kahn and Mats Carlsson, README, 1989]

Source code


  • Kenneth M. Kahn. A Grammar Kit in Prolog.
    • In New Horizons in Educational Computing, edited by M. Yazdani, Ellis Horwood Ltd., Chichester, U.K., 1983.
    • In Proc. AISB Easter Conference on Artificial Intelligence and Education, April 1983.
    • UPMAIL Technical Report 14C, Uppsala, revised February 2, 1985 by Mats Carlsson. PDF
  • Kenneth M. Kahn. Unique Features of LISP Machine Prolog. UPMAIL Technical Report 14, 1983 and Report 15B, revised February 1985 by Mats Carlsson. PDF
  • K. M. Kahn. A Primitive for the Control of Logic Programs. Proc. 1984 Symposium on Logic Programming, Atlantic City, and UPMAIL Technical Report 16, February 1983.
  • Mats Carlsson and Ken Kahn. LM-Prolog user manual. Technical Report 24, UPMAIL, Uppsala University, November 1983.
  • Mats Carlsson. LM-Prolog - The Language and its Implementation. Thesis for Licentiat of Philosophy in Computer Science at Uppsala University. UPMAIL Technical Report 30, October 1984. PDF
  • Kenneth M. Kahn and Mats Carlsson. The Compilation of Prolog Programs without the Use of a Prolog Compiler. Proceedings of the International Conference on Fifth Generation Computer Systems 1984, ICOT. PDF at
  • Mats Carlsson. On implementing Prolog in functional programming.
    • UPMAIL Technical Report 5, Uppsala, revised December 8, 1983. PDF
    • New Generation Computing, December 1984, Volume 2, Issue 4, pages 347-359. SpringerLink
  • K. M. Kahn and M. Carlsson. How to implement Prolog on a LISP Machine. Pages 117-134 in [Campbell 1984].
  • Kenneth M. Kahn. Partial Evaluation, Programming Methodology, and Artificial Intelligence. AI Magazine, Volume 5, Number 1, 1984, pages 53-57. Online at
  • M. Carlsson. A microcoded unifier for Lisp machine Prolog. In IEEE Proceedings 1985 Symposium on Logic Programming (Boston, July 1985), IEEE, New York, 1985, 162-171.



  • Executables for Tricia 0.9b and 0.95, for Macintosh Classic OS. CMU AI Repository
    "Credits to: Jonas Barklund, Monika Danielsson, Jan Gabrielsson, Per Mildner, Per-Eric Olsson and Jan Wÿnsche. The compiler was kindly contributed by Mats Carlsson. The editor and top level was contributed by e (a.k.a. Doug Currie)."

Papers about Tricia

  • J. Barklund, L. Oestreicher, Å. Hugosson, M. Nylén. Tricia User's Guide, Computing Science Department, Uppsala University, Sept. 1986.
  • J. Barklund, H. Millroth. Garbage Cut for Garbage Collection of Iterative Prolog Programs. 1986 Symposium on Logic Programming, Salt Lake City, Sept. 1986.
  • Mats Carlsson. Compilation for Tricia and Its Abstract Machine, UPMAIL Technical Report 35, Uppsala, Sept. 1986. PDF
  • J. Barklund, H. Millroth. Code Generation and Runtime System for Tricia. UPMAIL Technical Report 36, Uppsala, in preparation.
  • J. Barklund. Efficient interpretation of Prolog programs. Proceedings of the Symposium on Interpreters and Interpretive Techniques (SIGPLAN '87), Richard L. Wexelblat (Ed.). SIGPLAN Notices 22, 7 (July 1987), 132-137. ACM Digital Library
  • Jonas Barklund. Efficient Interpretation of Prolog Programs. Report 39, April 1987. Expanded version of previous paper. (PDF at
  • Jonas Barklund and Håkan Millroth. Integrating Complex Data Structures in Prolog. UPMAIL Technical Report 42, Uppsala, October 1987. (PDF at


Nova Prolog

  • Jonas Barklund and Håkan Millroth. Nova Prolog. UPMAIL Technical Report 52, Uppsala, July 1988.


Reform Prolog

"Reform Prolog is an (dependent) AND-parallel system based on recursion parallelism and Reform compilation. The system supports selective, userdeclared, parallelization of binding-deterministic Prolog programs (nondeterminism local to each parallel process is allowed). The implementation extends a convential Prolog machine with support for data sharing and process managment. Extensive global dataflow analysis is employed to facilitate parallelization." [Bevemyr et al 1993]

  • Source code and documentation: Online at
  • Project home page: via
  • Håkan Millroth. Reforming Compilation of Logic Programs. Proceedings International Symposium on Logical Programming, MIT Press, 1991. Also Technical Report 67, Computer Science Department, University of Uppsala, July 1991. PDF at
  • Håkan Millroth. Using the Reform Inference System for Parallel Prolog. Report 69, Computer Science Department, University of Uppsala, January 1992. PDF at
  • Johan Bevemyr, Thomas Lindgren and Håkan Millroth. Exploiting Recursion-Parallelism in Prolog. Report 75, Computer Science Department, University of Uppsala, November 1993. PDF at
  • Johan Bevemyr, Thomas Lindgren and Håkan Millroth. Reform Prolog: The Language and its Implementation. In Proc. of the 10th Int'l Conference on Logic Programming, MIT Press, pages 283-298, 1993. Also Technical Report 76, Computer Science Department, University of Uppsala, November 1993. PDF at



λProlog is a higher-order logic programming language. It extends Prolog with a polymorphic type system, higher-order programming, simply typed lambda-terms as data structures, higher-order unification, scoping mechanisms for program clauses and parameters, and modules and data abstraction. These new features are provided in a principled fashion by extending the classical first-order theory of Horn clauses to the intuitionistic higher-order theory of hereditary Harrop formulas.

There have been a series of implementations of λProlog: currently Teyjus, ELPI, and Makam; previously LP, Ergo LP, Prolog/Mali, and Terzo. There have also been refinements such as Lolli.


LP (Lambda Prolog)

The first implementation of λProlog was written in Prolog by Dale Miller and Gopalan Nadathur. Originally they used C-Prolog, and then adapted it for Quintus Prolog.

Source code

  • Dale Miller and Gopalan Nadathur. Lambda Prolog Version 2.7, 10 November 1988.  CMU AI Repository

    "This version of lambda Prolog is an amended form of Version 2.6. It also contains the source code for bringing up lambda Prolog under Quintus Prolog (Version 2.0). The following comments, made in the context of Version 2.6, provide a background to our efforts in the context of lambda Prolog." [readme.txt]


  • Dale A. Miller and Gopalan Nadathur. 1986. Some uses of higher-order logic in computational linguistics. In Proceedings of the 24th annual meeting on Association for Computational Linguistics (ACL '86). Association for Computational Linguistics, USA, pages 247–256. ACM Digital Library (open access)
  • Dale A. Miller and Gopalan Nadathur. Higher-Order Logic Programming. Proceedings of the Third International Logic Programming Conference, London, June 1986. Labo/Dale.Miller
  • Gopalan Nadathur. A Higher-Order Logic as the Basis for Logic Programming. Ph. D. Dissertation, University of Pennsylvania, 1987. ScholarlyCommons
  • Dale Miller, Gopalan Nadathur and Andre Scedrov. Hereditary Harrop Formulas and Uniform Proof Systems. Second Annual Symposium on Logic in Computer Science, Cornell University, pages 98-105, June 1987.
  • Dale Miller and Gopalan Nadathur. A Logic Programming Approach to Manipulating Formulas And Programs. IEEE Symposium on Logic Programming, San Franciso, September 1987, pages 378-388. PDF at
  • Gopalan Nadathur and Dale Miller. An Overview of Lambda Prolog. University of Pennsylvania Department of Computer and Information Science Technical Report No. MS-CIS-88-40, June 1988. Slightly corrected version of paper appearing in Fifth International Conference Symposium on Logic Programming, Seattle, August 1988. ScholarlyCommons
  • Gopalan Nadathur and Dale Miller. Higher-order Horn clauses. J. ACM  Volume 37, Number 4, Oct. 1990, pages 777–814. ACM Digital Library ScholarlyCommons
  • Dale Miller, Gopalan Nadathur, Frank Pfenning, and Andre Scedrov. Uniform proofs as a foundation for logic programming. Annals of Pure and Applied Logic, Volume 51, Issues 1–2, 1991, Pages 125-157. ScienceDirect open access


eLP (Ergo Lambda Prolog)

"eLP (Ergo Lambda Prolog) is an interpreter written by Conal Elliott, Frank Pfenning and Dale Miller in Common Lisp and implements the core of lambda Prolog (higher-order hereditary Harrop formulas). It is embedded in a larger development environment called ESS (the Ergo Support System). eLP implements all core language feature and offers a module system, I/O, some facilities for tracing, error handling, arithmetic, recursive top-levels, on-line documentation and a number of extended examples, including many programs from Amy Felty's and John Hannan's thesis." [from the release]

Source code

  • Conal Elliott et al. Ergo Lambda Prolog. Version 0.15, 12 February 1990. CMU AI Repository

    "We would like to acknowledge, however, that eLP was implemented primarily by Conal Elliott, with contributions by Frank Pfenning and Dale Miller and example suites by Scott Dietzen, Amy Felty, and John Hannan. The lambda Prolog language itself was designed primarily by Gopalan Nadathur and Dale Miller." [readme.txt]



"Prolog/Mali is a compiler for the higher-order language λProlog. λProlog is an extension of Prolog defined by Miller. It is an extension of Prolog where terms are simply typed lambda terms and clauses are higher order hereditary Harrop formulas. The main novelties are universal quantification on goals and implication. Prolog/Mali is a complete system which includes a C translator, a linker, libraries, runtime, and documentation, and runs on UNIX.

Possible applications are the same as standard Prolog, but with a real plus for those where scoping of variables is important, such as theorem-proving, implementation of type systems, and formal transformation on structured programs.

The system is a compiler (written in Prolog/Mali) which produces C code. The execution scheme uses Mali (an abstract memory for representing terms with efficient space management). Accordingly, it is necessary to compile MALI before compiling PM. A copy of MALI version 6 (16-DEC-93) is included in this directory."

  • Pascal Brisset and Olivier Ridoux. The Architecture of an Implementation of XProlog: Prolog/Mali. In Proceedings of the Workshop on the lambda-Prolog Programming Language, 1992.
  • P. Brisset. Compilation de LambdaProlog, Thesis, Rennes I, mars 92.
  • O. Ridoux and P. Brisset. The compilation of LambdaProlog with Mali, Research Report, IRISA/INRIA, to appear.
  • O. Ridoux and P. Brisset. Naive reverse can be linear. 8th International Conference on Logic Programming, Paris 1992.

Source code

  • Pascal Brisset and Olivier Ridoux. Prolog/Mali. Includes PM Version 1.8 (11 May 1992) and MALI Version 6 (16 December 1993). CMU AI Repository



The linear refinement λProlog, by Joshua Hodas.

Source code

Joshua Hodas. Lolli source code. Written in Standard ML of New Jersey.



An implementation of λProlog in Standard ML by Philip Wickline.

"This interpreter is the third in a sequence of lambda Prolog interpreters written and maintained by people from Bell Labs, Carnegie-Mellon, Duke University, and the University of Pennsylvania. A list of other implemenetations are also available. Terzo was the result of moving ELP to Standard ML. That reimplementation effort was started by by Frank Pfenning and Conal Eliott at Carnegie Mellon University, continued by Amy Felty at Bell Labs, and was restructured extensively by Philip Wickline, working with Dale Miller during 1995-96 academic year." [Home page]

Source code

  • Conal Elliot, Amy Felty, Elsa Gunter, Frank Pfenning, and Philip Wickline. LP-SML.
    • Version 1.2b, 6 January 1999. Source and compiled binaries Compilation requires SML/NJ 110 and the utility library that come with it.
    • Previous versions 1.1b of 23 April 1997 and Version 1.0b of September 1, 1996.
    • Previou version 0.1, 8 February 1996. Compilation requires SML/NJ 108, and the sml-nj library v.03.



"The name Teyjus stands ambiguously for a project and a family of systems that are about providing an efficient and robust implementation of the language λProlog. As a project, Teyjus has spanned a period of over fifteen years, involving people from Duke University, SUNY Buffalo, the University of Chicago and the University of Minnesota. As a system, Teyjus has seen two incarnations. Its first version, released in mid-1999, is characterized by a complete support for the operation of higher-order unification. Its second version, released in April 2008, is oriented around a special form of higher-order unification known as pattern unification. The new version also includes modularity notions coupled with a complete form of separate compilation." [Nadathur, 2010]

  • Home page.
  • Gopalan Nadathur and Dustin J. Mitchell. System Description: Teyjus - A Compiler and Abstract Machine Based Implementation of lambda-Prolog. In Proceedings of the 16th International Conference on Automated Deduction: Automated Deduction (CADE-16). Springer-Verlag, Berlin, Heidelberg, 287–291. SpringerLink
  • Gopalan Nadathur. Teyjus: A λProlog Implementation. Association for Logic Programming Newsletter, 31 March 2010.

Version 1

Released in mid 1999.

"The Teyjus system is the result of many years of research and development and has benefitted from the involvement of several people over time. The overall project has been directed by Gopalan Nadathur. The abstract machine, loader and compilation methods that underlie this implementation of Lambda Prolog have been designed by Gopalan Nadathur. Bharat Jayaraman and Keehang Kwon contributed valuable ideas to the structure of an earlier version of the abstract machine. The implementation of these three components, and of the concomitant higher-order unification procedure, in the present system is due to Gopalan Nadathur. A preliminary version of the loader was implemented by Guanshan Tong. Dustin Mitchell modified the low-level representation of Lambda Prolog types and terms towards realizing portability and is also responsible for the implementation of the changed scheme. The disassembler, the front-end for the system and the implementation of many builtins, especially those dealing with I/O, are due to him. Kenton Varda updated and improved on a scheme originally created by Dustin for the organization of the project code and the packaging of the distribution tarball. Andrew Gacek helped realize a better integration of the project web pages with the distribution tarball. Matt Fowles provided a nicer interface for regression testing. Shyan-Ming Perng provided initial implementations of many of the arithmetic and logical builtins and also of routines for reading and writing terms. Lyn Headley contributed to the implementation of the builtins.

An indispensable component of the release of a system of significant size such as Teyjus is its testing. Dale Miller has patiently used the system from its first, rough and ready, days, has helped pin-point several bugs and has also volunteered several suggestions towards improving its functionality. Others who have provided valuable feedback of this kind are Amy Felty, Chuck Liang, Frank Pfenning, Jeff Polakow, Xiaochu Qi and Jeremie Wajs." [Contributors]"

Version 2

Released in April 2008.

"Underlying the most recent version of the Teyjus system is a new and significantly improved virtual machine that has been designed by Xiaochu Qi as part of her doctoral dissertation work at the University of Minnesota. This virtual machine extensively exploits a special form of higher-order unification known as pattern unification." [Home page]



ELPI was designed by Claudio Sacerdoti Coen and Enrico Tassi and their colleagues.

"ELPI implements a variant of λProlog enriched with Constraint Handling Rules, a programming language well suited to manipulate syntax trees with binders. ELPI is designed to be embedded into larger applications written in OCaml as an extension language. It comes with an API to drive the interpreter and with an FFI for defining built-in predicates and data types, as well as quotations and similar goodies that come in handy to adapt the language to the host application." [Enrico Tassi, README]

  • Cvetan Dunchev, Ferruccio Guidi, Claudio Sacerdoti Coen, and Enrico Tassi. ELPI: fast, Embeddable, λProlog Interpreter. Proceedings of LPAR, Nov. 2015, Suva, Fiji. (open access)

Source code



Makam was designed by Antonis Stampoulis, with consultation by Adam Chlipala.

"Makam is a metalanguage: a language for implementing languages. It supports concise declarative definitions, aimed at allowing rapid prototyping and experimentation with new programming language research ideas. The design of Makam is based on higher-order logic programming and is a refinement of the λProlog language. Makam is implemented from scratch in OCaml." [Makam home page]

  • Antonis Stampoulis and Adam Chlipala. Prototyping a Functional Language using Higher-Order LogicProgramming: A Functional Pearl on Learning the Ways of λProlog/Makam. Proc. ACM Program. Lang., Volume 2, ICFP, Article 93, September 2018. ACM Digital Library (open access)
  • Home page.

Source code


Applied Logic Systems (ALS)


ALS Prolog

[See Syracuse/Argonne Prolog above.] "... A number of the group members decided to explore commercial possibilities in the PC arena and set out to reimplement the Research Group system design, targeting the then-current 16-bit systems, later extended to 32 bits. Applied Logic Systems, Inc. (ALS) was formed in 1984 to carry this out. The initial version, named ALS Prolog (or alspro), for the IBM PC/DOS, appeared in 1985, and implemented the compiler/WAM byte-code interpreter design from the research group. This was followed by a version for the Macintosh/MacOS. A native code compiler optimizing the WAM was developed for the IBM PC/DOS, and partially built for the Macintosh/MacOS. At the time, the native code compiler for the 386 chip was quite fast, and temporarily won the "naive reverse LIPS (Logical Inferences Per Second)" speed wars. However, the difficulty of maintaining and porting these native code compilers led to the development of a respectably efficient portable threaded code system which was subsequently used on all platforms.

These PC and Macintosh systems were followed relatively quickly (1987) by a version for Sun Workstations (Sun/SunOS/Solaris[m68000, later SPARC]), and then for other Unix workstations (Silcon Graphics/IRIX, HP/HPUX, IBM/AIX), VAX (a new version), NeXT/NeXTStep, and systems utilizing the Motorola 88k chip. An embeddable logic engine was developed under contract for Apple (plus a control interface for the Macintosh Programmer's Workshop (MPW)). It was delivered, but never released by Apple. In addition, tools for direct interfaces to dBase and R:Base were developed for the PC.

In the late 1980's - early 1990's, most of the original staff of ALS obtained their degrees from Syracuse University, and moved on to other employment. The remainder of ALS moved to Newton, MA (and later Cambridge, MA), where Chuck Houpt joined the company (and remains involved as a GitHub core memeber). XWindows interfaces were developed for the Unix workstations, and a port to Microsoft Windows was carried out via Win32. Later a port to Cygwin was developed and utilized for subsequent ports to Windows. A port to Linux was carried out, which later provided the basis for a Mac OSX version. Further database interface tools included ODBC and AccSys, together with ODBC-based interfaces to Microsoft Access, Microsoft SQL Server, mySQL and Oracle.

Extensions/improvements during the 1990's included:

  • Foreign language interfaces to Tcl/Tk, Python, and Java;
  • A basic integrated windowed development environment (alsdev) built using Tcl/Tk;
  • Delay/freeze support;
  • A platform agnostic I/O system (i.e. read/write different line-endings);
  • Improved ISO Prolog conformance.
The system has been converted to open source, and now is accessible on GitHub at Documentation and releases are available at"

[Kenneth Bowen, personal communication, 11 June 2019]

Source code

Documentation and papers

  • Prolog Execution Model. Applied Logic Systems, Inc. March 20, 1998 PDF at



Bell-Northern Research (BNR)

William J. Older of the Computing Research Laboratory, Bell-Northern Research, and his colleagues developed a series of Prolog implementations starting in 1986 and eventually encompassing the handling of cyclic structures, breadth-first unification, variable functors, variadic structures, and relational interval arithmetic. [Older 1994] gives the basic history as well as a detailed overview of the system as of 1994.


XMS Prolog

"The forerunner of BNR Prolog was XMS Prolog, which was developed in 1986-87 within the XMS Project at BNR by William Older and Bruce Spencer. The first four versions of XMS Prolog were toy implementations of a structure-sharing interpreter written in BNR Pascal, but were valuable learning exercises. Some features, such as the State Space and context stack were already present at this early date. In 1987 the interpreter was totally redesigned and reimplemented in 68000 Assembler by W. Older to become Version 5 of XMS Prolog. The handling of cyclic structures, breadth-first unification, variable functors, and variadic structures all date from this period." [Older 1994]

XMS Prolog ran on BNR's XMS operating system:

  • Marek Fridrich and William J. Older. Helix: The Architecture of the XMS Distributed File system. IEEE Software, Vol. 2, No. 3, 1985, pages 21-29. Online at


BNR Prolog

"BNR Prolog developed from XMS Prolog during 1988-89. Much of the Version 5 XMS Prolog core structure was retained, but ported into UCSD Pascal to run on Macs. Variable name retention was added at this time as well as freeze, and the syntax was changed radically to bring in it into conformance with the evolving Prolog standards. Also added was the relational interval subsystem based on the ideas of Dr. John Cleary of the U. of Calgary.(*) A major portion of the work was aimed at adapting the system from a conventional command line interpreter, to a relatively complete graphics-oriented programming environment with high level access to many of the Mac capabilities.

The development team consisted of William Older, John Rummell, Susan Antoft, Rick Snapper, Bijan Farrahi, Peter Hoddinott, André Vellino, Al Sary, and Marianne Morin, all under the direction of Rick Workman. Many contributions were made by other people during this period and in the next couple of years. In particular, Peter Cashin, the director of CRL, initiated (among other things) the Panels subsystem which was developed further by Rick Workman.

The Mac versions of BNR Prolog (and the associated manuals) were distributed to many in the academic community and other researchers around the world from 1989 to 1992. Several universities, such as Karlsruhe in Germany and Laval in Quebec, have adopted it as a teaching language at one time or another, so that many thousands of students have come into contact with it in various places. The interval arithmetic system has attracted much interest in the constraint programming community, and the technology has been copied several times: Interlog (Dassault Electronique, Fr.), ILOG Solver (Fr.), 1994 release of VM Prolog (IBM, Paris), and very likely by future Prolog IV (Marseille) and Prince (an Esprit project), as well as in several non-commercial systems.

The Unix versions of BNR Prolog originated in 1991 with William Older's design for a WAM-style compiler extended for BNR Prolog and its corresponding byte-coded interpreter. A wholly new core system based on this design was implemented in C in 1992-93 by John Rummell, and an alternate interpreter in 68K Assembler was done by W. Older. A team of developers under Jean Jervis developed the X-system interface in 1993 and reimplemented the GUI tools on top. A greatly extended new design for the relational interval arithmetic subsystem, renamed CLP(BNR), was developed by William Older and Frederic Benhamou and implemented in 1993 and subsequently upgraded in 1994." [Older 1994]

(*) See:

Source code

  • Source Archive of final BNR Prolog release, V5.0.5, 1999 for Unix platform(s) of that time. Online at

    "This archive is provided as is under the MIT license even though individual files do not have copyright notices..."

  • Re-implementation of CLP(BNR) in Prolog and packaged as an SWI-Prolog module. Online at


  • BNR Prolog Reference Manual (Macintosh Version). Bell-Northern Research Ltd., 1988. PDF
  • BNR Prolog User Guide (Macintosh Version). Bell-Northern Research Ltd., 1988. PDF

Papers about BNR Prolog

  • William J. Older and André Vellino. Extending Prolog with Constraint Arithmetic on Real Intervals. Proceedings of the Canadian Conference on Electric and Computer Engineering, 1990. PDF at

    [Colmerauer 2011] notes "[This paper] Will be important for Prolog IV."

  • William J. Older and André Vellino. Constraint Arithmetic on Real Intervals. Workshop on Constraint Logic Programming (WCLP 1991), pages 175-195. PDF
  • William J. Older. Inside BNR Prolog, or, Wendezvous with WAMA. Computational Research Laboratory, Bell-Northern Research, 1994. PDF at
  • BNR Prolog Papers: Collection of formal and informal papers covering design and use of BNR Prolog (1988-1995). Online at
  • W. J. Older and J. A. Rummell. An Incremental Garbage Collector for WAM-Based Prolog, Proceedings of the Joint International Conference and Symposium on Logic Programming, MIT Press, Cambridge, Mass., 1992.
  • William J. Older. Introduction to CLP(BNR): Notes from a course given at Carleton University, Winter Term, 1995. PDF


Universidade do Porto


YAP Prolog

"One of the most exciting developments was David H. D. Warren's abstract interpreter, eventually called the Warren Abstract Machine or WAM [Warren 1983], which became the foundation of Quintus Prolog. The success of Quintus Prolog motivated the development of several Prolog systems. Yet Another Prolog (YAP) is one example, and was started by Luís Damas and colleagues in 1984 at the University of Porto. Luís Damas had returned from the University of Edinburgh, where he had completed his PhD on type systems (Damas and Milner 1982). He was also interested in Logic Programming and, while at Edinburgh, had designed one of the first Prolog interpreters, written in the IMP programming language for the EMAS operating system, which would become the basis for the famous C-Prolog interpreter . Together with Miguel Filgueiras, who also had experience in Prolog implementation [Filgueiras 1984], they started work on the development of a new WAM-based Prolog. The goal was to design a compact, very fast system emulator, written in assembly. To do so, Luís Damas wrote the compiler in C and an emulator in 68000 assembly code.


The second chapter in YAP's history started on the mid-nineties. At this point in time, YAP development had slowed down. One problem was that the system had become very complex, mainly due to the need to support several instruction set architectures in assembly (at the time: 68000, VAX, MIPS, SPARC, HP-RISC, Intel x86). Unfortunately, a first attempt at using a C interpreter resulted in a much slower system. On the other hand, the user community was not only alive but growing, as Rui Camacho had taken YAP to the Turing Institute Machine Learning Group, where it was eventually adopted by Inductive Logic Programming (ILP) systems such as P-Progol, later Aleph, and IndLog. Second, researchers such as Vítor Santos Costa and Fernando Silva had returned to Porto and were interested in Parallel Logic Programming. While SICStus Prolog would have been an ideal platform, it was a closed source system. YAP therefore became a vehicle of research first in parallelism [Rocha et al. 1999] and later in tabling [Rocha et al. 2005]. A new, fast, C-based emulator was written to support this purpose [Santos Costa 1999] and brought YAP back to the list of the fastest Prolog systems [Demoen and Nguyen 2000].

Interest in YAP grew during the late nineties, leading to the third chapter in YAP's story. As hardware scaled up and users had more data to process, limitations in the YAP design become clear: Prolog programs perform well for small applications, but often just crash or perform unbearably slowly as application size grows. Effort has therefore been invested in rethinking the basics, step by step. The first step was rewriting the garbage collector [Castro and Santos Costa 2001]. But the main developments so far have been in indexing: it had become clear that the WAM's approach to indexing simply does not work for applications that need to manipulate complex, large, databases. Just-In-Time indexing [Santos Costa et al. 2007] tries to address this problem." [Santos Costa, Rocha, and Damas 2012]

  • Vítor Santos Costa. Implementação de Prolog. Provas de aptidão pedagógica e capacidade científica, Universidade do Porto, Dezembro 1988.
  • Ricardo Rocha. Um Sistema Baseado na Cópia de Ambientes para a Execução de Prolog em Paralelo. MSc Thesis, Department of Informatics, University of Minho, Portugal, July 1996.

    "This work addresses the issues of the design, implementation and performance evaluation of YapOr, an Or-parallel Prolog system. YapOr extends Yap's sequential execution model to exploit implicit Or-parallelism in Prolog programs. It is based on the environment copy model and implements most of the ideas introduced in the Muse system. "

  • Ricardo Rocha, Fernando Silva and Vítor Santos Costa. Or-Parallelism within Tabling. 1st International Workshop on Practical Aspects of Declarative Languages (PADL 1999), Springer, LNCS 1551, pages 137-151. San Antonio, Texas, January 1999.
  • Ricardo Rocha, Fernando Silva, and Vítor Santos Costa. YapOr: an Or-Parallel Prolog System Based on Environment Copying. In Portuguese Conference on Artificial Intelligence. Number 1695 in LNAI. Springer-Verlag, 1999, pages 178-192. SpringerLink
  • Vítor Santos Costa. Optimising bytecode emulation for Prolog. In LNCS 1702, Proceedings of PPDP'99. Springer-Verlag, 1999, pages 261-267. SpringerLink
  • Ricardo Rocha, Fernando Silva, and Vítor Santos Costa. YapTab: A tabling engine designed to support parallelism. In 2nd Conference on Tabulation in Parsing and Deduction (TAPD 2000), pages 77-87. Vigo, Spain, September 2000.
  • Vítor Santos Costa, Ricardo Rocha and Fernando Silva. Novel Models for Or-Parallel Logic Programs: A Performance Analysis. 6th International Euro-Par Conference (Euro-Par 2000), Springer, LNCS 1900, pages 744-753. Munich, Germany, August/September 2000. SpringerLink
  • Ricardo Rocha, Fernando Silva and Vítor Santos Costa. A Tabling Engine for the Yap Prolog System. 2000 Joint Conference on Declarative Programming (AGP 2000). La Habana, Cuba, December 2000.
  • B. Demoen and P.-L. Nguyen. So Many WAM Variations, So Little Time. In LNAI 1861, Proceedings Computational Logic - CL 2000. Springer-Verlag, 2000, pages 1240-1254. SpringerLink
  • L. F. Castro and V. Santos Costa. Understanding Memory Management in Prolog Systems. In Proceedings of Logic Programming, 17th International Conference, ICLP 2001. Lecture Notes in Computer Science, vol. 2237. Paphos, Cyprus, 2001, pages 11-26. SpringerLink
  • Ricardo Rocha, Fernando Silva and Vítor Santos Costa. On a Tabling Engine That Can Exploit Or-Parallelism. 17th International Conference on Logic Programming (ICLP 2001), Springer, LNCS 2237, pages 43-58. Paphos, Cyprus, November/December 2001. SpringerLink
  • Ricardo Rocha. On Applying Or-Parallelism and Tabling to Logic Programs. PhD Thesis, Department of Computer Science, Faculty of Sciences, University of Porto, Portugal, November 2001.
  • Ricardo Rocha, Fernando Silva and Vítor Santos Costa. Achieving Scalability in Parallel Tabled Logic Programs. 16th International Parallel and Distributed Processing Symposium (IPDPS 2002), IEEE Computer Society. Fort Lauderdale, Florida, April 2002. IEEE Xplore
  • Ricardo Rocha, Fernando Silva and Vítor Santos Costa. A Tabling Engine Designed to Support Mixed-Strategy Evaluation. 3rd Colloquium on Implementation of Constraint and Logic Programming Systems (CICLOPS 2003), pages 33-44. Mumbai, India, December 2003.
  • Michel Ferreira, Ricardo Rocha and Sabrina Silva. Comparing Alternative Approaches for Coupling Logic Programming with Relational Databases. 4th Colloquium on Implementation of Constraint and LOgic Programming Systems (CICLOPS 2004), pages 71-82. Saint-Malo, France, September 2004.
  • Michel Ferreira and Ricardo Rocha. Coupling OPTYap with a Database System. IADIS International Conference Applied Computing (IADIS-AC 2005), IADIS Press, volume II, pages 107-114. Algarve, Portugal, February 2005.
  • Tiago Soares, Ricardo Rocha and Michel Ferreira. Pruning Extensional Predicates in Deductive Databases. 5th Colloquium on Implementation of Constraint and Logic Programming Systems (CICLOPS 2005), pages 13-24. Sitges, Spain, October 2005.
  • Ricardo Rocha, Fernando Silva, and Vítor Santos Costa. On Applying Or-Parallelism and Tabling to Logic Programs. Theory and Practice of Logic Programming Systems 5, 1-2, 2005, pages 161-205. Cambridge University Press
  • Anderson Faustino da Silva and Vítor Santos Costa. The Design of the YAP Compiler: An Optimizing Compiler for Logic Programming Languages. Journal of Universal Computer Science, Volume 12, Number 7, 2006, pages. 764-787. J.UCS (open access)
  • Vítor Santos Costa. Prolog Performance on Larger Datasets. In Practical Aspects of Declarative Languages, 9th International Symposium, PADL 2007, Nice, France, January 14-15, 2007, M. Hanus, Ed. Lecture Notes in Computer Science, vol. 4354, Springer, 2007, pages 185-199. SpringerLink
  • V. Santos Costa, K. Sagonas, and R. Lopes. Demand-Driven Indexing of Prolog Clauses. In Proceedings of the 23rd International Conference on Logic Programming, V. Dahl and I. Niemelä, Eds. Lecture Notes in Computer Science, vol. 4670. Springer, 2007, pages 305-409. SpringerLink PDF at
  • Vítor Santos Costa. The Life of a Logic Programming System. In Proceedings of the 24th International Conference on Logic Programming (ICLP '08), Maria Garcia De La Banda and Enrico Pontelli (Eds.). Springer-Verlag, Berlin, Heidelberg, 2008, pages 1-6. SpringerLink
  • Vítor Santos Costa, Inês Dutra and Ricardo Rocha. Threads and Or-Parallelism Unified. Journal of Theory and Practice of Logic Programming, 26th International Conference on Logic Programming (ICLP 2010), Special Issue, Cambridge University Press, volume 10 (4&6), pages 417-432. Edinburgh, Scotland, July 2010.
  • Vítor Santos Costa, Ricardo Rocha, and Luís Damas. The YAP Prolog system. Theory and Practice of Logic Programming 12, 1-2 (January 2012), pages 5-34. Cambridge University Press

Source code



Swedish Institute of Computer Science (SICS) (now Research Institute of Sweden)


SICStus Prolog

"SICStus Prolog was released in 1987, with Mats Carlsson as it main developer, and it quickly gain appreciation in academic circles due to its speed and robustness. Its commercialization (by SICS) provided SICStus Prolog with the resources needed to add many components -- such as robust constraint solvers and comprehensive library modules -- that continued to attract academics and were crucial for its success in commercial applications. SICStus Prolog is well known also for two efforts it introduced at great cost and suspended later: native code generation and or-parallelism. Today SICStus Prolog is being used in teaching, research and production, running on everything from servers to handheld devices." [Demoen and Garcia de la Banda 2012]

"1985-1990. SICS is founded and recruits the first author, who joins the Logic Programming Systems laboratory, headed by Seif Haridi. The laboratory's first and main field of research was or-parallel execution of Prolog. The first author's first task at SICS is to develop the Prolog engine that will be the subject of parallelization (Gupta et al. 2001). This happens in the informal Aurora project (Lusk et al. 1990) involving David H.D. Warren and researchers from Manchester and ANL, who provide schedulers and visualizers. Subsequently, another SICStus-based or-parallel effort, MUSE (Ali and Karlsson 1990a; Ali and Karlsson 1990b), doing more copying and less sharing than Aurora, is being pursued by other SICS researchers. At the same time, SICS begins distribution of SICStus Prolog, which quickly becomes popular mainly in the academy. Visitors Carl Kesselman and Ralph Haygood develop execution profilers and native code compilers, respectively." [Carlsson and Mildner 2012]


Papers about SICStus Prolog

  • M. Carlsson. On Compiling Indexing and Cut for the WAM. Swedish Institute of Computer Science, Report R86011B, December 18, 1986. PDF
  • Mats Carlsson. An Implementation of dif and freeze in the WAM. Research Report R86012, Swedish Institute of Computer Science, December 18, 1986. PDF
  • M. Carlsson. Internals of Sicstus Prolog version 0.6. Internal Report, Gigalips Project, November, 1987.
  • Mats Carlsson. The SICStus emulator. SICS Report T91:15. Only the first 30 pages are present in the online copy. Online at SODA, the Software institutes' Online Digital Archive
  • Bart Demoen and Maria Garcia de la Banda. Introduction to the Special Issue on Prolog Systems. Theory and Practice of Logic Programming, Volume 12, Issue 1-2, 2012, pages 1-4. Cambridge University Press (open access)
  • M. Carlsson and P. Mildner. SICStus Prolog--The first 25 years. Theory and Practice of Logic Programming, Volume 12, Issue 1-2, 2012, pages 35-66. Cambridge Core - Draft at

Web site


Muse Prolog

"... Subsequently, another SICStus-based or-parallel effort, MUSE (Ali and Karlsson 1990a; Ali and Karlsson 1990b), doing more copying and less sharing than Aurora, is being pursued by other SICS researchers. [Carlsson and Mildner 2012]"

  • K. Ali and R. Karlsson. The Muse or-parallel Prolog model and its performance. In Proc. of the North American Conference on Logic Programming (NACLP '90). MIT Press, Cambridge, 757-776.
  • K. Ali and R. Karlsson. The Muse approach to or-parallel Prolog. International Journal of Parallel Programming 19, 2, 129-162, Springer.
  • Roland Karlsson and Khayri A. M. Ali. The Engine-Scheduler Interface used in the Muse OR-parallel Prolog System. Research Report R92:04, Swedish Institute of Computer Science, 1992. Online at DiVA Portal
  • Khayri A. M. Ali, Roland Karlsson, and Shyam Mudambi. Performance of Muse on Switch-Based Multiprocesor Machines. Research Report R92:07, Swedish Institute of Computer Science, 1992. Online at DiVA Portal


Universiteit van Amsterdam



"SWI-Prolog was started as a recreational program for personal understanding and enjoyment after reading [Bowen et al. 1983]. This toy landed in fertile soil. Our university department was involved in Shelley (Anjewierden et al. 1990) a work-bench for knowledge engineering that was to be implemented using Quintus Prolog (version 1) and PCE, an in-house developed object-oriented graphical library written in C. Frustrated by the inability of Quintus Prolog version 1 to make recursive calls between C and Prolog, which seriously complicated our integration between Prolog and the graphical system, we demonstrated the much cleaner integration achievable with the small SWI-Prolog system.

While SWI-Prolog was clearly inferior to Quintus in terms of robustness and execution speed, it quickly replaced Quintus, not only at our site, but also at the two overseas sites where modules for the workbench were being developed. Why did this happen? We think this was due to three small, yet much valued features: (1) the make/0 predicate that reloads all files that have been edited since last loaded (see section 3.2); (2) the ability to run make/0 on a restarted saved state dramatically reduced the application restart-time; (3) using the auto-loader the initial image could be restricted to the core parts of the application, which again reduced memory usage and startup times. The faster and bi-directional interface to the graphics libraries made the application much more responsive for typical interaction." [Wielemaker et al. 2012]

"SWI-Prolog was also released in 1987 and is the achievement of mainly one person: Jan Wielemaker. It was first developed as an in-house Prolog system to support the implementation of software prototypes in other research areas. Thus, its focus was on integrating technology that could improve this supporting role such as, for example, achieve fast interaction with external resources and reductions in memory usage or start-up times. The resulting system has obtained a considerable user and developer base both in the academic and commercial environments. Today the developers' aim is to convince a wider IT community that Logic Programming is a viable paradigm for developing and deploying applications. Critical to this is cooperation with developers and users of all Prolog systems to build a community with large-scale code sharing." [Demoen and Garcia de la Banda 2012]

Source code


  • J. Wielemaker and A. Anjewierden. An architecture for making object-oriented systems available from Prolog. In WLPE, 2002, pages 97-110.
  • J. Wielemaker. Native preemptive threads in SWI-Prolog. In Practical Aspects of Declarative Languages, C. Palamidessi, Ed. Springer-Verlag, Berlin, Germany, 2003, pages 331-345. LNCS 2916. SpringerLink PDF at
  • J. Wielemaker, G. Schreiber, and B. Wielinga. Prolog-based infrastructure for RDF: performance and scalability. In The Semantic Web - Proceedings ISWC'03, Sanibel Island, Florida, D. Fensel, K. Sycara, and J. Mylopoulos, Eds. Springer-Verlag, Berlin, Germany, 2003, pages 644-658. LNCS 2870. SpringerLink PDF at
  • T. Schrijvers, J. Wielemaker, and B. Demoen. Poster: Constraint Handling Rules for SWI-Prolog. In W(C)LP '05: Proceedings of the 19th Workshop on (Constraint) Logic Programming, A. Wolf, T. Frühwirth, and M. Meister, Eds. Ulmer Informatik-Berichte, vol. 2005-01, 2005. PDF at
  • J. Wielemaker, Z. Huang, and L. van der Meij. SWI-Prolog and the web. Theory and Practice of Logic Programming 8, 3, 2008, pages 363-392. Cambridge University Press
  • Jan Wielemaker. Logic programming for knowledge-intensive interactive applications. Ph.D. thesis, University of Amsterdam, 2009. Online at
  • Jan Wielemaker, Tom Schrijvers, Markus Triska, and Torbjörn Lager. SWI-Prolog. Theory and Practice of Logic Programming, Volume 12, Issue 1-2, 2012, pages 67-96. Cambridge University Press


State University of New York at Stony Brook

"After arriving at Stony Brook University and teaching for a couple of years, I was assigned to teach a graduate course on Artificial Intelligence. The book I used had a chapter on Prolog in it, and I figured I should probably cover that for the class (What danger could there be?) -- so I read the chapter. I like to remember it as instantaneous, but it might have taken a day or two: I realized I would spend the rest of my career with Prolog and Logic Programming. I say "realized" and not "decided" because there was no choice involved. I would just have to be the "other" David Warren for the rest of my life. The idea of Prolog and logic programming was too arresting and all-consuming for there to be any possibility for me not to pursue it. I would just have to deal with the consequences. And here I am, still dealing with the consequences." [D. S. Warren 2008]



"Attending my first LP conference, I found that I had so many more interests and concerns in common with the people I met there than I did with those I'd meet at Computational Linguistics conferences. Well, I got C-Prolog and studied Prolog implementation. I got my students together to work on a paper about evaluating Prolog programs on a network of processors. And I was thinking about implementing tabling in Prolog and realized that Prolog's depth-first backtracking search couldn't be maintained if we wanted to implement tabling, so there would need to be a more flexible way to handle environments in the Prolog implementation. And I wrote a paper on that. I heard about a close-by LP conference, the 1984 Symposium on Logic Programming in Atlantic City, and we submitted the papers there. Having submitted, I was sent several papers that were submitted by others to review. One of them was "Towards a Pipelined Processor for Prolog" by Evan Tick and David Warren (yes, that other David Warren.) I was fascinated! I pored for hours over that paper, teasing out why it didn't need a top-of-stack-pointer, how the last-call optimization really worked, and why a variable was unsafe. As Bart Demoen mentioned in the last Newsletter, that was the first public description of what came to be known as the WAM. It was dense, since the paper was about the WAM's performance not its description, but I figured out the WAM from that paper. And I was yet again blown away. That was, and remains, the most amazing piece of architecture I have ever seen, by far.

So now I had a new task: to completely understand the WAM. So I set out, with my students, to write a WAM emulator. I had my graduate compiler students write compilers that generated WAM instructions as intermediate code. I attended a wonderful workshop on the WAM at Argonne National Labs, organized by Ross Overbeek and Rusty Lusk. Our emulator turned into what later became known as SB-Prolog. Here I need to mention my students who did the work: David Znidarsic, a masters student who wrote the emulator and went on to work on the innards of Quintus Prolog, and Jiyang Xu, who worked on the engine and its performance and then went to work at ECRC, and Saumya Debray, who wrote the WAM compiler, in Prolog, of course, and went on to great things that you all know about." [D. S. Warren 2008]

"[Saumya Debray] took our code when he finished his PhD and went there in the 80’s. Arizona had a tradition of distributing research software, so he asked if he could distribute our Prolog code. I, of course, said yes, but didn’t think anyone would be much interested in it. He named it SB-Prolog, I presume to emphasize that it had been mostly developed at Stony Brook University." [D. S. Warren, personal communication, 12 October 2019]

  • Saumya K. Debray. The SB-Prolog System, Version 3.1: A User Manual. Department of Computer Science, University of Arizona, December 1989. Modified for the 386 MS-DOS version by Diomidis Spinellis, Department of Computing, Imperial College. ASCII

Source code



"The starting point of XSB (in 1990) was PSB-Prolog 2.0 by Jiyang Xu and David Warren. PSB-Prolog in its turn was based on SB-Prolog, primarily designed and written by Saumya Debray, David S. Warren, and Jiyang Xu.". [XSB Programmer's Manual]

"Jiyang Xu was my other student who worked on our Prolog system. He finished his PhD and went to work at ECRC (in Munich, I think.) He also took our Prolog code base, and while working at ECRC extended it by adding parallelism (and other things, like a module system) and called it PSB Prolog, for “Parallel” SB Prolog, I presume. That code was proprietary. [D. S. Warren, personal communication, 12 October 2019]"

  • Jiyang Xu. User Manual. PSBProlog System, Version 1.40, ECRC, 1991.


XSB Prolog

"So I went off to California to work at Quintus for a sabbatical year in 1986 to work on an interface to relational databases. I had been working with Dave Maier, a relational database expert, and had gotten him somewhat interested in Prolog. He had finished his seminal book on relational database theory and was looking for another book to write, so we had started working on "Computing with Logic". We decided to break it into three parts, starting with Prolog with only 0-ary predicates, then Prolog without function symbols, and finally full Prolog. So we wanted to come up with names for these languages: the first was easy and Proplog, and the last was already Prolog, but we needed a name for the middle one, and so came up with Datalog. Dave was also still working with his former advisor, Jeff Ullman, and introduced him to some of the ideas, and he got very interested in Datalog. That group came up with Magic Sets as a way to efficiently evaluate Datalog programs. I had not forgotten tabling, and had done some work on it, but never tried to seriously implement it. Who in their right mind would think about tabling the append predicate? Prolog was mostly a list-processing language, and tabling such predicates was obviously a losing proposition. But there was a lot of excitement about Magic Sets, and if that was so wonderful, maybe tabling could be interesting as well.

Then in 1989 I attended a PODS conference, where Catriel Beeri gave an hour-long tutorial on Magic Sets, explaining so clearly how it was really a different implementation of tabling. Well, Damn! If it was just tabling, I was convinced, with all the work we'd done on Prolog implementation and the WAM, that we could do as well or better than anyone in the database community who might implement Magic Sets. So it was back to serious implementation time. Again I was blessed with brilliant students: Weidong Chen who worked out the theoretical underpinnings of what became XSB, Terrance Swift who extended the WAM to table stratified programs, and Kostis Sagonas who extended it to compute the well-founded semantics. And there were others who made significant contributions. And it turned out that I was right about the WAM: our main competition from Magic Sets and the database community was the CORAL system, which was being developed at the University of Wisconsin by Raghu Ramakrishnan and his students. Both XSB and CORAL became "operational" at about the same time, and being eager to compare performance, we got a copy of CORAL and ran some simple benchmarks. It turned out that XSB was around 7 times faster than CORAL.... The WAM wins again! Of course we were very pleased and proud, but now I wonder if it might not have been better for the performances to have been closer. More competition might have been better for the us and the communities in the long run.

And since then I've been working on extending and improving XSB, but even more on applications of Prolog and XSB. I find that I really am a programmer at heart. I really do like to make systems that work and solve problems. So that's probably what I'll be doing for awhile to come.“ [D. S. Warren 2008]

"When I realized I wanted to implement tabling at the engine level (around 1990), we got the most recent versions of SB-Prolog and PSB-Prolog and after review, decided that PSB-Prolog had more of what we wanted to build on. We worked with Jiyang, who worked with ECRC, who allowed him to give us a stripped down version of PSB-Prolog, after he had removed all the code that implemented the parallelism. So that formed the basis for what became XSB-Prolog." [D. S. Warren, personal communication, 12 October 2019]


  • Theresa Swift, David S. Warren, Konstantinos Sagonas, Juliana Freire, Prasad Rao, Baoqiu Cui, Ernie Johnson, Luis de Castro, Rui F. Marques, Diptikalyan Saha, Steve Dawson, and Michael Kifer. The XSB System, Version 3.8.x, October 29, 2017.

Source code

  • Project home page. Source code, manual, executables, old releases starting with version 2.2 (April 27, 2000).
  • XSB Prolog: Prolog extended with OLDT (tabling) and Hilog terms. Version 1.3 (beta), September 1993. CMU AI Repository


  • David S. Warren Programming in Tabled Prolog (very) DRAFT July 31, 1999 Online at
  • Terrance Swift and David S. Warren. The XSB Logic Programming System. Association for Logic Programming Newsletter, Volume 20, No. 3/4, December 2007. Summary of recent developments in XSB. Online at PDF
  • Terrance Swift and David S. Warren (2012). XSB: Extending Prolog with Tabled Logic Programming. Theory and Practice of Logic Programming, Volume 12(Numbers 1-2), 2012, pages 157-187. Cambridge University Press



"I also realize that B-Prolog by Neng-Fa Zhou also started from the SB-Prolog code base. He made major changes to it in his development, primarily adding constraint processing (to my knowledge.)" [D. S. Warren, personal communication, 12 October 2019]


Gigalips Project (Argonne National Laboratory, University of Manchester, University of Bristol, SICS, and IQSOFT SZKI)

  • Péter Szeredi. Performance Analysis of the Aurora Or-Parallel Prolog System. In Proceedings of the North American Conference on Logic Programming, E. Lusk and R. Overbeek, Eds. MIT Press, Cambridge, MA, 713-732, 1989.
  • E. Lusk, R. Butler, T. Disz, R. Overbeek, R. Stevens, David H.D. Warren, A. Calderwood, Péter Szeredi, Per Brand, Mats Carlsson, Andrzej Ciepielewski, Bogumil Hausman, and Seif Haridi. The Aurora or-parallel Prolog system. New Generation Computing, 7 (2,3), February 1990, pages 243-271. SpringerLink
  • Péter Szeredi and Mats Carlsson. The Engine-Scheduler Interface in the Aurora Or-Parallel Prolog System. Technical Report TR90-09, University of Bristol, April 1990. PDF
  • Feliks Kluźniak. Developing Applications for Aurora Or-Parallel System. Technical Report TR-90-17, Dept. of Computer Science, University of Bristol, 1990.
  • Mats Carlsson and Péter Szeredi. The Aurora Abstract Machine and its Emulator. Report R90005, Swedish Institute of Computer Science, 1990. Online at SODA digital archive
  • Mats Carlsson. Design and Implementation of an OR-Parallel Prolog Engine. Ph.D. thesis, Royal Institute of Technology, Stockholm, 1990.
  • Péter Szeredi. Contributions To Or-Parallel Logic Programming. Ph.D. thesis, Technical University of Budapest, December 1997. PDF at


Humboldt-Universität zu Berlin (HU-Prolog)



"HU-Prolog is an efficient, portable, and expandable interpreter system for Prolog, which is available in source-text-compatible versions on PCs, workstations, and mainframes under the operating systems MS-DOS, UNIX, and VMS.

HU-Prolog is an implementation of the Clocksin-Mellish Standards and corresponds to DEC10-Prolog.

HU Prolog was written in 1987-1990 at the Humboldt University in Berlin. The original version of the language description corresponding to Release 1.54 appeared in the magazine edv-aspekte (8th year, issue 4, page 2-31).

The sources of HU-Prolog have been released to the public by the authors and can be copied and used for non-commercial purposes as long as the references to authorship and intellectual property are not removed from the program and the documentation.

Prolog is a living language and HU-Prolog is a living implementation. This text describes the implementation "HU-Prolog 2.025" of March 1993." [Horn, Dziadzka, and Horn 1993]

"In the ‘80s, I was a student at the Department of Mathematics, Humboldt-University Berlin, East-Germany. There was no CS department at this time. Together with another student and our teacher Christian Horn, we developed HU-Prolog ... It was used for teaching, was used for some research projects and even got used commercially in at least 2 projects. ... Commercial extensions like a dBase interface or a graphical extension for MS-DOS are unfortunately lost on some old tapes." [Dziadzka, personal communication, 28 March 2020]


University of York


York Prolog

  • J. M. Spivey. University of York Portable Prolog System (Release I) User's Guide, York, U.K., March 1983.
  • Michael Spivey. Pascal source code for York Prolog. Online at



By 1996, Spivey had been at Oxford University for a number of years.
  • Michael Spivey. An Introduction to Logic Programming Through Prolog. Prentice-Hall, Inc., Upper Saddle River, NJ, USA. Online at author's web site

    "The final part of the book, in Chapters 14 to 18, picks up where the second part left off. It explains how SLD-resolution can be implemented efficiently by machine, using the conventional technology of Prolog implementation. These chapters describe the functioning of an actual interpreter for a Prolog subset, and the complete source code for this interpreter is included as Appendix C of this book."

  • Michael Spivey. picoProlog source code. Online at author's web site



This project would not have been possible without help from many people:

  • Alain Colmerauer
  • Mike Alexander
  • Janusz Stanisław Bień
  • Ken Bowen
  • Lars Brinkhoff
  • Maurice Bruynooghe
  • Mats Carlsson
  • Peter Cashin
  • Mantis Hoi Ming Cheng
  • William F. Clocksin
  • José C. Cunha
  • Veronica Dahl
  • Saumya K. Debray
  • Bart Demoen
  • Christopher J. Dollin
  • Mirko Dziadzka
  • Maarten van Emden
  • Ian T. Foster
  • Randy Goebel
  • Steve Gregory
  • Chuck Houpt
  • Gerda Janssens
  • Feliks Kluźniak
  • Jan Komorowski
  • Robert Kowalski
  • Tim Lindholm
  • John Lloyd
  • Francis G. McCabe
  • Dale Miller
  • Gopalan Nadathur
  • Lee Naish
  • Guy Alain Narboni
  • Ulrich Neumerkel
  • William Older
  • Elena Pereira
  • Fernando C. N. Pereira
  • Luís Moniz Pereira
  • António Porto
  • Grant Roberts
  • Tim Robinson
  • Ricardo Rocha
  • Robert Schrag
  • Michael Spivey
  • Brian D. Steel
  • Stanisław Szpakowicz
  • André Vellino
  • David H. D. Warren
  • David S. Warren
  • Jan Wielemaker
  • Rick Workman
« January 2021 »
Su Mo Tu We Th Fr Sa
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30

Powered by Plone CMS, the Open Source Content Management System

This site conforms to the following standards: