1% MODULE clause_heads EXPORTS 2 3:- module( clause_heads, 4 [clause_heads/0, heads/1, heads/2, heads/3] 5 ). 6 7%IMPORTS 8:- use_module(home(div_utils), 9 [mysetof/3, different_predicates/2, make_unique/2, 10 variant_mem/2, split_examples/4, insert_unique/3, 11 remove_v/3]). 12:- use_module(home(var_utils), 13 [terms/4]). 14:- use_module(home(interpreter), 15 [proof_path/4]). 16:- use_module(home(kb), 17 [get_example/3, get_clause/5, store_clauses/2,delete_clause/1]). 18:- use_module(home(argument_types), 19 [type_restriction/2]). 20:- use_module(home(lgg), 21 [set_lgg/2]). 22:- use_module(home(evaluation), 23 [eval_examples/0]). 24:- use_module_if_exists(library(subsumes), 25 [subsumes_chk/2]). 26:- use_module_if_exists(library(basics), 27 [member/2]). 28:- use_module_if_exists(library(lists), 29 [rev/2]). 30 31% METAPREDICATES 32% none 33 34%************************************************************************ 35%* 36%* module: clause_heads.pl 37%* 38%* author: Irene Stahl date: 13. 10. 1992 39%* 40%* changed: 41%* 42%* description: algorithm for determining clause heads 43%* generates database entrys of the form 44%* known(ID,Head,true,CList,head,_) 45%* 46%* see also: 47%* 48%************************************************************************ 49 50 51 52%************************************************************************ 53%* 54%* predicate: clause_heads/0 55%* 56%* syntax: 57%* 58%* args: 59%* 60%* description: determines clause heads covering all positive examples in 61%* the kb and asserts them in the kb 62%* 63%* example: 64%* 65%* peculiarities: 66%* 67%* see also: 68%* 69%************************************************************************ 70 71clause_heads:- 72 mysetof(E,I^get_example(I,E,'+'),Elist), % Elist = [E1,..,En] pos examples 73 different_predicates(Elist,Elist1), % Elist1 = [[E1,..,Em],...] 74 % list of lists of pos examples with 75 % the same predicate symbol 76 clause_heads(Elist1). 77 78 79%************************************************************************ 80%* 81%* predicate: heads/1 82%* 83%* syntax: heads(-HL) 84%* 85%* args: HL list of clause heads 86%* 87%* description: returns list of heads covering all positive examples in 88%* the kb 89%* 90%* example: 91%* 92%* peculiarities: 93%* 94%* see also: 95%* 96%************************************************************************ 97 98heads(HL):- 99 clause_heads, 100 mysetof(Head, 101 ID^Body^CL^(get_clause(ID,Head,Body,CL,head),delete_clause(ID)), 102 HL). 103 104 105%************************************************************************ 106%* 107%* predicate: heads/2 108%* 109%* syntax: heads(+Pred,+Arity) 110%* 111%* args: Pred .. predicate symbol (atom), Arity.. an integer 112%* 113%* description: determines clause heads covering all positive examples for 114%* Pred/Arity and asserts them in the kb 115%* 116%* example: 117%* 118%* peculiarities: 119%* 120%* see also: 121%* 122%************************************************************************ 123 124heads(P,N):- 125 functor(E,P,N), 126 mysetof(E,I^get_example(I,E,'+'),Elist), 127 clause_heads([Elist]). 128 129%************************************************************************ 130%* 131%* predicate: heads/3 132%* 133%* syntax: heads(+Pred,+Arity,-HL) 134%* 135%* args: Pred .. predicate symbol, Arity .. integer, HL .. list of heads 136%* 137%* description: returns list of heads covering all positive examples for 138%* Pred/Arity 139%* 140%* example: 141%* 142%* peculiarities: 143%* 144%* see also: 145%* 146%************************************************************************ 147 148heads(P,N,HL):- 149 functor(E,P,N), 150 mysetof(E,I^get_example(I,E,'+'),Elist), 151 clause_heads([Elist]), 152 functor(Head,P,N), 153 mysetof(Head, 154 ID^Body^CL^(get_clause(ID,Head,Body,CL,head),delete_clause(ID)), 155 HL). 156 157%************************************************************************ 158%* 159%* predicate: clause_heads/1 160%* 161%* syntax: clause_heads(+ELL) 162%* 163%* args: ELL = [[E1,..,Em],...] list of lists of pos examples with the 164%* same predicate symbol 165%* 166%* description: determines for each [E1,..,Em] in ELL clause heads 167%* and asserts them in the knowledge base 168%* 169%* example: 170%* 171%* peculiarities: 172%* 173%* see also: 174%* 175%************************************************************************ 176 177clause_heads([]). 178clause_heads([EL|R]):- 179 clause_heads(R), 180 clause_heads(EL,Heads), 181 make_unique(Heads,Heads1), 182 minimize_heads(Heads1,EL,Heads2), 183 store_clauses(Heads2,head), 184 eval_examples. 185 186 187%************************************************************************ 188%* 189%* predicate: clause_heads/2 190%* 191%* syntax: clause_heads(+EL,-Heads) 192%* 193%* args: +EL = [E1,...,Em] positive examples of a predicate p/n 194%* Heads = [H1,..,Hk] heads for p/n covering EL 195%* 196%* description: determines heads for p/n by determining base heads 197%* and heads for non-base examples according to the 198%* differing types 199%* 200%* example: 201%* 202%* peculiarities: 203%* 204%* see also: 205%* 206%************************************************************************ 207 208clause_heads([E|R],Heads):- 209 functor(E,P,N),functor(P1,P,N), 210 ( type_restriction(P1,Types) -> 211 true 212 ; P1 =.. [_|P1A], 213 trivial_tr(P1A,Types) 214 ), 215 bases(N,[E|R],P1,Types,B), 216 remove_base_examples(B,[E|R],E1), 217 split_examples_by_types(E1,P1,Types,Hlist), 218 make_unique(Hlist,Hlist1), 219 best_lgg(Hlist1,[E|R],B,Heads). 220 221trivial_tr([],[]). 222trivial_tr([X|R],[T|R1]):- 223 trivial_tr(R,R1), 224 T =.. [all,X]. 225 226 227%************************************************************************ 228%* 229%* predicate: bases/5 230%* 231%* syntax: bases(+Count,+E,+P,+Type,-B) 232%* 233%* args: N .. counter 234%* E .. positive examples for p/n 235%* P, Type .. type restriction of the target predicate p/n 236%* B .. base heads for p/n 237%* 238%* description: for each argument position N, 239%* for each base case at b at that position, 240%* add lgg({p(..,b,..)|p(..,b,..) in E}) to B 241%* 242%* example: 243%* 244%* peculiarities: 245%* 246%* see also: 247%* 248%************************************************************************ 249 250bases(0,_,_,_,[]). 251bases(N,E,P,Type,B):- 252 N1 is N - 1, 253 bases(N1,E,P,Type,B1), 254 copy_term((P,Type),(P1,Type1)), 255 arg(N,P1,P1n), 256 member(T,Type1),T =.. [_,X], X == P1n, 257 mysetof(Base,I^CL^R^(get_clause(I,T,true,CL,type), T =.. [R,Base]), Bases), 258 bases1(Bases,N,E,B1,B). 259 260bases1([],_,_,B,B). 261bases1([B|R],N,E,B1,[H|B2]):- 262 bases1(R,N,E,B1,B2), 263 bases2(E,N,B,Eb), 264 set_lgg(Eb,H). 265 266bases2([],_,_,[]). 267bases2([E|R],N,B,[E|R1]):- 268 arg(N,E,B),!, 269 bases2(R,N,B,R1). 270bases2([_|R],N,B,R1):- 271 bases2(R,N,B,R1). 272 273 274%************************************************************************ 275%* 276%* predicate: split_examples_by_types/4 277%* 278%* syntax: split_examples_by_types(+E,+P,+Type,-Heads) 279%* 280%* args: E ... examles for p/n (without base examples) 281%* P,Type ... type restriction for p/n 282%* Heads ... list [..., H:terms(H),...] of heads for p/n according 283%* to different types 284%* 285%* description: splits examples E according to different argument types 286%* -> ELL list of example lists. For each EL in ELL, lgg(EL) is 287%* added to heads 288%* 289%* example: 290%* 291%* peculiarities: 292%* 293%* see also: 294%* 295%************************************************************************ 296 297split_examples_by_types(E,P,Types,Heads):- 298 split_examples_by_types(Types,P,E,[],Elist), 299 construct_heads(Elist,Heads). 300 301split_examples_by_types([],_,_,EL,EL). 302split_examples_by_types([T|R],P,E,EL,EL3):- 303 split_examples_by_types(R,P,E,EL,EL1), 304 mysetof((Ex,Ts),(member(Ex,E),proof_path(Ex,P,T,Ts)),Elist0), 305 split_example_list(Elist0,EL2), 306 append(EL1,EL2,EL3). 307 308 309split_example_list([],[]). 310split_example_list([(E,Ts)|R],[[E|EL]|R1]):- 311 split_elist(R,Ts,EL,R0), 312 split_example_list(R0,R1). 313 314split_elist([],_,[],[]). 315split_elist([(E,Ts)|R],Ts,[E|R1],R2):- 316 split_elist(R,Ts,R1,R2). 317split_elist([E|R],Ts,R1,[E|R2]):- 318 split_elist(R,Ts,R1,R2). 319 320 321%************************************************************************ 322%* 323%* predicate: construct_heads/2 324%* 325%* syntax: construct_heads(+ELL,-Heads) 326%* 327%* args: ELL ... list of lists of examples 328%* Heads ... list [...,H:terms(H),...] of heads 329%* 330%* description: for each EL in ELL set H:= lgg(EL), terms(H) terms of H 331%* 332%* example: 333%* 334%* peculiarities: 335%* 336%* see also: 337%* 338%************************************************************************ 339 340construct_heads([EL|R],[H:Vars|R1]):- 341 set_lgg(EL,H), 342 functor(H,_,N), 343 terms(N,H,[],Vars), 344 construct_heads(R,R1). 345construct_heads([],[]). 346 347 348%************************************************************************ 349%* 350%* predicate: best_lgg/4 351%* 352%* syntax: best_lgg(+ToRefine,+E,+Heads,-Heads) 353%* 354%* args: ToRefine ... list [...,H:terms(H),...] of heads 355%* E ... examples 356%* Heads ... resulting heads [...,H,...] 357%* 358%* description: while ToRefine \= [], 359%* add first element H to Heads and 360%* compute all refinements of H that result from unifying 361%* terms within H. Add the refinements to ToRefine. 362%* 363%* example: 364%* 365%* peculiarities: 366%* 367%* see also: 368%* 369%************************************************************************ 370 371best_lgg([],_,HL,HL). 372best_lgg([H:Vars|R],E,HL,HL1):- 373 ( variant_mem(H,HL) -> 374 best_lgg(R,E,HL,HL1) 375 ; try_to_unify(H,Vars,Vars,E,[],Lp), 376 append(Lp,R,R1), 377 best_lgg(R1,E,[H|HL],HL1) 378 ). 379 380 381%************************************************************************ 382%* 383%* predicate: try_to_unify/6 384%* 385%* syntax: try_to_unify(+H,+Terms,+Terms,+E,+Result,-Result) 386%* 387%* args: H .. head that is to be refined 388%* Terms ... terms(H) 389%* E ... examples 390%* Result ... list [...,H1:terms(H1),...] of refined heads 391%* 392%* description: for each pair X,Y (X \== Y) in terms(H) 393%* if H[X/Y] covers examples E' in E 394%* then add H1:terms(H1) to result where H1 = lgg(E') 395%* 396%* example: 397%* 398%* peculiarities: 399%* 400%* see also: 401%* 402%************************************************************************ 403 404try_to_unify(_,[],_,_,L,L). 405try_to_unify(H,[X|R],V,E,L,L2):- 406 unify_vars(H,X,V,E,L,L1), 407 try_to_unify(H,R,V,E,L1,L2). 408 409unify_vars(_,_,[],_,L,L). 410unify_vars(H,X,[Y|R],E,L,L2):- 411 copy_term((H,X,Y),(H1,X1,Y1)), 412 unify_var(H1,X1,Y1,E,L,L1), 413 unify_vars(H,X,R,E,L1,L2). 414 415unify_var(_,X,Y,_,L,L):- X == Y,!. 416unify_var(H,X,X,E,L0,L1):- !, 417 split_examples(E,H,Pos,_), 418 ( Pos \== [] -> 419 set_lgg(Pos,H1), 420 functor(H1,_,N), 421 terms(N,H1,[],Vars1), 422% ( Vars1 == [] -> 423% L1 = L0 424% ; 425 L1 = [H1:Vars1|L0] 426% ) 427 ; L1 = L0 428 ). 429unify_var(_,_,_,_,L,L). 430 431 432%************************************************************************ 433%* 434%* predicate: remove_base_example/3 435%* 436%* syntax: remove_base_example(+BHeads,+E,-E) 437%* 438%* args: BHeads ... base heads 439%* E ... examples 440%* 441%* description: removes all examples covered by base heads in BHeads from E 442%* 443%* example: 444%* 445%* peculiarities: 446%* 447%* see also: 448%* 449%************************************************************************ 450 451remove_base_examples(B,[E|R],R1):- 452 is_base_example(E,B),!, 453 remove_base_examples(B,R,R1). 454remove_base_examples(B,[E|R],[E|R1]):- 455 remove_base_examples(B,R,R1). 456remove_base_examples(_,[],[]). 457 458 459is_base_example(E,[B|_]):- 460 subsumes_chk(B,E),!. 461is_base_example(E,[_|R]):- 462 is_base_example(E,R). 463 464 465%************************************************************************ 466%* 467%* predicate: minimize_heads/3 468%* 469%* syntax: minimize_heads(+Heads,+Examples,-Heads) 470%* 471%* args: Heads.. list of clause heads 472%* Examples... positive examples to be covered by Heads 473%* 474%* description: minimizes the set of clause heads by first removing general 475%* redundant heads, then specific redundant heads. 476%* 477%* example: 478%* 479%* peculiarities: 480%* 481%* see also: 482%* 483%************************************************************************ 484 485minimize_heads(H,EL,H4):- 486 sort_heads_theta(H,H1), 487 remove_redundant(H1,H1,EL,H2), 488 rev(H2,H3), 489 remove_redundant(H3,H3,EL,H4). 490 491 492%************************************************************************ 493%* 494%* predicate: sort_heads_theta/2 495%* 496%* syntax: sort_heads_theta(+Heads,-Heads) 497%* 498%* args: Heads.. list of clause heads 499%* 500%* description: sorts Heads descendingly according to theta-subsumption 501%* 502%* example: 503%* 504%* peculiarities: 505%* 506%* see also: 507%* 508%************************************************************************ 509 510sort_heads_theta([],[]). 511sort_heads_theta([H|R],L):- 512 sort_heads_theta(R,L1), 513 insert_heads_theta(L1,H,L). 514 515insert_heads_theta([H1|R],H,[H1|R1]):- 516 subsumes_chk(H1,H),!, 517 insert_heads_theta(R,H,R1). 518insert_heads_theta(L,H,[H|L]). 519 520 521%************************************************************************ 522%* 523%* predicate: remove_redundant/4 524%* 525%* syntax: remove_redundant(+Heads,+Heads,+Examples,-Heads) 526%* 527%* args: Heads.. list of clause heads 528%* Examples... positive examples to be covered by Heads 529%* 530%* description: removes redundant heads from the list Heads 531%* 532%* example: 533%* 534%* peculiarities: 535%* 536%* see also: 537%* 538%************************************************************************ 539 540remove_redundant([H|R],HL,EL,HL1):- 541 remove_v([H],HL,HL0), 542 ( heads_cover(HL0,EL) -> 543 remove_redundant(R,HL0,EL,HL1) 544 ; remove_redundant(R,HL,EL,HL1) 545 ). 546remove_redundant([],HL,_,HL). 547 548 549%************************************************************************ 550%* 551%* predicate: heads_cover/2 552%* 553%* syntax: heads_cover(+Heads,+Examples) 554%* 555%* args: Heads.. list of clause heads 556%* Examples... positive examples to be covered by Heads 557%* 558%* description: tests whether the heads in Heads cover all examples 559%* 560%* example: 561%* 562%* peculiarities: 563%* 564%* see also: 565%* 566%************************************************************************ 567 568heads_cover(_,[]). 569heads_cover([H|R],E):- 570 split_examples(E,H,_,E1), 571 heads_cover(R,E1)