The Power of Prolog(metalevel.at)

348 pointsby nochvor 9 Jahren161 comments

https://www.metalevel.at/prolog

163 comments

jacquesmvor 9 Jahren

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_84...

bjackmanvor 9 Jahren

Also in applications with Prologue interpreters: you can express patch submitability predicates in Prolog for the Gerrit code review system.

Lets you automate arbitrary boring code submission prerequisite checks (e.g. "you must have a 'Verified' from a maintainer and a 'Code-Review +1' from 1 other person. If you are not the author and the author's email address doesn't end in @example.com you must have an 'IP-Reviewed' from a manager")

https://gerrit-review.googlesource.com/Documentation/prolog-...

Jtsummersvor 9 Jahren

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#.

andaivor 9 Jahren

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.

Jtsummersvor 9 Jahren

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_1vor 9 Jahren

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.

candiodarivor 9 Jahren

You're being asked to be a consultant, you know. They want to pretend that if you rewrite Prolog in C#, it'll be simpler, and that the average C# programmer (the cheapest one they can hire) will simply understand (badly written) logic programming solvers and be able to modify them.

Eventually you'll figure out to simply double your hourly rate and ask "do you want a bad Haskell implementation to go with that as well ? How about SQL ? Lisp ?"

Don't forget to terminate with "by the way here's my card" (asking them to mention their personal referral code "ID10T") when the inevitable happens, nobody understands that code at all when they have to modify it. And every time they ask you to update it you increase your hourly rate 20%.

You know, management realism. You can be victimized by it, or you can make a living out of it.

andaivor 9 Jahren

I don't know, sounds like it would be pretty confusing giving so many people the same referral code.

ruleabidinguservor 9 Jahren

Why couldn't you just tell them you were going to have to rewrite it if you couldnt get it embedded?

Jtsummersvor 9 Jahren

It wasn't already written in prolog. It just would've been much easier and more straightforward for that particular application to write the business logic side in prolog. From a UI standpoint, I've never used prolog for a GUI so it would've needed to be embedded in something else (likely C# given the office preference) anyways, so the decision was to put everything in C# and skip my prolog idea. If I still had those notes, I basically translated handwritten prolog-esque code into C# anyways.

EDIT: In very corporate offices like that one, you don't get to use <language of choice> unless it's staying strictly internal (this one had the potential to be released to customers), you have low oversight and can get away with it (not my case), you have a history of choosing wisely (I had little history with them at that point). They prefer to minimize the risk on the maintenance end (NB: doesn't mean they do what's needed to make maintainable code, they do what's needed to make it easy to hire maintainers by sticking to popular languages and frameworks instead).

cat199vor 9 Jahren

> they do what's needed to make it easy to hire maintainers by sticking to popular languages and frameworks instead)

And completely miss the moment where the new maintainer comes in and says:

"!@#$ why didn't they just write this in prolog? freaking PHB's"

fizixervor 9 Jahren

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

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.

Karrot_Kreamvor 9 Jahren

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.

abhghvor 9 Jahren

Prolog was part of course that I'd taken during my Masters. I loved it then. I would love to take a closer look when I have time ... whenever that happens <sigh> ...

Interestingly, IBM Watson uses Prolog. [1]

[1] https://www.cs.nmsu.edu/ALP/2011/03/natural-language-process...

bpynevor 9 Jahren

I used it for a graduate course in formal semantics. As our final project, we had to implement Lisp in Prolog and prove the semantics formally. Until that point, I thought I had a good grip on Prolog. Debugging the project nearly drove me nuts! If I had a do-over, I'd learn the SWI debugging tools before attempting it.

I love Prolog and hope to spend more time with it some day. But, the step from Novice to Intermediate is steep.

abhghvor 9 Jahren

That's helpful advice - thank you!

frikvor 9 Jahren

IBM uses a special version of Prolog with a different syntax and database access functionality. They hired a department of a university.

MS Windows (network code) contains a Prolog with C-style-syntax.

nnqvor 9 Jahren

Thanks. Do you know of any other resources describing Watson's inner workings? ...cause just googling for it leads to one of the zillions of marketing bullshit pages or whitepapers devoid of any real infos that IBM's marketing drones have flooded the web with.

frikvor 9 Jahren

Look for papers, search for Watson Prolog UIMA

wolfgkevor 9 Jahren

> MS Windows (network code) contains a Prolog with C-style-syntax.

Can you tell me details?

frikvor 9 Jahren

someone else wrote more details about it in this thread.

tannhaeuservor 9 Jahren

And Prolog is actually an ISO-standardized language so you have a choice of implementations to choose from (for example Yap Prolog, which I found much faster than SWI last I checked, or the highly regarded commercial Sicstus Prolog). Plus, implementing a Prolog engine isn't too much of an effort to do on your own (like I did two times). In fact, there are multiple Prolog implementations for the JVM, for JavaScript, etc.

random_gui2vor 9 Jahren

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_Kreamvor 9 Jahren

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.

YeGoblynQueennevor 9 Jahren

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

[2] https://en.wikipedia.org/wiki/Greibach_normal_form

tmalyvor 9 Jahren

I have used SWI Prolog in a professional setting to solve a very complex problem in a short deadline. It is definitely a tool to have in your toolbox.

eriknstrvor 9 Jahren

>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

eriknstrvor 9 Jahren

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/soluti...

philsnowvor 9 Jahren

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/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.

carapacevor 9 Jahren

I worked up this from the SEND MORE MONEY example in the CLP(FD) repo.

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]).

