# HG changeset patch # User wenzelm # Date 1157737483 -7200 # Node ID 99ad217b6974c15e61774f81c45b3e43001c48d3 # Parent 48fea5e99505e97959f073a2cf0a7b18e8528aa1 tuned; diff -r 48fea5e99505 -r 99ad217b6974 doc-src/IsarImplementation/Thy/document/logic.tex --- a/doc-src/IsarImplementation/Thy/document/logic.tex Fri Sep 08 17:33:05 2006 +0200 +++ b/doc-src/IsarImplementation/Thy/document/logic.tex Fri Sep 08 19:44:43 2006 +0200 @@ -81,35 +81,34 @@ A \emph{type constructor} \isa{{\isasymkappa}} is a \isa{k}-ary operator on types declared in the theory. Type constructor application is - usually written postfix as \isa{{\isacharparenleft}FIXME{\isacharparenright}{\isasymkappa}}. For \isa{k\ {\isacharequal}\ {\isadigit{0}}} - the argument tuple is omitted, e.g.\ \isa{prop} instead of - \isa{{\isacharparenleft}{\isacharparenright}prop}. For \isa{k\ {\isacharequal}\ {\isadigit{1}}} the parentheses are omitted, - e.g.\ \isa{{\isasymalpha}\ list} instead of \isa{{\isacharparenleft}{\isasymalpha}{\isacharparenright}list}. Further - notation is provided for specific constructors, notably - right-associative infix \isa{{\isasymalpha}\ {\isasymRightarrow}\ {\isasymbeta}} instead of \isa{{\isacharparenleft}{\isasymalpha}{\isacharcomma}\ {\isasymbeta}{\isacharparenright}fun} constructor. + usually written postfix as \isa{{\isacharparenleft}{\isasymalpha}\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ {\isasymalpha}\isactrlisub k{\isacharparenright}{\isasymkappa}}. + For \isa{k\ {\isacharequal}\ {\isadigit{0}}} the argument tuple is omitted, e.g.\ \isa{prop} instead of \isa{{\isacharparenleft}{\isacharparenright}prop}. For \isa{k\ {\isacharequal}\ {\isadigit{1}}} the + parentheses are omitted, e.g.\ \isa{{\isasymalpha}\ list} instead of \isa{{\isacharparenleft}{\isasymalpha}{\isacharparenright}list}. Further notation is provided for specific constructors, + notably the right-associative infix \isa{{\isasymalpha}\ {\isasymRightarrow}\ {\isasymbeta}} instead of + \isa{{\isacharparenleft}{\isasymalpha}{\isacharcomma}\ {\isasymbeta}{\isacharparenright}fun}. A \emph{type} is defined inductively over type variables and type - constructors as follows: \isa{{\isasymtau}\ {\isacharequal}\ {\isasymalpha}\isactrlisub s\ {\isacharbar}\ {\isacharquery}{\isasymalpha}\isactrlisub s\ {\isacharbar}\ {\isacharparenleft}{\isasymtau}\isactrlsub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ {\isasymtau}\isactrlsub k{\isacharparenright}c}. + constructors as follows: \isa{{\isasymtau}\ {\isacharequal}\ {\isasymalpha}\isactrlisub s\ {\isacharbar}\ {\isacharquery}{\isasymalpha}\isactrlisub s\ {\isacharbar}\ {\isacharparenleft}{\isasymtau}\isactrlsub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ {\isasymtau}\isactrlsub k{\isacharparenright}k}. - A \emph{type abbreviation} is a syntactic abbreviation of an - arbitrary type expression of the theory. Type abbreviations looks - like type constructors at the surface, but are expanded before the - core logic encounters them. + A \emph{type abbreviation} is a syntactic abbreviation \isa{{\isacharparenleft}\isactrlvec {\isasymalpha}{\isacharparenright}{\isasymkappa}\ {\isacharequal}\ {\isasymtau}} of an arbitrary type expression \isa{{\isasymtau}} over + variables \isa{\isactrlvec {\isasymalpha}}. Type abbreviations looks like type + constructors at the surface, but are fully expanded before entering + the logical core. A \emph{type arity} declares the image behavior of a type - constructor wrt.\ the algebra of sorts: \isa{c\ {\isacharcolon}{\isacharcolon}\ {\isacharparenleft}s\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ s\isactrlisub k{\isacharparenright}s} means that \isa{{\isacharparenleft}{\isasymtau}\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ {\isasymtau}\isactrlisub k{\isacharparenright}c} is - of sort \isa{s} if each argument type \isa{{\isasymtau}\isactrlisub i} is of - sort \isa{s\isactrlisub i}. Arity declarations are implicitly - completed, i.e.\ \isa{c\ {\isacharcolon}{\isacharcolon}\ {\isacharparenleft}\isactrlvec s{\isacharparenright}c} entails \isa{c\ {\isacharcolon}{\isacharcolon}\ {\isacharparenleft}\isactrlvec s{\isacharparenright}c{\isacharprime}} for any \isa{c{\isacharprime}\ {\isasymsupseteq}\ c}. + constructor wrt.\ the algebra of sorts: \isa{{\isasymkappa}\ {\isacharcolon}{\isacharcolon}\ {\isacharparenleft}s\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ s\isactrlisub k{\isacharparenright}s} means that \isa{{\isacharparenleft}{\isasymtau}\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ {\isasymtau}\isactrlisub k{\isacharparenright}{\isasymkappa}} is + of sort \isa{s} if every argument type \isa{{\isasymtau}\isactrlisub i} is + of sort \isa{s\isactrlisub i}. Arity declarations are implicitly + completed, i.e.\ \isa{{\isasymkappa}\ {\isacharcolon}{\isacharcolon}\ {\isacharparenleft}\isactrlvec s{\isacharparenright}c} entails \isa{{\isasymkappa}\ {\isacharcolon}{\isacharcolon}\ {\isacharparenleft}\isactrlvec s{\isacharparenright}c{\isacharprime}} for any \isa{c{\isacharprime}\ {\isasymsupseteq}\ c}. \medskip The sort algebra is always maintained as \emph{coregular}, which means that type arities are consistent with the subclass - relation: for each type constructor \isa{c} and classes \isa{c\isactrlisub {\isadigit{1}}\ {\isasymsubseteq}\ c\isactrlisub {\isadigit{2}}}, any arity \isa{c\ {\isacharcolon}{\isacharcolon}\ {\isacharparenleft}\isactrlvec s\isactrlisub {\isadigit{1}}{\isacharparenright}c\isactrlisub {\isadigit{1}}} has a corresponding arity \isa{c\ {\isacharcolon}{\isacharcolon}\ {\isacharparenleft}\isactrlvec s\isactrlisub {\isadigit{2}}{\isacharparenright}c\isactrlisub {\isadigit{2}}} where \isa{\isactrlvec s\isactrlisub {\isadigit{1}}\ {\isasymsubseteq}\ \isactrlvec s\isactrlisub {\isadigit{2}}} holds pointwise for all argument sorts. + relation: for each type constructor \isa{{\isasymkappa}} and classes \isa{c\isactrlisub {\isadigit{1}}\ {\isasymsubseteq}\ c\isactrlisub {\isadigit{2}}}, any arity \isa{{\isasymkappa}\ {\isacharcolon}{\isacharcolon}\ {\isacharparenleft}\isactrlvec s\isactrlisub {\isadigit{1}}{\isacharparenright}c\isactrlisub {\isadigit{1}}} has a corresponding arity \isa{{\isasymkappa}\ {\isacharcolon}{\isacharcolon}\ {\isacharparenleft}\isactrlvec s\isactrlisub {\isadigit{2}}{\isacharparenright}c\isactrlisub {\isadigit{2}}} where \isa{\isactrlvec s\isactrlisub {\isadigit{1}}\ {\isasymsubseteq}\ \isactrlvec s\isactrlisub {\isadigit{2}}} holds componentwise. The key property of a coregular order-sorted algebra is that sort - constraints may be always fulfilled in a most general fashion: for - each type constructor \isa{c} and sort \isa{s} there is a - most general vector of argument sorts \isa{{\isacharparenleft}s\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ s\isactrlisub k{\isacharparenright}} such that a type scheme \isa{{\isacharparenleft}{\isasymalpha}\isactrlbsub s\isactrlisub {\isadigit{1}}\isactrlesub {\isacharcomma}\ {\isasymdots}{\isacharcomma}\ {\isasymalpha}\isactrlbsub s\isactrlisub k\isactrlesub {\isacharparenright}c} is + constraints may be always solved in a most general fashion: for each + type constructor \isa{{\isasymkappa}} and sort \isa{s} there is a most + general vector of argument sorts \isa{{\isacharparenleft}s\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ s\isactrlisub k{\isacharparenright}} such that a type scheme \isa{{\isacharparenleft}{\isasymalpha}\isactrlbsub s\isactrlisub {\isadigit{1}}\isactrlesub {\isacharcomma}\ {\isasymdots}{\isacharcomma}\ {\isasymalpha}\isactrlbsub s\isactrlisub k\isactrlesub {\isacharparenright}{\isasymkappa}} is of sort \isa{s}. Consequently, the unification problem on the algebra of types has most general solutions (modulo renaming and equivalence of sorts). Moreover, the usual type-inference algorithm @@ -127,8 +126,9 @@ \begin{mldecls} \indexmltype{class}\verb|type class| \\ \indexmltype{sort}\verb|type sort| \\ + \indexmltype{arity}\verb|type arity| \\ \indexmltype{typ}\verb|type typ| \\ - \indexmltype{arity}\verb|type arity| \\ + \indexml{fold-atyps}\verb|fold_atyps: (typ -> 'a -> 'a) -> typ -> 'a -> 'a| \\ \indexml{Sign.subsort}\verb|Sign.subsort: theory -> sort * sort -> bool| \\ \indexml{Sign.of-sort}\verb|Sign.of_sort: theory -> typ * sort -> bool| \\ \indexml{Sign.add-types}\verb|Sign.add_types: (bstring * int * mixfix) list -> theory -> theory| \\ @@ -148,32 +148,35 @@ \verb|class list|. \item \verb|arity| represents type arities; this is an alias for - triples of the form \isa{{\isacharparenleft}c{\isacharcomma}\ \isactrlvec s{\isacharcomma}\ s{\isacharparenright}} for \isa{c\ {\isacharcolon}{\isacharcolon}\ {\isacharparenleft}\isactrlvec s{\isacharparenright}s} described above. + triples of the form \isa{{\isacharparenleft}{\isasymkappa}{\isacharcomma}\ \isactrlvec s{\isacharcomma}\ s{\isacharparenright}} for \isa{{\isasymkappa}\ {\isacharcolon}{\isacharcolon}\ {\isacharparenleft}\isactrlvec s{\isacharparenright}s} described above. \item \verb|typ| represents types; this is a datatype with constructors \verb|TFree|, \verb|TVar|, \verb|Type|. + \item \verb|fold_atyps|~\isa{f\ {\isasymtau}} iterates function \isa{f} + over all occurrences of atoms (\verb|TFree| or \verb|TVar|) of \isa{{\isasymtau}}; the type structure is traversed from left to right. + \item \verb|Sign.subsort|~\isa{thy\ {\isacharparenleft}s\isactrlisub {\isadigit{1}}{\isacharcomma}\ s\isactrlisub {\isadigit{2}}{\isacharparenright}} tests the subsort relation \isa{s\isactrlisub {\isadigit{1}}\ {\isasymsubseteq}\ s\isactrlisub {\isadigit{2}}}. \item \verb|Sign.of_sort|~\isa{thy\ {\isacharparenleft}{\isasymtau}{\isacharcomma}\ s{\isacharparenright}} tests whether a type is of a given sort. - \item \verb|Sign.add_types|~\isa{{\isacharbrackleft}{\isacharparenleft}c{\isacharcomma}\ k{\isacharcomma}\ mx{\isacharparenright}{\isacharcomma}\ {\isasymdots}{\isacharbrackright}} declares new - type constructors \isa{c} with \isa{k} arguments and + \item \verb|Sign.add_types|~\isa{{\isacharbrackleft}{\isacharparenleft}{\isasymkappa}{\isacharcomma}\ k{\isacharcomma}\ mx{\isacharparenright}{\isacharcomma}\ {\isasymdots}{\isacharbrackright}} declares new + type constructors \isa{{\isasymkappa}} with \isa{k} arguments and optional mixfix syntax. - \item \verb|Sign.add_tyabbrs_i|~\isa{{\isacharbrackleft}{\isacharparenleft}c{\isacharcomma}\ \isactrlvec {\isasymalpha}{\isacharcomma}\ {\isasymtau}{\isacharcomma}\ mx{\isacharparenright}{\isacharcomma}\ {\isasymdots}{\isacharbrackright}} - defines a new type abbreviation \isa{{\isacharparenleft}\isactrlvec {\isasymalpha}{\isacharparenright}c\ {\isacharequal}\ {\isasymtau}} with + \item \verb|Sign.add_tyabbrs_i|~\isa{{\isacharbrackleft}{\isacharparenleft}{\isasymkappa}{\isacharcomma}\ \isactrlvec {\isasymalpha}{\isacharcomma}\ {\isasymtau}{\isacharcomma}\ mx{\isacharparenright}{\isacharcomma}\ {\isasymdots}{\isacharbrackright}} + defines a new type abbreviation \isa{{\isacharparenleft}\isactrlvec {\isasymalpha}{\isacharparenright}{\isasymkappa}\ {\isacharequal}\ {\isasymtau}} with optional mixfix syntax. - \item \verb|Sign.primitive_class|~\isa{{\isacharparenleft}c{\isacharcomma}\ {\isacharbrackleft}c\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ c\isactrlisub n{\isacharbrackright}{\isacharparenright}} declares new class \isa{c} derived together with - class relations \isa{c\ {\isasymsubseteq}\ c\isactrlisub i}, for \isa{i\ {\isacharequal}\ {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ n}. + \item \verb|Sign.primitive_class|~\isa{{\isacharparenleft}c{\isacharcomma}\ {\isacharbrackleft}c\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ c\isactrlisub n{\isacharbrackright}{\isacharparenright}} declares new class \isa{c}, together with class + relations \isa{c\ {\isasymsubseteq}\ c\isactrlisub i}, for \isa{i\ {\isacharequal}\ {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ n}. \item \verb|Sign.primitive_classrel|~\isa{{\isacharparenleft}c\isactrlisub {\isadigit{1}}{\isacharcomma}\ c\isactrlisub {\isadigit{2}}{\isacharparenright}} declares class relation \isa{c\isactrlisub {\isadigit{1}}\ {\isasymsubseteq}\ c\isactrlisub {\isadigit{2}}}. - \item \verb|Sign.primitive_arity|~\isa{{\isacharparenleft}c{\isacharcomma}\ \isactrlvec s{\isacharcomma}\ s{\isacharparenright}} declares - arity \isa{c\ {\isacharcolon}{\isacharcolon}\ {\isacharparenleft}\isactrlvec s{\isacharparenright}s}. + \item \verb|Sign.primitive_arity|~\isa{{\isacharparenleft}{\isasymkappa}{\isacharcomma}\ \isactrlvec s{\isacharcomma}\ s{\isacharparenright}} declares + arity \isa{{\isasymkappa}\ {\isacharcolon}{\isacharcolon}\ {\isacharparenleft}\isactrlvec s{\isacharparenright}s}. \end{description}% \end{isamarkuptext}% diff -r 48fea5e99505 -r 99ad217b6974 doc-src/IsarImplementation/Thy/logic.thy --- a/doc-src/IsarImplementation/Thy/logic.thy Fri Sep 08 17:33:05 2006 +0200 +++ b/doc-src/IsarImplementation/Thy/logic.thy Fri Sep 08 19:44:43 2006 +0200 @@ -70,45 +70,46 @@ A \emph{type constructor} @{text "\"} is a @{text "k"}-ary operator on types declared in the theory. Type constructor application is - usually written postfix as @{text "(FIXME)\"}. For @{text "k = 0"} - the argument tuple is omitted, e.g.\ @{text "prop"} instead of - @{text "()prop"}. For @{text "k = 1"} the parentheses are omitted, - e.g.\ @{text "\ list"} instead of @{text "(\)list"}. Further - notation is provided for specific constructors, notably - right-associative infix @{text "\ \ \"} instead of @{text "(\, - \)fun"} constructor. + usually written postfix as @{text "(\\<^isub>1, \, \\<^isub>k)\"}. + For @{text "k = 0"} the argument tuple is omitted, e.g.\ @{text + "prop"} instead of @{text "()prop"}. For @{text "k = 1"} the + parentheses are omitted, e.g.\ @{text "\ list"} instead of @{text + "(\)list"}. Further notation is provided for specific constructors, + notably the right-associative infix @{text "\ \ \"} instead of + @{text "(\, \)fun"}. A \emph{type} is defined inductively over type variables and type constructors as follows: @{text "\ = \\<^isub>s | ?\\<^isub>s | - (\\<^sub>1, \, \\<^sub>k)c"}. + (\\<^sub>1, \, \\<^sub>k)k"}. - A \emph{type abbreviation} is a syntactic abbreviation of an - arbitrary type expression of the theory. Type abbreviations looks - like type constructors at the surface, but are expanded before the - core logic encounters them. + A \emph{type abbreviation} is a syntactic abbreviation @{text + "(\<^vec>\)\ = \"} of an arbitrary type expression @{text "\"} over + variables @{text "\<^vec>\"}. Type abbreviations looks like type + constructors at the surface, but are fully expanded before entering + the logical core. A \emph{type arity} declares the image behavior of a type - constructor wrt.\ the algebra of sorts: @{text "c :: (s\<^isub>1, \, - s\<^isub>k)s"} means that @{text "(\\<^isub>1, \, \\<^isub>k)c"} is - of sort @{text "s"} if each argument type @{text "\\<^isub>i"} is of - sort @{text "s\<^isub>i"}. Arity declarations are implicitly - completed, i.e.\ @{text "c :: (\<^vec>s)c"} entails @{text "c :: + constructor wrt.\ the algebra of sorts: @{text "\ :: (s\<^isub>1, \, + s\<^isub>k)s"} means that @{text "(\\<^isub>1, \, \\<^isub>k)\"} is + of sort @{text "s"} if every argument type @{text "\\<^isub>i"} is + of sort @{text "s\<^isub>i"}. Arity declarations are implicitly + completed, i.e.\ @{text "\ :: (\<^vec>s)c"} entails @{text "\ :: (\<^vec>s)c'"} for any @{text "c' \ c"}. \medskip The sort algebra is always maintained as \emph{coregular}, which means that type arities are consistent with the subclass - relation: for each type constructor @{text "c"} and classes @{text - "c\<^isub>1 \ c\<^isub>2"}, any arity @{text "c :: - (\<^vec>s\<^isub>1)c\<^isub>1"} has a corresponding arity @{text "c + relation: for each type constructor @{text "\"} and classes @{text + "c\<^isub>1 \ c\<^isub>2"}, any arity @{text "\ :: + (\<^vec>s\<^isub>1)c\<^isub>1"} has a corresponding arity @{text "\ :: (\<^vec>s\<^isub>2)c\<^isub>2"} where @{text "\<^vec>s\<^isub>1 \ - \<^vec>s\<^isub>2"} holds pointwise for all argument sorts. + \<^vec>s\<^isub>2"} holds componentwise. The key property of a coregular order-sorted algebra is that sort - constraints may be always fulfilled in a most general fashion: for - each type constructor @{text "c"} and sort @{text "s"} there is a - most general vector of argument sorts @{text "(s\<^isub>1, \, + constraints may be always solved in a most general fashion: for each + type constructor @{text "\"} and sort @{text "s"} there is a most + general vector of argument sorts @{text "(s\<^isub>1, \, s\<^isub>k)"} such that a type scheme @{text - "(\\<^bsub>s\<^isub>1\<^esub>, \, \\<^bsub>s\<^isub>k\<^esub>)c"} is + "(\\<^bsub>s\<^isub>1\<^esub>, \, \\<^bsub>s\<^isub>k\<^esub>)\"} is of sort @{text "s"}. Consequently, the unification problem on the algebra of types has most general solutions (modulo renaming and equivalence of sorts). Moreover, the usual type-inference algorithm @@ -119,8 +120,9 @@ \begin{mldecls} @{index_ML_type class} \\ @{index_ML_type sort} \\ + @{index_ML_type arity} \\ @{index_ML_type typ} \\ - @{index_ML_type arity} \\ + @{index_ML fold_atyps: "(typ -> 'a -> 'a) -> typ -> 'a -> 'a"} \\ @{index_ML Sign.subsort: "theory -> sort * sort -> bool"} \\ @{index_ML Sign.of_sort: "theory -> typ * sort -> bool"} \\ @{index_ML Sign.add_types: "(bstring * int * mixfix) list -> theory -> theory"} \\ @@ -140,36 +142,40 @@ @{ML_type "class list"}. \item @{ML_type arity} represents type arities; this is an alias for - triples of the form @{text "(c, \<^vec>s, s)"} for @{text "c :: + triples of the form @{text "(\, \<^vec>s, s)"} for @{text "\ :: (\<^vec>s)s"} described above. \item @{ML_type typ} represents types; this is a datatype with constructors @{ML TFree}, @{ML TVar}, @{ML Type}. + \item @{ML fold_atyps}~@{text "f \"} iterates function @{text "f"} + over all occurrences of atoms (@{ML TFree} or @{ML TVar}) of @{text + "\"}; the type structure is traversed from left to right. + \item @{ML Sign.subsort}~@{text "thy (s\<^isub>1, s\<^isub>2)"} tests the subsort relation @{text "s\<^isub>1 \ s\<^isub>2"}. \item @{ML Sign.of_sort}~@{text "thy (\, s)"} tests whether a type is of a given sort. - \item @{ML Sign.add_types}~@{text "[(c, k, mx), \]"} declares new - type constructors @{text "c"} with @{text "k"} arguments and + \item @{ML Sign.add_types}~@{text "[(\, k, mx), \]"} declares new + type constructors @{text "\"} with @{text "k"} arguments and optional mixfix syntax. - \item @{ML Sign.add_tyabbrs_i}~@{text "[(c, \<^vec>\, \, mx), \]"} - defines a new type abbreviation @{text "(\<^vec>\)c = \"} with + \item @{ML Sign.add_tyabbrs_i}~@{text "[(\, \<^vec>\, \, mx), \]"} + defines a new type abbreviation @{text "(\<^vec>\)\ = \"} with optional mixfix syntax. \item @{ML Sign.primitive_class}~@{text "(c, [c\<^isub>1, \, - c\<^isub>n])"} declares new class @{text "c"} derived together with - class relations @{text "c \ c\<^isub>i"}, for @{text "i = 1, \, n"}. + c\<^isub>n])"} declares new class @{text "c"}, together with class + relations @{text "c \ c\<^isub>i"}, for @{text "i = 1, \, n"}. \item @{ML Sign.primitive_classrel}~@{text "(c\<^isub>1, c\<^isub>2)"} declares class relation @{text "c\<^isub>1 \ c\<^isub>2"}. - \item @{ML Sign.primitive_arity}~@{text "(c, \<^vec>s, s)"} declares - arity @{text "c :: (\<^vec>s)s"}. + \item @{ML Sign.primitive_arity}~@{text "(\, \<^vec>s, s)"} declares + arity @{text "\ :: (\<^vec>s)s"}. \end{description} *}