The Power of Prolog

Me too, please post!

I wrote some prolog for a PL class recently and had to debug some cases of nontermination caused by the depth-first-search unification algorithm. I was wondering why prolog (or some other logic programming language) couldn't use breadth-first search instead, to avoid those cases, but couldn't find answers online - could someone who knows prolog better here have an answer?

Disclaimer: My knowledge on this topic is not in depth (as I said, I'm still learning).

I haven't heard of Z3 but it says it's a theorem prover, so it would be comparable to systems like Coq, Isabelle, which are also considered programming languages, and then compared to Agda, Idris, and, last but not the least, Haskell.

So a distilled form of your question would be:

- How does logic programming compare to pure functional programming and programming based on type theory? For that I would probably try to read the following [1] before spending more time on it.

- How does Prolog compare to Haskell? For this I'd probably look at something like this [2]

I'm not too well-versed in the SML/OCaml/Haskell arena, but if I have to venture a guess, if we try to build a complex GOFAI system in prolog vs in haskell, the prolog system would have less amount of prolog code and most of the complexity would reside in the database of facts, whereas in haskell, all/most of the complexity would manifest in the form of haskell code.

Another difference would be that a logic programming system comes with a general purpose inference engine and you can build any expert system using it, but you have to provide the relevant knowledge base. Whereas Haskell comes with a custom-built inference engine (the Hindley-Milner type inference) that only knows about types (if you need to build an expert system in Haskell, you would first build a general purpose inference engine, and essentially a prolog-like system, before you do anything else).

On the flip side, Prolog program interpretation mechanism would probably be considered ad hoc, whereas Haskell program interpretation is based on type theory. So a Haskell programmer would probably have to worry less about program correctness.

[1] http://stackoverflow.com/questions/8297574

[2] http://stackoverflow.com/questions/1932770

EDIT: And theorem proving also connects to areas of model checking, specification languages, as well as compiler backend areas like operational/denotational semantics. Like I said it's a tangled web of many core CS areas.

EDIT 2: On further reading, Z3 is listed on this wikipedia page [3] as a constraint-programming (CP) library for an imperative language. The contrast between CP and CLP is mentioned on that page (as well as both Z3 and Prolog). (that also means Z3 is not really comparable to Coq, Isabelle as I said earlier. Coq, Isabelle are interactive theorem provers or proof assistants, not automatic theorem provers which is a lot harder to do). Another useful discussion [4]

[3] https://en.wikipedia.org/wiki/Constraint_programming

[4] http://cs.stackexchange.com/questions/14946

In Prolog you can "run your logic backwards".

In Java you can declare a list "my_list" and then ask for its length as in "my_list.size()". You can do the same in Prolog. Given the above Prolog definitions, here's an example of computing a list's length:

    | ?- list_length([13, 42], ListLength).

    ListLength = 2

    yes
    | ?- 

NOT VERY EXCITING.

But wait, you can run your logic BACKWARD. You can say instead, I have a list of length 2 -- what's inside the list??????

    | ?- list_length(MyList, 2).

    MyList = [_,_] ? 

    yes
    | ?- 

So that's strange. Prolog just gave us the form of an entity whose list-length is 2. And because we didn't say ANYTHING MORE SPECIFIC about the elements of the list, Prolog just gave us two placeholders for the items in the list ... '_' and '_'. Java can't do that out-of-the-box -- you can't say a list is size 2 and then ask for all the possible lists back.

In our backwards-running Prolog example, we might have attached other conditions to the elements of the list ... in which case Prolog would (possibly) not have returned placeholders for the elements of the list, but might have done further work to figure out proper values to put into the list to satisfy the further conditions we gave for them.

Prolog's mathematical foundation is sound but the devil is in the details, and very soon, you encounter two of Prolog's most glaring flaws that lead to spaghetti code worse than what even BASIC ever produced:

- It's dynamically typed

- The cut operator