zmonxvor 9 Jahren

That's one of the most elegant Prolog formulations of this task I have seen so far. Great use of CLP(FD), especially considering that you have only started to learn this technology, as you mentioned in the other thread!

I have only two small suggestion: First, since you know that Vars = [GreenHouse, ...] (the Prolog program states this as a constraint), you can simply substitute Vars every time for this list. Therefore, you can start the whole program with: puzzle(Vars) :- ...

Second, exactly the same reasoning applies for the query you show. You can write it as: ?- puzzle(Vs), label(Vs).

Thank you very much for posting this beautiful solution, and also for carefully clarifying the additional assumptions!

carapacevor 9 Jahren

That's very kind of you. Your comment made my day! :-)

I came to Logic Programming via grokking mrocklin's port of Kanren to Python: https://github.com/logpy/logpy; and to solving logic puzzles via Laws of Form: http://www.markability.net/ (Last year the author of that site George Burnett-Stuart apparently cracked how to encode Predicate Calculus in the notation, which is an exciting development, IMHO!) So I'm not a complete novice. That said, at first I thought I should define relations like smokes and pet_of, but somehow between seeing the table on the Wikipedia entry for the Zebra Puzzle and the SEND MORE MONEY example (https://github.com/triska/clpfd/blob/master/sendmory.pl) it became obvious what to do. If you look at the SEND MORE MONEY solution you'll see the Zebra solution is laid out just like it. To me, it seems like the same sort of puzzle as Sudoku, but much simpler. It's unfortunate that the solution and the solving proper (querying for the result) obscure the art of the puzzle-maker, eh?

Thanks for the suggestion! I've incorporated it into the version in Github "gist": https://gist.github.com/calroc/603ed919bc814ccee10c1b3df6142... (I kept the more verbose query though, as I think the output is nicer. :-) YMMV)

zmonxvor 9 Jahren

Very, very nice formulation!

You can apply the same trick to the query, i.e., you only need to write down the whole list once, if you formulate the query for example like this:

    ?- Vs = [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],
       puzzle(Vs),
       label(Vs).

In the above, I have introduced the logical variable Vs to refer to the same list in both goals.

In the case of the Zebra puzzle, we only care about a few of these variables in particular, so we do not even introduce names for others. Instead, we can use anonymous variables, so that not even bindings are reported for those variables that do not matter in this case:

    ?- Vs = [_,_,_,_,_,
             Englishman, Spaniard, Ukrainian, Norwegian, Japanese,
             _,_,_,_,Zebra,
             _,_,_,_,Water|_],
       puzzle(Vs),
       label(Vs).

This yields the following solution:

    Vs = [5, 3, 4, 1, 2, 3, 4, 2, 1|...],
    Englishman = 3,
    Spaniard = 4,
    Ukrainian = 2,
    Norwegian = Water, Water = 1,
    Japanese = Zebra, Zebra = 5 .

By introducing additional variables like this, you can use maplist/2 to more compactly express the sequence of all_distinct/1 constraints.

That's really a very nice way to formulate the puzzle in Prolog, and makes excellent use of features that are still quite recent innovations in Prolog implementations.

carapacevor 9 Jahren

Cheers! That's awesome. I'm going to set aside some time to learn more Prolog. :-)

sriram_malharvor 9 Jahren

My z3 based solution in python looks like this: https://gist.github.com/sriram-srinivasan/2981825217f0802d9f...

pcmonkvor 9 Jahren

