6 ms·
One of the coolest things I've seen is to use Prolog with CLP(FD) to solve the 7-11 problem. The problem basically says the sum of the prices of four items is $
by kccqzy 8y ago
One of the coolest things I've seen is to use Prolog with CLP(FD) to solve the 7-11 problem. The problem basically says the sum of the prices of four items is $7.11, and the product is $7.11 too (no rounding); find the prices of these four items.
This can be solved in two lines of code that gives the (unique) solution in a second. Not even my expensive Mathematica can do this!
?- use_module(library(clpfd)).
true.
?- Vs = [A,B,C,D], Vs ins 1..711, A * B * C * D #= 711000000, A + B + C + D #= 711, A #>= B, B #>= C, C #>= D, labeling([ff, down], Vs).
Vs = [316, 150, 125, 120],
A = 316,
B = 150,
C = 125,
D = 120 ;
false.
Another great thing Prolog is good at is type inference. After all, type inference, in its simplest form, is just syntax-directed constraint generation and then using unification to solve constraints—exactly what Prolog gives you by default. You can write a type inference engine for simply typed lambda calculus in Prolog in 10 minutes. Google used to have a project to do type inference for Python written in Prolog, although they've since [switched away](https://github.com/google/pytype https://github.com/google/pytype).
- triska 8y agoHah! I used exactly this example to motivate the arbitrary precision CLP(FD) implementation, published as The Finite Domain Constraint Solver of SWI-Prolog, FLOPS 2012, LNCS 7294: https://www.metalevel.at/swiclpfd.pdf https://www.metalevel.at/swiclpfd.pdf The observations on type inference are also spot on. The project you mentioned was previously discussed on HN, but the page is no longer available: https://news.ycombinator.com/item?id=12108041 https://news.ycombinator.com/item?id=12108041
- kccqzy 8y agoOh you implemented this CLP(FD) and wrote that paper! Thanks a lot! My 7-11 example is probably because I first saw it in your paper then.
- ysleepy 8y agoThis reminds me of a recent HN post about a simple datalog engine being used in the rust borrow checker. https://github.com/frankmcsherry/blog/blob/master/posts/2018-05-19.md https://github.com/frankmcsherry/blog/blob/master/posts/2018... via https://news.ycombinator.com/item?id=17107527 https://news.ycombinator.com/item?id=17107527
- carapace 8y agoOoo! Lemme show off this CLP(FD) solution to the "Zebra Puzzle" https://en.wikipedia.org/wiki/Zebra_Puzzle https://en.wikipedia.org/wiki/Zebra_Puzzle that I made after reading the "Logic Puzzles with Prolog" chapter: https://gist.github.com/calroc/603ed919bc814ccee10c1b3df6142fec https://gist.github.com/calroc/603ed919bc814ccee10c1b3df6142...
- lucb1e 8y agoThat makes Prolog look downright useful! I heard from lots of people that it's fun as an esoteric language and some had a homework assignment or two in it, but nobody really uses it in practice. Do you think this might be more useful as a module to solve logic puzzles, rather than as a complete language by itself? I learned the very basics, but not worked with it enough myself to say whether that would be better than keeping it as a stand-alone language.
- yaantc 8y agoYes, a modern Prolog with CLP(FD) is very well suited to solve logic puzzles. There are many examples on the web, but you can look at this book on ECLiPSe CLP (nothing to do with the IDE, it's a Prolog system with good constraints support): http://www.anclp.pl/ http://www.anclp.pl/ However, nowadays I'd start with Minizinc and its default solver gecode: http://www.minizinc.org/ http://www.minizinc.org/ For combinatorial puzzles it's even easier than Prolog and very efficient. Just read the short tutorial and you should be good to go solving the Zebra/Einstein problem or similar: http://www.minizinc.org/downloads/doc-latest/minizinc-tute.pdf http://www.minizinc.org/downloads/doc-latest/minizinc-tute.p... Minizinc is purely declarative. When more control is needed then you can use Prolog.
- carapace 8y agoWell, the idea that "nobody really uses it in practice" doesn't hold up to the evidence in this thread, eh? It's used and under active development. I think it lacks hype. :-) > Do you think this might be more useful as a module to solve logic puzzles, rather than as a complete language by itself? I was thinking about it this morning and I came to the conclusion that Prolog really is AI. They did it. We have AI already and most of us just failed to notice. The Unification algorithm at the heart of Prolog (I'm not an expert!) is pretty much what your brain does when you solve logical puzzles and problems. We have a machine that can think. The way I think of Prolog is as a super-calculator that can be applied to a huge range of problems and tasks. (One thing to be aware of is that if you have a Prolog-shaped problem and try to solve it in some other language you'll likely wind up reinventing some portion of Prolog in that language! If you look up solutions to the Zebra Puzzle written in other languages you'll see that most of them proceed by implementing some sort of logic solver that resembles a crude Prolog.) There may be practical real-world issues in performance or interfacing for a given application, but in general I'd say that good ol' Prolog is vastly underutilized. (Put another way, we're working harder than we should be.)
- bloak 8y agoBut, but, the product of four prices cannot possible be measured in $. You must mean $^4. Edit: Here's a solution in Haskell. I've been paid to program in both Prolog and Haskell, but it was a while ago; my knowledge of both languages is very rusty. main = putStrLn $ show [(a, b, c, d) | a <- [1..711], b <- [a + 1..711], c <- [b + 1..711], d <- [711 - a - b - c], c <= d, a * b * c * d == 711000000]
- tonyg 8y agoAmazingly, this gives an answer within not too many tens of seconds of full CPU usage. (I interrupted it before it finished searching the full space, though.)
- deleted 8y ago[deleted]
- cousin_it 8y agoThis Python code does a full search and finds the unique solution instantly: p = 711 q = 711000000 for a in range(1, 1 + p // 4): if q % a == 0: for b in range(a, 1 + (p - a) // 3): if q % (a * b) == 0: for c in range(b, 1 + (p - a - b) // 2): d = p - a - b - c if a * b * c * d == q: print (a, b, c, d) Does Prolog do the same pruning? Alternatively, it could be dumber (omit some of the pruning that my code does) or smarter (start by factoring 711000000 or something).
- doublec 8y agoYou could write the same solution in prolog. The difference between yours and the original solution is the latter follows the original program specification and is easier to compare to it. That is, it defines what the problem is, not how to solve it.
- tom_mellior 8y agoProlog doesn't do that automatically, but you can write the same thing in Prolog too: xkcd_ugly(A, B, C, D) :- P = 711, Q = 711000000, Max_A is 1 + P // 4, between(1, Max_A, A), Q mod A =:= 0, Max_B is 1 + (P - A) // 3, between(A, Max_B, B), Q mod (A * B) =:= 0, Max_C is 1 + (P - A - B) // 2, between(B, Max_C, C), D is P - A - B - C, A * B * C * D =:= Q. In SWI-Prolog, I get the following timings: ?- time(xkcd_ugly(A, B, C, D)). % 383,992 inferences, 0.056 CPU in 0.056 seconds (100% CPU, 6825328 Lips) A = 120, B = 125, C = 150, D = 316 ; % 3,274 inferences, 0.003 CPU in 0.003 seconds (100% CPU, 1229464 Lips) false. That is to say, it found the first solution in 0.056 seconds CPU time, then took an additional 0.003 seconds to prove that there are no further solutions. (This is the minimum of a handful of runs, there is quite a bit of variation.) Quick and very dirty benchmarks on the same machine run your Python code in about 0.02 seconds. The CLP(FD) code above takes about 0.1 seconds but it's a lot clearer.
- cousin_it 8y agoThank you! That makes sense.