09 - Prolog.pdf

CSCI 3137 - Principles of Programming Languages 9 - Logic Programming with Prolog 1  Introducing SWI-Prolog SWI-Prolog is a free implementation of Prolog developed at the University of Amsterdam. You can downloa...

CSCI 3137 - Principles of Programming Languages 9 - Logic Programming with Prolog 1  Introducing SWI-Prolog SWI-Prolog is a free implementation of Prolog developed at the University of Amsterdam. You can download and install binaries for most systems from http://swi-prolog.org Or you can use SWISH, a web-based implementation available at http://swish.swi-prolog.org SWI-Prolog files have a.pl extension 2  Prolog Programs Functional programming languages like Scheme express computation as a system of functions. Logical programming languages like Prolog express predicates of objects and relations between objects. A program in Prolog consists of: A set of facts, predicates and relations that are known (or defined) to be true. A set of rules, predicates and relations that are true if other predicates or relations are true. 3  Querying a Prolog Program Prolog programs aren’t executed in the traditional sense. Instead, one queries a Prolog program to determine if some statement can be proven based on the given facts and rules. plus(Addend1, Addend2, Sum). is a built-in Prolog predicate that is true iff Addend1 + Addend2 = Sum ?- plus(1, 2, 3). is a query that asks: Is the statement 1 + 2 = 3 true? ?- plus(1, 2, Sum). is a query that asks: What value(s) of Sum make the statement 1 + 2 = Sum true? How about: ?- plus(Addend1, 2, 3). 4  Atoms Atoms are mere tokens. They represent whatever the programmer intends for them to represent. The atom socrates only has meaning because the programmer has decided that it does. It could refer to an ancient Greek philosopher, Or it could refer to my cat. Atoms can be constructed in three ways: String of letters, digits, underscores starting with a lowecase letter. Strings of special characters. (Some strings of special characters have predefined meanings) Strings of characters enclosed in single quotes. 5  Numbers Numbers in Prolog include integers, and real numbers (IEEE 754) Prolog is primarily used for symbolic computation so while integers are often used (for counting and indexing), real numbers see much less use in Prolog programs. 6  Compound Terms Compound Terms consist of a name (which is an atom) and one or more arguments (which can be arbitrary Prolog objects). The number of arguments a compound term has is called its arity. The compound term plus(1, 2, 3) has arity 3. The compound term f(a, b) has arity 2. In documentation, you will often see plus/3 or f/2 which is a shorthand. Like atoms, terms only have meaning because the programmer decides that they do. 7  Variables Start with an uppercase letter, or the underscore _ and consist of letters, digits, and underscores. They don’t have a fixed identity (like a memory address). Variables are local to the fact, rule, or query in which they appear. Behave more like placeholders than variables in imperative languages like C and Java. Once they are bound to a value, that value cannot be replaced (without backtracking). Does Prolog use a value model or a reference model of variables? 8  The Anonymous Variable The variable _ is known as the anonymous variable. The anonymous variable behaves like a wildcard. So, the query: ?- plus(_, 2, 3). is a query that asks: Is there a value of _ that makes the statement _ + 2 = 3 true? Each instance of the anonymous variable _ is distinct, so: ?- f(A, A) = f(a, b). is false, because A cannot be bound to a and b simultaneously, but ?- f(_, _) = f(a, b). is true, because each _ is considered a distinct variable. 9  Core Concept: Unification Unification is like a combination of equality and assignment. Rules of unification: A constant (atom or number) can be unified with itself. A free (unbound) variable can be unified with anything. (this binds the variable) A bound variable can only be unified with the object to which it is bound. When two free variables are unified they become a single free variable with multiple names. A compound term can be unified with another compound term with the same name and arity, provided that corresponding arguments can also be unified. 10  Unification of Constants A constant (atom or number) can be unified with itself. In this way, unification behaves like a test for equality. a = a or 5 = 5 (here, the = is the unification operator) a \= b or 5 \= 7 (here, the \= is the cannot-be-unified operator) 11  Unification of an Unbound Variable A free (unbound) variable can be unified with anything. (this binds the variable) In this way, unification behaves like assignment. But there isn’t a notion of l-values and r-values. So A = a and a = A are equivalent. Both bind the variable A to the atom a Note that (if A is unbound) A \= a fails because the variable A can be bound to the atom a 12  Unification of a Bound Variable A bound variable can be unified with the object to which it is bound. Lets assume that the variable A has been bound to the atom a. Then, for the purposes of unification, A behaves like a. So A = B would bind the variable B to the atom a. And A = a would succeed since it is equivalent to a = a. 13  Unification of Two Unbound Variables When two free variables are unified they become a single free variable with multiple names. So A = B causes both A and B to refer to the same object. Even if we don’t know what that object is yet! 14  Unification of Compound Terms A compound term can be unified with another compound term with the same name and arity, provided that corresponding arguments can also be unified. So f(a) = f(a) is true f(a) = f(a, b) is not true since the terms have different arity f(a) = g(a) is not true since the terms have different names f(a) = f(A) causes the variable A to be bound to the atom a But what about: f(A, b) = f(a, A)? 15  Unification of Compound Terms But what about: f(A, b) = f(a, A)? They have the same name, and arity But their arguments cannot be unified. Attempting to unify their first arguments would bind the variable A to the atom a Attempting to unify their second arguments would bind the variable A to the atom b The variable A cannot be bound to two different objects 16  Facts Facts express non-conditional statements that are true. They are represented in a program as terms followed by a period:. Examples: parent(marge, maggie). : marge is a parent of maggie parent(marge, lisa). : marge is a parent of lisa parent(marge, bart). : marge is a parent of bart 17  Rules Rules express mechanisms for deriving new facts from known facts. They have the form: head :- term_1, term_2,..., term_n. head is true if all of term_1, term_2,... term_n are true. Example: grandparent(GP, GC) :- parent(GP, P), parent(P, GC). GP is a grandparent of GC if there is a value of P such that GP is a parent of P and P is a parent of GC 18  Query Resolution Prolog resolves a query by finding facts or rules that can be unified with the given query (goal). If a query can be unified with a fact, then that query is true. ?- parent(marge, maggie). If a query can be unified with a rule’s head, then the rule’s body becomes the new goal (subgoal). ?- grandparent(jackie, bart). ?- parent(jackie, P), parent(P, bart). ?- parent(jackie, marge), parent(marge, bart). Sometimes more than one fact or rule matches a goal this creates a choice-point If necessary, the Prolog interpreter will backtrack to a choice point 19  Query Failure When a query fails, it does not necessarily mean that the statement represented by the query is false. Only that the statement cannot be proven from the facts and rules that are included in the program. 20  Conjunction between(Min, Max, V) :- Min = Expr2 Expr1 =:= Expr2 (equal) Expr1 =\= Expr2 (not equal) Both expressions are evaluated, and their values compared 42  Arithmetic in Prolog: equality vs unification Term1 = Term2 represents term unification Expr1 =:= Expr2 represents arithmetic equality So while 1 =:= 1.0 succeeds 1 = 1.0 fails Likewise for \= vs. =\= 43  Lists in Prolog Prolog treats lists similarly to Scheme. As one (or more) head element(s) followed by a tail list. using the following notation: [H|T] A list whose first element is H and the rest of which is T [H|[]] or [H] A list with one element H [H1, H2|T] A list whose first two elements are H1 and H2 and the rest of which is T... and so on 44  List Operations in Prolog: member The member(E, L) predicate succeeds if the element E is a member of the list L 45  List Operations in Prolog: member The member(E, L) predicate succeeds if the element E is a member of the list L member(E, [E|_]). member(E, [_|T]) :- member(E, T). 46  List Operations in Prolog: select The select(E, L, R) predicate succeeds if the element E can be removed from L leaving R 47  List Operations in Prolog: select The select(E, L, R) predicate succeeds if the element E can be removed from L leaving R select(E, [E|T], T). select(E, [H|T], [H|RT]) :- select(E, T, RT). 48  Now you try: length The length(L, N) predicate succeeds if the list L has N elements 49  List Operations in Prolog: length The length(L, N) predicate succeeds if the list L has N elements length([], 0). length([_|T], N) :- length(T, TN), plus(TN, 1, N). 50  List Operations in Prolog: permutation The permutation(L1, L2) predicate succeeds if the list L1 is a permutation of the list L2 51  List Operations in Prolog: permutation The permutation(L1, L2) predicate succeeds if the list L1 is a permutation of the list L2 permutation([], []). permutation([H|T], P) :- permutation(T, PT), select(H, P, PT). 52  List Operations in Prolog: findall The findall(Template, Goal, Bag) evaluates Goal, and unifies Bag with the values of Template for each solution. ?- findall(X, grandparent(X, maggie), Grandparents). will unify Grandparents with a list of all values of X for which grandparent(X, maggie) succeeds. 53  List Operations in Prolog: maplist The maplist(G, L1, L2,... Ln) predicate succeeds if the goal G succeeds for each set of corresponding elements of L1, L2,... ?- maplist(plus(3), [1, X], [Y, 2]). will succeed if plus(3, 1, Y) and plus(3, X, 2) succeed. maplist is also often used to generate solutions ?- length(L, 3), maplist(between(0, 1), L). 54