theory FirstSteps

imports Base

begin

chapter {* First Steps *}

text {*

  Isabelle programming is done in ML. Just like lemmas and proofs, ML-code

  in Isabelle is part of a theory. If you want to follow the code given in

  this chapter, we assume you are working inside the theory starting with

  \begin{quote}

  \begin{tabular}{@ {}l}

  \isacommand{theory} FirstSteps\\

  \isacommand{imports} Main\\

  \isacommand{begin}\\

  \ldots

  \end{tabular}

  \end{quote}

  We also generally assume you are working with HOL. The given examples might

  need to be adapted if you work in a different logic.

*}

section {* Including ML-Code *}

text {*

  The easiest and quickest way to include code in a theory is

  by using the \isacommand{ML}-command. For example:

\begin{isabelle}

\begin{graybox}

\isacommand{ML}~@{text "\<verbopen>"}\isanewline

\hspace{5mm}@{ML "3 + 4"}\isanewline

@{text "\<verbclose>"}\isanewline

@{text "> 7"}\smallskip

\end{graybox}

\end{isabelle}

  Like normal Isabelle scripts, \isacommand{ML}-commands can be

  evaluated by using the advance and undo buttons of your Isabelle

  environment. The code inside the \isacommand{ML}-command can also contain

  value and function bindings, for example

*}

ML %gray {* 

  val r = ref 0

  fun f n = n + 1 

*}

text {*

  and even those can be undone when the proof

  script is retracted.  As mentioned in the Introduction, we will drop the

  \isacommand{ML}~@{text "\<verbopen> \<dots> \<verbclose>"} scaffolding whenever we

  show code. The lines prefixed with @{text [quotes] ">"} are not part of the

  code, rather they indicate what the response is when the code is evaluated.

  Once a portion of code is relatively stable, you usually want to export it

  to a separate ML-file. Such files can then be included somewhere inside a 

  theory by using the command \isacommand{use}. For example

  \begin{quote}

  \begin{tabular}{@ {}l}

  \isacommand{theory} FirstSteps\\

  \isacommand{imports} Main\\

  \isacommand{uses}~@{text "(\"file_to_be_included.ML\")"} @{text "\<dots>"}\\

  \isacommand{begin}\\

  \ldots\\

  \isacommand{use}~@{text "\"file_to_be_included.ML\""}\\

  \ldots

  \end{tabular}

  \end{quote}

  The \isacommand{uses}-command in the header of the theory is needed in order 

  to indicate the dependency of the theory on the ML-file. Alternatively, the 

  file can be included by just writing in the header

  \begin{quote}

  \begin{tabular}{@ {}l}

  \isacommand{theory} FirstSteps\\

  \isacommand{imports} Main\\

  \isacommand{uses} @{text "\"file_to_be_included.ML\""} @{text "\<dots>"}\\

  \isacommand{begin}\\

  \ldots

  \end{tabular}

  \end{quote}

  Note that no parentheses are given this time.

*}

section {* Debugging and Printing\label{sec:printing} *}

text {*

  During development you might find it necessary to inspect some data

  in your code. This can be done in a ``quick-and-dirty'' fashion using 

  the function @{ML "writeln"}. For example 

  @{ML_response_fake [display,gray] "writeln \"any string\"" "\"any string\""}

  will print out @{text [quotes] "any string"} inside the response buffer

  of Isabelle.  This function expects a string as argument. If you develop under PolyML,

  then there is a convenient, though again ``quick-and-dirty'', method for

  converting values into strings, namely the function @{ML PolyML.makestring}:

  @{ML_response_fake [display,gray] "writeln (PolyML.makestring 1)" "\"1\""} 

  However, @{ML makestring} only works if the type of what is converted is monomorphic 

  and not a function.

  The function @{ML "writeln"} should only be used for testing purposes, because any

  output this function generates will be overwritten as soon as an error is

  raised. For printing anything more serious and elaborate, the

  function @{ML tracing} is more appropriate. This function writes all output into

  a separate tracing buffer. For example:

  @{ML_response_fake [display,gray] "tracing \"foo\"" "\"foo\""}

  It is also possible to redirect the ``channel'' where the string @{text "foo"} is 

  printed to a separate file, e.g., to prevent ProofGeneral from choking on massive 

  amounts of trace output. This redirection can be achieved with the code:

*}

