Logic programming is overrated, at least for logic puzzles (2013) • Hacker News Board

Re: Logic programming is overrated, at least for logic puzzles (2013)

#11

Post by lurquer » Thu, Jun 01, 2023, 6:30 PM UTC

I’ve written programs to solve and create those grid-style logic puzzles (such as “Five men went to dinner. Mr Brown ordered fish. The man with the red hat ordered lamb. The person who ordered beef was not Mr. White… etc.)

Once you have a way of encoding the clues into a machine-readable syntax, it’s trivial to solve. But, the tricky part is creating a good puzzle that can be solved by a human without guessing. That’s an art form. A brute-force solver won’t suffice to analyze your randomly generated sets of clues; instead, you need a solver that is only capable of making the types of deductions a human could make. Very subjective.

Re: Logic programming is overrated, at least for logic puzzles (2013)

#12

Post by jerf » Thu, Jun 01, 2023, 6:34 PM UTC

PaulHoule wrote: post #8

jerf wrote: post #6

For 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…

"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."

One of the lessons I'm still trying to absorb is how convinced we all were (and many still are) that there must be a ton of implicit parallelism in the world, but once we went looking for it, it turned out there was hardly any.

I've been chewing on this for years, trying to figure out whether this is something true about the world, true about the problems we try to solve, or because of the pervasive use of the imperative paradigm which is highly ordered and makes it very easy to impose ordering constraints. Now, clearly, the latter is a non-trivial component... but I still struggle with whether it is a full answer, because when people sat down with clean sheets of paper and tried to solve problems with extensive parallelism, they've largely failed to get more than low single-digit speedup factors. Non-imperative paradigms like logic programming have been tried, especially in these projects.

It isn't exactly news that our intuitive beliefs about our code and the real characteristics it has is quite out of whack. This underlies the pervasive advice to just go grab a profiler whenever you're trying to accelerate some code because even experts in the field with decades of experience are routinely completely wrong about what is slow in some bit of code. This is one particular aspect I'm still struggling with. It still feels like there should be so much more parallelism available....

Re: Logic programming is overrated, at least for logic puzzles (2013)

#13

Post by i_am_a_peasant » Thu, Jun 01, 2023, 6:39 PM UTC

bawolff wrote: post #7

I'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.

Sort of same as you except I just think of it as "constraint oriented programming"

Re: Logic programming is overrated, at least for logic puzzles (2013)

#14

Post by gowld » Thu, Jun 01, 2023, 6:42 PM UTC

PaulHoule wrote: post #2

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 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.

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 puzzles (2013)

#15

Post by gowld » Thu, Jun 01, 2023, 6:43 PM UTC

Jtsummers wrote: post #5

kazinator wrote: post #3

Earlier quoted context omitted.

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.

But the context of OP is for human-scale puzzles.

Re: Logic programming is overrated, at least for logic puzzles (2013)

#16

Post by Karrot_Kream » Thu, Jun 01, 2023, 6:56 PM UTC

bmitc wrote: post #10

jerf wrote: post #6

For 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.

This hasn't been my experience at all. I personally am great at thinking in logic programming. I often prototype algorithms or services in Prolog (for myself, not for wider circulation) because it matches how I think very well. I've had little trouble using cuts and other techniques to guide the search. But my experience working with others is that a lot of people find the Prolog search algorithm to be inscrutable and very non-intuitive. Sure one could make the argument as some FP advocates do that had we all started learning using logic programming ideas from the start that this would be the default, but in practice I find that most people struggle to structure their program in a way amenable to Prolog-style backtracking search.

Working on open source projects with other Prolog enthusiasts is a bit different because that crowd self-selects for being good with Prolog.

Re: Logic programming is overrated, at least for logic puzzles (2013)

#17

Post by tangus » Thu, Jun 01, 2023, 6:58 PM UTC

Sure, to solve a 5x5x5 puzzle we can test all 5!*5!*5! possibilities; it's faster than thinking it out. To solve a 7x7x7 one you'll need logic programming though.

Re: Logic programming is overrated, at least for logic puzzles (2013)

#18

Post by grose » Thu, Jun 01, 2023, 7:01 PM UTC

As pointed out in the comments in the article, these kinds of logic puzzles are easier to solve using constraint programming than "regular" logic programming.

For example, see the solution to the Zebra Puzzle here: https://www.metalevel.at/prolog/puzzles which uses CLPZ[^1].

[^1]: https://github.com/triska/clpz

Re: Logic programming is overrated, at least for logic puzzles (2013)

#19

Post by Jtsummers » Thu, Jun 01, 2023, 7:04 PM UTC

gowld wrote: post #15

Jtsummers wrote: post #5

Earlier quoted context omitted.

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.

But the context of OP is for human-scale puzzles.

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 puzzles (2013)

#20

Post by PaulHoule » Thu, Jun 01, 2023, 7:12 PM UTC

jerf wrote: post #12

PaulHoule wrote: post #8

Earlier quoted context omitted.

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…

"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." One of the lessons I'm still trying to absorb is how convinced we all were (and many still are) that there must be a ton of implicit parallelism in the world, but once we went looking for it, it turned out there was hardly any. I've been chewing on this for y…

Part of the "low code" puzzle is that part of the job of the professional programmer is to determine what sequence events need to happen in time.

There are some cases (make and the Spring Framework) where the user specifies the dependencies between things and the framework does a topological sort to figure out what order to do them in.

Even though this could be a basis for a whole paradigm of programming, professional programmers usually don't find it hard to figure out how to order things so there is little motivation to address this problem systematically. However, I think it is on the list of problems that non-professional programmers (say the subject matter expert who wants to learn Python to put their skills on wheels) get hung up. Instead it's seen as a special case that makes high-complexity systems scalable (... Spring lets you describe the parts of a system and how they are related without writing structurally unstable initialization code.)