COS 333: Chapter 16, Part 3

Summary

This lecture delves into logic programming languages, focusing on Prolog's basic elements, including arithmetic operations and list structures. It explores examples of list manipulation and discusses Prolog's limitations, such as resolution order control and the closed world assumption. The session also touches on practical applications of logic programming in databases, expert systems, and natural language processing, providing insights into the real-world uses of these languages.

Takeaways

• 📚 The lecture discusses Prolog, a logic programming language, and its basic elements, list structures, and real-world applications.
• 🔢 Prolog supports integer arithmetic operations using the 'is' operator, but avoids floating-point arithmetic due to potential issues in the resolution process.
• 🚗 The script provides an example of implementing a 'speed' and 'time' relation in Prolog and how to use these to calculate 'distance' with a query.
• 📝 Lists in Prolog are similar to those in Lisp and Scheme, allowing for nested structures and terminated by an empty list.
• 🔑 Prolog uses a recursive approach for list processing, requiring careful ordering of base and recursive cases for efficient execution.
• 🔄 The 'append' and 'reverse' propositions in Prolog are implemented recursively, demonstrating the language's capability for list manipulation.
• 🚫 Prolog has certain deficiencies, including issues with resolution order control, the closed world assumption, the negation problem, and intrinsic limitations in computations.
• ✂️ 'Cuts' in Prolog are used to control backtracking and can improve efficiency by preventing unnecessary search steps.
• 🔍 The 'not' operator in Prolog is used to handle logical negations, but it does not function as a true logical negation due to the closed world assumption.
• 🔑 Practical applications of logic programming include use in relational database management systems, expert systems, and natural language processing.
• 📈 The lecture concludes with a discussion on the practical uses of logic programming, highlighting its role in intelligent query systems and AI.

Q & A

What is the primary focus of the third lecture on logic programming languages?

The primary focus of the third lecture is to conclude the discussion on Prolog, covering topics such as basic elements of Prolog, simple arithmetic operations, list structures, general deficiencies of Prolog, and application areas of logic programming in the real world.

Why are floating point values and arithmetic not emphasized in Prolog?

Floating point values and arithmetic are not emphasized in Prolog because floating point values often do not represent exact fractional values, which can result in unexpected failures during the matching process performed by resolution.

How does Prolog support integer arithmetic?

Prolog supports integer arithmetic through the use of the 'is' operator, which has two operands and uses regular infix notation for arithmetic expressions, similar to languages like C++ or Java.

What is the significance of the 'is' operator in Prolog?

The 'is' operator in Prolog is used to instantiate a variable with the value of an arithmetic expression. It is important to note that the 'is' operator is not an assignment statement and has specific rules about variable instantiation on both its left and right operands.

Can you explain the concept of facts and rules in Prolog using the example of speed and time relations?

In Prolog, facts are used to define relations with parameters, such as the speed and time of vehicles. For example, facts like 'speed(ford, 100)' and 'time(ford, 20)' define the speed and time relations for a vehicle named 'ford'. Rules, on the other hand, can define more complex relations, like the distance traveled, using variables and other relations.

How does Prolog handle list structures?

Prolog handles list structures similarly to Lisp and Scheme, allowing for the creation of nested lists containing atoms, atomic propositions, and other terms. Lists are implicitly terminated by an empty list and can be manipulated using head and tail notation.

What is the general approach for implementing list processing in Prolog?

List processing in Prolog generally requires a recursive approach, working through lists one element at a time. This involves defining base cases and recursive cases as separate Prolog statements, with the base cases often being atomic propositions and the recursive cases being rules.

What is the purpose of the underscore character in Prolog?

The underscore character in Prolog represents an anonymous variable, indicating that the programmer does not care about the instantiation of that variable during the unification process. It is used to simplify Prolog implementations, particularly in list processing where certain values may not be relevant.

Can you provide an example of a Prolog proposition that performs list manipulation?

An example of a Prolog proposition that performs list manipulation is the 'member' proposition, which defines a relation between a term and a list. It checks if the term is contained within the list using a recursive strategy with a base case (when the term is the head of the list) and a recursive case (when the term is a member of the tail of the list).

What are some of the deficiencies associated with the Prolog programming language?

Some of the deficiencies associated with Prolog include resolution order control, the closed world assumption, the negation problem, and intrinsic limitations with certain kinds of computations that Prolog cannot perform efficiently.

How does Prolog handle the sorting of lists?

Prolog handles the sorting of lists by generating permutations of the original list and checking if each permutation is sorted. This process can be very inefficient as it may require generating every possible permutation of the list to find a sorted version.

What are some practical application areas for logic programming languages?

Logic programming languages have practical applications in relational database management systems for implementing intelligent query systems, in expert systems for decision making based on a set of rules, and in natural language processing within the domain of artificial intelligence.

Outlines

00:00

📚 Introduction to Prolog and Arithmetic Operations

The lecture delves into the intricacies of logic programming languages, specifically Prolog, by concluding the discussion on Prolog's basic elements. It commences with Prolog's support for simple arithmetic operations, emphasizing integer values and the use of the 'is' operator for expressions. The lecture also addresses the limitations of floating point values due to their potential to cause unexpected failures during the resolution process. The 'is' operator's role in variable instantiation and the distinction between Prolog's treatment of arithmetic and imperative programming languages like C++ or Java are highlighted.

05:01

🚗 Prolog's Data Structures: Relations and Rules

This segment introduces Prolog's list structures and their significance as the lecture's main focus. It presents example propositions akin to list manipulation programs previously discussed in Scheme. The script outlines the creation of relations and rules in Prolog, using the speed and time of vehicles as an example to illustrate how facts and rules interrelate to define complex relations such as distance traveled. The process of querying Prolog to determine instantiations for variables and the resolution process's role in searching for valid matches are explained.

10:02

🔗 List Processing in Prolog

The paragraph explores Prolog's list structures, drawing parallels with Lisp and Scheme, and emphasizing the recursive approach necessary for list processing. It explains the notation for accessing the head and tail of a list and discusses the importance of order in Prolog statements for recursive list processing. The paragraph also introduces the concept of anonymous variables represented by the underscore character for values that are not relevant to the outcome of a Prolog proposition.

