Introduction (Kannan Govindarajan and Ken Regan, 1995) ------------ There is evidence that we human beings reason most naturally in Disjunctive normal form ie in OR's of And's an eg would be (a1^a2^a3)v(b1^b2)... where ^ and V or each term in () is called a clause. BNF has the form: ::= | "(" "," "," ")" ::=any item. So the btree defn looks like a OR of AND's , hence it is in BNF. In a record or class, we conjoin all the fields to make up an object and that's another kind of AND. For a simple record there is no OR, but a variant record where OR comes in Another eg, this time using ML English: A shape cann be a rectangle OR a circle OR a Triangle. A rectangle is represented using a width,height. and so on In ML datatype Shape= Rectangle of int*int | Circle of real*real | Triangle of int*int This is also in DNF. Prolog applies the OR-of-AND idea directly to logic, in order to define a goal rather than an object. grandfather(X,Y) :- father(X,Z),parent(Z,Y). here :- means if , means AND parent(X,Y) :- mother (X,Y). parent(X,Y) :- father (X,Y). Since we have two identifiers with the same name, it implies an OR in prolog. The idea of prolog is that one can define your goals, and prolog will execute pattern matching(unification) to try to realize them---a little like ML's pattern matching. Case Sensitivity of prolog -------------------------- Prolog is case sensitive. lowercase---facts, like an ML datatype constructor (but note that current style is to make ML datatype tycons uppercase, like "Node"/ uppercase---variables. The minimum requirement is that the first letter of the variable is uppercase. Simple Arithmetical Assignment Statements ----------------------------------------- Consider A is B+C; If B and C are instantiated, then A is instantiated with value of B+C, otherwise this clause /fails/. This is different from = operator. Hence Sum=Sum+Number is never useful and will fail on the first time through the loop. Lists in Prolog --------------- syntax for a sample list: [apple, grapes] [] empty lists [X | Rest] X is the head of the list, Rest is the rest of the list same as ML's X::Rest, In lisp (first list) or (Car list) ==X and (rest list) or (cdr list) == Rest, where list is [X|Rest] We can also create lists using the notation [X|Y], which returns a list X::Y. This can be done anywhere inside a predicate. The following are equivalent [a,b,c|[]] [a,b|[c]] [a|[b,c]] In prolog, like ML, _ means don't care (There is a built-in predicate (NB: a predicate is called a "structure" in the text) "list" that can be used to have Prolog remember that list ([a,b,c]). The main purpose is that it can be unpacked using a structured rule such as list ([X | Rest]) :- .... This is similar to ML's fun foo(X::Rest) = ...) Resolution order control. ------------------------ Since prolog is a declarative language, the order of placing the clauses shouldnt' matter. But unfortuanately it does in prolog. Below are illustrated some of the places it could matter. The programmer can reorder the database for efficiency as it is depth first search. Prolog matches a database from top to bottom. So the clauses at the top get hit first. ancestor(x,y):-parent(x,y). Infinite loops. goes into an infinite loop, as f calls f calls f ... f(X,Y):-f(Z,Y),g(X,Z). This can be solved by reordering: f(X,Y):-g(X,Z),f(Z,Y). It is considered good prog practice to place the recursive clauses to the end of the programming ! operator - is called the cut operator. This means that the prolog system won't backtrack before the !. For eg. p(x):-h(x),!,g(x). It first matches the clause h(x), then tries to match g(x). If it fails it does'nt backtrack beyond !. So the ! specifies a flow of control, which is a bad thing in a language like prolog. In declarative languages, ideally, one should specify the clauses, and expect the system to find an answer. One should not use cuts, as it tampers with flow of control, undesirable in logic prog languages. generate and test paradigm -------------------------- eg. p(x):- generatesolution(x,y), test(x,y). Negation problem ---------------- not isn't the same as the boolean not. not(not(true))=true in boolean logic but not in prolog. Here not is negation as failure. This means that it negates the success/failure of a clause. This is different from boolean not. sibling(X,Y):-parent(M,X),parent(M,Y),not(X=Y). works as expected. but in not(not(member (X,[a,b,c]))). first X=mary, returns yes then returns no(because of the second not) then returns yes, with x=uninstatniated, as it uninstantiates all vars in goals that fails, Declarative style has less moving parts compared to imperative languages. This means we specify less of flow of control, ie we don't specify loops, iterators etc. Pure logic vs prolog -------------------- In oure logic the statement X is an ancestor of Y if x is the ancestor of z and z is the parent of y. Translated into first order pred calculus, becomes There exits a Z st x=ancestor(z) and z=parent(y). Note that the order does'nt matter. When translated into prolog however ancestor(x,y):-ancestor(x,z),parent(z,y). ancestor(x,y):-parent(x,y). is doubly out of order. The correct way to write it in prolog without going into infinite loops is: ancestor(x,y):-parent(x,y). ancestor(x,y):-parent(z,y),ancestor(x,z). The sumlist example in prolog ----------------------------- Using KWR's, redundant case syntax(for ML) fun sumlist(L)=case L of nil=>0; | x::rest = x+sumlist(rest); Using pattern matching on the function identifier name fun sumlist(nil)=0 | sumlist(x::rest)=x+sumlist(rest); note that neither of these are tail recursive as + is the last operator. For a tail recursive function, the last evaluated function should be the recursive call to itself. To do this in prolog one cannot do: /** WRONG: "sumlist" is being thought of as an operation, not a relation. */ sumlist([],Total). sumlist([X|Rest],Total):- Total is Total+X, sumlist(Rest,Total). as total is not instantiated the first time through the loop. The chief thing to note with Prolog patterns is that variables in patterns are both *read from* and *written to*, whereas in ML they are only written to. So one should do: sumlist([X|Rest],Total):- Total is 0, sumlist2([X|Rest],Total). sumlist2([],Total). sumlist2([X|Rest],Total):- Total is Total+X, sumlist2(Rest,Total). so that total is first initialized to 0. Prolog functions do not have return values like in ML---instead, they implicitly return values by pattern-matching. With the standard Prolog convention that variables whose intent is to receive the final answer come last (and as discussed in Ada in the very first week of term, one should try to avoid reading from them), this has the same look and working /as accumulator-passing style/. Prolog is more declarative than ML. but still have to think about pattern matching and how it would solve(using depth first). Prolog matches the first clause, then the second and so on. This is a depth first search. If it cannot match a clause it goes back to the previous clause. This is called backtracking. Better way: /** Total is the sum of the integers in the list L. Declarativelaratively, Total is the sum of the integers in the list L. sumlist3(L; Total): ^^^^ The ";" as a /comment/ separates out from in. */ sumlist3([],0). sumlist3([X | Rest], Total) :- % Y is Total + X %BAD: rhs of "is" are "in" quantities, but Total is "out"` sumlist3(Rest, RecTotal), %% should insert "cut !", OK to omit here. Total is RecTotal + X. %% last clause must end with .