Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

programming-puzzler.blogspot.com

Post reply on HN
Print view View original

31–40 of 43 posts

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

#31

Post by nerdponx »

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…

I think part of the problem is that there is plenty parallelism available, but it's not "high impact" parallelism, in that it's not worth whatever overhead you might incur (whether in language complexity or runtime overhead).

I think most "business logic" is fairly linear most of the time, and that even if it's highly branched, usually you don't have a large number of concurrently executing units of logic. You do have things like iterating/mapping over arrays, but that's precisely what I think is generally not "high impact" to parallelize. And when it is high impact, we do in fact have a rich space of tools available in the programming and software world, depending on the nature of the task at hand.

I know nothing why this particular Prolog parallelization project failed, but the above is generally my intuition about parallelism in computer programming, so I imagine it's at least somewhat relevant in this case.

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

#32

Post by slaymaker1907 »

gowld wrote: post #14
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?

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.

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

#33

Post by slaymaker1907 »

manasij7479 wrote: post #21
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…

The issue you have circled around here is a bit deeper and nuanced than trimming down exponential code to something more tractable. In fact, it's often worse, and O(2^n) can be a blessing! The problem with logic programming is the 'logic' part. Modern imperative and functional programming languages are constructive. Logic programming is not, and the expressive power varies with the exact logic being used. Elementary…

Of the logic programming languages, Prolog is actually pretty friendly when it comes to construction. You can easily force evaluation with an empty left clause, i.e. ":- thing1(x), thing2(y).", and Prolog gives you a lot of tools to control the current database with assert/retract (handy for memoization). Minikanren (which core.logic is based on) is much more restrictive and really wants things to be pure, though it does have the advantage of working as a library in an imperative language as a small runtime.

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

#34

Post by kazinator »

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.

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

#35

Post by coldtea »

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…

>That is to say, a "normal" line of code you type will be O(1)

Huh? This isn't remotely true especially today, and for the type of programming most do, where people work with functions and classes from libraries, with each line doing all kinds of O(?) stuff under the hood, and applying those to collections of objects, and so on.

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

#36

Post by PaulHoule »

nerdponx wrote: post #31
jerf wrote: post #12

Earlier quoted context omitted.

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

I think part of the problem is that there is plenty parallelism available, but it's not "high impact" parallelism, in that it's not worth whatever overhead you might incur (whether in language complexity or runtime overhead). I think most "business logic" is fairly linear most of the time, and that even if it's highly branched, usually you don't have a large number of concurrently executing units of logic. You do hav…

Oddly superscalar CPUs find quite a bit of parallelism at the micro level in ordinary scalar code although that is tied up very much with managing the comparatively slow motion of data from RAM to CPU and it is something the processor has to discover on the fly as the compiler can’t really know what will be in the cache every time.

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

#37

Post by kazinator »

Jtsummers wrote: post #19
gowld wrote: post #15

Earlier quoted context omitted.

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.

That depends; do you want to figure out how to solve the puzzle programmatically from scratch, or do you want to study how to apply/integrate SAT or constraint propagation systems. Equally valid.

Ad hoc brute force searches can be informed by constraint checking. Like if you're laying blocks into a box or something, your brute force search rejects placements that stick outside of the box.

I think "logic problems" may be referring to to those problems that tell you Bob is Alice's neighbor, and Jack plays piano, and, ..., and so then who owns the horse? We can identify all the propositions, round up their Boolean variables, and test. I've never seen a problem like this approach anywhere near 32 variables.

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

#38

Post by manasij7479 »

slaymaker1907 wrote: post #33
manasij7479 wrote: post #21

Earlier quoted context omitted.

The issue you have circled around here is a bit deeper and nuanced than trimming down exponential code to something more tractable. In fact, it's often worse, and O(2^n) can be a blessing! The problem with logic programming is the 'logic' part. Modern imperative and functional programming languages are constructive. Logic programming is not, and the expressive power varies with the exact logic being used. Elementary…

Of the logic programming languages, Prolog is actually pretty friendly when it comes to construction. You can easily force evaluation with an empty left clause, i.e. ":- thing1(x), thing2(y).", and Prolog gives you a lot of tools to control the current database with assert/retract (handy for memoization). Minikanren (which core.logic is based on) is much more restrictive and really wants things to be pure, though it…

Neat, I wonder if this idea could be developed into a more refined programming experience where you you spend time in the imperative world by default and only express some iterations as logic puzzles to be solved like this.

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

#39

Post by lurquer »

contingencies wrote: post #25
lurquer wrote: post #11

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

Couple of very good kids games recently on this theme: https://www.thinkfun.com/products/dog-crimes/ and https://www.thinkfun.com/products/cat-crimes/ If you have a suitably interested child, this could provide a fun bridge to constraint based programming.

If your kid is a Vulcan, give him this:

https://a.co/d/duMgX8q

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

#40

Post by TimSweeneyEpic »

This example shows that Clojure list comprehensions (the for... syntax) have much of the expressive power of logic programming (the first... syntax).

List comprehensions support a bundle of features including producing multiple values, and filtering them by testing and potentially failing.

Logic programming is that plus some more flexibility (more compositional forms of multiple value production) and some new features (such as using unification to solve for unknowns).

We should expect mainstream languages to evolve to support more logic features, since they provide a more general and more compositional way to do many things. Pattern matching expressions in most languages are a limited special case of logic programming that would benefit from using the more general case. Same with casting constructs, null propagation operators, boolean and/or/not, and the internal compiler logic supporting features like Haskell typeclasses and Rust traits. If we can replace lots of special-case language features a few general constructs, programming will be simpler as Niklaus Wirth advocates for.

Post reply on HN