equal
deleted
inserted
replaced
30 \caption{A Theory of Lists} |
30 \caption{A Theory of Lists} |
31 \label{fig:ToyList} |
31 \label{fig:ToyList} |
32 \end{figure} |
32 \end{figure} |
33 |
33 |
34 \index{*ToyList example|(} |
34 \index{*ToyList example|(} |
35 {\makeatother\medskip\input{ToyList/document/ToyList.tex}} |
35 {\makeatother\medskip\input{document/ToyList.tex}} |
36 |
36 |
37 The complete proof script is shown in Fig.\ts\ref{fig:ToyList-proofs}. The |
37 The complete proof script is shown in Fig.\ts\ref{fig:ToyList-proofs}. The |
38 concatenation of Figs.\ts\ref{fig:ToyList} and~\ref{fig:ToyList-proofs} |
38 concatenation of Figs.\ts\ref{fig:ToyList} and~\ref{fig:ToyList-proofs} |
39 constitutes the complete theory \texttt{ToyList} and should reside in file |
39 constitutes the complete theory \texttt{ToyList} and should reside in file |
40 \texttt{ToyList.thy}. |
40 \texttt{ToyList.thy}. |
201 for each constructor. Their order is immaterial. |
201 for each constructor. Their order is immaterial. |
202 A more general method for defining total recursive functions is introduced in |
202 A more general method for defining total recursive functions is introduced in |
203 {\S}\ref{sec:fun}. |
203 {\S}\ref{sec:fun}. |
204 |
204 |
205 \begin{exercise}\label{ex:Tree} |
205 \begin{exercise}\label{ex:Tree} |
206 \input{Misc/document/Tree.tex}% |
206 \input{document/Tree.tex}% |
207 \end{exercise} |
207 \end{exercise} |
208 |
208 |
209 \input{Misc/document/case_exprs.tex} |
209 \input{document/case_exprs.tex} |
210 |
210 |
211 \input{Ifexpr/document/Ifexpr.tex} |
211 \input{document/Ifexpr.tex} |
212 \index{datatypes|)} |
212 \index{datatypes|)} |
213 |
213 |
214 |
214 |
215 \section{Some Basic Types} |
215 \section{Some Basic Types} |
216 |
216 |
220 |
220 |
221 \subsection{Natural Numbers} |
221 \subsection{Natural Numbers} |
222 \label{sec:nat}\index{natural numbers}% |
222 \label{sec:nat}\index{natural numbers}% |
223 \index{linear arithmetic|(} |
223 \index{linear arithmetic|(} |
224 |
224 |
225 \input{Misc/document/fakenat.tex}\medskip |
225 \input{document/fakenat.tex}\medskip |
226 \input{Misc/document/natsum.tex} |
226 \input{document/natsum.tex} |
227 |
227 |
228 \index{linear arithmetic|)} |
228 \index{linear arithmetic|)} |
229 |
229 |
230 |
230 |
231 \subsection{Pairs} |
231 \subsection{Pairs} |
232 \input{Misc/document/pairs.tex} |
232 \input{document/pairs.tex} |
233 |
233 |
234 \subsection{Datatype {\tt\slshape option}} |
234 \subsection{Datatype {\tt\slshape option}} |
235 \label{sec:option} |
235 \label{sec:option} |
236 \input{Misc/document/Option2.tex} |
236 \input{document/Option2.tex} |
237 |
237 |
238 \section{Definitions} |
238 \section{Definitions} |
239 \label{sec:Definitions} |
239 \label{sec:Definitions} |
240 |
240 |
241 A definition is simply an abbreviation, i.e.\ a new name for an existing |
241 A definition is simply an abbreviation, i.e.\ a new name for an existing |
250 \index{type synonyms}% |
250 \index{type synonyms}% |
251 Type synonyms are similar to those found in ML\@. They are created by a |
251 Type synonyms are similar to those found in ML\@. They are created by a |
252 \commdx{type\protect\_synonym} command: |
252 \commdx{type\protect\_synonym} command: |
253 |
253 |
254 \medskip |
254 \medskip |
255 \input{Misc/document/types.tex} |
255 \input{document/types.tex} |
256 |
256 |
257 \input{Misc/document/prime_def.tex} |
257 \input{document/prime_def.tex} |
258 |
258 |
259 |
259 |
260 \section{The Definitional Approach} |
260 \section{The Definitional Approach} |
261 \label{sec:definitional} |
261 \label{sec:definitional} |
262 |
262 |
329 {\S}\ref{sec:nat} above. Arithmetic expressions are simplified using built-in |
329 {\S}\ref{sec:nat} above. Arithmetic expressions are simplified using built-in |
330 procedures that go beyond mere rewrite rules. New simplification procedures |
330 procedures that go beyond mere rewrite rules. New simplification procedures |
331 can be coded and installed, but they are definitely not a matter for this |
331 can be coded and installed, but they are definitely not a matter for this |
332 tutorial. |
332 tutorial. |
333 |
333 |
334 \input{Misc/document/simp.tex} |
334 \input{document/simp.tex} |
335 |
335 |
336 \index{simplification|)} |
336 \index{simplification|)} |
337 |
337 |
338 \input{Misc/document/Itrev.tex} |
338 \input{document/Itrev.tex} |
339 \begin{exercise} |
339 \begin{exercise} |
340 \input{Misc/document/Plus.tex}% |
340 \input{document/Plus.tex}% |
341 \end{exercise} |
341 \end{exercise} |
342 \begin{exercise} |
342 \begin{exercise} |
343 \input{Misc/document/Tree2.tex}% |
343 \input{document/Tree2.tex}% |
344 \end{exercise} |
344 \end{exercise} |
345 |
345 |
346 \input{CodeGen/document/CodeGen.tex} |
346 \input{document/CodeGen.tex} |
347 |
347 |
348 |
348 |
349 \section{Advanced Datatypes} |
349 \section{Advanced Datatypes} |
350 \label{sec:advanced-datatypes} |
350 \label{sec:advanced-datatypes} |
351 \index{datatype@\isacommand {datatype} (command)|(} |
351 \index{datatype@\isacommand {datatype} (command)|(} |
358 |
358 |
359 |
359 |
360 \subsection{Mutual Recursion} |
360 \subsection{Mutual Recursion} |
361 \label{sec:datatype-mut-rec} |
361 \label{sec:datatype-mut-rec} |
362 |
362 |
363 \input{Datatype/document/ABexpr.tex} |
363 \input{document/ABexpr.tex} |
364 |
364 |
365 \subsection{Nested Recursion} |
365 \subsection{Nested Recursion} |
366 \label{sec:nested-datatype} |
366 \label{sec:nested-datatype} |
367 |
367 |
368 {\makeatother\input{Datatype/document/Nested.tex}} |
368 {\makeatother\input{document/Nested.tex}} |
369 |
369 |
370 |
370 |
371 \subsection{The Limits of Nested Recursion} |
371 \subsection{The Limits of Nested Recursion} |
372 \label{sec:nested-fun-datatype} |
372 \label{sec:nested-fun-datatype} |
373 |
373 |
390 is ruled out but the following example of a potentially |
390 is ruled out but the following example of a potentially |
391 \index{infinitely branching trees}% |
391 \index{infinitely branching trees}% |
392 infinitely branching tree is accepted: |
392 infinitely branching tree is accepted: |
393 \smallskip |
393 \smallskip |
394 |
394 |
395 \input{Datatype/document/Fundata.tex} |
395 \input{document/Fundata.tex} |
396 |
396 |
397 If you need nested recursion on the left of a function arrow, there are |
397 If you need nested recursion on the left of a function arrow, there are |
398 alternatives to pure HOL\@. In the Logic for Computable Functions |
398 alternatives to pure HOL\@. In the Logic for Computable Functions |
399 (\rmindex{LCF}), types like |
399 (\rmindex{LCF}), types like |
400 \begin{isabelle} |
400 \begin{isabelle} |
460 |
460 |
461 Proper tries associate some value with each string. Since the |
461 Proper tries associate some value with each string. Since the |
462 information is stored only in the final node associated with the string, many |
462 information is stored only in the final node associated with the string, many |
463 nodes do not carry any value. This distinction is modeled with the help |
463 nodes do not carry any value. This distinction is modeled with the help |
464 of the predefined datatype \isa{option} (see {\S}\ref{sec:option}). |
464 of the predefined datatype \isa{option} (see {\S}\ref{sec:option}). |
465 \input{Trie/document/Trie.tex} |
465 \input{document/Trie.tex} |
466 \index{tries|)} |
466 \index{tries|)} |
467 |
467 |
468 \section{Total Recursive Functions: \isacommand{fun}} |
468 \section{Total Recursive Functions: \isacommand{fun}} |
469 \label{sec:fun} |
469 \label{sec:fun} |
470 \index{fun@\isacommand {fun} (command)|(}\index{functions!total|(} |
470 \index{fun@\isacommand {fun} (command)|(}\index{functions!total|(} |
477 In this section we restrict ourselves to functions where Isabelle can prove |
477 In this section we restrict ourselves to functions where Isabelle can prove |
478 termination automatically. More advanced function definitions, including user |
478 termination automatically. More advanced function definitions, including user |
479 supplied termination proofs, nested recursion and partiality, are discussed |
479 supplied termination proofs, nested recursion and partiality, are discussed |
480 in a separate tutorial~\cite{isabelle-function}. |
480 in a separate tutorial~\cite{isabelle-function}. |
481 |
481 |
482 \input{Fun/document/fun0.tex} |
482 \input{document/fun0.tex} |
483 |
483 |
484 \index{fun@\isacommand {fun} (command)|)}\index{functions!total|)} |
484 \index{fun@\isacommand {fun} (command)|)}\index{functions!total|)} |