mnemosyne_unify.erl

OTP是开放电信平台的简称

    apply_bind_triggers(Triggers, Bs, ordsets:new()).


apply_bind_triggers([H|T], Bs, KeptTriggers) when is_list(H) ->
    apply_bind_triggers(T, Bs, apply_bind_triggers(H,Bs,KeptTriggers));

apply_bind_triggers([T|Ts], Bs, KeptTriggers) ->
    {M,F,A} = T,
    case apply(M,F,[Bs|A]) of	% can throw(fail)
	remove_trigger ->
	    apply_bind_triggers(Ts, Bs, KeptTriggers);

	keep_trigger ->
	    apply_bind_triggers(Ts, Bs, 
				ordsets:add_element(T,KeptTriggers))
    end;

apply_bind_triggers([], Bs, KeptTriggers) ->
    KeptTriggers.

	
%%%----------------------------------------------------------------
variables({'#var',U}, Set) ->
    ordsets:add_element(U, Set);

variables([U|Us], Set) -> 
    variables(Us, variables(U,Set));

variables(U, Set) when is_tuple(U) ->
    variables(tuple_to_list(U), Set);

variables(_, Set) ->
    Set.

%%%----------------------------------------------------------------
count_variables({'#var','_'}, Dict) ->
    Dict;

count_variables({'#var',V}, Dict) ->
    insert_count_dict(V, Dict);

count_variables([U|Us], Dict) -> 
    count_variables(Us, count_variables(U,Dict));

count_variables(U, Dict) when is_tuple(U) ->
    count_variables(tuple_to_list(U), Dict);

count_variables(_, Dict) ->
    Dict.


insert_count_dict(V, Dict) ->
    case lists:keysearch(V,1,Dict) of
	{value, {V,N0}} ->
	    lists:keyreplace(V,1,Dict,{V,N0+1});
	false ->
	    [{V,1}|Dict]
    end.

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

rename_variables({'#var','_'}, S) -> 
    {{'#var','_'}, S};

rename_variables({'#var',X}, S) -> 
    case lists:keysearch(X,1,S) of
	{value,{X,V}} -> 
	    {V,S};
	false -> 
	    V = mnemosyne_lib:unique_var(X),
	    {V,[{X,V}|S]}
    end;

rename_variables([H|T], S) ->
    {Hp,Hs} = rename_variables(H, S),
    {Tp,Ts} = rename_variables(T, Hs),
    {[Hp|Tp], Ts};

rename_variables(T, S) when is_tuple(T) ->
    {Tp,Ts} = rename_variables(tuple_to_list(T), S),
    {list_to_tuple(Tp), Ts};

rename_variables(X, S) -> 
    {X,S}.


%%%----------------------------------------------------------------
deref_bs({L,K,V0,R}, Bs) ->
    V = 
	case V0 of
	    {'#var',_} ->
		case deref(any,K,Bs) of
		    {'#value',Val} -> {'#value',inst(Val,Bs)};
		    Others -> Others
		end;
	    {'#bind_trigger',Ts} ->
		{'#bind_trigger', apply_bind_triggers(Ts,Bs)};
	    Others ->
		inst(V0,Bs)
	end,
    {deref_bs(L,Bs), K, V, deref_bs(R,Bs)};
deref_bs([], Bs) ->
    [].


count_bs_vars1({L,V,_,R}, Dict) ->
    count_bs_vars1(L, count_bs_vars1(R,insert_count_dict(V,Dict)));
count_bs_vars1([], Dict) ->
    Dict.

%count_bs_vars1([{V,_}|Vs], Dict) -> 
%    count_bs_vars1(Vs, insert_count_dict(V,Dict));
%count_bs_vars1([], Dict) -> Dict.

%deref_bs([{U,X}|L], Bs, Acc) ->
%    New = 
%	case X of
%	    {'#var',V} ->
%		case deref(any,U,Bs) of
%		    {'#value',Val} -> {'#value',inst(Val,Bs)};
%		    Others -> Others
%		end;
	    
%	    {'#bind_trigger',Ts} ->
%		{'#bind_trigger', apply_bind_triggers(Ts,Bs)};
	    
%	    Others ->
%		inst(X,Bs)
%	end,
%    deref_bs(L, Bs, [{U,New}|Acc]);

%deref_bs([], _, Acc) ->
%    Acc.


inst([H|T], Bs) -> 
    [inst(H,Bs) | inst(T,Bs)];

inst({'#var',V}, Bs) ->
    %% return last variable in chain or value but not a bind_trigger
    case deref(var_val, V, Bs) of
	{'#value',Val} -> inst(Val,Bs);
	Var -> Var
    end;

inst(X, Bs) when is_tuple(X) -> 
    list_to_tuple(inst(tuple_to_list(X), Bs));

inst(X, Bs) ->
    X.


get_bound_vars(Bs, What) -> get_bound_vars(Bs, Bs, What, ordsets:new()).

get_bound_vars({L,V,{Type,_},R}, Bs, What, Set) ->
    get_bound_vars(L, Bs, What, 
		   get_bound_vars(R, Bs, What,
				  update_bound_set(Type,Bs,What,V,Set)));
get_bound_vars([], _, _, Set) ->
    Set.

update_bound_set(Type, Bs, all, V, Set) ->
    ordsets:add_element(V,Set);
