A First Look At Prolog
A First Look At Prolog
Chapter Nineteen
Copyright By PowCoder代写 加微信 powcoder
Modern Programming Languages, 2nd ed.
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Using a Prolog language system
The two faces of Prolog
Negation and failure
What Prolog is good for
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Everything in Prolog is built from terms:
Prolog programs
The data manipulated by Prolog programs
Three kinds of terms:
Constants: integers, real numbers, atoms
Compound terms
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Integer constants: 123
Real constants: 1.23
A lowercase letter followed by any number of additional letters, digits or underscores: fred
A sequence of non-alphanumeric characters:
*, ., =, @#$
Plus a few special atoms: []
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Atoms Are Not Variables
An atom can look like an ML or Java variable:
– i, size, length
But an atom is not a variable; it is not bound to anything, never equal to anything else
Think of atoms as being more like string constants: “i”, “size”, “length”
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Any name beginning with an uppercase letter or an underscore, followed by any number of additional letters, digits or underscores: X, Child, Fred, _, _123
Most of the variables you write will start with an uppercase letter
Those starting with an underscore, including
_, get special treatment
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Compound Terms
An atom followed by a parenthesized, comma-separated list of one or more terms: x(y,z), +(1,2), .(1,[]),
parent(adam,seth), x(Y,x(Y,Z))
A compound term can look like an ML function call: f(x,y)
Again, this is misleading
Think of them as structured data
Chapter Nineteen
Modern Programming Languages, 2nd ed.
All Prolog programs and data are built from such terms
Later, we will see that, for instance,
+(1,2) is usually written as 1+2
But these are not new kinds of terms, just abbreviations
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Unification
Pattern-matching using Prolog terms
Two terms unify if there is some way of binding their variables that makes them identical
For instance, parent(adam,Child) and parent(adam,seth) unify by binding the variable Child to the atom seth
More details later: Chapter 20
Chapter Nineteen
Modern Programming Languages, 2nd ed.
The Prolog Database
A Prolog language system maintains a collection of facts and rules of inference
It is like an internal database that changes as the Prolog language system runs
A Prolog program is just a set of data for this database
The simplest kind of thing in the database is a fact: a term followed by a period
Chapter Nineteen
Modern Programming Languages, 2nd ed.
parent(kim,holly). parent(margaret,kim). parent(margaret,kent). parent(esther,margaret). parent(herbert,margaret). parent(herbert,jean).
A Prolog program of six facts
Defining a predicate parent of arity 2
We would naturally interpret these as facts about families: Kim is the parent of Holly and so on
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Using a Prolog language system
The two faces of Prolog
Negation and failure
What Prolog is good for
Chapter Nineteen
Modern Programming Languages, 2nd ed.
SWI-Prolog
Prompting for a query with ?-
Normally interactive: get query, print result, repeat
Welcome to SWI-Prolog …
For help, use ?- help(Topic). or ?- apropos(Word).
Chapter Nineteen
Modern Programming Languages, 2nd ed.
The consult Predicate
Predefined predicate to read a program from a file into the database
File relations (or relations.pl) contains our parent facts
?- consult(relations).
% relations compiled 0.00 sec, 852 bytes true.
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Simple Queries
A query asks the language system to prove something
Some turn out to be true, some false
(Some queries, like consult, are executed only for their side-effects)
?- parent(margaret,kent).
?- parent(fred,pebbles).
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Final Period
Queries can take multiple lines
If you forget the final period, Prolog prompts for more input with |
?- parent(margaret,kent)
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Queries With Variables
Any term can appear as a query, including a term with variables
The Prolog system shows the bindings necessary to prove the query
?- parent(P,jean).
P = herbert.
?- parent(P,esther).
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Flexibility
Normally, variables can appear in any or all positions in a query:
parent(Parent,jean)
parent(esther,Child)
parent(Parent,Child)
parent(Person,Person)
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Multiple Solutions
When the system finds a solution, it prints the binding it found
If it could continue to search for additional solutions, it then prompts for input
Hitting Enter makes it stop searching and print the final period…
?- parent(Parent,Child).
Parent = kim, Child = holly .
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Multiple Solutions
… entering a semicolon makes it continue the search
As often as you do this, it will try to find another solution
In this case, there is one for every fact in the database
?- parent(Parent,Child).
Parent = kim, Child = holly ; Parent = margaret, Child = kim ; Parent = margaret, Child = kent ; Parent = esther, Child = margaret ; Parent = herbert, Child = margaret ; Parent = herbert, Child = jean.
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Conjunctions
A conjunctive query has a list of query terms separated by commas
The Prolog system tries prove them all (using a single set of bindings)
?- parent(margaret,X), parent(X,holly).
Chapter Nineteen
Modern Programming Languages, 2nd ed.
?- parent(Parent,kim), parent(Grandparent,Parent).
Parent = margaret, Grandparent = esther ; Parent = margaret, Grandparent = herbert ; false.
?- parent(esther,Child),
parent(Child,Grandchild), parent(Grandchild,GreatGrandchild).
Child = margaret, Grandchild = kim, GreatGrandchild = holly .
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Using a Prolog language system
The two faces of Prolog
Negation and failure
What Prolog is good for
Chapter Nineteen
Modern Programming Languages, 2nd ed.
The Need For Rules
Previous example had a lengthy query for great-grandchildren of would be nicer to query directly:
greatgrandparent(esther,GGC)
But we do not want to add separate facts of that form to the database
The relation should follow from the
parent relation already defined
A rule says how to prove something: to prove the head, prove the conditions
To prove greatgrandparent(GGP,GGC), find some GP and P for which you can prove parent(GGP,GP), then parent(GP,P) and then finally parent(P,GGC)
greatgrandparent(GGP,GGC) :- parent(GGP,GP), parent(GP,P),
parent(P,GGC).
conditions
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Chapter Nineteen
Modern Programming Languages, 2nd ed.
A Program With The Rule
A program consists of a list of clauses
A clause is either a fact or a rule, and ends with a period
parent(kim,holly). parent(margaret,kim). parent(margaret,kent). parent(esther,margaret). parent(herbert,margaret). parent(herbert,jean). greatgrandparent(GGP,GGC) :-
parent(GGP,GP), parent(GP,P), parent(P,GGC).
Chapter Nineteen
Modern Programming Languages, 2nd ed.
This shows the initial query and final result
Internally, there are intermediate goals:
The first goal is the initial query
The next is what remains to be proved after transforming the first goal using one of the clauses (in this case, the greatgrandparent rule)
And so on, until nothing remains to be proved
?- greatgrandparent(esther,GreatGrandchild).
GreatGrandchild = holly .
1. parent(kim,holly).
parent(margaret,kim).
parent(margaret,kent).
parent(esther,margaret).
parent(herbert,margaret).
parent(herbert,jean).
greatgrandparent(GGP,GGC) :-
parent(GGP,GP), parent(GP,P), parent(P,GGC).
greatgrandparent(esther,GreatGrandchild)
Clause 7, binding GGP to esther and GGC to GreatGrandChild
parent(esther,GP), parent(GP,P), parent(P,GreatGrandchild)
Clause 4, binding GP to margaret parent(margaret,P), parent(P,GreatGrandchild)
Clause 2, binding P to kim parent(kim,GreatGrandchild)
Clause 1, binding GreatGrandchild to holly
Chapter Nineteen
Modern Programming Languages, 2nd ed.
We will see more about Prolog’s model of execution in Chapter 20
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Rules Using Other Rules
Same relation, defined indirectly
Note that both clauses use a variable P
The scope of the definition of a variable is the clause that contains it
grandparent(GP,GC) :- parent(GP,P), parent(P,GC).
greatgrandparent(GGP,GGC) :- grandparent(GGP,P), parent(P,GGC).
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Recursive Rules
ancestor(X,Y) :- parent(X,Y). ancestor(X,Y) :-
parent(Z,Y), ancestor(X,Z).
X is an ancestor of Y if:
Base case: X is a parent of Y
Recursive case: there is some Z such that Z is a parent of Y, and X is an ancestor of Z
Prolog tries rules in the order you give them, so put base-case rules and facts first
Chapter Nineteen
Modern Programming Languages, 2nd ed.
?- ancestor(jean,jean).
?- ancestor(kim,holly).
?- ancestor(A,holly).
A = margaret ;
A = esther ; A = herbert ; false.
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Core Syntax Of Prolog
You have seen the complete core syntax:
There is not much more syntax for Prolog than this: it is a very simple language
Syntactically, that is!
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Using a Prolog language system
The two faces of Prolog
Negation and failure
What Prolog is good for
Chapter Nineteen
Modern Programming Languages, 2nd ed.
The Procedural Side
greatgrandparent(GGP,GGC) :-
parent(GGP,GP), parent(GP,P), parent(P,GGC).
A rule says how to prove something:
– To prove greatgrandparent(GGP,GGC), find some GP and P for which you can prove parent(GGP,GP), then parent(GP,P) and then finally parent(P,GGC)
A Prolog program specifies proof procedures for queries
The Declarative Side
A rule is a logical assertion:
– For all bindings of GGP, GP, P, and GGC, if parent(GGP,GP) and parent(GP,P) and parent(P,GGC), then greatgrandparent(GGP,GGC)
Just a formula – it doesn’t say how to do
anything – it just makes an assertion:
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Declarative Languages
Each piece of the program corresponds to a simple mathematical abstraction
Prolog clauses – formulas in first-order logic
ML fun definitions – functions
Many people use declarative as the opposite of imperative, including both logic languages and functional languages
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Declarative Advantages
Imperative languages are doomed to subtle side-effects and interdependencies
Simpler declarative semantics makes it easier to develop and maintain correct programs
Higher-level, more like automatic programming: describe the problem and have the computer write the program
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Prolog Has Both Aspects
Partly declarative
A Prolog program has logical content
Partly procedural
A Prolog program has procedural concerns: clause ordering, condition ordering, side- effecting predicates, etc.
It is important to be aware of both
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Using a Prolog language system
The two faces of Prolog
Negation and failure
What Prolog is good for
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Prolog has some predefined operators (and the ability to define new ones)
An operator is just a predicate for which a special abbreviated syntax is supported
Chapter Nineteen
Modern Programming Languages, 2nd ed.
The = Predicate
The goal =(X,Y) succeeds if and only if X
and Y can be unified:
Since = is an operator, it can be and usually is written like this:
?- =(parent(adam,seth),parent(adam,X)).
?- parent(adam,seth)=parent(adam,X).
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Arithmetic Operators
Predicates +, -, * and / are operators too, with the usual precedence and associativity
?- X = +(1,*(2,3)).
X = 1+2*3.
?- X = 1+2*3.
X = 1+2*3.
Prolog lets you use operator notation, and prints it out that way, but the underlying term is still +(1,*(2,3))
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Not Evaluated
The term is still +(1,*(2,3))
It is not evaluated
There is a way to make Prolog evaluate such terms, but we won’t need it yet
?- +(X,Y) = 1+2*3.
X = 1, Y = 2*3.
?- 7 = 1+2*3.
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Using a Prolog language system
The two faces of Prolog
Negation and failure
What Prolog is good for
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Lists in Prolog
A bit like ML lists
The atom [] represents the empty list
A predicate . corresponds to ML’s ::
ML expression Prolog term
1::[] .(1,[])
1::2::3::[] .(1,.(2,.(3,[])))
No equivalent. .(1,.(parent(X,Y),[]))
Chapter Nineteen
Modern Programming Languages, 2nd ed.
List Notation
ML-style notation for lists
These are just abbreviations for the underlying term using the . Predicate
Prolog usually displays lists in this notation
List notation Term denoted
[1] .(1,[])
[1,2,3] .(1,.(2,.(3,[])))
[1,parent(X,Y)] .(1,.(parent(X,Y),[]))
Chapter Nineteen
Modern Programming Languages, 2nd ed.
?- X = .(1,.(2,.(3,[]))).
X = [1, 2, 3].
?- .(X,Y) = [1,2,3].
Y = [2, 3].
Chapter Nineteen
Modern Programming Languages, 2nd ed.
List Notation With Tail
Last in a list can be the symbol | followed by a final term for the tail of the list
Useful in patterns: [1,2|X] unifies with any list that starts with 1,2 and binds X to the tail
List notation Term denoted
[1|X] .(1,X)
[1,2|X] .(1,.(2,X))
[1,2|[3,4]] same as [1,2,3,4]
?- [1,2|X] = [1,2,3,4,5].
X = [3, 4, 5].
Chapter Nineteen
Modern Programming Languages, 2nd ed.
The append Predicate
Predefined append(X,Y,Z) succeeds if and only if Z is the result of appending the list Y onto the end of the list X
?- append([1,2],[3,4],Z).
Z = [1, 2, 3, 4].
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Not Just A Function
append can be used with any pattern of instantiation (that is, with variables in any positions)
?- append(X,[3,4],[1,2,3,4]).
X = [1, 2] .
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Not Just A Function
?- append(X,Y,[1,2,3]).
Y = [1, 2, 3] ;
Y = [2, 3] ;
X = [1, 2],
X = [1, 2, 3], Y = [] ;
Chapter Nineteen
Modern Programming Languages, 2nd ed.
An Implementation
append([], B, B).
append([Head|TailA], B, [Head|TailC]) :- append(TailA, B, TailC).
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Other Predefined List Predicates
All flexible, like append
Queries can contain variables anywhere
Predicate Description
member(X,Y) Provable if the list Y contains the element X.
select(X,Y,Z) Provable if the list Y contains the element X, and Z is the same as Y but with one instance of X removed.
nth0(X,Y,Z) Provable if X is an integer, Y is a list, and Z is the Xth element of Y, counting from 0.
length(X,Y) Provable if X is a list of length Y.
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Using select
?- select(2,[1,2,3],Z).
Z = [1, 3] ;
?- select(2,Y,[1,3]).
Y = [2, 1, 3] ;
Y = [1, 2, 3] ;
Y = [1, 3, 2] ;
Chapter Nineteen
Modern Programming Languages, 2nd ed.
The reverse Predicate
Predefined reverse(X,Y) unifies Y with the reverse of the list X
?- reverse([1,2,3,4],Y).
Y = [4, 3, 2, 1].
Chapter Nineteen
Modern Programming Languages, 2nd ed.
An Implementation
reverse([],[]). reverse([Head|Tail],X) :-
reverse(Tail,Y), append(Y,[Head],X).
Not an efficient way to reverse
We’ll see why, and a more efficient solution, in Chapter 21
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Non-Terminating Queries
Asking for another solution caused an infinite loop
Hit Control-C to stop it, then a for abort
reverse cannot be used as flexibly as
?- reverse(X,[1,2,3,4]).
X = [4, 3, 2, 1] ;
^CAction (h for help) ? abort
% Execution Aborted
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Flexible and Inflexible
Ideally, predicates should all be flexible like
They are more declarative, with fewer procedural quirks to consider
But inflexible implementations are sometimes used, for efficiency or simplicity
Another example is sort…
Chapter Nineteen
Modern Programming Languages, 2nd ed.
A fully flexible sort would also be able to unsort—find all permutations
But it would not be as efficient for the more common task
?- sort([2,3,1,4],X).
X = [1, 2, 3, 4].
?- sort(X,[1,2,3,4]).
ERROR: Arguments are not sufficiently instantiated
Chapter Nineteen
Modern Programming Languages, 2nd ed.
The Anonymous Variable
The variable _ is an anonymous variable
Every occurrence is bound independently of every other occurrence
In effect, much like ML’s _: it matches any term without introducing bindings
Chapter Nineteen
Modern Programming Languages, 2nd ed.
tailof([_|A],A).
This tailof(X,Y) succeeds when X is a non-empty list and Y is the tail of that list
Don’t use this, even though it works:
tailof([Head|A],A).
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Dire Warning
append([], B, B).
append([Head|TailA], B, [Head|TailC]) :- append(TailA, B, Tailc).
Don’t ignore warning message about singleton variables
As in ML, it is bad style to introduce a variable you never use
More importantly: if you misspell a variable name, this is the only warning you will see
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Using a Prolog language system
The two faces of Prolog
Negation and failure
What Prolog is good for
Chapter Nineteen
Modern Programming Languages, 2nd ed.
The not Predicate
For simple applications, it often works quite a bit logical negation
But it has an important procedural side…
?- member(1,[1,2,3]). true .
?- not(member(4,[1,2,3])). false.
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Negation As Failure
To prove not(X), Prolog attempts to prove X
not(X) succeeds if X fails
The two faces again:
Declarative: not(X) = ¬X
Procedural: not(X) succeeds if X fails, fails if
X succeeds, and runs forever if X runs forever
sibling(X,Y) :-
parent(P,X),
parent(P,Y),
?- sibling(X,Y).
Y = kent ; X = kent, Y = kim ;
X = margaret, Y = jean ;
Y = margaret ;
sibling(X,Y) :- not(X=Y),
parent(P,X),
parent(P,Y).
?- sibling(kim,kent).
?- sibling(kim,kim).
?- sibling(X,Y).
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Chapter Nineteen
Modern Programming Languages, 2nd ed.
Using a Prolog language system
The two faces of Prolog
Negation and failure
What Prolog is good for
Chapter Nineteen
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com