Basic Prolog.ppt

1、Basic Prolog,Structure of Programs,Programs consist of procedures.Procedures consist of clauses.Each clause is a fact or a rule.Programs are executed by posing queries.,Clauses: Facts and Rules,“if“ “provided that“ “turnstile“,Head :- Body.,This is a rule.,Head.,This is a fact.,Full stop at the end.

2、,Body of a (Rule) Clause Contains Goals,Head,Body,Goals,:-,likes(mary, X),human(X), honest(X).,Example Program,elephant(george). elephant(mary). elephant(X) :- grey(X), mammal(X),hasTrunk(X).,Predicate,Procedure for elephant,Facts,Clauses can be interpreted in a declarative or a procedural way,Claus

3、e:Declarative reading:Procedural reading:,H :- G1, G2, , Gn.That H is provable follows fromgoals G1, G2, , Gn being provableTo execute procedure H, the procedures called by goals G1, G2, , Gn are executed first,Interpretation of Clauses,Interpretation of Clauses,Clauses can be interpreted in a decla

4、rative, or in a procedural way,Clause:Declarative reading:Procedural reading:,H :- G1, G2, , Gn.That H is provable follows fromgoals G1, G2, , Gn being provableTo execute procedure H, the procedures called by goals G1, G2, , Gn are executed first,Clauses,Clauses provide a convenient way to express c

5、ase analysis and non-determinism.Program clauses and data have the same form.A Prolog program can also be seen as a relational database containing rules and facts.The relational form of procedures makes it possible to define reversible procedures.,Unification,Term-manipulation that passes parameters

6、, returns results, selects and constructs data structuresBasic control flow model is backtrackingSometimes it is necessary to use control features that are not part of logic,Computation via Queries,Facts and rules are stored in a database They can be queried ?- likes(joe, fish). yes ?- likes(joe, ch

7、ocolate) no Important: no means “I know its false, or I dont know” yes means “I can prove it” asymmetric,Example Queries,Queries,Replies,?- elephant(george).Yes?- elephant(jane).no,Prologs Style,State the facts and rules Pose queries Prolog finds the answers by searching the facts deducing new facts

8、 from the rules Answers depend on the search algorithm,Imperative/Functional/Declarative Styles Example - Concatenate lists a and b,concat(, Z, Z). concat(H|T, L, H|Z) :- concat(T, L, Z).,list procedure concat(list a, list b) list t = list u = copylist(a);while (t.tail != nil) t = t.tail;t.tail = b;

9、return u; ,cat(a,b) if b = nil then aelse cons(head(a), concat(tail(a),b),In an imperative PL,In a functional PL,In a declarative PL,Example: Zoo,/* Facts */ elephant(gigi). elephant(mary). elephant(joe). panda(chi_chi). panda(ming_ming). stripey(tigger). stripey(mrED). big_teeth(tigger). isaCat(tig

10、ger). isaHorse(mrED). venomous(rattler). venomous(grass_snake).,/* Rules */ dangerous(X) :- big_teeth(X). dangerous(X) :- venomous(X). swims(Y) :- isaFish(Y). guess(X, tiger) :- stripey(X),big_teeth(X), isaCat(X). guess(X, koala) :-arboreal(X), sleepy(X). guess(X, zebra) :- stripey(X),isaHorse(X)./*

11、 Sample Queries */ ?- dangerous(ming_ming). ?- dangerous(X). ?- guess(X,Y).,www2.hawaii.edu/janst/313/prolog/zoo.pl,Colored ball problem,Find the correct sequence of colored balls to satisfy the given rules: One red, one black and one white ball Solution will be a permutation of red,black,white whit

12、e is just to the right of black If black is in pos1, white is in pos2, If black is in pos2, white is in pos3 black is not in the center Black cant be in pos2www2.hawaii.edu/janst/313/prolog/colors.pl,Cryptarithmatic Problem,Find the unique digit that will replace each character to solve a puzzleS E

13、N D + M O R E - M O N E Ywww2.hawaii.edu/janst/313/prolog/crypto.pl,Eight Queens Problem,Given an 8-by-8 chessboard, place 8 queens so that they do not threaten each other along a row, column, or a diagonalMathematically determine diagonal two queens are on the same / (UR-BL) diagonal iff the sum of

14、 the row and the column is the same for each two queens are on the same (UL-BR) diagonal iff the difference between the row and the column are the same for eachGeneralize: N queens (N =4),www2.hawaii.edu/janst/313/prolog/queens.pl,N-Queens Without Searching,A solution to the N-Queens problem for any N = 4Placing queens takes constant time per queen, O(N)Drawing the board takes O(N2) timePublished in ACM SIGART Bulletin, 2(2), page 7See example at www.apl.jhu.edu/hall/NQueens.html now unfortunately broken,