15:02

🔄 Recursive List Processing Techniques in Prolog

This section delves deeper into the recursive strategies for list processing in Prolog, illustrating how to implement propositions that perform operations like membership checks and list construction. It explains the member proposition, which determines if a term is part of a list, and the append proposition, which concatenates two lists. The importance of the order of statements and the use of base and recursive cases in implementing these recursive strategies are highlighted.

20:05

🔄 Implementing List Manipulations: Member and Append

The script provides a detailed walkthrough of implementing the 'member' and 'append' propositions in Prolog. It explains how the member proposition checks for the presence of an element within a list using a base and recursive case approach. Similarly, the append proposition is implemented to join two lists, with the process involving recursive elimination of list elements and re-adding them in reverse order. The explanation includes example queries that demonstrate the use of these propositions in Prolog.

25:06

🔄 Advanced List Manipulations: Reverse Proposition

The paragraph discusses the implementation of the reverse proposition in Prolog, which reverses the order of elements in a list. It describes the recursive strategy employed, which involves reversing the tail of the list first and then appending the head of the original list to this reversed tail. The explanation includes the use of the append proposition in achieving the reverse operation and provides example queries that showcase the reverse proposition's utility.

30:07

🚫 Deficiencies in Prolog Programming

This segment identifies and discusses four main deficiencies associated with Prolog programming. These include resolution order control, which affects the efficiency and context independence of Prolog programs; the closed world assumption, which limits Prolog's ability to handle negative responses; the negation problem, which complicates the handling of logical negations; and intrinsic limitations of the resolution process, which make certain computations inefficient. The paragraph provides examples to illustrate these deficiencies and their impact on Prolog's practical use.

35:08

✂️ Resolution Order Control and Cut Operator

The paragraph examines the issue of resolution order control in Prolog and its potential to cause non-terminating recursions. It contrasts two different implementations of the ancestor proposition to demonstrate how the order of rules can affect program execution. The explanation also introduces the cut operator, which allows programmers to control backtracking and improve program efficiency. The use of cuts is illustrated with an example of the 'valid member' proposition, highlighting their role in avoiding unnecessary computational steps.

40:10

🔒 Closed World Assumption and Negation Problem

This section delves into the closed world assumption of Prolog, which states that Prolog can only prove things with provided facts and rules, leading to potential misinterpretations of negative responses. The negation problem is also discussed, illustrating how Prolog's handling of logical negations can result in incorrect outcomes, such as the siblings proposition example. The paragraph explains the limitations of Prolog's 'not' operator and the challenges in establishing true logical negations within the language.

45:11

🔑 Intrinsic Limitations and Practical Applications

The final paragraph addresses the intrinsic limitations of Prolog, such as the inefficient resolution process for tasks like sorting lists, which can require generating all possible permutations. It then shifts focus to practical applications of logic programming languages, including their use in relational database management systems for intelligent query processing, in expert systems for decision-making based on rules, and in natural language processing within artificial intelligence.

Keywords

💡Logic Programming Languages

Logic programming languages are a type of programming paradigm that is primarily based on formal logic. In the context of the video, Prolog (Programming in Logic) is discussed as an example of such a language, where programs are expressed as a set of facts and rules about some problem domain, and computation is performed by deriving new statements from the existing ones through logical inference.

💡Prolog

Prolog is a logic programming language that is central to the video's discussion. It is known for its ability to handle complex queries and symbolic processing. The script delves into the specifics of Prolog's operations, such as arithmetic operations, list structures, and its unique syntax involving variables and predicates.

💡Arithmetic Operations

Arithmetic operations refer to the basic mathematical functions such as addition, subtraction, multiplication, and division. In the video, it is mentioned that Prolog supports simple integer arithmetic operations using the 'is' operator, which is significant for performing calculations and setting values within the program.

💡List Structures

List structures in Prolog represent a fundamental data type, allowing for the organization of elements in a sequence. The script discusses how Prolog lists are similar to those in Lisp and Scheme, and how they can be manipulated using operations such as accessing the head and tail of a list, which are crucial for list processing tasks.

💡Resolution Process

The resolution process in Prolog is the mechanism by which the language deduces new facts from existing ones. It is a form of inference that is used to match goals with program clauses, instantiate variables, and derive solutions to queries. The video explains how this process can be affected by the order of clauses and the instantiation of variables.

💡Variables

Variables in Prolog are used to represent unknown values that can be instantiated during the resolution process. The script explains the distinction between instantiated and non-instantiated variables, particularly in the context of the 'is' operator, where variables on the left side must not be instantiated, and those on the right must be.

💡Instantiation

Instantiation in Prolog refers to the process of assigning a value to a variable. The video describes how variables become instantiated with integer values through arithmetic expressions using the 'is' operator, and how this process is crucial for the functioning of predicates and rules within the language.

💡Rules

Rules in Prolog are used to define relationships between different elements and are a key part of the language's logic. The script provides an example of a rule defining a 'distance' relation, which is derived from the 'speed' and 'time' relations, illustrating how rules can be used to express complex logic.

💡Recursion

Recursion in the context of the video refers to the process of a function calling itself in order to solve a problem by breaking it down into smaller instances of the same problem. The script discusses how recursion is essential for list processing in Prolog, where operations such as 'member', 'append', and 'reverse' are implemented recursively.

💡Deficiencies

The video outlines several deficiencies associated with Prolog, including issues with resolution order control, the closed world assumption, the negation problem, and intrinsic limitations of the resolution process. These deficiencies highlight the challenges and limitations of using Prolog for certain types of computations and practical applications.

💡Practical Applications

The script concludes by discussing practical applications of logic programming, such as in relational database management systems, expert systems, and natural language processing. These applications demonstrate the relevance and utility of logic programming languages like Prolog in various domains of computer science and artificial intelligence.

Highlights

Introduction to the third lecture on logic programming languages, focusing on concluding the discussion on Prolog.

Continuation of the discussion on basic elements of Prolog, starting with support for simple arithmetic operations.

Emphasis on list structures as the main focus of the lecture, with examples of list manipulation programs similar to those in Scheme.

