Index: doc/theses/jiada_liang_MMath/intro.tex =================================================================== --- doc/theses/jiada_liang_MMath/intro.tex (revision 48b76d030ee6e161979d10ff348ed37189d4e12e) +++ doc/theses/jiada_liang_MMath/intro.tex (revision 41fb996a500250f2d0a7d1f16e6147ada3c96f01) @@ -1,12 +1,13 @@ \chapter{Introduction} -All types in a programming language must have a set of constants, and these constants have primary names, \eg integral types have constants @-1@, @17@, @12345@, \etc. +All types in a programming language must have a set of constants, and these constants have \Newterm{primary names}, \eg integral types have constants @-1@, @17@, @12345@, \etc. Constants can be overloaded among types, \eg @0@ is a null pointer for all pointer types, and the value zero for integral and floating-point types. Hence, each primary constant has a symbolic name referring to its internal representation, and these names are dictated by language syntax related to types. In theory, there are an infinite set of primary names per type. -Secondary naming is a common practice in mathematics and engineering, \eg $\pi$, $\tau$ (2$\pi$), $\phi$ (golden ratio), MHz (1E6), and in general situations, \eg specific times (noon, New Years), cities (Big Apple), flowers (Lily), \etc. +\Newterm{Secondary naming} is a common practice in mathematics and engineering, \eg $\pi$, $\tau$ (2$\pi$), $\phi$ (golden ratio), MHz (1E6), and in general situations, \eg specific times (noon, New Years), cities (Big Apple), flowers (Lily), \etc. Many programming languages capture this important software-engineering capability through a mechanism called \Newterm{constant} or \Newterm{literal} naming, where a secondary name is aliased to a primary name. In some cases, secondary naming is \Newterm{pure}, where the matching internal representation can be chosen arbitrarily, and only equality operations are available, \eg @O_RDONLY@, @O_WRONLY@, @O_CREAT@, @O_TRUNC@, @O_APPEND@. +(The names the thing.) Because a secondary name is a constant, it cannot appear in a mutable context, \eg \mbox{$\pi$ \lstinline{= 42}} is meaningless, and a constant has no address, \ie it is an \Newterm{rvalue}\footnote{ The term rvalue defines an expression that can only appear on the right-hand side of an assignment expression.}. @@ -22,5 +23,5 @@ to specify as in a list or catalogue.~\cite{OED} \end{quote} -Within an enumeration set, the enumeration names must be unique, and instances of an enumerated type are restricted to its secondary names. +Within an enumeration set, the enumeration names must be unique, and instances of an enumerated type are restricted to hold only the secondary names. It is possible to enumerate among set names without having an ordering among the set elements. For example, the week, the weekdays, the weekend, and every second day of the week. @@ -49,5 +50,5 @@ \it\color{red}enumeration & \multicolumn{8}{c}{\it\color{red}enumerators} \\ $\downarrow$\hspace*{25pt} & \multicolumn{8}{c}{$\downarrow$} \\ -@enum@ Weekday \{ & Mon, & Tue, & Wed, & Thu, & Fri, & Sat, & Sun = 42 & \}; \\ +@enum@ Week \{ & Mon, & Tue, & Wed, & Thu, & Fri, & Sat, & Sun = 42 & \}; \\ \it\color{red}label & Mon & Tue & Wed & Thu & Fri & Sat & Sun & \\ \it\color{red}order & 0 & 1 & 2 & 3 & 4 & 5 & 6 & \\ @@ -55,5 +56,5 @@ \end{tabular} \end{cquote} -Here, the enumeration @Weekday@ defines the enumerator labels @Mon@, @Tue@, @Wed@, @Thu@, @Fri@, @Sat@ and @Sun@. +Here, the enumeration @Week@ defines the enumerator labels @Mon@, @Tue@, @Wed@, @Thu@, @Fri@, @Sat@ and @Sun@. The implicit ordering implies the successor of @Tue@ is @Mon@ and the predecessor of @Tue@ is @Wed@, independent of any associated enumerator values. The value is the constant represented by the secondary name, which can be implicitly or explicitly set. @@ -105,5 +106,5 @@ Hence, a variant is dynamically typed, as in a dynamic-typed programming-language, but the set of types is statically bound, similar to some aspects of dynamic gradual-typing~\cite{Gradual Typing}. Knowing which type is in a variant instance is crucial for correctness. -Occasionally, it is possible to statically determine, all regions where each variant type is used, so a tag and runtime checking is unnecessary; +Occasionally, it is possible to statically determine all regions where each variant type is used, so a tag and runtime checking is unnecessary; otherwise, a tag is required to denote the particular type in the variant and the tag checked at runtime using some form of type pattern-matching. @@ -120,5 +121,5 @@ For safety, either all variant types must be listed or a @default@ case must exist with no field accesses. -To simulate an enumeration with a variant, the tag is re-purposed for either ordering or value and the variant types are omitted. +To simulate an enumeration with a variant, the tag is \emph{re-purposed} for either ordering or value and the variant types are omitted. \begin{cfa} variant Weekday { @@ -129,9 +130,9 @@ }; \end{cfa} -The type system ensures tag setting and testing are correct. +The type system ensures tag setting and testing are correctly done. However, the enumeration operations are limited to the available tag operations, \eg pattern matching. \begin{cfa} -Weekday weekday = Mon; -if ( @dynamic_cast(Mon)@weekday ) ... // test tag == Mon +Week week = Mon; +if ( @dynamic_cast(Mon)@week ) ... // test tag == Mon \end{cfa} While enumerating among tag names is possible: @@ -143,17 +144,18 @@ However, if a special @enum@ variant allows the tags to be heterogeneously typed, ordering must fall back on case positioning, as many types have incomparable values. Iterating using tag ordering and heterogeneous types, also requires pattern matching. -\begin{cfa} +\begin{cfa}[morekeywords={match}] for ( cursor = Mon; cursor <= Fri; cursor = succ( cursor) ) { - switch( cursor ) { + match( cursor ) { case Mon { /* access special type for Mon */ } ... case Fri { /* access special type for Fri */ } + default } } \end{cfa} -If the variant type adds/removes types or the loop range changes, the pattern matching must be adjusted. -As well, if the start/stop values are dynamic, it is impossible to statically determine if all variant types are listed. +If the variant type is changed by adding/removing types or the loop range changes, the pattern matching must be adjusted. +As well, if the start/stop values are dynamic, it may be impossible to statically determine if all variant types are listed. -Forcing the notion of enumerating into variant types is ill formed and confusing. +Re-purposing the notion of enumerating into variant types is ill formed and confusing. Hence, there is only a weak equivalence between an enumeration and variant type, justifying the enumeration type in a programming language. @@ -163,5 +165,5 @@ The goal of this work is to to extend the simple and unsafe enumeration type in the C programming-language into a sophisticated and safe type in the \CFA programming-language, while maintain backwards compatibility with C. On the surface, enumerations seem like a simple type. -However, when extended with advanced features, enumerations become complex for both the type system and the implementation. +However, when extended with advanced features, enumerations become complex for both the type system and the runtime implementation. \begin{enumerate} Index: doc/theses/jiada_liang_MMath/relatedwork.tex =================================================================== --- doc/theses/jiada_liang_MMath/relatedwork.tex (revision 48b76d030ee6e161979d10ff348ed37189d4e12e) +++ doc/theses/jiada_liang_MMath/relatedwork.tex (revision 41fb996a500250f2d0a7d1f16e6147ada3c96f01) @@ -608,255 +608,44 @@ \lstnewenvironment{rust}[1][]{\lstset{language=Rust,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} -Enumerations +Rust provides a scoped enumeration based on variant types. +% An enumeration, also referred to as an enum, is a simultaneous definition of a nominal enumerated type as well as a set of constructors, that can be used to create or pattern-match values of the corresponding enumerated type. +An enumeration without constructors is called field-less. \begin{rust} - Syntax - Enumeration : - enum IDENTIFIER GenericParams? WhereClause? { EnumItems? } - - EnumItems : - EnumItem ( , EnumItem )* ,? - - EnumItem : - OuterAttribute* Visibility? - IDENTIFIER ( EnumItemTuple | EnumItemStruct )? EnumItemDiscriminant? - - EnumItemTuple : - ( TupleFields? ) - - EnumItemStruct : - { StructFields? } - - EnumItemDiscriminant : - = Expression +enum Week { Mon, Tues, Wed, Thu, Fri, Sat, Sun@,@ } +let mut week: Week = Week::Mon; +week = Week::Fri; \end{rust} -An enumeration, also referred to as an enum, is a simultaneous definition of a nominal enumerated type as well as a set of constructors, that can be used to create or pattern-match values of the corresponding enumerated type. - -Enumerations are declared with the keyword enum. - -An example of an enum item and its use: +A field-less enumeration with only unit variants is called unit-only. \begin{rust} -enum Animal { - Dog, - Cat, -} - -let mut a: Animal = Animal::Dog; -a = Animal::Cat; +enum Week { Mon = 0, Tues = 1, Wed = 2, Thu = 3, Fri = 4, Sat = 5, Sun = 6 } \end{rust} Enum constructors can have either named or unnamed fields: \begin{rust} enum Animal { - Dog(String, f64), - Cat { name: String, weight: f64 }, -} - + Dog( String, f64 ), + Cat{ name: String, weight: f64 }, +} let mut a: Animal = Animal::Dog("Cocoa".to_string(), 37.2); a = Animal::Cat { name: "Spotty".to_string(), weight: 2.7 }; \end{rust} -In this example, Cat is a struct-like enum variant, whereas Dog is simply called an enum variant. - -An enum where no constructors contain fields are called a field-less enum. For example, this is a fieldless enum: +Here, @Dog@ is an @enum@ variant, whereas @Cat@ is a struct-like variant. + +Each @enum@ type has an implicit integer tag (discriminant), with a unique value for each variant type. +Like a C enumeration, the tag values for the variant types start at 0 with auto incrementing. +The tag is re-purposed for enumeration by allowing it to be explicitly set, and auto incrmenting continues from that value. +\begin{cquote} +\sf\setlength{\tabcolsep}{3pt} +\begin{tabular}{rcccccccr} +@enum@ Week \{ & Mon, & Tue, & Wed = 2, & Thu = 10, & Fri, & Sat = 5, & Sun & \}; \\ +\rm tags & 0 & 1 & 2 & 10 & 11 & 5 & 6 & \\ +\end{tabular} +\end{cquote} +In general, the tag can only be read as an opaque reference for comparison. \begin{rust} -enum Fieldless { - Tuple(), - Struct{}, - Unit, -} +if mem::discriminant(&week) == mem::discriminant(&Week::Mon) ... \end{rust} -If a field-less enum only contains unit variants, the enum is called an unit-only enum. For example: +If the enumeration is unit-only, or field-less with no explicit discriminants and where only unit variants are explicit, then the discriminant is accessible with a numeric cast. \begin{rust} -enum Enum { - Foo = 3, - Bar = 2, - Baz = 1, -} -\end{rust} - -\subsection{Discriminants} - -Each enum instance has a discriminant: an integer logically associated to it that is used to determine which variant it holds. - -Under the default representation, the discriminant is interpreted as an isize value. However, the compiler is allowed to use a smaller type (or another means of distinguishing variants) in its actual memory layout. - -\subsection{Assigning discriminant values} - -\subsection{Explicit discriminants} - -In two circumstances, the discriminant of a variant may be explicitly set by following the variant name with = and a constant expression: - - if the enumeration is "unit-only". - - if a primitive representation is used. For example: -\begin{rust} - #[repr(u8)] - enum Enum { - Unit = 3, - Tuple(u16), - Struct { - a: u8, - b: u16, - } = 1, - } -\end{rust} - -\subsection{Implicit discriminants} - -If a discriminant for a variant is not specified, then it is set to one higher than the discriminant of the previous variant in the declaration. If the discriminant of the first variant in the declaration is unspecified, then it is set to zero. -\begin{rust} -enum Foo { - Bar, // 0 - Baz = 123, // 123 - Quux, // 124 -} - -let baz_discriminant = Foo::Baz as u32; -assert_eq!(baz_discriminant, 123); -\end{rust} - -\subsection{Restrictions} - -It is an error when two variants share the same discriminant. -\begin{rust} -enum SharedDiscriminantError { - SharedA = 1, - SharedB = 1 -} - -enum SharedDiscriminantError2 { - Zero, // 0 - One, // 1 - OneToo = 1 // 1 (collision with previous!) -} -\end{rust} -It is also an error to have an unspecified discriminant where the previous discriminant is the maximum value for the size of the discriminant. -\begin{rust} -#[repr(u8)] -enum OverflowingDiscriminantError { - Max = 255, - MaxPlusOne // Would be 256, but that overflows the enum. -} - -#[repr(u8)] -enum OverflowingDiscriminantError2 { - MaxMinusOne = 254, // 254 - Max, // 255 - MaxPlusOne // Would be 256, but that overflows the enum. -} -\end{rust} - -\subsection{Accessing discriminant} - -\begin{rust} -Via mem::discriminant -\end{rust} -@mem::discriminant@ returns an opaque reference to the discriminant of an enum value which can be compared. This cannot be used to get the value of the discriminant. - -\subsection{Casting} - -If an enumeration is unit-only (with no tuple and struct variants), then its discriminant can be directly accessed with a numeric cast; e.g.: -\begin{rust} -enum Enum { - Foo, - Bar, - Baz, -} - -assert_eq!(0, Enum::Foo as isize); -assert_eq!(1, Enum::Bar as isize); -assert_eq!(2, Enum::Baz as isize); -\end{rust} -Field-less enums can be casted if they do not have explicit discriminants, or where only unit variants are explicit. -\begin{rust} -enum Fieldless { - Tuple(), - Struct{}, - Unit, -} - -assert_eq!(0, Fieldless::Tuple() as isize); -assert_eq!(1, Fieldless::Struct{} as isize); -assert_eq!(2, Fieldless::Unit as isize); -\end{rust} -\begin{rust} -#[repr(u8)] -enum FieldlessWithDiscrimants { - First = 10, - Tuple(), - Second = 20, - Struct{}, - Unit, -} - -assert_eq!(10, FieldlessWithDiscrimants::First as u8); -assert_eq!(11, FieldlessWithDiscrimants::Tuple() as u8); -assert_eq!(20, FieldlessWithDiscrimants::Second as u8); -assert_eq!(21, FieldlessWithDiscrimants::Struct{} as u8); -assert_eq!(22, FieldlessWithDiscrimants::Unit as u8); -\end{rust} - -\subsection{Pointer casting} - -If the enumeration specifies a primitive representation, then the discriminant may be reliably accessed via unsafe pointer casting: -\begin{rust} -#[repr(u8)] -enum Enum { - Unit, - Tuple(bool), - Struct{a: bool}, -} - -impl Enum { - fn discriminant(&self) -> u8 { - unsafe { *(self as *const Self as *const u8) } - } -} - -let unit_like = Enum::Unit; -let tuple_like = Enum::Tuple(true); -let struct_like = Enum::Struct{a: false}; - -assert_eq!(0, unit_like.discriminant()); -assert_eq!(1, tuple_like.discriminant()); -assert_eq!(2, struct_like.discriminant()); -\end{rust} - -\subsection{Zero-variant enums} - -Enums with zero variants are known as zero-variant enums. As they have no valid values, they cannot be instantiated. -\begin{rust} -enum ZeroVariants {} -\end{rust} -Zero-variant enums are equivalent to the never type, but they cannot be coerced into other types. -\begin{rust} -let x: ZeroVariants = panic!(); -let y: u32 = x; // mismatched type error -\end{rust} - -\subsection{Variant visibility} - -Enum variants syntactically allow a Visibility annotation, but this is rejected when the enum is validated. This allows items to be parsed with a unified syntax across different contexts where they are used. -\begin{rust} -macro_rules! mac_variant { - ($vis:vis $name:ident) => { - enum $name { - $vis Unit, - - $vis Tuple(u8, u16), - - $vis Struct { f: u8 }, - } - } -} - -// Empty `vis` is allowed. -mac_variant! { E } - -// This is allowed, since it is removed before being validated. -#[cfg(FALSE)] -enum E { - pub U, - pub(crate) T(u8), - pub(super) T { f: String } -} +if week as isize == Week::Mon as isize ... \end{rust}