isabelle-cookbook: comparison ProgTutorial/Essential.thy

equal deleted inserted replaced

-:95b42288294e
+:438703674711
 | Var of indexname * typ
 | Bound of int
 | Abs of string * typ * term
 | $ of term * term\<close>
+ML \<open>
+let
+val redex = @{term "(\<lambda>(x::int) (y::int). x)"}
+val arg1 = @{term "1::int"}
+val arg2 = @{term "2::int"}
+in
+pretty_term @{context} (redex $ arg1 $ arg2)
+end\<close>
 text \<open>
 This datatype implements Church-style lambda-terms, where types are
 explicitly recorded in variables, constants and abstractions.  The
 important point of having terms is that you can pattern-match against them;
 this cannot be done with certified terms. As can be seen in Line 5,
 terms use the usual de Bruijn index mechanism for representing bound
 variables.  For example in
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>@{term "\<lambda>x y. x y"}\<close>
 \<open>Abs ("x", "'a \<Rightarrow> 'b", Abs ("y", "'a", Bound 1 $ Bound 0))\<close>}
 the indices refer to the number of Abstractions (@{ML Abs}) that we need to
 skip until we hit the @{ML Abs} that binds the corresponding
 term-constructor @{ML $}.
 Be careful if you pretty-print terms. Consider pretty-printing the abstraction
 term shown above:
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>@{term "\<lambda>x y. x y"}
 |> pretty_term @{context}
 |> pwriteln\<close>
 \<open>\<lambda>x. x\<close>}
 This is one common source for puzzlement in Isabelle, which has
 tacitly eta-contracted the output. You obtain a similar result
 with beta-redexes
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>let
 val redex = @{term "(\<lambda>(x::int) (y::int). x)"}
 val arg1 = @{term "1::int"}
 val arg2 = @{term "2::int"}
 in
 \ref{sec:printing}), but none for beta-contractions. However you can avoid
 the beta-contractions by switching off abbreviations using the configuration
 value @{ML_ind show_abbrevs in Syntax}. For example
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>let
 val redex = @{term "(\<lambda>(x::int) (y::int). x)"}
 val arg1 = @{term "1::int"}
 val arg2 = @{term "2::int"}
 val ctxt = Config.put show_abbrevs false @{context}
 Isabelle makes a distinction between \emph{free} variables (term-constructor
 @{ML Free} and written on the user level in blue colour) and
 \emph{schematic} variables (term-constructor @{ML Var} and written with a
 leading question mark). Consider the following two examples
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>let
 val v1 = Var (("x", 3), @{typ bool})
 val v2 = Var (("x1", 3), @{typ bool})
 val v3 = Free ("x", @{typ bool})
 in
 \end{readmore}
 Constructing terms via antiquotations has the advantage that only typable
 terms can be constructed. For example
-@{ML_matchresult_fake_both [display,gray]
+@{ML_response [display,gray]
 \<open>@{term "x x"}\<close>
 \<open>Type unification failed: Occurs check!\<close>}
 raises a typing error, while it is perfectly ok to construct the term
 with the raw ML-constructors:
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val omega = Free ("x", @{typ "nat \<Rightarrow> nat"}) $ Free ("x", @{typ nat})
 in
 pwriteln (pretty_term @{context} omega)
 end\<close>
-\<open>x x\<close>}
+"x x"}
 Sometimes the internal representation of terms can be surprisingly different
 from what you see at the user-level, because the layers of
 parsing/type-checking/pretty printing can be quite elaborate.
 is needed whenever a term is constructed that will be proved as a theorem.
 As already seen above, types can be constructed using the antiquotation
 \<open>@{typ _}\<close>. For example:
-@{ML_matchresult_fake [display,gray] \<open>@{typ "bool \<Rightarrow> nat"}\<close> \<open>bool \<Rightarrow> nat\<close>}
+@{ML_response [display,gray] \<open>@{typ "bool \<Rightarrow> nat"}\<close> \<open>bool \<Rightarrow> nat\<close>}
 The corresponding datatype is
 \<close>
 ML_val %grayML\<open>datatype typ =
 text \<open>
 After that the types for booleans, lists and so on are printed out again
 the standard Isabelle way.
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
-\<open>@{typ "bool"};
+\<open>(@{typ "bool"},
-@{typ "'a list"}\<close>
+@{typ "'a list"})\<close>
-\<open>"bool"
+\<open>("bool",
-"'a List.list"\<close>}
+"'a list")\<close>}
 \begin{readmore}
 Types are described in detail in \isccite{sec:types}. Their
 definition and many useful operations are implemented
 in @{ML_file "Pure/type.ML"}.
 constructing terms. One is the function @{ML_ind list_comb in Term}, which
 takes as argument a term and a list of terms, and produces as output the
 term list applied to the term. For example
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val trm = @{term "P::bool \<Rightarrow> bool \<Rightarrow> bool"}
 val args = [@{term "True"}, @{term "False"}]
 in
 list_comb (trm, args)
 end\<close>
 \<open>Free ("P", "bool \<Rightarrow> bool \<Rightarrow> bool")
-$ Const ("True", "bool") $ Const ("False", "bool")\<close>}
+$ Const ("HOL.True", "bool") $ Const ("HOL.False", "bool")\<close>}
 Another handy function is @{ML_ind lambda in Term}, which abstracts a variable
 in a term. For example
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val x_nat = @{term "x::nat"}
 val trm = @{term "(P::nat \<Rightarrow> bool) x"}
 in
 lambda x_nat trm
 end\<close>
