17 ms·

The Power of Prolog

348 points by noch 10y ago

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.
jacquesm 10y ago
One of the nicest examples of the power of prolog is that Windows NT contained a prolog implementation to take care of network configuration, replacing the previous codebase: http://www.redditmirror.cc/cache/websites/web.archive.org_84624/web.archive.org/web/20040603192757/research.microsoft.com/research/dtg/davidhov/pap.htm http://www.redditmirror.cc/cache/websites/web.archive.org_84...
- Jtsummers 10y ago
  My one regret in a project at work (internal tool) was that I didn't persuade management to let me use an embedded prolog in the application. Instead I rewrote half of Prolog (badly) in C#.
  - andai 10y ago
    I don't get it. Isn't that the same thing but worse? Edit: Also, Greenspun's Tenth Rule of Programming: Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.
    - Jtsummers 10y ago
      It was worse. That office had an aversion to anything not-Microsoft for dev tools unless they were for the embedded systems we maintained. They also had an aversion to any language that wasn't "industry standard", whatever that meant (because, clearly, prolog and others do have industry standards associated with them; here they meant commonly used and easy to hire for).
      - julian_1 10y ago
        This is a frustration of mine. At university they try to install a knowledge of all kinds of crazy languages, before you're ready to appreciate their value and the issues they attempt to address. The most glaring example is probably teaching Haskell in first-year. As a working programmer, you're then corralled into following prescriptive industry-practice - that always errs on the side of dumbing down the choice of technologies available.
timonoko 10y ago
Never understood why natural numbers (or some set of N) is not in the search space: fib(X,X):- X<2. fib(X,Y1+Y2):- fib(X-1,Y1),fib(X-2,Y2). I tried to get answer to this kwestion in reddit, but all I got was personal insults.
- colanderman 10y ago
  You can do this in SWI Prolog using the between/3 predicate for the inequality, and the is/2 predicate for the arithmetic.
  - colanderman 10y ago
    Example, now that I'm at a terminal: fib(X, X) :- between(0, 1, X). fib(X, Y) :- (var(Y) -> between(2, infinite, X); MaxX is Y + 1, between(2, MaxX, X)), X1 is X - 1, X2 is X - 2, fib(X1, Y1), fib(X2, Y2), Y is Y1 + Y2. The trick with var/1 allows the fib(-, +) instantiation to terminate (albeit very slowly). Otherwise it's not necessary. What's even cooler is SWI-Prolog's CLP support. You can write fib/2 in the obvious manner and support all instantiations: ?- use_module(library(clpfd)). fib(X, X) :- X #>= 0, X #=< 1, indomain(X). fib(X, Y) :- X #>= 2, X #=< Y + 1, X1 #= X - 1, X2 #= X - 2, Y #= Y1 + Y2, fib(X1, Y1), fib(X2, Y2).
  - thisrod 10y ago
    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 that can solve linear algebra problems like that?
    - colanderman 10y ago
      SWI-Prolog has CLP extensions to do exactly that: http://www.swi-prolog.org/pldoc/man?section=clp 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.
signa11 10y ago
erlang syntax is prolog inspired, not sure if that's a good thing though :)
- nextos 10y ago
  Not just inspired. It was initially implemented in Prolog!
- macintux 10y ago
  The prologesque syntax gets a lot of grief, but I genuinely appreciate it. I like my different paradigm languages to look different, helps me think differently. (but it's much closer to Algol than Lisp is, so I don't have to bend my brain quite that hard)
- defined 10y ago
  I like it. There are some annoyances to do with minor syntactical warts, like commas and semicolons, but all in all, I find it expressive.
rcgorton 10y ago
The power: require a rethink of approaches to programming The failure: the claim by such folk that all compute problems are best solved by prolog/clojure/related even when such a domain specific language is not pertinent.
taylorking 10y ago
love(prolog).
- ragebol 10y ago
  true
- vram22 10y ago
  love(prolog) :- love(logic_programming), love(elegance).