Explanation of general deficiencies in Prolog programming language, affecting its practical usage.

Overview of application areas of logic programming in the real world, such as relational database management systems and expert systems.

Prolog's support for integer values and arithmetic operations, with a detailed explanation of the 'is' operator.

Discussion on the potential issues with floating point values in Prolog and the decision to focus on integer arithmetic.

Illustration of how integer arithmetic can be implemented in Prolog using facts and rules, with an example of a speed and time relation.

Introduction to list structures in Prolog, comparing them to lists in Lisp and Scheme, and explaining list notation and operations.

Explanation of the recursive approach needed for list processing in Prolog, with examples of base and recursive cases.

Discussion on the use of anonymous variables in Prolog to indicate irrelevant values during list processing.

Presentation of example Prolog propositions for list manipulations, including 'member', 'append', and 'reverse'.

Analysis of the deficiencies in Prolog, such as resolution order control and its impact on program efficiency.

Introduction and explanation of the closed world assumption in Prolog and its implications for query results.

Explanation of the negation problem in Prolog, demonstrating the difficulty in handling logical negations with examples.

Discussion on the intrinsic limitations of Prolog's resolution process, particularly in tasks like sorting lists.

Conclusion of the lecture with a summary of the practical applications of logic programming in various fields.

Transcripts

this is the third lecture on

logic programming languages in which

we'll conclude our discussion

on prologue

these are the topics that we'll be

covering in today's lecture

we'll continue with our discussion on

the basic elements of prologue

beginning with prologue support for

simple

arithmetic operations we'll then move on

to

list structures which will be the main

focus

of this lecture and we'll look at

a few example propositions which

are similar to the example list

manipulation programs

that we covered when we were looking at

scheme in the previous chapter

we'll then look at some general

deficiencies

of the prologue programming language and

then

finally finish off with a few

application areas

of logic programming in the real world

prolog allows variables to be

instantiated with

integer values and it also supports

simple integer arithmetic miniprolog

implementations

also support floating point values as

well as floating point arithmetic

however floating point values can

potentially cause a problem during the

resolution process

this is because floating point values

very often do not represent exact

fractional values

and therefore they can result in

unexpected

failures during the matching process

that is performed by

resolution as a result of this we won't

be focusing on floating point values

or floating point arithmetic any further

and we will instead only pay attention

to

integer values and integer arithmetic

so integer arithmetic then is supported

by means

of the is operator and the is operator

has

two operands a left operand and a

right operand the right operand of the

is operator

is an arithmetic expression and we

use regular infix notation

for these arithmetic expressions so in

other words the same kind of notation

that you would be used to from languages

like c

plus or java the left operand of the

is operator is a variable

so over here we have an example of an

expression that demonstrates the use

of the is operator we can see on the

left hand side we have a variable a

and on the right hand side we have an

arithmetic expression

which involves variables so we have the

variable

b and the value of that variable is

divided by

17 and then we add the value of the

variable

c to that result now it's important to

understand

that all variables on the right hand

side of the is operator must be

instantiated

and variables on the left hand side must

not be

instantiated then by means of the is

operator the variable on the left hand

side becomes instantiated

and it is instantiated with the value

of the expression on the right hand side

now these rules then mean

that the is operating prologue is

not an assignment statement so

in other words this kind of expression

here is

illegal and if we were to try to

implement this by means of

an assignment in a standard imperative

programming language like c

plus or java then this kind of

assignment would be valid however this

is always illegal in prologue

because of the sum variable so if we

assume then that the sum variable is

instantiated with

a value then the right

hand side is legal

however the left hand side is illegal

because the variable on the left hand

side must not be instantiated

conversely if the sum variable

has not been instantiated

then it means that the left hand side is

legal however the right hand side is

illegal

because all of the variables on the

right hand side must be

instantiated

this is a simple example that

illustrates how

integer arithmetic can be used in a

prologue implementation

so over here we have our implementation

and

this consists of eight facts

and a single rule if we look at

the first four facts we see that they

together define

the speed relation and the speed

relation

has two parameters the first parameter

is an atom that specifies a specific

vehicle so these vehicles in this

example then

are ford chevy

dodge and volvo notice that they all

start with a lower case letter

which indicates that they are all atoms

then the second parameter of the speed

relation

is an integer value and this represents

the speed

associated with a specific vehicle

so our first fact then would be read as

the speed of the forward

is 100 the second fact states that the

speed of the chevy

is 105 then we have the speed of the

dodge

is 95 and finally the speed of the volvo

is 80. our next four facts together

define

the time relation and the time relation

again

has two parameters the first of which

is an atom representing a specific

vehicle

and then the second parameter is an

integer value but this time representing

the time associated with a specific

vehicle

so the first time fact would then

be read as the time of the forward

is 20. next we have the time of

the chevy is 21 then the time of the

dodge

is 24 and finally the time of the volvo

is also 24. so now we can move on

to our rule and this rule

defines the distance relation which once

again

has two parameters the first parameter

represented by the variable x over here

is an atom that represents a specific

vehicle

and the second parameter y will be

an integer value that represents the

distance

traveled by a specific vehicle so

what are we specifying by means of this

rule

we are stating that y

is the distance traveled by a specific

vehicle

x if the speed of x

is defined by the variable

speed and the time of x

is defined by the variable time

notice that speed and time in both cases

here

are variables because they start with

uppercase letters

so then we finally have

the distance traveled by x which is

y as we see over here and y

then is defined as the variable speed

multiplied by the variable time

so now let's look at how this

distance rule would be used

we're assuming that we issue this

query to the prolog system in query mode

so we specify then the distance by means

of the relation

our first parameter is the atom chevy

and then we are specifying the second

parameter

as a variable x now it's important to

note that this variable

x in the query does not relate to

the x used in the rule over here

these are two independent variables

so what we are then essentially asking

prolog to do

by means of this query is determine an

instantiation for the variable x

such that that instantiation then

defines the distance

traveled by the chevy

so let's look then at the series of

instantiations that are performed

well first of all we look at our query

because recall that prolog works from

the query

to a fact or set of facts

that make the query true so

we see then that we reach our

rule with the consequent over here

and therefore we use the atom

chevy to instantiate the variable x

