9 ms·

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

by fizixer 10y ago

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. - There is also datalog, with pydatalog it's python equivalent. - Also pyke. And so on. Plus logic programming has very important (arguably necessary) extensions in the form of constraint-logic-programming (CLP), inductive-logic-programming (ILP), and so on. It's a huge area. EDIT: ILP at an advanced level starts making connections with PGMs (probabilistic graphical models) and hence machine learning, but its a long way to go for me (in terms of learning) before I start to make sense of all these puzzle pieces. EDIT 2: You can have a taste of logic programming without leaving your favorite programming language. Just try to solve the zebra puzzle [1] (without help if you can, esp. through any of Norvig posts or videos; they're addictive). [1] https://en.wikipedia.org/wiki/Zebra_Puzzle https://en.wikipedia.org/wiki/Zebra_Puzzle EDIT 3: An "expert system" (a term from the 1980s) is largely a logic programming system paired up with a huge database of facts (and probably some way of growing the database by providing an entry method to non-programmer domain experts). EDIT 4: In other words, logic programming (along with other things like graph search etc) is at the core of GOFAI (good old fashioned AI), the pre-machine-learning form of AI, chess engine being a preeminent example of it.

eriknstr 10y ago
>Zebra puzzle Interesting puzzle. I copied the puzzle text to a separate text file so that one does not accidentally read anything else in the Wikipedia article. https://pastebin.com/0DWbSSx3 https://pastebin.com/0DWbSSx3
- eriknstr 10y ago
  I've worked a bit on it. My solution is not incredible or anything, probably there are far more efficient and/or elegant solutions out there. Mine is not done yet but I'm going to continue with this one later and by then the activity in this thread will be over so I leave this link here now. https://github.com/eriknstr/puzzles/blob/master/zebra/solution.py https://github.com/eriknstr/puzzles/blob/master/zebra/soluti...
  - philsnow 10y ago
    Fun problem. My solution doesn't do really any "logic programming", and it takes around 2 minutes to run on my laptop. https://gist.github.com/philsnow/02e747241d46106b14b60146e5803e49 https://gist.github.com/philsnow/02e747241d46106b14b60146e58... The middle huge nested thing (where `some_possible_worlds` is defined) is gross but I'm not great with ruby and I couldn't think of another way to not blow up memory enumerating all the worlds just to eliminate 99% of them.
    - carapace 10y ago
      I worked up this from the SEND MORE MONEY example in the CLP(FD) repo. https://gist.github.com/calroc/603ed919bc814ccee10c1b3df6142fec https://gist.github.com/calroc/603ed919bc814ccee10c1b3df6142... There are five houses. The Englishman lives in the red house. The Spaniard owns the dog. Coffee is drunk in the green house. The Ukrainian drinks tea. The green house is immediately to the right of the ivory house. The Old Gold smoker owns snails. Kools are smoked in the yellow house. Milk is drunk in the middle house. The Norwegian lives in the first house. The man who smokes Chesterfields lives in the house next to the man with the fox. Kools are smoked in the house next to the house where the horse is kept. The Lucky Strike smoker drinks orange juice. The Japanese smokes Parliaments. The Norwegian lives next to the blue house. Now, who drinks water? Who owns the zebra? In the interest of clarity, it must be added that each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarets [sic]. One other thing: in statement 6, right means your right. :- use_module(library(clpfd)). house_next_to(H0, H1) :- abs(H0 - H1) #= 1. puzzle([ GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse, Englishman, Spaniard, Ukrainian, Norwegian, Japanese, Dog, Snails, Fox, Horse, Zebra, Coffee, Tea, Milk, OrangeJuice, Water, OldGold, Kools, Chesterfields, LuckyStrike, Parliaments ]) :- Vars = [GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse, Englishman, Spaniard, Ukrainian, Norwegian, Japanese, Dog, Snails, Fox, Horse, Zebra, Coffee, Tea, Milk, OrangeJuice, Water, OldGold, Kools, Chesterfields, LuckyStrike, Parliaments ], Vars ins 1..5, all_distinct([GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse]), all_distinct([Englishman, Spaniard, Ukrainian, Norwegian, Japanese]), all_distinct([Dog, Snails, Fox, Horse, Zebra]), all_distinct([Coffee, Tea, Milk, OrangeJuice, Water]), all_distinct([OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]), Englishman #= RedHouse, Spaniard #= Dog, Coffee #= GreenHouse, Ukrainian #= Tea, GreenHouse #= 1 + IvoryHouse, OldGold #= Snails, Kools #= YellowHouse, Milk #= 3, Norwegian #= 1, house_next_to(Chesterfields, Fox), house_next_to(Kools, Horse), LuckyStrike #= OrangeJuice, Japanese #= Parliaments, house_next_to(Norwegian, BlueHouse). Then to print out the solution after loading the program above use: puzzle([ GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse, Englishman, Spaniard, Ukrainian, Norwegian, Japanese, Dog, Snails, Fox, Horse, Zebra, Coffee, Tea, Milk, OrangeJuice, Water, OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]), label([ GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse, Englishman, Spaniard, Ukrainian, Norwegian, Japanese, Dog, Snails, Fox, Horse, Zebra, Coffee, Tea, Milk, OrangeJuice, Water, OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]).
- sriram_malhar 10y ago
  My z3 based solution in python looks like this: https://gist.github.com/sriram-srinivasan/2981825217f0802d9fbd9878578a711d https://gist.github.com/sriram-srinivasan/2981825217f0802d9f...
tunesmith 10y ago
It still seems fairly untapped in enterprise and entrepreneurial circles, too. I've been wanting to create a side project that is sort of like an expert system, except where users can create the rules as well as the facts, and that is also horizontally scalable (which doesn't seem to be a good fit for the Rete algorithm). So I'm not sure if I'm looking for some sort of jvm-runtime logic programming system that can be combined with a graph database or what.
Karrot_Kream 10y ago
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 Neolithic toy. Not only that but Prolog's Syntax gives you very similar properties to lisp's homoiconicity (first class atoms, metaprogramming, etc). Sure you can reimplement all of this in miniKanren, but it's all there waiting for you in SWI Prolog already! There's a lot more to a language than just its concepts. Every time I hack in Prolog I always feel like I'm living the idea that I "tell the computer what to do not how to do it". It's a shame that more folks don't use it.
- random_gui2 10y ago
  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?
  - Karrot_Kream 10y ago
    I typically wrap up a left recursive rule as another rule, and then have this rule choose between the base case and the recursive case. This is a pretty standard technique to break down left recursive rules though, and has nothing to do with Prolog, and everything to do with writing parsers.
  - YeGoblynQueenne 10y ago
    To complement Karrot_Kream's answer, there's another two things you can do if you're having DCG left-recursion troubles: The first thing is to use a different parsing strategy. For instance, the Earley parser [1] used to be a typical example of (advanced ish) Prolog and wikipedia says that it performs particularly well with left-recursive languages. The disadvantage of course is that you're giving up the simplicity of having a built-in grammar-and-parser capability in your language. But in some cases that's probably a very small price to pay. The other thing you can do, which is in a sense the exact opposite of changing parsers, is to eliminate the possibility of left-recursion from your DCGs by choosing a grammar formalism that precludes it. It boils down to keeping all your rules looking like this: P --> [a₁, a₂, ..., aₙ], A₁, A₂, .... Aₘ. Where each Aᵢ is a terminal or nonterminal and each [aₖ] a terminal. In other words, expand every nonterminal first to one or more terminals, then any mix of terminals and nonterminals. That way you'll always accept a terminal before expanding a nonterminal and there's no chance of left-recursion. You can write a short syntax checker to enforce this rule in a post-processing step, or just do it by hand. You can be a little bit more rigorous and stick to more strict forms, particularly right-regular grammars, or Greibach Normal Form [2], if your grammars are context-free. Right regular grammars allow a single nonterminal on the right-hand side: A --> [a], B. Whereas Greibach Normal Form allows a single terminal followed by any number of nonterminals: P --> [a], A₁, A₂, .... Aₙ. The benefit of GNF is that any context-free grammar can be transformed into a grammar in GNF, so you can first write your grammars in a loose form, then convert them to GNF to remove left-recursions. If you want I can probably dig up a reference to how to do the conversion. ___________ [1] https://en.wikipedia.org/wiki/Earley_parser https://en.wikipedia.org/wiki/Earley_parser [2] https://en.wikipedia.org/wiki/Greibach_normal_form https://en.wikipedia.org/wiki/Greibach_normal_form
