COS 333: Chapter 16, Part 3
Summary
TLDRThis 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
đ 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.
đ 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.
đ 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.
đ 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.
đ 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.
đ 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.
đ« 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.
âïž 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.
đ 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.
đ 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.
Mindmap
Keywords
đĄLogic Programming Languages
đĄProlog
đĄArithmetic Operations
đĄList Structures
đĄResolution Process
đĄVariables
đĄInstantiation
đĄRules
đĄRecursion
đĄDeficiencies
đĄPractical Applications
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
5.0 / 5 (0 votes)