over here so then we move

on to the antecedent of our rule

and we start off then with this speed

relation over here

well we see that we've instantiated x

to the atom chevy in this case so x here

then gets instantiated

to chevy so this is then our first

proper instantiation so

now we have our variable speed at this

point so now prolog needs to determine

what a valid instantiation is for this

variable

so prolog then begins searching from the

top of the program down towards the

bottom

and it then finds this

fact over here that specifies that we

have the speed of the chevy

which is 105. so this then results

in the speed variable being instantiated

with a value of

105. so now we can move

on to the next relation within

our antecedent and now we are trying to

find the time

for x and again we've instantiated

x to chevy so again we start then

searching from the top

of the program and we find

the fact over here that specifies the

time of the chevy so

this then results in 21

being the instantiation for the variable

time

over here so time then gets instantiated

to

a value of 21. finally

we then have our last term over here

which then creates an instantiation for

the variable

y so we have instantiated then speed

and time as we've previously seen speed

has been instantiated

to 105 and time has been instantiated

to 21. so the result then of this

multiplication

is 105 multiplied by 21 which gives us a

result

of 2205

and that then is the value that is used

to instantiate

our variable y so

now prolog has found an instantiation

for y in this case which is the second

parameter of

our distance relation which means that

it's found in instance

instantiation for the variable x

in our query and so at this point prolog

will then respond with

a yes or a true indicating that it has

found a valid instantiation that makes

the query true and then it will also

indicate that that instantiation is

for the variable x and the value then

is 2205

for that instantiation

we'll now turn our attention to list

structures

in prolog so lists represent

the second basic type of data structure

that prolog supports

the first basic data structure being

atomic propositions

that are used to represent relations

we've previously discussed atomic

propositions in quite a lot of detail

so lists in prologue are very similar

to the lists supported in the lisp and

scheme functional programming languages

that we discussed

in the previous chapter lists

consist of a number of elements

and are implicitly terminated by

an empty list the elements contained in

a list can be a mixture of atoms

atomic propositions and other terms

including

other lists so this means we can create

arbitrarily nested list structures

so over here we have an example of list

notation

in prolog and this is a simple list

that contains three atoms notice

that the list is delimited by means of

square brackets

and the list elements are separated by

commas

the three elements are apple

prune and grape and note that all three

of these start with a lowercase letter

which indicates that they are atoms

here we have an example of a more

complex list

this list contains two elements the

first element

is a nested list containing two atoms a

and b and the second element

is an atomic proposition describing the

sun relation

and the two parameters for this atomic

proposition

are the variable x and the atom bob

empty lists are represented in a fairly

intuitive fashion which we see

over here they are simply the delimiting

square brackets

with nothing placed between them

now we very often during list processing

want to be able to access the

head of a list in other words the first

element of a list

and then the tail of the list which

would be the remaining elements

in the list excluding the head

now in scheme we saw that we used

functions

to access the head or the tail of a list

in prologue we use this notation

over here so again we delimit

the list with square brackets but then

we use

a pipe symbol and to the left of the

pipe symbol

we have the head of the list which in

this case is represented by

a variable called x and to the right of

the pipe

we have the tail of the list which here

is represented by the variable

y now this kind of notation is used

both to disassemble lists and to

construct lists so when we disassemble

lists

we typically remove elements from the

list one by one

repeatedly removing the head from a list

until

eventually we have an empty list

as the tail constructing lists

conversely involves adding elements to a

list one

item at a time and to the head

of the list so what we saw then

in scheme was that we had list

construction

functions such as cons this is then

not the case in prologue

i'd like to take a moment now to discuss

the general philosophy

and approach that must be used when

implementing prologue propositions

that have to perform list processing

so in general list processing in

prologue must use a recursive approach

in order to work through lists one

element

at a time this recursive strategy

is similar to the recursive approach

used when implementing list processing

functions

in a functional programming language

such

as scheme in our discussion on the

previous chapter we looked at

a few examples of these kinds of

functions

in the scheme programming language now

it's important

to understand that prologue propositions

do not

return results instead results are

defined

using parameters now the

base cases and recursive cases are

implemented as separate prologue

statements

the base cases are often atomic

propositions

that use variables and the recursive

cases

are rules that also use variables

now it's important also to understand

that the order

of these statements is important

and this is because prologue's matching

process works

from the top of a program to the bottom

when matching against facts and rules

during the resolution process

so this then means that base case

statements must appear

first and recursive case statements must

appear after the base case

statements now recall from

the first lecture on this chapter

that prologue and logic programming

languages

in general aim to be context independent

so this means that each statement should

not depend

on previous statements that appear

before it within

a program now because the order of

statements is

important when defining recursive list

processing propositions in prolog

this then unfortunately means that

prologue isn't

entirely context independent

now sometimes in a prologue statement

a value might not be relevant

this happens fairly often in list

processing propositions

but we also see it in other contexts

within prologue programs

so an example of a situation where a

value might not be relevant during list

processing

might be where we have to ignore the

head of a list

in this case we can then use an

underscore character

to replace the variable representing the

head of the list

this underscore character represents an

anonymous variable

which has no name associated with it

the anonymous variable then indicates

that we don't care what instantiation

the variable gets

during the unification process

now in general the underscore character

representing an anonymous variable

would replace a variable that is unused

to define

a result in an atomic proposition

or in a rule now

the underscore character just serves

to simplify our prologue implementations

and it is not strictly speaking required

so in a situation where a variable

is unused within a result

and we don't use an underscore character

but instead

use a variable name we may get

a warning from our prologue interpreter

indicating that the variable is unused

but in general this won't cause any kind

of

problem when the prologue proposition

is actually used

we'll now look at three example

implementations of prologue propositions

that perform list manipulations our

first proposition

is the member proposition which defines

a relation

between two parameters the first

parameter which is represented here by

the variable x

is a term and the second parameter

represented by the variable y

is a list now the member proposition

should be true

if the term x is contained within

the list y so over here we have an

example of how the member proposition

can be used

and this proposition should be true

because the

first parameter which is the atom a

is contained within the second parameter

which is a list containing the atoms

b a and c

so how will we then go about

