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 *) |