equal
deleted
inserted
replaced
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} |