10 ms·

If you're trying to solve boolean satisfiability, you want a SAT solver, not Prolog. If you're trying to solve more general problems, you probably want an SMT

If you're trying to solve boolean satisfiability, you want a SAT solver, not Prolog. If you're trying to solve more general problems, you probably want an SMT solver or other more specific solver (e.g., ILP), not Prolog. If you're trying to verify software, you want a theorem prover, not Prolog. If you want database-ish stuff you want Datalog (or something like it), not Prolog. Prolog falls into the uncanny valley of being too general of a DSL for the sorts of optimizations that more narrow solvers enjoy, while being too narrow of a DSL for most general-purpose programming. I think because it was an early DSL, people got caught up in the idea of it being more "high-level" than other languages [1], but the DSL nature of it wasn't fully appreciated at the time. [1]: For fun, take a read through https://en.wikipedia.org/wiki/Fifth-generation_programming_language https://en.wikipedia.org/wiki/Fifth-generation_programming_l... , which was a whole thing in the 1980s.

jjtheblunt 3y ago
above is a fantastic lucid comment (not kidding)
usgroup 3y ago
I don’t think those are the problems since all sorts of solvers ship with prolog and it’s still a better way to write down a problem. I think it’s biggest headwind is that you have to be significantly more intelligent than the average developer to think in Prolog. Prolog requires you to think about code as the implication of constraints — you just have to keep a lot more in your head. Prolog also requires you to understand the execution model before you can do much of anything.
- nerdponx 3y ago
  What about Prolog as an embedded constraint-solving engine inside an application written in some other host language?
  - usgroup 3y ago
    I think embedding Prolog is a common use case for it, but I think “constraint solver” is the wrong metaphor. Use Prolog to “reason about X”, is closer to the gist.
  - christmm 3y ago
    [dead]
- discarded1023 3y ago
  > Prolog also requires you to understand the execution model before you can do much of anything. This is true of most (all?) languages. Prolog's control flow is ultimately not too different from the usual stack-based semantics people are used to from imperative languages like C (if you're not too ambitious with the backtracking; if you are, best of luck!). The tricky part is perhaps understanding the dataflow that arises from unification. That can be arbitrarily complex but it seems people tend to go no further than difference structures, which are easy to comprehend in terms of pointers. (Yes yes I know, but logic variables are essentially just single-assignment pointers.) The thing I find deeply weird about the logic programming literature is that if you want to reason about your program you're told to use things like Hoare logic [1] or intended interpretations [2] and not fundamental logical concepts like implementations implying specifications (ala Lamport and many others who grappled with refinement). [1] see Krzysztof Apt's papers [2] see e.g. https://people.eng.unimelb.edu.au/lee/papers/dd.html https://people.eng.unimelb.edu.au/lee/papers/dd.html
  - usgroup 3y ago
    > This is true of most (all?) languages. Well no, I’d go as far as to say that your average JS/Python dev will know very little about how their code is executed — and doesn’t need to know necessarily. SQL on the other hand is a different story . Noobs don’t know , but pros know and consider the execution graph of a query. You don’t really have a choice in Prolog —- gotta know what the interpreter is doing from the beginning otherwise you can’t debug.
    - felixyz 3y ago
      It't just that everyone has the execution model of imperative languages so internalized, we mostly don't think about it. Same with OO semantics, not to mention various JS pitfalls - they are second nature to enough people that they count as nature-given, but one false move and they come back to bite you.
      - convolvatron 3y ago
        It’s worth pointing out that the semantics of prodcedural programs tend to be pairwise, while coaxing the prolog solver to terminate is a more global, transitive problem