Another language reminiscent of Prolog is Clingo (web repl: 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".

gmfawcettvor 9 Jahren

Thanks, I hadn't heard of that one!

Another very interesting language in the Prolog family is Mercury (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.

YeGoblynQueennevor 9 Jahren

>> 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.

bpynevor 9 Jahren

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.

YeGoblynQueennevor 9 Jahren

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.

sligvor 9 Jahren

> 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/ [2] https://www.brainzilla.com/logic/zebra/einsteins-riddle/

mmarxvor 9 Jahren

> - 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.

JohnStrangevor 9 Jahren

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.

harperleevor 9 Jahren

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.

YeGoblynQueennevor 9 Jahren

>> 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/

[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.pd...

[3] That's the PRISM that stands for Programming In Statistical modelling, by Taisuke Sato:

http://rjida.meijo-u.ac.jp/prism/

fizixervor 9 Jahren

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.

YeGoblynQueennevor 9 Jahren

>> 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.

The way I know it, PGMs and HMMs are firmly within GOFAI- they're basically graphs with weights. Although I guess you can say the same thing about ANNs, the primary purpose of PGMs and HMMs is to represent structure (specifically, dependency relations). Which is a very GOFAI thing, to my mind.

It really depends on where you put the distinction between GOFAI and something else. My understanding is that the commonly accepted split is between AI with a (symbolic) representation and AI without, and the original proponent of the latter is Rodney Brooks who coined the term "Nouvelle AI" (sometimes "Nouveau") that is usually used as the modern counterpart to GOFAI.

Personally, I believe the distinction is a bit stale, especially if you think that ANNs are actually older than expert systems and that even if you look just a couple of years in the past you'll see that one of the most popular (family of) machine learning algorithms was Decision Tree learners, which are basically a perfect mix of the old algorithms and the new: a propositional logic rule-base built from examples using information-theoretic measures.

As to the revolution brought by Hinton, this is a bit political but I think that's just a good story, with little grounding in reality. Here's an example:

https://webcache.googleusercontent.com/search?q=cache:2JwVBr...

That's a (cached) page from an online machine learning data repository, with data sets taken from various papers etc. The page is about a familial relationship data set from two papers, one by Hinton and one by Quinlan (the Decision Tree guy). Hinton's paper is from 1986, Quinlan's from 1989. Hinton's paper has 43 citations, all but one of which is from 2002 or earlier and going back to the '90s (Quinlan's only has one, from 1990).

Which tells me that Hinton's "breakthrough result" did not revive interest in ANNs, neither was he the tenacious, lone underdog, that he likes to present thimself as: interest in ANNs and specifically Hinton's work has always been very popular, as has been the work of others (er, Schmidhuber).

My understanding is that machine learning goes way back, and basically starts with GOFAI: the first thing people noticed about expert systems was the difficulty of hand-crafting non-trivial rule-bases, so they looked for ways to automate that (see, e.g. Michalski's work that goes back to the '60s) and eventually realised that you didn't actually need the expert system if you could just automate the rule extraction.

But that's also probably just a cute but inaccurate narrative- there was a great deal of work in machine learning and a great deal of interest in it, that was not labelled as such, for instance, in "inductive inference" and so on.

tl;dr: when we talk of machine learning and AI these days we're hardly even scratching the surface. There's a lot of past work that most university courses simply don't have the time to teach and we newer students are missing lots of useful bits of it... and are probably condemned to reinvent.

gugagorevor 9 Jahren

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

tunesmithvor 9 Jahren

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.

agumonkeyvor 9 Jahren

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.

wuschelvor 9 Jahren

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

mmarxvor 9 Jahren

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.

estvor 9 Jahren

what about this?

https://github.com/Z3Prover/z3

Is it comparable with prolog or just a subset of prolog?

mballantynevor 9 Jahren

My understanding is that Z3 is primarily an SMT solver (https://en.wikipedia.org/wiki/Satisfiability_modulo_theories), though it has also expanded to support queries beyond SMT.

SMT solvers excel at solving finite sets of equations involving finite or atomic data, like numbers, bitvectors, strings, and arrays of fixed length. They've been very successfully applied in software and hardware verification. They're also the essential tool for a big category of approaches to program synthesis.

This has some overlap with the sorts of numeric constraint solving available in prolog and with non-recursive prolog goals. Prolog however can express turing-complete computation with recursive goals, dynamically allocate data structures of unknown size, etc. that SMT cannot easily encode.

Z3 also has support for datalog-like queries. I don't know much about datalog, but my understanding is that it supports a more limited set of queries than prolog but can solve them more efficiently with a totally different algorithm than prolog's goal-directed depth first search.

dreamcompilervor 9 Jahren

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.

fizixervor 9 Jahren

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

[2] 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

[4] http://cs.stackexchange.com/questions/14946

ScottBursonvor 9 Jahren

> Coq, Isabelle are interactive theorem provers or proof assistants, not automatic theorem provers which is a lot harder to do

Automatic theorem provers for first-order logic (FOL) have existed for some time [0], but higher-order logic (HOL) is another matter. The difference is that in HOL, predicates can be variables; in FOL they are all constants. HOL allows you to write rules for mathematical induction; for example:

  ∀P P(0) ∧ (∀n n ≥ 0 ∧ P(n) ⇒ P(n + 1)) ⇒ (∀n n ≥ 0 ⇒ P(n))

This says that for any predicate P on the natural numbers, if you can show, first, that P(0), and second, that for any natural n, P(n) implies P(n + 1), then you can conclude that P is true for any n. This rule is not a valid FOL statement, because it starts off quantifying over possible predicates, which is not permitted in FOL.

Reasoning of this kind, although usually informal, is necessary for programmers to understand any iterative or recursive piece of code. To understand such code, you have to know what invariant it maintains; proofs of such invariants are always inductive. So HOL is required, in most cases, for formal verification of software.

But no one has figured out how to build an automated prover for HOL. My own theory as to why is simply that the branching factor is higher. It's like the difference between chess and Go: the branching factor -- the average number of possible moves from any board position -- is small enough in chess that brute-force search can be sufficient to play at a world level, at least in the mid- and end-game; but in Go, it's much larger, so that brute-force search doesn't get you very far.

As you say, lacking a fully automated HOL prover, people have been using proof assistants instead. These keep track of the details of the proof, which is still a very useful function, and can perform certain simple deductive steps themselves, but require manual intervention at certain critical points, such as the introduction of induction hypotheses.

[0] https://en.wikipedia.org/wiki/Automated_theorem_proving

c-cubevor 9 Jahren

There are some automated theorem provers for higher-order logic [0][1], but they are not very good yet compared to their first-order counterpart. There are also some provers specialized in inductive proofs [2][3], although the frontier with proof assistants such as Coq or Isabelle starts getting blurry as you often need the user's intervention to explicitely provide lemmas.

I have some hopes that this is going to change in the next few years thanks to a colleague's effort [4] to build better higher-order provers. He's an expert in Sledgehammer (a tool to use automated provers from Isabelle) which is already a productivity boost, and should become better with this project.

You are right that the search space is more difficult to handle. Induction (and similar formulas) is particularly hard to handle because one usually has to introduce lemmas, and these lemmas have to be "guessed" (infinite branching factor there). Existing provers basically rely on heuristics to try and find lemmas that would be useful for solving the current goal(s). ACL2 [3] for instance uses heuristics accumulated and refined for decades.

Hopefully, proof assistants will get tighter and tighter integration with automated provers, and the user will have to specify only the main lemmas and the overall shape of a proof, leaving the details to CPU crunching.

[0] https://page.mi.fu-berlin.de/cbenzmueller/leo/ [1] https://www.ps.uni-saarland.de/~cebrown/satallax/ [2] https://github.com/sorinica/spike-prover [3] https://www.cs.utexas.edu/users/moore/acl2/ [4] http://matryoshka.gforge.inria.fr/

ScottBursonvor 9 Jahren

Thanks for the info!

saosebastiaovor 9 Jahren

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

gtycombvor 9 Jahren

Can SQL do resolution or backtracking similar to Prolog, I wonder.

benjiwebervor 9 Jahren

SQL gives you all the solutions to query by default unless you limit them right?

A relation (table) in SQL is conceptually a predicate that holds for all tuples (rows) therein. You can AND the predicates with "NATURAL JOIN". You can OR them with "UNION"

e.g. this example https://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpa...

becomes something like this in SQL.

  example=# select * from red;
    item   
  ---------
   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_melliorvor 9 Jahren

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".

benjiwebervor 9 Jahren

SQL can do recursive rules too. SQL tutorials often do SQL a disservice by introducing it as a database query language rather than relational algebra :)

  example=# select * from move;
    place  | method | newplace 
  ---------+--------+----------
   home    | taxi   | halifax
   halifax | train  | gatwick
   gatwick | plane  | rome
  (3 rows)
  
  example=# create view on_route as with recursive on_route(place, newplace, length, path) as (select place, newplace, 1 as length, place as path FROM move UNION select on_route.place, move.newplace, on_route.length + 1, path || '->' || move.place as path FROM move JOIN on_route ON on_route.newplace = move.place) SELECT place, newplace, length, path || '->' || newplace as path FROM on_route;
  CREATE VIEW
  example=# select distinct true from on_route WHERE place = 'home' and newplace = 'rome';
   bool 
  ------
   t
  (1 row)
  
  example=# select path from on_route WHERE place = 'home' and newplace = 'rome';
               path             
  ------------------------------
   home->halifax->gatwick->rome

tom_melliorvor 9 Jahren

Ha, excellent :-) I learned something, thanks.

(The greater point still stands, terms and unification and all that.)

samwalrusvor 9 Jahren

I run a youtube channel called 'playing with prolog' https://www.youtube.com/channel/UCfWpIHmy5MEx2p9c_GJrE_g

We demo little things that you can do in prolog.

Happy to take suggestions for videos :)