-\<open>Abs ("x", "Nat.nat", Free ("P", "bool \<Rightarrow> bool") $ Bound 0)\<close>}
+\<open>Abs ("x", "nat", Free ("P", "nat \<Rightarrow> bool") $ Bound 0)\<close>}
 In this example, @{ML lambda} produces a de Bruijn index (i.e.\ @{ML \<open>Bound 0\<close>}),
 and an abstraction, where it also records the type of the abstracted
 variable and for printing purposes also its name.  Note that because of the
 typing annotation on \<open>P\<close>, the variable \<open>x\<close> in \<open>P x\<close>
 is of the same type as the abstracted variable. If it is of different type,
 as in
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val x_int = @{term "x::int"}
 val trm = @{term "(P::nat \<Rightarrow> bool) x"}
 in
 lambda x_int trm
 There is also the function @{ML_ind subst_free in Term} with which terms can be
 replaced by other terms. For example below, we will replace in @{term
 "(f::nat \<Rightarrow> nat \<Rightarrow> nat) 0 x"} the subterm @{term "(f::nat \<Rightarrow> nat \<Rightarrow> nat) 0"} by
 @{term y}, and @{term x} by @{term True}.
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val sub1 = (@{term "(f::nat \<Rightarrow> nat \<Rightarrow> nat) 0"}, @{term "y::nat \<Rightarrow> nat"})
 val sub2 = (@{term "x::nat"}, @{term "True"})
 val trm = @{term "((f::nat \<Rightarrow> nat \<Rightarrow> nat) 0) x"}
 in
 subst_free [sub1, sub2] trm
 end\<close>
-\<open>Free ("y", "nat \<Rightarrow> nat") $ Const ("True", "bool")\<close>}
+\<open>Free ("y", "nat \<Rightarrow> nat") $ Const ("HOL.True", "bool")\<close>}
 As can be seen, @{ML subst_free} does not take typability into account.
 However it takes alpha-equivalence into account:
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>let
 val sub = (@{term "(\<lambda>y::nat. y)"}, @{term "x::nat"})
 val trm = @{term "(\<lambda>x::nat. x)"}
 in
 subst_free [sub] trm
 text \<open>
 The function returns a pair consisting of the stripped off variables and
 the body of the universal quantification. For example
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>strip_alls @{term "\<forall>x y. x = (y::bool)"}\<close>
 \<open>([Free ("x", "bool"), Free ("y", "bool")],
-Const ("op =", _) $ Bound 1 $ Bound 0)\<close>}
+Const ("HOL.eq",\<dots>) $ Bound 1 $ Bound 0)\<close>}
 Note that we produced in the body two dangling de Bruijn indices.
 Later on we will also use the inverse function that
 builds the quantification from a body and a list of (free) variables.
 \<close>
 text \<open>
 As said above, after calling @{ML strip_alls}, you obtain a term with loose
 bound variables. With the function @{ML subst_bounds}, you can replace these
 loose @{ML_ind Bound in Term}s with the stripped off variables.
-@{ML_matchresult_fake [display, gray, linenos]
+@{ML_response [display, gray, linenos]
 \<open>let
 val (vrs, trm) = strip_alls @{term "\<forall>x y. x = (y::bool)"}
 in
 subst_bounds (rev vrs, trm)
 |> pretty_term @{context}
 name is by no means unique. If clashes need to be avoided, then we should
 use the function @{ML_ind dest_abs in Term}, which returns the body where
 the loose de Bruijn index is replaced by a unique free variable. For example
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val body = Bound 0 $ Free ("x", @{typ nat})
 in
 Term.dest_abs ("x", @{typ "nat \<Rightarrow> bool"}, body)
 end\<close>
-\<open>("xa", Free ("xa", "Nat.nat \<Rightarrow> bool") $ Free ("x", "Nat.nat"))\<close>}
+\<open>("xa", Free ("xa", "nat \<Rightarrow> bool") $ Free ("x", "nat"))\<close>}
 Sometimes it is necessary to manipulate de Bruijn indices in terms directly.
 There are many functions to do this. We describe only two. The first,
 @{ML_ind incr_boundvars in Term}, increases by an integer the indices
 of the loose bound variables in a term. In the code below
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>@{term "\<forall>x y z u. z = u"}
 |> strip_alls
 ||> incr_boundvars 2
 |> build_alls
 |> pretty_term @{context}
 between the first two quantified variables.
 The second function, @{ML_ind loose_bvar1 in Text}, tests whether a term
 contains a loose bound of a certain index. For example
