/*********************************************************************

unify_silent.pl

Patrick Blackburn, 2000.
Kristina Striegnitz, 2002.

This code is essentially the program discussed on pages 235 -- 239 of
Gazdar and Mellish.

This is the same as unify_fixed.pl, but we suppress output onto the
screen, and return the result of the unification in an extra argument.

Usage: unify_silent(?feature structure, ?feature structure, -result)

Takes as input two feature structures written in our Prolog notation,
and attempts to unify them. The method used is destructive: if
unification succeeds, at the end, both input arguments are
instantiated to the result of the unification.

*********************************************************************/

:- op(500, xfy, --->).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% unify0(?feature structure, ?feature structure)

%%% Base case.
%%% If we can use Prolog unification, we do:
unify0(Dag,Dag) :- !.        

%%% Recursive step.
%%% We split the feature structure in the first argument into the
%%% initial pair 'Feature:Value', and the 'Rest' of the list. Then
%%% comes the curcial step: we call val/4 to ensure that 'Feature' has
%%% the value 'Value' in 'Dag', the second feature structure. 'val'
%%% also does something else: in its fourth argument a new feature
%%% structure, StripDag, which contains everything in Dag apart from
%%% the value for Feature. Finally, we recursively call unify on the
%%% Rest and StripDag.
unify0([Feature:Value|Rest],Dag) :-  
	val(Feature,Value,Dag,StripDag),   
	unify0(Rest,StripDag).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% val(+feature, +value, +feature structure, -feature structure)
%%% The fourth argument is the result of stripping the pair
%%% 'Feature:Value' out of 'Dag'.

%%% If the desired feature, 'Feature', is found as the first argument,
%%% we see if 'Value1' can be unified with 'Value2', via a call to
%%% unify0/2 (hence val/4 and unify/2 are mutually recursive). Note
%%% that the fourth argument is just the tail of the third argument:
%%% this is how the stripping takes place.
val(Feature,Value1,[Feature:Value2|Rest],Rest) :-
    !,
    unify0(Value1,Value2).


%%% The desired feature, 'Feature', is not the first element of the
%%% list, so we recursively call val/4 on the remainder 'Rest' of the list.
val(Feature,Value,[Dag|Rest],[Dag|NewRest]) :-
    !,
    val(Feature,Value,Rest,NewRest).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% unify_silent(?feature structure, ?feature structure, -feature structure)
%%% The first two clauses handle cases where one of the input feature
%%% structure is empty.
%%% The third clause calls unify0/2 and returns the result of unifying
%%% the first two feature structures  (if it is possible to unify
%%% them) in the third feature structure.

%%% The unification is *destructive*. If the input dags are unifiable,
%%% then at the end of the unification process, the original input
%%% values may have been destroyed. In that case both Dag1 and Dag2
%%% hold the result of the unification process.

unify_silent([],Dag,Dag) :- !.

unify_silent(Dag,[],Dag) :- !.

unify_silent(Dag1, Dag2, Dag1) :-
	unify0(Dag1,Dag2).


/**********************************************************************
                    That's all, folks!
***********************************************************************/