update_bound_set(Type, Bs, What, V, Set) ->
    case Type of
	What -> 
	    ordsets:add_element(V,Set);
	'#var' ->
	    case deref(any,V,Bs) of
		{What,_} -> ordsets:add_element(V,Set);
		_ -> Set
	    end;
	_ ->
	    Set
    end.


%%%----------------------------------------------------------------
%%% deref(Type, VariableNAME, Bindings)  find out what VariableNAME is bound to
%%%    follows chains like X->Y->.....->Z->VAL
%%%                        VAL = {'#value',    Value}
%%%                              {'#var',      Name}
%%%                              {'#bind_trigger',Bind_Trigger}
%%%    if Type = var_val : returns last '#var' or '#value'
%%%       Type = var     : returns last '#var'
%%%       Type = any     : returns VAL


deref(Type, Var, Bs) ->
    case BoundTo=lookup_binding(Var,Bs) of
	'#false' -> {'#var',Var};

	{'#var',X} when X=/=Var -> deref(Type, X, Bs);

	{'#value',Value}  when Type== var -> {'#var',Var};
	{'#value',Value}                  -> BoundTo;

	{'#bind_trigger',C} when Type==var_val ->  {'#var',Var};
	{'#bind_trigger',C} when Type==var     ->  {'#var',Var};
	{'#bind_trigger',C} when Type==any     ->  BoundTo
    end.

%%%----------------------------------------------------------------
remove(L, R, KeepRemove, OrdSet) ->
    %% No common keys in L and R
    insert_bs_bs(delete_bindings(L, KeepRemove, OrdSet),
		 delete_bindings(R, KeepRemove, OrdSet)).
    

%%% returns Bs2 + those bindings in Bs1 that are not present in Bs2

insert_bs_bs(Bs1, Bs2) ->
    insert_bs_bs(bindings_to_list(Bs1), bindings_to_list(Bs2), 
		 empty_bindings()).

insert_bs_bs([{K1,V1}|L1], [{K2,V2}|L2], Acc) ->
    if
	K1 < K2 -> insert_bs_bs(L1, [{K2,V2}|L2], mk_binding(K1,V1,Acc));
	K1 > K2 -> insert_bs_bs([{K1,V1}|L1], L2, mk_binding(K2,V2,Acc));
	K1 == K2-> insert_bs_bs(L1, L2, mk_binding(K2,V2,Acc))
    end;
insert_bs_bs([], [], Acc) -> Acc;
insert_bs_bs([], [{K,V}|L], Acc) -> insert_bs_bs([], L, mk_binding(K,V,Acc));
insert_bs_bs([{K,V}|L], [], Acc) -> insert_bs_bs(L, [], mk_binding(K,V,Acc)).

%%%================================================================
%%%
%%% Access functions for the Bindings data structure
%%%
%%%

lookup_binding(Var, {L,Key,Value,R}) ->
    if
	Var<Key  -> lookup_binding(Var, L);
	Var>Key  -> lookup_binding(Var, R);
	Var==Key -> Value
    end;
lookup_binding(Var, []) -> 
    '#false'.


%% When the Var already is bound to Value there will be some unnecessary
%% setelement

mk_binding(Var, Value, Tree) when is_tuple(Tree) ->
    {L,Key,KeyVal,R} = Tree,
    if
	Var<Key -> setelement(1, Tree, mk_binding(Var,Value,L));
	Var>Key -> setelement(4, Tree, mk_binding(Var,Value,R));
	Key==Var, KeyVal==Value -> Tree;
	Key==Var -> throw(fail)
    end;
mk_binding(Var, Value, []) -> 
    {[],Var,Value,[]}.



rebind(Var, Value, Tree) when is_tuple(Tree) ->
    {L,Key,KeyVal,R} = Tree,
    if
	Var<Key  -> setelement(1, Tree, rebind(Var,Value,L));
	Var>Key  -> setelement(4, Tree, rebind(Var,Value,R));
	Key==Var -> setelement(3, Tree, Value)
    end;
rebind(Var, Value, []) -> 
    {[],Var,Value,[]}.


bindings_to_list({L,K,V,R}, Acc) ->
    bindings_to_list(L, [{K,V}|bindings_to_list(R,Acc)]);
bindings_to_list([], Acc) ->
    Acc.


list_to_bindings([{V,Val}|L], Bs) ->
    list_to_bindings(L, mk_binding(V,Val,Bs));
list_to_bindings([], Bs) ->
    Bs.


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

numbervars(T, N, Vars) when Vars==[] -> 
    T;
numbervars(T, N, Vars) ->
    numbervars1(T, assign_numbers(Vars,N,[])).

numbervars1({'#variable',V}, D) ->
    {'#variable',{'#var',element(2,ok(lists:keysearch(V,1,D)))}};
numbervars1(T, D) when is_tuple(T) ->
    list_to_tuple(numbervars1(tuple_to_list(T), D));
numbervars1([H|T], D) ->
    [numbervars1(H,D) | numbervars1(T,D)];
numbervars1(T, _) ->
    T.

ok({value,V}) -> V.

assign_numbers([V|Vs], N, L) -> assign_numbers(Vs, N+1, [{V,N}|L]);
assign_numbers([],_,L) -> L.