src/Pure/term.ML
changeset 15531 08c8dad8e399
parent 15472 4674102737e9
child 15570 8d8c70b41bab
equal deleted inserted replaced
15530:6f43714517ee 15531:08c8dad8e399
   466     val ren = match_bvs (pat, obj, []);
   466     val ren = match_bvs (pat, obj, []);
   467     fun ren_abs (Abs (x, T, b)) =
   467     fun ren_abs (Abs (x, T, b)) =
   468           Abs (if_none (assoc_string (ren, x)) x, T, ren_abs b)
   468           Abs (if_none (assoc_string (ren, x)) x, T, ren_abs b)
   469       | ren_abs (f $ t) = ren_abs f $ ren_abs t
   469       | ren_abs (f $ t) = ren_abs f $ ren_abs t
   470       | ren_abs t = t
   470       | ren_abs t = t
   471   in if null ren then None else Some (ren_abs t) end;
   471   in if null ren then NONE else SOME (ren_abs t) end;
   472 
   472 
   473 (*Accumulate all 'loose' bound vars referring to level 'lev' or beyond.
   473 (*Accumulate all 'loose' bound vars referring to level 'lev' or beyond.
   474    (Bound 0) is loose at level 0 *)
   474    (Bound 0) is loose at level 0 *)
   475 fun add_loose_bnos (Bound i, lev, js) =
   475 fun add_loose_bnos (Bound i, lev, js) =
   476         if i<lev then js  else  (i-lev) ins_int js
   476         if i<lev then js  else  (i-lev) ins_int js
   594 (*Substitute new for free occurrences of old in a term*)
   594 (*Substitute new for free occurrences of old in a term*)
   595 fun subst_free [] = (fn t=>t)
   595 fun subst_free [] = (fn t=>t)
   596   | subst_free pairs =
   596   | subst_free pairs =
   597       let fun substf u =
   597       let fun substf u =
   598             case gen_assoc (op aconv) (pairs, u) of
   598             case gen_assoc (op aconv) (pairs, u) of
   599                 Some u' => u'
   599                 SOME u' => u'
   600               | None => (case u of Abs(a,T,t) => Abs(a, T, substf t)
   600               | NONE => (case u of Abs(a,T,t) => Abs(a, T, substf t)
   601                                  | t$u' => substf t $ substf u'
   601                                  | t$u' => substf t $ substf u'
   602                                  | _ => u)
   602                                  | _ => u)
   603       in  substf  end;
   603       in  substf  end;
   604 
   604 
   605 (*a total, irreflexive ordering on index names*)
   605 (*a total, irreflexive ordering on index names*)
   669 (*Substitute for type/term Vars in a term; see also envir/norm_term*)
   669 (*Substitute for type/term Vars in a term; see also envir/norm_term*)
   670 fun subst_vars(iTs,itms) = if null iTs then subst_Vars itms else
   670 fun subst_vars(iTs,itms) = if null iTs then subst_Vars itms else
   671   let fun subst(Const(a,T)) = Const(a,typ_subst_TVars iTs T)
   671   let fun subst(Const(a,T)) = Const(a,typ_subst_TVars iTs T)
   672         | subst(Free(a,T)) = Free(a,typ_subst_TVars iTs T)
   672         | subst(Free(a,T)) = Free(a,typ_subst_TVars iTs T)
   673         | subst(v as Var(ixn,T)) = (case assoc(itms,ixn) of
   673         | subst(v as Var(ixn,T)) = (case assoc(itms,ixn) of
   674             None   => Var(ixn,typ_subst_TVars iTs T)
   674             NONE   => Var(ixn,typ_subst_TVars iTs T)
   675           | Some t => t)
   675           | SOME t => t)
   676         | subst(b as Bound _) = b
   676         | subst(b as Bound _) = b
   677         | subst(Abs(a,T,t)) = Abs(a,typ_subst_TVars iTs T,subst t)
   677         | subst(Abs(a,T,t)) = Abs(a,typ_subst_TVars iTs T,subst t)
   678         | subst(f$t) = subst f $ subst t
   678         | subst(f$t) = subst f $ subst t
   679   in subst end;
   679   in subst end;
   680 
   680 
  1009 (*Substitute for type Vars in a type, version using Vartab*)
  1009 (*Substitute for type Vars in a type, version using Vartab*)
  1010 fun typ_subst_TVars_Vartab iTs T = if Vartab.is_empty iTs then T else
  1010 fun typ_subst_TVars_Vartab iTs T = if Vartab.is_empty iTs then T else
  1011   let fun subst(Type(a, Ts)) = Type(a, map subst Ts)
  1011   let fun subst(Type(a, Ts)) = Type(a, map subst Ts)
  1012         | subst(T as TFree _) = T
  1012         | subst(T as TFree _) = T
  1013         | subst(T as TVar(ixn, _)) =
  1013         | subst(T as TVar(ixn, _)) =
  1014             (case Vartab.lookup (iTs, ixn) of None => T | Some(U) => U)
  1014             (case Vartab.lookup (iTs, ixn) of NONE => T | SOME(U) => U)
  1015   in subst T end;
  1015   in subst T end;
  1016 
  1016 
  1017 (*Substitute for type Vars in a term, version using Vartab*)
  1017 (*Substitute for type Vars in a term, version using Vartab*)
  1018 val subst_TVars_Vartab = map_term_types o typ_subst_TVars_Vartab;
  1018 val subst_TVars_Vartab = map_term_types o typ_subst_TVars_Vartab;
  1019 
  1019 
  1027 
  1027 
  1028 val memo_types = ref (Typtab.empty: typ Typtab.table);
  1028 val memo_types = ref (Typtab.empty: typ Typtab.table);
  1029 
  1029 
  1030 fun compress_type T =
  1030 fun compress_type T =
  1031   (case Typtab.lookup (! memo_types, T) of
  1031   (case Typtab.lookup (! memo_types, T) of
  1032     Some T' => T'
  1032     SOME T' => T'
  1033   | None =>
  1033   | NONE =>
  1034       let val T' = (case T of Type (a, Ts) => Type (a, map compress_type Ts) | _ => T)
  1034       let val T' = (case T of Type (a, Ts) => Type (a, map compress_type Ts) | _ => T)
  1035       in memo_types := Typtab.update ((T', T'), ! memo_types); T' end);
  1035       in memo_types := Typtab.update ((T', T'), ! memo_types); T' end);
  1036 
  1036 
  1037 
  1037 
  1038 (** Sharing of atomic terms **)
  1038 (** Sharing of atomic terms **)
  1041 
  1041 
  1042 fun share_term (t $ u) = share_term t $ share_term u
  1042 fun share_term (t $ u) = share_term t $ share_term u
  1043   | share_term (Abs (a, T, u)) = Abs (a, T, share_term u)
  1043   | share_term (Abs (a, T, u)) = Abs (a, T, share_term u)
  1044   | share_term t =
  1044   | share_term t =
  1045       (case Termtab.lookup (! memo_terms, t) of
  1045       (case Termtab.lookup (! memo_terms, t) of
  1046         Some t' => t'
  1046         SOME t' => t'
  1047       | None => (memo_terms := Termtab.update ((t, t), ! memo_terms); t));
  1047       | NONE => (memo_terms := Termtab.update ((t, t), ! memo_terms); t));
  1048 
  1048 
  1049 val compress_term = share_term o map_term_types compress_type;
  1049 val compress_term = share_term o map_term_types compress_type;
  1050 
  1050 
  1051 
  1051 
  1052 (* dummy patterns *)
  1052 (* dummy patterns *)