Meh. As usual, functional programmers look at Prolog and completely miss the point. "Classical Prolog" (which part?) is "all about nondeterminism"?

The nondeterminism in Prolog comes from the completeness of SLD-Resolution as an inference rule. Because SLD-Resolution is complete [1], it can find every proof that exists. When there are many proofs, it is natural to have some mechanism to represent them all. Prolog does that by backtracking and trying different branches of a proof, hierarchically.

Parsing is indeed a good example of this. When a grammar is ambiguous, a string may have multiple different parses. But if a grammar is ambiguous, that's because the language it represents is ambiguous, and that means we want to represent the ambiguity, and have multiple parses. That is where a mechanism for nondeterministic return of all results is needed. A parser written in Prolog [2] will naturally backtrack and get all parses of a string.

So how about that maudlin cut, that people, like the authors of the article above, have bitched and moaned about, since the creation of Prolog? Well the cut clearly exists to avoid reaching unwanted branches of a proof, or in other words, to avoid unwanted backtracking.

But why then is there unwanted backtracking? The reason for unwanted backtracking is, invariably, that a program is over-general. In over-generalising, the program non-deterministically generates results that the programmer did not want, even as it returns (hopefully first) the results that the programmer wants. But human programmers are not perfect, and sometimes it can be too hard to write a program that is exactly as general, and as specific, as one wants, especially when the program crosses some threshold of size beyond which it is difficult to keep all of one's ducks in a row and understand exactly the behaviour of every single sub-program (i.e. predicate definition). That is when the cut is needed. The cut is a time-saver that keeps you from having to rewrite your entire program from scratch, multiple times, just because you are an imperfect programmer, and you cannot handle the full might of a programming language with Universal Turing Machine expressivity.

And more esoterically, perhaps, unwanted non-determinism arises because Resolution is semi-decidable, meaning that if a proof exists, Resultion will find it, but if a proof does not exist, it will keep trying forever. And that is the best that can be achieved under the Church-Turing thesis, and if you are unhappy with that, you can take your case with Mr. Gödel. In the meantime, you can use the cut to avoid your program going haywire, when you can tell (but the Prolog interpreter can't, because Church-Turing) that a program will loop forever after succeeding n times.

The authors say that "Classical Prolog" (really, what is that?) is not a "general purpose programming language". It is. Thanks to the cut. Now shoo, go code in your functional languages, which are safe and easy. Don't mess with my Prolog because you don't understand it.

___________________

[1] More precisely, SLD-Resolution is both sound and refutation complete.

[2] Generally, as a Definite Clause Grammar.

[3] https://www.doc.ic.ac.uk/~rak/papers/IFIP%2074.pdf