Ignore:
Timestamp:
Apr 19, 2017, 10:15:45 AM (5 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
cd348e7
Parents:
221c2de (diff), de4ce0e (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/rob_thesis/conclusions.tex

    r221c2de r154fdc8  
    33%======================================================================
    44
    5 Conclusion paragraphs.
     5Adding resource management and tuples to \CFA has been a challenging design, engineering, and implementation exercise.
     6On the surface, the work may appear as a rehash of similar mechanisms in \CC.
     7However, 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.
     8All of these new features are being used by the \CFA development-team to build the \CFA runtime system.
     9
     10\section{Constructors and Destructors}
     11\CFA supports the RAII idiom using constructors and destructors.
     12There are many engineering challenges in introducing constructors and destructors, partially since \CFA is not an object-oriented language.
     13By making use of managed types, \CFA programmers are afforded an extra layer of safety and ease of use in comparison to C programmers.
     14While constructors and destructors provide a sensible default behaviour, \CFA allows experienced programmers to declare unmanaged objects to take control of object management for performance reasons.
     15Constructors and destructors as named functions fit the \CFA polymorphism model perfectly, allowing polymorphic code to use managed types seamlessly.
     16
     17\section{Tuples}
     18\CFA can express functions with multiple return values in a way that is simple, concise, and safe.
     19The addition of multiple-return-value functions naturally requires a way to use multiple return values, which begets tuple types.
     20Tuples provide two useful notions of assignment: multiple assignment, allowing simple, yet expressive assignment between multiple variables, and mass assignment, allowing a lossless assignment of a single value across multiple variables.
     21Tuples have a flexible structure that allows the \CFA type-system to decide how to restructure tuples, making it syntactically simple to pass tuples between functions.
     22Tuple types can be combined with polymorphism and tuple conversions can apply during assertion inference to produce a cohesive feel.
     23
     24\section{Variadic Functions}
     25Type-safe variadic functions, with a similar feel to variadic templates, are added to \CFA.
     26The new variadic functions can express complicated recursive algorithms.
     27Unlike variadic templates, it is possible to write @new@ as a library routine and to separately compile @ttype@ polymorphic functions.
     28Variadic functions are statically type checked and provide a user experience that is consistent with that of tuples and polymorphic functions.
     29
     30\section{Future Work}
     31\subsection{Constructors and Destructors}
     32Both \CC and Rust support move semantics, which expand the user's control of memory management by providing the ability to transfer ownership of large data, rather than forcing potentially expensive copy semantics.
     33\CFA currently does not support move semantics, partially due to the complexity of the model.
     34The design space is currently being explored with the goal of finding an alternative to move semantics that provides necessary performance benefits, while reducing the amount of repetition required to create a new type, along with the cognitive burden placed on the user.
     35
     36% One technique being evaluated is whether named return-values can be used to eliminate unnecessary temporaries \cite{Buhr94a}.
     37% For example,
     38% \begin{cfacode}
     39% struct A { ... };
     40% [A x] f(A x);
     41% [A y] g(A y);
     42% [A z] h(A z);
     43
     44% struct A a1, a2;
     45% a2 = h(g(f(a1)));
     46% \end{cfacode}
     47% Here, since both @f@'s argument and return value have the same name and type, the compiler can infer that @f@ returns its argument.
     48% With this knowledge, the compiler can reuse the storage for the argument to @f@ as the argument to @g@.  % TODO: cite Till thesis?
     49
     50Exception handling is among the features expected to be added to \CFA in the near future.
     51For exception handling to properly interact with the rest of the language, it must ensure all RAII guarantees continue to be met.
     52That is, when an exception is raised, it must properly unwind the stack by calling the destructors for any objects that live between the raise and the handler.
     53This can be accomplished either by augmenting the translator to properly emit code that executes the destructors, or by switching destructors to hook into the GCC @cleanup@ attribute \cite[6.32.1]{GCCExtensions}.
     54
     55The @cleanup@ attribute, which is attached to a variable declaration, takes a function name as an argument and schedules that routine to be executed when the variable goes out of scope.
     56\begin{cfacode}
     57struct S { int x; };
     58void __dtor_S(struct S *);
     59{
     60  __attribute__((cleanup(__dtor_S))) struct S s;
     61} // calls __dtor_S(&s)
     62\end{cfacode}
     63This mechanism is known and understood by GCC, so that the destructor is properly called in any situation where a variable goes out of scope, including function returns, branches, and built-in GCC exception handling mechanisms using libunwind.
     64
     65A caveat of this approach is that the @cleanup@ attribute only permits a function that consumes a single argument of type @T *@ for a variable of type @T@.
     66This restriction means that any destructor that consumes multiple arguments (\eg, because it is polymorphic) or any destructor that is a function pointer (\eg, because it is an assertion parameter) must be called through a local thunk.
     67For example,
     68\begin{cfacode}
     69forall(otype T)
     70struct Box {
     71  T x;
     72};
     73forall(otype T) void ^?{}(Box(T) * x); // has implicit parameters
     74
     75forall(otype T)
     76void f(T x) {
     77  T y = x;  // destructor is a function-pointer parameter
     78  Box(T) z = { x }; // destructor has multiple parameters
     79}
     80\end{cfacode}
     81currently generates the following
     82\begin{cfacode}
     83void _dtor_BoxT(  // consumes more than 1 parameter due to assertions
     84  void (*_adapter_PTT)(void (*)(), void *, void *),
     85  void (*_adapter_T_PTT)(void (*)(), void *, void *, void *),
     86  long unsigned int _sizeof_T,
     87  long unsigned int _alignof_T,
     88  void *(*_assign_T_PTT)(void *, void *),
     89  void (*_ctor_PT)(void *),
     90  void (*_ctor_PTT)(void *, void *),
     91  void (*_dtor_PT)(void *),
     92  void *x
     93);
     94
     95void f(
     96  void (*_adapter_PTT)(void (*)(), void *, void *),
     97  void (*_adapter_T_PTT)(void (*)(), void *, void *, void *),
     98  long unsigned int _sizeof_T,
     99  long unsigned int _alignof_T,
     100  void *(*_assign_TT)(void *, void *),
     101  void (*_ctor_T)(void *),
     102  void (*_ctor_TT)(void *, void *),
     103  void (*_dtor_T)(void *),
     104  void *x
     105){
     106  void *y = __builtin_alloca(_sizeof_T);
     107  // constructor call elided
     108
     109  // generic layout computation elided
     110  long unsigned int _sizeof_BoxT = ...;
     111  void *z = __builtin_alloca(_sizeof_BoxT);
     112  // constructor call elided
     113
     114  _dtor_BoxT(  // ^?{}(&z); -- _dtor_BoxT has > 1 arguments
     115    _adapter_PTT,
     116    _adapter_T_PTT,
     117    _sizeof_T,
     118    _alignof_T,
     119    _assign_TT,
     120    _ctor_T,
     121    _ctor_TT,
     122    _dtor_T,
     123    z
     124  );
     125  _dtor_T(y);  // ^?{}(&y); -- _dtor_T is a function pointer
     126}
     127\end{cfacode}
     128Further to this point, every distinct array type will require a thunk for its destructor, where array destructor code is currently inlined, since array destructors hard code the length of the array.
     129
     130For function call temporaries, new scopes have to be added for destructor ordering to remain consistent.
     131In particular, the translator currently destroys argument and return value temporary objects as soon as the statement they were created for ends.
     132In order for this behaviour to be maintained, new scopes have to be added around every statement that contains a function call.
     133Since a nested expression can raise an exception, care must be taken when destroying temporary objects.
     134One way to achieve this is to split statements at every function call, to provide the correct scoping to destroy objects as necessary.
     135For example,
     136\begin{cfacode}
     137struct S { ... };
     138void ?{}(S *, S);
     139void ^?{}(S *);
     140
     141S f();
     142S g(S);
     143
     144g(f());
     145\end{cfacode}
     146would generate
     147\begin{cfacode}
     148struct S { ... };
     149void _ctor_S(struct S *, struct S);
     150void _dtor_S(struct S *);
     151
     152{
     153  __attribute__((cleanup(_dtor_S))) struct S _tmp1 = f();
     154  __attribute__((cleanup(_dtor_S))) struct S _tmp2 =
     155    (_ctor_S(&_tmp2, _tmp1), _tmp2);
     156  __attribute__((cleanup(_dtor_S))) struct S _tmp3 = g(_tmp2);
     157} // destroy _tmp3, _tmp2, _tmp1
     158\end{cfacode}
     159Note that destructors must be registered after the temporary is fully initialized, since it is possible for initialization expressions to raise exceptions, and a destructor should never be called on an uninitialized object.
     160This requires a slightly strange looking initializer for constructor calls, where a comma expression is used to produce the value of the object being initialized, after the constructor call, conceptually bitwise copying the initialized data into itself.
     161Since this copy is wholly unnecessary, it is easily optimized away.
     162
     163A second approach is to attach an accompanying boolean to every temporary that records whether the object contains valid data, and thus whether the value should be destructed.
     164\begin{cfacode}
     165struct S { ... };
     166void _ctor_S(struct S *, struct S);
     167void _dtor_S(struct S *);
     168
     169struct _tmp_bundle_S {
     170  bool valid;
     171  struct S value;
     172};
     173
     174void _dtor_tmpS(struct _tmp_bundle_S * ret) {
     175  if (ret->valid) {
     176    _dtor_S(&ret->value);
     177  }
     178}
     179
     180{
     181  __attribute__((cleanup(_dtor_tmpS))) struct _tmp_bundle_S _tmp1 = { 0 };
     182  __attribute__((cleanup(_dtor_tmpS))) struct _tmp_bundle_S _tmp2 = { 0 };
     183  __attribute__((cleanup(_dtor_tmpS))) struct _tmp_bundle_S _tmp3 = { 0 };
     184  _tmp2.value = g(
     185    (_ctor_S(
     186      &_tmp2.value,
     187      (_tmp1.value = f(), _tmp1.valid = 1, _tmp1.value)
     188    ), _tmp2.valid = 1, _tmp2.value)
     189  ), _tmp3.valid = 1, _tmp3.value;
     190} // destroy _tmp3, _tmp2, _tmp1
     191\end{cfacode}
     192In particular, the boolean is set immediately after argument construction and immediately after return value copy.
     193The boolean is checked as a part of the @cleanup@ routine, forwarding to the object's destructor if the object is valid.
     194One such type and @cleanup@ routine needs to be generated for every type used in a function parameter or return value.
     195
     196The former approach generates much simpler code, however splitting expressions requires care to ensure that expression evaluation order does not change.
     197Expression ordering has to be performed by a full compiler, so it is possible that the latter approach would be more suited to the \CFA prototype, whereas the former approach is clearly the better option in a full compiler.
     198More investigation is needed to determine whether the translator's current design can easily handle proper expression ordering.
     199
     200As discussed in Section \ref{s:implicit_copy_construction}, return values are destructed with a different @this@ pointer than they are constructed with.
     201This problem can be easily fixed once a full \CFA compiler is built, since it would have full control over the call/return mechanism.
     202In particular, since the callee is aware of where it needs to place the return value, it can construct the return value directly, rather than bitwise copy the internal data.
     203
     204Currently, the special functions are always auto-generated, except for generic types where the type parameter does not have assertions for the corresponding operation.
     205For example,
     206\begin{cfacode}
     207forall(dtype T | sized(T) | { void ?{}(T *); })
     208struct S { T x; };
     209\end{cfacode}
     210only auto-generates the default constructor for @S@, since the member @x@ is missing the other 3 special functions.
     211Once deleted functions have been added, function generation can make use of this information to disable generation of special functions when a member has a deleted function.
     212For example,
     213\begin{cfacode}
     214struct A {};
     215void ?{}(A *) = delete;
     216struct S { A x; };  // does not generate void ?{}(S *);
     217\end{cfacode}
     218
     219Unmanaged objects and their interactions with the managed \CFA environment are an open problem that deserves greater attention.
     220In particular, the interactions between unmanaged objects and copy semantics are subtle and can easily lead to errors.
     221It is possible that the compiler should mark some of these situations as errors by default, and possibly conditionally emit warnings for some situations.
     222Another possibility is to construct, destruct, and assign unmanaged objects using the intrinsic and auto-generated functions.
     223A more thorough examination of the design space for this problem is required.
     224
     225Currently, the \CFA translator does not support any warnings.
     226Ideally, the translator should support optional warnings in the case where it can detect that an object has been constructed twice.
     227For example, forwarding constructor calls are guaranteed to initialize the entire object, so redundant constructor calls can cause problems such as memory leaks, while looking innocuous to a novice user.
     228\begin{cfacode}
     229struct B { ... };
     230struct A {
     231  B x, y, z;
     232};
     233void ?{}(A * a, B x) {
     234  // y, z implicitly default constructed
     235  (&a->x){ ... }; // explicitly construct x
     236} // constructs an entire A
     237void ?{}(A * a) {
     238  (&a->y){}; // initialize y
     239  a{ (B){ ... } }; // forwarding constructor call
     240                   // initializes entire object, including y
     241}
     242\end{cfacode}
     243
     244Finally, while constructors provide a mechanism for establishing invariants, there is currently no mechanism for maintaining invariants without resorting to opaque types.
     245That 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.
     246A 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.
     247This approach could be added to \CFA, but it requires an idiomatic way of specifying what code is privileged.
     248One possibility is to tie access control into an eventual module system.
     249
     250\subsection{Tuples}
     251Named result values are planned, but not yet implemented.
     252This feature ties nicely into named tuples, as seen in D and Swift.
     253
     254Currently, tuple flattening and structuring conversions are 0-cost.
     255This 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.
     256Adding an appropriate cost function to tuple conversions will allow tuples to interact with the rest of the programming language more cohesively.
     257
     258\subsection{Variadic Functions}
     259Use of @ttype@ functions currently relies heavily on recursion.
     260\CC has opened variadic templates up so that recursion is not strictly necessary in some cases, and it would be interesting to see if any such cases can be applied to \CFA.
     261
     262\CC supports variadic templated data-types, making it possible to express arbitrary length tuples, arbitrary parameter function objects, and more with generic types.
     263Currently, \CFA does not support @ttype@-parameter generic-types, though there does not appear to be a technical reason that it cannot.
     264Notably, opening up support for this makes it possible to implement the exit form of scope guard (see section \ref{s:ResMgmt}), making it possible to call arbitrary functions at scope exit in idiomatic \CFA.
Note: See TracChangeset for help on using the changeset viewer.