ML{*val strip_specials =

let

  fun strip ("\^A" :: _ :: cs) = strip cs

    | strip (c :: cs) = c :: strip cs

    | strip [] = [];

in implode o strip o explode end;

fun redirect_tracing stream =

 Output.tracing_fn := (fn s =>

    (TextIO.output (stream, (strip_specials s));

     TextIO.output (stream, "\n");

     TextIO.flushOut stream)) *}

text {*

  Calling @{ML "redirect_tracing"} with @{ML "(TextIO.openOut \"foo.bar\")"} 

  will cause that all tracing information is printed into the file @{text "foo.bar"}.

  You can print out error messages with the function @{ML error}; for example:

@{ML_response_fake [display,gray] "if 0=1 then true else (error \"foo\")" 

"Exception- ERROR \"foo\" raised

At command \"ML\"."}

  (FIXME Mention how to work with @{ML Toplevel.debug} and @{ML Toplevel.profiling}.)

*}

(*

ML {* reset Toplevel.debug *}

ML {* fun dodgy_fun () = (raise TYPE ("",[],[]); 1) *}

ML {* fun innocent () = dodgy_fun () *}

ML {* exception_trace (fn () => cterm_of @{theory} (Bound 0)) *}

ML {* exception_trace (fn () => innocent ()) *}

ML {* Toplevel.program (fn () => cterm_of @{theory} (Bound 0)) *}

ML {* Toplevel.program (fn () => innocent ()) *}

*)

text {*

  Most often you want to inspect data of type @{ML_type term}, @{ML_type cterm} 

  or @{ML_type thm}. Isabelle contains elaborate pretty-printing functions for printing 

  them (see Section \ref{sec:pretty}), 

  but  for quick-and-dirty solutions they are far too unwieldy. A simple way to transform 

  a term into a string is to use the function @{ML Syntax.string_of_term}.

  @{ML_response_fake [display,gray]

  "Syntax.string_of_term @{context} @{term \"1::nat\"}"

  "\"\\^E\\^Fterm\\^E\\^E\\^Fconst\\^Fname=HOL.one_class.one\\^E1\\^E\\^F\\^E\\^E\\^F\\^E\""}

  This produces a string with some additional information encoded in it. The string

  can be properly printed by using the function @{ML writeln}.

  @{ML_response_fake [display,gray]

  "writeln (Syntax.string_of_term @{context} @{term \"1::nat\"})"

  "\"1\""}

  A @{ML_type cterm} can be transformed into a string by the following function.

*}

ML{*fun string_of_cterm ctxt t =  

   Syntax.string_of_term ctxt (term_of t)*}

text {*

  In this example the function @{ML term_of} extracts the @{ML_type term} from

  a @{ML_type cterm}.  If there are more than one @{ML_type cterm}s to be

  printed, you can use the function @{ML commas} to separate them.

*} 

ML{*fun string_of_cterms ctxt ts =  

   commas (map (string_of_cterm ctxt) ts)*}

text {*

  The easiest way to get the string of a theorem is to transform it

  into a @{ML_type cterm} using the function @{ML crep_thm}. 

*}