-@{ML_matchresult_fake [gray,display]
+@{ML_matchresult [gray,display]
 \<open>let
 val body = snd (strip_alls @{term "\<forall>x y. x = (y::bool)"})
 in
 [loose_bvar1 (body, 0),
 loose_bvar1 (body, 1),
 There are also many convenient functions that construct specific HOL-terms
 in the structure @{ML_structure HOLogic}. For example @{ML_ind mk_eq in
 HOLogic} constructs an equality out of two terms.  The types needed in this
 equality are calculated from the type of the arguments. For example
-@{ML_matchresult_fake [gray,display]
+@{ML_response [gray,display]
 \<open>let
 val eq = HOLogic.mk_eq (@{term "True"}, @{term "False"})
 in
 eq |> pretty_term @{context}
 |> pwriteln
 | _ => ty)\<close>
 text \<open>
 Here is an example:
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>map_types nat_to_int @{term "a = (1::nat)"}\<close>
-\<open>Const ("op =", "int \<Rightarrow> int \<Rightarrow> bool")
+\<open>Const ("HOL.eq", "int \<Rightarrow> int \<Rightarrow> bool")
-$ Free ("a", "int") $ Const ("HOL.one_class.one", "int")\<close>}
+$ Free ("a", "int") $ Const ("Groups.one_class.one", "int")\<close>}
 If you want to obtain the list of free type-variables of a term, you
 can use the function @{ML_ind  add_tfrees in Term}
 (similarly @{ML_ind  add_tvars in Term} for the schematic type-variables).
 One would expect that such functions
 below. In case of failure, @{ML typ_unify in Sign} will raise the exception
 \<open>TUNIFY\<close>.  We can print out the resulting type environment bound to
 @{ML tyenv_unif} with the built-in function @{ML_ind dest in Vartab} from the
 structure @{ML_structure Vartab}.
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>Vartab.dest tyenv_unif\<close>
-\<open>[(("'a", 0), (["HOL.type"], "?'b List.list")),
+\<open>[(("'a", 0), (["HOL.type"], "?'b list")),
 (("'b", 0), (["HOL.type"], "nat"))]\<close>}
 \<close>
 text_raw \<open>
 \begin{figure}[t]
 use in what follows our own pretty-printing function from
 Figure~\ref{fig:prettyenv} for @{ML_type "Type.tyenv"}s. For the type
 environment in the example this function prints out the more legible:
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>pretty_tyenv @{context} tyenv_unif\<close>
 \<open>[?'a := ?'b list, ?'b := nat]\<close>}
 The way the unification function @{ML typ_unify in Sign} is implemented
 using an initial type environment and initial index makes it easy to
 val ty2 = @{typ_pat "?'b::s2"}
 in
 Sign.typ_unify @{theory} (ty1, ty2) (Vartab.empty, 0)
 end\<close>
+declare[[show_sorts]]
 text \<open>
 To print out the result type environment we switch on the printing
 of sort information by setting @{ML_ind show_sorts in Syntax} to
 true. This allows us to inspect the typing environment.
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>pretty_tyenv @{context} tyenv\<close>
 \<open>[?'a::s1 := ?'a1::{s1, s2}, ?'b::s2 := ?'a1::{s1, s2}]\<close>}
+\<close>
+declare[[show_sorts=false]]
+text\<open>
 As can be seen, the type variables \<open>?'a\<close> and \<open>?'b\<close> are instantiated
 with a new type variable \<open>?'a1\<close> with sort \<open>{s1, s2}\<close>. Since a new
 type variable has been introduced the @{ML index}, originally being \<open>0\<close>,
 has been increased to \<open>1\<close>.
 Let us now return to the unification problem \<open>?'a * ?'b\<close> and
 \<open>?'b list * nat\<close> from the beginning of this section, and the
 calculated type environment @{ML tyenv_unif}:
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>pretty_tyenv @{context} tyenv_unif\<close>
 \<open>[?'a := ?'b list, ?'b := nat]\<close>}
 Observe that the type environment which the function @{ML typ_unify in
 Sign} returns is \emph{not} an instantiation in fully solved form: while \<open>?'b\<close> is instantiated to @{typ nat}, this is not propagated to the
 called an instantiation in \emph{triangular form}. These triangular
 instantiations, or triangular type environments, are used because of
 performance reasons. To apply such a type environment to a type, say \<open>?'a *
 ?'b\<close>, you should use the function @{ML_ind norm_type in Envir}:
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>Envir.norm_type tyenv_unif @{typ_pat "?'a * ?'b"}\<close>
-\<open>nat list * nat\<close>}
+\<open>nat list \<times> nat\<close>}
 Matching of types can be done with the function @{ML_ind typ_match in Sign}
 also from the structure @{ML_structure Sign}. This function returns a @{ML_type
 Type.tyenv} as well, but might raise the exception \<open>TYPE_MATCH\<close> in case
 of failure. For example
 end\<close>
 text \<open>
 Printing out the calculated matcher gives
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>pretty_tyenv @{context} tyenv_match\<close>
 \<open>[?'a := bool list, ?'b := nat]\<close>}
 Unlike unification, which uses the function @{ML norm_type in Envir},
 applying the matcher to a type needs to be done with the function
 @{ML_ind subst_type in Envir}. For example
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>Envir.subst_type tyenv_match @{typ_pat "?'a * ?'b"}\<close>
-\<open>bool list * nat\<close>}
+\<open>bool list \<times> nat\<close>}
 Be careful to observe the difference: always use
 @{ML subst_type in Envir} for matchers and @{ML norm_type in Envir}
 for unifiers. To show the difference, let us calculate the
 following matcher:
 text \<open>
 Now @{ML tyenv_unif} is equal to @{ML tyenv_match'}. If we apply
 @{ML norm_type in Envir} to the type \<open>?'a * ?'b\<close> we obtain
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>Envir.norm_type tyenv_match' @{typ_pat "?'a * ?'b"}\<close>
-\<open>nat list * nat\<close>}
+\<open>nat list \<times> nat\<close>}
 which does not solve the matching problem, and if
 we apply @{ML subst_type in Envir} to the same type we obtain
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>Envir.subst_type tyenv_unif @{typ_pat "?'a * ?'b"}\<close>
-\<open>?'b list * nat\<close>}
+\<open>?'b list \<times> nat\<close>}
 which does not solve the unification problem.
 \begin{readmore}
 Unification and matching for types is implemented
 text \<open>
 In this example we annotated types explicitly because then
 the type environment is empty and can be ignored. The
 resulting term environment is
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>pretty_env @{context} fo_env\<close>
 \<open>[?X := P, ?Y := \<lambda>a b. Q b a]\<close>}
 The matcher can be applied to a term using the function @{ML_ind subst_term
 in Envir} (remember the same convention for types applies to terms: @{ML
 subst_term in Envir} is for matchers and @{ML norm_term in Envir} for
 unifiers). The function @{ML subst_term in Envir} expects a type environment,
 which is set to empty in the example below, and a term environment.
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>let
 val trm = @{term_pat "(?X::(nat\<Rightarrow>nat\<Rightarrow>nat)\<Rightarrow>bool) ?Y"}
 in
 Envir.subst_term (Vartab.empty, fo_env) trm
 |> pretty_term @{context}
 alpha-equivalence, but this kind of matching should be used with care, since
 it is not clear whether the result is meaningful. A meaningful example is
 matching \<open>\<lambda>x. P x\<close> against the pattern \<open>\<lambda>y. ?X y\<close>. In this
 case, first-order matching produces \<open>[?X := P]\<close>.
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>let
 val fo_pat = @{term_pat "\<lambda>y. (?X::nat\<Rightarrow>bool) y"}
 val trm = @{term "\<lambda>x. (P::nat\<Rightarrow>bool) x"}
 val init = (Vartab.empty, Vartab.empty)
 in
 record of type @{ML_type Envir.env} containing a max-index, a type environment
 and a term environment). The corresponding functions are @{ML_ind match in Pattern}
 and @{ML_ind unify in Pattern}, both implemented in the structure
 @{ML_structure Pattern}. An example for higher-order pattern unification is
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>let
 val trm1 = @{term_pat "\<lambda>x y. g (?X y x) (f (?Y x))"}
 val trm2 = @{term_pat "\<lambda>u v. g u (f u)"}
 val init = Envir.empty 0
 val env = Pattern.unify (Context.Proof @{context}) (trm1, trm2) init (* FIXME: Reference to generic context *)
 text \<open>
 \footnote{\bf FIXME: what is the list of term pairs in the unifier: flex-flex pairs?}
 We can print them out as follows.
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
-\<open>pretty_env @{context} (Envir.term_env un1);
+\<open>pretty_env @{context} (Envir.term_env un1)\<close>
-pretty_env @{context} (Envir.term_env un2);
+\<open>[?X := \<lambda>a. a, ?Y := f a]\<close>}
-pretty_env @{context} (Envir.term_env un3)\<close>
+@{ML_response [display, gray]
-\<open>[?X := \<lambda>a. a, ?Y := f a]
+\<open>pretty_env @{context} (Envir.term_env un2)\<close>
-[?X := f, ?Y := a]
+\<open>[?X := f, ?Y := a]\<close>}
-[?X := \<lambda>b. f a]\<close>}
+@{ML_response [display, gray]
+\<open>pretty_env @{context} (Envir.term_env un3)\<close>
+\<open>[?X := \<lambda>b. f a]\<close>}
 In case of failure the function @{ML_ind unifiers in Unify} does not raise
 an exception, rather returns the empty sequence. For example
 also tries first to solve the problem by higher-order pattern
 unification. Only in case of failure full higher-order unification is
 called. This function has a built-in bound, which can be accessed and
 manipulated as a configuration value. For example
-@{ML_matchresult_fake [display,gray]
+@{ML_matchresult [display,gray]
 \<open>Config.get_global @{theory} (Unify.search_bound)\<close>
-\<open>Int 60\<close>}
+\<open>60\<close>}
 If this bound is reached during unification, Isabelle prints out the
 warning message @{text [quotes] "Unification bound exceeded"} and
 plenty of diagnostic information (sometimes annoyingly plenty of
 information).
 environments (Line 8). As a simple example we instantiate the
 @{thm [source] spec} rule so that its conclusion is of the form
 @{term "Q True"}.
-@{ML_matchresult_fake [gray,display,linenos]
+@{ML_response [gray,display,linenos]
 \<open>let
 val pat = Logic.strip_imp_concl (Thm.prop_of @{thm spec})
 val trm = @{term "Trueprop (Q True)"}
 val inst = matcher_inst @{context} pat trm 1
 in
 To calculate the type, this function traverses the whole term and will
 detect any typing inconsistency. For example changing the type of the variable
 @{term "x"} from @{typ "nat"} to @{typ "int"} will result in the error message:
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>type_of (@{term "f::nat \<Rightarrow> bool"} $ @{term "x::int"})\<close>
-\<open>*** Exception- TYPE ("type_of: type mismatch in application" \<dots>\<close>}
+\<open>exception TYPE raised \<dots>\<close>}
 Since the complete traversal might sometimes be too costly and
 not necessary, there is the function @{ML_ind fastype_of in Term}, which
 also returns the type of a term.
 information is redundant. A short-cut is to use the ``place-holder''
 type @{ML_ind dummyT in Term} and then let type-inference figure out the
 complete type. The type inference can be invoked with the function
 @{ML_ind check_term in Syntax}. An example is as follows:
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val c = Const (@{const_name "plus"}, dummyT)
 val o = @{term "1::nat"}
 val v = Free ("x", dummyT)
 in
 Syntax.check_term @{context} (c $ o $ v)
 end\<close>
-\<open>Const ("HOL.plus_class.plus", "nat \<Rightarrow> nat \<Rightarrow> nat") $
+\<open>Const ("Groups.plus_class.plus", "nat \<Rightarrow> nat \<Rightarrow> nat") $
-Const ("HOL.one_class.one", "nat") $ Free ("x", "nat")\<close>}
+Const ("Groups.one_class.one", "nat") $ Free ("x", "nat")\<close>}
 Instead of giving explicitly the type for the constant \<open>plus\<close> and the free
 variable \<open>x\<close>, type-inference fills in the missing information.
 \begin{readmore}
 be constructed via ``official interfaces''.
 Certification is always relative to a context. For example you can
 write:
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>Thm.cterm_of @{context} @{term "(a::nat) + b = c"}\<close>
 \<open>a + b = c\<close>}
 This can also be written with an antiquotation:
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>@{cterm "(a::nat) + b = c"}\<close>
 \<open>a + b = c\<close>}
 Attempting to obtain the certified term for
