9 this is assured because both have type "prop". |
9 this is assured because both have type "prop". |
10 *) |
10 *) |
11 |
11 |
12 signature UNIFY = |
12 signature UNIFY = |
13 sig |
13 sig |
14 val trace_bound: int Config.T |
|
15 val search_bound: int Config.T |
14 val search_bound: int Config.T |
16 val trace_simp: bool Config.T |
15 val unify_trace_bound: int Config.T |
17 val trace_types: bool Config.T |
16 val unify_trace_simp: bool Config.T |
|
17 val unify_trace_types: bool Config.T |
18 val hounifiers: (string * typ) list -> Context.generic * Envir.env * ((term * term) list) -> |
18 val hounifiers: (string * typ) list -> Context.generic * Envir.env * ((term * term) list) -> |
19 (Envir.env * (term * term) list) Seq.seq |
19 (Envir.env * (term * term) list) Seq.seq |
20 val unifiers: Context.generic * Envir.env * ((term * term) list) -> |
20 val unifiers: Context.generic * Envir.env * ((term * term) list) -> |
21 (Envir.env * (term * term) list) Seq.seq |
21 (Envir.env * (term * term) list) Seq.seq |
22 val smash_unifiers: Context.generic -> (term * term) list -> Envir.env -> Envir.env Seq.seq |
22 val smash_unifiers: Context.generic -> (term * term) list -> Envir.env -> Envir.env Seq.seq |
25 structure Unify : UNIFY = |
25 structure Unify : UNIFY = |
26 struct |
26 struct |
27 |
27 |
28 (*Unification options*) |
28 (*Unification options*) |
29 |
29 |
30 (*tracing starts above this depth, 0 for full*) |
|
31 val trace_bound = Config.declare_int ("unify_trace_bound", \<^here>) (K 50); |
|
32 |
|
33 (*unification quits above this depth*) |
30 (*unification quits above this depth*) |
34 val search_bound = Config.declare_int ("unify_search_bound", \<^here>) (K 60); |
31 val search_bound = Config.declare_int ("unify_search_bound", \<^here>) (K 60); |
35 |
32 |
|
33 |
|
34 (* diagnostics *) |
|
35 |
|
36 (*tracing starts above this depth, 0 for full*) |
|
37 val unify_trace_bound = Config.declare_int ("unify_trace_bound", \<^here>) (K 50); |
|
38 |
36 (*print dpairs before calling SIMPL*) |
39 (*print dpairs before calling SIMPL*) |
37 val trace_simp = Config.declare_bool ("unify_trace_simp", \<^here>) (K false); |
40 val unify_trace_simp = Config.declare_bool ("unify_trace_simp", \<^here>) (K false); |
38 |
41 |
39 (*announce potential incompleteness of type unification*) |
42 (*announce potential incompleteness of type unification*) |
40 val trace_types = Config.declare_bool ("unify_trace_types", \<^here>) (K false); |
43 val unify_trace_types = Config.declare_bool ("unify_trace_types", \<^here>) (K false); |
41 |
44 |
42 |
45 |
43 type binderlist = (string * typ) list; |
46 type binderlist = (string * typ) list; |
44 |
47 |
45 type dpair = binderlist * term * term; |
48 type dpair = binderlist * term * term; |
323 NB "vname" is only used in the call to make_args!! *) |
326 NB "vname" is only used in the call to make_args!! *) |
324 fun matchcopy context vname = |
327 fun matchcopy context vname = |
325 let |
328 let |
326 fun mc (rbinder, targs, u, ed as (env, dpairs)) : (term * (Envir.env * dpair list)) Seq.seq = |
329 fun mc (rbinder, targs, u, ed as (env, dpairs)) : (term * (Envir.env * dpair list)) Seq.seq = |
327 let |
330 let |
328 val trace_types = Config.get_generic context trace_types; |
331 val unify_trace_types = Config.get_generic context unify_trace_types; |
329 (*Produce copies of uarg and cons them in front of uargs*) |
332 (*Produce copies of uarg and cons them in front of uargs*) |
330 fun copycons uarg (uargs, (env, dpairs)) = |
333 fun copycons uarg (uargs, (env, dpairs)) = |
331 Seq.map (fn (uarg', ed') => (uarg' :: uargs, ed')) |
334 Seq.map (fn (uarg', ed') => (uarg' :: uargs, ed')) |
332 (mc (rbinder, targs,eta_norm env (rbinder, Envir.head_norm env uarg), |
335 (mc (rbinder, targs,eta_norm env (rbinder, Envir.head_norm env uarg), |
333 (env, dpairs))); |
336 (env, dpairs))); |
340 (*attempt projection on argument with given typ*) |
343 (*attempt projection on argument with given typ*) |
341 val Ts = map (curry (fastype env) rbinder) targs; |
344 val Ts = map (curry (fastype env) rbinder) targs; |
342 fun projenv (head, (Us, bary), targ, tail) = |
345 fun projenv (head, (Us, bary), targ, tail) = |
343 let |
346 let |
344 val env = |
347 val env = |
345 if trace_types then test_unify_types context (base, bary) env |
348 if unify_trace_types then test_unify_types context (base, bary) env |
346 else unify_types context (base, bary) env |
349 else unify_types context (base, bary) env |
347 in |
350 in |
348 Seq.make (fn () => |
351 Seq.make (fn () => |
349 let |
352 let |
350 val (env', args) = make_args vname (Ts, env, Us); |
353 val (env', args) = make_args vname (Ts, env, Us); |
582 Returns flex-flex disagreement pairs NOT IN normal form. |
585 Returns flex-flex disagreement pairs NOT IN normal form. |
583 SIMPL may raise exception CANTUNIFY. *) |
586 SIMPL may raise exception CANTUNIFY. *) |
584 fun hounifiers binders (context, env, tus : (term * term) list) |
587 fun hounifiers binders (context, env, tus : (term * term) list) |
585 : (Envir.env * (term * term) list) Seq.seq = |
588 : (Envir.env * (term * term) list) Seq.seq = |
586 let |
589 let |
587 val trace_bound = Config.get_generic context trace_bound; |
590 val unify_trace_bound = Config.get_generic context unify_trace_bound; |
|
591 val unify_trace_simp = Config.get_generic context unify_trace_simp; |
588 val search_bound = Config.get_generic context search_bound; |
592 val search_bound = Config.get_generic context search_bound; |
589 val trace_simp = Config.get_generic context trace_simp; |
|
590 fun add_unify tdepth ((env, dpairs), reseq) = |
593 fun add_unify tdepth ((env, dpairs), reseq) = |
591 Seq.make (fn () => |
594 Seq.make (fn () => |
592 let |
595 let |
593 val (env', flexflex, flexrigid) = |
596 val (env', flexflex, flexrigid) = |
594 (if tdepth > trace_bound andalso trace_simp |
597 (if tdepth > unify_trace_bound andalso unify_trace_simp |
595 then print_dpairs context "Enter SIMPL" (env, dpairs) else (); |
598 then print_dpairs context "Enter SIMPL" (env, dpairs) else (); |
596 SIMPL context (env, dpairs)); |
599 SIMPL context (env, dpairs)); |
597 in |
600 in |
598 (case flexrigid of |
601 (case flexrigid of |
599 [] => SOME (fold_rev (add_ffpair context) flexflex (env', []), reseq) |
602 [] => SOME (fold_rev (add_ffpair context) flexflex (env', []), reseq) |
600 | dp :: frigid' => |
603 | dp :: frigid' => |
601 if tdepth > search_bound then |
604 if tdepth > search_bound then |
602 (if Context_Position.is_visible_generic context |
605 (if Context_Position.is_visible_generic context |
603 then warning "Unification bound exceeded" else (); Seq.pull reseq) |
606 then warning "Unification bound exceeded" else (); Seq.pull reseq) |
604 else |
607 else |
605 (if tdepth > trace_bound then |
608 (if tdepth > unify_trace_bound then |
606 print_dpairs context "Enter MATCH" (env',flexrigid@flexflex) |
609 print_dpairs context "Enter MATCH" (env',flexrigid@flexflex) |
607 else (); |
610 else (); |
608 Seq.pull (Seq.it_right |
611 Seq.pull (Seq.it_right |
609 (add_unify (tdepth + 1)) (MATCH context (env',dp, frigid'@flexflex), reseq)))) |
612 (add_unify (tdepth + 1)) (MATCH context (env',dp, frigid'@flexflex), reseq)))) |
610 end |
613 end |
611 handle CANTUNIFY => |
614 handle CANTUNIFY => |
612 (if tdepth > trace_bound andalso Context_Position.is_visible_generic context |
615 (if tdepth > unify_trace_bound andalso Context_Position.is_visible_generic context |
613 then tracing "Failure node" |
616 then tracing "Failure node" |
614 else (); Seq.pull reseq)); |
617 else (); Seq.pull reseq)); |
615 val dps = map (fn (t, u) => (binders, t, u)) tus; |
618 val dps = map (fn (t, u) => (binders, t, u)) tus; |
616 in add_unify 1 ((env, dps), Seq.empty) end; |
619 in add_unify 1 ((env, dps), Seq.empty) end; |
617 |
620 |