News for hackers. Stuff that matters.
Re:Logic programming is overrated, at least for logic puzzle... by PaulHoule on Thursday June 01, 2023 @01:14PM (#36154238)
What 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 amount 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 puzzle... by kazinator on Thursday June 01, 2023 @01:23PM (#36154392)
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 puzzle... by Jtsummers on Thursday June 01, 2023 @01:41PM (#36154644)
* * *
Re:Logic programming is overrated, at least for logic puzzle... by gowld on Thursday June 01, 2023 @02:43PM (#36155508)
But the context of OP is for human-scale puzzles.
Re:Logic programming is overrated, at least for logic puzzle... by Jtsummers on Thursday June 01, 2023 @03:04PM (#36155831)
Human-scale puzzles can still have search spaces in the billions and trillions and beyond. You want a SAT/SMT solver that can reduce the search space rapidly or a constraint propagation system that can similarly reduce the search space if you code up solutions to them.
Re:Logic programming is overrated, at least for logic puzzle... by kazinator on Thursday June 01, 2023 @09:32PM (#36159784)
* * *
Re:Logic programming is overrated, at least for logic puzzle... by kazinator on Thursday June 01, 2023 @08:21PM (#36159263)
Hey, worked for someone working on FreeBSD sysinits

https://news.ycombinator.com/item?id=36002574

I'm referring only to logic puzzles, nothing general. You probably don't have to whip out a SAT solver for logic puzzles.

Re:Logic programming is overrated, at least for logic puzzle... by PaulHoule on Thursday June 01, 2023 @01:35PM (#36154549)
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 puzzle... by tannhaeuser on Thursday June 01, 2023 @02:10PM (#36155035)
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 puzzle... by gowld on Thursday June 01, 2023 @02:42PM (#36155493)
GHC for Haskell for example has a graph-reduction runtime, and a lot of effort goes into optimizing that to use referential transparency and laziness effectively.

Prolog is similar (even more so) an example of a high-level declarative language with an optimizing runtime, but (I guess) isn't as optimized. Prolog runtime could incorporate a SAT or SMT solver internally, without changind the language, right?

Re:Logic programming is overrated, at least for logic puzzle... by slaymaker1907 on Thursday June 01, 2023 @06:14PM (#36158146)
Not really because of the cut operator. It can be optimized with tricks like tabling, but changing the evaluation order is generally unsafe. I think a larger aspect is that a SAT/SMT solver introduces an even more confusing black box than Prolog's evaluation strategy. You can reason about the performance of Prolog programs in ways that you just can't with SAT/SMT solvers.