src/Doc/Isar_Ref/Generic.thy
author haftmann
Tue Oct 13 09:21:15 2015 +0200 (2015-10-13)
changeset 61424 c3658c18b7bc
parent 61421 e0825405d398
child 61439 2bf52eec4e8a
permissions -rw-r--r--
prod_case as canonical name for product type eliminator
wenzelm@26782
     1
theory Generic
wenzelm@42651
     2
imports Base Main
wenzelm@26782
     3
begin
wenzelm@26782
     4
wenzelm@58618
     5
chapter \<open>Generic tools and packages \label{ch:gen-tools}\<close>
wenzelm@26782
     6
wenzelm@58618
     7
section \<open>Configuration options \label{sec:config}\<close>
wenzelm@26782
     8
wenzelm@58618
     9
text \<open>Isabelle/Pure maintains a record of named configuration
wenzelm@40291
    10
  options within the theory or proof context, with values of type
wenzelm@40291
    11
  @{ML_type bool}, @{ML_type int}, @{ML_type real}, or @{ML_type
wenzelm@40291
    12
  string}.  Tools may declare options in ML, and then refer to these
wenzelm@40291
    13
  values (relative to the context).  Thus global reference variables
wenzelm@40291
    14
  are easily avoided.  The user may change the value of a
wenzelm@40291
    15
  configuration option by means of an associated attribute of the same
wenzelm@40291
    16
  name.  This form of context declaration works particularly well with
wenzelm@42655
    17
  commands such as @{command "declare"} or @{command "using"} like
wenzelm@42655
    18
  this:
wenzelm@58618
    19
\<close>
wenzelm@42655
    20
wenzelm@59905
    21
(*<*)experiment begin(*>*)
wenzelm@42655
    22
declare [[show_main_goal = false]]
wenzelm@26782
    23
wenzelm@42655
    24
notepad
wenzelm@42655
    25
begin
wenzelm@42655
    26
  note [[show_main_goal = true]]
wenzelm@42655
    27
end
wenzelm@59905
    28
(*<*)end(*>*)
wenzelm@42655
    29
wenzelm@59921
    30
text \<open>
wenzelm@26782
    31
  \begin{matharray}{rcll}
wenzelm@52060
    32
    @{command_def "print_options"} & : & @{text "context \<rightarrow>"} \\
wenzelm@26782
    33
  \end{matharray}
wenzelm@26782
    34
wenzelm@55112
    35
  @{rail \<open>
wenzelm@59917
    36
    @@{command print_options} ('!'?)
wenzelm@59917
    37
    ;
wenzelm@42596
    38
    @{syntax name} ('=' ('true' | 'false' | @{syntax int} | @{syntax float} | @{syntax name}))?
wenzelm@55112
    39
  \<close>}
wenzelm@26782
    40
wenzelm@28760
    41
  \begin{description}
wenzelm@26782
    42
  
wenzelm@52060
    43
  \item @{command "print_options"} prints the available configuration
wenzelm@59917
    44
  options, with names, types, and current values; the ``@{text "!"}'' option
wenzelm@59917
    45
  indicates extra verbosity.
wenzelm@26782
    46
  
wenzelm@28760
    47
  \item @{text "name = value"} as an attribute expression modifies the
wenzelm@28760
    48
  named option, with the syntax of the value depending on the option's
wenzelm@28760
    49
  type.  For @{ML_type bool} the default value is @{text true}.  Any
wenzelm@28760
    50
  attempt to change a global option in a local context is ignored.
wenzelm@26782
    51
wenzelm@28760
    52
  \end{description}
wenzelm@58618
    53
\<close>
wenzelm@26782
    54
wenzelm@26782
    55
wenzelm@58618
    56
section \<open>Basic proof tools\<close>
wenzelm@26782
    57
wenzelm@58618
    58
subsection \<open>Miscellaneous methods and attributes \label{sec:misc-meth-att}\<close>
wenzelm@26782
    59
wenzelm@58618
    60
text \<open>
wenzelm@26782
    61
  \begin{matharray}{rcl}
wenzelm@28761
    62
    @{method_def unfold} & : & @{text method} \\
wenzelm@28761
    63
    @{method_def fold} & : & @{text method} \\
wenzelm@28761
    64
    @{method_def insert} & : & @{text method} \\[0.5ex]
wenzelm@28761
    65
    @{method_def erule}@{text "\<^sup>*"} & : & @{text method} \\
wenzelm@28761
    66
    @{method_def drule}@{text "\<^sup>*"} & : & @{text method} \\
wenzelm@28761
    67
    @{method_def frule}@{text "\<^sup>*"} & : & @{text method} \\
wenzelm@43365
    68
    @{method_def intro} & : & @{text method} \\
wenzelm@43365
    69
    @{method_def elim} & : & @{text method} \\
wenzelm@60554
    70
    @{method_def fail} & : & @{text method} \\
wenzelm@28761
    71
    @{method_def succeed} & : & @{text method} \\
wenzelm@60554
    72
    @{method_def sleep} & : & @{text method} \\
wenzelm@26782
    73
  \end{matharray}
wenzelm@26782
    74
wenzelm@55112
    75
  @{rail \<open>
wenzelm@42596
    76
    (@@{method fold} | @@{method unfold} | @@{method insert}) @{syntax thmrefs}
wenzelm@26782
    77
    ;
wenzelm@42596
    78
    (@@{method erule} | @@{method drule} | @@{method frule})
wenzelm@42596
    79
      ('(' @{syntax nat} ')')? @{syntax thmrefs}
wenzelm@43365
    80
    ;
wenzelm@43365
    81
    (@@{method intro} | @@{method elim}) @{syntax thmrefs}?
wenzelm@60556
    82
    ;
wenzelm@60556
    83
    @@{method sleep} @{syntax real}
wenzelm@55112
    84
  \<close>}
wenzelm@26782
    85
wenzelm@28760
    86
  \begin{description}
wenzelm@26782
    87
  
wenzelm@28760
    88
  \item @{method unfold}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} and @{method fold}~@{text
wenzelm@28760
    89
  "a\<^sub>1 \<dots> a\<^sub>n"} expand (or fold back) the given definitions throughout
wenzelm@28760
    90
  all goals; any chained facts provided are inserted into the goal and
wenzelm@28760
    91
  subject to rewriting as well.
wenzelm@26782
    92
wenzelm@28760
    93
  \item @{method insert}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} inserts theorems as facts
wenzelm@28760
    94
  into all goals of the proof state.  Note that current facts
wenzelm@28760
    95
  indicated for forward chaining are ignored.
wenzelm@26782
    96
wenzelm@30397
    97
  \item @{method erule}~@{text "a\<^sub>1 \<dots> a\<^sub>n"}, @{method
wenzelm@30397
    98
  drule}~@{text "a\<^sub>1 \<dots> a\<^sub>n"}, and @{method frule}~@{text
wenzelm@30397
    99
  "a\<^sub>1 \<dots> a\<^sub>n"} are similar to the basic @{method rule}
wenzelm@30397
   100
  method (see \secref{sec:pure-meth-att}), but apply rules by
wenzelm@30397
   101
  elim-resolution, destruct-resolution, and forward-resolution,
wenzelm@58552
   102
  respectively @{cite "isabelle-implementation"}.  The optional natural
wenzelm@30397
   103
  number argument (default 0) specifies additional assumption steps to
wenzelm@30397
   104
  be performed here.
wenzelm@26782
   105
wenzelm@26782
   106
  Note that these methods are improper ones, mainly serving for
wenzelm@26782
   107
  experimentation and tactic script emulation.  Different modes of
wenzelm@26782
   108
  basic rule application are usually expressed in Isar at the proof
wenzelm@26782
   109
  language level, rather than via implicit proof state manipulations.
wenzelm@26782
   110
  For example, a proper single-step elimination would be done using
wenzelm@26782
   111
  the plain @{method rule} method, with forward chaining of current
wenzelm@26782
   112
  facts.
wenzelm@26782
   113
wenzelm@43365
   114
  \item @{method intro} and @{method elim} repeatedly refine some goal
wenzelm@43365
   115
  by intro- or elim-resolution, after having inserted any chained
wenzelm@43365
   116
  facts.  Exactly the rules given as arguments are taken into account;
wenzelm@43365
   117
  this allows fine-tuned decomposition of a proof problem, in contrast
wenzelm@43365
   118
  to common automated tools.
wenzelm@43365
   119
wenzelm@60554
   120
  \item @{method fail} yields an empty result sequence; it is the
wenzelm@60554
   121
  identity of the ``@{text "|"}'' method combinator (cf.\
wenzelm@60554
   122
  \secref{sec:proof-meth}).
wenzelm@60554
   123
wenzelm@28760
   124
  \item @{method succeed} yields a single (unchanged) result; it is
wenzelm@26782
   125
  the identity of the ``@{text ","}'' method combinator (cf.\
wenzelm@28754
   126
  \secref{sec:proof-meth}).
wenzelm@26782
   127
wenzelm@60554
   128
  \item @{method sleep}~@{text s} succeeds after a real-time delay of @{text
wenzelm@60554
   129
  s} seconds. This is occasionally useful for demonstration and testing
wenzelm@60554
   130
  purposes.
wenzelm@26782
   131
wenzelm@28760
   132
  \end{description}
wenzelm@26782
   133
wenzelm@26782
   134
  \begin{matharray}{rcl}
wenzelm@28761
   135
    @{attribute_def tagged} & : & @{text attribute} \\
wenzelm@28761
   136
    @{attribute_def untagged} & : & @{text attribute} \\[0.5ex]
wenzelm@28761
   137
    @{attribute_def THEN} & : & @{text attribute} \\
wenzelm@28761
   138
    @{attribute_def unfolded} & : & @{text attribute} \\
wenzelm@47497
   139
    @{attribute_def folded} & : & @{text attribute} \\
wenzelm@47497
   140
    @{attribute_def abs_def} & : & @{text attribute} \\[0.5ex]
wenzelm@28761
   141
    @{attribute_def rotated} & : & @{text attribute} \\
wenzelm@28761
   142
    @{attribute_def (Pure) elim_format} & : & @{text attribute} \\
wenzelm@28761
   143
    @{attribute_def no_vars}@{text "\<^sup>*"} & : & @{text attribute} \\
wenzelm@26782
   144
  \end{matharray}
wenzelm@26782
   145
wenzelm@55112
   146
  @{rail \<open>
wenzelm@42596
   147
    @@{attribute tagged} @{syntax name} @{syntax name}
wenzelm@26782
   148
    ;
wenzelm@42596
   149
    @@{attribute untagged} @{syntax name}
wenzelm@26782
   150
    ;
wenzelm@48205
   151
    @@{attribute THEN} ('[' @{syntax nat} ']')? @{syntax thmref}
wenzelm@26782
   152
    ;
wenzelm@42596
   153
    (@@{attribute unfolded} | @@{attribute folded}) @{syntax thmrefs}
wenzelm@26782
   154
    ;
wenzelm@42596
   155
    @@{attribute rotated} @{syntax int}?
wenzelm@55112
   156
  \<close>}
wenzelm@26782
   157
wenzelm@28760
   158
  \begin{description}
wenzelm@26782
   159
wenzelm@28764
   160
  \item @{attribute tagged}~@{text "name value"} and @{attribute
wenzelm@28760
   161
  untagged}~@{text name} add and remove \emph{tags} of some theorem.
wenzelm@26782
   162
  Tags may be any list of string pairs that serve as formal comment.
wenzelm@28764
   163
  The first string is considered the tag name, the second its value.
wenzelm@28764
   164
  Note that @{attribute untagged} removes any tags of the same name.
wenzelm@26782
   165
wenzelm@48205
   166
  \item @{attribute THEN}~@{text a} composes rules by resolution; it
wenzelm@48205
   167
  resolves with the first premise of @{text a} (an alternative
wenzelm@48205
   168
  position may be also specified).  See also @{ML_op "RS"} in
wenzelm@58552
   169
  @{cite "isabelle-implementation"}.
wenzelm@26782
   170
  
wenzelm@28760
   171
  \item @{attribute unfolded}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} and @{attribute
wenzelm@28760
   172
  folded}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} expand and fold back again the given
wenzelm@28760
   173
  definitions throughout a rule.
wenzelm@26782
   174
wenzelm@47497
   175
  \item @{attribute abs_def} turns an equation of the form @{prop "f x
wenzelm@47497
   176
  y \<equiv> t"} into @{prop "f \<equiv> \<lambda>x y. t"}, which ensures that @{method
wenzelm@47497
   177
  simp} or @{method unfold} steps always expand it.  This also works
wenzelm@47497
   178
  for object-logic equality.
wenzelm@47497
   179
wenzelm@28760
   180
  \item @{attribute rotated}~@{text n} rotate the premises of a
wenzelm@26782
   181
  theorem by @{text n} (default 1).
wenzelm@26782
   182
wenzelm@28760
   183
  \item @{attribute (Pure) elim_format} turns a destruction rule into
