CSI2120 Programming Paradigms Jochen Lang
jlang@uottawa.ca
Faculté de génie | Faculty of Engineering
Jochen Lang, EECS jlang@uOttawa.ca
Logic Programming in Prolog
• BacktrackingwiththeCut – The “Cut”
– Coding the existence of a single solution • no other rules should be tried
• no backtracking across this point
– Abandoning a goal with cut and fail • Datastructures:Lists
– Basic list processing
– Appending a list to another – Reading into a list
Jochen Lang, EECS jlang@uOttawa.ca
The “Cut” !
• “cut”offsomebacktrackingpath
– Prolog will not try to re-satisfy certain goals.
• Reasonsforusingthecut
– faster execution
– more efficient use of memory (don’t have to keep track of as many backtrack points)
• Syntax:!
– goal that always succeeds and has a side effect (on
Jochen Lang, EECS jlang@uOttawa.ca
the way backtracking works)
A Simple Example:
• Goal:Removingbranchesfromthesearchtreethatare known not to produce a solution.
• Example:Acatiseitheramaleorfemalecat.Whenone fact is proven, there is no point in searching for the opposite.
Jochen Lang, EECS jlang@uOttawa.ca
cat(X) :- tomcat(X), !.
cat(X) :- female_cat(X), !.
– The cut commits Prolog to the facts established • if the subgoal tomcat(X) succeeds, the cut
succeeds and the cat rule in the first row succeeds. The backtracking path is now cut off and Prolog will not search to re-satisfy tomcat(X) or cat(X).
Effect of the Cut
• Whenacutisencounteredasagoal,thesystem becomes committed to all choices made since the parent goal was invoked.
– This means the choice of which clause, and all the choices in the “sibling” goals up to the cut are fixed.
• ThereforetheCutpermitstheeliminationofbranchesin the search tree by
– eliminating other rules for the same goal – eliminating other choices for subgoals
Jochen Lang, EECS jlang@uOttawa.ca
Example: Search tree.
• Rules and facts a,b,c,d,e,h arranged in a tree
h de
h(X) :- d(X).
h(X) :- X=e.
d(X) :- X=a.
d(X) :- X=b.
d(X) :- X=c.
a.
b. c. e.
abc
• Query initiating a tree traversal:
?- h(X).
• Produces the leave nodes (depth first search): abce
Jochen Lang, EECS jlang@uOttawa.ca
Example: Search tree with cut branches
h de
• Rules and facts a,b,c,d,e,h arranged in a tree
h(X) :- d(X).
h(X) :- X=e.
d(X) :- X=a,!.
d(X) :- X=b.
d(X) :- X=c.
a.
b. c. e.
abc
• Query initiating a tree traversal:
?- h(X).
• Produces only the leave nodes (depth first search): ae
Jochen Lang, EECS jlang@uOttawa.ca
An Arithmetic Example: roots
• Anaivewaytocalculatetheintegerrootofanumberis to use a generator for integer numbers and see if the result succeeds.
• Generator
int(0).
int(N) :- int(N1), N is N1+1.
• Rootpredicate
root(N,R) :- int(K), K*K>N,!, R is K-1.
– Cut ensure that once , backtracking of the generator stops (int).
Jochen Lang, EECS jlang@uOttawa.ca
Red vs. Green Cuts
• RedCuts
– change the solution space (see the previous root example).
• GreenCuts
– remove choices that wouldn’t work anyway – efficiency gain
– reduced memory footprint
Jochen Lang, EECS jlang@uOttawa.ca
Summary: Utility of the Cut
• Delete branches that will not lead to a solution
• Removemutuallyexclusivecasesinrules
• Reducethenumberofsolutionsproduced
• Makesurethatcertainprograms(recursion)terminate • Controloftheproofprocedure
Jochen Lang, EECS jlang@uOttawa.ca
If-then-else
• Max function returning the larger of two numbers
max(X,Y,X) :- X >= Y.
max(_,Y,Y).
• This will produce surprising results, consider
Jochen Lang, EECS jlang@uOttawa.ca
?- max(7,5,X).
Call: (6) max(7, 5, _G1326) ? creep
Call: (7) 7>=5 ? creep
Exit: (7) 7>=5 ? creep
Exit: (6) max(7, 5, 7) ? creep
X=7;
Redo: (6) max(7, 5, _G1326) ? creep Exit: (6) max(7, 5, 5) ? creep
X = 5.
If-then-else with the Cut
• Solution: Use an explicit test
max(X,Y,X) :- X >= Y.
max(X,Y,Y) :- X < Y.
• Solution: Use the Cut for efficiency
max(X,Y,X) :- X >= Y, !.
max(_,Y,Y).
• Query
?- max(7,5,X).
Call: (6) max(7, 5, _G1326) ? creep
Call: (7) 7>=5 ? creep
Exit: (7) 7>=5 ? creep
Exit: (6) max(7, 5, 7) ? creep
X = 7.
Jochen Lang, EECS jlang@uOttawa.ca
Predicate fail
• Thefailpredicatealwaysfails.
• CombinedwiththeCutwegetnegation
is_false(P) :- P, !, fail.
is_false(P).
• TheclausePiseithertruethenthegoalis_falsefails. – Subgoal P is true, Cut is true cutting backtracking
off, fail succeeds making the goal is_false(P) fail. – If subgoal P fails, the second rule succeeds.
• Thecombinationiscalledcut-fail.
Jochen Lang, EECS jlang@uOttawa.ca
Built-in predicate not
• Predicatenotbehavesasthepreviousexample is_false.
?- not(fail).
true.
?- not(X=1).
false.
?- not(X=1),X=0.
false.
• Verifiesthefailureofaterm.
• not/1 should be used as a predicate with instantiated
arguments for verification purposes. – it does not generate solutions
Jochen Lang, EECS jlang@uOttawa.ca
Simple Example with Negation
happy_camper(X):- not(sad(X)), camper(X).
camper(joe).
sad(jane).
• Queries
?- happy_camper(joe).
true.
?- happy_camper(jane).
false.
?- happy_camper(X).
false.
Jochen Lang, EECS jlang@uOttawa.ca
Negation: not or \+
• Thenegationpredicatenot(F)withFatermcanalso be written with the operator \+F
– Associative prefix operator • Negationbyfailure
– Prolog proofs the success of a goal not(F) by showing that it can not satisfy F.
• Remember that Prolog may also fail to proof F for trivial reasons, e.g., it may simply missing facts in its database.
– Prolog’s proof strategy is referred to as closed world assumption.
Jochen Lang, EECS jlang@uOttawa.ca
Not Equals or Difference
• Wehaveseentheoperatornotequalsbefore.
X=\= Y.
• Binarydifferenceoperatoristheoppositeofa successful unification of its’ arguments.
– This operator is equivalent to the following definition
X =\= Y :- not(X = Y).
– expressed with cut-fail
Jochen Lang, EECS jlang@uOttawa.ca
X =\= X :- !,fail.
X =\= Y.
Interval Predicate Again
• Recallpreviousdefinitionofatestforanintervalanda separate definition of a generator for interval
intervalTest(X,L,H):- X>=L, X=