COS 333: Chapter 16, Part 2
Summary
TLDRThis lecture delves into the foundations of Prolog, a logic programming language developed in the 1970s for applications in natural language processing and automated theorem proving. It covers the basic elements of Prolog, including terms, fact, rule, and goal statements, and discusses the inferencing process, highlighting its distinction from first-order predicate calculus. The lecture also touches on Prolog's development, its two main dialects, and provides insights into its programming constructs, illustrating how facts and rules are used to prove goals, and introducing the concepts of resolution, backtracking, and the tracing model for debugging.
Takeaways
- 📜 The lecture covers Prolog, its origins, basic elements, and inferencing process.
- 🏛️ Prolog was developed in the 1970s-1980s by the University of Aix-Marseille in France and the University of Edinburgh in Scotland.
- 🔍 Prolog is used for natural language processing and automated theorem proving.
- 🔧 Prolog programs are built from terms, which can be constants, variables, or structures.
- 📚 Fact statements in Prolog represent basic ground truths, using structures to express hypotheses.
- 📏 Rule statements express theorems and consist of an antecedent and a consequent.
- ❓ Goal statements, or queries, are used for theorem proving, asking Prolog to prove the truth of propositions.
- 🔄 Prolog uses top-down resolution (backward chaining) to match goals to facts.
- 🌐 Multiple sub-goals are proved using depth-first search, and Prolog handles backtracking if a sub-goal fails.
- 🔍 Prolog's tracing model helps debug programs, showing events like call, exit, redo, and fail.
Q & A
What are the main topics covered in the second lecture on logic programming languages?
-The second lecture primarily focuses on Prolog, starting with its origins, moving on to basic elements like terms, facts, rules, and goals, and finally discussing how Prolog handles the inferencing process differently from theorem proving in first-order predicate calculus.
Which two universities were initially involved in the development of Prolog?
-The development of Prolog began as a collaboration between the University of Marseille in France and the University of Edinburgh in Scotland.
What were the main interests of the University of Marseille and Robert Kowalski in the development of Prolog?
-The University of Marseille aimed to use Prolog for natural language processing, while Robert Kowalski from the University of Edinburgh was interested in using it for automated theorem proving.
What are the three main kinds of terms in Prolog programming language?
-The three main kinds of terms in Prolog are constants (which can be atoms or integers), variables, and structures.
How are atoms named in Prolog and what are the conventions for naming them?
-Atoms in Prolog can be named using a string of letters, digits, and underscores beginning with a lowercase letter, or using any sequence of printable ASCII characters including spaces, as long as they are enclosed in single quotes. However, the first approach is standardized for better readability.
What is a variable in Prolog and how is it named?
-A variable in Prolog is a term that can be instantiated with a value during the resolution process. It is named as a string of letters, digits, and underscores but must always start with an uppercase letter.
What is a fact statement in Prolog and how is it represented?
-A fact statement in Prolog is an atomic proposition used to express a hypothesis or a basic ground truth. It is represented using Prolog structures as headless Horn clauses, starting with a functor followed by a pair of parentheses containing parameters.
What is the syntactic form of rule statements in Prolog and how do they differ from fact statements?
-Rule statements in Prolog are represented by headed Horn clauses, consisting of an antecedent (the 'if' part) and a consequent (the 'then' part), separated by a colon and dash, indicating an implication. They differ from fact statements in that they include a rule for deriving new facts from existing ones.
How does Prolog handle the inferencing process when attempting to prove the truth of a proposition?
-Prolog uses top-down resolution or backward chaining for its inferencing process. It starts with the goal and attempts to find a sequence of matches using rules that lead to facts, which are then used to prove the goal.
What are the two general approaches for proving multiple sub-goals in Prolog and which one does Prolog use?
-The two general approaches for proving multiple sub-goals are breadth-first search and depth-first search. Prolog uses the depth-first search approach due to its lower computational load.
What is backtracking in Prolog and when does it occur?
-Backtracking in Prolog occurs when the inferencing process fails to prove one of the sub-goals after proving a previous sub-goal. It involves moving back to the last successfully proved sub-goal and finding a different solution that could potentially satisfy the failed sub-goal.
What is the purpose of the trace structure in Prolog and what are the four events it provides?
-The trace structure in Prolog is used for debugging Prolog programs by providing insight into the steps performed during the inferencing process. The four events it provides are call (beginning of an attempt to satisfy a goal), exit (goal has been satisfied), redo (backtracking occurs), and fail (goal fails).
Outlines
📚 Introduction to Prolog Programming Language
This segment introduces the second lecture on logic programming languages, specifically focusing on Prolog. It outlines the lecture's agenda, including the origins of Prolog, its development in the 1970s by the University of Marseille and the University of Edinburgh, and its applications in natural language processing and automated theorem proving. The lecture will cover basic elements of Prolog, such as terms, facts, rules, goals, and the inferencing process, contrasting it with theorem proving in first-order predicate calculus.
🔍 Understanding Prolog's Basic Elements: Terms and Statements
This paragraph delves into the fundamental components of Prolog programs, starting with terms which can be constants, variables, or structures. Constants include atoms and integers, with atoms being symbolic values. Variables are distinguishable by starting with an uppercase letter, and structures represent atomic propositions. The paragraph also explains Prolog's three types of statements: fact statements representing basic truths, rule statements expressing theorems, and goal statements used in theorem proving.
📜 The Syntax and Semantics of Prolog Statements
The third paragraph discusses the syntax of Prolog statements, emphasizing how fact statements are represented using functors and parameters. It also explains rule statements, which are akin to implications with an antecedent and a consequent, and how they are read. The paragraph highlights the importance of the structure of these statements in expressing relationships and properties within Prolog programs.
🔄 Prolog's Rule Statements and Generalization
This section further explores rule statements in Prolog, differentiating between specific and general rules. It illustrates how general rules use variables to relate to universal objects, whereas specific rules relate to particular objects. The paragraph also explains how Prolog handles logical 'or' statements by creating separate rules for each condition, showcasing examples of rules that define parent and grandparent relationships.
🎯 Prolog's Goal Statements and Query Mechanism
The focus shifts to goal statements, or queries, in Prolog, which are used to prove the truth of propositions. The paragraph explains how Prolog's inferencing engine works behind the scenes to prove goals and how users can interact with the Prolog interpreter in query mode. It also demonstrates how to structure queries with examples and discusses the use of variables and conjunctive propositions within goals.
🔄 Prolog's Inferencing Process and Resolution
This segment explains the inferencing process in Prolog, detailing how Prolog attempts to prove the truth of goals using facts and rules. It contrasts two general approaches to the matching process: bottom-up resolution (forward chaining) and top-down resolution (backward chaining). The paragraph highlights Prolog's use of top-down resolution to focus the search for relevant facts and rules to prove a goal.
🌐 Prolog's Inferencing with Multiple Sub-Goals
The sixth paragraph addresses how Prolog handles queries with multiple sub-goals, discussing breadth-first and depth-first search strategies. It emphasizes Prolog's use of depth-first search due to its lower computational load. The paragraph also introduces the concept of backtracking, which occurs when Prolog fails to prove a sub-goal and must revert to a previous sub-goal to find an alternative solution.
🔍 Prolog's Backtracking and Tracing Model
This section delves into the backtracking process in Prolog with an example, illustrating how Prolog attempts to prove sub-goals and reverts to previous steps when a sub-goal cannot be proven. It also explains the tracing model in Prolog, which is used for debugging and provides insight into the inferencing process through events like call, exit, redo, and fail.
📝 Example of Prolog's Tracing Model in Action
The eighth paragraph provides a practical example of the tracing model, showing how Prolog attempts to satisfy sub-goals using facts about likes and dislikes. It demonstrates the steps Prolog takes to match facts with sub-goals, the instantiation of variables, and the use of the trace structure to visualize the inferencing process, including the points at which Prolog exits, fails, and backtracks.
🚀 Conclusion and Preview of Upcoming Lectures
The final paragraph concludes the current lecture and previews the next one, where the remaining elements of Prolog programs will be discussed, including basic arithmetic and lists. It also mentions the exploration of Prolog's deficiencies and practical applications, setting the stage for a deeper understanding of the language's capabilities and limitations.
Mindmap
Keywords
💡Prolog
💡Inferencing Process
💡Fact Statement
💡Rule Statement
💡Goal Statement
💡Term
💡Variable
💡Backtracking
💡Resolution
💡Tracing Model
💡Bottom-Up Resolution
💡Top-Down Resolution
Highlights
Lecture focuses on Prolog, a logic programming language, discussing its origins and basic elements.
Prolog was initially developed for natural language processing and automated theorem proving.
The development of Prolog began in the 1970s with collaboration between universities in France and Scotland.
Prolog programs are constructed from terms, which can be constants, variables, or structures.
Constants in Prolog can be atoms or integers, with atoms being symbolic values used in reasoning.
Variables in Prolog are identified by starting with an uppercase letter, differing from atoms.
Structures in Prolog represent atomic propositions and are used to build statements within the language.
Three types of statements in Prolog are fact, rule, and goal statements, each serving a unique purpose.
Fact statements represent basic truths or axioms within a Prolog program.
Rule statements in Prolog are used to derive new facts from existing ones, expressed as headed horn clauses.
Goal statements, or queries, are used in theorem proving to determine the truth of a proposition.
Prolog uses top-down resolution or backward chaining for its inferencing process.
The inferencing process involves matching and resolution to prove the truth of goals.
Prolog's inferencing engine handles instantiations during the resolution process when queries are issued.
Backtracking is a key part of Prolog's search process when a sub-goal fails to be proven.
Prolog interpreters provide a tracing model for debugging, offering insight into the inferencing process.
The tracing model includes events like call, exit, redo, and fail to trace the inferencing steps.
The lecture concludes with an example illustrating the tracing model in Prolog.
Transcripts
this is the second of our three lectures
on logic programming languages and in
this lecture we'll be moving on
to prologue which will then finish
off in the third lecture
these are the topics that we'll be
discussing in today's lecture
we'll begin with a quick look at the
origins of prologue
and where the programming language was
developed then we'll move
on to some of the basic elements that
prolog
programs are built up out of so we'll
begin by looking at
terms then we'll look at fact rule and
goal statements and then finally we'll
look at how
prologue deals with the inferencing
process
we'll see that this is a little bit
different to the
theorem proving in first order predicate
calculus that we spoke about
in the previous lecture in the lecture
following this one
we will continue looking at prologue
and we'll then move on to some practical
examples
of programs that manipulate lists which
in
many ways are similar to the example
programs that we covered in the previous
chapter
when we were dealing with the scheme
programming language
the development of the prologue
programming language began
in the early 1970s and continued
into the 1980s all the way until the end
of that decade
so the initial development was a
collaboration between two universities
firstly the university of ex marseille
in france
and secondly the university of edinburgh
in scotland
so at the university of ex marseille the
intention
was to use this new programming language
for natural language processing
natural language processing is the
automated processing
of natural language as it would be
written
or spoken by a human being
so in other words this is a subfield
within the domain
of artificial intelligence at the
university of edinburgh the main
collaborator was robert kowalski
and he was interested in using prologue
for automated theorem proving
so both of these application areas are
still very active
areas of research and prologue can still
be used for these purposes however the
set of programming languages that are
applicable in these two domains has
widened somewhat since the 1970s
and 1980s eventually
the two teams working on the development
of the programming language went their
separate ways
and so development then continued
and two main dialects of prologue were
developed
so the most commonly used and most
widely available
dialect of prologue is the dialect that
was developed at the university of
edinburgh
and the syntax used in this dialect is
referred to as edinburgh
syntax we will be assuming for
the remainder of this lecture and the
next lecture
that we are using edinburgh syntax
we are now ready to move on to the
prologue programming language
itself however as was the case for our
discussion
on scheme in the previous chapter we
first need to define a number of
fundamental concepts
the first of these concepts is the
notion of a
term and a term is a basic building
block
of a prologue program so a term can be
either a constant
a variable or a structure and we'll look
at each of these three
term forms one by one so first of all we
have
constants and constants can be either
atoms or
integers now integers are fairly
straightforward they are represented as
you would expect
like a normal integer literal in a
programming
language such as c plus or java
so an example of an integer is the value
42 as you can see over there
atoms are the symbolic values
that prolog uses so here
we are talking about symbolic values
once again
as abstract concepts that the prologue
programming
language reasons about
to the prologue programming language an
atom doesn't have an intrinsic meaning
but
we as humans attach a meaning to each
atom so an atom then
can be named in two ways it can first of
all
be a string of letters digits and
underscores as long as this sequence
begins with a lower case later
we use this same convention when we were
discussing first order predicate
calculus
so an example of this kind of naming is
joe
as you can see over there and note that
the
j is a lowercase letter
alternatively we can use any sequence
of printable ascii characters including
spaces
as long as they are delimited by
apostrophes
so in other words single quotes over
here we have an example of this kind of
naming convention so here some atom
is then the name of an atom
as a whole now we won't be using the
second kind of notation
due to the fact that it makes prologue
programs
slightly less readable so we will be
standardizing on the
first approach to naming atoms in other
words
a single string of letters digits and
underscores
no spaces and beginning with a lowercase
letter the
second kind of term that exists in
prolog
is the variable so a variable
like an atom is a string of letters
digits and
underscores however very importantly a
variable name must always start with an
upper case later
an underscore incidentally is considered
to be an uppercase letter however in
general we won't start variable names
with
underscores now variables are the
only components of a prologue program
that can start with an uppercase later
so therefore it is very easy to
identify variables in prolog programs
over here we have two examples of
variables so here we have an x note that
it's an uppercase x and
we'll see that fairly often in the
coming examples
we will use a single letter to
name a variable if it is also possible
to give more descriptive names to
variables
so for example here we have my var and
as you can see it starts with an
uppercase
m indicating that it is a variable
now variables are associated with
instantiations
and we've discussed instantiations in
the previous lecture
in the context of first order predicate
calculus
so to refresh your memory and
instantiation is
a binding of a value to a variable
an instantiation only happens during the
resolution process
that prologue performs when you issue a
query to it
but we'll get to more detail on this
process a little bit
later then the third and final kind of
term that exists in prologue is
a structure and a structure represents
an
atomic proposition in other words the
simplest kind of proposition
that we can represent so over here
we have the syntax for a
structure representing an atomic
proposition
and we can see that it uses exactly the
same kind of notation
as we used when we were representing
atomic propositions
in first order predicate calculus
so we start off then with the functor
which is essentially the name
of the relation represented by the
atomic proposition
and the functa name starts with
a lowercase letter exactly
in the same way as we saw for symbolic
atoms
then following the functo we have a pair
of parentheses
and within the parentheses we have a
list of parameters
where the parameters are separated by
commas
the three kinds of terms namely
constants
variables and structures are used to
build up statements within
prolog there are three kinds of
statements
that exist in the prologue programming
language
fact statements rule statements and
finally
goals we'll be looking at each of these
three types of statements in more detail
in the next few slides
the first and simplest kind of statement
that can appear in a prologue program
is a fact statement fact statements
are atomic propositions and they are
used to express
hypotheses so in other words fact
statements
are basic ground truths or axioms
that are assumed to be true within a
prologue
program prolog structures are used to
represent
fact statements so this means that these
statements are headless horn clauses
so over here we have four examples of
fact statements within
prologue and note that they all end with
a full stop they also start with a
functor so in the first example the
functi
is female in the second example the
functi is again
female in the third example the function
is male
and in the final example the functor is
father
note that the functors all start with
lowercase letters
so once again i'll reiterate that the
only things that can start with
uppercase letters in prolog
are variables then following each
functor we have a pair of parentheses
and within the parentheses we have
parameters
so in the first example there's only one
parameter namely shelly
in the second example again only one
parameter which is
ana and in the third example one
parameter
called bill and then in the final
example we have two parameters
bill and jake and note that they are
separated
using a comma now all of these
parameters start with lower case letters
so this means that they
are atoms once again i'll
reiterate that these atoms are simply
abstract objects as far as prologue is
concerned
however we as humans can attach some
kind of
meaning to them so in other words we can
specify
that shelly refers to a specific
person also
note that the functors do not have any
intrinsic meaning associated with them
they are simply abstract representations
of properties
or relationships between objects
we as humans once again can attach a
specific meaning to them
so for example in the first case we
could interpret this fact statement as
specifying that shelly is female
the second fact statement might be
interpreted as
anna is female in the third case we may
interpret this fact
as bill is male and in the final case
we could interpret the fact as stating
either that bull is the father of jake
or that jake is the father of bill
notice also that the fanta doesn't have
to appear only once
so over here we have two facts where the
functi
is female these represent then two
separate facts where the property
or properties described for the
parameter
hold for two separate objects
so in other words in this particular
example
we have two females namely shelly
and anna
the second kind of statement that can
exist
in a prologue program is the rule
statement
rule statements are used to express
theorems
so this means that these rules can be
used to derive
new facts given existing facts that
prologue already knows about within
a program they are represented by means
of headed horn clauses
and their syntactic form within prologue
is therefore quite similar to the horn
clauses that we discussed in the
previous lecture
these rules therefore consist of two
parts
a right side and a left side the right
side
is the antecedent in other words the if
part
of the rule and this may be either a
single term or a conjunction of terms
where a conjunction of terms is a set of
terms linked by
logical and operators
now the form that a conjunction takes in
prologue
is a list of several terms
which are separated from one another by
means of commas
there are no explicit logical and
operators
so in other words the commas serve
as implied and operators between the
terms
then the left side of a rule statement
is the consequence
in other words the then part of the rule
and this must be a single term so in
other words conjunctions
or disjunctions are not allowed on the
left side
of a rule
here we have some examples of rule
statements
as they might appear in a prologue
program
our first example over here is a
specific rule and this is because it
uses only atoms
and no variables what this means is that
the rule relates to specific
objects rather than objects in general
notice also that rule statements always
end with a full stop
in exactly the same way as fact
statements
do so we have two parts to this rule
on the right hand side we have the
antecedent and in this case the
antecedent is
a single term in other words not a
conjunction of terms
on the left hand side we have the
consequent and of course the consequent
must be a single term then between the
antecedent and the consequent we've got
this colon dash
and this represents an implication
the colon and the dash are together
meant to resemble an
arrow that points from the right hand
side to the left
so in other words pointing from the
antecedent
to the consequent so how would we read
this rule
well the usual way to read such a rule
is to start on the right hand side with
the antecedent
and move to the left hand side in other
words
the consequent so we would read this
rule
as if mary is the mother of shelly
then it implies that mary must also be
the ancestor of shelly
now often times i will read rules in the
opposite direction starting on the left
hand side and moving to the right hand
side
this is not a different expression of
the meaning of the rule it's simply a
restatement
of the previous way that i described
this rule
so instead of reading this rule as if
mary is the mother of shelly
then it implies that mary must also be
the ancestor of shelly
i can read it as mary
is the ancestor of shelley if
mary is the mother of shelly
so notice that with this
rephrasing of the rules meaning i am not
implying that the implication is
bidirectional
so i am saying that mary is the ancestor
of shelly
if mary is the mother of shelley rather
than
saying if mary is the ancestor of shelly
then mary must be the mother of shelly
so in general specific rules are
not as useful as general rules and this
is because as i mentioned before
specific rules relate to specific
objects usually we are trying to express
a rule that relates to all objects
and therefore we would use general rules
as these last four examples
illustrate so these general rules then
use variables and this means that they
relate to universal objects rather than
specific objects so our first
two rules over here describe the parent
relation now what we are trying to
express here
is that x is the parent of y
if either x is the mother of y
or x is the father of y
but of course as we've previously seen
prologue rules
cannot include disjunctions in other
words they can't
include logical or statements
so we address this then by creating
two rules that describe the parent
relation
so the first rule then states that x
is the parent of y if x
is the mother of y and the second rule
states that
x is the parent of y if x
is the father of y so
whenever you are attempting to express a
rule that contains
a logical or you must then
write this as separate rules
that relate to the same relation in this
example
it was the parent relation
the next example describes a grandparent
relation over here
and here you can see that the antecedent
contains
two terms that are connected by a
single comma so the comma then
represents a logical and
now what this example also illustrates
is
that we can use a variable in the
antecedent that doesn't appear in the
consequent
so you can see that the consequent uses
the variables x
and z and x and z
are also used in the antecedent however
the antecedent
also uses the variable y so
what are we trying to express here then
well we are
saying that x is the grandparent of z
if x is the parent of a y
and this y is also the parent
of z so in other words we are stating
that there
is an object that lies between x and y
where x is the parent of that object and
that object
is the parent of zed
our final example over here is a
slightly more
complex rule and this rule describes
the sibling relation so here we are
stating
that x is the sibling of y
if there exists an m such that
m is the mother of x and m is also the
mother of y
and then also an if exists
where if is the father of x
and f is also the father of
y so in other words what we are
specifying here is that x and y
are siblings if they share a mother in
common
and they also share a father in common
the third and final kind of statement
supported in
prologue is the goal statement
goal statements are often simply
referred to as goals or sometimes
queries
and they are used in theorem proving
so a theorem then is a proposition that
we present
to prologue and the prologue interpreter
is then responsible for attempting to
prove
the truth of this proposition
now the proof is handled behind the
scenes by the
interpreters inferencing engine and
therefore
the programmer themselves will not
actually
implement the proof now in general
a prologue interpreter will allow a
programmer to
provide facts and rules either in the
form
of a source code file or in an
interactive mode
similar to the interactive modes that
are usually provided by scheme
interpreters either way the prolog
interpreter will allow the programmer to
enter a second mode
which is referred to as the query mode
and in this mode they can then type in
goals or queries which the prolog
interpreter
then needs to answer
so a simple goal uses exactly the same
syntax
as a fact statement in other words these
are headless horn clauses
over here we have an example of such a
headless horn clause note that it ends
with a full stop and you will also
notice
that a question mark and a dash
symbol precede the query
so the question mark and dash symbols
are not
part of the query i simply use them
to clearly indicate when a query is
being presented
rather than a fact statement
so the reason that i use a question mark
and a dash symbol to indicate
that a query is being issued is that
this is
a fairly common prompt that is used by a
lot of prologue
interpreters when the interpreter is in
query mode so what
are we then asking the prolog
interpreter to do
when we issue a query such
as this well we're essentially asking
the prologue interpreter whether it can
prove
that fred is a man
the interpreter will then attempt to
answer
this question by considering the
facts and the rules that have been
provided by the programmer
if the prologue interpreter can answer
this
query and determine that it is true
then it will respond with a yes or
a true result if the prolog interpreter
can't prove the truth of this query then
it will respond with
a no or a false
now we can also use conjunctive
propositions
and variables within our propositions
within our goals so over here i have two
examples of these cases
here we have a simple goal so again it's
a single headless horn clause
but we can see that it includes a
variable
x over here so what we are
asking the prologue interpreter in this
case
is can you find a value for x
such that x is the father
of mike what will then happen
is prologue will attempt to find an
instantiation
for the variable x that will make this
query true so if prolog
can find an instantiation for x that
makes the query true it will then
respond with
yes or true and then it will also
indicate
what the value for x should be
if prolog cannot find an instantiation
for x
that makes this query true then it will
respond with
a no now it is also possible
to re-query within prolog
so what will happen then in that case is
we will enter our
initial query and then we will get a
response from prolog
we can then issue a re-query and there
are a variety of different syntactic
mechanisms that we can use
to do this but what we are then asking
prolog to do
is to find another instantiation of x
which is different to the first
instantiation
and also makes the query true
we can continue re-quering until
eventually prolog cannot find
a new instantiation for x that makes the
query true
and then in that case prolog will
respond with no
or false now in the final example over
here
we have a query that consists
of two simple goals and these
are referred to as sub goals
so here we have one sub goal and here we
have the second sub goal
and note that there is x a comma between
the two
which indicates implicitly a logical
and operation so what we are asking the
prolog interpreter to do
here is to find an instantiation for x
such that x is the father of mike
and x is also male once again if
prologue can
find such an instantiation that makes
both of these
sub-goals true then it will respond with
yes or true
and then provide the value for the
instantiation of
x if it cannot find such an
instantiation then it will respond with
no
or false and once again we can then
re-query prologue repeatedly to find
different instantiations for the
variable x
that make the sub-goals both true
and we can continue doing this until
eventually prologue can't find
a suitable instantiation at which point
it will then respond with
a no or a false
we've now discussed most of the basic
components
of a prologue program there are only
two topics that we still need to discuss
firstly prologues support for basic
arithmetic
and secondly lists in prologue we'll get
to these two topics
in the next lecture but for now we will
focus
our attention on the inferencing process
that is performed
by prologue so we've just seen that the
inferencing process
requires a prologue interpreter to
attempt to prove the truth
of either a goal or a set
of sub-goals now in order to do this
the prologue interpreter by means of its
inferencing engine
needs to find a chain that involves
facts and rules now this
chain then needs to link our goal which
will represent
as q to a fact
a and this fact a needs to be found
such that we have a series of links
from the fact to the goal q
so our fact a then needs to imply
another fact b fact b then
needs to imply fact c and so on
until eventually we arrive at fact p
which implies fact q which
is then the goal that we are trying to
prove
now this process then is referred to
as matching satisfying or
resolution now there are two
general approaches that we can use to
perform this
matching process that we've just
described
the first is called bottom up resolution
sometimes also referred to as forward
chaining
here we begin with facts that have been
specified by the programmer
and then we use rules in order to
attempt to find a sequence of matches
that will eventually lead to the goal we
are trying to prove
now this approach works well with a
large set of possibly
appropriate facts all of which will lead
to the goal this is because there's a
high
likelihood that we will select a fact
that will lead to the goal
and therefore our search will be fairly
focused the second approach
is called top down resolution or
backward chaining
and this approach is the opposite of
forward chaining so here we begin with
the goal that we
are trying to prove and then we attempt
to find
a sequence of matches using rules
that eventually lead to facts
now this approach works well if we have
a small set
of possibly appropriate facts that will
lead to the goal we are trying to prove
the reason for this is that forward
training
will be much more likely to select
a fact that will not lead to
the goal so therefore if we use backward
training and start with the goal
then our search will be more focused
towards finding one of the few
appropriate facts prologue uses
top-down resolution or backward chaining
in order to perform its matching process
so let's look at these two approaches
by means of a simple example over here
here we have
a single facts which we've specified and
this fact states that
bob is a father then we have
a rule and this rule states that if x
is a father then it implies that x must
also be
a man now we issue a
query to our system and this query
is asking whether bob is a man
now with bottom up resolution or forward
chaining
we begin with the facts
that have been specified by the
programmers so we start off then
with the fact that bob is a
father we then find that we have
a rule that involves the
relation father and we can then
substitute bob in for the variable
x in this case so this is then
an instantiation that we have performed
note that it is the inferencing process
that performs this
instantiation so now because we've
instantiated
x to bob we then know by means of the
implication
that bob must also be a
man this is the consequent of
this rule so this then is
the goal that we are trying to prove we
have found
now a path that leads from a fact
to our goal and therefore
the logic system would conclude
that this goal has been proven to be
true
now with top down resolution or backward
training which is what prologue uses
we begin with the goals in other words
we begin with the goal
that we are attempting to prove that bob
is
a man so then we look through
our facts and rules and we find
this rule which includes then the
relation man
which was used in our query
so we can then substitute bob for
the variable x in this case again that
is an instantiation and then
we arrive at the antecedent that
bob is a father we then
again search through our facts and rules
and we find this fact over here which
states that
bob is a father and this matches with
the
antecedent that we've just instantiated
so now we've found a path that leads
from our goal
to a fact that has been specified
next we need to consider how multiple
sub goals are dealt with
by the inferencing process so if we have
multiple sub goals
there are two general approaches that we
can use
to prove each of these sub goals
the first is a breadth first search and
here we work
on all of the sub goals in parallel
the second approach is a depth first
search
and here we start with the first
sub-goal and find
a complete proof for it we then move on
to the second sub-goal
and find a complete proof for that
sub-goal
and then the third sub-goal and so on
until
eventually we've proved all of the
sub-goals
so a depth-first search can generally be
performed with fewer computational
resources because we are focusing
on each proof individually where each
proof
involves finding a chain of matches
because of this lower computational load
involved with depth first search
prologue
uses this approach
now if we have multiple sub-goals to
prove
backtracking potentially comes into play
so backtracking occurs
when we have several sub-goals and we
are proving these sub-goals one by one
but we then fail to prove one of the
sub-goals
in this case we then need to backtrack
and this means
we have to then move back to the
previous
sub-goal that was proved just prior
to the sub-goal that failed we then need
to find
a different solution for this previous
sub-goal that potentially then could
lead
to us being able to prove the sub-goal
that failed when we
backtracked to a previous sub goal we
begin the search
for a different solution where the
previous
search left off now this backtracking
process can potentially lead to a lot of
wasted time
as well as wasted memory space and the
reason
for this is that we may have to keep
backtracking
until eventually we have found all of
the possible proofs
for every sub-goal so let's illustrate
this backtracking process
by means of this example query
and here we are assuming that we have a
prologue program
that specifies a number of facts
and some of these facts then are
specified by means
of the male relation and they specify
that particular atoms are male
we also have a number of facts
that are specified by means of the
parent relation
and the parent relation specifies that
one atom
is the parent of another atom
so what are we asking the prologue
interpreter to do
with this query well we're asking
the prologue interpreter to find an atom
which instantiates the variable x such
that that atom
is male and that atom is also
the parent of shelly
so how does prologue then go about
attempting to prove these two sub-goals
now what's important to understand here
is that prologue
always proves sub-goals from left
to right prologue also matches
from the top of the program to the
bottom
when it is considering facts
so what will happen then is prologue
will begin
with the first sub-goal and it will then
attempt to find the first
rule that specifies a
male relation for a particular atom
that atom will then be used to
instantiate
the variable x and then prologue will
move on to the next
sub-goal with this sub-goal it will then
use the instantiation of
x and it will then attempt to
find a fact that specifies that
the atom that x has been instantiated to
is the parent of shelly
now if this atom is not the parent of
shelly
then we've failed to prove the second
sub-goal
so we now need to backtrack to the first
sub-goal this then means that we
continue the search where we left off
so we don't reconsider the first rule
that is specified by means of the
male relation we therefore find the
second that specifies
that a particular atom is male
this then leads to another instantiation
of x with a different atom to the first
instantiation
and then we again move on to the second
sub goal
and now we need to prove that this
atom that has been instantiated
for x is again the parent
of shelly so we then continue this
backtracking process
until eventually we found an
instantiation for x
that satisfies both of the sub-goals
now let's consider a situation where
there is no male that is
a parent of shelly in this case what
will happen is we will continuously
backtrack until we have eventually
considered
every fact that specifies that a
particular atom
is male in that case we've then
exhausted all of the possible
instantiations for
x and we haven't managed to prove
both of the sub-goals in this case then
both sub-goals fail
and prologue will then respond with a no
or a false indicating that it could not
prove the goal
now prologue interpreters typically also
provide a tracing model and this
is provided by means of a built-in trace
structure the trace structure
is used when we are attempting to
debug our prologue programs and this
gives
us insight into the various steps that
are performed
during the inferencing process so the
tracing model
then has four events that
can occur the first is a call
and this indicates the beginning of an
attempt to satisfy
a goal the next event is an
exit and this occurs when a goal has
been satisfied
then we have a redo event and this
happens
when backtracking occurs and finally
we have a fail event which occurs
when a goal fails
let's finish this lecture by looking at
a simple example that illustrates how
the tracing model in prolog
works over here we have a simple
prologue program that consists
only of four fact statements
and the fact statements all use the
likes relation which specifies that one
atom likes another so the first
fact statement specifies that jake likes
chocolate the second fact statement
indicates that jake also likes apricots
the third fact statement tells us that
darcy
likes licorice and the final fact
statement specifies that darcy also
likes
apricots so now we enter query mode
and we begin then by using
the trace structure as you can see over
here
note that the trace ends with a full
stop and this
instructs the prologue interpreter
to print out each step that is performed
during the inferencing process
now we need to provide a query
to the interpreter and that's exactly
what we do
over here and note that this query
consists of two sub
goals here and here
and the two sub goals are separated by a
comma
also notice that the sub goals
use a variable named x
so what are we asking the prolog
interpreter
to do at this point well we want the
interpreter to find an
instantiation for x and
that instantiation should then result
in both of the sub-goals
being true now we are less interested
in the final result of this query and
more interested
in the steps that are performed to get
there
so once again recall that prologue
attempts to satisfy sub goals
from left to right so we begin with this
leftmost sub goal
and then move to the right one
so first what we need to do is find
an instantiation for x so that
the first sub goal is true
so that's exactly what we do with this
call over here
and at this point the variable x has not
been instantiated so that's what's
represented here by this underscore 0
which indicates that we do not have
a value instantiated for this variable
yet now recall again
that when prologue is
matching it moves from the top of
the program to the bottom so what will
happen
is we will look for a fact that
matches this first sub goal and we will
start
at the top and find the first matching
fact statement
so that first matching fact statement is
in fact
the first fact over here specified in
our program
that states that jake likes chocolate
so that then results in the variable
x being instantiated to
the atom chocolate and that's then
exactly what happens
in this exit that occurs at this point
so here we now indicate that we have
matched against the
fact that states that jake likes
chocolate
and therefore chocolate has been used to
instantiate
the variable x so
now we've satisfied the first sub goal
so we can then move on to the second
sub goal so we now have another call but
at this point
this variable x has been instantiated
with the atom chocolate so
we are then performing a call
for the statement that darcy likes
chocolate now again we need to then
perform our matching process from top to
bottom so we are looking
for a fact statement that specifies that
darcy
likes chocolate and of course you can
see that
none of the facts specify this so this
means
we then have a fail and this fail
then is for the
fact that darcy likes chocolate
so this means we have now failed to
prove our
second sub goal at this point so we now
need to backtrack
to the first sub goal and find another
instantiation
for the variable x so this is then
indicated by
the redo over here and now
we have an uninstantiated variable x
which is indicated by this underscore 0
at this point so now we continue the
search
where we left off so we left the search
at this point where we matched the
first fact for the first
sub-goal so now we continue our search
down
and we then find the second
fact over here that states that jake
likes apricots so
we then have an exit and this exit then
indicates
that the variable has been instantiated
with the atom apricots
so now we have once again satisfied the
first sub-goal and we need to move on to
the second sub goal over here
so we have now instantiated the
variable x with the value apricots
which then means that we have a call
for the statement that
darcy likes apricots
we then begin the search once again at
the top of our program matching the
facts one by one and we see that we then
can match the statement that dorsey
likes apricots by means of the
lost fact over here so now we've found a
match
this then results in an exit which means
that we have now satisfied
the second sub-goal so now we've
satisfied both
sub-goals which means that the
inferencing process can now
terminate and it will respond then with
a
yes or a true and then indicate
that the instantiation for x is
apricots which then satisfies both
of the two sub-goals
now we could then at this point issue
a re-query again and this then tells
prologue
to attempt to find another value for
x that will make both sub goals
true so then again we will begin
with our first sub goal over here
and we will try to then find another
instantiation
for x that will make this first sub-goal
true
but at this point we have now considered
all of the
facts that involve jake liking
something else so we then cannot find
another matching fact meaning we can't
then
locate another valid instantiation for
the variable x at this point
so at this stage prologue will then fail
and respond with a no
or a false indicating that it can't find
another instantiation for the x
variable all right so that concludes
this
lecture in the next lecture we will
continue
looking at the last two remaining
elements
of prologue programs and we will then
look at some example prologue programs
that reason about lists we will also
look
at some deficiencies associated with the
prologue
programming language and then finally we
will look at some practical applications
of prologue
5.0 / 5 (0 votes)