Programming Languages 2e Tucker and Noonan Chapter 15 part 2 Logic Programming Q: How many legs does a dog have if you call its tail a leg? A: Four. Calling a tail a leg doesnt make it one. Abraham Lincoln Review Prolog is a logic-based language

Its syntax is based on Horn clauses, a predicate form derived from the predicate calculus. It is also a declarative language Prolog programs describe goals and provide facts and rules for the Prolog system to use in searching for a goal solution. Compare to imperative languages, which describe algorithms and specify the exact steps required to achieve a goal.

Review Propositions: statements which are either true or false; e.g., my dog is black Propositions can be represented by symbols, combined with logical operators, and have truth values based on the individual propositions; e.g. p q is true only if both p and q are true. Predicates: Propositions with variables, and/ or quantifiers: (for all) for all) (for all) there exists) x(for all) dog(for all) x) black(for all) x)); (for all) x)(for all) dog(for all) x) black(for all) x))

Review: Basic Program Elements A Prolog program consists of terms: Atoms: literal strings or numbers Variables: consist of letters and underscores, must start with an upper-case letter Atoms are distinguished from variables because atoms start with a lower-case letter Prolog variables arent the same as variables in imperative languages; they dont represent values. They are temporarily bound to objects/values during resolution.

Structures: functor(for all) parameters) Structures are predicates Review: Facts and Rules Prolog facts are headless Horn clauses: student(for all) jack, cs424). sweet(for all) sugar). Prolog rules are headed Horn clauses: fattening(for all) X) :- sweet(for all) X).

driversLicense(for all) X) :- sixteen(for all) X), passTest(for all) X). Review: Queries Prolog programs consist of facts and rules. Users describe goal states by posing queries. Goals are described by assertions that state the characteristics of the desired goal. Using the facts and rules in the program, the Prolog system attempts to find a

solution to the query. Review Prolog uses resolution theorem proving, instantiation, and unification to find goal states. The search process is a backtracking approach: in case one goal cannot be satisfied, back up to the nearest previous goal state and try another approach.

Example Suppose a program has these facts & rules: mother(for all) sue). mother(for all) jane). female(for all) X) :- mother(for all) X).

To prove/disprove the goal female(jane). First find the fact mother(sue). Reject. Next find mother(jane). Matches on jane Unify mother(for all) X) in the rule and mother(for all) jane) in the fact (for all) by instantiating X with jane) to infer female(for all) jane). Breadth-first v Depth-first Search Suppose a query has compound goals (for all) several propositions must be satisfied)

Depth-first searches prove the first goal before looking at the others. Breadth-first works on goals in parallel. Prolog uses the depth-first approach. Backtracking When a compound goal is being proved, it may be that a subgoal cannot be shown true. In that case, Prolog will back up and try to find another solution to a previous

subgoal. * A Partial Family Tree Figure 15.3 A Small Family Tree Figure 15.4 Processing Queries ?- father(X, sue)

The query is satisfied with the first comparison. X is instantiated with john. ?- mother(sue, X) Satisfied with X = nancy, X = jeff ?- mother(alice, ron) Fails ?- grandparent(Who, ron). Instantiating grandparent rule from query: Grandparent(Who,ron):parent(Who,X),parent(X,ron). First, find a fact that satisfies parent (for all) Who,X)

This entails finding a fact to satisfy either father (Who, X) or mother(Who, X) First try: father(for all) john, sue) - father rule is first Next, find a fact that satisfies parent(sue, ron) This does not succeed, ?- grandparent(Who, ron). Must satisfy both subgoals with same values Grandparent(Who,ron):parent(Who,X),parent(X,ron). The first attempt, instantiating parent(for all) Who, X) as

