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.
Interestingly, IBM Watson uses Prolog. [1]
[1] https://www.cs.nmsu.edu/ALP/2011/03/natural-language-process...
I love Prolog and hope to spend more time with it some day. But, the step from Novice to Intermediate is steep.
MS Windows (network code) contains a Prolog with C-style-syntax.
Can you tell me details?
What's your solution?
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ₘ.
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.
P --> [a], A₁, A₂, .... Aₙ.
___________
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://github.com/eriknstr/puzzles/blob/master/zebra/soluti...
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.
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.
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).
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]).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!
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)
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 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).
Vs = [5, 3, 4, 1, 2, 3, 4, 2, 1|...],
Englishman = 3,
Spaniard = 4,
Ukrainian = 2,
Norwegian = Water, Water = 1,
Japanese = Zebra, Zebra = 5 .
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.
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".
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.
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.
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.
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/
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.
Honest question, I'm trying to learn new things, not trying to sound as an expert!! As I said, limited experience.
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:
> ... 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.
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.
https://github.com/Z3Prover/z3
Is it comparable with prolog or just a subset of prolog?
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.
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]
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))
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.
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/
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)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".
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(The greater point still stands, terms and unification and all that.)
- 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.