wenzelm@28760
   184
  elimination rule format, by resolving with the rule @{prop "PROP A \<Longrightarrow>
wenzelm@28760
   185
  (PROP A \<Longrightarrow> PROP B) \<Longrightarrow> PROP B"}.
wenzelm@26782
   186
  
wenzelm@26782
   187
  Note that the Classical Reasoner (\secref{sec:classical}) provides
wenzelm@26782
   188
  its own version of this operation.
wenzelm@26782
   189
wenzelm@28760
   190
  \item @{attribute no_vars} replaces schematic variables by free
wenzelm@26782
   191
  ones; this is mainly for tuning output of pretty printed theorems.
wenzelm@26782
   192
wenzelm@28760
   193
  \end{description}
wenzelm@58618
   194
\<close>
wenzelm@26782
   195
wenzelm@26782
   196
wenzelm@58618
   197
subsection \<open>Low-level equational reasoning\<close>
wenzelm@27044
   198
wenzelm@58618
   199
text \<open>
wenzelm@27044
   200
  \begin{matharray}{rcl}
wenzelm@28761
   201
    @{method_def subst} & : & @{text method} \\
wenzelm@28761
   202
    @{method_def hypsubst} & : & @{text method} \\
wenzelm@28761
   203
    @{method_def split} & : & @{text method} \\
wenzelm@27044
   204
  \end{matharray}
wenzelm@27044
   205
wenzelm@55112
   206
  @{rail \<open>
wenzelm@55029
   207
    @@{method subst} ('(' 'asm' ')')? \<newline> ('(' (@{syntax nat}+) ')')? @{syntax thmref}
wenzelm@27044
   208
    ;
wenzelm@44094
   209
    @@{method split} @{syntax thmrefs}
wenzelm@55112
   210
  \<close>}
wenzelm@27044
   211
wenzelm@27044
   212
  These methods provide low-level facilities for equational reasoning
wenzelm@27044
   213
  that are intended for specialized applications only.  Normally,
wenzelm@27044
   214
  single step calculations would be performed in a structured text
wenzelm@27044
   215
  (see also \secref{sec:calculation}), while the Simplifier methods
wenzelm@27044
   216
  provide the canonical way for automated normalization (see
wenzelm@27044
   217
  \secref{sec:simplifier}).
wenzelm@27044
   218
wenzelm@28760
   219
  \begin{description}
wenzelm@27044
   220
wenzelm@28760
   221
  \item @{method subst}~@{text eq} performs a single substitution step
wenzelm@28760
   222
  using rule @{text eq}, which may be either a meta or object
wenzelm@27044
   223
  equality.
wenzelm@27044
   224
wenzelm@28760
   225
  \item @{method subst}~@{text "(asm) eq"} substitutes in an
wenzelm@27044
   226
  assumption.
wenzelm@27044
   227
wenzelm@28760
   228
  \item @{method subst}~@{text "(i \<dots> j) eq"} performs several
wenzelm@27044
   229
  substitutions in the conclusion. The numbers @{text i} to @{text j}
wenzelm@27044
   230
  indicate the positions to substitute at.  Positions are ordered from
wenzelm@27044
   231
  the top of the term tree moving down from left to right. For
wenzelm@27044
   232
  example, in @{text "(a + b) + (c + d)"} there are three positions
wenzelm@28760
   233
  where commutativity of @{text "+"} is applicable: 1 refers to @{text
wenzelm@28760
   234
  "a + b"}, 2 to the whole term, and 3 to @{text "c + d"}.
wenzelm@27044
   235
wenzelm@27044
   236
  If the positions in the list @{text "(i \<dots> j)"} are non-overlapping
wenzelm@27044
   237
  (e.g.\ @{text "(2 3)"} in @{text "(a + b) + (c + d)"}) you may
wenzelm@27044
   238
  assume all substitutions are performed simultaneously.  Otherwise
wenzelm@27044
   239
  the behaviour of @{text subst} is not specified.
wenzelm@27044
   240
wenzelm@28760
   241
  \item @{method subst}~@{text "(asm) (i \<dots> j) eq"} performs the
wenzelm@27071
   242
  substitutions in the assumptions. The positions refer to the
wenzelm@27071
   243
  assumptions in order from left to right.  For example, given in a
wenzelm@27071
   244
  goal of the form @{text "P (a + b) \<Longrightarrow> P (c + d) \<Longrightarrow> \<dots>"}, position 1 of
wenzelm@27071
   245
  commutativity of @{text "+"} is the subterm @{text "a + b"} and
wenzelm@27071
   246
  position 2 is the subterm @{text "c + d"}.
wenzelm@27044
   247
wenzelm@28760
   248
  \item @{method hypsubst} performs substitution using some
wenzelm@27044
   249
  assumption; this only works for equations of the form @{text "x =
wenzelm@27044
   250
  t"} where @{text x} is a free or bound variable.
wenzelm@27044
   251
wenzelm@28760
   252
  \item @{method split}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} performs single-step case
wenzelm@44094
   253
  splitting using the given rules.  Splitting is performed in the
wenzelm@44094
   254
  conclusion or some assumption of the subgoal, depending of the
wenzelm@44094
   255
  structure of the rule.
wenzelm@27044
   256
  
wenzelm@27044
   257
  Note that the @{method simp} method already involves repeated
wenzelm@44094
   258
  application of split rules as declared in the current context, using
wenzelm@44094
   259
  @{attribute split}, for example.
wenzelm@27044
   260
wenzelm@28760
   261
  \end{description}
wenzelm@58618
   262
\<close>
wenzelm@27044
   263
wenzelm@27044
   264
wenzelm@58618
   265
section \<open>The Simplifier \label{sec:simplifier}\<close>
wenzelm@26782
   266
wenzelm@58618
   267
text \<open>The Simplifier performs conditional and unconditional
wenzelm@50063
   268
  rewriting and uses contextual information: rule declarations in the
wenzelm@50063
   269
  background theory or local proof context are taken into account, as
wenzelm@50063
   270
  well as chained facts and subgoal premises (``local assumptions'').
wenzelm@50063
   271
  There are several general hooks that allow to modify the
wenzelm@50063
   272
  simplification strategy, or incorporate other proof tools that solve
wenzelm@50063
   273
  sub-problems, produce rewrite rules on demand etc.
wenzelm@50063
   274
wenzelm@50075
   275
  The rewriting strategy is always strictly bottom up, except for
wenzelm@50075
   276
  congruence rules, which are applied while descending into a term.
wenzelm@50075
   277
  Conditions in conditional rewrite rules are solved recursively
wenzelm@50075
   278
  before the rewrite rule is applied.
wenzelm@50075
   279
wenzelm@50063
   280
  The default Simplifier setup of major object logics (HOL, HOLCF,
wenzelm@50063
   281
  FOL, ZF) makes the Simplifier ready for immediate use, without
wenzelm@50063
   282
  engaging into the internal structures.  Thus it serves as
wenzelm@50063
   283
  general-purpose proof tool with the main focus on equational
wenzelm@50075
   284
  reasoning, and a bit more than that.
wenzelm@58618
   285
\<close>
wenzelm@50063
   286
wenzelm@50063
   287
wenzelm@58618
   288
subsection \<open>Simplification methods \label{sec:simp-meth}\<close>
wenzelm@26782
   289
wenzelm@58618
   290
text \<open>
wenzelm@57591
   291
  \begin{tabular}{rcll}
wenzelm@28761
   292
    @{method_def simp} & : & @{text method} \\
wenzelm@28761
   293
    @{method_def simp_all} & : & @{text method} \\
wenzelm@57591
   294
    @{attribute_def simp_depth_limit} & : & @{text attribute} & default @{text 100} \\
wenzelm@57591
   295
  \end{tabular}
wenzelm@61421
   296
  \<^medskip>
wenzelm@26782
   297
wenzelm@55112
   298
  @{rail \<open>
wenzelm@42596
   299
    (@@{method simp} | @@{method simp_all}) opt? (@{syntax simpmod} * )
wenzelm@26782
   300
    ;
wenzelm@26782
   301
wenzelm@40255
   302
    opt: '(' ('no_asm' | 'no_asm_simp' | 'no_asm_use' | 'asm_lr' ) ')'
wenzelm@26782
   303
    ;
wenzelm@50063
   304
    @{syntax_def simpmod}: ('add' | 'del' | 'only' | 'split' (() | 'add' | 'del') |
wenzelm@50063
   305
      'cong' (() | 'add' | 'del')) ':' @{syntax thmrefs}
wenzelm@55112
   306
  \<close>}
wenzelm@26782
   307
wenzelm@28760
   308
  \begin{description}
wenzelm@26782
   309
wenzelm@50063
   310
  \item @{method simp} invokes the Simplifier on the first subgoal,
wenzelm@50063
   311
  after inserting chained facts as additional goal premises; further
wenzelm@50063
   312
  rule declarations may be included via @{text "(simp add: facts)"}.
wenzelm@50063
   313
  The proof method fails if the subgoal remains unchanged after
wenzelm@50063
   314
  simplification.
wenzelm@26782
   315
wenzelm@50063
   316
  Note that the original goal premises and chained facts are subject
wenzelm@50063
   317
  to simplification themselves, while declarations via @{text
wenzelm@50063
   318
  "add"}/@{text "del"} merely follow the policies of the object-logic
wenzelm@50063
   319
  to extract rewrite rules from theorems, without further
wenzelm@50063
   320
  simplification.  This may lead to slightly different behavior in
wenzelm@50063
   321
  either case, which might be required precisely like that in some
wenzelm@50063
   322
  boundary situations to perform the intended simplification step!
wenzelm@50063
   323
wenzelm@61421
   324
  \<^medskip>
wenzelm@61421
   325
  The @{text only} modifier first removes all other rewrite
wenzelm@50063
   326
  rules, looper tactics (including split rules), congruence rules, and
wenzelm@50063
   327
  then behaves like @{text add}.  Implicit solvers remain, which means
wenzelm@50063
   328
  that trivial rules like reflexivity or introduction of @{text
wenzelm@50063
   329
  "True"} are available to solve the simplified subgoals, but also
wenzelm@50063
   330
  non-trivial tools like linear arithmetic in HOL.  The latter may
wenzelm@50063
   331
  lead to some surprise of the meaning of ``only'' in Isabelle/HOL
wenzelm@50063
   332
  compared to English!
wenzelm@26782
   333
wenzelm@61421
   334
  \<^medskip>
wenzelm@61421
   335
  The @{text split} modifiers add or delete rules for the
wenzelm@50079
   336
  Splitter (see also \secref{sec:simp-strategies} on the looper).
wenzelm@26782
   337
  This works only if the Simplifier method has been properly setup to
wenzelm@26782
   338
  include the Splitter (all major object logics such HOL, HOLCF, FOL,
wenzelm@26782
   339
  ZF do this already).
wenzelm@26782
   340
wenzelm@50065
   341
  There is also a separate @{method_ref split} method available for
wenzelm@50065
   342
  single-step case splitting.  The effect of repeatedly applying
wenzelm@50065
   343
  @{text "(split thms)"} can be imitated by ``@{text "(simp only:
wenzelm@50065
   344
  split: thms)"}''.
wenzelm@50065
   345
wenzelm@61421
   346
  \<^medskip>
wenzelm@61421
   347
  The @{text cong} modifiers add or delete Simplifier
wenzelm@50063
   348
  congruence rules (see also \secref{sec:simp-rules}); the default is
wenzelm@50063
   349
  to add.
wenzelm@50063
   350
wenzelm@28760
   351
  \item @{method simp_all} is similar to @{method simp}, but acts on
wenzelm@50063
   352
  all goals, working backwards from the last to the first one as usual
wenzelm@50063
   353
  in Isabelle.\footnote{The order is irrelevant for goals without
wenzelm@50063
   354
  schematic variables, so simplification might actually be performed
wenzelm@50063
   355
  in parallel here.}
wenzelm@50063
   356
wenzelm@50063
   357
  Chained facts are inserted into all subgoals, before the
wenzelm@50063
   358
  simplification process starts.  Further rule declarations are the
wenzelm@50063
   359
  same as for @{method simp}.
wenzelm@50063
   360
wenzelm@50063
   361
  The proof method fails if all subgoals remain unchanged after
wenzelm@50063
   362
  simplification.
wenzelm@26782
   363
wenzelm@57591
   364
  \item @{attribute simp_depth_limit} limits the number of recursive
wenzelm@57591
   365
  invocations of the Simplifier during conditional rewriting.
wenzelm@57591
   366
wenzelm@28760
   367
  \end{description}
wenzelm@26782
   368
wenzelm@50063
   369
  By default the Simplifier methods above take local assumptions fully
wenzelm@50063
   370
  into account, using equational assumptions in the subsequent
wenzelm@50063
   371
  normalization process, or simplifying assumptions themselves.
wenzelm@50063
   372
  Further options allow to fine-tune the behavior of the Simplifier
wenzelm@50063
   373
  in this respect, corresponding to a variety of ML tactics as
wenzelm@50063
   374
  follows.\footnote{Unlike the corresponding Isar proof methods, the
wenzelm@50063
   375
  ML tactics do not insist in changing the goal state.}
wenzelm@50063
   376
wenzelm@50063
   377
  \begin{center}
wenzelm@50063
   378
  \small
wenzelm@59782
   379
  \begin{tabular}{|l|l|p{0.3\textwidth}|}
wenzelm@50063
   380
  \hline
wenzelm@50063
   381
  Isar method & ML tactic & behavior \\\hline
wenzelm@50063
   382
wenzelm@50063
   383
  @{text "(simp (no_asm))"} & @{ML simp_tac} & assumptions are ignored
wenzelm@50063
   384
  completely \\\hline
wenzelm@26782
   385
wenzelm@50063
   386
  @{text "(simp (no_asm_simp))"} & @{ML asm_simp_tac} & assumptions
wenzelm@50063
   387
  are used in the simplification of the conclusion but are not
wenzelm@50063
   388
  themselves simplified \\\hline
wenzelm@50063
   389
wenzelm@50063
   390
  @{text "(simp (no_asm_use))"} & @{ML full_simp_tac} & assumptions
wenzelm@50063
   391
  are simplified but are not used in the simplification of each other
wenzelm@50063
   392
  or the conclusion \\\hline
wenzelm@26782
   393
wenzelm@50063
   394
  @{text "(simp)"} & @{ML asm_full_simp_tac} & assumptions are used in
wenzelm@50063
   395
  the simplification of the conclusion and to simplify other
wenzelm@50063
   396
  assumptions \\\hline
wenzelm@50063
   397
wenzelm@50063
   398
  @{text "(simp (asm_lr))"} & @{ML asm_lr_simp_tac} & compatibility
wenzelm@50063
   399
  mode: an assumption is only used for simplifying assumptions which
wenzelm@50063
   400
  are to the right of it \\\hline
wenzelm@50063
   401
wenzelm@59782
   402
  \end{tabular}
wenzelm@50063
   403
  \end{center}
wenzelm@58618
   404
\<close>
wenzelm@26782
   405
wenzelm@26782
   406
wenzelm@58618
   407
subsubsection \<open>Examples\<close>
wenzelm@50064
   408
wenzelm@58618
   409
text \<open>We consider basic algebraic simplifications in Isabelle/HOL.
wenzelm@50064
   410
  The rather trivial goal @{prop "0 + (x + 0) = x + 0 + 0"} looks like
wenzelm@50064
   411
  a good candidate to be solved by a single call of @{method simp}:
wenzelm@58618
   412
\<close>
wenzelm@50064
   413
wenzelm@50064
   414
lemma "0 + (x + 0) = x + 0 + 0" apply simp? oops
wenzelm@50064
   415
wenzelm@58618
   416
text \<open>The above attempt \emph{fails}, because @{term "0"} and @{term
wenzelm@50064
   417
  "op +"} in the HOL library are declared as generic type class
wenzelm@50064
   418
  operations, without stating any algebraic laws yet.  More specific
wenzelm@50064
   419
  types are required to get access to certain standard simplifications
wenzelm@58618
   420
  of the theory context, e.g.\ like this:\<close>
wenzelm@50064
   421
wenzelm@50064
   422
lemma fixes x :: nat shows "0 + (x + 0) = x + 0 + 0" by simp
wenzelm@50064
   423
lemma fixes x :: int shows "0 + (x + 0) = x + 0 + 0" by simp
wenzelm@50064
   424
lemma fixes x :: "'a :: monoid_add" shows "0 + (x + 0) = x + 0 + 0" by simp
wenzelm@50064
   425
wenzelm@58618
   426
text \<open>
wenzelm@61421
   427
  \<^medskip>
wenzelm@61421
   428
  In many cases, assumptions of a subgoal are also needed in
wenzelm@50064
   429
  the simplification process.  For example:
wenzelm@58618
   430
\<close>
wenzelm@50064
   431
wenzelm@50064
   432
lemma fixes x :: nat shows "x = 0 \<Longrightarrow> x + x = 0" by simp
wenzelm@50064
   433
lemma fixes x :: nat assumes "x = 0" shows "x + x = 0" apply simp oops
wenzelm@50064
   434
lemma fixes x :: nat assumes "x = 0" shows "x + x = 0" using assms by simp
wenzelm@50064
   435
wenzelm@58618
   436
text \<open>As seen above, local assumptions that shall contribute to
wenzelm@50064
   437
  simplification need to be part of the subgoal already, or indicated
wenzelm@50064
   438
  explicitly for use by the subsequent method invocation.  Both too
wenzelm@50064
   439
  little or too much information can make simplification fail, for
wenzelm@50064
   440
  different reasons.
wenzelm@50064
   441
wenzelm@50064
   442
  In the next example the malicious assumption @{prop "\<And>x::nat. f x =
wenzelm@50064
   443
  g (f (g x))"} does not contribute to solve the problem, but makes
wenzelm@50064
   444
  the default @{method simp} method loop: the rewrite rule @{text "f
wenzelm@50064
   445
  ?x \<equiv> g (f (g ?x))"} extracted from the assumption does not
wenzelm@50064
   446
  terminate.  The Simplifier notices certain simple forms of
wenzelm@50064
   447
  nontermination, but not this one.  The problem can be solved
wenzelm@50064
   448
  nonetheless, by ignoring assumptions via special options as
wenzelm@50064
   449
  explained before:
wenzelm@58618
   450
\<close>
wenzelm@50064
   451
wenzelm@50064
   452
lemma "(\<And>x::nat. f x = g (f (g x))) \<Longrightarrow> f 0 = f 0 + 0"
wenzelm@50064
   453
  by (simp (no_asm))
wenzelm@50064
   454
wenzelm@58618
   455
text \<open>The latter form is typical for long unstructured proof
wenzelm@50064
   456
  scripts, where the control over the goal content is limited.  In
wenzelm@50064
   457
  structured proofs it is usually better to avoid pushing too many
wenzelm@50064
   458
  facts into the goal state in the first place.  Assumptions in the
wenzelm@50064
   459
  Isar proof context do not intrude the reasoning if not used
wenzelm@50064
   460
  explicitly.  This is illustrated for a toplevel statement and a
wenzelm@50064
   461
  local proof body as follows:
wenzelm@58618
   462
\<close>
wenzelm@50064
   463
wenzelm@50064
   464
lemma
wenzelm@50064
   465
  assumes "\<And>x::nat. f x = g (f (g x))"
wenzelm@50064
   466
  shows "f 0 = f 0 + 0" by simp
wenzelm@50064
   467
wenzelm@50064
   468
notepad
wenzelm@50064
   469
begin
wenzelm@50064
   470
  assume "\<And>x::nat. f x = g (f (g x))"
wenzelm@50064
   471
  have "f 0 = f 0 + 0" by simp
wenzelm@50064
   472
end
wenzelm@50064
   473
wenzelm@61421
   474
text \<open>
wenzelm@61421
   475
  \<^medskip>
wenzelm@61421
   476
  Because assumptions may simplify each other, there
wenzelm@50064
   477
  can be very subtle cases of nontermination. For example, the regular
wenzelm@50064
   478
  @{method simp} method applied to @{prop "P (f x) \<Longrightarrow> y = x \<Longrightarrow> f x = f y
wenzelm@50064
   479
  \<Longrightarrow> Q"} gives rise to the infinite reduction sequence
wenzelm@50064
   480
  \[
wenzelm@50064
   481
  @{text "P (f x)"} \stackrel{@{text "f x \<equiv> f y"}}{\longmapsto}
wenzelm@50064
   482
  @{text "P (f y)"} \stackrel{@{text "y \<equiv> x"}}{\longmapsto}
wenzelm@50064
   483
  @{text "P (f x)"} \stackrel{@{text "f x \<equiv> f y"}}{\longmapsto} \cdots
wenzelm@50064
   484
  \]
wenzelm@50064
   485
  whereas applying the same to @{prop "y = x \<Longrightarrow> f x = f y \<Longrightarrow> P (f x) \<Longrightarrow>
wenzelm@50064
   486
  Q"} terminates (without solving the goal):
wenzelm@58618
   487
\<close>
wenzelm@50064
   488
wenzelm@50064
   489
lemma "y = x \<Longrightarrow> f x = f y \<Longrightarrow> P (f x) \<Longrightarrow> Q"
wenzelm@50064
   490
  apply simp
wenzelm@50064
   491
  oops
wenzelm@50064
   492
wenzelm@58618
   493
text \<open>See also \secref{sec:simp-trace} for options to enable
wenzelm@50064
   494
  Simplifier trace mode, which often helps to diagnose problems with
wenzelm@50064
   495
  rewrite systems.
wenzelm@58618
   496
\<close>
wenzelm@50064
   497
wenzelm@50064
   498
wenzelm@58618
   499
subsection \<open>Declaring rules \label{sec:simp-rules}\<close>
wenzelm@26782
   500
wenzelm@58618
   501
text \<open>
wenzelm@26782
   502
  \begin{matharray}{rcl}
wenzelm@28761
   503
    @{attribute_def simp} & : & @{text attribute} \\
wenzelm@28761
   504
    @{attribute_def split} & : & @{text attribute} \\
wenzelm@50063
   505
    @{attribute_def cong} & : & @{text attribute} \\
wenzelm@50077
   506
    @{command_def "print_simpset"}@{text "\<^sup>*"} & : & @{text "context \<rightarrow>"} \\
wenzelm@26782
   507
  \end{matharray}
wenzelm@26782
   508
wenzelm@55112
   509
  @{rail \<open>
wenzelm@50063
   510
    (@@{attribute simp} | @@{attribute split} | @@{attribute cong})
wenzelm@50063
   511
      (() | 'add' | 'del')
wenzelm@59917
   512
    ;
wenzelm@59917
   513
    @@{command print_simpset} ('!'?)
wenzelm@55112
   514
  \<close>}
wenzelm@26782
   515
wenzelm@28760
   516
  \begin{description}
wenzelm@26782
   517
wenzelm@50076
   518
  \item @{attribute simp} declares rewrite rules, by adding or
wenzelm@50065
   519
  deleting them from the simpset within the theory or proof context.
wenzelm@50076
   520
  Rewrite rules are theorems expressing some form of equality, for
wenzelm@50076
   521
  example:
wenzelm@50076
   522
wenzelm@50076
   523
  @{text "Suc ?m + ?n = ?m + Suc ?n"} \\
wenzelm@50076
   524
  @{text "?P \<and> ?P \<longleftrightarrow> ?P"} \\
wenzelm@50076
   525
  @{text "?A \<union> ?B \<equiv> {x. x \<in> ?A \<or> x \<in> ?B}"}
wenzelm@50076
   526
wenzelm@61421
   527
  \<^medskip>
wenzelm@50076
   528
  Conditional rewrites such as @{text "?m < ?n \<Longrightarrow> ?m div ?n = 0"} are
wenzelm@50076
   529
  also permitted; the conditions can be arbitrary formulas.
wenzelm@50076
   530
wenzelm@61421
   531
  \<^medskip>
wenzelm@61421
   532
  Internally, all rewrite rules are translated into Pure
wenzelm@50076
   533
  equalities, theorems with conclusion @{text "lhs \<equiv> rhs"}. The
wenzelm@50076
   534
  simpset contains a function for extracting equalities from arbitrary
wenzelm@50076
   535
  theorems, which is usually installed when the object-logic is
wenzelm@50076
   536
  configured initially. For example, @{text "\<not> ?x \<in> {}"} could be
wenzelm@50076
   537
  turned into @{text "?x \<in> {} \<equiv> False"}. Theorems that are declared as
wenzelm@50076
   538
  @{attribute simp} and local assumptions within a goal are treated
wenzelm@50076
   539
  uniformly in this respect.
wenzelm@50076
   540
wenzelm@50076
   541
  The Simplifier accepts the following formats for the @{text "lhs"}
wenzelm@50076
   542
  term:
wenzelm@50076
   543
wenzelm@50076
   544
  \begin{enumerate}
wenzelm@50065
   545
wenzelm@61421
   546
  \<^enum> First-order patterns, considering the sublanguage of
wenzelm@50076
   547
  application of constant operators to variable operands, without
wenzelm@50076
   548
  @{text "\<lambda>"}-abstractions or functional variables.
wenzelm@50076
   549
  For example:
wenzelm@50076
   550
wenzelm@50076
   551
  @{text "(?x + ?y) + ?z \<equiv> ?x + (?y + ?z)"} \\
wenzelm@50076
   552
  @{text "f (f ?x ?y) ?z \<equiv> f ?x (f ?y ?z)"}
wenzelm@50076
   553
wenzelm@61421
   554
  \<^enum> Higher-order patterns in the sense of @{cite "nipkow-patterns"}.
wenzelm@50076
   555
  These are terms in @{text "\<beta>"}-normal form (this will always be the
wenzelm@50076
   556
  case unless you have done something strange) where each occurrence
wenzelm@50076
   557
  of an unknown is of the form @{text "?F x\<^sub>1 \<dots> x\<^sub>n"}, where the
wenzelm@50076
   558
  @{text "x\<^sub>i"} are distinct bound variables.
wenzelm@50076
   559
wenzelm@50076
   560
  For example, @{text "(\<forall>x. ?P x \<and> ?Q x) \<equiv> (\<forall>x. ?P x) \<and> (\<forall>x. ?Q x)"}
wenzelm@50076
   561
  or its symmetric form, since the @{text "rhs"} is also a
wenzelm@50076
   562
  higher-order pattern.
wenzelm@50076
   563
wenzelm@61421
   564
  \<^enum> Physical first-order patterns over raw @{text "\<lambda>"}-term
wenzelm@50076
   565
  structure without @{text "\<alpha>\<beta>\<eta>"}-equality; abstractions and bound
wenzelm@50076
   566
  variables are treated like quasi-constant term material.
wenzelm@50076
   567
wenzelm@50076
   568
  For example, the rule @{text "?f ?x \<in> range ?f = True"} rewrites the
wenzelm@50076
   569
  term @{text "g a \<in> range g"} to @{text "True"}, but will fail to
wenzelm@50076
   570
  match @{text "g (h b) \<in> range (\<lambda>x. g (h x))"}. However, offending
wenzelm@50076
   571
  subterms (in our case @{text "?f ?x"}, which is not a pattern) can
wenzelm@50076
   572
  be replaced by adding new variables and conditions like this: @{text
wenzelm@50076
   573
  "?y = ?f ?x \<Longrightarrow> ?y \<in> range ?f = True"} is acceptable as a conditional
wenzelm@50076
   574
  rewrite rule of the second category since conditions can be
wenzelm@50076
   575
  arbitrary terms.
wenzelm@50076
   576
wenzelm@50076
   577
  \end{enumerate}
wenzelm@26782
   578
wenzelm@28760
   579
  \item @{attribute split} declares case split rules.
wenzelm@26782
   580
wenzelm@45645
   581
  \item @{attribute cong} declares congruence rules to the Simplifier
wenzelm@45645
   582
  context.
wenzelm@45645
   583
wenzelm@45645
   584
  Congruence rules are equalities of the form @{text [display]
wenzelm@45645
   585
  "\<dots> \<Longrightarrow> f ?x\<^sub>1 \<dots> ?x\<^sub>n = f ?y\<^sub>1 \<dots> ?y\<^sub>n"}
wenzelm@45645
   586
wenzelm@45645
   587
  This controls the simplification of the arguments of @{text f}.  For
wenzelm@45645
   588
  example, some arguments can be simplified under additional
wenzelm@45645
   589
  assumptions: @{text [display] "?P\<^sub>1 \<longleftrightarrow> ?Q\<^sub>1 \<Longrightarrow> (?Q\<^sub>1 \<Longrightarrow> ?P\<^sub>2 \<longleftrightarrow> ?Q\<^sub>2) \<Longrightarrow>
wenzelm@45645
   590
  (?P\<^sub>1 \<longrightarrow> ?P\<^sub>2) \<longleftrightarrow> (?Q\<^sub>1 \<longrightarrow> ?Q\<^sub>2)"}
wenzelm@45645
   591
wenzelm@56594
   592
  Given this rule, the Simplifier assumes @{text "?Q\<^sub>1"} and extracts
wenzelm@45645
   593
  rewrite rules from it when simplifying @{text "?P\<^sub>2"}.  Such local
wenzelm@45645
   594
  assumptions are effective for rewriting formulae such as @{text "x =
wenzelm@45645
   595
  0 \<longrightarrow> y + x = y"}.
wenzelm@45645
   596
wenzelm@45645
   597
  %FIXME
wenzelm@45645
   598
  %The local assumptions are also provided as theorems to the solver;
wenzelm@45645
   599
  %see \secref{sec:simp-solver} below.
wenzelm@45645
   600
wenzelm@61421
   601
  \<^medskip>
wenzelm@61421
   602
  The following congruence rule for bounded quantifiers also
wenzelm@45645
   603
  supplies contextual information --- about the bound variable:
wenzelm@45645
   604
  @{text [display] "(?A = ?B) \<Longrightarrow> (\<And>x. x \<in> ?B \<Longrightarrow> ?P x \<longleftrightarrow> ?Q x) \<Longrightarrow>
wenzelm@45645
   605
    (\<forall>x \<in> ?A. ?P x) \<longleftrightarrow> (\<forall>x \<in> ?B. ?Q x)"}
wenzelm@45645
   606
wenzelm@61421
   607
  \<^medskip>
wenzelm@61421
   608
  This congruence rule for conditional expressions can
wenzelm@45645
   609
  supply contextual information for simplifying the arms:
wenzelm@45645
   610
  @{text [display] "?p = ?q \<Longrightarrow> (?q \<Longrightarrow> ?a = ?c) \<Longrightarrow> (\<not> ?q \<Longrightarrow> ?b = ?d) \<Longrightarrow>
wenzelm@45645
   611
    (if ?p then ?a else ?b) = (if ?q then ?c else ?d)"}
wenzelm@45645
   612
wenzelm@45645
   613
  A congruence rule can also \emph{prevent} simplification of some
wenzelm@45645
   614
  arguments.  Here is an alternative congruence rule for conditional
wenzelm@45645
   615
  expressions that conforms to non-strict functional evaluation:
wenzelm@45645
   616
  @{text [display] "?p = ?q \<Longrightarrow> (if ?p then ?a else ?b) = (if ?q then ?a else ?b)"}
wenzelm@45645
   617
wenzelm@45645
   618
  Only the first argument is simplified; the others remain unchanged.
wenzelm@45645
   619
  This can make simplification much faster, but may require an extra
wenzelm@45645
   620
  case split over the condition @{text "?q"} to prove the goal.
wenzelm@50063
   621
wenzelm@59917
   622
  \item @{command "print_simpset"} prints the collection of rules declared
wenzelm@59917
   623
  to the Simplifier, which is also known as ``simpset'' internally; the
wenzelm@59917
   624
  ``@{text "!"}'' option indicates extra verbosity.
wenzelm@50077
   625
wenzelm@50077
   626
  For historical reasons, simpsets may occur independently from the
wenzelm@50077
   627
  current context, but are conceptually dependent on it.  When the
wenzelm@50077
   628
  Simplifier is invoked via one of its main entry points in the Isar
wenzelm@50077
   629
  source language (as proof method \secref{sec:simp-meth} or rule
wenzelm@50077
   630
  attribute \secref{sec:simp-meth}), its simpset is derived from the
wenzelm@50077
   631
  current proof context, and carries a back-reference to that for
wenzelm@50077
   632
  other tools that might get invoked internally (e.g.\ simplification
wenzelm@50077
   633
  procedures \secref{sec:simproc}).  A mismatch of the context of the
wenzelm@50077
   634
  simpset and the context of the problem being simplified may lead to
wenzelm@50077
   635
  unexpected results.
wenzelm@50077
   636
wenzelm@50063
   637
  \end{description}
wenzelm@50065
   638
wenzelm@50065
   639
  The implicit simpset of the theory context is propagated
wenzelm@50065
   640
  monotonically through the theory hierarchy: forming a new theory,
wenzelm@50065
   641
  the union of the simpsets of its imports are taken as starting
wenzelm@50065
   642
  point.  Also note that definitional packages like @{command
blanchet@58310
   643
  "datatype"}, @{command "primrec"}, @{command "fun"} routinely
wenzelm@50065
   644
  declare Simplifier rules to the target context, while plain
wenzelm@50065
   645
  @{command "definition"} is an exception in \emph{not} declaring
wenzelm@50065
   646
  anything.
wenzelm@50065
   647
wenzelm@61421
   648
  \<^medskip>
wenzelm@61421
   649
  It is up the user to manipulate the current simpset further
wenzelm@50065
   650
  by explicitly adding or deleting theorems as simplification rules,
wenzelm@50065
   651
  or installing other tools via simplification procedures
wenzelm@50065
   652
  (\secref{sec:simproc}).  Good simpsets are hard to design.  Rules
wenzelm@50065
   653
  that obviously simplify, like @{text "?n + 0 \<equiv> ?n"} are good
wenzelm@50065
   654
  candidates for the implicit simpset, unless a special
wenzelm@50065
   655
  non-normalizing behavior of certain operations is intended.  More
wenzelm@50065
   656
  specific rules (such as distributive laws, which duplicate subterms)
wenzelm@50065
   657
  should be added only for specific proof steps.  Conversely,
wenzelm@50065
   658
  sometimes a rule needs to be deleted just for some part of a proof.
wenzelm@50065
   659
  The need of frequent additions or deletions may indicate a poorly
wenzelm@50065
   660
  designed simpset.
wenzelm@50065
   661
wenzelm@50065
   662
  \begin{warn}
wenzelm@50065
   663
  The union of simpsets from theory imports (as described above) is
wenzelm@50065
   664
  not always a good starting point for the new theory.  If some
wenzelm@50065
   665
  ancestors have deleted simplification rules because they are no
wenzelm@50065
   666
  longer wanted, while others have left those rules in, then the union
wenzelm@50065
   667
  will contain the unwanted rules, and thus have to be deleted again
wenzelm@50065
   668
  in the theory body.
wenzelm@50065
   669
  \end{warn}
wenzelm@58618
   670
\<close>
wenzelm@45645
   671
wenzelm@45645
   672
wenzelm@58618
   673
subsection \<open>Ordered rewriting with permutative rules\<close>
wenzelm@50080
   674
wenzelm@58618
   675
text \<open>A rewrite rule is \emph{permutative} if the left-hand side and
wenzelm@50080
   676
  right-hand side are the equal up to renaming of variables.  The most
wenzelm@50080
   677
  common permutative rule is commutativity: @{text "?x + ?y = ?y +
wenzelm@50080
   678
  ?x"}.  Other examples include @{text "(?x - ?y) - ?z = (?x - ?z) -
wenzelm@50080
   679
  ?y"} in arithmetic and @{text "insert ?x (insert ?y ?A) = insert ?y
wenzelm@50080
   680
  (insert ?x ?A)"} for sets.  Such rules are common enough to merit
wenzelm@50080
   681
  special attention.
wenzelm@50080
   682
wenzelm@50080
   683
  Because ordinary rewriting loops given such rules, the Simplifier
wenzelm@50080
   684
  employs a special strategy, called \emph{ordered rewriting}.
wenzelm@50080
   685
  Permutative rules are detected and only applied if the rewriting
wenzelm@50080
   686
  step decreases the redex wrt.\ a given term ordering.  For example,
wenzelm@50080
   687
  commutativity rewrites @{text "b + a"} to @{text "a + b"}, but then
wenzelm@50080
   688
  stops, because the redex cannot be decreased further in the sense of
wenzelm@50080
   689
  the term ordering.
wenzelm@50080
   690
wenzelm@50080
   691
  The default is lexicographic ordering of term structure, but this
wenzelm@50080
   692
  could be also changed locally for special applications via
wenzelm@50080
   693
  @{index_ML Simplifier.set_termless} in Isabelle/ML.
wenzelm@50080
   694
wenzelm@61421
   695
  \<^medskip>
wenzelm@61421
   696
  Permutative rewrite rules are declared to the Simplifier
wenzelm@50080
   697
  just like other rewrite rules.  Their special status is recognized
wenzelm@50080
   698
  automatically, and their application is guarded by the term ordering
wenzelm@58618
   699
  accordingly.\<close>
wenzelm@50080
   700
wenzelm@50080
   701
wenzelm@58618
   702
subsubsection \<open>Rewriting with AC operators\<close>
wenzelm@50080
   703
wenzelm@58618
   704
text \<open>Ordered rewriting is particularly effective in the case of
wenzelm@50080
   705
  associative-commutative operators.  (Associativity by itself is not
wenzelm@50080
   706
  permutative.)  When dealing with an AC-operator @{text "f"}, keep
wenzelm@50080
   707
  the following points in mind:
wenzelm@50080
   708
wenzelm@50080
   709
  \begin{itemize}
wenzelm@50080
   710
wenzelm@61421
   711
  \<^item> The associative law must always be oriented from left to
wenzelm@50080
   712
  right, namely @{text "f (f x y) z = f x (f y z)"}.  The opposite
wenzelm@50080
   713
  orientation, if used with commutativity, leads to looping in
wenzelm@50080
   714
  conjunction with the standard term order.
wenzelm@50080
   715
wenzelm@61421
   716
  \<^item> To complete your set of rewrite rules, you must add not just
wenzelm@50080
   717
  associativity (A) and commutativity (C) but also a derived rule
wenzelm@50080
   718
  \emph{left-commutativity} (LC): @{text "f x (f y z) = f y (f x z)"}.
wenzelm@50080
   719
wenzelm@50080
   720
  \end{itemize}
wenzelm@50080
   721
wenzelm@50080
   722
  Ordered rewriting with the combination of A, C, and LC sorts a term
wenzelm@50080
   723
  lexicographically --- the rewriting engine imitates bubble-sort.
wenzelm@58618
   724
\<close>
wenzelm@50080
   725
wenzelm@59905
   726
experiment
wenzelm@50080
   727
  fixes f :: "'a \<Rightarrow> 'a \<Rightarrow> 'a"  (infix "\<bullet>" 60)
wenzelm@50080
   728
  assumes assoc: "(x \<bullet> y) \<bullet> z = x \<bullet> (y \<bullet> z)"
wenzelm@50080
   729
  assumes commute: "x \<bullet> y = y \<bullet> x"
wenzelm@50080
   730
begin
wenzelm@50080
   731
wenzelm@50080
   732
lemma left_commute: "x \<bullet> (y \<bullet> z) = y \<bullet> (x \<bullet> z)"
wenzelm@50080
   733
proof -
wenzelm@50080
   734
  have "(x \<bullet> y) \<bullet> z = (y \<bullet> x) \<bullet> z" by (simp only: commute)
wenzelm@50080
   735
  then show ?thesis by (simp only: assoc)
wenzelm@50080
   736
qed
wenzelm@50080
   737
wenzelm@50080
   738
lemmas AC_rules = assoc commute left_commute
wenzelm@50080
   739
wenzelm@58618
   740
text \<open>Thus the Simplifier is able to establish equalities with
wenzelm@50080
   741
  arbitrary permutations of subterms, by normalizing to a common
wenzelm@58618
   742
  standard form.  For example:\<close>
wenzelm@50080
   743
wenzelm@50080
   744
lemma "(b \<bullet> c) \<bullet> a = xxx"
wenzelm@50080
   745
  apply (simp only: AC_rules)
wenzelm@58618
   746
  txt \<open>@{subgoals}\<close>
wenzelm@50080
   747
  oops
wenzelm@50080
   748
wenzelm@50080
   749
lemma "(b \<bullet> c) \<bullet> a = a \<bullet> (b \<bullet> c)" by (simp only: AC_rules)
wenzelm@50080
   750
lemma "(b \<bullet> c) \<bullet> a = c \<bullet> (b \<bullet> a)" by (simp only: AC_rules)
wenzelm@50080
   751
lemma "(b \<bullet> c) \<bullet> a = (c \<bullet> b) \<bullet> a" by (simp only: AC_rules)
wenzelm@50080
   752
wenzelm@50080
   753
end
wenzelm@50080
   754
wenzelm@58618
   755
text \<open>Martin and Nipkow @{cite "martin-nipkow"} discuss the theory and
wenzelm@50080
   756
  give many examples; other algebraic structures are amenable to
wenzelm@56594
   757
  ordered rewriting, such as Boolean rings.  The Boyer-Moore theorem
wenzelm@58552
   758
  prover @{cite bm88book} also employs ordered rewriting.
wenzelm@58618
   759
\<close>
wenzelm@50080
   760
wenzelm@50080
   761
wenzelm@58618
   762
subsubsection \<open>Re-orienting equalities\<close>
wenzelm@50080
   763
wenzelm@58618
   764
text \<open>Another application of ordered rewriting uses the derived rule
wenzelm@50080
   765
  @{thm [source] eq_commute}: @{thm [source = false] eq_commute} to
wenzelm@50080
   766
  reverse equations.
wenzelm@50080
   767
wenzelm@50080
   768
  This is occasionally useful to re-orient local assumptions according
wenzelm@50080
   769
  to the term ordering, when other built-in mechanisms of
wenzelm@58618
   770
  reorientation and mutual simplification fail to apply.\<close>
wenzelm@50080
   771
wenzelm@50080
   772
wenzelm@58618
   773
subsection \<open>Simplifier tracing and debugging \label{sec:simp-trace}\<close>
wenzelm@50063
   774
wenzelm@58618
   775
text \<open>
wenzelm@50063
   776
  \begin{tabular}{rcll}
wenzelm@50063
   777
    @{attribute_def simp_trace} & : & @{text attribute} & default @{text false} \\
wenzelm@50063
   778
    @{attribute_def simp_trace_depth_limit} & : & @{text attribute} & default @{text 1} \\
wenzelm@50063
   779
    @{attribute_def simp_debug} & : & @{text attribute} & default @{text false} \\
wenzelm@57591
   780
    @{attribute_def simp_trace_new} & : & @{text attribute} \\
wenzelm@57591
   781
    @{attribute_def simp_break} & : & @{text attribute} \\
wenzelm@50063
   782
  \end{tabular}
wenzelm@61421
   783
  \<^medskip>
wenzelm@50063
   784
wenzelm@57591
   785
  @{rail \<open>
wenzelm@57591
   786
    @@{attribute simp_trace_new} ('interactive')? \<newline>
wenzelm@57591
   787
      ('mode' '=' ('full' | 'normal'))? \<newline>
wenzelm@57591
   788
      ('depth' '=' @{syntax nat})?
wenzelm@57591
   789
    ;
wenzelm@57591
   790
wenzelm@57591
   791
    @@{attribute simp_break} (@{syntax term}*)
wenzelm@57591
   792
  \<close>}
wenzelm@57591
   793
wenzelm@57591
   794
  These attributes and configurations options control various aspects of
wenzelm@57591
   795
  Simplifier tracing and debugging.
wenzelm@50063
   796
wenzelm@50063
   797
  \begin{description}
wenzelm@50063
   798
wenzelm@50063
   799
  \item @{attribute simp_trace} makes the Simplifier output internal
wenzelm@50063
   800
  operations.  This includes rewrite steps, but also bookkeeping like
wenzelm@50063
   801
  modifications of the simpset.
wenzelm@50063
   802
wenzelm@50063
   803
  \item @{attribute simp_trace_depth_limit} limits the effect of
wenzelm@50063
   804
  @{attribute simp_trace} to the given depth of recursive Simplifier
wenzelm@50063
   805
  invocations (when solving conditions of rewrite rules).
wenzelm@50063
   806
wenzelm@50063
   807
  \item @{attribute simp_debug} makes the Simplifier output some extra
wenzelm@50063
   808
  information about internal operations.  This includes any attempted
wenzelm@50063
   809
  invocation of simplification procedures.
wenzelm@50063
   810
wenzelm@57591
   811
  \item @{attribute simp_trace_new} controls Simplifier tracing within
wenzelm@58552
   812
  Isabelle/PIDE applications, notably Isabelle/jEdit @{cite "isabelle-jedit"}.
wenzelm@57591
   813
  This provides a hierarchical representation of the rewriting steps
wenzelm@57591
   814
  performed by the Simplifier.
wenzelm@57591
   815
wenzelm@57591
   816
  Users can configure the behaviour by specifying breakpoints, verbosity and
wenzelm@57591
   817
  enabling or disabling the interactive mode. In normal verbosity (the
wenzelm@57591
   818
  default), only rule applications matching a breakpoint will be shown to
wenzelm@57591
   819
  the user. In full verbosity, all rule applications will be logged.
wenzelm@57591
   820
  Interactive mode interrupts the normal flow of the Simplifier and defers
wenzelm@57591
   821
  the decision how to continue to the user via some GUI dialog.
wenzelm@57591
   822
wenzelm@57591
   823
  \item @{attribute simp_break} declares term or theorem breakpoints for
wenzelm@57591
   824
  @{attribute simp_trace_new} as described above. Term breakpoints are
wenzelm@57591
   825
  patterns which are checked for matches on the redex of a rule application.
wenzelm@57591
   826
  Theorem breakpoints trigger when the corresponding theorem is applied in a
wenzelm@57591
   827
  rewrite step. For example:
wenzelm@57591
   828
wenzelm@50063
   829
  \end{description}
wenzelm@58618
   830
\<close>
wenzelm@50063
   831
wenzelm@59905
   832
(*<*)experiment begin(*>*)
wenzelm@57591
   833
declare conjI [simp_break]
wenzelm@57590
   834
declare [[simp_break "?x \<and> ?y"]]
wenzelm@59905
   835
(*<*)end(*>*)
wenzelm@57590
   836
wenzelm@50063
   837
wenzelm@58618
   838
subsection \<open>Simplification procedures \label{sec:simproc}\<close>
wenzelm@26782
   839
wenzelm@58618
   840
text \<open>Simplification procedures are ML functions that produce proven
wenzelm@42925
   841
  rewrite rules on demand.  They are associated with higher-order
wenzelm@42925
   842
  patterns that approximate the left-hand sides of equations.  The
wenzelm@42925
   843
  Simplifier first matches the current redex against one of the LHS
wenzelm@42925
   844
  patterns; if this succeeds, the corresponding ML function is
wenzelm@42925
   845
  invoked, passing the Simplifier context and redex term.  Thus rules
wenzelm@42925
   846
  may be specifically fashioned for particular situations, resulting
wenzelm@42925
   847
  in a more powerful mechanism than term rewriting by a fixed set of
wenzelm@42925
   848
  rules.
wenzelm@42925
   849
wenzelm@42925
   850
  Any successful result needs to be a (possibly conditional) rewrite
wenzelm@42925
   851
  rule @{text "t \<equiv> u"} that is applicable to the current redex.  The
wenzelm@42925
   852
  rule will be applied just as any ordinary rewrite rule.  It is
wenzelm@42925
   853
  expected to be already in \emph{internal form}, bypassing the
wenzelm@42925
   854
  automatic preprocessing of object-level equivalences.
wenzelm@42925
   855
wenzelm@26782
   856
  \begin{matharray}{rcl}
wenzelm@28761
   857
    @{command_def "simproc_setup"} & : & @{text "local_theory \<rightarrow> local_theory"} \\
wenzelm@28761
   858
    simproc & : & @{text attribute} \\
wenzelm@26782
   859
  \end{matharray}
wenzelm@26782
   860
wenzelm@55112
   861
  @{rail \<open>
wenzelm@42596
   862
    @@{command simproc_setup} @{syntax name} '(' (@{syntax term} + '|') ')' '='
wenzelm@55029
   863
      @{syntax text} \<newline> (@'identifier' (@{syntax nameref}+))?
wenzelm@26782
   864
    ;
wenzelm@26782
   865
wenzelm@42596
   866
    @@{attribute simproc} (('add' ':')? | 'del' ':') (@{syntax name}+)
wenzelm@55112
   867
  \<close>}
wenzelm@26782
   868
wenzelm@28760
   869
  \begin{description}
wenzelm@26782
   870
wenzelm@28760
   871
  \item @{command "simproc_setup"} defines a named simplification
wenzelm@26782
   872
  procedure that is invoked by the Simplifier whenever any of the
wenzelm@26782
   873
  given term patterns match the current redex.  The implementation,
wenzelm@26782
   874
  which is provided as ML source text, needs to be of type @{ML_type
wenzelm@26782
   875
  "morphism -> simpset -> cterm -> thm option"}, where the @{ML_type
wenzelm@26782
   876
  cterm} represents the current redex @{text r} and the result is
wenzelm@26782
   877
  supposed to be some proven rewrite rule @{text "r \<equiv> r'"} (or a
wenzelm@26782
   878
  generalized version), or @{ML NONE} to indicate failure.  The
wenzelm@26782
   879
  @{ML_type simpset} argument holds the full context of the current
wenzelm@26782
   880
  Simplifier invocation, including the actual Isar proof context.  The
wenzelm@26782
   881
  @{ML_type morphism} informs about the difference of the original
wenzelm@26782
   882
  compilation context wrt.\ the one of the actual application later
wenzelm@26782
   883
  on.  The optional @{keyword "identifier"} specifies theorems that
wenzelm@26782
   884
  represent the logical content of the abstract theory of this
wenzelm@26782
   885
  simproc.
wenzelm@26782
   886
wenzelm@26782
   887
  Morphisms and identifiers are only relevant for simprocs that are
wenzelm@26782
   888
  defined within a local target context, e.g.\ in a locale.
wenzelm@26782
   889
wenzelm@28760
   890
  \item @{text "simproc add: name"} and @{text "simproc del: name"}
wenzelm@26782
   891
  add or delete named simprocs to the current Simplifier context.  The
wenzelm@26782
   892
  default is to add a simproc.  Note that @{command "simproc_setup"}
wenzelm@26782
   893
  already adds the new simproc to the subsequent context.
wenzelm@26782
   894
wenzelm@28760
   895
  \end{description}
wenzelm@58618
   896
\<close>
wenzelm@26782
   897
wenzelm@26782
   898
wenzelm@58618
   899
subsubsection \<open>Example\<close>
wenzelm@42925
   900
wenzelm@58618
   901
text \<open>The following simplification procedure for @{thm
wenzelm@42925
   902
  [source=false, show_types] unit_eq} in HOL performs fine-grained
wenzelm@42925
   903
  control over rule application, beyond higher-order pattern matching.
wenzelm@42925
   904
  Declaring @{thm unit_eq} as @{attribute simp} directly would make
wenzelm@56594
   905
  the Simplifier loop!  Note that a version of this simplification
wenzelm@58618
   906
  procedure is already active in Isabelle/HOL.\<close>
wenzelm@42925
   907
wenzelm@59905
   908
(*<*)experiment begin(*>*)
wenzelm@59782
   909
simproc_setup unit ("x::unit") =
wenzelm@59782
   910
  \<open>fn _ => fn _ => fn ct =>
wenzelm@59582
   911
    if HOLogic.is_unit (Thm.term_of ct) then NONE
wenzelm@59782
   912
    else SOME (mk_meta_eq @{thm unit_eq})\<close>
wenzelm@59905
   913
(*<*)end(*>*)
wenzelm@42925
   914
wenzelm@58618
   915
text \<open>Since the Simplifier applies simplification procedures
wenzelm@42925
   916
  frequently, it is important to make the failure check in ML
wenzelm@58618
   917
  reasonably fast.\<close>
wenzelm@42925
   918
wenzelm@42925
   919
wenzelm@58618
   920
subsection \<open>Configurable Simplifier strategies \label{sec:simp-strategies}\<close>
wenzelm@50079
   921
wenzelm@58618
   922
text \<open>The core term-rewriting engine of the Simplifier is normally
wenzelm@50079
   923
  used in combination with some add-on components that modify the
wenzelm@50079
   924
  strategy and allow to integrate other non-Simplifier proof tools.
wenzelm@50079
   925
  These may be reconfigured in ML as explained below.  Even if the
wenzelm@50079
   926
  default strategies of object-logics like Isabelle/HOL are used
wenzelm@50079
   927
  unchanged, it helps to understand how the standard Simplifier
wenzelm@58618
   928
  strategies work.\<close>
wenzelm@50079
   929
wenzelm@50079
   930
wenzelm@58618
   931
subsubsection \<open>The subgoaler\<close>
wenzelm@50079
   932
wenzelm@58618
   933
text \<open>
wenzelm@50079
   934
  \begin{mldecls}
wenzelm@51717
   935
  @{index_ML Simplifier.set_subgoaler: "(Proof.context -> int -> tactic) ->
wenzelm@51717
   936
  Proof.context -> Proof.context"} \\
wenzelm@51717
   937
  @{index_ML Simplifier.prems_of: "Proof.context -> thm list"} \\
wenzelm@50079
   938
  \end{mldecls}
wenzelm@50079
   939
wenzelm@50079
   940
  The subgoaler is the tactic used to solve subgoals arising out of
wenzelm@50079
   941
  conditional rewrite rules or congruence rules.  The default should
wenzelm@50079
   942
  be simplification itself.  In rare situations, this strategy may
wenzelm@50079
   943
  need to be changed.  For example, if the premise of a conditional
wenzelm@50079
   944
  rule is an instance of its conclusion, as in @{text "Suc ?m < ?n \<Longrightarrow>
wenzelm@50079
   945
  ?m < ?n"}, the default strategy could loop.  % FIXME !??
wenzelm@50079
   946
wenzelm@50079
   947
  \begin{description}
wenzelm@50079
   948
wenzelm@51717
   949
  \item @{ML Simplifier.set_subgoaler}~@{text "tac ctxt"} sets the
wenzelm@51717
   950
  subgoaler of the context to @{text "tac"}.  The tactic will
wenzelm@51717
   951
  be applied to the context of the running Simplifier instance.
wenzelm@50079
   952
wenzelm@51717
   953
  \item @{ML Simplifier.prems_of}~@{text "ctxt"} retrieves the current
wenzelm@51717
   954
  set of premises from the context.  This may be non-empty only if
wenzelm@50079
   955
  the Simplifier has been told to utilize local assumptions in the
wenzelm@50079
   956
  first place (cf.\ the options in \secref{sec:simp-meth}).
wenzelm@50079
   957
wenzelm@50079
   958
  \end{description}
wenzelm@50079
   959
wenzelm@50079
   960
  As an example, consider the following alternative subgoaler:
wenzelm@58618
   961
\<close>
wenzelm@50079
   962
wenzelm@59905
   963
ML_val \<open>
wenzelm@51717
   964
  fun subgoaler_tac ctxt =
wenzelm@58963
   965
    assume_tac ctxt ORELSE'
wenzelm@59498
   966
    resolve_tac ctxt (Simplifier.prems_of ctxt) ORELSE'
wenzelm@51717
   967
    asm_simp_tac ctxt
wenzelm@58618
   968
\<close>
wenzelm@50079
   969
wenzelm@58618
   970
text \<open>This tactic first tries to solve the subgoal by assumption or
wenzelm@50079
   971
  by resolving with with one of the premises, calling simplification
wenzelm@58618
   972
  only if that fails.\<close>
wenzelm@50079
   973
wenzelm@50079
   974
wenzelm@58618
   975
subsubsection \<open>The solver\<close>
wenzelm@50079
   976
wenzelm@58618
   977
text \<open>
wenzelm@50079
   978
  \begin{mldecls}
wenzelm@50079
   979
  @{index_ML_type solver} \\
wenzelm@51717
   980
  @{index_ML Simplifier.mk_solver: "string ->
wenzelm@51717
   981
  (Proof.context -> int -> tactic) -> solver"} \\
wenzelm@51717
   982
  @{index_ML_op setSolver: "Proof.context * solver -> Proof.context"} \\
wenzelm@51717
   983
  @{index_ML_op addSolver: "Proof.context * solver -> Proof.context"} \\
wenzelm@51717
   984
  @{index_ML_op setSSolver: "Proof.context * solver -> Proof.context"} \\
wenzelm@51717
   985
  @{index_ML_op addSSolver: "Proof.context * solver -> Proof.context"} \\
wenzelm@50079
   986
  \end{mldecls}
wenzelm@50079
   987
wenzelm@50079
   988
  A solver is a tactic that attempts to solve a subgoal after
wenzelm@50079
   989
  simplification.  Its core functionality is to prove trivial subgoals
wenzelm@50079
   990
  such as @{prop "True"} and @{text "t = t"}, but object-logics might
wenzelm@50079
   991
  be more ambitious.  For example, Isabelle/HOL performs a restricted
wenzelm@50079
   992
  version of linear arithmetic here.
wenzelm@50079
   993
wenzelm@50079
   994
  Solvers are packaged up in abstract type @{ML_type solver}, with
wenzelm@50079
   995
  @{ML Simplifier.mk_solver} as the only operation to create a solver.
wenzelm@50079
   996
wenzelm@61421
   997
  \<^medskip>
wenzelm@61421
   998
  Rewriting does not instantiate unknowns.  For example,
wenzelm@50079
   999
  rewriting alone cannot prove @{text "a \<in> ?A"} since this requires
wenzelm@50079
  1000
  instantiating @{text "?A"}.  The solver, however, is an arbitrary
wenzelm@50079
  1001
  tactic and may instantiate unknowns as it pleases.  This is the only
wenzelm@50079
  1002
  way the Simplifier can handle a conditional rewrite rule whose
wenzelm@50079
  1003
  condition contains extra variables.  When a simplification tactic is
wenzelm@50079
  1004
  to be combined with other provers, especially with the Classical
wenzelm@50079
  1005
  Reasoner, it is important whether it can be considered safe or not.
wenzelm@50079
  1006
  For this reason a simpset contains two solvers: safe and unsafe.
wenzelm@50079
  1007
wenzelm@50079
  1008
  The standard simplification strategy solely uses the unsafe solver,
wenzelm@50079
  1009
  which is appropriate in most cases.  For special applications where
wenzelm@50079
  1010
  the simplification process is not allowed to instantiate unknowns
wenzelm@50079
  1011
  within the goal, simplification starts with the safe solver, but may
wenzelm@50079
  1012
  still apply the ordinary unsafe one in nested simplifications for
wenzelm@50079
  1013
  conditional rules or congruences. Note that in this way the overall
wenzelm@50079
  1014
  tactic is not totally safe: it may instantiate unknowns that appear
wenzelm@50079
  1015
  also in other subgoals.
wenzelm@50079
  1016
wenzelm@50079
  1017
  \begin{description}
wenzelm@50079
  1018
wenzelm@50079
  1019
  \item @{ML Simplifier.mk_solver}~@{text "name tac"} turns @{text
wenzelm@50079
  1020
  "tac"} into a solver; the @{text "name"} is only attached as a
wenzelm@50079
  1021
  comment and has no further significance.
wenzelm@50079
  1022
wenzelm@51717
  1023
  \item @{text "ctxt setSSolver solver"} installs @{text "solver"} as
wenzelm@51717
  1024
  the safe solver of @{text "ctxt"}.
wenzelm@50079
  1025
wenzelm@51717
  1026
  \item @{text "ctxt addSSolver solver"} adds @{text "solver"} as an
wenzelm@50079
  1027
  additional safe solver; it will be tried after the solvers which had
wenzelm@51717
  1028
  already been present in @{text "ctxt"}.
wenzelm@50079
  1029
wenzelm@51717
  1030
  \item @{text "ctxt setSolver solver"} installs @{text "solver"} as the
wenzelm@51717
  1031
  unsafe solver of @{text "ctxt"}.
wenzelm@50079
  1032
wenzelm@51717
  1033
  \item @{text "ctxt addSolver solver"} adds @{text "solver"} as an
wenzelm@50079
  1034
  additional unsafe solver; it will be tried after the solvers which
wenzelm@51717
  1035
  had already been present in @{text "ctxt"}.
wenzelm@50079
  1036
wenzelm@50079
  1037
  \end{description}
wenzelm@50079
  1038
wenzelm@61421
  1039
  \<^medskip>
wenzelm@61421
  1040
  The solver tactic is invoked with the context of the
wenzelm@51717
  1041
  running Simplifier.  Further operations
wenzelm@50079
  1042
  may be used to retrieve relevant information, such as the list of
wenzelm@50079
  1043
  local Simplifier premises via @{ML Simplifier.prems_of} --- this
wenzelm@50079
  1044
  list may be non-empty only if the Simplifier runs in a mode that
wenzelm@50079
  1045
  utilizes local assumptions (see also \secref{sec:simp-meth}).  The
wenzelm@50079
  1046
  solver is also presented the full goal including its assumptions in
wenzelm@50079
  1047
  any case.  Thus it can use these (e.g.\ by calling @{ML
wenzelm@50079
  1048
  assume_tac}), even if the Simplifier proper happens to ignore local
wenzelm@50079
  1049
  premises at the moment.
wenzelm@50079
  1050
wenzelm@61421
  1051
  \<^medskip>
wenzelm@61421
  1052
  As explained before, the subgoaler is also used to solve
wenzelm@50079
  1053
  the premises of congruence rules.  These are usually of the form
wenzelm@50079
  1054
  @{text "s = ?x"}, where @{text "s"} needs to be simplified and
wenzelm@50079
  1055
  @{text "?x"} needs to be instantiated with the result.  Typically,
wenzelm@50079
  1056
  the subgoaler will invoke the Simplifier at some point, which will
wenzelm@50079
  1057
  eventually call the solver.  For this reason, solver tactics must be
wenzelm@50079
  1058
  prepared to solve goals of the form @{text "t = ?x"}, usually by
wenzelm@50079
  1059
  reflexivity.  In particular, reflexivity should be tried before any
wenzelm@50079
  1060
  of the fancy automated proof tools.
wenzelm@50079
  1061
wenzelm@50079
  1062
  It may even happen that due to simplification the subgoal is no
wenzelm@50079
  1063
  longer an equality.  For example, @{text "False \<longleftrightarrow> ?Q"} could be
wenzelm@50079
  1064
  rewritten to @{text "\<not> ?Q"}.  To cover this case, the solver could
wenzelm@50079
  1065
  try resolving with the theorem @{text "\<not> False"} of the
wenzelm@50079
  1066
  object-logic.
wenzelm@50079
  1067
wenzelm@61421
  1068
  \<^medskip>
wenzelm@50079
  1069
  \begin{warn}
wenzelm@50079
  1070
  If a premise of a congruence rule cannot be proved, then the
wenzelm@50079
  1071
  congruence is ignored.  This should only happen if the rule is
wenzelm@50079
  1072
  \emph{conditional} --- that is, contains premises not of the form
wenzelm@50079
  1073
  @{text "t = ?x"}.  Otherwise it indicates that some congruence rule,
wenzelm@50079
  1074
  or possibly the subgoaler or solver, is faulty.
wenzelm@50079
  1075
  \end{warn}
wenzelm@58618
  1076
\<close>
wenzelm@50079
  1077
wenzelm@50079
  1078
wenzelm@58618
  1079
subsubsection \<open>The looper\<close>
wenzelm@50079
  1080
wenzelm@58618
  1081
text \<open>
wenzelm@50079
  1082
  \begin{mldecls}
wenzelm@51717
  1083
  @{index_ML_op setloop: "Proof.context *
wenzelm@51717
  1084
  (Proof.context -> int -> tactic) -> Proof.context"} \\
wenzelm@51717
  1085
  @{index_ML_op addloop: "Proof.context *
wenzelm@51717
  1086
  (string * (Proof.context -> int -> tactic))
wenzelm@51717
  1087
  -> Proof.context"} \\
wenzelm@51717
  1088
  @{index_ML_op delloop: "Proof.context * string -> Proof.context"} \\
wenzelm@51717
  1089
  @{index_ML Splitter.add_split: "thm -> Proof.context -> Proof.context"} \\
wenzelm@51717
  1090
  @{index_ML Splitter.del_split: "thm -> Proof.context -> Proof.context"} \\
wenzelm@50079
  1091
  \end{mldecls}
wenzelm@50079
  1092
wenzelm@50079
  1093
  The looper is a list of tactics that are applied after
wenzelm@50079
  1094
  simplification, in case the solver failed to solve the simplified
wenzelm@50079
  1095
  goal.  If the looper succeeds, the simplification process is started
wenzelm@50079
  1096
  all over again.  Each of the subgoals generated by the looper is
wenzelm@50079
  1097
  attacked in turn, in reverse order.
wenzelm@50079
  1098
wenzelm@50079
  1099
  A typical looper is \emph{case splitting}: the expansion of a
wenzelm@50079
  1100
  conditional.  Another possibility is to apply an elimination rule on
wenzelm@50079
  1101
  the assumptions.  More adventurous loopers could start an induction.
wenzelm@50079
  1102
wenzelm@50079
  1103
  \begin{description}
wenzelm@50079
  1104
wenzelm@51717
  1105
  \item @{text "ctxt setloop tac"} installs @{text "tac"} as the only
wenzelm@52037
  1106
  looper tactic of @{text "ctxt"}.
wenzelm@50079
  1107
wenzelm@51717
  1108
  \item @{text "ctxt addloop (name, tac)"} adds @{text "tac"} as an
wenzelm@50079
  1109
  additional looper tactic with name @{text "name"}, which is
wenzelm@50079
  1110
  significant for managing the collection of loopers.  The tactic will
wenzelm@50079
  1111
  be tried after the looper tactics that had already been present in
wenzelm@52037
  1112
  @{text "ctxt"}.
wenzelm@50079
  1113
wenzelm@51717
  1114
  \item @{text "ctxt delloop name"} deletes the looper tactic that was
wenzelm@51717
  1115
  associated with @{text "name"} from @{text "ctxt"}.
wenzelm@50079
  1116
wenzelm@51717
  1117
  \item @{ML Splitter.add_split}~@{text "thm ctxt"} adds split tactics
wenzelm@51717
  1118
  for @{text "thm"} as additional looper tactics of @{text "ctxt"}.
wenzelm@50079
  1119
wenzelm@51717
  1120
  \item @{ML Splitter.del_split}~@{text "thm ctxt"} deletes the split
wenzelm@50079
  1121
  tactic corresponding to @{text thm} from the looper tactics of
wenzelm@51717
  1122
  @{text "ctxt"}.
wenzelm@50079
  1123
wenzelm@50079
  1124
  \end{description}
wenzelm@50079
  1125
wenzelm@50079
  1126
  The splitter replaces applications of a given function; the
wenzelm@50079
  1127
  right-hand side of the replacement can be anything.  For example,
wenzelm@50079
  1128
  here is a splitting rule for conditional expressions:
wenzelm@50079
  1129
wenzelm@50079
  1130
  @{text [display] "?P (if ?Q ?x ?y) \<longleftrightarrow> (?Q \<longrightarrow> ?P ?x) \<and> (\<not> ?Q \<longrightarrow> ?P ?y)"}
wenzelm@50079
  1131
wenzelm@50079
  1132
  Another example is the elimination operator for Cartesian products
haftmann@61424
  1133
  (which happens to be called @{const case_prod} in Isabelle/HOL:
wenzelm@50079
  1134
haftmann@61424
  1135
  @{text [display] "?P (case_prod ?f ?p) \<longleftrightarrow> (\<forall>a b. ?p = (a, b) \<longrightarrow> ?P (f a b))"}
wenzelm@50079
  1136
wenzelm@50079
  1137
  For technical reasons, there is a distinction between case splitting
wenzelm@50079
  1138
  in the conclusion and in the premises of a subgoal.  The former is
wenzelm@50079
  1139
  done by @{ML Splitter.split_tac} with rules like @{thm [source]
wenzelm@50079
  1140
  split_if} or @{thm [source] option.split}, which do not split the
wenzelm@50079
  1141
  subgoal, while the latter is done by @{ML Splitter.split_asm_tac}
wenzelm@50079
  1142
  with rules like @{thm [source] split_if_asm} or @{thm [source]
wenzelm@50079
  1143
  option.split_asm}, which split the subgoal.  The function @{ML
wenzelm@50079
  1144
  Splitter.add_split} automatically takes care of which tactic to
wenzelm@50079
  1145
  call, analyzing the form of the rules given as argument; it is the
wenzelm@50079
  1146
  same operation behind @{text "split"} attribute or method modifier
wenzelm@50079
  1147
  syntax in the Isar source language.
wenzelm@50079
  1148
wenzelm@50079
  1149
  Case splits should be allowed only when necessary; they are
wenzelm@50079
  1150
  expensive and hard to control.  Case-splitting on if-expressions in
wenzelm@50079
  1151
  the conclusion is usually beneficial, so it is enabled by default in
wenzelm@50079
  1152
  Isabelle/HOL and Isabelle/FOL/ZF.
wenzelm@50079
  1153
wenzelm@50079
  1154
  \begin{warn}
wenzelm@50079
  1155
  With @{ML Splitter.split_asm_tac} as looper component, the
wenzelm@50079
  1156
  Simplifier may split subgoals!  This might cause unexpected problems
wenzelm@50079
  1157
  in tactic expressions that silently assume 0 or 1 subgoals after
wenzelm@50079
  1158
  simplification.
wenzelm@50079
  1159
  \end{warn}
wenzelm@58618
  1160
\<close>
wenzelm@50079
  1161
wenzelm@50079
  1162
wenzelm@58618
  1163
subsection \<open>Forward simplification \label{sec:simp-forward}\<close>
wenzelm@26782
  1164
wenzelm@58618
  1165
text \<open>
wenzelm@26782
  1166
  \begin{matharray}{rcl}
wenzelm@28761
  1167
    @{attribute_def simplified} & : & @{text attribute} \\
wenzelm@26782
  1168
  \end{matharray}
wenzelm@26782
  1169
wenzelm@55112
  1170
  @{rail \<open>
wenzelm@42596
  1171
    @@{attribute simplified} opt? @{syntax thmrefs}?
wenzelm@26782
  1172
    ;
wenzelm@26782
  1173
wenzelm@40255
  1174
    opt: '(' ('no_asm' | 'no_asm_simp' | 'no_asm_use') ')'
wenzelm@55112
  1175
  \<close>}
wenzelm@26782
  1176
wenzelm@28760
  1177
  \begin{description}
wenzelm@26782
  1178
  
wenzelm@28760
  1179
  \item @{attribute simplified}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} causes a theorem to
wenzelm@28760
  1180
  be simplified, either by exactly the specified rules @{text "a\<^sub>1, \<dots>,
wenzelm@28760
  1181
  a\<^sub>n"}, or the implicit Simplifier context if no arguments are given.
wenzelm@28760
  1182
  The result is fully simplified by default, including assumptions and
wenzelm@28760
  1183
  conclusion; the options @{text no_asm} etc.\ tune the Simplifier in
wenzelm@28760
  1184
  the same way as the for the @{text simp} method.
wenzelm@26782
  1185
wenzelm@56594
  1186
  Note that forward simplification restricts the Simplifier to its
wenzelm@26782
  1187
  most basic operation of term rewriting; solver and looper tactics
wenzelm@50079
  1188
  (\secref{sec:simp-strategies}) are \emph{not} involved here.  The
wenzelm@50079
  1189
  @{attribute simplified} attribute should be only rarely required
wenzelm@50079
  1190
  under normal circumstances.
wenzelm@26782
  1191
wenzelm@28760
  1192
  \end{description}
wenzelm@58618
  1193
\<close>
wenzelm@26782
  1194
wenzelm@26782
  1195
wenzelm@58618
  1196
section \<open>The Classical Reasoner \label{sec:classical}\<close>
wenzelm@26782
  1197
wenzelm@58618
  1198
subsection \<open>Basic concepts\<close>
wenzelm@42927
  1199
wenzelm@58618
  1200
text \<open>Although Isabelle is generic, many users will be working in
wenzelm@42927
  1201
  some extension of classical first-order logic.  Isabelle/ZF is built
wenzelm@42927
  1202
  upon theory FOL, while Isabelle/HOL conceptually contains
wenzelm@42927
  1203
  first-order logic as a fragment.  Theorem-proving in predicate logic
wenzelm@42927
  1204
  is undecidable, but many automated strategies have been developed to
wenzelm@42927
  1205
  assist in this task.
wenzelm@42927
  1206
wenzelm@42927
  1207
  Isabelle's classical reasoner is a generic package that accepts
wenzelm@42927
  1208
  certain information about a logic and delivers a suite of automatic
wenzelm@42927
  1209
  proof tools, based on rules that are classified and declared in the
wenzelm@42927
  1210
  context.  These proof procedures are slow and simplistic compared
wenzelm@42927
  1211
  with high-end automated theorem provers, but they can save
wenzelm@42927
  1212
  considerable time and effort in practice.  They can prove theorems
wenzelm@58552
  1213
  such as Pelletier's @{cite pelletier86} problems 40 and 41 in a few
wenzelm@58618
  1214
  milliseconds (including full proof reconstruction):\<close>
wenzelm@42927
  1215
wenzelm@42927
  1216
lemma "(\<exists>y. \<forall>x. F x y \<longleftrightarrow> F x x) \<longrightarrow> \<not> (\<forall>x. \<exists>y. \<forall>z. F z y \<longleftrightarrow> \<not> F z x)"
wenzelm@42927
  1217
  by blast
wenzelm@42927
  1218
wenzelm@42927
  1219
lemma "(\<forall>z. \<exists>y. \<forall>x. f x y \<longleftrightarrow> f x z \<and> \<not> f x x) \<longrightarrow> \<not> (\<exists>z. \<forall>x. f x z)"
wenzelm@42927
  1220
  by blast
wenzelm@42927
  1221
wenzelm@58618
  1222
text \<open>The proof tools are generic.  They are not restricted to
wenzelm@42927
  1223
  first-order logic, and have been heavily used in the development of
wenzelm@42927
  1224
  the Isabelle/HOL library and applications.  The tactics can be
wenzelm@42927
  1225
  traced, and their components can be called directly; in this manner,
wenzelm@58618
  1226
  any proof can be viewed interactively.\<close>
wenzelm@42927
  1227
wenzelm@42927
  1228
wenzelm@58618
  1229
subsubsection \<open>The sequent calculus\<close>
wenzelm@42927
  1230
wenzelm@58618
  1231
text \<open>Isabelle supports natural deduction, which is easy to use for
wenzelm@42927
  1232
  interactive proof.  But natural deduction does not easily lend
wenzelm@42927
  1233
  itself to automation, and has a bias towards intuitionism.  For
wenzelm@42927
  1234
  certain proofs in classical logic, it can not be called natural.
wenzelm@42927
  1235
  The \emph{sequent calculus}, a generalization of natural deduction,
wenzelm@42927
  1236
  is easier to automate.
wenzelm@42927
  1237
wenzelm@42927
  1238
  A \textbf{sequent} has the form @{text "\<Gamma> \<turnstile> \<Delta>"}, where @{text "\<Gamma>"}
wenzelm@42927
  1239
  and @{text "\<Delta>"} are sets of formulae.\footnote{For first-order
wenzelm@42927
  1240
  logic, sequents can equivalently be made from lists or multisets of
wenzelm@42927
  1241
  formulae.} The sequent @{text "P\<^sub>1, \<dots>, P\<^sub>m \<turnstile> Q\<^sub>1, \<dots>, Q\<^sub>n"} is
wenzelm@42927
  1242
  \textbf{valid} if @{text "P\<^sub>1 \<and> \<dots> \<and> P\<^sub>m"} implies @{text "Q\<^sub>1 \<or> \<dots> \<or>
wenzelm@42927
  1243
  Q\<^sub>n"}.  Thus @{text "P\<^sub>1, \<dots>, P\<^sub>m"} represent assumptions, each of which
wenzelm@42927
  1244
  is true, while @{text "Q\<^sub>1, \<dots>, Q\<^sub>n"} represent alternative goals.  A
wenzelm@42927
  1245
  sequent is \textbf{basic} if its left and right sides have a common
wenzelm@42927
  1246
  formula, as in @{text "P, Q \<turnstile> Q, R"}; basic sequents are trivially
wenzelm@42927
  1247
  valid.
wenzelm@42927
  1248
wenzelm@42927
  1249
  Sequent rules are classified as \textbf{right} or \textbf{left},
wenzelm@42927
  1250
  indicating which side of the @{text "\<turnstile>"} symbol they operate on.
wenzelm@42927
  1251
  Rules that operate on the right side are analogous to natural
wenzelm@42927
  1252
  deduction's introduction rules, and left rules are analogous to
wenzelm@42927
  1253
  elimination rules.  The sequent calculus analogue of @{text "(\<longrightarrow>I)"}
wenzelm@42927
  1254
  is the rule
wenzelm@42927
  1255
  \[
wenzelm@42927
  1256
  \infer[@{text "(\<longrightarrow>R)"}]{@{text "\<Gamma> \<turnstile> \<Delta>, P \<longrightarrow> Q"}}{@{text "P, \<Gamma> \<turnstile> \<Delta>, Q"}}
wenzelm@42927
  1257
  \]
wenzelm@42927
  1258
  Applying the rule backwards, this breaks down some implication on
wenzelm@42927
  1259
  the right side of a sequent; @{text "\<Gamma>"} and @{text "\<Delta>"} stand for
wenzelm@42927
  1260
  the sets of formulae that are unaffected by the inference.  The
wenzelm@42927
  1261
  analogue of the pair @{text "(\<or>I1)"} and @{text "(\<or>I2)"} is the
wenzelm@42927
  1262
  single rule
wenzelm@42927
  1263
  \[
wenzelm@42927
  1264
  \infer[@{text "(\<or>R)"}]{@{text "\<Gamma> \<turnstile> \<Delta>, P \<or> Q"}}{@{text "\<Gamma> \<turnstile> \<Delta>, P, Q"}}
wenzelm@42927
  1265
  \]
wenzelm@42927
  1266
  This breaks down some disjunction on the right side, replacing it by
wenzelm@42927
  1267
  both disjuncts.  Thus, the sequent calculus is a kind of
wenzelm@42927
  1268
  multiple-conclusion logic.
wenzelm@42927
  1269
wenzelm@42927
  1270
  To illustrate the use of multiple formulae on the right, let us
wenzelm@42927
  1271
  prove the classical theorem @{text "(P \<longrightarrow> Q) \<or> (Q \<longrightarrow> P)"}.  Working
wenzelm@42927
  1272
  backwards, we reduce this formula to a basic sequent:
wenzelm@42927
  1273
  \[
wenzelm@42927
  1274
  \infer[@{text "(\<or>R)"}]{@{text "\<turnstile> (P \<longrightarrow> Q) \<or> (Q \<longrightarrow> P)"}}
wenzelm@42927
  1275
    {\infer[@{text "(\<longrightarrow>R)"}]{@{text "\<turnstile> (P \<longrightarrow> Q), (Q \<longrightarrow> P)"}}
wenzelm@42927
  1276
      {\infer[@{text "(\<longrightarrow>R)"}]{@{text "P \<turnstile> Q, (Q \<longrightarrow> P)"}}
wenzelm@42927
  1277
        {@{text "P, Q \<turnstile> Q, P"}}}}
wenzelm@42927
  1278
  \]
wenzelm@42927
  1279
wenzelm@42927
  1280
  This example is typical of the sequent calculus: start with the
wenzelm@42927
  1281
  desired theorem and apply rules backwards in a fairly arbitrary
wenzelm@42927
  1282
  manner.  This yields a surprisingly effective proof procedure.
wenzelm@42927
  1283
  Quantifiers add only few complications, since Isabelle handles
wenzelm@58552
  1284
  parameters and schematic variables.  See @{cite \<open>Chapter 10\<close>
wenzelm@58618
  1285
  "paulson-ml2"} for further discussion.\<close>
wenzelm@42927
  1286
wenzelm@42927
  1287
wenzelm@58618
  1288
subsubsection \<open>Simulating sequents by natural deduction\<close>
wenzelm@42927
  1289
wenzelm@58618
  1290
text \<open>Isabelle can represent sequents directly, as in the
wenzelm@42927
  1291
  object-logic LK.  But natural deduction is easier to work with, and
wenzelm@42927
  1292
  most object-logics employ it.  Fortunately, we can simulate the
wenzelm@42927
  1293
  sequent @{text "P\<^sub>1, \<dots>, P\<^sub>m \<turnstile> Q\<^sub>1, \<dots>, Q\<^sub>n"} by the Isabelle formula
wenzelm@42927
  1294
  @{text "P\<^sub>1 \<Longrightarrow> \<dots> \<Longrightarrow> P\<^sub>m \<Longrightarrow> \<not> Q\<^sub>2 \<Longrightarrow> ... \<Longrightarrow> \<not> Q\<^sub>n \<Longrightarrow> Q\<^sub>1"} where the order of
wenzelm@42927
  1295
  the assumptions and the choice of @{text "Q\<^sub>1"} are arbitrary.
wenzelm@42927
  1296
  Elim-resolution plays a key role in simulating sequent proofs.
wenzelm@42927
  1297
wenzelm@42927
  1298
  We can easily handle reasoning on the left.  Elim-resolution with
wenzelm@42927
  1299
  the rules @{text "(\<or>E)"}, @{text "(\<bottom>E)"} and @{text "(\<exists>E)"} achieves
wenzelm@42927
  1300
  a similar effect as the corresponding sequent rules.  For the other
wenzelm@42927
  1301
  connectives, we use sequent-style elimination rules instead of
wenzelm@42927
  1302
  destruction rules such as @{text "(\<and>E1, 2)"} and @{text "(\<forall>E)"}.
wenzelm@42927
  1303
  But note that the rule @{text "(\<not>L)"} has no effect under our
wenzelm@42927
  1304
  representation of sequents!
wenzelm@42927
  1305
  \[
wenzelm@42927
  1306
  \infer[@{text "(\<not>L)"}]{@{text "\<not> P, \<Gamma> \<turnstile> \<Delta>"}}{@{text "\<Gamma> \<turnstile> \<Delta>, P"}}
wenzelm@42927
  1307
  \]
wenzelm@42927
  1308
wenzelm@42927
  1309
  What about reasoning on the right?  Introduction rules can only
wenzelm@42927
  1310
  affect the formula in the conclusion, namely @{text "Q\<^sub>1"}.  The
wenzelm@42927
  1311
  other right-side formulae are represented as negated assumptions,
wenzelm@42927
  1312
  @{text "\<not> Q\<^sub>2, \<dots>, \<not> Q\<^sub>n"}.  In order to operate on one of these, it
wenzelm@42927
  1313
  must first be exchanged with @{text "Q\<^sub>1"}.  Elim-resolution with the
wenzelm@42927
  1314
  @{text swap} rule has this effect: @{text "\<not> P \<Longrightarrow> (\<not> R \<Longrightarrow> P) \<Longrightarrow> R"}
wenzelm@42927
  1315
wenzelm@42927
  1316
  To ensure that swaps occur only when necessary, each introduction
wenzelm@42927
  1317
  rule is converted into a swapped form: it is resolved with the
wenzelm@42927
  1318
  second premise of @{text "(swap)"}.  The swapped form of @{text
wenzelm@42927
  1319
  "(\<and>I)"}, which might be called @{text "(\<not>\<and>E)"}, is
wenzelm@42927
  1320
  @{text [display] "\<not> (P \<and> Q) \<Longrightarrow> (\<not> R \<Longrightarrow> P) \<Longrightarrow> (\<not> R \<Longrightarrow> Q) \<Longrightarrow> R"}
wenzelm@42927
  1321
wenzelm@42927
  1322
  Similarly, the swapped form of @{text "(\<longrightarrow>I)"} is
wenzelm@42927
  1323
  @{text [display] "\<not> (P \<longrightarrow> Q) \<Longrightarrow> (\<not> R \<Longrightarrow> P \<Longrightarrow> Q) \<Longrightarrow> R"}
wenzelm@42927
  1324
wenzelm@42927
  1325
  Swapped introduction rules are applied using elim-resolution, which
wenzelm@42927
  1326
  deletes the negated formula.  Our representation of sequents also
wenzelm@42927
  1327
  requires the use of ordinary introduction rules.  If we had no
wenzelm@42927
  1328
  regard for readability of intermediate goal states, we could treat
wenzelm@42927
  1329
  the right side more uniformly by representing sequents as @{text
wenzelm@42927
  1330
  [display] "P\<^sub>1 \<Longrightarrow> \<dots> \<Longrightarrow> P\<^sub>m \<Longrightarrow> \<not> Q\<^sub>1 \<Longrightarrow> \<dots> \<Longrightarrow> \<not> Q\<^sub>n \<Longrightarrow> \<bottom>"}
wenzelm@58618
  1331
\<close>
wenzelm@42927
  1332
wenzelm@42927
  1333
wenzelm@58618
  1334
subsubsection \<open>Extra rules for the sequent calculus\<close>
wenzelm@42927
  1335
wenzelm@58618
  1336
text \<open>As mentioned, destruction rules such as @{text "(\<and>E1, 2)"} and
wenzelm@42927
  1337
  @{text "(\<forall>E)"} must be replaced by sequent-style elimination rules.
wenzelm@42927
  1338
  In addition, we need rules to embody the classical equivalence
wenzelm@42927
  1339
  between @{text "P \<longrightarrow> Q"} and @{text "\<not> P \<or> Q"}.  The introduction
wenzelm@42927
  1340
  rules @{text "(\<or>I1, 2)"} are replaced by a rule that simulates
wenzelm@42927
  1341
  @{text "(\<or>R)"}: @{text [display] "(\<not> Q \<Longrightarrow> P) \<Longrightarrow> P \<or> Q"}
wenzelm@42927
  1342
wenzelm@42927
  1343
  The destruction rule @{text "(\<longrightarrow>E)"} is replaced by @{text [display]
wenzelm@42927
  1344
  "(P \<longrightarrow> Q) \<Longrightarrow> (\<not> P \<Longrightarrow> R) \<Longrightarrow> (Q \<Longrightarrow> R) \<Longrightarrow> R"}
wenzelm@42927
  1345
wenzelm@42927
  1346
  Quantifier replication also requires special rules.  In classical
wenzelm@42927
  1347
  logic, @{text "\<exists>x. P x"} is equivalent to @{text "\<not> (\<forall>x. \<not> P x)"};
wenzelm@42927
  1348
  the rules @{text "(\<exists>R)"} and @{text "(\<forall>L)"} are dual:
wenzelm@42927
  1349
  \[
wenzelm@42927
  1350
  \infer[@{text "(\<exists>R)"}]{@{text "\<Gamma> \<turnstile> \<Delta>, \<exists>x. P x"}}{@{text "\<Gamma> \<turnstile> \<Delta>, \<exists>x. P x, P t"}}
wenzelm@42927
  1351
  \qquad
wenzelm@42927
  1352
  \infer[@{text "(\<forall>L)"}]{@{text "\<forall>x. P x, \<Gamma> \<turnstile> \<Delta>"}}{@{text "P t, \<forall>x. P x, \<Gamma> \<turnstile> \<Delta>"}}
wenzelm@42927
  1353
  \]
wenzelm@42927
  1354
  Thus both kinds of quantifier may be replicated.  Theorems requiring
wenzelm@42927
  1355
  multiple uses of a universal formula are easy to invent; consider
wenzelm@42927
  1356
  @{text [display] "(\<forall>x. P x \<longrightarrow> P (f x)) \<and> P a \<longrightarrow> P (f\<^sup>n a)"} for any
wenzelm@42927
  1357
  @{text "n > 1"}.  Natural examples of the multiple use of an
wenzelm@42927
  1358
  existential formula are rare; a standard one is @{text "\<exists>x. \<forall>y. P x
wenzelm@42927
  1359
  \<longrightarrow> P y"}.
wenzelm@42927
  1360
wenzelm@42927
  1361
  Forgoing quantifier replication loses completeness, but gains
wenzelm@42927
  1362
  decidability, since the search space becomes finite.  Many useful
wenzelm@42927
  1363
  theorems can be proved without replication, and the search generally
wenzelm@42927
  1364
  delivers its verdict in a reasonable time.  To adopt this approach,
wenzelm@42927
  1365
  represent the sequent rules @{text "(\<exists>R)"}, @{text "(\<exists>L)"} and
wenzelm@42927
  1366
  @{text "(\<forall>R)"} by @{text "(\<exists>I)"}, @{text "(\<exists>E)"} and @{text "(\<forall>I)"},
wenzelm@42927
  1367
  respectively, and put @{text "(\<forall>E)"} into elimination form: @{text
wenzelm@42927
  1368
  [display] "\<forall>x. P x \<Longrightarrow> (P t \<Longrightarrow> Q) \<Longrightarrow> Q"}
wenzelm@42927
  1369
wenzelm@42927
  1370
  Elim-resolution with this rule will delete the universal formula
wenzelm@42927
  1371
  after a single use.  To replicate universal quantifiers, replace the
wenzelm@42927
  1372
  rule by @{text [display] "\<forall>x. P x \<Longrightarrow> (P t \<Longrightarrow> \<forall>x. P x \<Longrightarrow> Q) \<Longrightarrow> Q"}
wenzelm@42927
  1373
wenzelm@42927
  1374
  To replicate existential quantifiers, replace @{text "(\<exists>I)"} by
wenzelm@42927
  1375
  @{text [display] "(\<not> (\<exists>x. P x) \<Longrightarrow> P t) \<Longrightarrow> \<exists>x. P x"}
wenzelm@42927
  1376
wenzelm@42927
  1377
  All introduction rules mentioned above are also useful in swapped
wenzelm@42927
  1378
  form.
wenzelm@42927
  1379
wenzelm@42927
  1380
  Replication makes the search space infinite; we must apply the rules
wenzelm@42927
  1381
  with care.  The classical reasoner distinguishes between safe and
wenzelm@42927
  1382
  unsafe rules, applying the latter only when there is no alternative.
wenzelm@42927
  1383
  Depth-first search may well go down a blind alley; best-first search
wenzelm@42927
  1384
  is better behaved in an infinite search space.  However, quantifier
wenzelm@42927
  1385
  replication is too expensive to prove any but the simplest theorems.
wenzelm@58618
  1386
\<close>
wenzelm@42927
  1387
wenzelm@42927
  1388
wenzelm@58618
  1389
subsection \<open>Rule declarations\<close>
wenzelm@42928
  1390
wenzelm@58618
  1391
text \<open>The proof tools of the Classical Reasoner depend on
wenzelm@42928
  1392
  collections of rules declared in the context, which are classified
wenzelm@42928
  1393
  as introduction, elimination or destruction and as \emph{safe} or
wenzelm@42928
  1394
  \emph{unsafe}.  In general, safe rules can be attempted blindly,
wenzelm@42928
  1395
  while unsafe rules must be used with care.  A safe rule must never
wenzelm@42928
  1396
  reduce a provable goal to an unprovable set of subgoals.
wenzelm@42928
  1397
wenzelm@42928
  1398
  The rule @{text "P \<Longrightarrow> P \<or> Q"} is unsafe because it reduces @{text "P
wenzelm@42928
  1399
  \<or> Q"} to @{text "P"}, which might turn out as premature choice of an
wenzelm@42928
  1400
  unprovable subgoal.  Any rule is unsafe whose premises contain new
wenzelm@42928
  1401
  unknowns.  The elimination rule @{text "\<forall>x. P x \<Longrightarrow> (P t \<Longrightarrow> Q) \<Longrightarrow> Q"} is
wenzelm@42928
  1402
  unsafe, since it is applied via elim-resolution, which discards the
wenzelm@42928
  1403
  assumption @{text "\<forall>x. P x"} and replaces it by the weaker
wenzelm@42928
  1404
  assumption @{text "P t"}.  The rule @{text "P t \<Longrightarrow> \<exists>x. P x"} is
wenzelm@42928
  1405
  unsafe for similar reasons.  The quantifier duplication rule @{text
wenzelm@42928
  1406
  "\<forall>x. P x \<Longrightarrow> (P t \<Longrightarrow> \<forall>x. P x \<Longrightarrow> Q) \<Longrightarrow> Q"} is unsafe in a different sense:
wenzelm@42928
  1407
  since it keeps the assumption @{text "\<forall>x. P x"}, it is prone to
wenzelm@42928
  1408
  looping.  In classical first-order logic, all rules are safe except
wenzelm@42928
  1409
  those mentioned above.
wenzelm@42928
  1410
wenzelm@42928
  1411
  The safe~/ unsafe distinction is vague, and may be regarded merely
wenzelm@42928
  1412
  as a way of giving some rules priority over others.  One could argue
wenzelm@42928
  1413
  that @{text "(\<or>E)"} is unsafe, because repeated application of it
wenzelm@42928
  1414
  could generate exponentially many subgoals.  Induction rules are
wenzelm@42928
  1415
  unsafe because inductive proofs are difficult to set up
wenzelm@42928
  1416
  automatically.  Any inference is unsafe that instantiates an unknown
wenzelm@42928
  1417
  in the proof state --- thus matching must be used, rather than
wenzelm@42928
  1418
  unification.  Even proof by assumption is unsafe if it instantiates
wenzelm@42928
  1419
  unknowns shared with other subgoals.
wenzelm@42928
  1420
wenzelm@42928
  1421
  \begin{matharray}{rcl}
wenzelm@42928
  1422
    @{command_def "print_claset"}@{text "\<^sup>*"} & : & @{text "context \<rightarrow>"} \\
wenzelm@42928
  1423
    @{attribute_def intro} & : & @{text attribute} \\
wenzelm@42928
  1424
    @{attribute_def elim} & : & @{text attribute} \\
wenzelm@42928
  1425
    @{attribute_def dest} & : & @{text attribute} \\
wenzelm@42928
  1426
    @{attribute_def rule} & : & @{text attribute} \\
wenzelm@42928
  1427
    @{attribute_def iff} & : & @{text attribute} \\
wenzelm@42928
  1428
    @{attribute_def swapped} & : & @{text attribute} \\
wenzelm@42928
  1429
  \end{matharray}
wenzelm@42928
  1430
wenzelm@55112
  1431
  @{rail \<open>
wenzelm@42928
  1432
    (@@{attribute intro} | @@{attribute elim} | @@{attribute dest}) ('!' | () | '?') @{syntax nat}?
wenzelm@42928
  1433
    ;
wenzelm@42928
  1434
    @@{attribute rule} 'del'
wenzelm@42928
  1435
    ;
wenzelm@42928
  1436
    @@{attribute iff} (((() | 'add') '?'?) | 'del')
wenzelm@55112
  1437
  \<close>}
wenzelm@42928
  1438
wenzelm@42928
  1439
  \begin{description}
wenzelm@42928
  1440
wenzelm@42928
  1441
  \item @{command "print_claset"} prints the collection of rules
wenzelm@42928
  1442
  declared to the Classical Reasoner, i.e.\ the @{ML_type claset}
wenzelm@42928
  1443
  within the context.
wenzelm@42928
  1444
wenzelm@42928
  1445
  \item @{attribute intro}, @{attribute elim}, and @{attribute dest}
wenzelm@42928
  1446
  declare introduction, elimination, and destruction rules,
wenzelm@42928
  1447
  respectively.  By default, rules are considered as \emph{unsafe}
wenzelm@42928
  1448
  (i.e.\ not applied blindly without backtracking), while ``@{text
wenzelm@42928
  1449
  "!"}'' classifies as \emph{safe}.  Rule declarations marked by
wenzelm@42928
  1450
  ``@{text "?"}'' coincide with those of Isabelle/Pure, cf.\
wenzelm@42928
  1451
  \secref{sec:pure-meth-att} (i.e.\ are only applied in single steps
wenzelm@42928
  1452
  of the @{method rule} method).  The optional natural number
wenzelm@42928
  1453
  specifies an explicit weight argument, which is ignored by the
wenzelm@42928
  1454
  automated reasoning tools, but determines the search order of single
wenzelm@42928
  1455
  rule steps.
wenzelm@42928
  1456
wenzelm@42928
  1457
  Introduction rules are those that can be applied using ordinary
wenzelm@42928
  1458
  resolution.  Their swapped forms are generated internally, which
wenzelm@42928
  1459
  will be applied using elim-resolution.  Elimination rules are
wenzelm@42928
  1460
  applied using elim-resolution.  Rules are sorted by the number of
wenzelm@42928
  1461
  new subgoals they will yield; rules that generate the fewest
wenzelm@42928
  1462
  subgoals will be tried first.  Otherwise, later declarations take
wenzelm@42928
  1463
  precedence over earlier ones.
wenzelm@42928
  1464
wenzelm@42928
  1465
  Rules already present in the context with the same classification
wenzelm@42928
  1466
  are ignored.  A warning is printed if the rule has already been
wenzelm@42928
  1467
  added with some other classification, but the rule is added anyway
wenzelm@42928
  1468
  as requested.
wenzelm@42928
  1469
wenzelm@42928
  1470
  \item @{attribute rule}~@{text del} deletes all occurrences of a
wenzelm@42928
  1471
  rule from the classical context, regardless of its classification as
wenzelm@42928
  1472
  introduction~/ elimination~/ destruction and safe~/ unsafe.
wenzelm@42928
  1473
wenzelm@42928
  1474
  \item @{attribute iff} declares logical equivalences to the
wenzelm@42928
  1475
  Simplifier and the Classical reasoner at the same time.
wenzelm@42928
  1476
  Non-conditional rules result in a safe introduction and elimination
wenzelm@42928
  1477
  pair; conditional ones are considered unsafe.  Rules with negative
wenzelm@42928
  1478
  conclusion are automatically inverted (using @{text "\<not>"}-elimination
wenzelm@42928
  1479
  internally).
wenzelm@42928
  1480
wenzelm@42928
  1481
  The ``@{text "?"}'' version of @{attribute iff} declares rules to
wenzelm@42928
  1482
  the Isabelle/Pure context only, and omits the Simplifier
wenzelm@42928
  1483
  declaration.
wenzelm@42928
  1484
wenzelm@42928
  1485
  \item @{attribute swapped} turns an introduction rule into an
wenzelm@42928
  1486
  elimination, by resolving with the classical swap principle @{text
wenzelm@42928
  1487
  "\<not> P \<Longrightarrow> (\<not> R \<Longrightarrow> P) \<Longrightarrow> R"} in the second position.  This is mainly for
wenzelm@42928
  1488
  illustrative purposes: the Classical Reasoner already swaps rules
wenzelm@42928
  1489
  internally as explained above.
wenzelm@42928
  1490
wenzelm@28760
  1491
  \end{description}
wenzelm@58618
  1492
\<close>
wenzelm@26782
  1493
wenzelm@26782
  1494
wenzelm@58618
  1495
subsection \<open>Structured methods\<close>
wenzelm@43365
  1496
wenzelm@58618
  1497
text \<open>
wenzelm@43365
  1498
  \begin{matharray}{rcl}
wenzelm@43365
  1499
    @{method_def rule} & : & @{text method} \\
wenzelm@43365
  1500
    @{method_def contradiction} & : & @{text method} \\
wenzelm@43365
  1501
  \end{matharray}
wenzelm@43365
  1502
wenzelm@55112
  1503
  @{rail \<open>
wenzelm@43365
  1504
    @@{method rule} @{syntax thmrefs}?
wenzelm@55112
  1505
  \<close>}
wenzelm@43365
  1506
wenzelm@43365
  1507
  \begin{description}
wenzelm@43365
  1508
wenzelm@43365
  1509
  \item @{method rule} as offered by the Classical Reasoner is a
wenzelm@43365
  1510
  refinement over the Pure one (see \secref{sec:pure-meth-att}).  Both
wenzelm@43365
  1511
  versions work the same, but the classical version observes the
wenzelm@43365
  1512
  classical rule context in addition to that of Isabelle/Pure.
wenzelm@43365
  1513
wenzelm@43365
  1514
  Common object logics (HOL, ZF, etc.) declare a rich collection of
wenzelm@43365
  1515
  classical rules (even if these would qualify as intuitionistic
wenzelm@43365
  1516
  ones), but only few declarations to the rule context of
wenzelm@43365
  1517
  Isabelle/Pure (\secref{sec:pure-meth-att}).
wenzelm@43365
  1518
wenzelm@43365
  1519
  \item @{method contradiction} solves some goal by contradiction,
wenzelm@43365
  1520
  deriving any result from both @{text "\<not> A"} and @{text A}.  Chained
wenzelm@43365
  1521
  facts, which are guaranteed to participate, may appear in either
wenzelm@43365
  1522
  order.
wenzelm@43365
  1523
wenzelm@43365
  1524
  \end{description}
wenzelm@58618
  1525
\<close>
wenzelm@43365
  1526
wenzelm@43365
  1527
wenzelm@58618
  1528
subsection \<open>Fully automated methods\<close>
wenzelm@26782
  1529
wenzelm@58618
  1530
text \<open>
wenzelm@26782
  1531
  \begin{matharray}{rcl}
wenzelm@28761
  1532
    @{method_def blast} & : & @{text method} \\
wenzelm@42930
  1533
    @{method_def auto} & : & @{text method} \\
wenzelm@42930
  1534
    @{method_def force} & : & @{text method} \\
wenzelm@28761
  1535
    @{method_def fast} & : & @{text method} \\
wenzelm@28761
  1536
    @{method_def slow} & : & @{text method} \\
wenzelm@28761
  1537
    @{method_def best} & : & @{text method} \\
nipkow@44911
  1538
    @{method_def fastforce} & : & @{text method} \\
wenzelm@28761
  1539
    @{method_def slowsimp} & : & @{text method} \\
wenzelm@28761
  1540
    @{method_def bestsimp} & : & @{text method} \\
wenzelm@43367
  1541
    @{method_def deepen} & : & @{text method} \\
wenzelm@26782
  1542
  \end{matharray}
wenzelm@26782
  1543
wenzelm@55112
  1544
  @{rail \<open>
wenzelm@42930
  1545
    @@{method blast} @{syntax nat}? (@{syntax clamod} * )
wenzelm@42930
  1546
    ;
wenzelm@42596
  1547
    @@{method auto} (@{syntax nat} @{syntax nat})? (@{syntax clasimpmod} * )
wenzelm@26782
  1548
    ;
wenzelm@42930
  1549
    @@{method force} (@{syntax clasimpmod} * )
wenzelm@42930
  1550
    ;
wenzelm@42930
  1551
    (@@{method fast} | @@{method slow} | @@{method best}) (@{syntax clamod} * )
wenzelm@26782
  1552
    ;
nipkow@44911
  1553
    (@@{method fastforce} | @@{method slowsimp} | @@{method bestsimp})
wenzelm@42930
  1554
      (@{syntax clasimpmod} * )
wenzelm@42930
  1555
    ;
wenzelm@43367
  1556
    @@{method deepen} (@{syntax nat} ?) (@{syntax clamod} * )
wenzelm@43367
  1557
    ;
wenzelm@42930
  1558
    @{syntax_def clamod}:
wenzelm@42930
  1559
      (('intro' | 'elim' | 'dest') ('!' | () | '?') | 'del') ':' @{syntax thmrefs}
wenzelm@42930
  1560
    ;
wenzelm@42596
  1561
    @{syntax_def clasimpmod}: ('simp' (() | 'add' | 'del' | 'only') |
wenzelm@26782
  1562
      ('cong' | 'split') (() | 'add' | 'del') |
wenzelm@26782
  1563
      'iff' (((() | 'add') '?'?) | 'del') |
wenzelm@42596
  1564
      (('intro' | 'elim' | 'dest') ('!' | () | '?') | 'del')) ':' @{syntax thmrefs}
wenzelm@55112
  1565
  \<close>}
wenzelm@26782
  1566
wenzelm@28760
  1567
  \begin{description}
wenzelm@26782
  1568
wenzelm@42930
  1569
  \item @{method blast} is a separate classical tableau prover that
wenzelm@42930
  1570
  uses the same classical rule declarations as explained before.
wenzelm@42930
  1571
wenzelm@42930
  1572
  Proof search is coded directly in ML using special data structures.
wenzelm@42930
  1573
  A successful proof is then reconstructed using regular Isabelle
wenzelm@42930
  1574
  inferences.  It is faster and more powerful than the other classical
wenzelm@42930
  1575
  reasoning tools, but has major limitations too.
wenzelm@42930
  1576
wenzelm@42930
  1577
  \begin{itemize}
wenzelm@42930
  1578
wenzelm@61421
  1579
  \<^item> It does not use the classical wrapper tacticals, such as the
nipkow@44911
  1580
  integration with the Simplifier of @{method fastforce}.
wenzelm@42930
  1581
wenzelm@61421
  1582
  \<^item> It does not perform higher-order unification, as needed by the
wenzelm@42930
  1583
  rule @{thm [source=false] rangeI} in HOL.  There are often
wenzelm@42930
  1584
  alternatives to such rules, for example @{thm [source=false]
wenzelm@42930
  1585
  range_eqI}.
wenzelm@42930
  1586
wenzelm@61421
  1587
  \<^item> Function variables may only be applied to parameters of the
wenzelm@42930
  1588
  subgoal.  (This restriction arises because the prover does not use
wenzelm@42930
  1589
  higher-order unification.)  If other function variables are present
wenzelm@61413
  1590
  then the prover will fail with the message
wenzelm@61413
  1591
  @{verbatim [display] \<open>Function unknown's argument not a bound variable\<close>}
wenzelm@42930
  1592
wenzelm@61421
  1593
  \<^item> Its proof strategy is more general than @{method fast} but can
wenzelm@42930
  1594
  be slower.  If @{method blast} fails or seems to be running forever,
wenzelm@42930
  1595
  try @{method fast} and the other proof tools described below.
wenzelm@42930
  1596
wenzelm@42930
  1597
  \end{itemize}
wenzelm@42930
  1598
wenzelm@42930
  1599
  The optional integer argument specifies a bound for the number of
wenzelm@42930
  1600
  unsafe steps used in a proof.  By default, @{method blast} starts
wenzelm@42930
  1601
  with a bound of 0 and increases it successively to 20.  In contrast,
wenzelm@42930
  1602
  @{text "(blast lim)"} tries to prove the goal using a search bound
wenzelm@42930
  1603
  of @{text "lim"}.  Sometimes a slow proof using @{method blast} can
wenzelm@42930
  1604
  be made much faster by supplying the successful search bound to this
wenzelm@42930
  1605
  proof method instead.
wenzelm@42930
  1606
wenzelm@42930
  1607
  \item @{method auto} combines classical reasoning with
wenzelm@42930
  1608
  simplification.  It is intended for situations where there are a lot
wenzelm@42930
  1609
  of mostly trivial subgoals; it proves all the easy ones, leaving the
wenzelm@42930
  1610
  ones it cannot prove.  Occasionally, attempting to prove the hard
wenzelm@42930
  1611
  ones may take a long time.
wenzelm@42930
  1612
wenzelm@43332
  1613
  The optional depth arguments in @{text "(auto m n)"} refer to its
wenzelm@43332
  1614
  builtin classical reasoning procedures: @{text m} (default 4) is for
wenzelm@43332
  1615
  @{method blast}, which is tried first, and @{text n} (default 2) is
wenzelm@43332
  1616
  for a slower but more general alternative that also takes wrappers
wenzelm@43332
  1617
  into account.
wenzelm@42930
  1618
wenzelm@42930
  1619
  \item @{method force} is intended to prove the first subgoal
wenzelm@42930
  1620
  completely, using many fancy proof tools and performing a rather
wenzelm@42930
  1621
  exhaustive search.  As a result, proof attempts may take rather long
wenzelm@42930
  1622
  or diverge easily.
wenzelm@42930
  1623
wenzelm@42930
  1624
  \item @{method fast}, @{method best}, @{method slow} attempt to
wenzelm@42930
  1625
  prove the first subgoal using sequent-style reasoning as explained
wenzelm@42930
  1626
  before.  Unlike @{method blast}, they construct proofs directly in
wenzelm@42930
  1627
  Isabelle.
wenzelm@26782
  1628
wenzelm@42930
  1629
  There is a difference in search strategy and back-tracking: @{method
wenzelm@42930
  1630
  fast} uses depth-first search and @{method best} uses best-first
wenzelm@42930
  1631
  search (guided by a heuristic function: normally the total size of
wenzelm@42930
  1632
  the proof state).
wenzelm@42930
  1633
wenzelm@42930
  1634
  Method @{method slow} is like @{method fast}, but conducts a broader
wenzelm@42930
  1635
  search: it may, when backtracking from a failed proof attempt, undo
wenzelm@42930
  1636
  even the step of proving a subgoal by assumption.
wenzelm@42930
  1637
wenzelm@47967
  1638
  \item @{method fastforce}, @{method slowsimp}, @{method bestsimp}
wenzelm@47967
  1639
  are like @{method fast}, @{method slow}, @{method best},
wenzelm@47967
  1640
  respectively, but use the Simplifier as additional wrapper. The name
wenzelm@47967
  1641
  @{method fastforce}, reflects the behaviour of this popular method
wenzelm@47967
  1642
  better without requiring an understanding of its implementation.
wenzelm@42930
  1643
wenzelm@43367
  1644
  \item @{method deepen} works by exhaustive search up to a certain
wenzelm@43367
  1645
  depth.  The start depth is 4 (unless specified explicitly), and the
wenzelm@43367
  1646
  depth is increased iteratively up to 10.  Unsafe rules are modified
wenzelm@43367
  1647
  to preserve the formula they act on, so that it be used repeatedly.
wenzelm@43367
  1648
  This method can prove more goals than @{method fast}, but is much
wenzelm@43367
  1649
  slower, for example if the assumptions have many universal
wenzelm@43367
  1650
  quantifiers.
wenzelm@43367
  1651
wenzelm@42930
  1652
  \end{description}
wenzelm@42930
  1653
wenzelm@42930
  1654
  Any of the above methods support additional modifiers of the context
wenzelm@42930
  1655
  of classical (and simplifier) rules, but the ones related to the
wenzelm@42930
  1656
  Simplifier are explicitly prefixed by @{text simp} here.  The
wenzelm@42930
  1657
  semantics of these ad-hoc rule declarations is analogous to the
wenzelm@42930
  1658
  attributes given before.  Facts provided by forward chaining are
wenzelm@42930
  1659
  inserted into the goal before commencing proof search.
wenzelm@58618
  1660
\<close>
wenzelm@42930
  1661
wenzelm@42930
  1662
wenzelm@58618
  1663
subsection \<open>Partially automated methods\<close>
wenzelm@42930
  1664
wenzelm@58618
  1665
text \<open>These proof methods may help in situations when the
wenzelm@42930
  1666
  fully-automated tools fail.  The result is a simpler subgoal that
wenzelm@42930
  1667
  can be tackled by other means, such as by manual instantiation of
wenzelm@42930
  1668
  quantifiers.
wenzelm@42930
  1669
wenzelm@42930
  1670
  \begin{matharray}{rcl}
wenzelm@42930
  1671
    @{method_def safe} & : & @{text method} \\
wenzelm@42930
  1672
    @{method_def clarify} & : & @{text method} \\
wenzelm@42930
  1673
    @{method_def clarsimp} & : & @{text method} \\
wenzelm@42930
  1674
  \end{matharray}
wenzelm@42930
  1675
wenzelm@55112
  1676
  @{rail \<open>
wenzelm@42930
  1677
    (@@{method safe} | @@{method clarify}) (@{syntax clamod} * )
wenzelm@42930
  1678
    ;
wenzelm@42930
  1679
    @@{method clarsimp} (@{syntax clasimpmod} * )
wenzelm@55112
  1680
  \<close>}
wenzelm@42930
  1681
wenzelm@42930
  1682
  \begin{description}
wenzelm@42930
  1683
wenzelm@42930
  1684
  \item @{method safe} repeatedly performs safe steps on all subgoals.
wenzelm@42930
  1685
  It is deterministic, with at most one outcome.
wenzelm@42930
  1686
wenzelm@43366
  1687
  \item @{method clarify} performs a series of safe steps without
wenzelm@50108
  1688
  splitting subgoals; see also @{method clarify_step}.
wenzelm@42930
  1689
wenzelm@42930
  1690
  \item @{method clarsimp} acts like @{method clarify}, but also does
wenzelm@42930
  1691
  simplification.  Note that if the Simplifier context includes a
wenzelm@42930
  1692
  splitter for the premises, the subgoal may still be split.
wenzelm@26782
  1693
wenzelm@28760
  1694
  \end{description}
wenzelm@58618
  1695
\<close>
wenzelm@26782
  1696
wenzelm@26782
  1697
wenzelm@58618
  1698
subsection \<open>Single-step tactics\<close>
wenzelm@43366
  1699
wenzelm@58618
  1700
text \<open>
wenzelm@50108
  1701
  \begin{matharray}{rcl}
wenzelm@50108
  1702
    @{method_def safe_step} & : & @{text method} \\
wenzelm@50108
  1703
    @{method_def inst_step} & : & @{text method} \\
wenzelm@50108
  1704
    @{method_def step} & : & @{text method} \\
wenzelm@50108
  1705
    @{method_def slow_step} & : & @{text method} \\
wenzelm@50108
  1706
    @{method_def clarify_step} & : &  @{text method} \\
wenzelm@50108
  1707
  \end{matharray}
wenzelm@43366
  1708
wenzelm@50070
  1709
  These are the primitive tactics behind the automated proof methods
wenzelm@50070
  1710
  of the Classical Reasoner.  By calling them yourself, you can
wenzelm@50070
  1711
  execute these procedures one step at a time.
wenzelm@43366
  1712
wenzelm@43366
  1713
  \begin{description}
wenzelm@43366
  1714
wenzelm@50108
  1715
  \item @{method safe_step} performs a safe step on the first subgoal.
wenzelm@50108
  1716
  The safe wrapper tacticals are applied to a tactic that may include
wenzelm@50108
  1717
  proof by assumption or Modus Ponens (taking care not to instantiate
wenzelm@50108
  1718
  unknowns), or substitution.
wenzelm@43366
  1719
wenzelm@50108
  1720
  \item @{method inst_step} is like @{method safe_step}, but allows
wenzelm@43366
  1721
  unknowns to be instantiated.
wenzelm@43366
  1722
wenzelm@50108
  1723
  \item @{method step} is the basic step of the proof procedure, it
wenzelm@50108
  1724
  operates on the first subgoal.  The unsafe wrapper tacticals are
wenzelm@50108
  1725
  applied to a tactic that tries @{method safe}, @{method inst_step},
wenzelm@50108
  1726
  or applies an unsafe rule from the context.
wenzelm@43366
  1727
wenzelm@50108
  1728
  \item @{method slow_step} resembles @{method step}, but allows
wenzelm@50108
  1729
  backtracking between using safe rules with instantiation (@{method
wenzelm@50108
  1730
  inst_step}) and using unsafe rules.  The resulting search space is
wenzelm@50108
  1731
  larger.
wenzelm@43366
  1732
wenzelm@50108
  1733
  \item @{method clarify_step} performs a safe step on the first
wenzelm@50108
  1734
  subgoal; no splitting step is applied.  For example, the subgoal
wenzelm@50108
  1735
  @{text "A \<and> B"} is left as a conjunction.  Proof by assumption,
wenzelm@50108
  1736
  Modus Ponens, etc., may be performed provided they do not
wenzelm@50108
  1737
  instantiate unknowns.  Assumptions of the form @{text "x = t"} may
wenzelm@50108
  1738
  be eliminated.  The safe wrapper tactical is applied.
wenzelm@43366
  1739
wenzelm@43366
  1740
  \end{description}
wenzelm@58618
  1741
\<close>
wenzelm@43366
  1742
wenzelm@43366
  1743
wenzelm@58618
  1744
subsection \<open>Modifying the search step\<close>
wenzelm@50071
  1745
wenzelm@58618
  1746
text \<open>
wenzelm@50071
  1747
  \begin{mldecls}
wenzelm@50071
  1748
    @{index_ML_type wrapper: "(int -> tactic) -> (int -> tactic)"} \\[0.5ex]
wenzelm@51703
  1749
    @{index_ML_op addSWrapper: "Proof.context *
wenzelm@51703
  1750
  (string * (Proof.context -> wrapper)) -> Proof.context"} \\
wenzelm@51703
  1751
    @{index_ML_op addSbefore: "Proof.context *
wenzelm@51717
  1752
  (string * (Proof.context -> int -> tactic)) -> Proof.context"} \\
wenzelm@51703
  1753
    @{index_ML_op addSafter: "Proof.context *
wenzelm@51717
  1754
  (string * (Proof.context -> int -> tactic)) -> Proof.context"} \\
wenzelm@51703
  1755
    @{index_ML_op delSWrapper: "Proof.context * string -> Proof.context"} \\[0.5ex]
wenzelm@51703
  1756
    @{index_ML_op addWrapper: "Proof.context *
wenzelm@51703
  1757
  (string * (Proof.context -> wrapper)) -> Proof.context"} \\
wenzelm@51703
  1758
    @{index_ML_op addbefore: "Proof.context *
wenzelm@51717
  1759
  (string * (Proof.context -> int -> tactic)) -> Proof.context"} \\
wenzelm@51703
  1760
    @{index_ML_op addafter: "Proof.context *
wenzelm@51717
  1761
  (string * (Proof.context -> int -> tactic)) -> Proof.context"} \\
wenzelm@51703
  1762
    @{index_ML_op delWrapper: "Proof.context * string -> Proof.context"} \\[0.5ex]
wenzelm@50071
  1763
    @{index_ML addSss: "Proof.context -> Proof.context"} \\
wenzelm@50071
  1764
    @{index_ML addss: "Proof.context -> Proof.context"} \\
wenzelm@50071
  1765
  \end{mldecls}
wenzelm@50071
  1766
wenzelm@50071
  1767
  The proof strategy of the Classical Reasoner is simple.  Perform as
wenzelm@50071
  1768
  many safe inferences as possible; or else, apply certain safe rules,
wenzelm@50071
  1769
  allowing instantiation of unknowns; or else, apply an unsafe rule.
wenzelm@50071
  1770
  The tactics also eliminate assumptions of the form @{text "x = t"}
wenzelm@50071
  1771
  by substitution if they have been set up to do so.  They may perform
wenzelm@50071
  1772
  a form of Modus Ponens: if there are assumptions @{text "P \<longrightarrow> Q"} and
wenzelm@50071
  1773
  @{text "P"}, then replace @{text "P \<longrightarrow> Q"} by @{text "Q"}.
wenzelm@50071
  1774
wenzelm@50071
  1775
  The classical reasoning tools --- except @{method blast} --- allow
wenzelm@50071
  1776
  to modify this basic proof strategy by applying two lists of
wenzelm@50071
  1777
  arbitrary \emph{wrapper tacticals} to it.  The first wrapper list,
wenzelm@50108
  1778
  which is considered to contain safe wrappers only, affects @{method
wenzelm@50108
  1779
  safe_step} and all the tactics that call it.  The second one, which
wenzelm@50108
  1780
  may contain unsafe wrappers, affects the unsafe parts of @{method
wenzelm@50108
  1781
  step}, @{method slow_step}, and the tactics that call them.  A
wenzelm@50071
  1782
  wrapper transforms each step of the search, for example by
wenzelm@50071
  1783
  attempting other tactics before or after the original step tactic.
wenzelm@50071
  1784
  All members of a wrapper list are applied in turn to the respective
wenzelm@50071
  1785
  step tactic.
wenzelm@50071
  1786
wenzelm@50071
  1787
  Initially the two wrapper lists are empty, which means no
wenzelm@50071
  1788
  modification of the step tactics. Safe and unsafe wrappers are added
wenzelm@59905
  1789
  to the context with the functions given below, supplying them with
wenzelm@50071
  1790
  wrapper names.  These names may be used to selectively delete
wenzelm@50071
  1791
  wrappers.
wenzelm@50071
  1792
wenzelm@50071
  1793
  \begin{description}
wenzelm@50071
  1794
wenzelm@51703
  1795
  \item @{text "ctxt addSWrapper (name, wrapper)"} adds a new wrapper,
wenzelm@50071
  1796
  which should yield a safe tactic, to modify the existing safe step
wenzelm@50071
  1797
  tactic.
wenzelm@50071
  1798
wenzelm@51703
  1799
  \item @{text "ctxt addSbefore (name, tac)"} adds the given tactic as a
wenzelm@50071
  1800
  safe wrapper, such that it is tried \emph{before} each safe step of
wenzelm@50071
  1801
  the search.
wenzelm@50071
  1802
wenzelm@51703
  1803
  \item @{text "ctxt addSafter (name, tac)"} adds the given tactic as a
wenzelm@50071
  1804
  safe wrapper, such that it is tried when a safe step of the search
wenzelm@50071
  1805
  would fail.
wenzelm@50071
  1806
wenzelm@51703
  1807
  \item @{text "ctxt delSWrapper name"} deletes the safe wrapper with
wenzelm@50071
  1808
  the given name.
wenzelm@50071
  1809
wenzelm@51703
  1810
  \item @{text "ctxt addWrapper (name, wrapper)"} adds a new wrapper to
wenzelm@50071
  1811
  modify the existing (unsafe) step tactic.
wenzelm@50071
  1812
wenzelm@51703
  1813
  \item @{text "ctxt addbefore (name, tac)"} adds the given tactic as an
wenzelm@50071
  1814
  unsafe wrapper, such that it its result is concatenated
wenzelm@50071
  1815
  \emph{before} the result of each unsafe step.
wenzelm@50071
  1816
wenzelm@51703
  1817
  \item @{text "ctxt addafter (name, tac)"} adds the given tactic as an
wenzelm@50071
  1818
  unsafe wrapper, such that it its result is concatenated \emph{after}
wenzelm@50071
  1819
  the result of each unsafe step.
wenzelm@50071
  1820
wenzelm@51703
  1821
  \item @{text "ctxt delWrapper name"} deletes the unsafe wrapper with
wenzelm@50071
  1822
  the given name.
wenzelm@50071
  1823
wenzelm@50071
  1824
  \item @{text "addSss"} adds the simpset of the context to its
wenzelm@50071
  1825
  classical set. The assumptions and goal will be simplified, in a
wenzelm@50071
  1826
  rather safe way, after each safe step of the search.
wenzelm@50071
  1827
wenzelm@50071
  1828
  \item @{text "addss"} adds the simpset of the context to its
wenzelm@50071
  1829
  classical set. The assumptions and goal will be simplified, before
wenzelm@50071
  1830
  the each unsafe step of the search.
wenzelm@50071
  1831
wenzelm@50071
  1832
  \end{description}
wenzelm@58618
  1833
\<close>
wenzelm@50071
  1834
wenzelm@50071
  1835
wenzelm@58618
  1836
section \<open>Object-logic setup \label{sec:object-logic}\<close>
wenzelm@26790
  1837
wenzelm@58618
  1838
text \<open>
wenzelm@26790
  1839
  \begin{matharray}{rcl}
wenzelm@28761
  1840
    @{command_def "judgment"} & : & @{text "theory \<rightarrow> theory"} \\
wenzelm@28761
  1841
    @{method_def atomize} & : & @{text method} \\
wenzelm@28761
  1842
    @{attribute_def atomize} & : & @{text attribute} \\
wenzelm@28761
  1843
    @{attribute_def rule_format} & : & @{text attribute} \\
wenzelm@28761
  1844
    @{attribute_def rulify} & : & @{text attribute} \\
wenzelm@26790
  1845
  \end{matharray}
wenzelm@26790
  1846
wenzelm@26790
  1847
  The very starting point for any Isabelle object-logic is a ``truth
wenzelm@26790
  1848
  judgment'' that links object-level statements to the meta-logic
wenzelm@26790
  1849
  (with its minimal language of @{text prop} that covers universal
wenzelm@26790
  1850
  quantification @{text "\<And>"} and implication @{text "\<Longrightarrow>"}).
wenzelm@26790
  1851
wenzelm@26790
  1852
  Common object-logics are sufficiently expressive to internalize rule
wenzelm@26790
  1853
  statements over @{text "\<And>"} and @{text "\<Longrightarrow>"} within their own
wenzelm@26790
  1854
  language.  This is useful in certain situations where a rule needs
wenzelm@26790
  1855
  to be viewed as an atomic statement from the meta-level perspective,
wenzelm@26790
  1856
  e.g.\ @{text "\<And>x. x \<in> A \<Longrightarrow> P x"} versus @{text "\<forall>x \<in> A. P x"}.
wenzelm@26790
  1857
wenzelm@26790
  1858
  From the following language elements, only the @{method atomize}
wenzelm@26790
  1859
  method and @{attribute rule_format} attribute are occasionally
wenzelm@26790
  1860
  required by end-users, the rest is for those who need to setup their
wenzelm@26790
  1861
  own object-logic.  In the latter case existing formulations of
wenzelm@26790
  1862
  Isabelle/FOL or Isabelle/HOL may be taken as realistic examples.
wenzelm@26790
  1863
wenzelm@26790
  1864
  Generic tools may refer to the information provided by object-logic
wenzelm@26790
  1865
  declarations internally.
wenzelm@26790
  1866
wenzelm@55112
  1867
  @{rail \<open>
wenzelm@46494
  1868
    @@{command judgment} @{syntax name} '::' @{syntax type} @{syntax mixfix}?
wenzelm@26790
  1869
    ;
wenzelm@42596
  1870
    @@{attribute atomize} ('(' 'full' ')')?
wenzelm@26790
  1871
    ;
wenzelm@42596
  1872
    @@{attribute rule_format} ('(' 'noasm' ')')?
wenzelm@55112
  1873
  \<close>}
wenzelm@26790
  1874
wenzelm@28760
  1875
  \begin{description}
wenzelm@26790
  1876
  
wenzelm@28760
  1877
  \item @{command "judgment"}~@{text "c :: \<sigma> (mx)"} declares constant
wenzelm@28760
  1878
  @{text c} as the truth judgment of the current object-logic.  Its
wenzelm@28760
  1879
  type @{text \<sigma>} should specify a coercion of the category of
wenzelm@28760
  1880
  object-level propositions to @{text prop} of the Pure meta-logic;
wenzelm@28760
  1881
  the mixfix annotation @{text "(mx)"} would typically just link the
wenzelm@28760
  1882
  object language (internally of syntactic category @{text logic})
wenzelm@28760
  1883
  with that of @{text prop}.  Only one @{command "judgment"}
wenzelm@28760
  1884
  declaration may be given in any theory development.
wenzelm@26790
  1885
  
wenzelm@28760
  1886
  \item @{method atomize} (as a method) rewrites any non-atomic
wenzelm@26790
  1887
  premises of a sub-goal, using the meta-level equations declared via
wenzelm@26790
  1888
  @{attribute atomize} (as an attribute) beforehand.  As a result,
wenzelm@26790
  1889
  heavily nested goals become amenable to fundamental operations such
wenzelm@42626
  1890
  as resolution (cf.\ the @{method (Pure) rule} method).  Giving the ``@{text
wenzelm@26790
  1891
  "(full)"}'' option here means to turn the whole subgoal into an
wenzelm@26790
  1892
  object-statement (if possible), including the outermost parameters
wenzelm@26790
  1893
  and assumptions as well.
wenzelm@26790
  1894
wenzelm@26790
  1895
  A typical collection of @{attribute atomize} rules for a particular
wenzelm@26790
  1896
  object-logic would provide an internalization for each of the
wenzelm@26790
  1897
  connectives of @{text "\<And>"}, @{text "\<Longrightarrow>"}, and @{text "\<equiv>"}.
wenzelm@26790
  1898
  Meta-level conjunction should be covered as well (this is
wenzelm@26790
  1899
  particularly important for locales, see \secref{sec:locale}).
wenzelm@26790
  1900
wenzelm@28760
  1901
  \item @{attribute rule_format} rewrites a theorem by the equalities
wenzelm@28760
  1902
  declared as @{attribute rulify} rules in the current object-logic.
wenzelm@28760
  1903
  By default, the result is fully normalized, including assumptions
wenzelm@28760
  1904
  and conclusions at any depth.  The @{text "(no_asm)"} option
wenzelm@28760
  1905
  restricts the transformation to the conclusion of a rule.
wenzelm@26790
  1906
wenzelm@26790
  1907
  In common object-logics (HOL, FOL, ZF), the effect of @{attribute
wenzelm@26790
  1908
  rule_format} is to replace (bounded) universal quantification
wenzelm@26790
  1909
  (@{text "\<forall>"}) and implication (@{text "\<longrightarrow>"}) by the corresponding
wenzelm@26790
  1910
  rule statements over @{text "\<And>"} and @{text "\<Longrightarrow>"}.
wenzelm@26790
  1911
wenzelm@28760
  1912
  \end{description}
wenzelm@58618
  1913
\<close>
wenzelm@26790
  1914
wenzelm@50083
  1915
wenzelm@58618
  1916
section \<open>Tracing higher-order unification\<close>
wenzelm@50083
  1917
wenzelm@58618
  1918
text \<open>
wenzelm@50083
  1919
  \begin{tabular}{rcll}
wenzelm@50083
  1920
    @{attribute_def unify_trace_simp} & : & @{text "attribute"} & default @{text "false"} \\
wenzelm@50083
  1921
    @{attribute_def unify_trace_types} & : & @{text "attribute"} & default @{text "false"} \\
wenzelm@50083
  1922
    @{attribute_def unify_trace_bound} & : & @{text "attribute"} & default @{text "50"} \\
wenzelm@50083
  1923
    @{attribute_def unify_search_bound} & : & @{text "attribute"} & default @{text "60"} \\
wenzelm@50083
  1924
  \end{tabular}
wenzelm@61421
  1925
  \<^medskip>
wenzelm@50083
  1926
wenzelm@50083
  1927
  Higher-order unification works well in most practical situations,
wenzelm@50083
  1928
  but sometimes needs extra care to identify problems.  These tracing
wenzelm@50083
  1929
  options may help.
wenzelm@50083
  1930
wenzelm@50083
  1931
  \begin{description}
wenzelm@50083
  1932
wenzelm@50083
  1933
  \item @{attribute unify_trace_simp} controls tracing of the
wenzelm@50083
  1934
  simplification phase of higher-order unification.
wenzelm@50083
  1935
wenzelm@50083
  1936
  \item @{attribute unify_trace_types} controls warnings of
wenzelm@50083
  1937
  incompleteness, when unification is not considering all possible
wenzelm@50083
  1938
  instantiations of schematic type variables.
wenzelm@50083
  1939
wenzelm@50083
  1940
  \item @{attribute unify_trace_bound} determines the depth where
wenzelm@50083
  1941
  unification starts to print tracing information once it reaches
wenzelm@50083
  1942
  depth; 0 for full tracing.  At the default value, tracing
wenzelm@50083
  1943
  information is almost never printed in practice.
wenzelm@50083
  1944
wenzelm@50083
  1945
  \item @{attribute unify_search_bound} prevents unification from
wenzelm@50083
  1946
  searching past the given depth.  Because of this bound, higher-order
wenzelm@50083
  1947
  unification cannot return an infinite sequence, though it can return
wenzelm@50083
  1948
  an exponentially long one.  The search rarely approaches the default
wenzelm@50083
  1949
  value in practice.  If the search is cut off, unification prints a
wenzelm@50083
  1950
  warning ``Unification bound exceeded''.
wenzelm@50083
  1951
wenzelm@50083
  1952
  \end{description}
wenzelm@50083
  1953
wenzelm@50083
  1954
  \begin{warn}
wenzelm@50083
  1955
  Options for unification cannot be modified in a local context.  Only
wenzelm@50083
  1956
  the global theory content is taken into account.
wenzelm@50083
  1957
  \end{warn}
wenzelm@58618
  1958
\<close>
wenzelm@50083
  1959
wenzelm@26782
  1960
end