The Power of Prolog

https://www.metalevel.at/prolog

by noch • 9 years ago

348 161 9 years ago

fizixer3• 9 years 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

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.

eriknstr2• 9 years 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

eriknstr2• 9 years 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/soluti...

sriram_malhar• 9 years ago

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

tunesmith• 9 years 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_Kream5• 9 years 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• 9 years 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?

tannhaeuser• 9 years ago

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.

abhgh2• 9 years ago

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

tmaly• 9 years ago

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.

gugagore2• 9 years ago

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

est• 9 years ago

what about this?

https://github.com/Z3Prover/z3

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

fizixer3• 9 years 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

[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

dreamcompiler2• 9 years 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.

mballantyne2• 9 years ago

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.

pcmonk• 9 years ago

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

gmfawcett2• 9 years ago

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.

saosebastiao• 9 years ago

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

gtycomb• 9 years ago

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

JohnStrange• 9 years 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• 9 years 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.

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

wuschel• 9 years ago

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

mmarx2• 9 years 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• 9 years 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.

YeGoblynQueenne7• 9 years 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.

bpyne2• 9 years 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.

YeGoblynQueenne7• 9 years 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/

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

fizixer3• 9 years 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• 9 years 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_84...

Jtsummers3• 9 years 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#.

andai3• 9 years 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.

ruleabidinguser• 9 years ago

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

bjackman• 9 years ago

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

timonoko• 9 years 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.

colanderman3• 9 years ago

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

colanderman3• 9 years 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).

thisrod2• 9 years 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?

wozer• 9 years ago

Constraint Programming with finite domains can probably do this.

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

tom_mellior10• 9 years ago

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

signa11• 9 years ago

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

nextos• 9 years ago

Not just inspired. It was initially implemented in Prolog!

macintux• 9 years 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• 9 years 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• 9 years 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• 9 years ago

love(prolog).

ragebol• 9 years ago

true

vram222• 9 years ago

love(prolog) :-

        love(logic_programming),
        love(elegance).

hexmiles• 9 years 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):

        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• 9 years ago

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.

na853• 9 years 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.

StreamBright2• 9 years ago

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

tomdre• 9 years ago

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.

FabHK3• 9 years ago

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

carapace6• 9 years ago

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

dreamcompiler2• 9 years ago

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.

doublec2• 9 years ago

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/

StreamBright2• 9 years ago

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

vram222• 9 years ago

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.

haddr2• 9 years 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_Kream5• 9 years 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.

carapace6• 9 years ago

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

haddr2• 9 years ago

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_mellior10• 9 years ago

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.

moderation• 9 years 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-...

zodiac• 9 years 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• 9 years ago

BFS space complexity is order exponential.

mballantyne2• 9 years 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

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

hota_mazi• 9 years 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

gmfawcett2• 9 years ago

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

nwatson2• 9 years 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

The basis for it all ... Prolog.

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

dmh2000• 9 years ago

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.

zmonx4• 9 years 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.

lacampbell2• 9 years 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• 9 years 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.

lacampbell2• 9 years 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.

insulanian• 9 years ago

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_mellior10• 9 years ago

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.

kdtg• 9 years ago

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.

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

hyperion2010• 9 years ago

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• 9 years ago

http://archive.is/RSzu

pg314• 9 years 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.htm...

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

exDM69• 9 years ago

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

abhirag• 9 years ago

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

samwalrus• 9 years ago

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

pjc50• 9 years ago

"No."

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

bschwindHN• 9 years 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

norswap• 9 years ago

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

mark_l_watson2• 9 years 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.

FabHK3• 9 years ago

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

mark_l_watson2• 9 years 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• 9 years 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• 9 years ago

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

zmonx4• 9 years 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-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.

andai3• 9 years ago

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!

camelNotation• 9 years 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• 9 years 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

huherto• 9 years 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

The Power of Prolog

Related Stories