Index: doc/bibliography/pl.bib =================================================================== --- doc/bibliography/pl.bib (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ doc/bibliography/pl.bib (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -1263,5 +1263,5 @@ school = {School of Computer Science, University of Waterloo}, year = 2019, - optaddress = {Waterloo, Ontario, Canada, N2L 3G1}, + address = {Waterloo, Ontario, Canada, N2L 3G1}, note = {\url{https://uwspace.uwaterloo.ca/handle/10012/14584}}, } @@ -1955,5 +1955,5 @@ school = {School of Computer Sc., University of Waterloo}, year = 2015, - optaddress = {Waterloo, Ontario, Canada, N2L 3G1}, + address = {Waterloo, Ontario, Canada, N2L 3G1}, note = {\url{https://uwspace.uwaterloo.ca/handle/10012/10013}}, } @@ -4130,5 +4130,5 @@ school = {School of Computer Sc., University of Waterloo}, year = 2019, - optaddress = {Waterloo, Ontario, Canada, N2L 3G1}, + address = {Waterloo, Ontario, Canada, N2L 3G1}, note = {\url{https://uwspace.uwaterloo.ca/handle/10012/14706}}, } @@ -4323,5 +4323,5 @@ school = {School of Computer Science, University of Waterloo}, year = 2003, - optaddress = {Waterloo, Ontario, Canada, N2L 3G1}, + address = {Waterloo, Ontario, Canada, N2L 3G1}, note = {\url{http://plg.uwaterloo.ca/theses/BilsonThesis.pdf}}, } @@ -4364,5 +4364,5 @@ year = 2018, month = sep, - optaddress = {Waterloo, Ontario, Canada, N2L 3G1}, + address = {Waterloo, Ontario, Canada, N2L 3G1}, note = {\url{https://uwspace.uwaterloo.ca/handle/10012/13935}}, } @@ -5990,5 +5990,5 @@ key = {OCaml}, title = {The {OC}aml system, release 5.1}, - optaddress = {Rust Project Developers}, + address = {Rust Project Developers}, year = 2023, note = {\url{https://v2.ocaml.org/manual/}}, @@ -7007,7 +7007,7 @@ organization= {United States Department of Defense}, edition = {{ANSI/MIL-STD-1815A-1983}}, + address = {Springer, New York}, month = feb, year = 1983, - note = {Springer, New York}, } @@ -7421,5 +7421,5 @@ school = {School of Computer Science, University of Waterloo}, year = 2017, - optaddress = {Waterloo, Ontario, Canada, N2L 3G1}, + address = {Waterloo, Ontario, Canada, N2L 3G1}, note = {\url{https://uwspace.uwaterloo.ca/handle/10012/11830}}, } @@ -7508,5 +7508,5 @@ key = {Rust}, title = {{R}ust Programming Language}, - optaddress = {Rust Project Developers}, + address = {Rust Project Developers}, year = 2015, note = {\url{https://doc.rust-lang.org/reference.html}}, @@ -7729,26 +7729,4 @@ publisher = {Morgan \& Claypool}, year = 2013, -} - -@inproceedings{Leissa14, - title = {{S}ierra: a {SIMD} extension for {C}++}, - author = {Lei{\ss}a, Roland and Haffner, Immanuel and Hack, Sebastian}, - booktitle = {Proceedings of the 2014 Workshop on Workshop on programming models for SIMD/Vector processing}, - pages = {17-24}, - year = {2014}, - organization= {ACM} -} - -@article{Nickolls08, - author = {Nickolls, John and Buck, Ian and Garland, Michael and Skadron, Kevin}, - title = {Scalable Parallel Programming with CUDA}, - journal = {Queue}, - volume = {6}, - number = {2}, - month = mar, - year = 2008, - pages = {40-53}, - publisher = {ACM}, - address = {New York, NY, USA}, } Index: doc/theses/jiada_liang_MMath/CFAenum.tex =================================================================== --- doc/theses/jiada_liang_MMath/CFAenum.tex (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ doc/theses/jiada_liang_MMath/CFAenum.tex (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -1,6 +1,6 @@ -\chapter{\CFA-Style Enum} - - -\CFA supports C-Style enumeration using the same syntax and semantics for backwards compatibility. +\chapter{\CFA Enumeration} + + +\CFA supports C enumeration using the same syntax and semantics for backwards compatibility. \CFA also extends C-Style enumeration by adding a number of new features that bring enumerations inline with other modern programming languages. @@ -16,16 +16,18 @@ Finally, qualification is provided to disambiguate any ambiguous situations. \begin{cfa} -enum C1 { First, Second, Third, Fourth }; -enum C2 { @Fourth@, @Third@, @Second@, @First@ }; -C1 p() { return Third; } $\C{// correctly resolved duplicate names}$ -C2 p() { return Fourth; } +enum E1 { First, Second, Third, Fourth }; +enum E2 { @Fourth@, @Third@, @Second@, @First@ }; +E1 p() { return Third; } $\C{// correctly resolved duplicate names}$ +E2 p() { return Fourth; } void foo() { - C1 e1 = First; C2 e2 = First; + E1 e1 = First; E2 e2 = First; e1 = Second; e2 = Second; e1 = p(); e2 = p(); $\C{// correctly resolved function call}$ - int i = @C1.@First + @C2.@First; $\C{// ambiguous without qualification}$ -} -\end{cfa} -\CFA overloading allows programmers to use the most meaningful names without fear of unresolvable clashes from included files, which are correctable with qualification. + int i = @E1.@First + @E2.@First; $\C{// disambiguate with qualification}$ + int j = @(E1)@First + @(E2)@First; $\C{// disambiguate with cast}$ +} +\end{cfa} +\CFA overloading allows programmers to use the most meaningful names without fear of name clashes from include files. +Either the type system implicitly disambiguates or the programmer explicitly disambiguates using qualification or casting. @@ -34,23 +36,22 @@ An enumeration can be scoped, so the enumerator constants are not projected into the enclosing scope, using @'!'@. \begin{cfa} -enum Weekday @!@ { /* as above */ }; -enum( char * ) Names @!@ { /* as above */ }; +enum Weekday @!@ { Mon, Tue, Wed, Thu = 10, Fri, Sat, Sun }; +enum RGB @!@ { Red, Green, Blue }; \end{cfa} Now the enumerators \emph{must} be qualified with the associated enumeration. \begin{cfa} -Weekday weekday = @Weekday@.Monday; -Names names = @Names.@Fred; -names = @Names.@Jane; +Weekday weekday = @Weekday@.Mon; +weekday = @Weekday@.Sat; +RGB rgb = RGB.Red; +rgb = RGB.Blue; \end{cfa} It is possible to toggle back to unscoping using the \CFA @with@ clause/statement (see also \CC \lstinline[language=c++]{using enum} in Section~\ref{s:C++RelatedWork}). \begin{cfa} -Weekday weekday; -with ( @Weekday@, @Names@ ) { $\C{// type names}$ - Names names = @Fred@; - names = @Jane@; - weekday = Saturday; -} -\end{cfa} -As in Section~\ref{s:EnumeratorNameResolution}, opening multiple unscoped enumerations can result in duplicate enumeration names, but \CFA type resolution and falling back to explicit qualification handles name resolution. +with ( @Weekday@, @RGB@ ) { $\C{// type names}$ + weekday = @Sun@; $\C{// no qualification}$ + rgb = @Green@; +} +\end{cfa} +As in Section~\ref{s:EnumeratorNameResolution}, opening multiple unscoped enumerations can result in duplicate enumeration names, but \CFA implicit type resolution and explicit qualification/casting handles name resolution. \section{Enumerator Typing} @@ -80,5 +81,5 @@ \begin{cfa} // integral - enum( @char@ ) Currency { Dollar = '$\textdollar$', Euro = '$\texteuro$', Pound = '$\textsterling$' }; + enum( @char@ ) Currency { Dollar = '$\textdollar$', Cent = '$\textcent$', Yen = '$\textyen$', Pound = '$\textsterling$', Euro = 'E' }; enum( @signed char@ ) srgb { Red = -1, Green = 0, Blue = 1 }; enum( @long long int@ ) BigNum { X = 123_456_789_012_345, Y = 345_012_789_456_123 }; @@ -87,5 +88,5 @@ enum( @_Complex@ ) Plane { X = 1.5+3.4i, Y = 7+3i, Z = 0+0.5i }; // pointer - enum( @char *@ ) Names { Fred = "FRED", Mary = "MARY", Jane = "JANE" }; + enum( @const char *@ ) Name { Fred = "FRED", Mary = "MARY", Jane = "JANE" }; int i, j, k; enum( @int *@ ) ptr { I = &i, J = &j, K = &k }; @@ -98,5 +99,6 @@ // aggregate struct Person { char * name; int age, height; }; -@***@enum( @Person@ ) friends { @Liz@ = { "ELIZABETH", 22, 170 }, @Beth@ = Liz, Jon = { "JONATHAN", 35, 190 } }; +@***@enum( @Person@ ) friends { @Liz@ = { "ELIZABETH", 22, 170 }, @Beth@ = Liz, + Jon = { "JONATHAN", 35, 190 } }; \end{cfa} \caption{Enumerator Typing} @@ -140,7 +142,7 @@ \begin{cfa} enum() Mode { O_RDONLY, O_WRONLY, O_CREAT, O_TRUNC, O_APPEND }; -@***@Mode iomode = O_RDONLY; -bool b = iomode == O_RDONLY || iomode < O_APPEND; -int i = iomode; $\C{\color{red}// disallowed}$ +Mode iomode = O_RDONLY; +bool b = iomode == O_RDONLY || iomode < O_APPEND; $\C{// ordering}$ +@***@@int i = iomode;@ $\C{// disallow conversion to int}$ \end{cfa} @@ -149,6 +151,6 @@ If follows from enumerator typing that the enumerator type can be another enumerator. \begin{cfa} -enum( @char@ ) Currency { Dollar = '$\textdollar$', Euro = '$\texteuro$', Pound = '$\textsterling$' }; -enum( @Currency@ ) Europe { Euro = Currency.Euro, Pound = Currency.Pound }; // intersection +enum( @char@ ) Currency { Dollar = '$\textdollar$', Cent = '$\textcent$', Yen = '$\textyen$', Pound = '$\textsterling$', Euro = 'E' }; +enum( Currency ) Europe { Euro = Currency.Euro, Pound = Currency.Pound }; enum( char ) Letter { A = 'A', B = 'B', C = 'C', ..., Z = 'Z' }; enum( @Letter@ ) Greek { Alph = A, Beta = B, ..., Zeta = Z }; // intersection @@ -158,7 +160,7 @@ \begin{cfa} Letter letter = A; -@***@Greak greek = Beta; -letter = Beta; $\C{// allowed, letter == B}$ -greek = A; $\C{\color{red}// disallowed}$ +Greak greek = Beta; +letter = Beta; $\C{// allowed, greek == B}$ +@greek = A;@ $\C{// disallowed}$ \end{cfa} @@ -277,2 +279,46 @@ p(variable_d); // 3 \end{cfa} + + +\section{Planet Example} + +\VRef[Figure]{f:PlanetExample} shows an archetypal enumeration example illustrating all of the \CFA enumeration features. +Enumeration @Planet@ is a typed enumeration of type @MR@. +Each of the planet enumerators is initialized to a specific mass/radius, @MR@, value. +The unnamed enumeration projects the gravitational-constant enumerator @G@. +The program main iterates through the planets computing the weight on each planet for a given earth weight. + +\begin{figure} +\begin{cfa} +struct MR { double mass, radius; }; +enum( MR ) Planet { + // mass radius + MERCURY = { 3.303_E23, 2.4397_E6 }, + VENUS = { 4.869_E24, 6.0518_E6 }, + EARTH = { 5.976_E24, 6.3781_E6 }, + MARS = { 6.421_E23, 3.3972_E6 }, + JUPITER = { 1.898_E27, 7.1492_E7 }, + SATURN = { 5.688_E26, 6.0268_E7 }, + URANUS = { 8.686_E25, 2.5559_E7 }, + NEPTUNE = { 1.024_E26, 2.4746_E7 }, +}; +enum( double ) { G = 6.6743E-11 }; // universal gravitational constant (m3 kg-1 s-2) + +static double surfaceGravity( Planet p ) with( p ) { + return G * mass / ( radius * radius ); +} +static double surfaceWeight( Planet p, double otherMass ) { + return otherMass * surfaceGravity( p ); +} +int main( int argc, char * argv[] ) { + if ( argc != 2 ) exit | "Usage: " | argv[0] | "earth-weight"; + double earthWeight = convert( argv[1] ); + double mass = earthWeight / surfaceGravity( EARTH ); + for ( p; Planet ) { + sout | "Your weight on" | labelE(p) | "is" | surfaceWeight( p, mass ); + } +} +\end{cfa} +\caption{Planet Example} +\label{f:PlanetExample} +\end{figure} Index: doc/theses/jiada_liang_MMath/background.tex =================================================================== --- doc/theses/jiada_liang_MMath/background.tex (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ doc/theses/jiada_liang_MMath/background.tex (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -1,24 +1,69 @@ \chapter{Background} +\lstnewenvironment{clang}[1][]{\lstset{language=[ANSI]C,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} + +\CFA is a backwards-compatible extension of the C programming language. +Therefore, it must support C-style enumerations and any enumeration extensions must be intuitive to C programmers both in syntax and semantics. + +It is common for C programmers to ``believe'' there are three equivalent forms of named constants. +\begin{clang} +#define Mon 0 +static const int Mon = 0; +enum { Mon }; +\end{clang} +\begin{enumerate}[leftmargin=*] +\item +For @#define@, the programmer has to explicitly manage the constant name and value. +Furthermore, these C preprocessor macro names are outside of the C type-system, and hence cannot be overloaded, and can incorrectly change random text in a program. +\item +The same explicit management is true for the @const@ declaration, and the @const@ variable cannot appear in constant-expression locations, like @case@ labels, array dimensions,\footnote{ +C allows variable-length array-declarations (VLA), so this case does work, but it fails in \CC, which does not support VLAs, unless it is \lstinline{g++}.} immediate operands of assembler instructions, and occupy storage. +\begin{clang} +$\$$ nm test.o +0000000000000018 r Mon +\end{clang} +\item +Only the @enum@ form is managed by the compiler, is part of the language type-system, and works in all C constant-expression locations. +\end{enumerate} -\section{C-Style Enum} +\section{C \lstinline{const}} -The C-Style enumeration has the following syntax and semantics. -\begin{cfa} -enum Weekday { Monday, Tuesday, Wednesday, Thursday@ = 10@, Friday, Saturday, Sunday }; -\end{cfa} +As noted, C has the equivalent of Pascal typed @const@ declarations \see{\VRef{s:Pascal}}, with static and dynamic initialization. +\begin{clang} +static const int one = 0 + 1; $\C{// static intialization}$ +static const void * NIL = NULL; +static const double PI = 3.14159; +static const char Plus = '+'; +static const char * Fred = "Fred"; +static const int Mon = 0, Tue = Mon + 1, Wed = Tue + 1, Thu = Wed + 1, Fri = Thu + 1, + Sat = Fri + 1, Sun = Sat + 1; +void foo() { + const int r = random(); $\C{// dynamic intialization}$ + int sa[Sun]; $\C{// VLA, local scope only}$ +} +\end{clang} +Statically initialized identifiers may appear in any constant-expression context, \eg @case@. +Dynamically initialized identifiers may appear as array dimensions in @g++@, which allows variable-sized arrays. + + +\section{C Enumeration} + +The C enumeration has the following syntax and semantics. +\begin{clang} +enum Weekday { Mon, Tue, Wed, Thu@ = 10@, Fri, Sat, Sun, }; +\end{clang} Enumerators without an explicitly designated constant value are \Newterm{auto-initialized} by the compiler: from left to right, starting at zero or the next explicitly initialized constant, incrementing by @1@. -For example, @Monday@ to @Wednesday@ are implicitly assigned with constants @0@--@2@, @Thursday@ is explicitly set to constant @10@, and @Friday@ to @Sunday@ are implicitly assigned with constants @11@--@13@. +For example, @Mon@ to @Wed@ are implicitly assigned with constants @0@--@2@, @Thu@ is explicitly set to constant @10@, and @Fri@ to @Sun@ are implicitly assigned with constants @11@--@13@. Initialization may occur in any order. -\begin{cfa} -enum Weekday { Thursday@ = 10@, Friday, Saturday, Sunday, Monday@ = 0@, Tuesday, Wednesday }; -\end{cfa} +\begin{clang} +enum Weekday { Thu@ = 10@, Fri, Sat, Sun, Mon@ = 0@, Tue, Wed }; +\end{clang} Note, the comma in the enumerator list can be a terminator or a separator, allowing the list to end with a dangling comma. -\begin{cfa} +\begin{clang} enum Weekday { - Thursday = 10, Friday, Saturday, Sunday, - Monday = 0, Tuesday, Wednesday@,@ // terminating comma + Thu = 10, Fri, Sat, Sun, + Mon = 0, Tue, Wed@,@ // terminating comma }; -\end{cfa} +\end{clang} This feature allow enumerator lines to be interchanged without moving a comma.\footnote{ A terminating comma appears in other C syntax, \eg the initializer list.} @@ -28,25 +73,13 @@ In practice, since integral constants are used, which have type @int@ (unless qualified with a size suffix), C uses @int@ as the underlying type for enumeration variables. Finally, there is an implicit bidirectional conversion between an enumeration and its integral type. -\begin{cfa} +\begin{clang} { enum Weekday { /* as above */ }; $\C{// enumerators implicitly projected into local scope}$ - Weekday weekday = Monday; $\C{// weekday == 0}$ - weekday = Friday; $\C{// weekday == 11}$ - int i = Sunday; $\C{// implicit conversion to int, i == 13}$ + Weekday weekday = Mon; $\C{// weekday == 0}$ + weekday = Fri; $\C{// weekday == 11}$ + int i = Sun; $\C{// implicit conversion to int, i == 13}$ weekday = 10000; $\C{// UNDEFINED! implicit conversion to Weekday}$ } -int j = Wednesday; $\C{// ERROR! Wednesday is not declared in this scope}$ -\end{cfa} +int j = Wed; $\C{// ERROR! Wed is not declared in this scope}$ +\end{clang} The implicit conversion from @int@ to an enumeration type is an unnecessary source of error. - -It is common for C programmers to ``believe'' there are 3 equivalent forms of constant enumeration. -\begin{cfa} -#define Monday 0 -static const int Monday = 0; -enum { Monday }; -\end{cfa} -For @#define@, the programmer has to play compiler and explicitly manage the enumeration values; -furthermore, these are independent constants outside of any language type mechanism. -The same explicit management is true for @const@ declarations, and the @const@ variable cannot appear in constant-expression locations, like @case@ labels, array dimensions,\footnote{ -C allows variable-length array-declarations (VLA), so this case does work, but it fails in \CC, which does not support VLAs, unless it is \lstinline{g++}.} and immediate operands of assembler instructions. -Only the @enum@ form is managed by the compiler, is part of the language type-system, and works in all C constant-expression locations. Index: doc/theses/jiada_liang_MMath/implementation.tex =================================================================== --- doc/theses/jiada_liang_MMath/implementation.tex (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ doc/theses/jiada_liang_MMath/implementation.tex (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -548,5 +548,5 @@ \begin{cfa} enum(int) Weekday { - Monday=10, Tuesday, ... + Mon = 10, Tue, ... }; Index: doc/theses/jiada_liang_MMath/intro.tex =================================================================== --- doc/theses/jiada_liang_MMath/intro.tex (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ doc/theses/jiada_liang_MMath/intro.tex (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -1,30 +1,180 @@ \chapter{Introduction} -Naming values is a common practice in mathematics and engineering, \eg $\pi$, $\tau$ (2$\pi$), $\phi$ (golden ratio), MHz (1E6), etc. -Naming is also commonly used to represent many other numerical phenomenon, such as days of the week, months of a year, floors of a building (basement), specific times (noon, New Years). -Many programming languages capture this important software engineering capability through a mechanism called an \Newterm{enumeration}. -An enumeration is similar to other programming-language types by providing a set of constrained values, but adds the ability to name \emph{all} the values in its set. -Note, all enumeration names must be unique but different names can represent the same value (eight note, quaver), which are synonyms. +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. -Specifically, an enumerated type restricts its values to a fixed set of named constants. -While all types are restricted to a fixed set of values because of the underlying von Neumann architecture, and hence, to a corresponding set of constants, \eg @3@, @3.5@, @3.5+2.1i@, @'c'@, @"abc"@, etc., these values are not named, other than the programming-language supplied constant names. +\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.}. -Fundamentally, all enumeration systems have an \Newterm{enumeration} type with an associated set of \Newterm{enumerator} names. -An enumeration has three universal attributes, \Newterm{position}, \Newterm{label}, and \Newterm{value}, as shown by this representative enumeration, where position and value can be different. +Secondary names can form an (ordered) set, \eg days of the week, months of a year, floors of a building (basement, ground, 1st), colours in a rainbow, \etc. +Many programming languages capture these groupings through a mechanism called an \Newterm{enumeration}. +\begin{quote} +enumerate (verb, transitive). +To count, ascertain the number of; +\emph{more +usually, to mention (a number of things or persons) separately, as if for the +purpose of counting}; +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 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. +\begin{cfa}[morekeywords={in}] +for ( cursor in Mon, Tue, Wed, Thu, Fri, Sat, Sun } ... $\C[3.75in]{// week}$ +for ( cursor in Mon, Tue, Wed, Thu, Fri } ... $\C{// weekday}$ +for ( cursor in Thu, Fri } ... $\C{// weekend}$ +for ( cursor in Mon, Wed, Fri, Sun } ... $\C{// every second day of week}\CRT$ +\end{cfa} +This independence from internal representation allows multiple names to have the same representation (eight note, quaver), giving synonyms. +A set can have a partial or total ordering, making it possible to compare set elements, \eg Monday is before Friday and Friday is after. +Ordering allows iterating among the enumeration set using relational operators and advancement, \eg +\begin{cfa} +for ( cursor = Monday; cursor @<=@ Friday; cursor = @succ@( cursor ) ) ... +\end{cfa} +Here the internal representations for the secondary names are \emph{generated} rather than listing a subset of names. + + +\section{Terminology} + +The term \Newterm{enumeration} defines the set of secondary names, and the term \Newterm{enumerator} represents an arbitrary secondary name. +As well, an enumerated type has three fundamental properties, \Newterm{label}, \Newterm{order}, and \Newterm{value}. \begin{cquote} -\small\sf\setlength{\tabcolsep}{3pt} -\begin{tabular}{rccccccccccc} -\it\color{red}enumeration & \multicolumn{7}{c}{\it\color{red}enumerators} \\ -$\downarrow$\hspace*{25pt} & \multicolumn{7}{c}{$\downarrow$} \\ -@enum@ Weekday \{ & Monday, & Tuesday, & Wednesday, & Thursday,& Friday, & Saturday, & Sunday \}; \\ -\it\color{red}position & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ -\it\color{red}label & Monday & Tuesday & Wednesday & Thursday & Friday & Saturday & Sunday \\ -\it\color{red}value & 0 & 1 & 2 & 3 & 4 & 5 & 6 +\sf\setlength{\tabcolsep}{3pt} +\begin{tabular}{rcccccccr} +\it\color{red}enumeration & \multicolumn{8}{c}{\it\color{red}enumerators} \\ +$\downarrow$\hspace*{25pt} & \multicolumn{8}{c}{$\downarrow$} \\ +@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 & \\ +\it\color{red}value & 0 & 1 & 2 & 3 & 4 & 5 & 42 & \end{tabular} \end{cquote} -Here, the \Newterm{enumeration} @Weekday@ defines the ordered \Newterm{enumerator}s @Monday@, @Tuesday@, @Wednesday@, @Thursday@, @Friday@, @Saturday@ and @Sunday@. -By convention, the successor of @Tuesday@ is @Monday@ and the predecessor of @Tuesday@ is @Wednesday@, independent of the associated enumerator constant values. -Because an enumerator is a constant, it cannot appear in a mutable context, \eg @Mon = Sun@ is meaningless, and an enumerator has no address, it is an \Newterm{rvalue}\footnote{ -The term rvalue defines an expression that can only appear on the right-hand side of an assignment.}. +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. + +Specifying complex ordering is possible: +\begin{cfa} +enum E1 { $\color{red}[\(_1\)$ {A, B}, $\color{blue}[\(_2\)$ C $\color{red}]\(_1\)$, {D, E} $\color{blue}]\(_2\)$ }; $\C{// overlapping square brackets}$ +enum E2 { {A, {B, C} }, { {D, E}, F }; $\C{// nesting}$ +\end{cfa} +For @E1@, there is the partial ordering among @A@, @B@ and @C@, and @C@, @D@ and @E@, but not among @A@, @B@ and @D@, @E@. +For @E2@, there is the total ordering @A@ $<$ @{B, C}@ $<$ @{D, E}@ $<$ @F@. +Only flat total-ordering among enumerators is considered in this work. + + +\section{Motivation} + +Some programming languages only provide secondary renaming, which can be simulated by an enumeration without ordering. +\begin{cfa} +const Size = 20, Pi = 3.14159; +enum { Size = 20, Pi = 3.14159 }; // unnamed enumeration $\(\Rightarrow\)$ no ordering +\end{cfa} +In both cases, it is possible to compare the secondary names, \eg @Size < Pi@, if that is meaningful; +however, without an enumeration type-name, it is impossible to create an iterator cursor. + +Secondary renaming can similate an enumeration, but with extra effort. +\begin{cfa} +const Mon = 1, Tue = 2, Wed = 3, Thu = 4, Fri = 5, Sat = 6, Sun = 7; +\end{cfa} +Furthermore, reordering the enumerators requires manual renumbering. +\begin{cfa} +const Sun = 1, Mon = 2, Tue = 3, Wed = 4, Thu = 5, Fri = 6, Sat = 7; +\end{cfa} +Finally, there is no common type to create a type-checked instance or iterator cursor. +Hence, there is only a weak equivalence between secondary naming and enumerations, justifying the enumeration type in a programming language. + +A variant (algebraic) type is often promoted as a kind of enumeration, \ie a varient type can simulate an enumeration. +A variant type is a tagged-union, where the possible types may be heterogeneous. +\begin{cfa} +@variant@ Variant { + @int tag;@ // optional/implicit: 0 => int, 1 => double, 2 => S + @union {@ // implicit + case int i; + case double d; + case struct S { int i, j; } s; + @};@ +}; +\end{cfa} +Crucially, the union implies instance storage is shared by all of the variant types. +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; +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. + +The tag can be implicitly set by the compiler on assignment, or explicitly set by the program\-mer. +Type pattern-matching is then used to dynamically test the tag and branch to a section of code to safely manipulate the value, \eg: +\begin{cfa}[morekeywords={match}] +Variant v = 3; // implicitly set tag to 0 +@match@( v ) { // know the type or test the tag + case int { /* only access i field in v */ } + case double { /* only access d field in v */ } + case S { /* only access s field in v */ } +} +\end{cfa} +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 \emph{re-purposed} for either ordering or value and the variant types are omitted. +\begin{cfa} +variant Weekday { + int tag; // implicit 0 => Mon, ..., 6 => Sun + @case Mon;@ // no type + ... + @case Sun;@ +}; +\end{cfa} +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} +Week week = Mon; +if ( @dynamic_cast(Mon)@week ) ... // test tag == Mon +\end{cfa} +While enumerating among tag names is possible: +\begin{cfa}[morekeywords={in}] +for ( cursor in Mon, Wed, Fri, Sun ) ... +\end{cfa} +ordering for iteration would require a \emph{magic} extension, such as a special @enum@ variant, because it has no meaning for a regular variant, \ie @int@ < @double@. + +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}[morekeywords={match}] +for ( cursor = Mon; cursor <= Fri; cursor = succ( cursor) ) { + match( cursor ) { + case Mon { /* access special type for Mon */ } + ... + case Fri { /* access special type for Fri */ } + default + } +} +\end{cfa} +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. + +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. + \section{Contributions} + +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 runtime implementation. + +\begin{enumerate} +\item +overloading +\item +scoping +\item +typing +\item +subset +\item +inheritance +\end{enumerate} Index: doc/theses/jiada_liang_MMath/relatedwork.tex =================================================================== --- doc/theses/jiada_liang_MMath/relatedwork.tex (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ doc/theses/jiada_liang_MMath/relatedwork.tex (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -2,4 +2,5 @@ \label{s:RelatedWork} +\begin{comment} An algebraic data type (ADT) can be viewed as a recursive sum of product types. A sum type lists values as members. @@ -15,4 +16,5 @@ Enumerated types are a special case of product/sum types with non-mutable fields, \ie initialized (constructed) once at the type's declaration, possible restricted to compile-time initialization. Values of algebraic types are access by subscripting, field qualification, or type (pattern) matching. +\end{comment} Enumeration types exist in many popular programming languages, both past and present, \eg Pascal~\cite{Pascal}, Ada~\cite{Ada}, \Csharp~\cite{Csharp}, OCaml~\cite{OCaml} \CC, Go~\cite{Go}, Java~\cite{Java}, Modula-3~\cite{Modula-3}, Rust~\cite{Rust}, Swift~\cite{Swift}, Python~\cite{Python}. @@ -20,4 +22,5 @@ \section{Pascal} +\label{s:Pascal} \lstnewenvironment{pascal}[1][]{\lstset{language=pascal,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} @@ -27,5 +30,5 @@ PI = 3.14159; Plus = '+'; Fred = 'Fred'; \end{pascal} -Here, there is no enumeration because there is no specific type (pseudo enumeration). +This mechanism is not an enumeration because there is no specific type (pseudo enumeration). Hence, there is no notion of a (possibly ordered) set, modulo the \lstinline[language=pascal]{set of} type. The type of each constant name (enumerator) is inferred from the constant-expression type. @@ -81,16 +84,16 @@ with Ada.Text_IO; use Ada.Text_IO; procedure test is - type RGB is ( @Red@, Green, Blue ); - type Traffic_Light is ( @Red@, Yellow, Green ); -- overload - procedure @Red@( Colour : RGB ) is begin -- overload - Put_Line( "Colour is " & RGB'Image( Colour ) ); - end Red; - procedure @Red@( TL : Traffic_Light ) is begin -- overload - Put_Line( "Light is " & Traffic_Light'Image( TL ) ); - end Red; + type RGB is ( @Red@, Green, Blue ); + type Traffic_Light is ( @Red@, Yellow, Green ); -- overload + procedure @Red@( Colour : RGB ) is begin -- overload + Put_Line( "Colour is " & RGB'Image( Colour ) ); + end Red; + procedure @Red@( TL : Traffic_Light ) is begin -- overload + Put_Line( "Light is " & Traffic_Light'Image( TL ) ); + end Red; begin - @Red@( Blue ); -- RGB - @Red@( Yellow ); -- Traffic_Light - @Red@( @RGB'(Red)@ ); -- ambiguous without cast + @Red@( Blue ); -- RGB + @Red@( Yellow ); -- Traffic_Light + @Red@( @RGB'(Red)@ ); -- ambiguous without cast end test; \end{ada} @@ -224,6 +227,27 @@ \lstnewenvironment{c++}[1][]{\lstset{language=[GNU]C++,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} -\CC is largely backwards compatible with C, so it inherited C's enumerations. -However, the following non-backwards compatible changes have been made. +\CC has the equivalent of Pascal typed @const@ declarations \see{\VRef{s:Pascal}}, with static and dynamic initialization. +\begin{c++} +const auto one = 0 + 1; $\C{// static intialization}$ +const auto NULL = nullptr; +const auto PI = 3.14159; +const auto Plus = '+'; +const auto Fred = "Fred"; +const auto Mon = 0, Tue = Mon + 1, Wed = Tue + 1, Thu = Wed + 1, Fri = Thu + 1, + Sat = Fri + 1, Sun = Sat + 1; +int sa[Sun]; +const auto r = random(); $\C{// dynamic intialization}$ +int da[r]; $\C{// VLA}$ +\end{c++} +Statically initialized identifiers may appear in any constant-expression context, \eg @case@. +Dynamically intialized identifiers may appear as array dimensions in @g++@, which allows variable-sized arrays. +Interestingly, global \CC @const@ declarations are implicitly marked @static@ (@r@ rather than @R@). +\begin{c++} +$\$$ nm test.o +0000000000000018 @r@ Mon +\end{c++} + +\CC enumeration is largely backwards compatible with C, so it inherited C's enumerations. +However, the following non-backwards compatible changes are made. \begin{cquote} @@ -423,5 +447,5 @@ \begin{Go} const ( Mon = iota; Tue; Wed; // 0, 1, 2 - @Thu = 10@; Fri; Sat; Sun ) // 10, 10, 10, 10 + @Thu = 10@; Fri; Sat; Sun ) // 10, 10, 10, 10 \end{Go} Auto-incrementing can be restarted with an expression containing \emph{one} \lstinline[language=Go]{iota}. @@ -429,5 +453,5 @@ const ( V1 = iota; V2; @V3 = 7;@ V4 = @iota@; V5 ) // 0 1 7 3 4 const ( Mon = iota; Tue; Wed; // 0, 1, 2 - @Thu = 10;@ Fri = @iota - Wed + Thu - 1@; Sat; Sun ) // 10, 11, 12, 13 + @Thu = 10;@ Fri = @iota - Wed + Thu - 1@; Sat; Sun ) // 10, 11, 12, 13 \end{Go} Note, \lstinline[language=Go]{iota} is advanced for an explicitly initialized enumerator, like the underscore @_@ identifier. @@ -584,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} @@ -1200,61 +1013,41 @@ \lstnewenvironment{python}[1][]{\lstset{language=Python,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} -An @Enum@ is a set of symbolic names bound to unique values. -They are similar to global variables, but they offer a more useful @repr()@, grouping, type-safety, and a few other features. - -They are most useful when you have a variable that can take one of a limited selection of values. For example, the days of the week: -\begin{python} ->>> from enum import Enum ->>> class Weekday(Enum): -... MONDAY = 1 -... TUESDAY = 2 -... WEDNESDAY = 3 -... THURSDAY = 4 -... FRIDAY = 5 -... SATURDAY = 6 -... SUNDAY = 7 -\end{python} -Or perhaps the RGB primary colors: -\begin{python} ->>> from enum import Enum ->>> class Color(Enum): -... RED = 1 -... GREEN = 2 -... BLUE = 3 -\end{python} -As you can see, creating an @Enum@ is as simple as writing a class that inherits from @Enum@ itself. - -Note: Case of Enum Members - -Because Enums are used to represent constants, and to help avoid issues with name clashes between mixin-class methods/attributes and enum names, we strongly recommend using @UPPER_CASE@ names for members, and will be using that style in our examples. +A Python enumeration is a set of symbolic names bound to \emph{unique} values. +They are similar to global variables, but offer a more useful @repr()@, grouping, type-safety, and additional features. +Enumerations inherits from the @Enum@ class, \eg: +\begin{python} +class Weekday(@Enum@): Mon = 1; Tue = 2; Wed = 3; Thu = 4; Fri = 5; Sat = 6; Sun = 7 +class RGB(@Enum@): Red = 1; Green = 2; Blue = 3 +\end{python} Depending on the nature of the enum a member's value may or may not be important, but either way that value can be used to get the corresponding member: \begin{python} ->>> Weekday(3) - +print( repr( Weekday( 3 ) ) ) + \end{python} As you can see, the @repr()@ of a member shows the enum name, the member name, and the value. The @str()@ of a member shows only the enum name and member name: \begin{python} -print(Weekday.THURSDAY) -Weekday.THURSDAY +print( str( Weekday.Thu ), Weekday.Thu ) +Weekday.Thu Weekday.Thu \end{python} The type of an enumeration member is the enum it belongs to: \begin{python} ->>> type(Weekday.MONDAY) +print( type( Weekday.Thu ) ) -isinstance(Weekday.FRIDAY, Weekday) +print( isinstance(Weekday.Fri, Weekday) ) True \end{python} Enum members have an attribute that contains just their name: \begin{python} ->>> print(Weekday.TUESDAY.name) +print(Weekday.TUESDAY.name) TUESDAY \end{python} Likewise, they have an attribute for their value: \begin{python} ->>> Weekday.WEDNESDAY.value +Weekday.WEDNESDAY.value 3 \end{python} + Unlike many languages that treat enumerations solely as name/value pairs, Python @Enum@s can have behavior added. For example, @datetime.date@ has two methods for returning the weekday: @weekday()@ and @isoweekday()@. @@ -1262,22 +1055,8 @@ Rather than keep track of that ourselves we can add a method to the @Weekday@ enum to extract the day from the date instance and return the matching enum member: \begin{python} +class Weekday(Enum): Mon = 1; Tue = 2; Wed = 3; Thu = 10; Fri = 15; Sat = 16; Sun = 17 $@$classmethod def from_date(cls, date): - return cls(date.isoweekday()) -\end{python} -The complete Weekday enum now looks like this: -\begin{python} ->>> class Weekday(Enum): -... MONDAY = 1 -... TUESDAY = 2 -... WEDNESDAY = 3 -... THURSDAY = 4 -... FRIDAY = 5 -... SATURDAY = 6 -... SUNDAY = 7 -... # -... $@$classmethod -... def from_date(cls, date): -... return cls(date.isoweekday()) + return cls(date.isoweekday()) \end{python} Now we can find out what today is! Observe: @@ -1291,32 +1070,18 @@ This Weekday enum is great if our variable only needs one day, but what if we need several? Maybe we're writing a function to plot chores during a week, and don't want to use a @list@ -- we could use a different type of @Enum@: \begin{python} ->>> from enum import Flag ->>> class Weekday(Flag): -... MONDAY = 1 -... TUESDAY = 2 -... WEDNESDAY = 4 -... THURSDAY = 8 -... FRIDAY = 16 -... SATURDAY = 32 -... SUNDAY = 64 +from enum import Flag +class WeekdayF(@Flag@): Mon = @1@; Tue = @2@; Wed = @4@; Thu = @8@; Fri = @16@; Sat = @32@; Sun = @64@ \end{python} We've changed two things: we're inherited from @Flag@, and the values are all powers of 2. -Just like the original @Weekday@ enum above, we can have a single selection: -\begin{python} ->>> first_week_day = Weekday.MONDAY ->>> first_week_day - -\end{python} -But @Flag@ also allows us to combine several members into a single variable: -\begin{python} ->>> weekend = Weekday.SATURDAY | Weekday.SUNDAY ->>> weekend - +@Flag@ allows combining several members into a single variable: +\begin{python} +print( repr(WeekdayF.Sat | WeekdayF.Sun) ) + \end{python} You can even iterate over a @Flag@ variable: \begin{python} ->>> for day in weekend: -... print(day) +for day in weekend: + print(day) Weekday.SATURDAY Weekday.SUNDAY @@ -1382,15 +1147,5 @@ \subsection{Duplicating enum members and values} -Having two enum members with the same name is invalid: -\begin{python} ->>> class Shape(Enum): -... SQUARE = 2 -... SQUARE = 3 -... -Traceback (most recent call last): -... -TypeError: 'SQUARE' already defined as 2 -\end{python} -However, an enum member can have other names associated with it. +An enum member can have other names associated with it. Given two entries @A@ and @B@ with the same value (and @A@ defined first), @B@ is an alias for the member @A@. By-value lookup of the value of @A@ will return the member @A@. @@ -1398,10 +1153,5 @@ By-name lookup of @B@ will also return the member @A@: \begin{python} ->>> class Shape(Enum): -... SQUARE = 2 -... DIAMOND = 1 -... CIRCLE = 3 -... ALIAS_FOR_SQUARE = 2 -... +class Shape(Enum): SQUARE = 2; DIAMOND = 1; CIRCLE = 3; ALIAS_FOR_SQUARE = 2 >>> Shape.SQUARE @@ -1419,14 +1169,7 @@ When this behavior isn't desired, you can use the @unique()@ decorator: \begin{python} ->>> from enum import Enum, unique ->>> $@$unique -... class Mistake(Enum): -... ONE = 1 -... TWO = 2 -... THREE = 3 -... FOUR = 3 -... -Traceback (most recent call last): -... +from enum import Enum, unique +$@$unique +class DupVal(Enum): ONE = 1; TWO = 2; THREE = 3; FOUR = 3 ValueError: duplicate values found in : FOUR -> THREE \end{python} @@ -1436,14 +1179,9 @@ If the exact value is unimportant you can use @auto@: \begin{python} ->>> from enum import Enum, auto ->>> class Color(Enum): -... RED = auto() -... BLUE = auto() -... GREEN = auto() -... ->>> [member.value for member in Color] -[1, 2, 3] -\end{python} -The values are chosen by \_generate\_next\_value\_(), which can be overridden: +from enum import Enum, auto +class RGBa(Enum): RED = auto(); BLUE = auto(); GREEN = auto() +\end{python} +(Like Golang @iota@.) +The values are chosen by @_generate_next_value_()@, which can be overridden: \begin{python} >>> class AutoName(Enum): @@ -1582,5 +1320,5 @@ \begin{python} class EnumName([mix-in, ...,] [data-type,] base-enum): - pass + pass \end{python} Also, subclassing an enumeration is allowed only if the enumeration does not define any members. @@ -1699,12 +1437,12 @@ \begin{python} Enum( - value='NewEnumName', - names=<...>, - *, - module='...', - qualname='...', - type=, - start=1, - ) + value='NewEnumName', + names=<...>, + *, + module='...', + qualname='...', + type=, + start=1, + ) \end{python} \begin{itemize} @@ -1935,5 +1673,5 @@ \begin{python} class IntEnum(int, Enum): - pass + pass \end{python} This demonstrates how similar derived enumerations can be defined; @@ -2070,5 +1808,5 @@ \begin{python} def __bool__(self): - return bool(self.value) + return bool(self.value) \end{python} Plain @Enum@ classes always evaluate as @True@. @@ -2414,28 +2152,39 @@ If @__new__()@ or @__init__()@ is defined, the value of the enum member will be passed to those methods: -\begin{python} ->>> class Planet(Enum): -... MERCURY = (3.303e+23, 2.4397e6) -... VENUS = (4.869e+24, 6.0518e6) -... EARTH = (5.976e+24, 6.37814e6) -... MARS = (6.421e+23, 3.3972e6) -... JUPITER = (1.9e+27, 7.1492e7) -... SATURN = (5.688e+26, 6.0268e7) -... URANUS = (8.686e+25, 2.5559e7) -... NEPTUNE = (1.024e+26, 2.4746e7) -... def __init__(self, mass, radius): -... self.mass = mass # in kilograms -... self.radius = radius # in meters -... $\@$property -... def surface_gravity(self): -... # universal gravitational constant (m3 kg-1 s-2) -... G = 6.67300E-11 -... return G * self.mass / (self.radius * self.radius) -... ->>> Planet.EARTH.value -(5.976e+24, 6378140.0) ->>> Planet.EARTH.surface_gravity -9.802652743337129 -\end{python} +\begin{figure} +\begin{python} +from enum import Enum +class Planet(Enum): + MERCURY = ( 3.303E23, 2.4397E6 ) + VENUS = ( 4.869E24, 6.0518E6 ) + EARTH = (5.976E24, 6.37814E6) + MARS = (6.421E23, 3.3972E6) + JUPITER = (1.9E27, 7.1492E7) + SATURN = (5.688E26, 6.0268E7) + URANUS = (8.686E25, 2.5559E7) + NEPTUNE = (1.024E26, 2.4746E7) + def __init__( self, mass, radius ): + self.mass = mass # in kilograms + self.radius = radius # in meters + def surface_gravity( self ): + # universal gravitational constant (m3 kg-1 s-2) + G = 6.67300E-11 + return G * self.mass / (self.radius * self.radius) +for p in Planet: + print( f"{p.name}: {p.value}" ) + +MERCURY: (3.303e+23, 2439700.0) +VENUS: (4.869e+24, 6051800.0) +EARTH: (5.976e+24, 6378140.0) +MARS: (6.421e+23, 3397200.0) +JUPITER: (1.9e+27, 71492000.0) +SATURN: (5.688e+26, 60268000.0) +URANUS: (8.686e+25, 25559000.0) +NEPTUNE: (1.024e+26, 24746000.0) +\end{python} +\caption{Python Planet Example} +\label{f:PythonPlanetExample} +\end{figure} + \subsection{TimePeriod} @@ -2464,4 +2213,6 @@ \section{OCaml} \lstnewenvironment{ocaml}[1][]{\lstset{language=OCaml,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} + +% https://ocaml.org/docs/basic-data-types#enumerated-data-types OCaml provides a variant (union) type, where multiple heterogeneously-typed objects share the same storage. @@ -2553,4 +2304,158 @@ With valediction, - Gregor Richards + + +Date: Thu, 14 Mar 2024 21:45:52 -0400 +Subject: Re: OCaml "enums" do come with ordering +To: "Peter A. Buhr" +From: Gregor Richards + +On 3/14/24 21:30, Peter A. Buhr wrote: +> I've marked 3 places with your name to shows places with enum ordering. +> +> type weekday = Mon | Tue | Wed | Thu | Fri | Sat | Sun +> let day : weekday = Mon +> let take_class( d : weekday ) = +> if d <= Fri then (* Gregor *) +> Printf.printf "weekday\n" +> else if d >= Sat then (* Gregor *) +> Printf.printf "weekend\n"; +> match d with +> Mon | Wed -> Printf.printf "CS442\n" | +> Tue | Thu -> Printf.printf "CS343\n" | +> Fri -> Printf.printf "Tutorial\n" | +> _ -> Printf.printf "Take a break\n" +> +> let _ = take_class( Mon ); take_class( Sat ); +> +> type colour = Red | Green of string | Blue of int * float +> let c = Red +> let _ = match c with Red -> Printf.printf "Red, " +> let c = Green( "abc" ) +> let _ = match c with Green g -> Printf.printf "%s, " g +> let c = Blue( 1, 1.5 ) +> let _ = match c with Blue( i, f ) -> Printf.printf "%d %g\n" i f +> +> let check_colour(c: colour): string = +> if c < Green( "xyz" ) then (* Gregor *) +> Printf.printf "green\n"; +> match c with +> Red -> "Red" | +> Green g -> g | +> Blue(i, f) -> string_of_int i ^ string_of_float f +> let _ = check_colour( Red ); check_colour( Green( "xyz" ) ); +> +> type stringList = Empty | Pair of string * stringList +> let rec len_of_string_list(l: stringList): int = +> match l with +> Empty -> 0 | +> Pair(_ , r) -> 1 + len_of_string_list r +> +> let _ = for i = 1 to 10 do +> Printf.printf "%d, " i +> done +> +> (* Local Variables: *) +> (* tab-width: 4 *) +> (* compile-command: "ocaml test.ml" *) +> (* End: *) + +My functional-language familiarity is far more with Haskell than OCaml. I +mostly view OCaml through a lens of "it's Haskell but with cheating". Haskell +"enums" (ADTs) aren't ordered unless you specifically and manually put them in +the Ord typeclass by defining the comparators. Apparently, OCaml has some +other rule, which I would guess is something like "sort by tag then by order of +parameter". Having a default behavior for comparators is *bizarre*; my guess +would be that it gained this behavior in its flirtation with object +orientation, but that's just a guess (and irrelevant). + +This gives a total order, but not enumerability (which would still be +effectively impossible or even meaningless since enums are just a special case +of ADTs). + +With valediction, + - Gregor Richards + +Date: Wed, 20 Mar 2024 18:16:44 -0400 +Subject: Re: +To: "Peter A. Buhr" +From: Gregor Richards + + +On 3/20/24 17:26, Peter A. Buhr wrote: +> Gregor, everyone at this end would like a definition of "enumerability". Can +> you formulate one? + +According to the OED (emphasis added to the meaning I'm after): + +enumerate (verb, transitive). To count, ascertain the number of; **more +usually, to mention (a number of things or persons) separately, as if for the +purpose of counting**; to specify as in a list or catalogue. + +With C enums, if you know the lowest and highest value, you can simply loop +over them in a for loop (this is, of course, why so many enums come with an +ENUM_WHATEVER_LAST value). But, I would be hesitant to use the word "loop" to +describe enumerability, since in functional languages, you would recurse for +such a purpose. + +In Haskell, in order to do something with every member of an "enumeration", you +would have to explicitly list them all. The type system will help a bit since +it knows if you haven't listed them all, but you would have to statically have +every element in the enumeration. If somebody added new elements to the +enumeration later, your code to enumerate over them would no longer work +correctly, because you can't simply say "for each member of this enumeration do +X". In Haskell that's because there aren't actually enumerations; what they use +as enumerations are a degenerate form of algebraic datatypes, and ADTs are +certainly not enumerable. In OCaml, you've demonstrated that they impose +comparability, but I would still assume that you can't make a loop over every +member of an enumeration. (But, who knows!) + +Since that's literally what "enumerate" means, it seems like a rather important +property for enumerations to have ;) + +With valediction, + - Gregor Richards + + +From: Andrew James Beach +To: Gregor Richards , Peter Buhr +CC: Michael Leslie Brooks , Fangren Yu , + Jiada Liang +Subject: Re: Re: +Date: Thu, 21 Mar 2024 14:26:36 +0000 + +Does this mean that not all enum declarations in C create enumerations? If you +declare an enumeration like: + +enum Example { + Label, + Name = 10, + Tag = 3, +}; + +I don't think there is any way to enumerate (iterate, loop, recurse) over these +values without listing all of them. + + +Date: Thu, 21 Mar 2024 10:31:49 -0400 +Subject: Re: +To: Andrew James Beach , Peter Buhr +CC: Michael Leslie Brooks , Fangren Yu , + Jiada Liang +From: Gregor Richards + +I consider this conclusion reasonable. C enums can be nothing more than const +ints, and if used in that way, I personally wouldn't consider them as +enumerations in any meaningful sense, particularly since the type checker +essentially does nothing for you there. Then they're a way of writing consts +repeatedly with some textual indicator that these definitions are related; more +namespace, less enum. + +When somebody writes bitfield members as an enum, is that *really* an +enumeration, or just a use of the syntax for enums to keep related definitions +together? + +With valediction, + - Gregor Richards \end{comment} @@ -2558,15 +2463,47 @@ \section{Comparison} -\begin{tabular}{r|ccccccccc} -feat. / lang. & Pascal & Ada & \Csharp & OCaml & Java & Modula-3 & Rust & Swift & Python \\ +\VRef[Table]{t:FeatureLanguageComparison} shows a comparison of enumeration features and programming languages. +The features are high level and may not capture nuances within a particular language +The @const@ feature is simple macros substitution and not a typed enumeration. + +\begin{table} +\caption{Enumeration Feature / Language Comparison} +\label{t:FeatureLanguageComparison} +\small +\setlength{\tabcolsep}{3pt} +\newcommand{\CM}{\checkmark} +\begin{tabular}{r|c|c|c|c|c|c|c|c|c|c|c|c|c} + &Pascal & Ada &\Csharp& OCaml & Java &Modula-3&Golang& Rust & Swift & Python& C & \CC & \CFA \\ \hline -pure & & & & & & & & & \\ -ordered & & & & & & & & & \\ -setable & & & & & & & & & \\ -auto-init & & & & & & & & & \\ -scoped & & & & & & & & & \\ -typed & & & & & & & & & \\ -switch & & & & & & & & & \\ -loop & & & & & & & & & \\ -array & & & & & & & & & \\ +@const@ & \CM & & & & & & \CM & & & & & \CM & \\ +\hline +\hline +pure & & & & & & & & & & & & & \CM \\ +\hline +typed & & & & & & & & & & & @int@ & integral & @T@ \\ +\hline +safe & & & & & & & & & & & & \CM & \CM \\ +\hline +ordered & & & & & & & & & & & \CM & \CM & \CM \\ +\hline +dup. values & & & & & & & & & & alias & \CM & \CM & \CM \\ +\hline +setable & & & & & & & & & & & \CM & \CM & \CM \\ +\hline +auto-init & & & & & & & & & & & \CM & \CM & \CM \\ +\hline +(un)scoped & & & & & & & & & & & U & U/S & U/S \\ +\hline +overload & & \CM & & & & & & & & & & \CM & \CM \\ +\hline +switch & & & & & & & & & & & \CM & \CM & \CM \\ +\hline +loop & & & & & & & & & & & & & \CM \\ +\hline +array & & & & & & & & & & & \CM & & \CM \\ +\hline +subtype & & & & & & & & & & & & & \CM \\ +\hline +inheritance & & & & & & & & & & & & & \CM \\ \end{tabular} +\end{table} Index: doc/theses/mike_brooks_MMath/array.tex =================================================================== --- doc/theses/mike_brooks_MMath/array.tex (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ doc/theses/mike_brooks_MMath/array.tex (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -510,2 +510,67 @@ \subsection{Retire pointer arithmetic} + + +\section{\CFA} + +XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX \\ +moved from background chapter \\ +XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX \\ + +Traditionally, fixing C meant leaving the C-ism alone, while providing a better alternative beside it. +(For later: That's what I offer with array.hfa, but in the future-work vision for arrays, the fix includes helping programmers stop accidentally using a broken C-ism.) + +\subsection{\CFA features interacting with arrays} + +Prior work on \CFA included making C arrays, as used in C code from the wild, +work, if this code is fed into @cfacc@. +The quality of this this treatment was fine, with no more or fewer bugs than is typical. + +More mixed results arose with feeding these ``C'' arrays into preexisting \CFA features. + +A notable success was with the \CFA @alloc@ function, +which type information associated with a polymorphic return type +replaces @malloc@'s use of programmer-supplied size information. +\begin{cfa} +// C, library +void * malloc( size_t ); +// C, user +struct tm * el1 = malloc( sizeof(struct tm) ); +struct tm * ar1 = malloc( 10 * sizeof(struct tm) ); + +// CFA, library +forall( T * ) T * alloc(); +// CFA, user +tm * el2 = alloc(); +tm (*ar2)[10] = alloc(); +\end{cfa} +The alloc polymorphic return compiles into a hidden parameter, which receives a compiler-generated argument. +This compiler's argument generation uses type information from the left-hand side of the initialization to obtain the intended type. +Using a compiler-produced value eliminates an opportunity for user error. + +TODO: fix in following: even the alloc call gives bad code gen: verify it was always this way; walk back the wording about things just working here; assignment (rebind) seems to offer workaround, as in bkgd-cfa-arrayinteract.cfa + +Bringing in another \CFA feature, reference types, both resolves a sore spot of the last example, and gives a first example of an array-interaction bug. +In the last example, the choice of ``pointer to array'' @ar2@ breaks a parallel with @ar1@. +They are not subscripted in the same way. +\begin{cfa} +ar1[5]; +(*ar2)[5]; +\end{cfa} +Using ``reference to array'' works at resolving this issue. TODO: discuss connection with Doug-Lea \CC proposal. +\begin{cfa} +tm (&ar3)[10] = *alloc(); +ar3[5]; +\end{cfa} +The implicit size communication to @alloc@ still works in the same ways as for @ar2@. + +Using proper array types (@ar2@ and @ar3@) addresses a concern about using raw element pointers (@ar1@), albeit a theoretical one. +TODO xref C standard does not claim that @ar1@ may be subscripted, +because no stage of interpreting the construction of @ar1@ has it be that ``there is an \emph{array object} here.'' +But both @*ar2@ and the referent of @ar3@ are the results of \emph{typed} @alloc@ calls, +where the type requested is an array, making the result, much more obviously, an array object. + +The ``reference to array'' type has its sore spots too. +TODO see also @dimexpr-match-c/REFPARAM_CALL@ (under @TRY_BUG_1@) + +TODO: I fixed a bug associated with using an array as a T. I think. Did I really? What was the bug? Index: doc/theses/mike_brooks_MMath/background.tex =================================================================== --- doc/theses/mike_brooks_MMath/background.tex (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ doc/theses/mike_brooks_MMath/background.tex (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -1,75 +1,8 @@ \chapter{Background} -This chapter states facts about the prior work, upon which my contributions build. -Each receives a justification of the extent to which its statement is phrased to provoke controversy or surprise. - -\section{C} - -\subsection{Common knowledge} - -The reader is assumed to have used C or \CC for the coursework of at least four university-level courses, or have equivalent experience. -The current discussion introduces facts, unaware of which, such a functioning novice may be operating. - -% TODO: decide if I'm also claiming this collection of facts, and test-oriented presentation is a contribution; if so, deal with (not) arguing for its originality - -\subsection{Convention: C is more touchable than its standard} - -When it comes to explaining how C works, I like illustrating definite program semantics. -I prefer doing so, over a quoting manual's suggested programmer's intuition, or showing how some compiler writers chose to model their problem. -To illustrate definite program semantics, I devise a program, whose behaviour exercises the point at issue, and I show its behaviour. - -This behaviour is typically one of -\begin{itemize} - \item my statement that the compiler accepts or rejects the program - \item the program's printed output, which I show - \item my implied assurance that its assertions do not fail when run -\end{itemize} - -The compiler whose program semantics is shown is -\begin{cfa} -$ gcc --version -gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0 -\end{cfa} -running on Architecture @x86_64@, with the same environment targeted. - -Unless explicit discussion ensues about differences among compilers or with (versions of) the standard, it is further implied that there exists a second version of GCC and some version of Clang, running on and for the same platform, that give substantially similar behaviour. -In this case, I do not argue that my sample of major Linux compilers is doing the right thing with respect to the C standard. - - -\subsection{C reports many ill-typed expressions as warnings} - -These attempts to assign @y@ to @x@ and vice-versa are obviously ill-typed. -\lstinput{12-15}{bkgd-c-tyerr.c} -with warnings: -\begin{cfa} -warning: assignment to 'float *' from incompatible pointer type 'void (*)(void)' -warning: assignment to 'void (*)(void)' from incompatible pointer type 'float *' -\end{cfa} -Similarly, -\lstinput{17-19}{bkgd-c-tyerr.c} -with warning: -\begin{cfa} -warning: passing argument 1 of 'f' from incompatible pointer type -note: expected 'void (*)(void)' but argument is of type 'float *' -\end{cfa} -with a segmentation fault at runtime. - -That @f@'s attempt to call @g@ fails is not due to 3.14 being a particularly unlucky choice of value to put in the variable @pi@. -Rather, it is because obtaining a program that includes this essential fragment, yet exhibits a behaviour other than "doomed to crash," is a matter for an obfuscated coding competition. - -A "tractable syntactic method for proving the absence of certain program behaviours by classifying phrases according to the kinds of values they compute"*1 rejected the program. -The behaviour (whose absence is unprovable) is neither minor nor unlikely. -The rejection shows that the program is ill-typed. - -Yet, the rejection presents as a GCC warning. - -In the discussion following, ``ill-typed'' means giving a nonzero @gcc -Werror@ exit condition with a message that discusses typing. - -*1 TAPL-pg1 definition of a type system - - -\section{C Arrays} - -\subsection{C has an array type (!)} +Since this work builds on C, it is necessary to explain the C mechanisms and their shortcomings for array, linked list, and string, + + +\section{Array} When a programmer works with an array, C semantics provide access to a type that is different in every way from ``pointer to its first element.'' @@ -511,61 +444,6 @@ -\section{\CFA} - -Traditionally, fixing C meant leaving the C-ism alone, while providing a better alternative beside it. -(For later: That's what I offer with array.hfa, but in the future-work vision for arrays, the fix includes helping programmers stop accidentally using a broken C-ism.) - -\subsection{\CFA features interacting with arrays} - -Prior work on \CFA included making C arrays, as used in C code from the wild, -work, if this code is fed into @cfacc@. -The quality of this this treatment was fine, with no more or fewer bugs than is typical. - -More mixed results arose with feeding these ``C'' arrays into preexisting \CFA features. - -A notable success was with the \CFA @alloc@ function, -which type information associated with a polymorphic return type -replaces @malloc@'s use of programmer-supplied size information. -\begin{cfa} -// C, library -void * malloc( size_t ); -// C, user -struct tm * el1 = malloc( sizeof(struct tm) ); -struct tm * ar1 = malloc( 10 * sizeof(struct tm) ); - -// CFA, library -forall( T * ) T * alloc(); -// CFA, user -tm * el2 = alloc(); -tm (*ar2)[10] = alloc(); -\end{cfa} -The alloc polymorphic return compiles into a hidden parameter, which receives a compiler-generated argument. -This compiler's argument generation uses type information from the left-hand side of the initialization to obtain the intended type. -Using a compiler-produced value eliminates an opportunity for user error. - -TODO: fix in following: even the alloc call gives bad code gen: verify it was always this way; walk back the wording about things just working here; assignment (rebind) seems to offer workaround, as in bkgd-cfa-arrayinteract.cfa - -Bringing in another \CFA feature, reference types, both resolves a sore spot of the last example, and gives a first example of an array-interaction bug. -In the last example, the choice of ``pointer to array'' @ar2@ breaks a parallel with @ar1@. -They are not subscripted in the same way. -\begin{cfa} -ar1[5]; -(*ar2)[5]; -\end{cfa} -Using ``reference to array'' works at resolving this issue. TODO: discuss connection with Doug-Lea \CC proposal. -\begin{cfa} -tm (&ar3)[10] = *alloc(); -ar3[5]; -\end{cfa} -The implicit size communication to @alloc@ still works in the same ways as for @ar2@. - -Using proper array types (@ar2@ and @ar3@) addresses a concern about using raw element pointers (@ar1@), albeit a theoretical one. -TODO xref C standard does not claim that @ar1@ may be subscripted, -because no stage of interpreting the construction of @ar1@ has it be that ``there is an \emph{array object} here.'' -But both @*ar2@ and the referent of @ar3@ are the results of \emph{typed} @alloc@ calls, -where the type requested is an array, making the result, much more obviously, an array object. - -The ``reference to array'' type has its sore spots too. -TODO see also @dimexpr-match-c/REFPARAM_CALL@ (under @TRY_BUG_1@) - -TODO: I fixed a bug associated with using an array as a T. I think. Did I really? What was the bug? +\section{Linked List} + + +\section{String} Index: doc/theses/mike_brooks_MMath/intro.tex =================================================================== --- doc/theses/mike_brooks_MMath/intro.tex (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ doc/theses/mike_brooks_MMath/intro.tex (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -1,3 +1,6 @@ \chapter{Introduction} + +All modern programming languages provide three high-level containers (collection): array, linked-list, and string. +Often array is part of the programming language, while linked-list is built from pointer types, and string from a combination of array and linked-list. \cite{Blache19} @@ -5,7 +8,93 @@ \cite{Ruef19} -\section{Arrays} +\section{Array} -\section{Strings} +Array provides a homogeneous container with $O(1)$ access to elements using subscripting. +The array size can be static, dynamic but fixed after creation, or dynamic and variable after creation. +For static and dynamic-fixed, an array can be stack allocated, while dynamic-variable requires the heap. + + +\section{Linked List} + +Linked-list provides a homogeneous container with $O(log N)$/$O(N)$ access to elements using successor and predecessor operations. +Subscripting by value is sometimes available, \eg hash table. +Linked types are normally dynamically sized by adding/removing nodes using link fields internal or external to the elements (nodes). +If a programming language allows pointer to stack storage, linked-list types can be allocated on the stack; +otherwise, elements are heap allocated and explicitly/implicitly managed. + + +\section{String} + +String provides a dynamic array of homogeneous elements, where the elements are often human-readable characters. +What differentiates string from other types in that string operations work on blocks of elements for scanning and changing the elements, rather than accessing individual elements. +Nevertheless, subscripting is often available. +The cost of string operations is less important than the power of the block operation to accomplish complex manipulation. +The dynamic nature of string means storage is normally heap allocated but often implicitly managed, even in unmanaged languages. + + +\section{Motivation} + +The goal of this work is to introduce safe and complex versions of array, link-lists, and string into the programming language \CFA~\cite{CFA}, which is based on C. +Unfortunately, to make C better, while retaining a high level of backwards compatibility, requires a significant knowledge of C's design. +Hence, it is assumed the reader has a medium knowledge of C or \CC, on which extensive new C knowledge is built. + + +\subsection{C?} + +Like many established programming languages, C has a standards committee and multiple ANSI/\-ISO language manuals~\cite{C99,C11,C18,C23}. +However, most programming languages are only partially explained by standard's manuals. +When it comes to explaining how C works, the definitive source is the @gcc@ compiler, which is mimicked by other C compilers, such as Clang~\cite{clang}. +Often other C compilers must \emph{ape} @gcc@ because a large part of the C library (runtime) system contains @gcc@ features. +While some key aspects of C need to be explained by quoting from the language reference manual, to illustrate definite program semantics, I devise a program, whose behaviour exercises the point at issue, and shows its behaviour. +These example programs show +\begin{itemize} + \item the compiler accepts or rejects certain syntax, + \item prints output to buttress a claim of behaviour, + \item executes without triggering any embedded assertions testing pre/post-assertions or invariants. +\end{itemize} +This work has been tested across @gcc@ versions 8--12 and clang version 10 running on ARM, AMD, and Intel architectures. +Any discovered anomalies among compilers or versions is discussed. +In this case, I do not argue that my sample of major Linux compilers is doing the right thing with respect to the C standard. + + +\subsection{Ill-Typed Expressions} + +C reports many ill-typed expressions as warnings. +For example, these attempts to assign @y@ to @x@ and vice-versa are obviously ill-typed. +\lstinput{12-15}{bkgd-c-tyerr.c} +with warnings: +\begin{cfa} +warning: assignment to 'float *' from incompatible pointer type 'void (*)(void)' +warning: assignment to 'void (*)(void)' from incompatible pointer type 'float *' +\end{cfa} +Similarly, +\lstinput{17-19}{bkgd-c-tyerr.c} +with warning: +\begin{cfa} +warning: passing argument 1 of 'f' from incompatible pointer type +note: expected 'void (*)(void)' but argument is of type 'float *' +\end{cfa} +with a segmentation fault at runtime. +Clearly, @gcc@ understands these ill-typed case, and yet allows the program to compile, which seems like madness. +Compiling with flag @-Werror@, which turns warnings into errors, is often too strong, because some warnings are just warnings. +In the following discussion, ``ill-typed'' means giving a nonzero @gcc@ exit condition with a message that discusses typing. +Note, \CFA's type-system rejects all these ill-typed cases as type mismatch errors. + +% That @f@'s attempt to call @g@ fails is not due to 3.14 being a particularly unlucky choice of value to put in the variable @pi@. +% Rather, it is because obtaining a program that includes this essential fragment, yet exhibits a behaviour other than "doomed to crash," is a matter for an obfuscated coding competition. + +% A "tractable syntactic method for proving the absence of certain program behaviours by classifying phrases according to the kinds of values they compute"*1 rejected the program. +% The behaviour (whose absence is unprovable) is neither minor nor unlikely. +% The rejection shows that the program is ill-typed. +% +% Yet, the rejection presents as a GCC warning. +% *1 TAPL-pg1 definition of a type system + \section{Contributions} + +\subsection{Linked List} + +\subsection{Array} + +\subsection{String} Index: doc/theses/mike_brooks_MMath/uw-ethesis.tex =================================================================== --- doc/theses/mike_brooks_MMath/uw-ethesis.tex (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ doc/theses/mike_brooks_MMath/uw-ethesis.tex (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -218,6 +218,6 @@ \input{intro} \input{background} +\input{array} \input{list} -\input{array} \input{string} \input{conclusion} Index: libcfa/src/stdlib.cfa =================================================================== --- libcfa/src/stdlib.cfa (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ libcfa/src/stdlib.cfa (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -10,6 +10,6 @@ // Created On : Thu Jan 28 17:10:29 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Aug 14 18:22:36 2023 -// Update Count : 642 +// Last Modified On : Sun Mar 17 08:25:32 2024 +// Update Count : 699 // @@ -21,7 +21,7 @@ #include // memcpy, memset -//#include // fabsf, fabs, fabsl #include // _Complex_I #include +#include // isblank #pragma GCC visibility push(default) @@ -65,6 +65,78 @@ //--------------------------------------- +// Check if all string characters are a specific kind, e.g., checkif( s, isblank ) + +bool checkif( const char s[], int (* kind)( int ) ) { + for () { + if ( *s == '\0' ) return true; + if ( ! kind( *s ) ) return false; + s += 1; + } // for +} // checkif + +bool checkif( const char s[], int (* kind)( int, locale_t ), locale_t locale ) { + for () { + if ( *s == '\0' ) return true; + if ( ! kind( *s, locale ) ) return false; + s += 1; + } // for +} // checkif + +//--------------------------------------- + +float _Complex strto( const char sptr[], char * eptr[] ) { + float re, im; + char * eeptr; + errno = 0; // reset + re = strtof( sptr, &eeptr ); + if ( sptr != eeptr ) { + im = strtof( eeptr, &eeptr ); + if ( sptr != eeptr ) { + if ( *eeptr == 'i' ) { + if ( eptr != 0p ) *eptr = eeptr + 1; + return re + im * _Complex_I; + } // if + } // if + } // if + if ( eptr != 0p ) *eptr = eeptr; // error case + return 0.0f + 0.0f * _Complex_I; +} // strto + +double _Complex strto( const char sptr[], char * eptr[] ) { + double re, im; + char * eeptr; + re = strtod( sptr, &eeptr ); + if ( sptr != eeptr ) { + im = strtod( eeptr, &eeptr ); + if ( sptr != eeptr ) { + if ( *eeptr == 'i' ) { + if ( eptr != 0p ) *eptr = eeptr + 1; + return re + im * _Complex_I; + } // if + } // if + } // if + if ( eptr != 0p ) *eptr = eeptr; // error case + return 0.0 + 0.0 * _Complex_I; +} // strto + +long double _Complex strto( const char sptr[], char * eptr[] ) { + long double re, im; + char * eeptr; + re = strtold( sptr, &eeptr ); + if ( sptr != eeptr ) { + im = strtold( eeptr, &eeptr ); + if ( sptr != eeptr ) { + if ( *eeptr == 'i' ) { + if ( eptr != 0p ) *eptr = eeptr + 1; + return re + im * _Complex_I; + } // if + } // if + } // if + if ( eptr != 0p ) *eptr = eeptr; // error case + return 0.0L + 0.0L * _Complex_I; +} // strto + forall( T | { T strto( const char sptr[], char * eptr[], int ); } ) -T convert( const char sptr[] ) { +T convert( const char sptr[] ) { // integral char * eptr; errno = 0; // reset @@ -72,40 +144,18 @@ if ( errno == ERANGE ) throw ExceptionInst( out_of_range ); if ( eptr == sptr || // conversion failed, no characters generated - *eptr != '\0' ) throw ExceptionInst( invalid_argument ); // not at end of str ? + eptr[0] != '\0' && ! checkif( eptr, isblank ) ) throw ExceptionInst( invalid_argument ); // not at end of blank str ? return val; } // convert -float _Complex strto( const char sptr[], char * eptr[] ) { - float re, im; - char * eeptr; - re = strtof( sptr, &eeptr ); - if ( sptr == eeptr ) { if ( eptr != 0 ) *eptr = eeptr; return 0.0f + 0.0f * _Complex_I; } - im = strtof( eeptr, &eeptr ); - if ( sptr == eeptr ) { if ( eptr != 0 ) *eptr = eeptr; return 0.0f + 0.0f * _Complex_I; } - if ( *eeptr != 'i' ) { if ( eptr != 0 ) *eptr = eeptr; return 0.0f + 0.0f * _Complex_I; } - return re + im * _Complex_I; -} // strto - -double _Complex strto( const char sptr[], char * eptr[] ) { - double re, im; - char * eeptr; - re = strtod( sptr, &eeptr ); - if ( sptr == eeptr ) { if ( eptr != 0 ) *eptr = eeptr; return 0.0 + 0.0 * _Complex_I; } - im = strtod( eeptr, &eeptr ); - if ( sptr == eeptr ) { if ( eptr != 0 ) *eptr = eeptr; return 0.0 + 0.0 * _Complex_I; } - if ( *eeptr != 'i' ) { if ( eptr != 0 ) *eptr = eeptr; return 0.0 + 0.0 * _Complex_I; } - return re + im * _Complex_I; -} // strto - -long double _Complex strto( const char sptr[], char * eptr[] ) { - long double re, im; - char * eeptr; - re = strtold( sptr, &eeptr ); - if ( sptr == eeptr ) { if ( eptr != 0 ) *eptr = eeptr; return 0.0L + 0.0L * _Complex_I; } - im = strtold( eeptr, &eeptr ); - if ( sptr == eeptr ) { if ( eptr != 0 ) *eptr = eeptr; return 0.0L + 0.0L * _Complex_I; } - if ( *eeptr != 'i' ) { if ( eptr != 0 ) *eptr = eeptr; return 0.0L + 0.0L * _Complex_I; } - return re + im * _Complex_I; -} // strto +forall( T | { T strto( const char sptr[], char * eptr[] ); } ) +T convert( const char sptr[] ) { // floating-point + char * eptr; + errno = 0; // reset + T val = strto( sptr, &eptr ); // attempt conversion + if ( errno == ERANGE ) throw ExceptionInst( out_of_range ); + if ( eptr == sptr || // conversion failed, no characters generated + eptr[0] != '\0' && ! checkif( eptr, isblank ) ) throw ExceptionInst( invalid_argument ); // not at end of blank str ? + return val; +} // convert //--------------------------------------- Index: libcfa/src/stdlib.hfa =================================================================== --- libcfa/src/stdlib.hfa (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ libcfa/src/stdlib.hfa (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -10,6 +10,6 @@ // Created On : Thu Jan 28 17:12:35 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Sun Oct 8 09:18:28 2023 -// Update Count : 789 +// Last Modified On : Sun Mar 17 08:25:31 2024 +// Update Count : 796 // @@ -291,4 +291,9 @@ forall( T & | sized(T) | { void ^?{}( T & ); } ) void adelete( T arr[] ); forall( T & | sized(T) | { void ^?{}( T & ); }, TT... | { void adelete( TT ); } ) void adelete( T arr[], TT rest ); +//--------------------------------------- + +// Check if all string characters are a specific kind, e.g., checkif( s, isblank ) +bool checkif( const char s[], int (* kind)( int ) ); +bool checkif( const char s[], int (* kind)( int, locale_t ), locale_t locale ); //--------------------------------------- @@ -315,5 +320,7 @@ forall( T | { T strto( const char sptr[], char * eptr[], int ); } ) -T convert( const char sptr[] ); +T convert( const char sptr[] ); // integrals +forall( T | { T strto( const char sptr[], char * eptr[] ); } ) +T convert( const char sptr[] ); // floating-point (no base) static inline { Index: src/CodeGen/CodeGenerator.cpp =================================================================== --- src/CodeGen/CodeGenerator.cpp (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ src/CodeGen/CodeGenerator.cpp (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -192,10 +192,13 @@ } - assert( decl->returns.size() < 2 ); if ( 1 == decl->returns.size() ) { ast::ptr const & type = decl->returns[0]->get_type(); output << genTypeNoAttr( type, acc.str(), subOptions ); - } else { + } else if ( 0 == decl->returns.size() ) { output << "void " + acc.str(); + } else { + assertf( !options.genC, "Multi-return should not reach code generation." ); + ast::ptr type = new ast::TupleType( copy( decl->type->returns ) ); + output << genTypeNoAttr( type, acc.str(), subOptions ); } Index: src/Parser/DeclarationNode.cc =================================================================== --- src/Parser/DeclarationNode.cc (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ src/Parser/DeclarationNode.cc (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -185,6 +185,4 @@ newnode->type->aggregate.fields = fields; newnode->type->aggregate.body = body; - newnode->type->aggregate.tagged = false; - newnode->type->aggregate.parent = nullptr; return newnode; } // DeclarationNode::newAggregate @@ -199,6 +197,10 @@ newnode->type->enumeration.typed = typed; newnode->type->enumeration.hiding = hiding; - if ( base && base->type ) { + if ( base ) { + assert( typed ); + assert( base->type ); newnode->type->base = base->type; + base->type = nullptr; + delete base; } // if @@ -220,14 +222,12 @@ DeclarationNode * DeclarationNode::newEnumValueGeneric( const string * name, InitializerNode * init ) { - if ( init ) { - if ( init->get_expression() ) { - return newEnumConstant( name, init->get_expression() ); - } else { - DeclarationNode * newnode = newName( name ); - newnode->initializer = init; - return newnode; - } // if + if ( nullptr == init ) { + return newName( name ); + } else if ( init->get_expression() ) { + return newEnumConstant( name, init->get_expression() ); } else { - return newName( name ); + DeclarationNode * newnode = newName( name ); + newnode->initializer = init; + return newnode; } // if } // DeclarationNode::newEnumValueGeneric @@ -502,4 +502,102 @@ } +// This code handles a special issue with the attribute transparent_union. +// +// typedef union U { int i; } typedef_name __attribute__(( aligned(16) )) __attribute__(( transparent_union )) +// +// Here the attribute aligned goes with the typedef_name, so variables declared of this type are +// aligned. However, the attribute transparent_union must be moved from the typedef_name to +// alias union U. Currently, this is the only know attribute that must be moved from typedef to +// alias. +static void moveUnionAttribute( DeclarationNode * decl, DeclarationNode * unionDecl ) { + assert( decl->type->kind == TypeData::Symbolic ); + assert( decl->type->symbolic.isTypedef ); + assert( unionDecl->type->kind == TypeData::Aggregate ); + + if ( unionDecl->type->aggregate.kind != ast::AggregateDecl::Union ) return; + + // Ignore the Aggregate_t::attributes. Why did we add that before the rework? + for ( auto attr = decl->attributes.begin() ; attr != decl->attributes.end() ; ) { + if ( (*attr)->name == "transparent_union" || (*attr)->name == "__transparent_union__" ) { + unionDecl->attributes.emplace_back( attr->release() ); + attr = decl->attributes.erase( attr ); + } else { + ++attr; + } + } +} + +// Helper for addTypedef, handles the case where the typedef wraps an +// aggregate declaration (not a type), returns a chain of nodes. +static DeclarationNode * addTypedefAggr( + DeclarationNode * olddecl, TypeData * newtype ) { + TypeData *& oldaggr = olddecl->type->aggInst.aggregate; + + // Handle anonymous aggregates: typedef struct { int i; } foo + // Give the typedefed type a consistent name across translation units. + if ( oldaggr->aggregate.anon ) { + delete oldaggr->aggregate.name; + oldaggr->aggregate.name = new string( "__anonymous_" + *olddecl->name ); + oldaggr->aggregate.anon = false; + oldaggr->qualifiers.reset(); + } + + // Replace the wrapped TypeData with a forward declaration. + TypeData * newaggr = new TypeData( TypeData::Aggregate ); + newaggr->aggregate.kind = oldaggr->aggregate.kind; + newaggr->aggregate.name = oldaggr->aggregate.name ? new string( *oldaggr->aggregate.name ) : nullptr; + newaggr->aggregate.body = false; + newaggr->aggregate.anon = oldaggr->aggregate.anon; + swap( newaggr, oldaggr ); + + newtype->base = olddecl->type; + olddecl->type = newtype; + DeclarationNode * newdecl = new DeclarationNode; + newdecl->type = newaggr; + newdecl->next = olddecl; + + moveUnionAttribute( olddecl, newdecl ); + + return newdecl; +} + +// Helper for addTypedef, handles the case where the typedef wraps an +// enumeration declaration (not a type), returns a chain of nodes. +static DeclarationNode * addTypedefEnum( + DeclarationNode * olddecl, TypeData * newtype ) { + TypeData *& oldenum = olddecl->type->aggInst.aggregate; + + // Handle anonymous enumeration: typedef enum { A, B, C } foo + // Give the typedefed type a consistent name across translation units. + if ( oldenum->enumeration.anon ) { + delete oldenum->enumeration.name; + oldenum->enumeration.name = new string( "__anonymous_" + *olddecl->name ); + oldenum->enumeration.anon = false; + oldenum->qualifiers.reset(); + } + + // Replace the wrapped TypeData with a forward declaration. + TypeData * newenum = new TypeData( TypeData::Enum ); + newenum->enumeration.name = oldenum->enumeration.name ? new string( *oldenum->enumeration.name ) : nullptr; + newenum->enumeration.body = false; + newenum->enumeration.anon = oldenum->enumeration.anon; + newenum->enumeration.typed = oldenum->enumeration.typed; + newenum->enumeration.hiding = oldenum->enumeration.hiding; + swap( newenum, oldenum ); + + newtype->base = olddecl->type; + olddecl->type = newtype; + DeclarationNode * newdecl = new DeclarationNode; + newdecl->type = newenum; + newdecl->next = olddecl; + + return newdecl; +} + +// Wrap the declaration in a typedef. It actually does that by modifying the +// existing declaration, and may split it into two declarations. +// This only happens if the wrapped type is actually a declaration of a SUE +// type. If it does, the DeclarationNode for the SUE declaration is the node +// returned, make sure later transformations are applied to the right node. DeclarationNode * DeclarationNode::addTypedef() { TypeData * newtype = new TypeData( TypeData::Symbolic ); @@ -507,7 +605,20 @@ newtype->symbolic.isTypedef = true; newtype->symbolic.name = name ? new string( *name ) : nullptr; - newtype->base = type; - type = newtype; - return this; + // If this typedef is wrapping an aggregate, separate them out. + if ( TypeData::AggregateInst == type->kind + && TypeData::Aggregate == type->aggInst.aggregate->kind + && type->aggInst.aggregate->aggregate.body ) { + return addTypedefAggr( this, newtype ); + // If this typedef is wrapping an enumeration, separate them out. + } else if ( TypeData::AggregateInst == type->kind + && TypeData::Enum == type->aggInst.aggregate->kind + && type->aggInst.aggregate->enumeration.body ) { + return addTypedefEnum( this, newtype ); + // There is no internal declaration, just a type. + } else { + newtype->base = type; + type = newtype; + return this; + } } @@ -711,73 +822,4 @@ } -// If a typedef wraps an anonymous declaration, name the inner declaration so it has a consistent name across -// translation units. -static void nameTypedefedDecl( - DeclarationNode * innerDecl, - const DeclarationNode * outerDecl ) { - TypeData * outer = outerDecl->type; - assert( outer ); - // First make sure this is a typedef: - if ( outer->kind != TypeData::Symbolic || !outer->symbolic.isTypedef ) { - return; - } - TypeData * inner = innerDecl->type; - assert( inner ); - // Always clear any CVs associated with the aggregate: - inner->qualifiers.reset(); - // Handle anonymous aggregates: typedef struct { int i; } foo - if ( inner->kind == TypeData::Aggregate && inner->aggregate.anon ) { - delete inner->aggregate.name; - inner->aggregate.name = new string( "__anonymous_" + *outerDecl->name ); - inner->aggregate.anon = false; - assert( outer->base ); - delete outer->base->aggInst.aggregate->aggregate.name; - outer->base->aggInst.aggregate->aggregate.name = new string( "__anonymous_" + *outerDecl->name ); - outer->base->aggInst.aggregate->aggregate.anon = false; - outer->base->aggInst.aggregate->qualifiers.reset(); - // Handle anonymous enumeration: typedef enum { A, B, C } foo - } else if ( inner->kind == TypeData::Enum && inner->enumeration.anon ) { - delete inner->enumeration.name; - inner->enumeration.name = new string( "__anonymous_" + *outerDecl->name ); - inner->enumeration.anon = false; - assert( outer->base ); - delete outer->base->aggInst.aggregate->enumeration.name; - outer->base->aggInst.aggregate->enumeration.name = new string( "__anonymous_" + *outerDecl->name ); - outer->base->aggInst.aggregate->enumeration.anon = false; - // No qualifiers.reset() here. - } -} - -// This code handles a special issue with the attribute transparent_union. -// -// typedef union U { int i; } typedef_name __attribute__(( aligned(16) )) __attribute__(( transparent_union )) -// -// Here the attribute aligned goes with the typedef_name, so variables declared of this type are -// aligned. However, the attribute transparent_union must be moved from the typedef_name to -// alias union U. Currently, this is the only know attribute that must be moved from typedef to -// alias. -static void moveUnionAttribute( ast::Decl * decl, ast::UnionDecl * unionDecl ) { - if ( auto typedefDecl = dynamic_cast( decl ) ) { - // Is the typedef alias a union aggregate? - if ( nullptr == unionDecl ) return; - - // If typedef is an alias for a union, then its alias type was hoisted above and remembered. - if ( auto unionInstType = typedefDecl->base.as() ) { - auto instType = ast::mutate( unionInstType ); - // Remove all transparent_union attributes from typedef and move to alias union. - for ( auto attr = instType->attributes.begin() ; attr != instType->attributes.end() ; ) { - assert( *attr ); - if ( (*attr)->name == "transparent_union" || (*attr)->name == "__transparent_union__" ) { - unionDecl->attributes.emplace_back( attr->release() ); - attr = instType->attributes.erase( attr ); - } else { - attr++; - } - } - typedefDecl->base = instType; - } - } -} - // Get the non-anonymous name of the instance type of the declaration, // if one exists. @@ -800,14 +842,9 @@ try { bool extracted_named = false; - ast::UnionDecl * unionDecl = nullptr; if ( DeclarationNode * extr = cur->extractAggregate() ) { assert( cur->type ); - nameTypedefedDecl( extr, cur ); if ( ast::Decl * decl = extr->build() ) { - // Remember the declaration if it is a union aggregate ? - unionDecl = dynamic_cast( decl ); - *out++ = decl; @@ -828,6 +865,4 @@ if ( ast::Decl * decl = cur->build() ) { - moveUnionAttribute( decl, unionDecl ); - if ( "" == decl->name && !cur->get_inLine() ) { // Don't include anonymous declaration for named aggregates, Index: src/Parser/TypeData.cc =================================================================== --- src/Parser/TypeData.cc (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ src/Parser/TypeData.cc (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -88,6 +88,4 @@ aggregate.fields = nullptr; aggregate.body = false; - aggregate.tagged = false; - aggregate.parent = nullptr; aggregate.anon = false; break; @@ -221,5 +219,4 @@ newtype->aggregate.kind = aggregate.kind; newtype->aggregate.name = aggregate.name ? new string( *aggregate.name ) : nullptr; - newtype->aggregate.parent = aggregate.parent ? new string( *aggregate.parent ) : nullptr; newtype->aggregate.params = maybeCopy( aggregate.params ); newtype->aggregate.actuals = maybeCopy( aggregate.actuals ); @@ -228,5 +225,4 @@ newtype->aggregate.body = aggregate.body; newtype->aggregate.anon = aggregate.anon; - newtype->aggregate.tagged = aggregate.tagged; break; case AggregateInst: Index: src/Parser/TypeData.h =================================================================== --- src/Parser/TypeData.h (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ src/Parser/TypeData.h (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -48,5 +48,4 @@ ast::AggregateDecl::Aggregate kind; const std::string * name = nullptr; - const std::string * parent = nullptr; DeclarationNode * params = nullptr; ExpressionNode * actuals = nullptr; // holds actual parameters later applied to AggInst @@ -55,5 +54,4 @@ bool body; bool anon; - bool tagged; }; Index: src/Parser/parser.yy =================================================================== --- src/Parser/parser.yy (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ src/Parser/parser.yy (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -10,6 +10,6 @@ // Created On : Sat Sep 1 20:22:55 2001 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Mar 11 18:30:03 2024 -// Update Count : 6589 +// Last Modified On : Sat Mar 16 18:19:23 2024 +// Update Count : 6617 // @@ -485,5 +485,5 @@ %type elaborated_type elaborated_type_nobody -%type enumerator_list enum_type enum_type_nobody +%type enumerator_list enum_type enum_type_nobody enumerator_type %type enumerator_value_opt @@ -2742,8 +2742,24 @@ enum_type: - ENUM attribute_list_opt '{' enumerator_list comma_opt '}' - { $$ = DeclarationNode::newEnum( nullptr, $4, true, false )->addQualifiers( $2 ); } - | ENUM attribute_list_opt '!' '{' enumerator_list comma_opt '}' // invalid syntax rule - { SemanticError( yylloc, "syntax error, hiding ('!') the enumerator names of an anonymous enumeration means the names are inaccessible." ); $$ = nullptr; } + // anonymous, no type name + ENUM attribute_list_opt hide_opt '{' enumerator_list comma_opt '}' + { + if ( $3 == EnumHiding::Hide ) { + SemanticError( yylloc, "syntax error, hiding ('!') the enumerator names of an anonymous enumeration means the names are inaccessible." ); $$ = nullptr; + } // if + $$ = DeclarationNode::newEnum( nullptr, $5, true, false )->addQualifiers( $2 ); + } + | ENUM enumerator_type attribute_list_opt hide_opt '{' enumerator_list comma_opt '}' + { + if ( $2 && ($2->storageClasses.val != 0 || $2->type->qualifiers.any()) ) { + SemanticError( yylloc, "syntax error, storage-class and CV qualifiers are not meaningful for enumeration constants, which are const." ); + } + if ( $4 == EnumHiding::Hide ) { + SemanticError( yylloc, "syntax error, hiding ('!') the enumerator names of an anonymous enumeration means the names are inaccessible." ); $$ = nullptr; + } // if + $$ = DeclarationNode::newEnum( nullptr, $6, true, true, $2 )->addQualifiers( $3 ); + } + + // named type | ENUM attribute_list_opt identifier { typedefTable.makeTypedef( *$3, "enum_type 1" ); } @@ -2752,43 +2768,25 @@ | ENUM attribute_list_opt typedef_name hide_opt '{' enumerator_list comma_opt '}' // unqualified type name { $$ = DeclarationNode::newEnum( $3->name, $6, true, false, nullptr, $4 )->addQualifiers( $2 ); } - | ENUM '(' cfa_abstract_parameter_declaration ')' attribute_list_opt '{' enumerator_list comma_opt '}' - { - if ( $3->storageClasses.val != 0 || $3->type->qualifiers.any() ) { + | ENUM enumerator_type attribute_list_opt identifier attribute_list_opt + { + if ( $2 && ($2->storageClasses.any() || $2->type->qualifiers.val != 0) ) { SemanticError( yylloc, "syntax error, storage-class and CV qualifiers are not meaningful for enumeration constants, which are const." ); } - $$ = DeclarationNode::newEnum( nullptr, $7, true, true, $3 )->addQualifiers( $5 ); - } - | ENUM '(' cfa_abstract_parameter_declaration ')' attribute_list_opt '!' '{' enumerator_list comma_opt '}' // unqualified type name - { SemanticError( yylloc, "syntax error, hiding ('!') the enumerator names of an anonymous enumeration means the names are inaccessible." ); $$ = nullptr; } - | ENUM '(' ')' attribute_list_opt '{' enumerator_list comma_opt '}' - { - $$ = DeclarationNode::newEnum( nullptr, $6, true, true )->addQualifiers( $4 ); - } - | ENUM '(' ')' attribute_list_opt '!' '{' enumerator_list comma_opt '}' // invalid syntax rule - { SemanticError( yylloc, "syntax error, hiding ('!') the enumerator names of an anonymous enumeration means the names are inaccessible." ); $$ = nullptr; } - | ENUM '(' cfa_abstract_parameter_declaration ')' attribute_list_opt identifier attribute_list_opt - { - if ( $3 && ($3->storageClasses.any() || $3->type->qualifiers.val != 0) ) { - SemanticError( yylloc, "syntax error, storage-class and CV qualifiers are not meaningful for enumeration constants, which are const." ); - } - typedefTable.makeTypedef( *$6, "enum_type 2" ); + typedefTable.makeTypedef( *$4, "enum_type 2" ); } hide_opt '{' enumerator_list comma_opt '}' - { - $$ = DeclarationNode::newEnum( $6, $11, true, true, $3, $9 )->addQualifiers( $5 )->addQualifiers( $7 ); - } - | ENUM '(' ')' attribute_list_opt identifier attribute_list_opt hide_opt '{' enumerator_list comma_opt '}' - { - $$ = DeclarationNode::newEnum( $5, $9, true, true, nullptr, $7 )->addQualifiers( $4 )->addQualifiers( $6 ); - } - | ENUM '(' cfa_abstract_parameter_declaration ')' attribute_list_opt typedef_name attribute_list_opt hide_opt '{' enumerator_list comma_opt '}' - { - $$ = DeclarationNode::newEnum( $6->name, $10, true, true, $3, $8 )->addQualifiers( $5 )->addQualifiers( $7 ); - } - | ENUM '(' ')' attribute_list_opt typedef_name attribute_list_opt hide_opt '{' enumerator_list comma_opt '}' - { - $$ = DeclarationNode::newEnum( $5->name, $9, true, true, nullptr, $7 )->addQualifiers( $4 )->addQualifiers( $6 ); - } + { $$ = DeclarationNode::newEnum( $4, $9, true, true, $2, $7 )->addQualifiers( $3 )->addQualifiers( $5 ); } + | ENUM enumerator_type attribute_list_opt typedef_name attribute_list_opt hide_opt '{' enumerator_list comma_opt '}' + { $$ = DeclarationNode::newEnum( $4->name, $8, true, true, $2, $6 )->addQualifiers( $3 )->addQualifiers( $5 ); } + + // forward declaration | enum_type_nobody + ; + +enumerator_type: + '(' ')' // pure enumeration + { $$ = nullptr; } + | '(' cfa_abstract_parameter_declaration ')' // typed enumeration + { $$ = $2; } ; Index: src/main.cc =================================================================== --- src/main.cc (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ src/main.cc (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -101,8 +101,4 @@ } -// Helpers for checkInvariant: -void checkInvariants( std::list< Declaration * > & ) {} -using ast::checkInvariants; - #define PASS( name, pass, unit, ... ) \ if ( errorp ) { cerr << name << endl; } \ @@ -112,5 +108,5 @@ Stats::Time::StopBlock(); \ if ( invariant ) { \ - checkInvariants(unit); \ + ast::checkInvariants(unit); \ } Index: tests/.expect/ato.arm64.txt =================================================================== --- tests/.expect/ato.arm64.txt (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ tests/.expect/ato.arm64.txt (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -3,25 +3,41 @@ -123 -123 123 123 +-123 -123 +123 123 +-123.456 -123.456 +-123.456789012346 -123.4567890123456 +-123.45678901234567890123456789 -123.45678901234567890123456789 +-123.456-123.456i -123.456-123.456i +-123.456789012346+123.456789012346i -123.4567890123456+123.4567890123456i +123.45678901234567890123456789-123.45678901234567890123456789i 123.45678901234567890123456789-123.45678901234567890123456789i +123.45678901234-123.456789i 123.45678901234 -123.4567890i -123 -123 123 123 +-123 -123 +123 123 +-123 -123 +123 123 -123.456 -123.456 -123.456789012346 -123.4567890123456 --123.45678901234567890123456789 -123.45678901234567890123456789 +-123.45678901234567890123456789 -123.45678901234567890123456789 +-123.456-123.456i -123.456-123.456i +-123.456789012346+123.456789012346i -123.4567890123456+123.4567890123456i +123.45678901234567890123456789-123.45678901234567890123456789i 123.45678901234567890123456789-123.45678901234567890123456789i +123.45678901234-123.456789i 123.45678901234 -123.4567890i +invalid argument 2.0fred +invalid argument 2 3x +-123 -123 +123 123 +-123 -123 +123 123 +-123 -123 +123 123 +-123.456 -123.456 +-123.456789012346 -123.4567890123456 +-123.45678901234567890123456789 -123.45678901234567890123456789 -123.456-123.456i -123.456-123.456i -123.456789012346+123.456789012346i -123.4567890123456+123.4567890123456i 123.45678901234567890123456789-123.45678901234567890123456789i 123.45678901234567890123456789-123.45678901234567890123456789i 123.45678901234-123.456789i 123.45678901234-123.4567890i --123 -123 -123 123 --123 -123 -123 123 --123 -123 -123 123 --123.456 -123.456 --123.456789012346 -123.4567890123456 --123.45678901234567890123456789 -123.45678901234567890123456789 --123.456-123.456i -123.456-123.456i -0.+0.i 2 3 --123.456789012346+123.456789012346i -123.4567890123456+123.4567890123456i -123.45678901234567890123456789-123.45678901234567890123456789i 123.45678901234567890123456789-123.45678901234567890123456789i -123.45678901234-123.456789i 123.45678901234-123.4567890i +invalid argument 2.0fred +invalid argument 2 3x Index: tests/.expect/ato.x64.txt =================================================================== --- tests/.expect/ato.x64.txt (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ tests/.expect/ato.x64.txt (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -3,25 +3,41 @@ -123 -123 123 123 +-123 -123 +123 123 +-123.456 -123.456 +-123.456789012346 -123.4567890123456 +-123.456789012345679 -123.45678901234567890123456789 +-123.456-123.456i -123.456-123.456i +-123.456789012346+123.456789012346i -123.4567890123456+123.4567890123456i +123.456789012345679-123.456789012345679i 123.45678901234567890123456789-123.45678901234567890123456789i +123.45678901234-123.456789i 123.45678901234 -123.4567890i -123 -123 123 123 +-123 -123 +123 123 +-123 -123 +123 123 -123.456 -123.456 -123.456789012346 -123.4567890123456 --123.456789012345679 -123.45678901234567890123456789 +-123.456789012345679 -123.45678901234567890123456789 +-123.456-123.456i -123.456-123.456i +-123.456789012346+123.456789012346i -123.4567890123456+123.4567890123456i +123.456789012345679-123.456789012345679i 123.45678901234567890123456789-123.45678901234567890123456789i +123.45678901234-123.456789i 123.45678901234 -123.4567890i +invalid argument 2.0fred +invalid argument 2 3x +-123 -123 +123 123 +-123 -123 +123 123 +-123 -123 +123 123 +-123.456 -123.456 +-123.456789012346 -123.4567890123456 +-123.456789012345679 -123.45678901234567890123456789 -123.456-123.456i -123.456-123.456i -123.456789012346+123.456789012346i -123.4567890123456+123.4567890123456i 123.456789012345679-123.456789012345679i 123.45678901234567890123456789-123.45678901234567890123456789i 123.45678901234-123.456789i 123.45678901234-123.4567890i --123 -123 -123 123 --123 -123 -123 123 --123 -123 -123 123 --123.456 -123.456 --123.456789012346 -123.4567890123456 --123.456789012345679 -123.45678901234567890123456789 --123.456-123.456i -123.456-123.456i -0.+0.i 2 3 --123.456789012346+123.456789012346i -123.4567890123456+123.4567890123456i -123.456789012345679-123.456789012345679i 123.45678901234567890123456789-123.45678901234567890123456789i -123.45678901234-123.456789i 123.45678901234-123.4567890i +invalid argument 2.0fred +invalid argument 2 3x Index: tests/.expect/ato.x86.txt =================================================================== --- tests/.expect/ato.x86.txt (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ tests/.expect/ato.x86.txt (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -3,25 +3,41 @@ -123 -123 123 123 +-123 -123 +123 123 +-123.456 -123.456 +-123.456789012346 -123.4567890123456 +-123.456789012345679 -123.45678901234567890123456789 +-123.456-123.456i -123.456-123.456i +-123.456789012346+123.456789012346i -123.4567890123456+123.4567890123456i +123.456789012345679-123.456789012345679i 123.45678901234567890123456789-123.45678901234567890123456789i +123.45678901234-123.456789i 123.45678901234 -123.4567890i -123 -123 123 123 +-123 -123 +123 123 +-123 -123 +123 123 -123.456 -123.456 -123.456789012346 -123.4567890123456 --123.456789012345679 -123.45678901234567890123456789 +-123.456789012345679 -123.45678901234567890123456789 +-123.456-123.456i -123.456-123.456i +-123.456789012346+123.456789012346i -123.4567890123456+123.4567890123456i +123.456789012345679-123.456789012345679i 123.45678901234567890123456789-123.45678901234567890123456789i +123.45678901234-123.456789i 123.45678901234 -123.4567890i +invalid argument 2.0fred +invalid argument 2 3x +-123 -123 +123 123 +-123 -123 +123 123 +-123 -123 +123 123 +-123.456 -123.456 +-123.456789012346 -123.4567890123456 +-123.456789012345679 -123.45678901234567890123456789 -123.456-123.456i -123.456-123.456i -123.456789012346+123.456789012346i -123.4567890123456+123.4567890123456i 123.456789012345679-123.456789012345679i 123.45678901234567890123456789-123.45678901234567890123456789i 123.45678901234-123.456789i 123.45678901234-123.4567890i --123 -123 -123 123 --123 -123 -123 123 --123 -123 -123 123 --123.456 -123.456 --123.456789012346 -123.4567890123456 --123.456789012345679 -123.45678901234567890123456789 --123.456-123.456i -123.456-123.456i -0.+0.i 2 3 --123.456789012346+123.456789012346i -123.4567890123456+123.4567890123456i -123.456789012345679-123.456789012345679i 123.45678901234567890123456789-123.45678901234567890123456789i -123.45678901234-123.456789i 123.45678901234-123.4567890i +invalid argument 2.0fred +invalid argument 2 3x Index: tests/ato.cfa =================================================================== --- tests/ato.cfa (revision df78cce298234f5393935a7b378e26335eaf33ff) +++ tests/ato.cfa (revision 486caad7c0e53d562d8675ebf6836c087eaa427b) @@ -10,6 +10,6 @@ // Created On : Thu Feb 4 08:10:57 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Tue Dec 4 21:33:53 2018 -// Update Count : 92 +// Last Modified On : Fri Mar 15 17:58:35 2024 +// Update Count : 145 // @@ -18,4 +18,6 @@ int main( void ) { + // ato + const char * sptr = "-123"; int i = ato( sptr ); @@ -32,8 +34,8 @@ sout | uli | sptr; - sptr = "-123"; + sptr = " -123 "; // spaces allowed long long int lli = ato( sptr ); sout | lli | sptr; - sptr = "123"; + sptr = " 123 "; // spaces allowed unsigned long long int ulli = ato( sptr ); sout | ulli | sptr; @@ -45,5 +47,5 @@ double d = ato( sptr ); sout | d | sptr; - sptr = "-123.45678901234567890123456789"; + sptr = " -123.45678901234567890123456789 "; // spaces allowed long double ld = ato( sptr ); sout | ld | sptr; @@ -58,62 +60,133 @@ long double _Complex ldc = ato( sptr ); sout | ldc | sptr; - sptr = "123.45678901234-123.4567890i"; + sptr = " 123.45678901234 -123.4567890i "; // spaces allowed long double _Complex ldc2 = ato( sptr ); sout | ldc2 | sptr; + // strto sptr = "-123"; - i = strto( sptr, 0, 10 ); + i = strto( sptr, 0p, 10 ); sout | i | sptr; sptr = "123"; - ui = strto( sptr, 0, 10 ); + ui = strto( sptr, 0p, 10 ); sout | ui | sptr; sptr = "-123"; - li = strto( sptr, 0, 10 ); + li = strto( sptr, 0p, 10 ); sout | li | sptr; sptr = "123"; - uli = strto( sptr, 0, 10 ); + uli = strto( sptr, 0p, 10 ); sout | uli | sptr; - sptr = "-123"; - lli = strto( sptr, 0, 10 ); + sptr = " -123 "; // spaces allowed + lli = strto( sptr, 0p, 10 ); sout | lli | sptr; - sptr = "123"; - ulli = strto( sptr, 0, 10 ); + sptr = " 123 "; // spaces allowed + ulli = strto( sptr, 0p, 10 ); sout | ulli | sptr; sptr = "-123.456"; - f = strto( sptr, 0 ); + f = strto( sptr, 0p ); sout | f | sptr; sptr = "-123.4567890123456"; - d = strto( sptr, 0 ); + d = strto( sptr, 0p ); sout | d | sptr; - sptr = "-123.45678901234567890123456789"; - ld = strto( sptr, 0 ); + sptr = " -123.45678901234567890123456789 "; // spaces allowed + ld = strto( sptr, 0p ); sout | ld | sptr; sptr = "-123.456-123.456i"; - fc = strto( sptr, 0 ); + fc = strto( sptr, 0p ); sout | fc | sptr; - - char * eptr = 0; - // sptr = "2fred"; - // fc = strto( sptr, &eptr ); - // sout | fc | sptr | eptr; - - sptr = "2 3"; - fc = strto( sptr, &eptr ); - sout | fc | sptr | eptr; - sptr = "-123.4567890123456+123.4567890123456i"; - dc = strto( sptr, 0 ); + dc = strto( sptr, 0p ); sout | dc | sptr; sptr = "123.45678901234567890123456789-123.45678901234567890123456789i"; - ldc = strto( sptr, 0 ); + ldc = strto( sptr, 0p ); + sout | ldc | sptr; + sptr = " 123.45678901234 -123.4567890i "; // spaces allowed + ldc2 = strto( sptr, 0p ); + sout | ldc2 | sptr; + + sptr = "2.0fred"; + char * eptr = 0p; + errno = 0; // reset + f = strto( sptr, &eptr ); + if ( errno == ERANGE ) sout | "out of range"; + if ( eptr == sptr || // conversion failed, no characters generated + *eptr != '\0' ) sout | "invalid argument" | sptr; // not at end of str ? + else assert( false ); + + sptr = "2 3x"; + eptr = 0p; + errno = 0; // reset + fc = strto( sptr, &eptr ); + if ( errno == ERANGE ) sout | "out of range"; + if ( eptr == sptr || // conversion failed, no characters generated + *eptr != '\0' ) sout | "invalid argument" | sptr; // not at end of str ? + else assert( false ); + + // convert + + sptr = "-123"; + i = convert( sptr ); + sout | i | sptr; + sptr = "123"; + ui = convert( sptr ); + sout | ui | sptr; + + sptr = "-123"; + li = convert( sptr ); + sout | li | sptr; + sptr = "123"; + uli = convert( sptr ); + sout | uli | sptr; + + sptr = " -123 "; // spaces allowed + lli = convert( sptr ); + sout | lli | sptr; + sptr = " 123 "; // spaces allowed + ulli = convert( sptr ); + sout | ulli | sptr; + + sptr = "-123.456"; + f = convert( sptr ); + sout | f | sptr; + sptr = "-123.4567890123456"; + d = convert( sptr ); + sout | d | sptr; + sptr = " -123.45678901234567890123456789 "; // spaces allowed + ld = convert( sptr ); + sout | ld | sptr; + + sptr = "-123.456-123.456i"; + fc = convert( sptr ); + sout | fc | sptr; + sptr = "-123.4567890123456+123.4567890123456i"; + dc = convert( sptr ); + sout | dc | sptr; + sptr = "123.45678901234567890123456789-123.45678901234567890123456789i"; + ldc = convert( sptr ); sout | ldc | sptr; sptr = "123.45678901234-123.4567890i"; - ldc2 = strto( sptr, 0 ); + ldc2 = convert( sptr ); sout | ldc2 | sptr; + + sptr = "2.0fred"; + try { + f = convert( sptr ); + assert( false ); + } catch( invalid_argument * ) { + sout | "invalid argument" | sptr; + } // try + + sptr = "2 3x"; + try { + fc = convert( sptr ); + assert( false ); + } catch( invalid_argument * ) { + sout | "invalid argument" | sptr; + } // try } // main