implementing this member proposition

well we need to search through the list

one element

at a time i'm trying to find a match

between

the term and the element that we are

currently

looking at so this implies that we have

to use

a recursive strategy which means that we

need a base case

and a recursive case so we can state

that a term is a member of the list if

this term

is either the head of the list or

a member of the tail of the list the

situation where the term

is the head of the list corresponds to

our base case

because this terminates our recursion

due to the fact that we have found the

element in the list that we

are searching for the situation where

the term

is a member of the tail of the list

corresponds to our recursive case

because

the tail requires further processing

after ignoring the head of the list

so over here we have our implementation

of the member proposition and we can see

that we

have two statements the first statement

corresponds to our base case and the

second statement corresponds to

our recursive case our base case

is represented by means of an atomic

proposition

and our recursive case is a bit more

complex and is represented by means

of a rule so let's look at

our base case first here we specify

that the variable element is a

member of a list if

this element is the head of the list

notice that we have used an underscore

symbol for the tail of the list

this means that we are working with

an anonymous variable which means we are

not interested

in the instantiation of this variable

this makes sense because we don't care

about

the tail of the list because we have

found

the elements that we are searching for

next we'll move on to the statement that

defines

our recursive case now here

it's important to take notes of the fact

that the order of the statements is

important

and this is because prologue matches

from the top of the program

to the bottom of the program so what

this thing means

is the second statement will only be

matched

in a situation where the first statement

has not been matched in other words

we have not found the base case

for our search in this case we then

know that the element is not the head of

the list so we can discard

the head of the list and then here we

specify

that the element represented by the

variable element

is a member of a list where the tail of

the list is represented by the variable

lis and the element

is a member of lis

lis again being the tail of the list

so again here notice that we have used

an underscore symbol in other words an

anonymous variable

for the head of our list and this is

because

we are not interested in an

instantiation

for that variable because we are

discarding

the first element in the list

so notice also here that we do not

need to create any prologue statements

that relate to a situation where an

element

has not been found in other words where

we have reached the

end of the list if we reach the end of

the list without the base case

being satisfied then the entire

member proposition will fail and we will

then get

a no or a false response this of course

makes sense because we haven't found the

elements that we are

searching for now what i would like you

to

do at this point is pause the video and

consider what would happen

if we swapped the two statements so in

other words

we had the base case appearing after

the recursive case

so finally down here we have two

example queries that are valid for the

member proposition

over here we are asking whether the atom

a

is a member of the list containing the

atoms

d b and c and of course here

the atom a is not contained within this

list which means that our member

proposition

will then fail and prologue will respond

with no or false

the second query over here

asks prologue to find an instantiation

for the variable

x such that x is a member

of the list containing the atoms a b and

c

so what will happen here is prolog will

find an initial

instantiation for the variable x which

will be

the atom a we can then re-query

prologue again and in this case we are

then asking prolog to find

a second instantiation that makes this

proposition

true so this point prolog will then

instantiate

x to the atom b and will respond with

a yes or a true result if we

re-query another time then prologue will

instantiate the x variable

to the atom c and then if we try

re-quering again

after this prologue will not be able to

find another instantiation of the

variable x

that is contained within the list

our next prolog implementation is for an

append proposition the append

proposition

defines a relation between three

parameters

here represented by the variables x y

and z

respectively all three parameters are

lists so the append proposition

is true if appending the list

y to the end of the list x

produces the list z as a result

over here we have an example of how the

append proposition

could be used and this proposition

should be true because if we append the

list containing the atoms

c and d to the end of the list

containing the atoms a

and b then the result should be

a list containing the atoms a b c

and d in that order

so how will we then go about

implementing the append

proposition well we need to work through

a list one element

at a time so this means we have to use

a recursive strategy with a base case

and a recursive case so the approach

that we will use is that we

will append the second list to the tail

of the first list to produce a result

and then we prepend the head of the

first list

to the result so let's look at the

strategy

in relation to our example proposition

over here what we are essentially doing

then

is we are working through the first list

one element at a time and we are

eliminating at each step

the head of the list so with the first

recursive step we eliminate the first

element

in the first list which is the atom a

and that leaves us with a list

containing only

the atom b we then need

to append our list containing the atom c

and d to this list containing only the

atom b

however we haven't eliminated all of the

elements within the list yet

so we need to then eliminate the atom

b which leaves us only then with

the implicit tail of the list which as

we've previously seen

is an empty list at this point

we have reached our base case because we

are now appending the list containing

the atoms c

and d to an empty list and the result

of that of course should simply be the

list containing the atoms

c and d so now that we've reached our

base case

we then return and unwind the call stack

and as we unwind the call stack we then

prepend each atom that we've eliminated

from the first list and this happens

in the reverse order of which they were

removed so we then pre-pinned the atom

b to the list containing the atoms c and

d

and this gives us the list containing

the atoms

b c and d then

when we unwind to our final step we

pre-pinned

the atom a to the list containing the

atoms

b c and d and this gives us our final

result which is the list containing the

atoms

a b c and d so over here

we have an implementation of the

prologue append proposition

and again it notes that we have two

statements the first statement

representing the base case

and the second statement representing

the

recursive case so our base case

is fairly simple here we are appending a

list

represented by the variable list

to an empty list and the result of this

is simply list once again

now we can move on to our recursive case

which is a little more complicated

and is implemented by means of a rule

so here we are appending a list which is

represented by the variable

list 2 to a list where the head of this

list is represented by the variable head

and the tail of this list is represented

by the variable

list 1. now what we need to do

is discard the head element from this

list

and append list two to the tail

list one so this is done in the

antecedent

of our rule over here where we are

appending

list 2 to list 1 which is the

tail of the first list then

the result that we get is defined by the

variable

list 3. so finally we can now

define our final result

over here in the consequent

and the final result then is

the list 3 variable which is the list

that we've

created by means of this append

operation

over here with the head

prepended to that list where the head

is the first element of the first

list so here we have

four example queries that we could

use which involve the append proposition

the first query is relatively

straightforward here we

are asking prologue whether appending

the list

containing the atoms c and d to the list

containing the atoms a

and b produces a list containing the

atoms

a b c and d this of course is the case

