src/HOL/Tools/function_package/fundef_package.ML
author bulwahn
Sat May 16 20:17:59 2009 +0200 (2009-05-16)
changeset 31174 f1f1e9b53c81
parent 31172 74d72ba262fb
child 31177 c39994cb152a
permissions -rw-r--r--
added new kind generated_theorem for theorems which are generated by packages to distinguish between theorems from users and packages
krauss@19564
     1
(*  Title:      HOL/Tools/function_package/fundef_package.ML
krauss@19564
     2
    Author:     Alexander Krauss, TU Muenchen
krauss@19564
     3
wenzelm@20363
     4
A package for general recursive function definitions.
krauss@19564
     5
Isar commands.
krauss@19564
     6
*)
krauss@19564
     7
wenzelm@20363
     8
signature FUNDEF_PACKAGE =
krauss@19564
     9
sig
wenzelm@30493
    10
    val add_fundef :  (binding * typ option * mixfix) list
wenzelm@30493
    11
                       -> (Attrib.binding * term) list
wenzelm@30493
    12
                       -> FundefCommon.fundef_config
wenzelm@30493
    13
                       -> local_theory
wenzelm@30493
    14
                       -> Proof.state
wenzelm@30493
    15
    val add_fundef_cmd :  (binding * string option * mixfix) list
krauss@30789
    16
                      -> (Attrib.binding * string) list
wenzelm@20877
    17
                      -> FundefCommon.fundef_config
wenzelm@20877
    18
                      -> local_theory
krauss@22733
    19
                      -> Proof.state
krauss@20523
    20
wenzelm@30493
    21
    val termination_proof : term option -> local_theory -> Proof.state
wenzelm@30493
    22
    val termination_proof_cmd : string option -> local_theory -> Proof.state
wenzelm@30493
    23
    val termination : term option -> local_theory -> Proof.state
wenzelm@30493
    24
    val termination_cmd : string option -> local_theory -> Proof.state
krauss@19564
    25
krauss@19564
    26
    val setup : theory -> theory
wenzelm@30493
    27
    val get_congs : Proof.context -> thm list
krauss@19564
    28
end
krauss@19564
    29
krauss@19564
    30
krauss@23203
    31
structure FundefPackage : FUNDEF_PACKAGE =
krauss@19564
    32
struct
krauss@19564
    33
krauss@21051
    34
open FundefLib
krauss@19564
    35
open FundefCommon
krauss@19564
    36
krauss@30789
    37
val simp_attribs = map (Attrib.internal o K)
krauss@30789
    38
    [Simplifier.simp_add,
krauss@30789
    39
     Code.add_default_eqn_attribute,
bulwahn@31172
    40
     Nitpick_Const_Simp_Thms.add,
bulwahn@31172
    41
     Quickcheck_RecFun_Simp_Thms.add]
krauss@30789
    42
krauss@30789
    43
val psimp_attribs = map (Attrib.internal o K)
krauss@30789
    44
    [Simplifier.simp_add,
krauss@30789
    45
     Nitpick_Const_Psimp_Thms.add]
krauss@30789
    46
wenzelm@30435
    47
fun note_theorem ((name, atts), ths) =
bulwahn@31174
    48
  LocalTheory.note Thm.generated_theoremK ((Binding.qualified_name name, atts), ths)
wenzelm@21435
    49
krauss@30789
    50
fun mk_defname fixes = fixes |> map (fst o fst) |> space_implode "_"
krauss@22166
    51
krauss@26529
    52
fun add_simps fnames post sort extra_qualify label moreatts simps lthy =
krauss@19564
    53
    let
krauss@23819
    54
      val spec = post simps
krauss@30789
    55
                   |> map (apfst (apsnd (fn ats => moreatts @ ats)))
krauss@26529
    56
                   |> map (apfst (apfst extra_qualify))
krauss@21255
    57
krauss@22166
    58
      val (saved_spec_simps, lthy) =
bulwahn@31174
    59
        fold_map (LocalTheory.note Thm.generated_theoremK) spec lthy
krauss@23819
    60
krauss@22498
    61
      val saved_simps = flat (map snd saved_spec_simps)
krauss@22166
    62
      val simps_by_f = sort saved_simps
krauss@19564
    63
krauss@22166
    64
      fun add_for_f fname simps =
wenzelm@30364
    65
        note_theorem ((Long_Name.qualify fname label, []), simps) #> snd
krauss@19564
    66
    in
krauss@22166
    67
      (saved_simps,
krauss@22166
    68
       fold2 add_for_f fnames simps_by_f lthy)
krauss@19564
    69
    end
krauss@19564
    70
krauss@30787
    71
fun gen_add_fundef is_external prep default_constraint fixspec eqns config lthy =
krauss@20523
    72
    let
krauss@29051
    73
      val constrn_fxs = map (fn (b, T, mx) => (b, SOME (the_default default_constraint T), mx))
