COS 333: Chapter 16, Part 2

Summary

This 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

00:00

📚 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.

05:01

🔍 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.

10:02

📜 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.

15:06

🔄 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.

20:07

🎯 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.

25:08

🔄 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.

30:10

🌐 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.

35:12

🔍 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.

40:14

📝 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.

45:16

🚀 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.

Keywords

💡Prolog

Prolog is a logic programming language primarily associated with artificial intelligence. It is known for its ability to handle complex queries and symbolic processing. In the video, Prolog is the central theme, with its origins, syntax, and inferencing process being discussed extensively. For example, the script mentions the development of Prolog at the University of Ex Marseille and the University of Edinburgh, highlighting its applications in natural language processing and automated theorem proving.

💡Inferencing Process

The inferencing process in Prolog is the mechanism by which the language deduces new facts from existing ones. It is central to how Prolog operates, using a top-down resolution or backward chaining approach. The script explains this process in detail, contrasting it with the theorem proving in first-order predicate calculus and illustrating it with examples such as determining if 'bob' is a 'man' based on the given facts and rules.

💡Fact Statement

A fact statement in Prolog represents a basic truth or axiom within the program. It is a type of statement that uses Prolog structures to express hypotheses. The script provides several examples of fact statements, such as 'female(shelly).' or 'father(bill, jake).', which serve as the foundational knowledge for the inferencing process.

💡Rule Statement

Rule statements in Prolog are used to express theorems and derive new facts from existing ones. They are represented by headed horn clauses and consist of an antecedent (the 'if' part) and a consequent (the 'then' part). The script discusses how these rules are used to express relationships, such as 'parent(x, y)' being defined by 'mother(x, y)' or 'father(x, y)'.

💡Goal Statement

A goal statement, often referred to as a query in Prolog, is used in theorem proving. It is a proposition presented to Prolog, which the interpreter then attempts to prove true. The script explains how goal statements are used in query mode, such as asking Prolog to prove that 'fred' is 'male', and how the interpreter responds based on the facts and rules provided.

💡Term

In Prolog, a term is a basic building block of a program and can be a constant, a variable, or a structure. The script defines terms and provides examples, such as constants being atoms or integers, variables starting with an uppercase letter, and structures representing atomic propositions like 'father(X, Y)'.

💡Variable

Variables in Prolog are used to represent unknown values and are a key component in the language's ability to perform general reasoning. They always start with an uppercase letter, distinguishing them from atoms and constants. The script illustrates variables with examples like 'X' and 'my_var', and discusses their role in instantiation during the resolution process.

💡Backtracking

Backtracking is a fundamental concept in Prolog related to the search for solutions when proving goals. If a sub-goal fails to be proven, Prolog backtracks to find alternative solutions. The script provides an example of backtracking in the context of finding an instantiation for 'x' that satisfies multiple sub-goals, such as finding a male who is also the parent of 'shelly'.

💡Resolution

Resolution is the process of proving goals in Prolog by finding a chain of facts and rules that link a goal to a known fact. The script describes how Prolog uses top-down resolution or backward chaining to perform this process, starting with the goal and working backward to find matching facts and rules.

💡Tracing Model

The tracing model in Prolog is a debugging tool that provides insight into the steps performed during the inferencing process. The script mentions the trace structure and its use in understanding the various events like 'call', 'exit', 'redo', and 'fail' that occur as Prolog attempts to satisfy goals.

💡Bottom-Up Resolution

Bottom-up resolution, also known as forward chaining, is one of the two general approaches to the matching process in Prolog. It starts with the facts and uses rules to find matches leading to the goal. The script contrasts this approach with top-down resolution, explaining that bottom-up resolution works well with a large set of facts that could potentially lead to the goal.

💡Top-Down Resolution

Top-down resolution, or backward chaining, is the approach Prolog uses for its inferencing process. It starts with the goal and works backward to find a sequence of matches using rules that lead to facts. The script explains that this approach is more focused and efficient when there are fewer facts that could lead to the goal.

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