hexmilesvor 9 Jahren

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):

        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?

carapacevor 9 Jahren

Well do you know what a predicate is, in logic? https://en.wikipedia.org/wiki/Predicate_%28mathematical_logi...

What this prolog code is doing is defining a predicate called “list_length“, which captures the relation between a list and the integer that represents the length of the list.

To do that you start with a base case, the relation between an empty list and the integer that represents the length of the list. That's the first prolog statement:

    list_length([], 0).

It has no Body so this Head clause is always true: we are defining the list_length predicate for [] and 0. (Another way of saying that is that the pair ([], 0) is in some set called list_length.)

The second statement has three Body clauses that specify three conditions:

1. You have an integer (technically a Natural number, not negative) named 'N' that is greater than zero. We do not care which integer it actually is at this point, just that it's greater than zero.

2. That integer 'N' is the sum of some other integer named 'N0' and one. We also do not care what 'N0' actually is, just that it is one less than 'N'.

3. There is some list named 'Ls', and the pair (Ls, N0) is in the set named 'list_length'. We also do not care what this list actually contains, just that it exists and that list_length(Ls, N0) is True.

Given the above three conditions are satified, Prolog can conclude:

4. The pair ([_|Ls], N) is in the set named 'list_length'.

You have to understand that the '_' mean anything, and '[foo|bar]' is how you add foo to the list bar to make a new longer list. (Like [1|[2|[3|[]]]] is the list 3 2 1.) See https://en.wikipedia.org/wiki/Cons#Lists