- rurban 3y ago
  > I think it’s biggest headwind is that you have to be significantly more intelligent than the average developer to think in Prolog. This is arguably wrong. Thinking in Prolog is much easier than knowing how to solve a problem beforehand. In Prolog you just state the facts and known rules, but you have no clear idea what would be the best way to solve it. Prolog solves it for you then, if possible. No intelligence needed. A "dumb" friend of mine on the 80ies only used Prolog for his work and was very happy with it. Lisp, Pascal or C was too hard for him. The problem with Prolog is mostly that you'll through too hard problems at it, mostly with exponential complexity. Tiny changes have huge influences then, it either works or not. Also the tabling and SAT/SMT integration sucks.
  - hnfong 3y ago
    The problem with your claims is that once you start “debugging”, it gets complicated quickly. You’ll have to gain an intuition of how the language actually tries so solve the problem under the hood. sometimes the problem you encounter doesn’t match the capabilities of the language, and then you’ll have to state the problem in a roundabout way to coax the language to do what you intended. It’s probably great for the small number of toy problems that it was designed to solve, but in my limited experience prolog doesn’t do well on real world problems that have all sorts of edge cases and dirty inputs.
    - forgetfulness 3y ago
      You see this often in the data side of things, we delegate very laborious or very complicated tasks to powerful the powerful engines behind Postgres, BigQuery, Spark, and the like, and while they provide you with a high level interface that make common tasks very convenient, mastery can take years as you have to study the architecture and implementation behind them. It's a huge investment on your end to do that, and people do it readily because the return is being able to process datasets of sizes and complexity that you otherwise wouldn't be able to. People haven't found it to be a good investment in their time to commit themselves to Prolog's engine.
  - logicmoo 3y ago
    -------- > Thinking in Prolog is much easier than knowing how to solve a problem beforehand. In Prolog you just state the facts and known rules, but you have no clear idea what would be the best way to solve it. While Prolog streamlines certain aspects of problem-solving due to its declarative nature, it still necessitates a clear understanding of the desired solution and the proper organization of facts and rules. Although Prolog's approach abstracts some implementation details, a well-planned strategy remains essential. -------- > No intelligence needed. Prolog might make some tasks seem simpler, but intelligence and a deep comprehension of logic programming are still needed to efficiently create and maintain solutions. -------- > A "dumb" friend of mine on the 80ies only used Prolog for his work and was very happy with it. Lisp, Pascal or C was too hard for him. I may be the "dumb" friend you referred to? Consider this: someone skilled in producing valuable software using Prolog is likely knowledgeable and proficient enough to program professionally in various other languages, such as C, Lisp, C#, C++, Scala, Java, Pascal, Python, Assembly, and more. As an experienced programmer with a strong background in multiple languages, I often receive requests to translate my Prolog software into languages like Python, Java, or C#. However, I usually decline and claim that "it would be too hard" -------- > The problem with Prolog is mostly that you'll throw too hard problems at it, mostly with exponential complexity. Prolog isn't inherently prone to exponential complexity problems. The complexity depends on the problem being solved and how the facts and rules are structured. It's crucial to understand the problem domain and optimize the Prolog code accordingly The complexity of a problem and fluid nature of flow control shifts during software runtime often make it unfeasible to implement the software in alternative languages. So consequently, in the rare instances when I or others have attempted this, we have either developed or found a Prolog interpreter in the target language and executed the original code. Had these tasks not been so daunting, others would have already implemented solutions to them in different languages, and there would be no need for people to continually request my assistance! -------- > Tiny changes have huge influences then, it either works or not. While it is true that small changes can sometimes have significant impacts on the behavior of a Prolog program, this is not unique to Prolog. Any programming language can experience similar issues if the underlying logic is not well-designed or properly tested. It is the developer's responsibility to understand the problem domain and design the logic appropriately to avoid unintended consequences. -------- > Also the tabling and SAT/SMT integration sucks. Tabling is a technique used in Prolog to store intermediate results of a computation to avoid redundant sub-computations, thus improving the efficiency of certain types of queries. While it may have some limitations, it is generally considered a valuable feature of Prolog that can enhance performance for specific types of problems. Prolog's integration with SAT (Boolean Satisfiability) and SMT (Satisfiability Modulo Theories) solvers is not inherently flawed. Prolog can be used effectively in combination with these solvers to tackle complex problems in various domains. Integrating Prolog with these solvers might require a good understanding of the solver's functionality and the problem domain, but the same can be said for integrating any other programming language with these solvers. It's important to leverage the latest Prolog tools and libraries to optimize these aspects of your program.
- JimmyRuska 3y ago
  Prolog solvers don't necessarily optimize like gurobi, cplex or OR-tools would. Yes they can give you a solution that satisfies the constraints, and you can query for more possible answers, but it doesn't really optimize for the objective function in the same way.
- deleted 3y ago
  [deleted]
- logicmoo 3y ago
  > I think it’s biggest headwind is that you have to be significantly more intelligent than the average developer to think in Prolog. This is very true!
