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