doc-src/TutorialI/fp.tex
changeset 48522 708278fc2dff
parent 44049 9f9a40e778d6
child 48524 5af593945522
equal deleted inserted replaced
48521:0e4bb86c74fd 48522:708278fc2dff
    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|)}