Context Navigation

-                      rae6cc8b
+                      r7493339
 \section{\CFA Background}
 \label{s:background}
 \CFA is a modern extension to the C programming language.
+\CFA is a modern non-object-oriented extension to the C programming language.
 As it is an extension of C, there is already a wealth of existing C code and principles that govern the design of the language.
 Among the goals set out in the original design of \CFA, four points stand out \cite{Bilson03}.
 …
 Therefore, these design principles must be kept in mind throughout the design and development of new language features.
 In order to appeal to existing C programmers, great care must be taken to ensure that new features naturally feel like C.
 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. % TODO: harmonize with?
+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.
 \subsection{C Background}
 …
 For example, in the initialization of @a1@, the initializer of @y@ is @7@, and the unnamed initializer @6@ initializes the next subobject, @z@.
 Later initializers override earlier initializers, so a subobject for which there is more than one initializer is only initailized by its last initializer.
 This 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.
+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.
 …
 There are times when a function should logically return multiple values.
 Since a function in standard C can only return a single value, a programmer must either take in additional return values by address, or the function's designer must create a wrapper structure t0 package multiple return-values.
+Since a function in standard C can only return a single value, a programmer must either take in additional return values by address, or the function's designer must create a wrapper structure to package multiple return-values.
 \begin{cfacode}
 int f(int * ret) {        // returns a value through parameter ret
 …
 \end{cfacode}
 The former solution is awkward because it requires the caller to explicitly allocate memory for $n$ result variables, even if they are only temporary values used as a subexpression, or even not used at all.
+The latter approach:
 \begin{cfacode}
 struct A {
 …
 ... res3.x ... res3.y ... // use result values
 \end{cfacode}
 The latter approach requires the caller to either learn the field names of the structure or learn the names of helper routines to access the individual return values.
+requires the caller to either learn the field names of the structure or learn the names of helper routines to access the individual return values.
 Both solutions are syntactically unnatural.
 In \CFA, it is possible to directly declare a function returning mutliple values.
 This provides important semantic information to the caller, since return values are only for output.
 \begin{cfacode}
 [int, int] f() {       // don't need to create a new type
+This extension provides important semantic information to the caller, since return values are only for output.
+\begin{cfacode}
+[int, int] f() {       // no new type
   return [123, 37];
+}
 \end{cfacode}
+However, the ability to return multiple values requires a syntax for accepting the results from a function.
+However, the ability to return multiple values is useless without a syntax for accepting the results from the function.
 In standard C, return values are most commonly assigned directly into local variables, or are used as the arguments to another function call.
 \CFA allows both of these contexts to accept multiple return values.
 …
   g(f());             // selects (2)
   \end{cfacode}
 In this example, the only possible call to @f@ that can produce the two @int@s required by @g@ is the second option.
 A similar reasoning holds for assigning into multiple variables.
+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@.
 In \CFA, overloading also applies to operator names, known as \emph{operator overloading}.
 …
   bool ?<?(A x, A y);
   \end{cfacode}
 Notably, the only difference in this example is syntax.
+Notably, the only difference is syntax.
 Most of the operators supported by \CC for operator overloading are also supported in \CFA.
 Of notable exception are the logical operators (e.g. @||@), the sequence operator (i.e. @,@), and the member-access operators (e.g. @.@ and \lstinline{->}).
 …
 Finally, \CFA also permits overloading variable identifiers.
 This feature is not available in \CC.
   \begin{cfacode} % TODO: pick something better than x? max, zero, one?
+  \begin{cfacode}
   struct Rational { int numer, denom; };
   int x = 3;               // (1)
 …
 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.
+When used judiciously, this feature allows names like @MAX@, @MIN@, and @PI@ to apply across many types.
 Finally, the values @0@ and @1@ have special status in standard C.
 …
+}
 \end{cfacode}
 Every if statement in C compares the condition with @0@, and every increment and decrement operator is semantically equivalent to adding or subtracting the value @1@ and storing the result.
+Every if- and iteration-statement in C compares the condition with @0@, and every increment and decrement operator is semantically equivalent to adding or subtracting the value @1@ and storing the result.
 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.
+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++
 …
 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 with type-safe @malloc@.
+\begin{cfacode}
+forall(dtype T | sized(T))
+T * malloc() {
+  return (T*)malloc(sizeof(T)); // call C malloc
+}
+int * x = malloc();     // malloc(sizeof(int))
+double * y = malloc();  // malloc(sizeof(double))
+struct S { ... };
+S * s = malloc();       // malloc(sizeof(S))
+\end{cfacode}
+The built-in trait @sized@ ensures that size and alignment information for @T@ is available to @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.
 \section{Invariants}
+% TODO: discuss software engineering benefits of ctor/dtors: {pre/post} conditions, invariants
+% an important invariant is the state of the environment (memory, resources)
+% some objects pass their contract to the object user
+An \emph{invariant} is a logical assertion that true for some duration of a program's execution.
+An \emph{invariant} is a logical assertion that is true for some duration of a program's execution.
 Invariants help a programmer to reason about code correctness and prove properties of programs.
 In object-oriented programming languages, type invariants are typically established in a constructor and maintained throughout the object's lifetime.
 This is typically achieved through a combination of access control modifiers and a restricted interface.
+These assertions are typically achieved through a combination of access control modifiers and a restricted interface.
 Typically, data which requires the maintenance of an invariant is hidden from external sources using the \emph{private} modifier, which restricts reads and writes to a select set of trusted routines, including member functions.
 It is these trusted routines that perform all modifications to internal data in a way that is consistent with the invariant, by ensuring that the invariant holds true at the end of the routine call.
 …
 In C, the @assert@ macro is often used to ensure invariants are true.
 Using @assert@, the programmer can check a condition and abort execution if the condition is not true.
 This is a powerful tool that forces the programmer to deal with logical inconsistencies as they occur.
+This powerful tool forces the programmer to deal with logical inconsistencies as they occur.
 For production, assertions can be removed by simply defining the preprocessor macro @NDEBUG@, making it simple to ensure that assertions are 0-cost for a performance intensive application.
 \begin{cfacode}
 …
 \end{dcode}
 The D compiler is able to assume that assertions and invariants hold true and perform optimizations based on those assumptions.
+An important invariant is the state of the execution environment, including the heap, the open file table, the state of global variables, etc.
+Since resources are finite, it is important to ensure that objects clean up properly when they are finished, restoring the execution environment to a stable state so that new objects can reuse resources.
+Note, these invariants are internal to the type's correct behaviour.
+Types also have external invarients with state of the execution environment, including the heap, the open file-table, the state of global variables, etc.
+Since resources are finite and shared (concurrency), it is important to ensure that objects clean up properly when they are finished, restoring the execution environment to a stable state so that new objects can reuse resources.
 \section{Resource Management}
 …
 However, whenever a program needs a variable to outlive the block it is created in, the storage must be allocated dynamically with @malloc@ and later released with @free@.
 This pattern is extended to more complex objects, such as files and sockets, which also outlive the block where they are created, but at their core is resource management.
 Once allocated storage escapes a block, the responsibility for deallocating the storage is not specified in a function's type, that is, that the return value is owned by the caller.
+Once allocated storage escapes\footnote{In garbage collected languages, such as Java, escape analysis \cite{Choi:1999:EAJ:320385.320386} is used to determine when dynamically allocated objects are strictly contained within a function, which allows the optimizer to allocate them on the stack.} a block, the responsibility for deallocating the storage is not specified in a function's type, that is, that the return value is owned by the caller.
 This implicit convention is provided only through documentation about the expectations of functions.
 …
 On the other hand, destructors provide a simple mechanism for tearing down an object and resetting the environment in which the object lived.
 RAII ensures that if all resources are acquired in a constructor and released in a destructor, there are no resource leaks, even in exceptional circumstances.
 A type with at least one non-trivial constructor or destructor will henceforth be referred to as a \emph{managed type}.
+A type with at least one non-trivial constructor or destructor is henceforth referred to as a \emph{managed type}.
 In the context of \CFA, a non-trivial constructor is either a user defined constructor or an auto generated constructor that calls a non-trivial constructor.
 …
 There are many kinds of resources that the garbage collector does not understand, such as sockets, open files, and database connections.
 In particular, Java supports \emph{finalizers}, which are similar to destructors.
 Sadly, finalizers come with far fewer guarantees, to the point where a completely conforming JVM may never call a single finalizer. % TODO: citation JVM spec; http://stackoverflow.com/a/2506514/2386739
 Due to operating system resource limits, this is unacceptable for many long running tasks. % TODO: citation?
 Instead, the paradigm in Java requires programmers manually keep track of all resource \emph{except} memory, leading many novices and experts alike to forget to close files, etc.
 Complicating the picture, uncaught exceptions can cause control flow to change dramatically, leaking a resource which appears on first glance to be closed.
+Sadly, finalizers are only guaranteed to be called before an object is reclaimed by the garbage collector \cite[p.~373]{Java8}, which may not happen if memory use is not contentious.
+Due to operating-system resource-limits, this is unacceptable for many long running programs. % TODO: citation?
+Instead, the paradigm in Java requires programmers to manually keep track of all resources \emph{except} memory, leading many novices and experts alike to forget to close files, etc.
+Complicating the picture, uncaught exceptions can cause control flow to change dramatically, leaking a resource that appears on first glance to be released.
 \begin{javacode}
 void write(String filename, String msg) throws Exception {
 …
+}
 \end{javacode}
+Any line in this program can throw an exception.
+This leads to a profusion of finally blocks around many function bodies, since it isn't always clear when an exception may be thrown.
+Any line in this program can throw an exception, which leads to a profusion of finally blocks around many function bodies, since it is not always clear when an exception may be thrown.
 \begin{javacode}
 public void write(String filename, String msg) throws Exception {
 …
 \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 which can throw an exception on close can leak nested resources. % TODO: cite oracle article http://www.oracle.com/technetwork/articles/java/trywithresources-401775.html?
+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}.
 \begin{javacode}
 public void write(String filename, String msg) throws Exception {
   try (
+  try (  // try-with-resources
     FileOutputStream out = new FileOutputStream(filename);
     FileOutputStream log = new FileOutputStream("log.txt");
 …
+}
 \end{javacode}
+On the other hand, the Java compiler generates more code if more resources are declared, meaning that users must be more familiar with each type and library designers must provide better documentation.
+Variables declared as part of a try-with-resources statement must conform to the @AutoClosable@ interface, and the compiler implicitly calls @close@ on each of the variables at the end of the block.
+Depending on when the exception is raised, both @out@ and @log@ are null, @log@ is null, or both are non-null, therefore, the cleanup for these variables at the end is appropriately guarded and conditionally executed to prevent null-pointer exceptions.
+% TODO: discuss Rust?
+% Like \CC, Rust \cite{Rust} provides RAII through constructors and destructors.
+% Smart pointers are deeply integrated in the Rust type-system.
 % D has constructors and destructors that are worth a mention (under classes) https://dlang.org/spec/spec.html
 …
 Like Java, using the garbage collector means that destructors may never be called, 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.
+Finally, D provides a scope guard statement, which allows an arbitrary statement to be executed at normal scope exit with \emph{success}, at exceptional scope exit with \emph{failure}, or at normal and exceptional scope exit with \emph{exit}. % cite? https://dlang.org/spec/statement.html#ScopeGuardStatement
+It has been shown that the \emph{exit} form of the scope guard statement can be implemented in a library in \CC. % cite: http://www.drdobbs.com/184403758
+% TODO: discussion of lexical scope vs. dynamic
+% see Peter's suggestions
+% RAII works in both cases. Guaranteed to work in stack case, works in heap case if root is deleted (but it's dangerous to rely on this, because of exceptions)
+Finally, D provides a scope guard statement, which allows an arbitrary statement to be executed at normal scope exit with \emph{success}, at exceptional scope exit with \emph{failure}, or at normal and exceptional scope exit with \emph{exit}. % TODO: cite? https://dlang.org/spec/statement.html#ScopeGuardStatement
+It has been shown that the \emph{exit} form of the scope guard statement can be implemented in a library in \CC \cite{ExceptSafe}.
+To provide managed types in \CFA, new kinds of constructors and destructors are added to C and discussed in Chapter 2.
 \section{Tuples}
 \label{s:Tuples}
 In mathematics, tuples are finite-length sequences which, unlike sets, allow duplicate elements.
 In programming languages, tuples are a construct that provide fixed-sized heterogeneous lists of elements.
+In programming languages, tuples provide fixed-sized heterogeneous lists of elements.
 Many programming languages have tuple constructs, such as SETL, \KWC, ML, and Scala.
 …
 Adding tuples to \CFA has previously been explored by Esteves \cite{Esteves04}.
 The design of tuples in \KWC took much of its inspiration from SETL.
+The design of tuples in \KWC took much of its inspiration from SETL \cite{SETL}.
 SETL is a high-level mathematical programming language, with tuples being one of the primary data types.
 Tuples in SETL allow a number of operations, including subscripting, dynamic expansion, and multiple assignment.
 …
 \begin{cppcode}
 tuple<int, int, int> triple(10, 20, 30);
 get<1>(triple); // access component 1 => 30
+get<1>(triple); // access component 1 => 20
 tuple<int, double> f();
 …
 Tuples are simple data structures with few specific operations.
 In particular, it is possible to access a component of a tuple using @std::get<N>@.
 Another interesting feature is @std::tie@, which creates a tuple of references, which allows assigning the results of a tuple-returning function into separate local variables, without requiring a temporary variable.
+Another interesting feature is @std::tie@, which creates a tuple of references, allowing assignment of the results of a tuple-returning function into separate local variables, without requiring a temporary variable.
 Tuples also support lexicographic comparisons, making it simple to write aggregate comparators using @std::tie@.
 There is a proposal for \CCseventeen called \emph{structured bindings}, that introduces new syntax to eliminate the need to pre-declare variables and use @std::tie@ for binding the results from a function call. % TODO: cite http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0144r0.pdf
+There is a proposal for \CCseventeen called \emph{structured bindings} \cite{StructuredBindings}, that introduces new syntax to eliminate the need to pre-declare variables and use @std::tie@ for binding the results from a function call.
 \begin{cppcode}
 tuple<int, double> f();
 …
 Structured bindings allow unpacking any struct with all public non-static data members into fresh local variables.
 The use of @&@ allows declaring new variables as references, which is something that cannot be done with @std::tie@, since \CC references do not support rebinding.
 This extension requires the use of @auto@ to infer the types of the new variables, so complicated expressions with a non-obvious type must documented with some other mechanism.
+This extension requires the use of @auto@ to infer the types of the new variables, so complicated expressions with a non-obvious type must be documented with some other mechanism.
 Furthermore, structured bindings are not a full replacement for @std::tie@, as it always declares new variables.
 Like \CC, D provides tuples through a library variadic template struct.
 In D, it is possible to name the fields of a tuple type, which creates a distinct type.
+\begin{dcode} % TODO: cite http://dlang.org/phobos/std_typecons.html
+% TODO: cite http://dlang.org/phobos/std_typecons.html
+\begin{dcode}
 Tuple!(float, "x", float, "y") point2D;
 Tuple!(float, float) float2;  // different types
+Tuple!(float, float) float2;  // different type from point2D
 point2D[0]; // access first element
 …
 The @expand@ method produces the components of the tuple as a list of separate values, making it possible to call a function that takes $N$ arguments using a tuple with $N$ components.
 Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML.
+Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML \cite{sml}.
 A function in SML always accepts exactly one argument.
 There are two ways to mimic multiple argument functions: the first through currying and the second by accepting tuple arguments.
 …
 Tuples are a foundational tool in SML, allowing the creation of arbitrarily complex structured data types.
 Scala, like \CC, provides tuple types through the standard library.
+Scala, like \CC, provides tuple types through the standard library \cite{Scala}.
 Scala provides tuples of size 1 through 22 inclusive through generic data structures.
 Tuples support named access and subscript access, among a few other operations.
 …
 \end{scalacode}
 In Scala, tuples are primarily used as simple data structures for carrying around multiple values or for returning multiple values from a function.
 The 22-element restriction is an odd and arbitrary choice, but in practice it doesn't cause problems since large tuples are uncommon.
+The 22-element restriction is an odd and arbitrary choice, but in practice it does not cause problems since large tuples are uncommon.
 Subscript access is provided through the @productElement@ method, which returns a value of the top-type @Any@, since it is impossible to receive a more precise type from a general subscripting method due to type erasure.
 The disparity between named access beginning at @_1@ and subscript access starting at @0@ is likewise an oddity, but subscript access is typically avoided since it discards type information.
 …
 \Csharp has similarly strange limitations, allowing tuples of size up to 7 components. % TODO: cite https://msdn.microsoft.com/en-us/library/system.tuple(v=vs.110).aspx
+\Csharp also has tuples, but has similarly strange limitations, allowing tuples of size up to 7 components. % TODO: cite https://msdn.microsoft.com/en-us/library/system.tuple(v=vs.110).aspx
 The officially supported workaround for this shortcoming is to nest tuples in the 8th component.
 \Csharp allows accessing a component of a tuple by using the field @Item$N$@ for components 1 through 7, and @Rest@ for the nested tuple.
+% TODO: cite 5.3 https://docs.python.org/3/tutorial/datastructures.html
+In Python, tuples are immutable sequences that provide packing and unpacking operations.
+In Python \cite{Python}, tuples are immutable sequences that provide packing and unpacking operations.
 While the tuple itself is immutable, and thus does not allow the assignment of components, there is nothing preventing a component from being internally mutable.
 The components of a tuple can be accessed by unpacking into multiple variables, indexing, or via field name, like D.
 Tuples support multiple assignment through a combination of packing and unpacking, in addition to the common sequence operations.
+% TODO: cite https://developer.apple.com/library/content/documentation/Swift/Conceptual/Swift_Programming_Language/Types.html#//apple_ref/doc/uid/TP40014097-CH31-ID448
+Swift, like D, provides named tuples, with components accessed by name, index, or via extractors.
+Swift \cite{Swift}, like D, provides named tuples, with components accessed by name, index, or via extractors.
 Tuples are primarily used for returning multiple values from a function.
 In Swift, @Void@ is an alias for the empty tuple, and there are no single element tuples.
+% TODO: this statement feels like it's too strong
+Tuples as powerful as the above languages are added to C and discussed in Chapter 3.
 \section{Variadic Functions}
 …
 A parameter pack matches 0 or more elements, which can be types or expressions depending on the context.
 Like other templates, variadic template functions rely on an implicit set of constraints on a type, in this example a @print@ routine.
 That is, it is possible to use the @f@ routine any any type provided there is a corresponding @print@ routine, making variadic templates fully open to extension, unlike variadic functions in C.
+That is, it is possible to use the @f@ routine on any type provided there is a corresponding @print@ routine, making variadic templates fully open to extension, unlike variadic functions in C.
 Recent \CC standards (\CCfourteen, \CCseventeen) expand on the basic premise by allowing variadic template variables and providing convenient expansion syntax to remove the need for recursion in some cases, amongst other things.
 …
 Unfortunately, Java's use of nominal inheritance means that types must explicitly inherit from classes or interfaces in order to be considered a subclass.
 The combination of these two issues greatly restricts the usefulness of variadic functions in Java.
+Type-safe variadic functions are added to C and discussed in Chapter 4.

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 7493339 for doc/rob_thesis/intro.tex

Legend:

doc/rob_thesis/intro.tex

Download in other formats: