10 *) |
10 *) |
11 |
11 |
12 signature UNIFY = |
12 signature UNIFY = |
13 sig |
13 sig |
14 val search_bound: int Config.T |
14 val search_bound: int Config.T |
|
15 val unify_trace: bool Config.T |
15 val unify_trace_bound: int Config.T |
16 val unify_trace_bound: int Config.T |
16 val unify_trace_simp: bool Config.T |
17 val unify_trace_simp: bool Config.T |
17 val unify_trace_types: bool Config.T |
18 val unify_trace_types: bool Config.T |
18 val hounifiers: (string * typ) list -> Context.generic * Envir.env * ((term * term) list) -> |
19 val hounifiers: (string * typ) list -> Context.generic * Envir.env * ((term * term) list) -> |
19 (Envir.env * (term * term) list) Seq.seq |
20 (Envir.env * (term * term) list) Seq.seq |
31 val search_bound = Config.declare_int ("unify_search_bound", \<^here>) (K 60); |
32 val search_bound = Config.declare_int ("unify_search_bound", \<^here>) (K 60); |
32 |
33 |
33 |
34 |
34 (* diagnostics *) |
35 (* diagnostics *) |
35 |
36 |
|
37 val unify_trace = Config.declare_bool ("unify_trace", \<^here>) (K false); |
|
38 |
36 (*tracing starts above this depth, 0 for full*) |
39 (*tracing starts above this depth, 0 for full*) |
37 val unify_trace_bound = Config.declare_int ("unify_trace_bound", \<^here>) (K 50); |
40 val unify_trace_bound = Config.declare_int ("unify_trace_bound", \<^here>) (K 50); |
38 |
41 |
39 (*print dpairs before calling SIMPL*) |
42 (*print dpairs before calling SIMPL*) |
40 val unify_trace_simp = Config.declare_bool ("unify_trace_simp", \<^here>) (K false); |
43 val unify_trace_simp = Config.declare_bool ("unify_trace_simp", \<^here>) (K false); |
41 |
44 |
42 (*announce potential incompleteness of type unification*) |
45 (*announce potential incompleteness of type unification*) |
43 val unify_trace_types = Config.declare_bool ("unify_trace_types", \<^here>) (K false); |
46 val unify_trace_types = Config.declare_bool ("unify_trace_types", \<^here>) (K false); |
|
47 |
|
48 fun cond_tracing ctxt msg = |
|
49 if Config.get_generic ctxt unify_trace andalso Context_Position.is_visible_generic ctxt then |
|
50 tracing (msg ()) |
|
51 else (); |
44 |
52 |
45 |
53 |
46 type binderlist = (string * typ) list; |
54 type binderlist = (string * typ) list; |
47 |
55 |
48 type dpair = binderlist * term * term; |
56 type dpair = binderlist * term * term; |
179 fun unify_types context TU env = |
187 fun unify_types context TU env = |
180 Pattern.unify_types context TU env handle Pattern.Unif => raise CANTUNIFY; |
188 Pattern.unify_types context TU env handle Pattern.Unif => raise CANTUNIFY; |
181 |
189 |
182 fun test_unify_types context (T, U) env = |
190 fun test_unify_types context (T, U) env = |
183 let |
191 let |
184 fun trace () = |
192 fun msg () = |
185 if Context_Position.is_visible_generic context then |
193 let val str_of = Syntax.string_of_typ (Context.proof_of context) |
186 let val str_of = Syntax.string_of_typ (Context.proof_of context) |
194 in "Potential loss of completeness: " ^ str_of U ^ " = " ^ str_of T end |
187 in tracing ("Potential loss of completeness: " ^ str_of U ^ " = " ^ str_of T) end |
|
188 else (); |
|
189 val env' = unify_types context (T, U) env; |
195 val env' = unify_types context (T, U) env; |
190 in if is_TVar T orelse is_TVar U then trace () else (); env' end; |
196 in if is_TVar T orelse is_TVar U then cond_tracing context msg else (); env' end; |
191 |
197 |
192 (*Is the term eta-convertible to a single variable with the given rbinder? |
198 (*Is the term eta-convertible to a single variable with the given rbinder? |
193 Examples: ?a ?f(B.0) ?g(B.1,B.0) |
199 Examples: ?a ?f(B.0) ?g(B.1,B.0) |
194 Result is var a for use in SIMPL. *) |
200 Result is var a for use in SIMPL. *) |
195 fun get_eta_var ([], _, Var vT) = vT |
201 fun get_eta_var ([], _, Var vT) = vT |
566 |
572 |
567 (*Print a tracing message + list of dpairs. |
573 (*Print a tracing message + list of dpairs. |
568 In t \<equiv> u print u first because it may be rigid or flexible -- |
574 In t \<equiv> u print u first because it may be rigid or flexible -- |
569 t is always flexible.*) |
575 t is always flexible.*) |
570 fun print_dpairs context msg (env, dpairs) = |
576 fun print_dpairs context msg (env, dpairs) = |
571 if Context_Position.is_visible_generic context then |
577 let |
572 let |
578 fun pdp (rbinder, t, u) = |
573 fun pdp (rbinder, t, u) = |
579 let |
574 let |
580 val ctxt = Context.proof_of context; |
575 val ctxt = Context.proof_of context; |
581 fun termT t = |
576 fun termT t = |
582 Syntax.pretty_term ctxt (Envir.norm_term env (Logic.rlist_abs (rbinder, t))); |
577 Syntax.pretty_term ctxt (Envir.norm_term env (Logic.rlist_abs (rbinder, t))); |
583 val prt = Pretty.blk (0, [termT u, Pretty.str " \<equiv>\<^sup>?", Pretty.brk 1, termT t]); |
578 val prt = Pretty.blk (0, [termT u, Pretty.str " \<equiv>\<^sup>?", Pretty.brk 1, termT t]); |
584 in Pretty.string_of prt end; |
579 in tracing (Pretty.string_of prt) end; |
585 in |
580 in tracing msg; List.app pdp dpairs end |
586 cond_tracing context (fn () => msg); |
581 else (); |
587 List.app (fn dp => cond_tracing context (fn () => pdp dp)) dpairs |
|
588 end; |
582 |
589 |
583 |
590 |
584 (*Unify the dpairs in the environment. |
591 (*Unify the dpairs in the environment. |
585 Returns flex-flex disagreement pairs NOT IN normal form. |
592 Returns flex-flex disagreement pairs NOT IN normal form. |
586 SIMPL may raise exception CANTUNIFY. *) |
593 SIMPL may raise exception CANTUNIFY. *) |
600 in |
607 in |
601 (case flexrigid of |
608 (case flexrigid of |
602 [] => SOME (fold_rev (add_ffpair context) flexflex (env', []), reseq) |
609 [] => SOME (fold_rev (add_ffpair context) flexflex (env', []), reseq) |
603 | dp :: frigid' => |
610 | dp :: frigid' => |
604 if tdepth > search_bound then |
611 if tdepth > search_bound then |
605 (if Context_Position.is_visible_generic context |
612 (if Context_Position.is_visible_generic context then |
606 then warning "Unification bound exceeded" else (); Seq.pull reseq) |
613 warning "Unification bound exceeded -- see unify trace for details" |
|
614 else (); Seq.pull reseq) |
607 else |
615 else |
608 (if tdepth > unify_trace_bound then |
616 (if tdepth > unify_trace_bound then |
609 print_dpairs context "Enter MATCH" (env',flexrigid@flexflex) |
617 print_dpairs context "Enter MATCH" (env',flexrigid@flexflex) |
610 else (); |
618 else (); |
611 Seq.pull (Seq.it_right |
619 Seq.pull (Seq.it_right |
612 (add_unify (tdepth + 1)) (MATCH context (env',dp, frigid'@flexflex), reseq)))) |
620 (add_unify (tdepth + 1)) (MATCH context (env',dp, frigid'@flexflex), reseq)))) |
613 end |
621 end |
614 handle CANTUNIFY => |
622 handle CANTUNIFY => |
615 (if tdepth > unify_trace_bound andalso Context_Position.is_visible_generic context |
623 (if tdepth > unify_trace_bound |
616 then tracing "Failure node" |
624 then cond_tracing context (fn () => "Failure node") |
617 else (); Seq.pull reseq)); |
625 else (); Seq.pull reseq)); |
618 val dps = map (fn (t, u) => (binders, t, u)) tus; |
626 val dps = map (fn (t, u) => (binders, t, u)) tus; |
619 in add_unify 1 ((env, dps), Seq.empty) end; |
627 in add_unify 1 ((env, dps), Seq.empty) end; |
620 |
628 |
621 fun unifiers (params as (context, env, tus)) = |
629 fun unifiers (params as (context, env, tus)) = |