-@{ML_matchresult_fake_both [display,gray]
+@{ML_response [display,gray]
 \<open>@{cterm "1 + True"}\<close>
-\<open>Type unification failed \<dots>\<close>}
+\<open>Type unification failed\<dots>\<close>}
 yields an error (since the term is not typable). A slightly more elaborate
 example that type-checks is:
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val natT = @{typ "nat"}
 val zero = @{term "0::nat"}
 val plus = Const (@{const_name plus}, [natT, natT] ---> natT)
 in
 In Isabelle not just terms need to be certified, but also types. For example,
 you obtain the certified type for the Isabelle type @{typ "nat \<Rightarrow> bool"} on
 the ML-level as follows:
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>Thm.ctyp_of @{context} (@{typ nat} --> @{typ bool})\<close>
 \<open>nat \<Rightarrow> bool\<close>}
 or with the antiquotation:
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>@{ctyp "nat \<Rightarrow> bool"}\<close>
 \<open>nat \<Rightarrow> bool\<close>}
 Since certified terms are, unlike terms, abstract objects, we cannot
 pattern-match against them. However, we can construct them. For example
 the function @{ML_ind apply in Thm} produces a certified application.
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>Thm.apply @{cterm "P::nat \<Rightarrow> bool"} @{cterm "3::nat"}\<close>
 \<open>P 3\<close>}
 Similarly the function @{ML_ind list_comb in Drule} from the structure @{ML_structure Drule}
 applies a list of @{ML_type cterm}s.
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val chead = @{cterm "P::unit \<Rightarrow> nat \<Rightarrow> bool"}
 val cargs = [@{cterm "()"}, @{cterm "3::nat"}]
 in
 Drule.list_comb (chead, cargs)
 inserts necessary \<open>Trueprop\<close>s.
 If we print out the value of @{ML my_thm} then we see only the
 final statement of the theorem.
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>pwriteln (pretty_thm @{context} my_thm)\<close>
 \<open>\<lbrakk>\<And>x. P x \<Longrightarrow> Q x; P t\<rbrakk> \<Longrightarrow> Q t\<close>}
 However, internally the code-snippet constructs the following
 proof.
 Many functions destruct theorems into @{ML_type cterm}s. For example
 the functions @{ML_ind lhs_of in Thm} and @{ML_ind rhs_of in Thm} return
 the left and right-hand side, respectively, of a meta-equality.
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val eq = @{thm True_def}
 in
 (Thm.lhs_of eq, Thm.rhs_of eq)
-|> apply2 (Pretty.string_of o (pretty_cterm @{context}))
+|> apply2 (YXML.content_of o Pretty.string_of o (pretty_cterm @{context}))
 end\<close>
-\<open>(True, (\<lambda>x. x) = (\<lambda>x. x))\<close>}
+\<open>("True", "(\<lambda>x. x) = (\<lambda>x. x)")\<close>}
 Other function produce terms that can be pattern-matched.
 Suppose the following two theorems.
 \<close>
 Section~\ref{sec:simplifier}, the simplifier
 can be used to work directly over theorems, for example to unfold definitions. To show
 this, we build the theorem @{term "True \<equiv> True"} (Line 1) and then
 unfold the constant @{term "True"} according to its definition (Line 2).