That code is enough information for the underlying Horn Clause Resolution to be able to do things like find the length of a list, or find lists of a given length. It's very powerful. https://en.wikipedia.org/wiki/Horn_clause

dreamcompilervor 9 Jahren

Couple of weird things about Prolog: It's a pattern-matcher, in much the same way Haskell is -- but Prolog invented it first. Thus the first rule tries to match the args you give it, and if you give it the literals [] and 0, it just says "True" or "Yes" (depending on which Prolog you're using). If you give it something it cannot match to [] and 0, it will try the second clause and assume the first arg is a list with a head and a tail, and the second arg is an integer.

The other weird thing is that Prolog functions can often run backwards. If you ask Prolog

?- list_length(Foo, 4)

it will hand you back a list of 4 elements that it just made up on the spot. This is why Prolog rules are considered generalizations of functions: They don't have explicit inputs vs. outputs. They're relations, not functions.

This stuff blew my mind when I first encountered Prolog and it changed forever how I thought about programming.

doublecvor 9 Jahren

The reversibility of Prolog computations was a big eye opener for me too back when I first encountered it. I recently wrote a post about relational programming using Prolog and Mozart/Oz as examples https://bluishcoder.co.nz/2017/03/20/relational-programming-...

Another interesting language in the same domain is Picat http://picat-lang.org/

sordinavor 9 Jahren

Check out 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.

StreamBrightvor 9 Jahren

Excellent. How am I supposed to interpret this, or being able to write code? Even Erlang is much more readable and understandable at the first sight. :)

naaskingvor 9 Jahren

That's because Erlang is still a traditional imperative programming language, so it just slightly tweaks what you're already used to. Logic programming is completely different.

na85vor 9 Jahren

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.

outworldervor 9 Jahren

It is not a waste of time. Stop trying to match it to programming languages you already know and try to think in the abstract.

This example is about a list. But you could be very well telling the system about relationships between car parts instead. Or git commits.

Gerrit provides an actual real world use case: https://gerrit-review.googlesource.com/Documentation/prolog-...

tathougiesvor 9 Jahren

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

Koshkinvor 9 Jahren

I guess, the point was, if list is a built-in construct, the function length should be also built in. (Unless, that is, natural numbers are defined in the standard library.)

YeGoblynQueennevor 9 Jahren

Prolog lists are predicates, like pretty much everything else in the language. Lists have the functor '.' (the dot) and two arguments, a term and a list, so they're defined recursively.

Frex, this is a list:

  .(a, .(b, .(c, .(d, []))))

'[]' is an atom that stands for the empty list.

Normally however we write lists like this:

  [a,b,c,d]

Which is syntactic sugar used in the vast majority of Prolog code.

The easiest way to think of it is that a list is a pattern, consisting of two square brackets enclosing any number of terms. You can't really call functions on it, but you can pass it as an argument to other predicates, and match it to other patterns.

tom_melliorvor 9 Jahren

> I guess, the point was, if list is a built-in construct, the function length should be also built in.

It is built in. No need to write your own length predicate. The quoted example is an illustration of a possible implementation.

(Cue boring discussion of "built in" vs. "defined in the standard library".)

vidarhvor 9 Jahren

That something is "built in" doesn't mean it won't be defined somewhere, such as in the standard library.

nwatsonvor 9 Jahren

In Prolog you can "run your logic backwards".

