:- module(_,_,[bf]). % :- use_package(bf). % ------------------------------------------------------------------- % First program: pets database. pet(X) <- animal(X), barks(X). pet(X) <- animal(X), meows(X). animal(spot) <- . animal(barry) <- . animal(hobbes) <- . barks(spot) <- . meows(barry) <- . roars(hobbes) <- . % Some queries: % pet(spot). % pet(X). % ------------------------------------------------------------------- % Family database: father_of(john, peter) <- . father_of(john, mary) <- . father_of(peter, michael) <- . mother_of(mary, david) <- . grandfather_of(L,M) <- father_of(L,N), father_of(N,M). grandfather_of(X,Y) <- father_of(X,Z), mother_of(Z,Y). % Some queries: % % father_of(john,peter). father_of(john,david). % father_of(john,X). grandfather_of(X,michael). % grandfather_of(X,Y). grandfather_of(X,X). parent(X,Y) <- father_of(X,Y). parent(X,Y) <- mother_of(X,Y). ancestor(X,Y) <- parent(X,Y). ancestor(X,Y) <- parent(X,Z), ancestor(Z,Y). % queries: ancestor(john,michael). (Is John ancestor of michael?) % ancestor(john,elisabeth). (Is john ancestor of elisabeth?) % ancestor(john,X). (John's successors) % ancestor(X,elisabeth). (Elisabeth's ancestors) % ancestor(X,michael). (Michael's ancestors) % Exercises: related(X,Y) <- ancestor(Z,X), ancestor(Z,Y). % queries: related(peter,mary). % related(peter,david). % related(mary,elisabeth). % related(michael,mary). % related(peter,X). % related(john,peter). (john is not related to peter!) ancestor2(X,X) <- . ancestor2(X,Y) <- parent(X,Z), ancestor2(Z,Y). related2(X,Y) <- ancestor2(Z,X), ancestor2(Z,Y). % queries: related2(john,peter). (it works!) % related2(peter,X). (duplicated answers!) % ------------------------------------------------------------------- % Circuit: resistor(power,n1) <- . resistor(power,n2) <- . transistor(n2,ground,n1) <- . transistor(n3,n4,n2) <- . transistor(n5,ground,n4) <- . % ------------------------------------------------------------------- % Circuit theory: inverter(Input,Output) <- transistor(Input,ground,Output), resistor(power,Output). nand_gate(Input1,Input2,Output) <- transistor(Input1,X,Output), transistor(Input2,ground,X), resistor(power,Output). and_gate(Input1,Input2,Output) <- nand_gate(Input1,Input2,X), inverter(X, Output). % Some queries: % and_gate(In1,In2,Out). % nand_gate(In1,In2,Out). % inverter(In,Out). % resistor(In,Out). % ------------------------------------------------------------------- % Course info: course(complog,Time,Lecturer, Location) <- Time = t(mond,18:30,20:30), Lecturer = lect('M.','Hermenegildo'), Location = loc(new,5102). % Some queries: % course(complog,Time, A, B). % course(complog,Time, _, _). % ------------------------------------------------------------------- % Circuit (with structure): %% named_resistor(res(P1,P2),P1,P2) <- resistor(P1,P2). %% named_transistor(trans(P1,P2,P3),P1,P2,P3) <- transistor(P1,P2,P3). named_resistor(r1,power,n1) <- . named_resistor(r2,power,n2) <- . named_transistor(t1,n2,ground,n1) <- . named_transistor(t2,n3,n4,n2) <- . named_transistor(t3,n5,ground,n4) <- . named_inverter(inv(T,R),Input,Output) <- named_transistor(T,Input,ground,Output), named_resistor(R,power,Output). named_nand_gate(nand(T1,T2,R),Input1,Input2,Output) <- named_transistor(T1,Input1,X,Output), named_transistor(T2,Input2,ground,X), named_resistor(R,power,Output). named_and_gate(and(N,I),Input1,Input2,Output) <- named_nand_gate(N,Input1,Input2,X), named_inverter(I,X,Output). % Some queries: % named_inverter(Inv,I,O). % named_nand_gate(G,In1,In2,Out). % named_and_gate(G,In1,In2,Out). % named_resistor(R1,P1,P2). % named_transistor(T1,P1,P2,P3). % ------------------------------------------------------------------- % Relational database: person(brown,20,male) <- . person(jones,21,female) <- . person(smith,36,male) <- . person2(cabeza,33,male) <- . person2(bueno,39,male) <- . person2(jones,21,female) <- . lived_in(brown,london,15) <- . lived_in(brown,york,5) <- . lived_in(jones,paris,21) <- . lived_in(smith,brussels,15) <- . lived_in(smith,santander,5) <- . % Union: all_persons(Name,Age,Sex) <- person(Name,Age,Sex). all_persons(Name,Age,Sex) <- person2(Name,Age,Sex). % Query: all_persons(Name,Age,Sex). % Difference: difference(Name,Age,Sex) <- person(Name,Age,Sex), \+ person2(Name,Age,Sex). difference(Name,Age,Sex) <- person2(Name,Age,Sex), \+ person(Name,Age,Sex). % Query: difference(Name,Age,Sex). % Cartesian Product: person_X_lived_in(Name1,Age,Sex,Name2,Town,Years) <- person(Name1,Age,Sex), lived_in(Name2,Town,Years). % Query: person_X_lived_in(Name1,Age,Sex,Name2,Town,Years).o % Projection: city(C) <- lived_in(_,C,_). % Query: city(C). % Selection: underage_person(Name,Age,Sex) <- person(Name,Age,Sex), Age < 21. % Query: underage_person(Name,Age,Sex). % Intersection: person_lived_in(Name,Age,Sex,Town,Years) <- person(Name,Age,Sex), lived_in(Name,Town,Years). % Query: person_lived_in(Name,Age,Sex,Town,Years). % Join: person_joinName_person2(Name,Age,Sex) <- person(Name,Age,Sex), person2(Name,_Age2,_Sex2). % Query: person_joinName_person2(Name,Age,Sex). % ------------------------------------------------------------------- % Types: is_weekday('Monday') <- . is_weekday('Tuesday') <- . is_weekday('Wednesday') <- . is_weekday('Thursday') <- . is_weekday('Friday') <- . is_weekday('Saturday') <- . is_weekday('Sunday') <- . is_day_of_month(1) <- . is_day_of_month(2) <- . % ... is_day_of_month(31) <- . is_date(date(W,D)) <- is_weekday(W), is_day_of_month(D). % Sample queries: % is_weekday(Day). % is_date(Date). % ------------------------------------------------------------------- % Recursive Types: nat(0) <- . nat(s(X)) <- nat(X). %% :- op(500,fy,s). %% :- op(500,fy,-). pint(X) <- nat(X). pint(-X) <- nat(X). less_or_equal(0,X) <- nat(X). less_or_equal(s(X),s(Y)) <- less_or_equal(X,Y). %% Multiple uses: %% less_or_equal(s(0),s(s(0))). %% less_or_equal(X,0). %% %% Multiple solutions: %% less_or_equal(X,s(0)). %% less_or_equal(s(s(0)),Y). less(0,s(X)) <- nat(X). less(s(X),s(Y)) <- less(X,Y). less_or_equal_pairs(pair(0,X)) <- nat(X). less_or_equal_pairs(pair(s(X),s(Y))) <- less_or_equal_pairs(pair(X,Y)). %% =<(0,X) <- nat(X). %% =<(s(X),s(Y)) <- =<(X,Y). %% 0 =< X <- nat(X). %% s(X) =< s(Y) <- X =< Y. plus(0,Y,Y) <- nat(Y). plus(s(X),Y,s(Z)) <- plus(X,Y,Z). %% Multiple uses: %% plus(s(s(0)),s(0),Z). %% plus(s(s(0)),Y,s(0)). %% plus(s(0),Y,s(s(s(0)))). %% %% Multiple solutions: %% plus(X,Y,s(s(s(0)))). %% plus(X,0,X) <- nat(X). %% plus(X,s(Y),s(Z)) <- plus(X,Y,Z). % ------------------------------------------------------------------- times(0,Y,0) <- nat(Y). times(s(X),Y,Z) <- plus(W,Y,Z), times(X,Y,W). %% times(s s 0, s s 0, Y). %% times(s s 0, s s 0, s s 0). %% times(s s 0, Y, s s 0). %% times(Y, s s 0, s s 0). % ------------------------------------------------------------------- % ------------------------------------------------------------------- square(X,Y) <- times(X,X,Y). %% square(s s 0, Y). %% square(X, s s s s 0 ). %% square(X, Y). % ------------------------------------------------------------------- % :- op(500,fy,s). factorial(0, 0) <- . factorial(s(0),s(0)) <- . factorial(s(N),FN1) <- nat(N), less_or_equal(s(0),N), factorial(N,FN), times(s(N),FN,FN1). % factorial(s s s 0, Z). % factorial(Z,s s s s s s 0). % ------------------------------------------------------------------- exp(0, X, s(0)) <- nat(X). exp(s(N),X,Y) <- exp(N,X,W), times(X,W,Y). %% exp(s(s(0)),s(s(0)),Y). %% exp(s(s(0)),s(s(s(0))),Y). %% exp(s(s(s(0))),s(s(0)),Y). % ------------------------------------------------------------------- mod(X,Y,Z) <- less(Z,Y), plus(W,Z,X), times(Y,_Q,W). mod2(X,Y,X) <- less(X,Y). mod2(X,Y,Z) <- plus(X1,Y,X), mod2(X1,Y,Z). %% mod(s s s s s s s s s 0, s s s s 0, Z). and ; % ------------------------------------------------------------------- ackermann(0,N,s(N)) <- . ackermann(s(M),0,Val) <- ackermann(M,s(0),Val). ackermann(s(M),s(N),Val) <- ackermann(s(M),N,Val1), ackermann(M,Val1,Val). % ackermann(s s 0, s s s 0, X). % ackermann(s s 0, s s s 0, s s s s s s s s s 0). % ackermann(s s 0, Y, s s s s s s s s s 0). % ackermann(X, s s s 0, s s s s s s s s s 0). % ------------------------------------------------------------------- list([]) <- . list([_|Y]) <- list(Y). % list( [1,2] ). % list( .(1, .(2, [] ) ) ). natlist([]) <- . natlist([X|Y]) <- nat(X), natlist(Y). %% Reverse order of body literals? % ------------------------------------------------------------------- list_member(X,[X|Y]) <- list(Y). list_member(X,[_|T]) <- list_member(X,T). %% Queries: %% list_member(b, [a,b,c]). %% list_member(X, [a,b,c]). %% list_member(a, L). % ------------------------------------------------------------------- mylength([],0) <- . mylength([_|T],s(N)) <- mylength(T,N). %% Queries: %% mylength([a, b, c], N). %% mylength(L, s(s(s(0)))). %% mylength(L, 3). %% mylength(L, N). % ------------------------------------------------------------------- prefix([],X) <- list(X). prefix([X|Xs],[X|Ys]) <- prefix(Xs,Ys). % Queries: % prefix([a,b], [a,b,c,d]). % prefix([X,Y], [a,b,c,d]). % prefix(P, [a,b,c,d]). % prefix([a,b], L). % prefix(P, L). suffix(X,X) <- list(X). suffix(X,[_|Ys]) <- suffix(X,Ys). /* Queries: suffix([c,d], [a,b,c,d]). suffix([X,Y], [a,b,c,d]). suffix(P, [a,b,c,d]). suffix([a,b], L). suffix(P, L). */ sublist(X,Y) <- suffix(Z,Y), prefix(X,Z). % Queries: % sublist([b,c], [a,b,c]). % sublist(X, [a,b,c]). % sublist([b,c], [d,a,X,Y]). % sublist(X, Y). % Other (equivalent) definition for sublist. sublist1(X,Y) <- prefix(Z,Y), suffix(X,Z). % Other definition for sublist (no repeated solutions). sublist2([],Ys) <- list(Ys). sublist2([Xs|Ts],Ys) <- prefix([Xs|Ts],Ys). sublist2([Xs|Ts], [_|Ys]) <- sublist2([Xs|Ts], Ys). %% sublist2([],Ys) <- %% list(Ys). %% sublist2(Xs,Ys) <- %% sublist2b(Xs,Ys). %% sublist2b(Xs,Ys) <- %% prefix2(Xs,Ys). %% sublist2b(Xs,[_|Ys]) <- %% sublist2b(Xs,Ys). %% %% prefix2([X],[X|Xs]) <- list(Xs). %% prefix2([X|Xs],[X|Ys]) <- %% prefix2(Xs,Ys). % ------------------------------------------------------------------- myappend([],L,L) <- list(L). myappend([X|Xs],Ys,[X|Zs]) <- myappend(Xs,Ys,Zs). %% Queries: %% %% myappend([a,b], [c], X). %% myappend(X, [c], [a,b,c]). %% myappend(X, Y, [a,b,c]). % ------------------------------------------------------------------- reverse([],[]) <- . reverse([X|Xs],Ys) <- reverse(Xs,Zs), myappend(Zs,[X],Ys). % reverse([a,b,c],X). % reverse(X,[c,b,a]). % reverse(X,Y). % ------------------------------------------------------------------- reverse2(Xs,Ys) <- reverse3(Xs,[],Ys). reverse3([],Ys,Ys) <- . reverse3([X|Xs],Acc,Ys) <- reverse3(Xs,[X|Acc],Ys). % reverse2([a,b,c],X). % reverse2(X,[c,b,a]). % reverse2(X,Y). % ------------------------------------------------------------------- binary_tree(void) <- . binary_tree(tree(_Element,Left,Right)) <- binary_tree(Left), binary_tree(Right). % Queries: % tree_example(T), binary_tree(T). % binary_tree(tree(a, b, c)). % binary_tree(tree(a, void, void)). % binary_tree(T). % ------------------------------------------------------------------- %% tree_member(X,tree(X,_Left,_Right)) <- . tree_member(X,tree(X,Left,Right)) <- binary_tree(Left), binary_tree(Right). tree_member(X,tree(_Y,Left,_Right)) <- tree_member(X,Left). tree_member(X,tree(_Y,_Left,Right)) <- tree_member(X,Right). tree_example( tree( a, tree( b, void, void ), tree( c, tree( b, void, void ), void ) )) <- . % Queries: % tree_example(_T), tree_member(b, _T). % tree_example(_T), tree_member(X, _T). % tree_example(_T), tree_member(e, _T). %-------------------------------------------------------------------- pre_order(void, []) <- . pre_order(tree(X,Left,Right), Order) <- pre_order(Left, OrderLeft), pre_order(Right, OrderRight), myappend([X|OrderLeft], OrderRight, Order). in_order(void, []) <- . in_order(tree(X,Left,Right), Order) <- in_order(Left, OrderLeft), in_order(Right, OrderRight), myappend(OrderLeft, [X|OrderRight], Order). post_order(void, []) <- . post_order(tree(X,Left,Right), Order) <- post_order(Left, OrderLeft), post_order(Right, OrderRight), myappend(OrderRight, [X], OrderRight2), myappend(OrderLeft, OrderRight2, Order). % queries: % tree_example(_T),pre_order(_T,List). % tree_example(_T),in_order(_T,List). % tree_example(_T),post_order(_T,List). (node list generation) % post_order(X,[a,b]). (tree generation) % tree_example(_T),post_order(_T,[Y|_]). (leftmost leaf) % ------------------------------------------------------------------- lt_member(X, [X|Y]) <- list(Y). lt_member(X, [_|T]) <- lt_member(X, T). lt_member(X, tree(X, L, R)) <- binary_tree(L), binary_tree(R). lt_member(X, tree(_Y, L, _R)) <- lt_member(X, L). lt_member(X, tree(_Y, _L, R)) <- lt_member(X, R). % lt_member(M,[1,2,3]). % tree_example(_T), lt_member(M,_T). % But: % lt_member(M,T). % mixed type! %-------------------------------------------------------------------- % Modification: lt_member_2 (no mixed type). lt_member_2(X, [X|Y]) <- list(Y). lt_member_2(X, [_|T]) <- list(T), lt_member_2(X, T). lt_member_2(X, tree(X, L, R)) <- binary_tree(L), binary_tree(R). lt_member_2(X, tree(_Y, L, R)) <- binary_tree(L), binary_tree(R), lt_member_2(X, L). lt_member_2(X, tree(_Y, L, R)) <- binary_tree(L), binary_tree(R), lt_member_2(X, R). % polynomial(X,X) <- . polynomial(Term,_X) <- pconstant(Term). polynomial(Term1+Term2,X) <- polynomial(Term1,X), polynomial(Term2,X). polynomial(Term1-Term2,X) <- polynomial(Term1,X), polynomial(Term2,X). polynomial(Term1*Term2,X) <- polynomial(Term1,X), polynomial(Term2,X). polynomial(Term1/Term2,X) <- polynomial(Term1,X), pconstant(Term2). polynomial(Term1^N,X) <- polynomial(Term1,X), nat(N). pconstant(X) <- nat(X). pconstant(a) <- . pconstant(b) <- . pconstant(c) <- . %% polynomial(a * x ^ s(s(0)) + b, x). %% polynomial(P, x). % ------------------------------------------------------------------- deriv(X,X,s(0)) <- . deriv(C,_X,0) <- pconstant(C). deriv(U+V,X,DU+DV) <- deriv(U,X,DU), deriv(V,X,DV). deriv(U-V,X,DU-DV) <- deriv(U,X,DU), deriv(V,X,DV). deriv(U*V,X,DU*V+U*DV) <- deriv(U,X,DU), deriv(V,X,DV). deriv(U/V,X,(DU*V-U*DV)/V^s(s(0))) <- deriv(U,X,DU), deriv(V,X,DV). deriv(U^s(N),X,s(N)*U^N*DU) <- deriv(U,X,DU), nat(N). deriv(log(U),X,DU/U) <- deriv(U,X,DU). %% deriv(s(s(s(0)))*x+s(s(0)),x,Y). %% deriv(s(s(s(0)))*x+s(s(0)),x,0*x+s(s(s(0)))*s(0)+0). %% deriv(E,x,0*x+s(s(s(0)))*s(0)+0). % ------------------------------------------------------------------- % ------------------------------------------------------------------- % Graph: % (Exercise:) % ------------------------------------------------------- % Example: Logic Database + recursion + types. % Directed graph. % % a ----> b f % | | | % v v v % c ----> d ----> e g % | % v % h % ------------------------------------------------------- edge(a,b) <- . edge(a,c) <- . edge(b,d) <- . edge(c,d) <- . edge(d,e) <- . edge(d,h) <- . edge(f,g) <- . % connected(X,Y) : There is a path from X to Y. % (transitive closure of the edge relationship). connected(X,X) <- . connected(X,Y) <- edge(X,Z), connected(Z,Y). % queries: connected(a,e). % yes % connected(a,g). % no % connected(c,X). % nodes that c is connected to. % connected(X,Y). % connected nodes. % % Observe first variable unification. % % Duplicate solutions for different paths. % ------------------------------------------------------------------- % Exercise: % Example. The power of unification + database. % Coloring a planar map with at most 4 colors. next(blue,yellow). next(blue,red). next(blue,green). next(yellow,blue). next(yellow,red). next(yellow,green). next(red,blue). next(red,yellow). next(red,green). next(green,blue). next(green,yellow). next(green,red). map_colors(R1,R2,R3,R4,R5,R6) <- next(R1,R2),next(R1,R3), next(R1,R5),next(R1,R6), next(R2,R3),next(R2,R4), next(R2,R5),next(R2,R6), next(R3,R4),next(R3,R6), next(R5,R6). % queries: map_colors(R1,R2,R3,R4,R5,R6). % ------------------------------------------------------------------- accept(S) <- initial(Q), accept_from(S, Q). accept_from([],Q) <- final(Q). accept_from([X|Xs],Q) <- delta(Q, X, NewQ), accept_from(Xs,NewQ). initial(q0) <- . final(q0) <- . delta(q0, a, q1) <- . delta(q1, b, q0) <- . delta(q1, b, q1) <- . % Queries: % accept([a,b,b]). % accept([A, B, C, D]). % accept(X). % ------------------------------------------------------------------- ndsfa_accept(S) <- ndsfa_initial(Q), ndsfa_accept_from(S, Q, []). ndsfa_accept_from([], Q, []) <- ndsfa_final(Q). ndsfa_accept_from([X|Xs], Q, S) <- ndsfa_delta(Q, X, S, NewQ, NewS), ndsfa_accept_from(Xs, NewQ, NewS). ndsfa_initial(q0) <- . ndsfa_final(q1) <- . ndsfa_delta(q0, X, Xs, q0, [X|Xs]) <- . ndsfa_delta(q0, X, Xs, q1, [X|Xs]) <- . ndsfa_delta(q0, _, Xs, q1, Xs) <- . ndsfa_delta(q1, X, [X|Xs], q1, Xs) <- . % Queries: % ndsfa_accept([a,b,b,a]). % ndsfa_accept([a,b,c,b,a]). % ndsfa_accept([a,b,c,c,b,a]). % ndsfa_accept([a,b,X,a]). % ndsfa_accept([A, B, C, D]). % ndsfa_accept(X). % % Alternative: accept only words formed with symbols of % a particular alphabet. %% ndsfa_delta_alt(q0, X, Xs, q0, [X|Xs]) <- symbol(X). %% ndsfa_delta_alt(q0, X, Xs, q1, [X|Xs]) <- symbol(X). %% ndsfa_delta_alt(q0, _, Xs, q1, Xs) <- symbol(X). %% ndsfa_delta_alt(q1, X, [X|Xs], q1, Xs) <- symbol(X). %% symbol(a) <- . %% symbol(b) <- . %% % symbol(c) <- . % % ------------------------------------------------------------------- % Move N disks from peg A to peg B using peg C. hanoi_moves(N, Moves) <- hanoi(N, a, b, c, Moves). hanoi(s(0), Orig, Dest, _Help, [move(Orig, Dest)]) <- . hanoi(s(N), Orig, Dest, Help, Moves) <- hanoi(N, Orig, Help, Dest, Moves1), hanoi(N, Help, Dest, Orig, Moves2), myappend(Moves1, [move(Orig, Dest)|Moves2], Moves). % hanoi_moves(s(s(s(0))),M). % hanoi_moves(s(s(s(0))),M), hanoi_moves(N,M). % hanoi_moves(M,N). % -------------------------------------------------------------------