User23 3y ago
The Norvig AI book really makes its nature as a DSL clear.
otabdeveloper4 3y ago
Solvers are integrated into Prolog nowadays, like the other commenter said. The real problem is that Prolog doesn't play nice with relational databases. (Too bad the people behind the short-lived NoSQL fad didn't know about Prolog, though.)
- baq 3y ago
  Smuggle a Prolog in YAML somewhere, call it YAMLogic or anything else really which can’t be directly traced to it and watch the kids be amazed at what you can make computers do. Only about 33% serious here, but… still a bit serious.
maweki 3y ago
Prolog being tied to this very specific execution model of SLD resolution is somewhat root to the problems you have described. The promise of declerative programming in general, and logic and constraint programming specifically is, that programs are easier to reason about because the execution model is abstracted away and there's a relatively simple and mathematically pure definition of the model(s) of a program. But again and again one uses extralogical constructs in Prolog programming. Case in point: basically all your mentioned alternatives (Datalog, SMT, I'd add ASP) have implementations that use the Prolog syntax or something close to it with very similar semantics. But not being tied to that specific execution model can give you (better) answers or more complete answers, termination guarantees, or other things we might need.
- usgroup 3y ago
  I don’t think is true because ASP is not more popular than Prolog but it is essential (or at least much moreso) declarative. I think Prologs big strength amongst others is the meta interpreter and higher order functions which I think are essentially tied to SLD.
  - discarded1023 3y ago
    Higher order functions! -- in Prolog! oh my. Prolog has predicates, not functions. (It has uninterpreted function symbols -- aka functors in this context.) It's based on first-order logic, i.e., it has nothing higher order in it, if you want to take it (formally) seriously. But of course there is `call/1` and so forth, which are just hacks... err, "non declarative". There are some interesting higher-order logic programming languages, e.g. Mercury. I like the approach taken by HiLog [1] as it struck me as (semantically) honest and simple. I don't know if it's usable. [1] https://en.wikipedia.org/wiki/HiLog https://en.wikipedia.org/wiki/HiLog
    - usgroup 3y ago
      * Higher order predicates. Prolog has them.
    - 3y ago
weinzierl 3y ago
That's a very apt description of where Prolog stands. The niche I see it fit in is as a teaching tool for first-order-logic in computer science (not necessarily math). At least that's how I learned it and I'm glad I did.
YeGoblynQueenne 3y ago
Prolog is not a DSL. Or I guess you can see it as a DSL where the "Domain" is the entire set of programs computable by a Universal Turing Machine. It's a DSL for writing programs that manipulate programs that manipulate programs. But, not really. It's just not a DSL.

jjtheblunt 3y ago

above is a fantastic lucid comment (not kidding)

usgroup 3y ago

I don’t think those are the problems since all sorts of solvers ship with prolog and it’s still a better way to write down a problem. I think it’s biggest headwind is that you have to be significantly more intelligent than the average developer to think in Prolog. Prolog requires you to think about code as the implication of constraints — you just have to keep a lot more in your head. Prolog also requires you to understand the execution model before you can do much of anything.

nerdponx 3y ago
What about Prolog as an embedded constraint-solving engine inside an application written in some other host language?
- usgroup 3y ago
  I think embedding Prolog is a common use case for it, but I think “constraint solver” is the wrong metaphor. Use Prolog to “reason about X”, is closer to the gist.
- christmm 3y ago
  [dead]