ML{*fun string_of_thm ctxt thm =

  string_of_cterm ctxt (#prop (crep_thm thm))*}

text {*

  Theorems also include schematic variables, such as @{text "?P"}, 

  @{text "?Q"} and so on. 

  @{ML_response_fake [display, gray]

  "writeln (string_of_thm @{context} @{thm conjI})"

  "\<lbrakk>?P; ?Q\<rbrakk> \<Longrightarrow> ?P \<and> ?Q"}

  In order to improve the readability of theorems we convert

  these schematic variables into free variables using the 

  function @{ML Variable.import_thms}.

*}

ML{*fun no_vars ctxt thm =

let 

  val ((_, [thm']), _) = Variable.import_thms true [thm] ctxt

in

  thm'

end

fun string_of_thm_no_vars ctxt thm =

  string_of_cterm ctxt (#prop (crep_thm (no_vars ctxt thm)))*}

text {* 

  Theorem @{thm [source] conjI} is now printed as follows:

  @{ML_response_fake [display, gray]

  "writeln (string_of_thm_no_vars @{context} @{thm conjI})"

  "\<lbrakk>P; Q\<rbrakk> \<Longrightarrow> P \<and> Q"}

  Again the function @{ML commas} helps with printing more than one theorem. 

*}

ML{*fun string_of_thms ctxt thms =  

  commas (map (string_of_thm ctxt) thms)

fun string_of_thms_no_vars ctxt thms =  

  commas (map (string_of_thm_no_vars ctxt) thms) *}

section {* Combinators\label{sec:combinators} *}

text {*

  For beginners perhaps the most puzzling parts in the existing code of Isabelle are

  the combinators. At first they seem to greatly obstruct the

  comprehension of the code, but after getting familiar with them, they

  actually ease the understanding and also the programming.

  The simplest combinator is @{ML I}, which is just the identity function defined as

*}

ML{*fun I x = x*}

text {* Another simple combinator is @{ML K}, defined as *}

ML{*fun K x = fn _ => x*}

text {*

  @{ML K} ``wraps'' a function around the argument @{text "x"}. However, this 

  function ignores its argument. As a result, @{ML K} defines a constant function 

  always returning @{text x}.

  The next combinator is reverse application, @{ML "|>"}, defined as: 

*}

ML{*fun x |> f = f x*}

text {* While just syntactic sugar for the usual function application,

  the purpose of this combinator is to implement functions in a  

  ``waterfall fashion''. Consider for example the function *}

ML %linenosgray{*fun inc_by_five x =

  x |> (fn x => x + 1)

    |> (fn x => (x, x))

    |> fst

    |> (fn x => x + 4)*}

text {*

  which increments its argument @{text x} by 5. It proceeds by first incrementing 

  the argument by 1 (Line 2); then storing the result in a pair (Line 3); taking 

  the first component of the pair (Line 4) and finally incrementing the first 

  component by 4 (Line 5). This kind of cascading manipulations of values is quite

  common when dealing with theories (for example by adding a definition, followed by

  lemmas and so on). The reverse application allows you to read what happens in 

  a top-down manner. This kind of coding should also be familiar, 

  if you have been exposed to Haskell's {\it do}-notation. Writing the function 

  @{ML inc_by_five} using the reverse application is much clearer than writing

*}

ML{*fun inc_by_five x = fst ((fn x => (x, x)) (x + 1)) + 4*}

text {* or *}

ML{*fun inc_by_five x = 

       ((fn x => x + 4) o fst o (fn x => (x, x)) o (fn x => x + 1)) x*}

text {* and typographically more economical than *}

ML{*fun inc_by_five x =

   let val y1 = x + 1

       val y2 = (y1, y1)

       val y3 = fst y2

       val y4 = y3 + 4

   in y4 end*}

text {* 

  Another reason why the let-bindings in the code above are better to be

  avoided: it is more than easy to get the intermediate values wrong, not to 

  mention the nightmares the maintenance of this code causes!

  In Isabelle, a ``real world'' example for a function written in 

  the waterfall fashion might be the following code:

*}

ML %linenosgray{*fun apply_fresh_args f ctxt =

    f |> fastype_of

      |> binder_types 

      |> map (pair "z")

      |> Variable.variant_frees ctxt [f]

      |> map Free  

      |> (curry list_comb) f *}

text {*

  This code extracts the argument types of a given function @{text "f"} and then generates 

  for each argument type a distinct variable; finally it applies the generated 

  variables to the function. For example:

  @{ML_response_fake [display,gray]

"apply_fresh_args @{term \"P::nat \<Rightarrow> int \<Rightarrow> unit \<Rightarrow> bool\"} @{context} 

 |> Syntax.string_of_term @{context}

 |> writeln"

  "P z za zb"}

  You can read off this behaviour from how @{ML apply_fresh_args} is

  coded: in Line 2, the function @{ML fastype_of} calculates the type of the

  function; @{ML binder_types} in the next line produces the list of argument

  types (in the case above the list @{text "[nat, int, unit]"}); Line 4 

  pairs up each type with the string  @{text "z"}; the

  function @{ML variant_frees in Variable} generates for each @{text "z"} a

  unique name avoiding the given @{text f}; the list of name-type pairs is turned

  into a list of variable terms in Line 6, which in the last line is applied

  by the function @{ML list_comb} to the function. In this last step we have to 

  use the function @{ML curry}, because @{ML list_comb} expects the function and the

  variables list as a pair. This kind of functions is often needed when

  constructing terms and the infrastructure helps tremendously to avoid

  any name clashes. Consider for example: 

   @{ML_response_fake [display,gray]

"apply_fresh_args @{term \"za::'a \<Rightarrow> 'b \<Rightarrow> 'c\"} @{context} 

 |> Syntax.string_of_term @{context}

 |> writeln"

  "za z zb"}

  The combinator @{ML "#>"} is the reverse function composition. It can be

  used to define the following function

*}

ML{*val inc_by_six = 

      (fn x => x + 1)

   #> (fn x => x + 2)

   #> (fn x => x + 3)*}

text {* 

  which is the function composed of first the increment-by-one function and then

  increment-by-two, followed by increment-by-three. Again, the reverse function 

  composition allows you to read the code top-down.

  The remaining combinators described in this section add convenience for the

  ``waterfall method'' of writing functions. The combinator @{ML tap} allows

  you to get hold of an intermediate result (to do some side-calculations for

  instance). The function

 *}

ML %linenosgray{*fun inc_by_three x =

     x |> (fn x => x + 1)

       |> tap (fn x => tracing (PolyML.makestring x))

       |> (fn x => x + 2)*}

text {* 

  increments the argument first by @{text "1"} and then by @{text "2"}. In the

  middle (Line 3), however, it uses @{ML tap} for printing the ``plus-one''

  intermediate result inside the tracing buffer. The function @{ML tap} can

  only be used for side-calculations, because any value that is computed

  cannot be merged back into the ``main waterfall''. To do this, you can use

  the next combinator.

  The combinator @{ML "`"} (a backtick) is similar to @{ML tap}, but applies a

  function to the value and returns the result together with the value (as a

  pair). For example the function 

*}

ML{*fun inc_as_pair x =

     x |> `(fn x => x + 1)

       |> (fn (x, y) => (x, y + 1))*}

text {*

  takes @{text x} as argument, and then increments @{text x}, but also keeps

  @{text x}. The intermediate result is therefore the pair @{ML "(x + 1, x)"

  for x}. After that, the function increments the right-hand component of the

  pair. So finally the result will be @{ML "(x + 1, x + 1)" for x}.

  The combinators @{ML "|>>"} and @{ML "||>"} are defined for 

  functions manipulating pairs. The first applies the function to

  the first component of the pair, defined as

*}

ML{*fun (x, y) |>> f = (f x, y)*}

text {*

  and the second combinator to the second component, defined as

*}

ML{*fun (x, y) ||> f = (x, f y)*}

text {*

  With the combinator @{ML "|->"} you can re-combine the elements from a pair.

  This combinator is defined as

*}

ML{*fun (x, y) |-> f = f x y*}

text {* 

  and can be used to write the following roundabout version 

  of the @{text double} function: 

*}

ML{*fun double x =

      x |>  (fn x => (x, x))

        |-> (fn x => fn y => x + y)*}

text {* 

  The combinator @{ML ||>>} plays a central rôle whenever your task is to update a 

  theory and the update also produces a side-result (for example a theorem). Functions 

  for such tasks return a pair whose second component is the theory and the fist 

  component is the side-result. Using @{ML ||>>}, you can do conveniently the update 

  and also accumulate the side-results. Considder the following simple function. 

*}

ML %linenosgray{*fun acc_incs x =

    x |> (fn x => ("", x)) 

      ||>> (fn x => (x, x + 1))

      ||>> (fn x => (x, x + 1))

      ||>> (fn x => (x, x + 1))*}

text {*

  The purpose of Line 2 is to just pair up the argument with a dummy value (since

  @{ML "||>>"} operates on pairs). Each of the next three lines just increment 

  the value by one, but also nest the intrermediate results to the left. For example 

  @{ML_response [display,gray]

  "acc_incs 1"

  "((((\"\", 1), 2), 3), 4)"}

  You can continue this chain with:

  @{ML_response [display,gray]

  "acc_incs 1 ||>> (fn x => (x, x + 2))"

  "(((((\"\", 1), 2), 3), 4), 6)"}

  (FIXME: maybe give a ``real world'' example)

*}

text {*

  Recall that @{ML "|>"} is the reverse function application. Recall also that

  the related 

  reverse function composition is @{ML "#>"}. In fact all the combinators @{ML "|->"},