[ScottBurson]

No, the problem was not that Prolog was too slow. The problem was that it was too stupid.

Prolog's strict left-to-right, depth-first search strategy allowed the implementations to be, in fact, quite fast. But that same strategy also kept it from being more than a small step toward true declarative programming, because Prolog programmers have to understand the order in which subgoals are tried. For example, consider a goal that can be satisfied by either of two clauses, which we'll call A and B, and where every problem instance can be solved by exactly one of these; however, clause A always completes (either succeeding or failing) in constant time, but clause B, if invoked on an instance that would cause it to fail, goes into infinite recursion (an easy thing to do by accident in Prolog). It's imperative (ha!) for the Prolog programmer to make sure that clause A is tried before B.

This kind of thing comes up all the time in Prolog programming. On the one hand, you have to be aware of the order of operations so you don't cause infinite recursions (or, short of that, cause your program to take exponential time); on the other, Prolog programmers frequently exploit the left-to-right, depth-first strategy by using the operator known as the "cut". The cut is a non-logical operator in the sense that its semantics can be expressed only by reference to the Prolog search order.

Programs written in a true declarative language might superficially look a lot like Prolog programs, but the implementation would need to be much smarter -- doing things like figuring out the correct order of operations on its own. (I think machine learning might actually turn out to help with this.)

Anyway the problem with your suggestion that we just need to throw more hardware at Prolog should be evident by this point. It doesn't matter how fast your machine is if your algorithm is exponential in the typical case (never mind if it contains an infinite recursion!).

[YeGoblynQueenne]

>> The problem was that it was too stupid.

It's ... a programming language? It's Turing complete. Nobody said it's intelligent.

>> It's imperative (ha!) for the Prolog programmer to make sure that clause A is tried before B.

That is one of those cases where Prolog takes the pragmatic approach to allow efficient computation rather than sticking to "pure" semantics of the kind that tends to make a big mess of things just to keep things "clean" (like, oh, I don't know... monads?).

Btw, I've written reams and reams of Prolog in the last five or six years. The fact that your code has two readings, declarative and imperative is only a problem if you allow your mind to remain stuck in some purist definition of declarative programming that looks beautiful but doesn't really work.

If you accept that we live in an imperfect world, have to contend with primitive computers and limited resources of all kind, then Prolog is fine and miles and miles ahead of anything else in terms of declarative semantics. Even lisps have magickal and mysterious stuff like eval etc.

In actual Prolog programming practice the imperative reading means you can actually debug your code and follow it around as it falls over your own bugs. A purely declarative program would also be purely undebugable.

The dual semantics is only a problem if you don't understand the language. And in what language is that not what you'd expect?

>> Prolog programmers frequently exploit the left-to-right, depth-first strategy by using the operator known as the "cut".

No, let's say things the way they really are. The cut is there to allow a branch of the depth-first tree to be, well, cut. Correct, its semantics are purely imperative. Its real use though is to stop unnecessary searching and backtracking and therefore make your program more efficient.

It's not there to "exploit" anything. The fact that it can be exploited is troublesome, but so is all sorts of stuff in programming, like buffer overruns or sql injection. It sucks, but ... imperfect world, scarce resources etc.

>> your algorithm is exponential in the typical case

What? Why does your algorithm have to be exponential if it's in Prolog? What the hell are you on about?

[ScottBurson]

I guess my use of the term "stupid" made my post sound more pejorative than I meant it to be. I have enjoyed writing Prolog programs on occasion. Some of my best friends are Prolog programmers!

But I was trying to explain why Prolog is not the declarative language that we all hope for (well, a lot of us do, anyway) and that it initially appeared, to some, to be. And I think the answer to that is exactly what I said. That doesn't mean it's not a useful tool!

> [The cut is] not there to "exploit" anything. The fact that it can be exploited is troublesome, but so is all sorts of stuff in programming, like buffer overruns or sql injection.

Whoa! "Exploit" is a general term; it doesn't just refer to security vulnerabilities. Dictionary.com offers this definition for the verb: "to utilize, especially for profit; turn to practical account: to exploit a business opportunity". (The definition I would offer is "to take advantage of", which can mean to make use of a vulnerability, but doesn't have to: you can take advantage of a convenient feature of a program.)

So when I say people "exploit" the search strategy by using the cut, I mean only that they gain benefit from it; if the search strategy were not so well-defined, the cut would be unusable.

> Why does your algorithm have to be exponential if it's in Prolog? What the hell are you on about?

If you try to write a significant Prolog program without understanding the search strategy, as if it really were a declarative language, your program will wind up being exponential or worse. Merely throwing hardware at this problem won't fix it. That's all I'm saying. I agree I didn't say it well the first time.

[YeGoblynQueenne]

>> Some of my best friends are Prolog programmers!

:P

>> Whoa! "Exploit" is a general term; it doesn't just refer to security vulnerabilities.

Of course. I didn't mean it in that sense. Buffer overruns can be exploited for non-malicious purposes also. Basically, any quirk of any language or architecture, or really any system, can be exploited for whatever purpose. Let us pause for a second and reflect on The Story of Mel [1] as handed down to us by our forefathers and mothers of old.

So what I'm saying is that the cut is there to stop unnecessary backtracking and not to change the behaviour of your program, but of course there's nothing stopping some poor fool from using it in the latter manner, as indeed I've done too many times in the past myself, being the particularly foolish fool that I am. Prolog programmers even have a term for the two types of cut: "green" and "red", respectively. Any Prolog tutorial or bit of documentation will tell you that the cut is to be used sparingly and only to stop unnecessary backtracking, not to make your program change behaviour. The good ones go to some lengths to give you examples of what happens if you don't stick to the advice. If you screw up after that you have nobody to blame but your inexperience, and that gets better with time.

So the cut is dangerous, but that's all it is.

I learned to program with C# oddly, at the University of Hull in the UK. There, our programming 101 tutor explained why C#, or, hell, Java- and not C or C++. His point was that those other languages are more powerful but because of their power they give you the tools to cut yourself to pieces. He used a metaphor involving a chainsaw, that I don't remember very well (that was back in 2005, 11 years now). But basically his point was that a chainsaw is powerful but you can really hurt yourself with it if you don't know how to use it, so you don't want to start learning ... er, forestry? with one.

Well, think of Prolog as a particularly dangerous language. I will admit this: Prolog is not your friend. It doesn't even try to make things easy for you. It's not an "easy language to pick up and start hacking in immediately". It takes a long time to learn it well and it keeps surprising you in very nasty ways for a very long time.

But- once you've learned it pays back in spades and you can do stuff in it that you can really not do in any other language, like declare grammars and then execute them, and use them to parse strings and generate strings. Or run your code backwards. Or do list appends in single-steps and so on.

Well. Apologies, that got a bit out of hand.

[1] http://www.catb.org/jargon/html/story-of-mel.html