-@{ML_matchresult_fake [display,gray,linenos]
+@{ML_response [display,gray,linenos]
 \<open>Thm.reflexive @{cterm "True"}
 |> Simplifier.rewrite_rule @{context} [@{thm True_def}]
 |> pretty_thm @{context}
 |> pwriteln\<close>
 \<open>(\<lambda>x. x) = (\<lambda>x. x) \<equiv> (\<lambda>x. x) = (\<lambda>x. x)\<close>}
 from the meta logic are more convenient for reasoning. Therefore there are
 some build in functions which help with these transformations. The function
 @{ML_ind rulify in Object_Logic}
 replaces all object connectives by equivalents in the meta logic. For example
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>Object_Logic.rulify @{context} @{thm foo_test2}\<close>
 \<open>\<lbrakk>?A; ?B\<rbrakk> \<Longrightarrow> ?C\<close>}
 The transformation in the other direction can be achieved with function
 @{ML_ind atomize in Object_Logic} and the following code.
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val thm = @{thm foo_test1}
 val meta_eq = Object_Logic.atomize @{context} (Thm.cprop_of thm)
 in
 Raw_Simplifier.rewrite_rule @{context} [meta_eq] thm
 end\<close>
 text \<open>
 This function produces for the theorem @{thm [source] list.induct}
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>atomize_thm @{context} @{thm list.induct}\<close>
-\<open>\<forall>P list. P [] \<longrightarrow> (\<forall>a list. P list \<longrightarrow> P (a # list)) \<longrightarrow> P list\<close>}
+\<open>"\<forall>P list. P [] \<longrightarrow> (\<forall>x1 x2. P x2 \<longrightarrow> P (x1 # x2)) \<longrightarrow> P list"\<close>}
 Theorems can also be produced from terms by giving an explicit proof.
 One way to achieve this is by using the function @{ML_ind prove in Goal}
 in the structure @{ML_structure Goal}. For example below we use this function
 to prove the term @{term "P \<Longrightarrow> P"}.
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val trm = @{term "P \<Longrightarrow> P::bool"}
 val tac = K (assume_tac @{context} 1)
 in
 Goal.prove @{context} ["P"] [] trm tac
 using the function @{ML_ind prove_common in Goal}. For this let us define the
 following three helper functions.
 \<close>
 ML %grayML\<open>fun rep_goals i = replicate i @{prop "f x = f x"}
-fun rep_tacs i = replicate i (resolve_tac @{context} [@{thm refl}])
+fun rep_tacs ctxt i = replicate i (resolve_tac ctxt [@{thm refl}])
 fun multi_test ctxt i =
 Goal.prove_common ctxt NONE ["f", "x"] [] (rep_goals i)
-(K ((Goal.conjunction_tac THEN' RANGE (rep_tacs i)) 1))\<close>
+(K ((Goal.conjunction_tac THEN' RANGE (rep_tacs ctxt i)) 1))\<close>
 text \<open>
 With them we can now produce three theorem instances of the
 proposition.
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>multi_test @{context} 3\<close>
 \<open>["?f ?x = ?f ?x", "?f ?x = ?f ?x", "?f ?x = ?f ?x"]\<close>}
 However you should be careful with @{ML prove_common in Goal} and very
 large goals. If you increase the counter in the code above to \<open>3000\<close>,
 @{ML_structure Skip_Proof} that allows us to turn any proposition into a theorem.
 Potentially making the system unsound.  This is sometimes useful for developing
 purposes, or when explicit proof construction should be omitted due to performace
 reasons. An example of this function is as follows:
-@{ML_matchresult_fake [display, gray]
+@{ML_response [display, gray]
 \<open>Skip_Proof.make_thm @{theory} @{prop "True = False"}\<close>
 \<open>True = False\<close>}
 \begin{readmore}
 Functions that setup goal states and prove theorems are implemented in
 kind, the names for cases and so on. This data is stored in a string-string
 list and can be retrieved with the function @{ML_ind get_tags in
 Thm}. Assume you prove the following lemma.
 \<close>
-lemma foo_data:
+theorem foo_data:
 shows "P \<Longrightarrow> P \<Longrightarrow> P" by assumption
 text \<open>
 The auxiliary data of this lemma can be retrieved using the function
 @{ML_ind get_tags in Thm}. So far the the auxiliary data of this lemma is
-@{ML_matchresult_fake [display,gray]
+@{ML_matchresult [display,gray]
 \<open>Thm.get_tags @{thm foo_data}\<close>
-\<open>[("name", "General.foo_data"), ("kind", "lemma")]\<close>}
+\<open>[("name", "Essential.foo_data"), ("kind", "theorem")]\<close>}
 consisting of a name and a kind.  When we store lemmas in the theorem database,
 we might want to explicitly extend this data by attaching case names to the
 two premises of the lemma.  This can be done with the function @{ML_ind name in Rule_Cases}
 from the structure @{ML_structure Rule_Cases}.
 @{thm foo_data})]) #> snd\<close>
 text \<open>
 The data of the theorem @{thm [source] foo_data'} is then as follows:
-@{ML_matchresult_fake [display,gray]
+@{ML_matchresult [display,gray]
 \<open>Thm.get_tags @{thm foo_data'}\<close>
-\<open>[("name", "General.foo_data'"), ("kind", "lemma"),
+\<open>[("name", "Essential.foo_data'"),
-("case_names", "foo_case_one;foo_case_two")]\<close>}
+("case_names", "foo_case_one;foo_case_two"), ("kind", "theorem")]\<close>}
 You can observe the case names of this lemma on the user level when using
 the proof methods \<open>cases\<close> and \<open>induct\<close>. In the proof below
 \<close>
 structure @{ML_structure Proofterm}.
 \<close>
 ML %grayML\<open>fun pthms_of (PBody {thms, ...}) = map #2 thms
 val get_names = (map Proofterm.thm_node_name) o pthms_of
-val get_pbodies = map (Future.join o Proofterm.thm_node_body) o pthms_of\<close>
+val get_pbodies = map (Future.join o Proofterm.thm_node_body) o pthms_of
+fun get_all_names thm =
+let
+(*proof body with digest*)
+val body = Proofterm.strip_thm (Thm.proof_body_of thm);
+(*all theorems used in the graph of nested proofs*)
+in Proofterm.fold_body_thms
+(fn {name, ...} => insert (op =) name) [body] []
+end\<close>
 text \<open>
 To see what their purpose is, consider the following three short proofs.
 \<close>
+ML \<open>
+\<close>
 lemma my_conjIa:
 shows "A \<and> B \<Longrightarrow> A \<and> B"
 apply(rule conjI)
 apply(drule conjunct1)
 apply(assumption)
 lemma my_conjIc:
 shows "A \<and> B \<Longrightarrow> A \<and> B"
 apply(auto)
 done
+ML "Proofterm.proofs"
+ML \<open>@{thm my_conjIa}
+|> get_all_names\<close>
 text \<open>
 While the information about which theorems are used is obvious in
 the first two proofs, it is not obvious in the third, because of the
 \<open>auto\<close>-step.  Fortunately, ``behind'' every proved theorem is
 a proof-tree that records all theorems that are employed for
 establishing this theorem.  We can traverse this proof-tree
 extracting this information.  Let us first extract the name of the
 established theorem. This can be done with
-@{ML_matchresult_fake [display,gray]
+@{ML_matchresult [display,gray]
 \<open>@{thm my_conjIa}
 |> Thm.proof_body_of
 |> get_names\<close>
 \<open>["Essential.my_conjIa"]\<close>}
 we established the theorem @{thm [source] my_conjIa}. The function @{ML_ind
 proof_body_of in Thm} returns a part of the data that is stored in a
 theorem.  Notice that the first proof above references
 three theorems, namely @{thm [source] conjI}, @{thm [source] conjunct1}
 and @{thm [source] conjunct2}. We can obtain them by descending into the
-first level of the proof-tree, as follows.
+proof-tree. The function @{ML get_all_names} recursively selects all names.
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>@{thm my_conjIa}
-|> Thm.proof_body_of
+|> get_all_names |> sort string_ord\<close>
-|> get_pbodies
+\<open>["", "HOL.All_def", "HOL.FalseE", "HOL.False_def", "HOL.TrueI", "HOL.True_def",
-|> map get_names
+"HOL.True_or_False", "HOL.allI", "HOL.and_def", "HOL.conjI",
-|> List.concat\<close>
+"HOL.conjunct1", "HOL.conjunct2", "HOL.disjE", "HOL.eqTrueE", "HOL.eqTrueI",
-\<open>["HOL.conjunct2", "HOL.conjunct1", "HOL.conjI", "Pure.protectD",
+"HOL.ext", "HOL.fun_cong", "HOL.iffD1", "HOL.iffD2", "HOL.iffI",
-"Pure.protectI"]\<close>}
+"HOL.impI", "HOL.mp", "HOL.or_def", "HOL.refl", "HOL.rev_iffD1",
+"HOL.rev_iffD2", "HOL.spec", "HOL.ssubst", "HOL.subst", "HOL.sym",
+"Pure.protectD", "Pure.protectI"]\<close>}
 The theorems @{thm [source] Pure.protectD} and @{thm [source]
 Pure.protectI} that are internal theorems are always part of a
-proof in Isabelle. Note also that applications of \<open>assumption\<close> do not
+proof in Isabelle. The other theorems are the theorems used in the proofs of the theorems
+@{thm [source] conjunct1}, @{thm [source] conjunct2} and @{thm [source] conjI}.
+Note also that applications of \<open>assumption\<close> do not
 count as a separate theorem, as you can see in the following code.
-@{ML_matchresult_fake [display,gray]
+@{ML_matchresult [display,gray]
 \<open>@{thm my_conjIb}
-|> Thm.proof_body_of
+|> get_all_names |> sort string_ord\<close>
-|> get_pbodies
+\<open>["", "Pure.protectD", "Pure.protectI"]\<close>}
-|> map get_names
-|> List.concat\<close>
-\<open>["Pure.protectD", "Pure.protectI"]\<close>}
 Interestingly, but not surprisingly, the proof of @{thm [source]
 my_conjIc} procceeds quite differently from @{thm [source] my_conjIa}
 and @{thm [source] my_conjIb}, as can be seen by the theorems that
 are returned for @{thm [source] my_conjIc}.
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>@{thm my_conjIc}
-|> Thm.proof_body_of
+|> get_all_names\<close>
-|> get_pbodies
+\<open>["HOL.simp_thms_25", "Pure.conjunctionD1", "Pure.conjunctionD2", "Pure.conjunctionI",
-|> map get_names
+"HOL.rev_mp", "HOL.exI", "HOL.allE", "HOL.exE",\<dots>]\<close>}
-|> List.concat\<close>
-\<open>["HOL.Eq_TrueI", "HOL.simp_thms_25", "HOL.eq_reflection",
-"HOL.conjunct2", "HOL.conjunct1", "HOL.TrueI", "Pure.protectD",
-"Pure.protectI"]\<close>}
-Of course we can also descend into the second level of the tree
-``behind'' @{thm [source] my_conjIa} say, which
-means we obtain the theorems that are used in order to prove
-@{thm [source] conjunct1}, @{thm [source] conjunct2} and @{thm [source] conjI}.
-@{ML_matchresult_fake [display, gray]
-\<open>@{thm my_conjIa}
-|> Thm.proof_body_of
-|> get_pbodies
-|> map get_pbodies
-|> (map o map) get_names
-|> List.concat
-|> List.concat
-|> duplicates (op=)\<close>
-\<open>["HOL.spec", "HOL.and_def", "HOL.mp", "HOL.impI", "Pure.protectD",
-"Pure.protectI"]\<close>}
 \begin{exercise}
 Have a look at the theorems that are used when a lemma is ``proved''
 by \isacommand{sorry}?
 \end{exercise}
 lemma trueI_2[my_thms]: "True" by simp
 text \<open>
 then you can see it is added to the initially empty list.
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>MyThms.get @{context}\<close>
 \<open>["True"]\<close>}
 You can also add theorems using the command \isacommand{declare}.
 \<close>
 text \<open>
 With this attribute, the \<open>add\<close> operation is the default and does
 not need to be explicitly given. These three declarations will cause the
 theorem list to be updated as:
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>MyThms.get @{context}\<close>
 \<open>["True", "Suc (Suc 0) = 2"]\<close>}
 The theorem @{thm [source] trueI_2} only appears once, since the
 function @{ML_ind  add_thm in Thm} tests for duplicates, before extending
 declare test[my_thms del]
 text \<open>After this, the theorem list is again:
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>MyThms.get @{context}\<close>
 \<open>["True"]\<close>}
 We used in this example two functions declared as @{ML_ind
 declaration_attribute in Thm}, but there can be any number of them. We just
 follows we will use the following wrapper function for printing a pretty
 type:
 \<close>
 ML %grayML\<open>fun pprint prt = tracing (Pretty.string_of prt)\<close>