In Java you can declare a list "my_list" and then ask for its length as in "my_list.size()". You can do the same in Prolog. Given the above Prolog definitions, here's an example of computing a list's length:

    | ?- list_length([13, 42], ListLength).

    ListLength = 2

    yes
    | ?-

NOT VERY EXCITING.

But wait, you can run your logic BACKWARD. You can say instead, I have a list of length 2 -- what's inside the list??????

    | ?- list_length(MyList, 2).

    MyList = [_,_] ? 

    yes
    | ?-

So that's strange. Prolog just gave us the form of an entity whose list-length is 2. And because we didn't say ANYTHING MORE SPECIFIC about the elements of the list, Prolog just gave us two placeholders for the items in the list ... '_' and '_'. Java can't do that out-of-the-box -- you can't say a list is size 2 and then ask for all the possible lists back.

In our backwards-running Prolog example, we might have attached other conditions to the elements of the list ... in which case Prolog would (possibly) not have returned placeholders for the elements of the list, but might have done further work to figure out proper values to put into the list to satisfy the further conditions we gave for them.

kevhitovor 9 Jahren

It's no different than:

  public class LinkedList {
     ...
     public int size() {
        if (head == null) {
           return 0;
        } else {
           int n0 = 1 + head.size();
        }
    }

Actually, it is different. In prolog, you don't tell it how to compute an answer. You tell it what the answer is, and it figures out the rest.

In the previous example, I'd phrase it more like this:

I am sure [] has 0 length. I would be sure [_:Ls] has N length, if I was sure N>0 and N=N0+1 and [Ls] has N0 length.

Notice I never really told prolog how it is supposed to go about figuring out that [Ls] has N0 length -- prolog might use recursion. Or there might be other facts which let it figure out the length of [Ls]. Prolog will try to find a way. For example, I might introduce a rule

list_length(join(a, b), N) :- N #= NA + NB, list_length(a, NA), list_length(b, NB)

Now prolog knows that when you join two lists of known length, the lengths can be summed, without actually counting the length of either list or the combined list. And actually prolog doesn't even know or care what "join" means here, it just knows that "join" will cause the lengths to get summed.

na85vor 9 Jahren

Why on earth doesn't LinkedList already have a size() method? I'm thinking of typed languages, I guess, but surely any sane collection type knows how to perform addition/concatenation with other instances of its own type, right?

doublecvor 9 Jahren

There is a built in function for it in Prolog. But when it's presented as an example of how to implement it in the same way that list classes are often used as examples in OO languages even if they language implementation includes one.

saghmvor 9 Jahren

This is describing how you would implement LinkedList. Obviously, the size method has to be defined somewhere, and this is showing a potential implementation of it

YeGoblynQueennevor 9 Jahren

Prolog is a logic programming language. It's not object-oriented, so it doesn't have objects or methods.

If you want to know the length of a list you can use the predicate length/2:

  ?- length([a,b,c,d], N).
  N = 4.

The example above just shows you how length/2 works (albeit with some CLP operators that are not typical).

Edit: also, lists are not a "collection type" or any type at all. They're predicates, like everything else in the language. See my comment below - the easiest way to think of them is as patterns (just like in regexes, only Turing complete).

vidarhvor 9 Jahren

Those collections have to be implemented by someone. You seem to be assuming that these collections spring fully formed into the world and are black boxes without an implementation.

na85vor 9 Jahren

I think you are willingly missing my point, because I believe it is obvious that I am not making that assumption.

vidarhvor 9 Jahren

Looking at the other responses to your comment, clearly it is not obvious that you're not making that assumption.

If that's not what you were trying to say, then I still don't understand what you were trying to say.

tomdrevor 9 Jahren

The fact list_length([], 0) says "the length of an empty list [] is 0". The clause says "the length of the list [_|Ls] (i.e, any element concat Ls) has length N if N>0, N=N0+1, and the length of Ls is N0". Hope this helps.

FabHKvor 9 Jahren

Why do you have to specify that N>0?

Seems to me that this ought to be sufficient:

the list [_|Ls] has length N if N=N0+1, and the length of Ls is N0

tom_melliorvor 9 Jahren

In this particular example, specifying that N > 0 helps with running the predicate "backwards": You can use the query "length(L, 3)" to enumerate "all" lists of length 3, for example:

    ?- length(L, 3).
    L = [_G926, _G929, _G932].

This is not particularly informative for beginners, but it's a list containing exactly three distinct logic variables. Any three-element list is an instance of this.

When running in this mode, the N #> 0 constraint ensures termination; otherwise, the recursive clause would find the three-element list, but then continue a futile infinite search for further lists (of negative length, which cannot exist). It takes a bit of getting used to Prolog's execution model to really understand why this is the case.

FabHKvor 9 Jahren

Thanks for the informative reply.

A related observation, by the way, regarding programming languages: often it all sort of makes sense, and you can put stuff together that gets you the correct result without really knowing what's actually going on behind the scenes.

However, when you need stuff to go fast, then you really need to know the underlying runtime, execution model, memory model, etc. to find the incantation that's not only right, but efficient.

StreamBrightvor 9 Jahren

Same here, I don't think this is a particularly great way of starting with Prolog. I have found these videos helpful for understanding Prolog:

https://www.youtube.com/watch?v=SykxWpFwMGs

https://www.youtube.com/watch?v=G_eYTctGZw8

vram22vor 9 Jahren

I see there are multiple good answers already, but I'll just add my 2c - which answers from a different angle, sort of (though partially similar to some of the other answers). It may help, if you understand recursive calls to functions, and an imperative language like Python - the examples are in Python:

Recursive computation of simple functions:

https://jugad2.blogspot.in/2016/03/recursive-computation-of-...

The first example shown is for computing the length of a list, recursively.

Edit: To make it clear, my example uses an imperative approach, while your Prolog example uses a declarative approach. As the excellent comments by carapace and kevhito show, the two approaches are different. Just that my example may help you to get the solution used. But in Python, we tell the interpreter how to compute the length of a list. In Prolog, it is sort of as though we tell the interpreter what we want it to find out (a goal), and give it some facts / properties and rules to help it do that. It then does that, using its inference engine.

HTH.

haddrvor 9 Jahren

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_Kreamvor 9 Jahren

> 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.

carapacevor 9 Jahren

I'd like to hear that story, when you get the chance. ;-)

Karrot_Kreamvor 9 Jahren

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). 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).