hexmiles 10y ago
i have always trouble understaing prolog, lot of guide online seem to just tackle the syntax or assume you already know a lot of logic programming, for example the first example in the link (https://www.metalevel.at/prolog/facets https://www.metalevel.at/prolog/facets): list_length([], 0). list_length([_|Ls], N) :- N #> 0, N #= N0 + 1, list_length(Ls, N0). i don't undestand it, i read the segment describing it multiple time but i still don't get it, and is not the syntax i don't undestand how it should work, a tried reading the next few chapter but i feel i'm missing something! is there a "prolog for dummies" out there?
- sordina 10y ago
  Check out https://en.wikipedia.org/wiki/Horn_clause https://en.wikipedia.org/wiki/Horn_clause You can read this as two statements: "The length of a list is 0, if the list is empty." "Otherwise, if the length of a list Ls is N0, and N is N0 + 1, and N is greater than 0, then Ls with an additional element is of length N.
  - na85 10y ago
    Good lord, does that mean it's necessary to explicitly tell the compiler the length of an empty list? Shouldn't the list type already know its own size? I fail to see the benefit... honestly it just seems like a waste of time.
    - tathougies 10y ago
      No. This is the standard implementation of the length/2 predicate. Like any other language, prolog has a standard library that includes this predicate. You'd never need to write this in practice, but this is how it would be written in the standard library. In general, any general purpose language worth it's salt will have substantial portions of its standard library written in that language, and in this regard, prolog meets the criteria for respectsbl languages
      - Koshkin 10y ago
haddr 10y ago
There is a class of problems which you can solve using Prolog with pure pleasure. There is one thing however: Prolog can magically hide the complexity of many things, which is a two-sided sword. On many occasions you are hiding away the computational complexity and wonder why the execution is so slow. This rarely happens in imperative languages (where you are more aware of all the loops and recursions). I guess this is why many people hate Prolog...
- Karrot_Kream 10y ago
  > 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 execution model: a lot of beginners just don't understand how the depth first search unification algorithm really works. Playing around in the REPL should help build that Intuition fairly quickly though. I can post a concrete example if you want. Recently I changed an O(n^2) goal to an O(n) one and didn't have much trouble debugging it at all. I'm on mobile now but can post it later if you want.
  - carapace 10y ago
    I'd like to hear that story, when you get the chance. ;-)
    - drunkpotato 10y ago
      Me too, please post!
    - Karrot_Kream 10y ago
      Sure and thanks for the wait! 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 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).
moderation 10y ago
See the Open Policy Agent [1] project that has a language and REPL called Rego inspired by Datalog. 1. http://www.openpolicyagent.org/documentation/how-do-i-write-policies/ http://www.openpolicyagent.org/documentation/how-do-i-write-...
zodiac 10y ago
I wrote some prolog for a PL class recently and had to debug some cases of nontermination caused by the depth-first-search unification algorithm. I was wondering why prolog (or some other logic programming language) couldn't use breadth-first search instead, to avoid those cases, but couldn't find answers online - could someone who knows prolog better here have an answer?
- yeowMeng 10y ago
  BFS space complexity is order exponential.
