%  Figure 7.3  A procedure for substituting a subterm of a term by another subterm.

% substitute( Subterm, Term, Subterm1, Term1):
%    if all occurrences of Subterm in Term are substituted
%    with Subterm1 then we get Term1.

% Case 1: Substitute whole term
substitute( Term, Term, Term1, Term1)  :-  !.


% Case 2: Nothing to substitute
substitute( _, Term, _, Term)  :-
   atomic(Term), !.


% Case 3: Do substitution on arguments
substitute( Sub, Term, Sub1, Term1)  :-
   Term  =..  [F|Args],                 % Get arguments
   substlist( Sub, Args, Sub1, Args1),  % Perform substitution on them
   Term1  =..  [F|Args1].


substlist( _, [], _, []).

substlist( Sub, [Term|Terms], Sub1, [Term1|Terms1])  :-
   substitute( Sub, Term, Sub1, Term1),
   substlist( Sub, Terms, Sub1, Terms1).