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