- mballantyne 10y ago
  Other search algorithms can take up lots of memory to store progress they've made down different paths. Having only one active state also lets you map unification down to efficient low level cpu operations. If you have multiple states, you either have to copy lots of data when you fork the state or you use a persistent data structure but can't use side effects, so everything is a bit slower. It's a tradeoff though. I work on miniKanren, which is a logic programming language with a complete search that doesn't hit the nontermination issues you mention. The complete search lets us do some pretty cool stuff with program synthesis (though we're not about to put any programmers out of business just yet): https://www.youtube.com/watch?v=er_lLvkklsk https://www.youtube.com/watch?v=er_lLvkklsk Note that you can implement iterative deepening depth first search on top of prolog if you want a complete search there. Iterative deepening takes a little more time but avoids the memory problems with breath-first. SWI has tools built in to help there: http://www.swi-prolog.org/pldoc/doc_for?object=call_with_depth_limit/3 http://www.swi-prolog.org/pldoc/doc_for?object=call_with_dep... And I believe Ciao implements its iterative deepening library with a meta-interpreter: https://ciao-lang.org/docs/ciao/id_doc.html#0 https://ciao-lang.org/docs/ciao/id_doc.html#0
hota_mazi 10y ago
Prolog's mathematical foundation is sound but the devil is in the details, and very soon, you encounter two of Prolog's most glaring flaws that lead to spaghetti code worse than what even BASIC ever produced: - It's dynamically typed - The cut operator
- gmfawcett 10y ago
  If you like Prolog, but want static typing and no cut operator, you might really like Mercury (https://mercurylang.org/ https://mercurylang.org/).
nwatson 10y ago
The Japanese government spent US $400 million in the '80's (a lot in those days) to try to jump ahead of "western" computer technology via its "5th Generation Project". https://news.ycombinator.com/item?id=14047780 https://news.ycombinator.com/item?id=14047780 The basis for it all ... Prolog.
- rdtsc 10y ago
  > Japanese Government said this week that it was willing to give away the software developed by the project to anyone who wanted it, even foreigners. Was wondering what they released as a result. Surely after a $400 in 80's money they had some lines of code written. Apparently they focused on concurrent logic programming and wasted a lot of money on exotic hardware in https://en.wikipedia.org/wiki/Fifth_generation_computer https://en.wikipedia.org/wiki/Fifth_generation_computer by the time they were done off-the-shelf CPUs could run circles around the fancy workstations.
- dmh2000 10y ago
  and it was an epic fail https://en.wikipedia.org/wiki/Fifth_generation_computer#Failure https://en.wikipedia.org/wiki/Fifth_generation_computer#Fail... A primary problem was the choice of concurrent logic programming as the bridge between the parallel computer architecture and the use of logic as a knowledge representation and problem solving language for AI applications.
  - zmonx 10y ago
    Personal anecdote: I once asked a retired Japanese computer scientist why the 5th generation project had failed. He replied with: "What do you mean 'failed'? All my colleagues who worked on this project have become professors!" In this respect, the project was actually a smashing success.
lacampbell 10y ago
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.
- ahelwer 10y ago
  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.
  - lacampbell 10y ago
    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.
    - tom_mellior 10y ago
      It is indeed backtracking as a language, but you don't get optimization entirely for free. The backtracking part only means that you can write down a problem that has multiple solutions and get Prolog to enumerate those solutions using its default order. 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.
      - bloaf 10y ago
        Would it work well for algorithms like A*, or other quazi-AI problems that crop up in games?
skdotdan 10y ago
Something I would like to be able to understand/know/study is how logic programming languages are implemented and how their runtime looks like.
- c-cube 10y ago
  you can start by looking for "warren abstract machine" (usually shortened as WAM). It's an intermediate format for compiling prolog programs (sets of Horn clauses, that is, rules). It makes every operation very explicit, including unification (to match the current goal against each rule's conclusion) and backtracking (to enumerate solutions; this involves stacks, unsurprisingly). I think most state of the art prolog implementations are then able to compile this format to native code. Of course prolog also requires that the runtime has a GC (to collect dead terms) and that it can dynamically add/remove rules, use reflection to observe the shape of a term, etc. https://en.wikipedia.org/wiki/XSB https://en.wikipedia.org/wiki/XSB is an implementation to which Warren contributes, with additional features such as tabling (a powerful form of memoization that avoids many infinite recursions).
- hyperion2010 10y ago
  http://www.amzi.com/articles/prolog_under_the_hood.htm http://www.amzi.com/articles/prolog_under_the_hood.htm I find this article very helpful when it comes to understanding how Prolog actually works.
  - smarx007 10y ago
    http://archive.is/RSzu http://archive.is/RSzu
- pg314 10y ago
  Section 4.4 in Structure and Implementation of Computer Programs [1] presents an implementation of a Prolog-like logic programming language in Scheme. It is very instructive to contrast it to the meta-circular evaluator of Scheme in that same book to see the similarities and differences. Paradigms of Artificial Programming by Norvig also contains a chapter implementing Prolog in Common Lisp. The code can be found at [2]. [1] https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-29.html#%_sec_4.4 https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-29.htm... [2] http://norvig.com/paip/prolog.lisp http://norvig.com/paip/prolog.lisp
samwalrus 10y ago
I run a youtube channel called 'playing with prolog' https://www.youtube.com/channel/UCfWpIHmy5MEx2p9c_GJrE_g https://www.youtube.com/channel/UCfWpIHmy5MEx2p9c_GJrE_g We demo little things that you can do in prolog. Happy to take suggestions for videos :)
pjc50 10y ago
"No." (Disclaimer: this is a joke referencing prolog's default return when it can't find a solution.)
bschwindHN 10y ago
I once wanted to solve a problem that is perfect for Prolog, but I wanted it in Clojure. Turns out there's a great library for that! I don't think it has the full power of Prolog (I only know of Prolog and what it does but I've never used it), but for integer constraint programming it was a joy to work with. https://github.com/aengelberg/loco https://github.com/aengelberg/loco
deleted 10y ago
[deleted]
norswap 10y ago
If you want to exercise your Prolog-foo: https://github.com/norswap/prolog-dry https://github.com/norswap/prolog-dry
deleted 10y ago
[deleted]
mark_l_watson 10y ago
I bookmarked this. I have been revisiting my own programming history. I used Prolog a lot in the 1980s, partially because I was influenced by the ill-fated Japanese 5th generation project. A few weeks ago I pulled my old Prolog code experiments from an old repo. Prolog is a great language for some applications, and Swi-Prolog has some great libraries and sample programs. I also have used Common Lisp a lot since the 1980s and I am in the process of working through a few of the classic text books, and I have it on my schedule to update my own CL book with a second edition.
- FabHK 10y ago
  You had version control systems in the 80s? I had cassette tapes and later 5 1/4 inch floppy disks!
  - mark_l_watson 10y ago
    I moved everything to svn, and later to git repos. I actually had 8" floppy disks on my Xerox Lisp Machine. An unnatural size for floppy disks!
SagelyGuru 10y ago
I used to teach Prolog in the GOFAI days of early 80's. It certainly was fun and probably the quickest way how to start solving interesting search based problems without having to write pages and pages of code. It was very good for motivation. Also for encouraging "top-down" design.
arikrak 10y ago
Question - is prolog used in the real world? I.e. are there businesses that use prolog in production?
- zmonx 10y ago
  Yes, there are several businesses that use Prolog in production. For example, please see the quotes from the SICStus page, a professional Prolog system (ISO standard compliant) with many commercial applications: https://www.sics.se/projects/sicstus-prolog-leading-prolog-technology https://www.sics.se/projects/sicstus-prolog-leading-prolog-t... Here is a salient quote from the article: "SICStus Prolog is a workhorse in the transport and logistics industries, running systems that handle a third of all airline tickets, and helping railways to operate their trains better." Further major commercial applications of SICStus Prolog are listed at: https://sicstus.sics.se/customers.html https://sicstus.sics.se/customers.html These include a voice-operated procedure browser for the International Space Station, and a dispensation order generation algorithm for biological research. In addition, Prolog is often used in logistics software and for scheduling, among several other tasks for which it is very well suited. A commercial Prolog's multi-user license easily costs thousands of dollars, so an industrial strength Prolog system is not the kind of software you typically "just buy" as an individual. Typical customers of commercial Prolog systems are other companies, and also universities who buy licenses for research purposes and to teach Prolog.
andai 10y ago
For an introduction to Prolog: Learn Prolog Now - Free Online Version http://www.learnprolognow.org/lpnpage.php?pageid=online http://www.learnprolognow.org/lpnpage.php?pageid=online I like this one because it's beginner-friendly (and uses characters from Pulp Fiction as examples). -- edit: actually, The Power of Prolog to is great, too! If anyone knows more good resources, I'd be happy to hear about them!
camelNotation 10y ago
One of my professors in college was an original creator of the Prolog language. He made us learn Prolog so that he could teach us something we could have just as easily done in C or Java. I strongly disliked him. For that reason, I am filled with negative vibes when I think about Prolog.
pjonesdotca 10y ago
A great intro to Prolog can be found here if you're not the type that learns solely from reading. https://www.youtube.com/watch?v=SykxWpFwMGs https://www.youtube.com/watch?v=SykxWpFwMGs
huherto 10y ago
I implemented the Wumpus World form Peter Norvig's AIMA using different techniques. I found that Bayesian Logic was much more powerful than Logic programming. Perhaps that explains why Prolog has flourished. Logic programming is limited to values of true or false. 0 or 1. Bayesian logic can deal with uncertainty values like .2 or .3. It almost seems like a superset. It is also more intuitive IMHO. I keep the wumpus implementation here if anyone is interested. https://github.com/huherto/aima3/tree/master/src/wumpus https://github.com/huherto/aima3/tree/master/src/wumpus

348 points by noch 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.

jacquesm 10y ago

One of the nicest examples of the power of prolog is that Windows NT contained a prolog implementation to take care of network configuration, replacing the previous codebase: http://www.redditmirror.cc/cache/websites/web.archive.org_84624/web.archive.org/web/20040603192757/research.microsoft.com/research/dtg/davidhov/pap.htm http://www.redditmirror.cc/cache/websites/web.archive.org_84...

Jtsummers 10y ago
My one regret in a project at work (internal tool) was that I didn't persuade management to let me use an embedded prolog in the application. Instead I rewrote half of Prolog (badly) in C#.
- andai 10y ago
  I don't get it. Isn't that the same thing but worse? Edit: Also, Greenspun's Tenth Rule of Programming: Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.
  - Jtsummers 10y ago
    It was worse. That office had an aversion to anything not-Microsoft for dev tools unless they were for the embedded systems we maintained. They also had an aversion to any language that wasn't "industry standard", whatever that meant (because, clearly, prolog and others do have industry standards associated with them; here they meant commonly used and easy to hire for).
    - julian_1 10y ago
      This is a frustration of mine. At university they try to install a knowledge of all kinds of crazy languages, before you're ready to appreciate their value and the issues they attempt to address. The most glaring example is probably teaching Haskell in first-year. As a working programmer, you're then corralled into following prescriptive industry-practice - that always errs on the side of dumbing down the choice of technologies available.

timonoko 10y ago

Never understood why natural numbers (or some set of N) is not in the search space: fib(X,X):- X<2. fib(X,Y1+Y2):- fib(X-1,Y1),fib(X-2,Y2). I tried to get answer to this kwestion in reddit, but all I got was personal insults.

colanderman 10y ago
You can do this in SWI Prolog using the between/3 predicate for the inequality, and the is/2 predicate for the arithmetic.
- colanderman 10y ago
  Example, now that I'm at a terminal: fib(X, X) :- between(0, 1, X). fib(X, Y) :- (var(Y) -> between(2, infinite, X); MaxX is Y + 1, between(2, MaxX, X)), X1 is X - 1, X2 is X - 2, fib(X1, Y1), fib(X2, Y2), Y is Y1 + Y2. The trick with var/1 allows the fib(-, +) instantiation to terminate (albeit very slowly). Otherwise it's not necessary. What's even cooler is SWI-Prolog's CLP support. You can write fib/2 in the obvious manner and support all instantiations: ?- use_module(library(clpfd)). fib(X, X) :- X #>= 0, X #=< 1, indomain(X). fib(X, Y) :- X #>= 2, X #=< Y + 1, X1 #= X - 1, X2 #= X - 2, Y #= Y1 + Y2, fib(X1, Y1), fib(X2, Y2).
- thisrod 10y ago
  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 that can solve linear algebra problems like that?
  - colanderman 10y ago
    SWI-Prolog has CLP extensions to do exactly that: http://www.swi-prolog.org/pldoc/man?section=clp 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.

signa11 10y ago

erlang syntax is prolog inspired, not sure if that's a good thing though :)

nextos 10y ago
Not just inspired. It was initially implemented in Prolog!
macintux 10y ago
The prologesque syntax gets a lot of grief, but I genuinely appreciate it. I like my different paradigm languages to look different, helps me think differently. (but it's much closer to Algol than Lisp is, so I don't have to bend my brain quite that hard)
defined 10y ago
I like it. There are some annoyances to do with minor syntactical warts, like commas and semicolons, but all in all, I find it expressive.

rcgorton 10y ago

The power: require a rethink of approaches to programming The failure: the claim by such folk that all compute problems are best solved by prolog/clojure/related even when such a domain specific language is not pertinent.

taylorking 10y ago

love(prolog).

ragebol 10y ago
true
vram22 10y ago
love(prolog) :- love(logic_programming), love(elegance).

hexmiles 10y ago

i have always trouble understaing prolog, lot of guide online seem to just tackle the syntax or assume you already know a lot of logic programming, for example the first example in the link (https://www.metalevel.at/prolog/facets https://www.metalevel.at/prolog/facets): list_length([], 0). list_length([_|Ls], N) :- N #> 0, N #= N0 + 1, list_length(Ls, N0). i don't undestand it, i read the segment describing it multiple time but i still don't get it, and is not the syntax i don't undestand how it should work, a tried reading the next few chapter but i feel i'm missing something! is there a "prolog for dummies" out there?

sordina 10y ago
Check out https://en.wikipedia.org/wiki/Horn_clause https://en.wikipedia.org/wiki/Horn_clause You can read this as two statements: "The length of a list is 0, if the list is empty." "Otherwise, if the length of a list Ls is N0, and N is N0 + 1, and N is greater than 0, then Ls with an additional element is of length N.
- na85 10y ago
  Good lord, does that mean it's necessary to explicitly tell the compiler the length of an empty list? Shouldn't the list type already know its own size? I fail to see the benefit... honestly it just seems like a waste of time.
  - tathougies 10y ago
    No. This is the standard implementation of the length/2 predicate. Like any other language, prolog has a standard library that includes this predicate. You'd never need to write this in practice, but this is how it would be written in the standard library. In general, any general purpose language worth it's salt will have substantial portions of its standard library written in that language, and in this regard, prolog meets the criteria for respectsbl languages
    - Koshkin 10y ago

haddr 10y ago

There is a class of problems which you can solve using Prolog with pure pleasure. There is one thing however: Prolog can magically hide the complexity of many things, which is a two-sided sword. On many occasions you are hiding away the computational complexity and wonder why the execution is so slow. This rarely happens in imperative languages (where you are more aware of all the loops and recursions). I guess this is why many people hate Prolog...

Karrot_Kream 10y ago
> 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 execution model: a lot of beginners just don't understand how the depth first search unification algorithm really works. Playing around in the REPL should help build that Intuition fairly quickly though. I can post a concrete example if you want. Recently I changed an O(n^2) goal to an O(n) one and didn't have much trouble debugging it at all. I'm on mobile now but can post it later if you want.
- carapace 10y ago
  I'd like to hear that story, when you get the chance. ;-)
  - drunkpotato 10y ago
    Me too, please post!
  - Karrot_Kream 10y ago
    Sure and thanks for the wait! 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 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).

moderation 10y ago

See the Open Policy Agent [1] project that has a language and REPL called Rego inspired by Datalog. 1. http://www.openpolicyagent.org/documentation/how-do-i-write-policies/ http://www.openpolicyagent.org/documentation/how-do-i-write-...

zodiac 10y ago

I wrote some prolog for a PL class recently and had to debug some cases of nontermination caused by the depth-first-search unification algorithm. I was wondering why prolog (or some other logic programming language) couldn't use breadth-first search instead, to avoid those cases, but couldn't find answers online - could someone who knows prolog better here have an answer?

yeowMeng 10y ago
BFS space complexity is order exponential.
mballantyne 10y ago
Other search algorithms can take up lots of memory to store progress they've made down different paths. Having only one active state also lets you map unification down to efficient low level cpu operations. If you have multiple states, you either have to copy lots of data when you fork the state or you use a persistent data structure but can't use side effects, so everything is a bit slower. It's a tradeoff though. I work on miniKanren, which is a logic programming language with a complete search that doesn't hit the nontermination issues you mention. The complete search lets us do some pretty cool stuff with program synthesis (though we're not about to put any programmers out of business just yet): https://www.youtube.com/watch?v=er_lLvkklsk https://www.youtube.com/watch?v=er_lLvkklsk Note that you can implement iterative deepening depth first search on top of prolog if you want a complete search there. Iterative deepening takes a little more time but avoids the memory problems with breath-first. SWI has tools built in to help there: http://www.swi-prolog.org/pldoc/doc_for?object=call_with_depth_limit/3 http://www.swi-prolog.org/pldoc/doc_for?object=call_with_dep... And I believe Ciao implements its iterative deepening library with a meta-interpreter: https://ciao-lang.org/docs/ciao/id_doc.html#0 https://ciao-lang.org/docs/ciao/id_doc.html#0

hota_mazi 10y ago

Prolog's mathematical foundation is sound but the devil is in the details, and very soon, you encounter two of Prolog's most glaring flaws that lead to spaghetti code worse than what even BASIC ever produced: - It's dynamically typed - The cut operator

gmfawcett 10y ago
If you like Prolog, but want static typing and no cut operator, you might really like Mercury (https://mercurylang.org/ https://mercurylang.org/).

nwatson 10y ago

The Japanese government spent US $400 million in the '80's (a lot in those days) to try to jump ahead of "western" computer technology via its "5th Generation Project". https://news.ycombinator.com/item?id=14047780 https://news.ycombinator.com/item?id=14047780 The basis for it all ... Prolog.

rdtsc 10y ago
> Japanese Government said this week that it was willing to give away the software developed by the project to anyone who wanted it, even foreigners. Was wondering what they released as a result. Surely after a $400 in 80's money they had some lines of code written. Apparently they focused on concurrent logic programming and wasted a lot of money on exotic hardware in https://en.wikipedia.org/wiki/Fifth_generation_computer https://en.wikipedia.org/wiki/Fifth_generation_computer by the time they were done off-the-shelf CPUs could run circles around the fancy workstations.
dmh2000 10y ago
and it was an epic fail https://en.wikipedia.org/wiki/Fifth_generation_computer#Failure https://en.wikipedia.org/wiki/Fifth_generation_computer#Fail... A primary problem was the choice of concurrent logic programming as the bridge between the parallel computer architecture and the use of logic as a knowledge representation and problem solving language for AI applications.
- zmonx 10y ago
  Personal anecdote: I once asked a retired Japanese computer scientist why the 5th generation project had failed. He replied with: "What do you mean 'failed'? All my colleagues who worked on this project have become professors!" In this respect, the project was actually a smashing success.

lacampbell 10y ago

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.

ahelwer 10y ago
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.
- lacampbell 10y ago
  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.
  - tom_mellior 10y ago
    It is indeed backtracking as a language, but you don't get optimization entirely for free. The backtracking part only means that you can write down a problem that has multiple solutions and get Prolog to enumerate those solutions using its default order. 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.
    - bloaf 10y ago
      Would it work well for algorithms like A*, or other quazi-AI problems that crop up in games?

skdotdan 10y ago

Something I would like to be able to understand/know/study is how logic programming languages are implemented and how their runtime looks like.

c-cube 10y ago
you can start by looking for "warren abstract machine" (usually shortened as WAM). It's an intermediate format for compiling prolog programs (sets of Horn clauses, that is, rules). It makes every operation very explicit, including unification (to match the current goal against each rule's conclusion) and backtracking (to enumerate solutions; this involves stacks, unsurprisingly). I think most state of the art prolog implementations are then able to compile this format to native code. Of course prolog also requires that the runtime has a GC (to collect dead terms) and that it can dynamically add/remove rules, use reflection to observe the shape of a term, etc. https://en.wikipedia.org/wiki/XSB https://en.wikipedia.org/wiki/XSB is an implementation to which Warren contributes, with additional features such as tabling (a powerful form of memoization that avoids many infinite recursions).
hyperion2010 10y ago
http://www.amzi.com/articles/prolog_under_the_hood.htm http://www.amzi.com/articles/prolog_under_the_hood.htm I find this article very helpful when it comes to understanding how Prolog actually works.
- smarx007 10y ago
  http://archive.is/RSzu http://archive.is/RSzu
pg314 10y ago
Section 4.4 in Structure and Implementation of Computer Programs [1] presents an implementation of a Prolog-like logic programming language in Scheme. It is very instructive to contrast it to the meta-circular evaluator of Scheme in that same book to see the similarities and differences. Paradigms of Artificial Programming by Norvig also contains a chapter implementing Prolog in Common Lisp. The code can be found at [2]. [1] https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-29.html#%_sec_4.4 https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-29.htm... [2] http://norvig.com/paip/prolog.lisp http://norvig.com/paip/prolog.lisp

samwalrus 10y ago

I run a youtube channel called 'playing with prolog' https://www.youtube.com/channel/UCfWpIHmy5MEx2p9c_GJrE_g https://www.youtube.com/channel/UCfWpIHmy5MEx2p9c_GJrE_g We demo little things that you can do in prolog. Happy to take suggestions for videos :)

pjc50 10y ago

"No." (Disclaimer: this is a joke referencing prolog's default return when it can't find a solution.)

bschwindHN 10y ago

I once wanted to solve a problem that is perfect for Prolog, but I wanted it in Clojure. Turns out there's a great library for that! I don't think it has the full power of Prolog (I only know of Prolog and what it does but I've never used it), but for integer constraint programming it was a joy to work with. https://github.com/aengelberg/loco https://github.com/aengelberg/loco

deleted 10y ago

[deleted]

norswap 10y ago

If you want to exercise your Prolog-foo: https://github.com/norswap/prolog-dry https://github.com/norswap/prolog-dry

deleted 10y ago

[deleted]

mark_l_watson 10y ago

I bookmarked this. I have been revisiting my own programming history. I used Prolog a lot in the 1980s, partially because I was influenced by the ill-fated Japanese 5th generation project. A few weeks ago I pulled my old Prolog code experiments from an old repo. Prolog is a great language for some applications, and Swi-Prolog has some great libraries and sample programs. I also have used Common Lisp a lot since the 1980s and I am in the process of working through a few of the classic text books, and I have it on my schedule to update my own CL book with a second edition.

FabHK 10y ago
You had version control systems in the 80s? I had cassette tapes and later 5 1/4 inch floppy disks!
- mark_l_watson 10y ago
  I moved everything to svn, and later to git repos. I actually had 8" floppy disks on my Xerox Lisp Machine. An unnatural size for floppy disks!

SagelyGuru 10y ago

I used to teach Prolog in the GOFAI days of early 80's. It certainly was fun and probably the quickest way how to start solving interesting search based problems without having to write pages and pages of code. It was very good for motivation. Also for encouraging "top-down" design.

arikrak 10y ago

Question - is prolog used in the real world? I.e. are there businesses that use prolog in production?

zmonx 10y ago
Yes, there are several businesses that use Prolog in production. For example, please see the quotes from the SICStus page, a professional Prolog system (ISO standard compliant) with many commercial applications: https://www.sics.se/projects/sicstus-prolog-leading-prolog-technology https://www.sics.se/projects/sicstus-prolog-leading-prolog-t... Here is a salient quote from the article: "SICStus Prolog is a workhorse in the transport and logistics industries, running systems that handle a third of all airline tickets, and helping railways to operate their trains better." Further major commercial applications of SICStus Prolog are listed at: https://sicstus.sics.se/customers.html https://sicstus.sics.se/customers.html These include a voice-operated procedure browser for the International Space Station, and a dispensation order generation algorithm for biological research. In addition, Prolog is often used in logistics software and for scheduling, among several other tasks for which it is very well suited. A commercial Prolog's multi-user license easily costs thousands of dollars, so an industrial strength Prolog system is not the kind of software you typically "just buy" as an individual. Typical customers of commercial Prolog systems are other companies, and also universities who buy licenses for research purposes and to teach Prolog.

andai 10y ago

For an introduction to Prolog: Learn Prolog Now - Free Online Version http://www.learnprolognow.org/lpnpage.php?pageid=online http://www.learnprolognow.org/lpnpage.php?pageid=online I like this one because it's beginner-friendly (and uses characters from Pulp Fiction as examples). -- edit: actually, The Power of Prolog to is great, too! If anyone knows more good resources, I'd be happy to hear about them!

camelNotation 10y ago

One of my professors in college was an original creator of the Prolog language. He made us learn Prolog so that he could teach us something we could have just as easily done in C or Java. I strongly disliked him. For that reason, I am filled with negative vibes when I think about Prolog.

pjonesdotca 10y ago

A great intro to Prolog can be found here if you're not the type that learns solely from reading. https://www.youtube.com/watch?v=SykxWpFwMGs https://www.youtube.com/watch?v=SykxWpFwMGs

huherto 10y ago

I implemented the Wumpus World form Peter Norvig's AIMA using different techniques. I found that Bayesian Logic was much more powerful than Logic programming. Perhaps that explains why Prolog has flourished. Logic programming is limited to values of true or false. 0 or 1. Bayesian logic can deal with uncertainty values like .2 or .3. It almost seems like a superset. It is also more intuitive IMHO. I keep the wumpus implementation here if anyone is interested. https://github.com/huherto/aima3/tree/master/src/wumpus https://github.com/huherto/aima3/tree/master/src/wumpus