gugagore 10y ago
Here are some (I thought helpful) comments regarding some of the tools you mentioned https://github.com/logpy/logpy/issues/24#issuecomment-269444915 https://github.com/logpy/logpy/issues/24#issuecomment-269444...
est 10y ago
what about this? https://github.com/Z3Prover/z3 https://github.com/Z3Prover/z3 Is it comparable with prolog or just a subset of prolog?
- dreamcompiler 10y ago
  Z3 is a theorem prover; it's a tool you would use to formally analyze a hardware logic design or a software program to ensure that it meets certain criteria (e.g. that it contains none of a certain class of security vulnerabilities). Theorem provers incorporate a lot of the same basic ideas as Prolog, but they're specialized tools (many have been written in Prolog). Prolog itself is a general-purpose programming language.
- fizixer 10y ago
  Disclaimer: My knowledge on this topic is not in depth (as I said, I'm still learning). I haven't heard of Z3 but it says it's a theorem prover, so it would be comparable to systems like Coq, Isabelle, which are also considered programming languages, and then compared to Agda, Idris, and, last but not the least, Haskell. So a distilled form of your question would be: - How does logic programming compare to pure functional programming and programming based on type theory? For that I would probably try to read the following [1] before spending more time on it. - How does Prolog compare to Haskell? For this I'd probably look at something like this [2] I'm not too well-versed in the SML/OCaml/Haskell arena, but if I have to venture a guess, if we try to build a complex GOFAI system in prolog vs in haskell, the prolog system would have less amount of prolog code and most of the complexity would reside in the database of facts, whereas in haskell, all/most of the complexity would manifest in the form of haskell code. Another difference would be that a logic programming system comes with a general purpose inference engine and you can build any expert system using it, but you have to provide the relevant knowledge base. Whereas Haskell comes with a custom-built inference engine (the Hindley-Milner type inference) that only knows about types (if you need to build an expert system in Haskell, you would first build a general purpose inference engine, and essentially a prolog-like system, before you do anything else). On the flip side, Prolog program interpretation mechanism would probably be considered ad hoc, whereas Haskell program interpretation is based on type theory. So a Haskell programmer would probably have to worry less about program correctness. [1] http://stackoverflow.com/questions/8297574 http://stackoverflow.com/questions/8297574 [2] http://stackoverflow.com/questions/1932770 http://stackoverflow.com/questions/1932770 EDIT: And theorem proving also connects to areas of model checking, specification languages, as well as compiler backend areas like operational/denotational semantics. Like I said it's a tangled web of many core CS areas. EDIT 2: On further reading, Z3 is listed on this wikipedia page [3] as a constraint-programming (CP) library for an imperative language. The contrast between CP and CLP is mentioned on that page (as well as both Z3 and Prolog). (that also means Z3 is not really comparable to Coq, Isabelle as I said earlier. Coq, Isabelle are interactive theorem provers or proof assistants, not automatic theorem provers which is a lot harder to do). Another useful discussion [4] [3] https://en.wikipedia.org/wiki/Constraint_programming https://en.wikipedia.org/wiki/Constraint_programming [4] http://cs.stackexchange.com/questions/14946 http://cs.stackexchange.com/questions/14946
pcmonk 10y ago
Another language reminiscent of Prolog is Clingo (web repl: https://potassco.org/clingo/run/ https://potassco.org/clingo/run/). It's a lot like Prolog, but it's based in answer set programming, which gives you nice guarantees like "doesn't matter what order you write the rules in" and "always terminates".
- gmfawcett 10y ago
  Thanks, I hadn't heard of that one! Another very interesting language in the Prolog family is Mercury (http://www.mercurylang.org/ http://www.mercurylang.org/), which has a more functional and static flavour than Prolog, and has a suite of compilers that can produce quite efficient code.
saosebastiao 10y ago
You forgot the most successful logic programming language to date: SQL.
- gtycomb 10y ago
  Can SQL do resolution or backtracking similar to Prolog, I wonder.
  - benjiweber 10y ago
    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/prologpages/search.html https://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpa... becomes something like this in SQL. example=# select * from red; item --------- apple_1 block_1 car_27 (3 rows) example=# select * from car; item ----------- desoto_48 edsel_57 (2 rows) example=# select * from blue; item ---------- flower_3 glass_9 honda_81 (3 rows) example=# select * from bike; item ---------- iris_8 my_bike honda_81 (3 rows) example=# CREATE view fun as (select item from red NATURAL JOIN car) UNION (select item from blue NATURAL JOIN bike); CREATE VIEW example=# SELECT * FROM fun; item ---------- honda_81 (1 row)
    - tom_mellior 10y ago
      This is all true, but only for the small subset of Prolog that happens to be introduced on that web page. This analogy breaks down as soon as you have more complex data, not just atoms, or as soon as you introduce recursive rules. 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".
      - benjiweber 10y ago
JohnStrange 10y ago
Minikanren is not a viable substitute for Prolog. But yes, there are other logic programming languages worth trying. I've never tried it myself but heard good things about Mercury.
- harperlee 10y ago
  Could you expand a little bit on why not? My limited experience with minikanren and core.logic is that non-relational goals from prolog (cuts etc) exist, but are discouraged, and several CLP flavours that provide relational goals with constraints are proposed as alternative (although they are not very exhaustive). You can also project and use normal clojure on grounded variables... Honest question, I'm trying to learn new things, not trying to sound as an expert!! As I said, limited experience.
mmarx 10y ago
> - There is also datalog, with pydatalog it's python equivalent. Datalog is a strict subset of Prolog that guarantees termination (over finite sets), i.e., it's not turing-complete. This makes it more suitable for knowledge representation tasks than general programming. pydatalog is a specific implementation of a datalog reasoner.
slig 10y ago
> Just try to solve the zebra puzzle [1] (without help if you can, esp. through any of Norvig posts or videos; they're addictive). FWIW, I generated (using a small Python script) a bunch of zebra puzzles [1] that can be played on the browser, including the original "Einstein's Riddle" [2] [1] https://www.brainzilla.com/logic/zebra/ https://www.brainzilla.com/logic/zebra/ [2] https://www.brainzilla.com/logic/zebra/einsteins-riddle/ https://www.brainzilla.com/logic/zebra/einsteins-riddle/
wuschel 10y ago
I wonder what the difference is between, say, SWI-Prolog, and a graph database/query system like Neo4J?
- mmarx 10y ago
  Prolog is a turing-complete programming language suitable for general programming tasks. Datalog is a subset of Prolog that is suitable for use as a database/query system. The main difference between datalog and Neo4J is that datalog allows for predicates of arbitrary arity.
agumonkey 10y ago
I was surprised by the number of books on CLP at a large public library. It seems that it became the main interest on "logic" programming.
YeGoblynQueenne 10y ago
>> 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., It is also by far the most popular logic programming language, in terms of the number of users and the number of different interpreters. It's a bit like LISP and functional languages, although of course functional programming has been adopted far more than logic programming so there's many more functional, than logic programming languages.
- bpyne 10y ago
  Out of curiosity, have you used Curry? The combination of logic and functional paradigms in one language is intriguing to me, but I have no time (right now) to play with it.
  - YeGoblynQueenne 10y ago
    I haven't, no. I should probably check it out, the combination is very promising. I tried out Mercury very briefly a few years ago but only briefly. Swi Prolog 7.x has added some rudimentary functional ish facilities (basically, dicts, named data structures that you can access using a dot-notation), although nothing as complete as Mercury.
YeGoblynQueenne 10y ago
>> EDIT: ILP at an advanced level starts making connections with PGMs (probabilistic graphical models) and hence machine learning, but its a long way to go for me (in terms of learning) before I start to make sense of all these puzzle pieces. ILP is machine learning, it's a family of algorithms that learn logic programs usually from structured data. So for instance, table rows go in one end and Prolog clauses come out the other end. Connections with PGMs... hmm, not sure what you mean. There are probabilistic ILP algorithms, like Stochastic Relational Learning [1] and Probabilistic ILP [2], but I think you're probably referring to probablistic logic programming a family of probabilistic programming languages either based on Prolog, like PRISM [3], or having logic programming characteristics. PRISM in particular is basically Prolog with probabilities and probabilistic algorithms like Expectation-Maximisation. Prolog's depth-first search tree plus probabilities to guide branching does sound an awful lot like a PGM so I'm guessing that's what you mean. Source: personal interst in ILP and I'm starting a PhD on the subject in September :) __________________ [1] Introduction to Statistical and Relational Learning (Book by Lise Getoor and Ben Taskar): http://www.cs.umd.edu/srl-book/ http://www.cs.umd.edu/srl-book/ [2] Probabilistic Inductive Logic Programming (paper in Lecture notes in AI, by Luc De Raedt and Kristian Kersting): http://people.csail.mit.edu/kersting/ecmlpkdd05_pilp/pilp.pdf http://people.csail.mit.edu/kersting/ecmlpkdd05_pilp/pilp.pd... [3] That's the PRISM that stands for Programming In Statistical modelling, by Taisuke Sato: http://rjida.meijo-u.ac.jp/prism/ http://rjida.meijo-u.ac.jp/prism/
- fizixer 10y ago
  Thanks for the comment and references. Good luck with your PhD program. > ... Connections with PGMs... hmm, not sure what you mean. What I meant is that ILP, PGM, HMM, are some of the topics that were being explored as an extension to GOFAI in the 1990s and first half of 2000s before the 2006 breakthrough results by Hinton which drastically shifted the focus towards NNs, Deep learning, etc. Essentially these topics were being explored as a result of the slow realization that logic is not enough to represent highly complex systems, and there is a need to move towards a hybrid of logical and probabilistic approaches. I'm keenly interested in these areas but currently busy with graduate work related to numerical analysis and scientific computing. In our circles 'adaptive' is the big word, and there is attempt to utilize AI/ML methodologies in scientific simulation, but it's at a very early stage. Once my work is finished, I hope to get more involved in ML related research and applications.

by fizixer 10y ago

eriknstr 10y ago

>Zebra puzzle Interesting puzzle. I copied the puzzle text to a separate text file so that one does not accidentally read anything else in the Wikipedia article. https://pastebin.com/0DWbSSx3 https://pastebin.com/0DWbSSx3

eriknstr 10y ago
I've worked a bit on it. My solution is not incredible or anything, probably there are far more efficient and/or elegant solutions out there. Mine is not done yet but I'm going to continue with this one later and by then the activity in this thread will be over so I leave this link here now. https://github.com/eriknstr/puzzles/blob/master/zebra/solution.py https://github.com/eriknstr/puzzles/blob/master/zebra/soluti...
- philsnow 10y ago
  Fun problem. My solution doesn't do really any "logic programming", and it takes around 2 minutes to run on my laptop. https://gist.github.com/philsnow/02e747241d46106b14b60146e5803e49 https://gist.github.com/philsnow/02e747241d46106b14b60146e58... The middle huge nested thing (where `some_possible_worlds` is defined) is gross but I'm not great with ruby and I couldn't think of another way to not blow up memory enumerating all the worlds just to eliminate 99% of them.
  - carapace 10y ago
    I worked up this from the SEND MORE MONEY example in the CLP(FD) repo. https://gist.github.com/calroc/603ed919bc814ccee10c1b3df6142fec https://gist.github.com/calroc/603ed919bc814ccee10c1b3df6142... There are five houses. The Englishman lives in the red house. The Spaniard owns the dog. Coffee is drunk in the green house. The Ukrainian drinks tea. The green house is immediately to the right of the ivory house. The Old Gold smoker owns snails. Kools are smoked in the yellow house. Milk is drunk in the middle house. The Norwegian lives in the first house. The man who smokes Chesterfields lives in the house next to the man with the fox. Kools are smoked in the house next to the house where the horse is kept. The Lucky Strike smoker drinks orange juice. The Japanese smokes Parliaments. The Norwegian lives next to the blue house. Now, who drinks water? Who owns the zebra? In the interest of clarity, it must be added that each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarets [sic]. One other thing: in statement 6, right means your right. :- use_module(library(clpfd)). house_next_to(H0, H1) :- abs(H0 - H1) #= 1. puzzle([ GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse, Englishman, Spaniard, Ukrainian, Norwegian, Japanese, Dog, Snails, Fox, Horse, Zebra, Coffee, Tea, Milk, OrangeJuice, Water, OldGold, Kools, Chesterfields, LuckyStrike, Parliaments ]) :- Vars = [GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse, Englishman, Spaniard, Ukrainian, Norwegian, Japanese, Dog, Snails, Fox, Horse, Zebra, Coffee, Tea, Milk, OrangeJuice, Water, OldGold, Kools, Chesterfields, LuckyStrike, Parliaments ], Vars ins 1..5, all_distinct([GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse]), all_distinct([Englishman, Spaniard, Ukrainian, Norwegian, Japanese]), all_distinct([Dog, Snails, Fox, Horse, Zebra]), all_distinct([Coffee, Tea, Milk, OrangeJuice, Water]), all_distinct([OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]), Englishman #= RedHouse, Spaniard #= Dog, Coffee #= GreenHouse, Ukrainian #= Tea, GreenHouse #= 1 + IvoryHouse, OldGold #= Snails, Kools #= YellowHouse, Milk #= 3, Norwegian #= 1, house_next_to(Chesterfields, Fox), house_next_to(Kools, Horse), LuckyStrike #= OrangeJuice, Japanese #= Parliaments, house_next_to(Norwegian, BlueHouse). Then to print out the solution after loading the program above use: puzzle([ GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse, Englishman, Spaniard, Ukrainian, Norwegian, Japanese, Dog, Snails, Fox, Horse, Zebra, Coffee, Tea, Milk, OrangeJuice, Water, OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]), label([ GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse, Englishman, Spaniard, Ukrainian, Norwegian, Japanese, Dog, Snails, Fox, Horse, Zebra, Coffee, Tea, Milk, OrangeJuice, Water, OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]).
sriram_malhar 10y ago
My z3 based solution in python looks like this: https://gist.github.com/sriram-srinivasan/2981825217f0802d9fbd9878578a711d https://gist.github.com/sriram-srinivasan/2981825217f0802d9f...

tunesmith 10y ago

It still seems fairly untapped in enterprise and entrepreneurial circles, too. I've been wanting to create a side project that is sort of like an expert system, except where users can create the rules as well as the facts, and that is also horizontally scalable (which doesn't seem to be a good fit for the Rete algorithm). So I'm not sure if I'm looking for some sort of jvm-runtime logic programming system that can be combined with a graph database or what.

Karrot_Kream 10y ago

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 Neolithic toy. Not only that but Prolog's Syntax gives you very similar properties to lisp's homoiconicity (first class atoms, metaprogramming, etc). Sure you can reimplement all of this in miniKanren, but it's all there waiting for you in SWI Prolog already! There's a lot more to a language than just its concepts. Every time I hack in Prolog I always feel like I'm living the idea that I "tell the computer what to do not how to do it". It's a shame that more folks don't use it.

random_gui2 10y ago
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?
- Karrot_Kream 10y ago
  I typically wrap up a left recursive rule as another rule, and then have this rule choose between the base case and the recursive case. This is a pretty standard technique to break down left recursive rules though, and has nothing to do with Prolog, and everything to do with writing parsers.
- YeGoblynQueenne 10y ago
  To complement Karrot_Kream's answer, there's another two things you can do if you're having DCG left-recursion troubles: The first thing is to use a different parsing strategy. For instance, the Earley parser [1] used to be a typical example of (advanced ish) Prolog and wikipedia says that it performs particularly well with left-recursive languages. The disadvantage of course is that you're giving up the simplicity of having a built-in grammar-and-parser capability in your language. But in some cases that's probably a very small price to pay. The other thing you can do, which is in a sense the exact opposite of changing parsers, is to eliminate the possibility of left-recursion from your DCGs by choosing a grammar formalism that precludes it. It boils down to keeping all your rules looking like this: P --> [a₁, a₂, ..., aₙ], A₁, A₂, .... Aₘ. Where each Aᵢ is a terminal or nonterminal and each [aₖ] a terminal. In other words, expand every nonterminal first to one or more terminals, then any mix of terminals and nonterminals. That way you'll always accept a terminal before expanding a nonterminal and there's no chance of left-recursion. You can write a short syntax checker to enforce this rule in a post-processing step, or just do it by hand. You can be a little bit more rigorous and stick to more strict forms, particularly right-regular grammars, or Greibach Normal Form [2], if your grammars are context-free. Right regular grammars allow a single nonterminal on the right-hand side: A --> [a], B. Whereas Greibach Normal Form allows a single terminal followed by any number of nonterminals: P --> [a], A₁, A₂, .... Aₙ. The benefit of GNF is that any context-free grammar can be transformed into a grammar in GNF, so you can first write your grammars in a loose form, then convert them to GNF to remove left-recursions. If you want I can probably dig up a reference to how to do the conversion. ___________ [1] https://en.wikipedia.org/wiki/Earley_parser https://en.wikipedia.org/wiki/Earley_parser [2] https://en.wikipedia.org/wiki/Greibach_normal_form https://en.wikipedia.org/wiki/Greibach_normal_form

gugagore 10y ago

Here are some (I thought helpful) comments regarding some of the tools you mentioned https://github.com/logpy/logpy/issues/24#issuecomment-269444915 https://github.com/logpy/logpy/issues/24#issuecomment-269444...

est 10y ago

what about this? https://github.com/Z3Prover/z3 https://github.com/Z3Prover/z3 Is it comparable with prolog or just a subset of prolog?

dreamcompiler 10y ago
Z3 is a theorem prover; it's a tool you would use to formally analyze a hardware logic design or a software program to ensure that it meets certain criteria (e.g. that it contains none of a certain class of security vulnerabilities). Theorem provers incorporate a lot of the same basic ideas as Prolog, but they're specialized tools (many have been written in Prolog). Prolog itself is a general-purpose programming language.
fizixer 10y ago
Disclaimer: My knowledge on this topic is not in depth (as I said, I'm still learning). I haven't heard of Z3 but it says it's a theorem prover, so it would be comparable to systems like Coq, Isabelle, which are also considered programming languages, and then compared to Agda, Idris, and, last but not the least, Haskell. So a distilled form of your question would be: - How does logic programming compare to pure functional programming and programming based on type theory? For that I would probably try to read the following [1] before spending more time on it. - How does Prolog compare to Haskell? For this I'd probably look at something like this [2] I'm not too well-versed in the SML/OCaml/Haskell arena, but if I have to venture a guess, if we try to build a complex GOFAI system in prolog vs in haskell, the prolog system would have less amount of prolog code and most of the complexity would reside in the database of facts, whereas in haskell, all/most of the complexity would manifest in the form of haskell code. Another difference would be that a logic programming system comes with a general purpose inference engine and you can build any expert system using it, but you have to provide the relevant knowledge base. Whereas Haskell comes with a custom-built inference engine (the Hindley-Milner type inference) that only knows about types (if you need to build an expert system in Haskell, you would first build a general purpose inference engine, and essentially a prolog-like system, before you do anything else). On the flip side, Prolog program interpretation mechanism would probably be considered ad hoc, whereas Haskell program interpretation is based on type theory. So a Haskell programmer would probably have to worry less about program correctness. [1] http://stackoverflow.com/questions/8297574 http://stackoverflow.com/questions/8297574 [2] http://stackoverflow.com/questions/1932770 http://stackoverflow.com/questions/1932770 EDIT: And theorem proving also connects to areas of model checking, specification languages, as well as compiler backend areas like operational/denotational semantics. Like I said it's a tangled web of many core CS areas. EDIT 2: On further reading, Z3 is listed on this wikipedia page [3] as a constraint-programming (CP) library for an imperative language. The contrast between CP and CLP is mentioned on that page (as well as both Z3 and Prolog). (that also means Z3 is not really comparable to Coq, Isabelle as I said earlier. Coq, Isabelle are interactive theorem provers or proof assistants, not automatic theorem provers which is a lot harder to do). Another useful discussion [4] [3] https://en.wikipedia.org/wiki/Constraint_programming https://en.wikipedia.org/wiki/Constraint_programming [4] http://cs.stackexchange.com/questions/14946 http://cs.stackexchange.com/questions/14946

pcmonk 10y ago

Another language reminiscent of Prolog is Clingo (web repl: https://potassco.org/clingo/run/ https://potassco.org/clingo/run/). It's a lot like Prolog, but it's based in answer set programming, which gives you nice guarantees like "doesn't matter what order you write the rules in" and "always terminates".

gmfawcett 10y ago
Thanks, I hadn't heard of that one! Another very interesting language in the Prolog family is Mercury (http://www.mercurylang.org/ http://www.mercurylang.org/), which has a more functional and static flavour than Prolog, and has a suite of compilers that can produce quite efficient code.

saosebastiao 10y ago

You forgot the most successful logic programming language to date: SQL.

gtycomb 10y ago
Can SQL do resolution or backtracking similar to Prolog, I wonder.
- benjiweber 10y ago
  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/prologpages/search.html https://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpa... becomes something like this in SQL. example=# select * from red; item --------- apple_1 block_1 car_27 (3 rows) example=# select * from car; item ----------- desoto_48 edsel_57 (2 rows) example=# select * from blue; item ---------- flower_3 glass_9 honda_81 (3 rows) example=# select * from bike; item ---------- iris_8 my_bike honda_81 (3 rows) example=# CREATE view fun as (select item from red NATURAL JOIN car) UNION (select item from blue NATURAL JOIN bike); CREATE VIEW example=# SELECT * FROM fun; item ---------- honda_81 (1 row)
  - tom_mellior 10y ago
    This is all true, but only for the small subset of Prolog that happens to be introduced on that web page. This analogy breaks down as soon as you have more complex data, not just atoms, or as soon as you introduce recursive rules. 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".
    - benjiweber 10y ago

JohnStrange 10y ago

Minikanren is not a viable substitute for Prolog. But yes, there are other logic programming languages worth trying. I've never tried it myself but heard good things about Mercury.

harperlee 10y ago
Could you expand a little bit on why not? My limited experience with minikanren and core.logic is that non-relational goals from prolog (cuts etc) exist, but are discouraged, and several CLP flavours that provide relational goals with constraints are proposed as alternative (although they are not very exhaustive). You can also project and use normal clojure on grounded variables... Honest question, I'm trying to learn new things, not trying to sound as an expert!! As I said, limited experience.

mmarx 10y ago

> - There is also datalog, with pydatalog it's python equivalent. Datalog is a strict subset of Prolog that guarantees termination (over finite sets), i.e., it's not turing-complete. This makes it more suitable for knowledge representation tasks than general programming. pydatalog is a specific implementation of a datalog reasoner.

slig 10y ago

> Just try to solve the zebra puzzle [1] (without help if you can, esp. through any of Norvig posts or videos; they're addictive). FWIW, I generated (using a small Python script) a bunch of zebra puzzles [1] that can be played on the browser, including the original "Einstein's Riddle" [2] [1] https://www.brainzilla.com/logic/zebra/ https://www.brainzilla.com/logic/zebra/ [2] https://www.brainzilla.com/logic/zebra/einsteins-riddle/ https://www.brainzilla.com/logic/zebra/einsteins-riddle/

wuschel 10y ago

I wonder what the difference is between, say, SWI-Prolog, and a graph database/query system like Neo4J?

mmarx 10y ago
Prolog is a turing-complete programming language suitable for general programming tasks. Datalog is a subset of Prolog that is suitable for use as a database/query system. The main difference between datalog and Neo4J is that datalog allows for predicates of arbitrary arity.

agumonkey 10y ago

I was surprised by the number of books on CLP at a large public library. It seems that it became the main interest on "logic" programming.

YeGoblynQueenne 10y ago

>> 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., It is also by far the most popular logic programming language, in terms of the number of users and the number of different interpreters. It's a bit like LISP and functional languages, although of course functional programming has been adopted far more than logic programming so there's many more functional, than logic programming languages.

bpyne 10y ago
Out of curiosity, have you used Curry? The combination of logic and functional paradigms in one language is intriguing to me, but I have no time (right now) to play with it.
- YeGoblynQueenne 10y ago
  I haven't, no. I should probably check it out, the combination is very promising. I tried out Mercury very briefly a few years ago but only briefly. Swi Prolog 7.x has added some rudimentary functional ish facilities (basically, dicts, named data structures that you can access using a dot-notation), although nothing as complete as Mercury.

YeGoblynQueenne 10y ago

>> EDIT: ILP at an advanced level starts making connections with PGMs (probabilistic graphical models) and hence machine learning, but its a long way to go for me (in terms of learning) before I start to make sense of all these puzzle pieces. ILP is machine learning, it's a family of algorithms that learn logic programs usually from structured data. So for instance, table rows go in one end and Prolog clauses come out the other end. Connections with PGMs... hmm, not sure what you mean. There are probabilistic ILP algorithms, like Stochastic Relational Learning [1] and Probabilistic ILP [2], but I think you're probably referring to probablistic logic programming a family of probabilistic programming languages either based on Prolog, like PRISM [3], or having logic programming characteristics. PRISM in particular is basically Prolog with probabilities and probabilistic algorithms like Expectation-Maximisation. Prolog's depth-first search tree plus probabilities to guide branching does sound an awful lot like a PGM so I'm guessing that's what you mean. Source: personal interst in ILP and I'm starting a PhD on the subject in September :) __________________ [1] Introduction to Statistical and Relational Learning (Book by Lise Getoor and Ben Taskar): http://www.cs.umd.edu/srl-book/ http://www.cs.umd.edu/srl-book/ [2] Probabilistic Inductive Logic Programming (paper in Lecture notes in AI, by Luc De Raedt and Kristian Kersting): http://people.csail.mit.edu/kersting/ecmlpkdd05_pilp/pilp.pdf http://people.csail.mit.edu/kersting/ecmlpkdd05_pilp/pilp.pd... [3] That's the PRISM that stands for Programming In Statistical modelling, by Taisuke Sato: http://rjida.meijo-u.ac.jp/prism/ http://rjida.meijo-u.ac.jp/prism/

fizixer 10y ago
Thanks for the comment and references. Good luck with your PhD program. > ... Connections with PGMs... hmm, not sure what you mean. What I meant is that ILP, PGM, HMM, are some of the topics that were being explored as an extension to GOFAI in the 1990s and first half of 2000s before the 2006 breakthrough results by Hinton which drastically shifted the focus towards NNs, Deep learning, etc. Essentially these topics were being explored as a result of the slow realization that logic is not enough to represent highly complex systems, and there is a need to move towards a hybrid of logical and probabilistic approaches. I'm keenly interested in these areas but currently busy with graduate work related to numerical analysis and scientific computing. In our circles 'adaptive' is the big word, and there is attempt to utilize AI/ML methodologies in scientific simulation, but it's at a very early stage. Once my work is finished, I hope to get more involved in ML related research and applications.