src/Pure/net.ML

Initial revision

(*  Title: 	net
    ID:         $Id$
    Author: 	Lawrence C Paulson, Cambridge University Computer Laboratory
    Copyright   1993  University of Cambridge

Discrimination nets: a data structure for indexing items

From the book 
    E. Charniak, C. K. Riesbeck, D. V. McDermott. 
    Artificial Intelligence Programming.
    (Lawrence Erlbaum Associates, 1980).  [Chapter 14]
*)

signature NET = 
  sig
  type key
  type 'a net
  exception DELETE and INSERT
  val delete: (key list * 'a) * 'a net * ('a*'a -> bool) -> 'a net
  val delete_term:   (term * 'a) * 'a net * ('a*'a -> bool) -> 'a net
  val empty: 'a net
  val insert: (key list * 'a) * 'a net * ('a*'a -> bool) -> 'a net
  val insert_term:   (term * 'a) * 'a net * ('a*'a -> bool) -> 'a net
  val lookup: 'a net * key list -> 'a list
  val match_term: 'a net -> term -> 'a list
  val key_of_term: term -> key list
  val unify_term: 'a net -> term -> 'a list
  end;


functor NetFun () : NET = 
struct

datatype key = CombK | VarK | AtomK of string;

(*Only 'loose' bound variables could arise, since Abs nodes are skipped*)
fun string_of_bound i = "*B*" ^ chr i;

(*Keys are preorder lists of symbols -- constants, Vars, bound vars, ...
  Any term whose head is a Var is regarded entirely as a Var;
  abstractions are also regarded as Vars (to cover eta-conversion)
*)
fun add_key_of_terms (t, cs) = 
  let fun rands (f$t, cs) = CombK :: rands (f, add_key_of_terms(t, cs))
	| rands (Const(c,_), cs) = AtomK c :: cs
	| rands (Free(c,_),  cs) = AtomK c :: cs
	| rands (Bound i,  cs) = AtomK (string_of_bound i) :: cs
  in case (head_of t) of
      Var _       => VarK :: cs
    | Abs (_,_,t) => VarK :: cs
    | _ => rands(t,cs)
  end;

(*convert a term to a key -- a list of keys*)
fun key_of_term t = add_key_of_terms (t, []);


(*Trees indexed by key lists: each arc is labelled by a key.
  Each node contains a list of items, and arcs to children.
  Keys in the association list (alist) are stored in ascending order.
  The empty key addresses the entire net.
  Lookup functions preserve order in items stored at same level.
*)
datatype 'a net = Leaf of 'a list
		| Net of {comb: 'a net, 
			  var: 'a net,
			  alist: (string * 'a net) list};

val empty = Leaf[];
val emptynet = Net{comb=empty, var=empty, alist=[]};


(*** Insertion into a discrimination net ***)

exception INSERT;	(*duplicate item in the net*)


(*Adds item x to the list at the node addressed by the keys.
  Creates node if not already present.
  eq is the equality test for items. 
  The empty list of keys generates a Leaf node, others a Net node.
*)
fun insert ((keys,x), net, eq) =
  let fun ins1 ([], Leaf xs) = 
            if gen_mem eq (x,xs) then  raise INSERT  else Leaf(x::xs)
        | ins1 (keys, Leaf[]) = ins1 (keys, emptynet)   (*expand empty...*)
        | ins1 (CombK :: keys, Net{comb,var,alist}) =
	    Net{comb=ins1(keys,comb), var=var, alist=alist}
	| ins1 (VarK :: keys, Net{comb,var,alist}) =
	    Net{comb=comb, var=ins1(keys,var), alist=alist}
	| ins1 (AtomK a :: keys, Net{comb,var,alist}) =
	    let fun newpair net = (a, ins1(keys,net)) 
		fun inslist [] = [newpair empty]
		  | inslist((b: string, netb) :: alist) =
		      if a=b then newpair netb :: alist
		      else if a<b then (*absent, ins1ert in alist*)
			  newpair empty :: (b,netb) :: alist
		      else (*a>b*) (b,netb) :: inslist alist
	    in  Net{comb=comb, var=var, alist= inslist alist}  end
  in  ins1 (keys,net)  end;

fun insert_term ((t,x), net, eq) = insert((key_of_term t, x), net, eq);

(*** Deletion from a discrimination net ***)

exception DELETE;	(*missing item in the net*)

(*Create a new Net node if it would be nonempty*)
fun newnet {comb=Leaf[], var=Leaf[], alist=[]} = empty
  | newnet {comb,var,alist} = Net{comb=comb, var=var, alist=alist};

(*add new (b,net) pair to the alist provided net is nonempty*)
fun conspair((b, Leaf[]), alist) = alist
  | conspair((b, net), alist)    = (b, net) :: alist;

(*Deletes item x from the list at the node addressed by the keys.
  Raises DELETE if absent.  Collapses the net if possible.
  eq is the equality test for items. *)
fun delete ((keys, x), net, eq) = 
  let fun del1 ([], Leaf xs) =
            if gen_mem eq (x,xs) then Leaf (gen_rem eq (xs,x))
            else raise DELETE
	| del1 (keys, Leaf[]) = raise DELETE
	| del1 (CombK :: keys, Net{comb,var,alist}) =
	    newnet{comb=del1(keys,comb), var=var, alist=alist}
	| del1 (VarK :: keys, Net{comb,var,alist}) =
	    newnet{comb=comb, var=del1(keys,var), alist=alist}
	| del1 (AtomK a :: keys, Net{comb,var,alist}) =
	    let fun newpair net = (a, del1(keys,net)) 
		fun dellist [] = raise DELETE
		  | dellist((b: string, netb) :: alist) =
		      if a=b then conspair(newpair netb, alist)
		      else if a<b then (*absent*) raise DELETE
		      else (*a>b*)  (b,netb) :: dellist alist
	    in  newnet{comb=comb, var=var, alist= dellist alist}  end
  in  del1 (keys,net)  end;

fun delete_term ((t,x), net, eq) = delete((key_of_term t, x), net, eq);

(*** Retrieval functions for discrimination nets ***)

exception OASSOC;

(*Ordered association list lookup*)
fun oassoc ([], a: string) = raise OASSOC
  | oassoc ((b,x)::pairs, a) =
      if b<a then oassoc(pairs,a)
      else if a=b then x
      else raise OASSOC;

(*Return the list of items at the given node, [] if no such node*)
fun lookup (Leaf(xs), []) = xs
  | lookup (Leaf _, _::_) = []	(*non-empty keys and empty net*)
  | lookup (Net{comb,var,alist}, CombK :: keys) = lookup(comb,keys)
  | lookup (Net{comb,var,alist}, VarK :: keys) = lookup(var,keys)
  | lookup (Net{comb,var,alist}, AtomK a :: keys) = 
      lookup(oassoc(alist,a),keys)  handle  OASSOC => [];


(*Skipping a term in a net.  Recursively skip 2 levels if a combination*)
fun net_skip (Leaf _, nets) = nets
  | net_skip (Net{comb,var,alist}, nets) = 
    foldr net_skip 
          (net_skip (comb,[]), 
	   foldr (fn ((_,net), nets) => net::nets) (alist, var::nets));

(** Matching and Unification**)

(*conses the linked net, if present, to nets*)
fun look1 (alist, a) nets =
       oassoc(alist,a) :: nets  handle  OASSOC => nets;

(*Return the nodes accessible from the term (cons them before nets) 
  "unif" signifies retrieval for unification rather than matching.
  Var in net matches any term.
  Abs in object (and Var if "unif") regarded as wildcard.
  If not "unif", Var in object only matches a variable in net.*)
fun matching unif t (net,nets) =
  let fun rands _ (Leaf _, nets) = nets
	| rands t (Net{comb,alist,...}, nets) =
	    case t of 
		(f$t) => foldr (matching unif t) (rands f (comb,[]), nets)
	      | (Const(c,_)) => look1 (alist, c) nets
	      | (Free(c,_))  => look1 (alist, c) nets
	      | (Bound i)    => look1 (alist, string_of_bound i) nets
  in 
     case net of
	 Leaf _ => nets
       | Net{var,...} =>
	   case (head_of t) of
	       Var _      => if unif then net_skip (net,nets)
			     else var::nets	   (*only matches Var in net*)
	     | Abs(_,_,u) => net_skip (net,nets)   (*could match anything*)
	     | _ => rands t (net, var::nets)	   (*var could match also*)
  end;

val extract_leaves = flat o map (fn Leaf(xs) => xs);

(*return items whose key could match t*)
fun match_term net t = 
    extract_leaves (matching false t (net,[]));

(*return items whose key could unify with t*)
fun unify_term net t = 
    extract_leaves (matching true t (net,[]));

end;