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

unify.pl

Patrick Blackburn, 2000.
Kristina Striegnitz, 2002.

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

Usage: unify(?feature structure, ?feature structure)

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(?feature structure, ?feature structure)
%%% A simple driver predicate. It calls unify/2 and writes out the
%%% result of unifying the input feature structures (if it is possible
%%% to unify them).
%%%
%%% Why is the result the value of Dag1? Because we are doing
%%% *destructive* unification. If the input dags are unifiable, then
%%% at the end of the unification process, the original input values
%%% no longer exist. Both Dag1 and Dag1 now hold the result of the
%%% unification process. So in fact, we could replace the third line
%%% of this driver by:
%%%
%%%      write('Result of unification is: '),nl, nl, write(Dag2),
%%%
%%% and it would work just as well. (The only difference would be that
%%% the items in the result might be written in a different order.)

unify(Dag1,Dag2) :- 
	unify0(Dag1,Dag2),
	nl,
	write('Result of unification is: '),nl,nl,write(Dag1),
	nl.


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