parent(for all) john,sue), failed because the second subgoal, parent(for all) sue,ron), could not be proved. Backtrack to parent(for all) Who, X) and use father(for all) john, bill) fact next. Instantiate Who=john, X=bill, and try to satisfy second subgoal, parent(for all) bill, ron). Success; because father(for all) bill, ron) is a fact. Who = john, so grandparent(for all) john, ron) Prolog Lists The list is Prologs basic data structure Lists are a series of Prolog terms,

separated by commas Each list element can be a(for all) n) atom variable sublist etc. Examples of Lists The empty list: [] List with embedded list: [girls, [like, boys]]

List with variables: [x, V1, y, V2, [A, B]] V1, V2, A, and B are variables that may be instantiated with data at a later time. Multi-type lists: [A, _, Z] [boy, [1, 2, 3], ran] The _ means dont care sometimes referred to as

an unbound variable. Working with Lists [Head|Tail] notation simplifies processing: Head represents the first list element, Tail represents everything else. Head can be any Prolog term (for all) list, variable, atom, predicate, etc.) If L = [a, b, c] then Head = a and Tail = [b,c] Tail is always another list. What is the head of [a]? The tail?

The append Function append is a built-in Prolog function that concatenates two lists. append(A, B, L) concatenates the lists A and B and returns them as L. append([my, cat], [is, fat], L). yields L = [my, cat, is, fat]

The Append Function append(for all) L1, L2, L3): append([], X, X). %base case append([Head|Tail], Y, [Head|Z]) :- append(Tail, Y, Z). This definition says: The empty list concatenated with any list (for all) X) returns an unchanged list (for all) X again). If Tail is concatenated with Y to get Z, then a list one element larger [Head | Tail] can

be concatenated with Y to get [Head | Z]. ?- Append(for all) [english, russian], [spanish], L). H=english, T=[russian], Y=[spanish], L=[english,Z] 1 and Z = [russian, spanish] Append(for all) [russian],[spanish], [Z]). H = russian, T=[ ], Y=[spanish], Z=[russian|Z1] 2 Append(for all) [ ], [spanish], [Z1]). So Z1= [spanish]

X=[spanish], Z1=[spanish] 3 Append(for all) [ ], [spanish], [spanish]). Recursion/ member The function returns yes if x is a member of a given list. member(for all) X, [X | _ ]). member(for all) X, [ _ | Y]) :- member(for all) X, Y). Member(for all) X,Y)

The test for membership succeeds if either: X is the head of the list [X |_] X is not the head of the list [_| Y] , but X is a member of the list Y. Notes: pattern matching governs tests for equality. Dont care entries (for all) _) mark parts of a list that arent important to the rule.

Using append prefix(for all) X, Z) :- append(for all) X, Y, Z). (for all) finds all prefixes of a list Z) suffix(for all) Y, Z) :- append(for all) X, Y, Z). (for all) finds all suffixes of Z) Naming Lists Defining a set of lists: a(for all) [single]). a(for all) [a, b, c]). a(for all) [cat, dog, sheep]).

When a query such as a(for all) L), prefix(for all) X, L). Is posed, all three lists will be processed. Other lists, such as b(for all) [red, yellow, green]), would be ignored. A Sample List Program a([single]). a([a, b, c]). a([cat, dog, sheep]). prefix(X, Z) :- append(X, _, Z). suffix(Y, Z) :- append(_, Y, Z).

% To make queries about lists in the database: % suffix(X, [the, cat, is, fat]). % a(L), prefix(X, L). Sample Output ?- a(L), prefix(X, L). L = [single] X = [] ; Based on the program on

the previous slide: a(for all) [single]). a(for all) [a, b, c]). a(for all) [cat, dog, sheep]). prefix(for all) X, Z) :- append(for all) X, _, Z). suffix(for all) Y, Z) :- append(for all) _, Y, Z). L = [single] X = [single] ; L = [a, b, c] X = [] ;

L = [a, b, c] X = [a] ; L = [a, b, c] X = [a, b] ; L = [a, b, c] X = [a, b, c] ; L = [cat, dog, sheep] X = [] Sample Output 35 ?- a(L), append([cat], L, M).

