src/HOL/Tools/Sledgehammer/metis_tactics.ML
changeset 37402 12cb33916e37
parent 37399 34f080a12063
child 37410 2bf7e6136047
equal deleted inserted replaced
37401:e8c34222814b 37402:12cb33916e37
    83       (CombConst ((c, _), _, tys), tms) =>
    83       (CombConst ((c, _), _, tys), tms) =>
    84         let val tyargs = map hol_type_to_fol tys
    84         let val tyargs = map hol_type_to_fol tys
    85             val args   = map hol_term_to_fol_FO tms
    85             val args   = map hol_term_to_fol_FO tms
    86         in Metis.Term.Fn (c, tyargs @ args) end
    86         in Metis.Term.Fn (c, tyargs @ args) end
    87     | (CombVar ((v, _), _), []) => Metis.Term.Var v
    87     | (CombVar ((v, _), _), []) => Metis.Term.Var v
    88     | _ => error "hol_term_to_fol_FO";
    88     | _ => raise Fail "hol_term_to_fol_FO";
    89 
    89 
    90 fun hol_term_to_fol_HO (CombVar ((s, _), _)) = Metis.Term.Var s
    90 fun hol_term_to_fol_HO (CombVar ((s, _), _)) = Metis.Term.Var s
    91   | hol_term_to_fol_HO (CombConst ((a, _), _, tylist)) =
    91   | hol_term_to_fol_HO (CombConst ((a, _), _, tylist)) =
    92       Metis.Term.Fn (fn_isa_to_met a, map hol_type_to_fol tylist)
    92       Metis.Term.Fn (fn_isa_to_met a, map hol_type_to_fol tylist)
    93   | hol_term_to_fol_HO (CombApp (tm1, tm2)) =
    93   | hol_term_to_fol_HO (CombApp (tm1, tm2)) =
   196   | types_of (Type T :: tts) = T :: types_of tts;
   196   | types_of (Type T :: tts) = T :: types_of tts;
   197 
   197 
   198 fun apply_list rator nargs rands =
   198 fun apply_list rator nargs rands =
   199   let val trands = terms_of rands
   199   let val trands = terms_of rands
   200   in  if length trands = nargs then Term (list_comb(rator, trands))
   200   in  if length trands = nargs then Term (list_comb(rator, trands))
   201       else error
   201       else raise Fail
   202         ("apply_list: wrong number of arguments: " ^ Syntax.string_of_term_global Pure.thy rator ^
   202         ("apply_list: wrong number of arguments: " ^ Syntax.string_of_term_global Pure.thy rator ^
   203           " expected " ^ Int.toString nargs ^
   203           " expected " ^ Int.toString nargs ^
   204           " received " ^ commas (map (Syntax.string_of_term_global Pure.thy) trands))
   204           " received " ^ commas (map (Syntax.string_of_term_global Pure.thy) trands))
   205   end;
   205   end;
   206 
   206 
   231      (case strip_prefix tconst_prefix x of
   231      (case strip_prefix tconst_prefix x of
   232           SOME tc => Term.Type (invert_type_const tc, map (fol_type_to_isa ctxt) tys)
   232           SOME tc => Term.Type (invert_type_const tc, map (fol_type_to_isa ctxt) tys)
   233         | NONE    =>
   233         | NONE    =>
   234       case strip_prefix tfree_prefix x of
   234       case strip_prefix tfree_prefix x of
   235           SOME tf => mk_tfree ctxt tf
   235           SOME tf => mk_tfree ctxt tf
   236         | NONE    => error ("fol_type_to_isa: " ^ x));
   236         | NONE    => raise Fail ("fol_type_to_isa: " ^ x));
   237 
   237 
   238 fun reintroduce_skolem_Eps thy skolem_somes =
   238 fun reintroduce_skolem_Eps thy skolem_somes =
   239   let
   239   let
   240     fun aux Ts args t =
   240     fun aux Ts args t =
   241       case t of
   241       case t of
   272             let val (rator,rands) = strip_happ [] t
   272             let val (rator,rands) = strip_happ [] t
   273             in  case rator of
   273             in  case rator of
   274                     Metis.Term.Fn(fname,ts) => applic_to_tt (fname, ts @ rands)
   274                     Metis.Term.Fn(fname,ts) => applic_to_tt (fname, ts @ rands)
   275                   | _ => case tm_to_tt rator of
   275                   | _ => case tm_to_tt rator of
   276                              Term t => Term (list_comb(t, terms_of (map tm_to_tt rands)))
   276                              Term t => Term (list_comb(t, terms_of (map tm_to_tt rands)))
   277                            | _ => error "tm_to_tt: HO application"
   277                            | _ => raise Fail "tm_to_tt: HO application"
   278             end
   278             end
   279         | tm_to_tt (Metis.Term.Fn (fname, args)) = applic_to_tt (fname,args)
   279         | tm_to_tt (Metis.Term.Fn (fname, args)) = applic_to_tt (fname,args)
   280       and applic_to_tt ("=",ts) =
   280       and applic_to_tt ("=",ts) =
   281             Term (list_comb(Const (@{const_name "op ="}, HOLogic.typeT), terms_of (map tm_to_tt ts)))
   281             Term (list_comb(Const (@{const_name "op ="}, HOLogic.typeT), terms_of (map tm_to_tt ts)))
   282         | applic_to_tt (a,ts) =
   282         | applic_to_tt (a,ts) =
   287                       val nterms = length ts - ntypes
   287                       val nterms = length ts - ntypes
   288                       val tts = map tm_to_tt ts
   288                       val tts = map tm_to_tt ts
   289                       val tys = types_of (List.take(tts,ntypes))
   289                       val tys = types_of (List.take(tts,ntypes))
   290                   in if length tys = ntypes then
   290                   in if length tys = ntypes then
   291                          apply_list (Const (c, dummyT)) nterms (List.drop(tts,ntypes))
   291                          apply_list (Const (c, dummyT)) nterms (List.drop(tts,ntypes))
   292                      else error ("Constant " ^ c ^ " expects " ^ Int.toString ntypes ^
   292                      else
   293                                  " but gets " ^ Int.toString (length tys) ^
   293                        raise Fail ("Constant " ^ c ^ " expects " ^ Int.toString ntypes ^
   294                                  " type arguments\n" ^
   294                                    " but gets " ^ Int.toString (length tys) ^
   295                                  cat_lines (map (Syntax.string_of_typ ctxt) tys) ^
   295                                    " type arguments\n" ^
   296                                  " the terms are \n" ^
   296                                    cat_lines (map (Syntax.string_of_typ ctxt) tys) ^
   297                                  cat_lines (map (Syntax.string_of_term ctxt) (terms_of tts)))
   297                                    " the terms are \n" ^
       
   298                                    cat_lines (map (Syntax.string_of_term ctxt) (terms_of tts)))
   298                      end
   299                      end
   299               | NONE => (*Not a constant. Is it a type constructor?*)
   300               | NONE => (*Not a constant. Is it a type constructor?*)
   300             case strip_prefix tconst_prefix a of
   301             case strip_prefix tconst_prefix a of
   301                 SOME b =>
   302                 SOME b =>
   302                   Type (Term.Type (invert_type_const b, types_of (map tm_to_tt ts)))
   303                   Type (Term.Type (invert_type_const b, types_of (map tm_to_tt ts)))
   306               | NONE => (*a fixed variable? They are Skolem functions.*)
   307               | NONE => (*a fixed variable? They are Skolem functions.*)
   307             case strip_prefix fixed_var_prefix a of
   308             case strip_prefix fixed_var_prefix a of
   308                 SOME b =>
   309                 SOME b =>
   309                   let val opr = Term.Free(b, HOLogic.typeT)
   310                   let val opr = Term.Free(b, HOLogic.typeT)
   310                   in  apply_list opr (length ts) (map tm_to_tt ts)  end
   311                   in  apply_list opr (length ts) (map tm_to_tt ts)  end
   311               | NONE => error ("unexpected metis function: " ^ a)
   312               | NONE => raise Fail ("unexpected metis function: " ^ a)
   312   in
   313   in
   313     case tm_to_tt fol_tm of
   314     case tm_to_tt fol_tm of
   314       Term t => t
   315       Term t => t
   315     | _ => error "fol_tm_to_tt: Term expected"
   316     | _ => raise Fail "fol_tm_to_tt: Term expected"
   316   end
   317   end
   317 
   318 
   318 (*Maps fully-typed metis terms to isabelle terms*)
   319 (*Maps fully-typed metis terms to isabelle terms*)
   319 fun hol_term_from_fol_FT ctxt fol_tm =
   320 fun hol_term_from_fol_FT ctxt fol_tm =
   320   let val _ = trace_msg (fn () => "hol_term_from_fol_FT: " ^
   321   let val _ = trace_msg (fn () => "hol_term_from_fol_FT: " ^
   329            (case strip_prefix const_prefix x of
   330            (case strip_prefix const_prefix x of
   330                 SOME c => Const (invert_const c, dummyT)
   331                 SOME c => Const (invert_const c, dummyT)
   331               | NONE => (*Not a constant. Is it a fixed variable??*)
   332               | NONE => (*Not a constant. Is it a fixed variable??*)
   332             case strip_prefix fixed_var_prefix x of
   333             case strip_prefix fixed_var_prefix x of
   333                 SOME v => Free (v, fol_type_to_isa ctxt ty)
   334                 SOME v => Free (v, fol_type_to_isa ctxt ty)
   334               | NONE => error ("hol_term_from_fol_FT bad constant: " ^ x))
   335               | NONE => raise Fail ("hol_term_from_fol_FT bad constant: " ^ x))
   335         | cvt (Metis.Term.Fn ("ti", [Metis.Term.Fn (".",[tm1,tm2]), _])) =
   336         | cvt (Metis.Term.Fn ("ti", [Metis.Term.Fn (".",[tm1,tm2]), _])) =
   336             cvt tm1 $ cvt tm2
   337             cvt tm1 $ cvt tm2
   337         | cvt (Metis.Term.Fn (".",[tm1,tm2])) = (*untyped application*)
   338         | cvt (Metis.Term.Fn (".",[tm1,tm2])) = (*untyped application*)
   338             cvt tm1 $ cvt tm2
   339             cvt tm1 $ cvt tm2
   339         | cvt (Metis.Term.Fn ("{}", [arg])) = cvt arg   (*hBOOL*)
   340         | cvt (Metis.Term.Fn ("{}", [arg])) = cvt arg   (*hBOOL*)
   382    trace_msg (fn () => "Metis: " ^ Metis.Thm.toString fth);
   383    trace_msg (fn () => "Metis: " ^ Metis.Thm.toString fth);
   383    trace_msg (fn () => "Isabelle: " ^ Display.string_of_thm_without_context th));
   384    trace_msg (fn () => "Isabelle: " ^ Display.string_of_thm_without_context th));
   384 
   385 
   385 fun lookth thpairs (fth : Metis.Thm.thm) =
   386 fun lookth thpairs (fth : Metis.Thm.thm) =
   386   the (AList.lookup (uncurry Metis.Thm.equal) thpairs fth)
   387   the (AList.lookup (uncurry Metis.Thm.equal) thpairs fth)
   387   handle Option => error ("Failed to find a Metis theorem " ^ Metis.Thm.toString fth);
   388   handle Option =>
       
   389          raise Fail ("Failed to find a Metis theorem " ^ Metis.Thm.toString fth);
   388 
   390 
   389 fun is_TrueI th = Thm.eq_thm(TrueI,th);
   391 fun is_TrueI th = Thm.eq_thm(TrueI,th);
   390 
   392 
   391 fun cterm_incr_types thy idx = cterm_of thy o (map_types (Logic.incr_tvar idx));
   393 fun cterm_incr_types thy idx = cterm_of thy o (map_types (Logic.incr_tvar idx));
   392 
   394 
   475                               (Metis.Term.Fn atm)
   477                               (Metis.Term.Fn atm)
   476         val _ = trace_msg (fn () => "  atom: " ^ Syntax.string_of_term ctxt i_atm)
   478         val _ = trace_msg (fn () => "  atom: " ^ Syntax.string_of_term ctxt i_atm)
   477         val prems_th1 = prems_of i_th1
   479         val prems_th1 = prems_of i_th1
   478         val prems_th2 = prems_of i_th2
   480         val prems_th2 = prems_of i_th2
   479         val index_th1 = get_index (mk_not i_atm) prems_th1
   481         val index_th1 = get_index (mk_not i_atm) prems_th1
   480               handle Empty => error "Failed to find literal in th1"
   482               handle Empty => raise Fail "Failed to find literal in th1"
   481         val _ = trace_msg (fn () => "  index_th1: " ^ Int.toString index_th1)
   483         val _ = trace_msg (fn () => "  index_th1: " ^ Int.toString index_th1)
   482         val index_th2 = get_index i_atm prems_th2
   484         val index_th2 = get_index i_atm prems_th2
   483               handle Empty => error "Failed to find literal in th2"
   485               handle Empty => raise Fail "Failed to find literal in th2"
   484         val _ = trace_msg (fn () => "  index_th2: " ^ Int.toString index_th2)
   486         val _ = trace_msg (fn () => "  index_th2: " ^ Int.toString index_th2)
   485     in  resolve_inc_tyvars (Meson.select_literal index_th1 i_th1, index_th2, i_th2)  end
   487     in  resolve_inc_tyvars (Meson.select_literal index_th1 i_th1, index_th2, i_th2)  end
   486   end;
   488   end;
   487 
   489 
   488 (* INFERENCE RULE: REFL *)
   490 (* INFERENCE RULE: REFL *)
   523                 (r, list_comb (tm1, replace_item_list t p' args))
   525                 (r, list_comb (tm1, replace_item_list t p' args))
   524             end
   526             end
   525       fun path_finder_HO tm [] = (tm, Term.Bound 0)
   527       fun path_finder_HO tm [] = (tm, Term.Bound 0)
   526         | path_finder_HO (t$u) (0::ps) = (fn(x,y) => (x, y$u)) (path_finder_HO t ps)
   528         | path_finder_HO (t$u) (0::ps) = (fn(x,y) => (x, y$u)) (path_finder_HO t ps)
   527         | path_finder_HO (t$u) (_::ps) = (fn(x,y) => (x, t$y)) (path_finder_HO u ps)
   529         | path_finder_HO (t$u) (_::ps) = (fn(x,y) => (x, t$y)) (path_finder_HO u ps)
       
   530         | path_finder_HO tm ps =
       
   531           raise Fail ("equality_inf, path_finder_HO: path = " ^
       
   532                       space_implode " " (map Int.toString ps) ^
       
   533                       " isa-term: " ^  Syntax.string_of_term ctxt tm)
   528       fun path_finder_FT tm [] _ = (tm, Term.Bound 0)
   534       fun path_finder_FT tm [] _ = (tm, Term.Bound 0)
   529         | path_finder_FT tm (0::ps) (Metis.Term.Fn ("ti", [t1, _])) =
   535         | path_finder_FT tm (0::ps) (Metis.Term.Fn ("ti", [t1, _])) =
   530             path_finder_FT tm ps t1
   536             path_finder_FT tm ps t1
   531         | path_finder_FT (t$u) (0::ps) (Metis.Term.Fn (".", [t1, _])) =
   537         | path_finder_FT (t$u) (0::ps) (Metis.Term.Fn (".", [t1, _])) =
   532             (fn(x,y) => (x, y$u)) (path_finder_FT t ps t1)
   538             (fn(x,y) => (x, y$u)) (path_finder_FT t ps t1)
   533         | path_finder_FT (t$u) (1::ps) (Metis.Term.Fn (".", [_, t2])) =
   539         | path_finder_FT (t$u) (1::ps) (Metis.Term.Fn (".", [_, t2])) =
   534             (fn(x,y) => (x, t$y)) (path_finder_FT u ps t2)
   540             (fn(x,y) => (x, t$y)) (path_finder_FT u ps t2)
   535         | path_finder_FT tm ps t = error ("equality_inf, path_finder_FT: path = " ^
   541         | path_finder_FT tm ps t =
   536                                         space_implode " " (map Int.toString ps) ^
   542           raise Fail ("equality_inf, path_finder_FT: path = " ^
   537                                         " isa-term: " ^  Syntax.string_of_term ctxt tm ^
   543                       space_implode " " (map Int.toString ps) ^
   538                                         " fol-term: " ^ Metis.Term.toString t)
   544                       " isa-term: " ^  Syntax.string_of_term ctxt tm ^
       
   545                       " fol-term: " ^ Metis.Term.toString t)
   539       fun path_finder FO tm ps _ = path_finder_FO tm ps
   546       fun path_finder FO tm ps _ = path_finder_FO tm ps
   540         | path_finder HO (tm as Const(@{const_name "op ="},_) $ _ $ _) (p::ps) _ =
   547         | path_finder HO (tm as Const(@{const_name "op ="},_) $ _ $ _) (p::ps) _ =
   541              (*equality: not curried, as other predicates are*)
   548              (*equality: not curried, as other predicates are*)
   542              if p=0 then path_finder_HO tm (0::1::ps)  (*select first operand*)
   549              if p=0 then path_finder_HO tm (0::1::ps)  (*select first operand*)
   543              else path_finder_HO tm (p::ps)        (*1 selects second operand*)
   550              else path_finder_HO tm (p::ps)        (*1 selects second operand*)
   585   | (_, Metis.Proof.Equality (f_lit, f_p, f_r)) =>
   592   | (_, Metis.Proof.Equality (f_lit, f_p, f_r)) =>
   586     equality_inf ctxt mode skolem_somes f_lit f_p f_r
   593     equality_inf ctxt mode skolem_somes f_lit f_p f_r
   587 
   594 
   588 fun real_literal (_, (c, _)) = not (String.isPrefix class_prefix c);
   595 fun real_literal (_, (c, _)) = not (String.isPrefix class_prefix c);
   589 
   596 
   590 (* TODO: use "fold" instead *)
   597 (* FIXME: use "fold" instead *)
   591 fun translate _ _ _ thpairs [] = thpairs
   598 fun translate _ _ _ thpairs [] = thpairs
   592   | translate ctxt mode skolem_somes thpairs ((fol_th, inf) :: infpairs) =
   599   | translate ctxt mode skolem_somes thpairs ((fol_th, inf) :: infpairs) =
   593       let val _ = trace_msg (fn () => "=============================================")
   600       let val _ = trace_msg (fn () => "=============================================")
   594           val _ = trace_msg (fn () => "METIS THM: " ^ Metis.Thm.toString fol_th)
   601           val _ = trace_msg (fn () => "METIS THM: " ^ Metis.Thm.toString fol_th)
   595           val _ = trace_msg (fn () => "INFERENCE: " ^ Metis.Proof.inferenceToString inf)
   602           val _ = trace_msg (fn () => "INFERENCE: " ^ Metis.Proof.inferenceToString inf)
   682         in
   689         in
   683            {axioms = (mth, Meson.make_meta_clause ith) :: axioms,
   690            {axioms = (mth, Meson.make_meta_clause ith) :: axioms,
   684             tfrees = union (op =) tfree_lits tfrees,
   691             tfrees = union (op =) tfree_lits tfrees,
   685             skolem_somes = skolem_somes}
   692             skolem_somes = skolem_somes}
   686         end;
   693         end;
   687       val lmap = {axioms = [], tfrees = init_tfrees ctxt, skolem_somes = []}
   694       val lmap as {skolem_somes, ...} =
   688                  |> fold (add_thm true) cls
   695         {axioms = [], tfrees = init_tfrees ctxt, skolem_somes = []}
   689                  |> add_tfrees
   696         |> fold (add_thm true) cls
   690                  |> fold (add_thm false) ths
   697         |> add_tfrees
       
   698         |> fold (add_thm false) ths
   691       val clause_lists = map (Metis.Thm.clause o #1) (#axioms lmap)
   699       val clause_lists = map (Metis.Thm.clause o #1) (#axioms lmap)
   692       fun used c = exists (Metis.LiteralSet.exists (const_in_metis c o #2)) clause_lists
   700       fun used c = exists (Metis.LiteralSet.exists (const_in_metis c o #2)) clause_lists
   693       (*Now check for the existence of certain combinators*)
   701       (*Now check for the existence of certain combinators*)
   694       val thI  = if used "c_COMBI" then [cnf_th @{theory} @{thm COMBI_def}] else []
   702       val thI  = if used "c_COMBI" then [cnf_th @{theory} @{thm COMBI_def}] else []
   695       val thK  = if used "c_COMBK" then [cnf_th @{theory} @{thm COMBK_def}] else []
   703       val thK  = if used "c_COMBK" then [cnf_th @{theory} @{thm COMBK_def}] else []
   699       val thEQ  = if used "c_fequal" then [cnf_th @{theory} @{thm fequal_imp_equal}, cnf_th @{theory} @{thm equal_imp_fequal}] else []
   707       val thEQ  = if used "c_fequal" then [cnf_th @{theory} @{thm fequal_imp_equal}, cnf_th @{theory} @{thm equal_imp_fequal}] else []
   700       val lmap =
   708       val lmap =
   701         lmap |> mode <> FO
   709         lmap |> mode <> FO
   702                 ? fold (add_thm false) (thEQ @ thS @ thC @ thB @ thK @ thI)
   710                 ? fold (add_thm false) (thEQ @ thS @ thC @ thB @ thK @ thI)
   703   in
   711   in
   704       (mode, add_type_thm (type_ext thy (map prop_of (cls @ ths))) lmap)
   712       (mode, add_type_thm (type_ext thy 
       
   713                                 (* FIXME: Call"kill_skolem_Eps" here? *)
       
   714                           (map ((*snd o kill_skolem_Eps ~1 skolem_somes o*) prop_of)
       
   715                                (cls @ ths))) lmap)
   705   end;
   716   end;
   706 
   717 
   707 fun refute cls =
   718 fun refute cls =
   708     Metis.Resolution.loop (Metis.Resolution.new Metis.Resolution.default cls);
   719     Metis.Resolution.loop (Metis.Resolution.new Metis.Resolution.default cls);
   709 
   720