discarded1023 3y ago
> Prolog also requires you to understand the execution model before you can do much of anything. This is true of most (all?) languages. Prolog's control flow is ultimately not too different from the usual stack-based semantics people are used to from imperative languages like C (if you're not too ambitious with the backtracking; if you are, best of luck!). The tricky part is perhaps understanding the dataflow that arises from unification. That can be arbitrarily complex but it seems people tend to go no further than difference structures, which are easy to comprehend in terms of pointers. (Yes yes I know, but logic variables are essentially just single-assignment pointers.) The thing I find deeply weird about the logic programming literature is that if you want to reason about your program you're told to use things like Hoare logic [1] or intended interpretations [2] and not fundamental logical concepts like implementations implying specifications (ala Lamport and many others who grappled with refinement). [1] see Krzysztof Apt's papers [2] see e.g. https://people.eng.unimelb.edu.au/lee/papers/dd.html https://people.eng.unimelb.edu.au/lee/papers/dd.html
- usgroup 3y ago
  > This is true of most (all?) languages. Well no, I’d go as far as to say that your average JS/Python dev will know very little about how their code is executed — and doesn’t need to know necessarily. SQL on the other hand is a different story . Noobs don’t know , but pros know and consider the execution graph of a query. You don’t really have a choice in Prolog —- gotta know what the interpreter is doing from the beginning otherwise you can’t debug.
  - felixyz 3y ago
    It't just that everyone has the execution model of imperative languages so internalized, we mostly don't think about it. Same with OO semantics, not to mention various JS pitfalls - they are second nature to enough people that they count as nature-given, but one false move and they come back to bite you.
    - convolvatron 3y ago
      It’s worth pointing out that the semantics of prodcedural programs tend to be pairwise, while coaxing the prolog solver to terminate is a more global, transitive problem
rurban 3y ago
> I think it’s biggest headwind is that you have to be significantly more intelligent than the average developer to think in Prolog. This is arguably wrong. Thinking in Prolog is much easier than knowing how to solve a problem beforehand. In Prolog you just state the facts and known rules, but you have no clear idea what would be the best way to solve it. Prolog solves it for you then, if possible. No intelligence needed. A "dumb" friend of mine on the 80ies only used Prolog for his work and was very happy with it. Lisp, Pascal or C was too hard for him. The problem with Prolog is mostly that you'll through too hard problems at it, mostly with exponential complexity. Tiny changes have huge influences then, it either works or not. Also the tabling and SAT/SMT integration sucks.
- hnfong 3y ago
  The problem with your claims is that once you start “debugging”, it gets complicated quickly. You’ll have to gain an intuition of how the language actually tries so solve the problem under the hood. sometimes the problem you encounter doesn’t match the capabilities of the language, and then you’ll have to state the problem in a roundabout way to coax the language to do what you intended. It’s probably great for the small number of toy problems that it was designed to solve, but in my limited experience prolog doesn’t do well on real world problems that have all sorts of edge cases and dirty inputs.
  - forgetfulness 3y ago
    You see this often in the data side of things, we delegate very laborious or very complicated tasks to powerful the powerful engines behind Postgres, BigQuery, Spark, and the like, and while they provide you with a high level interface that make common tasks very convenient, mastery can take years as you have to study the architecture and implementation behind them. It's a huge investment on your end to do that, and people do it readily because the return is being able to process datasets of sizes and complexity that you otherwise wouldn't be able to. People haven't found it to be a good investment in their time to commit themselves to Prolog's engine.
- logicmoo 3y ago
  -------- > Thinking in Prolog is much easier than knowing how to solve a problem beforehand. In Prolog you just state the facts and known rules, but you have no clear idea what would be the best way to solve it. While Prolog streamlines certain aspects of problem-solving due to its declarative nature, it still necessitates a clear understanding of the desired solution and the proper organization of facts and rules. Although Prolog's approach abstracts some implementation details, a well-planned strategy remains essential. -------- > No intelligence needed. Prolog might make some tasks seem simpler, but intelligence and a deep comprehension of logic programming are still needed to efficiently create and maintain solutions. -------- > A "dumb" friend of mine on the 80ies only used Prolog for his work and was very happy with it. Lisp, Pascal or C was too hard for him. I may be the "dumb" friend you referred to? Consider this: someone skilled in producing valuable software using Prolog is likely knowledgeable and proficient enough to program professionally in various other languages, such as C, Lisp, C#, C++, Scala, Java, Pascal, Python, Assembly, and more. As an experienced programmer with a strong background in multiple languages, I often receive requests to translate my Prolog software into languages like Python, Java, or C#. However, I usually decline and claim that "it would be too hard" -------- > The problem with Prolog is mostly that you'll throw too hard problems at it, mostly with exponential complexity. Prolog isn't inherently prone to exponential complexity problems. The complexity depends on the problem being solved and how the facts and rules are structured. It's crucial to understand the problem domain and optimize the Prolog code accordingly The complexity of a problem and fluid nature of flow control shifts during software runtime often make it unfeasible to implement the software in alternative languages. So consequently, in the rare instances when I or others have attempted this, we have either developed or found a Prolog interpreter in the target language and executed the original code. Had these tasks not been so daunting, others would have already implemented solutions to them in different languages, and there would be no need for people to continually request my assistance! -------- > Tiny changes have huge influences then, it either works or not. While it is true that small changes can sometimes have significant impacts on the behavior of a Prolog program, this is not unique to Prolog. Any programming language can experience similar issues if the underlying logic is not well-designed or properly tested. It is the developer's responsibility to understand the problem domain and design the logic appropriately to avoid unintended consequences. -------- > Also the tabling and SAT/SMT integration sucks. Tabling is a technique used in Prolog to store intermediate results of a computation to avoid redundant sub-computations, thus improving the efficiency of certain types of queries. While it may have some limitations, it is generally considered a valuable feature of Prolog that can enhance performance for specific types of problems. Prolog's integration with SAT (Boolean Satisfiability) and SMT (Satisfiability Modulo Theories) solvers is not inherently flawed. Prolog can be used effectively in combination with these solvers to tackle complex problems in various domains. Integrating Prolog with these solvers might require a good understanding of the solver's functionality and the problem domain, but the same can be said for integrating any other programming language with these solvers. It's important to leverage the latest Prolog tools and libraries to optimize these aspects of your program.
