Artificial Intelligence: Logic Programming II
Oliver Ray
Datalog
From Datalog to Prolog
Datalog
Last week, you began your exploration of Prolog from a very simple database perspective (known as Datalog) in which
• Prolog facts → relational database
• one predicate per table; one fact per row
• Prolog rules → relational views
• intentional definition; materialised when needed
• Prolog queries → relational algebra (RA) • but Prolog is much easier than RA! (or SQL)
movie(american_beauty,1999).
released_after(M,Y) :- movie(M,Z), Z>Y.
?- actor(_, A, _), director(_, A).
Translation to RA (Hints)
Title
MOVIE
Year
Title
DIRECTOR
Director
american_beauty
anna
…
1999
1987
…
american_beauty
anna
…
sam_mendes
yurek_bogayevicz
…
ACTOR
Title
Name
Role
american_beauty
kevin_spacey
lester_burnham
…
…
…
ACTRESS
Title
Name
Role
american_beauty
annette_bening
carolyn_burnham
…
…
…
project union join select
?- ( actor(_, A, _) ; actress(_, A, _) ) , director(_, A) .
Prolog
• This week, you’ll look at a more expressive subset of Prolog that includes recursive definitions and structured terms
• which together mean Prolog is Turing complete (unlike RA/SQL) • and which allow the list data type to play as crucial a role in logic
programming as it does in functional programming (e.g. Haskell)
• We’ll also see that, while Prolog syntax can be mapped very neatly to (a subset of) First Order Logic (FOL), its semantics is non-classical in a way that makes it more suited to AI tasks
Translation to FOL (Hints)
The connectives “:-”, “,”, “;” and “\+” map to “”, “”, “” and “¬” (over implicit universally quantified variables):
plays(M,A,R) :- actor(M,A,R) ; actress(M,A,R).
solo(M,A) :- plays(M,A,_), \+ (plays(M,B,_), A\=B).
M .A .R . ( plays(M,A,R) ( actor(M,A,R) actress(M,A,R) ) )
M.A .B.X .Y.(solo(M,A) (plays(M,A,X) (plays(M,B,Y) AB)))
. . ( solo(M,A) . . . (plays(M,A,X) ( plays(M,B,Y) A B ) ) ) MA BXY
But, be careful, as “\+” is more accurately regarded as not-provable, rather than not-true (in the sense of FOL)! And bear in mind that Prolog searches for answers to calls in the order that they appear from left-to-right in rules using the definitions of those predicates in the order that they appear from top-to-bottom in the knowledge base. Moreover, clausal form allows no connectives in the head and no nested clauses in the body.
But, Remain Vigilant!
So, some classical equivalences don’t work in Prolog (if negations or built-ins have unbound variables at call time). For example, the following are all equivalent in FOL, but only the first and last are operationally correct in Prolog:
solo(M,A) :- plays(M,A,_), \+ (plays(M,B,_), A\=B).
. . ( solo(M,A) . . . (plays(M,A,X) ( plays(M,B,Y) AB ) ) ) MA BXY
solo(M,A) :- plays(M,A,_), ( \+plays(M,B,_) ; A=B ).
solo(M,A) :- plays(M,A,_), \+plays(M,B,_). solo(M,A) :- plays(M,A,_), A=B .
. .(solo(M,A) . ..(plays(M,A,X) (plays(M,B,Y) A=B))) MA BXY
solo(M,A) :- plays(M,A,_), forall(plays(M,B,_), A=B).
. . ( solo(M,A) . . . (plays(M,A,X) ( plays(M,B,Y) → A=B ) ) ) MA BXY
Negation As Failure (to prove)
Suppose we have a single Prolog rule (stating Diego is happy if he doesn’t see a grilled cheese sandwich):
And suppose we are interested in the following query (asking if Diego is happy): The translation of the clause into classical logic gives
happy(diego) :- \+ sees(diego, sandwich)
?- happy(diego).
happy(diego) sees(diego, sandwich)
And the classical FOL interpretations of this formula can be partitioned into • 16 non-models where ¬happy(diego) and ¬sees(diego, sandwich)
• 16 models where ¬happy(diego) and sees(diego, sandwich) • 16 models where happy(diego) and ¬sees(diego, sandwich) • 16 models where happy(diego) and sees(diego, sandwich)
where the remaining 4 atoms can each be true or false: happy(sandwich), sees(diego, diego), sees(sandwich, diego), sees(sandwich, sandwich)
happy(diego) sees(diego, sandwich)
As Diego is happy in 32 models and unhappy in 16, neither happy(diego) nor ¬happy(diego) is entailed by FOL!
Negation As Failure (to prove)
Suppose we have a single Prolog rule (stating Diego is happy if he doesn’t see a grilled cheese sandwich): And suppose we are interested in the following query (asking if Diego is happy):
But this query succeeds as Prolog concludes that the given rule provides a justification for concluding Diego is happy on the basis that he doesn’t see a sandwich – as there are no rules to suggest that could be the case! However, if extra knowledge implying sees(diego, sandwich) were to be added, then the query would fail
Thus, like real agents Prolog is non-classical (i.e. may returns answers that are not strictly entailed by FOL) • And, like real agents, Prolog is non-monotonic (i.e. may have to retract answers in the face of new data)
• And, like real agents, Prolog is closed-world (i.e. may assume false facts for which can never be proved)
• And this is what allows Prolog to simulate common-sense reasoning about norms, exceptions and priorities
The formalisation of the intended semantics of NAF preoccupied logic programmers for decades and gave rise to many proposals: e.g. Clark-completion, iterated-fixpoints, 3-valued semantics, preferred models, well-founded models and (the eventual favourite) stable models; but its practical value has been evident from the outset!
happy(diego) :- \+ sees(diego, sandwich)
?- happy(diego).
Transitive closure
The following example illustrates another very powerful property of Prolog: Suppose we give Prolog the definition of a relation (e.g. father):
father(adam,cain). father(adam,abel). father(adam,seth). father(cain,enoch). father(enoch,irad). …
Then we can easily compute its transitive closure (i.e. patrilineal ancestorship):
• It is interesting to note that, while Prolog does exactly what we expect and correctly computes the transitive closure, it has been shown that this operation is not even definable within classical FOL (Fagin, 1974).
• For example, . .(ancestor(X,Y) father(X,Y)) and . . .(ancestor(X,Z) father(X,Y), ancestor(Y,Z)) can XY XYz
easily be shown to have valid classical models in which every person is an ancestor of every other!
• The issue is that FOL can’t express the required closed-world property that the intended solution is in fact the smallest possible relation satisfying the transitive closure property!
ancestor(X,Y) :- father(X,Y).
ancestor(X,Z) :- father(X,Y), ancestor(Y,Z).
Prolog in AI
• common-sense inference with closed-world assumption and computing inductively defined relations outside FOL
• supporting imperative & functional programming styles while offering supporting a more declarative and human interpretable style of representation and reasoning
• the huge convenience of Definite Clause Grammars for artificial and natural language processing
• Excellent tool for rapid prototyping: as “to understand the problem is to have the solution”
Some major strengths of Prolog for AI are its ability for:
Lists
Example
Example
% q1: what if “\=” replaces “@>“?
% q2: what if it is moved earlier?
% q3: try ?- display(X),display(Y),X@>Y.
Lists are the prototypical structured term
• the empty list is []/0 and the list constructor: ‘[|]’/2
• in other Prologs and SWI v6 the list constructor is ‘.’/2
• but the ‘.’/2 is now reserved for dict structures as of SWI v7
• in Prolog lists are written and displayed in shorthand notation • ‘[|]’(Head,Tail) is written [Head|Tail]
• [Head|[]] is written [Head]
• [Head1| [Head2|Tail] ] is written [Head1,Head2|Tail]
List Notation
List Definitions: From Haskell to Prolog
verifier
forwards generator
backwards generator
arbitrary generator
Note: The Prolog definitions are both shorter, simpler and can be used much more flexibly!
List forming (higher-order) predicates
https://www.swi-prolog.org/pldoc/doc_for?object=bagof/3
• bagof(C,Q,L), setof(C,Q,L) and findall(C,Q,L) collect all instantiations of term C generated by solutions to query Q all together in a list L
• bagof/3 allows explicit (existential) quantification of (free) query variables (in Q but not in C); and fails if Q fails
• setof/3 is like bagof/3 but returns a sorted list (without duplicates)
• findall/3 is like bagof/3 but with all implicit quantification over all free query variable; and it succeeds with L=[] if Q fails
Note: arities (…/n) and mode declarations (+,-,? and 🙂 are only used in predicate documentation !!!
bagof/3
explicit existential quantification
between/3 and maplist/3
maplist(p(X1,…,Xk), [Y1,…,Yn], [Z1,…,Zn]) :- p(X1,…,Xk, Y1, Z1),
…
p(X1,…,Xk, Yn, Zn).
Folds and filters are supported: https://www.swi-prolog.org/pldoc/man?section=apply
And there is a library for lambda expressions: https://www.swi-prolog.org/pldoc/man?section=yall
Equality Operators (you’ll only need two!)
forall/2
is
Debugging Tips: simple logging
Inserting print statements into your program to log its execution can often be a quick and effective solution to help you track down errors
The most convenient predicates for this are the built-ins write/1, nl/0, writeln/1 and format/2 (see the online manual for more information)
To debug calls to a particular predicate, a useful trick (which takes advantage of Prolog’s standard depth-first search strategy) is to add an initial dummy clause (which must be the FIRST clause in definition) which prints out the arguments and fails in order to hand control over to the actual predicate definition
For example, if you have a predicate p/2 then you could do the following
p(A,B) :- format(“Calling p with args ~w and ~w\n”,[A,B]), fail. p(…) :- … % your definition of p/2 goes here
Debugging Tips: basic tracing
It is often worth “tracing” a query using a textual or graphical debugger which is typically based around a simple “procedure-box” model with 4 (or 5 or 6) “ports” nicely described here: http://gprolog.org/manual/html_node/gprolog012.html
You can type the commands “trace” and “notrace” to turn the tracer off and on; and the most useful SWIPL options (corresponding to the SWISH icons) are:
• “enter to “creep into” a call (useful to see how this call unfolds step by step)
• “s” to “skip over” a call (useful to jump over an uninteresting call)
• “r” to “retry” a call that just exited (useful to replay a call you just skipped over)
• “u” to “go up” out of this call to the exit of the parent call (useful if you accidentally crept
into a call that that you should have skipped over)
• Press “n” to turn off debugging and continue to the end of the computation (useful if
you realise debugging is no longer required)
• Press “a” to abort the computation (useful if you’ve now realised what the bug is)
Debugging Tips: intermediate tracing
Once you’re familiar with the basic tracing options, the following commands more advanced are also useful (only in SWIPL):
• Press “+” to “set a spy point” on the current predicate
• Press “l” to “leap” to the next spy point (useful if you are interested in calls to specific
predicates)
• Press “-” to “remove spy points” on the current predicate
• Press “b” to invoke an interactive Prolog “break session” where you can type commands
in the current debug context
• you can turn off tracing in the break session using the “n” option
• if you nest break sessions then nesting level is displayed in square brackets
• hit
For more information and advanced options, please see the online manual:
https://www.swi-prolog.org/pldoc/man?section=debugoverview
Debugging Tips: declarative debugging
The above approaches to debugging have a very procedural flavour; but there are also some very useful techniques in an area known as declarative debugging
Here’s a nice video intro to a couple of these techniques – called generalisation and failure slicing: https://www.youtube.com/watch?v=4IWruicMd4c
A textual description is available here: https://www.metalevel.at/prolog/debugging
Note that some of the claims in this video only apply to pure logic programs without cut or negation and where constraints are used instead of built-in arithmetic predicates – but the distinctions are not that important as you can still usefully use these techniques in the coursework or exam preparation
Thank you