src/Pure/unify.ML
changeset 29269 5c25a2012975
parent 28173 f7b5b963205e
child 32032 a6a6e8031c14
equal deleted inserted replaced
29268:6aefc5ff8e63 29269:5c25a2012975
     1 (*  Title:      Pure/unify.ML
     1 (*  Title:      Pure/unify.ML
     2     ID:         $Id$
       
     3     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
     2     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
     4     Copyright   Cambridge University 1992
     3     Copyright   Cambridge University 1992
     5 
     4 
     6 Higher-Order Unification.
     5 Higher-Order Unification.
     7 
     6 
   102       and occur (Const _)  = false
   101       and occur (Const _)  = false
   103   | occur (Bound _)  = false
   102   | occur (Bound _)  = false
   104   | occur (Free _)  = false
   103   | occur (Free _)  = false
   105   | occur (Var (w, T))  =
   104   | occur (Var (w, T))  =
   106       if member (op =) (!seen) w then false
   105       if member (op =) (!seen) w then false
   107       else if eq_ix(v,w) then true
   106       else if Term.eq_ix (v, w) then true
   108         (*no need to lookup: v has no assignment*)
   107         (*no need to lookup: v has no assignment*)
   109       else (seen := w:: !seen;
   108       else (seen := w:: !seen;
   110             case Envir.lookup (env, (w, T)) of
   109             case Envir.lookup (env, (w, T)) of
   111           NONE    => false
   110           NONE    => false
   112         | SOME t => occur t)
   111         | SOME t => occur t)
   165       and occur (Const _)  = NoOcc
   164       and occur (Const _)  = NoOcc
   166   | occur (Bound _)  = NoOcc
   165   | occur (Bound _)  = NoOcc
   167   | occur (Free _)  = NoOcc
   166   | occur (Free _)  = NoOcc
   168   | occur (Var (w, T))  =
   167   | occur (Var (w, T))  =
   169       if member (op =) (!seen) w then NoOcc
   168       if member (op =) (!seen) w then NoOcc
   170       else if eq_ix(v,w) then Rigid
   169       else if Term.eq_ix (v, w) then Rigid
   171       else (seen := w:: !seen;
   170       else (seen := w:: !seen;
   172             case Envir.lookup (env, (w, T)) of
   171             case Envir.lookup (env, (w, T)) of
   173           NONE    => NoOcc
   172           NONE    => NoOcc
   174         | SOME t => occur t)
   173         | SOME t => occur t)
   175   | occur (Abs(_,_,body)) = occur body
   174   | occur (Abs(_,_,body)) = occur body
   176   | occur (t as f$_) =  (*switch to nonrigid search?*)
   175   | occur (t as f$_) =  (*switch to nonrigid search?*)
   177      (case head_of_in (env,f) of
   176      (case head_of_in (env,f) of
   178         Var (w,_) => (*w is not assigned*)
   177         Var (w,_) => (*w is not assigned*)
   179     if eq_ix(v,w) then Rigid
   178     if Term.eq_ix (v, w) then Rigid
   180     else  nonrigid t
   179     else  nonrigid t
   181       | Abs(_,_,body) => nonrigid t (*not in normal form*)
   180       | Abs(_,_,body) => nonrigid t (*not in normal form*)
   182       | _ => occomb t)
   181       | _ => occomb t)
   183   in  occur t  end;
   182   in  occur t  end;
   184 
   183 
   539 fun add_ffpair thy ((rbinder,t0,u0), (env,tpairs))
   538 fun add_ffpair thy ((rbinder,t0,u0), (env,tpairs))
   540       : Envir.env * (term*term)list =
   539       : Envir.env * (term*term)list =
   541   let val t = Envir.norm_term env t0  and  u = Envir.norm_term env u0
   540   let val t = Envir.norm_term env t0  and  u = Envir.norm_term env u0
   542   in  case  (head_of t, head_of u) of
   541   in  case  (head_of t, head_of u) of
   543       (Var(v,T), Var(w,U)) =>  (*Check for identical variables...*)
   542       (Var(v,T), Var(w,U)) =>  (*Check for identical variables...*)
   544   if eq_ix(v,w) then     (*...occur check would falsely return true!*)
   543   if Term.eq_ix (v, w) then     (*...occur check would falsely return true!*)
   545       if T=U then (env, add_tpair (rbinder, (t,u), tpairs))
   544       if T=U then (env, add_tpair (rbinder, (t,u), tpairs))
   546       else raise TERM ("add_ffpair: Var name confusion", [t,u])
   545       else raise TERM ("add_ffpair: Var name confusion", [t,u])
   547   else if Term.indexname_ord (v, w) = LESS then (*prefer to update the LARGER variable*)
   546   else if TermOrd.indexname_ord (v, w) = LESS then (*prefer to update the LARGER variable*)
   548        clean_ffpair thy ((rbinder, u, t), (env,tpairs))
   547        clean_ffpair thy ((rbinder, u, t), (env,tpairs))
   549         else clean_ffpair thy ((rbinder, t, u), (env,tpairs))
   548         else clean_ffpair thy ((rbinder, t, u), (env,tpairs))
   550     | _ => raise TERM ("add_ffpair: Vars expected", [t,u])
   549     | _ => raise TERM ("add_ffpair: Vars expected", [t,u])
   551   end;
   550   end;
   552 
   551