COMP 481, Prolog Chapters 1 to 3
Ch 1: Facts, Rules, and Queries
Copyright By PowCoder代写 加微信 powcoder
Ch 2: Matching and Proof Search
Ch 3: Recursion
University of the Fraser Valley
COMP 481: Functional and Logic Programming
• Chapter 1
• Knowledge Base 1: kb1.pl
• Knowledge Base 2: kb2.pl
• Knowledge Base 3: kb3.pl
• Knowledge Base 4: kb4.pl
• Knowledge Base 5: kb5.pl
• Prolog Syntax
• Chapter 2
• Matching
• The Occurs Check
• Programming with Matching
• Proof Search
• Chapter 3
• Recursive Definitions
• Descendance
• Successor
• Addition
• Clause Ordering, Goal Ordering, and Termination
Programming conditions within if-statement constructs
gives you natural experience with logical expressions.
Recall logical operators:
• variables `p` and `q` can be replaced with values `True` or `False`
• we perform Boolean operations, such as AND and OR
p q p AND q
p q p OR q
We can combine logical expressions to create formal
arguments (for example, modus ponens):
All statements except the last in the argument must be
true, so that we can imply the last statement is true.
So, we expand our knowledge in argumentation.
But it is all very robotic… …so why not make a computer do it?
— Chapter 1 —
Definitions
• knowledge base — is a Prolog program
• facts — true or false statements
• rules — we start with “if” :- statements, but can be more complex
• head to the left of :- and body to the right
• clause — parts of a statement that themselves can be true or false
• predicate — function with true false output value
• property — like a predicate, but one input value
• relation — like a predicate, but more than one input value
• query — interactive SWI-Prolog statement we type in
• goals — the intermediate clauses that Prolog proves to answer query
• matching / variable binding / instantiation (discussed later)
• terms (described in more detail at end of chapter)
• atoms, numbers, variables, complex terms
• a collection of facts and rules is called a knowledge base
(also called a database)
• facts/rules are logical statements that can be true or false
• but there is an order of execution Prolog follows for such statements
• a Prolog program is a knowledge base
• we use a Prolog program by issuing queries
• to ask questions about info written in the knowledge base
• originally, Prolog was to be an interactive NLP system
The first example of a Prolog program is written with the
following facts:
• Mia, Jody, and Yolanda are women
• Jody plays air guitar
woman(mia).
woman(jody).
woman(yolanda).
playsAirGuitar(jody).
The text calls this example of four facts `KB1`.
Make sure:
• do NOT name files with dashes
• name with lowercase first letter
(and not a starting underscore),
then lowercase/uppercase/underscore characters ONLY
• finish with file extension `.pl`
Interactive
Some description of interactive Prolog sessions:
• begin in CMD with `swipl kb1.pl`
• prompt starts with `?-`
• type in a statement you would like to check against KB1
• e.g.: `woman(mia).`
• note the period at the end (“full stop”)
• `woman(mia).` matches a statements in KB1, so Prolog replies `true.`
• e.g.: `playsAirGuitar(mia).`
• reply is `false.`, since no statements in KB1 match
• none of the statements infer our query is true either
Two other queries that result in `false.`:
• `playsAirGuitar(vincent).`
(because `vincent` is not a value in the knowledge base)
• `tatooed(jody).`
(because `tatooed` is not a property in the knowledge base)
listensToMusic(mia).
happy(yolanda).
playsAirGuitar(mia) :- listensToMusic(mia).
playsAirGuitar(yolanda) :- listensToMusic(yolanda).
listensToMusic(yolanda) :- happy(yolanda).
The first two statements are facts:
• Mia listens to music
• Yolanda is happy
The last three statements are rules:
• Mia plays air guitar if she listens to music
• Yolanda plays air guitar if she listens to music
• Yolanda listens to music if she is happy
A rule with `:-` syntax has:
• statement head to the left
• and statement body to the right
So a rule `head :- body`
• allows Prolog to infer `head` is true
• when `body` is matched and true in the knowledge base
The above deduction argument is called modus ponens.
With `kb2.pl`, we can ask the query
`playsAirGuitar(mia).`
that results in `true.` from Prolog executing its search.
Prolog does so by matching with modus ponens argument:
• listensToMusic(mia).
• playsAirGuitar(mia) :- listensToMusic(mia).
Hence, our query must be true.
Depending on the order of statements in our knowledge base,
Prolog may find a different argument to imply the truth of a query.
Further implied statements can be used as input to more
rules for yet more deductions:
• happy(yolanda).
• listensToMusic(yolanda) :- happy(yolanda).
• playsAirGuitar(yolanda) :- listensToMusic(yolanda).
Therefore, `playsAirGuitar(yolanda)` is true.
Prolog can chain the above rules together in multiple
applications of modus ponens.
Predicates
Predicates represent potential values having a property.
The three predicates in KB2 are:
• listensToMusic
• playsAirGuitar
The `playsAirGuitar` is defined with two statements:
• one a rule involving `mia`
• and the other a rule involving `yolanda`
A fact can also be considered a rule with an empty body.
• conditionals with no antecedent conditions
• or degenerate rules
happy(vincent).
listensToMusic(butch).
playsAirGuitar(vincent) :-
listensToMusic(vincent),
happy(vincent).
playsAirGuitar(butch) :-
happy(butch).
playsAirGuitar(butch) :-
listensToMusic(butch).
• the first two clauses are facts, and the last three are rules
• a clause can be continued to the next line with an indent
• blank lines add some readability between blocks of statements
KB3 defines a predicate with the three rules for
`playsAirGuitar`:
The rule involving `vincent` has two items in its body:
• the items are formally called goals in Prolog
• first goal is `listensToMusic(vincent)`
• second goal is `happy(vincent)`
• the two goals are separated by a comma
• the comma represents logical AND operation
Results in
So Vincent plays air guitar
• if he listens to music
• and he is happy
• but a query `playsAirGuitar(vincent)` would result in `false.`
• Vincent is happy, `happy(vincent)` is in KB3
• but he is not listening to music, as `listensToMusic(vincent)`
• is not a fact
• cannot be implied
The last two rules for `playsAirGuitar` involving `butch`
give syntax for logical “OR” operation:
• both rules with the same head, but different body
• a query `playsAirGuitar(butch)` results in `true.`
• `happy(butch)` is false
• but `listensToMusic(butch)` is a fact
and implies `playsAirGuitar(butch)`
The shorthand operation for “OR” is to use semicolon to
separate clauses.
woman(mia).
woman(jody).
woman(yolanda).
loves(vincent, mia).
loves(marcellus, mia).
No rules here, and only facts.
• examples of predicates with two parameters
• another name for this is a relation
Interactive
A query made on `kb4.pl` demonstrate use of variables:
?- woman(X).
• variable `X` will be searched for matches with the knowledge base
• the matches should satisfy the entire statement in the query
• all such matches for `X` will be found
• we can iterate over the matches interactively with `;`+`ENTER`
(remember, `;` means the “OR” operation)
• (textbook uses old Prolog: `;` iteration ends with result `no.`)
• SWI-Prolog will just provide another prompt after
the last value is matched when matching is finished
So which values for `X` have property that are `woman`?
This is because of facts like `woman(mia)` in `kb4.pl`
• so `X` matches `mia`
(and similarly for the other values found)
Matching is called variable binding or instantiation.
Conjunction
We can combine clauses in a query with `,` for the “AND”
operation:
loves(marcellus, X), woman(X).
In plain language, we are asking
“Who loves Marcellus and is a woman?”
• we have result `X = mia`
• `mia` has property `woman`
• the relation `loves(marcellus, mia)` is in the knowledge base
The interactive execution that Prolog provides to satisfy
queries is the entire point of the language.
We will learn more about order of execution when
matching (to best use it and avoid endless processing).
loves(vincent, mia).
loves(marcellus, mia).
jealous(X, Y) :- loves(X, Z), loves(Y, Z).
The last rule says much more with variables:
• if both `X` and `Y` love the same `Z`, then `X` will be jealous of `Y`
• this is only a logical way we might define the notion of jealousy
• the rule does not have the true complexity of real jealousy
• the `jealous` rule is a general statement
(about everything) that involves variables `X`, `Y`, and `Z`
We can then query:
jealous(marcellus, W).
• in plain language: Who is Marcellus is jealous of?
• both Marcellus and Vincent love Mia
• by rule of `jealous`, then `marcellus` is jealous of `vincent`
Therefore, the result is `W = vincent`, but you can see
another value if you press semicolon.
• how much sense does this notion of jealousy make after we see the
matched values from our query?
— Prolog Syntax —
There are four kinds of parts to facts and rules in Prolog
that are all collectively named terms:
2. numbers
3. variables
4. complex terms
• the first three are categorized as simple terms
• atoms and numbers are also called constants
Characters
Naming things in Prolog requires us to have a clear
understanding of what characters are available for use:
• uppercase letters
• lowercase letters
• digits 0 to 9
• special characters:
`+`, `-`, `*`, `/`, `<`, `>`, `=`, `:`, `.`, `&`, `~`, and `_`
• the space character
An atom is one of:
1. a string of characters
• uppercase
• lowercase
• underscore
• must begin with lowercase letter
2. arbitrary sequence of characters in single quotes
• spaces are allowed
3. a string of special characters
• some already predefined: `:-`, `;`
We will mostly focus on the integers for use with lists.
It is possible to do floating-point calculations with Prolog.
(I might demonstrate some later in the semester)
A variable is:
• a sequence of uppercase, lowercase, digits, and underscore
• must begin with uppercase or underscore
The single underscore, `_`, is preset to be used as the
anonymous variable.
Anonymous is typically used when there is no need to refer
to a head parameter in the body of a rule.
Complex terms are built up:
• with a functor, which must be an atom
• arguments, which can each be any kind of term
For example, the complex term `playsAirGuitar(jody)`:
• has functor `playsAirGuitar`
• has parameter `jody`
The complex term `jealous(marcellus, W)`:
• has functor `jealous`
• two parameters
• `marcellus`
• and variable `W`
The definition is recursive, where we can nest complex
terms further:
• hide(X, father(father(father(butch))))
• the nesting of complex terms stops at base atom `butch`
Recursively structured terms allows concepts to be
represented naturally.
The number of parameters that a complex term contains is
called its arity:
• `woman(mia)` has arity 1
• `loves(vincent, mia)` has arity 2
Predicates with same name but different arity are different.
• so, Prolog will not try to match statements of different arity
A predicate has signature description with syntax:
• forward-slash suffix after the predicate’s name,
followed by the arity number
For example, with `kb4.pl`:
— Chapter 2 —
— Matching —
In knowledge base `kb4.pl` from Ch 1, the term matching
was introduced, which formally means:
Recall the types of terms:
1. Constants—can be atoms (e.g.: `vincent`) or numbers.
2. Variables.
3. Complex terms—these have the form:
`functor(term_1, term_2, … , term_n)`.
“Two terms match, if they are equal or if they contain
variables that can be instantiated in such a way that the
resulting terms are equal.” (pg. 17)
No Variables
There are simple examples, involving no variables, to
demonstrate matching:
• `mia` and `mia`
• `woman(mia)` and `woman(mia)`
• `42` and `42`
But `woman(mia)` and `woman(vincent)` do not match:
• because the nested constants `mia` and `vincent` do not match
With Variables
Are the terms `mia` and `X` matching?
• `X` can be instantiated with constant `mia`,
so they do satisfy the definition of matching
• by the same reasoning, `woman(mia)` and `woman(X)` match
What about `loves(vincent,X)` and `loves(X,mia)`?
• there are no constants we can instantiate
for `X` that make both terms match
• e.g.: `loves(vincent,vincent)` and `loves(vincent,mia)`
are not the same (instantiated `X` with `vincent`)
• e.g.: `loves(vincent,mia)` and `loves(mia,mia)`
are not the same (instantiated `X` with `mia`)
• therefore, these two terms do not match
Definition
Prolog instantiates variables between two terms
to make all possible matchings between them.
• matching is a fundamental part of Prolog
• we can build complex terms recursively
• there is a formal set of steps we can follow
to find out exactly what makes two terms equal
Definition
1. If two terms are constants, then they only match if they are the
same atom or number.
2. If `term1` is a variable, and `term2` is any type of term:
• `term1` is instantiated to `term2` (so `term1` and `term2` match)
• vice versa for swapped roles of `term1` and `term2`
• if both are variables, they are both instantiated to each other
(we say they share values)
3. If `term1` and `term2` are complex terms, then they match
if and only if:
a) They have the same functor and arity.
b) All their corresponding arguments match
c) and the variable instantiations are consistent.
(no change in value across the same variable between the terms)
4. Two terms match if and only if it follows from the previous three
descriptions that they match.
Definition
The fourth description accounts for when terms do not
• e.g.: `batman` and `daughter(ink)` do not match
• because none of the first three descriptions apply.
In an interactive `swipl` session, give the following a try:
=(mia,mia).
• Prolog should respond with `true.`
The above is an example of the `=/2` predicate in Prolog.
(`/2` means it takes two arguments)
=(vincent,mia).
• Prolog should respond with `false.`
It is more natural to use the infix notation for `=`.
Try the following:
mia = mia.
vincent = mia.
The above examples can be determined by description (1).
There is a slightly tricky detail when using single quotes:
‘mia’ = mia.
‘mia2’ = mia2.
Prolog does not respond `true.`, but outputs the value
assigned to the variable `X` that makes the statement true.
• in the above example, description (2) applied
A similar output happens when we check two variables:
• if `X` is ever instantiated, then `Y` will be also with the same values
(in the same knowledge base, or in a query conjunction)
We can combine two statements with an “AND” operation
using a comma:
X = mia, X = vincent.
• because the variable `X` cannot be both atoms `mia` and `vincent` at
the same time, the conjunction is false
Now try with “OR” operation:
X = mia; X = vincent.
• should get the first of the two atoms listed for `X` to be instantiated
• interactively iterate to the next value that satisfies by pressing `;`
• output then iterates to `X = vincent` instantiated
We can try more complex statements:
travel(drive(car),Y) = travel(X,ride(bicycle)).
• you should see the instantiations output:
Y = ride(bicycle),
X = drive(car).
• note the comma as an AND operation
• both variable values are simultaneously instantiated to satisfy the statement
• description (3) applies here: the functor name `travel`
and the number of arguments match
• sub-description (b) means we must now recurse to match arguments
• so, `X` and `drive(car)` match by description (2)
• `Y` and `ride(bicycle)` match by description (2)
Another example for you to step through the definition
clauses for matching:
?- travel(drive(car), ride(bicycle)) = travel(X,ride(Y)).
X = drive(car),
Y = bicycle.
A last example:
?- loves(X,X) = loves(marcellus,mia).
• description (3) has the functor `loves` match with the same number
of arguments
• but, the argument instantiated `X = marcellus`
• is not consistent with `X = mia` at the same time
— The Occurs Check —
Some textbooks describe matching instead as unification.
• Prolog uses a shortcut to check if two terms match
• consider the query `father(X) = X`
• no instantiation for `X` will have the same nesting of `father`
if `X = father(father(butch))`
then `father(X) = father(father(father(butch))`
therefore, `X = father(father(father(butch))`
• old Prolog would desperately try to keep trying to match, but would
run out of memory continuing with instantiating further nesting
• swipl just reports the same `X = father(X)`, but some other
interactive Prolog shells may report infinite nesting with ellipses
So, modern implementations of Prolog are able to detect
cycles in terms without memory issues:
• standard unification algorithms are pessimistic
• occurs check: is it safe to look further at the two terms? (expensive)
• SWI-Prolog has some optimization:
https://swi-prolog.discourse.group/t/what-occurs-check-optimizations-is-swi-prolog-using/3461/14
Old Prolog:
• Prolog is optimistic by assuming you will not give dangerous queries
• it does not do an occurs check
• this makes it faster than the pessimistic version, but less safe
• it is unlikely you are going to make queries such as `father(X) = X`
https://swi-prolog.discourse.group/t/what-occurs-check-optimizations-is-swi-prolog-using/3461/14
— Programming with Matching —
Programming
Matching is a fundamental operation for Prolog to perform
proof search.
• we can write statements to help determine useful logical info
For example, consider the two-line knowledge base that
describes the concept of horizontal lines and vertical lines:
vertical( line( point(X,_), point(X,_) ))
horizontal( line( point(_,Y), point(_,Y) ))
(anonymous variables, unlike the textbook—and avoid singleton variable error)
Concept of
Rectilinear
vertical(line(point(X,_),point(X,_)))
horizontal(line(point(_,Y),point(_,Y)))
There are variables nested furthest in these terms, so they
are describing general rules.
• `point/2` functor describes Cartesian coordinates
• two variable arguments for the horizontal and vertical distances
• from some fixed point (typically, the origin)
• `line/2` functor takes two `point` terms as arguments for a line
• `vertical/1` term has one argument for a line
with both points having the same 𝑥𝑥-coordinate
• similarly, `hori
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com