Paul McJones, editor
paul@mcjones.org
https://mcjones.org/dustydecks/
Last modified 12 October 2025
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.
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.
The primary source for the creation of Prolog is [Colmerauer and Roussel 1996].
[Colmerauer and Roussel 1996]
- "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
difpredicate (for ≠) into the very first version of Prolog."- "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'."
- "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."
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. Descriptions of the language Prolog and of the man-machine communication system written in it are in this report, which apparently had at least one revision:
Roussel's dissertation describes the immediate predecessor, OEDIPE:
For more information about the implementation of Prolog 0, see section 7.4 of [Colmerauer and Roussel 1996].
"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 [sic] 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].
There are no known surviving copies, but see Warsaw for a (relatively slight) modification and port of the final Marseille interpreter to an ODRA computer.
The last three slides, "Example to Illustrate How PROLOG Is Implemented", served as the basis for Péter Szeredi's implementation of NIM_IGÜSZI Prolog in CDL.
"Yes, Epilog[400,400] was my minimal online guide to using Marseille Prolog on the Edinburgh DEC-10. At some point, it may have included mention of my 'supervisor' SVW, which implemented the 'Edinburgh' syntax, and was an alternative to the standard SVI 'supervisor' from Marseille. (The latter I think/guess was the end result of successive incarnations by Colmerauer, Roussel and Bazzoli). Later versions of Epilog might have mentioned the availability of the new compiler-based DEC-10 Prolog, but that would only have been (as far as I recall) from late 1976 or 1977 onwards." [Warren, personal communication, 14 February 2021; updated 6 February 2022]
"It looks pretty much as I would have produced it in early 1974, soon after completing the port. However, I suspect appendixes A2-A4 may have been added later, possibly in 1975. My memory on all this is very patchy. I do remember that Battani and Meloni visited us in Edinburgh, nominally to assist in any issues with the system, of which miraculously there were almost none. I suspect they brought along a new version of the superviser, called SV2, referred to in appendix A2, which apparently fixed some minor bugs, but used up more memory. So that may mean this version of Epilog[400,400] was actually from 1975." [Warren, personal communication, 23 November 2022]
"The file odra.6 monitortext is roughly what I remember of Philippe Roussel’s 'superviser', written in Prolog.
The SAIL files of DEC-10 Prolog are a later incarnation of what I most remember. I think the Prolog in JREAD.PL (which reads a Prolog term in Edinburgh syntax) is at the heart of what I adapted from Roussel’s 'superviser'." [Warren, personal communication, 6 February 2022]
"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]
Includes full source code.
"A listing of the program GEOM written and a PROLOG user's guide will be sent upon request.
"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 '*'."
"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 ..."
* Prolog II included the dif/2 predicate, which had been part of Prolog 0 but not Prolog 1 or Edinburgh Prolog.
The download link for the program is broken, but this works: .zip via archive.org
"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]
"... 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?
[Colmerauer 2011]
- 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."
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]
Findeisen-Bellert joined McGill University in Montréal in 1972.
"A former student, Hélène Le Gloan, installed [Marseille Prolog] at the University of Montreal." [Colmerauer and Roussel 1996]
"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]
"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]
An extended version of these lecture notes, first written for an advanced course at the Mathematics Center in Amsterdam, was published as: Robert Kowalski. Logic for Problem Solving. North-Holland, 1979. PDF at doc.ic.ac.uk
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.
"In the fall of 1974 it was my turn to visit Marseille. Colmerauer showed me the work on his natural-language question-answering system based on non-clausal full first-order logic. Alain had no use for logic programming. He wanted to build parsers for natural language and theorem provers. He needed a better programming language for that, and now he had one. He also showed me a little side exercise: a compiler for a simple Algol-like programming language, written in Prolog. ...
When I was getting ready to leave Edinburgh for good in the summer of 1975, it turned out that I had forgotten to show David Warren Colmerauer's little compiler program. David pounced on it. Within a year he was sending me successively more extensive compilers for Prolog, written in Prolog." [van Emden 2006]
"... the original compiler took Prolog source with declarations needed for linkage to external predicates, and produced MACRO-10 files. Those could then be linked with the interpreter compiled Prolog modules and the (MACRO-10) runtime modules to create a runnable interactive Prolog with the compiled Prolog code available for combination with interpreted Prolog code.
Later, David conceived of a new scheme where the compiler lived inside the interpreter and generated relocatable DEC-10 machine code that was then stored in memory for immediate execution. This involved a somewhat intricate scheme to jump between interpreted and compiled code, with a tricky bootstrapping arrangement. That's the system in SAIL." [Fernando Pereira, personal communication, 18 Feb 2021]
"I vaguely remember the switch to an 'in-core' compiler, but Fernando remembers the details much better. I suspect he’s being unduly modest, in that he did all the difficult stuff to make my ('wouldn’t it be good if') idea work." [David Warren, personal communication, 19 Feb 2021]
"Some handwritten notes by DW, probably mainly to assist FP in writing the garbage collector, and therefore probably written quite early (1976?)." [David Warren, personal communication, 18 Feb 2021]
"Some rough handwritten notes by FP. Probably a forerunner to his installation guide, and written quite early on (1976 or 1977?)." [David Warren, personal communication, 18 Feb 2021]
"Typewritten guide produced by FP, dated 26 Jun 1978, with a changes summary dated 15 Jun 1978." [David Warren, personal communication, 18 February 2021]
"A summary of the DEC-10 Prolog modules produced by FP, probably also dating from Jun 1978. The author of each module is noted (DW or FP), with DW+ indicating a module written by DW with some modifications by FP." [David H.D. Warren, personal communication, 18 Feb 2021]
Cited in [Warren 1978].
Accompanying examples. ASCII at saildart.org
"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]
Part I was later published as [Warren 1980]; Part II had been published as [Warren 1977b].
Appendix 3 is a full listing of the TUGA program, written in DECsystem-10 Prolog.
"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."
A slightly revised version was published as Technical Note 275, AI Center, SRI International, January 1983. Online at ai.src.com via archive.org
In 1980, Luís Damas wrote a Prolog in the IMP programing language for Edinburgh Multi-Access System (EMAS) (which started on the ICL 4/75 and had been ported to the ICL 2900 series). [F. Pereira, C-Prolog read.me, 1982]
This version appears to have been heavily modified by Lawrence Byrd at Edinburgh. Then Bob Eager, who was maintaining EMAS at the University of Kent, made further changes. Later he donated a set of files to the The Edinburgh Computer History Project, which makes the files available through its online archive.
"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, read.me, 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]
"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.
[William Clocksin, personal communication, 11 June 2019]
- 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.
- 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!
- 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."
prologX/how.to.make.prologx describes the full bootstrap procedure, which uses an existing CProlog system to execute the "standalone compiler" (sacom.pro) on the three modules written in Prolog (pip.pro, rescom.pro, and standio.pro). However prologX includes the compiled versions (with suffix .zap), so that step may be omitted. makefile.zip builds Clocksin's original C version; makefile builds Robinson's microcoded version, which depends on the microcode in the parallel prologM directory.
"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."
"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)."
Proposes a benchmark of naive reverse of a 30-element list, which is said to take 53.7 milliseconds under DEC-10 Prolog.
Proposes a conventional (uniform) heap memory with incremental garbage collector.
"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."
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"?
"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."
"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]
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.
“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."
"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."
"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]
"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]
"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]
"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]
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:
"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.ca
"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 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 ..."
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]
"Many thanks to Ron Ferguson for some very helpful discussions."
"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."
These projects were carried out at the Institute of Informatics, Warsaw University.
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.
"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].
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(*):
1.2APPEND3NIL000NIL0 3.2APPEND3.2012.203.2APPEND3123NIL0(*) 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)." odra.4- "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(NIL,*L,*L) +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]
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 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.
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.
"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]
"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]
"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]
"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]
"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]
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.
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.
Describes a natural language question-answering system implemented using a slightly modified version of Edinburgh PDP-11 Prolog for RT-11.
"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]
"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]
"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]
"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]
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 cs.bham.ac.uk
This work followed the Prolog machine of Warren's thesis, and slightly preceded the Warren Abstract Machine (see below); it was a byte-coded Prolog instruction set for a goal stacking model rather than an environment stacking model.
The scans in this section are all courtesy of David H. D. Warren.
Summary of some work and ideas leading up to the WAM, funded by DEC.
"... a small note written for Symbolics, suggesting how Prolog could be efficiently implemented on their Lisp Machine. They were enthusiastic, but Quintus seemed a better way for me to go." [Warren, personal communication, 15 Feb 2021]
"A note describing the 'Old Prolog Engine', which was a predecessor to the WAM." [Warren, personal communication, 15 Feb 2021]"
"A compiler for the Progol macro-language, which was used to implement emulators for the old and new engine instruction sets - this version translates into MC68000 instructions." [Warren, personal communication, 15 Feb 2021]
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.
Around 1998, the Swedish Institute of Computer Science (SICS) acquired Quintus Prolog from a company named Andata, which had apparently recently acquired AI International. The code base acquired by SICS included ports to Motorola 68k, Sparc, x86, HP-UX, Alpha AXP, and possibly others, but not DEC VAX. [Source: Mats Carlsson, personal communication, 17 November 2024.] SICS continues to sell and support Release 3.5.
"... based on ideas from CSP, Delta-Prolog and Luca Cardelli's rendezvous facility for Amber."
"Quintus has carefully considered a number of approaches to a parallel version of Quintus Prolog for the Sequent Symmetry series of machines, under the Dynix version of Unix. The present proposal indicates intent for a specific direction, among two principal alternatives."
"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."
"Xerox Quintus Prolog was designed to run alongside Interlisp-D, and to take advantage of the extended microstore on the higher-end Xerox Dandelion (1108) workstation, a configuration dubbed the 'Dandetiger.'" [Herb Jellenik, personal communication, 22 Feb 2021]
Microcode originally written by Don Charnley of Xerox based on executable Lisp prototypes written by Richard O'Keefe. William Kornfeld wrote higher-level Lisp code for the project. Later Peter Schacter worked on the Lisp code.
Digital Equipment Corporation offered Quintus Prolog 2.4 for their VAX architecture computers, running on both VMS and Ultrix. Software support was available via Quintus. SICS's acquisition of Quintus Prolog (see above) did not include the DEC VAX implementation. [Source: Mats Carlsson, personal communication, 17 November 2024.]
The company was founded in the early 1980s by Peter Schnupp.
"IF/Prolog was for some time the biggest competitor to Quintus. The fast native code compiler was written by Christian Pichler in part in his Diploma thesis [Pichler 1984]." [Ulrich Neumerkel, personal communication, June 2023]
'Jan. 1994 Louvre Mikissimes (Paris, France) becomes the first venue for the Mikissimes Design System, in which eyewear is designed for individual customers by computer graphics incorporating artificial intelligence.'Minerva helped to fix issues in the Prolog standard as of 2017, by providing the solution already in 1997 or earlier." [Ulrich Neumerkel, personal communication, 12 June 2023]
"MINERVA is a declarative language that inherits and combines the advantages of Java and Prolog, resulting in a very practical tool. MINERVA is implemented in Java and provides the core functionality of ISO/IEC 13211-1." [Robert Tolksdorf 2009]
"IF Computer announces MINERVA, a commercial Prolog compiler implemented in Java. It produces Java stand-alones and applets that are executable in Web browsers such as Netscape and Internet Explorer.
Application areas include government services, help desks, intelligent Web front ends, and sales support. Advantages of MINERVA: reduced network traffic for interactive applications, faster response times, reduced server load, and client privacy protection.
MINERVA's client-side processing complements the IntelligentWeb http/cgi-bin interface library developed by IF/Prolog for server-side processing.
MINERVA is available for licensing as an end-user or OEM software product. IF Computer also invites proposals for joint research projects using MINERVA.
For more information, see http://www.ifcomputer.com/MINERVA or send email to info@ifcomputer.com
Oskar Bartenstein
IF Computer Japan Ltd.
5-28-2 Sendagi, Bunkyo-ku, Tokyo 113, Japan
Tel: +81 3 5814 3352
Fax: +81 3 5814 3357
Email: ifcj@IFComputer.co.jp
URL: http://www.ifcomputer.com"
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]
"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]
See also this list of early Computer Science Department reports.
UPMAIL stands for Uppsala Programming Methodology and Artificial Intelligence Laboratory.
YAQ was a structure copying Prolog interpreter originally written in Maclisp by Mats Carlsson, UPMAIL, Uppsala University, 1982.
"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]
"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)."
"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]
λ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.
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.
"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]
"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]
"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."
The linear refinement λProlog, by Joshua Hodas.
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]
"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]
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]"
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]
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]
[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:
The system has been converted to open source, and now is accessible on GitHub at github.com/AppliedLogicSystems/ALSProlog. Documentation and releases are available at alsprolog.com."
- 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.
[Kenneth Bowen, personal communication, 11 June 2019]
In 1986, Borland released version 1.0 of Turbo Prolog, a product that had been developed for Borland by Prolog Development Center (now PDC A/S), which was founded in 1984 in Denmark. Borland released version 2.0 in 1988. Later marketing of the product returned to PDC, which released it first under the name PDC Prolog and later Visual Prolog.
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.
"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:
"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:
- J.G. Cleary. Logical Arithmetic. Future Computing Systems, Vol. 2, No. 2, 1987. Online at ucalgary.ca
"This archive is provided as is under the MIT license even though individual files do not have copyright notices..."
[Colmerauer 2011] notes "[This paper] Will be important for Prolog IV."
"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]
"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. "
"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]
"This manual corresponds to Sicstus version 0.6."
"... 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]"
"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]
"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 80s. Arizona had a tradition of distributing research software, so he asked if he could distribute our Prolog code. I, of course, said yes, but didnt 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]
"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]"
"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]
"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]
"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]
"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."
Extends [Kowalski 2013].
This project would not have been possible without help from many people: