Index: doc/papers/general/Paper.tex =================================================================== --- doc/papers/general/Paper.tex (revision 0188a0bce49abf2833b0cb95e8193b3beaaadced) +++ doc/papers/general/Paper.tex (revision 804b57e31aa94e0c84b8dbfd4fb6997a6e25868a) @@ -148,5 +148,5 @@ The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from commercial operating-systems to hobby projects. This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more. -The \cite{TIOBE} ranks the top 5 most popular programming languages as: Java 16\%, \Textbf{C 7\%}, \Textbf{\CC 5\%}, \Csharp 4\%, Python 4\% = 36\%, where the next 50 languages are less than 3\% each with a long tail. +The TIOBE\cite{TIOBE} ranks the top 5 most popular programming languages as: Java 16\%, \Textbf{C 7\%}, \Textbf{\CC 5\%}, \Csharp 4\%, Python 4\% = 36\%, where the next 50 languages are less than 3\% each with a long tail. The top 3 rankings over the past 30 years are: \lstDeleteShortInline@% @@ -185,5 +185,5 @@ \label{sec:poly-fns} -\CFA{}\hspace{1pt}'s polymorphism was originally formalized by \cite{Ditchfield92}, and first implemented by \cite{Bilson03}. +\CFA{}\hspace{1pt}'s polymorphism was originally formalized by Ditchfield\cite{Ditchfield92}, and first implemented by Bilson\cite{Bilson03}. The signature feature of \CFA is parametric-polymorphic functions~\cite{forceone:impl,Cormack90,Duggan96} with functions generalized using a @forall@ clause (giving the language its name): \begin{lstlisting} @@ -258,5 +258,5 @@ } \end{lstlisting} -Within the block, the nested version of @<@ performs @>@ and this local version overrides the built-in @<@ so it is passed to @qsort@. +Within the block, the nested version of @??@ and this local version overrides the built-in @?0` = 5; $\C{// change quotient}$ bar( qr`.1`, qr ); $\C{// pass remainder and quotient/remainder}$ -rem = [42, div( 13, 5 )]`.0.1`; $\C{// access 2nd component of 1st component of tuple expression}$ +rem = [div( 13, 5 ), 42]`.0.1`; $\C{// access 2nd component of 1st component of tuple expression}$ \end{lstlisting} @@ -730,5 +728,5 @@ \end{lstlisting} Hence, function parameter and return lists are flattened for the purposes of type unification allowing the example to pass expression resolution. -This relaxation is possible by extending the thunk scheme described by~\cite{Bilson03}. +This relaxation is possible by extending the thunk scheme described by Bilson\cite{Bilson03}. Whenever a candidate's parameter structure does not exactly match the formal parameter's structure, a thunk is generated to specialize calls to the actual function: \begin{lstlisting} @@ -901,4 +899,31 @@ \end{comment} +\section{Improved Procedural Paradigm} + +It is important to the design team that \CFA subjectively ``feel like'' C to user programmers. +An important part of this subjective feel is maintaining C's procedural programming paradigm, as opposed to the object-oriented paradigm of other systems languages such as \CC and Rust. +Maintaining this procedural paradigm means that coding patterns that work in C will remain not only functional but idiomatic in \CFA, reducing the mental burden of retraining C programmers and switching between C and \CFA development. +Nonetheless, some features of object-oriented languages are undeniably convienient, and the \CFA design team has attempted to adapt them to a procedural paradigm so as to incorporate their benefits into \CFA; two of these features are resource management and name scoping. + +\subsection{Constructors and Destructors} + +One of the strengths of C is the control over memory management it gives programmers, allowing resource release to be more consistent and precisely timed than is possible with garbage-collected memory management. +However, this manual approach to memory management is often verbose, and it is useful to manage resources other than memory (\eg file handles) using the same mechanism as memory. +\CC is well-known for an approach to manual memory management that addresses both these issues, Resource Allocation Is Initialization (RAII), implemented by means of special \emph{constructor} and \emph{destructor} functions; we have implemented a similar feature in \CFA. + +\TODO{Fill out section. Mention field-constructors and at-equal escape hatch to C-style initialization. Probably pull some text from Rob's thesis for first draft.} + +\subsection{@with@ Statement} + +In any programming language, some functions have a naturally close relationship with a particular data type. +Object-oriented programming allows this close relationship to be codified in the language by making such functions \emph{class methods} of their related data type. +Class methods have certain privileges with respect to their associated data type, notably un-prefixed access to the fields of that data type. +When writing C functions in an object-oriented style, this un-prefixed access is swiftly missed, as access to fields of a @Foo* f@ requires an extra three characters @f->@ every time, which disrupts coding flow and clutters the produced code. + +\TODO{Fill out section. Be sure to mention arbitrary expressions in with-blocks, recent change driven by Thierry to prioritize field name over parameters.} + +\section{References} + +\TODO{Pull draft text from user manual; make sure to discuss nested references and rebind operator drawn from } \section{Evaluation} @@ -1013,5 +1038,5 @@ In contrast, \CFA has a single facility for polymorphic code supporting type-safe separate-compilation of polymorphic functions and generic (opaque) types, which uniformly leverage the C procedural paradigm. The key mechanism to support separate compilation is \CFA's \emph{explicit} use of assumed properties for a type. -Until \CC~\cite{C++Concepts} are standardized (anticipated for \CCtwenty), \CC provides no way to specify the requirements of a generic function in code beyond compilation errors during template expansion; +Until \CC concepts~\cite{C++Concepts} are standardized (anticipated for \CCtwenty), \CC provides no way to specify the requirements of a generic function in code beyond compilation errors during template expansion; furthermore, \CC concepts are restricted to template polymorphism. @@ -1021,17 +1046,17 @@ In \CFA terms, all Cyclone polymorphism must be dtype-static. While the Cyclone design provides the efficiency benefits discussed in Section~\ref{sec:generic-apps} for dtype-static polymorphism, it is more restrictive than \CFA's general model. -\cite{Smith98} present Polymorphic C, an ML dialect with polymorphic functions and C-like syntax and pointer types; it lacks many of C's features, however, most notably structure types, and so is not a practical C replacement. - -\cite{obj-c-book} is an industrially successful extension to C. +Smith and Volpano~\cite{Smith98} present Polymorphic C, an ML dialect with polymorphic functions, C-like syntax, and pointer types; it lacks many of C's features, however, most notably structure types, and so is not a practical C replacement. + +Objective-C~\cite{obj-c-book} is an industrially successful extension to C. However, Objective-C is a radical departure from C, using an object-oriented model with message-passing. Objective-C did not support type-checked generics until recently \cite{xcode7}, historically using less-efficient runtime checking of object types. -The~\cite{GObject} framework also adds object-oriented programming with runtime type-checking and reference-counting garbage-collection to C; +The GObject~\cite{GObject} framework also adds object-oriented programming with runtime type-checking and reference-counting garbage-collection to C; these features are more intrusive additions than those provided by \CFA, in addition to the runtime overhead of reference-counting. -\cite{Vala} compiles to GObject-based C, adding the burden of learning a separate language syntax to the aforementioned demerits of GObject as a modernization path for existing C code-bases. +Vala~\cite{Vala} compiles to GObject-based C, adding the burden of learning a separate language syntax to the aforementioned demerits of GObject as a modernization path for existing C code-bases. Java~\cite{Java8} included generic types in Java~5, which are type-checked at compilation and type-erased at runtime, similar to \CFA's. However, in Java, each object carries its own table of method pointers, while \CFA passes the method pointers separately to maintain a C-compatible layout. Java is also a garbage-collected, object-oriented language, with the associated resource usage and C-interoperability burdens. -D~\cite{D}, Go, and~\cite{Rust} are modern, compiled languages with abstraction features similar to \CFA traits, \emph{interfaces} in D and Go and \emph{traits} in Rust. +D~\cite{D}, Go, and Rust~\cite{Rust} are modern, compiled languages with abstraction features similar to \CFA traits, \emph{interfaces} in D and Go and \emph{traits} in Rust. However, each language represents a significant departure from C in terms of language model, and none has the same level of compatibility with C as \CFA. D and Go are garbage-collected languages, imposing the associated runtime overhead. @@ -1054,5 +1079,5 @@ \CCeleven introduced @std::tuple@ as a library variadic template structure. Tuples are a generalization of @std::pair@, in that they allow for arbitrary length, fixed-size aggregation of heterogeneous values. -Operations include @std::get@ to extract vales, @std::tie@ to create a tuple of references used for assignment, and lexicographic comparisons. +Operations include @std::get@ to extract values, @std::tie@ to create a tuple of references used for assignment, and lexicographic comparisons. \CCseventeen proposes \emph{structured bindings}~\cite{Sutter15} to eliminate pre-declaring variables and use of @std::tie@ for binding the results. 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. @@ -1068,5 +1093,5 @@ The goal of \CFA is to provide an evolutionary pathway for large C development-environments to be more productive and safer, while respecting the talent and skill of C programmers. While other programming languages purport to be a better C, they are in fact new and interesting languages in their own right, but not C extensions. -The purpose of this paper is to introduce \CFA, and showcase two language features that illustrate the \CFA type-system and approaches taken to achieve the goal of evolutionary C extension. +The purpose of this paper is to introduce \CFA, and showcase language features that illustrate the \CFA type-system and approaches taken to achieve the goal of evolutionary C extension. The contributions are a powerful type-system using parametric polymorphism and overloading, generic types, and tuples, which all have complex interactions. The work is a challenging design, engineering, and implementation exercise. Index: doc/working/assertion_resolution.md =================================================================== --- doc/working/assertion_resolution.md (revision 804b57e31aa94e0c84b8dbfd4fb6997a6e25868a) +++ doc/working/assertion_resolution.md (revision 804b57e31aa94e0c84b8dbfd4fb6997a6e25868a) @@ -0,0 +1,62 @@ +The prototype system uses a 5-tuple for expression cost: +1. *unsafe*: unsafe conversion cost +2. *poly*: count of parameters and return types bound to a polymorphic type +3. *vars*: count of polymorphic type variables +4. -*spec*: count of polymorphic type specializations and type assertions, lowers cost + * e.g. given `dtype T` `T*` has spec 1, `T**` has spec 2, and each type assertion also has spec 1 +5. *safe*: safe conversion cost + +Note that in this framework, type assertions are bound to their unique minimum-cost resolution (if extant), but unlike the CFA'03, the cost of type assertion resolution does not change the cost of the overall expression resolution. In particular, it is possible to defer type assertion resolution arbitrarily late in expression resolution without changing the cost of any interpretation that has satisfiable type assertions. This means that we can defer assertion resolution until all the expressions explicitly provided in the user code ("primary expressions") are tentatively resolved. + +Even after resolving all the primary expressions, there may be types in the assertions which remain polymorphic. I will call these "auxiliary types", as in the following example (drawn from the `multi_type` test in the prototype repository): + +``` +struct a {}; +struct b {}; + +forall(dtype A, dtype B | { B foo(A); A bar(B); }) +A baz(A); + +b foo(a); +a bar(b); + +a x; +baz(x); +``` + +In the course of resolving this expression, `A` is obviously bound to `a`, but `B` is left unbound by the primary expressions, an auxiliary type. There is, however, a unique min-cost resolution for this, where `B` is bound to `b`. In the cost model of the prototype system, if there is a unique min-cost mutually-satisfying resolution for the two type assertions, the cost of resolving `baz(x)` is (0, 2, 2, -2, 0). + +The most-common failure case for type assertions in CFA is a set of partial specializations of auxilliary types that does not ever specialize to a concrete type, as in this example (drawn from the `exp` test in the prototype repository -- note that an equivalent to the `make` function shows up fairly often as an implicit conversion from `void*` to any other pointer type, and `ctor` and `dtor` correspond to two of the common `otype` constraints): + +``` +struct base {}; +forall(dtype T) struct box {}; + +void ctor(base); +void dtor(base); + +forall(dtype T | { void ctor(T); void dtor(T); }) +void ctor(box(T)); +forall(dtype T | { void ctor(T); void dtor(T); }) +void dtor(box(T)); + +forall(dtype S | { void ctor(S); void dtor(S); }) +void f(box(S)); + +forall(dtype Q | { void ctor(Q); void dtor(Q); }) +Q make(); + +f( make() ); +``` + +`make()` has a cost of (0, 1, 1, -3, 0) for any binding of `ctor` and `dtor` (spec is -2 for the constraints, -1 for the partially-specialized polymorphic type `box(Q)`). `f( make() )` then forces a binding `Q => box(S)`, with a total expression cost of (0, 2, 2, -6, 0) for any satisfying resolution of the four constraints (`ctor` and `dtor` on `Q` and `S`). The given `ctor` and `dtor` for `box(T)` will satisfy the constraints on `Q` if `S` can be satisfied, so the question is what to bind the auxiliary type `S` to: `base` would work (at zero cost), as would `box(T)` (at cost (0, 1, 1, -3, 0)), provided we can bind the auxiliary type `T`, a recursive case of exactly the same problem. + +Now, at this point, in either the prototype cost model or that in CFA-CC, it should be clear that `S => base` is the cheapest resolution, which should be chosen. The prototype model has the advantage that it has already calculated the cost for `S => box(T)` (assuming a satisfactory `T`), while CFA-CC would determine the cost of satisfying `T` to add to the cost of `S => box(T)`. Since `T` can be `box(box(... box(base) ...))` nested arbitrarily deeply, there are an infinite number of possible bindings, and this computation does not terminate without the imposition of a limit on depth of recursive type assertion resolution. + +However, given this problem, a few observations can be made. Firstly, all satisfactory bindings of auxiliary types will be concrete types -- that is, they will not include any unbound type variables. Secondly, since type assertion resolution does not allow conversions (at least in the prototype system -- there may be type conversions to match a type variable, but its assertions cannot use implicit conversions), a concrete match for an assertion parameter will always be cheaper than a polymorphic match for an assertion parameter (which may recursively add more type assertions). + +It follows, then, that if a mutually-satisfactory set of concrete matches for all assertion parameters can be found, that there is no cheaper set of matches including more polymorphic matches, and thus no need to attempt to recursively resolve further type assertions of potential polymorphic matches. Thus, given some set of concrete matches for all type assertions, if there is a unique min-cost such set, it can safely be used, whereas if there is no uniquely-minimal set, then the assertion set is ambiguous, as there will not be any cheaper resolution. If there is no concrete match (e.g. remove `ctor(base)` and `dtor(base)` from the example above), then the calculation may still recurse infinitely (as discussed above), however it is possible this sort of cycle could be precisely detected and terminated on, or, alternately, the existing approach of limiting depth of recursive type assertion resolution should suffice in practice. + +I further argue that in reasonable code the depth at which such concrete solutions can be found is likely to be fairly small, by appeal to structural-induction-based handwaving. I posit that any *useful* polymorphic function either (1) does not satisfy its own type assertions or (2) only satisfies any of its own type assertions through partial specialization of the type. `f` above would be an example of (1), while `ctor` and `dtor` would be an example of (2). `ctor` and `dtor` do satisfy their own type assertions, with the binding `T => box(T')`. However, any object that exists in the system must have a finitely-expressible type (generally with a nesting level bounded by a small natural number), so there should be very few repetitions of this cycle before an appropriate concrete type is discovered. This informal argument also applies if the cycle is composed of two or more functions which satisfy each other's type assertions. While it is syntactically and semantically legal to write a function that falls into neither category, its addition cannot make any previously-unresolvable code resolvable, and thus it is unlikely to exist in user code. An example of such a function would be this, clearly useless: `forall(dtype T | { T* f(T*); } ) T* f(T*);` + +In conclusion, the existing CFA-CC compiler essentially does a depth-first exploration of the space of possible resolutions of auxiliary types (up to bounded depth); a breadth-first approach would seem likely to be more efficient in practice, as it could be terminated at the first depth any solution was found with a minimal-cost solution or ambiguous result. This does not remove the necessity for an assertion recursion limit, but should prevent the compiler from reaching that limit as often in practice.