src/Doc/IsarImplementation/ML.thy
changeset 52416 383ffec6a548
parent 51636 e49bf0be79ba
child 52417 0590d4a83035
equal deleted inserted replaced
52415:d9fed6e99a57 52416:383ffec6a548
   809   decorate the code with meaningless permutations of arguments.
   809   decorate the code with meaningless permutations of arguments.
   810 
   810 
   811   This can be avoided by \emph{canonical argument order}, which
   811   This can be avoided by \emph{canonical argument order}, which
   812   observes certain standard patterns and minimizes adhoc permutations
   812   observes certain standard patterns and minimizes adhoc permutations
   813   in their application.  In Isabelle/ML, large portions of text can be
   813   in their application.  In Isabelle/ML, large portions of text can be
   814   written without ever using @{text "swap: \<alpha> \<times> \<beta> \<rightarrow> \<beta> \<times> \<alpha>"}, or the
   814   written without auxiliary operations like @{text "swap: \<alpha> \<times> \<beta> \<rightarrow> \<beta> \<times>
   815   combinator @{text "C: (\<alpha> \<rightarrow> \<beta> \<rightarrow> \<gamma>) \<rightarrow> (\<beta> \<rightarrow> \<alpha> \<rightarrow> \<gamma>)"} that is not even
   815   \<alpha>"} or @{text "C: (\<alpha> \<rightarrow> \<beta> \<rightarrow> \<gamma>) \<rightarrow> (\<beta> \<rightarrow> \<alpha> \<rightarrow> \<gamma>)"} (the latter not
   816   defined in our library.
   816   present in the Isabelle/ML library).
   817 
   817 
   818   \medskip The basic idea is that arguments that vary less are moved
   818   \medskip The basic idea is that arguments that vary less are moved
   819   further to the left than those that vary more.  Two particularly
   819   further to the left than those that vary more.  Two particularly
   820   important categories of functions are \emph{selectors} and
   820   important categories of functions are \emph{selectors} and
   821   \emph{updates}.
   821   \emph{updates}.
   823   The subsequent scheme is based on a hypothetical set-like container
   823   The subsequent scheme is based on a hypothetical set-like container
   824   of type @{text "\<beta>"} that manages elements of type @{text "\<alpha>"}.  Both
   824   of type @{text "\<beta>"} that manages elements of type @{text "\<alpha>"}.  Both
   825   the names and types of the associated operations are canonical for
   825   the names and types of the associated operations are canonical for
   826   Isabelle/ML.
   826   Isabelle/ML.
   827 
   827 
   828   \medskip
   828   \begin{center}
   829   \begin{tabular}{ll}
   829   \begin{tabular}{ll}
   830   kind & canonical name and type \\\hline
   830   kind & canonical name and type \\\hline
   831   selector & @{text "member: \<beta> \<rightarrow> \<alpha> \<rightarrow> bool"} \\
   831   selector & @{text "member: \<beta> \<rightarrow> \<alpha> \<rightarrow> bool"} \\
   832   update & @{text "insert: \<alpha> \<rightarrow> \<beta> \<rightarrow> \<beta>"} \\
   832   update & @{text "insert: \<alpha> \<rightarrow> \<beta> \<rightarrow> \<beta>"} \\
   833   \end{tabular}
   833   \end{tabular}
   834   \medskip
   834   \end{center}
   835 
   835 
   836   Given a container @{text "B: \<beta>"}, the partially applied @{text
   836   Given a container @{text "B: \<beta>"}, the partially applied @{text
   837   "member B"} is a predicate over elements @{text "\<alpha> \<rightarrow> bool"}, and
   837   "member B"} is a predicate over elements @{text "\<alpha> \<rightarrow> bool"}, and
   838   thus represents the intended denotation directly.  It is customary
   838   thus represents the intended denotation directly.  It is customary
   839   to pass the abstract predicate to further operations, not the
   839   to pass the abstract predicate to further operations, not the
   892   @{index_ML_op "|> ": "'a * ('a -> 'b) -> 'b"} \\
   892   @{index_ML_op "|> ": "'a * ('a -> 'b) -> 'b"} \\
   893   @{index_ML_op "|-> ": "('c * 'a) * ('c -> 'a -> 'b) -> 'b"} \\
   893   @{index_ML_op "|-> ": "('c * 'a) * ('c -> 'a -> 'b) -> 'b"} \\
   894   @{index_ML_op "#> ": "('a -> 'b) * ('b -> 'c) -> 'a -> 'c"} \\
   894   @{index_ML_op "#> ": "('a -> 'b) * ('b -> 'c) -> 'a -> 'c"} \\
   895   @{index_ML_op "#-> ": "('a -> 'c * 'b) * ('c -> 'b -> 'd) -> 'a -> 'd"} \\
   895   @{index_ML_op "#-> ": "('a -> 'c * 'b) * ('c -> 'b -> 'd) -> 'a -> 'd"} \\
   896   \end{mldecls}
   896   \end{mldecls}
   897 
       
   898   %FIXME description!?
       
   899 *}
   897 *}
   900 
   898 
   901 
   899 
   902 subsection {* Canonical iteration *}
   900 subsection {* Canonical iteration *}
   903 
   901 
   952   The literature on functional programming provides a multitude of
   950   The literature on functional programming provides a multitude of
   953   combinators called @{text "foldl"}, @{text "foldr"} etc.  SML97
   951   combinators called @{text "foldl"}, @{text "foldr"} etc.  SML97
   954   provides its own variations as @{ML List.foldl} and @{ML
   952   provides its own variations as @{ML List.foldl} and @{ML
   955   List.foldr}, while the classic Isabelle library also has the
   953   List.foldr}, while the classic Isabelle library also has the
   956   historic @{ML Library.foldl} and @{ML Library.foldr}.  To avoid
   954   historic @{ML Library.foldl} and @{ML Library.foldr}.  To avoid
   957   further confusion, all of this should be ignored, and @{ML fold} (or
   955   unnecessary complication and confusion, all these historical
   958   @{ML fold_rev}) used exclusively.
   956   versions should be ignored, and @{ML fold} (or @{ML fold_rev}) used
       
   957   exclusively.
   959   \end{warn}
   958   \end{warn}
   960 *}
   959 *}
   961 
   960 
   962 text %mlex {* The following example shows how to fill a text buffer
   961 text %mlex {* The following example shows how to fill a text buffer
   963   incrementally by adding strings, either individually or from a given
   962   incrementally by adding strings, either individually or from a given
   975 *}
   974 *}
   976 
   975 
   977 text {* Note how @{ML "fold (Buffer.add o string_of_int)"} above saves
   976 text {* Note how @{ML "fold (Buffer.add o string_of_int)"} above saves
   978   an extra @{ML "map"} over the given list.  This kind of peephole
   977   an extra @{ML "map"} over the given list.  This kind of peephole
   979   optimization reduces both the code size and the tree structures in
   978   optimization reduces both the code size and the tree structures in
   980   memory (``deforestation''), but requires some practice to read and
   979   memory (``deforestation''), but it requires some practice to read
   981   write it fluently.
   980   and write fluently.
   982 
   981 
   983   \medskip The next example elaborates the idea of canonical
   982   \medskip The next example elaborates the idea of canonical
   984   iteration, demonstrating fast accumulation of tree content using a
   983   iteration, demonstrating fast accumulation of tree content using a
   985   text buffer.
   984   text buffer.
   986 *}
   985 *}
  1090 
  1089 
  1091   \begin{warn}
  1090   \begin{warn}
  1092   The actual error channel is accessed via @{ML Output.error_msg}, but
  1091   The actual error channel is accessed via @{ML Output.error_msg}, but
  1093   the old interaction protocol of Proof~General \emph{crashes} if that
  1092   the old interaction protocol of Proof~General \emph{crashes} if that
  1094   function is used in regular ML code: error output and toplevel
  1093   function is used in regular ML code: error output and toplevel
  1095   command failure always need to coincide.
  1094   command failure always need to coincide in classic TTY interaction.
  1096   \end{warn}
  1095   \end{warn}
  1097 
  1096 
  1098   \end{description}
  1097   \end{description}
  1099 
  1098 
  1100   \begin{warn}
  1099   \begin{warn}