so therefore prolog will respond with

yes or true

however with the remaining three queries

we now see the power of prologue

propositions so what prologue allows us

to do

is to ask for an instantiation

of any one of the three parameters

as long as we provide sufficient

information

for the instantiation to take place

which means that we provide

values for the other two parameters

so in our second query over here we are

asking prologue

what the result is of appending

the list containing the atoms c and d

to the list containing the atoms a and b

prologue will then respond with yes or

true and it will indicate that the

instantiation for the variable

x is the list containing the atoms a

b c and d in the next query over here

we are asking prologue what do we need

to

append to the list containing the atoms

a

and b in order to get a result which

is the list containing the atoms a b c

and d prologue can find an instantiation

for this variable x because it has

sufficient remaining information

to perform the instantiation and it will

then respond with

yes or true and it will indicate that

the instantiation for the variable

x should be the list containing the

atoms

c and d finally in

our last query we are asking prologue

if we append the list containing the

atoms c

and d to a list and the result

is the list containing the atoms a b c

and d what must this list be that we

append

to once again prolog can answer this

question because it has sufficient

information

so it will respond with a yes or true

and indicate that the instantiation for

the variable

x must be the list containing the atoms

a and b

the final implementation example we'll

look at is for

a reverse proposition so the reverse

proposition defines a relation between

two parameters

which are represented by the variables x

and y respectively

both x and y are lists so the reverse

proposition

is true if the list y is the reversed

version

of the list x over here we have

an example of how the reverse

proposition could be

used and this proposition should be true

because if we reverse the list

containing the atoms

a b and c in that order then we get

a result which is the list containing

the atoms

c b and a in that order

so what approach then will we use for

implementing our reverse proposition

well we need to work through the first

list one element at a time

so this again suggests that we have to

use a recursive strategy

with a base case and a recursive case

so the approach that we will use is that

we will first

reverse the tail of the first list

and then we will append the head of the

first list

to this reversed version of the tail

now the subpending operation will be

implemented

by means of the append proposition

that we defined in the previous slide

so if we look at this procedure in terms

of the application of our reverse

proposition

then what we are doing in this case is

taking our first list which contains the

atoms a b and c

and we are reversing the tail of the

list which is a list containing the

atoms b

and c so the reversed version of that

tail should then

be the list containing the atom c

followed by the atom b and

then we append the atom a which is the

head of this list

to the reversed version of that tail

which then gives

us our final result which is the list

containing the atoms

c b and a finally

so what we are essentially doing here in

a similar fashion

to the append proposition that we looked

at

on the previous slide is we are

eliminating elements

from the first list one by one

we are performing the append operations

as we return our recursive calls in

other words as the call stack

unwinds so once again we will use an

empty list

to represent our base case

and this is once again because we are

eliminating elements from the first list

until eventually we are left only with

the implicit final tale

of the list which is an empty list

so over here we have our implementation

of the reverse

proposition and first of all we have our

base case

so the base case is very simple it

simply states

that if we reverse an empty list then

the result

is an empty list once again

now if we look at our recursive case

over here we see once again that we have

to use

a rule which is slightly more complex

so we are reversing our first list

over here and the first list consists

of a head which is represented by the

variable head

and a tail represented by the variable

tail so what we first need to do then

is reverse this tail and this is done

in our antecedent over here

where we specify that we

reverse the tail using a recursive

application of the reverse proposition

in order to get

a result which we will indicate by means

of

a variable called result we then perform

an append operation using the append

proposition that we previously defined

and here we are appending then the head

which is the first element

of the first list to the

result which is the result

of reversing the tail

and the result then of the subpending

operation

is a list which we will refer to

as the variable list

this list then is the final result

which is then the second parameter of

the reverse

proposition now notice that

the head that we use in this append

operation

is a list as is indicated by means of

the opening

and closing square brackets so why do we

have to provide

those opening and closing square

brackets

well the reason is that as we previously

saw our definition of the append

proposition

works with three lists so this means

that

our second parameter must be a list

however the head of a list is

simply an element in the example that we

used it would simply be

an atom so we therefore cannot use

an atom as this second parameter over

here we must use a list

and so we simply convert this head

element to a list

by surrounding it by these square

brackets

so finally we have three examples of

valid

queries that use the reverse proposition

the first one again is fairly simple so

here we

are asking prologue whether the list

containing the items

cb and a is a reversed version of the

list containing the atoms

a b and c of course this is the case

so prologue will respond with yes or

true

we can once again use variables in

our queries which we do in the last two

example queries over here

so in this case we are asking prologue

what is the reversed version of

the list containing the atoms a b and c

prologue can find an instantiation for

the variable x

over here so it will respond with yes

or true and it will then indicate that

the instantiation

for x is the list containing the atoms

c b and a in that order

in our final query over here we are

asking prologue

what list do we have to reverse

in order to get the list that contains

the atoms a b

and c in that order again prologue can

answer this query so it will respond

with a yes

or true and then it will indicate that

the instantiation

for the variable x must be the

list containing the atoms c b and

a in that order

so hopefully these queries that involve

variables illustrate the flexibility

of the prologue programming language

it's important

to note that we don't need to define

new reverse propositions in order to

use the reverse proposition in this way

so in other words we simply define our

reverse proposition

which produces a result by means of the

second parameter

and then the queries will

work regardless of which parameter we

specify

by means of a variable that needs to be

instantiated

this is particularly interesting in the

previous example that we looked at for

our implementation

of the append proposition and this

is because using the append proposition

with variables in the three contexts

of the three separate parameters would

typically

require three separate functions to be

implemented

in an imperative programming language

like c

plus or java

we will now take a look at four

deficiencies that are associated with

the prologue

programming language these deficiencies

are the reason that prologue is not more

widely used

in a practical context so

the first deficiency is resolution order

control

the second deficiency is referred to as

the

closed world assumption the third

deficiency

is called the negation problem and then

finally

we have some intrinsic limitations

associated

with certain kinds of computations

that prologue cannot perform efficiently

we'll look at each of these deficiencies

in order

over the remaining slides

the first deficiency associated with the

prologue programming language

relates to resolution order control

now in order to understand the problems

