diff -r e9ab4ad7bd15 -r 23307fd33906 src/Doc/Tutorial/Advanced/WFrec.thy --- a/src/Doc/Tutorial/Advanced/WFrec.thy Thu Jan 11 13:48:17 2018 +0100 +++ b/src/Doc/Tutorial/Advanced/WFrec.thy Fri Jan 12 14:08:53 2018 +0100 @@ -1,12 +1,12 @@ (*<*)theory WFrec imports Main begin(*>*) -text{*\noindent +text\\noindent So far, all recursive definitions were shown to terminate via measure functions. Sometimes this can be inconvenient or impossible. Fortunately, \isacommand{recdef} supports much more general definitions. For example, termination of Ackermann's function can be shown by means of the \rmindex{lexicographic product} @{text"<*lex*>"}: -*} +\ consts ack :: "nat\nat \ nat" recdef ack "measure(\m. m) <*lex*> measure(\n. n)" @@ -14,7 +14,7 @@ "ack(Suc m,0) = ack(m, 1)" "ack(Suc m,Suc n) = ack(m,ack(Suc m,n))" -text{*\noindent +text\\noindent The lexicographic product decreases if either its first component decreases (as in the second equation and in the outer call in the third equation) or its first component stays the same and the second @@ -39,7 +39,7 @@ product of two well-founded relations is again well-founded, which we relied on when defining Ackermann's function above. Of course the lexicographic product can also be iterated: -*} +\ consts contrived :: "nat \ nat \ nat \ nat" recdef contrived @@ -49,7 +49,7 @@ "contrived(Suc i,0,0) = contrived(i,i,i)" "contrived(0,0,0) = 0" -text{* +text\ Lexicographic products of measure functions already go a long way. Furthermore, you may embed a type in an existing well-founded relation via the inverse image construction @{term @@ -64,42 +64,42 @@ \isacommand{recdef}. For example, the greater-than relation can be made well-founded by cutting it off at a certain point. Here is an example of a recursive function that calls itself with increasing values up to ten: -*} +\ consts f :: "nat \ nat" recdef (*<*)(permissive)(*>*)f "{(i,j). j i \ (10::nat)}" "f i = (if 10 \ i then 0 else i * f(Suc i))" -text{*\noindent +text\\noindent Since \isacommand{recdef} is not prepared for the relation supplied above, Isabelle rejects the definition. We should first have proved that our relation was well-founded: -*} +\ lemma wf_greater: "wf {(i,j). j i \ (N::nat)}" -txt{*\noindent +txt\\noindent The proof is by showing that our relation is a subset of another well-founded relation: one given by a measure function.\index{*wf_subset (theorem)} -*} +\ apply (rule wf_subset [of "measure (\k::nat. N-k)"], blast) -txt{* +txt\ @{subgoals[display,indent=0,margin=65]} \noindent The inclusion remains to be proved. After unfolding some definitions, we are left with simple arithmetic that is dispatched automatically. -*} +\ by (clarify, simp add: measure_def inv_image_def) -text{*\noindent +text\\noindent Armed with this lemma, we use the \attrdx{recdef_wf} attribute to attach a crucial hint\cmmdx{hints} to our definition: -*} +\ (*<*) consts g :: "nat \ nat" recdef g "{(i,j). j i \ (10::nat)}" @@ -107,13 +107,13 @@ (*>*) (hints recdef_wf: wf_greater) -text{*\noindent +text\\noindent Alternatively, we could have given @{text "measure (\k::nat. 10-k)"} for the well-founded relation in our \isacommand{recdef}. However, the arithmetic goal in the lemma above would have arisen instead in the \isacommand{recdef} termination proof, where we have less control. A tailor-made termination relation makes even more sense when it can be used in several function declarations. -*} +\ (*<*)end(*>*)