1% File : STRUCT.PL 2% Author : Richard A. O'Keefe. 3% Updated: 15 September 1984 4% Purpose: General term hacking. See also OCCUR.PL, METUTL.PL. 5 6:- module(struct). % SEPIA header 7 8:- export 9 subst/3, 10 occ/3, 11 variables/2, 12 copy_ground/3. 13 14:- op(950,xfy,#). % Used for disjunction 15:- op(920,xfy,&). % Used for conjunction 16 17/* 18 These routines view a term as a data-structure. In particular, 19they handle Prolog variables in the terms as objects. This is not 20entirely satisfactory. A proper separations of levels is needed. 21*/ 22 23 24% subst(Substitution, Term, Result) applies a substitution, where 25% <substitution> ::= <OldTerm> = <NewTerm> 26% | <Substitution> & <Substitution> 27% | <Substitution> # <Substitution> 28% The last two possibilities only make sense when the input Term is 29% an equation, and the substitution is a set of solutions. The 30% "conjunction" of substitutions really refers to back-substitution, 31% and the order in which the substitutions are done may be crucial. 32% If the substitution is ill-formed, and only then, subst will fail. 33 34 35subst(Subst1 & Subst2, Old, New) :- 36 subst(Subst1, Old, Mid), !, 37 subst(Subst2, Mid, New). 38subst(Subst1 # Subst2, Old, New1 # New2) :- 39 subst(Subst1, Old, New1), !, 40 subst(Subst2, Old, New2). 41subst(Lhs = Rhs, Old, New) :- !, 42 subst(Lhs, Rhs, Old, New). 43subst(true, Old, Old). 44 45 46 subst(Lhs, Rhs, Old, Rhs) :- % apply substitution 47 Old == Lhs, !. 48 subst(_, _, Old, Old) :- % copy unchanged 49 var(Old), !. 50 subst(Lhs, Rhs, Old, New) :- % apply to arguments 51 functor(Old, Functor, Arity), 52 functor(New, Functor, Arity), 53 subst(Arity, Lhs, Rhs, Old, New). 54 55 56 subst(0, _, _, _, _) :- !. 57 subst(N, Lhs, Rhs, Old, New) :- 58 arg(N, Old, OldArg), 59 subst(Lhs, Rhs, OldArg, NewArg), 60 arg(N, New, NewArg), 61 M is N-1, !, 62 subst(M, Lhs, Rhs, Old, New). 63 64 65% occ(Subterm, Term, Times) counts the number of times that the subterm 66% occurs in the term. It requires the subterm to be ground. We have to 67% introduce occ/4, because occ's last argument may already be instantiated. 68% It is useful to do so, because we can use accumulator arguments to make 69% occ/4 and occ/5 tail-recursive. NB if you merely want to check whether 70% SubTerm occurs in Term or not, it is possible to do better than this. 71% See Util:Occur.Pl . 72 73 74occ(SubTerm, Term, Occurrences) :- 75 occ(SubTerm, Term, 0, Times), !, 76 Occurrences = Times. 77 78 occ(SubTerm, Term, SoFar, Total) :- 79 Term == SubTerm, !, 80 Total is SoFar+1. 81 occ(_, Term, Total, Total) :- 82 var(Term), !. 83 occ(SubTerm, Term, SoFar, Total) :- 84 functor(Term, _, Arity), !, 85 occ(Arity, SubTerm, Term, SoFar, Total). 86 87 occ(0, _, _, Total, Total) :- !. 88 occ(N, SubTerm, Term, SoFar, Total) :- 89 arg(N, Term, Arg), 90 occ(SubTerm, Arg, SoFar, Accum), 91 M is N-1, !, 92 occ(M, SubTerm, Term, Accum, Total). 93 94 95% The previous two predicates operate on ground arguments, and have some 96% pretence of being logical (though at the next level up). The next one 97% is thoroughly non-logical. Given a Term, 98% variables(Term, VarList) 99% returns a list whose elements are the variables occuring in Term, each 100% appearing exactly once in the list. var_member_check(L, V) checks 101% that the variable V is *not* a member of the list L. The original 102% version of variables/2 had its second argument flagged as "?", but this 103% is actually no use, because the order of elements in the list is not 104% specified, and may change from implementation to implementation. 105% The only application of this routine I have seen is in Lawrence's code 106% for tidy_withvars. The new version of tidy uses copy_ground (next page). 107% If that is the only use, this routine could be dropped. 108 109 110variables(Term, VarList) :- 111 variables(Term, [], VarList). 112 113 variables(Term, VarList, [Term|VarList]) :- 114 var(Term), 115 var_member_check(VarList, Term), !. 116 variables(Term, VarList, VarList) :- 117 var(Term), !. 118 variables(Term, SoFar, VarList) :- 119 functor(Term, _, Arity), !, 120 variables(Arity, Term, SoFar, VarList). 121 122 variables(0, _, VarList, VarList) :- !. 123 variables(N, Term, SoFar, VarList) :- 124 arg(N, Term, Arg), 125 variables(Arg, SoFar, Accum), 126 M is N-1, !, 127 variables(M, Term, Accum, VarList). 128 129 var_member_check([], _). 130 var_member_check([Head|Tail], Var) :- 131 Var \== Head, !, 132 var_member_check(Tail, Var). 133 134/* In order to handle statements and expressions which contain variables, 135 we have to create a copy of the given data-structure with variables 136 replaced by ground terms of some sort, do an ordinary tidy, then put 137 the variables back. Since we can use subst/3 to do this last step, a 138 natural choice of working structure in the first step is a substitution 139 $VAR(k) = Vk & ... & $VAR(0) = V0 & 9 = 9. 140 The rest is straight-forward. The cost of building the copy is o(E*V) 141 where E is the size of the original expression and V is the number of 142 variables it contains. The final substitution is the same order of cost. 143 For what it's worth, copy_ground(X,Y,_) & numbervars(X,0,_) => X == Y. 144*/ 145 146 147copy_ground(Term, Copy, Substitution) :- 148 copy_ground(Term, Copy, 9=9, Substitution). 149 150 copy_ground(Term, Copy, SubstIn, SubstOut) :- 151 var(Term), !, 152 subst_member(SubstIn, Term, Copy, SubstOut). 153 copy_ground(Term, Copy, SubstIn, SubstOut) :- 154 functor(Term, Functor, Arity), 155 functor(Copy, Functor, Arity), !, 156 copy_ground(Arity, Term, Copy, SubstIn, SubstOut). 157 158 copy_ground(0, _, _, SubstIn, SubstIn) :- !. 159 copy_ground(N, Term, Copy, SubstIn, SubstOut) :- 160 arg(N, Term, TermN), 161 copy_ground(TermN, CopyN, SubstIn, SubstMid), 162 arg(N, Copy, CopyN), 163 M is N-1, !, 164 copy_ground(M, Term, Copy, SubstMid, SubstOut). 165 166 subst_member(SubstIn, Term, Copy, SubstIn) :- 167 subst_member(SubstIn, Term, Copy), !. 168 subst_member(SubstIn, Term, Copy, (Copy = Term) & SubstIn) :- 169 ( SubstIn = (('$VAR'(M) = _) & _), 170 N is M+1 % M+1 variables seen 171 ; N = 0 % SubstIn = 9=9 172 ), !, 173 Copy = '$VAR'(N). 174 175 subst_member((Copy = Vrbl) & _, Term, Copy) :- 176 Vrbl == Term, !. 177 subst_member(_ & Rest, Term, Copy) :- 178 subst_member(Rest, Term, Copy). 179 180 181