source: doc/theses/jiada_liang_MMath/intro.tex @ 91b9e10

Last change on this file since 91b9e10 was ccfbfd9, checked in by Peter A. Buhr <pabuhr@…>, 6 months ago

more proofreading with respect to Gregor's comments

  • Property mode set to 100644
File size: 14.6 KB
Line 
1\chapter{Introduction}
2
3All 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.
4Constants 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.
5(In \CFA, the constants @0@ and @1@ can be overloaded for any type.)
6A constant's symbolic name is dictated by language syntax related to types.
7In general, the representation of a constant's value is \newterm{opaque}, so the internal representation can be chosen arbitrarily.
8In theory, there are an infinite set of constant names per type representing an infinite set of values.
9
10It is common in mathematics, engineering and computer science to alias new constants to existing constants so they have the same value, \eg $\pi$, $\tau$ (2$\pi$), $\phi$ (golden ratio), K(k), M, G, T for powers of 2\footnote{Overloaded with SI powers of 10.} often prefixing bits (b) or bytes (B), \eg Gb, MB, and in general situations, \eg specific times (noon, New Years), cities (Big Apple), flowers (Lily), \etc.
11An alias can bind to another alias, which transitively binds it to the specified constant.
12Multiple aliases can represent the same value, \eg eighth note and quaver, giving synonyms.
13
14Many 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.
15Its 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.
16Thereafter, changing the aliasing of the new constant to another constant automatically distributes the rebinding, preventing errors.
17% and only equality operations are available, \eg @O_RDONLY@, @O_WRONLY@, @O_CREAT@, @O_TRUNC@, @O_APPEND@.
18Because 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{
19The term rvalue defines an expression that can only appear on the right-hand side of an assignment expression.}.
20In theory, there are an infinite set of possible aliasing, in practice, the number of aliasing per program is finite and small.
21
22Aliased constants can form an (ordered) set, \eg days of a week, months of a year, floors of a building (basement, ground, 1st), colours in a rainbow, \etc.
23In this case, the binding between a constant name and value can be implicit, where the values are chosen to support any set operations.
24Many programming languages capture the aliasing and ordering through a mechanism called an \newterm{enumeration}.
25\begin{quote}
26enumerate (verb, transitive).
27To count, ascertain the number of;
28more usually, to mention (a number of things or persons) separately, as if for the purpose of counting;
29to specify as in a list or catalogue.~\cite{OEDenumerate}
30\end{quote}
31Within an enumeration set, the enumeration names (aliases) must be unique, and instances of an enumerated type are \emph{often} restricted to hold only these names.
32
33It is possible to enumerate among set names without having an ordering among the set values.
34For example, the week, the weekdays, the weekend, and every second day of the week.
35\begin{cfa}[morekeywords={in}]
36for ( cursor in Mon, Tue, Wed, Thu, Fri, Sat, Sun } ... $\C[3.75in]{// week}$
37for ( cursor in Mon, Tue, Wed, Thu, Fri } ...   $\C{// weekday}$
38for ( cursor in Sat, Sun } ...                                  $\C{// weekend}$
39for ( cursor in Mon, Wed, Fri, Sun } ...                $\C{// every second day of week}\CRT$
40\end{cfa}
41A set can have a partial or total ordering, making it possible to compare set elements, \eg Monday is before Friday and Friday is after.
42Ordering allows iterating among the enumeration set using relational operators and advancement, \eg:
43\begin{cfa}
44for ( cursor = Monday; cursor @<=@ Friday; cursor = @succ@( cursor ) ) ...
45\end{cfa}
46Here the values for the set names are logically \emph{generated} rather than listing a subset of names.
47
48Hence, the fundamental aspects of an enumeration are:
49\begin{enumerate}
50\item
51\begin{sloppypar}
52It provides a finite set of new constants, which are implicitly or explicitly assigned values that must be appropriate for any set operations.
53This aspect differentiates an enumeration from general types with an infinite set of constants.
54\end{sloppypar}
55\item
56The alias names are constants, which follows transitively from their binding to other constants.
57\item
58Defines a type for generating instants (variables).
59\item
60For safety, an enumeration instance should be restricted to hold only its constant names.
61\item
62There is a mechanism for \emph{enumerating} over the enumeration names, where the ordering can be implicit from the type, explicitly listed, or generated arithmetically.
63\end{enumerate}
64
65
66\section{Terminology}
67\label{s:Terminology}
68
69The term \newterm{enumeration} defines a type with a set of new constants, and the term \newterm{enumerator} represents an arbitrary alias name \see{\VRef{s:CEnumeration} for the name derivation}.
70As well, an enumerated type can have three fundamental properties, \newterm{label}, \newterm{order}, and \newterm{value}.
71\begin{cquote}
72\sf\setlength{\tabcolsep}{3pt}
73\begin{tabular}{rcccccccr}
74\it\color{red}enumeration       & \multicolumn{8}{c}{\it\color{red}enumerators} \\
75$\downarrow$\hspace*{15pt}      & \multicolumn{8}{c}{$\downarrow$}                              \\
76@enum@ Week \{                          & Mon,  & Tue,  & Wed,  & Thu,  & Fri,  & Sat,  & Sun {\color{red}= 42} & \};   \\
77\it\color{red}label                     & Mon   & Tue   & Wed   & Thu   & Fri   & Sat   & Sun           &               \\
78\it\color{red}order                     & 0             & 1             & 2             & 3             & 4             & 5             & 6                     &               \\
79\it\color{red}value                     & 0             & 1             & 2             & 3             & 4             & 5             & {\color{red}42}               &
80\end{tabular}
81\end{cquote}
82Here, the enumeration @Week@ defines the enumerator constant @Mon@, @Tue@, @Wed@, @Thu@, @Fri@, @Sat@ and @Sun@.
83The implicit ordering implies the successor of @Tue@ is @Mon@ and the predecessor of @Tue@ is @Wed@, independent of any associated enumerator values.
84The value is the implicitly/explicitly assigned constant to support any enumeration operations;
85the value may be hidden (opaque) or visible.
86
87Specifying complex ordering is possible:
88\begin{cfa}
89enum E1 { $\color{red}[\(_1\)$ {A, B}, $\color{blue}[\(_2\)$ C $\color{red}]\(_1\)$, {D, E} $\color{blue}]\(_2\)$ }; $\C{// overlapping square brackets}$
90enum E2 { {A, {B, C} }, { {D, E}, F };  $\C{// nesting}$
91\end{cfa}
92For @E1@, there is the partial ordering among @A@, @B@ and @C@, and @C@, @D@ and @E@, but not among @A@, @B@ and @D@, @E@.
93For @E2@, there is the total ordering @A@ $<$ @{B, C}@ $<$ @{D, E}@ $<$ @F@.
94Only flat total-ordering among enumerators is considered in this work.
95
96
97\section{Motivation}
98
99Many programming languages provide an enumeration-like mechanism, which may or may not cover the previous five fundamental enumeration aspects.
100Hence, the term \emph{enumeration} can be confusing and misunderstood.
101Furthermore, some languages conjoin the enumeration with other type features, making it difficult to tease apart which feature is being used.
102This section discusses some language features that are sometimes called an enumeration but do not provide all enumeration aspects.
103
104
105\subsection{Aliasing}
106\label{s:Aliasing}
107
108Some languages provide simple aliasing (renaming), \eg:
109\begin{cfa}
110const Size = 20, Pi = 3.14159, Name = "Jane";
111\end{cfa}
112The alias name is logically replaced in the program text by its matching constant.
113It is possible to compare aliases, if the constants allow it, \eg @Size < Pi@;
114whereas \eg @Pi < Name@ might be disallowed depending on the language.
115
116Aliasing 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.
117With aliasing, each new name is part of the language, and hence, participates fully, such as name overloading in the type system.
118Aliasing is not an immutable variable, \eg:
119\begin{cfa}
120extern @const@ int Size = 20;
121extern void foo( @const@ int @&@ size );
122foo( Size ); // take the address of (reference) Size
123\end{cfa}
124Taking the address of an immutable variable makes it an \newterm{lvalue}, which implies it has storage.
125With separate compilation, it is necessary to choose one translation unit to perform the initialization.
126If aliasing does require storage, its address and initialization are opaque (compiler only), similar to \CC rvalue reference @&&@.
127
128Aliasing does provide readability and automatic resubstitution.
129It also provides simple enumeration properties, but with effort.
130\begin{cfa}
131const Mon = 1, Tue = 2, Wed = 3, Thu = 4, Fri = 5, Sat = 6, Sun = 7;
132\end{cfa}
133Any reordering of the enumerators requires manual renumbering.
134\begin{cfa}
135const Sun = 1, Mon = 2, Tue = 3, Wed = 4, Thu = 5, Fri = 6, Sat = 7;
136\end{cfa}
137For these reasons, aliasing is sometimes called an enumeration.
138However, there is no type to create a type-checked instance or iterator cursor, so there is no ability for enumerating.
139Hence, there are multiple enumeration aspects not provided by aliasing, justifying a separate enumeration type in a programming language.
140
141
142\subsection{Algebraic Data Type}
143\label{s:AlgebraicDataType}
144
145An algebraic data type (ADT)\footnote{ADT is overloaded with abstract data type.} is another language feature often linked with enumeration, where an ADT conjoins an arbitrary type, possibly a \lstinline[language=C++]{class} or @union@, and a named constructor.
146For example, in Haskell:
147\begin{haskell}
148data S = S { i::Int, d::Double }                $\C{// structure}$
149data @Foo@ = A Int | B Double | C S             $\C{// ADT, composed of three types}$
150foo = A 3;                                                              $\C{// type Foo is inferred}$
151bar = B 3.5
152baz = C S{ i = 7, d = 7.5 }
153\end{haskell}
154the ADT has three variants (constructors), @A@, @B@, @C@ with associated types @Int@, @Double@, and @S@.
155The constructors create an initialized value of the specific type that is bound to the immutable variables @foo@, @bar@, and @baz@.
156Hence, 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.
157\begin{cquote}
158\setlength{\tabcolsep}{15pt}
159\begin{tabular}{@{}ll@{}}
160\begin{haskell}
161prtfoo val = -- function
162    -- pattern match on constructor
163    case val of
164      @A@ a -> print a
165      @B@ b -> print b
166      @C@ (S i d) -> do
167          print i
168          print d
169\end{haskell}
170&
171\begin{haskell}
172main = do
173    prtfoo foo
174    prtfoo bar
175    prtfoo baz
1763
1773.5
1787
1797.5
180\end{haskell}
181\end{tabular}
182\end{cquote}
183For safety, most languages require all associated types to be listed or a default case with no field accesses.
184
185A less frequent case is multiple constructors with the same type.
186\begin{haskell}
187data Bar = X Int | Y Int | Z Int;
188foo = X 3;
189bar = Y 3;
190baz = Z 5;
191\end{haskell}
192Here, the constructor name gives different meaning to the values in the common \lstinline[language=Haskell]{Int} type, \eg the value @3@ has different interpretations depending on the constructor name in the pattern matching.
193
194Note, the term \newterm{variant} is often associated with ADTs.
195However, there are multiple languages with a @variant@ type that is not an ADT \see{Algol68~\cite{Algol68} or \CC \lstinline{variant}}.
196In these languages, the variant is often a union using RTTI tags for discrimination, which cannot be used to simulate an enumeration.
197Hence, in this work the term variant is not a synonym for ADT.
198
199% https://downloads.haskell.org/ghc/latest/docs/libraries/base-4.19.1.0-179c/GHC-Enum.html
200% https://hackage.haskell.org/package/base-4.19.1.0/docs/GHC-Enum.html
201
202The association between ADT and enumeration occurs if all the constructors have a unit (empty) type, \eg @struct unit {}@.
203Note, the unit type is not the same as \lstinline{void}, \eg:
204\begin{cfa}
205void foo( void );
206struct unit {} u;  // empty type
207unit bar( unit );
208foo( foo() );        // void argument does not match with void parameter
209bar( bar( u ) );   // unit argument does match with unit parameter
210\end{cfa}
211
212For example, in the Haskell ADT:
213\begin{haskell}
214data Week = Mon | Tue | Wed | Thu | Fri | Sat | Sun deriving(Enum, Eq, Show)
215\end{haskell}
216the 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.
217The nullary constructors for the unit types are numbered left-to-right from $0$ to @maxBound@$- 1$, and provides enumerating operations @succ@, @pred@, @enumFrom@ @enumFromTo@.
218\VRef[Figure]{f:HaskellEnumeration} shows enumeration comparison and iterating (enumerating).
219
220\begin{figure}
221\begin{cquote}
222\setlength{\tabcolsep}{15pt}
223\begin{tabular}{@{}ll@{}}
224\begin{haskell}
225day = Tue
226main = do
227    if day == Tue then
228        print day
229    else
230        putStr "not Tue"
231    print (enumFrom Mon)            -- week
232    print (enumFromTo Mon Fri)   -- weekday
233    print (enumFromTo Sat Sun)  -- weekend
234\end{haskell}
235&
236\begin{haskell}
237Tue
238[Mon,Tue,Wed,Thu,Fri,Sat,Sun]
239[Mon,Tue,Wed,Thu,Fri]
240[Sat,Sun]
241
242
243
244
245
246\end{haskell}
247\end{tabular}
248\end{cquote}
249\caption{Haskell Enumeration}
250\label{f:HaskellEnumeration}
251\end{figure}
252
253The 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.
254While the enumeration is constructed using the ADT mechanism, it is so restricted it is not an ADT.
255Furthermore, a general ADT cannot be an enumeration because the constructors generate different values making enumerating meaningless.
256While functional programming languages regularly repurpose the ADT type into an enumeration type, this process seems contrived and confusing.
257Hence, there is only a weak equivalence between an enumeration and ADT, justifying a separate enumeration type in a programming language.
258
259
260\section{Contributions}
261
262The goal of this work is to to extend 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.
263On the surface, enumerations seem like a simple type.
264However, when extended with advanced features, enumerations become complex for both the type system and the runtime implementation.
265
266The contribution of this work are:
267\begin{enumerate}
268\item
269overloading
270\item
271scoping
272\item
273typing
274\item
275subseting
276\item
277inheritance
278\end{enumerate}
Note: See TracBrowser for help on using the repository browser.