I have used Lisp languages far more often than Prolog, but I do have my own Prolog success story: I had just used ExperLisp on the Macintosh to write a little app ExperOPS5 for the company who wrote and marketed ExperLisp and ExperProlog. After this I was given an internal research grant to write a complete simulation environment in ExperLisp as part of trying to win a large contract. Given familiarity with the tools…
The Prolog Story (2010)
21–30 of 31 posts
Re: The Prolog Story (2010)
#22Summary: They needed to do some complex queries on data in a SQL database, queries that were clearly better suited for Prolog. So they 1) queried for the relevant data from SQL, 2) formatted the data into the form of Prolog terms and dumped it into a file, 3) fired up the Prolog interpreter and loaded the data along with a small amount of Prolog query code, 4) ran the Prolog queries, 5) formatted the results into CSV…
> Prolog is being used kind of like a more powerful version of Awk / Perl I have limited experience with Prolog, but it is not just a quick and dirty scripting language (how I view Perl). They were able to build the system so fast, because they only needed to translate the customer's requirements into Prolog declarations, and the Prolog engine is powerful enough to solve the constraints. In my experience, imperative…
Re: The Prolog Story (2010)
#23There are a few problems that don't fit well with Prolog, but not many. For everything else, if you're not using Prolog you're probably working too hard.
Consider that achieving feature parity with 1/5th the code means 1/5th the bugs, right off the top.
But often Prolog code is more useful than some equivalent imperative code, for example, a Sudoku relation defined in Prolog serves to solve puzzles, but it can also generate new puzzles and verify partial puzzles (count the solutions and assert that there's only one.) https://swish.swi-prolog.org/p/Boring%20Sudoku.swinb
Prolog is also old.
I keep thinking, "What about FOO?", only to find that FOO has been explored years ago by a group of researchers, and often there is working code off-the-shelf and ready to go to solve whatever problem.
Anyhow, TL;DR: For goodness' sake please check out Prolog. It's like time-traveling into the future.
Re: The Prolog Story (2010)
#24Nice pun!
Re: The Prolog Story (2010)
#25I recently used prolog for a complicated binary reverse-engineering task: bit packing. Likewise prolog is perfect for compilation. https://savannah.gnu.org/forum/forum.php?forum_id=9203 In fact it's a better prolog, picat, which also allows pretty straightforward statements, like loops, and has solver support. http://picat-lang.org/
Re: The Prolog Story (2010)
#26I would like to know what Prolog implementation the author used. In particular, the article claims: 1. > An initial analysis found that we would need to implement a complex depth/breadth search algorithm either in the client application or in SQL. 2. The Prolog runtime would efficiently solve this problem given rules that naively described it. I am skeptical, as this is emphatically not my experience with Prolog. In…
Most modern Prologs use indexing on predicates' symbols and arguments to speed up queries and the days when Prolog was a "slow" language are long gone by.
As to the search strategy, it's a bog-standard, depth-first search (no approximation). Unification is part of the theorem-proving algorith, SLD-resolution. Depth-first search is used to find "resolvents", i.e. candidates for resolution (ish).
The parent post describes a backward-chaining problem, where rules must be selected depending on their arguments, most likelly to perform some complex reasoning procedure. In that context, search is required to select relevant rules at each step of the reasoning process- not, say, to search a large database for all records of persons with a name starting from "m".
For this kind of use-case, Prolog's search is not only perfectly adequate, but also nearly perfectly optimised, due to long years of development as a language.
That said, "searching a database for all records starting from m" is very much like searching for resolvents and thanks to modern practices, like indexing, Prolog can do that kind of search just fine also.
Re: The Prolog Story (2010)
#27I recently used prolog for a complicated binary reverse-engineering task: bit packing. Likewise prolog is perfect for compilation. https://savannah.gnu.org/forum/forum.php?forum_id=9203 In fact it's a better prolog, picat, which also allows pretty straightforward statements, like loops, and has solver support. http://picat-lang.org/
What types of problems does one use constraint programming for? Large optimization problems require something like CPLEX usually.
It's a biig discussion and I'm not the one to make the argument for CLP, but, for example, in straight-up Prolog arithmetic is implemented using the is/2 predicate, which looks a bit like this:
A is 1 + 2.
Where A is the result of the addition of 1 and 2. In CLP on the other hand, particularly in the CLP library for reasoning over integers, CLP(FD), the addition above looks like this: X #= 1+2.
Note that here, "#=/2" ("equals") is a constraint, so the statement above is true, iff the expression on the left-hand side of the #= is equal to the right-hand side of it. Which lets you do things like this: ?- 3 #= Y+2.
Y = 1.
Where trying to do the same thing with is/2 will give you an error (because Y is not sufficiently instantiated). And because of how constraint programming works, you can also do arithmetic with ranges, like so: ?- X #= A + B, A in 1..3, B in 4..6.
X in 5..9,
A+B#=X,
A in 1..3,
B in 4..6.
In fact, what comes out the other end of the query above (the bit after the query prompt, "?") is a set of new constraints, where the result of adding A in [1,3] and B in [4,6] is a number, X, in [5,9].You can find more information in the CLP(FD) library documentation, here:
http://www.swi-prolog.org/man/clpfd.html
Or, if Markus Triska (the author of the library) is around, he can probably elucidate its use a bit better than I can :)
Re: The Prolog Story (2010)
#28Earlier quoted context omitted.
What types of problems does one use constraint programming for? Large optimization problems require something like CPLEX usually.
Constraint logic programming is generally proposed as a more natural alternative for arithmetic, in Prolog, than Prolog's native arithmetic functions. It's a biig discussion and I'm not the one to make the argument for CLP, but, for example, in straight-up Prolog arithmetic is implemented using the is/2 predicate, which looks a bit like this: A is 1 + 2. Where A is the result of the addition of 1 and 2. In CLP on the…
Re: The Prolog Story (2010)
#29Prolog looks like the exact right language for at least some part of Netflix's OPA[0] -- I wonder why they didn't use it or why it wasn't a good fit (if someone considered it). I often want to reach for prolog when I face a problem like this, but I just don't know enough about how it degrades/breaks and of course don't want to use it to do any of the rest of the program stuff (web server, DB access), etc. [0]: http:/…
(OPA co-founder here.) The semantics of OPA's policy language are based on Datalog, a non-Turing complete subset of Prolog. This means that all policy queries in OPA are guaranteed to terminate (which makes it a good fit for problems like authorization.) Beyond regular Datalog, OPA adds first-class support for querying complex/nested data structures like JSON. As a side note, OPA was not developed at Netflix, but the…
Did you guys build your own engine? I took a quick look at the repo but don't see anything that looks like a datalog library in your glide package list.
Last but not least, thanks for making and open sourcing such an awesome tool! Will definitely be passing the word on about Styra[2], I had no idea there was a whole company/more efforts behind OPA. I plan on using OPA in a bunch of upcoming projects -- it looks like a fantastic, stable addition to the toolbox of people looking to build robust programs/services.
[0]: https://www.youtube.com/watch?v=XEHeexPpgrA
Re: The Prolog Story (2010)
#30Earlier quoted context omitted.
(OPA co-founder here.) The semantics of OPA's policy language are based on Datalog, a non-Turing complete subset of Prolog. This means that all policy queries in OPA are guaranteed to terminate (which makes it a good fit for problems like authorization.) Beyond regular Datalog, OPA adds first-class support for querying complex/nested data structures like JSON. As a side note, OPA was not developed at Netflix, but the…
Thanks so much for the answer -- I thoroughly enjoyed the OPA talks I've seen[0][1]. I apologize for mistaking OPA as a netflix product, I think one of the first times I saw it was as it was being used by Netflix so I assumed it was one of their F/OSS projects or built by someone there. Did you guys build your own engine? I took a quick look at the repo but don't see anything that looks like a datalog library in your…
Yes, the language implementation (parser/compiler/evaluator) is implemented from scratch.
> Last but not least, thanks for making and open sourcing such an awesome tool!
Thanks for the kind words! If you have questions or need help, feel free to file issues on Github or ask questions on Slack.