doc-src/TutorialI/fp.tex
changeset 11419 9577530e8a5a
parent 11309 d666f11ca2d4
child 11428 332347b9b942
equal deleted inserted replaced
11418:53a402c10ba9 11419:9577530e8a5a
    64 and can be skipped by casual readers.
    64 and can be skipped by casual readers.
    65 
    65 
    66 There are two kinds of commands used during a proof: the actual proof
    66 There are two kinds of commands used during a proof: the actual proof
    67 commands and auxiliary commands for examining the proof state and controlling
    67 commands and auxiliary commands for examining the proof state and controlling
    68 the display. Simple proof commands are of the form
    68 the display. Simple proof commands are of the form
    69 \isacommand{apply}\isa{(method)}\indexbold{apply} where \bfindex{method} is a
    69 \commdx{apply}\isa{(method)}, where \isa{method} is typically 
    70 synonym for ``theorem proving function''. Typical examples are
    70 \isa{induct_tac} or \isa{auto}.  All such theorem proving operations
    71 \isa{induct_tac} and \isa{auto}. Further methods are introduced throughout
    71 are referred to as \bfindex{methods}, and further ones are
    72 the tutorial.  Unless stated otherwise you may assume that a method attacks
    72 introduced throughout the tutorial.  Unless stated otherwise, you may
    73 merely the first subgoal. An exception is \isa{auto} which tries to solve all
    73 assume that a method attacks merely the first subgoal. An exception is
    74 subgoals.
    74 \isa{auto}, which tries to solve all subgoals.
    75 
    75 
    76 The most useful auxiliary commands are:
    76 The most useful auxiliary commands are as follows:
    77 \begin{description}
    77 \begin{description}
    78 \item[Undoing:] \isacommand{undo}\indexbold{*undo} undoes the effect of the
    78 \item[Undoing:] \commdx{undo} undoes the effect of
       
    79 the
    79   last command; \isacommand{undo} can be undone by
    80   last command; \isacommand{undo} can be undone by
    80   \isacommand{redo}\indexbold{*redo}.  Both are only needed at the shell
    81   \commdx{redo}.  Both are only needed at the shell
    81   level and should not occur in the final theory.
    82   level and should not occur in the final theory.
    82 \item[Printing the current state:] \isacommand{pr}\indexbold{*pr} redisplays
    83 \item[Printing the current state:] \commdx{pr}
       
    84 redisplays
    83   the current proof state, for example when it has scrolled past the top of
    85   the current proof state, for example when it has scrolled past the top of
    84   the screen.
    86   the screen.
    85 \item[Limiting the number of subgoals:] \isacommand{pr}~$n$ tells Isabelle to
    87 \item[Limiting the number of subgoals:] \isacommand{pr}~$n$ tells Isabelle to
    86   print only the first $n$ subgoals from now on and redisplays the current
    88   print only the first $n$ subgoals from now on and redisplays the current
    87   proof state. This is helpful when there are many subgoals.
    89   proof state. This is helpful when there are many subgoals.
    88 \item[Modifying the order of subgoals:]
    90 \item[Modifying the order of subgoals:]
    89 \isacommand{defer}\indexbold{*defer} moves the first subgoal to the end and
    91 \commdx{defer} moves the first subgoal to the end and
    90 \isacommand{prefer}\indexbold{*prefer}~$n$ moves subgoal $n$ to the front.
    92 \commdx{prefer}~$n$ moves subgoal $n$ to the front.
    91 \item[Printing theorems:]
    93 \item[Printing theorems:]
    92   \isacommand{thm}\indexbold{*thm}~\textit{name}$@1$~\dots~\textit{name}$@n$
    94   \commdx{thm}~\textit{name}$@1$~\dots~\textit{name}$@n$
    93   prints the named theorems.
    95   prints the named theorems.
    94 \item[Displaying types:] We have already mentioned the flag
    96 \item[Displaying types:] We have already mentioned the flag
    95   \ttindex{show_types} above. It can also be useful for detecting typos in
    97   \ttindex{show_types} above. It can also be useful for detecting typos in
    96   formulae early on. For example, if \texttt{show_types} is set and the goal
    98   formulae early on. For example, if \texttt{show_types} is set and the goal
    97   \isa{rev(rev xs) = xs} is started, Isabelle prints the additional output
    99   \isa{rev(rev xs) = xs} is started, Isabelle prints the additional output
   110 ~~re~::~'a~list~{\isasymRightarrow}~'a~list\isanewline
   112 ~~re~::~'a~list~{\isasymRightarrow}~'a~list\isanewline
   111 ~~xs~::~'a~list%
   113 ~~xs~::~'a~list%
   112 \end{isabelle}%
   114 \end{isabelle}%
   113 \par\noindent
   115 \par\noindent
   114 would have alerted us because of the unexpected variable \isa{re}.
   116 would have alerted us because of the unexpected variable \isa{re}.
   115 \item[Reading terms and types:] \isacommand{term}\indexbold{*term}
   117 \item[Reading terms and types:] \commdx{term}
   116   \textit{string} reads, type-checks and prints the given string as a term in
   118   \textit{string} reads, type-checks and prints the given string as a term in
   117   the current context; the inferred type is output as well.
   119   the current context; the inferred type is output as well.
   118   \isacommand{typ}\indexbold{*typ} \textit{string} reads and prints the given
   120   \commdx{typ} \textit{string} reads and prints the given
   119   string as a type in the current context.
   121   string as a type in the current context.
   120 \item[(Re)loading theories:] When you start your interaction you must open a
   122 \item[(Re)loading theories:] When you start your interaction you must open a
   121   named theory with the line \isa{\isacommand{theory}~T~=~\dots~:}. Isabelle
   123   named theory with the line \isa{\isacommand{theory}~T~=~\dots~:}. Isabelle
   122   automatically loads all the required parent theories from their respective
   124   automatically loads all the required parent theories from their respective
   123   files (which may take a moment, unless the theories are already loaded and
   125   files (which may take a moment, unless the theories are already loaded and
   124   the files have not been modified).
   126   the files have not been modified).
   125   
   127   
   126   If you suddenly discover that you need to modify a parent theory of your
   128   If you suddenly discover that you need to modify a parent theory of your
   127   current theory, you must first abandon your current theory\indexbold{abandon
   129   current theory, you must first abandon your current theory\indexbold{abandon
   128   theory}\indexbold{theory!abandon} (at the shell
   130   theory}\indexbold{theory!abandon} (at the shell
   129   level type \isacommand{kill}\indexbold{*kill}). After the parent theory has
   131   level type \commdx{kill}). After the parent theory has
   130   been modified, you go back to your original theory. When its first line
   132   been modified, you go back to your original theory. When its first line
   131   \isa{\isacommand{theory}~T~=~\dots~:} is processed, the
   133   \isa{\isacommand{theory}~T~=~\dots~:} is processed, the
   132   modified parent is reloaded automatically.
   134   modified parent is reloaded automatically.
   133   
   135   
   134 %  The only time when you need to load a theory by hand is when you simply
   136 %  The only time when you need to load a theory by hand is when you simply
   135 %  want to check if it loads successfully without wanting to make use of the
   137 %  want to check if it loads successfully without wanting to make use of the
   136 %  theory itself. This you can do by typing
   138 %  theory itself. This you can do by typing
   137 %  \isa{\isacommand{use\_thy}\indexbold{*use_thy}~"T"}.
   139 %  \isa{\commdx{use\_thy}~"T"}.
   138 \end{description}
   140 \end{description}
   139 Further commands are found in the Isabelle/Isar Reference Manual.
   141 Further commands are found in the Isabelle/Isar Reference Manual.
   140 
   142 
   141 We now examine Isabelle's functional programming constructs systematically,
   143 We now examine Isabelle's functional programming constructs systematically,
   142 starting with inductive datatypes.
   144 starting with inductive datatypes.
   157 Lists are one of the essential datatypes in computing. Readers of this
   159 Lists are one of the essential datatypes in computing. Readers of this
   158 tutorial and users of HOL need to be familiar with their basic operations.
   160 tutorial and users of HOL need to be familiar with their basic operations.
   159 Theory \isa{ToyList} is only a small fragment of HOL's predefined theory
   161 Theory \isa{ToyList} is only a small fragment of HOL's predefined theory
   160 \isa{List}\footnote{\url{http://isabelle.in.tum.de/library/HOL/List.html}}.
   162 \isa{List}\footnote{\url{http://isabelle.in.tum.de/library/HOL/List.html}}.
   161 The latter contains many further operations. For example, the functions
   163 The latter contains many further operations. For example, the functions
   162 \isaindexbold{hd} (``head'') and \isaindexbold{tl} (``tail'') return the first
   164 \cdx{hd} (``head'') and \cdx{tl} (``tail'') return the first
   163 element and the remainder of a list. (However, pattern-matching is usually
   165 element and the remainder of a list. (However, pattern-matching is usually
   164 preferable to \isa{hd} and \isa{tl}.)  
   166 preferable to \isa{hd} and \isa{tl}.)  
   165 Also available are higher-order functions like \isa{map} and \isa{filter}.
   167 Also available are higher-order functions like \isa{map} and \isa{filter}.
   166 Theory \isa{List} also contains
   168 Theory \isa{List} also contains
   167 more syntactic sugar: \isa{[}$x@1$\isa{,}\dots\isa{,}$x@n$\isa{]} abbreviates
   169 more syntactic sugar: \isa{[}$x@1$\isa{,}\dots\isa{,}$x@n$\isa{]} abbreviates
   190 primitive recursive function definitions.
   192 primitive recursive function definitions.
   191 
   193 
   192 Every datatype $t$ comes equipped with a \isa{size} function from $t$ into
   194 Every datatype $t$ comes equipped with a \isa{size} function from $t$ into
   193 the natural numbers (see~{\S}\ref{sec:nat} below). For lists, \isa{size} is
   195 the natural numbers (see~{\S}\ref{sec:nat} below). For lists, \isa{size} is
   194 just the length, i.e.\ \isa{size [] = 0} and \isa{size(x \# xs) = size xs +
   196 just the length, i.e.\ \isa{size [] = 0} and \isa{size(x \# xs) = size xs +
   195   1}.  In general, \isaindexbold{size} returns \isa{0} for all constructors
   197   1}.  In general, \cdx{size} returns \isa{0} for all constructors
   196 that do not have an argument of type $t$, and for all other constructors
   198 that do not have an argument of type $t$, and for all other constructors
   197 \isa{1 +} the sum of the sizes of all arguments of type $t$. Note that because
   199 \isa{1 +} the sum of the sizes of all arguments of type $t$. Note that because
   198 \isa{size} is defined on every datatype, it is overloaded; on lists
   200 \isa{size} is defined on every datatype, it is overloaded; on lists
   199 \isa{size} is also called \isaindexbold{length}, which is not overloaded.
   201 \isa{size} is also called \sdx{length}, which is not overloaded.
   200 Isabelle will always show \isa{size} on lists as \isa{length}.
   202 Isabelle will always show \isa{size} on lists as \isa{length}.
   201 
   203 
   202 
   204 
   203 \subsection{Primitive Recursion}
   205 \subsection{Primitive Recursion}
   204 
   206