gugagorevor 9 Jahren

Just to clarify, it was O(n^2) for n the length of the string, not the number of statuses. Right?

Karrot_Kreamvor 9 Jahren

Correct.

carapacevor 9 Jahren

Cheers. :-)

drunkpotatovor 9 Jahren

Me too, please post!

haddrvor 9 Jahren

Thanks! it's good to know that it is easier now to diagnose those complexity issues. Anyway if you can post an example, that could be really cool!

tom_melliorvor 9 Jahren

Ah, blaming the language. See https://accidentallyquadratic.tumblr.com/ for other languages and systems (including HN's current favorite, Rust), which apparently also "[hide] away the computational complexity and [make you] wonder why the execution is so slow".

Not saying Prolog performance can't be tricky, but it's not that easy in other languages.

andaivor 9 Jahren

For an introduction to Prolog:

Learn Prolog Now - Free Online Version 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!

timonokovor 9 Jahren

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.

tom_melliorvor 9 Jahren

> fib(X,Y1+Y2):- fib(X-1,Y1),fib(X-2,Y2).

As others have noted, it's possible to write nicely behaved Prolog versions of this that you can use in various ways: call "fib(3, N)" to find the third Fibonacci number, "fib(3, 6)" to see if the third Fibonacci number is 6, or "fib(I, 6)" to find if 6 is the I-th Fibonacci number for some I.

But these solutions use slightly more verbose syntax that makes the evaluation of arithmetic expressions explicit. As for the question why this is the case and why Prolog doesn't support this natively, it's because the Prolog system would have to know (a) which terms represent arithmetic expressions and (b) at what time all the variables in those terms will be instantiated.

