6 ms·

Can anyone give examples of the kinds of problems prolog is ideally suited to? I took a course on it at university. It looked interesting but I didn't really "g

Can anyone give examples of the kinds of problems prolog is ideally suited to? I took a course on it at university. It looked interesting but I didn't really "get it". It might be worth another look now I have a bit more experience under my belt. I've got a lingering feeling it would solve a certain kind of problem very easily.

ahelwer 10y ago
It's pretty much Backtracking as a language. So stuff like N Queens, Einstein's Puzzle (the Englishman lives in the red house, the Swede in the blue house, etc.) and so on. Any time you want to write down the rules of a discrete system and ask questions about the properties of that system, Prolog is a great way to do it. One practical application: it's very easy to write the logic for a network firewall in Prolog.
- lacampbell 10y ago
  ah! backtracking. combinatorial optimisation would be incredibly useful for me. if prolog is indeed backtracking as a language I definitely need to look into it.
  - tom_mellior 10y ago
    It is indeed backtracking as a language, but you don't get optimization entirely for free. The backtracking part only means that you can write down a problem that has multiple solutions and get Prolog to enumerate those solutions using its default order. If the set of solutions is small enough, you can enumerate all of them and pick out the best one, or have it enumerate them until you get one that is good enough. But if you need a smarter exploration of the search space, you will (in general) have to write that yourself. Many implementations include an integer constraints library that will give you functionality similar to an ILP solver, which may or may not fit your domain.
    - bloaf 10y ago
      Would it work well for algorithms like A*, or other quazi-AI problems that crop up in games?
      - tom_mellior 10y ago
        Yes, but you shouldn't expect it to have much more magic support for this kind of algorithms than other languages.
- insulanian 10y ago
  Is it possible to do that kind of stuff (e.g. Einstein's Puzzle) in Haskell/OCaml/F# and how would one approach it?
  - tom_mellior 10y ago
    Yes, it's possible. Most approaches use brute-force search, just like the simpler Prolog variants: http://rosettacode.org/wiki/Zebra_puzzle http://rosettacode.org/wiki/Zebra_puzzle
tom_mellior 10y ago
I've used it with enjoyment and success in several programming language projects (compilation, program analysis). It's well suited for these things for the same reason that languages like OCaml and Haskell are well suited and commonly used for them: algebraic data types and pattern matching (called terms and unification in Prolog, and a bit more powerful than simple pattern matching). You can more easily and directly access your data than is usual in imperative or object-oriented languages. I do note that this is a domain where you have less need to "get" the backtracking search part of Prolog, it's more like functional programming. The point being that you can do useful programming, even imperative, in Prolog, not only logical "automatically exploring a large search space" stuff. It's a general-purpose programming language plus a search system that you can choose to use or ignore as it fits your problem. But yeah, it's not usually presented as such.
kdtg 10y ago
Intractable problems i.e., the ones that can't be solve in polynomial time. Logic programming in general is NP-Hard, so it's suitable for NP-Hard problems (constraint satisfaction problems, backtracking, etc). If you try to solve polynomial problems, it doesn't perform well.

ahelwer 10y ago

It's pretty much Backtracking as a language. So stuff like N Queens, Einstein's Puzzle (the Englishman lives in the red house, the Swede in the blue house, etc.) and so on. Any time you want to write down the rules of a discrete system and ask questions about the properties of that system, Prolog is a great way to do it. One practical application: it's very easy to write the logic for a network firewall in Prolog.

lacampbell 10y ago
ah! backtracking. combinatorial optimisation would be incredibly useful for me. if prolog is indeed backtracking as a language I definitely need to look into it.
- tom_mellior 10y ago
  It is indeed backtracking as a language, but you don't get optimization entirely for free. The backtracking part only means that you can write down a problem that has multiple solutions and get Prolog to enumerate those solutions using its default order. If the set of solutions is small enough, you can enumerate all of them and pick out the best one, or have it enumerate them until you get one that is good enough. But if you need a smarter exploration of the search space, you will (in general) have to write that yourself. Many implementations include an integer constraints library that will give you functionality similar to an ILP solver, which may or may not fit your domain.
  - bloaf 10y ago
    Would it work well for algorithms like A*, or other quazi-AI problems that crop up in games?
    - tom_mellior 10y ago
      Yes, but you shouldn't expect it to have much more magic support for this kind of algorithms than other languages.
insulanian 10y ago
Is it possible to do that kind of stuff (e.g. Einstein's Puzzle) in Haskell/OCaml/F# and how would one approach it?
- tom_mellior 10y ago
  Yes, it's possible. Most approaches use brute-force search, just like the simpler Prolog variants: http://rosettacode.org/wiki/Zebra_puzzle http://rosettacode.org/wiki/Zebra_puzzle

tom_mellior 10y ago

I've used it with enjoyment and success in several programming language projects (compilation, program analysis). It's well suited for these things for the same reason that languages like OCaml and Haskell are well suited and commonly used for them: algebraic data types and pattern matching (called terms and unification in Prolog, and a bit more powerful than simple pattern matching). You can more easily and directly access your data than is usual in imperative or object-oriented languages. I do note that this is a domain where you have less need to "get" the backtracking search part of Prolog, it's more like functional programming. The point being that you can do useful programming, even imperative, in Prolog, not only logical "automatically exploring a large search space" stuff. It's a general-purpose programming language plus a search system that you can choose to use or ignore as it fits your problem. But yeah, it's not usually presented as such.

kdtg 10y ago

Intractable problems i.e., the ones that can't be solve in polynomial time. Logic programming in general is NP-Hard, so it's suitable for NP-Hard problems (constraint satisfaction problems, backtracking, etc). If you try to solve polynomial problems, it doesn't perform well.