L = [single] M = [cat, single] ; L = [a, b, c] M = [cat, a, b, c] ; L = [cat, dog, sheep] M = [cat, cat, dog, sheep] ; The Trace Function To see the dynamics of a function call, use the trace function. For example,given the following function: factorial(0, 1).

factorial(N, Result):N > 0, M is N-1, factorial(M, SubRes), Result is N * SubRes. %is ~ assignment ?- trace(for all) factorial/2). Tracing Output

?- factorial(4, X). Call: ( 7) factorial(4,

Call: ( 8) factorial(3, Call: ( 9) factorial(2, Call: ( 10) factorial(1, Call: ( 11) factorial(0, Exit: ( 11) factorial(0, Exit: ( 10) factorial(1, Exit: ( 9) factorial(2, Exit: ( 8) factorial(3, Exit: ( 7) factorial(4, X = 24

These are temporary variables _G173) _L131) _L144) _L157) _L170) 1) 1)

2) 6) 24) These are levels in the search tree Logic Programming 15.2.2: Practical Aspects 15.3: Example Applications

Simple Arithmetic Integer variables and integer operations are possible, but imperative language assignment statements dont exist. Sample Program

speed(for all) fred, 60). speed(for all) carol, 75). time(for all) fred, 20). time(for all) carol, 21). distance(for all) X, Y) :- speed(for all) X, Speed), time(for all) X, Time), Y is Speed * Time. area_square(for all) S, A) :- A is S * S. Prolog Operators is can be used to cause a variable to be

temporarily instantiated with a value. Does not have the same effect as an assignment statement, because the effect isnt permanent. The not operator is used to indicate goal failure. For example not(P) is true when P is false. Arithmetic Originally, used prefix notation +(for all) 7, X) Modern versions have infix notation

X is Y * C + 3. Qualification: Y and C must be instantiated, as in the Speed program, but X cannot be (for all) Its not a traditional assignment statement). X = X + Y is illegal. X is X + Y is illegal. Arguments are not sufficiently instantiated More About Arithmetic Example of simple arithmetic

?- x is 3 + 7. x = 10 Yes Arithmetic operators: +, -, *, /, ^ (for all) exponentiation) Relational operators: <, >, =, =<, >=, \= Revisiting the Trace Function At the prompt, type trace. Then type the query. Prolog will show the rules it uses and the

instantiation of unbound constants. Revisiting The Factorial Function Evaluation of clauses is from left to right. Note the use of is to temporarily assign values to M and Result Trace of Factorial (4) Other Features

cut (for all) !) controls backtracking not(for all) ) negation assert(for all) C) add to database retract(for all) C) removes from database The cut & not Operators The cut (for all) !) is used to control backtracking.

It tells Prolog to stop at this point (for all) if the goals have succeeded once). Reasons: Faster execution, saves memory Not(P) will succeed when P fails. In some places it can replace the ! Operator. Example: Revised Factorial factorial(N, 1):- N < 1, !. factorial(N, Result):- M is N 1, factorial(M, P), Result is N * P.
factorial(N, 1):- N < 1. factorial(N, Result):- not(N < 1), M is N1, factorial(M, P), Result is N * P. When Cut Might Be Used (for all) Clocksin & Mellish) To tell Prolog that it has found the right rule:
if you get this far, you have picked the correct rule for this goal. To tell Prolog to fail a particular goal without trying other solutions: if you get to here, you should stop trying to satisfy the goal.

