81–90 of 164 posts
Something I would like to be able to understand/know/study is how logic programming languages are implemented and how their runtime looks like.
I find this article very helpful when it comes to understanding how Prolog actually works.
Earlier quoted context omitted.
When I tried out Prolog, I was struck by the inelegance of is/2. There has to be something like it, because no one knows how to write an interpreter for arcsin(X,Y) :- sin(Y,X). However, MetaPost can do that for linear expressions. You can say (in Prolog syntax) midpoint(X,Y,Z) :- Z == (X+Y)/2. two(X) :- midpoint(0,X,1). And the MetaPost interpreter will find the solution two(2). Does anyone know of Prolog extensions…
SWI-Prolog has CLP extensions to do exactly that: http://www.swi-prolog.org/pldoc/man?section=clp ?- use_module(library(clpq)). midpoint(X, Y, Z) :- {Z =:= (X+Y)/2}. two(X) :- midpoint(0, X, 1). does what you want.
Roughly half the 'power of prolog' comes from the 'power of logic programming' and prolog is by far not the only logic programming language, e.g., - You can do logic programming using minikanren in scheme. (you can also extend the minikanren system if you find a feature missing). - Minikanren was implemented in clojure and called core.logic. - It was also ported to python by Matthew Rocklin I think, called logpy. - T…
Not really. I use SWI Prolog for a lot of personal projects (that actually see QPS no less) and there's a lot more to it than that. SWI gives you: good debugging support (with trace and spy), hooks into the Prolog database (with asserta/z and retract), optimized implementations of difference lists, online help, and so much more. Don't even get me started on its amazing DCG support that makes Regex feel like a Neolith…
Interestingly, IBM Watson uses Prolog. [1]
[1] https://www.cs.nmsu.edu/ALP/2011/03/natural-language-process...
love(prolog).
Earlier quoted context omitted.
Can SQL do resolution or backtracking similar to Prolog, I wonder.
SQL gives you all the solutions to query by default unless you limit them right? A relation (table) in SQL is conceptually a predicate that holds for all tuples (rows) therein. You can AND the predicates with "NATURAL JOIN". You can OR them with "UNION" e.g. this example https://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpa... becomes something like this in SQL. example=# select * from red; item --------- appl…
Prolog tutorials really do Prolog a disservice by introducing it as a database query language, which is then misunderstood (or misremembered) by many as "it's only a database query language".
Earlier quoted context omitted.
It's pretty much Backtracking as a language. So stuff like N Queens, Einstein's Puzzle (the Englishman lives in the red house, the Swede in the blue house, etc.) and so on. Any time you want to write down the rules of a discrete system and ask questions about the properties of that system, Prolog is a great way to do it. One practical application: it's very easy to write the logic for a network firewall in Prolog.
ah! backtracking. combinatorial optimisation would be incredibly useful for me. if prolog is indeed backtracking as a language I definitely need to look into it.
If the set of solutions is small enough, you can enumerate all of them and pick out the best one, or have it enumerate them until you get one that is good enough. But if you need a smarter exploration of the search space, you will (in general) have to write that yourself.
Many implementations include an integer constraints library that will give you functionality similar to an ILP solver, which may or may not fit your domain.
Can anyone give examples of the kinds of problems prolog is ideally suited to? I took a course on it at university. It looked interesting but I didn't really "get it". It might be worth another look now I have a bit more experience under my belt. I've got a lingering feeling it would solve a certain kind of problem very easily.
It's pretty much Backtracking as a language. So stuff like N Queens, Einstein's Puzzle (the Englishman lives in the red house, the Swede in the blue house, etc.) and so on. Any time you want to write down the rules of a discrete system and ask questions about the properties of that system, Prolog is a great way to do it. One practical application: it's very easy to write the logic for a network firewall in Prolog.
Earlier quoted context omitted.
> On many occasions you are hiding away the conputational complexity and wonder why the execution is so slow. I disagree. Prolog is a language where it's quite easy to lose performance because of the density of each goal (a goal is "dense" and is basically a form of executable pseudocode), but equally easy to diagnose because of the terse expressiveness of the language. What gets a lot of Prolog beginners is the exec…
I'd like to hear that story, when you get the chance. ;-)
To give a bit of background: I run a service for some folks that allows them to get status messages. Some of my users wanted stats on the kinds of messages they received. My first implementation was quick and dirty: shell scripts which would run filters and aggregations through combinations of grep, sort, and uniq. Eventually as more demands came in with different types of functionality, this became unscalable, so I wrote an analysis engine in Prolog.
Problem: Find status lines that have valid "http" links in them.
First attempt: SWI Prolog contains a goal sub_string/5 (http://www.swi-prolog.org/pldoc/man?predicate=sub_string/5). The goal is invoked as: sub_string(+String, ?Before, ?Length, ?After, ?SubString). I was storing status messages in the Prolog database wrapped in the "status" dynamic goal, so a status message looked like: `status("hello world")`. At a Prolog REPL, to query for all status messages, I could match along the goal `status(X)` and all bound instances of X would be the messages.
I created a DCG and wrapped it in a goal called `parse_http_string(String)` which would evaluate to true if `String` was a valid HTTP string. My first attempt was a goal like:
`status(String), sub_string(String, _, _, _, Needle), parse_http_string(Needle) `
This is an O(n^2) query. We first bind `String` to a status message, and the `sub_string` predicate will match _all valid substrings_ of `String` and stuff it into `Needle`. `parse_http_string/1` will then run on `Needle` and return true when the goal succeeds on a substring.
This was slow, but the query wasn't used very often and it worked for my customers.
Second Attempt: I realized that all HTTP links started with the text "http". By searching the status message for the string "http" and then starting the substring search at the starting index at the beginning of this match, I'd only be doing an O(n) search of substrings (because I'm only varying the end index of `sub_string/1` rather than both the start and end index). The modified goal looked like the following:
`status(String), sub_string(String, HttpStart, _, _, "http"), sub_string(String, HttpStart, _, Needle), parse_http_string(Needle) `
This produced the expected O(n) algorithm, despite only adding a single line and modifying the next line. This also made the query a lot faster, so I could rest easier when my customers began to look for links en masse in their status messages! (Which they did, as surely as any product you hand to users ever scales).
Earlier quoted context omitted.
Not really. I use SWI Prolog for a lot of personal projects (that actually see QPS no less) and there's a lot more to it than that. SWI gives you: good debugging support (with trace and spy), hooks into the Prolog database (with asserta/z and retract), optimized implementations of difference lists, online help, and so much more. Don't even get me started on its amazing DCG support that makes Regex feel like a Neolith…
How can you use DCG in a productive way? If haven't found a good way when there is left recursion. Memonization(tabbling) only sometimes helps and refactoring the grammar into non-left-recursive takes a lot of time and is error prone. What's your solution?
Roughly half the 'power of prolog' comes from the 'power of logic programming' and prolog is by far not the only logic programming language, e.g., - You can do logic programming using minikanren in scheme. (you can also extend the minikanren system if you find a feature missing). - Minikanren was implemented in clojure and called core.logic. - It was also ported to python by Matthew Rocklin I think, called logpy. - T…