JimmyRuska 3y ago
Prolog solvers don't necessarily optimize like gurobi, cplex or OR-tools would. Yes they can give you a solution that satisfies the constraints, and you can query for more possible answers, but it doesn't really optimize for the objective function in the same way.
deleted 3y ago
[deleted]
logicmoo 3y ago
> I think it’s biggest headwind is that you have to be significantly more intelligent than the average developer to think in Prolog. This is very true!

User23 3y ago

The Norvig AI book really makes its nature as a DSL clear.

otabdeveloper4 3y ago

Solvers are integrated into Prolog nowadays, like the other commenter said. The real problem is that Prolog doesn't play nice with relational databases. (Too bad the people behind the short-lived NoSQL fad didn't know about Prolog, though.)

baq 3y ago
Smuggle a Prolog in YAML somewhere, call it YAMLogic or anything else really which can’t be directly traced to it and watch the kids be amazed at what you can make computers do. Only about 33% serious here, but… still a bit serious.

maweki 3y ago

Prolog being tied to this very specific execution model of SLD resolution is somewhat root to the problems you have described. The promise of declerative programming in general, and logic and constraint programming specifically is, that programs are easier to reason about because the execution model is abstracted away and there's a relatively simple and mathematically pure definition of the model(s) of a program. But again and again one uses extralogical constructs in Prolog programming. Case in point: basically all your mentioned alternatives (Datalog, SMT, I'd add ASP) have implementations that use the Prolog syntax or something close to it with very similar semantics. But not being tied to that specific execution model can give you (better) answers or more complete answers, termination guarantees, or other things we might need.

usgroup 3y ago
I don’t think is true because ASP is not more popular than Prolog but it is essential (or at least much moreso) declarative. I think Prologs big strength amongst others is the meta interpreter and higher order functions which I think are essentially tied to SLD.
- discarded1023 3y ago
  Higher order functions! -- in Prolog! oh my. Prolog has predicates, not functions. (It has uninterpreted function symbols -- aka functors in this context.) It's based on first-order logic, i.e., it has nothing higher order in it, if you want to take it (formally) seriously. But of course there is `call/1` and so forth, which are just hacks... err, "non declarative". There are some interesting higher-order logic programming languages, e.g. Mercury. I like the approach taken by HiLog [1] as it struck me as (semantically) honest and simple. I don't know if it's usable. [1] https://en.wikipedia.org/wiki/HiLog https://en.wikipedia.org/wiki/HiLog
  - usgroup 3y ago
    * Higher order predicates. Prolog has them.
  - 3y ago

weinzierl 3y ago

That's a very apt description of where Prolog stands. The niche I see it fit in is as a teaching tool for first-order-logic in computer science (not necessarily math). At least that's how I learned it and I'm glad I did.

YeGoblynQueenne 3y ago

Prolog is not a DSL. Or I guess you can see it as a DSL where the "Domain" is the entire set of programs computable by a Universal Turing Machine. It's a DSL for writing programs that manipulate programs that manipulate programs. But, not really. It's just not a DSL.