59

What kind of problems is better solved in Prolog than in Haskell? What are the main differences between these two languages?

Edit

Is there a Haskell library (kind of a logical solver) that can mimic Prolog functionality?

nbro
  • 15,395
  • 32
  • 113
  • 196
danatel
  • 4,844
  • 11
  • 48
  • 62
  • 2
    That added question is good on its own. If there's some way to transfer gknauth's answer to a new question, you should ask it again so both will have their own high-quality answers. – Nathan Shively-Sanders Dec 21 '09 at 15:37
  • 2
    Have a look at the KiCS2 implementation of the Curry language — a dialect of Haskell that supports logic programming from the ground up. http://www-ps.informatik.uni-kiel.de/kics2/ & https://jeltsch.wordpress.com/2013/04/27/a-taste-of-curry/ – Erik Kaplun Jan 16 '16 at 21:11
  • Higher level languages have less-determinism than lower-level languages, and are more declarative. On the imperative - declarative spectrum: Assembler > C > Java/C# > Lisp/ML > Haskell > Prolog > natural language – aoeu256 Jul 14 '19 at 19:18
  • 1
    for the record, Prolog is pure like Haskell, but in a different sense: https://www.metalevel.at/prolog/purity – Erik Kaplun Nov 19 '19 at 13:55

5 Answers5

41

Regarding the logic library question: If it doesn't exist, it should be possible to build one a variety of ways. The Reasoned Schemer builds logical reasoning capabilities into Scheme. Chapters 33-34 of PLAI discuss Prolog and implementing Prolog. These authors are building bridges between Scheme and Prolog. The creators of PLT Scheme have built as one of their languages a Lazy Scheme after the lazy evaluation feature of Haskell. Oleg Kiselyov's LogicT paper is brilliant as usual--he pushes the boundary for what is possible in many languages. There is also a logic programming example on the Haskell Wiki.

Profpatsch
  • 4,918
  • 5
  • 27
  • 32
gknauth
  • 2,310
  • 2
  • 29
  • 44
37

Prolog is mainly a language targeted at logical problems, especially from the AI and linguistic fields. Haskell is more of a general-purpose language.

Prolog is declarative (logical) language, what makes it easier to state logical problems in it. Haskell is a functional language and hence much better suited to computational problems.

Wikipedia on declarative programming:

In computer science, declarative programming is a programming paradigm that expresses the logic of a computation without describing its control flow. It attempts to minimize or eliminate side effects by describing what the program should accomplish, rather than describing how to go about accomplishing it. This is in contrast from imperative programming, which requires a detailed description of the algorithm to be run.

Declarative programming consider programs as theories of a formal logic, and computations as deductions in that logic space. Declarative programming has become of particular interest recently, as it may greatly simplify writing parallel programs.

Wikipedia on functional programming:

In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state. Functional programming has its roots in the lambda calculus, a formal system developed in the 1930s to investigate function definition, function application, and recursion. Many functional programming languages can be viewed as embellishments to the lambda calculus.

In short a declarative language declares a set of rules about what outputs should result from which inputs and uses those rules to deduce an output from an input, while a functional language declares a set of mathematical or logical functions which define how input is translated to output.

As for the ADDED question : none that I know of but you can either translate Haskell to Prolog, or implement Prolog in Haskell :)

nbro
  • 15,395
  • 32
  • 113
  • 196
Kornel Kisielewicz
  • 55,802
  • 15
  • 111
  • 149
  • 76
    This answer is slightly misleading. Logic programming (Prolog) and functional programming (Haskell) are *both* declarative programming languages, but they represent different approaches to the declarative paradigm. – nedned Aug 04 '10 at 14:53
  • 4
    Haskell can be most likely translated into Prolog if the Prolog system has support for suspended goals. With suspended goals we can model lazy evaluation. But the translation will be a type erased program, since Prolog does not have types. –  Sep 10 '11 at 16:16
  • 3
    For those new to Prolog, the above answer is indeed a good answer. But be aware, the order of clauses in a Prolog goal does indeed matter greatly. Therefore the Wikipedia quote "declarative programming is a programming paradigm that expresses the logic of a computation without describing its control flow" might be misconstrued to mean that the order of the clauses in a goal doesn't matter, which would be wrong. The control flow of a Prolog program is very much affected by the order of the clauses in a goal, including the sequence that "red" cuts appear in clauses. – Robert Oschler Jan 25 '15 at 12:41
  • 2
    What @RobertOschler said is 100% true. Prolog processes by precedent, where the highest are :- and --> because they define the rules for how the program handles queries and builds search trees for the available facts. Prolog reads predicates top to bottom, and clauses left to right. Prolog is effectively a List based language, where clauses are separated into goals to be satisfied from left to right. A list of goals is defines a rule, where all goals must be met for the rule to apply. Prolog takes the first goal from the list, evaluates it, and if true it takes the next until the list is empty – G_V Jan 19 '18 at 11:55
34

