haftmann@24219: (*  Title:      Tools/code/code_funcgr.ML
haftmann@24219:     Author:     Florian Haftmann, TU Muenchen
haftmann@24219: 
haftmann@29899: Retrieving, normalizing and structuring code equations in graph
haftmann@24219: with explicit dependencies.
haftmann@30202: 
haftmann@30202: Legacy.  To be replaced by Tools/code/code_wellsorted.ML
haftmann@24219: *)
haftmann@24219: 
haftmann@30202: signature CODE_WELLSORTED =
haftmann@24219: sig
haftmann@24219:   type T
haftmann@28370:   val eqns: T -> string -> (thm * bool) list
haftmann@26971:   val typ: T -> string -> (string * sort) list * typ
haftmann@24423:   val all: T -> string list
haftmann@24219:   val pretty: theory -> T -> Pretty.T
haftmann@28924:   val make: theory -> string list
haftmann@28924:     -> ((sort -> sort) * Sorts.algebra) * T
haftmann@28924:   val eval_conv: theory
haftmann@28924:     -> (term -> term * (((sort -> sort) * Sorts.algebra) -> T -> thm)) -> cterm -> thm
haftmann@28924:   val eval_term: theory
haftmann@28924:     -> (term -> term * (((sort -> sort) * Sorts.algebra) -> T -> 'a)) -> term -> 'a
haftmann@26971:   val timing: bool ref
haftmann@24219: end
haftmann@24219: 
haftmann@30202: structure Code_Wellsorted : CODE_WELLSORTED =
haftmann@24219: struct
haftmann@24219: 
haftmann@24219: (** the graph type **)
haftmann@24219: 
haftmann@28350: type T = (((string * sort) list * typ) * (thm * bool) list) Graph.T;
haftmann@24219: 
haftmann@28370: fun eqns funcgr =
haftmann@24423:   these o Option.map snd o try (Graph.get_node funcgr);
haftmann@24219: 
haftmann@24219: fun typ funcgr =
haftmann@24423:   fst o Graph.get_node funcgr;
haftmann@24219: 
haftmann@24423: fun all funcgr = Graph.keys funcgr;
haftmann@24219: 
haftmann@24219: fun pretty thy funcgr =
haftmann@24423:   AList.make (snd o Graph.get_node funcgr) (Graph.keys funcgr)
haftmann@28054:   |> (map o apfst) (Code_Unit.string_of_const thy)
haftmann@24219:   |> sort (string_ord o pairself fst)
haftmann@24219:   |> map (fn (s, thms) =>
haftmann@24219:        (Pretty.block o Pretty.fbreaks) (
haftmann@24219:          Pretty.str s
haftmann@28350:          :: map (Display.pretty_thm o fst) thms
haftmann@24219:        ))
haftmann@24219:   |> Pretty.chunks;
haftmann@24219: 
haftmann@24219: 
haftmann@24219: (** generic combinators **)
haftmann@24219: 
haftmann@24219: fun fold_consts f thms =
haftmann@24219:   thms
haftmann@24219:   |> maps (op :: o swap o apfst (snd o strip_comb) o Logic.dest_equals o Thm.plain_prop_of)
haftmann@24219:   |> (fold o fold_aterms) (fn Const c => f c | _ => I);
haftmann@24219: 
haftmann@24219: fun consts_of (const, []) = []
haftmann@24423:   | consts_of (const, thms as _ :: _) = 
haftmann@24219:       let
haftmann@24423:         fun the_const (c, _) = if c = const then I else insert (op =) c
haftmann@28350:       in fold_consts the_const (map fst thms) [] end;
haftmann@24219: 
haftmann@26971: fun insts_of thy algebra tys sorts =
haftmann@24219:   let
haftmann@24219:     fun class_relation (x, _) _ = x;
haftmann@24219:     fun type_constructor tyco xs class =
haftmann@26971:       (tyco, class) :: (maps o maps) fst xs;
haftmann@24219:     fun type_variable (TVar (_, sort)) = map (pair []) sort
haftmann@24219:       | type_variable (TFree (_, sort)) = map (pair []) sort;
haftmann@26971:     fun of_sort_deriv ty sort =
wenzelm@26939:       Sorts.of_sort_derivation (Syntax.pp_global thy) algebra
haftmann@24219:         { class_relation = class_relation, type_constructor = type_constructor,
haftmann@24219:           type_variable = type_variable }
haftmann@26517:         (ty, sort) handle Sorts.CLASS_ERROR _ => [] (*permissive!*)
haftmann@26971:   in (flat o flat) (map2 of_sort_deriv tys sorts) end;
haftmann@24219: 
haftmann@26971: fun meets_of thy algebra =
haftmann@24219:   let
haftmann@26971:     fun meet_of ty sort tab =
haftmann@26971:       Sorts.meet_sort algebra (ty, sort) tab
haftmann@26971:         handle Sorts.CLASS_ERROR _ => tab (*permissive!*);
haftmann@26971:   in fold2 meet_of end;
haftmann@24219: 
haftmann@24219: 
haftmann@24219: (** graph algorithm **)
haftmann@24219: 
haftmann@24219: val timing = ref false;
haftmann@24219: 
haftmann@24219: local
haftmann@24219: 
haftmann@26971: fun resort_thms thy algebra typ_of thms =
haftmann@26971:   let
haftmann@26971:     val cs = fold_consts (insert (op =)) thms [];
haftmann@26971:     fun meets (c, ty) = case typ_of c
haftmann@26971:        of SOME (vs, _) =>
haftmann@26971:             meets_of thy algebra (Sign.const_typargs thy (c, ty)) (map snd vs)
haftmann@26971:         | NONE => I;
haftmann@26971:     val tab = fold meets cs Vartab.empty;
haftmann@28423:   in map (Code_Unit.inst_thm thy tab) thms end;
haftmann@24219: 
haftmann@28370: fun resort_eqnss thy algebra funcgr =
haftmann@24219:   let
haftmann@24423:     val typ_funcgr = try (fst o Graph.get_node funcgr);
haftmann@28350:     val resort_dep = (apsnd o burrow_fst) (resort_thms thy algebra typ_funcgr);
haftmann@26997:     fun resort_rec typ_of (c, []) = (true, (c, []))
haftmann@28350:       | resort_rec typ_of (c, thms as (thm, _) :: _) = if is_some (AxClass.inst_of_param thy c)
haftmann@26997:           then (true, (c, thms))
haftmann@26997:           else let
haftmann@28423:             val (_, (vs, ty)) = Code_Unit.head_eqn thy thm;
haftmann@28350:             val thms' as (thm', _) :: _ = burrow_fst (resort_thms thy algebra typ_of) thms
haftmann@28423:             val (_, (vs', ty')) = Code_Unit.head_eqn thy thm'; (*FIXME simplify check*)
haftmann@26997:           in (Sign.typ_equiv thy (ty, ty'), (c, thms')) end;
haftmann@28370:     fun resort_recs eqnss =
haftmann@24219:       let
haftmann@28370:         fun typ_of c = case these (AList.lookup (op =) eqnss c)
haftmann@28423:          of (thm, _) :: _ => (SOME o snd o Code_Unit.head_eqn thy) thm
haftmann@26971:           | [] => NONE;
haftmann@28370:         val (unchangeds, eqnss') = split_list (map (resort_rec typ_of) eqnss);
haftmann@24219:         val unchanged = fold (fn x => fn y => x andalso y) unchangeds true;
haftmann@28370:       in (unchanged, eqnss') end;
haftmann@28370:     fun resort_rec_until eqnss =
haftmann@24219:       let
haftmann@28370:         val (unchanged, eqnss') = resort_recs eqnss;
haftmann@28370:       in if unchanged then eqnss' else resort_rec_until eqnss' end;
haftmann@24219:   in map resort_dep #> resort_rec_until end;
haftmann@24219: 
haftmann@24219: fun instances_of thy algebra insts =
haftmann@24219:   let
haftmann@24219:     val thy_classes = (#classes o Sorts.rep_algebra o Sign.classes_of) thy;
haftmann@24835:     fun all_classparams tyco class =
wenzelm@24969:       these (try (#params o AxClass.get_info thy) class)
haftmann@26517:       |> map_filter (fn (c, _) => try (AxClass.param_of_inst thy) (c, tyco))
haftmann@24219:   in
haftmann@24219:     Symtab.empty
haftmann@24219:     |> fold (fn (tyco, class) =>
haftmann@24219:         Symtab.map_default (tyco, []) (insert (op =) class)) insts
haftmann@24835:     |> (fn tab => Symtab.fold (fn (tyco, classes) => append (maps (all_classparams tyco)
haftmann@24219:          (Graph.all_succs thy_classes classes))) tab [])
haftmann@24219:   end;
haftmann@24219: 
haftmann@24219: fun instances_of_consts thy algebra funcgr consts =
haftmann@24219:   let
haftmann@26971:     fun inst (cexpr as (c, ty)) = insts_of thy algebra
haftmann@26971:       (Sign.const_typargs thy (c, ty)) ((map snd o fst) (typ funcgr c));
haftmann@24219:   in
haftmann@24219:     []
haftmann@24219:     |> fold (fold (insert (op =)) o inst) consts
haftmann@24219:     |> instances_of thy algebra
haftmann@24219:   end;
haftmann@24219: 
haftmann@24283: fun ensure_const' thy algebra funcgr const auxgr =
haftmann@24423:   if can (Graph.get_node funcgr) const
haftmann@24219:     then (NONE, auxgr)
haftmann@24423:   else if can (Graph.get_node auxgr) const
haftmann@24219:     then (SOME const, auxgr)
haftmann@24219:   else if is_some (Code.get_datatype_of_constr thy const) then
haftmann@24219:     auxgr
haftmann@24423:     |> Graph.new_node (const, [])
haftmann@24219:     |> pair (SOME const)
haftmann@24219:   else let
haftmann@28370:     val thms = Code.these_eqns thy const
haftmann@28423:       |> burrow_fst (Code_Unit.norm_args thy)
haftmann@28423:       |> burrow_fst (Code_Unit.norm_varnames thy Code_Name.purify_tvar Code_Name.purify_var);
haftmann@24219:     val rhs = consts_of (const, thms);
haftmann@24219:   in
haftmann@24219:     auxgr
haftmann@24423:     |> Graph.new_node (const, thms)
haftmann@24283:     |> fold_map (ensure_const thy algebra funcgr) rhs
haftmann@24423:     |-> (fn rhs' => fold (fn SOME const' => Graph.add_edge (const, const')
haftmann@24219:                            | NONE => I) rhs')
haftmann@24219:     |> pair (SOME const)
haftmann@24219:   end
haftmann@24283: and ensure_const thy algebra funcgr const =
haftmann@24219:   let
haftmann@24219:     val timeap = if !timing
haftmann@28054:       then Output.timeap_msg ("time for " ^ Code_Unit.string_of_const thy const)
haftmann@24219:       else I;
haftmann@24283:   in timeap (ensure_const' thy algebra funcgr const) end;
haftmann@24219: 
haftmann@28370: fun merge_eqnss thy algebra raw_eqnss funcgr =
haftmann@24219:   let
haftmann@28370:     val eqnss = raw_eqnss
haftmann@28370:       |> resort_eqnss thy algebra funcgr
haftmann@24423:       |> filter_out (can (Graph.get_node funcgr) o fst);
haftmann@28423:     fun typ_eqn c [] = Code.default_typscheme thy c
haftmann@28423:       | typ_eqn c (thms as (thm, _) :: _) = (snd o Code_Unit.head_eqn thy) thm;
haftmann@28370:     fun add_eqns (const, thms) =
haftmann@28370:       Graph.new_node (const, (typ_eqn const thms, thms));
haftmann@28370:     fun add_deps (eqns as (const, thms)) funcgr =
haftmann@24219:       let
haftmann@28370:         val deps = consts_of eqns;
haftmann@24219:         val insts = instances_of_consts thy algebra funcgr
haftmann@28350:           (fold_consts (insert (op =)) (map fst thms) []);
haftmann@24219:       in
haftmann@24219:         funcgr
haftmann@26997:         |> ensure_consts thy algebra insts
haftmann@24423:         |> fold (curry Graph.add_edge const) deps
haftmann@24423:         |> fold (curry Graph.add_edge const) insts
haftmann@24219:        end;
haftmann@24219:   in
haftmann@24219:     funcgr
haftmann@28370:     |> fold add_eqns eqnss
haftmann@28370:     |> fold add_deps eqnss
haftmann@24219:   end
haftmann@26997: and ensure_consts thy algebra cs funcgr =
haftmann@24219:   let
haftmann@24423:     val auxgr = Graph.empty
haftmann@24283:       |> fold (snd oo ensure_const thy algebra funcgr) cs;
haftmann@24219:   in
haftmann@24219:     funcgr
haftmann@28370:     |> fold (merge_eqnss thy algebra)
haftmann@24423:          (map (AList.make (Graph.get_node auxgr))
haftmann@24423:          (rev (Graph.strong_conn auxgr)))
haftmann@26997:   end;
haftmann@24219: 
haftmann@24219: in
haftmann@24219: 
haftmann@24219: (** retrieval interfaces **)
haftmann@24219: 
haftmann@26997: val ensure_consts = ensure_consts;
haftmann@24219: 
haftmann@28724: fun proto_eval thy cterm_of evaluator_lift evaluator proto_ct funcgr =
haftmann@24219:   let
haftmann@26740:     val ct = cterm_of proto_ct;
wenzelm@26939:     val _ = Sign.no_vars (Syntax.pp_global thy) (Thm.term_of ct);
haftmann@24219:     val _ = Term.fold_types (Type.no_tvars #> K I) (Thm.term_of ct) ();
haftmann@28724:     fun consts_of t =
haftmann@28724:       fold_aterms (fn Const c_ty => cons c_ty | _ => I) t [];
haftmann@26740:     val algebra = Code.coregular_algebra thy;
haftmann@28423:     val thm = Code.preprocess_conv thy ct;
haftmann@26740:     val ct' = Thm.rhs_of thm;
haftmann@26740:     val t' = Thm.term_of ct';
haftmann@26740:     val consts = map fst (consts_of t');
haftmann@26740:     val funcgr' = ensure_consts thy algebra consts funcgr;
haftmann@28724:     val (t'', evaluator_funcgr) = evaluator t';
haftmann@26740:     val consts' = consts_of t'';
haftmann@26740:     val dicts = instances_of_consts thy algebra funcgr' consts';
haftmann@26740:     val funcgr'' = ensure_consts thy algebra dicts funcgr';
haftmann@28924:   in (evaluator_lift (evaluator_funcgr (Code.operational_algebra thy)) thm funcgr'', funcgr'') end;
haftmann@26740: 
haftmann@26740: fun proto_eval_conv thy =
haftmann@26740:   let
haftmann@28724:     fun evaluator_lift evaluator thm1 funcgr =
haftmann@24219:       let
haftmann@28724:         val thm2 = evaluator funcgr;
haftmann@28423:         val thm3 = Code.postprocess_conv thy (Thm.rhs_of thm2);
haftmann@24219:       in
haftmann@26740:         Thm.transitive thm1 (Thm.transitive thm2 thm3) handle THM _ =>
haftmann@26971:           error ("could not construct evaluation proof:\n"
wenzelm@26928:           ^ (cat_lines o map Display.string_of_thm) [thm1, thm2, thm3])
haftmann@24219:       end;
haftmann@28724:   in proto_eval thy I evaluator_lift end;
haftmann@24283: 
haftmann@26740: fun proto_eval_term thy =
haftmann@24283:   let
haftmann@28724:     fun evaluator_lift evaluator _ funcgr = evaluator funcgr;
haftmann@28724:   in proto_eval thy (Thm.cterm_of thy) evaluator_lift end;
haftmann@24219: 
haftmann@24219: end; (*local*)
haftmann@24219: 
haftmann@24219: structure Funcgr = CodeDataFun
wenzelm@24713: (
haftmann@24219:   type T = T;
haftmann@24423:   val empty = Graph.empty;
haftmann@27609:   fun purge _ cs funcgr =
haftmann@27609:     Graph.del_nodes ((Graph.all_preds funcgr 
haftmann@27609:       o filter (can (Graph.get_node funcgr))) cs) funcgr;
wenzelm@24713: );
haftmann@24219: 
haftmann@24219: fun make thy =
haftmann@28924:   pair (Code.operational_algebra thy)
haftmann@28924:   o Funcgr.change thy o ensure_consts thy (Code.coregular_algebra thy);
haftmann@24219: 
haftmann@24219: fun eval_conv thy f =
haftmann@26740:   fst o Funcgr.change_yield thy o proto_eval_conv thy f;
haftmann@24283: 
haftmann@24283: fun eval_term thy f =
haftmann@26740:   fst o Funcgr.change_yield thy o proto_eval_term thy f;
haftmann@24219: 
haftmann@27103: 
haftmann@27103: (** diagnostic commands **)
haftmann@27103: 
haftmann@28350: fun code_depgr thy consts =
haftmann@28350:   let
haftmann@28924:     val (_, gr) = make thy consts;
haftmann@28350:     val select = Graph.all_succs gr consts;
haftmann@28350:   in
haftmann@28350:     gr
haftmann@28350:     |> not (null consts) ? Graph.subgraph (member (op =) select) 
haftmann@28350:     |> Graph.map_nodes ((apsnd o map o apfst) (AxClass.overload thy))
haftmann@28350:   end;
haftmann@27103: 
haftmann@27103: fun code_thms thy = Pretty.writeln o pretty thy o code_depgr thy;
haftmann@27103: 
haftmann@27103: fun code_deps thy consts =
haftmann@27103:   let
haftmann@27103:     val gr = code_depgr thy consts;
haftmann@27103:     fun mk_entry (const, (_, (_, parents))) =
haftmann@27103:       let
haftmann@28054:         val name = Code_Unit.string_of_const thy const;
haftmann@28054:         val nameparents = map (Code_Unit.string_of_const thy) parents;
haftmann@27103:       in { name = name, ID = name, dir = "", unfold = true,
haftmann@27103:         path = "", parents = nameparents }
haftmann@27103:       end;
haftmann@27103:     val prgr = Graph.fold ((fn x => fn xs => xs @ [x]) o mk_entry) gr [];
haftmann@27103:   in Present.display_graph prgr end;
haftmann@27103: 
haftmann@27103: local
haftmann@27103: 
haftmann@27103: structure P = OuterParse
haftmann@27103: and K = OuterKeyword
haftmann@27103: 
haftmann@28054: fun code_thms_cmd thy = code_thms thy o op @ o Code_Name.read_const_exprs thy;
haftmann@28054: fun code_deps_cmd thy = code_deps thy o op @ o Code_Name.read_const_exprs thy;
haftmann@27103: 
haftmann@27103: in
haftmann@27103: 
haftmann@27103: val _ =
haftmann@29961:   OuterSyntax.improper_command "code_thms" "print system of code equations for code" OuterKeyword.diag
haftmann@28338:     (Scan.repeat P.term_group
haftmann@27103:       >> (fn cs => Toplevel.no_timing o Toplevel.unknown_theory
haftmann@27103:         o Toplevel.keep ((fn thy => code_thms_cmd thy cs) o Toplevel.theory_of)));
haftmann@27103: 
haftmann@27103: val _ =
haftmann@29961:   OuterSyntax.improper_command "code_deps" "visualize dependencies of code equations for code" OuterKeyword.diag
haftmann@28338:     (Scan.repeat P.term_group
haftmann@27103:       >> (fn cs => Toplevel.no_timing o Toplevel.unknown_theory
haftmann@27103:         o Toplevel.keep ((fn thy => code_deps_cmd thy cs) o Toplevel.theory_of)));
haftmann@27103: 
haftmann@27103: end;
haftmann@27103: 
haftmann@24219: end; (*struct*)