6 ms·
20 years ago : you are right. Although be warned, Prolog has some killer issues, principally the way that the knowledge base and search system works means that
by sgt101 8y ago
20 years ago : you are right. Although be warned, Prolog has some killer issues, principally the way that the knowledge base and search system works means that you will end up stirring fiddle factors (cut) into your logic program and at scale the brain boggling complexity of what is going on can lead to complete, sudden and irretrievable project failure.
As in : it doesn't work, no one knows why, no one can fix it and no one has a plan that doesn't involve starting from the beginning and doing it differently.
consider two programs
Good prolog :
on(a,b).
on(b,c).
above(X,Y) :- on(X,Y).
above(X,Y) :- on(X,Z), above(Z,Y).
->above(a,c).
You'll get TRUE (yay) a is above c ! GOOOOOOOD prolog.
but now :
on(a,b).
on(b,c).
above(X,Y) :- above(X,Z), on(Z,Y).
above(X,Y) :- on(X,Y).
-> above(a,c).
ERROR: Out of local stack
Exception: (1,675,220) above(a, _4808) ?
BAD BAD BAD BAD prolog. Go to your room!
ERROR: Out of local stack
Exception: (1,675,220) above(a, _4808) ?
Prolog gets stuck expanding the first search until it can't carry on. One line is out of order in the program and you are dead, and the problem is that you will not find that line until that question is asked, and when you find it (in a real example) it really is the devils own job to work out where the expansion is coming and how to fix it.
But there you go - search based logic resolution, brought to you by 1970's computer architecture (small main store) and solvers. Note, not only is "it doesn't bloody work" an issue, but also (probably much worse) "it keeps hanging for five minutes". This inconsistency and problem is hard to replicate and very, very hard to debug. It's caused by an occasional big search happening in the knowledge base, but a big search that doesn't end up exploding the system, it's often accompanied by shifty developer behaviour involving parameters and special cases. In a real project it's a nightmare.
Now : NOOOOOOO! Instead use Problog or something similar and reason using Answer Sets. For your first steps an answer set system looks very like Prolog, but does not suffer from the issues above (as far as I can see). There has not been (so far) a big charge to use this in prod (with Prolog and KBS's there was, it failed, because above) because everyone is playing with 40 layer 200 billion parameter neural networks and wondering why proving they can beat a tiny part of one benchmark or mostly steer a car without killing many people is not translating into application success. And this is a good thing because I don't think that the tech is quite there yet and the community needs five years and about half a dozen big "let's make this practical" applied research projects (btw. keen on partners?) to actually make this manageable for people with deadlines and investors.
But - it's going to help you more than Prolog.
- ahmedalsudani 8y agoInteresting. Thank you for sharing that. Gave it a shot on SWI Prolog and got the same error. It seems like a problem that ought to be solvable with static analysis or a fuzzer -- solvable in the sense that the error is detected before the question is asked. I imagine if Prolog had wider adoption, somebody would have taken a crack at it.
- yorwba 8y agoThe problem is nontermination. Static analysis of arbitrary programs to detect nontermination is the famous Halting Problem and known to be impossible. At its core, Prolog combines term unification with a depth-first search strategy. Implement those two primitives and you get a Prolog. But there are problems where depth-first search is not the best approach (e.g. when the search space is potentially infinite), and being able to code a different strategy is important. Modern languages support limited unification in the form of destructuring assignment. If they could make it bidirectional without also completely confusing everyone used to more traditional programming languages, Prolog wouldn't have many advantages left.
- nickpsecurity 8y ago"The problem is nontermination. Static analysis of arbitrary programs to detect nontermination is the famous Halting Problem and known to be impossible." People reading that might think you can never prove termination of programs automatically. Sounds overstated given the results happening in CompSci. There are a few tools that can automatically prove termination of a given program. AProVe was an older example that used rewriting like a lot of them: https://www.researchgate.net/publication/2877806_Automated_Termination_Proofs_with_AProVE https://www.researchgate.net/publication/2877806_Automated_T... Terminator is one for C programs: https://www.microsoft.com/en-us/research/video/automatically-proving-the-termination-of-c-programs/ https://www.microsoft.com/en-us/research/video/automatically... There's also a site where many tool builders competed in lots of categories: http://termination-portal.org/wiki/Termination_Competition http://termination-portal.org/wiki/Termination_Competition Lots of research happens under the "temporal logic" banner where they run it through model checkers, provers, and so on. Anyway, it seems proving termination of useful programs, protocols, or just critical portions is possible in general and doable with current tools for some subset.