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

subsumes.pl

Patrick Blackburn, 2000.
Kristina Striegnitz, 2002.

This code is also based on Gazdar and Mellish.

This is an extension of subsumes.pl, such that empty feature
structures (represented as the empty list) are treated correctly. (The
only addition is the first clause of subsumes which wasn't there
before.)


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

Takes as input two feature structures written in our Prolog notation,
and checks whether the first one subsumes the second one.

Strategy: Instantiate all variables in the second feature structur
with atoms. Different variables get different atoms. Then try to
unify. If it works, the subsumption relation holds. (Reason: no new
information has to be added to the second feature structure.)
Otherwise, the subsumption relation does not hold.

Double negation to avoid destructively changing the feature
structures.

NOTE: you have to also consult unify.pl for this to work.

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% subsumes(?feature structure, ?feature structure)

%%% If F1 is empty, it clearly subsumes F2, no matter what F2 is.
subsumes([],_F2) :- !.

subsumes(F1,F2) :-
	\+ (inst_vars(F2), 
            \+ (unify0(F1,F2))).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% inst_vars(?feature structure)

inst_vars(F) :-
	inst_vars0(F,v(0),_).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% inst_vars0(?feature structure, +current atom, -next atom)

%%% 1st argument is a variable -> instantiate it
inst_vars0(F,I,v(I)) :-
	var(F),!,
	F = I.

%%% 1st arg is the empty list -> do nothing
inst_vars0([],I,I) :- !.

%%% 1st arg is a non-empty list -> instantiate all variables in the
%%% first element and then all variables in the rest
inst_vars0([H|T],I,IOut) :- !,
	inst_vars0(H,I,I0),
	inst_vars0(T,I0,IOut).

%%% 1st arg is a feature value pair -> instantiate all variables in
%%% the value
inst_vars0(_F:V,I,IOut) :- !,
	inst_vars0(V,I,IOut).

%%% do nothing in all other cases
inst_vars0(_,I,I).	


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