Index: doc/rob_thesis/cfa-format.tex =================================================================== --- doc/rob_thesis/cfa-format.tex (revision 0111dc78014e8cb9bf465cd3dda3af109d744b69) +++ doc/rob_thesis/cfa-format.tex (revision 29137d3a649bfcc5cdde5a1d7d6e2daeed39a49d) @@ -1,4 +1,4 @@ -\usepackage{xcolor} -\usepackage{listings} +% \usepackage{xcolor} +% \usepackage{listings} % \usepackage{booktabs} % \usepackage{array} @@ -103,4 +103,6 @@ \renewcommand{\ttdefault}{pcr} + +\newcommand{\basicstylesmall}{\scriptsize\ttfamily\color{basicCol}} \lstdefinestyle{defaultStyle}{ @@ -131,5 +133,5 @@ style=defaultStyle } -\lstMakeShortInline[basewidth=0.5em,breaklines=true,basicstyle=\normalsize\ttfamily\color{basicCol}]@ % single-character for \lstinline +\lstMakeShortInline[basewidth=0.5em,breaklines=true,breakatwhitespace,basicstyle=\normalsize\ttfamily\color{basicCol}]@ % single-character for \lstinline \lstnewenvironment{cfacode}[1][]{ @@ -195,4 +197,6 @@ \newcommand{\one}{\lstinline{one_t}\xspace} \newcommand{\ateq}{\lstinline{\@=}\xspace} + +\newenvironment{newtext}{\color{red}}{\ignorespacesafterend} % \lstset{ % Index: doc/rob_thesis/conclusions.tex =================================================================== --- doc/rob_thesis/conclusions.tex (revision 0111dc78014e8cb9bf465cd3dda3af109d744b69) +++ doc/rob_thesis/conclusions.tex (revision 29137d3a649bfcc5cdde5a1d7d6e2daeed39a49d) @@ -6,5 +6,6 @@ On the surface, the work may appear as a rehash of similar mechanisms in \CC. However, every added feature is different than its \CC counterpart, often with extended functionality, better integration with C and its programmers, and always supports separate compilation. -All of these new features are being used by the \CFA development-team to build the \CFA runtime system. +All of these new features are being used extensively by the \CFA development-team to build the \CFA runtime system. +In particular, the concurrency system is built on top of RAII, library functions @new@ and @delete@ are used to manage dynamically allocated objects, and tuples are used to provide uniform interfaces to C library routines such as @div@ and @remquo@. \section{Constructors and Destructors} @@ -245,6 +246,26 @@ That is, structure fields can be accessed and modified by any block of code without restriction, so while it is possible to ensure that an object is initially set to a valid state, it is not possible to ensure that it remains in a consistent state throughout its lifetime. A popular technique for ensuring consistency in object-oriented programming languages is to provide access modifiers such as @private@, which provides compile-time checks that only privileged code accesses private data. -This approach could be added to \CFA, but it requires an idiomatic way of specifying what code is privileged. +This approach could be added to \CFA, but it requires an idiomatic way of specifying what code is privileged and what data is protected. One possibility is to tie access control into an eventual module system. + +\begin{sloppypar} +The current implementation of implicit subobject-construction is currently an all-or-nothing check. +That is, if a subobject is conditionally constructed, \eg within an if-statement, no implicit constructors for that object are added. +\begin{cfacode} +struct A { ... }; +void ?{}(A * a) { ... } + +struct B { + A a; +}; +void ?{}(B * b) { + if (...) { + (&b->a){}; // explicitly constructed + } // does not construct in else case +} +\end{cfacode} +This behaviour is unsafe and breaks the guarantee that constructors fully initialize objects. +This situation should be properly handled, either by examining all paths and inserting implicit constructor calls only in the paths missing construction, or by emitting an error or warning. +\end{sloppypar} \subsection{Tuples} @@ -252,5 +273,5 @@ This feature ties nicely into named tuples, as seen in D and Swift. -Currently, tuple flattening and structuring conversions are 0-cost. +Currently, tuple flattening and structuring conversions are 0-cost conversions in the resolution algorithm. This makes tuples conceptually very simple to work with, but easily causes unnecessary ambiguity in situations where the type system should be able to differentiate between alternatives. Adding an appropriate cost function to tuple conversions will allow tuples to interact with the rest of the programming language more cohesively. Index: doc/rob_thesis/ctordtor.tex =================================================================== --- doc/rob_thesis/ctordtor.tex (revision 0111dc78014e8cb9bf465cd3dda3af109d744b69) +++ doc/rob_thesis/ctordtor.tex (revision 29137d3a649bfcc5cdde5a1d7d6e2daeed39a49d) @@ -6,6 +6,7 @@ % doesn't seem possible to do this without allowing ttype on generic structs? -Since \CFA is a true systems language, it does not provide a garbage collector. -As well, \CFA is not an object-oriented programming language, \ie, structures cannot have routine members. +Since \CFA is a true systems language, it does not require a garbage collector. +As well, \CFA is not an object-oriented programming language, \ie, structures cannot have methods. +While structures can have function pointer members, this is different from methods, since methods have implicit access to structure members and methods cannot be reassigned. Nevertheless, one important goal is to reduce programming complexity and increase safety. To that end, \CFA provides support for implicit pre/post-execution of routines for objects, via constructors and destructors. @@ -32,5 +33,5 @@ The key difference between assignment and initialization being that assignment occurs on a live object (\ie, an object that contains data). It is important to note that this means @x@ could have been used uninitialized prior to being assigned, while @y@ could not be used uninitialized. -Use of uninitialized variables yields undefined behaviour, which is a common source of errors in C programs. +Use of uninitialized variables yields undefined behaviour \cite[p.~558]{C11}, which is a common source of errors in C programs. Initialization of a declaration is strictly optional, permitting uninitialized variables to exist. @@ -70,11 +71,11 @@ int x2 = opaque_get(x, 2); \end{cfacode} -This pattern is cumbersome to use since every access becomes a function call. +This pattern is cumbersome to use since every access becomes a function call, requiring awkward syntax and a performance cost. While useful in some situations, this compromise is too restrictive. Furthermore, even with this idiom it is easy to make mistakes, such as forgetting to destroy an object or destroying it multiple times. A constructor provides a way of ensuring that the necessary aspects of object initialization is performed, from setting up invariants to providing compile- and run-time checks for appropriate initialization parameters. -This goal is achieved through a guarantee that a constructor is called implicitly after every object is allocated from a type with associated constructors, as part of an object's definition. -Since a constructor is called on every object of a managed type, it is impossible to forget to initialize such objects, as long as all constructors perform some sensible form of initialization. +This goal is achieved through a \emph{guarantee} that a constructor is called \emph{implicitly} after every object is allocated from a type with associated constructors, as part of an object's \emph{definition}. +Since a constructor is called on every object of a managed type, it is \emph{impossible} to forget to initialize such objects, as long as all constructors perform some sensible form of initialization. In \CFA, a constructor is a function with the name @?{}@. @@ -114,5 +115,5 @@ In other words, a default constructor is a constructor that takes a single argument: the @this@ parameter. -In \CFA, a destructor is a function much like a constructor, except that its name is \lstinline!^?{}! and it takes only one argument. +In \CFA, a destructor is a function much like a constructor, except that its name is \lstinline!^?{}! \footnote{Originally, the name @~?{}@ was chosen for destructors, to provide familiarity to \CC programmers. Unforunately, this name causes parsing conflicts with the bitwise-not operator when used with operator syntax (see section \ref{sub:syntax}.)} and it takes only one argument. A destructor for the @Array@ type can be defined as: \begin{cfacode} @@ -135,5 +136,6 @@ On line 2, @z@ is initialized with the value of @x@, while on line 3, @y@ is assigned the value of @x@. The key distinction between initialization and assignment is that a value to be initialized does not hold any meaningful values, whereas an object to be assigned might. -In particular, these cases cannot be handled the same way because in the former case @z@ does not currently own an array, while @y@ does. +In particular, these cases cannot be handled the same way because in the former case @z@ has no array, while @y@ does. +A \emph{copy constructor} is used to perform initialization using another object of the same type. \begin{cfacode}[emph={other}, emphstyle=\color{red}] @@ -151,7 +153,9 @@ } \end{cfacode} -The two functions above handle these cases. -The first function is called a \emph{copy constructor}, because it constructs its argument by copying the values from another object of the same type. +The two functions above handle the cases of initialization and assignment. +The first function is called a copy constructor, because it constructs its argument by copying the values from another object of the same type. The second function is the standard copy-assignment operator. +\CFA does not currently have the concept of reference types, so the most appropriate type for the source object in copy constructors and assignment operators is a value type. +Appropriate care is taken in the implementation to avoid recursive calls to the copy constructor. The four functions (default constructor, destructor, copy constructor, and assignment operator) are special in that they safely control the state of most objects. @@ -216,8 +220,8 @@ A * y = malloc(); // copy construct: ?{}(&y, malloc()) +^?{}(&x); // explicit destroy x, in different order ?{}(&x); // explicit construct x, second construction +^?{}(y); // explicit destroy y ?{}(y, x); // explit construct y from x, second construction -^?{}(&x); // explicit destroy x, in different order -^?{}(y); // explicit destroy y // implicit ^?{}(&y); @@ -279,4 +283,7 @@ \end{cfacode} In this example, @malloc@ dynamically allocates storage and initializes it using a constructor, all before assigning it into the variable @x@. +Intuitively, the expression-resolver determines that @malloc@ returns some type @T *@, as does the constructor expression since it returns the type of its argument. +This type flows outwards to the declaration site where the expected type is known to be @X *@, thus the first argument to the constructor must be @X *@, narrowing the search space. + If this extension is not present, constructing dynamically allocated objects is much more cumbersome, requiring separate initialization of the pointer and initialization of the pointed-to memory. \begin{cfacode} @@ -300,5 +307,5 @@ It should be noted that this technique is not exclusive to @malloc@, and allows a user to write a custom allocator that can be idiomatically used in much the same way as a constructed @malloc@ call. -It should be noted that while it is possible to use operator syntax with destructors, destructors invalidate their argument, thus operator syntax with destructors is a statement and does not produce a value. +While it is possible to use operator syntax with destructors, destructors invalidate their argument, thus operator syntax with destructors is void-typed expression. \subsection{Function Generation} @@ -308,10 +315,25 @@ If the translator can expect these functions to exist, then it can unconditionally attempt to resolve them. Moreover, the existence of a standard interface allows polymorphic code to interoperate with new types seamlessly. +While automatic generation of assignment functions is present in previous versions of \CFA, the the implementation has been largely rewritten to accomodate constructors and destructors. To mimic the behaviour of standard C, the default constructor and destructor for all of the basic types and for all pointer types are defined to do nothing, while the copy constructor and assignment operator perform a bitwise copy of the source parameter (as in \CC). +This default is intended to maintain backwards compatibility and performance, by not imposing unexpected operations for a C programmer, as a zero-default behaviour would. +However, it is possible for a user to define such constructors so that variables are safely zeroed by default, if desired. +%%%%%%%%%%%%%%%%%%%%%%%%%% line width %%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{cfacode} +void ?{}(int * i) { *i = 0; } +forall(dtype T) void ?{}(T ** p) { *p = 0; } // any pointer type +void f() { + int x; // initialized to 0 + int * p; // initialized to 0 +} +\end{cfacode} +%%%%%%%%%%%%%%%%%%%%%%%%%% line width %%%%%%%%%%%%%%%%%%%%%%%%%% There are several options for user-defined types: structures, unions, and enumerations. To aid in ease of use, the standard set of four functions is automatically generated for a user-defined type after its definition is completed. By auto-generating these functions, it is ensured that legacy C code continues to work correctly in every context where \CFA expects these functions to exist, since they are generated for every complete type. +As well, these functions are always generated, since they may be needed by polymorphic functions. +With that said, the generated functions are not called implicitly unless they are non-trivial, and are never exported, making it simple for the optimizer to strip them away when they are not used. The generated functions for enumerations are the simplest. @@ -338,5 +360,5 @@ } \end{cfacode} -In the future, \CFA will introduce strongly-typed enumerations, like those in \CC. +In the future, \CFA will introduce strongly-typed enumerations, like those in \CC, wherein enumerations create a new type distinct from @int@ so that integral values require an explicit cast to be stored in an enumeration variable. The existing generated routines are sufficient to express this restriction, since they are currently set up to take in values of that enumeration type. Changes related to this feature only need to affect the expression resolution phase, where more strict rules will be applied to prevent implicit conversions from integral types to enumeration types, but should continue to permit conversions from enumeration types to @int@. @@ -492,5 +514,5 @@ In addition to freedom, \ateq provides a simple path for migrating legacy C code to \CFA, in that objects can be moved from C-style initialization to \CFA gradually and individually. It is worth noting that the use of unmanaged objects can be tricky to get right, since there is no guarantee that the proper invariants are established on an unmanaged object. -It is recommended that most objects be managed by sensible constructors and destructors, except where absolutely necessary. +It is recommended that most objects be managed by sensible constructors and destructors, except where absolutely necessary, such as memory-mapped devices, trigger devices, I/O controllers, etc. When a user declares any constructor or destructor, the corresponding intrinsic/generated function and all field constructors for that type are hidden, so that they are not found during expression resolution until the user-defined function goes out of scope. @@ -545,4 +567,6 @@ \end{cfacode} However, if the translator sees a sub-object used within the body of a constructor, but does not see a constructor call that uses the sub-object as the target of a constructor, then the translator assumes the object is to be implicitly constructed (copy constructed in a copy constructor and default constructed in any other constructor). +To override this rule, \ateq can be used to force the translator to trust the programmer's discretion. +This form of \ateq is not yet implemented. \begin{cfacode} void ?{}(A * a) { @@ -556,11 +580,15 @@ } +void ?{}(A * a, int x) { + // object forwarded to another constructor, + // does not implicitly construct any members + (&a){}; +} + void ^?{}(A * a) { ^(&a->x){}; // explicit destructor call } // z, y, w implicitly destructed, in this order \end{cfacode} -If at any point, the @this@ parameter is passed directly as the target of another constructor, then it is assumed that constructor handles the initialization of all of the object's members and no implicit constructor calls are added. -To override this rule, \ateq can be used to force the translator to trust the programmer's discretion. -This form of \ateq is not yet implemented. +If at any point, the @this@ parameter is passed directly as the target of another constructor, then it is assumed the other constructor handles the initialization of all of the object's members and no implicit constructor calls are added to the current constructor. Despite great effort, some forms of C syntax do not work well with constructors in \CFA. @@ -619,6 +647,19 @@ The body of @A@ has been omitted, since only the constructor interfaces are important. -It should be noted that unmanaged objects can still make use of designations and nested initializers in \CFA. +It should be noted that unmanaged objects, i.e. objects that have only trivial constructors, can still make use of designations and nested initializers in \CFA. It is simple to overcome this limitation for managed objects by making use of compound literals, so that the arguments to the constructor call are explicitly typed. +%%%%%%%%%%%%%%%%%%%%%%%%%% line width %%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{cfacode} +struct B { int x; }; +struct C { int y; }; +struct A { B b; C c; }; +void ?{}(A *, B); +void ?{}(A *, C); + +A a = { + (C){ 10 } // disambiguate with compound literal +}; +\end{cfacode} +%%%%%%%%%%%%%%%%%%%%%%%%%% line width %%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Implicit Destructors} @@ -744,4 +785,18 @@ \end{cfacode} +While \CFA supports the GCC computed-goto extension, the behaviour of managed objects in combination with computed-goto is undefined. +\begin{cfacode} +void f(int val) { + void * l = val == 0 ? &&L1 : &&L2; + { + A x; + L1: ; + goto *l; // branches differently depending on argument + } + L2: ; +} +\end{cfacode} +Likewise, destructors are not executed at scope-exit due to a computed-goto in \CC, as of g++ version 6.2. + \subsection{Implicit Copy Construction} \label{s:implicit_copy_construction} @@ -750,8 +805,8 @@ Exempt from these rules are intrinsic and built-in functions. It should be noted that unmanaged objects are subject to copy constructor calls when passed as arguments to a function or when returned from a function, since they are not the \emph{target} of the copy constructor call. -That is, since the parameter is not marked as an unmanaged object using \ateq, it is be copy constructed if it is returned by value or passed as an argument to another function, so to guarantee consistent behaviour, unmanaged objects must be copy constructed when passed as arguments. +That is, since the parameter is not marked as an unmanaged object using \ateq, it is copy constructed if it is returned by value or passed as an argument to another function, so to guarantee consistent behaviour, unmanaged objects must be copy constructed when passed as arguments. These semantics are important to bear in mind when using unmanaged objects, and could produce unexpected results when mixed with objects that are explicitly constructed. \begin{cfacode} -struct A; +struct A { ... }; void ?{}(A *); void ?{}(A *, A); @@ -810,4 +865,9 @@ It should be noted that reference types will allow specifying that a value does not need to be copied, however reference types do not provide a means of preventing implicit copy construction from uses of the reference, so the problem is still present when passing or returning the reference by value. +Adding implicit copy construction imposes the additional runtime cost of the copy constructor for every argument and return value in a function call. +This cost is necessary to maintain appropriate value semantics when calling a function. +In the future, return-value-optimization (RVO) can be implemented for \CFA to elide unnecessary copy construction and destruction of temporary objects. +This cost is not present for types with trivial copy constructors and destructors. + A known issue with this implementation is that the argument and return value temporaries are not guaranteed to have the same address for their entire lifetimes. In the previous example, since @_retval_f@ is allocated and constructed in @f@, then returned by value, the internal data is bitwise copied into the caller's stack frame. @@ -908,5 +968,5 @@ \subsection{Array Initialization} Arrays are a special case in the C type-system. -C arrays do not carry around their size, making it impossible to write a standalone \CFA function that constructs or destructs an array while maintaining the standard interface for constructors and destructors. +Type checking largely ignores size information for C arrays, making it impossible to write a standalone \CFA function that constructs or destructs an array, while maintaining the standard interface for constructors and destructors. Instead, \CFA defines the initialization and destruction of an array recursively. That is, when an array is defined, each of its elements is constructed in order from element 0 up to element $n-1$. @@ -1147,4 +1207,10 @@ \end{cfacode} +This implementation comes at the runtime cost of an additional branch for every @static@ local variable, each time the function is called. +Since initializers are not required to be compile-time constant expressions, they can involve global variables, function arguments, function calls, etc. +As a direct consequence, @static@ local variables cannot be initialized with an attribute-constructor routines like global variables can. +However, in the case where the variable is unmanaged and has a compile-time constant initializer, a C-compliant initializer is generated and the additional cost is not present. +\CC shares the same semantics for its @static@ local variables. + \subsection{Polymorphism} As mentioned in section \ref{sub:polymorphism}, \CFA currently has 3 type-classes that are used to designate polymorphic data types: @otype@, @dtype@, and @ftype@. @@ -1172,2 +1238,22 @@ These additions allow @f@'s body to create and destroy objects of type @T@, and pass objects of type @T@ as arguments to other functions, following the normal \CFA rules. A point of note here is that objects can be missing default constructors (and eventually other functions through deleted functions), so it is important for \CFA programmers to think carefully about the operations needed by their function, as to not over-constrain the acceptable parameter types and prevent potential reuse. + +These additional assertion parameters impose a runtime cost on all managed temporary objects created in polymorphic code, even those with trivial constructors and destructors. +This cost is necessary because polymorphic code does not know the actual type at compile-time, due to separate compilation. +Since trivial constructors and destructors either do not perform operations or are simply bit-wise copy operations, the imposed cost is essentially the cost of the function calls. + +\section{Summary} + +When creating a new object of a managed type, it is guaranteed that a constructor is be called to initialize the object at its definition point, and is destructed when the object's lifetime ends. +Destructors are called in the reverse order of construction. + +Every argument passed to a function is copy constructed into a temporary object that is passed by value to the functions and destructed at the end of the statement. +Function return values are copy constructed inside the function at the return statement, passed by value to the call-site, and destructed at the call-site at the end of the statement. + +Every complete object type has a default constructor, copy constructor, assignment operator, and destructor. +To accomplish this, these functions are generated as appropriate for new types. +User-defined functions shadow built-in and automatically generated functions, so it is possible to specialize the behaviour of a type. +Furthermore, default constructors and aggregate field constructors are hidden when \emph{any} constructor is defined. + +Objects dynamically allocated with @malloc@, \ateq objects, and objects with only trivial constructors and destructors are unmanaged. +Unmanaged objects are never the target of an implicit constructor or destructor call. Index: doc/rob_thesis/examples/malloc.cc =================================================================== --- doc/rob_thesis/examples/malloc.cc (revision 29137d3a649bfcc5cdde5a1d7d6e2daeed39a49d) +++ doc/rob_thesis/examples/malloc.cc (revision 29137d3a649bfcc5cdde5a1d7d6e2daeed39a49d) @@ -0,0 +1,20 @@ +#include +#include +using namespace std; + +class A { +public: + A() { + cout << "A()" << endl; + } + ~A(){ + cout << "~A()" << endl; + } +}; + +int main() { + A * x = (A*)malloc(sizeof(A)); + A * y = new A; + delete y; + free(x); +} Index: doc/rob_thesis/examples/poly.c =================================================================== --- doc/rob_thesis/examples/poly.c (revision 29137d3a649bfcc5cdde5a1d7d6e2daeed39a49d) +++ doc/rob_thesis/examples/poly.c (revision 29137d3a649bfcc5cdde5a1d7d6e2daeed39a49d) @@ -0,0 +1,14 @@ +forall(dtype T) +void foo(T x) { + +} + +forall(dtype T) +void bar(T * y) { } + +int main() { + foo(5); + foo("baz"); + foo(foo); + bar(foo); +} Index: doc/rob_thesis/intro.tex =================================================================== --- doc/rob_thesis/intro.tex (revision 0111dc78014e8cb9bf465cd3dda3af109d744b69) +++ doc/rob_thesis/intro.tex (revision 29137d3a649bfcc5cdde5a1d7d6e2daeed39a49d) @@ -19,10 +19,15 @@ 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,5 +48,4 @@ 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,4 +61,28 @@ 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,33 +92,69 @@ 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 ? 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,41 +316,46 @@ 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 - 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 +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 - 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 +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,5 +364,5 @@ \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,24 +377,24 @@ 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,4 +410,52 @@ 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 ? 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,5 +587,5 @@ \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,6 +658,6 @@ % 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,2 +892,19 @@ 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. Index: doc/rob_thesis/thesis-frontpgs.tex =================================================================== --- doc/rob_thesis/thesis-frontpgs.tex (revision 0111dc78014e8cb9bf465cd3dda3af109d744b69) +++ doc/rob_thesis/thesis-frontpgs.tex (revision 29137d3a649bfcc5cdde5a1d7d6e2daeed39a49d) @@ -86,13 +86,32 @@ %\newpage -% % A C K N O W L E D G E M E N T S -% % ------------------------------- +% A C K N O W L E D G E M E N T S +% ------------------------------- -% \begin{center}\textbf{Acknowledgements}\end{center} +\begin{center}\textbf{Acknowledgements}\end{center} -% % I would like to thank all the little people who made this possible. -% TODO -% \cleardoublepage -% %\newpage +I would like to thank my supervisor, Professor Peter Buhr, for all of his help, including reading the many drafts of this thesis and providing guidance throughout my degree. +This work would not have been as enjoyable, nor would it have been as strong without Peter's knowledge, help, and encouragement. + +I would like to thank my readers, Professors Gregor Richards and Patrick Lam for all of their helpful feedback. + +Thanks to Aaron Moss and Thierry Delisle for many helpful discussions, both work-related and not, and for all of the work they have put into the \CFA project. +This thesis would not have been the same without their efforts. + +I thank Glen Ditchfield and Richard Bilson, for all of their help with both the design and implementation of \CFA. + +I thank my partner, Erin Blackmere, for all of her love and support. +Without her, I would not be who I am today. + +Thanks to my parents, Bob and Jackie Schluntz, for their love and support throughout my life, and for always encouraging me to be my best. + +Thanks to my best friends, Travis Bartlett, Abraham Dubrisingh, and Kevin Wu, whose companionship is always appreciated. +The time we've spent together over the past 4 years has always kept me entertained. +An extra shout-out to Kaleb Alway, Max Bardakov, Ten Bradley, and Ed Lee, with whom I've shared many a great meal; thank you for being my friend. + +Finally, I would like to acknowledge financial support in the form of a David R. Cheriton Graduate Scholarship and a corporate partnership with Huawei Ltd. + +\cleardoublepage +%\newpage % % D E D I C A T I O N Index: doc/rob_thesis/thesis.tex =================================================================== --- doc/rob_thesis/thesis.tex (revision 0111dc78014e8cb9bf465cd3dda3af109d744b69) +++ doc/rob_thesis/thesis.tex (revision 29137d3a649bfcc5cdde5a1d7d6e2daeed39a49d) @@ -118,4 +118,7 @@ \usepackage[pdftex]{graphicx} % For including graphics N.B. pdftex graphics driver +\usepackage{xcolor} +\usepackage{listings} + \input{cfa-format.tex} @@ -138,5 +141,5 @@ pdftitle={Resource Management and Tuples in \CFA}, % title: CHANGE THIS TEXT! pdfauthor={Rob Schluntz}, % author: CHANGE THIS TEXT! and uncomment this line -% pdfsubject={Subject}, % subject: CHANGE THIS TEXT! and uncomment this line + pdfsubject={Programming Languages}, % subject: CHANGE THIS TEXT! and uncomment this line % pdfkeywords={keyword1} {key2} {key3}, % list of keywords, and uncomment this line if desired pdfnewwindow=true, % links in new window Index: doc/rob_thesis/tuples.tex =================================================================== --- doc/rob_thesis/tuples.tex (revision 0111dc78014e8cb9bf465cd3dda3af109d744b69) +++ doc/rob_thesis/tuples.tex (revision 29137d3a649bfcc5cdde5a1d7d6e2daeed39a49d) @@ -161,6 +161,7 @@ \end{cfacode} +\begin{sloppypar} In addition to variables of tuple type, it is also possible to have pointers to tuples, and arrays of tuples. -Tuple types can be composed of any types, except for array types, since arrays do not carry their size around, which makes tuple assignment difficult when a tuple contains an array. +Tuple types can be composed of any types, except for array types, since array assignment is disallowed, which makes tuple assignment difficult when a tuple contains an array. \begin{cfacode} [double, int] di; @@ -169,4 +170,5 @@ \end{cfacode} This examples declares a variable of type @[double, int]@, a variable of type pointer to @[double, int]@, and an array of ten @[double, int]@. +\end{sloppypar} \subsection{Tuple Indexing} @@ -212,5 +214,5 @@ The flexible structure of tuples permits a simple and expressive function-call syntax to work seamlessly with both single- and multiple-return-value functions, and with any number of arguments of arbitrarily complex structure. -In \KWC \cite{Buhr94a,Till89}, a precursor to \CFA, there were 4 tuple coercions: opening, closing, flattening, and structuring. +In \KWC \cite{Buhr94a,Till89}, there were 4 tuple coercions: opening, closing, flattening, and structuring. Opening coerces a tuple value into a tuple of values, while closing converts a tuple of values into a single tuple value. Flattening coerces a nested tuple into a flat tuple, \ie it takes a tuple with tuple components and expands it into a tuple with only non-tuple components. @@ -218,4 +220,5 @@ In \CFA, the design has been simplified to require only the two conversions previously described, which trigger only in function call and return situations. +This simplification is a primary contribution of this thesis to the design of tuples in \CFA. Specifically, the expression resolution algorithm examines all of the possible alternatives for an expression to determine the best match. In resolving a function call expression, each combination of function value and list of argument alternatives is examined. @@ -254,5 +257,11 @@ Let $L_i$ for $i$ in $[0, n)$ represent each component of the flattened left side, $R_i$ represent each component of the flattened right side of a multiple assignment, and $R$ represent the right side of a mass assignment. -For a multiple assignment to be valid, both tuples must have the same number of elements when flattened. Multiple assignment assigns $R_i$ to $L_i$ for each $i$. +For a multiple assignment to be valid, both tuples must have the same number of elements when flattened. +For example, the following is invalid because the number of components on the left does not match the number of components on the right. +\begin{cfacode} +[int, int] x, y, z; +[x, y] = z; // multiple assignment, invalid 4 != 2 +\end{cfacode} +Multiple assignment assigns $R_i$ to $L_i$ for each $i$. That is, @?=?(&$L_i$, $R_i$)@ must be a well-typed expression. In the previous example, @[x, y] = z@, @z@ is flattened into @z.0, z.1@, and the assignments @x = z.0@ and @y = z.1@ happen. @@ -265,5 +274,5 @@ Both kinds of tuple assignment have parallel semantics, such that each value on the left side and right side is evaluated \emph{before} any assignments occur. -As a result, it is possible to swap the values in two variables without explicitly creating any temporary variables or calling a function, +As a result, it is possible to swap the values in two variables without explicitly creating any temporary variables or calling a function. \begin{cfacode} int x = 10, y = 20; @@ -296,4 +305,5 @@ \subsection{Tuple Construction} Tuple construction and destruction follow the same rules and semantics as tuple assignment, except that in the case where there is no right side, the default constructor or destructor is called on each component of the tuple. +As constructors and destructors did not exist in previous versions of \CFA or in \KWC, this is a primary contribution of this thesis to the design of tuples. \begin{cfacode} struct S; @@ -433,5 +443,5 @@ \section{Casting} In C, the cast operator is used to explicitly convert between types. -In \CFA, the cast operator has a secondary use, which is type ascription, since it force the expression resolution algorithm to choose the lowest cost conversion to the target type. +In \CFA, the cast operator has a secondary use, which is type ascription, since it forces the expression resolution algorithm to choose the lowest cost conversion to the target type. That is, a cast can be used to select the type of an expression when it is ambiguous, as in the call to an overloaded function. \begin{cfacode} @@ -487,4 +497,5 @@ \section{Polymorphism} Due to the implicit flattening and structuring conversions involved in argument passing, @otype@ and @dtype@ parameters are restricted to matching only with non-tuple types. +The integration of polymorphism, type assertions, and monomorphic specialization of tuple-assertions are a primary contribution of this thesis to the design of tuples. \begin{cfacode} forall(otype T, dtype U) @@ -524,5 +535,5 @@ It is also important to note that these calls could be disambiguated if the function return types were different, as they likely would be for a reasonable implementation of @?+?@, since the return type is used in overload resolution. Still, these semantics are a deficiency of the current argument matching algorithm, and depending on the function, differing return values may not always be appropriate. -These issues could be rectified by applying an appropriate cost to the structuring and flattening conversions, which are currently 0-cost conversions. +These issues could be rectified by applying an appropriate conversion cost to the structuring and flattening conversions, which are currently 0-cost conversions in the expression resolver. Care would be needed in this case to ensure that exact matches do not incur such a cost. \begin{cfacode} @@ -559,4 +570,7 @@ \section{Implementation} Tuples are implemented in the \CFA translator via a transformation into generic types. +Generic types are an independent contribution developed at the same time. +The transformation into generic types and the generation of tuple-specific code are primary contributions of this thesis to tuples. + The first time an $N$-tuple is seen for each $N$ in a scope, a generic type with $N$ type parameters is generated. For example, Index: doc/rob_thesis/variadic.tex =================================================================== --- doc/rob_thesis/variadic.tex (revision 0111dc78014e8cb9bf465cd3dda3af109d744b69) +++ doc/rob_thesis/variadic.tex (revision 29137d3a649bfcc5cdde5a1d7d6e2daeed39a49d) @@ -5,8 +5,8 @@ \section{Design Criteria} % TODO: better section name??? C provides variadic functions through the manipulation of @va_list@ objects. -A variadic function is one which contains at least one parameter, followed by @...@ as the last token in the parameter list. -In particular, some form of \emph{argument descriptor} is needed to inform the function of the number of arguments and their types. +In C, a variadic function is one which contains at least one parameter, followed by @...@ as the last token in the parameter list. +In particular, some form of \emph{argument descriptor} or \emph{sentinel value} is needed to inform the function of the number of arguments and their types. Two common argument descriptors are format strings or counter parameters. -It is important to note that both of these mechanisms are inherently redundant, because they require the user to explicitly specify information that the compiler already knows. +It is important to note that both of these mechanisms are inherently redundant, because they require the user to explicitly specify information that the compiler already knows \footnote{While format specifiers can convey some information the compiler does not know, such as whether to print a number in decimal or hexadecimal, the number of arguments is wholly redundant.}. This required repetition is error prone, because it is easy for the user to add or remove arguments without updating the argument descriptor. In addition, C requires the programmer to hard code all of the possible expected types. @@ -152,4 +152,5 @@ That is to say, the programmer who writes @sum@ does not need full program knowledge of every possible data type, unlike what is necessary to write an equivalent function using the standard C mechanisms. +\begin{sloppypar} Going one last step, it is possible to achieve full generality in \CFA, allowing the summation of arbitrary lists of summable types. \begin{cfacode} @@ -170,4 +171,5 @@ \end{cfacode} The \CFA translator requires adding explicit @double ?+?(int, double)@ and @double ?+?(double, int)@ functions for this call to work, since implicit conversions are not supported for assertions. +\end{sloppypar} A notable limitation of this approach is that it heavily relies on recursive assertions. @@ -226,5 +228,5 @@ In the call to @new@, @Array@ is selected to match @T@, and @Params@ is expanded to match @[int, int, int, int]@. To satisfy the assertions, a constructor with an interface compatible with @void ?{}(Array *, int, int, int)@ must exist in the current scope. -The @new@ function provides the combination of type-safe @malloc@ with a constructor call, so that it becomes impossible to forget to construct dynamically-allocated objects. +The @new@ function provides the combination of polymorphic @malloc@ with a constructor call, so that it becomes impossible to forget to construct dynamically-allocated objects. This approach provides the type-safety of @new@ in \CC, without the need to specify the allocated type, thanks to return-type inference.