> Prolog is becoming more interesting now that several conforming and free implementations with comprehensive features arise
What's wrong with SWI-Prolog?
What's wrong with SWI-Prolog?
https://www.complang.tuwien.ac.at/ulrich/iso-prolog/SWI7_and...
In my experience, there are two Prolog worlds, and that has been true right from the beginning of Prolog with Kowalski coming from the world of pure mathematical formalisms, and Colmerauer coming from the world of pragmatic, practical programmers. The power of Prolog (no pun intended :) comes from the tension between these two worlds.
If Kowalski had his way, Prolog would probably be a perfect jewel encased in golden amber, completely unusable but a wonder to behold. If Colmerauer had his way, Prolog would be a quick and dirty programming language fit to replace javascript or C. But they worked together, hand-in-hand, and made something bigger and better and more wonderful than either could have imagined [1].
This duality is also a curse, of course, because its critics can attack it from two sides: it's not pure enough for the purists, not dirty enough for the programmers. Half of its critics complain that it's not 100% declarative, the other half complain that it is not "general purpose" (see elsewhere in this thread). Well, it's not 100% declarative because it's got side-effects, but then what use is a programming language without side-effects? One simply ends up with twisted abominations like monads [2]. And I still don't understand what "general puprose" means, if it doesn't describe Prolog.
I think Jan Wielemaker [maintainer of SWI-Prolog] is firmly in the Colmerauer camp, striving to create a language that everybody can use, not just musty academics in their (our!) ivory towers. I have to say I don't always agree with his choices, but I, personally, am infinitely grateful for his oeuvre and I have often considered how little I could have done, for example in my PhD research, without his work.
_________________
[1] To hear the French say it of course, it was Colmerauer and Philippe Roussel who created Prolog and Kowalski was probably only visiting Marseilles for unrelated reasons. See the Prolog article on French wikipedia: https://fr.wikipedia.org/wiki/Prolog
[2] On the other hand, I think we can both agree that the dynamic database is evil.
"The language was developed and implemented in Marseille, France, in 1972 by Alain Colmerauer with Philippe Roussel, based on Robert Kowalski's procedural interpretation of Horn clauses at University of Edinburgh."
No. There are far too many such allusions in this post that it is difficult to dismantle them all. So I will stick to this one.
Note that Prolog was born exactly in the very moment when Colmerauer understood how to encode grammars. How much is this quick and dirty? Since Robinson there was some unease about how to encode grammars as this (so far) only lead to extremely inefficient proof procedures. (Roughly, any partition of a text had to be analyzed, most of which were finally discarded) Prior to this moment of understanding in the summer of 1972, as is best illustrated by Philippe Roussel's thesis of May 1972, it was not clear which strategy to use.
Quick and dirty features were rather introduced when Prolog was taken from Marseille to Edinburgh. In particular,
1mo, the quite clean error mechanism was replaced by just silent failure. `T =.. L` just failed. Thereby disregarding the observation of Battani and Meloni 1973 that built-in predicates have three possible outcomes: success, failure, and error.
2do, characters were replaced by character codes something any self respecting compiler writer would have never done.
But then, all in all, DEC10 Prolog had so many improvements that helped to spread Prolog.
Errors are absolutely essential to ensure the correctness of pure Prolog programs. It took some more decades to recover from these quick and dirty setbacks.
There is only one single such quick and dirty issue in Prolog I and that is the omission of the occurs check which was present with a flag in Prolog 0 (the first version written in Algol-W). In particular the lame excuse of this omission was started with the Prolog I manual of 1975. It was then mindlessly reiterated time and again to DEC10's and many other systems' manuals. At least, Colmerauer developed thereafter the notion of rational trees present since Prolog II.
It is only now that systems slowly recover from this offering an optional occurs check.
https://en.wikipedia.org/wiki/Occurs_check#Sound_Unification
One such recent source is this documentary (in French) about Alain Colmerauer by a lady who shares his surname (a relative, I'm guessing):
https://youtu.be/74Ig_QKndvE?t=311
I've pointed the link to just before the start of an interview with Kowalski where he says (in English) what I transfer above, that Colmerauer was more practically minded and coming from a computer science side point of view while he (Kowalski) was more theoretically minded and coming from a mathematical logic point of view, and also that this tension created an "alchemy" that would not have transpired otherwise. I watched this documentary very recently and I guess it coloured my comment above.
More generally, it's easy to find discussion of the "pure" subset of Prolog and about its purported advantages compared to the rest. I'd have to go back to those textbooks to be sure, but I think I first encountered this idea in The Art of Prolog (O'Keefe) or "The Craft of Prolog" (Sterling & Shapiro), or probably both. And I have heard Ivan Bratko's coding style in his Prolog Programming for AI described as being too imperative and not the recommended style today [2].
I guess what people mean when they talk about "purity" is the lack of side-effects, and other concessions to the everyday needs of the working programmer. I understand the occurs-check flag to be one such concession, for example [3].
So I don't think that all this is just my imagination. In my experience, there really is a divide between Prolog users that think of Prolog as a kind of mathematical notation for computers and smart at the thought of its "dirty" side-effects, and those who just want to use it as a powerful, and beautiful, tool. Like myself.
But I should try to be less sentimental in my analysis in the future. Again, thanks for reminding me to check my assumptions and try to remember where my knowledge comes from.
_____________
[1] I spent four years during my PhD at Imperial College literally down the corridor from Kowalski's office, but I never had the guts to go and talk to him and ask him about Prolog's history, that I am always very curious about. I regert that now that my PhD is ended and I'm no longer in the same building, or the same city :/
[2] Which is nonsense. Also Bratko said I'm good with Prolog, so there.
[3] What does the DEC10 Prolog manual say about the occurs check?
See I.2.1. Occur Check of https://userweb.fct.unl.pt/~lmp/publications/online-papers/D...
A recent related discussion: https://stackoverflow.com/questions/65600226/what-occurs-che...
In general, we do agree on the observation that Prolog profits from both the theoretical and the practical side. But still even today I have the impression that the highly theoretically leaning side does not appreciate the fundamental contribution errors have on ensuring correctness properties. At least this was my impression of November 10th in Paris.
Just one personal recollection (from memory) which probably also influences my view on the Kowalski-Colmerauer relation. At a META 90 tutorial/talk about meta interpreters, Sterling attributed the origin of meta interpreters to Warren and the DEC10 manual. Kowalski responded (publicly during the talk) that this was well known to Colmerauer, well before Warren ever got into Prolog.
As to the lady you are referring to she is his widow, a linguist.
> ... whereas unification without the occur check is linear on the size of the smallest of the terms being unified.
This claim is incorrect, it goes far beyond what is possible. To see its incorrectness consider the unification problem X = Y. And just for illustrative purposes, think of them both as being very big and evolved. Now, consider a related unification problem Z-Z = X-Y with Z just a variable. According to above claim, the cost would be now independent of X and Y which cannot be.
I wonder if all that was more of a consideration in an older time, with weaker hardware. Anyway where I come from (ILP research, again) "polynomial time" is synonymous to "efficient" and the bigger problem is proofs failing to terminate.
I might actually try some learning experiments with the occurs check flag set to "true" just to see what happens. I mean, I wonder. I'm so used to leaving the flag to default false that I wonder if I haven't formed a completely wrong model about the execution of Prolog programs. I've been coding in Prolog for more than ten years now and it still catches me off-guard at times.
>> A recent related discussion: https://stackoverflow.com/questions/65600226/what-occurs-che...
Thanks! I'll have a look.
It's funny but my go-to reference for unification (Foundations of Inductive Logic Programming, 1997) says that the occurs check is crucial for the performance of the algorithm (because without it unification can go on forever, whereas with the occurs check unification will terminate and find an mgu if one exists). That's exactly the opposite argument than the one in the PDP-11 and Sicstus manuals.
I confess it's been a while since I've looked at the matter. Thanks for reminding me to refresh on it. Just in case it comes up in some internet conversation and I come across as clueless :P
>> Just one personal recollection (from memory) which probably also influences my view on the Kowalski-Colmerauer relation. At a META 90 tutorial/talk about meta interpreters, Sterling attributed the origin of meta interpreters to Warren and the DEC10 manual. Kowalski responded (publicly during the talk) that this was well known to Colmerauer, well before Warren ever got into Prolog.
Wow, that's a really interesting historical tidbit. My specific research in ILP is on an approach called "meta-interpretive learning". Doesn't quite roll of the tongue but it's basically what it says on the tin: a Prolog meta-interpreter used for induction (i.e. learning). Without the idea of meta-interpreters that wouldn't have been possible. And meta-interpreters themselves, btw, would not have been possible with strict adherence to logic programming formalisms. What I mean is, Prolog programs can take as arguments Prolog programs so Prolog programs can't be first-order. And they're not! But that opens up entire avenues of possibility, like representing second and higher-order logics.
>> As to the lady you are referring to she is his widow, a linguist.
Ah, thanks. A linguist. That figures!
Many current systems perform rational tree unification. Like SICStus, SWI by default, Scryer by default etc. This claim that unification going on forever only holds for rather the minority of systems today.
“Interesting” is inherently subjective, and relative specifically to the interests of some specific entity or group. When the Austrian Federal Computing Centre says something is “interesting”, it is shaped by the needs and constraints of the Austrian Federal Computing Centre.
What is interesting to you may be different, because you probably have different interests than the Austrian Federal Computing Centre.
:- use_module(library(clpfd)).
The arithmetic built in to prolog is traditionally of the form
A is 1+2,
B is A+3,
... etc.