% Sample Prolog code. % Can you guess how to put comments in Prolog? :-o above(X,Y) :- on(X,Y). above(X,Z) :- on(X,Y), above(Y,Z). pyramid(X) :- not(block(X)). on(a,b). on(b,c). on(c,d). % Other kinds of well-formed Prolog clauses: on(a,X) :- pyramid(X); X = b. on(a,b) :- (on(b,c); on(c,d)), on(a,c). % ------ Examples of INVALID Prolog clauses: % on(a,b), on(b,c) :- on(d,c). : non-atomic formula on left of :- % not(on(X,Y)) :- on(Y,X). : again, non-atomic formula on left of :- % on(X,Y) :- (on(a,b) :- on(b,c)), on(a,c). : embedded ":-" not allowed. % ----- More Prolog Examples ----- owns(harry,ferari). owns(larry,spot). dog(spot). loves(harry,mary). loves(mary,larry). loves(spot,X). loves(larry,X) :- dog(X). loves(harry,X) :- owns(harry,X). %------ family relations friendof(nick,rick). friendof(rick,dick). friendof(X,Y) :- friendof(Y,X). % why should the above rule be last? % ....................................................... %------- Generic Programming examples. (don't worry about these % too much until we've talked more about inductive definitions. % The examples above all have an AI-ish flavor. But Prolog can % be used for general purpose programming as well. % linked list notation: % [] : empty list (null in java) % [H|T] : list with first element H (head, datatum), and T (next, tail) as % rest of the list. % [1,2,3] : shorthand for [1|[2|[3|[]]]]. % In Java, (integer) lists are usually represented by a class: % class list { int head; list tail }. It is very important to understand that % the tail of a list is ANOTHER list. It works just as well to invent our own % notation using lists. Pick the constant "null" as the empty list, and % "cons(H,T)" instead of [H|T] (prolog lets you use new constants and variables % without declaring them!). The [1,2,3] would be the equivalent of % "cons(1,cons(2,cons(3,null)))". We shall use the built-in prolog % notation for convenience. % Determining if something is inside a list (acutally, the built-in predicate % "member" does this also): inlist(X,[X|T]). inlist(X,[H|T]) :- inlist(X,T). % "inlist" as a predicate axiomatizes the property of list membership in the % sense that inlist(X,L) is provable from the two clauses above if AND ONLY if % X is a member of the list L (assuming L terminates in the empty list). % Taking two lists and merging them end to end (the built-in "append" does this % also): Notice that though a prolog query is simlilar to a function call, % a query does not RETURN anything except true or false. The result of the % computation is stored in one of the variables that the interpreter instantiates. % This is called "relational programming" as opposed to functional and imperative % programming used in Java. % We want "merge" to be axiomatized so that "merge(A,B,C)" holds if and only if % C is the result of merging lists A and B: merge([],L,L). merge([H|T],L,[H|M]) :- merge(T,L,M). % The first clause states that merging the empty list onto a list has no effect. % The second clause says, the result of merging a list of the form [H|T] onto % a list L is of the form [H|M] where M is the result of (recursively) merging % T onto L. % finding the smallest number in a list of numbers: % Want: "min(X,L)" if and only if X is the smallest number in list L: min([X],X). % the smallest number of a singleton list is the single element min([A,B|T],M) :- (A < B), min([A|T],M). min([A,B|T],M) :- (B =< A), min([B|T],M). % reversing a list: % Want: "reverse(A,B)" iff A is the reverse of list B. reverse([],[]). reverse([H|T],L) :- reverse(T,S), merge(S,[H],L). % Deleting all occurance of an element from a list: % Want: "delete(X,L,M)" iff M is L with all occurences of X removed: delete(X,[],[]). delete(X,[X|T],R) :- delete(X,T,R). delete(X,[H|T],[H|R]) :- not(X = H), delete(X,T,R). % Removing duplicates % Want "remdups(L,M)" iff M is L with all duplicate elements removed - e.g, % remdups([3,4,3,5],X) will return true with X = [3,4,5]: remdups([],[]). remdups([H|T],[H|R]) :- delete(H,T,S), remdups(S,R). % Just as these axioms has a natural declarative interpretation, they can % also be given a procedural interpretation because of the manner in which % the clauses are written. The first clause says to terminate the procedure % at the empty list (because the result of removing duplicates from the % empty list is the empty list). The second clause says, procedurally, that % to remove duplicates from a non-empty list of the form [H|T], we first % delete all occurences of H from T, recording the result in S. Then we % (recursively) remove all duplicates from S, recording the result in R. % The final result of removing duplicates from [H|T] will be [H|R]. % Compare delete and remdups with the Java equivalents: note the similarities! % class intlist {int H; intlist T;} % % public class stuff_about_lists { % % intlist delete(int X, intlist L) % { if (L == null) return null; % else if (X == L.H) return delete(X,L.T); % else { L.T = delete(X,L.T); % return L; } % } % % intlist remdups(intlist L) % { if (L == null) return null; % else { L.T = remdups(delete(L.H,L.T)); % return L; } % } % } // end of stuff_about_lists % The major differences between the Java and the Prolog renditions are % that: % 1. java uses functions instead of relational predicates. % 2. as a consequence of the above, prolog tends to use separate % clauses instead of a single function with if-else statements. % 3. java is object-oriented, so we need to use classes, while % prolog can use the simpler, algebraic notation as in "[H|T]". % 4. we have to declare types (int, intlist) in java. % 5. java uses "assignment" as in L.T = delete(X,L.T), while prolog % avoids this "imperative" feature. The java version may seem more % efficient because it modifies the same list instead of creating new % ones. But this kind of optimization can be performed by the compiler % also, so the prolog version is not necessarily inefficient. % But the ALGORITHMS, and the LOGIC, are the same!