How AI based programming could work

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

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.

: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