src/Doc/Implementation/ML.thy
changeset 61503 28e788ca2c5d
parent 61493 0debd22f0c0e
child 61504 a7ae3ef886a9
equal deleted inserted replaced
61502:760e21900b01 61503:28e788ca2c5d
    65 text \<open>Isabelle source files have a certain standardized header
    65 text \<open>Isabelle source files have a certain standardized header
    66   format (with precise spacing) that follows ancient traditions
    66   format (with precise spacing) that follows ancient traditions
    67   reaching back to the earliest versions of the system by Larry
    67   reaching back to the earliest versions of the system by Larry
    68   Paulson.  See @{file "~~/src/Pure/thm.ML"}, for example.
    68   Paulson.  See @{file "~~/src/Pure/thm.ML"}, for example.
    69 
    69 
    70   The header includes at least @{verbatim Title} and @{verbatim
    70   The header includes at least \<^verbatim>\<open>Title\<close> and \<^verbatim>\<open>Author\<close> entries,
    71   Author} entries, followed by a prose description of the purpose of
    71   followed by a prose description of the purpose of
    72   the module.  The latter can range from a single line to several
    72   the module.  The latter can range from a single line to several
    73   paragraphs of explanations.
    73   paragraphs of explanations.
    74 
    74 
    75   The rest of the file is divided into sections, subsections,
    75   The rest of the file is divided into sections, subsections,
    76   subsubsections, paragraphs etc.\ using a simple layout via ML
    76   subsubsections, paragraphs etc.\ using a simple layout via ML
   261 
   261 
   262   Note that the goal state @{ML_text st} above is rarely made
   262   Note that the goal state @{ML_text st} above is rarely made
   263   explicit, if tactic combinators (tacticals) are used as usual.
   263   explicit, if tactic combinators (tacticals) are used as usual.
   264 
   264 
   265   A tactic that requires a proof context needs to make that explicit as seen
   265   A tactic that requires a proof context needs to make that explicit as seen
   266   in the @{verbatim ctxt} argument above. Do not refer to the background
   266   in the \<^verbatim>\<open>ctxt\<close> argument above. Do not refer to the background
   267   theory of @{verbatim st} -- it is not a proper context, but merely a formal
   267   theory of \<^verbatim>\<open>st\<close> -- it is not a proper context, but merely a formal
   268   certificate.
   268   certificate.
   269 \<close>
   269 \<close>
   270 
   270 
   271 
   271 
   272 subsection \<open>General source layout\<close>
   272 subsection \<open>General source layout\<close>
   514   environment holds ML compiler bindings, logical entities, and many other
   514   environment holds ML compiler bindings, logical entities, and many other
   515   things.
   515   things.
   516 
   516 
   517   Object-logics like Isabelle/HOL are built within the Isabelle/ML/Isar
   517   Object-logics like Isabelle/HOL are built within the Isabelle/ML/Isar
   518   environment by introducing suitable theories with associated ML modules,
   518   environment by introducing suitable theories with associated ML modules,
   519   either inlined within @{verbatim ".thy"} files, or as separate @{verbatim
   519   either inlined within \<^verbatim>\<open>.thy\<close> files, or as separate \<^verbatim>\<open>.ML\<close> files that are
   520   ".ML"} files that are loading from some theory. Thus Isabelle/HOL is defined
   520   loading from some theory. Thus Isabelle/HOL is defined
   521   as a regular user-space application within the Isabelle framework. Further
   521   as a regular user-space application within the Isabelle framework. Further
   522   add-on tools can be implemented in ML within the Isar context in the same
   522   add-on tools can be implemented in ML within the Isar context in the same
   523   manner: ML is part of the standard repertoire of Isabelle, and there is no
   523   manner: ML is part of the standard repertoire of Isabelle, and there is no
   524   distinction between ``users'' and ``developers'' in this respect.
   524   distinction between ``users'' and ``developers'' in this respect.
   525 \<close>
   525 \<close>
   968   messages: regular output, high-volume tracing information, warnings,
   968   messages: regular output, high-volume tracing information, warnings,
   969   and errors.
   969   and errors.
   970 
   970 
   971   Depending on the user interface involved, these messages may appear
   971   Depending on the user interface involved, these messages may appear
   972   in different text styles or colours.  The standard output for
   972   in different text styles or colours.  The standard output for
   973   batch sessions prefixes each line of warnings by @{verbatim
   973   batch sessions prefixes each line of warnings by \<^verbatim>\<open>###\<close> and errors by
   974   "###"} and errors by @{verbatim "***"}, but leaves anything else
   974   \<^verbatim>\<open>***\<close>, but leaves anything else
   975   unchanged.  The message body may contain further markup and formatting,
   975   unchanged.  The message body may contain further markup and formatting,
   976   which is routinely used in the Prover IDE @{cite "isabelle-jedit"}.
   976   which is routinely used in the Prover IDE @{cite "isabelle-jedit"}.
   977 
   977 
   978   Messages are associated with the transaction context of the running
   978   Messages are associated with the transaction context of the running
   979   Isar command.  This enables the front-end to manage commands and
   979   Isar command.  This enables the front-end to manage commands and
  1218   all.  Isabelle strings consist of a sequence of symbols, represented
  1218   all.  Isabelle strings consist of a sequence of symbols, represented
  1219   as a packed string or an exploded list of strings.  Each symbol is
  1219   as a packed string or an exploded list of strings.  Each symbol is
  1220   in itself a small string, which has either one of the following
  1220   in itself a small string, which has either one of the following
  1221   forms:
  1221   forms:
  1222 
  1222 
  1223   \<^enum> a single ASCII character ``\<open>c\<close>'', for example
  1223   \<^enum> a single ASCII character ``\<open>c\<close>'', for example ``\<^verbatim>\<open>a\<close>'',
  1224   ``@{verbatim a}'',
       
  1225 
  1224 
  1226   \<^enum> a codepoint according to UTF-8 (non-ASCII byte sequence),
  1225   \<^enum> a codepoint according to UTF-8 (non-ASCII byte sequence),
  1227 
  1226 
  1228   \<^enum> a regular symbol ``@{verbatim \<open>\\<close>}@{verbatim "<"}\<open>ident\<close>@{verbatim ">"}'', for example ``@{verbatim "\<alpha>"}'',
  1227   \<^enum> a regular symbol ``\<^verbatim>\<open>\\<close>\<^verbatim>\<open><\<close>\<open>ident\<close>\<^verbatim>\<open>>\<close>'', for example ``\<^verbatim>\<open>\<alpha>\<close>'',
  1229 
  1228 
  1230   \<^enum> a control symbol ``@{verbatim \<open>\\<close>}@{verbatim "<^"}\<open>ident\<close>@{verbatim ">"}'', for example ``@{verbatim "\<^bold>"}'',
  1229   \<^enum> a control symbol ``\<^verbatim>\<open>\\<close>\<^verbatim>\<open><^\<close>\<open>ident\<close>\<^verbatim>\<open>>\<close>'', for example ``\<^verbatim>\<open>\<^bold>\<close>'',
  1231 
  1230 
  1232   \<^enum> a raw symbol ``@{verbatim \<open>\\<close>}@{verbatim "<^raw:"}\<open>text\<close>@{verbatim ">"}'' where \<open>text\<close> consists of printable characters
  1231   \<^enum> a raw symbol ``\<^verbatim>\<open>\\<close>\<^verbatim>\<open><^raw:\<close>\<open>text\<close>\<^verbatim>\<open>>\<close>'' where \<open>text\<close> consists of printable characters
  1233   excluding ``@{verbatim "."}'' and ``@{verbatim ">"}'', for example
  1232   excluding ``\<^verbatim>\<open>.\<close>'' and ``\<^verbatim>\<open>>\<close>'', for example
  1234   ``@{verbatim "\<^raw:$\sum_{i = 1}^n$>"}'',
  1233   ``\<^verbatim>\<open>\<^raw:$\sum_{i = 1}^n$>\<close>'',
  1235 
  1234 
  1236   \<^enum> a numbered raw control symbol ``@{verbatim \<open>\\<close>}@{verbatim
  1235   \<^enum> a numbered raw control symbol ``\<^verbatim>\<open>\\<close>\<^verbatim>\<open><^raw\<close>\<open>n\<close>\<^verbatim>\<open>>\<close>, where \<open>n\<close> consists
  1237   "<^raw"}\<open>n\<close>@{verbatim ">"}, where \<open>n\<close> consists of digits, for
  1236   of digits, for example ``\<^verbatim>\<open>\<^raw42>\<close>''.
  1238   example ``@{verbatim "\<^raw42>"}''.
       
  1239 
  1237 
  1240 
  1238 
  1241   The \<open>ident\<close> syntax for symbol names is \<open>letter
  1239   The \<open>ident\<close> syntax for symbol names is \<open>letter
  1242   (letter | digit)\<^sup>*\<close>, where \<open>letter = A..Za..z\<close> and \<open>digit = 0..9\<close>.  There are infinitely many regular symbols and
  1240   (letter | digit)\<^sup>*\<close>, where \<open>letter = A..Za..z\<close> and \<open>digit = 0..9\<close>.  There are infinitely many regular symbols and
  1243   control symbols, but a fixed collection of standard symbols is
  1241   control symbols, but a fixed collection of standard symbols is
  1244   treated specifically.  For example, ``@{verbatim "\<alpha>"}'' is
  1242   treated specifically.  For example, ``\<^verbatim>\<open>\<alpha>\<close>'' is
  1245   classified as a letter, which means it may occur within regular
  1243   classified as a letter, which means it may occur within regular
  1246   Isabelle identifiers.
  1244   Isabelle identifiers.
  1247 
  1245 
  1248   The character set underlying Isabelle symbols is 7-bit ASCII, but 8-bit
  1246   The character set underlying Isabelle symbols is 7-bit ASCII, but 8-bit
  1249   character sequences are passed-through unchanged. Unicode/UCS data in UTF-8
  1247   character sequences are passed-through unchanged. Unicode/UCS data in UTF-8
  1253   to the standard collection of Isabelle regular symbols.
  1251   to the standard collection of Isabelle regular symbols.
  1254 
  1252 
  1255   \<^medskip>
  1253   \<^medskip>
  1256   Output of Isabelle symbols depends on the print mode. For example,
  1254   Output of Isabelle symbols depends on the print mode. For example,
  1257   the standard {\LaTeX} setup of the Isabelle document preparation system
  1255   the standard {\LaTeX} setup of the Isabelle document preparation system
  1258   would present ``@{verbatim "\<alpha>"}'' as \<open>\<alpha>\<close>, and ``@{verbatim
  1256   would present ``\<^verbatim>\<open>\<alpha>\<close>'' as \<open>\<alpha>\<close>, and ``\<^verbatim>\<open>\<^bold>\<alpha>\<close>'' as \<open>\<^bold>\<alpha>\<close>. On-screen rendering
  1259   "\<^bold>\<alpha>"}'' as \<open>\<^bold>\<alpha>\<close>. On-screen rendering usually works by mapping a
  1257   usually works by mapping a finite subset of Isabelle symbols to suitable
  1260   finite subset of Isabelle symbols to suitable Unicode characters.
  1258   Unicode characters.
  1261 \<close>
  1259 \<close>
  1262 
  1260 
  1263 text %mlref \<open>
  1261 text %mlref \<open>
  1264   \begin{mldecls}
  1262   \begin{mldecls}
  1265   @{index_ML_type "Symbol.symbol": string} \\
  1263   @{index_ML_type "Symbol.symbol": string} \\
  1359   
  1357   
  1360     \<^enum> XML tree structure via YXML (see also @{cite "isabelle-system"}),
  1358     \<^enum> XML tree structure via YXML (see also @{cite "isabelle-system"}),
  1361     with @{ML YXML.parse_body} as key operation.
  1359     with @{ML YXML.parse_body} as key operation.
  1362 
  1360 
  1363   Note that Isabelle/ML string literals may refer Isabelle symbols like
  1361   Note that Isabelle/ML string literals may refer Isabelle symbols like
  1364   ``@{verbatim \<alpha>}'' natively, \<^emph>\<open>without\<close> escaping the backslash. This is a
  1362   ``\<^verbatim>\<open>\<alpha>\<close>'' natively, \<^emph>\<open>without\<close> escaping the backslash. This is a
  1365   consequence of Isabelle treating all source text as strings of symbols,
  1363   consequence of Isabelle treating all source text as strings of symbols,
  1366   instead of raw characters.
  1364   instead of raw characters.
  1367 \<close>
  1365 \<close>
  1368 
  1366 
  1369 text %mlex \<open>The subsequent example illustrates the difference of
  1367 text %mlex \<open>The subsequent example illustrates the difference of
  1380 
  1378 
  1381 text \<open>Note that in Unicode renderings of the symbol \<open>\<A>\<close>,
  1379 text \<open>Note that in Unicode renderings of the symbol \<open>\<A>\<close>,
  1382   variations of encodings like UTF-8 or UTF-16 pose delicate questions
  1380   variations of encodings like UTF-8 or UTF-16 pose delicate questions
  1383   about the multi-byte representations of its codepoint, which is outside
  1381   about the multi-byte representations of its codepoint, which is outside
  1384   of the 16-bit address space of the original Unicode standard from
  1382   of the 16-bit address space of the original Unicode standard from
  1385   the 1990-ies.  In Isabelle/ML it is just ``@{verbatim \<A>}''
  1383   the 1990-ies.  In Isabelle/ML it is just ``\<^verbatim>\<open>\<A>\<close>''
  1386   literally, using plain ASCII characters beyond any doubts.\<close>
  1384   literally, using plain ASCII characters beyond any doubts.\<close>
  1387 
  1385 
  1388 
  1386 
  1389 subsection \<open>Integers\<close>
  1387 subsection \<open>Integers\<close>
  1390 
  1388 
  1539   \<^descr> @{ML AList.lookup}, @{ML AList.defined}, @{ML AList.update}
  1537   \<^descr> @{ML AList.lookup}, @{ML AList.defined}, @{ML AList.update}
  1540   implement the main ``framework operations'' for mappings in
  1538   implement the main ``framework operations'' for mappings in
  1541   Isabelle/ML, following standard conventions for their names and
  1539   Isabelle/ML, following standard conventions for their names and
  1542   types.
  1540   types.
  1543 
  1541 
  1544   Note that a function called @{verbatim lookup} is obliged to express its
  1542   Note that a function called \<^verbatim>\<open>lookup\<close> is obliged to express its
  1545   partiality via an explicit option element.  There is no choice to
  1543   partiality via an explicit option element.  There is no choice to
  1546   raise an exception, without changing the name to something like
  1544   raise an exception, without changing the name to something like
  1547   \<open>the_element\<close> or \<open>get\<close>.
  1545   \<open>the_element\<close> or \<open>get\<close>.
  1548 
  1546 
  1549   The \<open>defined\<close> operation is essentially a contraction of @{ML
  1547   The \<open>defined\<close> operation is essentially a contraction of @{ML
  1550   is_some} and @{verbatim "lookup"}, but this is sufficiently frequent to
  1548   is_some} and \<^verbatim>\<open>lookup\<close>, but this is sufficiently frequent to
  1551   justify its independent existence.  This also gives the
  1549   justify its independent existence.  This also gives the
  1552   implementation some opportunity for peep-hole optimization.
  1550   implementation some opportunity for peep-hole optimization.
  1553 
  1551 
  1554 
  1552 
  1555   Association lists are adequate as simple implementation of finite mappings
  1553   Association lists are adequate as simple implementation of finite mappings
  1840   evaluation via futures, asynchronous evaluation via promises,
  1838   evaluation via futures, asynchronous evaluation via promises,
  1841   evaluation with time limit etc.
  1839   evaluation with time limit etc.
  1842 
  1840 
  1843   \<^medskip>
  1841   \<^medskip>
  1844   An \<^emph>\<open>unevaluated expression\<close> is represented either as
  1842   An \<^emph>\<open>unevaluated expression\<close> is represented either as
  1845   unit abstraction @{verbatim "fn () => a"} of type
  1843   unit abstraction \<^verbatim>\<open>fn () => a\<close> of type
  1846   @{verbatim "unit -> 'a"} or as regular function
  1844   \<^verbatim>\<open>unit -> 'a\<close> or as regular function
  1847   @{verbatim "fn a => b"} of type @{verbatim "'a -> 'b"}.  Both forms
  1845   \<^verbatim>\<open>fn a => b\<close> of type \<^verbatim>\<open>'a -> 'b\<close>.  Both forms
  1848   occur routinely, and special care is required to tell them apart ---
  1846   occur routinely, and special care is required to tell them apart ---
  1849   the static type-system of SML is only of limited help here.
  1847   the static type-system of SML is only of limited help here.
  1850 
  1848 
  1851   The first form is more intuitive: some combinator \<open>(unit ->
  1849   The first form is more intuitive: some combinator \<open>(unit ->
  1852   'a) -> 'a\<close> applies the given function to \<open>()\<close> to initiate
  1850   'a) -> 'a\<close> applies the given function to \<open>()\<close> to initiate
  1906   \<^descr> @{ML Par_Exn.release_all}~\<open>results\<close> combines results
  1904   \<^descr> @{ML Par_Exn.release_all}~\<open>results\<close> combines results
  1907   that were produced independently (e.g.\ by parallel evaluation).  If
  1905   that were produced independently (e.g.\ by parallel evaluation).  If
  1908   all results are regular values, that list is returned.  Otherwise,
  1906   all results are regular values, that list is returned.  Otherwise,
  1909   the collection of all exceptions is raised, wrapped-up as collective
  1907   the collection of all exceptions is raised, wrapped-up as collective
  1910   parallel exception.  Note that the latter prevents access to
  1908   parallel exception.  Note that the latter prevents access to
  1911   individual exceptions by conventional @{verbatim "handle"} of ML.
  1909   individual exceptions by conventional \<^verbatim>\<open>handle\<close> of ML.
  1912 
  1910 
  1913   \<^descr> @{ML Par_Exn.release_first} is similar to @{ML
  1911   \<^descr> @{ML Par_Exn.release_first} is similar to @{ML
  1914   Par_Exn.release_all}, but only the first (meaningful) exception that has
  1912   Par_Exn.release_all}, but only the first (meaningful) exception that has
  1915   occurred in the original evaluation process is raised again, the others are
  1913   occurred in the original evaluation process is raised again, the others are
  1916   ignored.  That single exception may get handled by conventional
  1914   ignored.  That single exception may get handled by conventional
  2008   @{index_ML Lazy.lazy: "(unit -> 'a) -> 'a lazy"} \\
  2006   @{index_ML Lazy.lazy: "(unit -> 'a) -> 'a lazy"} \\
  2009   @{index_ML Lazy.value: "'a -> 'a lazy"} \\
  2007   @{index_ML Lazy.value: "'a -> 'a lazy"} \\
  2010   @{index_ML Lazy.force: "'a lazy -> 'a"} \\
  2008   @{index_ML Lazy.force: "'a lazy -> 'a"} \\
  2011   \end{mldecls}
  2009   \end{mldecls}
  2012 
  2010 
  2013   \<^descr> Type @{ML_type "'a lazy"} represents lazy values over type @{verbatim
  2011   \<^descr> Type @{ML_type "'a lazy"} represents lazy values over type \<^verbatim>\<open>'a\<close>.
  2014   "'a"}.
       
  2015 
  2012 
  2016   \<^descr> @{ML Lazy.lazy}~\<open>(fn () => e)\<close> wraps the unevaluated
  2013   \<^descr> @{ML Lazy.lazy}~\<open>(fn () => e)\<close> wraps the unevaluated
  2017   expression \<open>e\<close> as unfinished lazy value.
  2014   expression \<open>e\<close> as unfinished lazy value.
  2018 
  2015 
  2019   \<^descr> @{ML Lazy.value}~\<open>a\<close> wraps the value \<open>a\<close> as finished lazy
  2016   \<^descr> @{ML Lazy.value}~\<open>a\<close> wraps the value \<open>a\<close> as finished lazy
  2097   @{index_ML Future.cancel_group: "Future.group -> unit"} \\[0.5ex]
  2094   @{index_ML Future.cancel_group: "Future.group -> unit"} \\[0.5ex]
  2098   @{index_ML Future.promise: "(unit -> unit) -> 'a future"} \\
  2095   @{index_ML Future.promise: "(unit -> unit) -> 'a future"} \\
  2099   @{index_ML Future.fulfill: "'a future -> 'a -> unit"} \\
  2096   @{index_ML Future.fulfill: "'a future -> 'a -> unit"} \\
  2100   \end{mldecls}
  2097   \end{mldecls}
  2101 
  2098 
  2102   \<^descr> Type @{ML_type "'a future"} represents future values over type
  2099   \<^descr> Type @{ML_type "'a future"} represents future values over type \<^verbatim>\<open>'a\<close>.
  2103   @{verbatim "'a"}.
       
  2104 
  2100 
  2105   \<^descr> @{ML Future.fork}~\<open>(fn () => e)\<close> registers the unevaluated
  2101   \<^descr> @{ML Future.fork}~\<open>(fn () => e)\<close> registers the unevaluated
  2106   expression \<open>e\<close> as unfinished future value, to be evaluated eventually
  2102   expression \<open>e\<close> as unfinished future value, to be evaluated eventually
  2107   on the parallel worker-thread farm. This is a shorthand for @{ML
  2103   on the parallel worker-thread farm. This is a shorthand for @{ML
  2108   Future.forks} below, with default parameters and a single expression.
  2104   Future.forks} below, with default parameters and a single expression.