prolog questions
daih17
Lecture_Slides_export2.ziplecture21_slides.pdf
Michael McThrow November 9, 2020
Cuts and Negation CS 152 -- Programming Paradigms San José State University
Agenda
• Backtracking and Search Trees • Cuts • Negation • Project #2 Details • Final Four Weeks of CS 152
Backtracking and Search Trees
Search Trees • According to Sterling and Shapiro, "A search tree of a goal G with respect to a
program P is defined as follows":
• G is the tree's root. • Nodes are goals (can be conjunctive). • "There is an edge leading from a node N for each clause in the program
whose head unifies with the selected goal."
• "Each branch in the tree from the root is a computation of G by P." • Leaves are either success nodes or failure nodes. Each success node is a
solution of the query.
Search Tree Example 111 Theory of Logic Programs
Figure 5.2 Two search trees
reduction is the first goal. The edges are labeled with substitutions that are applied to the variables in the leftmost goal. These substitutions are computed as part of the unification algorithm.
Search trees correspond closely to traces for deterministic computa- tions. The traces for the append query and hanoi query given, respec- tively, in Figures 4.3 and 4.5 can be easily made into search trees. This is Exercise (i) at the end of this section.
Search trees contain multiple success nodes if the query has mul- tiple solutions. Figure 5.3 contains the search tree for the query ap- pend(As , Bs, [a, b, ci)? with respect to Program 3.15 for append, asking to split the list [a, b, ci into two. The solutions for As and Bs are found by collecting the labels of the edges in the branch leading to the success node. For example, in the figure, following the leftmost branch gives the solution {As=[a,b,c] ,Bs=[ J).
The number of success nodes is the same for any search tree of a given goal with respect to a program.
Search trees can have infinite branches, which correspond to nonter- minating computations. Consider the goal append(Xs, [c,di ,Ys) with respect to the standard program for append. The search tree is given in Figure 5.4. The infinite branch is the nonterminating computation given in Figure 4.6.
From Sterling and Shapiro, p. 111
Search Tree Example
From Sterling and Shapiro, p. 112
112 Chapter 5
Figure 5.3 Search tree with multiple success nodes
Complexity measures can also be defined in terms of search trees. Pro- log programs perform a depth-first traversal of the search tree. There- fore, measures based on the size of the search tree will be a more real- istic measure of the complexity of Prolog programs than those based on the complexity of the proof tree. However, the complexity of the search tree is much harder to analyze.
There is a deeper point lurking. The relation between proof trees and search trees is the relation between nondeterministic computations and deterministic computations. Whether the complexity classes defined via proof trees are equivalent to complexity classes defined via search trees is a reformulation of the classic P=NP question in terms of logic program- ming.
5.4.1 Exercises for Section 5.4
Transform the traces of Figure 4.3 and 4.5 into search trees.
Draw a search tree for the query sort([2,4, 1] ,Xs)? using permu- tation sort.
],Bsa,c]}
{Asl =[ ],Bs=[b,c]}
C {As2=[ },Bs=lcJ}
Search Trees
• Sometimes there can be multiple possible search trees for a search query. • Each possible search tree depends on decisions made regarding how new
elements are added to the resolvent when resolving the query and how the new clause A' from P is found.
Review: Resolution Algorithm
From Sterling and Shapiro, p. 93
Review: Resolution Algorithm (with Prolog implementation details)
From Sterling and Shapiro, p. 93
resolvent is a stack
A = resolvent.pop() choose first A' in program P that unifies with A
B1,...,BN are pushed onto the stack
Backtracking
From Sterling and Shapiro, p. 93
What happens when there is no A'? We backtrack to the last A that successfully unified. This allows us to try a different computation path. Note that backtracking is not shown in this algorithm.
Cuts
Problems That Arise When Using Prolog • Unnecessary backtracking in some queries. • This unnecessary backtracking leads to wasted computations.
• It would be nice for the programmer to be able to ignore, or "prune" branches of a search tree that the programmer knows are "unfruitful."
• Prolog provides such functionality by providing cuts.
Cuts • A cut is expressed as a ! in Prolog. • Whenever Prolog encounters a ! inside of a rule, this means that Prolog will
commit to all of the choices made before ! appeared; the interpreter will not backtrack on any decision made before !.
Merge Example from Textbook (p. 190)190 Chapter 11 merge(Xs,Ys,Zs) -
Zs is an ordered list of integers obtained from merging the ordered lists of integers Xs and Ys.
merge([XJXs], [YIYs] , [XIZs]) - X < Y, merge(Xs, [YIYs] ,Zs). merge([XIXs], [YIYs] , [X,YZs]) - X=:=Y, merge(Xs,Ys,Zs).
merge([XXs], [YIYs] , [YIZs]) - X > Y, merge([XIXs] ,Ys,Zs). merge(Xs, E ] ,Xs). merge([ ],Ys,Ys).
Program 11.1 Merging ordered lists
The cut, denoted !, can be used to express the mutually exclusive nature of the tests. It is placed after the arithmetic tests. For example, the first merge clause is written
merge([XIXs],[YIYs],[XIZs]) x < Y, !, merge(Xs,[Y IYs],Zs).
Operationally, the cut is handled as follows. The goal succeeds and commits Prolog to all the choices made since the
parent goal was unified with the head of the clause the cut occurs in. Although this definition is complete and precise, its ramifications and
implications are not always intuitively clear or apparent. Misunderstandings concerning the effects of a cut are a major source
for bugs for experienced and inexperienced Prolog programmers alike. The misunderstandings fall into two categories: assuming that the cut prunes computation paths it does not, and assuming that it does not prune solutions where it actually does.
The following implications may help clarify the foregoing terse defini- tion:
First, a cut prunes all clauses below it. A goal p unified with a clause containing a cut that succeeded would not be able to produce solutions using clauses that occur below that clause. Second, a cut prunes all alternative solutions to the conjunction of goals that appear to its left in the clause. For example, a conjunctive goal followed by a cut will produce at most one solution. On the other hand, the cut does not affect the goals to its right in the clause. They can produce more than one solution in the event of backtracking. However, once this conjunction fails, the search proceeds
190 Chapter 11
merge(Xs,Ys,Zs) - Zs is an ordered list of integers obtained from merging the ordered lists of integers Xs and Ys.
merge([XJXs], [YIYs] , [XIZs]) - X < Y, merge(Xs, [YIYs] ,Zs). merge([XIXs], [YIYs] , [X,YZs]) - X=:=Y, merge(Xs,Ys,Zs).
merge([XXs], [YIYs] , [YIZs]) - X > Y, merge([XIXs] ,Ys,Zs). merge(Xs, E ] ,Xs). merge([ ],Ys,Ys).
Program 11.1 Merging ordered lists
The cut, denoted !, can be used to express the mutually exclusive nature of the tests. It is placed after the arithmetic tests. For example, the first merge clause is written
merge([XIXs],[YIYs],[XIZs]) x < Y, !, merge(Xs,[Y IYs],Zs).
Operationally, the cut is handled as follows. The goal succeeds and commits Prolog to all the choices made since the
parent goal was unified with the head of the clause the cut occurs in. Although this definition is complete and precise, its ramifications and
implications are not always intuitively clear or apparent. Misunderstandings concerning the effects of a cut are a major source
for bugs for experienced and inexperienced Prolog programmers alike. The misunderstandings fall into two categories: assuming that the cut prunes computation paths it does not, and assuming that it does not prune solutions where it actually does.
The following implications may help clarify the foregoing terse defini- tion:
First, a cut prunes all clauses below it. A goal p unified with a clause containing a cut that succeeded would not be able to produce solutions using clauses that occur below that clause. Second, a cut prunes all alternative solutions to the conjunction of goals that appear to its left in the clause. For example, a conjunctive goal followed by a cut will produce at most one solution. On the other hand, the cut does not affect the goals to its right in the clause. They can produce more than one solution in the event of backtracking. However, once this conjunction fails, the search proceeds
Replacement of first rule with an included cut
Merge Example with Cuts (p. 192) 192 Chapter 11
merge(Xs,Ys,Zs) - Zs is an ordered list of integers obtained from merging the ordered lists of integers Xs and Ys.
merge([XIXs],[YIYs],[XIZs]) - X < Y, !, merge(Xs,[YIYs],Zs).
merge([XXs] ,[YIYs] , [X,YIZs]) - X=:=Y, !, merge(Xs,Ys,Zs).
merge([XIXs] , [Y lYs], [YIZs]) - X > Y, !, merge([XIXs],Ys,Zs).
merge(Xs, E ] ,Xs) - merge([ ],Ys,Ys) - L
Program 11.2 Merging with cuts
We restate the effect of a cut in a general clause C = A - B1,. . . ,Bk,!, Bk+2, . . . ,B in a procedure defining A. If the current goal G unifies with the head of C, and B1,. . .,B further succeed, the cut has the following effect. The program is committed to the choice of C for reducing G; any alternative clauses for A that might unify with G are ignored. Further, should B fail for i> k + 1, backtracking goes back only as far as the L Other choices remaining in the computation of B, i k, are pruned from the search tree. If backtracking actually reaches the cut, then the cut fails, and the search proceeds from the last choice made before the choice of G to reduce C.
The cuts used in the merge program express that merge is determinis- tic. That is, only one of the clauses can be used successfully for proving an applicable goal. The cut commits the computation to a single clause, once the computation has progressed enough to determine that this is the only clause to be used.
The information conveyed by the cut prunes the search tree, and hence shortens the path traversed by Prolog, which reduces the computation time. In practice, using cuts in a program is even more important for saving space. Intuitively, knowing that a computation is deterministic means that less information needs to be kept for use in the event of backtracking. This can be exploited by Prolog implementations with tail recursion optimization, discussed in Section 11.2.
Let us consider some other examples. Cuts can be added to the pro- gram for computing the minimum of two numbers (Program 3.7) in pre- cisely the same way as for merge. Once an arithmetic test succeeds, there
Minimum Example with Cuts (p. 193)193 Cuts and Negation
minimum(X,Y,Min) - Min is the minimum of the numbers X and Y.
minimuin(X,Y,X) - XY, L minimuin(X,Y,Y) - X > Y, L
Program 11.3 minimum with cuts
polynomial ( Term,X) - Term is a poiynornial in X.
polynomial(X,X) - L polynomial(Term,X) -
constant (Term), polynomial (Terml+Term2 , X)
polynomial (Terni, X), polynomial(Term2,X). polynomial (Terml-Term2 , X)
!, polynomial(Terml,X), polynomial(Term2,X). polynomial (Terml*Term2 ,X)
polynomial(Termi,X), polynomial (Term2,X). polynomial (Terml/Term2 , X)
polynomial (Terml,X) constant (Term2) polynomial(TermIN,X) -
!, integer(N), N > O, polynomial (Term,X).
Program 11.4 Recog zing polynomials
is no possibility for the other test succeeding. Program 11.3 is the appro- priately modified version of minimum.
A more substantial example where cuts can be added to indicate that a program is deterministic is provided by Program 3.29. The program defines the relation polynomial(Term,X) for recognizing if Term is a polynomial in X. A typical rule is
polynomial (Ternil+Term2 , X) -
polynomial(Terml,X), polynomial(Term2,X).
Once the term being tested has been recognized as a sum (by unifying with the head of the rule), it is known that none of the other polynomial rules will be applicable. Program 11.4 gives the complete polynomial program with cuts added. The result is a deterministic program that has a mixture of cuts after conditions and cuts after unification.
Green and Red Cuts • Green cuts are used for removing unnecessary backtracking in Prolog
programs.
• All examples shown have been examples of green cuts. • Green cuts are less controversial.
• Red cuts are used for changing the set of goals the program can prove. • "A standard Prolog programming technique using red cuts is the omission
of explicit conditions. Knowledge of the behavior of Prolog, specifically the order in which rules are used in a program, is relied on to omit conditions that could be inferred to be true" [Sterling and Shapiro, p. 203].
• Highly controversial; USE WITH EXTREME CAUTION!
Negation
Why should Prolog programmers be cautious about negation?
Recall that in logic programming, if a query results in a "no" or "false" answer, this does not state anything about the
truth of the query; it means that the interpreter failed to prove the query from the program [Sterling and Shapiro, p. 13].
However, it is convenient for programmers to express certain logical
statements using negation.
Examples of Negation
• single(X) :- not married(X). • fake(X) :- not authentic(X). • import(X) :- not domestic(X).
The concept "negation as failure" allows us to express negation in logic
programming.
According to Sterling and Shapiro, "A goal not G will be assumed to be a consequence of a
program P if G is not a consequence of P" (p. 114).
Cuts can be used to implement negation as failure.
Negation as Failure • Prolog provides a fail_if(Goal) predicate, which is equivalent to the not
statement.
• Prolog also has a system predicate called fail that always fails.
• Semantics of not G [Sterling and Shapiro, p. 198]:
198 Chapter 11
notX - X is not provable.
not X - X, !, fail. not X.
Program 11.6 Negation as failure
11.3 Negation
The cut can be used to implement a version of negation as failure. Pro- gram 11.6 defines a predicate not (Goal), which succeeds if Goal fails. As well as using cut, the program uses the meta-variable facility described in Chapter 10, and a system predicate fail that always fails.
Standard Prolog provides a predicate fail_if (Goal), which has the same behavior as not/i. Other Prologs provide the same predicate under the name \+/i. The rationale for not calling the system predicate not is that the predicate does not implement true logical negation, and it is misleading to label it as such. We believe that the user easily learns how the predicate differs from true negation, as we will explain, and programmers are helped rather than misled by the name.
Let us consider the behavior of Program 11.6 in answering the query not G? The first rule applies, and G is called using the meta-variable facility. If G succeeds, the cut is encountered. The computation is then committed to the first rule, and not G fails. If the call to G fails, then the second rule of Program 11.6 is used, which succeeds. Thus not G fails if G succeeds and succeeds if G fails.
The rule order is essential for Program 11.6 to behave as intended. This introduces a new, not entirely desirable, dimension to Prolog programs. Previously, changing the rule order only changed the order of solutions. Now the meaning of the program can change. Procedures where the rule order is critical in this sense must be considered as a single unit rather than as a collection of individual clauses.
The termination of a goal not G depends on the termination of G. If G terminates, so does not G. If G does not terminate, then not G may or may not terminate depending on whether a success node is found in the search tree before an infinite branch. Consider the following nontermi- nating program:
Project #2 Details
Project #2 Details • You will be implementing a simple Prolog interpreter. • No numbers, no type predicates, no meta-logical predicates, no cuts or negation; just
the Prolog you learned in the first 5-6 chapters of The Art of Prolog.
• The key is implementing resolution, unification, and backtracking correctly. You will use the resolution and unification algorithms from the textbook.
• Choices of programming languages for implementation: • C, C++, Java, Python, Racket (using DrRacket).
• May work with one partner. Only one partner has to submit, but both names need to be in the submission files.
• Feel free to test your interpreter on your Lab #3 submissions. • Due date: Monday, November 23 at 11:59pm Pacific Standard Time.
Final Four Weeks of CS 152 • Week 14 (11/16 and 11/18): Smalltalk • Week 15 (11/23): Self and JavaScript • Week 16 (11/30 and 12/2): Miscellaneous Topics
• I'm going to take a poll from the class where students can choose from various programming language topics. The two topics with the most votes from the class will be covered on November 30 and December 2.
• Material covered this week will be on the final exam, so choose something you're passionate about :).
• Week 17 (12/7 and 12/9): Final Review and Final Exam
Lab and Project Schedule • Labs • Lab #4 (Prolog) is due Friday, November 13 • Lab #5 (Smalltalk) will be assigned Monday, November 16 and is due Wednesday,
November 25
• Lab #6 (to be determined) will be assigned Saturday, November 28 and will be due Monday, December 7.
• Projects • Project #2 (Prolog interpreter) was assigned today and is due Monday, November
23.
• Project #3 (to be determined) will be assigned Monday, November 23 and is due Friday, December 11 (note that this is after the final).
lecture20_slides.pdf
Type Predicates Accessing Compound Terms Meta-logical Predicates
Structure Inspection and Meta-logical Predicates in Prolog
Michael McThrow
San Jose State University Computer Science Department
CS 152 – Programming Paradigms
November 2, 2020
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
Table of Contents
1 Type Predicates
2 Accessing Compound Terms
3 Meta-logical Predicates
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
Table of Contents
1 Type Predicates
2 Accessing Compound Terms
3 Meta-logical Predicates
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
Type Predicates
A type predicate is a unary predicate that is able to determine the type of a term.
Type predicates in Prolog have an equivalent in Scheme (e.g., number?, pair?, symbol?, etc).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
Type Predicates
A type predicate is a unary predicate that is able to determine the type of a term.
Type predicates in Prolog have an equivalent in Scheme (e.g., number?, pair?, symbol?, etc).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
integer
integer determines whether a parameter is an integer.
Examples:
integer(5)? ⇒ true. integer(-3)? ⇒ true. integer(x)? ⇒ false.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
integer
integer determines whether a parameter is an integer.
Examples:
integer(5)? ⇒ true. integer(-3)? ⇒ true. integer(x)? ⇒ false.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
atom
atom determines whether the parameter is an atom (i.e., a lowercase symbol in Scheme terminology).
Examples:
atom(bulbasaur)? ⇒ true. atom(5)? ⇒ false.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
atom
atom determines whether the parameter is an atom (i.e., a lowercase symbol in Scheme terminology).
Examples:
atom(bulbasaur)? ⇒ true. atom(5)? ⇒ false.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
compound
compound determines whether the parameter has the form of a relation with one or more arguments.
compound(evolution(bulbasaur,ivysaur))? ⇒ true. compound(s(0))? ⇒ true. compound(bulbasaur)? ⇒ false.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
compound
compound determines whether the parameter has the form of a relation with one or more arguments.
compound(evolution(bulbasaur,ivysaur))? ⇒ true. compound(s(0))? ⇒ true. compound(bulbasaur)? ⇒ false.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
number
number determines whether the parameter is a number. The number can be floating-point as well as an integer.
number(5)? ⇒ true. number(5.1)? ⇒ true. number(-5.1)? ⇒ true. number(x)? ⇒ false.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
number
number determines whether the parameter is a number. The number can be floating-point as well as an integer.
number(5)? ⇒ true. number(5.1)? ⇒ true. number(-5.1)? ⇒ true. number(x)? ⇒ false.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
atomic
atomic determines whether the parameter is either an atom or a number.
atomic(5)? ⇒ true. atomic(-3.14159)? ⇒ true. atomic(x)? ⇒ true. atomic(s(0))? ⇒ false.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
atomic
atomic determines whether the parameter is either an atom or a number.
atomic(5)? ⇒ true. atomic(-3.14159)? ⇒ true. atomic(x)? ⇒ true. atomic(s(0))? ⇒ false.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
Time for a demo in SWI-Prolog.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
What about for variables? Are there any built-in type predicates that detect whether a term is a variable?
Yes, and we will explore them later during this lecture.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
Table of Contents
1 Type Predicates
2 Accessing Compound Terms
3 Meta-logical Predicates
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
Recall that a compound term is one that has the form of a relation with one or more arguments.
Examples:
evolution(bulbasaur,ivysaur).
plus(s(0),s(s(0)),s(s(s(0)))).
s(0).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
Recall that a compound term is one that has the form of a relation with one or more arguments.
Examples:
evolution(bulbasaur,ivysaur).
plus(s(0),s(s(0)),s(s(s(0)))).
s(0).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
Suppose we want to obtain information about a compound term, such as its arguments or its arity (i.e., number of arguments).
We can obtain this information by using two built-in relations: functor/3 and arg/3.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
Suppose we want to obtain information about a compound term, such as its arguments or its arity (i.e., number of arguments). We can obtain this information by using two built-in relations: functor/3 and arg/3.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
functor
functor(Term,Name,Arity) is a relation that accepts a compound term Term and checks to see if the term’s name matches with Name and if the arity of the term is equal to Arity.
Example:
functor(evolution(eevee,jolteon),evolution,2)? ⇒ true.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
functor
functor(Term,Name,Arity) is a relation that accepts a compound term Term and checks to see if the term’s name matches with Name and if the arity of the term is equal to Arity.
Example:
functor(evolution(eevee,jolteon),evolution,2)? ⇒ true.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
arg
arg(N,Term,Arg) checks the compound term Term to see if its Nth argument is equal to Arg. Note that N starts at 1.
Example:
arg(1,evolution(eevee,jolteon),eevee)? ⇒ true. arg(2,evolution(eevee,jolteon),eevee)? ⇒ false.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
arg
arg(N,Term,Arg) checks the compound term Term to see if its Nth argument is equal to Arg. Note that N starts at 1.
Example:
arg(1,evolution(eevee,jolteon),eevee)? ⇒ true. arg(2,evolution(eevee,jolteon),eevee)? ⇒ false.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
Time for another SWI-Prolog demo.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
Table of Contents
1 Type Predicates
2 Accessing Compound Terms
3 Meta-logical Predicates
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
Meta-logical predicates are predicates that “sit above” the logic programming system. They are used for exercising control over the execution of logic programs.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
So, back to our earlier question? Are there any built-in type predicates that detect whether a term is a variable?
Yes.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
So, back to our earlier question? Are there any built-in type predicates that detect whether a term is a variable?
Yes.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
var and nonvar
var(Term) checks if Term is a variable.
nonvar(Term) checks if Term is not a variable.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
Example
Here is a new version of plus(X,Y,Z) that uses nonvar:
plus(X,Y,Z) :- nonvar(X),nonvar(Y),Z is X+Y.
plus(X,Y,Z) :- nonvar(X),nonvar(Z),Y is Z-X.
plus(X,Y,Z) :- nonvar(Y),nonvar(Z),X is Z-Y.
Compared to the last plus example from previous lectures, this has restored some query functionality; we can now run queries such as plus(X,6,10)?. Note that performing queries with two variables is still not supported in this above definition, but we have the tools to extend the definition to support such queries (and this will be one of your lab exercises).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
Example
Here is a new version of plus(X,Y,Z) that uses nonvar:
plus(X,Y,Z) :- nonvar(X),nonvar(Y),Z is X+Y.
plus(X,Y,Z) :- nonvar(X),nonvar(Z),Y is Z-X.
plus(X,Y,Z) :- nonvar(Y),nonvar(Z),X is Z-Y.
Compared to the last plus example from previous lectures, this has restored some query functionality; we can now run queries such as plus(X,6,10)?. Note that performing queries with two variables is still not supported in this above definition, but we have the tools to extend the definition to support such queries (and this will be one of your lab exercises).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
Example
Here is a new version of plus(X,Y,Z) that uses nonvar:
plus(X,Y,Z) :- nonvar(X),nonvar(Y),Z is X+Y.
plus(X,Y,Z) :- nonvar(X),nonvar(Z),Y is Z-X.
plus(X,Y,Z) :- nonvar(Y),nonvar(Z),X is Z-Y.
The uses of nonvar that are placed at the initial parts of the bodies of the above clauses are examples of meta-logical tests. Meta-logical tests decide which clause in a procedure should be used [Sterling and Shapiro].
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
The == predicate checks to see if X and Y are identical. \== checks to see if X and Y are not identical.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
freeze and melt
The relation freeze(Term,Frozen) makes a copy of Frozen and makes it ground (i.e., treats it as if it had no variables). The relation melt(Frozen,Thawed). “unfreezes” Frozen and makes it un-ground. Note that the textbook describes a melt new relation, but it is not defined in SWI-Prolog.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
Type Predicates Accessing Compound Terms Meta-logical Predicates
Logical Disjunction in Prolog
We can perform logical conjunction (i.e, AND) by using commas in Prolog rules.
For logical disjunction, we use the semicolon:
Example: (X ; Y). means X OR Y.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Structure Inspection and Meta-logical Predicates in Prolog
- Type Predicates
- Accessing Compound Terms
- Meta-logical Predicates
lecture19_slides.pdf
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Introduction to Pure Prolog
Michael McThrow
San Jose State University Computer Science Department
CS 152 – Programming Paradigms
October 28, 2020
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Table of Contents
1 Overview
2 Prolog’s Execution Model
3 Arithmetic in Prolog
4 Preview of Monday’s Lecture
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Table of Contents
1 Overview
2 Prolog’s Execution Model
3 Arithmetic in Prolog
4 Preview of Monday’s Lecture
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
You might be wondering, “haven’t we been learning Prolog this whole time? Why is this lecture titled, ‘Introduction to Pure Prolog?”’
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Yes, we have been learning Prolog this whole time. You can run the examples shown thus far in this course using SWI-Prolog or other Prolog implementations.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
But, you have been learning a small, core subset of Prolog.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
In this lecture, we will cover additional pure Prolog features, such as arithmetic, and we will also cover Prolog’s execution model.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Table of Contents
1 Overview
2 Prolog’s Execution Model
3 Arithmetic in Prolog
4 Preview of Monday’s Lecture
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Let’s recall the resolution algorithm we studied in our last lesson:
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Resolution with Unification
Figure: Resolution algorithm with unification [Sterling and Shapiro 1994, p. 93]
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
There are two decisions that Prolog implementations need to make:
1 How to choose a goal A from the resolvent.
2 How to replace A with A′ ← B1, ..., Bn from the program.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
There are two decisions that Prolog implementations need to make:
1 How to choose a goal A from the resolvent.
2 How to replace A with A′ ← B1, ..., Bn from the program.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
There are two decisions that Prolog implementations need to make:
1 How to choose a goal A from the resolvent.
2 How to replace A with A′ ← B1, ..., Bn from the program.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
In Prolog, the resolvent is a stack.
When the interpreter chooses a goal A from the resolvent, it pops it from the stack.
When the interpreter chooses a A′ ← B1, ..., Bn from the program:
1 It chooses the first goal in the program that unifies with A. According to Sterling and Shapiro, “if no unifiable clause is found for the popped goal, the computation is unwound to the last choice made, and the next unifiable clause is chosen” [p. 120].
2 It pushes the elements B1, ..., Bn onto the stack.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Rule Order in Prolog
Because of how Prolog implementations handle resolvents, rule order in Prolog matters.
To directly quote Sterling and Shapiro, “the rule order determines the order in which solutions are found” [p. 130, emphasis original].
This is unimportant for pure Prolog programs since reordering rules will not affect the results of computations, but this will be very important once the cut feature is introduced next week.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Is it possible for a Prolog query to not terminate?
Yes, it is possible for a Prolog query to not terminate.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Is it possible for a Prolog query to not terminate? Yes, it is possible for a Prolog query to not terminate.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Non-termination in Prolog
This is particularly a problem with left-recursive rules.
A left-recursive rule is one where the first goal in the body is recursive (e.g., married(X,Y) :- married(Y,X).).
The best way to deal with possible non-termination in left-recursive rules is to avoid them by rewriting the rule in such a way to avoid left-recursion.
For example, we could define a new predicate, are married(Person1,Person2) with the following rules:
are married(X,Y) :- married(X,Y).
are married(X,Y) :- married(Y,X).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Circular definitions are also problematic; make sure you avoid them.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
The ordering that does matter considerably is the ordering of goals; i.e., each Bi in A ← B1, ..., Bn where 1 ≤ i ≤ n.
Goal ordering is important not only for runtime efficiency reasons, but also for termination reasons.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
The ordering that does matter considerably is the ordering of goals; i.e., each Bi in A ← B1, ..., Bn where 1 ≤ i ≤ n.
Goal ordering is important not only for runtime efficiency reasons, but also for termination reasons.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Given the rule
ancestor(X,Y) :- parent(X,Z),ancestor(Z,Y).
What would happen if the goals were swapped, resulting in the rule
ancestor(X,Y) :- ancestor(Z,Y),parent(X,Z).
This would introduce left-recursion to the rule, which means the rule would become non-terminating.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Given the rule
ancestor(X,Y) :- parent(X,Z),ancestor(Z,Y).
What would happen if the goals were swapped, resulting in the rule
ancestor(X,Y) :- ancestor(Z,Y),parent(X,Z).
This would introduce left-recursion to the rule, which means the rule would become non-terminating.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Table of Contents
1 Overview
2 Prolog’s Execution Model
3 Arithmetic in Prolog
4 Preview of Monday’s Lecture
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
System Predicates
Not all operations in Prolog can be conveniently or efficiently expressed as pure logic programs.
For example, we want to be able to perform arithmetic using our computer’s ALU and not by using custom functors.
To provide such functionality, Prolog has system predicates.
This is analogous to Scheme’s built-in functions such as define and lambda.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Arithmetic in Prolog
Prolog provides built-in predicates for performing arithmetic.
Examples include +, -, *, and /.
We can perform queries using the following form: Value is Expression?.
Examples of queries:
(X is 3+5)? ⇒ X=8. (8 is 3+5)? ⇒ yes.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
What does the query (3+5 is 3+5)? evaluate to?
Actually, this query will fail.
The reason this query fail is because the left side of is expects a value, not an expression.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
What does the query (3+5 is 3+5)? evaluate to?
Actually, this query will fail.
The reason this query fail is because the left side of is expects a value, not an expression.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Comparisons in Prolog
Prolog provides the following built-in comparison predicates: <, >, <=, and >=.
We can perform queries using the following form: A op B, where A and B are arithmetic expressions and op is one of the above comparison predicates.
Examples:
(1 < 2)? ⇒ yes. (4*6 < 5*5)? ⇒ yes. (6/2 < 5-1)? ⇒ no.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
What does the query (N < 1)? evaluate to?
This query results in an error since N is not an expression, but rather, a variable.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
What does the query (N < 1)? evaluate to?
This query results in an error since N is not an expression, but rather, a variable.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Arithmetic Queries
We can now write rules such as the following:
plus(X,Y,Z) :- Z is X+Y.
Unfortunately, we can’t perform queries such as the following:
plus(3,X,8)?
In order to do so, we need to use meta-logical predicates, which will be covered in the next lecture and is discussed in Chapter 10 of the textbook.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Arithmetic Queries
We can now write rules such as the following:
plus(X,Y,Z) :- Z is X+Y.
Unfortunately, we can’t perform queries such as the following:
plus(3,X,8)?
In order to do so, we need to use meta-logical predicates, which will be covered in the next lecture and is discussed in Chapter 10 of the textbook.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Table of Contents
1 Overview
2 Prolog’s Execution Model
3 Arithmetic in Prolog
4 Preview of Monday’s Lecture
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
On Monday we will be covering more system predicates that deal with types in Prolog, and we will also be covering meta-logical predicates, which allow us to exploit the full power of arithmetic in our Prolog programs.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
Overview Prolog’s Execution Model Arithmetic in Prolog Preview of Monday’s Lecture
Class Updates
I should finally have Project 1 grades finished no later than the end of this weekend (I apologize for the delay; I’ve been swamped lately).
Lab 3 is due Thursday.
I will be assigning Lab 4 and Project 2 on Monday. Lab 4 will consist of more exercises from The Art of Prolog, while Project 2 will consist of a significant Prolog programming exercise.
Just three more lectures on Prolog (November 2, November 4, and November 9)! November 11 is a holiday (Veteran’s Day), and November 16 will be the start of our third and final segment of the course, which will revisit object-oriented programming, using Smalltalk as our main language.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Pure Prolog
- Overview
- Prolog's Execution Model
- Arithmetic in Prolog
- Preview of Monday's Lecture
lecture18_slides.pdf
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Resolution and Unification in Logic Programming
Michael McThrow
San Jose State University Computer Science Department
CS 152 – Programming Paradigms
October 26, 2020
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Table of Contents
1 Basic Concepts
2 Resolving Ground Queries
3 Unification
4 Resolving Queries with Unification
5 Preview of Wednesday’s Lecture
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Table of Contents
1 Basic Concepts
2 Resolving Ground Queries
3 Unification
4 Resolving Queries with Unification
5 Preview of Wednesday’s Lecture
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Ground and Non-ground Terms
Terms that lack variables are ground.
Terms that contain variables are non-ground.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Examples of Ground and Non-ground Terms
Ground Terms:
evolution(bulbasaur, ivysaur).
fire(charmander).
plus(s(s(0)), s(s(s(0))), s(s(s(s(s(0)))))).
Non-ground Terms:
evolution(ivysaur, X)?
plus(0, X, 0).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Table of Contents
1 Basic Concepts
2 Resolving Ground Queries
3 Unification
4 Resolving Queries with Unification
5 Preview of Wednesday’s Lecture
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Definition of Resolution
Definition (Resolution)
“Resolution is the process of matching facts and rules to perform inferencing, the derivation of logical conclusions from the rules” [from Professor Tom Austin’s Spring 2019 CS 152 slides].
When we issue a query, the interpreter resolves it.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
The simple case is when we are issuing ground queries; i.e., queries with no variables such as evolution(bulbasaur, ivysaur)?.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
How do we resolve ground queries?
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Resolution Algorithm for Ground Queries and Terms
Figure: Resolution algorithm for ground queries and terms [Sterling and Shapiro 1994, p. 22]
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Let’s go to the whiteboard for an example.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Each iteration of the while loop in the resolution algorithm is called a reduction.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Definition of a Reduction
Definition (Reduction)
“A reduction of a goal G by a program P is the replacement of G by the body of an instance of a clause in P, whose head is identical to the chosen goal” [Sterling and Shapiro, p. 23].
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
This resolution algorithm works for ground queries given a program consisting of ground rules. But how do we deal with non-ground queries and rules?
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Table of Contents
1 Basic Concepts
2 Resolving Ground Queries
3 Unification
4 Resolving Queries with Unification
5 Preview of Wednesday’s Lecture
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Common Instance
Definition (Common Instance)
“A term t is a common instance of two terms t1 and t2, if there exist substitutions θ1 and θ2 such that t equals t1θ1 and t2θ2” [Sterling and Shapiro, p. 88].
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Definition of “More General”
Definition
“A term s is more general than a term t is t is an instance of s but s is not an instance of t” [Sterling and Shapiro, p. 88].
For example, fire(X) is more general than fire(charizard), since fire(charizard) is an instance of fire(X), but fire(X) is not an instance of fire(charizard).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Definition of “More General”
Definition
“A term s is more general than a term t is t is an instance of s but s is not an instance of t” [Sterling and Shapiro, p. 88].
For example, fire(X) is more general than fire(charizard), since fire(charizard) is an instance of fire(X), but fire(X) is not an instance of fire(charizard).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Alphabetic Variants
Definition (Alphabetic Variant)
“A term s is an alphabetic variant of a term t if both s is an instance of t and t is an instance of s” [Sterling and Shapiro, p. 88].
For example, these terms are alphabetic variants of each other:
member(X, tree(Left, X, Right))
member(Y, tree(Left, Y, Z))
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Alphabetic Variants
Definition (Alphabetic Variant)
“A term s is an alphabetic variant of a term t if both s is an instance of t and t is an instance of s” [Sterling and Shapiro, p. 88].
For example, these terms are alphabetic variants of each other:
member(X, tree(Left, X, Right))
member(Y, tree(Left, Y, Z))
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Unification
“A unifier of two terms is a substitution making the terms identical. If two terms have a unifier, we say they unify” [Sterling and Shapiro, p. 88].
“Any unifier determines a common instance, and conversely, any common instance determines a unifier” [p. 88].
Example: Given the terms append([1,2,3],[3,4],List) and append([X|Xs],Ys,[X|Zs]), the unifying substitution is X=1, Xs=[2,3], Ys=[3,4], List=[1,Zs] and the common instance is append([1,2,3],[3,4],[1|Zs]).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Unification
“A unifier of two terms is a substitution making the terms identical. If two terms have a unifier, we say they unify” [Sterling and Shapiro, p. 88].
“Any unifier determines a common instance, and conversely, any common instance determines a unifier” [p. 88].
Example: Given the terms append([1,2,3],[3,4],List) and append([X|Xs],Ys,[X|Zs]), the unifying substitution is X=1, Xs=[2,3], Ys=[3,4], List=[1,Zs] and the common instance is append([1,2,3],[3,4],[1|Zs]).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Most General Unifier (MGU)
Definition (Most General Unifier)
“A most general unifier, or MGU, of two terms is a unifier such that the associated common instance is most general” [p. 88].
The goal of unification is to identify the MGU of two terms. The resolution algorithm will use the MGU when resolving queries.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Most General Unifier (MGU)
Definition (Most General Unifier)
“A most general unifier, or MGU, of two terms is a unifier such that the associated common instance is most general” [p. 88].
The goal of unification is to identify the MGU of two terms. The resolution algorithm will use the MGU when resolving queries.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Unification Algorithm [Sterling and Shapiro 1994, p. 90]
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Let’s go to the whiteboard for an example.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Table of Contents
1 Basic Concepts
2 Resolving Ground Queries
3 Unification
4 Resolving Queries with Unification
5 Preview of Wednesday’s Lecture
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Resolution with Unification
Figure: Resolution algorithm with unification [Sterling and Shapiro 1994, p. 93]
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Table of Contents
1 Basic Concepts
2 Resolving Ground Queries
3 Unification
4 Resolving Queries with Unification
5 Preview of Wednesday’s Lecture
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
In the past few lectures, we’ve been going over pure logic programming with Prolog syntax. Beginning Wednesday, we will begin covering some more concrete elements of Prolog, including arithmetic and its execution model.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
Basic Concepts Resolving Ground Queries Unification Resolving Queries with Unification Preview of Wednesday’s Lecture
Reading Assignment
Please read chapters 6, 7, and 8 of The Art of Prolog.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Resolution and Unification in Logic Programming
- Basic Concepts
- Resolving Ground Queries
- Unification
- Resolving Queries with Unification
- Preview of Wednesday's Lecture
lecture17_slides.pdf
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Recursion in Logic Programming
Michael McThrow
San Jose State University Computer Science Department
CS 152 – Programming Paradigms
October 21, 2020
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Table of Contents
1 SWI-Prolog Demo
2 Recursion in Logic Programming
3 Lists
4 Preview of Monday’s Lecture
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Table of Contents
1 SWI-Prolog Demo
2 Recursion in Logic Programming
3 Lists
4 Preview of Monday’s Lecture
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
SWI-Prolog
We will be using SWI-Prolog as our Prolog implementation for this course. SWI-Prolog is open source and is available on Windows, macOS, and Linux.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
SWI-Prolog Demo
I will be providing a live demonstration on the basics of SWI-Prolog.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Table of Contents
1 SWI-Prolog Demo
2 Recursion in Logic Programming
3 Lists
4 Preview of Monday’s Lecture
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Motivation
Without recursion, we can use finite data structures.
Recursion gives us the power to define infinite data structures.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Defining Natural Numbers with Logic Programming
Now, Prolog does have built-in features for handling natural numbers that leverages the CPU’s arithmetic functionality.
However, it is instructive to define numbers in terms of logic programming rules.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Defining Natural Numbers with Logic Programming
Definition:
natural_number(0).
natural_number(s(X)) :- natural_number(X).
where s is the successor function of arity 1. Please note that the notation :- is equivalent to ←; when you are typing your Prolog programs, you would use :-.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Examples of Natural Numbers
0 0
s(0) 1
s(s(0)) 2
s(s(s(0))) 3
... ...
sn(0) n
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Example: Let’s run the query natural number(s(s(0)))?
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
What if we wanted to state that natural number X is less than or equal to natural number Y ?
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Let’s define X <= Y, which is equivalent to ’<=’(X, Y).
0 <= X :- natural_number(X).
s(X) <= s(Y) :- X <= Y.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Let’s define X <= Y, which is equivalent to ’<=’(X, Y).
0 <= X :- natural_number(X).
s(X) <= s(Y) :- X <= Y.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Let’s perform some queries involving X <= Y on the whiteboard and using SWI-Prolog.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Let’s also define plus(X,Y,Z), where Z is the sum of X and Y:
plus(0,X,X) :- natural_number(X).
plus(s(X),Y,s(Z)) :- plus(X,Y,Z).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Let’s also define plus(X,Y,Z), where Z is the sum of X and Y:
plus(0,X,X) :- natural_number(X).
plus(s(X),Y,s(Z)) :- plus(X,Y,Z).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Let’s do a few examples of plus(X,Y,Z) on the whiteboard.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
We can also take advantage of conjunction in our recursive definitions. For example, below is the definition of times(X,Y,Z), where Z is the product of X and Y:
times(0,X,0).
times(s(X),Y,Z) :- times(X,Y,XY),plus(XY,Y,Z).
What this does is perform the addition of Y to itself X times (e.g., 4 ∗ 5 = 5 + 5 + 5 + 5).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
We can also take advantage of conjunction in our recursive definitions. For example, below is the definition of times(X,Y,Z), where Z is the product of X and Y:
times(0,X,0).
times(s(X),Y,Z) :- times(X,Y,XY),plus(XY,Y,Z).
What this does is perform the addition of Y to itself X times (e.g., 4 ∗ 5 = 5 + 5 + 5 + 5).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Let’s perform s(s(0)) ∗ s(s(s(0))) using times on the whiteboard.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Table of Contents
1 SWI-Prolog Demo
2 Recursion in Logic Programming
3 Lists
4 Preview of Monday’s Lecture
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Lists in Prolog
Prolog has built-in support for lists.
As in Scheme and most other Lisp-derived languages, a list is made up of pairs, where the first element is the head of the list and the second element contains the rest of the list; the final pair’s second element contains an empty list.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Lists in Prolog
The fact describing a pair is .(X,Y), where X is the head of the list and Y is the second element. This is called the dot functor.
Prolog provides syntactic sugar for pairs in the form of [X|Y]; this usage is far more common.
The dot functor is the equivalent of a Lisp cons cell.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Defining a List in Prolog
list([]).
list([X|Xs]) :- list(Xs).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Let’s show an example of list on the whiteboard.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
How do we determine whether an element X is a member of a list?
member(X,[X|Xs]).
member(X,[Y|Ys]) :- member(X,Ys).
Note that the first clause could also be
member(X,[X|Xs]) :- list(Xs).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
How do we determine whether an element X is a member of a list?
member(X,[X|Xs]).
member(X,[Y|Ys]) :- member(X,Ys).
Note that the first clause could also be
member(X,[X|Xs]) :- list(Xs).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Here are some possible queries that we could perform:
member(a, [a, b, c])?
Is a a member of the list [a, b, c]?
member(X, [a, b, c])?
What are the members of the list [a, b, c]?
member(a, X)?
Which lists contain a?
Yes, we could do this in logic programming.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Demo in SWI-Prolog
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Finding the Prefix and Suffix of a List
prefix – Does the second list begin with the first list?
prefix([],Ys).
prefix([X|Xs],[X|Ys]) :- prefix(Xs,Ys).
suffix – Is the end of the second list the first list?
suffix(Xs,Xs).
suffix(Xs,[Y|Ys]) :- suffix(Xs,Ys).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Let’s do some examples of prefix and suffix on the whiteboard.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
append – Appends the second list to the first list
append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Let’s do an example of append on the whiteboard.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Interestingly, we could define prefix and suffix in terms of append:
prefix(Xs,Ys) :- append(Xs,As,Ys).
suffix(Xs,Ys) :- append(As,Xs,Ys).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Reversing a List
We could leverage append to reverse a list:
reverse([],[]).
reverse([X|Xs],Zs) :- reverse(Xs,Ys),append(Ys[X],Zs).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Reversing a List
However, we could make its execution more efficient by using an accumulator.
reverse(Xs,Ys) :- reverse(Xs,[],Ys).
reverse([X|Xs], Acc, Ys) :- reverse(Xs,[X|Acc],Ys).
reverse([],Ys,Ys).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
A Note About the Ordering of Rules in Prolog
The order of rules in Prolog matters; when executing queries Prolog looks up rules from the first defined to the last. For the examples in this slide rule ordering should not matter, but in more complex programs, rule order matters.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Table of Contents
1 SWI-Prolog Demo
2 Recursion in Logic Programming
3 Lists
4 Preview of Monday’s Lecture
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Resolution and Unification
In logic programming, an interpreter uses resolution and unification to answer queries.
Borrowing from Professor Tom Austin’s definitions from his Spring 2019 CS 152 slides:
“Resolution is the process of matching facts and rules to perform inferencing, the derivation of logical conclusions from the rules.” “Unification is the instantiation of variables via pattern matching.”
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
SWI-Prolog Demo Recursion in Logic Programming Lists Preview of Monday’s Lecture
Reading for Monday
Please read Chapters 4 and 5 of The Art of Prolog. For supplemental reading, the textbook we used for Scheme, Structure and Interpretation of Computer Programs, has information about an entire logic programming engine built in Scheme in Chapter 4.4.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Recursion in Logic Programming
- SWI-Prolog Demo
- Recursion in Logic Programming
- Lists
- Preview of Monday's Lecture
lecture16_slides.pdf
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Introduction to Logic Programming
Michael McThrow
San Jose State University Computer Science Department
CS 152 – Programming Paradigms
October 19, 2020
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Table of Contents
1 Imperative and Declarative Programming
2 Overview of Logic Programming
3 Basic Constructs of Logic Programming
4 Preview of Wednesday’s Lecture
5 Lab 3
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Table of Contents
1 Imperative and Declarative Programming
2 Overview of Logic Programming
3 Basic Constructs of Logic Programming
4 Preview of Wednesday’s Lecture
5 Lab 3
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
In this course, we have explored two programming paradigms: procedural programming and functional programming. The next paradigm we will be exploring is logic programming.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Imperative and Declarative Programming
Programming language paradigms can be split into two categories: imperative and declarative.
Imperative programming languages emphasize how to perform a computation.
Declarative programming languages emphasize what to compute.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Imperative and Declarative Programming
Programming language paradigms can be split into two categories: imperative and declarative.
Imperative programming languages emphasize how to perform a computation.
Declarative programming languages emphasize what to compute.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Imperative and Declarative Programming
Programming language paradigms can be split into two categories: imperative and declarative.
Imperative programming languages emphasize how to perform a computation.
Declarative programming languages emphasize what to compute.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Imperative vs. Declarative Example
Example: Let’s find all people under 25 years old.
# Imperative Example in Python
results = []
for person in people:
if person.age < 25:
results.add(person)
-- Declarative Example in SQL
SELECT * FROM people WHERE age < 25;
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Is functional programming declarative?
Yes, provided that we avoid side-effects and mutation.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Is functional programming declarative? Yes, provided that we avoid side-effects and mutation.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Table of Contents
1 Imperative and Declarative Programming
2 Overview of Logic Programming
3 Basic Constructs of Logic Programming
4 Preview of Wednesday’s Lecture
5 Lab 3
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Logic programming is a declarative programming paradigm that is rooted in first-order logic, also known as predicate logic.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Models of Computation
Turing machines → Procedural programming Lambda calculus → Functional programming First-order logic → Logic programming
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Like functional programming, logic programming is an alternative to the von Neumann architecture and the imperative programming paradigm it promotes.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
What is Logic Programming
Instead of providing explicit execution steps as in imperative programming, we instead provide knowledge that the runtime environment treats as logical axioms. We then query this knowledge base in order to solve problems.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Quote from The Art of Prolog
“In its ultimate and purest form, logic programming suggests that even explicit instructions for operation not be given but rather that the knowledge about the problem and assumptions sufficient to solve it be stated explicitly, as logical axioms” [Sterling and Shapiro, p. 3].
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
How Execution Works in Logic Programming
“The program can be executed by providing it with a problem formalized as a logical statement to be proved, called a goal statement” (p. 3).
“The execution is an attempt to solve the problem, that is, to prove the goal statement, given the assumptions in the logic program” (p. 3-4).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Structure of Goal Statements
“There exists a list X such that sorting the list [3, 1, 2] gives X” (p. 4).
“In this example, assuming the logic function contains appropriate axioms defining the sort relation, the output of the computation would be X = [1, 2, 3]” (p. 4).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Summary of Logic Programming (from The Art of Prolog)
A program is a set of axioms.
A computation is a constructive proof of a goal statement from the program.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Table of Contents
1 Imperative and Declarative Programming
2 Overview of Logic Programming
3 Basic Constructs of Logic Programming
4 Preview of Wednesday’s Lecture
5 Lab 3
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Facts
Definition (Fact)
A fact is a statement of the relationship between objects. Note that “a finite set of facts constitutes a program” (p. 12).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Examples of Facts
evolution(bulbasaur,ivysaur).
evolution(ivysaur,venusaur).
evolution(charmander,charmeleon).
evolution(charmeleon,charizard).
evolution(squirtle,wartortle).
evolution(wartortle,blastoise).
These relations (or predicates) specify Pokémon evolutions (e.g., Bulbasaur evolves into Ivysaur). Note that the lowercase text and the period at the end matter.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
More Examples of Facts
fire(charmander).
fire(charmeleon).
fire(charizard).
flying(charizard).
plus(0,0,0).
plus(0,1,1).
plus(1,0,1).
plus(1,1,2).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Queries
We use queries to get information from a program. Queries end with a question mark ? instead of a period.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Difference Between a Fact and a Query
fire(charizard).
This is a fact. Statement that fire(charizard) is true (i.e., Charizard is a fire-type Pokémon).
fire(charizard)?
This is a query. Query that asks whether fire(charizard) is true (i.e., is Charizard a fire-type Pokémon?).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Examples of Queries
fire(charizard)? ⇒ yes fire(venusaur)? ⇒ no
IMPORTANT: A no does not mean the query is false; it means it couldn’t be proved from the program.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Another Query Example
Based on the facts we have provided thus far, fire(vulpix)? would result in no because it hasn’t been defined in the program. However, all Pokémon fans know that Vulpix is a fire-type Pokémon. Thus, a no does not mean that the query is false; it simply means that the query could not be proved from the program.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Queries with Variables
How could we find out what a Pokémon evolves into?
We can use a variable to find this out.
evolution(bulbasaur,X)? results in X = ivysaur.
evolution(venusaur,X)? results in no (Venusaur cannot evolve, and for the more serious Pokémon fans, I’m ignoring Mega Evolution).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Queries with Variables
How could we find out what a Pokémon evolves into?
We can use a variable to find this out.
evolution(bulbasaur,X)? results in X = ivysaur.
evolution(venusaur,X)? results in no (Venusaur cannot evolve, and for the more serious Pokémon fans, I’m ignoring Mega Evolution).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Queries with Variables
How could we find out what a Pokémon evolves into?
We can use a variable to find this out.
evolution(bulbasaur,X)? results in X = ivysaur.
evolution(venusaur,X)? results in no (Venusaur cannot evolve, and for the more serious Pokémon fans, I’m ignoring Mega Evolution).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Queries with Variables
How could we find out what a Pokémon evolves into?
We can use a variable to find this out.
evolution(bulbasaur,X)? results in X = ivysaur.
evolution(venusaur,X)? results in no (Venusaur cannot evolve, and for the more serious Pokémon fans, I’m ignoring Mega Evolution).
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Queries with Variables
Sometimes a query could yield multiple answers.
Example: In the query fire(X)?, X = charmander, charmeleon, charizard.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Facts with Variables
We can use variables to assign universal facts.
Example: likes(X,pomegrantes). means for all X, X likes pomegrantes.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Conjunctive Queries
We can use a comma to join multiple queries using a logical AND.
Example: The conjunctive query fire(X),flying(X)? retrieves X = charizard since Charizard is both fire- and flying-type.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Rules
Definition (Rule)
A rule is a statement of the following form:
A ← B1,B2,...,Bn
where A is the head and B1,B2,...,Bn is the body.
Rules, facts, and queries are examples of Horn caluses.
← is used to denote logical implication. A logic program is a finite set of rules.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Table of Contents
1 Imperative and Declarative Programming
2 Overview of Logic Programming
3 Basic Constructs of Logic Programming
4 Preview of Wednesday’s Lecture
5 Lab 3
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
On Wednesday, I will be covering recursion in logic programming, which is an important and powerful construct.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Table of Contents
1 Imperative and Declarative Programming
2 Overview of Logic Programming
3 Basic Constructs of Logic Programming
4 Preview of Wednesday’s Lecture
5 Lab 3
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
Imperative and Declarative Programming Overview of Logic Programming Basic Constructs of Logic Programming Preview of Wednesday’s Lecture Lab 3
Lab 3
My original plan for Lab 3 was to assign a type checker, but I’m going to save this for later.
Instead, Lab 3 is going to be exercises from the textbook The Art of Prolog, which is available freely online.
Due date is Thursday, October 29 at 11:59pm. Note that Chapter 3 exercises depend on the material from the next lecture.
Michael McThrow San Jose State University Computer Science Department CS 152 – Programming Paradigms
Introduction to Logic Programming
- Imperative and Declarative Programming
- Overview of Logic Programming
- Basic Constructs of Logic Programming
- Preview of Wednesday's Lecture
- Lab 3