Prolog is a logic programming language, whereas Haskell is a functional language. Functional languages are based on the concept of a function which takes a number of arguments and computes a value.

Prolog, on the other hand, does not have functions. Instead, predicates are used to prove a "theorem". Prolog predicates do not compute a value, they can answer "yes" or "no" and optionally bind input variables to values:

The usefulness of functional and logic programming often overlap. Functional programming has gained quite a bit of traction lately, while Prolog is still much a niche language, much due to the fact that it is much more different from the common concepts of functions and methods of mainstream OOP than functional programming is, and often considered (very) difficult to learn.

Certain problems become almost trivial to implement in Prolog, especially in combination with constraint solvers.

You can read more about logic programming on Wikipedia.

JesperE
  • 63,317
  • 21
  • 138
  • 197
  • 1
    Thank you for your valuable answer. It is a pity than only one best answer can be selected. – danatel Dec 20 '09 at 10:46
  • Definitely have to agree on Prolog being difficult to learn. I used it in two courses: AI to create an expert system, along with solving the water jug problem. In programming language concepts we used Prolog to do number problems, data structures so it was neat to see the two sides to the language. In programming languages, we used a dialect of Prolog called FP, which was written by the instructor, in Prolog. It introduced functional elements into prolog, allowing car, cdr, cons, tail/rest etc. We also learned how to implement our own back tracking search engines in imperative languages – Tanner Apr 30 '12 at 15:46
  • @Tanner It's mostly difficult to learn because in my experience most humans do not naturally think in logic trees, but in systems, which is more in line with OO programming. For example recognizing a chair as a concept is natural. You don't need to define each individual chair to recognize it as such. In Prolog, solving tree-based logic problems is very easy to implement compared to OO, but building systems with inputs and outputs that change state or return one predictable result are imo easier in OO based languages. – G_V Jan 19 '18 at 12:01
  • *Prolog, on the other hand, does not have functions. Instead, predicates are used to prove a "theorem".* It might be fairer to say that predicates are used to test assertions or, more plainly, to answer questions about the facts entered and conclusions drawable from them. Prolog, despite its impression of complexity, requires no advance experience of computing and is reasonably intuitive to new learners. It used to be taught in some colleges to freshmen. Now I think it's just Cambridge that do this. – Trunk Feb 25 '21 at 13:26
15

You might find the paper Escape from Zurg: An Exercise in Logic Programming an interesting read. It shows a side-by-side comparison of the implementation of a simple search problem in Prolog and Haskell, along with a little typeclass framework for representing search problems more generally. The conclusion that the authors come to is that expressing at least some of these types of problems in Haskell is easier than in Prolog, primarily because the Haskell type system makes it easier to come up with nice representations of search states and moves from state to state.

Ian Ross
  • 987
  • 8
  • 14
  • 2
    I guess we could refute the paper in many ways: Types are not necessary for higher order programming (I don't see any types in call/n), Haskell pattern matching and structure building could be slow compared to Prolog (didn't check it yet), the problem could make use of CLP (the <=60) (I don't see that Haskell has anything to offer here), etc.. –  Sep 10 '11 at 16:15
  • 7
    Mentioned paper contains Prolog programs clearly written by programmers not accustomed to the Prolog language. Example: Fig. 1, `trans/4`: `append/3` is used. A Prolog programmer would put the list into the head, making it a constant operation instead a linear one for each answer. – false Feb 20 '12 at 15:54
  • 1
    A [native Prolog](https://www.metalevel.at/zurg/). – false Apr 30 '17 at 08:49
-10

In reality there are only 2 languages:

  1. Machine language
  2. Human language.

All other languages in between are merely translators and nothing more. When we use the machine language we must think like the machine and when using human languages we think like humans.

The true job of a programmer is to think both ways. Some programming tools like the assembler force the programmer to spend a lot more time thinking like the machine. Other tools like Prolog allows us to spend more time thinking like a human.

There is a penalty to be paid at each extreme either in performance or in cost.

If the business logic of your application can be reduced to a set of rules and its output to a set of goals (for example writing a game of Chess) then Prolog is ideal. On the other hand if you need to take the input and tell the computer how to compute the output then a functional language would be more appropriate.

Square Rig Master
  • 644
  • 4
  • 7
  • 10
    If you have used Prolog much, you know that you spend most of your time thinking like a backtracking constraint-resolution machine rather than a human. :) Humans don't think like Prolog at all, although perhaps more than like a Turing machine. – Nathan Shively-Sanders Dec 21 '09 at 15:35
  • 4
    Perhaps I should backtrack given the constraints of the thread :) You are absoloutely right about the Turing machine. I have used and continue to use Prolog. In fact I still have my copy of Turbo Prolog on 5.1/4 inch double sided double density floppy disks in pristine condition. Perhaps I should take it to the comic book guy. – Square Rig Master Dec 21 '09 at 21:44
  • I'm not surprised this got -9 – PascalVKooten Nov 30 '16 at 07:53