+ML %invisible\<open>val pprint = YXML.content_of o Pretty.string_of\<close>
 text \<open>
 The point of the pretty-printing infrastructure is to give hints about how to
 layout text and let Isabelle do the actual layout. Let us first explain
 how you can insert places where a line break can occur. For this assume the
 following function that replicates a string n times:
 aaaaaaar fooooooooooooooobaaaaaaaaaaaar fooooooooooooooobaaaaaaaaaaaar fo
 oooooooooooooobaaaaaaaaaaaar\<close>}
 We obtain the same if we just use the function @{ML pprint}.
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>pprint (Pretty.str test_str)\<close>
 \<open>fooooooooooooooobaaaaaaaaaaaar fooooooooooooooobaaaaaaaaaaaar foooooooooo
 ooooobaaaaaaaaaaaar fooooooooooooooobaaaaaaaaaaaar fooooooooooooooobaaaaa
 aaaaaaar fooooooooooooooobaaaaaaaaaaaar fooooooooooooooobaaaaaaaaaaaar fo
 oooooooooooooobaaaaaaaaaaaar\<close>}
 function @{ML_ind breaks in Pretty}, which expects a list of pretty types
 and inserts a possible line break in between every two elements in this
 list. To print this list of pretty types as a single string, we concatenate
 them with the function @{ML_ind blk in Pretty} as follows:
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val ptrs = map Pretty.str (space_explode " " test_str)
 in
 pprint (Pretty.blk (0, Pretty.breaks ptrs))
 end\<close>
 Here the layout of @{ML test_str} is much more pleasing to the
 eye. The @{ML \<open>0\<close>} in @{ML_ind  blk in Pretty} stands for no hanging
 indentation of the printed string. You can increase the indentation
 and obtain
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val ptrs = map Pretty.str (space_explode " " test_str)
 in
 pprint (Pretty.blk (3, Pretty.breaks ptrs))
 end\<close>
 where starting from the second line the indent is 3. If you want
 that every line starts with the same indent, you can use the
 function @{ML_ind  indent in Pretty} as follows:
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val ptrs = map Pretty.str (space_explode " " test_str)
 in
 pprint (Pretty.indent 10 (Pretty.blk (0, Pretty.breaks ptrs)))
 end\<close>
 If you want to print out a list of items separated by commas and
 have the linebreaks handled properly, you can use the function
 @{ML_ind  commas in Pretty}. For example
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val ptrs = map (Pretty.str o string_of_int) (99998 upto 100020)
 in
 pprint (Pretty.blk (0, Pretty.commas ptrs))
 end\<close>
 @{ML_ind  enum in Pretty}. For example
 \<close>
 text \<open>
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val ptrs = map (Pretty.str o string_of_int) (99998 upto 100020)
 in
 pprint (Pretty.enum "," "{" "}" ptrs)
 end\<close>
 to insert a space (of length 1) before the
 @{text [quotes] "and"}. This space is also a place where a line break
 can occur. We do the same after the @{text [quotes] "and"}. This gives you
 for example
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val ptrs1 = map (Pretty.str o string_of_int) (1 upto 22)
+in
+pprint (Pretty.blk (0, and_list ptrs1))
+end\<close>
+\<open>1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21
+and 22\<close>}
+@{ML_response [display,gray]
+\<open>let
 val ptrs2 = map (Pretty.str o string_of_int) (10 upto 28)
 in
-pprint (Pretty.blk (0, and_list ptrs1));
 pprint (Pretty.blk (0, and_list ptrs2))
 end\<close>
-\<open>1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21
+\<open>10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27 and
-and 22
-10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27 and
 28\<close>}
 Like @{ML blk in Pretty}, the function @{ML_ind chunks in Pretty} prints out
 a list of items, but automatically inserts forced breaks between each item.
 Compare
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val a_and_b = [Pretty.str "a", Pretty.str "b"]
 in
