Index: doc/theses/jiada_liang_MMath/intro.tex =================================================================== --- doc/theses/jiada_liang_MMath/intro.tex (revision 8789ae481e3c9f5d1643c516232faf5d3834d566) +++ doc/theses/jiada_liang_MMath/intro.tex (revision 433e2c3fb7ad367e63441101bb26ac863372e64e) @@ -1,9 +1,15 @@ \chapter{Introduction} -All types in a programming language have a set of constants (symbols), and these constants represent values, \eg integer types have constants @-1@, @17@, @0xff@ representing whole numbers, floating-point types have constants @5.3@, @2.3E-5@, @0xff.ffp0@ representing real numbers, character types have constants @'a'@, @"abc\n"@, \mbox{\lstinline{u8"}\texttt{\guillemotleft{na\"{i}ve}\guillemotright}\lstinline{"}} representing (human readable) text, \etc. +All basic types in a programming language have a set of constants (symbols), and these constants represent computable values, \eg integer types have constants @-1@, @17@, @0xff@ representing whole numbers, floating-point types have constants @5.3@, @2.3E-5@, @0xff.ffp0@ representing real numbers, character types have constants @'a'@, @"abc\n"@, \mbox{\lstinline{u8"}\texttt{\guillemotleft{na\"{i}ve}\guillemotright}\lstinline{"}} representing (human readable) text, \etc. Constants can be overloaded among types, \eg @0@ is a null pointer for all pointer types, and the value zero for integer and floating-point types. (In \CFA, the constants @0@ and @1@ can be overloaded for any type.) +Higher-level types compose constants from the basic constants. +\begin{cfa} +struct S { int i, j, k; } s; +s = (S){ 1, 2, 3 }; $\C[2in]{// structure constant}$ +int x[5] = { 1, 2, 3, 4, 5 }; $\C{// array constant}\CRT$ +\end{cfa} A constant's symbolic name is dictated by language syntax related to types, \eg @5.@ (double), @5.0f@ (float), @5l@ (long double). -In general, the representation of a constant's value is \newterm{opaque}, so the internal representation can be chosen arbitrarily. +In general, the representation of a constant's value is \newterm{opaque}, so the internal representation can be chosen arbitrarily, \eg two's complement, IEEE floating-point. In theory, there are an infinite set of constant names per type representing an infinite set of values. @@ -13,7 +19,6 @@ Many programming languages capture this important software-engineering capability through a mechanism called \newterm{constant} or \newterm{literal} naming, where a new constant is aliased to an existing constant. -Its purpose is for readability: replacing a constant name that directly represents a value with a name that is more symbolic and meaningful in the context of the program. -Thereafter, changing the aliasing of the new constant to another constant automatically distributes the rebinding, preventing errors. -% and only equality operations are available, \eg @O_RDONLY@, @O_WRONLY@, @O_CREAT@, @O_TRUNC@, @O_APPEND@. +Its purpose is for readability: replacing constant values in a program with symbolic names that are more meaningful to programmers in the context of the application. +Thereafter, associating a name to a different value automatically distributes this rebinding, preventing errors. Because an aliased 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.}. @@ -39,8 +44,8 @@ for ( cursor in Mon, Wed, Fri, Sun } ... $\C{// every second day of week}\CRT$ \end{cfa} -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. +A set can have a partial or total ordering, making it possible to compare set elements, \eg Monday is before Tuesday and Tuesday 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 ) ) ... +for ( cursor = Monday; cursor @<=@ Friday; cursor = @succ@( cursor ) ) ... // weekdays \end{cfa} Here the values for the set names are logically \emph{generated} rather than listing a subset of names. @@ -50,5 +55,5 @@ \item \begin{sloppypar} -It provides a finite set of new constants, which are implicitly or explicitly assigned values that must be appropriate for any set operations. +It provides a finite set of new constants, which are implicitly or explicitly assigned values that must be appropriate for any set operations, \eg increasing order. This aspect differentiates an enumeration from general types with an infinite set of constants. \end{sloppypar} @@ -106,5 +111,5 @@ \label{s:Aliasing} -Some languages provide simple aliasing (renaming), \eg: +Some languages provide simple aliasing (renaming). \begin{cfa} const Size = 20, Pi = 3.14159, Name = "Jane"; @@ -113,7 +118,7 @@ It is possible to compare aliases, if the constants allow it, \eg @Size < Pi@, whereas @Pi < Name@ might be disallowed depending on the language. -Aliasing is not macro substitution, \eg @#define Size 20@, where a name is replaced by its value \emph{before} compilation, so the name is invisible to the programming language. +Aliasing is \emph{not} macro substitution, \eg @#define Size 20@, where a name is replaced by its value \emph{before} compilation, so the name is invisible to the programming language. With aliasing, each new name is part of the language, and hence, participates fully, such as name overloading in the type system. -Aliasing is not an immutable variable, \eg: +Aliasing is not an immutable variable. \begin{cfa} extern @const@ int Size = 20; @@ -123,5 +128,5 @@ Taking the address of an immutable variable makes it an \newterm{lvalue}, which implies it has storage. With separate compilation, it is necessary to choose one translation unit to perform the initialization. -If aliasing does require storage, its address and initialization are opaque (compiler only), similar to \CC rvalue reference @&&@. +If aliasing requires storage, its address and initialization are opaque (compiler only), similar to \CC rvalue reference @&&@. Aliasing does provide readability and automatic resubstitution. @@ -151,26 +156,26 @@ baz = C S{ i = 7, d = 7.5 } \end{haskell} -the ADT has three variants (constructors), @A@, @B@, @C@ with associated types @Int@, @Double@, and @S@. +the ADT has three variants (constructors), @A@, @B@, @C@, with associated types @Int@, @Double@, and @S@. The constructors create an initialized value of the specific type that is bound to the immutable variables @foo@, @bar@, and @baz@. Hence, the ADT @Foo@ is like a union containing values of the associated types, and a constructor name is used to intialize and access the value using dynamic pattern-matching. \begin{cquote} -\setlength{\tabcolsep}{15pt} +\setlength{\tabcolsep}{20pt} \begin{tabular}{@{}ll@{}} \begin{haskell} prtfoo val = -- function - -- pattern match on constructor - case val of - @A@ a -> print a - @B@ b -> print b - @C@ (S i d) -> do - print i - print d + -- pattern match on constructor + case val of + @A@ a -> print a + @B@ b -> print b + @C@ (S i d) -> do + print i + print d \end{haskell} & \begin{haskell} main = do - prtfoo foo - prtfoo bar - prtfoo baz + prtfoo foo + prtfoo bar + prtfoo baz 3 3.5 @@ -193,6 +198,34 @@ Note, the term \newterm{variant} is often associated with ADTs. However, there are multiple languages with a @variant@ type that is not an ADT \see{Algol68~\cite{Algol68} or \CC \lstinline{variant}}. -In these languages, the variant is often a union using RTTI tags for discrimination, which cannot be used to simulate an enumeration. +Here, the type (and possibly the position for equivalent types) is used to discriminant the specific \emph{variant} within the variant instance. +For example, \VRef[Figure]{f:C++variant} shows the \CC equivalent of the two Haskell ADT types using variant types. +In these languages, the variant cannot be used to simulate an enumeration. Hence, in this work the term variant is not a synonym for ADT. + +\begin{figure} +\begin{c++} +struct S { char s[32]; }; +variant< int, double, S > vd; +variant< int, int, int > vs; + +// discrimination based on type +vd = 3; +if ( holds_alternative(vd) ) cout << "int " << get(vd ) << endl; +vd = 3.5; +if ( holds_alternative(vd) ) cout << "double " << get(vd) << endl; +vd = (S){ "abc" }; +if ( holds_alternative(vd) ) cout << "S.s " << get(vd).s << endl; + +// discrimination based on type and position within type +vs = (variant){ in_place_index<0>, 12 }; +if ( vs.index() == 0 ) cout << "posn 0 " << get<0>(vs) << endl; +vs = (variant){ in_place_index<1>, 4 }; +if ( vs.index() == 1 ) cout << "posn 1 " << get<1>(vs) << endl; +vs = (variant){ in_place_index<2>, 5 }; +if ( vs.index() == 2 ) cout << "posn 2 " << get<2>(vs) << endl; +\end{c++} +\caption{\CC \lstinline[language=C++]{variant} Discrimination Using RTTI/Position} +\label{f:C++variant} +\end{figure} % https://downloads.haskell.org/ghc/latest/docs/libraries/base-4.19.1.0-179c/GHC-Enum.html @@ -200,10 +233,10 @@ The association between ADT and enumeration occurs if all the constructors have a unit (empty) type, \eg @struct unit {}@. -Note, the unit type is not the same as \lstinline{void}, \eg: +Note, the unit type is not the same as \lstinline{void}. \begin{cfa} void foo( void ); struct unit {} u; $\C[1.5in]{// empty type}$ unit bar( unit ); -foo( foo() ); $\C{// void argument does not match with void parameter}$ +foo( @foo()@ ); $\C{// void argument does not match with void parameter}$ bar( bar( u ) ); $\C{// unit argument does match with unit parameter}\CRT$ \end{cfa} @@ -214,21 +247,21 @@ \end{haskell} the default type for each constructor is the unit type, and deriving from @Enum@ enforces no other associated types, @Eq@ allows equality comparison, and @Show@ is for printing. -The nullary constructors for the unit types are numbered left-to-right from $0$ to @maxBound@$- 1$, and provides enumerating operations @succ@, @pred@, @enumFrom@ @enumFromTo@. +The nullary constructors for the unit types are numbered left-to-right from $0$ to @maxBound@$- 1$, and provides enumerating operations @succ@, @pred@, @enumFrom@, @enumFromTo@. \VRef[Figure]{f:HaskellEnumeration} shows enumeration comparison and iterating (enumerating). \begin{figure} \begin{cquote} -\setlength{\tabcolsep}{15pt} +\setlength{\tabcolsep}{40pt} \begin{tabular}{@{}ll@{}} \begin{haskell} day = Tue main = do - if day == Tue then - print day - else - putStr "not Tue" - print (enumFrom Mon) -- week - print (enumFromTo Mon Fri) -- weekday - print (enumFromTo Sat Sun) -- weekend + if day == Tue then + print day + else + putStr "not Tue" + print (enumFrom Mon) $\C[2.25in]{-- week}$ + print (enumFromTo Mon Fri) $\C{-- weekday}$ + print (enumFromTo Sat Sun) $\C{-- weekend}\CRT$ \end{haskell} & @@ -251,5 +284,5 @@ The key observation is the dichotomy between an ADT and enumeration: the ADT uses the associated type resulting in a union-like data structure, and the enumeration does not use the associated type, and hence, is not a union. -While an enumeration is constructed using the ADT mechanism, it is so restricted it is not an ADT. +In contrast, an enumeration may be constructed using the ADT mechanism, but it is so restricted it is not an ADT. Furthermore, a general ADT cannot be an enumeration because the constructors generate different values making enumerating meaningless. While functional programming languages regularly repurpose the ADT type into an enumeration type, this process seems contrived and confusing. @@ -266,5 +299,5 @@ \begin{enumerate} \item -overloading +overloading: \item scoping Index: doc/theses/jiada_liang_MMath/uw-ethesis-frontpgs.tex =================================================================== --- doc/theses/jiada_liang_MMath/uw-ethesis-frontpgs.tex (revision 8789ae481e3c9f5d1643c516232faf5d3834d566) +++ doc/theses/jiada_liang_MMath/uw-ethesis-frontpgs.tex (revision 433e2c3fb7ad367e63441101bb26ac863372e64e) @@ -131,16 +131,25 @@ \begin{center}\textbf{Abstract}\end{center} -% An enumeration is a type defining an ordered set of named constant values, where a name abstracts a value, \eg @PI@ versus @3.145159@. -% C restrict an enumeration type to the integral type @signed int@, which \CC support, meaning enumeration names bind to integer constants. -% \CFA extends C enumerations to allow all basic and custom types for the enumeration type, like other modern programming languages. -% Furthermore, \CFA adds other useful features for enumerations to support better software-engineering practices and simplify program development. -The \CFA (C-for-all) programming language is an evolutionary refinement of C programing language. One of its distinctive feature is the generic -types. But legacy data type from C, such as enumerations, does not adapt well into the \CFA generic type system. - -This thesis presents an adaptation of enumerated types, in a way that integrates naturallly with the generic type feature of \CFA while being -backward-compatiable to C. This thesis also presents a number of smaller refinement to the \CFA overload resolution rules for enumerated types, -each of which improves the intuitive nature of enumerations. -The enumeration types improvement has been implemented into \CFA compiler and run-time environment. The root ideas behinds the change of -enumeration is to discover the approach of C data types working with \CFA generic types in order to improve the language expressiveity and safety. +An \emph{enumeration} is a type defining a (ordered) set of named constant values. +\begin{cfa} +enum Week { Mon, Tue, Wed, Thu, Fri, Sat, Sun }; +enum Math { PI = 3.14159, Tau = 6.28318, Phi = 1.61803 }; +enum RGB { Red = 100b, Green = 010b, Blue = 001b }; +\end{cfa} +Its purpose is for readability: replacing constant values in a program with symbolic names that are more meaningful to programmers in the context of the application. +Thereafter, associating a name to a different value automatically distributes this rebinding, preventing errors. +One of the key properties of an enumeration is the ability to enumerate (iterate) through the constants, and hence, access their values, if present. +C restricts an enumeration to the integral type @signed int@, while \CC extends enumerations to all integral types, meaning enumeration names must bind to integer constants. +Other modern programming languages provide bindings to any type and additional features to extend enumeration capabilities for better software-engineering practices. + +The \CFA (C-for-all) programming language is an evolutionary refinement of the C programing language. +One of its distinctive feature is a parametric-polymorphic generic type. +However, legacy data types from C, such as enumerations, do not adapt well into the \CFA generic type-system. + +This thesis extends the simple and unsafe enumeration type in the C programming language into a complex and safe enumeration type in the \CFA programming-language, while maintaining backwards compatibility with C. +The major contribution is an adaptation of enumerated types with the \CFA type-system in a way that integrates naturally with the generic types. +This thesis also presents a number of smaller refinement to the \CFA overload resolution rules for enumerated types, each of which improves the intuitive nature of enumeration name resolution by the compiler. +Finally, this work adds other useful features to enumerations that better support software-engineering practices and simplify program development. + \cleardoublepage \phantomsection % allows hyperref to link to the correct page @@ -151,13 +160,14 @@ \begin{center}\textbf{Acknowledgements}\end{center} -To begin, I would like to thank my supervisor Proferssor Peter Buhr. Thank you for your guidance and -support throughout my study and research. I would not be here without you. - -Thanks Gregor Richards and Yzihou Zhang for reading my thesis. +To begin, I would like to thank my supervisor Professor Peter Buhr. +Thank you for your guidance and support throughout my study and research. +I would not be here without you. + +Thanks to Gregor Richards and Yzihou Zhang for reading my thesis. Special thanks to Andrew James Beach for your insight on the theory development on the thesis. Thanks to Michael Brooks, Fangran Yu, Colby Parsons, Thierry Delisle, Mubeen Zulifiqar, - and entire Cforall team for development of the \CFA language, making it the best language it can be. +and the entire \CFA team for development of the \CFA language, making it the best language it can be. Finally, a special thank you to Huawei Canada for funding this work.