What do people use Prolog for in the real world? I learned about it on a university course and it seems so esoteric compared to other things on the course. Like something invented just for computer scientists to enjoy.
Prolog is very succinct and interactive so it is quite nice for modeling and analysing problem spaces, similar to what you might do with Z3 or some other solver library.
Prolog also has exceptionally good string management through DCG:s. If you have a bunch of structured text and want to query it, Prolog allows you to do that. The syntax is very simple so you can even just sed your data into Prolog code and load that sometimes.
Supposedly SICSTUS Prolog is used in flight booking, and NASA did something with it sometime, but that's kind of obscure. If you ever need a rule engine, consider poking it with logic programming for a bit, perhaps it'll turn out both pragmatic and elegant.
Many years ago I used Prolog (BIM Prolog, I believe ) since it was used as an event correlation engine in Tivoli Enterprise Console (IBM). Fun to assert predicates for complex correlation logic.
There's something quite illuminating with this first "horror", where they basically say "it's OK to report wrong answers, because you can check the answers".
I don't think I've ever felt like it's OK for my program to provide a list of answers where some are right and some are wrong, but reading this... and generally believing in P != NP.... maybe that's a decent way of looking at some stuff!
As someone who has developed a somewhat weird obsession with Prolog, I can highly recommend Markus Triska's other articles on Prolog. His article on meta-interpreters [0] was particularly inspiring for me.
I haven’t used Prolog, but I have a little experience with Erlang and a lot with Elixir. As I understand it, the early versions of Erlang were inspired by Prolog.
For those with familiarity with both Prolog and Erlang, can you comment on the similarities and differences between? Is/was Erlang basically Prolog with OTP bolted on?
I get what he's saying but I think it's overstated. I'd categorise his list as "Things to be careful with" not "Coding horrors". For example, "The primary means to make your programs defective in this way is to use predicates like assertz/1 and retract/1" is an unqualified statement that makes it sound like you should never ever use them, and that's not the case. I have a real-life Prolog app that applies rules to facts read from JSON data files. I could do that two ways:
1) Read the JSON with Prolog (there's a library) and assertz() the facts from that, building an immutable database in the first phase before applying the rules in the second phase.
2) Externally transform the JSON into Prolog facts, load that into the app on startup and apply the same rules to it.
I agree that mutating the database in the second phase is probably a bad idea, but that's not the same as saying "assertz() always bad". I'd read his site before it appeared on HN and whilst there a lot of very good stuff on it, some of it reminds me of FP purist edicts - fine if you want to go that way and it's appropriate to your problem, but that isn't always going to be the case. That was the basis of my earlier (downvoted) "Mostly overblown" comment.
Prolog operators like `4 > 5` are a syntax sugar which desugars into a normal function call `>(4, 5)`. This part of the language is programmable, so you can add your own function `#>(X, Y)` and then declare it as an operator and use it like `4 #> 5`. See [1]. Nitpickingly, this means we can't be sure what #> is without looking, but it's common in Scryer and SWI Prolog (at least) that the #> #< versions of numeric comparison operators are used by constraint solver libraries. In imaginary Python it might be this code:
:- using constraint solver library
X in 0..100,
X #> 50,
label(X)
where "in" and "#>" were added into the language at runtime by the import of the constraint library. That is, it calls out to a custom 'function' which tells the constraint solver to restrict possible values for for X from 0..100 down to 51..100.
> "and what ! does"
This is a concept which doesn't translate easily to other languages, but analogously it's like the performance difference between this code which always searches the entire haystack:
found = false
for item in haystack:
if item == 'needle':
found = true
return found
and this which stops searching the haystack if the needle is found, but still searches the entire haystack in the worst case:
for item in haystack:
if item == 'needle':
return true
return false
The catch being that ! is not exactly a performance thing, it's an instruction to the Prolog runtime to skip some of the code, which can speed up performance but if you throw it in carelessly, your code no longer gives the right answers.
[1] They aren't Prolog "functions", they are predicates, functions are different, but it will do for this explanation.
>> The version without ! looks identical to the version with ! except only the ! is removed - is this a joke?
That's just showing getting rid of the cut in two stages. The line that makes it possible to remove it is this one:
N #> 0,
Markus Triskas' argument is that if you use the #> etc versions of declarative arithmetic operators, instead of the > ones, you can then call the factorial predicate with both arguments as variables, i.e. without inputs, just outputs, to enumerate the entire factorial relation. Like this:
?- n_factorial(N, F).
N = 0, F = 1
; N = 1, F = 1
; N = 2, F = 2
; N = 3, F = 6
; ... .
If you use > instead of #> the line N > 0 will raise an exception if N is a variable, which will be the case if you call it as above. This stops you from enumerating the relation, which declarative arithmetic allows.
Of course there are other ways to write a factorial predicate (or any predicate) so that it always enumerates a relation but they are more verbose. Then again, you do need a special library to use declarative arithmetic anyway, so.
Well, with respect to Markus Triska, I don't like purity. Prolog gives you plenty of "impure" constructs like the cut (!/0) and the assert/retract family of database manipulation predicates. It also gives you impure I/O and arithmetic functions that are quite separate from the otherwise logical, declarative-ish style of the language.
I'm fine with all that. The language gives you sensible tools to deal with edge cases that otherwise require you to jump through hoops or import libraries (like the constraint arithmetic libraries that Markus recommends... and that he had to mostly write himself before he could recommend). You can get into a spot of bother if you use those facilities without knowing why they are there and why you shouldn't just spam them in every case, but that's why good textbooks exist.
And more to the point, that's why Prolog Coding Guidelines are a thing, more precisely, a paper, which you can find here from the website of Michael Covington who's one of its (many) authors:
Here's what the Guidelines has to say about assert/retract:
5.10 Avoid asserta/assertz and retract unless you actually need to preserve
information through backtracking
Although it depends on your compiler, asserta/assertz and retract are usually
very slow. Their purpose is to store information that must survive backtracking. If
you are merely passing intermediate results from one step of computation to the
next, use arguments.
If you have a dynamic predicate, write interface predicates for changing it instead
of using “bare” calls to asserta/assertz and retract, so that your interface
predicates can check that the changes are logically correct, maintain mutexes for
multiple threads, and so forth.
Sound advice. In fact that's what I've always done myself even before reading the Guidelines.
And here's some advice on using the "horror" of the cut without having to wake the Great Old Ones:
5.4 Use cuts sparingly but precisely
First think through how to do the computation without a cut; then add cuts to save
work. For further guidance see O’Keefe (1990, pp. 88–101). Concerning code layout,
make sure cuts do not go unnoticed: if a green cut7 may be placed on the same line
as the previous predicate call, red cuts definitely must be on their own line of code.
5.5 Never add a cut to correct an unknown problem
A common type of Prolog programing error is manifested in a predicate that yields
the right result on the first try but goes wrong upon backtracking. Rather than add
a cut to eliminate the backtracking, investigate what went wrong with the logic.
There is a real risk that if the problem is cured by adding the cut, the cut will be far
away from the actual error (even in a different predicate), which will remain present
to cause other problems later
Basically the message should be that we can help the novice to navigate the complexities of the language without underestimating or pataronising them. Cuts, asserts, and the lot, are just there to make things easier. They only make things harder when they're not explained properly. And telling everyone to just stay away from them is, I think, not the proper way to explain anything.
19 comments
[ 1.1 ms ] story [ 49.0 ms ] threadProlog also has exceptionally good string management through DCG:s. If you have a bunch of structured text and want to query it, Prolog allows you to do that. The syntax is very simple so you can even just sed your data into Prolog code and load that sometimes.
Supposedly SICSTUS Prolog is used in flight booking, and NASA did something with it sometime, but that's kind of obscure. If you ever need a rule engine, consider poking it with logic programming for a bit, perhaps it'll turn out both pragmatic and elegant.
I don't think I've ever felt like it's OK for my program to provide a list of answers where some are right and some are wrong, but reading this... and generally believing in P != NP.... maybe that's a decent way of looking at some stuff!
https://grack.com/writing/school/enel553/report/prolog.html
[0] https://www.complang.tuwien.ac.at/ulrich/prolog_misc/acomip....
For those with familiarity with both Prolog and Erlang, can you comment on the similarities and differences between? Is/was Erlang basically Prolog with OTP bolted on?
1) Read the JSON with Prolog (there's a library) and assertz() the facts from that, building an immutable database in the first phase before applying the rules in the second phase.
2) Externally transform the JSON into Prolog facts, load that into the app on startup and apply the same rules to it.
I agree that mutating the database in the second phase is probably a bad idea, but that's not the same as saying "assertz() always bad". I'd read his site before it appeared on HN and whilst there a lot of very good stuff on it, some of it reminds me of FP purist edicts - fine if you want to go that way and it's appropriate to your problem, but that isn't always going to be the case. That was the basis of my earlier (downvoted) "Mostly overblown" comment.
But nice to see Prolog mentioned at all on HN :-)
The version without ! looks identical to the version with ! except only the ! is removed - is this a joke?
> "and what ! does"
This is a concept which doesn't translate easily to other languages, but analogously it's like the performance difference between this code which always searches the entire haystack:
and this which stops searching the haystack if the needle is found, but still searches the entire haystack in the worst case: The catch being that ! is not exactly a performance thing, it's an instruction to the Prolog runtime to skip some of the code, which can speed up performance but if you throw it in carelessly, your code no longer gives the right answers.[1] They aren't Prolog "functions", they are predicates, functions are different, but it will do for this explanation.
That's just showing getting rid of the cut in two stages. The line that makes it possible to remove it is this one:
N #> 0,
Markus Triskas' argument is that if you use the #> etc versions of declarative arithmetic operators, instead of the > ones, you can then call the factorial predicate with both arguments as variables, i.e. without inputs, just outputs, to enumerate the entire factorial relation. Like this:
If you use > instead of #> the line N > 0 will raise an exception if N is a variable, which will be the case if you call it as above. This stops you from enumerating the relation, which declarative arithmetic allows.Of course there are other ways to write a factorial predicate (or any predicate) so that it always enumerates a relation but they are more verbose. Then again, you do need a special library to use declarative arithmetic anyway, so.
I'm fine with all that. The language gives you sensible tools to deal with edge cases that otherwise require you to jump through hoops or import libraries (like the constraint arithmetic libraries that Markus recommends... and that he had to mostly write himself before he could recommend). You can get into a spot of bother if you use those facilities without knowing why they are there and why you shouldn't just spam them in every case, but that's why good textbooks exist.
And more to the point, that's why Prolog Coding Guidelines are a thing, more precisely, a paper, which you can find here from the website of Michael Covington who's one of its (many) authors:
https://www.covingtoninnovations.com/mc/plcoding.pdf
Here's what the Guidelines has to say about assert/retract:
5.10 Avoid asserta/assertz and retract unless you actually need to preserve information through backtracking Although it depends on your compiler, asserta/assertz and retract are usually very slow. Their purpose is to store information that must survive backtracking. If you are merely passing intermediate results from one step of computation to the next, use arguments.
If you have a dynamic predicate, write interface predicates for changing it instead of using “bare” calls to asserta/assertz and retract, so that your interface predicates can check that the changes are logically correct, maintain mutexes for multiple threads, and so forth.
Sound advice. In fact that's what I've always done myself even before reading the Guidelines.
And here's some advice on using the "horror" of the cut without having to wake the Great Old Ones:
5.4 Use cuts sparingly but precisely First think through how to do the computation without a cut; then add cuts to save work. For further guidance see O’Keefe (1990, pp. 88–101). Concerning code layout, make sure cuts do not go unnoticed: if a green cut7 may be placed on the same line as the previous predicate call, red cuts definitely must be on their own line of code.
5.5 Never add a cut to correct an unknown problem A common type of Prolog programing error is manifested in a predicate that yields the right result on the first try but goes wrong upon backtracking. Rather than add a cut to eliminate the backtracking, investigate what went wrong with the logic. There is a real risk that if the problem is cured by adding the cut, the cut will be far away from the actual error (even in a different predicate), which will remain present to cause other problems later
Basically the message should be that we can help the novice to navigate the complexities of the language without underestimating or pataronising them. Cuts, asserts, and the lot, are just there to make things easier. They only make things harder when they're not explained properly. And telling everyone to just stay away from them is, I think, not the proper way to explain anything.