if you get to here, you have found the only solution to this problem and there is no point in ever looking for alternatives. f(for all) X, 0) :- X < 3, !. f(for all) X, 2) :- 3 =< X, X < 6, !. f(for all) X, 4) :- 6 =< X. 14 ?- consult(for all) 'C:/Temp/prologProgs/cut_example.pl'). % C:/Temp/prologProgs/cut_example.pl compiled 0.00 sec, 8 bytes true
15 ?- f(for all) 1, Y), 2 < Y. false 16 ?- X = 4, f(for all) X, Y), 2 < Y. false ?- X = 4, f(for all) X, Y). X = 4, Y = 2. Since the three rules above are mutually exclusive, once one rule succeeds there is no need to try another. In the first example, rule 1 succeeds (for all) X < 3). If we try rules 2 and 3 they will fail. In the second case (for all) X = 4) the second rule succeeds.
The cut symbol prevents further attempts that will fail anyway. Family Tree Assert(for all) ) 15 ?- child(for all) jeff). ERROR: Undefined procedure: child/1 16 ?- assert(for all) child(for all) jeff)). Yes 17 ?- child(for all) jeff). Yes Assert and Retract

More sophisticated uses: assert can be embedded in a function definition so new facts and rules can be added to the database in real time. Useful for learning programs, for example. Retract(for all) C) deletes a clause that matches C Symbolic Differentiation Rules Figure 15.9

Prolog Symbolic Differentiator Figure 15.10 Search Tree for the Query d(x, 2*x+1, Ans) Figure 15.11 Executing a Prolog Program Create a file containing facts and rules; e.g., familytree.pl or download the sample program from the class web page.

From the Start menu select SWI-Prolog/Prolog Under the file drop-down menu select consult to load the file into the interpreter. From the Start menu select consult and browse to the file you want to execute. Double click and it will compile and be ready to query. Type queries and the interpreter will try to find answers ?- owner(for all) X, Y). See the web page for more complete instructions.

SWIplEdit compile error If SWI-Prolog finds an error in the .pl file it will give a message such as ERROR: c:/temp/prologprogs/remove.pl: 18:0: Syntax error: Illegal start of term (for all) 18 is the line number) Runtime Error Message The function samelength was called with

one parameter when it needed 2: 21 ?- samelength(X). ERROR:Undefined procedure: samelength/1 ERROR:However, there are definitions for: samelength/2 Runtime Errors Here, the error is an error of omission: 22 ?- samelength([a, b, c,],[a, b]) |

Queries must end with a period. If you hit enter without typing a period SWIpl just thinks you arent through. Using SWI Prolog If there is an error that you cant figure out (for all) for example you dont get any answers, you dont get a prompt, typing a semicolon doesnt help) try interrupt under the Run button.

If changes are made to the program, dont forget to consult again. Test Review

Chapter 5 (for all) Last Half) Chapter 6.1 (for all) Type Systems) Chapter 7.1-7.5 (for all) Semantics) Chapter 12 (for all) Imperative Programming) Chapter 13: (for all) Object Oriented Programming) Chapter 15 (for all) Logic Programming) Python & Scripting Languages (for all) from the notes). Homework Questions I Might Have Assigned

In C-like languages, when an expression consists of two or more sub-expressions , such as a + f(for all) a) or x*y + x*y++ or x/3 y + 4(for all) x+y), the sub-expressions are evaluated Left-to-right

Right-to-left It depends on the precedence of the operators in the sub-expression It depends on the compiler. Homework Questions I Might Have Assigned - Functions 1 int a = 0; .. 11 int newVal(for all) int c) 12 {

.. 19 void main (for all) ) .. 24 return 0; 25 } ----------------------------------------- Show the stack of activation records as it would exist when line 8 has executed but before line 9 executes. Your answer should follow the format in Figure 9.8

Show the stack again after the execution of line 23, but before the main function terminates. Homework Questions I Might Have Assigned Consider the following Horn clauses: parent(X, Y):- father(X, Y). grandparent(X,Z):- parent(X,Y), parent(Y,Z).

Use resolution, as in Prolog, to deduce a new proposition from the two above Homework Questions I Might Have Assigned Write a rule for the family tree data base that defines a sister relation For example the sister of X has the same father or mother.