623 here.\footnote{Such a stateless compilation environment is also a |
623 here.\footnote{Such a stateless compilation environment is also a |
624 prerequisite for robust parallel compilation within independent |
624 prerequisite for robust parallel compilation within independent |
625 nodes of the implicit theory development graph.} |
625 nodes of the implicit theory development graph.} |
626 |
626 |
627 \medskip The next example shows how to embed ML into Isar proofs, using |
627 \medskip The next example shows how to embed ML into Isar proofs, using |
628 \indexref{}{command}{ML\_prf}\hyperlink{command.ML-prf}{\mbox{\isa{\isacommand{ML{\isacharunderscore}prf}}}} instead of Instead of \indexref{}{command}{ML}\hyperlink{command.ML}{\mbox{\isa{\isacommand{ML}}}}. |
628 \indexref{}{command}{ML\_prf}\hyperlink{command.ML-prf}{\mbox{\isa{\isacommand{ML{\isaliteral{5F}{\isacharunderscore}}prf}}}} instead of Instead of \indexref{}{command}{ML}\hyperlink{command.ML}{\mbox{\isa{\isacommand{ML}}}}. |
629 As illustrated below, the effect on the ML environment is local to |
629 As illustrated below, the effect on the ML environment is local to |
630 the whole proof body, ignoring the block structure.% |
630 the whole proof body, ignoring the block structure.% |
631 \end{isamarkuptext}% |
631 \end{isamarkuptext}% |
632 \isamarkuptrue% |
632 \isamarkuptrue% |
633 \isacommand{example{\isacharunderscore}proof}\isamarkupfalse% |
633 \isacommand{example{\isaliteral{5F}{\isacharunderscore}}proof}\isamarkupfalse% |
634 \isanewline |
634 \isanewline |
635 % |
635 % |
636 \isadelimML |
636 \isadelimML |
637 \ \ % |
637 \ \ % |
638 \endisadelimML |
638 \endisadelimML |
639 % |
639 % |
640 \isatagML |
640 \isatagML |
641 \isacommand{ML{\isacharunderscore}prf}\isamarkupfalse% |
641 \isacommand{ML{\isaliteral{5F}{\isacharunderscore}}prf}\isamarkupfalse% |
642 \ {\isacharverbatimopen}\ val\ a\ {\isacharequal}\ {\isadigit{1}}\ {\isacharverbatimclose}\isanewline |
642 \ {\isaliteral{7B2A}{\isacharverbatimopen}}\ val\ a\ {\isaliteral{3D}{\isacharequal}}\ {\isadigit{1}}\ {\isaliteral{2A7D}{\isacharverbatimclose}}\isanewline |
643 \ \ \isacommand{{\isacharbraceleft}}\isamarkupfalse% |
643 \ \ \isacommand{{\isaliteral{7B}{\isacharbraceleft}}}\isamarkupfalse% |
644 \isanewline |
644 \isanewline |
645 \ \ \ \ \isacommand{ML{\isacharunderscore}prf}\isamarkupfalse% |
645 \ \ \ \ \isacommand{ML{\isaliteral{5F}{\isacharunderscore}}prf}\isamarkupfalse% |
646 \ {\isacharverbatimopen}\ val\ b\ {\isacharequal}\ a\ {\isacharplus}\ {\isadigit{1}}\ {\isacharverbatimclose}\isanewline |
646 \ {\isaliteral{7B2A}{\isacharverbatimopen}}\ val\ b\ {\isaliteral{3D}{\isacharequal}}\ a\ {\isaliteral{2B}{\isacharplus}}\ {\isadigit{1}}\ {\isaliteral{2A7D}{\isacharverbatimclose}}\isanewline |
647 \ \ \isacommand{{\isacharbraceright}}\isamarkupfalse% |
647 \ \ \isacommand{{\isaliteral{7D}{\isacharbraceright}}}\isamarkupfalse% |
648 \ % |
648 \ % |
649 \isamarkupcmt{Isar block structure ignored by ML environment% |
649 \isamarkupcmt{Isar block structure ignored by ML environment% |
650 } |
650 } |
651 \isanewline |
651 \isanewline |
652 \ \ \isacommand{ML{\isacharunderscore}prf}\isamarkupfalse% |
652 \ \ \isacommand{ML{\isaliteral{5F}{\isacharunderscore}}prf}\isamarkupfalse% |
653 \ {\isacharverbatimopen}\ val\ c\ {\isacharequal}\ b\ {\isacharplus}\ {\isadigit{1}}\ {\isacharverbatimclose}\isanewline |
653 \ {\isaliteral{7B2A}{\isacharverbatimopen}}\ val\ c\ {\isaliteral{3D}{\isacharequal}}\ b\ {\isaliteral{2B}{\isacharplus}}\ {\isadigit{1}}\ {\isaliteral{2A7D}{\isacharverbatimclose}}\isanewline |
654 \isacommand{qed}\isamarkupfalse% |
654 \isacommand{qed}\isamarkupfalse% |
655 % |
655 % |
656 \endisatagML |
656 \endisatagML |
657 {\isafoldML}% |
657 {\isafoldML}% |
658 % |
658 % |
665 blocks, embedded ML code can refer to the different contexts and |
665 blocks, embedded ML code can refer to the different contexts and |
666 manipulate corresponding entities, e.g.\ export a fact from a block |
666 manipulate corresponding entities, e.g.\ export a fact from a block |
667 context. |
667 context. |
668 |
668 |
669 \medskip Two further ML commands are useful in certain situations: |
669 \medskip Two further ML commands are useful in certain situations: |
670 \indexref{}{command}{ML\_val}\hyperlink{command.ML-val}{\mbox{\isa{\isacommand{ML{\isacharunderscore}val}}}} and \indexref{}{command}{ML\_command}\hyperlink{command.ML-command}{\mbox{\isa{\isacommand{ML{\isacharunderscore}command}}}} are |
670 \indexref{}{command}{ML\_val}\hyperlink{command.ML-val}{\mbox{\isa{\isacommand{ML{\isaliteral{5F}{\isacharunderscore}}val}}}} and \indexref{}{command}{ML\_command}\hyperlink{command.ML-command}{\mbox{\isa{\isacommand{ML{\isaliteral{5F}{\isacharunderscore}}command}}}} are |
671 \emph{diagnostic} in the sense that there is no effect on the |
671 \emph{diagnostic} in the sense that there is no effect on the |
672 underlying environment, and can thus used anywhere (even outside a |
672 underlying environment, and can thus used anywhere (even outside a |
673 theory). The examples below produce long strings of digits by |
673 theory). The examples below produce long strings of digits by |
674 invoking \verb|factorial|: \hyperlink{command.ML-val}{\mbox{\isa{\isacommand{ML{\isacharunderscore}val}}}} already takes care of |
674 invoking \verb|factorial|: \hyperlink{command.ML-val}{\mbox{\isa{\isacommand{ML{\isaliteral{5F}{\isacharunderscore}}val}}}} already takes care of |
675 printing the ML toplevel result, but \hyperlink{command.ML-command}{\mbox{\isa{\isacommand{ML{\isacharunderscore}command}}}} is silent |
675 printing the ML toplevel result, but \hyperlink{command.ML-command}{\mbox{\isa{\isacommand{ML{\isaliteral{5F}{\isacharunderscore}}command}}}} is silent |
676 so we produce an explicit output message.% |
676 so we produce an explicit output message.% |
677 \end{isamarkuptext}% |
677 \end{isamarkuptext}% |
678 \isamarkuptrue% |
678 \isamarkuptrue% |
679 % |
679 % |
680 \isadelimML |
680 \isadelimML |
681 % |
681 % |
682 \endisadelimML |
682 \endisadelimML |
683 % |
683 % |
684 \isatagML |
684 \isatagML |
685 \isacommand{ML{\isacharunderscore}val}\isamarkupfalse% |
685 \isacommand{ML{\isaliteral{5F}{\isacharunderscore}}val}\isamarkupfalse% |
686 \ {\isacharverbatimopen}\ factorial\ {\isadigit{1}}{\isadigit{0}}{\isadigit{0}}\ {\isacharverbatimclose}\isanewline |
686 \ {\isaliteral{7B2A}{\isacharverbatimopen}}\ factorial\ {\isadigit{1}}{\isadigit{0}}{\isadigit{0}}\ {\isaliteral{2A7D}{\isacharverbatimclose}}\isanewline |
687 \isacommand{ML{\isacharunderscore}command}\isamarkupfalse% |
687 \isacommand{ML{\isaliteral{5F}{\isacharunderscore}}command}\isamarkupfalse% |
688 \ {\isacharverbatimopen}\ writeln\ {\isacharparenleft}string{\isacharunderscore}of{\isacharunderscore}int\ {\isacharparenleft}factorial\ {\isadigit{1}}{\isadigit{0}}{\isadigit{0}}{\isacharparenright}{\isacharparenright}\ {\isacharverbatimclose}% |
688 \ {\isaliteral{7B2A}{\isacharverbatimopen}}\ writeln\ {\isaliteral{28}{\isacharparenleft}}string{\isaliteral{5F}{\isacharunderscore}}of{\isaliteral{5F}{\isacharunderscore}}int\ {\isaliteral{28}{\isacharparenleft}}factorial\ {\isadigit{1}}{\isadigit{0}}{\isadigit{0}}{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{2A7D}{\isacharverbatimclose}}% |
689 \endisatagML |
689 \endisatagML |
690 {\isafoldML}% |
690 {\isafoldML}% |
691 % |
691 % |
692 \isadelimML |
692 \isadelimML |
693 % |
693 % |
694 \endisadelimML |
694 \endisadelimML |
695 \isanewline |
695 \isanewline |
696 \isanewline |
696 \isanewline |
697 \isacommand{example{\isacharunderscore}proof}\isamarkupfalse% |
697 \isacommand{example{\isaliteral{5F}{\isacharunderscore}}proof}\isamarkupfalse% |
698 \isanewline |
698 \isanewline |
699 % |
699 % |
700 \isadelimML |
700 \isadelimML |
701 \ \ % |
701 \ \ % |
702 \endisadelimML |
702 \endisadelimML |
703 % |
703 % |
704 \isatagML |
704 \isatagML |
705 \isacommand{ML{\isacharunderscore}val}\isamarkupfalse% |
705 \isacommand{ML{\isaliteral{5F}{\isacharunderscore}}val}\isamarkupfalse% |
706 \ {\isacharverbatimopen}\ factorial\ {\isadigit{1}}{\isadigit{0}}{\isadigit{0}}\ {\isacharverbatimclose}\ \ \isanewline |
706 \ {\isaliteral{7B2A}{\isacharverbatimopen}}\ factorial\ {\isadigit{1}}{\isadigit{0}}{\isadigit{0}}\ {\isaliteral{2A7D}{\isacharverbatimclose}}\ \ \isanewline |
707 \ \ \isacommand{ML{\isacharunderscore}command}\isamarkupfalse% |
707 \ \ \isacommand{ML{\isaliteral{5F}{\isacharunderscore}}command}\isamarkupfalse% |
708 \ {\isacharverbatimopen}\ writeln\ {\isacharparenleft}string{\isacharunderscore}of{\isacharunderscore}int\ {\isacharparenleft}factorial\ {\isadigit{1}}{\isadigit{0}}{\isadigit{0}}{\isacharparenright}{\isacharparenright}\ {\isacharverbatimclose}% |
708 \ {\isaliteral{7B2A}{\isacharverbatimopen}}\ writeln\ {\isaliteral{28}{\isacharparenleft}}string{\isaliteral{5F}{\isacharunderscore}}of{\isaliteral{5F}{\isacharunderscore}}int\ {\isaliteral{28}{\isacharparenleft}}factorial\ {\isadigit{1}}{\isadigit{0}}{\isadigit{0}}{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{2A7D}{\isacharverbatimclose}}% |
709 \endisatagML |
709 \endisatagML |
710 {\isafoldML}% |
710 {\isafoldML}% |
711 % |
711 % |
712 \isadelimML |
712 \isadelimML |
713 \isanewline |
713 \isanewline |
809 |
809 |
810 Here \hyperlink{syntax.nameref}{\mbox{\isa{nameref}}} and \hyperlink{syntax.args}{\mbox{\isa{args}}} are regular outer syntax |
810 Here \hyperlink{syntax.nameref}{\mbox{\isa{nameref}}} and \hyperlink{syntax.args}{\mbox{\isa{args}}} are regular outer syntax |
811 categories \cite{isabelle-isar-ref}. Attributes and proof methods |
811 categories \cite{isabelle-isar-ref}. Attributes and proof methods |
812 use similar syntax. |
812 use similar syntax. |
813 |
813 |
814 \medskip A regular antiquotation \isa{{\isacharat}{\isacharbraceleft}name\ args{\isacharbraceright}} processes |
814 \medskip A regular antiquotation \isa{{\isaliteral{40}{\isacharat}}{\isaliteral{7B}{\isacharbraceleft}}name\ args{\isaliteral{7D}{\isacharbraceright}}} processes |
815 its arguments by the usual means of the Isar source language, and |
815 its arguments by the usual means of the Isar source language, and |
816 produces corresponding ML source text, either as literal |
816 produces corresponding ML source text, either as literal |
817 \emph{inline} text (e.g. \isa{{\isacharat}{\isacharbraceleft}term\ t{\isacharbraceright}}) or abstract |
817 \emph{inline} text (e.g. \isa{{\isaliteral{40}{\isacharat}}{\isaliteral{7B}{\isacharbraceleft}}term\ t{\isaliteral{7D}{\isacharbraceright}}}) or abstract |
818 \emph{value} (e.g. \isa{{\isacharat}{\isacharbraceleft}thm\ th{\isacharbraceright}}). This pre-compilation |
818 \emph{value} (e.g. \isa{{\isaliteral{40}{\isacharat}}{\isaliteral{7B}{\isacharbraceleft}}thm\ th{\isaliteral{7D}{\isacharbraceright}}}). This pre-compilation |
819 scheme allows to refer to formal entities in a robust manner, with |
819 scheme allows to refer to formal entities in a robust manner, with |
820 proper static scoping and with some degree of logical checking of |
820 proper static scoping and with some degree of logical checking of |
821 small portions of the code. |
821 small portions of the code. |
822 |
822 |
823 Special antiquotations like \isa{{\isacharat}{\isacharbraceleft}let\ {\isasymdots}{\isacharbraceright}} or \isa{{\isacharat}{\isacharbraceleft}note\ {\isasymdots}{\isacharbraceright}} augment the compilation context without generating code. The |
823 Special antiquotations like \isa{{\isaliteral{40}{\isacharat}}{\isaliteral{7B}{\isacharbraceleft}}let\ {\isaliteral{5C3C646F74733E}{\isasymdots}}{\isaliteral{7D}{\isacharbraceright}}} or \isa{{\isaliteral{40}{\isacharat}}{\isaliteral{7B}{\isacharbraceleft}}note\ {\isaliteral{5C3C646F74733E}{\isasymdots}}{\isaliteral{7D}{\isacharbraceright}}} augment the compilation context without generating code. The |
824 non-ASCII braces \isa{{\isasymlbrace}} and \isa{{\isasymrbrace}} allow to delimit the |
824 non-ASCII braces \isa{{\isaliteral{5C3C6C62726163653E}{\isasymlbrace}}} and \isa{{\isaliteral{5C3C7262726163653E}{\isasymrbrace}}} allow to delimit the |
825 effect by introducing local blocks within the pre-compilation |
825 effect by introducing local blocks within the pre-compilation |
826 environment. |
826 environment. |
827 |
827 |
828 \medskip See also \cite{Wenzel-Chaieb:2007b} for a broader |
828 \medskip See also \cite{Wenzel-Chaieb:2007b} for a broader |
829 perspective on Isabelle/ML antiquotations.% |
829 perspective on Isabelle/ML antiquotations.% |
935 \isamarkupsection{Canonical argument order \label{sec:canonical-argument-order}% |
935 \isamarkupsection{Canonical argument order \label{sec:canonical-argument-order}% |
936 } |
936 } |
937 \isamarkuptrue% |
937 \isamarkuptrue% |
938 % |
938 % |
939 \begin{isamarkuptext}% |
939 \begin{isamarkuptext}% |
940 Standard ML is a language in the tradition of \isa{{\isasymlambda}}-calculus and \emph{higher-order functional programming}, |
940 Standard ML is a language in the tradition of \isa{{\isaliteral{5C3C6C616D6264613E}{\isasymlambda}}}-calculus and \emph{higher-order functional programming}, |
941 similar to OCaml, Haskell, or Isabelle/Pure and HOL as logical |
941 similar to OCaml, Haskell, or Isabelle/Pure and HOL as logical |
942 languages. Getting acquainted with the native style of representing |
942 languages. Getting acquainted with the native style of representing |
943 functions in that setting can save a lot of extra boiler-plate of |
943 functions in that setting can save a lot of extra boiler-plate of |
944 redundant shuffling of arguments, auxiliary abstractions etc. |
944 redundant shuffling of arguments, auxiliary abstractions etc. |
945 |
945 |
946 Functions are usually \emph{curried}: the idea of turning arguments |
946 Functions are usually \emph{curried}: the idea of turning arguments |
947 of type \isa{{\isasymtau}\isactrlsub i} (for \isa{i\ {\isasymin}\ {\isacharbraceleft}{\isadigit{1}}{\isacharcomma}\ {\isasymdots}\ n{\isacharbraceright}}) into a result of |
947 of type \isa{{\isaliteral{5C3C7461753E}{\isasymtau}}\isaliteral{5C3C5E7375623E}{}\isactrlsub i} (for \isa{i\ {\isaliteral{5C3C696E3E}{\isasymin}}\ {\isaliteral{7B}{\isacharbraceleft}}{\isadigit{1}}{\isaliteral{2C}{\isacharcomma}}\ {\isaliteral{5C3C646F74733E}{\isasymdots}}\ n{\isaliteral{7D}{\isacharbraceright}}}) into a result of |
948 type \isa{{\isasymtau}} is represented by the iterated function space |
948 type \isa{{\isaliteral{5C3C7461753E}{\isasymtau}}} is represented by the iterated function space |
949 \isa{{\isasymtau}\isactrlsub {\isadigit{1}}\ {\isasymrightarrow}\ {\isasymdots}\ {\isasymrightarrow}\ {\isasymtau}\isactrlsub n\ {\isasymrightarrow}\ {\isasymtau}}. This is isomorphic to the well-known |
949 \isa{{\isaliteral{5C3C7461753E}{\isasymtau}}\isaliteral{5C3C5E7375623E}{}\isactrlsub {\isadigit{1}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C646F74733E}{\isasymdots}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C7461753E}{\isasymtau}}\isaliteral{5C3C5E7375623E}{}\isactrlsub n\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C7461753E}{\isasymtau}}}. This is isomorphic to the well-known |
950 encoding via tuples \isa{{\isasymtau}\isactrlsub {\isadigit{1}}\ {\isasymtimes}\ {\isasymdots}\ {\isasymtimes}\ {\isasymtau}\isactrlsub n\ {\isasymrightarrow}\ {\isasymtau}}, but the curried |
950 encoding via tuples \isa{{\isaliteral{5C3C7461753E}{\isasymtau}}\isaliteral{5C3C5E7375623E}{}\isactrlsub {\isadigit{1}}\ {\isaliteral{5C3C74696D65733E}{\isasymtimes}}\ {\isaliteral{5C3C646F74733E}{\isasymdots}}\ {\isaliteral{5C3C74696D65733E}{\isasymtimes}}\ {\isaliteral{5C3C7461753E}{\isasymtau}}\isaliteral{5C3C5E7375623E}{}\isactrlsub n\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C7461753E}{\isasymtau}}}, but the curried |
951 version fits more smoothly into the basic calculus.\footnote{The |
951 version fits more smoothly into the basic calculus.\footnote{The |
952 difference is even more significant in higher-order logic, because |
952 difference is even more significant in higher-order logic, because |
953 the redundant tuple structure needs to be accommodated by formal |
953 the redundant tuple structure needs to be accommodated by formal |
954 reasoning.} |
954 reasoning.} |
955 |
955 |
956 Currying gives some flexiblity due to \emph{partial application}. A |
956 Currying gives some flexiblity due to \emph{partial application}. A |
957 function \isa{f{\isacharcolon}\ {\isasymtau}\isactrlsub {\isadigit{1}}\ {\isasymrightarrow}\ {\isasymtau}\isactrlbsub {\isadigit{2}}\isactrlesub \ {\isasymrightarrow}\ {\isasymtau}} can be applied to \isa{x{\isacharcolon}\ {\isasymtau}\isactrlsub {\isadigit{1}}} |
957 function \isa{f{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{5C3C7461753E}{\isasymtau}}\isaliteral{5C3C5E7375623E}{}\isactrlsub {\isadigit{1}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C7461753E}{\isasymtau}}\isaliteral{5C3C5E627375623E}{}\isactrlbsub {\isadigit{2}}\isaliteral{5C3C5E657375623E}{}\isactrlesub \ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C7461753E}{\isasymtau}}} can be applied to \isa{x{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{5C3C7461753E}{\isasymtau}}\isaliteral{5C3C5E7375623E}{}\isactrlsub {\isadigit{1}}} |
958 and the remaining \isa{{\isacharparenleft}f\ x{\isacharparenright}{\isacharcolon}\ {\isasymtau}\isactrlsub {\isadigit{2}}\ {\isasymrightarrow}\ {\isasymtau}} passed to another function |
958 and the remaining \isa{{\isaliteral{28}{\isacharparenleft}}f\ x{\isaliteral{29}{\isacharparenright}}{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{5C3C7461753E}{\isasymtau}}\isaliteral{5C3C5E7375623E}{}\isactrlsub {\isadigit{2}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C7461753E}{\isasymtau}}} passed to another function |
959 etc. How well this works in practice depends on the order of |
959 etc. How well this works in practice depends on the order of |
960 arguments. In the worst case, arguments are arranged erratically, |
960 arguments. In the worst case, arguments are arranged erratically, |
961 and using a function in a certain situation always requires some |
961 and using a function in a certain situation always requires some |
962 glue code. Thus we would get exponentially many oppurtunities to |
962 glue code. Thus we would get exponentially many oppurtunities to |
963 decorate the code with meaningless permutations of arguments. |
963 decorate the code with meaningless permutations of arguments. |
964 |
964 |
965 This can be avoided by \emph{canonical argument order}, which |
965 This can be avoided by \emph{canonical argument order}, which |
966 observes certain standard patterns and minimizes adhoc permutations |
966 observes certain standard patterns and minimizes adhoc permutations |
967 in their application. In Isabelle/ML, large portions of text can be |
967 in their application. In Isabelle/ML, large portions of text can be |
968 written without ever using \isa{swap{\isacharcolon}\ {\isasymalpha}\ {\isasymtimes}\ {\isasymbeta}\ {\isasymrightarrow}\ {\isasymbeta}\ {\isasymtimes}\ {\isasymalpha}}, or the |
968 written without ever using \isa{swap{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{5C3C616C7068613E}{\isasymalpha}}\ {\isaliteral{5C3C74696D65733E}{\isasymtimes}}\ {\isaliteral{5C3C626574613E}{\isasymbeta}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C626574613E}{\isasymbeta}}\ {\isaliteral{5C3C74696D65733E}{\isasymtimes}}\ {\isaliteral{5C3C616C7068613E}{\isasymalpha}}}, or the |
969 combinator \isa{C{\isacharcolon}\ {\isacharparenleft}{\isasymalpha}\ {\isasymrightarrow}\ {\isasymbeta}\ {\isasymrightarrow}\ {\isasymgamma}{\isacharparenright}\ {\isasymrightarrow}\ {\isacharparenleft}{\isasymbeta}\ {\isasymrightarrow}\ {\isasymalpha}\ {\isasymrightarrow}\ {\isasymgamma}{\isacharparenright}} that is not even |
969 combinator \isa{C{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{28}{\isacharparenleft}}{\isaliteral{5C3C616C7068613E}{\isasymalpha}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C626574613E}{\isasymbeta}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C67616D6D613E}{\isasymgamma}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{28}{\isacharparenleft}}{\isaliteral{5C3C626574613E}{\isasymbeta}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C616C7068613E}{\isasymalpha}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C67616D6D613E}{\isasymgamma}}{\isaliteral{29}{\isacharparenright}}} that is not even |
970 defined in our library. |
970 defined in our library. |
971 |
971 |
972 \medskip The basic idea is that arguments that vary less are moved |
972 \medskip The basic idea is that arguments that vary less are moved |
973 further to the left than those that vary more. Two particularly |
973 further to the left than those that vary more. Two particularly |
974 important categories of functions are \emph{selectors} and |
974 important categories of functions are \emph{selectors} and |
975 \emph{updates}. |
975 \emph{updates}. |
976 |
976 |
977 The subsequent scheme is based on a hypothetical set-like container |
977 The subsequent scheme is based on a hypothetical set-like container |
978 of type \isa{{\isasymbeta}} that manages elements of type \isa{{\isasymalpha}}. Both |
978 of type \isa{{\isaliteral{5C3C626574613E}{\isasymbeta}}} that manages elements of type \isa{{\isaliteral{5C3C616C7068613E}{\isasymalpha}}}. Both |
979 the names and types of the associated operations are canonical for |
979 the names and types of the associated operations are canonical for |
980 Isabelle/ML. |
980 Isabelle/ML. |
981 |
981 |
982 \medskip |
982 \medskip |
983 \begin{tabular}{ll} |
983 \begin{tabular}{ll} |
984 kind & canonical name and type \\\hline |
984 kind & canonical name and type \\\hline |
985 selector & \isa{member{\isacharcolon}\ {\isasymbeta}\ {\isasymrightarrow}\ {\isasymalpha}\ {\isasymrightarrow}\ bool} \\ |
985 selector & \isa{member{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{5C3C626574613E}{\isasymbeta}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C616C7068613E}{\isasymalpha}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ bool} \\ |
986 update & \isa{insert{\isacharcolon}\ {\isasymalpha}\ {\isasymrightarrow}\ {\isasymbeta}\ {\isasymrightarrow}\ {\isasymbeta}} \\ |
986 update & \isa{insert{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{5C3C616C7068613E}{\isasymalpha}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C626574613E}{\isasymbeta}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C626574613E}{\isasymbeta}}} \\ |
987 \end{tabular} |
987 \end{tabular} |
988 \medskip |
988 \medskip |
989 |
989 |
990 Given a container \isa{B{\isacharcolon}\ {\isasymbeta}}, the partially applied \isa{member\ B} is a predicate over elements \isa{{\isasymalpha}\ {\isasymrightarrow}\ bool}, and |
990 Given a container \isa{B{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{5C3C626574613E}{\isasymbeta}}}, the partially applied \isa{member\ B} is a predicate over elements \isa{{\isaliteral{5C3C616C7068613E}{\isasymalpha}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ bool}, and |
991 thus represents the intended denotation directly. It is customary |
991 thus represents the intended denotation directly. It is customary |
992 to pass the abstract predicate to further operations, not the |
992 to pass the abstract predicate to further operations, not the |
993 concrete container. The argument order makes it easy to use other |
993 concrete container. The argument order makes it easy to use other |
994 combinators: \isa{forall\ {\isacharparenleft}member\ B{\isacharparenright}\ list} will check a list of |
994 combinators: \isa{forall\ {\isaliteral{28}{\isacharparenleft}}member\ B{\isaliteral{29}{\isacharparenright}}\ list} will check a list of |
995 elements for membership in \isa{B} etc. Often the explicit |
995 elements for membership in \isa{B} etc. Often the explicit |
996 \isa{list} is pointless and can be contracted to \isa{forall\ {\isacharparenleft}member\ B{\isacharparenright}} to get directly a predicate again. |
996 \isa{list} is pointless and can be contracted to \isa{forall\ {\isaliteral{28}{\isacharparenleft}}member\ B{\isaliteral{29}{\isacharparenright}}} to get directly a predicate again. |
997 |
997 |
998 In contrast, an update operation varies the container, so it moves |
998 In contrast, an update operation varies the container, so it moves |
999 to the right: \isa{insert\ a} is a function \isa{{\isasymbeta}\ {\isasymrightarrow}\ {\isasymbeta}} to |
999 to the right: \isa{insert\ a} is a function \isa{{\isaliteral{5C3C626574613E}{\isasymbeta}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C626574613E}{\isasymbeta}}} to |
1000 insert a value \isa{a}. These can be composed naturally as |
1000 insert a value \isa{a}. These can be composed naturally as |
1001 \isa{insert\ c\ {\isasymcirc}\ insert\ b\ {\isasymcirc}\ insert\ a}. The slightly awkward |
1001 \isa{insert\ c\ {\isaliteral{5C3C636972633E}{\isasymcirc}}\ insert\ b\ {\isaliteral{5C3C636972633E}{\isasymcirc}}\ insert\ a}. The slightly awkward |
1002 inversion of the composition order is due to conventional |
1002 inversion of the composition order is due to conventional |
1003 mathematical notation, which can be easily amended as explained |
1003 mathematical notation, which can be easily amended as explained |
1004 below.% |
1004 below.% |
1005 \end{isamarkuptext}% |
1005 \end{isamarkuptext}% |
1006 \isamarkuptrue% |
1006 \isamarkuptrue% |
1009 } |
1009 } |
1010 \isamarkuptrue% |
1010 \isamarkuptrue% |
1011 % |
1011 % |
1012 \begin{isamarkuptext}% |
1012 \begin{isamarkuptext}% |
1013 Regular function application and infix notation works best for |
1013 Regular function application and infix notation works best for |
1014 relatively deeply structured expressions, e.g.\ \isa{h\ {\isacharparenleft}f\ x\ y\ {\isacharplus}\ g\ z{\isacharparenright}}. The important special case of \emph{linear transformation} |
1014 relatively deeply structured expressions, e.g.\ \isa{h\ {\isaliteral{28}{\isacharparenleft}}f\ x\ y\ {\isaliteral{2B}{\isacharplus}}\ g\ z{\isaliteral{29}{\isacharparenright}}}. The important special case of \emph{linear transformation} |
1015 applies a cascade of functions \isa{f\isactrlsub n\ {\isacharparenleft}{\isasymdots}\ {\isacharparenleft}f\isactrlsub {\isadigit{1}}\ x{\isacharparenright}{\isacharparenright}}. This |
1015 applies a cascade of functions \isa{f\isaliteral{5C3C5E7375623E}{}\isactrlsub n\ {\isaliteral{28}{\isacharparenleft}}{\isaliteral{5C3C646F74733E}{\isasymdots}}\ {\isaliteral{28}{\isacharparenleft}}f\isaliteral{5C3C5E7375623E}{}\isactrlsub {\isadigit{1}}\ x{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}}. This |
1016 becomes hard to read and maintain if the functions are themselves |
1016 becomes hard to read and maintain if the functions are themselves |
1017 given as complex expressions. The notation can be significantly |
1017 given as complex expressions. The notation can be significantly |
1018 improved by introducing \emph{forward} versions of application and |
1018 improved by introducing \emph{forward} versions of application and |
1019 composition as follows: |
1019 composition as follows: |
1020 |
1020 |
1021 \medskip |
1021 \medskip |
1022 \begin{tabular}{lll} |
1022 \begin{tabular}{lll} |
1023 \isa{x\ {\isacharbar}{\isachargreater}\ f} & \isa{{\isasymequiv}} & \isa{f\ x} \\ |
1023 \isa{x\ {\isaliteral{7C}{\isacharbar}}{\isaliteral{3E}{\isachargreater}}\ f} & \isa{{\isaliteral{5C3C65717569763E}{\isasymequiv}}} & \isa{f\ x} \\ |
1024 \isa{f\ {\isacharhash}{\isachargreater}\ g} & \isa{{\isasymequiv}} & \isa{x\ {\isacharbar}{\isachargreater}\ f\ {\isacharbar}{\isachargreater}\ g} \\ |
1024 \isa{f\ {\isaliteral{23}{\isacharhash}}{\isaliteral{3E}{\isachargreater}}\ g} & \isa{{\isaliteral{5C3C65717569763E}{\isasymequiv}}} & \isa{x\ {\isaliteral{7C}{\isacharbar}}{\isaliteral{3E}{\isachargreater}}\ f\ {\isaliteral{7C}{\isacharbar}}{\isaliteral{3E}{\isachargreater}}\ g} \\ |
1025 \end{tabular} |
1025 \end{tabular} |
1026 \medskip |
1026 \medskip |
1027 |
1027 |
1028 This enables to write conveniently \isa{x\ {\isacharbar}{\isachargreater}\ f\isactrlsub {\isadigit{1}}\ {\isacharbar}{\isachargreater}\ {\isasymdots}\ {\isacharbar}{\isachargreater}\ f\isactrlsub n} or |
1028 This enables to write conveniently \isa{x\ {\isaliteral{7C}{\isacharbar}}{\isaliteral{3E}{\isachargreater}}\ f\isaliteral{5C3C5E7375623E}{}\isactrlsub {\isadigit{1}}\ {\isaliteral{7C}{\isacharbar}}{\isaliteral{3E}{\isachargreater}}\ {\isaliteral{5C3C646F74733E}{\isasymdots}}\ {\isaliteral{7C}{\isacharbar}}{\isaliteral{3E}{\isachargreater}}\ f\isaliteral{5C3C5E7375623E}{}\isactrlsub n} or |
1029 \isa{f\isactrlsub {\isadigit{1}}\ {\isacharhash}{\isachargreater}\ {\isasymdots}\ {\isacharhash}{\isachargreater}\ f\isactrlsub n} for its functional abstraction over \isa{x}. |
1029 \isa{f\isaliteral{5C3C5E7375623E}{}\isactrlsub {\isadigit{1}}\ {\isaliteral{23}{\isacharhash}}{\isaliteral{3E}{\isachargreater}}\ {\isaliteral{5C3C646F74733E}{\isasymdots}}\ {\isaliteral{23}{\isacharhash}}{\isaliteral{3E}{\isachargreater}}\ f\isaliteral{5C3C5E7375623E}{}\isactrlsub n} for its functional abstraction over \isa{x}. |
1030 |
1030 |
1031 \medskip There is an additional set of combinators to accommodate |
1031 \medskip There is an additional set of combinators to accommodate |
1032 multiple results (via pairs) that are passed on as multiple |
1032 multiple results (via pairs) that are passed on as multiple |
1033 arguments (via currying). |
1033 arguments (via currying). |
1034 |
1034 |
1035 \medskip |
1035 \medskip |
1036 \begin{tabular}{lll} |
1036 \begin{tabular}{lll} |
1037 \isa{{\isacharparenleft}x{\isacharcomma}\ y{\isacharparenright}\ {\isacharbar}{\isacharminus}{\isachargreater}\ f} & \isa{{\isasymequiv}} & \isa{f\ x\ y} \\ |
1037 \isa{{\isaliteral{28}{\isacharparenleft}}x{\isaliteral{2C}{\isacharcomma}}\ y{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{7C}{\isacharbar}}{\isaliteral{2D}{\isacharminus}}{\isaliteral{3E}{\isachargreater}}\ f} & \isa{{\isaliteral{5C3C65717569763E}{\isasymequiv}}} & \isa{f\ x\ y} \\ |
1038 \isa{f\ {\isacharhash}{\isacharminus}{\isachargreater}\ g} & \isa{{\isasymequiv}} & \isa{x\ {\isacharbar}{\isachargreater}\ f\ {\isacharbar}{\isacharminus}{\isachargreater}\ g} \\ |
1038 \isa{f\ {\isaliteral{23}{\isacharhash}}{\isaliteral{2D}{\isacharminus}}{\isaliteral{3E}{\isachargreater}}\ g} & \isa{{\isaliteral{5C3C65717569763E}{\isasymequiv}}} & \isa{x\ {\isaliteral{7C}{\isacharbar}}{\isaliteral{3E}{\isachargreater}}\ f\ {\isaliteral{7C}{\isacharbar}}{\isaliteral{2D}{\isacharminus}}{\isaliteral{3E}{\isachargreater}}\ g} \\ |
1039 \end{tabular} |
1039 \end{tabular} |
1040 \medskip% |
1040 \medskip% |
1041 \end{isamarkuptext}% |
1041 \end{isamarkuptext}% |
1042 \isamarkuptrue% |
1042 \isamarkuptrue% |
1043 % |
1043 % |
1069 \isamarkupsubsection{Canonical iteration% |
1069 \isamarkupsubsection{Canonical iteration% |
1070 } |
1070 } |
1071 \isamarkuptrue% |
1071 \isamarkuptrue% |
1072 % |
1072 % |
1073 \begin{isamarkuptext}% |
1073 \begin{isamarkuptext}% |
1074 As explained above, a function \isa{f{\isacharcolon}\ {\isasymalpha}\ {\isasymrightarrow}\ {\isasymbeta}\ {\isasymrightarrow}\ {\isasymbeta}} can be |
1074 As explained above, a function \isa{f{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{5C3C616C7068613E}{\isasymalpha}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C626574613E}{\isasymbeta}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C626574613E}{\isasymbeta}}} can be |
1075 understood as update on a configuration of type \isa{{\isasymbeta}}, |
1075 understood as update on a configuration of type \isa{{\isaliteral{5C3C626574613E}{\isasymbeta}}}, |
1076 parametrized by arguments of type \isa{{\isasymalpha}}. Given \isa{a{\isacharcolon}\ {\isasymalpha}} |
1076 parametrized by arguments of type \isa{{\isaliteral{5C3C616C7068613E}{\isasymalpha}}}. Given \isa{a{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{5C3C616C7068613E}{\isasymalpha}}} |
1077 the partial application \isa{{\isacharparenleft}f\ a{\isacharparenright}{\isacharcolon}\ {\isasymbeta}\ {\isasymrightarrow}\ {\isasymbeta}} operates |
1077 the partial application \isa{{\isaliteral{28}{\isacharparenleft}}f\ a{\isaliteral{29}{\isacharparenright}}{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{5C3C626574613E}{\isasymbeta}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C626574613E}{\isasymbeta}}} operates |
1078 homogeneously on \isa{{\isasymbeta}}. This can be iterated naturally over a |
1078 homogeneously on \isa{{\isaliteral{5C3C626574613E}{\isasymbeta}}}. This can be iterated naturally over a |
1079 list of parameters \isa{{\isacharbrackleft}a\isactrlsub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ a\isactrlsub n{\isacharbrackright}} as \isa{f\ a\isactrlsub {\isadigit{1}}\ {\isacharhash}{\isachargreater}\ {\isasymdots}\ {\isacharhash}{\isachargreater}\ f\ a\isactrlbsub n\isactrlesub \isactrlbsub \isactrlesub }. The latter expression is again a function \isa{{\isasymbeta}\ {\isasymrightarrow}\ {\isasymbeta}}. |
1079 list of parameters \isa{{\isaliteral{5B}{\isacharbrackleft}}a\isaliteral{5C3C5E7375623E}{}\isactrlsub {\isadigit{1}}{\isaliteral{2C}{\isacharcomma}}\ {\isaliteral{5C3C646F74733E}{\isasymdots}}{\isaliteral{2C}{\isacharcomma}}\ a\isaliteral{5C3C5E7375623E}{}\isactrlsub n{\isaliteral{5D}{\isacharbrackright}}} as \isa{f\ a\isaliteral{5C3C5E7375623E}{}\isactrlsub {\isadigit{1}}\ {\isaliteral{23}{\isacharhash}}{\isaliteral{3E}{\isachargreater}}\ {\isaliteral{5C3C646F74733E}{\isasymdots}}\ {\isaliteral{23}{\isacharhash}}{\isaliteral{3E}{\isachargreater}}\ f\ a\isaliteral{5C3C5E627375623E}{}\isactrlbsub n\isaliteral{5C3C5E657375623E}{}\isactrlesub \isaliteral{5C3C5E627375623E}{}\isactrlbsub \isaliteral{5C3C5E657375623E}{}\isactrlesub }. The latter expression is again a function \isa{{\isaliteral{5C3C626574613E}{\isasymbeta}}\ {\isaliteral{5C3C72696768746172726F773E}{\isasymrightarrow}}\ {\isaliteral{5C3C626574613E}{\isasymbeta}}}. |
1080 It can be applied to an initial configuration \isa{b{\isacharcolon}\ {\isasymbeta}} to |
1080 It can be applied to an initial configuration \isa{b{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{5C3C626574613E}{\isasymbeta}}} to |
1081 start the iteration over the given list of arguments: each \isa{a} in \isa{a\isactrlsub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ a\isactrlsub n} is applied consecutively by updating a |
1081 start the iteration over the given list of arguments: each \isa{a} in \isa{a\isaliteral{5C3C5E7375623E}{}\isactrlsub {\isadigit{1}}{\isaliteral{2C}{\isacharcomma}}\ {\isaliteral{5C3C646F74733E}{\isasymdots}}{\isaliteral{2C}{\isacharcomma}}\ a\isaliteral{5C3C5E7375623E}{}\isactrlsub n} is applied consecutively by updating a |
1082 cumulative configuration. |
1082 cumulative configuration. |
1083 |
1083 |
1084 The \isa{fold} combinator in Isabelle/ML lifts a function \isa{f} as above to its iterated version over a list of arguments. |
1084 The \isa{fold} combinator in Isabelle/ML lifts a function \isa{f} as above to its iterated version over a list of arguments. |
1085 Lifting can be repeated, e.g.\ \isa{{\isacharparenleft}fold\ {\isasymcirc}\ fold{\isacharparenright}\ f} iterates |
1085 Lifting can be repeated, e.g.\ \isa{{\isaliteral{28}{\isacharparenleft}}fold\ {\isaliteral{5C3C636972633E}{\isasymcirc}}\ fold{\isaliteral{29}{\isacharparenright}}\ f} iterates |
1086 over a list of lists as expected. |
1086 over a list of lists as expected. |
1087 |
1087 |
1088 The variant \isa{fold{\isacharunderscore}rev} works inside-out over the list of |
1088 The variant \isa{fold{\isaliteral{5F}{\isacharunderscore}}rev} works inside-out over the list of |
1089 arguments, such that \isa{fold{\isacharunderscore}rev\ f\ {\isasymequiv}\ fold\ f\ {\isasymcirc}\ rev} holds. |
1089 arguments, such that \isa{fold{\isaliteral{5F}{\isacharunderscore}}rev\ f\ {\isaliteral{5C3C65717569763E}{\isasymequiv}}\ fold\ f\ {\isaliteral{5C3C636972633E}{\isasymcirc}}\ rev} holds. |
1090 |
1090 |
1091 The \isa{fold{\isacharunderscore}map} combinator essentially performs \isa{fold} and \isa{map} simultaneously: each application of \isa{f} produces an updated configuration together with a side-result; |
1091 The \isa{fold{\isaliteral{5F}{\isacharunderscore}}map} combinator essentially performs \isa{fold} and \isa{map} simultaneously: each application of \isa{f} produces an updated configuration together with a side-result; |
1092 the iteration collects all such side-results as a separate list.% |
1092 the iteration collects all such side-results as a separate list.% |
1093 \end{isamarkuptext}% |
1093 \end{isamarkuptext}% |
1094 \isamarkuptrue% |
1094 \isamarkuptrue% |
1095 % |
1095 % |
1096 \isadelimmlref |
1096 \isadelimmlref |
1200 % |
1200 % |
1201 \endisadelimML |
1201 \endisadelimML |
1202 % |
1202 % |
1203 \isatagML |
1203 \isatagML |
1204 \isacommand{ML}\isamarkupfalse% |
1204 \isacommand{ML}\isamarkupfalse% |
1205 \ {\isacharverbatimopen}\isanewline |
1205 \ {\isaliteral{7B2A}{\isacharverbatimopen}}\isanewline |
1206 \ \ datatype\ tree\ {\isacharequal}\ Text\ of\ string\ {\isacharbar}\ Elem\ of\ string\ {\isacharasterisk}\ tree\ list{\isacharsemicolon}\isanewline |
1206 \ \ datatype\ tree\ {\isaliteral{3D}{\isacharequal}}\ Text\ of\ string\ {\isaliteral{7C}{\isacharbar}}\ Elem\ of\ string\ {\isaliteral{2A}{\isacharasterisk}}\ tree\ list{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
1207 \isanewline |
1207 \isanewline |
1208 \ \ fun\ slow{\isacharunderscore}content\ {\isacharparenleft}Text\ txt{\isacharparenright}\ {\isacharequal}\ txt\isanewline |
1208 \ \ fun\ slow{\isaliteral{5F}{\isacharunderscore}}content\ {\isaliteral{28}{\isacharparenleft}}Text\ txt{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{3D}{\isacharequal}}\ txt\isanewline |
1209 \ \ \ \ {\isacharbar}\ slow{\isacharunderscore}content\ {\isacharparenleft}Elem\ {\isacharparenleft}name{\isacharcomma}\ ts{\isacharparenright}{\isacharparenright}\ {\isacharequal}\isanewline |
1209 \ \ \ \ {\isaliteral{7C}{\isacharbar}}\ slow{\isaliteral{5F}{\isacharunderscore}}content\ {\isaliteral{28}{\isacharparenleft}}Elem\ {\isaliteral{28}{\isacharparenleft}}name{\isaliteral{2C}{\isacharcomma}}\ ts{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{3D}{\isacharequal}}\isanewline |
1210 \ \ \ \ \ \ \ \ {\isachardoublequote}{\isacharless}{\isachardoublequote}\ {\isacharcircum}\ name\ {\isacharcircum}\ {\isachardoublequote}{\isachargreater}{\isachardoublequote}\ {\isacharcircum}\isanewline |
1210 \ \ \ \ \ \ \ \ {\isaliteral{22}{\isachardoublequote}}{\isaliteral{3C}{\isacharless}}{\isaliteral{22}{\isachardoublequote}}\ {\isaliteral{5E}{\isacharcircum}}\ name\ {\isaliteral{5E}{\isacharcircum}}\ {\isaliteral{22}{\isachardoublequote}}{\isaliteral{3E}{\isachargreater}}{\isaliteral{22}{\isachardoublequote}}\ {\isaliteral{5E}{\isacharcircum}}\isanewline |
1211 \ \ \ \ \ \ \ \ implode\ {\isacharparenleft}map\ slow{\isacharunderscore}content\ ts{\isacharparenright}\ {\isacharcircum}\isanewline |
1211 \ \ \ \ \ \ \ \ implode\ {\isaliteral{28}{\isacharparenleft}}map\ slow{\isaliteral{5F}{\isacharunderscore}}content\ ts{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5E}{\isacharcircum}}\isanewline |
1212 \ \ \ \ \ \ \ \ {\isachardoublequote}{\isacharless}{\isacharslash}{\isachardoublequote}\ {\isacharcircum}\ name\ {\isacharcircum}\ {\isachardoublequote}{\isachargreater}{\isachardoublequote}\isanewline |
1212 \ \ \ \ \ \ \ \ {\isaliteral{22}{\isachardoublequote}}{\isaliteral{3C}{\isacharless}}{\isaliteral{2F}{\isacharslash}}{\isaliteral{22}{\isachardoublequote}}\ {\isaliteral{5E}{\isacharcircum}}\ name\ {\isaliteral{5E}{\isacharcircum}}\ {\isaliteral{22}{\isachardoublequote}}{\isaliteral{3E}{\isachargreater}}{\isaliteral{22}{\isachardoublequote}}\isanewline |
1213 \isanewline |
1213 \isanewline |
1214 \ \ fun\ add{\isacharunderscore}content\ {\isacharparenleft}Text\ txt{\isacharparenright}\ {\isacharequal}\ Buffer{\isachardot}add\ txt\isanewline |
1214 \ \ fun\ add{\isaliteral{5F}{\isacharunderscore}}content\ {\isaliteral{28}{\isacharparenleft}}Text\ txt{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{3D}{\isacharequal}}\ Buffer{\isaliteral{2E}{\isachardot}}add\ txt\isanewline |
1215 \ \ \ \ {\isacharbar}\ add{\isacharunderscore}content\ {\isacharparenleft}Elem\ {\isacharparenleft}name{\isacharcomma}\ ts{\isacharparenright}{\isacharparenright}\ {\isacharequal}\isanewline |
1215 \ \ \ \ {\isaliteral{7C}{\isacharbar}}\ add{\isaliteral{5F}{\isacharunderscore}}content\ {\isaliteral{28}{\isacharparenleft}}Elem\ {\isaliteral{28}{\isacharparenleft}}name{\isaliteral{2C}{\isacharcomma}}\ ts{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{3D}{\isacharequal}}\isanewline |
1216 \ \ \ \ \ \ \ \ Buffer{\isachardot}add\ {\isacharparenleft}{\isachardoublequote}{\isacharless}{\isachardoublequote}\ {\isacharcircum}\ name\ {\isacharcircum}\ {\isachardoublequote}{\isachargreater}{\isachardoublequote}{\isacharparenright}\ {\isacharhash}{\isachargreater}\isanewline |
1216 \ \ \ \ \ \ \ \ Buffer{\isaliteral{2E}{\isachardot}}add\ {\isaliteral{28}{\isacharparenleft}}{\isaliteral{22}{\isachardoublequote}}{\isaliteral{3C}{\isacharless}}{\isaliteral{22}{\isachardoublequote}}\ {\isaliteral{5E}{\isacharcircum}}\ name\ {\isaliteral{5E}{\isacharcircum}}\ {\isaliteral{22}{\isachardoublequote}}{\isaliteral{3E}{\isachargreater}}{\isaliteral{22}{\isachardoublequote}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{23}{\isacharhash}}{\isaliteral{3E}{\isachargreater}}\isanewline |
1217 \ \ \ \ \ \ \ \ fold\ add{\isacharunderscore}content\ ts\ {\isacharhash}{\isachargreater}\isanewline |
1217 \ \ \ \ \ \ \ \ fold\ add{\isaliteral{5F}{\isacharunderscore}}content\ ts\ {\isaliteral{23}{\isacharhash}}{\isaliteral{3E}{\isachargreater}}\isanewline |
1218 \ \ \ \ \ \ \ \ Buffer{\isachardot}add\ {\isacharparenleft}{\isachardoublequote}{\isacharless}{\isacharslash}{\isachardoublequote}\ {\isacharcircum}\ name\ {\isacharcircum}\ {\isachardoublequote}{\isachargreater}{\isachardoublequote}{\isacharparenright}{\isacharsemicolon}\isanewline |
1218 \ \ \ \ \ \ \ \ Buffer{\isaliteral{2E}{\isachardot}}add\ {\isaliteral{28}{\isacharparenleft}}{\isaliteral{22}{\isachardoublequote}}{\isaliteral{3C}{\isacharless}}{\isaliteral{2F}{\isacharslash}}{\isaliteral{22}{\isachardoublequote}}\ {\isaliteral{5E}{\isacharcircum}}\ name\ {\isaliteral{5E}{\isacharcircum}}\ {\isaliteral{22}{\isachardoublequote}}{\isaliteral{3E}{\isachargreater}}{\isaliteral{22}{\isachardoublequote}}{\isaliteral{29}{\isacharparenright}}{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
1219 \isanewline |
1219 \isanewline |
1220 \ \ fun\ fast{\isacharunderscore}content\ tree\ {\isacharequal}\isanewline |
1220 \ \ fun\ fast{\isaliteral{5F}{\isacharunderscore}}content\ tree\ {\isaliteral{3D}{\isacharequal}}\isanewline |
1221 \ \ \ \ Buffer{\isachardot}empty\ {\isacharbar}{\isachargreater}\ add{\isacharunderscore}content\ tree\ {\isacharbar}{\isachargreater}\ Buffer{\isachardot}content{\isacharsemicolon}\isanewline |
1221 \ \ \ \ Buffer{\isaliteral{2E}{\isachardot}}empty\ {\isaliteral{7C}{\isacharbar}}{\isaliteral{3E}{\isachargreater}}\ add{\isaliteral{5F}{\isacharunderscore}}content\ tree\ {\isaliteral{7C}{\isacharbar}}{\isaliteral{3E}{\isachargreater}}\ Buffer{\isaliteral{2E}{\isachardot}}content{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
1222 {\isacharverbatimclose}% |
1222 {\isaliteral{2A7D}{\isacharverbatimclose}}% |
1223 \endisatagML |
1223 \endisatagML |
1224 {\isafoldML}% |
1224 {\isafoldML}% |
1225 % |
1225 % |
1226 \isadelimML |
1226 \isadelimML |
1227 % |
1227 % |
1761 \indexdef{}{ML}{update}\verb|update: ('a * 'a -> bool) -> 'a -> 'a list -> 'a list| \\ |
1761 \indexdef{}{ML}{update}\verb|update: ('a * 'a -> bool) -> 'a -> 'a list -> 'a list| \\ |
1762 \end{mldecls} |
1762 \end{mldecls} |
1763 |
1763 |
1764 \begin{description} |
1764 \begin{description} |
1765 |
1765 |
1766 \item \verb|cons|~\isa{x\ xs} evaluates to \isa{x\ {\isacharcolon}{\isacharcolon}\ xs}. |
1766 \item \verb|cons|~\isa{x\ xs} evaluates to \isa{x\ {\isaliteral{3A}{\isacharcolon}}{\isaliteral{3A}{\isacharcolon}}\ xs}. |
1767 |
1767 |
1768 Tupled infix operators are a historical accident in Standard ML. |
1768 Tupled infix operators are a historical accident in Standard ML. |
1769 The curried \verb|cons| amends this, but it should be only used when |
1769 The curried \verb|cons| amends this, but it should be only used when |
1770 partial application is required. |
1770 partial application is required. |
1771 |
1771 |
1772 \item \verb|member|, \verb|insert|, \verb|remove|, \verb|update| treat |
1772 \item \verb|member|, \verb|insert|, \verb|remove|, \verb|update| treat |
1773 lists as a set-like container that maintains the order of elements. |
1773 lists as a set-like container that maintains the order of elements. |
1774 See \hyperlink{file.~~/src/Pure/library.ML}{\mbox{\isa{\isatt{{\isachartilde}{\isachartilde}{\isacharslash}src{\isacharslash}Pure{\isacharslash}library{\isachardot}ML}}}} for the full specifications |
1774 See \hyperlink{file.~~/src/Pure/library.ML}{\mbox{\isa{\isatt{{\isaliteral{7E}{\isachartilde}}{\isaliteral{7E}{\isachartilde}}{\isaliteral{2F}{\isacharslash}}src{\isaliteral{2F}{\isacharslash}}Pure{\isaliteral{2F}{\isacharslash}}library{\isaliteral{2E}{\isachardot}}ML}}}} for the full specifications |
1775 (written in ML). There are some further derived operations like |
1775 (written in ML). There are some further derived operations like |
1776 \verb|union| or \verb|inter|. |
1776 \verb|union| or \verb|inter|. |
1777 |
1777 |
1778 Note that \verb|insert| is conservative about elements that are |
1778 Note that \verb|insert| is conservative about elements that are |
1779 already a \verb|member| of the list, while \verb|update| ensures that |
1779 already a \verb|member| of the list, while \verb|update| ensures that |
1909 types. |
1909 types. |
1910 |
1910 |
1911 Note that a function called \isa{lookup} is obliged to express its |
1911 Note that a function called \isa{lookup} is obliged to express its |
1912 partiality via an explicit option element. There is no choice to |
1912 partiality via an explicit option element. There is no choice to |
1913 raise an exception, without changing the name to something like |
1913 raise an exception, without changing the name to something like |
1914 \isa{the{\isacharunderscore}element} or \isa{get}. |
1914 \isa{the{\isaliteral{5F}{\isacharunderscore}}element} or \isa{get}. |
1915 |
1915 |
1916 The \isa{defined} operation is essentially a contraction of \verb|is_some| and \isa{lookup}, but this is sufficiently frequent to |
1916 The \isa{defined} operation is essentially a contraction of \verb|is_some| and \isa{lookup}, but this is sufficiently frequent to |
1917 justify its independent existence. This also gives the |
1917 justify its independent existence. This also gives the |
1918 implementation some opportunity for peep-hole optimization. |
1918 implementation some opportunity for peep-hole optimization. |
1919 |
1919 |
1920 \end{description} |
1920 \end{description} |
1921 |
1921 |
1922 Association lists are adequate as simple and light-weight |
1922 Association lists are adequate as simple and light-weight |
1923 implementation of finite mappings in many practical situations. A |
1923 implementation of finite mappings in many practical situations. A |
1924 more heavy-duty table structure is defined in \hyperlink{file.~~/src/Pure/General/table.ML}{\mbox{\isa{\isatt{{\isachartilde}{\isachartilde}{\isacharslash}src{\isacharslash}Pure{\isacharslash}General{\isacharslash}table{\isachardot}ML}}}}; that version scales easily to |
1924 more heavy-duty table structure is defined in \hyperlink{file.~~/src/Pure/General/table.ML}{\mbox{\isa{\isatt{{\isaliteral{7E}{\isachartilde}}{\isaliteral{7E}{\isachartilde}}{\isaliteral{2F}{\isacharslash}}src{\isaliteral{2F}{\isacharslash}}Pure{\isaliteral{2F}{\isacharslash}}General{\isaliteral{2F}{\isacharslash}}table{\isaliteral{2E}{\isachardot}}ML}}}}; that version scales easily to |
1925 thousands or millions of elements.% |
1925 thousands or millions of elements.% |
1926 \end{isamarkuptext}% |
1926 \end{isamarkuptext}% |
1927 \isamarkuptrue% |
1927 \isamarkuptrue% |
1928 % |
1928 % |
1929 \isamarkupsubsection{Unsynchronized references% |
1929 \isamarkupsubsection{Unsynchronized references% |
2276 \item \verb|Synchronized.guarded_access|~\isa{var\ f} lets the |
2276 \item \verb|Synchronized.guarded_access|~\isa{var\ f} lets the |
2277 function \isa{f} operate within a critical section on the state |
2277 function \isa{f} operate within a critical section on the state |
2278 \isa{x} as follows: if \isa{f\ x} produces \verb|NONE|, it |
2278 \isa{x} as follows: if \isa{f\ x} produces \verb|NONE|, it |
2279 continues to wait on the internal condition variable, expecting that |
2279 continues to wait on the internal condition variable, expecting that |
2280 some other thread will eventually change the content in a suitable |
2280 some other thread will eventually change the content in a suitable |
2281 manner; if \isa{f\ x} produces \verb|SOME|~\isa{{\isacharparenleft}y{\isacharcomma}\ x{\isacharprime}{\isacharparenright}} it is |
2281 manner; if \isa{f\ x} produces \verb|SOME|~\isa{{\isaliteral{28}{\isacharparenleft}}y{\isaliteral{2C}{\isacharcomma}}\ x{\isaliteral{27}{\isacharprime}}{\isaliteral{29}{\isacharparenright}}} it is |
2282 satisfied and assigns the new state value \isa{x{\isacharprime}}, broadcasts a |
2282 satisfied and assigns the new state value \isa{x{\isaliteral{27}{\isacharprime}}}, broadcasts a |
2283 signal to all waiting threads on the associated condition variable, |
2283 signal to all waiting threads on the associated condition variable, |
2284 and returns the result \isa{y}. |
2284 and returns the result \isa{y}. |
2285 |
2285 |
2286 \end{description} |
2286 \end{description} |
2287 |
2287 |
2288 There are some further variants of the \verb|Synchronized.guarded_access| combinator, see \hyperlink{file.~~/src/Pure/Concurrent/synchronized.ML}{\mbox{\isa{\isatt{{\isachartilde}{\isachartilde}{\isacharslash}src{\isacharslash}Pure{\isacharslash}Concurrent{\isacharslash}synchronized{\isachardot}ML}}}} for details.% |
2288 There are some further variants of the \verb|Synchronized.guarded_access| combinator, see \hyperlink{file.~~/src/Pure/Concurrent/synchronized.ML}{\mbox{\isa{\isatt{{\isaliteral{7E}{\isachartilde}}{\isaliteral{7E}{\isachartilde}}{\isaliteral{2F}{\isacharslash}}src{\isaliteral{2F}{\isacharslash}}Pure{\isaliteral{2F}{\isacharslash}}Concurrent{\isaliteral{2F}{\isacharslash}}synchronized{\isaliteral{2E}{\isachardot}}ML}}}} for details.% |
2289 \end{isamarkuptext}% |
2289 \end{isamarkuptext}% |
2290 \isamarkuptrue% |
2290 \isamarkuptrue% |
2291 % |
2291 % |
2292 \endisatagmlref |
2292 \endisatagmlref |
2293 {\isafoldmlref}% |
2293 {\isafoldmlref}% |
2320 % |
2320 % |
2321 \endisadelimML |
2321 \endisadelimML |
2322 % |
2322 % |
2323 \isatagML |
2323 \isatagML |
2324 \isacommand{ML}\isamarkupfalse% |
2324 \isacommand{ML}\isamarkupfalse% |
2325 \ {\isacharverbatimopen}\isanewline |
2325 \ {\isaliteral{7B2A}{\isacharverbatimopen}}\isanewline |
2326 \ \ local\isanewline |
2326 \ \ local\isanewline |
2327 \ \ \ \ val\ counter\ {\isacharequal}\ Synchronized{\isachardot}var\ {\isachardoublequote}counter{\isachardoublequote}\ {\isadigit{0}}{\isacharsemicolon}\isanewline |
2327 \ \ \ \ val\ counter\ {\isaliteral{3D}{\isacharequal}}\ Synchronized{\isaliteral{2E}{\isachardot}}var\ {\isaliteral{22}{\isachardoublequote}}counter{\isaliteral{22}{\isachardoublequote}}\ {\isadigit{0}}{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
2328 \ \ in\isanewline |
2328 \ \ in\isanewline |
2329 \ \ \ \ fun\ next\ {\isacharparenleft}{\isacharparenright}\ {\isacharequal}\isanewline |
2329 \ \ \ \ fun\ next\ {\isaliteral{28}{\isacharparenleft}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{3D}{\isacharequal}}\isanewline |
2330 \ \ \ \ \ \ Synchronized{\isachardot}guarded{\isacharunderscore}access\ counter\isanewline |
2330 \ \ \ \ \ \ Synchronized{\isaliteral{2E}{\isachardot}}guarded{\isaliteral{5F}{\isacharunderscore}}access\ counter\isanewline |
2331 \ \ \ \ \ \ \ \ {\isacharparenleft}fn\ i\ {\isacharequal}{\isachargreater}\isanewline |
2331 \ \ \ \ \ \ \ \ {\isaliteral{28}{\isacharparenleft}}fn\ i\ {\isaliteral{3D}{\isacharequal}}{\isaliteral{3E}{\isachargreater}}\isanewline |
2332 \ \ \ \ \ \ \ \ \ \ let\ val\ j\ {\isacharequal}\ i\ {\isacharplus}\ {\isadigit{1}}\isanewline |
2332 \ \ \ \ \ \ \ \ \ \ let\ val\ j\ {\isaliteral{3D}{\isacharequal}}\ i\ {\isaliteral{2B}{\isacharplus}}\ {\isadigit{1}}\isanewline |
2333 \ \ \ \ \ \ \ \ \ \ in\ SOME\ {\isacharparenleft}j{\isacharcomma}\ j{\isacharparenright}\ end{\isacharparenright}{\isacharsemicolon}\isanewline |
2333 \ \ \ \ \ \ \ \ \ \ in\ SOME\ {\isaliteral{28}{\isacharparenleft}}j{\isaliteral{2C}{\isacharcomma}}\ j{\isaliteral{29}{\isacharparenright}}\ end{\isaliteral{29}{\isacharparenright}}{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
2334 \ \ end{\isacharsemicolon}\isanewline |
2334 \ \ end{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
2335 {\isacharverbatimclose}\isanewline |
2335 {\isaliteral{2A7D}{\isacharverbatimclose}}\isanewline |
2336 \isanewline |
2336 \isanewline |
2337 \isacommand{ML}\isamarkupfalse% |
2337 \isacommand{ML}\isamarkupfalse% |
2338 \ {\isacharverbatimopen}\isanewline |
2338 \ {\isaliteral{7B2A}{\isacharverbatimopen}}\isanewline |
2339 \ \ val\ a\ {\isacharequal}\ next\ {\isacharparenleft}{\isacharparenright}{\isacharsemicolon}\isanewline |
2339 \ \ val\ a\ {\isaliteral{3D}{\isacharequal}}\ next\ {\isaliteral{28}{\isacharparenleft}}{\isaliteral{29}{\isacharparenright}}{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
2340 \ \ val\ b\ {\isacharequal}\ next\ {\isacharparenleft}{\isacharparenright}{\isacharsemicolon}\isanewline |
2340 \ \ val\ b\ {\isaliteral{3D}{\isacharequal}}\ next\ {\isaliteral{28}{\isacharparenleft}}{\isaliteral{29}{\isacharparenright}}{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
2341 \ \ % |
2341 \ \ % |
2342 \isaantiq |
2342 \isaantiq |
2343 assert% |
2343 assert{}% |
2344 \endisaantiq |
2344 \endisaantiq |
2345 \ {\isacharparenleft}a\ {\isacharless}{\isachargreater}\ b{\isacharparenright}{\isacharsemicolon}\isanewline |
2345 \ {\isaliteral{28}{\isacharparenleft}}a\ {\isaliteral{3C}{\isacharless}}{\isaliteral{3E}{\isachargreater}}\ b{\isaliteral{29}{\isacharparenright}}{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
2346 {\isacharverbatimclose}% |
2346 {\isaliteral{2A7D}{\isacharverbatimclose}}% |
2347 \endisatagML |
2347 \endisatagML |
2348 {\isafoldML}% |
2348 {\isafoldML}% |
2349 % |
2349 % |
2350 \isadelimML |
2350 \isadelimML |
2351 % |
2351 % |
2352 \endisadelimML |
2352 \endisadelimML |
2353 % |
2353 % |
2354 \begin{isamarkuptext}% |
2354 \begin{isamarkuptext}% |
2355 \medskip See \hyperlink{file.~~/src/Pure/Concurrent/mailbox.ML}{\mbox{\isa{\isatt{{\isachartilde}{\isachartilde}{\isacharslash}src{\isacharslash}Pure{\isacharslash}Concurrent{\isacharslash}mailbox{\isachardot}ML}}}} how |
2355 \medskip See \hyperlink{file.~~/src/Pure/Concurrent/mailbox.ML}{\mbox{\isa{\isatt{{\isaliteral{7E}{\isachartilde}}{\isaliteral{7E}{\isachartilde}}{\isaliteral{2F}{\isacharslash}}src{\isaliteral{2F}{\isacharslash}}Pure{\isaliteral{2F}{\isacharslash}}Concurrent{\isaliteral{2F}{\isacharslash}}mailbox{\isaliteral{2E}{\isachardot}}ML}}}} how |
2356 to implement a mailbox as synchronized variable over a purely |
2356 to implement a mailbox as synchronized variable over a purely |
2357 functional queue.% |
2357 functional queue.% |
2358 \end{isamarkuptext}% |
2358 \end{isamarkuptext}% |
2359 \isamarkuptrue% |
2359 \isamarkuptrue% |
2360 % |
2360 % |