ProgTutorial/Essential.thy
changeset 567 f7c97e64cc2a
parent 566 6103b0eadbf2
child 569 f875a25aa72d
equal deleted inserted replaced
566:6103b0eadbf2 567:f7c97e64cc2a
    25 text \<open>
    25 text \<open>
    26   In Isabelle, there are certified terms and uncertified terms (respectively types). 
    26   In Isabelle, there are certified terms and uncertified terms (respectively types). 
    27   Uncertified terms are often just called terms. One way to construct them is by 
    27   Uncertified terms are often just called terms. One way to construct them is by 
    28   using the antiquotation \mbox{\<open>@{term \<dots>}\<close>}. For example
    28   using the antiquotation \mbox{\<open>@{term \<dots>}\<close>}. For example
    29 
    29 
    30   @{ML_response [display,gray] 
    30   @{ML_matchresult [display,gray] 
    31 "@{term \"(a::nat) + b = c\"}" 
    31 "@{term \"(a::nat) + b = c\"}" 
    32 "Const (\"HOL.eq\", _) $ 
    32 "Const (\"HOL.eq\", _) $ 
    33   (Const (\"Groups.plus_class.plus\", _) $ _ $ _) $ _"}
    33   (Const (\"Groups.plus_class.plus\", _) $ _ $ _) $ _"}
    34 
    34 
    35   constructs the term @{term "(a::nat) + b = c"}. The resulting term is printed using 
    35   constructs the term @{term "(a::nat) + b = c"}. The resulting term is printed using 
    51   important point of having terms is that you can pattern-match against them;
    51   important point of having terms is that you can pattern-match against them;
    52   this cannot be done with certified terms. As can be seen in Line 5,
    52   this cannot be done with certified terms. As can be seen in Line 5,
    53   terms use the usual de Bruijn index mechanism for representing bound
    53   terms use the usual de Bruijn index mechanism for representing bound
    54   variables.  For example in
    54   variables.  For example in
    55 
    55 
    56   @{ML_response_fake [display, gray]
    56   @{ML_matchresult_fake [display, gray]
    57   "@{term \"\<lambda>x y. x y\"}"
    57   "@{term \"\<lambda>x y. x y\"}"
    58   "Abs (\"x\", \"'a \<Rightarrow> 'b\", Abs (\"y\", \"'a\", Bound 1 $ Bound 0))"}
    58   "Abs (\"x\", \"'a \<Rightarrow> 'b\", Abs (\"y\", \"'a\", Bound 1 $ Bound 0))"}
    59 
    59 
    60   the indices refer to the number of Abstractions (@{ML Abs}) that we need to
    60   the indices refer to the number of Abstractions (@{ML Abs}) that we need to
    61   skip until we hit the @{ML Abs} that binds the corresponding
    61   skip until we hit the @{ML Abs} that binds the corresponding
    67   term-constructor @{ML $}.
    67   term-constructor @{ML $}.
    68 
    68 
    69   Be careful if you pretty-print terms. Consider pretty-printing the abstraction
    69   Be careful if you pretty-print terms. Consider pretty-printing the abstraction
    70   term shown above:
    70   term shown above:
    71 
    71 
    72   @{ML_response_fake [display, gray]
    72   @{ML_matchresult_fake [display, gray]
    73 "@{term \"\<lambda>x y. x y\"}
    73 "@{term \"\<lambda>x y. x y\"}
    74   |> pretty_term @{context}
    74   |> pretty_term @{context}
    75   |> pwriteln"
    75   |> pwriteln"
    76   "\<lambda>x. x"}
    76   "\<lambda>x. x"}
    77 
    77 
    78   This is one common source for puzzlement in Isabelle, which has 
    78   This is one common source for puzzlement in Isabelle, which has 
    79   tacitly eta-contracted the output. You obtain a similar result 
    79   tacitly eta-contracted the output. You obtain a similar result 
    80   with beta-redexes
    80   with beta-redexes
    81 
    81 
    82   @{ML_response_fake [display, gray]
    82   @{ML_matchresult_fake [display, gray]
    83 "let 
    83 "let 
    84   val redex = @{term \"(\<lambda>(x::int) (y::int). x)\"} 
    84   val redex = @{term \"(\<lambda>(x::int) (y::int). x)\"} 
    85   val arg1 = @{term \"1::int\"} 
    85   val arg1 = @{term \"1::int\"} 
    86   val arg2 = @{term \"2::int\"}
    86   val arg2 = @{term \"2::int\"}
    87 in
    87 in
    95   \ref{sec:printing}), but none for beta-contractions. However you can avoid
    95   \ref{sec:printing}), but none for beta-contractions. However you can avoid
    96   the beta-contractions by switching off abbreviations using the configuration
    96   the beta-contractions by switching off abbreviations using the configuration
    97   value @{ML_ind show_abbrevs in Syntax}. For example
    97   value @{ML_ind show_abbrevs in Syntax}. For example
    98 
    98 
    99 
    99 
   100   @{ML_response_fake [display, gray]
   100   @{ML_matchresult_fake [display, gray]
   101   "let 
   101   "let 
   102   val redex = @{term \"(\<lambda>(x::int) (y::int). x)\"} 
   102   val redex = @{term \"(\<lambda>(x::int) (y::int). x)\"} 
   103   val arg1 = @{term \"1::int\"} 
   103   val arg1 = @{term \"1::int\"} 
   104   val arg2 = @{term \"2::int\"}
   104   val arg2 = @{term \"2::int\"}
   105   val ctxt = Config.put show_abbrevs false @{context}
   105   val ctxt = Config.put show_abbrevs false @{context}
   112   Isabelle makes a distinction between \emph{free} variables (term-constructor
   112   Isabelle makes a distinction between \emph{free} variables (term-constructor
   113   @{ML Free} and written on the user level in blue colour) and
   113   @{ML Free} and written on the user level in blue colour) and
   114   \emph{schematic} variables (term-constructor @{ML Var} and written with a
   114   \emph{schematic} variables (term-constructor @{ML Var} and written with a
   115   leading question mark). Consider the following two examples
   115   leading question mark). Consider the following two examples
   116   
   116   
   117   @{ML_response_fake [display, gray]
   117   @{ML_matchresult_fake [display, gray]
   118 "let
   118 "let
   119   val v1 = Var ((\"x\", 3), @{typ bool})
   119   val v1 = Var ((\"x\", 3), @{typ bool})
   120   val v2 = Var ((\"x1\", 3), @{typ bool})
   120   val v2 = Var ((\"x1\", 3), @{typ bool})
   121   val v3 = Free (\"x\", @{typ bool})
   121   val v3 = Free (\"x\", @{typ bool})
   122 in
   122 in
   142   \end{readmore}
   142   \end{readmore}
   143   
   143   
   144   Constructing terms via antiquotations has the advantage that only typable
   144   Constructing terms via antiquotations has the advantage that only typable
   145   terms can be constructed. For example
   145   terms can be constructed. For example
   146 
   146 
   147   @{ML_response_fake_both [display,gray]
   147   @{ML_matchresult_fake_both [display,gray]
   148   "@{term \"x x\"}"
   148   "@{term \"x x\"}"
   149   "Type unification failed: Occurs check!"}
   149   "Type unification failed: Occurs check!"}
   150 
   150 
   151   raises a typing error, while it is perfectly ok to construct the term
   151   raises a typing error, while it is perfectly ok to construct the term
   152   with the raw ML-constructors:
   152   with the raw ML-constructors:
   153 
   153 
   154   @{ML_response_fake [display,gray] 
   154   @{ML_matchresult_fake [display,gray] 
   155 "let
   155 "let
   156   val omega = Free (\"x\", @{typ \"nat \<Rightarrow> nat\"}) $ Free (\"x\", @{typ nat})
   156   val omega = Free (\"x\", @{typ \"nat \<Rightarrow> nat\"}) $ Free (\"x\", @{typ nat})
   157 in 
   157 in 
   158   pwriteln (pretty_term @{context} omega)
   158   pwriteln (pretty_term @{context} omega)
   159 end"
   159 end"
   184 text \<open>
   184 text \<open>
   185   The antiquotation \<open>@{prop \<dots>}\<close> constructs terms by inserting the 
   185   The antiquotation \<open>@{prop \<dots>}\<close> constructs terms by inserting the 
   186   usually invisible \<open>Trueprop\<close>-coercions whenever necessary. 
   186   usually invisible \<open>Trueprop\<close>-coercions whenever necessary. 
   187   Consider for example the pairs
   187   Consider for example the pairs
   188 
   188 
   189 @{ML_response [display,gray] "(@{term \"P x\"}, @{prop \"P x\"})" 
   189 @{ML_matchresult [display,gray] "(@{term \"P x\"}, @{prop \"P x\"})" 
   190 "(Free (\"P\", _) $ Free (\"x\", _),
   190 "(Free (\"P\", _) $ Free (\"x\", _),
   191  Const (\"HOL.Trueprop\", _) $ (Free (\"P\", _) $ Free (\"x\", _)))"}
   191  Const (\"HOL.Trueprop\", _) $ (Free (\"P\", _) $ Free (\"x\", _)))"}
   192 
   192 
   193   where a coercion is inserted in the second component and 
   193   where a coercion is inserted in the second component and 
   194 
   194 
   195   @{ML_response [display,gray] "(@{term \"P x \<Longrightarrow> Q x\"}, @{prop \"P x \<Longrightarrow> Q x\"})" 
   195   @{ML_matchresult [display,gray] "(@{term \"P x \<Longrightarrow> Q x\"}, @{prop \"P x \<Longrightarrow> Q x\"})" 
   196   "(Const (\"Pure.imp\", _) $ _ $ _, 
   196   "(Const (\"Pure.imp\", _) $ _ $ _, 
   197  Const (\"Pure.imp\", _) $ _ $ _)"}
   197  Const (\"Pure.imp\", _) $ _ $ _)"}
   198 
   198 
   199   where it is not (since it is already constructed by a meta-implication). 
   199   where it is not (since it is already constructed by a meta-implication). 
   200   The purpose of the \<open>Trueprop\<close>-coercion is to embed formulae of
   200   The purpose of the \<open>Trueprop\<close>-coercion is to embed formulae of
   202   is needed whenever a term is constructed that will be proved as a theorem. 
   202   is needed whenever a term is constructed that will be proved as a theorem. 
   203 
   203 
   204   As already seen above, types can be constructed using the antiquotation 
   204   As already seen above, types can be constructed using the antiquotation 
   205   \<open>@{typ _}\<close>. For example:
   205   \<open>@{typ _}\<close>. For example:
   206 
   206 
   207   @{ML_response_fake [display,gray] "@{typ \"bool \<Rightarrow> nat\"}" "bool \<Rightarrow> nat"}
   207   @{ML_matchresult_fake [display,gray] "@{typ \"bool \<Rightarrow> nat\"}" "bool \<Rightarrow> nat"}
   208 
   208 
   209   The corresponding datatype is
   209   The corresponding datatype is
   210 \<close>
   210 \<close>
   211   
   211   
   212 ML_val %grayML\<open>datatype typ =
   212 ML_val %grayML\<open>datatype typ =
   222   like @{typ "int"} or @{typ bool}, are types with an empty list
   222   like @{typ "int"} or @{typ bool}, are types with an empty list
   223   of argument types. However, it needs a bit of effort to show an
   223   of argument types. However, it needs a bit of effort to show an
   224   example, because Isabelle always pretty prints types (unlike terms).
   224   example, because Isabelle always pretty prints types (unlike terms).
   225   Using just the antiquotation \<open>@{typ "bool"}\<close> we only see
   225   Using just the antiquotation \<open>@{typ "bool"}\<close> we only see
   226 
   226 
   227   @{ML_response [display, gray]
   227   @{ML_matchresult [display, gray]
   228   "@{typ \"bool\"}"
   228   "@{typ \"bool\"}"
   229   "bool"}
   229   "bool"}
   230   which is the pretty printed version of \<open>bool\<close>. However, in PolyML
   230   which is the pretty printed version of \<open>bool\<close>. However, in PolyML
   231   (version \<open>\<ge>\<close>5.3) it is easy to install your own pretty printer. With the
   231   (version \<open>\<ge>\<close>5.3) it is easy to install your own pretty printer. With the
   232   function below we mimic the behaviour of the usual pretty printer for
   232   function below we mimic the behaviour of the usual pretty printer for
   261 
   261 
   262 ML \<open>@{typ "bool"}\<close>
   262 ML \<open>@{typ "bool"}\<close>
   263 text \<open>
   263 text \<open>
   264   Now the type bool is printed out in full detail.
   264   Now the type bool is printed out in full detail.
   265 
   265 
   266   @{ML_response [display,gray]
   266   @{ML_matchresult [display,gray]
   267   "@{typ \"bool\"}"
   267   "@{typ \"bool\"}"
   268   "Type (\"HOL.bool\", [])"}
   268   "Type (\"HOL.bool\", [])"}
   269 
   269 
   270   When printing out a list-type
   270   When printing out a list-type
   271   
   271   
   272   @{ML_response [display,gray]
   272   @{ML_matchresult [display,gray]
   273   "@{typ \"'a list\"}"
   273   "@{typ \"'a list\"}"
   274   "Type (\"List.list\", [TFree (\"'a\", [\"HOL.type\"])])"}
   274   "Type (\"List.list\", [TFree (\"'a\", [\"HOL.type\"])])"}
   275 
   275 
   276   we can see the full name of the type is actually \<open>List.list\<close>, indicating
   276   we can see the full name of the type is actually \<open>List.list\<close>, indicating
   277   that it is defined in the theory \<open>List\<close>. However, one has to be 
   277   that it is defined in the theory \<open>List\<close>. However, one has to be 
   278   careful with names of types, because even if
   278   careful with names of types, because even if
   279   \<open>fun\<close> is defined in the theory \<open>HOL\<close>, it is  
   279   \<open>fun\<close> is defined in the theory \<open>HOL\<close>, it is  
   280   still represented by its simple name.
   280   still represented by its simple name.
   281 
   281 
   282    @{ML_response [display,gray]
   282    @{ML_matchresult [display,gray]
   283   "@{typ \"bool \<Rightarrow> nat\"}"
   283   "@{typ \"bool \<Rightarrow> nat\"}"
   284   "Type (\"fun\", [Type (\"HOL.bool\", []), Type (\"Nat.nat\", [])])"}
   284   "Type (\"fun\", [Type (\"HOL.bool\", []), Type (\"Nat.nat\", [])])"}
   285 
   285 
   286   We can restore the usual behaviour of Isabelle's pretty printer
   286   We can restore the usual behaviour of Isabelle's pretty printer
   287   with the code
   287   with the code
   292 
   292 
   293 text \<open>
   293 text \<open>
   294   After that the types for booleans, lists and so on are printed out again 
   294   After that the types for booleans, lists and so on are printed out again 
   295   the standard Isabelle way.
   295   the standard Isabelle way.
   296 
   296 
   297   @{ML_response_fake [display, gray]
   297   @{ML_matchresult_fake [display, gray]
   298   "@{typ \"bool\"};
   298   "@{typ \"bool\"};
   299 @{typ \"'a list\"}"
   299 @{typ \"'a list\"}"
   300   "\"bool\"
   300   "\"bool\"
   301 \"'a List.list\""}
   301 \"'a List.list\""}
   302 
   302 
   336 text \<open>
   336 text \<open>
   337   To see this, apply \<open>@{term S}\<close> and \<open>@{term T}\<close> 
   337   To see this, apply \<open>@{term S}\<close> and \<open>@{term T}\<close> 
   338   to both functions. With @{ML make_imp} you obtain the intended term involving 
   338   to both functions. With @{ML make_imp} you obtain the intended term involving 
   339   the given arguments
   339   the given arguments
   340 
   340 
   341   @{ML_response [display,gray] "make_imp @{term S} @{term T}" 
   341   @{ML_matchresult [display,gray] "make_imp @{term S} @{term T}" 
   342 "Const _ $ 
   342 "Const _ $ 
   343   Abs (\"x\", Type (\"Nat.nat\",[]),
   343   Abs (\"x\", Type (\"Nat.nat\",[]),
   344     Const _ $ (Free (\"S\",_) $ _) $ (Free (\"T\",_) $ _))"}
   344     Const _ $ (Free (\"S\",_) $ _) $ (Free (\"T\",_) $ _))"}
   345 
   345 
   346   whereas with @{ML make_wrong_imp} you obtain a term involving the @{term "P"} 
   346   whereas with @{ML make_wrong_imp} you obtain a term involving the @{term "P"} 
   347   and \<open>Q\<close> from the antiquotation.
   347   and \<open>Q\<close> from the antiquotation.
   348 
   348 
   349   @{ML_response [display,gray] "make_wrong_imp @{term S} @{term T}" 
   349   @{ML_matchresult [display,gray] "make_wrong_imp @{term S} @{term T}" 
   350 "Const _ $ 
   350 "Const _ $ 
   351   Abs (\"x\", _,
   351   Abs (\"x\", _,
   352     Const _ $ (Const _ $ (Free (\"P\",_) $ _)) $ 
   352     Const _ $ (Const _ $ (Free (\"P\",_) $ _)) $ 
   353                 (Const _ $ (Free (\"Q\",_) $ _)))"}
   353                 (Const _ $ (Free (\"Q\",_) $ _)))"}
   354 
   354 
   356   constructing terms. One is the function @{ML_ind list_comb in Term}, which
   356   constructing terms. One is the function @{ML_ind list_comb in Term}, which
   357   takes as argument a term and a list of terms, and produces as output the
   357   takes as argument a term and a list of terms, and produces as output the
   358   term list applied to the term. For example
   358   term list applied to the term. For example
   359 
   359 
   360 
   360 
   361 @{ML_response_fake [display,gray]
   361 @{ML_matchresult_fake [display,gray]
   362 "let
   362 "let
   363   val trm = @{term \"P::bool \<Rightarrow> bool \<Rightarrow> bool\"}
   363   val trm = @{term \"P::bool \<Rightarrow> bool \<Rightarrow> bool\"}
   364   val args = [@{term \"True\"}, @{term \"False\"}]
   364   val args = [@{term \"True\"}, @{term \"False\"}]
   365 in
   365 in
   366   list_comb (trm, args)
   366   list_comb (trm, args)
   369    $ Const (\"True\", \"bool\") $ Const (\"False\", \"bool\")"}
   369    $ Const (\"True\", \"bool\") $ Const (\"False\", \"bool\")"}
   370 
   370 
   371   Another handy function is @{ML_ind lambda in Term}, which abstracts a variable 
   371   Another handy function is @{ML_ind lambda in Term}, which abstracts a variable 
   372   in a term. For example
   372   in a term. For example
   373 
   373 
   374   @{ML_response_fake [display,gray]
   374   @{ML_matchresult_fake [display,gray]
   375 "let
   375 "let
   376   val x_nat = @{term \"x::nat\"}
   376   val x_nat = @{term \"x::nat\"}
   377   val trm = @{term \"(P::nat \<Rightarrow> bool) x\"}
   377   val trm = @{term \"(P::nat \<Rightarrow> bool) x\"}
   378 in
   378 in
   379   lambda x_nat trm
   379   lambda x_nat trm
   385   variable and for printing purposes also its name.  Note that because of the
   385   variable and for printing purposes also its name.  Note that because of the
   386   typing annotation on \<open>P\<close>, the variable \<open>x\<close> in \<open>P x\<close>
   386   typing annotation on \<open>P\<close>, the variable \<open>x\<close> in \<open>P x\<close>
   387   is of the same type as the abstracted variable. If it is of different type,
   387   is of the same type as the abstracted variable. If it is of different type,
   388   as in
   388   as in
   389 
   389 
   390   @{ML_response_fake [display,gray]
   390   @{ML_matchresult_fake [display,gray]
   391 "let
   391 "let
   392   val x_int = @{term \"x::int\"}
   392   val x_int = @{term \"x::int\"}
   393   val trm = @{term \"(P::nat \<Rightarrow> bool) x\"}
   393   val trm = @{term \"(P::nat \<Rightarrow> bool) x\"}
   394 in
   394 in
   395   lambda x_int trm
   395   lambda x_int trm
   404   There is also the function @{ML_ind subst_free in Term} with which terms can be
   404   There is also the function @{ML_ind subst_free in Term} with which terms can be
   405   replaced by other terms. For example below, we will replace in @{term
   405   replaced by other terms. For example below, we will replace in @{term
   406   "(f::nat \<Rightarrow> nat \<Rightarrow> nat) 0 x"} the subterm @{term "(f::nat \<Rightarrow> nat \<Rightarrow> nat) 0"} by
   406   "(f::nat \<Rightarrow> nat \<Rightarrow> nat) 0 x"} the subterm @{term "(f::nat \<Rightarrow> nat \<Rightarrow> nat) 0"} by
   407   @{term y}, and @{term x} by @{term True}.
   407   @{term y}, and @{term x} by @{term True}.
   408 
   408 
   409   @{ML_response_fake [display,gray]
   409   @{ML_matchresult_fake [display,gray]
   410 "let
   410 "let
   411   val sub1 = (@{term \"(f::nat \<Rightarrow> nat \<Rightarrow> nat) 0\"}, @{term \"y::nat \<Rightarrow> nat\"})
   411   val sub1 = (@{term \"(f::nat \<Rightarrow> nat \<Rightarrow> nat) 0\"}, @{term \"y::nat \<Rightarrow> nat\"})
   412   val sub2 = (@{term \"x::nat\"}, @{term \"True\"})
   412   val sub2 = (@{term \"x::nat\"}, @{term \"True\"})
   413   val trm = @{term \"((f::nat \<Rightarrow> nat \<Rightarrow> nat) 0) x\"}
   413   val trm = @{term \"((f::nat \<Rightarrow> nat \<Rightarrow> nat) 0) x\"}
   414 in
   414 in
   417   "Free (\"y\", \"nat \<Rightarrow> nat\") $ Const (\"True\", \"bool\")"}
   417   "Free (\"y\", \"nat \<Rightarrow> nat\") $ Const (\"True\", \"bool\")"}
   418 
   418 
   419   As can be seen, @{ML subst_free} does not take typability into account.
   419   As can be seen, @{ML subst_free} does not take typability into account.
   420   However it takes alpha-equivalence into account:
   420   However it takes alpha-equivalence into account:
   421 
   421 
   422   @{ML_response_fake [display, gray]
   422   @{ML_matchresult_fake [display, gray]
   423 "let
   423 "let
   424   val sub = (@{term \"(\<lambda>y::nat. y)\"}, @{term \"x::nat\"})
   424   val sub = (@{term \"(\<lambda>y::nat. y)\"}, @{term \"x::nat\"})
   425   val trm = @{term \"(\<lambda>x::nat. x)\"}
   425   val trm = @{term \"(\<lambda>x::nat. x)\"}
   426 in
   426 in
   427   subst_free [sub] trm
   427   subst_free [sub] trm
   444 
   444 
   445 text \<open>
   445 text \<open>
   446   The function returns a pair consisting of the stripped off variables and
   446   The function returns a pair consisting of the stripped off variables and
   447   the body of the universal quantification. For example
   447   the body of the universal quantification. For example
   448 
   448 
   449   @{ML_response_fake [display, gray]
   449   @{ML_matchresult_fake [display, gray]
   450   "strip_alls @{term \"\<forall>x y. x = (y::bool)\"}"
   450   "strip_alls @{term \"\<forall>x y. x = (y::bool)\"}"
   451 "([Free (\"x\", \"bool\"), Free (\"y\", \"bool\")],
   451 "([Free (\"x\", \"bool\"), Free (\"y\", \"bool\")],
   452   Const (\"op =\", _) $ Bound 1 $ Bound 0)"}
   452   Const (\"op =\", _) $ Bound 1 $ Bound 0)"}
   453 
   453 
   454   Note that we produced in the body two dangling de Bruijn indices. 
   454   Note that we produced in the body two dangling de Bruijn indices. 
   464 text \<open>
   464 text \<open>
   465   As said above, after calling @{ML strip_alls}, you obtain a term with loose
   465   As said above, after calling @{ML strip_alls}, you obtain a term with loose
   466   bound variables. With the function @{ML subst_bounds}, you can replace these
   466   bound variables. With the function @{ML subst_bounds}, you can replace these
   467   loose @{ML_ind Bound in Term}s with the stripped off variables.
   467   loose @{ML_ind Bound in Term}s with the stripped off variables.
   468 
   468 
   469   @{ML_response_fake [display, gray, linenos]
   469   @{ML_matchresult_fake [display, gray, linenos]
   470   "let
   470   "let
   471   val (vrs, trm) = strip_alls @{term \"\<forall>x y. x = (y::bool)\"}
   471   val (vrs, trm) = strip_alls @{term \"\<forall>x y. x = (y::bool)\"}
   472 in 
   472 in 
   473   subst_bounds (rev vrs, trm) 
   473   subst_bounds (rev vrs, trm) 
   474   |> pretty_term @{context}
   474   |> pretty_term @{context}
   486   name is by no means unique. If clashes need to be avoided, then we should
   486   name is by no means unique. If clashes need to be avoided, then we should
   487   use the function @{ML_ind dest_abs in Term}, which returns the body where
   487   use the function @{ML_ind dest_abs in Term}, which returns the body where
   488   the loose de Bruijn index is replaced by a unique free variable. For example
   488   the loose de Bruijn index is replaced by a unique free variable. For example
   489 
   489 
   490 
   490 
   491   @{ML_response_fake [display,gray]
   491   @{ML_matchresult_fake [display,gray]
   492   "let
   492   "let
   493   val body = Bound 0 $ Free (\"x\", @{typ nat})
   493   val body = Bound 0 $ Free (\"x\", @{typ nat})
   494 in
   494 in
   495   Term.dest_abs (\"x\", @{typ \"nat \<Rightarrow> bool\"}, body)
   495   Term.dest_abs (\"x\", @{typ \"nat \<Rightarrow> bool\"}, body)
   496 end"
   496 end"
   499   Sometimes it is necessary to manipulate de Bruijn indices in terms directly.
   499   Sometimes it is necessary to manipulate de Bruijn indices in terms directly.
   500   There are many functions to do this. We describe only two. The first,
   500   There are many functions to do this. We describe only two. The first,
   501   @{ML_ind incr_boundvars in Term}, increases by an integer the indices 
   501   @{ML_ind incr_boundvars in Term}, increases by an integer the indices 
   502   of the loose bound variables in a term. In the code below
   502   of the loose bound variables in a term. In the code below
   503 
   503 
   504 @{ML_response_fake [display,gray]
   504 @{ML_matchresult_fake [display,gray]
   505 "@{term \"\<forall>x y z u. z = u\"}
   505 "@{term \"\<forall>x y z u. z = u\"}
   506   |> strip_alls
   506   |> strip_alls
   507   ||> incr_boundvars 2
   507   ||> incr_boundvars 2
   508   |> build_alls
   508   |> build_alls
   509   |> pretty_term @{context}
   509   |> pretty_term @{context}
   517   between the first two quantified variables.
   517   between the first two quantified variables.
   518 
   518 
   519   The second function, @{ML_ind loose_bvar1 in Text}, tests whether a term
   519   The second function, @{ML_ind loose_bvar1 in Text}, tests whether a term
   520   contains a loose bound of a certain index. For example
   520   contains a loose bound of a certain index. For example
   521 
   521 
   522   @{ML_response_fake [gray,display]
   522   @{ML_matchresult_fake [gray,display]
   523 "let
   523 "let
   524   val body = snd (strip_alls @{term \"\<forall>x y. x = (y::bool)\"})
   524   val body = snd (strip_alls @{term \"\<forall>x y. x = (y::bool)\"})
   525 in
   525 in
   526   [loose_bvar1 (body, 0),
   526   [loose_bvar1 (body, 0),
   527    loose_bvar1 (body, 1),
   527    loose_bvar1 (body, 1),
   528    loose_bvar1 (body, 2)]
   528    loose_bvar1 (body, 2)]
   529 end"
   529 end"
   530   "[true, true, false]"}
   530   "[true, true, false]"}
   531 
   531 
   532   There are also many convenient functions that construct specific HOL-terms
   532   There are also many convenient functions that construct specific HOL-terms
   533   in the structure @{ML_struct HOLogic}. For example @{ML_ind mk_eq in
   533   in the structure @{ML_structure HOLogic}. For example @{ML_ind mk_eq in
   534   HOLogic} constructs an equality out of two terms.  The types needed in this
   534   HOLogic} constructs an equality out of two terms.  The types needed in this
   535   equality are calculated from the type of the arguments. For example
   535   equality are calculated from the type of the arguments. For example
   536 
   536 
   537 @{ML_response_fake [gray,display]
   537 @{ML_matchresult_fake [gray,display]
   538 "let
   538 "let
   539   val eq = HOLogic.mk_eq (@{term \"True\"}, @{term \"False\"})
   539   val eq = HOLogic.mk_eq (@{term \"True\"}, @{term \"False\"})
   540 in
   540 in
   541   eq |> pretty_term @{context}
   541   eq |> pretty_term @{context}
   542      |> pwriteln
   542      |> pwriteln
   567   | is_all _ = false\<close>
   567   | is_all _ = false\<close>
   568 
   568 
   569 text \<open>
   569 text \<open>
   570   will not correctly match the formula @{prop[source] "\<forall>x::nat. P x"}: 
   570   will not correctly match the formula @{prop[source] "\<forall>x::nat. P x"}: 
   571 
   571 
   572   @{ML_response [display,gray] "is_all @{term \"\<forall>x::nat. P x\"}" "false"}
   572   @{ML_matchresult [display,gray] "is_all @{term \"\<forall>x::nat. P x\"}" "false"}
   573 
   573 
   574   The problem is that the \<open>@term\<close>-antiquotation in the pattern 
   574   The problem is that the \<open>@term\<close>-antiquotation in the pattern 
   575   fixes the type of the constant @{term "All"} to be @{typ "('a \<Rightarrow> bool) \<Rightarrow> bool"} for 
   575   fixes the type of the constant @{term "All"} to be @{typ "('a \<Rightarrow> bool) \<Rightarrow> bool"} for 
   576   an arbitrary, but fixed type @{typ "'a"}. A properly working alternative 
   576   an arbitrary, but fixed type @{typ "'a"}. A properly working alternative 
   577   for this function is
   577   for this function is
   581   | is_all _ = false\<close>
   581   | is_all _ = false\<close>
   582 
   582 
   583 text \<open>
   583 text \<open>
   584   because now
   584   because now
   585 
   585 
   586   @{ML_response [display,gray] "is_all @{term \"\<forall>x::nat. P x\"}" "true"}
   586   @{ML_matchresult [display,gray] "is_all @{term \"\<forall>x::nat. P x\"}" "true"}
   587 
   587 
   588   matches correctly (the first wildcard in the pattern matches any type and the
   588   matches correctly (the first wildcard in the pattern matches any type and the
   589   second any term).
   589   second any term).
   590 
   590 
   591   However there is still a problem: consider the similar function that
   591   However there is still a problem: consider the similar function that
   596   | is_nil _ = false\<close>
   596   | is_nil _ = false\<close>
   597 
   597 
   598 text \<open>
   598 text \<open>
   599   Unfortunately, also this function does \emph{not} work as expected, since
   599   Unfortunately, also this function does \emph{not} work as expected, since
   600 
   600 
   601   @{ML_response [display,gray] "is_nil @{term \"Nil\"}" "false"}
   601   @{ML_matchresult [display,gray] "is_nil @{term \"Nil\"}" "false"}
   602 
   602 
   603   The problem is that on the ML-level the name of a constant is more
   603   The problem is that on the ML-level the name of a constant is more
   604   subtle than you might expect. The function @{ML is_all} worked correctly,
   604   subtle than you might expect. The function @{ML is_all} worked correctly,
   605   because @{term "All"} is such a fundamental constant, which can be referenced
   605   because @{term "All"} is such a fundamental constant, which can be referenced
   606   by @{ML "Const (\"All\", some_type)" for some_type}. However, if you look at
   606   by @{ML "Const (\"All\", some_type)" for some_type}. However, if you look at
   607 
   607 
   608   @{ML_response [display,gray] "@{term \"Nil\"}" "Const (\"List.list.Nil\", _)"}
   608   @{ML_matchresult [display,gray] "@{term \"Nil\"}" "Const (\"List.list.Nil\", _)"}
   609 
   609 
   610   the name of the constant \<open>Nil\<close> depends on the theory in which the
   610   the name of the constant \<open>Nil\<close> depends on the theory in which the
   611   term constructor is defined (\<open>List\<close>) and also in which datatype
   611   term constructor is defined (\<open>List\<close>) and also in which datatype
   612   (\<open>list\<close>). Even worse, some constants have a name involving
   612   (\<open>list\<close>). Even worse, some constants have a name involving
   613   type-classes. Consider for example the constants for @{term "zero"} and
   613   type-classes. Consider for example the constants for @{term "zero"} and
   614   \mbox{@{term "times"}}:
   614   \mbox{@{term "times"}}:
   615 
   615 
   616   @{ML_response [display,gray] "(@{term \"0::nat\"}, @{term \"times\"})" 
   616   @{ML_matchresult [display,gray] "(@{term \"0::nat\"}, @{term \"times\"})" 
   617  "(Const (\"Groups.zero_class.zero\", _), 
   617  "(Const (\"Groups.zero_class.zero\", _), 
   618  Const (\"Groups.times_class.times\", _))"}
   618  Const (\"Groups.times_class.times\", _))"}
   619 
   619 
   620   While you could use the complete name, for example 
   620   While you could use the complete name, for example 
   621   @{ML "Const (\"List.list.Nil\", some_type)" for some_type}, for referring to or
   621   @{ML "Const (\"List.list.Nil\", some_type)" for some_type}, for referring to or
   634 
   634 
   635 text \<open>
   635 text \<open>
   636   The antiquotation for properly referencing type constants is \<open>@{type_name \<dots>}\<close>.
   636   The antiquotation for properly referencing type constants is \<open>@{type_name \<dots>}\<close>.
   637   For example
   637   For example
   638 
   638 
   639   @{ML_response [display,gray]
   639   @{ML_matchresult [display,gray]
   640   "@{type_name \"list\"}" "\"List.list\""}
   640   "@{type_name \"list\"}" "\"List.list\""}
   641 
   641 
   642   Although types of terms can often be inferred, there are many
   642   Although types of terms can often be inferred, there are many
   643   situations where you need to construct types manually, especially  
   643   situations where you need to construct types manually, especially  
   644   when defining constants. For example the function returning a function 
   644   when defining constants. For example the function returning a function 
   672    | _ => ty)\<close>
   672    | _ => ty)\<close>
   673 
   673 
   674 text \<open>
   674 text \<open>
   675   Here is an example:
   675   Here is an example:
   676 
   676 
   677 @{ML_response_fake [display,gray] 
   677 @{ML_matchresult_fake [display,gray] 
   678 "map_types nat_to_int @{term \"a = (1::nat)\"}" 
   678 "map_types nat_to_int @{term \"a = (1::nat)\"}" 
   679 "Const (\"op =\", \"int \<Rightarrow> int \<Rightarrow> bool\")
   679 "Const (\"op =\", \"int \<Rightarrow> int \<Rightarrow> bool\")
   680            $ Free (\"a\", \"int\") $ Const (\"HOL.one_class.one\", \"int\")"}
   680            $ Free (\"a\", \"int\") $ Const (\"HOL.one_class.one\", \"int\")"}
   681 
   681 
   682   If you want to obtain the list of free type-variables of a term, you
   682   If you want to obtain the list of free type-variables of a term, you
   689 
   689 
   690   that is they take, besides a term, also a list of type-variables as input. 
   690   that is they take, besides a term, also a list of type-variables as input. 
   691   So in order to obtain the list of type-variables of a term you have to 
   691   So in order to obtain the list of type-variables of a term you have to 
   692   call them as follows
   692   call them as follows
   693 
   693 
   694   @{ML_response [gray,display]
   694   @{ML_matchresult [gray,display]
   695   "Term.add_tfrees @{term \"(a, b)\"} []"
   695   "Term.add_tfrees @{term \"(a, b)\"} []"
   696   "[(\"'b\", [\"HOL.type\"]), (\"'a\", [\"HOL.type\"])]"}
   696   "[(\"'b\", [\"HOL.type\"]), (\"'a\", [\"HOL.type\"])]"}
   697 
   697 
   698   The reason for this definition is that @{ML add_tfrees in Term} can
   698   The reason for this definition is that @{ML add_tfrees in Term} can
   699   be easily folded over a list of terms. Similarly for all functions
   699   be easily folded over a list of terms. Similarly for all functions
   774   schematic variables.
   774   schematic variables.
   775 
   775 
   776   Let us begin with describing the unification and matching functions for
   776   Let us begin with describing the unification and matching functions for
   777   types.  Both return type environments (ML-type @{ML_type "Type.tyenv"})
   777   types.  Both return type environments (ML-type @{ML_type "Type.tyenv"})
   778   which map schematic type variables to types and sorts. Below we use the
   778   which map schematic type variables to types and sorts. Below we use the
   779   function @{ML_ind typ_unify in Sign} from the structure @{ML_struct Sign}
   779   function @{ML_ind typ_unify in Sign} from the structure @{ML_structure Sign}
   780   for unifying the types \<open>?'a * ?'b\<close> and \<open>?'b list *
   780   for unifying the types \<open>?'a * ?'b\<close> and \<open>?'b list *
   781   nat\<close>. This will produce the mapping, or type environment, \<open>[?'a :=
   781   nat\<close>. This will produce the mapping, or type environment, \<open>[?'a :=
   782   ?'b list, ?'b := nat]\<close>.
   782   ?'b list, ?'b := nat]\<close>.
   783 \<close>
   783 \<close>
   784 
   784 
   794   environment, which is needed for starting the unification without any
   794   environment, which is needed for starting the unification without any
   795   (pre)instantiations. The \<open>0\<close> is an integer index that will be explained
   795   (pre)instantiations. The \<open>0\<close> is an integer index that will be explained
   796   below. In case of failure, @{ML typ_unify in Sign} will raise the exception
   796   below. In case of failure, @{ML typ_unify in Sign} will raise the exception
   797   \<open>TUNIFY\<close>.  We can print out the resulting type environment bound to 
   797   \<open>TUNIFY\<close>.  We can print out the resulting type environment bound to 
   798   @{ML tyenv_unif} with the built-in function @{ML_ind dest in Vartab} from the
   798   @{ML tyenv_unif} with the built-in function @{ML_ind dest in Vartab} from the
   799   structure @{ML_struct Vartab}.
   799   structure @{ML_structure Vartab}.
   800 
   800 
   801   @{ML_response_fake [display,gray]
   801   @{ML_matchresult_fake [display,gray]
   802   "Vartab.dest tyenv_unif"
   802   "Vartab.dest tyenv_unif"
   803   "[((\"'a\", 0), ([\"HOL.type\"], \"?'b List.list\")), 
   803   "[((\"'a\", 0), ([\"HOL.type\"], \"?'b List.list\")), 
   804  ((\"'b\", 0), ([\"HOL.type\"], \"nat\"))]"} 
   804  ((\"'b\", 0), ([\"HOL.type\"], \"nat\"))]"} 
   805 \<close>
   805 \<close>
   806 
   806 
   837   use in what follows our own pretty-printing function from
   837   use in what follows our own pretty-printing function from
   838   Figure~\ref{fig:prettyenv} for @{ML_type "Type.tyenv"}s. For the type
   838   Figure~\ref{fig:prettyenv} for @{ML_type "Type.tyenv"}s. For the type
   839   environment in the example this function prints out the more legible:
   839   environment in the example this function prints out the more legible:
   840 
   840 
   841 
   841 
   842   @{ML_response_fake [display, gray]
   842   @{ML_matchresult_fake [display, gray]
   843   "pretty_tyenv @{context} tyenv_unif"
   843   "pretty_tyenv @{context} tyenv_unif"
   844   "[?'a := ?'b list, ?'b := nat]"}
   844   "[?'a := ?'b list, ?'b := nat]"}
   845 
   845 
   846   The way the unification function @{ML typ_unify in Sign} is implemented 
   846   The way the unification function @{ML typ_unify in Sign} is implemented 
   847   using an initial type environment and initial index makes it easy to
   847   using an initial type environment and initial index makes it easy to
   880 text \<open>
   880 text \<open>
   881   To print out the result type environment we switch on the printing 
   881   To print out the result type environment we switch on the printing 
   882   of sort information by setting @{ML_ind show_sorts in Syntax} to 
   882   of sort information by setting @{ML_ind show_sorts in Syntax} to 
   883   true. This allows us to inspect the typing environment.
   883   true. This allows us to inspect the typing environment.
   884 
   884 
   885   @{ML_response_fake [display,gray]
   885   @{ML_matchresult_fake [display,gray]
   886   "pretty_tyenv @{context} tyenv"
   886   "pretty_tyenv @{context} tyenv"
   887   "[?'a::s1 := ?'a1::{s1, s2}, ?'b::s2 := ?'a1::{s1, s2}]"}
   887   "[?'a::s1 := ?'a1::{s1, s2}, ?'b::s2 := ?'a1::{s1, s2}]"}
   888 
   888 
   889   As can be seen, the type variables \<open>?'a\<close> and \<open>?'b\<close> are instantiated
   889   As can be seen, the type variables \<open>?'a\<close> and \<open>?'b\<close> are instantiated
   890   with a new type variable \<open>?'a1\<close> with sort \<open>{s1, s2}\<close>. Since a new
   890   with a new type variable \<open>?'a1\<close> with sort \<open>{s1, s2}\<close>. Since a new
   891   type variable has been introduced the @{ML index}, originally being \<open>0\<close>, 
   891   type variable has been introduced the @{ML index}, originally being \<open>0\<close>, 
   892   has been increased to \<open>1\<close>.
   892   has been increased to \<open>1\<close>.
   893 
   893 
   894   @{ML_response [display,gray]
   894   @{ML_matchresult [display,gray]
   895   "index"
   895   "index"
   896   "1"}
   896   "1"}
   897 
   897 
   898   Let us now return to the unification problem \<open>?'a * ?'b\<close> and 
   898   Let us now return to the unification problem \<open>?'a * ?'b\<close> and 
   899   \<open>?'b list * nat\<close> from the beginning of this section, and the 
   899   \<open>?'b list * nat\<close> from the beginning of this section, and the 
   900   calculated type environment @{ML tyenv_unif}:
   900   calculated type environment @{ML tyenv_unif}:
   901 
   901 
   902   @{ML_response_fake [display, gray]
   902   @{ML_matchresult_fake [display, gray]
   903   "pretty_tyenv @{context} tyenv_unif"
   903   "pretty_tyenv @{context} tyenv_unif"
   904   "[?'a := ?'b list, ?'b := nat]"}
   904   "[?'a := ?'b list, ?'b := nat]"}
   905 
   905 
   906   Observe that the type environment which the function @{ML typ_unify in
   906   Observe that the type environment which the function @{ML typ_unify in
   907   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
   907   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
   909   called an instantiation in \emph{triangular form}. These triangular 
   909   called an instantiation in \emph{triangular form}. These triangular 
   910   instantiations, or triangular type environments, are used because of 
   910   instantiations, or triangular type environments, are used because of 
   911   performance reasons. To apply such a type environment to a type, say \<open>?'a *
   911   performance reasons. To apply such a type environment to a type, say \<open>?'a *
   912   ?'b\<close>, you should use the function @{ML_ind norm_type in Envir}:
   912   ?'b\<close>, you should use the function @{ML_ind norm_type in Envir}:
   913 
   913 
   914   @{ML_response_fake [display, gray]
   914   @{ML_matchresult_fake [display, gray]
   915   "Envir.norm_type tyenv_unif @{typ_pat \"?'a * ?'b\"}"
   915   "Envir.norm_type tyenv_unif @{typ_pat \"?'a * ?'b\"}"
   916   "nat list * nat"}
   916   "nat list * nat"}
   917 
   917 
   918   Matching of types can be done with the function @{ML_ind typ_match in Sign}
   918   Matching of types can be done with the function @{ML_ind typ_match in Sign}
   919   also from the structure @{ML_struct Sign}. This function returns a @{ML_type
   919   also from the structure @{ML_structure Sign}. This function returns a @{ML_type
   920   Type.tyenv} as well, but might raise the exception \<open>TYPE_MATCH\<close> in case
   920   Type.tyenv} as well, but might raise the exception \<open>TYPE_MATCH\<close> in case
   921   of failure. For example
   921   of failure. For example
   922 \<close>
   922 \<close>
   923 
   923 
   924 ML %grayML\<open>val tyenv_match = let
   924 ML %grayML\<open>val tyenv_match = let
   929 end\<close>
   929 end\<close>
   930 
   930 
   931 text \<open>
   931 text \<open>
   932   Printing out the calculated matcher gives
   932   Printing out the calculated matcher gives
   933 
   933 
   934   @{ML_response_fake [display,gray]
   934   @{ML_matchresult_fake [display,gray]
   935   "pretty_tyenv @{context} tyenv_match"
   935   "pretty_tyenv @{context} tyenv_match"
   936   "[?'a := bool list, ?'b := nat]"}
   936   "[?'a := bool list, ?'b := nat]"}
   937   
   937   
   938   Unlike unification, which uses the function @{ML norm_type in Envir}, 
   938   Unlike unification, which uses the function @{ML norm_type in Envir}, 
   939   applying the matcher to a type needs to be done with the function
   939   applying the matcher to a type needs to be done with the function
   940   @{ML_ind subst_type in Envir}. For example
   940   @{ML_ind subst_type in Envir}. For example
   941 
   941 
   942   @{ML_response_fake [display, gray]
   942   @{ML_matchresult_fake [display, gray]
   943   "Envir.subst_type tyenv_match @{typ_pat \"?'a * ?'b\"}"
   943   "Envir.subst_type tyenv_match @{typ_pat \"?'a * ?'b\"}"
   944   "bool list * nat"}
   944   "bool list * nat"}
   945 
   945 
   946   Be careful to observe the difference: always use
   946   Be careful to observe the difference: always use
   947   @{ML subst_type in Envir} for matchers and @{ML norm_type in Envir} 
   947   @{ML subst_type in Envir} for matchers and @{ML norm_type in Envir} 
   958 
   958 
   959 text \<open>
   959 text \<open>
   960   Now @{ML tyenv_unif} is equal to @{ML tyenv_match'}. If we apply 
   960   Now @{ML tyenv_unif} is equal to @{ML tyenv_match'}. If we apply 
   961   @{ML norm_type in Envir} to the type \<open>?'a * ?'b\<close> we obtain
   961   @{ML norm_type in Envir} to the type \<open>?'a * ?'b\<close> we obtain
   962 
   962 
   963   @{ML_response_fake [display, gray]
   963   @{ML_matchresult_fake [display, gray]
   964   "Envir.norm_type tyenv_match' @{typ_pat \"?'a * ?'b\"}"
   964   "Envir.norm_type tyenv_match' @{typ_pat \"?'a * ?'b\"}"
   965   "nat list * nat"}
   965   "nat list * nat"}
   966 
   966 
   967   which does not solve the matching problem, and if
   967   which does not solve the matching problem, and if
   968   we apply @{ML subst_type in Envir} to the same type we obtain
   968   we apply @{ML subst_type in Envir} to the same type we obtain
   969 
   969 
   970   @{ML_response_fake [display, gray]
   970   @{ML_matchresult_fake [display, gray]
   971   "Envir.subst_type tyenv_unif @{typ_pat \"?'a * ?'b\"}"
   971   "Envir.subst_type tyenv_unif @{typ_pat \"?'a * ?'b\"}"
   972   "?'b list * nat"}
   972   "?'b list * nat"}
   973   
   973   
   974   which does not solve the unification problem.
   974   which does not solve the unification problem.
   975 
   975 
  1021 text \<open>
  1021 text \<open>
  1022   In this example we annotated types explicitly because then 
  1022   In this example we annotated types explicitly because then 
  1023   the type environment is empty and can be ignored. The 
  1023   the type environment is empty and can be ignored. The 
  1024   resulting term environment is
  1024   resulting term environment is
  1025 
  1025 
  1026   @{ML_response_fake [display, gray]
  1026   @{ML_matchresult_fake [display, gray]
  1027   "pretty_env @{context} fo_env"
  1027   "pretty_env @{context} fo_env"
  1028   "[?X := P, ?Y := \<lambda>a b. Q b a]"}
  1028   "[?X := P, ?Y := \<lambda>a b. Q b a]"}
  1029 
  1029 
  1030   The matcher can be applied to a term using the function @{ML_ind subst_term
  1030   The matcher can be applied to a term using the function @{ML_ind subst_term
  1031   in Envir} (remember the same convention for types applies to terms: @{ML
  1031   in Envir} (remember the same convention for types applies to terms: @{ML
  1032   subst_term in Envir} is for matchers and @{ML norm_term in Envir} for
  1032   subst_term in Envir} is for matchers and @{ML norm_term in Envir} for
  1033   unifiers). The function @{ML subst_term in Envir} expects a type environment,
  1033   unifiers). The function @{ML subst_term in Envir} expects a type environment,
  1034   which is set to empty in the example below, and a term environment.
  1034   which is set to empty in the example below, and a term environment.
  1035 
  1035 
  1036   @{ML_response_fake [display, gray]
  1036   @{ML_matchresult_fake [display, gray]
  1037   "let
  1037   "let
  1038   val trm = @{term_pat \"(?X::(nat\<Rightarrow>nat\<Rightarrow>nat)\<Rightarrow>bool) ?Y\"}
  1038   val trm = @{term_pat \"(?X::(nat\<Rightarrow>nat\<Rightarrow>nat)\<Rightarrow>bool) ?Y\"}
  1039 in
  1039 in
  1040   Envir.subst_term (Vartab.empty, fo_env) trm
  1040   Envir.subst_term (Vartab.empty, fo_env) trm
  1041   |> pretty_term @{context}
  1041   |> pretty_term @{context}
  1048   alpha-equivalence, but this kind of matching should be used with care, since
  1048   alpha-equivalence, but this kind of matching should be used with care, since
  1049   it is not clear whether the result is meaningful. A meaningful example is
  1049   it is not clear whether the result is meaningful. A meaningful example is
  1050   matching \<open>\<lambda>x. P x\<close> against the pattern \<open>\<lambda>y. ?X y\<close>. In this
  1050   matching \<open>\<lambda>x. P x\<close> against the pattern \<open>\<lambda>y. ?X y\<close>. In this
  1051   case, first-order matching produces \<open>[?X := P]\<close>.
  1051   case, first-order matching produces \<open>[?X := P]\<close>.
  1052 
  1052 
  1053   @{ML_response_fake [display, gray]
  1053   @{ML_matchresult_fake [display, gray]
  1054   "let
  1054   "let
  1055   val fo_pat = @{term_pat \"\<lambda>y. (?X::nat\<Rightarrow>bool) y\"}
  1055   val fo_pat = @{term_pat \"\<lambda>y. (?X::nat\<Rightarrow>bool) y\"}
  1056   val trm = @{term \"\<lambda>x. (P::nat\<Rightarrow>bool) x\"} 
  1056   val trm = @{term \"\<lambda>x. (P::nat\<Rightarrow>bool) x\"} 
  1057   val init = (Vartab.empty, Vartab.empty) 
  1057   val init = (Vartab.empty, Vartab.empty) 
  1058 in
  1058 in
  1069   \emph{\index*{pattern}} is a well-formed term in which the arguments to
  1069   \emph{\index*{pattern}} is a well-formed term in which the arguments to
  1070   every schematic variable are distinct bounds.
  1070   every schematic variable are distinct bounds.
  1071   In particular this excludes terms where a
  1071   In particular this excludes terms where a
  1072   schematic variable is an argument of another one and where a schematic
  1072   schematic variable is an argument of another one and where a schematic
  1073   variable is applied twice with the same bound variable. The function
  1073   variable is applied twice with the same bound variable. The function
  1074   @{ML_ind pattern in Pattern} in the structure @{ML_struct Pattern} tests
  1074   @{ML_ind pattern in Pattern} in the structure @{ML_structure Pattern} tests
  1075   whether a term satisfies these restrictions under the assumptions
  1075   whether a term satisfies these restrictions under the assumptions
  1076   that it is beta-normal, well-typed and has no loose bound variables.
  1076   that it is beta-normal, well-typed and has no loose bound variables.
  1077 
  1077 
  1078   @{ML_response [display, gray]
  1078   @{ML_matchresult [display, gray]
  1079   "let
  1079   "let
  1080   val trm_list = 
  1080   val trm_list = 
  1081         [@{term_pat \"?X\"}, @{term_pat \"a\"},
  1081         [@{term_pat \"?X\"}, @{term_pat \"a\"},
  1082          @{term_pat \"f (\<lambda>a b. ?X a b) c\"},
  1082          @{term_pat \"f (\<lambda>a b. ?X a b) c\"},
  1083          @{term_pat \"\<lambda>a b. (+) a b\"},
  1083          @{term_pat \"\<lambda>a b. (+) a b\"},
  1097   In this way, matching and unification can be implemented as functions that 
  1097   In this way, matching and unification can be implemented as functions that 
  1098   produce a type and term environment (unification actually returns a 
  1098   produce a type and term environment (unification actually returns a 
  1099   record of type @{ML_type Envir.env} containing a max-index, a type environment 
  1099   record of type @{ML_type Envir.env} containing a max-index, a type environment 
  1100   and a term environment). The corresponding functions are @{ML_ind match in Pattern}
  1100   and a term environment). The corresponding functions are @{ML_ind match in Pattern}
  1101   and @{ML_ind unify in Pattern}, both implemented in the structure
  1101   and @{ML_ind unify in Pattern}, both implemented in the structure
  1102   @{ML_struct Pattern}. An example for higher-order pattern unification is
  1102   @{ML_structure Pattern}. An example for higher-order pattern unification is
  1103 
  1103 
  1104   @{ML_response_fake [display, gray]
  1104   @{ML_matchresult_fake [display, gray]
  1105   "let
  1105   "let
  1106   val trm1 = @{term_pat \"\<lambda>x y. g (?X y x) (f (?Y x))\"}
  1106   val trm1 = @{term_pat \"\<lambda>x y. g (?X y x) (f (?Y x))\"}
  1107   val trm2 = @{term_pat \"\<lambda>u v. g u (f u)\"}
  1107   val trm2 = @{term_pat \"\<lambda>u v. g u (f u)\"}
  1108   val init = Envir.empty 0
  1108   val init = Envir.empty 0
  1109   val env = Pattern.unify (Context.Proof @{context}) (trm1, trm2) init (* FIXME: Reference to generic context *)
  1109   val env = Pattern.unify (Context.Proof @{context}) (trm1, trm2) init (* FIXME: Reference to generic context *)
  1150 text \<open>
  1150 text \<open>
  1151   \footnote{\bf FIXME: what is the list of term pairs in the unifier: flex-flex pairs?}
  1151   \footnote{\bf FIXME: what is the list of term pairs in the unifier: flex-flex pairs?}
  1152 
  1152 
  1153   We can print them out as follows.
  1153   We can print them out as follows.
  1154 
  1154 
  1155   @{ML_response_fake [display, gray]
  1155   @{ML_matchresult_fake [display, gray]
  1156   "pretty_env @{context} (Envir.term_env un1);
  1156   "pretty_env @{context} (Envir.term_env un1);
  1157 pretty_env @{context} (Envir.term_env un2);
  1157 pretty_env @{context} (Envir.term_env un2);
  1158 pretty_env @{context} (Envir.term_env un3)"
  1158 pretty_env @{context} (Envir.term_env un3)"
  1159   "[?X := \<lambda>a. a, ?Y := f a]
  1159   "[?X := \<lambda>a. a, ?Y := f a]
  1160 [?X := f, ?Y := a]
  1160 [?X := f, ?Y := a]
  1162 
  1162 
  1163 
  1163 
  1164   In case of failure the function @{ML_ind unifiers in Unify} does not raise
  1164   In case of failure the function @{ML_ind unifiers in Unify} does not raise
  1165   an exception, rather returns the empty sequence. For example
  1165   an exception, rather returns the empty sequence. For example
  1166 
  1166 
  1167   @{ML_response [display, gray]
  1167   @{ML_matchresult [display, gray]
  1168 "let 
  1168 "let 
  1169   val trm1 = @{term \"a\"}
  1169   val trm1 = @{term \"a\"}
  1170   val trm2 = @{term \"b\"}
  1170   val trm2 = @{term \"b\"}
  1171   val init = Envir.empty 0
  1171   val init = Envir.empty 0
  1172 in
  1172 in
  1179   also tries first to solve the problem by higher-order pattern
  1179   also tries first to solve the problem by higher-order pattern
  1180   unification. Only in case of failure full higher-order unification is
  1180   unification. Only in case of failure full higher-order unification is
  1181   called. This function has a built-in bound, which can be accessed and
  1181   called. This function has a built-in bound, which can be accessed and
  1182   manipulated as a configuration value. For example
  1182   manipulated as a configuration value. For example
  1183 
  1183 
  1184   @{ML_response_fake [display,gray]
  1184   @{ML_matchresult_fake [display,gray]
  1185   "Config.get_global @{theory} (Unify.search_bound)"
  1185   "Config.get_global @{theory} (Unify.search_bound)"
  1186   "Int 60"}
  1186   "Int 60"}
  1187 
  1187 
  1188   If this bound is reached during unification, Isabelle prints out the
  1188   If this bound is reached during unification, Isabelle prints out the
  1189   warning message @{text [quotes] "Unification bound exceeded"} and
  1189   warning message @{text [quotes] "Unification bound exceeded"} and
  1190   plenty of diagnostic information (sometimes annoyingly plenty of 
  1190   plenty of diagnostic information (sometimes annoyingly plenty of 
  1191   information). 
  1191   information). 
  1192 
  1192 
  1193 
  1193 
  1194   For higher-order matching the function is called @{ML_ind matchers in Unify}
  1194   For higher-order matching the function is called @{ML_ind matchers in Unify}
  1195   implemented in the structure @{ML_struct Unify}. Also this function returns
  1195   implemented in the structure @{ML_structure Unify}. Also this function returns
  1196   sequences with possibly more than one matcher.  Like @{ML unifiers in
  1196   sequences with possibly more than one matcher.  Like @{ML unifiers in
  1197   Unify}, this function does not raise an exception in case of failure, but
  1197   Unify}, this function does not raise an exception in case of failure, but
  1198   returns an empty sequence. It also first tries out whether the matching
  1198   returns an empty sequence. It also first tries out whether the matching
  1199   problem can be solved by first-order matching.
  1199   problem can be solved by first-order matching.
  1200 
  1200 
  1211   as an introduction rule. Applying it directly can lead to unexpected
  1211   as an introduction rule. Applying it directly can lead to unexpected
  1212   behaviour since the unification has more than one solution. One way round
  1212   behaviour since the unification has more than one solution. One way round
  1213   this problem is to instantiate the schematic variables \<open>?P\<close> and
  1213   this problem is to instantiate the schematic variables \<open>?P\<close> and
  1214   \<open>?x\<close>.  Instantiation function for theorems is 
  1214   \<open>?x\<close>.  Instantiation function for theorems is 
  1215   @{ML_ind instantiate_normalize in Drule} from the structure 
  1215   @{ML_ind instantiate_normalize in Drule} from the structure 
  1216   @{ML_struct Drule}. One problem, however, is
  1216   @{ML_structure Drule}. One problem, however, is
  1217   that this function expects the instantiations as lists of @{ML_type "((indexname * sort) * ctyp)"}
  1217   that this function expects the instantiations as lists of @{ML_type "((indexname * sort) * ctyp)"}
  1218   respective @{ML_type "(indexname * typ) * cterm"}:
  1218   respective @{ML_type "(indexname * typ) * cterm"}:
  1219 
  1219 
  1220   \begin{isabelle}
  1220   \begin{isabelle}
  1221   @{ML instantiate_normalize in Drule}\<open>:\<close>
  1221   @{ML instantiate_normalize in Drule}\<open>:\<close>
  1264   environments (Line 8). As a simple example we instantiate the
  1264   environments (Line 8). As a simple example we instantiate the
  1265   @{thm [source] spec} rule so that its conclusion is of the form 
  1265   @{thm [source] spec} rule so that its conclusion is of the form 
  1266   @{term "Q True"}. 
  1266   @{term "Q True"}. 
  1267  
  1267  
  1268 
  1268 
  1269   @{ML_response_fake [gray,display,linenos] 
  1269   @{ML_matchresult_fake [gray,display,linenos] 
  1270   "let  
  1270   "let  
  1271   val pat = Logic.strip_imp_concl (Thm.prop_of @{thm spec})
  1271   val pat = Logic.strip_imp_concl (Thm.prop_of @{thm spec})
  1272   val trm = @{term \"Trueprop (Q True)\"}
  1272   val trm = @{term \"Trueprop (Q True)\"}
  1273   val inst = matcher_inst @{context} pat trm 1
  1273   val inst = matcher_inst @{context} pat trm 1
  1274 in
  1274 in
  1352   enough typing information (constants, free variables and abstractions all have typing 
  1352   enough typing information (constants, free variables and abstractions all have typing 
  1353   information) so that it is always clear what the type of a term is. 
  1353   information) so that it is always clear what the type of a term is. 
  1354   Given a well-typed term, the function @{ML_ind type_of in Term} returns the 
  1354   Given a well-typed term, the function @{ML_ind type_of in Term} returns the 
  1355   type of a term. Consider for example:
  1355   type of a term. Consider for example:
  1356 
  1356 
  1357   @{ML_response [display,gray] 
  1357   @{ML_matchresult [display,gray] 
  1358   "type_of (@{term \"f::nat \<Rightarrow> bool\"} $ @{term \"x::nat\"})" "bool"}
  1358   "type_of (@{term \"f::nat \<Rightarrow> bool\"} $ @{term \"x::nat\"})" "bool"}
  1359 
  1359 
  1360   To calculate the type, this function traverses the whole term and will
  1360   To calculate the type, this function traverses the whole term and will
  1361   detect any typing inconsistency. For example changing the type of the variable 
  1361   detect any typing inconsistency. For example changing the type of the variable 
  1362   @{term "x"} from @{typ "nat"} to @{typ "int"} will result in the error message: 
  1362   @{term "x"} from @{typ "nat"} to @{typ "int"} will result in the error message: 
  1363 
  1363 
  1364   @{ML_response_fake [display,gray] 
  1364   @{ML_matchresult_fake [display,gray] 
  1365   "type_of (@{term \"f::nat \<Rightarrow> bool\"} $ @{term \"x::int\"})" 
  1365   "type_of (@{term \"f::nat \<Rightarrow> bool\"} $ @{term \"x::int\"})" 
  1366   "*** Exception- TYPE (\"type_of: type mismatch in application\" \<dots>"}
  1366   "*** Exception- TYPE (\"type_of: type mismatch in application\" \<dots>"}
  1367 
  1367 
  1368   Since the complete traversal might sometimes be too costly and
  1368   Since the complete traversal might sometimes be too costly and
  1369   not necessary, there is the function @{ML_ind fastype_of in Term}, which 
  1369   not necessary, there is the function @{ML_ind fastype_of in Term}, which 
  1370   also returns the type of a term.
  1370   also returns the type of a term.
  1371 
  1371 
  1372   @{ML_response [display,gray] 
  1372   @{ML_matchresult [display,gray] 
  1373   "fastype_of (@{term \"f::nat \<Rightarrow> bool\"} $ @{term \"x::nat\"})" "bool"}
  1373   "fastype_of (@{term \"f::nat \<Rightarrow> bool\"} $ @{term \"x::nat\"})" "bool"}
  1374 
  1374 
  1375   However, efficiency is gained on the expense of skipping some tests. You 
  1375   However, efficiency is gained on the expense of skipping some tests. You 
  1376   can see this in the following example
  1376   can see this in the following example
  1377 
  1377 
  1378    @{ML_response [display,gray] 
  1378    @{ML_matchresult [display,gray] 
  1379   "fastype_of (@{term \"f::nat \<Rightarrow> bool\"} $ @{term \"x::int\"})" "bool"}
  1379   "fastype_of (@{term \"f::nat \<Rightarrow> bool\"} $ @{term \"x::int\"})" "bool"}
  1380 
  1380 
  1381   where no error is detected.
  1381   where no error is detected.
  1382 
  1382 
  1383   Sometimes it is a bit inconvenient to construct a term with 
  1383   Sometimes it is a bit inconvenient to construct a term with 
  1385   information is redundant. A short-cut is to use the ``place-holder'' 
  1385   information is redundant. A short-cut is to use the ``place-holder'' 
  1386   type @{ML_ind dummyT in Term} and then let type-inference figure out the 
  1386   type @{ML_ind dummyT in Term} and then let type-inference figure out the 
  1387   complete type. The type inference can be invoked with the function
  1387   complete type. The type inference can be invoked with the function
  1388   @{ML_ind check_term in Syntax}. An example is as follows:
  1388   @{ML_ind check_term in Syntax}. An example is as follows:
  1389 
  1389 
  1390   @{ML_response_fake [display,gray] 
  1390   @{ML_matchresult_fake [display,gray] 
  1391 "let
  1391 "let
  1392   val c = Const (@{const_name \"plus\"}, dummyT) 
  1392   val c = Const (@{const_name \"plus\"}, dummyT) 
  1393   val o = @{term \"1::nat\"} 
  1393   val o = @{term \"1::nat\"} 
  1394   val v = Free (\"x\", dummyT)
  1394   val v = Free (\"x\", dummyT)
  1395 in   
  1395 in   
  1430   be constructed via ``official interfaces''.
  1430   be constructed via ``official interfaces''.
  1431 
  1431 
  1432   Certification is always relative to a context. For example you can 
  1432   Certification is always relative to a context. For example you can 
  1433   write:
  1433   write:
  1434 
  1434 
  1435   @{ML_response_fake [display,gray] 
  1435   @{ML_matchresult_fake [display,gray] 
  1436   "Thm.cterm_of @{context} @{term \"(a::nat) + b = c\"}" 
  1436   "Thm.cterm_of @{context} @{term \"(a::nat) + b = c\"}" 
  1437   "a + b = c"}
  1437   "a + b = c"}
  1438 
  1438 
  1439   This can also be written with an antiquotation:
  1439   This can also be written with an antiquotation:
  1440 
  1440 
  1441   @{ML_response_fake [display,gray] 
  1441   @{ML_matchresult_fake [display,gray] 
  1442   "@{cterm \"(a::nat) + b = c\"}" 
  1442   "@{cterm \"(a::nat) + b = c\"}" 
  1443   "a + b = c"}
  1443   "a + b = c"}
  1444 
  1444 
  1445   Attempting to obtain the certified term for
  1445   Attempting to obtain the certified term for
  1446 
  1446 
  1447   @{ML_response_fake_both [display,gray] 
  1447   @{ML_matchresult_fake_both [display,gray] 
  1448   "@{cterm \"1 + True\"}" 
  1448   "@{cterm \"1 + True\"}" 
  1449   "Type unification failed \<dots>"}
  1449   "Type unification failed \<dots>"}
  1450 
  1450 
  1451   yields an error (since the term is not typable). A slightly more elaborate
  1451   yields an error (since the term is not typable). A slightly more elaborate
  1452   example that type-checks is:
  1452   example that type-checks is:
  1453 
  1453 
  1454 @{ML_response_fake [display,gray] 
  1454 @{ML_matchresult_fake [display,gray] 
  1455 "let
  1455 "let
  1456   val natT = @{typ \"nat\"}
  1456   val natT = @{typ \"nat\"}
  1457   val zero = @{term \"0::nat\"}
  1457   val zero = @{term \"0::nat\"}
  1458   val plus = Const (@{const_name plus}, [natT, natT] ---> natT)
  1458   val plus = Const (@{const_name plus}, [natT, natT] ---> natT)
  1459 in
  1459 in
  1463 
  1463 
  1464   In Isabelle not just terms need to be certified, but also types. For example, 
  1464   In Isabelle not just terms need to be certified, but also types. For example, 
  1465   you obtain the certified type for the Isabelle type @{typ "nat \<Rightarrow> bool"} on 
  1465   you obtain the certified type for the Isabelle type @{typ "nat \<Rightarrow> bool"} on 
  1466   the ML-level as follows:
  1466   the ML-level as follows:
  1467 
  1467 
  1468   @{ML_response_fake [display,gray]
  1468   @{ML_matchresult_fake [display,gray]
  1469   "Thm.ctyp_of @{context} (@{typ nat} --> @{typ bool})"
  1469   "Thm.ctyp_of @{context} (@{typ nat} --> @{typ bool})"
  1470   "nat \<Rightarrow> bool"}
  1470   "nat \<Rightarrow> bool"}
  1471 
  1471 
  1472   or with the antiquotation:
  1472   or with the antiquotation:
  1473 
  1473 
  1474   @{ML_response_fake [display,gray]
  1474   @{ML_matchresult_fake [display,gray]
  1475   "@{ctyp \"nat \<Rightarrow> bool\"}"
  1475   "@{ctyp \"nat \<Rightarrow> bool\"}"
  1476   "nat \<Rightarrow> bool"}
  1476   "nat \<Rightarrow> bool"}
  1477 
  1477 
  1478   Since certified terms are, unlike terms, abstract objects, we cannot
  1478   Since certified terms are, unlike terms, abstract objects, we cannot
  1479   pattern-match against them. However, we can construct them. For example
  1479   pattern-match against them. However, we can construct them. For example
  1480   the function @{ML_ind apply in Thm} produces a certified application.
  1480   the function @{ML_ind apply in Thm} produces a certified application.
  1481 
  1481 
  1482   @{ML_response_fake [display,gray]
  1482   @{ML_matchresult_fake [display,gray]
  1483   "Thm.apply @{cterm \"P::nat \<Rightarrow> bool\"} @{cterm \"3::nat\"}"
  1483   "Thm.apply @{cterm \"P::nat \<Rightarrow> bool\"} @{cterm \"3::nat\"}"
  1484   "P 3"}
  1484   "P 3"}
  1485 
  1485 
  1486   Similarly the function @{ML_ind list_comb in Drule} from the structure @{ML_struct Drule}
  1486   Similarly the function @{ML_ind list_comb in Drule} from the structure @{ML_structure Drule}
  1487   applies a list of @{ML_type cterm}s.
  1487   applies a list of @{ML_type cterm}s.
  1488 
  1488 
  1489   @{ML_response_fake [display,gray]
  1489   @{ML_matchresult_fake [display,gray]
  1490   "let
  1490   "let
  1491   val chead = @{cterm \"P::unit \<Rightarrow> nat \<Rightarrow> bool\"}
  1491   val chead = @{cterm \"P::unit \<Rightarrow> nat \<Rightarrow> bool\"}
  1492   val cargs = [@{cterm \"()\"}, @{cterm \"3::nat\"}]
  1492   val cargs = [@{cterm \"()\"}, @{cterm \"3::nat\"}]
  1493 in
  1493 in
  1494   Drule.list_comb (chead, cargs)
  1494   Drule.list_comb (chead, cargs)
  1544   inserts necessary \<open>Trueprop\<close>s.
  1544   inserts necessary \<open>Trueprop\<close>s.
  1545 
  1545 
  1546   If we print out the value of @{ML my_thm} then we see only the 
  1546   If we print out the value of @{ML my_thm} then we see only the 
  1547   final statement of the theorem.
  1547   final statement of the theorem.
  1548 
  1548 
  1549   @{ML_response_fake [display, gray]
  1549   @{ML_matchresult_fake [display, gray]
  1550   "pwriteln (pretty_thm @{context} my_thm)"
  1550   "pwriteln (pretty_thm @{context} my_thm)"
  1551   "\<lbrakk>\<And>x. P x \<Longrightarrow> Q x; P t\<rbrakk> \<Longrightarrow> Q t"}
  1551   "\<lbrakk>\<And>x. P x \<Longrightarrow> Q x; P t\<rbrakk> \<Longrightarrow> Q t"}
  1552 
  1552 
  1553   However, internally the code-snippet constructs the following 
  1553   However, internally the code-snippet constructs the following 
  1554   proof.
  1554   proof.
  1568 
  1568 
  1569   While we obtained a theorem as result, this theorem is not
  1569   While we obtained a theorem as result, this theorem is not
  1570   yet stored in Isabelle's theorem database. Consequently, it cannot be 
  1570   yet stored in Isabelle's theorem database. Consequently, it cannot be 
  1571   referenced on the user level. One way to store it in the theorem database is
  1571   referenced on the user level. One way to store it in the theorem database is
  1572   by using the function @{ML_ind note in Local_Theory} from the structure 
  1572   by using the function @{ML_ind note in Local_Theory} from the structure 
  1573   @{ML_struct Local_Theory} (the Isabelle command
  1573   @{ML_structure Local_Theory} (the Isabelle command
  1574   \isacommand{local\_setup} will be explained in more detail in 
  1574   \isacommand{local\_setup} will be explained in more detail in 
  1575   Section~\ref{sec:local}).
  1575   Section~\ref{sec:local}).
  1576 \<close>
  1576 \<close>
  1577 
  1577 
  1578 (*FIXME: add forward reference to Proof_Context.export *)
  1578 (*FIXME: add forward reference to Proof_Context.export *)
  1604 
  1604 
  1605 text \<open>
  1605 text \<open>
  1606   Note that we have to use another name under which the theorem is stored,
  1606   Note that we have to use another name under which the theorem is stored,
  1607   since Isabelle does not allow us to call  @{ML_ind note in Local_Theory} twice
  1607   since Isabelle does not allow us to call  @{ML_ind note in Local_Theory} twice
  1608   with the same name. The attribute needs to be wrapped inside the function @{ML_ind
  1608   with the same name. The attribute needs to be wrapped inside the function @{ML_ind
  1609   internal in Attrib} from the structure @{ML_struct Attrib}. If we use the function 
  1609   internal in Attrib} from the structure @{ML_structure Attrib}. If we use the function 
  1610   @{ML get_thm_names_from_ss} from
  1610   @{ML get_thm_names_from_ss} from
  1611   the previous chapter, we can check whether the theorem has actually been
  1611   the previous chapter, we can check whether the theorem has actually been
  1612   added.
  1612   added.
  1613 
  1613 
  1614 
  1614 
  1615   @{ML_response [display,gray]
  1615   @{ML_matchresult [display,gray]
  1616   "let
  1616   "let
  1617   fun pred s = match_string \"my_thm_simp\" s
  1617   fun pred s = match_string \"my_thm_simp\" s
  1618 in
  1618 in
  1619   exists pred (get_thm_names_from_ss @{context})
  1619   exists pred (get_thm_names_from_ss @{context})
  1620 end"
  1620 end"
  1714   and   thm3: "\<forall>y. Q y" sorry
  1714   and   thm3: "\<forall>y. Q y" sorry
  1715 
  1715 
  1716 text \<open>
  1716 text \<open>
  1717   Testing them for alpha equality produces:
  1717   Testing them for alpha equality produces:
  1718 
  1718 
  1719   @{ML_response [display,gray]
  1719   @{ML_matchresult [display,gray]
  1720 "(Thm.eq_thm_prop (@{thm thm1}, @{thm thm2}),
  1720 "(Thm.eq_thm_prop (@{thm thm1}, @{thm thm2}),
  1721  Thm.eq_thm_prop (@{thm thm2}, @{thm thm3}))"
  1721  Thm.eq_thm_prop (@{thm thm2}, @{thm thm3}))"
  1722 "(true, false)"}
  1722 "(true, false)"}
  1723 
  1723 
  1724   Many functions destruct theorems into @{ML_type cterm}s. For example
  1724   Many functions destruct theorems into @{ML_type cterm}s. For example
  1725   the functions @{ML_ind lhs_of in Thm} and @{ML_ind rhs_of in Thm} return 
  1725   the functions @{ML_ind lhs_of in Thm} and @{ML_ind rhs_of in Thm} return 
  1726   the left and right-hand side, respectively, of a meta-equality.
  1726   the left and right-hand side, respectively, of a meta-equality.
  1727 
  1727 
  1728   @{ML_response_fake [display,gray]
  1728   @{ML_matchresult_fake [display,gray]
  1729   "let
  1729   "let
  1730   val eq = @{thm True_def}
  1730   val eq = @{thm True_def}
  1731 in
  1731 in
  1732   (Thm.lhs_of eq, Thm.rhs_of eq) 
  1732   (Thm.lhs_of eq, Thm.rhs_of eq) 
  1733   |> apply2 (Pretty.string_of o (pretty_cterm @{context}))
  1733   |> apply2 (Pretty.string_of o (pretty_cterm @{context}))
  1743   and   foo_test2: "A \<longrightarrow> B \<longrightarrow> C" sorry
  1743   and   foo_test2: "A \<longrightarrow> B \<longrightarrow> C" sorry
  1744 
  1744 
  1745 text \<open>
  1745 text \<open>
  1746   We can destruct them into premises and conclusions as follows. 
  1746   We can destruct them into premises and conclusions as follows. 
  1747 
  1747 
  1748  @{ML_response_fake [display,gray]
  1748  @{ML_matchresult_fake [display,gray]
  1749 "let
  1749 "let
  1750   val ctxt = @{context}
  1750   val ctxt = @{context}
  1751   fun prems_and_concl thm =
  1751   fun prems_and_concl thm =
  1752      [[Pretty.str \"Premises:\", pretty_terms ctxt (Thm.prems_of thm)], 
  1752      [[Pretty.str \"Premises:\", pretty_terms ctxt (Thm.prems_of thm)], 
  1753       [Pretty.str \"Conclusion:\", pretty_term ctxt (Thm.concl_of thm)]]
  1753       [Pretty.str \"Conclusion:\", pretty_term ctxt (Thm.concl_of thm)]]
  1776   Section~\ref{sec:simplifier}, the simplifier 
  1776   Section~\ref{sec:simplifier}, the simplifier 
  1777   can be used to work directly over theorems, for example to unfold definitions. To show
  1777   can be used to work directly over theorems, for example to unfold definitions. To show
  1778   this, we build the theorem @{term "True \<equiv> True"} (Line 1) and then 
  1778   this, we build the theorem @{term "True \<equiv> True"} (Line 1) and then 
  1779   unfold the constant @{term "True"} according to its definition (Line 2).
  1779   unfold the constant @{term "True"} according to its definition (Line 2).
  1780 
  1780 
  1781   @{ML_response_fake [display,gray,linenos]
  1781   @{ML_matchresult_fake [display,gray,linenos]
  1782   "Thm.reflexive @{cterm \"True\"}
  1782   "Thm.reflexive @{cterm \"True\"}
  1783   |> Simplifier.rewrite_rule @{context} [@{thm True_def}]
  1783   |> Simplifier.rewrite_rule @{context} [@{thm True_def}]
  1784   |> pretty_thm @{context}
  1784   |> pretty_thm @{context}
  1785   |> pwriteln"
  1785   |> pwriteln"
  1786   "(\<lambda>x. x) = (\<lambda>x. x) \<equiv> (\<lambda>x. x) = (\<lambda>x. x)"}
  1786   "(\<lambda>x. x) = (\<lambda>x. x) \<equiv> (\<lambda>x. x) = (\<lambda>x. x)"}
  1793   from the meta logic are more convenient for reasoning. Therefore there are
  1793   from the meta logic are more convenient for reasoning. Therefore there are
  1794   some build in functions which help with these transformations. The function 
  1794   some build in functions which help with these transformations. The function 
  1795   @{ML_ind rulify in Object_Logic} 
  1795   @{ML_ind rulify in Object_Logic} 
  1796   replaces all object connectives by equivalents in the meta logic. For example
  1796   replaces all object connectives by equivalents in the meta logic. For example
  1797 
  1797 
  1798   @{ML_response_fake [display, gray]
  1798   @{ML_matchresult_fake [display, gray]
  1799   "Object_Logic.rulify @{context} @{thm foo_test2}"
  1799   "Object_Logic.rulify @{context} @{thm foo_test2}"
  1800   "\<lbrakk>?A; ?B\<rbrakk> \<Longrightarrow> ?C"}
  1800   "\<lbrakk>?A; ?B\<rbrakk> \<Longrightarrow> ?C"}
  1801 
  1801 
  1802   The transformation in the other direction can be achieved with function
  1802   The transformation in the other direction can be achieved with function
  1803   @{ML_ind atomize in Object_Logic} and the following code.
  1803   @{ML_ind atomize in Object_Logic} and the following code.
  1804 
  1804 
  1805   @{ML_response_fake [display,gray]
  1805   @{ML_matchresult_fake [display,gray]
  1806   "let
  1806   "let
  1807   val thm = @{thm foo_test1}
  1807   val thm = @{thm foo_test1}
  1808   val meta_eq = Object_Logic.atomize @{context} (Thm.cprop_of thm)
  1808   val meta_eq = Object_Logic.atomize @{context} (Thm.cprop_of thm)
  1809 in
  1809 in
  1810   Raw_Simplifier.rewrite_rule @{context} [meta_eq] thm
  1810   Raw_Simplifier.rewrite_rule @{context} [meta_eq] thm
  1835 end\<close>
  1835 end\<close>
  1836 
  1836 
  1837 text \<open>
  1837 text \<open>
  1838   This function produces for the theorem @{thm [source] list.induct}
  1838   This function produces for the theorem @{thm [source] list.induct}
  1839 
  1839 
  1840   @{ML_response_fake [display, gray]
  1840   @{ML_matchresult_fake [display, gray]
  1841   "atomize_thm @{context} @{thm list.induct}"
  1841   "atomize_thm @{context} @{thm list.induct}"
  1842   "\<forall>P list. P [] \<longrightarrow> (\<forall>a list. P list \<longrightarrow> P (a # list)) \<longrightarrow> P list"}
  1842   "\<forall>P list. P [] \<longrightarrow> (\<forall>a list. P list \<longrightarrow> P (a # list)) \<longrightarrow> P list"}
  1843 
  1843 
  1844   Theorems can also be produced from terms by giving an explicit proof. 
  1844   Theorems can also be produced from terms by giving an explicit proof. 
  1845   One way to achieve this is by using the function @{ML_ind prove in Goal}
  1845   One way to achieve this is by using the function @{ML_ind prove in Goal}
  1846   in the structure @{ML_struct Goal}. For example below we use this function
  1846   in the structure @{ML_structure Goal}. For example below we use this function
  1847   to prove the term @{term "P \<Longrightarrow> P"}.
  1847   to prove the term @{term "P \<Longrightarrow> P"}.
  1848   
  1848   
  1849   @{ML_response_fake [display,gray]
  1849   @{ML_matchresult_fake [display,gray]
  1850   "let
  1850   "let
  1851   val trm = @{term \"P \<Longrightarrow> P::bool\"}
  1851   val trm = @{term \"P \<Longrightarrow> P::bool\"}
  1852   val tac = K (assume_tac @{context} 1)
  1852   val tac = K (assume_tac @{context} 1)
  1853 in
  1853 in
  1854   Goal.prove @{context} [\"P\"] [] trm tac
  1854   Goal.prove @{context} [\"P\"] [] trm tac
  1876 
  1876 
  1877 text \<open>
  1877 text \<open>
  1878   With them we can now produce three theorem instances of the 
  1878   With them we can now produce three theorem instances of the 
  1879   proposition.
  1879   proposition.
  1880 
  1880 
  1881   @{ML_response_fake [display, gray]
  1881   @{ML_matchresult_fake [display, gray]
  1882   "multi_test @{context} 3"
  1882   "multi_test @{context} 3"
  1883   "[\"?f ?x = ?f ?x\", \"?f ?x = ?f ?x\", \"?f ?x = ?f ?x\"]"}
  1883   "[\"?f ?x = ?f ?x\", \"?f ?x = ?f ?x\", \"?f ?x = ?f ?x\"]"}
  1884 
  1884 
  1885   However you should be careful with @{ML prove_common in Goal} and very
  1885   However you should be careful with @{ML prove_common in Goal} and very
  1886   large goals. If you increase the counter in the code above to \<open>3000\<close>, 
  1886   large goals. If you increase the counter in the code above to \<open>3000\<close>, 
  1896 end\<close>
  1896 end\<close>
  1897 
  1897 
  1898 text \<open>
  1898 text \<open>
  1899   While the LCF-approach of going through interfaces ensures soundness in Isabelle, there
  1899   While the LCF-approach of going through interfaces ensures soundness in Isabelle, there
  1900   is the function @{ML_ind make_thm in Skip_Proof} in the structure 
  1900   is the function @{ML_ind make_thm in Skip_Proof} in the structure 
  1901   @{ML_struct Skip_Proof} that allows us to turn any proposition into a theorem.
  1901   @{ML_structure Skip_Proof} that allows us to turn any proposition into a theorem.
  1902   Potentially making the system unsound.  This is sometimes useful for developing 
  1902   Potentially making the system unsound.  This is sometimes useful for developing 
  1903   purposes, or when explicit proof construction should be omitted due to performace 
  1903   purposes, or when explicit proof construction should be omitted due to performace 
  1904   reasons. An example of this function is as follows:
  1904   reasons. An example of this function is as follows:
  1905 
  1905 
  1906   @{ML_response_fake [display, gray]
  1906   @{ML_matchresult_fake [display, gray]
  1907   "Skip_Proof.make_thm @{theory} @{prop \"True = False\"}"
  1907   "Skip_Proof.make_thm @{theory} @{prop \"True = False\"}"
  1908   "True = False"}
  1908   "True = False"}
  1909 
  1909 
  1910   \begin{readmore}
  1910   \begin{readmore}
  1911   Functions that setup goal states and prove theorems are implemented in 
  1911   Functions that setup goal states and prove theorems are implemented in 
  1924 
  1924 
  1925 text \<open>
  1925 text \<open>
  1926   The auxiliary data of this lemma can be retrieved using the function 
  1926   The auxiliary data of this lemma can be retrieved using the function 
  1927   @{ML_ind get_tags in Thm}. So far the the auxiliary data of this lemma is 
  1927   @{ML_ind get_tags in Thm}. So far the the auxiliary data of this lemma is 
  1928 
  1928 
  1929   @{ML_response_fake [display,gray]
  1929   @{ML_matchresult_fake [display,gray]
  1930   "Thm.get_tags @{thm foo_data}"
  1930   "Thm.get_tags @{thm foo_data}"
  1931   "[(\"name\", \"General.foo_data\"), (\"kind\", \"lemma\")]"}
  1931   "[(\"name\", \"General.foo_data\"), (\"kind\", \"lemma\")]"}
  1932 
  1932 
  1933   consisting of a name and a kind.  When we store lemmas in the theorem database, 
  1933   consisting of a name and a kind.  When we store lemmas in the theorem database, 
  1934   we might want to explicitly extend this data by attaching case names to the 
  1934   we might want to explicitly extend this data by attaching case names to the 
  1935   two premises of the lemma.  This can be done with the function @{ML_ind name in Rule_Cases}
  1935   two premises of the lemma.  This can be done with the function @{ML_ind name in Rule_Cases}
  1936   from the structure @{ML_struct Rule_Cases}.
  1936   from the structure @{ML_structure Rule_Cases}.
  1937 \<close>
  1937 \<close>
  1938 
  1938 
  1939 local_setup %gray \<open>
  1939 local_setup %gray \<open>
  1940   Local_Theory.note ((@{binding "foo_data'"}, []), 
  1940   Local_Theory.note ((@{binding "foo_data'"}, []), 
  1941     [(Rule_Cases.name ["foo_case_one", "foo_case_two"] 
  1941     [(Rule_Cases.name ["foo_case_one", "foo_case_two"] 
  1942        @{thm foo_data})]) #> snd\<close>
  1942        @{thm foo_data})]) #> snd\<close>
  1943 
  1943 
  1944 text \<open>
  1944 text \<open>
  1945   The data of the theorem @{thm [source] foo_data'} is then as follows:
  1945   The data of the theorem @{thm [source] foo_data'} is then as follows:
  1946 
  1946 
  1947   @{ML_response_fake [display,gray]
  1947   @{ML_matchresult_fake [display,gray]
  1948   "Thm.get_tags @{thm foo_data'}"
  1948   "Thm.get_tags @{thm foo_data'}"
  1949   "[(\"name\", \"General.foo_data'\"), (\"kind\", \"lemma\"), 
  1949   "[(\"name\", \"General.foo_data'\"), (\"kind\", \"lemma\"), 
  1950  (\"case_names\", \"foo_case_one;foo_case_two\")]"}
  1950  (\"case_names\", \"foo_case_one;foo_case_two\")]"}
  1951 
  1951 
  1952   You can observe the case names of this lemma on the user level when using 
  1952   You can observe the case names of this lemma on the user level when using 
  1994 text \<open>
  1994 text \<open>
  1995   Sometimes one wants to know the theorems that are involved in
  1995   Sometimes one wants to know the theorems that are involved in
  1996   proving a theorem, especially when the proof is by \<open>auto\<close>. These theorems can be obtained by introspecting the proved theorem.
  1996   proving a theorem, especially when the proof is by \<open>auto\<close>. These theorems can be obtained by introspecting the proved theorem.
  1997   To introspect a theorem, let us define the following three functions
  1997   To introspect a theorem, let us define the following three functions
  1998   that analyse the @{ML_type_ind proof_body} data-structure from the
  1998   that analyse the @{ML_type_ind proof_body} data-structure from the
  1999   structure @{ML_struct Proofterm}.
  1999   structure @{ML_structure Proofterm}.
  2000 \<close>
  2000 \<close>
  2001 
  2001 
  2002 ML %grayML\<open>fun pthms_of (PBody {thms, ...}) = map #2 thms 
  2002 ML %grayML\<open>fun pthms_of (PBody {thms, ...}) = map #2 thms 
  2003 val get_names = (map Proofterm.thm_node_name) o pthms_of 
  2003 val get_names = (map Proofterm.thm_node_name) o pthms_of 
  2004 val get_pbodies = map (Future.join o Proofterm.thm_node_body) o pthms_of\<close>
  2004 val get_pbodies = map (Future.join o Proofterm.thm_node_body) o pthms_of\<close>
  2034   a proof-tree that records all theorems that are employed for
  2034   a proof-tree that records all theorems that are employed for
  2035   establishing this theorem.  We can traverse this proof-tree
  2035   establishing this theorem.  We can traverse this proof-tree
  2036   extracting this information.  Let us first extract the name of the
  2036   extracting this information.  Let us first extract the name of the
  2037   established theorem. This can be done with
  2037   established theorem. This can be done with
  2038 
  2038 
  2039   @{ML_response_fake [display,gray]
  2039   @{ML_matchresult_fake [display,gray]
  2040   "@{thm my_conjIa}
  2040   "@{thm my_conjIa}
  2041   |> Thm.proof_body_of
  2041   |> Thm.proof_body_of
  2042   |> get_names"
  2042   |> get_names"
  2043   "[\"Essential.my_conjIa\"]"}
  2043   "[\"Essential.my_conjIa\"]"}
  2044 
  2044 
  2048   theorem.  Notice that the first proof above references
  2048   theorem.  Notice that the first proof above references
  2049   three theorems, namely @{thm [source] conjI}, @{thm [source] conjunct1} 
  2049   three theorems, namely @{thm [source] conjI}, @{thm [source] conjunct1} 
  2050   and @{thm [source] conjunct2}. We can obtain them by descending into the
  2050   and @{thm [source] conjunct2}. We can obtain them by descending into the
  2051   first level of the proof-tree, as follows.
  2051   first level of the proof-tree, as follows.
  2052 
  2052 
  2053   @{ML_response_fake [display,gray]
  2053   @{ML_matchresult_fake [display,gray]
  2054   "@{thm my_conjIa}
  2054   "@{thm my_conjIa}
  2055   |> Thm.proof_body_of
  2055   |> Thm.proof_body_of
  2056   |> get_pbodies
  2056   |> get_pbodies
  2057   |> map get_names
  2057   |> map get_names
  2058   |> List.concat"
  2058   |> List.concat"
  2062   The theorems @{thm [source] Pure.protectD} and @{thm [source]
  2062   The theorems @{thm [source] Pure.protectD} and @{thm [source]
  2063   Pure.protectI} that are internal theorems are always part of a
  2063   Pure.protectI} that are internal theorems are always part of a
  2064   proof in Isabelle. Note also that applications of \<open>assumption\<close> do not
  2064   proof in Isabelle. Note also that applications of \<open>assumption\<close> do not
  2065   count as a separate theorem, as you can see in the following code.
  2065   count as a separate theorem, as you can see in the following code.
  2066 
  2066 
  2067   @{ML_response_fake [display,gray]
  2067   @{ML_matchresult_fake [display,gray]
  2068   "@{thm my_conjIb}
  2068   "@{thm my_conjIb}
  2069   |> Thm.proof_body_of
  2069   |> Thm.proof_body_of
  2070   |> get_pbodies
  2070   |> get_pbodies
  2071   |> map get_names
  2071   |> map get_names
  2072   |> List.concat"
  2072   |> List.concat"
  2075   Interestingly, but not surprisingly, the proof of @{thm [source]
  2075   Interestingly, but not surprisingly, the proof of @{thm [source]
  2076   my_conjIc} procceeds quite differently from @{thm [source] my_conjIa}
  2076   my_conjIc} procceeds quite differently from @{thm [source] my_conjIa}
  2077   and @{thm [source] my_conjIb}, as can be seen by the theorems that
  2077   and @{thm [source] my_conjIb}, as can be seen by the theorems that
  2078   are returned for @{thm [source] my_conjIc}.
  2078   are returned for @{thm [source] my_conjIc}.
  2079 
  2079 
  2080   @{ML_response_fake [display,gray]
  2080   @{ML_matchresult_fake [display,gray]
  2081   "@{thm my_conjIc}
  2081   "@{thm my_conjIc}
  2082   |> Thm.proof_body_of
  2082   |> Thm.proof_body_of
  2083   |> get_pbodies
  2083   |> get_pbodies
  2084   |> map get_names
  2084   |> map get_names
  2085   |> List.concat"
  2085   |> List.concat"
  2090   Of course we can also descend into the second level of the tree 
  2090   Of course we can also descend into the second level of the tree 
  2091   ``behind'' @{thm [source] my_conjIa} say, which
  2091   ``behind'' @{thm [source] my_conjIa} say, which
  2092   means we obtain the theorems that are used in order to prove
  2092   means we obtain the theorems that are used in order to prove
  2093   @{thm [source] conjunct1}, @{thm [source] conjunct2} and @{thm [source] conjI}.
  2093   @{thm [source] conjunct1}, @{thm [source] conjunct2} and @{thm [source] conjI}.
  2094 
  2094 
  2095   @{ML_response_fake [display, gray]
  2095   @{ML_matchresult_fake [display, gray]
  2096   "@{thm my_conjIa}
  2096   "@{thm my_conjIa}
  2097   |> Thm.proof_body_of
  2097   |> Thm.proof_body_of
  2098   |> get_pbodies
  2098   |> get_pbodies
  2099   |> map get_pbodies
  2099   |> map get_pbodies
  2100   |> (map o map) get_names
  2100   |> (map o map) get_names
  2406 lemma trueI_2[my_thms]: "True" by simp
  2406 lemma trueI_2[my_thms]: "True" by simp
  2407 
  2407 
  2408 text \<open>
  2408 text \<open>
  2409   then you can see it is added to the initially empty list.
  2409   then you can see it is added to the initially empty list.
  2410 
  2410 
  2411   @{ML_response_fake [display,gray]
  2411   @{ML_matchresult_fake [display,gray]
  2412   "MyThms.get @{context}" 
  2412   "MyThms.get @{context}" 
  2413   "[\"True\"]"}
  2413   "[\"True\"]"}
  2414 
  2414 
  2415   You can also add theorems using the command \isacommand{declare}.
  2415   You can also add theorems using the command \isacommand{declare}.
  2416 \<close>
  2416 \<close>
  2420 text \<open>
  2420 text \<open>
  2421   With this attribute, the \<open>add\<close> operation is the default and does 
  2421   With this attribute, the \<open>add\<close> operation is the default and does 
  2422   not need to be explicitly given. These three declarations will cause the 
  2422   not need to be explicitly given. These three declarations will cause the 
  2423   theorem list to be updated as:
  2423   theorem list to be updated as:
  2424 
  2424 
  2425   @{ML_response_fake [display,gray]
  2425   @{ML_matchresult_fake [display,gray]
  2426   "MyThms.get @{context}"
  2426   "MyThms.get @{context}"
  2427   "[\"True\", \"Suc (Suc 0) = 2\"]"}
  2427   "[\"True\", \"Suc (Suc 0) = 2\"]"}
  2428 
  2428 
  2429   The theorem @{thm [source] trueI_2} only appears once, since the 
  2429   The theorem @{thm [source] trueI_2} only appears once, since the 
  2430   function @{ML_ind  add_thm in Thm} tests for duplicates, before extending
  2430   function @{ML_ind  add_thm in Thm} tests for duplicates, before extending
  2433 
  2433 
  2434 declare test[my_thms del]
  2434 declare test[my_thms del]
  2435 
  2435 
  2436 text \<open>After this, the theorem list is again: 
  2436 text \<open>After this, the theorem list is again: 
  2437 
  2437 
  2438   @{ML_response_fake [display,gray]
  2438   @{ML_matchresult_fake [display,gray]
  2439   "MyThms.get @{context}"
  2439   "MyThms.get @{context}"
  2440   "[\"True\"]"}
  2440   "[\"True\"]"}
  2441 
  2441 
  2442   We used in this example two functions declared as @{ML_ind
  2442   We used in this example two functions declared as @{ML_ind
  2443   declaration_attribute in Thm}, but there can be any number of them. We just
  2443   declaration_attribute in Thm}, but there can be any number of them. We just
  2466   @{ML_type_ind [display, gray] "Pretty.T"}
  2466   @{ML_type_ind [display, gray] "Pretty.T"}
  2467 
  2467 
  2468   The function @{ML str in Pretty} transforms a (plain) string into such a pretty 
  2468   The function @{ML str in Pretty} transforms a (plain) string into such a pretty 
  2469   type. For example
  2469   type. For example
  2470 
  2470 
  2471   @{ML_response_fake [display,gray]
  2471   @{ML_matchresult_fake [display,gray]
  2472   "Pretty.str \"test\"" "String (\"test\", 4)"}
  2472   "Pretty.str \"test\"" "String (\"test\", 4)"}
  2473 
  2473 
  2474   where the result indicates that we transformed a string with length 4. Once
  2474   where the result indicates that we transformed a string with length 4. Once
  2475   you have a pretty type, you can, for example, control where linebreaks may
  2475   you have a pretty type, you can, for example, control where linebreaks may
  2476   occur in case the text wraps over a line, or with how much indentation a
  2476   occur in case the text wraps over a line, or with how much indentation a
  2501 text \<open>
  2501 text \<open>
  2502   We deliberately chose a large string so that it spans over more than one line. 
  2502   We deliberately chose a large string so that it spans over more than one line. 
  2503   If we print out the string using the usual ``quick-and-dirty'' method, then
  2503   If we print out the string using the usual ``quick-and-dirty'' method, then
  2504   we obtain the ugly output:
  2504   we obtain the ugly output:
  2505 
  2505 
  2506 @{ML_response_fake [display,gray]
  2506 @{ML_matchresult_fake [display,gray]
  2507 "tracing test_str"
  2507 "tracing test_str"
  2508 "fooooooooooooooobaaaaaaaaaaaar fooooooooooooooobaaaaaaaaaaaar foooooooooo
  2508 "fooooooooooooooobaaaaaaaaaaaar fooooooooooooooobaaaaaaaaaaaar foooooooooo
  2509 ooooobaaaaaaaaaaaar fooooooooooooooobaaaaaaaaaaaar fooooooooooooooobaaaaa
  2509 ooooobaaaaaaaaaaaar fooooooooooooooobaaaaaaaaaaaar fooooooooooooooobaaaaa
  2510 aaaaaaar fooooooooooooooobaaaaaaaaaaaar fooooooooooooooobaaaaaaaaaaaar fo
  2510 aaaaaaar fooooooooooooooobaaaaaaaaaaaar fooooooooooooooobaaaaaaaaaaaar fo
  2511 oooooooooooooobaaaaaaaaaaaar"}
  2511 oooooooooooooobaaaaaaaaaaaar"}
  2512 
  2512 
  2513   We obtain the same if we just use the function @{ML pprint}.
  2513   We obtain the same if we just use the function @{ML pprint}.
  2514 
  2514 
  2515 @{ML_response_fake [display,gray]
  2515 @{ML_matchresult_fake [display,gray]
  2516 "pprint (Pretty.str test_str)"
  2516 "pprint (Pretty.str test_str)"
  2517 "fooooooooooooooobaaaaaaaaaaaar fooooooooooooooobaaaaaaaaaaaar foooooooooo
  2517 "fooooooooooooooobaaaaaaaaaaaar fooooooooooooooobaaaaaaaaaaaar foooooooooo
  2518 ooooobaaaaaaaaaaaar fooooooooooooooobaaaaaaaaaaaar fooooooooooooooobaaaaa
  2518 ooooobaaaaaaaaaaaar fooooooooooooooobaaaaaaaaaaaar fooooooooooooooobaaaaa
  2519 aaaaaaar fooooooooooooooobaaaaaaaaaaaar fooooooooooooooobaaaaaaaaaaaar fo
  2519 aaaaaaar fooooooooooooooobaaaaaaaaaaaar fooooooooooooooobaaaaaaaaaaaar fo
  2520 oooooooooooooobaaaaaaaaaaaar"}
  2520 oooooooooooooobaaaaaaaaaaaar"}
  2524   function @{ML_ind breaks in Pretty}, which expects a list of pretty types
  2524   function @{ML_ind breaks in Pretty}, which expects a list of pretty types
  2525   and inserts a possible line break in between every two elements in this
  2525   and inserts a possible line break in between every two elements in this
  2526   list. To print this list of pretty types as a single string, we concatenate
  2526   list. To print this list of pretty types as a single string, we concatenate
  2527   them with the function @{ML_ind blk in Pretty} as follows:
  2527   them with the function @{ML_ind blk in Pretty} as follows:
  2528 
  2528 
  2529 @{ML_response_fake [display,gray]
  2529 @{ML_matchresult_fake [display,gray]
  2530 "let
  2530 "let
  2531   val ptrs = map Pretty.str (space_explode \" \" test_str)
  2531   val ptrs = map Pretty.str (space_explode \" \" test_str)
  2532 in
  2532 in
  2533   pprint (Pretty.blk (0, Pretty.breaks ptrs))
  2533   pprint (Pretty.blk (0, Pretty.breaks ptrs))
  2534 end"
  2534 end"
  2540   Here the layout of @{ML test_str} is much more pleasing to the 
  2540   Here the layout of @{ML test_str} is much more pleasing to the 
  2541   eye. The @{ML "0"} in @{ML_ind  blk in Pretty} stands for no hanging 
  2541   eye. The @{ML "0"} in @{ML_ind  blk in Pretty} stands for no hanging 
  2542   indentation of the printed string. You can increase the indentation 
  2542   indentation of the printed string. You can increase the indentation 
  2543   and obtain
  2543   and obtain
  2544   
  2544   
  2545 @{ML_response_fake [display,gray]
  2545 @{ML_matchresult_fake [display,gray]
  2546 "let
  2546 "let
  2547   val ptrs = map Pretty.str (space_explode \" \" test_str)
  2547   val ptrs = map Pretty.str (space_explode \" \" test_str)
  2548 in
  2548 in
  2549   pprint (Pretty.blk (3, Pretty.breaks ptrs))
  2549   pprint (Pretty.blk (3, Pretty.breaks ptrs))
  2550 end"
  2550 end"
  2555 
  2555 
  2556   where starting from the second line the indent is 3. If you want
  2556   where starting from the second line the indent is 3. If you want
  2557   that every line starts with the same indent, you can use the
  2557   that every line starts with the same indent, you can use the
  2558   function @{ML_ind  indent in Pretty} as follows:
  2558   function @{ML_ind  indent in Pretty} as follows:
  2559 
  2559 
  2560 @{ML_response_fake [display,gray]
  2560 @{ML_matchresult_fake [display,gray]
  2561 "let
  2561 "let
  2562   val ptrs = map Pretty.str (space_explode \" \" test_str)
  2562   val ptrs = map Pretty.str (space_explode \" \" test_str)
  2563 in
  2563 in
  2564   pprint (Pretty.indent 10 (Pretty.blk (0, Pretty.breaks ptrs)))
  2564   pprint (Pretty.indent 10 (Pretty.blk (0, Pretty.breaks ptrs)))
  2565 end"
  2565 end"
  2570 
  2570 
  2571   If you want to print out a list of items separated by commas and 
  2571   If you want to print out a list of items separated by commas and 
  2572   have the linebreaks handled properly, you can use the function 
  2572   have the linebreaks handled properly, you can use the function 
  2573   @{ML_ind  commas in Pretty}. For example
  2573   @{ML_ind  commas in Pretty}. For example
  2574 
  2574 
  2575 @{ML_response_fake [display,gray]
  2575 @{ML_matchresult_fake [display,gray]
  2576 "let
  2576 "let
  2577   val ptrs = map (Pretty.str o string_of_int) (99998 upto 100020)
  2577   val ptrs = map (Pretty.str o string_of_int) (99998 upto 100020)
  2578 in
  2578 in
  2579   pprint (Pretty.blk (0, Pretty.commas ptrs))
  2579   pprint (Pretty.blk (0, Pretty.commas ptrs))
  2580 end"
  2580 end"
  2588   @{ML_ind  enum in Pretty}. For example
  2588   @{ML_ind  enum in Pretty}. For example
  2589 \<close>
  2589 \<close>
  2590 
  2590 
  2591 text \<open>
  2591 text \<open>
  2592   
  2592   
  2593 @{ML_response_fake [display,gray]
  2593 @{ML_matchresult_fake [display,gray]
  2594 "let
  2594 "let
  2595   val ptrs = map (Pretty.str o string_of_int) (99998 upto 100020)
  2595   val ptrs = map (Pretty.str o string_of_int) (99998 upto 100020)
  2596 in
  2596 in
  2597   pprint (Pretty.enum \",\" \"{\" \"}\" ptrs)
  2597   pprint (Pretty.enum \",\" \"{\" \"}\" ptrs)
  2598 end"
  2598 end"
  2627   to insert a space (of length 1) before the 
  2627   to insert a space (of length 1) before the 
  2628   @{text [quotes] "and"}. This space is also a place where a line break 
  2628   @{text [quotes] "and"}. This space is also a place where a line break 
  2629   can occur. We do the same after the @{text [quotes] "and"}. This gives you
  2629   can occur. We do the same after the @{text [quotes] "and"}. This gives you
  2630   for example
  2630   for example
  2631 
  2631 
  2632 @{ML_response_fake [display,gray]
  2632 @{ML_matchresult_fake [display,gray]
  2633 "let
  2633 "let
  2634   val ptrs1 = map (Pretty.str o string_of_int) (1 upto 22)
  2634   val ptrs1 = map (Pretty.str o string_of_int) (1 upto 22)
  2635   val ptrs2 = map (Pretty.str o string_of_int) (10 upto 28)
  2635   val ptrs2 = map (Pretty.str o string_of_int) (10 upto 28)
  2636 in
  2636 in
  2637   pprint (Pretty.blk (0, and_list ptrs1));
  2637   pprint (Pretty.blk (0, and_list ptrs1));
  2644 
  2644 
  2645   Like @{ML blk in Pretty}, the function @{ML_ind chunks in Pretty} prints out 
  2645   Like @{ML blk in Pretty}, the function @{ML_ind chunks in Pretty} prints out 
  2646   a list of items, but automatically inserts forced breaks between each item.
  2646   a list of items, but automatically inserts forced breaks between each item.
  2647   Compare
  2647   Compare
  2648 
  2648 
  2649   @{ML_response_fake [display,gray]
  2649   @{ML_matchresult_fake [display,gray]
  2650   "let
  2650   "let
  2651   val a_and_b = [Pretty.str \"a\", Pretty.str \"b\"]
  2651   val a_and_b = [Pretty.str \"a\", Pretty.str \"b\"]
  2652 in
  2652 in
  2653   pprint (Pretty.blk (0, a_and_b));
  2653   pprint (Pretty.blk (0, a_and_b));
  2654   pprint (Pretty.chunks a_and_b)
  2654   pprint (Pretty.chunks a_and_b)
  2659 
  2659 
  2660   The function @{ML_ind big_list in Pretty} helps with printing long lists.
  2660   The function @{ML_ind big_list in Pretty} helps with printing long lists.
  2661   It is used for example in the command \isacommand{print\_theorems}. An
  2661   It is used for example in the command \isacommand{print\_theorems}. An
  2662   example is as follows.
  2662   example is as follows.
  2663 
  2663 
  2664   @{ML_response_fake [display,gray]
  2664   @{ML_matchresult_fake [display,gray]
  2665   "let
  2665   "let
  2666   val pstrs = map (Pretty.str o string_of_int) (4 upto 10)
  2666   val pstrs = map (Pretty.str o string_of_int) (4 upto 10)
  2667 in
  2667 in
  2668   pprint (Pretty.big_list \"header\" pstrs)
  2668   pprint (Pretty.big_list \"header\" pstrs)
  2669 end"
  2669 end"
  2679   The point of the pretty-printing functions is to conveninetly obtain 
  2679   The point of the pretty-printing functions is to conveninetly obtain 
  2680   a lay-out of terms and types that is pleasing to the eye. If we print
  2680   a lay-out of terms and types that is pleasing to the eye. If we print
  2681   out the the terms produced by the the function @{ML de_bruijn} from 
  2681   out the the terms produced by the the function @{ML de_bruijn} from 
  2682   exercise~\ref{ex:debruijn} we obtain the following: 
  2682   exercise~\ref{ex:debruijn} we obtain the following: 
  2683 
  2683 
  2684   @{ML_response_fake [display,gray]
  2684   @{ML_matchresult_fake [display,gray]
  2685   "pprint (Syntax.pretty_term  @{context} (de_bruijn 4))"
  2685   "pprint (Syntax.pretty_term  @{context} (de_bruijn 4))"
  2686   "(P 3 = P 4 \<longrightarrow> P 4 \<and> P 3 \<and> P 2 \<and> P 1) \<and>
  2686   "(P 3 = P 4 \<longrightarrow> P 4 \<and> P 3 \<and> P 2 \<and> P 1) \<and>
  2687 (P 2 = P 3 \<longrightarrow> P 4 \<and> P 3 \<and> P 2 \<and> P 1) \<and>
  2687 (P 2 = P 3 \<longrightarrow> P 4 \<and> P 3 \<and> P 2 \<and> P 1) \<and>
  2688 (P 1 = P 2 \<longrightarrow> P 4 \<and> P 3 \<and> P 2 \<and> P 1) \<and> 
  2688 (P 1 = P 2 \<longrightarrow> P 4 \<and> P 3 \<and> P 2 \<and> P 1) \<and> 
  2689 (P 1 = P 4 \<longrightarrow> P 4 \<and> P 3 \<and> P 2 \<and> P 1) \<longrightarrow>
  2689 (P 1 = P 4 \<longrightarrow> P 4 \<and> P 3 \<and> P 2 \<and> P 1) \<longrightarrow>
  2713   Pretty} in order to enclose the term and type inside quotation marks. In
  2713   Pretty} in order to enclose the term and type inside quotation marks. In
  2714   Line 9 we add a period right after the type without the possibility of a
  2714   Line 9 we add a period right after the type without the possibility of a
  2715   line break, because we do not want that a line break occurs there.
  2715   line break, because we do not want that a line break occurs there.
  2716   Now you can write
  2716   Now you can write
  2717 
  2717 
  2718   @{ML_response_fake [display,gray]
  2718   @{ML_matchresult_fake [display,gray]
  2719   "tell_type @{context} @{term \"min (Suc 0)\"}"
  2719   "tell_type @{context} @{term \"min (Suc 0)\"}"
  2720   "The term \"min (Suc 0)\" has type \"nat \<Rightarrow> nat\"."}
  2720   "The term \"min (Suc 0)\" has type \"nat \<Rightarrow> nat\"."}
  2721   
  2721   
  2722   To see the proper line breaking, you can try out the function on a bigger term 
  2722   To see the proper line breaking, you can try out the function on a bigger term 
  2723   and type. For example:
  2723   and type. For example:
  2724 
  2724 
  2725   @{ML_response_fake [display,gray]
  2725   @{ML_matchresult_fake [display,gray]
  2726   "tell_type @{context} @{term \"(=) ((=) ((=) ((=) ((=) (=)))))\"}"
  2726   "tell_type @{context} @{term \"(=) ((=) ((=) ((=) ((=) (=)))))\"}"
  2727   "The term \"(=) ((=) ((=) ((=) ((=) (=)))))\" has type 
  2727   "The term \"(=) ((=) ((=) ((=) ((=) (=)))))\" has type 
  2728 \"((((('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> bool) \<Rightarrow> bool) \<Rightarrow> bool) \<Rightarrow> bool) \<Rightarrow> bool\"."}
  2728 \"((((('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> bool) \<Rightarrow> bool) \<Rightarrow> bool) \<Rightarrow> bool) \<Rightarrow> bool\"."}
  2729 
  2729 
  2730   \begin{readmore}
  2730   \begin{readmore}