768 o #const) constrs) |
768 o #const) constrs) |
769 |
769 |
770 val empty_rel = KK.Product (KK.None, KK.None) |
770 val empty_rel = KK.Product (KK.None, KK.None) |
771 |
771 |
772 (* nfa_table -> typ -> typ -> KK.rel_expr list *) |
772 (* nfa_table -> typ -> typ -> KK.rel_expr list *) |
773 fun direct_path_rel_exprs nfa start final = |
773 fun direct_path_rel_exprs nfa start_T final_T = |
774 case AList.lookup (op =) nfa final of |
774 case AList.lookup (op =) nfa final_T of |
775 SOME trans => map fst (filter (curry (op =) start o snd) trans) |
775 SOME trans => map fst (filter (curry (op =) start_T o snd) trans) |
776 | NONE => [] |
776 | NONE => [] |
777 (* kodkod_constrs -> nfa_table -> typ list -> typ -> typ -> KK.rel_expr *) |
777 (* kodkod_constrs -> nfa_table -> typ list -> typ -> typ -> KK.rel_expr *) |
778 and any_path_rel_expr ({kk_union, ...} : kodkod_constrs) nfa [] start final = |
778 and any_path_rel_expr ({kk_union, ...} : kodkod_constrs) nfa [] start_T |
779 fold kk_union (direct_path_rel_exprs nfa start final) |
779 final_T = |
780 (if start = final then KK.Iden else empty_rel) |
780 fold kk_union (direct_path_rel_exprs nfa start_T final_T) |
781 | any_path_rel_expr (kk as {kk_union, ...}) nfa (q :: qs) start final = |
781 (if start_T = final_T then KK.Iden else empty_rel) |
782 kk_union (any_path_rel_expr kk nfa qs start final) |
782 | any_path_rel_expr (kk as {kk_union, ...}) nfa (T :: Ts) start_T final_T = |
783 (knot_path_rel_expr kk nfa qs start q final) |
783 kk_union (any_path_rel_expr kk nfa Ts start_T final_T) |
|
784 (knot_path_rel_expr kk nfa Ts start_T T final_T) |
784 (* kodkod_constrs -> nfa_table -> typ list -> typ -> typ -> typ |
785 (* kodkod_constrs -> nfa_table -> typ list -> typ -> typ -> typ |
785 -> KK.rel_expr *) |
786 -> KK.rel_expr *) |
786 and knot_path_rel_expr (kk as {kk_join, kk_reflexive_closure, ...}) nfa qs start |
787 and knot_path_rel_expr (kk as {kk_join, kk_reflexive_closure, ...}) nfa Ts |
787 knot final = |
788 start_T knot_T final_T = |
788 kk_join (kk_join (any_path_rel_expr kk nfa qs knot final) |
789 kk_join (kk_join (any_path_rel_expr kk nfa Ts knot_T final_T) |
789 (kk_reflexive_closure (loop_path_rel_expr kk nfa qs knot))) |
790 (kk_reflexive_closure (loop_path_rel_expr kk nfa Ts knot_T))) |
790 (any_path_rel_expr kk nfa qs start knot) |
791 (any_path_rel_expr kk nfa Ts start_T knot_T) |
791 (* kodkod_constrs -> nfa_table -> typ list -> typ -> KK.rel_expr *) |
792 (* kodkod_constrs -> nfa_table -> typ list -> typ -> KK.rel_expr *) |
792 and loop_path_rel_expr ({kk_union, ...} : kodkod_constrs) nfa [] start = |
793 and loop_path_rel_expr ({kk_union, ...} : kodkod_constrs) nfa [] start_T = |
793 fold kk_union (direct_path_rel_exprs nfa start start) empty_rel |
794 fold kk_union (direct_path_rel_exprs nfa start_T start_T) empty_rel |
794 | loop_path_rel_expr (kk as {kk_union, kk_closure, ...}) nfa (q :: qs) start = |
795 | loop_path_rel_expr (kk as {kk_union, kk_closure, ...}) nfa (T :: Ts) |
795 if start = q then |
796 start_T = |
796 kk_closure (loop_path_rel_expr kk nfa qs start) |
797 if start_T = T then |
|
798 kk_closure (loop_path_rel_expr kk nfa Ts start_T) |
797 else |
799 else |
798 kk_union (loop_path_rel_expr kk nfa qs start) |
800 kk_union (loop_path_rel_expr kk nfa Ts start_T) |
799 (knot_path_rel_expr kk nfa qs start q start) |
801 (knot_path_rel_expr kk nfa Ts start_T T start_T) |
800 |
802 |
801 (* nfa_table -> unit NfaGraph.T *) |
803 (* nfa_table -> unit NfaGraph.T *) |
802 fun graph_for_nfa nfa = |
804 fun graph_for_nfa nfa = |
803 let |
805 let |
804 (* typ -> unit NfaGraph.T -> unit NfaGraph.T *) |
806 (* typ -> unit NfaGraph.T -> unit NfaGraph.T *) |
805 fun new_node q = perhaps (try (NfaGraph.new_node (q, ()))) |
807 fun new_node T = perhaps (try (NfaGraph.new_node (T, ()))) |
806 (* nfa_table -> unit NfaGraph.T -> unit NfaGraph.T *) |
808 (* nfa_table -> unit NfaGraph.T -> unit NfaGraph.T *) |
807 fun add_nfa [] = I |
809 fun add_nfa [] = I |
808 | add_nfa ((_, []) :: nfa) = add_nfa nfa |
810 | add_nfa ((_, []) :: nfa) = add_nfa nfa |
809 | add_nfa ((q, ((_, q') :: transitions)) :: nfa) = |
811 | add_nfa ((T, ((_, T') :: transitions)) :: nfa) = |
810 add_nfa ((q, transitions) :: nfa) o NfaGraph.add_edge (q, q') o |
812 add_nfa ((T, transitions) :: nfa) o NfaGraph.add_edge (T, T') o |
811 new_node q' o new_node q |
813 new_node T' o new_node T |
812 in add_nfa nfa NfaGraph.empty end |
814 in add_nfa nfa NfaGraph.empty end |
813 |
815 |
814 (* nfa_table -> nfa_table list *) |
816 (* nfa_table -> nfa_table list *) |
815 fun strongly_connected_sub_nfas nfa = |
817 fun strongly_connected_sub_nfas nfa = |
816 nfa |> graph_for_nfa |> NfaGraph.strong_conn |
818 nfa |> graph_for_nfa |> NfaGraph.strong_conn |
817 |> map (fn keys => filter (member (op =) keys o fst) nfa) |
819 |> map (fn keys => filter (member (op =) keys o fst) nfa) |
818 |
820 |
819 (* dtype_spec list -> kodkod_constrs -> nfa_table -> typ -> KK.formula *) |
821 (* kodkod_constrs -> dtype_spec list -> nfa_table -> typ -> KK.formula *) |
820 fun acyclicity_axiom_for_datatype dtypes kk nfa start = |
822 fun acyclicity_axiom_for_datatype kk dtypes nfa start_T = |
821 #kk_no kk (#kk_intersect kk |
823 #kk_no kk (#kk_intersect kk |
822 (loop_path_rel_expr kk nfa (map fst nfa) start) KK.Iden) |
824 (loop_path_rel_expr kk nfa (map fst nfa) start_T) KK.Iden) |
823 (* hol_context -> kodkod_constrs -> nut NameTable.table -> dtype_spec list |
825 (* hol_context -> kodkod_constrs -> nut NameTable.table -> dtype_spec list |
824 -> KK.formula list *) |
826 -> KK.formula list *) |
825 fun acyclicity_axioms_for_datatypes hol_ctxt kk rel_table dtypes = |
827 fun acyclicity_axioms_for_datatypes hol_ctxt kk rel_table dtypes = |
826 map_filter (nfa_entry_for_datatype hol_ctxt kk rel_table dtypes) dtypes |
828 map_filter (nfa_entry_for_datatype hol_ctxt kk rel_table dtypes) dtypes |
827 |> strongly_connected_sub_nfas |
829 |> strongly_connected_sub_nfas |
828 |> maps (fn nfa => map (acyclicity_axiom_for_datatype dtypes kk nfa o fst) |
830 |> maps (fn nfa => |
829 nfa) |
831 map (acyclicity_axiom_for_datatype kk dtypes nfa o fst) nfa) |
830 |
832 |
831 (* hol_context -> int -> kodkod_constrs -> nut NameTable.table -> KK.rel_expr |
833 (* hol_context -> int -> kodkod_constrs -> nut NameTable.table -> KK.rel_expr |
832 -> constr_spec -> int -> KK.formula *) |
834 -> constr_spec -> int -> KK.formula *) |
833 fun sel_axiom_for_sel hol_ctxt j0 |
835 fun sel_axiom_for_sel hol_ctxt j0 |
834 (kk as {kk_all, kk_implies, kk_formula_if, kk_subset, kk_rel_eq, kk_no, |
836 (kk as {kk_all, kk_implies, kk_formula_if, kk_subset, kk_rel_eq, kk_no, |