For (a) you need a static type system, which is a well-known concept, and for (b) something called a "mode system", which is something more or less specific to logic and constraint languages. The mode system tells you when certain variables will be bound to values. Consider the example "fib(3, N)", where X is bound, which allows you to compute "X-1" and "X-2", from which you can compute Y1 and Y2, and from these finally "Y1+Y2", i.e., N. For the call "fib(I, 6)" the whole computation is in reverse: From "6 = Y1+Y2" you would need to derive values for Y1 and Y2 (this already involves a search), from which you can derive values that allow you to find values that should be equal, respectively, to "X-1" and "X-2", and from that you might deduce a value for X. This is a completely different computation. It's doable, but you would need to know data types (which in general you don't, in Prolog), predicate modes (which again you don't), and you would need to use separate computations for each mode.

There is a functional/logic language called Mercury, which is a superset of a restricted subset of Prolog, which has static types and modes (using user annotations) and compiles separate versions of each predicate for each mode, and in which something more like what you want is already possible. (If I understand correctly, even in Mercury this example wouldn't work, because it only allows you to unify 6 with "Y1+Y2" if at least one of those variables is known.)

colandermanvor 9 Jahren

You can do this in SWI Prolog using the between/3 predicate for the inequality, and the is/2 predicate for the arithmetic.

colandermanvor 9 Jahren

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).

thisrodvor 9 Jahren

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?

colandermanvor 9 Jahren

SWI-Prolog has CLP extensions to do exactly that: http://www.swi-prolog.org/pldoc/man?section=clp

    ?- use_module(library(clpq)).
    midpoint(X, Y, Z) :- {Z =:= (X+Y)/2}.
    two(X) :- midpoint(0, X, 1).

does what you want.

thisrodvor 9 Jahren

Thank you. It's a relief to know that I don't need to invent it.

wozervor 9 Jahren

Constraint Programming with finite domains can probably do this.

For example http://mozart.github.io/

skdotdanvor 9 Jahren

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

pg314vor 9 Jahren

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.htm...

[2] http://norvig.com/paip/prolog.lisp

exDM69vor 9 Jahren

Here [0] is a video link to SICP lecture 8A about Logic Programming, which accompanies the section 4.4. It's an excellent lecture!

[0] https://ocw.mit.edu/courses/electrical-engineering-and-compu...

c-cubevor 9 Jahren

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 is an implementation to which Warren contributes, with additional features such as tabling (a powerful form of memoization that avoids many infinite recursions).

hyperion2010vor 9 Jahren

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.

smarx007vor 9 Jahren

http://archive.is/RSzu

abhiragvor 9 Jahren

You should have a look at https://mitpress.mit.edu/books/reasoned-schemer

moderationvor 9 Jahren

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-...

huhertovor 9 Jahren

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

lacampbellvor 9 Jahren

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.

tom_melliorvor 9 Jahren

I've used it with enjoyment and success in several programming language projects (compilation, program analysis). It's well suited for these things for the same reason that languages like OCaml and Haskell are well suited and commonly used for them: algebraic data types and pattern matching (called terms and unification in Prolog, and a bit more powerful than simple pattern matching). You can more easily and directly access your data than is usual in imperative or object-oriented languages.

I do note that this is a domain where you have less need to "get" the backtracking search part of Prolog, it's more like functional programming. The point being that you can do useful programming, even imperative, in Prolog, not only logical "automatically exploring a large search space" stuff.

It's a general-purpose programming language plus a search system that you can choose to use or ignore as it fits your problem. But yeah, it's not usually presented as such.

ahelwervor 9 Jahren

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.

lacampbellvor 9 Jahren

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_melliorvor 9 Jahren

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.

bloafvor 9 Jahren

Would it work well for algorithms like A*, or other quazi-AI problems that crop up in games?

tom_melliorvor 9 Jahren

Yes, but you shouldn't expect it to have much more magic support for this kind of algorithms than other languages.

insulanianvor 9 Jahren

Is it possible to do that kind of stuff (e.g. Einstein's Puzzle) in Haskell/OCaml/F# and how would one approach it?

tom_melliorvor 9 Jahren

Yes, it's possible. Most approaches use brute-force search, just like the simpler Prolog variants: http://rosettacode.org/wiki/Zebra_puzzle

kdtgvor 9 Jahren

Intractable problems i.e., the ones that can't be solve in polynomial time. Logic programming in general is NP-Hard, so it's suitable for NP-Hard problems (constraint satisfaction problems, backtracking, etc). If you try to solve polynomial problems, it doesn't perform well.

SagelyGuruvor 9 Jahren

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.

camelNotationvor 9 Jahren

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.

pjonesdotcavor 9 Jahren

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

mark_l_watsonvor 9 Jahren

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.

FabHKvor 9 Jahren

You had version control systems in the 80s? I had cassette tapes and later 5 1/4 inch floppy disks!

mark_l_watsonvor 9 Jahren

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!

norswapvor 9 Jahren

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

[deleted]vor 9 Jahren

bschwindHNvor 9 Jahren

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

zodiacvor 9 Jahren

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?

mballantynevor 9 Jahren

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

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_dep... And I believe Ciao implements its iterative deepening library with a meta-interpreter: https://ciao-lang.org/docs/ciao/id_doc.html#0

yeowMengvor 9 Jahren

BFS space complexity is order exponential.

nwatsonvor 9 Jahren

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

The basis for it all ... Prolog.

rdtscvor 9 Jahren

> 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 by the time they were done off-the-shelf CPUs could run circles around the fancy workstations.

dmh2000vor 9 Jahren

and it was an epic fail 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.

zmonxvor 9 Jahren

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.

pjc50vor 9 Jahren

"No."

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

arikrakvor 9 Jahren

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

zmonxvor 9 Jahren

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-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

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.

rcgortonvor 9 Jahren

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.

signa11vor 9 Jahren

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

macintuxvor 9 Jahren

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)

nextosvor 9 Jahren

Not just inspired. It was initially implemented in Prolog!

definedvor 9 Jahren

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.

[deleted]vor 9 Jahren

taylorkingvor 9 Jahren

love(prolog).

vram22vor 9 Jahren

love(prolog) :-

        love(logic_programming),
        love(elegance).

ragebolvor 9 Jahren

true

hota_mazivor 9 Jahren

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

gmfawcettvor 9 Jahren

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