Changes in doc/rob_thesis/intro.tex [0111dc7:12d3187]

File:

• doc/rob_thesis/intro.tex (modified) (14 diffs)

doc/rob_thesis/intro.tex

@@ -19 +19 @@
 Unfortunately, \CC is actively diverging from C, so incremental additions require significant effort and training, coupled with multiple legacy design-choices that cannot be updated.
 
-The remainder of this section describes some of the important new features that currently exist in \CFA, to give the reader the necessary context in which the new features presented in this thesis must dovetail.
+The current implementation of \CFA is a source-to-source translator from \CFA to GNU C \cite{GCCExtensions}.
+
+The remainder of this section describes some of the important features that currently exist in \CFA, to give the reader the necessary context in which the new features presented in this thesis must dovetail.
 
 \subsection{C Background}
 \label{sub:c_background}
+In the context of this work, the term \emph{object} refers to a region of data storage in the execution environment, the contents of which can represent values \cite[p.~6]{C11}.
+
 One of the lesser-known features of standard C is \emph{designations}.
 Designations are similar to named parameters in languages such as Python and Scala, except that they only apply to aggregate initializers.
+Note that in \CFA, designations use a colon separator, rather than an equals sign as in C, because this syntax is one of the few places that conflicts with the new language features.
 \begin{cfacode}
 struct A {
@@ -43 +48 @@
 Later initializers override earlier initializers, so a sub-object for which there is more than one initializer is only initialized by its last initializer.
 These semantics can be seen in the initialization of @a0@, where @x@ is designated twice, and thus initialized to @8@.
-Note that in \CFA, designations use a colon separator, rather than an equals sign as in C, because this syntax is one of the few places that conflicts with the new language features.
 
 C also provides \emph{compound literal} expressions, which provide a first-class mechanism for creating unnamed objects.
@@ -57 +61 @@
 Compound literals create an unnamed object, and result in an lvalue, so it is legal to assign a value into a compound literal or to take its address \cite[p.~86]{C11}.
 Syntactically, compound literals look like a cast operator followed by a brace-enclosed initializer, but semantically are different from a C cast, which only applies basic conversions and coercions and is never an lvalue.
+
+The \CFA translator makes use of several GNU C extensions, including \emph{nested functions} and \emph{attributes}.
+Nested functions make it possible to access data that is lexically in scope in the nested function's body.
+\begin{cfacode}
+int f() {
+  int x = 0;
+  void g() {
+    x++;
+  }
+  g();  // changes x
+}
+\end{cfacode}
+Nested functions come with the usual C caveat that they should not leak into the containing environment, since they are only valid as long as the containing function's stack frame is active.
+
+Attributes make it possible to inform the compiler of certain properties of the code.
+For example, a function can be marked as deprecated, so that legacy APIs can be identified and slowly removed, or as \emph{hot}, so that the compiler knows the function is called frequently and should be aggresively optimized.
+\begin{cfacode}
+__attribute__((deprecated("foo is deprecated, use bar instead")))
+void foo();
+__attribute__((hot)) void bar(); // heavily optimized
+
+foo();  // warning
+bar();
+\end{cfacode}
 
 \subsection{Overloading}
@@ -64 +92 @@
 C provides a small amount of built-in overloading, \eg + is overloaded for the basic types.
 Like in \CC, \CFA allows user-defined overloading based both on the number of parameters and on the types of parameters.
-  \begin{cfacode}
-  void f(void);  // (1)
-  void f(int);   // (2)
-  void f(char);  // (3)
-
-  f('A');        // selects (3)
-  \end{cfacode}
+\begin{cfacode}
+void f(void);  // (1)
+void f(int);   // (2)
+void f(char);  // (3)
+
+f('A');        // selects (3)
+\end{cfacode}
 In this case, there are three @f@ procedures, where @f@ takes either 0 or 1 arguments, and if an argument is provided then it may be of type @int@ or of type @char@.
 Exactly which procedure is executed depends on the number and types of arguments passed.
 If there is no exact match available, \CFA attempts to find a suitable match by examining the C built-in conversion heuristics.
-  \begin{cfacode}
-  void g(long long);
-
-  g(12345);
-  \end{cfacode}
+The \CFA expression resolution algorithm uses a cost function to determine the interpretation that uses the fewest conversions and polymorphic type bindings.
+\begin{cfacode}
+void g(long long);
+
+g(12345);
+\end{cfacode}
 In the above example, there is only one instance of @g@, which expects a single parameter of type @long long@.
 Here, the argument provided has type @int@, but since all possible values of type @int@ can be represented by a value of type @long long@, there is a safe conversion from @int@ to @long long@, and so \CFA calls the provided @g@ routine.
 
+Overloading solves the problem present in C where there can only be one function with a given name, requiring multiple names for functions that perform the same operation but take in different types.
+This can be seen in the example of the absolute value functions C:
+\begin{cfacode}
+// stdlib.h
+int abs(int);
+long int labs(long int);
+long long int llabs(long long int);
+\end{cfacode}
+In \CFA, the functions @labs@ and @llabs@ are replaced by appropriate overloads of @abs@.
+
 In addition to this form of overloading, \CFA also allows overloading based on the number and types of \emph{return} values.
 This extension is a feature that is not available in \CC, but is available in other programming languages such as Ada \cite{Ada95}.
-  \begin{cfacode}
-  int g();         // (1)
-  double g();      // (2)
-
-  int x = g();     // selects (1)
-  \end{cfacode}
+\begin{cfacode}
+int g();         // (1)
+double g();      // (2)
+
+int x = g();     // selects (1)
+\end{cfacode}
 Here, the only difference between the signatures of the different versions of @g@ is in the return values.
 The result context is used to select an appropriate routine definition.
 In this case, the result of @g@ is assigned into a variable of type @int@, so \CFA prefers the routine that returns a single @int@, because it is an exact match.
+
+Return-type overloading solves similar problems to parameter-list overloading, in that multiple functions that perform similar operations can have the same, but produce different values.
+One use case for this feature is to provide two versions of the @bsearch@ routine:
+\begin{cfacode}
+forall(otype T | { int ?<?( T, T ); })
+T * bsearch(T key, const T * arr, size_t dimension) {
+  int comp(const void * t1, const void * t2) {
+    return *(T *)t1 < *(T *)t2 ? -1 : *(T *)t2 < *(T *)t1 ? 1 : 0;
+  }
+  return (T *)bsearch(&key, arr, dimension, sizeof(T), comp);
+}
+forall(otype T | { int ?<?( T, T ); })
+unsigned int bsearch(T key, const T * arr, size_t dimension) {
+  T *result = bsearch(key, arr, dimension);
+  // pointer subtraction includes sizeof(T)
+  return result ? result - arr : dimension;
+}
+double key = 5.0;
+double vals[10] = { /* 10 floating-point values */ };
+
+double * val = bsearch( 5.0, vals, 10 ); // selection based on return type
+int posn = bsearch( 5.0, vals, 10 );
+\end{cfacode}
+The first version provides a thin wrapper around the C @bsearch@ routine, converting untyped @void *@ to the polymorphic type @T *@, allowing the \CFA compiler to catch errors when the type of @key@, @arr@, and the target at the call-site do not agree.
+The second version provides an alternate return of the index in the array of the selected element, rather than its address.
 
 There are times when a function should logically return multiple values.
@@ -145 +209 @@
 
 An extra quirk introduced by multiple return values is in the resolution of function calls.
-  \begin{cfacode}
-  int f();            // (1)
-  [int, int] f();     // (2)
-
-  void g(int, int);
-
-  int x, y;
-  [x, y] = f();       // selects (2)
-  g(f());             // selects (2)
-  \end{cfacode}
+\begin{cfacode}
+int f();            // (1)
+[int, int] f();     // (2)
+
+void g(int, int);
+
+int x, y;
+[x, y] = f();       // selects (2)
+g(f());             // selects (2)
+\end{cfacode}
 In this example, the only possible call to @f@ that can produce the two @int@s required for assigning into the variables @x@ and @y@ is the second option.
 A similar reasoning holds calling the function @g@.
+
+This duality between aggregation and aliasing can be seen in the C standard library in the @div@ and @remquo@ functions, which return the quotient and remainder for a division of integer and floating-point values, respectively.
+\begin{cfacode}
+typedef struct { int quo, rem; } div_t; // from stdlib.h
+div_t div( int num, int den );
+double remquo( double num, double den, int * quo );
+div_t qr = div( 13, 5 );            // return quotient/remainder aggregate
+int q;
+double r = remquo( 13.5, 5.2, &q ); // return remainder, alias quotient
+\end{cfacode}
+@div@ aggregates the quotient/remainder in a structure, while @remquo@ aliases a parameter to an argument.
+Alternatively, a programming language can directly support returning multiple values, \eg in \CFA:
+\begin{lstlisting}
+[int, int] div(int num, int den);               // return two integers
+[double, double] div( double num, double den ); // return two doubles
+int q, r;                     // overloaded variable names
+double q, r;
+[q, r] = div(13, 5);          // select appropriate div and q, r
+[q, r] = div(13.5, 5.2);
+\end{lstlisting}
 
 In \CFA, overloading also applies to operator names, known as \emph{operator overloading}.
 Similar to function overloading, a single operator is given multiple meanings by defining new versions of the operator with different signatures.
 In \CC, this can be done as follows
-  \begin{cppcode}
-  struct A { int i; };
-  int operator+(A x, A y);
-  bool operator<(A x, A y);
-  \end{cppcode}
+\begin{cppcode}
+struct A { int i; };
+A operator+(A x, A y);
+bool operator<(A x, A y);
+\end{cppcode}
 
 In \CFA, the same example can be written as follows.
-  \begin{cfacode}
-  struct A { int i; };
-  int ?+?(A x, A y);    // '?'s represent operands
-  bool ?<?(A x, A y);
-  \end{cfacode}
+\begin{cfacode}
+struct A { int i; };
+A ?+?(A x, A y);    // '?'s represent operands
+int ?<?(A x, A y);
+\end{cfacode}
 Notably, the only difference is syntax.
 Most of the operators supported by \CC for operator overloading are also supported in \CFA.
@@ -179 +263 @@
 Finally, \CFA also permits overloading variable identifiers.
 This feature is not available in \CC.
-  \begin{cfacode}
-  struct Rational { int numer, denom; };
-  int x = 3;               // (1)
-  double x = 1.27;         // (2)
-  Rational x = { 4, 11 };  // (3)
-
-  void g(double);
-
-  x += 1;                  // chooses (1)
-  g(x);                    // chooses (2)
-  Rational y = x;          // chooses (3)
-  \end{cfacode}
+\begin{cfacode}
+struct Rational { int numer, denom; };
+int x = 3;               // (1)
+double x = 1.27;         // (2)
+Rational x = { 4, 11 };  // (3)
+
+void g(double);
+
+x += 1;                  // chooses (1)
+g(x);                    // chooses (2)
+Rational y = x;          // chooses (3)
+\end{cfacode}
 In this example, there are three definitions of the variable @x@.
 Based on the context, \CFA attempts to choose the variable whose type best matches the expression context.
@@ -208 +292 @@
 Due to these rewrite rules, the values @0@ and @1@ have the types \zero and \one in \CFA, which allow for overloading various operations that connect to @0@ and @1@ \footnote{In the original design of \CFA, @0@ and @1@ were overloadable names \cite[p.~7]{cforall}.}.
 The types \zero and \one have special built-in implicit conversions to the various integral types, and a conversion to pointer types for @0@, which allows standard C code involving @0@ and @1@ to work as normal.
-  \begin{cfacode}
-  // lvalue is similar to returning a reference in C++
-  lvalue Rational ?+=?(Rational *a, Rational b);
-  Rational ?=?(Rational * dst, zero_t) {
-    return *dst = (Rational){ 0, 1 };
-  }
-
-  Rational sum(Rational *arr, int n) {
-    Rational r;
-    r = 0;     // use rational-zero_t assignment
-    for (; n > 0; n--) {
-      r += arr[n-1];
-    }
-    return r;
-  }
-  \end{cfacode}
+\begin{cfacode}
+// lvalue is similar to returning a reference in C++
+lvalue Rational ?+=?(Rational *a, Rational b);
+Rational ?=?(Rational * dst, zero_t) {
+  return *dst = (Rational){ 0, 1 };
+}
+
+Rational sum(Rational *arr, int n) {
+  Rational r;
+  r = 0;     // use rational-zero_t assignment
+  for (; n > 0; n--) {
+    r += arr[n-1];
+  }
+  return r;
+}
+\end{cfacode}
 This function takes an array of @Rational@ objects and produces the @Rational@ representing the sum of the array.
 Note the use of an overloaded assignment operator to set an object of type @Rational@ to an appropriate @0@ value.
@@ -232 +316 @@
 In particular, \CFA supports the notion of parametric polymorphism.
 Parametric polymorphism allows a function to be written generically, for all values of all types, without regard to the specifics of a particular type.
-For example, in \CC, the simple identity function for all types can be written as
-  \begin{cppcode}
-  template<typename T>
-  T identity(T x) { return x; }
-  \end{cppcode}
-\CC uses the template mechanism to support parametric polymorphism. In \CFA, an equivalent function can be written as
-  \begin{cfacode}
-  forall(otype T)
-  T identity(T x) { return x; }
-  \end{cfacode}
+For example, in \CC, the simple identity function for all types can be written as:
+\begin{cppcode}
+template<typename T>
+T identity(T x) { return x; }
+\end{cppcode}
+\CC uses the template mechanism to support parametric polymorphism. In \CFA, an equivalent function can be written as:
+\begin{cfacode}
+forall(otype T)
+T identity(T x) { return x; }
+\end{cfacode}
 Once again, the only visible difference in this example is syntactic.
 Fundamental differences can be seen by examining more interesting examples.
-In \CC, a generic sum function is written as follows
-  \begin{cppcode}
-  template<typename T>
-  T sum(T *arr, int n) {
-    T t;  // default construct => 0
-    for (; n > 0; n--) t += arr[n-1];
-    return t;
-  }
-  \end{cppcode}
+In \CC, a generic sum function is written as follows:
+\begin{cppcode}
+template<typename T>
+T sum(T *arr, int n) {
+  T t;  // default construct => 0
+  for (; n > 0; n--) t += arr[n-1];
+  return t;
+}
+\end{cppcode}
 Here, the code assumes the existence of a default constructor, assignment operator, and an addition operator over the provided type @T@.
 If any of these required operators are not available, the \CC compiler produces an error message stating which operators could not be found.
 
-A similar sum function can be written in \CFA as follows
-  \begin{cfacode}
-  forall(otype T | **R**{ T ?=?(T *, zero_t); T ?+=?(T *, T); }**R**)
-  T sum(T *arr, int n) {
-    T t = 0;
-    for (; n > 0; n--) t = t += arr[n-1];
-    return t;
-  }
-  \end{cfacode}
+A similar sum function can be written in \CFA as follows:
+\begin{cfacode}
+forall(otype T | **R**{ T ?=?(T *, zero_t); T ?+=?(T *, T); }**R**)
+T sum(T *arr, int n) {
+  T t = 0;
+  for (; n > 0; n--) t = t += arr[n-1];
+  return t;
+}
+\end{cfacode}
 The first thing to note here is that immediately following the declaration of @otype T@ is a list of \emph{type assertions} that specify restrictions on acceptable choices of @T@.
 In particular, the assertions above specify that there must be an assignment from \zero to @T@ and an addition assignment operator from @T@ to @T@.
 The existence of an assignment operator from @T@ to @T@ and the ability to create an object of type @T@ are assumed implicitly by declaring @T@ with the @otype@ type-class.
 In addition to @otype@, there are currently two other type-classes.
+
+@dtype@, short for \emph{data type}, serves as the top type for object types; any object type, complete or incomplete, can be bound to a @dtype@ type variable.
+To contrast, @otype@, short for \emph{object type}, is a @dtype@ with known size, alignment, and an assignment operator, and thus bind only to complete object types.
+With this extra information, complete objects can be used in polymorphic code in the same way they are used in monomorphic code, providing familiarity and ease of use.
+The third type-class is @ftype@, short for \emph{function type}, matching only function types.
 The three type parameter kinds are summarized in \autoref{table:types}
 
@@ -275 +364 @@
     \begin{tabular}{|c||c|c|c||c|c|c|}
                                                                                                     \hline
-    name    & object type & incomplete type & function type & can assign value & can create & has size \\ \hline
+    name    & object type & incomplete type & function type & can assign & can create & has size \\ \hline
     @otype@ & X           &                 &               & X                & X          & X        \\ \hline
     @dtype@ & X           & X               &               &                  &            &          \\ \hline
@@ -288 +377 @@
 In contrast, the explicit nature of assertions allows \CFA's polymorphic functions to be separately compiled, as the function prototype states all necessary requirements separate from the implementation.
 For example, the prototype for the previous sum function is
-  \begin{cfacode}
-  forall(otype T | **R**{ T ?=?(T *, zero_t); T ?+=?(T *, T); }**R**)
-  T sum(T *arr, int n);
-  \end{cfacode}
+\begin{cfacode}
+forall(otype T | **R**{ T ?=?(T *, zero_t); T ?+=?(T *, T); }**R**)
+T sum(T *arr, int n);
+\end{cfacode}
 With this prototype, a caller in another translation unit knows all of the constraints on @T@, and thus knows all of the operations that need to be made available to @sum@.
 
 In \CFA, a set of assertions can be factored into a \emph{trait}.
 \begin{cfacode}
-  trait Addable(otype T) {
-    T ?+?(T, T);
-    T ++?(T);
-    T ?++(T);
-  }
-  forall(otype T | Addable(T)) void f(T);
-  forall(otype T | Addable(T) | { T --?(T); }) T g(T);
-  forall(otype T, U | Addable(T) | { T ?/?(T, U); }) U h(T, U);
+trait Addable(otype T) {
+  T ?+?(T, T);
+  T ++?(T);
+  T ?++(T);
+}
+forall(otype T | Addable(T)) void f(T);
+forall(otype T | Addable(T) | { T --?(T); }) T g(T);
+forall(otype T, U | Addable(T) | { T ?/?(T, U); }) U h(T, U);
 \end{cfacode}
 This capability allows specifying the same set of assertions in multiple locations, without the repetition and likelihood of mistakes that come with manually writing them out for each function declaration.
 
-An interesting application of return-type resolution and polymorphism is a type-safe version of @malloc@.
+An interesting application of return-type resolution and polymorphism is a polymorphic version of @malloc@.
 \begin{cfacode}
 forall(dtype T | sized(T))
@@ -321 +410 @@
 The built-in trait @sized@ ensures that size and alignment information for @T@ is available in the body of @malloc@ through @sizeof@ and @_Alignof@ expressions respectively.
 In calls to @malloc@, the type @T@ is bound based on call-site information, allowing \CFA code to allocate memory without the potential for errors introduced by manually specifying the size of the allocated block.
+
+\subsection{Planned Features}
+
+One of the planned features \CFA is \emph{reference types}.
+At a high level, the current proposal is to add references as a way to cleanup pointer syntax.
+With references, it will be possible to store any address, as with a pointer, with the key difference being that references are automatically dereferenced.
+\begin{cfacode}
+int x = 0;
+int * p = &x;  // needs &
+int & ref = x; // no &
+
+printf("%d %d\n", *p, ref); // pointer needs *, ref does not
+\end{cfacode}
+
+It is possible to add new functions or shadow existing functions for the duration of a scope, using normal C scoping rules.
+One application of this feature is to reverse the order of @qsort@.
+\begin{cfacode}
+forall(otype T | { int ?<?( T, T ); })
+void qsort(const T * arr, size_t size) {
+  int comp(const void * t1, const void * t2) {
+    return *(T *)t1 < *(T *)t2 ? -1 : *(T *)t2 < *(T *)t1 ? 1 : 0;
+  }
+  qsort(arr, dimension, sizeof(T), comp);
+
+}
+double vals[10] = { ... };
+qsort(vals, 10);                // ascending order
+{
+  int ?<?(double x, double y) { // locally override behaviour
+    return x > y;
+  }
+  qsort(vals, 10);              // descending sort
+}
+\end{cfacode}
+Currently, there is no way to \emph{remove} a function from consideration from the duration of a scope.
+For example, it may be desirable to eliminate assignment from a scope, to reduce accidental mutation.
+To address this desire, \emph{deleted functions} are a planned feature for \CFA.
+\begin{cfacode}
+forall(otype T) void f(T *);
+
+int x = 0;
+f(&x);  // might modify x
+{
+  int ?=?(int *, int) = delete;
+  f(&x);   // error, no assignment for int
+}
+\end{cfacode}
+Now, if the deleted function is chosen as the best match, the expression resolver emits an error.
 
 \section{Invariants}
@@ -450 +587 @@
 \end{javacode}
 In Java 7, a new \emph{try-with-resources} construct was added to alleviate most of the pain of working with resources, but ultimately it still places the burden squarely on the user rather than on the library designer.
-Furthermore, for complete safety this pattern requires nested objects to be declared separately, otherwise resources that can throw an exception on close can leak nested resources \cite{TryWithResources}.
+Furthermore, for complete safety this pattern requires nested objects to be declared separately, otherwise resources that can throw an exception on close can leak nested resources \footnote{Since close is only guaranteed to be called on objects declared in the try-list and not objects passed as constructor parameters, the @B@ object may not be closed in @new A(new B())@ if @A@'s close raises an exception.} \cite{TryWithResources}.
 \begin{javacode}
 public void write(String filename, String msg) throws Exception {
@@ -521 +658 @@
 % these are declared in the struct, so they're closer to C++ than to CFA, at least syntactically. Also do not allow for default constructors
 % D has a GC, which already makes the situation quite different from C/C++
-The programming language, D, also manages resources with constructors and destructors \cite{D}.
-In D, @struct@s are stack allocated and managed via scoping like in \CC, whereas @class@es are managed automatically by the garbage collector.
+The programming language D also manages resources with constructors and destructors \cite{D}.
+In D, @struct@s are stack allocatable and managed via scoping like in \CC, whereas @class@es are managed automatically by the garbage collector.
 Like Java, using the garbage collector means that destructors are called indeterminately, requiring the use of finally statements to ensure dynamically allocated resources that are not managed by the garbage collector, such as open files, are cleaned up.
 Since D supports RAII, it is possible to use the same techniques as in \CC to ensure that resources are released in a timely manner.
@@ -755 +892 @@
 
 Type-safe variadic functions are added to \CFA and discussed in Chapter 4.
+
+\section{Contributions}
+\label{s:contributions}
+
+No prior work on constructors or destructors had been done for \CFA.
+I did both the design and implementation work.
+While the overall design is based on constructors and destructors in object-oriented C++, it had to be re-engineered into non-object-oriented \CFA.
+I also had to make changes to the \CFA expression-resolver to integrate constructors and destructors into the type system.
+
+Prior work on the design of tuples for \CFA was done by Till, and some initial implementation work by Esteves.
+I largely took the Till design but added tuple indexing, which exists in a number of programming languages with tuples, simplified the implicit tuple conversions, and integrated with the \CFA polymorphism and assertion satisfaction model.
+I did a new implementation of tuples, and extensively
+augmented initial work by Bilson to incorporate tuples into the \CFA expression-resolver and type-unifier.
+
+No prior work on variadic functions had been done for \CFA.
+I did both the design and implementation work.
+While the overall design is based on variadic templates in C++, my design is novel in the way it is incorporated into the \CFA polymorphism model, and is engineered into \CFA so it dovetails with tuples.