that go hand in hand

with resolution order control we must

first remember that prologue always

matches

from top to bottom when it is

considering facts and rules

and from left to right when it is

working through

sub goals now one of the consequences

of this is that a programmer can

directly

affect the efficiency of a prologue

program and one simple way that they can

do this

is by placing rules that are more likely

to succeed

higher up in their program

this means that these rules will

tend to be matched earlier which means

that there will be fewer matches that

will

fail and this then results in fewer

computational

steps when the prologue program is

executed

now this in itself is not a serious

problem it's essentially

just an optimization that can be

performed by a programmer

however what this does do is reduce

the context independence of prologue

and as we've previously seen context

independence

is a major goal of all logic

programming languages a more serious

problem

however is that resolution order

can lead to non-terminating recursions

in certain cases so in order to

illustrate this

we'll look at an example

within this example we have two

alternate

implementations of the ancestor

proposition

which defines a relation between

two parameters now we will assume

that both of these parameters are atoms

in addition we have a parent proposition

which specifies that one atom is the

parent of another atom

now we will consider in both of these

cases

that an atom is considered to be an

ancestor

of itself this is of course not accurate

in a real world context however it works

for this example

so we then also consider one atom to be

the ancestor of another atom

if there is a series of

parents that link the first

atom to the second atom in the ancestor

proposition so we specified in this case

by means of a rule and here we specify

that x is the ancestor of

y if a z exists

such that z is an ancestor

of y and then x

is the parent of this

z ancestor so this of course

then makes sense in an intuitive

fashion but how will this proposition

actually function if we issue a query to

prologue

using the ancestor relation

well this will work in a situation

where we have an atom that is an

ancestor of itself

obviously because this is the base case

and it will also work

in a situation where x

and y are directly related by means

of a parent proposition however in a

situation where x and y

are not directly linked by a parent

proposition we will then

have to move on to the antecedent

of our rule and prologue then

works from the left hand side to the

right hand side

treating the ancestor proposition as a

goal

and then the parent proposition as a

second goal

so before we can move on to the parent

proposition we must first of all

satisfy the ancestor proposition

what will happen here then is that

prologue will attempt to find an

instantiation

for zed such that zed is an

ancestor of y the second atom in the

ancestor proposition this

will ultimately result in prologue then

matching against the rule once again

and this will then continue happening

over and over

until eventually prologue runs out of

memory we will never get to a situation

where we can then attempt to satisfy the

second sub-goal

which is the parent proposition

now let's look at the second

implementation over here

and we see that the base case is exactly

the same

as in the previous implementation

however our rule is slightly different

and the only difference

is that the two propositions

in the antecedent of the rule are

swapped

when we compare them to the first

rule that we looked at so in this case

the ancestor proposition will work

correctly

because we first of all attempt to

find a parent x of another atom

z we can of course then satisfy

this proposition as a sub goal

because we have parent relations that

are specified by means of

rules in our prologue program so

we then create an instantiation for z

and then we test to see whether zed is

an

ancestor of why this will then

eventually allow us to perform all of

the

matches that are required which will

then

either prove or ultimately disprove

that x is an ancestor of y

prologue provides an additional feature

referred to

as a cut and cuts are not

deficiencies related to the prologue

programming language

but they are very closely related to

resolution order control cuts

allow a programmer to explicitly control

backtracking which is performed during

prologues resolution process

so a cut is a special kind of goal

and is represented by means of an

exclamation mark symbol

this goal is always satisfied

however the cut and any sub-goals that

appear to the left of the cut

cannot be re-satisfied by means of

backtracking

now cuts can be very complex and there

are

different kinds of cuts but we are not

interested in

this level of detail instead we will

simply illustrate how cuts

work by means of a simple example

so this example presents two

implementations

of a proposition called valid member

the valid member proposition has a

single parameter

which we will assume is an atom and it

is represented here by means

of the variable x so the valid member

proposition

is meant to check first of all whether x

is

a member of an organization and secondly

whether x satisfies some kind of

requirement

to be a valid member so in order to

determine whether x is a valid member we

need to look at

the antecedent of this rule and we see

that the antecedent

has two sub-goals the first

sub-goal tests to see whether x

is a member of a list by means of

the member proposition now we assume

that this list contains atoms and that

these

atoms represent individual members

of an organization the

ellipses between the square brackets of

the list

simply indicate that the list

contains a lot of atoms and is therefore

very long we also assume

that the list contains no duplicate

elements

so once our first sub-goal has

determined that x

is a member of this list we can then

move on to the second sub

goal and this sub goal uses a test

proposition

in order to determine whether x

satisfies

the requirements for being a valid

member

so this is then a sensible

implementation

for the valid member proposition however

let's look at how prolog will actually

interpret the valid member proposition

if it is used in a query

so let's assume then that we test

whether a particular atom

is a valid member and we also assume

that this atom is contained within

the list so in other words our first sub

goal

succeeds we then move on to

our second sub goal however we assume

then that x fails its test so in other

words

the second sub goal is not

satisfied now we know

by means of our understanding of the

resolution process

that prologue now needs to backtrack to

the

previous sub-goal and this will then

continue the search for x

within the list however

we know that the list contains no

duplicate elements

so this continued searching is then

guaranteed to

fail once the remainder of the search

then fails

then our entire application of the valid

member proposition

fails however this continued

search is unnecessary and therefore

introduces additional computational

complexity

which is not necessary so now let's look

at

our second implementation of the valid

member proposition

we can see that this valid member

proposition is implemented in exactly

the same way

as our first example and it has

the same two sub-goals however between

the two sub-goals

we have an additional sub-goal which is

a cut represented by the exclamation

mark symbol so let's assume exactly

the same scenario that i described for

the previous implementation of the valid

member proposition

so again we then find x within

our list we then move on to the next sub

goal which is our cut

and the sub goal is automatically

satisfied

we then move on to our last sub goal

where we perform

our test on x and we again assume that

this test

fails so this point prologue would then

backtrack

however it encounters the

exclamation mark symbol which represents

a

cut and this means it cannot backtrack

past the cut

to the first sub-goal this then

means that our application of the valid

member proposition will immediately fail

without backtracking to perform

