home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / lifeos2.zip / LIFE-1.02 / TESTS / LF / Z_COMB.LF < prev    next >
Text File  |  1996-06-04  |  7KB  |  234 lines
  1. % Copyright 1991 Digital Equipment Corporation
  2. % Written by Peter Van Roy
  3. % Written in LIFE
  4.  
  5. main(Z) :- a1(A), force(A,Z).
  6.  
  7. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  8.  
  9. % Utilities.
  10.  
  11. % Subset
  12. subsetp([], _) :- !.
  13. subsetp([A|S1], [B|S2]) :- A=:=B, !, subsetp(S1,     S2).
  14. subsetp([A|S1], [B|S2]) :- A>B,   !, subsetp([A|S1], S2).
  15.  
  16. % Difference
  17. % Does this not work because matching is done on the head only?
  18. % Therefore the second rule always matches & the following ones are never used.
  19. diff(S, [],  S) :- !.
  20. diff([], _, []) :- !.
  21. diff([A|S1], [B|S2], [A|S]) :- A<B,   !, diff(S1, [B|S2], S).
  22. diff([A|S1], [B|S2],     S) :- A=:=B, !, diff(S1,     S2, S).
  23. diff([A|S1], [B|S2],     S) :- A>B,   !, diff([A|S1], S2, S).
  24.  
  25. % Last element of a list
  26. last([X]) -> X.
  27. last([_|L]) -> last(L).
  28.  
  29. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  30.  
  31. % Generator utilities.
  32.  
  33. % These are written in Prolog-like style since they must give solutions
  34. % on backtracking.
  35.  
  36. % Subsets of an interval.
  37. % subset(L, S, H) is true if S is a subset of [L..H].
  38. % The smallest subsets are given first.
  39. subset(L, Subset, H) :-
  40.     range(0, N, H-L+1),
  41.     comb(N, L, Subset, H).
  42.  
  43. % Combinations of elements from an interval.
  44. % comb(N, L, Comb, H) is true if Comb is a combination in sorted order of
  45. % N elements of [L..H].
  46. % The combinations with smallest elements are given first.
  47. comb(0, _, [], _) :- !.
  48. comb(N, L, [I|Rest], H) :- N>0,
  49.     range(L, I, H),
  50.     comb(N-1, I+1, Rest, H).
  51.  
  52. % Membership in an interval.
  53. % range(L, I, H) is true if I is an integer in the interval [L..H].
  54. % The smallest integer is given first.
  55. range(L, I, H) :-
  56.     L<H+1,
  57.     (I=L ; range(L+1, I, H)).
  58.  
  59. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  60.  
  61. % *** So far, don't need type b ***
  62. % Extension to type boolean for correct collapse:
  63. % Need a unification of true and false that is different from failure.
  64. % Define new types x (don't care), t (true), f (false), b (boolean).
  65. % Note: can't redefine 'true' and 'false' themselves because that changes
  66. % the meaning of any part of the program that relies on them.
  67. % Sometimes want to unify t and f to get x, other times want it to fail.
  68. % x <| t.
  69. % x <| f.
  70. t <| b.
  71. f <| b.
  72.  
  73. % Collapse a list into a single element by unifying all its members:
  74. % Fails for the empty list.
  75. collapse(A, [X|L], Z) :-
  76.     Z=root_sort(X),
  77.     collapse_loop(A, L, X, Z).
  78.     
  79. collapse_loop(A, [],    Z, Z) :- !.
  80. collapse_loop(A, [X|L], Y, Z) :-
  81.     combine(A, X, Y, Z1),
  82.     collapse_loop(A, L, Z1, Z).
  83.  
  84. % This "cdring down the arguments" style is *not* satisfactory.
  85. combine(0, _, _, _) :- !.
  86. combine(N, X, Y, Z) :- N>0,
  87.     Z.N = combine_one(X.N,Y.N),
  88.     combine(N-1, X, Y, Z).
  89.  
  90. % Create don't cares 'x'.
  91. combine_one(f, f) -> f.
  92. combine_one(f, t) -> x.
  93. combine_one(t, f) -> x.
  94. combine_one(t, t) -> t.
  95. combine_one(f, x) -> x.
  96. combine_one(t, x) -> x.
  97. combine_one(x, f) -> x.
  98. combine_one(x, t) -> x.
  99. combine_one(x, x) -> x.
  100.  
  101. % Instantiate a functor to true or false for each member of a given subset:
  102. instantiate([], _).
  103. instantiate([I|S], F) :-
  104.     boolean(B),
  105.     B = F.I,
  106.     % F=_(I => B),    % This is not legal in LIFE.  Attributes must be const.
  107.     instantiate(S, F).
  108.  
  109. % true or false.
  110. boolean(f).
  111. boolean(t).
  112.  
  113. % true or false or dontcare.
  114. anybool(x) :- !.  % Don't care must come first.
  115. anybool(f) :- !.
  116. anybool(t) :- !.
  117.  
  118. make_dontcare(0, _) :- !.
  119. make_dontcare(N, X) :- N>0,
  120.     anybool(X.N),
  121.     % (x = X.N; succeed), !,
  122.     make_dontcare(N-1, X).
  123.  
  124. % Order of checking is ok because input is in order from largest to smallest
  125. % subset.
  126. % A kluge: using n.a.f. as a filter.
  127. % Remove forcings that are trivially implied by other forcings.
  128. % I.e.: Find the minimum number of inputs that forces a given output.
  129. filter_redundant_1([], []) :- !.
  130. filter_redundant_1([F|InF], OutF) :-
  131.     F=force(S1,_,F1),
  132.     member(force(S2,_,F2), InF),
  133.     F1=F2,
  134.     subsetp(S2, S1),  % S2 is more powerful than S1, so keep only S2.
  135.     !,
  136.     filter_redundant_1(InF, OutF).
  137. filter_redundant_1([F|InF], [F|OutF]) :-
  138.     !,
  139.     filter_redundant_1(InF, OutF).
  140.  
  141. % A kluge: using n.a.f. as a filter.
  142. % Remove forcings that are less trivially implied by other forcings.
  143. % I.e.: Find the minimum number of inputs that forces a given output.
  144. % In this case, disregard for two forcings those inputs that are not used
  145. % in both.
  146. % Filter 2 has a weaker condition than filter 1 and subsumes it.
  147. filter_redundant_2(_, [], []) :- !.
  148. filter_redundant_2(A, [F|InF], OutF) :-
  149.     F=force(S1,_,F1),
  150.     member(force(S2,_,F2), InF),
  151.     subsetp(S2, S1),
  152.     diff(S1, S2, Diff),
  153.     % check_condition(A, S1, F1, F2),
  154.     check_condition(A, Diff, F1, F2),
  155.     !,
  156.     filter_redundant_2(A, InF, OutF).
  157. filter_redundant_2(A, [F|InF], [F|OutF]) :-
  158.     !,
  159.     filter_redundant_2(A, InF, OutF).
  160.  
  161. % Check that all arguments are identical except maybe for those in Diff:
  162. check_condition(0, _, _, _) :- !.
  163. check_condition(N, Diff, F1, F2) :- N>0,
  164.     F1.N=F2.N,
  165.     !,
  166.     check_condition(N-1, Diff, F1, F2).
  167. check_condition(N, Diff, F1, F2) :- N>0,
  168.     member(N, Diff),
  169.     !,
  170.     check_condition(N-1, Diff, F1, F2).
  171.  
  172. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  173.  
  174. a1(A) :- A=names(['860GAT(334)','847GAT(335)','834GAT(336)','[85]','[84]'],[_(f,b,b,t),_(t,f,f,b)]).
  175.  
  176. a2(A) :- A=names(['1GAT(0)','[73]','602GAT(240)'],[_(t,t),_(f,f)]).
  177.  
  178. % Term is F(A1, A2, ..., An) where F is some boolean predicate.
  179. % It is not at all important for calculating the forcings, but
  180. % elsewhere we assume by convention that arguments A1, ..., An-1
  181. % are inputs and argument An is the output.
  182.  
  183. % This algorithm is exponential; it's fine for boolean predicates with
  184. % bounded (small) number of arguments.  Note that in general the number
  185. % of constraints can grow exponentially with the number of arguments,
  186. % so that the problem is inherently exponential (is this really true?).
  187.  
  188. % Since (2) subsumes (1), it may be faster just to do (2):
  189. force(Def, F) :-
  190.     Def = names(Names,DefTerms),  % A unification.
  191.     A = length(Names),            % A function call.
  192.     Term = last(Names),          % A function call.
  193.         % write(a),
  194.     filter_redundant_1(forcings(A,Term,DefTerms), F1),
  195.         % write(b),
  196.     filter_redundant_2(A, F1, F).
  197.  
  198. % Generate the forcings.
  199. forcings(A, Term, DefTerms) ->
  200.     bagof(X, a_forcing(A, Term, DefTerms, X)).
  201.  
  202. % The only asymmetry between the inputs and the outputs is that *all*
  203. % combinations of the inputs exist in the definition of the function,
  204. % whereas this is not necessarily true of the output.  The method of finding
  205. % forcings works independently of this condition.
  206. a_forcing(A, Term, DT, force(Subset,Term,Forcing)) :-
  207.     subset(1, Subset, A),
  208.         % write(c),
  209.     instantiate(Subset, Term), % Instantiate output and arguments.
  210.         % write(d),
  211.         % trace,
  212.     collapse(A, bagof(Term,(all_tf(A,Term),general(A,Term,DT))), Forcing),
  213.         % write(e),
  214.     make_dontcare(A, Term),
  215.         % write(f),
  216.     \+ Term=Forcing,
  217.         % write(g),
  218.     nl,write(Forcing),nl.
  219.  
  220. general(A, Term, DefTerms) :-
  221.     member(Term, DefTerms),
  222.     !,
  223.     t = Term.A.
  224. general(A, Term, _) :-
  225.     f = Term.A.
  226.  
  227. all_tf(0, _) :- !.
  228. all_tf(N, T) :- N>0,
  229.     B = T.N,
  230.     boolean(B),
  231.     all_tf(N-1, T).
  232.  
  233. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  234.