src/Pure/unify.ML
changeset 79742 2e4518e8a36b
parent 79162 c1bbaa0d89b4
child 79743 3648e9c88d0c
equal deleted inserted replaced
79741:513829904beb 79742:2e4518e8a36b
     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