a continued search for x within

the list we've therefore eliminated

the additional search steps that are not

required

and this means that this implementation

of the valid member proposition

is more efficient now what i would like

you to do at this point

is to pause the video and see if you can

think

of a another solution to

efficiently implement the valid member

proposition

but without using a cut

the second deficiency that is associated

with prologue is referred to

as the closed world assumption now

recall

that prologue can only prove things

using facts

and rules that have been provided to it

so if we assume that we issue a query

to prolog and prologue answers with

a yes or true response then it means

that the query can be proven true

however if prolog answers no or

false to the query then it means that

the query cannot be

proven and this doesn't necessarily mean

that the query is false

we may get for example a no or a false

response

if we have insufficient facts to prove

a query or the rules required to prove

the query

are implemented incorrectly now there's

no feedback mechanism

indicating that a no or a false response

is due to an implementation mistake or

due to a query

actually being false and this can

potentially lead to

a programmer drawing the wrong

conclusions from

a negative response

the next prologue deficiency that we'll

look at

is referred to as the negation problem

and this

is fairly closely related to the closed

world assumption we just discussed

now the negation problem relates to the

fact that it is difficult

to handle logical negations within

prolog

so in order to illustrate this let's

look at

a simple implementation and here we've

provided

two facts as well as a single

rule to prologue the first fact states

that

bill is jake's parent and the

second fact specifies that bill is also

the parent of

shelly next we have our rule that

specifies

a sibling proposition and it specifies

that two atoms x and y are siblings

if there exists an m such that

m is the parent of x and m

is also the parent of y

so this implementation then seems to

make sense

however let's consider a situation where

we provide

this query to prolog so here we are

asking prologue to find

instantiations for x and y

such that x and y are siblings

now we would assume then that prologue

would

instantiate x and y to jake

and shelby however what we find

is that prologue responds with a yes or

a true

indicating that it can find a valid

instantiation

but then it instantiates x and y

both to jake now why does this happen

well put simply there is nothing

explicitly

telling prologue that x and y must be

different atoms but to explain this on a

more

technical level we can look look at how

the resolution process

um deals with this query

so the resolution process will then

consider

the two sub goals in the antecedent of

our rule

and it will first of all try to find

a parent m of x

so we know then that the matching

procedure performed by prologue begins

at the top of the program and moves to

the bottom

so this first sub goal will then

match to the first fact so in other

words

m will be instantiated to bull

and x will be instantiated to jake

next we need to move on to the second

sub goal

but this sub goal is satisfied

independently of the first

sub goal so once again prologue will

then begin its search

from the top of the program and move

towards the bottom

and again it can then satisfy this

second sub goal with the first fact that

has been provided

which once again then states that bill

is the parent of jake

therefore m is once again

bull and y has been instantiated

to jake so this is why

both x and y are instantiated

to the atom jake so

how can we then solve this problem

well we can approach this in a fairly

simple fashion

by means of rewriting the

sibling proposition and we do this

by adding a third sub goal

to the antecedent of our rule

and this sub goal then uses the

not operator that prolog provides

and the not operator is then satisfied

if its parameter is not satisfied

so in other words this goal will only be

satisfied if

the statement that x is equivalent to y

fails this will then ensure

that x is not instantiated to jake while

y

is also instantiated to jake and

therefore

we will get the correct response that we

expect

now it is very important to understand

that the not

operator doesn't function like a true

logical not as i previously mentioned

the

not operator succeeds if its parameter

proposition

fails however we saw when we were

discussing the closed world assumption

that a proposition fails if prologue

can't prove

its truth and this doesn't then

necessarily mean that the parameter is

actually false so if we look at the use

of the not

operator as it appeared in the example

that we looked at

on the previous slide this use

of the not operator means that the

resolution process

cannot prove that x is the same as

y so in other words there are no

facts that state that x and y are equal

to one another

it however doesn't mean that x is not

equal to y so in order to actually

properly establish that two atoms

are unequal we would need to

implement a separate fact for each pair

of atoms

which would specify that these two atoms

are

not equivalent to each other now of

course this approach

is impractical for any moderately large

set

of atoms and therefore we typically

don't use this approach in practice and

we therefore

need to rely on the not operator even

though

it isn't actually a true logical knot

finally probably the biggest deficiency

associated with prologue

is that there are intrinsic limitations

associated with the resolution process

that prologue performs

this means that there are certain kinds

of tasks that are simply impossible

to specify efficiently so

over here we have an implementation

example

of one such case and we've actually

discussed this

example previously in the first lecture

on this chapter

when we were discussing first order

predicate calculus

so here we are defining a sort

proposition and the sort proposition

states

that new list is a sorted version of old

list

if new list is a permutation

of old list in other words a reordering

of the elements in old list

and new list is also sorted

we test where the new list is sorted by

means of

the sorted proposition which is defined

over here and the sorted proposition

essentially just

defines the characteristics of a sorted

list

so how does prolog then actually go

about

sorting old list well essentially it

generates

a permutation of old list and then it

checks to see whether this permutation

is sorted if this permutation isn't

sorted then it generates

another different permutation of old

list

and then tests to see with this new

permutation is sorted

it continues doing this until eventually

it generates a permutation that is a

sorted version of old list

so this can obviously take a very long

time and it may in fact require

that prologue generate every possible

permutation

of old list so this is

then a very inefficient mechanism for

sorting a list

however it is the only way that we can

define

a sorting of a list within

the prologue programming language

finally we will finish this lecture by

looking at

a few practical application areas for

logic programming so first of all

logic programming languages have been

used in relational

database management systems and here

they

are used to implement intelligent query

systems

for these databases which allow a user

to perform a logical query

on the contents of a relational database

secondly logic programming languages

have been used within

expert systems and expert systems

are essentially a set of rules

that are used within a decision making

system obviously logic programming

languages make sense

because they support rules and expert

systems are based on rules

and then finally logic programming

languages such as

prologue have been used for natural

language processing

in the domain of artificial intelligence

all right so that then concludes our

discussion on chapter 16.

in the next lecture we will move back to

earlier chapters

where we will skip chapters three and

four

and begin looking at chapter five

of the textbook