-pprint (Pretty.blk (0, a_and_b));
+pprint (Pretty.blk (0, a_and_b))
+end\<close>
+\<open>ab\<close>}
+@{ML_response [display,gray]
+\<open>let
+val a_and_b = [Pretty.str "a", Pretty.str "b"]
+in
 pprint (Pretty.chunks a_and_b)
 end\<close>
-\<open>ab
+\<open>a
-a
 b\<close>}
 The function @{ML_ind big_list in Pretty} helps with printing long lists.
 It is used for example in the command \isacommand{print\_theorems}. An
 example is as follows.
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>let
 val pstrs = map (Pretty.str o string_of_int) (4 upto 10)
 in
 pprint (Pretty.big_list "header" pstrs)
 end\<close>
 The point of the pretty-printing functions is to conveninetly obtain
 a lay-out of terms and types that is pleasing to the eye. If we print
 out the the terms produced by the the function @{ML de_bruijn} from
 exercise~\ref{ex:debruijn} we obtain the following:
-@{ML_matchresult_fake [display,gray]
+@{ML_response [display,gray]
 \<open>pprint (Syntax.pretty_term  @{context} (de_bruijn 4))\<close>
 \<open>(P 3 = P 4 \<longrightarrow> P 4 \<and> P 3 \<and> P 2 \<and> P 1) \<and>
 (P 2 = P 3 \<longrightarrow> P 4 \<and> P 3 \<and> P 2 \<and> P 1) \<and>
 (P 1 = P 2 \<longrightarrow> P 4 \<and> P 3 \<and> P 2 \<and> P 1) \<and>
 (P 1 = P 4 \<longrightarrow> P 4 \<and> P 3 \<and> P 2 \<and> P 1) \<longrightarrow>

changeset 572	438703674711
parent 569	f875a25aa72d
child 573	321e220a6baa