wenzelm@30486
    74
      val ((fixes0, spec0), ctxt') = prep (constrn_fxs fixspec) eqns lthy
wenzelm@30223
    75
      val fixes = map (apfst (apfst Binding.name_of)) fixes0;
krauss@30790
    76
      val spec = map (fn (bnd, prop) => (bnd, [prop])) spec0;
krauss@30787
    77
      val (eqs, post, sort_cont, cnames) = FundefCommon.get_preproc lthy config ctxt' fixes spec
krauss@22166
    78
krauss@22166
    79
      val defname = mk_defname fixes
krauss@22166
    80
krauss@23819
    81
      val ((goalstate, cont), lthy) =
krauss@23203
    82
          FundefMutual.prepare_fundef_mutual config defname fixes eqs lthy
krauss@20523
    83
krauss@30907
    84
      fun afterqed [[proof]] lthy =
krauss@30907
    85
        let
krauss@30907
    86
          val FundefResult {fs, R, psimps, trsimps,  simple_pinducts, termination,
krauss@30907
    87
                            domintros, cases, ...} =
krauss@30907
    88
          cont (Thm.close_derivation proof)
krauss@30907
    89
krauss@30907
    90
          val fnames = map (fst o fst) fixes
krauss@30907
    91
          val qualify = Long_Name.qualify defname
krauss@30907
    92
          val addsmps = add_simps fnames post sort_cont
krauss@30907
    93
krauss@30907
    94
          val (((psimps', pinducts'), (_, [termination'])), lthy) =
krauss@30907
    95
            lthy
krauss@30907
    96
            |> addsmps (Binding.qualify false "partial") "psimps"
krauss@30907
    97
                 psimp_attribs psimps
krauss@30907
    98
            ||> fold_option (snd oo addsmps I "simps" simp_attribs) trsimps
krauss@30907
    99
            ||>> note_theorem ((qualify "pinduct",
krauss@30907
   100
                   [Attrib.internal (K (RuleCases.case_names cnames)),
krauss@30907
   101
                    Attrib.internal (K (RuleCases.consumes 1)),
krauss@30907
   102
                    Attrib.internal (K (Induct.induct_pred ""))]), simple_pinducts)
krauss@30907
   103
            ||>> note_theorem ((qualify "termination", []), [termination])
krauss@30907
   104
            ||> (snd o note_theorem ((qualify "cases",
krauss@30907
   105
                   [Attrib.internal (K (RuleCases.case_names cnames))]), [cases]))
krauss@30907
   106
            ||> fold_option (snd oo curry note_theorem (qualify "domintros", [])) domintros
krauss@30907
   107
krauss@30907
   108
          val cdata = FundefCtxData { add_simps=addsmps, case_names=cnames, psimps=psimps',
krauss@30907
   109
                                      pinducts=snd pinducts', termination=termination',
krauss@30907
   110
                                      fs=fs, R=R, defname=defname }
krauss@30907
   111
          val _ =
krauss@30907
   112
            if not is_external then ()
krauss@30907
   113
            else Specification.print_consts lthy (K false) (map fst fixes)
krauss@30907
   114
        in
krauss@30907
   115
          lthy
krauss@30907
   116
          |> LocalTheory.declaration (add_fundef_data o morph_fundef_data cdata)
krauss@30907
   117
        end
krauss@20523
   118
    in
krauss@22733
   119
      lthy
wenzelm@26594
   120
        |> is_external ? LocalTheory.set_group (serial_string ())
krauss@22733
   121
        |> Proof.theorem_i NONE afterqed [[(Logic.unprotect (concl_of goalstate), [])]]
krauss@22733
   122
        |> Proof.refine (Method.primitive_text (fn _ => goalstate)) |> Seq.hd
krauss@20523
   123
    end
krauss@20523
   124
wenzelm@30493
   125
val add_fundef = gen_add_fundef false Specification.check_spec (TypeInfer.anyT HOLogic.typeS)
wenzelm@30493
   126
val add_fundef_cmd = gen_add_fundef true Specification.read_spec "_::type"
wenzelm@30493
   127
wenzelm@30493
   128
fun gen_termination_proof prep_term raw_term_opt lthy =
krauss@20523
   129
    let
wenzelm@30493
   130
      val term_opt = Option.map (prep_term lthy) raw_term_opt
krauss@22733
   131
      val data = the (case term_opt of
wenzelm@30493
   132
                        SOME t => (import_fundef_data t lthy
wenzelm@30493
   133
                          handle Option.Option =>
wenzelm@30493
   134
                            error ("Not a function: " ^ quote (Syntax.string_of_term lthy t)))
wenzelm@30493
   135
                      | NONE => (import_last_fundef lthy handle Option.Option => error "Not a function"))
krauss@20523
   136
krauss@30907
   137
        val FundefCtxData { termination, R, add_simps, case_names, psimps,
krauss@30907
   138
                            pinducts, defname, ...} = data
krauss@22325
   139
        val domT = domain_type (fastype_of R)
krauss@30907
   140
        val goal = HOLogic.mk_Trueprop
krauss@30907
   141
                     (HOLogic.mk_all ("x", domT, mk_acc domT R $ Free ("x", domT)))
krauss@30907
   142
        fun afterqed [[totality]] lthy =
krauss@30907
   143
          let
krauss@30907
   144
            val totality = Thm.close_derivation totality
krauss@30907
   145
            val remove_domain_condition =
krauss@30907
   146
              full_simplify (HOL_basic_ss addsimps [totality, True_implies_equals])
krauss@30907
   147
            val tsimps = map remove_domain_condition psimps
krauss@30907
   148
            val tinduct = map remove_domain_condition pinducts
krauss@30907
   149
            val qualify = Long_Name.qualify defname;
krauss@30907
   150
          in
krauss@30907
   151
            lthy
krauss@30907
   152
            |> add_simps I "simps" simp_attribs tsimps |> snd
krauss@30907
   153
            |> note_theorem
krauss@30907
   154
               ((qualify "induct",
krauss@30907
   155
                 [Attrib.internal (K (RuleCases.case_names case_names))]),
krauss@30907
   156
                tinduct) |> snd
krauss@30907
   157
          end
krauss@20523
   158
    in
wenzelm@20877
   159
      lthy
krauss@30907
   160
      |> ProofContext.note_thmss ""
krauss@30907
   161
         [((Binding.empty, [ContextRules.rule_del]), [([allI], [])])] |> snd
krauss@30907
   162
      |> ProofContext.note_thmss ""
krauss@30907
   163
         [((Binding.empty, [ContextRules.intro_bang (SOME 1)]), [([allI], [])])] |> snd
krauss@30907
   164
      |> ProofContext.note_thmss ""
krauss@30907
   165
         [((Binding.name "termination", [ContextRules.intro_bang (SOME 0)]),
krauss@30907
   166
           [([Goal.norm_result termination], [])])] |> snd
krauss@30907
   167
      |> Proof.theorem_i NONE afterqed [[(goal, [])]]
krauss@20523
   168
    end
krauss@20523
   169
wenzelm@30493
   170
val termination_proof = gen_termination_proof Syntax.check_term;
wenzelm@30493
   171
val termination_proof_cmd = gen_termination_proof Syntax.read_term;
wenzelm@30493
   172
wenzelm@30493
   173
fun termination term_opt lthy =
wenzelm@30493
   174
  lthy
wenzelm@30493
   175
  |> LocalTheory.set_group (serial_string ())
wenzelm@30493
   176
  |> termination_proof term_opt;
wenzelm@30493
   177
wenzelm@26171
   178
fun termination_cmd term_opt lthy =
wenzelm@26171
   179
  lthy
wenzelm@26171
   180
  |> LocalTheory.set_group (serial_string ())
wenzelm@30493
   181
  |> termination_proof_cmd term_opt;
krauss@19611
   182
krauss@19564
   183
krauss@21235
   184
(* Datatype hook to declare datatype congs as "fundef_congs" *)
krauss@21235
   185
krauss@21235
   186
wenzelm@21602
   187
fun add_case_cong n thy =
krauss@24168
   188
    Context.theory_map (FundefCtxTree.map_fundef_congs (Thm.add_thm
krauss@21235
   189
                          (DatatypePackage.get_datatype thy n |> the
krauss@21235
   190
                           |> #case_cong
wenzelm@21602
   191
                           |> safe_mk_meta_eq)))
krauss@21235
   192
                       thy
krauss@21235
   193
haftmann@24626
   194
val case_cong = fold add_case_cong
krauss@21235
   195
wenzelm@24711
   196
val setup_case_cong = DatatypePackage.interpretation case_cong
haftmann@24626
   197
wenzelm@30493
   198
krauss@19564
   199
(* setup *)
krauss@19564
   200
wenzelm@21602
   201
val setup =
krauss@30907
   202
  Attrib.setup @{binding fundef_cong}
krauss@30907
   203
    (Attrib.add_del FundefCtxTree.cong_add FundefCtxTree.cong_del)
krauss@30907
   204
    "declaration of congruence rule for function definitions"
haftmann@24626
   205
  #> setup_case_cong
wenzelm@22846
   206
  #> FundefRelation.setup
krauss@26749
   207
  #> FundefCommon.TerminationSimps.setup
krauss@19564
   208
wenzelm@30493
   209
val get_congs = FundefCtxTree.get_fundef_congs
krauss@19770
   210
krauss@21235
   211
krauss@19564
   212
(* outer syntax *)
krauss@19564
   213
krauss@19564
   214
local structure P = OuterParse and K = OuterKeyword in
krauss@19564
   215
wenzelm@24867
   216
val _ =
wenzelm@26989
   217
  OuterSyntax.local_theory_to_proof "function" "define general recursive functions" K.thy_goal
krauss@22498
   218
  (fundef_parser default_config
krauss@30787
   219
     >> (fn ((config, fixes), statements) => add_fundef_cmd fixes statements config));
krauss@20523
   220
wenzelm@24867
   221
val _ =
wenzelm@26989
   222
  OuterSyntax.local_theory_to_proof "termination" "prove termination of a recursive function" K.thy_goal
wenzelm@26989
   223
  (Scan.option P.term >> termination_cmd);
krauss@19564
   224
krauss@19564
   225
end;
krauss@19564
   226
krauss@19564
   227
wenzelm@19585
   228
end