constant(X) :- atomic(X).

%----------------------------------------------

% subterm(Sub,Term)
% Sub is a subterm of term Term

subterm(Term,Term).
subterm(Sub,Term) :-
	compound(Term), functor(Term,_,N), subterm(N,Sub,Term).

subterm(N,Sub,Term) :-
	N>1, N1 is N-1, subterm(N1,Sub,Term).

subterm(N,Sub,Term) :-
	arg(N,Term,Arg), subterm(Sub,Arg).


%----------------------------------------------

% substitute(Old,New,OldTerm,NewTerm)
% the term NewTerm equals the term OldTerm except that each occurrence of
% Old in OldTerm corresponds to an occurrence of New in NewTerm


substitute(Old,New,Old,New).

substitute(Old,_,Term,Term) :-
	constant(Term), Term \== Old.

substitute(Old,New,Term,Term1) :-
	compound(Term),
	functor(Term,F,N),
	functor(Term1,F,N),
	substitute(N,Old,New,Term,Term1).

substitute(N,Old,New,Term,Term1) :-
	N > 0,
	arg(N,Term,Arg),
	substitute(Old,New,Arg,Arg1),
	arg(N,Term1,Arg1),
	N1 is N-1,
	substitute(N1,Old,New,Term,Term1).

substitute(0,_,_,_,_).