Comment by falsissime | Hacker News Reader

Comment by falsissime | Hacker News Reader

Parent Full thread

> If Colmerauer had his way, Prolog would be a quick and dirty programming language fit to replace javascript or C.

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

Thanks for trying to correct me, if I'm wrong (but thanks anyway). What I write is the impression I've formed after reading various sources on the history of Prolog, over the years. Some of them are even by Kowalski himself and my impression that he was the "neat" and Colmerauer the "scruffy" comes from his comments on their relation. I certainly could have misunderstood his comments, or be misremembering them. Unfortunately it will take me some time to dig out the specific sources and check my assumptions [1].

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?

> [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.

Just to note one error in I.2.1:

> ... 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.

Yes, I see, that doesn't make sense.

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.

Consider to set the flag to "error" to see if there are any cases where infinite terms would be created.

>> 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...

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!

> 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).

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.

Reply on news.ycombinator.com