ARM Club 3

home *** CD-ROM | disk | FTP | other *** search

/ ARM Club 3 / TheARMClub_PDCD3.iso / hensa / programming / huprolog_1 / Help! / s < prev

Wrap

Text File | 1995-09-15 | 27.6 KB | 777 lines

/* ---------------------------------------------------------------------- (The dashes are cosmetic.) "start" file. ============= These comments, marked by the slash*, will be ignored by Prolog. There is a user option to interpret a particular scenario and make up a personal file of clues. These can be entered instead of one of the collected clues files "a", "h", "l", "m". Facts, present in this Udunit tend to show that identity X is, or is not, compatible to identity Y. It will be seen that a pair of facts which fit each other c(williamtell,crossbow) is a compatibility. Otherwise the fact i(williamtell,sherwoodforest), for instance, is an incompatibility. To reduce the number of files which need to be loaded a gleaned clues listing may be inserted into a "group" file. These group files "marinatale", "loungetale" etc apart from "remarks" otherwise contain only lists of the principals seen in a particular episode. Thus, together with your inserted clues would replace the standard "clus" file. This ability to introduce your own material underlines the importance of making a backup of the disc first. As a rule the user's clues collection will be effectively the same as the resident "clus" version, provided that all the transparent clues have been entered and without aberrations. Loading "monitor" may provide guidance if you suspect that all is not well with your entries. With the clue processor inside this file Prolog will progress towards a solution to an episode through a process of data correlation. On the first pass correlation between various i(X,Y) will produce one or more c(X,Y) by virtue of Prolog's scrutiny and elimination of n-1 impossibilities in a field of n candidates. The c(X,Y) produced will on subsequent passes be cross-correlated with the earlier data. Although not actually mandatory, in this type of problem there are the same number of individuals in each group. Of these, n-1 members (in a group) can be eliminated from any particular activity. Actual names of the utilities used will be as long as need be to reflect their purpose to the user. All this commentary will be ignored by Prolog. (Note. The slash ends the comments.) ------------------------------------ */ % This is a one-line comment. /* A discussion of the utilities will be accompanied by reference to the relevant Prolog conventions. This will become less necessary as we go along. */ % " :- " means " IF ". s :- nl,nl, % " nl," means new line. write(' Start.'),nl, % " , " means " AND ". write(' ------'),nl,nl, start. % For readability a space is usually maintained % between the name and the semicolon. start :- episode, % Title, if any, given in the readout. fail. % A pseudo "fail". The next "start" clause % will now be addressed. start :- i(_,_), % Has data been entered ?. remove_duplicates. % Readouts will look better without % repetitive data. start :- c(_,_), % Data is in the form "i(X,Y)" and/or "c(X,Y)". remove_duplicates. start :- % If Prolog arrives here the data has not been loaded. nl,nl, write(' DATA HAS NOT YET BEEN ENTERED.'),nl, write(' ------------------------------'),nl,nl, write(' Prolog halts here.'). /* Composers of logic problems ensure that only the minimum number of facts necessary to obtain a solution are available. This rule has been relaxed in this Udunit. However, a very few of the clues in each episode express similar data in slightly different ways. This gives rise to duplicated entry of these clues. Redundancy of entries need not trouble us here as they will be suppressed at run time thus avoiding repetition of Prolog output. This is achieved by the procedure below. Clauses found to have been duplicated of course could, instead, have been cached under a new name and made inactive. */ remove_duplicates :- write(' Duplicates removed and Inversions introduced .'),nl, write(' ----------------------------------------------'),nl, fail. /* The negation "bar" is used in the following utility where it is a safeguard against duplicated data being processed. The resident Prolog predicate "not" would usually be employed for this purpose. However an alias, "bar", will be used in its stead for the reasons stated below. */ % A slave j(X,Y) in place of the particular i(X,Y) being dealt with, % without duplicates, will now be raised. Although KeyLink kprolog % could enable a simpler utility to be used which can retract and % save a copy of a clause to a cache, this utility is more general % purpose. remove_duplicates :- i(X,Y), % These may have had duplicates. bar(j(X,Y)), % If done already Prolog now backtracks assert(j(X,Y)), % to find the next i(X,Y) candidate, if any. fail. % Both "bar" and "fail" are construed below. /* Prolog will backtrack on seeing "fail" and try to find other i(X,Y) clauses before addressing the next "remove_duplicates" clause. */ /* Note, the definition of the ad hoc utility "bar", is not given whilst in the middle of this "remove_duplicates" procedure. Otherwise, Prolog will draw our attention to what it would construe as possibly dislocated clauses. */ remove_duplicates :- abolish(i,2), fail. % Any duplications in i(X,Y) in database are, % thus, also abolished. /* We have cleared the database of any duplicates by the expediency of raising j(X,Y) and abolishing the i(X,Y) data. Going full circle, the functor name "i" can be resurrected. Also, to promote a solution, the inversions i(Y,X) generated from pristine i(X,Y). The readout will look rather like this, i(alpha,beta) i(beta,alpha) i(mu,phi) i(phi,mu) i(epsilon,gamma) i(gamma,epsilon) More simply, i(alpha,beta) i(beta,alpha) i(mu,phi) i(phi,mu) i(epsilon,gamma) i(gamma,epsilon) */ remove_duplicates :- j(X,Y), % The interim form. bar(i(X,Y)), assert(i(X,Y)), assert(i(Y,X)), write(i(X,Y)),nl, % More simply, remove "nl," and reduce to, tab(30), % say, tab(15). write(i(Y,X)),nl, fail. remove_duplicates :- abolish(j,2), % No further need for these. c_data. % "c_data" will check for c(X,Y) data. If none % then a jump will made. /* Now "not" and "bar". PrologX will raise an objection for some uses of "not". Briefly, the negation of a fact which has not yet made its entry into the circumscribed world of the database can be a bit tricky. This, perhaps, partly stems from the fact that both " not X " and " not(X) " can be used. Hence to avoid initial confusion the "bar" alias, which has been given the same definition as "not", is used. The user later can engage the usual form. */ bar(Goal) :- % The term "bar" has been substituted for "not". call(Goal),!, % "!", A cut. If the goal is found, and this fail. % could be an unwanted duplicate, then the % second clause, bar(_),will not be addressed. bar(_). % Also, perforce, the goal is made to fail. /* If (Goal) was not found then the cut ! would not be encountered as backtracking would occur. The next clause, bar(Anything) then enables the procedure to continue. */ /* ---------------------------------------------------------------------- The "member" utility, below, will now be used fairly frequently. Let us consider a list, that is any number of constants contained within square brackets. For instance, [a,b,c,d,e], or indeed the empty list [] which has a significant part to play in Prolog. The "member" utility operates by first looking at the element currently at the head of the list. Thus something is a member of a list if it is at its head. This leaves the tail of the list remaining for scrutiny. The definition below shows the Prolog use of the vertical separator "|". The member utility: Let [Head|Tail] be [a,b,c,d,e]. ------------------- member(X,[X|_]). % X is obviously a member of [X|_]. % Example: member(a,[a|_]). member(X,[_|Tail]) :- member(X,Tail). % Example: member(d,[_|[b,c,d,e]]). As the tail is also a list "member" will simply shed the head of the list progressively until it either finds a match or fails. ---------------------------------------------------------- */ % In order to avoid conflict with HUprolog, and others, "member" is % renamed "member2". (Any particular prolog facility regards its % built-in predicates as sacrosanct.) member2(X,[X|_]). member2(X,[_|Tail]) :- member2(X,Tail). c_data :- nl, c(_,_), % Are there any c(X,Y) ?. c_inverse. % Various forms of correlation will take place % between all elements that have been introduced by % the data file. c_data :- % No c(X,Y) in the initial data if Prolog gets here. make_subgroups. % (See NOTE). /* NOTE. If a c(X,Y) had not been entered then the next few utilities which are designed to operate on c(X,Y) will be avoided on a first pass. Subsequent recursions however will call up these facilities. Thus an absence of c(X,Y) at the outset will cause Prolog to go to "make_subgroups" early. This being in the main loop. "make_subgroups" will then collect something like: Example: i(X,a1), i(X,a2), i(X,a4), i(X,a5), and thus c(X,a3) would be generated. The variable X could have been replaced with an arbitrary constant. One of the episodes gives up no transparent c(X,Y), however read "c_inverse" since it is functionally similar to the inversion of i(X,Y). Follow this with Introduction to "findall", just below. */ c_inverse :- nl,nl, % If c(X,Y) then c(Y,X) also is needed. write(' inverse'),nl, write(' -------'),nl,nl, c(X,Y), % Both will be used. bar(c(Y,X)), % If already in database base don't bother. assert(c(Y,X)), write(c(X,Y)),nl, tab(30), write(c(Y,X)),nl, fail. c_inverse :- cross_correlate, % These are defined later. auto_correlate, % "c_inverse" would not have been called up % if no c(X,Y) had been entered as in the % harem episode "h". make_subgroups. /* ---------------------------------------------------------------------- Introduction to "findall". -------------------------- The procedure "make_subgroups" will use "findall" to make up subgroups of elements from Y in i(X,Y). We could, instead, have chosen to find all X in i(X,Y). A description of "findall" is usually given as findall(X,Goal,List) which can be interpreted here as, either; findall(X,i(X,Y),List) or findall(Y,i(X,Y),List). We will use the latter and declare X as being the identity which is incompatible to the contents of List. Example: If, say, group([snail,rat,mosquito,tsetse_fly,sand_fly]), was sitting in the database and user entered from the keyboard: ?- assert(i(lassa_fever,snail)). assert(i(lassa_fever,mosquito)). assert(i(lassa_fever,tsetse_fly)). assert(i(lassa_fever,sand_fly)). findall(Y,i(X,Y),List). (Then Prolog would return:) List = [snail,mosquito,tsetse_fly,sand_fly] As Lassa fever is not attributable to any of these agents an extension of the inquiry would give up the compatible pair: c(lassa_fever,rat). The range of any list is limited in length only by the Prolog facility storage allocation. ------------------- */ /* The implementation of the findall relation shown here is seen in Bratko's "Prolog, Programming for Artificial intelligence." Other versions may cache the "find" using "asserta" instead of "assertz", where the suffix "z" means go to the bottom of the pile. Originated by D.H.D.Warren it was refined by R,A.O'Keefe et al. An ad hoc version which performed well with this clue processor was regretfully set aside as it flies in the face of the fully evolved "findall" predicate. It does however point up the fact that it is not particularly difficult to produce workable utilities for a knowledge database. */ % In order to avoid conflict with "findall" in both HUprolog and % PrologX the utility will be renamed "findall3". The new name is % suggested by the fact that there are three parameters or arguments % in "findall". % An understanding of "findall" is not particularly germane to the % user's progress through this clue processor at the outset. findall3(X,Goal,Xlist):- % The structure for "findall". call(Goal), % Find items and assertz(queue(X)), % assert each to end of a queue. fail; % ";" means OR. assertz(queue(bottom)), % Mark the end of the queue. collect(Xlist). % Collect items to list. collect(L) :- % L becomes Xlist. retract(queue(X)),!, % Retract next item. (X == bottom,!,L = []; % No more items ? L = [X|Rest], collect(Rest)). % Otherwise collect the rest. % The [] of course means "empty". make_subgroups :- % Subgroups of the form ii(a1,[b1,b2,b3,b5]) abolish(ii,2), % will be fashioned. A simple way to avoid the fail. % clutter of small subgroups of the previous % recursion is to abolish them. make_subgroups :- % This leads to the use of the "findall3" utility. nl, write(' make_subgroups'),nl, write(' --------------'),nl,nl, fail. /* To prevent Prolog from looping indefinitely should insufficient data have been entered the next clause will assert a flag to the top of the functor c(_,_) pile. This will be "c([],[])", it could have been "c(insufficient,data)", say. Thus, when during the course of this new recursion a fresh c(X,Y) is found it will displace c([],[]) from the top of the pile. At the end of a recursion involving each element in turn as a reference, if all is well the marker c([],[]) will have been relegated to the bottom of the current pile. It remains then to restore it to the top of the pile before the start of the next recursion. Conversely if a new c(X,Y) had not been encountered then a call to "c(X,Y)" would produce c([],[]) immediately. This, still the topmost clause, would then cause Prolog to signal "Insufficient data." and await further information. */ make_subgroups :- write(' The flag c([],[]), below, will be hidden when a c(X,Y) is disclosed. Failing this, the program will stop due to insufficient data.'), nl,nl, write('Small wait.'),nl,nl, fail. make_subgroups :- asserta(c([],[])), % If this is still top of the pile after c(X,Y), % "data_check" below then "Insufficient tab(40), % data.". write(c(X,Y)),write(' asserted.'),!, nl,nl, subgroups. subgroups :- group(XX), % Get a group. member2(X,XX), % Select the head of the list. group(YY), % This group will supply the Y in i(X,Y). YY \== XX, % Prevents Prolog from assigning the same % group to different variables. makej(X,YY), % "makej/2" will produce one subset at a fail. % time of i(X,Y) clauses using a unique % X and a selected group(YY). subgroups :- oddoneout. % Here a search for n-1 instances of Y in % a possible n i(X,Y) clauses. % "findall3" will be called up. makej(X,YY) :- member2(Y,YY), i(X,Y), assert(j(X,Y)), fail. makej(X,YY) :- findjy. findjy :- j(X,_), findall3(Y,j(X,Y),Subgroup), bar(ii(X,Subgroup)), assert(ii(X,Subgroup)), fail. findjy :- abolish(j,2). % Returns to "subgroups". Another recursion. /* The next utility, "oddoneout", compares complete groups with the current Subgroups. Employing the "difference" predicate it marks the presence of all n-1 subgroups so enabling compatible pairs to be raised. This is done by noting when the difference "Diff" is equal to the singleton [Head|[]]. Example: group([a1,a2,a3,a4,a5]) ii(X,([a1,a2,a4,a5])). This leads to c(X,a3). Numeric example: difference([1,2,3,4,5], [2,3,5,6], Diff). Diff = [1,4] "difference" is a predicate favoured by more than one text book. The "Utilities" directory shows the utility "length" which could be used to compare a "group" with a subgroup. The odd one out can then be ascertained when the difference in length is a singleton. From a group list [a1,a2,a3,a4,a5] and its subgroup list [a1,a2,a4,a5] the element a3 would emerge thus pointing to c(X,a3). */ difference([],_,[]). difference([X|Set1],Set2,Diff) :- member2(X,Set2), !, difference(Set1,Set2,Diff). difference([X|Set1],Set2,[X|Diff]) :- difference(Set1,Set2,Diff). oddoneout :- write( ' Permutations of n-1 subsets will be encountered. These also will be shown but only one the first one seen will be operated on.'), nl,nl,nl, fail. oddoneout :- ii(X,List), % ii(X,[a1,a2,a4,a5]). write(ii(X,List)),nl, member1(M,List), % Confirming that List is a subgroup of G. group(G), % e.g. group([a1,a2,a3,a4,a5]). member2(M,G), % Say, member2(a1,[a1,a2,a3,a4,a5]). % difference(G,List,Difference) % Difference is a list, [Head|Tail]. % So let us use: difference(G,List,[Head|[]]), % That is a Head followed by an empty tail. % Which is exactly what we are looking for. bar(c(X,Head)), asserta(c(X,Head)), nl, write(ii(X,List)),nl, tab(1), write(c(X,Head)), bar(c(Head,X)), asserta(c(Head,X)), tab(5), write(c(Head,X)), write(' shown.'),nl,nl, fail. oddoneout :- nl, c(X,Y), write(c(X,Y)), nl, fail. oddoneout :- progress, cross_correlate, auto_correlate, fail. oddoneout :- do, % This utility will inspect the data file for % additional instructions. fail. oddoneout :- monitor, % Operative if the monitor file has been loaded. fail. oddoneout :- sort_c, delete_unwanted_i. progress :- c(X,Y),!, % Only the first instance found will be used. check(X). % One of the parameters is passed on for vetting. check(X) :- [] == X, nl,nl, write('..... End; c([],[]) still at the top of the pile.'), nl,nl, write('c([],[]) not displaced.'),nl,nl, nl,nl, write(' WE HAVE INSUFFICIENT DATA.'), nl, write(' --------------------------'), nl,nl, abort. check(X) :- % Prolog has seen fresh data. nl, retract(c([],[])), nl, tab(10), write('c([],[]) retracted.'),nl,nl. cross_correlate :- nl, write(' c(Y,Z) generated from c(X,Y) and c(X,Z).'), nl, fail. % This utility has been awaiting the production of further c(X,Y). % It was unlikely that both c(X,Y) and c(X,Z) were available from % file. cross_correlate :- c(X,Y), c(X,Z), Z \== Y, bar(c(Y,Z)), assert(c(Y,Z)), write(c(Y,Z)),nl, fail. cross_correlate :- nl, write(' If c(X,Y) and i(X,Z) then i(Y,Z).'),nl, fail. cross_correlate :- % nl, c(X,Y), % c(a1,b1), i(X,Z), % i(a1,c1), group(YY), % group([b1,b2,b3,b4,b5]), member2(Y,YY), % member2(b1,[b1,b2,b3,b4,b5]), bar(member2(Z,YY)), % bar(member2(c1,[b1,b2,b3,b4,b5]). bar(i(Y,Z)), % If done already don't bother. assert(i(Y,Z)), % assert(i(b1,c1)), bar(i(Z,Y)), assert(i(Z,Y)), % assert(i(c1,b1)), write(i(Y,Z)),nl, % There will be a fair number of these. fail. % Prefix "write" with a "%" to % avoid a readout. cross_correlate. /* Suppose c(a1,Y) and group([a1,a2,a3,a4,a5]) then i(a2,Y), i(a3,Y) etc. must be asserted. */ auto_correlate :- nl,nl, write(' c(a1,Y) will evoke i(a2,Y), i(a3,Y) etc.'),nl,nl, write( ' They are comprised of the following, with their inverts.'), nl,nl, fail. auto_correlate :- group(XX), member2(X,XX), c(X,Y), member2(X2,XX), X2 \== X, bar(i(X2,Y)), assert(i(X2,Y)), write(i(X2,Y)),nl, bar(i(Y,X2)), assert(i(Y,X2)), fail. auto_correlate. sort_c :- group(XX), member2(X,XX), c(X,Y), asserta(slave(X,Y)), fail. sort_c :- abolish(c,2), fail. sort_c :- slave(X,Y), asserta(c(X,Y)), fail. sort_c :- abolish(slave,2). delete_unwanted_i :- % i(X,Y) are still in evidence. nl,nl, write('We are looking for subgroups of n-1 elements.'),nl, write('---------------------------------------------'), nl,nl, fail. % To avoid clutter, as c(x,y) are present, certain i(X,Y) will be % deleted. delete_unwanted_i :- write(' delete_unwanted_i'),nl, write(' -----------------'), group(YY), % group([a1,a2,a3,a4,a5]). member2(Y,YY), % member2(a5,[a1,a2,a3,a4,a5]), say. c(X,Y), % c(X,a5), say. member2(Y2,YY), % member2(M,[a1,a2,a3,a4,a5]). Y2 \== Y, % M \== a5. i(X,Y2), % These would be i(X,a1)..i(X,a4). retract(i(X,Y2)), % When, eventually, the global i(X,Y) have fail. % been retracted then the logic problem is % solved. delete_unwanted_i :- i(_,_), % Any i(X,Y) left ?. make_subgroups. % Another recursion. delete_unwanted_i :- % If Prolog gets here then collect_sets. % no i(X,Y) left. (See NOTE.) /* NOTE. Only compatible elements remain in the database. Inverts c(Y,X) can be suppressed. A general clean-up will now take place in "collect_sets". */ collect_sets :- nl, write(' collect_sets '),nl, write(' ------------ '),nl,nl, write( 'All c(X,Y) including inverts have been found. Interacting components will be retained but their inverts will be suppressed. This will facilitate the subsequent attraction of complete sets of compatible elements.'), nl,nl, make_one_list. % Use only c(X,Y) with X of one list. make_one_list :- nl, write('consolidated lists.'),nl, fail. make_one_list :- write( ' One group only will be used to attract its compatibles, namely.'), nl,nl, group(XX), klists(XX). klists(XX) :- write(XX),nl,nl, group(XX), member2(X,XX), c(X,Y), assert(k(X,Y)), write(k(X,Y)),nl, fail. klists(XX) :- ccsets. ccsets :- nl, k(X,_), findall3(Y,k(X,Y),Subset), precede(X,Subset,Set), bar(cc(Set)), assert(cc(Set)), write(cc(Set)),nl, fail. ccsets :- nl, write(' * all_done *'),nl, write(' ------------'),nl,nl, write(' PROBLEM SOLVED.'),nl,nl, write(' The cc sets show connected elements.'),nl, write( ' To do a re-run do < ss.>.'),nl,nl, write(' ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤'),nl. delete(X,List1,List2) :- conc(L1,[X|L2],List1), conc(L1,L2,List2). % Used above. precede(X,List,[X|List]). % Appends a single element X to a list. % Example precede(a,[b,c,d],List]). % List = [a,b,c,d] member1(X,[X|_]) :- !. % This will find one member only. member1(X,[_|T]) :- member1(X,T). conc([],L,L). conc([X|L1],L2,[X|L3]) :- conc(L1,L2,L3). ss :- write('* ss *'),nl, write('------'),nl,nl, nl,nl, group(YY), % group([y1,y2,y3,y4,y5]). member2(Y,YY), % member2(y1,[y1,y2,y3,y4,y5]). c(X,Y), % c(x1,y1). member2(Y1,YY), % member2(y2,[y1,y2,y3,y4,y5]). Y1 \== Y, % y2 \== y1. bar(i(X,Y1)), % bar(i(x1,y2)), assert(i(X,Y1)), % assert(i(x1,y2)), fail. ss :- abolish(k,2), abolish(c,2), abolish(cc,1), nl, make_subgroups. % This is a convenient entry into the programme.