Logic programming is overrated, at least for logic puzzles (2013)
programming-puzzler.blogspot.com
Logic programming is overrated, at least for logic puzzles (2013)
1–10 of 43 posts
Re: Logic programming is overrated, at least for logic puzzles (2013)
#2What you really want for logic puzzles is a SAT or SMT solver as it gets the same results as exhaustive search except it usually can eliminate large amounts of the search space. A language like Prolog superficially looks like it can solve logic puzzles natively but the search strategy is usually too limited.
Re: Logic programming is overrated, at least for logic puzzles (2013)
#3What you really want for logic puzzles is a SAT or SMT solver as it gets the same results as exhaustive search except it usually can eliminate large amounts of the search space. A language like Prolog superficially looks like it can solve logic puzzles natively but the search strategy is usually too limited.
Which you don't even have to bother with if the search space is small, like a dozen Boolean variables or whatever.
Re: Logic programming is overrated, at least for logic puzzles (2013)
#4What you really want for logic puzzles is a SAT or SMT solver as it gets the same results as exhaustive search except it usually can eliminate large amounts of the search space. A language like Prolog superficially looks like it can solve logic puzzles natively but the search strategy is usually too limited.
Which you don't even have to bother with if the search space is small, like a dozen Boolean variables or whatever.
Granted, but if the tools were ergonomic it would be easier to use the SAT solver and, in the habit, you might find more problems they are good for.
Re: Logic programming is overrated, at least for logic puzzles (2013)
#5What you really want for logic puzzles is a SAT or SMT solver as it gets the same results as exhaustive search except it usually can eliminate large amounts of the search space. A language like Prolog superficially looks like it can solve logic puzzles natively but the search strategy is usually too limited.
Which you don't even have to bother with if the search space is small, like a dozen Boolean variables or whatever.
That's also true about sorting algorithms: Why bother with anything other than bubble sort if you only have a dozen or so items to sort? Because many real world problems are larger than that.
Re: Logic programming is overrated, at least for logic puzzles (2013)
#6For me, I think the problem is that normal, boring, stupid, unsophisticated, plebian imperative programming lives in a world of O(1) operations. That is to say, a "normal" line of code you type will be O(1), and then you generally start gluing those together with various things that start stacking on O(n) complexities. As things like the accidentally quadratic blog [1], in the normal programming world it is a bit humorous to even so much as accidentally stack two of those things unnecessarily on top of each other.
Certainly, people manage to make poorly performing things even so, but at least at the base level, your primitives may be stupid, but they are generally fast.
The logic programming world works in a default space of O(n) operations, that stack together more freely than the imperative world, and that gives easy access to O(2^n). Since this is essentially impossible, a great deal of work is done to try to get that down, but you're always intrinsically starting behind the eight-ball. It is easier to work up from O(1) operations than to write an exponential or super-exponential algorithm and then try to trim it back down to a decent complexity for a normal programmer.
I think this is the root cause as to why logic programming is generally not something we see a lot of. It's like a wild stallion; it may be powerful but the amount of effort you pour into just keeping it under control may exceed any benefit you could get.
It isn't useless, of course. Amazing work has been done in the field of SAT solvers, and there's certainly a niche for it. The problems that are intrinsically higher-order polynomials or (technically) exponential, well, they are what they are and if you're going to be stuck in that world, logic programming may offer you a much better toolset than conventional programming on its own. But there was a hope a long time ago, in the Prolog era, that it could become part of the normal toolkit of general purpose programming, and I don't think that will ever happen, because of this line of logic.
This is a bit tangential to the article, it's just what I happened to read that finally crystallized this in my mind.
Re: Logic programming is overrated, at least for logic puzzles (2013)
#7I've only done a bit of prolog programming, but from what i've seen so far it feels like "logic" is the wrong lense.
It feels more like its based around describing a graph, where some verticies have side effects, and then releasing DFS on the graph. I'd call it DFS programming, but also im a noob at it, so maybe more experienced people would disagree.
Re: Logic programming is overrated, at least for logic puzzles (2013)
#8For me, I think the problem is that normal, boring, stupid, unsophisticated, plebian imperative programming lives in a world of O(1) operations. That is to say, a "normal" line of code you type will be O(1), and then you generally start gluing those together with various things that start stacking on O(n) complexities. As things like the accidentally quadratic blog [1], in the normal programming world it is a bit hum…
I took a comparative programming languages class in 1993 and the prof said that he thought Prolog was the future.
It had numerous setbacks. The Japanese thought they could parallelize Prolog programs for their Fifth Generation Computing Project in the 1980s but found out quickly that you couldn't. They made a language called KL1 which was parallelizable, but it wasn't as good as Prolog in other respects.
The ability to implement simple parsers in the Prolog using its evaluation process impressed me a lot when I didn't know much about parsers, now that I know how to implement parsers it doesn't impress me much.
You can write mixed logical/imperative problems in Prolog but boy is it awkward.
When I got interested in RDF circa 2010 I was interested in Datalog (a pure logical language) but found nobody else seemed interested in it and it was hard to find literature on it. That situation has changed a lot as Datalog is a pretty clear way to make database query code composable.
Production rules engines (say Drools) are another "old A.I." technology that is largely forgotten even though they are heavily used in banks and a few other corners of the business world. These implement “forward chaining” inference distinct from the “backward chaining” inference implemented in Prolog. Between RETE engines and effective indexing structures it is easy to handle 1000x's more rules in your knowledge base in the 1980s but production rules never got standardized like C, FORTRAN or COBOL and no really general answers have come up for questions like controlling the order of execution when that matters.
Re: Logic programming is overrated, at least for logic puzzles (2013)
#9What you really want for logic puzzles is a SAT or SMT solver as it gets the same results as exhaustive search except it usually can eliminate large amounts of the search space. A language like Prolog superficially looks like it can solve logic puzzles natively but the search strategy is usually too limited.
Except you first have to encode the problem as a logic expression over (potentially tens of thousands of) Boolean variables. Might be impractical, or might even be impossible for eg robotic planning with an unlimited number of planning steps, and doesn't necessarily extend well to solving with respect to an objective function (eg optimization). What you usually see is a domain-specific problem description/language that then gets compiled into a SAT problem using a custom transformator/generator program. In other words, the problem of a suitable problem description language isn't solved ;)
You can override/customize Prolog's default search strategy as desired, Prolog being Turing-complete. Prolog syntax and resolution in this case just provides a straightforward starting point; which is much needed as you explore the complexities and challenges of your problem domain to kick-off a project (you know, as opposed to prematurely optimizing a program for transforming you DSL into a SAT/SMT formulation). I think Prolog works very well for this.
Note Prolog also has libraries for offloading to SAT solvers and eg. z3 supports a Datalog subset as an alternative to SMTLIB/Lisp-like syntax.
Re: Logic programming is overrated, at least for logic puzzles (2013)
#10For me, I think the problem is that normal, boring, stupid, unsophisticated, plebian imperative programming lives in a world of O(1) operations. That is to say, a "normal" line of code you type will be O(1), and then you generally start gluing those together with various things that start stacking on O(n) complexities. As things like the accidentally quadratic blog [1], in the normal programming world it is a bit hum…
In my experience, performance concerns have rarely been priority or the primary blocking issue with software development. With Prolog, you can often write entire programs in just a few lines that would require hundreds of lines in another language, which would likely contain the same performance pitfalls of the Prolog code.