Changeset f92aa32


Ignore:
Timestamp:
Apr 7, 2017, 6:25:23 PM (4 years ago)
Author:
Rob Schluntz <rschlunt@…>
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:
2ccb93c
Parents:
c51b5a3
Message:

thesis conclusions and editting pass

Location:
doc/rob_thesis
Files:
3 added
8 edited

Legend:

Unmodified
Added
Removed
  • doc/rob_thesis/cfa-format.tex

    rc51b5a3 rf92aa32  
    7272  morecomment=[n]{/+}{+/},
    7373  morecomment=[n][\color{blue}]{/++}{+/},
     74  % Options
     75  sensitive=true
     76}
     77
     78\lstdefinelanguage{rust}{
     79  % Keywords
     80  morekeywords=[1]{
     81    abstract, alignof, as, become, box,
     82    break, const, continue, crate, do,
     83    else, enum, extern, false, final,
     84    fn, for, if, impl, in,
     85    let, loop, macro, match, mod,
     86    move, mut, offsetof, override, priv,
     87    proc, pub, pure, ref, return,
     88    Self, self, sizeof, static, struct,
     89    super, trait, true,  type, typeof,
     90    unsafe, unsized, use, virtual, where,
     91    while, yield
     92  },
     93  % Strings
     94  morestring=[b]{"},
     95  % Comments
     96  comment=[l]{//},
     97  morecomment=[s]{/*}{*/},
    7498  % Options
    7599  sensitive=true
     
    155179  \lstset{
    156180    language = D,
     181    style=defaultStyle,
     182    #1
     183  }
     184}{}
     185
     186\lstnewenvironment{rustcode}[1][]{
     187  \lstset{
     188    language = rust,
    157189    style=defaultStyle,
    158190    #1
  • doc/rob_thesis/conclusions.tex

    rc51b5a3 rf92aa32  
    33%======================================================================
    44
    5 Conclusion paragraphs.
     5\section{Constructors and Destructors}
     6\CFA supports the RAII idiom using constructors and destructors.
     7There are many engineering challenges in introducing constructors and destructors, partially since \CFA is not an object-oriented language.
     8By making use of managed types, \CFA programmers are afforded an extra layer of safety and ease of use in comparison to C programmers.
     9While 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.
     10Constructors and destructors as named functions fit the \CFA polymorphism model perfectly, allowing polymorphic code to use managed types seamlessly.
     11
     12\section{Tuples}
     13\CFA can express functions with multiple return values in a way that is simple, concise, and safe.
     14The addition of multiple-return-value functions naturally requires a way to use multiple return values, which begets tuple types.
     15Tuples 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.
     16Tuples 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.
     17Tuple types can be combined with polymorphism and tuple conversions can apply during assertion inference to produce a cohesive feel.
     18
     19\section{Variadic Functions}
     20Type-safe variadic functions of a similar feel to variadic templates are added to \CFA.
     21The new variadic functions can express complicated recursive algorithms.
     22Unlike variadic templates, it is possible to write @new@ as a library routine and to separately compile @ttype@ polymorphic functions.
     23Variadic functions are statically type checked and provide a user experience that is consistent with that of tuples and polymorphic functions.
    624
    725\section{Future Work}
    8 
    926\subsection{Constructors and Destructors}
    10 % TODO: discuss move semantics; they haven't been implemented, but could be. Currently looking at alternative models.
    11 
    12 % TODO: discuss exceptions
    13 
    14 % TODO: fix return value destruction in full compiler
    15 
    16 % TODO: once deleted functions are added, unions can have deleted standard functions, like C++11 (may not need to mention this again...)
    17 
    18 % TODO: better study and fix the ways @= objects interact with the rest of the world (e.g. provide @= equivalent for assignment, or otherwise have @= objects default to using intrinsic/autogen ops?)
    19 
    20 
     27Both \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.
     28\CFA currently does not support move semantics, partially due to the complexity of the model.
     29The 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.
     30
     31Exception handling is among the features expected to be added to \CFA in the near future.
     32For exception handling to properly interact with the rest of the language, it must ensure all RAII guarantees continue to be met.
     33That 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.
     34This 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}.
     35
     36The @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.
     37\begin{cfacode}
     38struct S { int x; };
     39void __dtor_S(struct S *);
     40{
     41  __attribute__((cleanup(__dtor_S))) struct S s;
     42} // calls __dtor_S(&s)
     43\end{cfacode}
     44This 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.
     45
     46A caveat of this approach is that the @cleanup@ attribute only permits a name that refers to a function that consumes a single argument of type @T *@ for a variable of type @T@.
     47This means that any destructor that consumes multiple arguments (e.g., because it is polymorphic) or any destructor that is a function pointer (e.g., because it is an assertion parameter) must be called through a local thunk.
     48For example,
     49\begin{cfacode}
     50forall(otype T)
     51struct Box {
     52  T x;
     53};
     54forall(otype T) void ^?{}(Box(T) * x);
     55
     56forall(otype T)
     57void f(T x) {
     58  T y = x;
     59  Box(T) z = { x };
     60}
     61\end{cfacode}
     62currently generates the following
     63\begin{cfacode}
     64void _dtor_BoxT(  // consumes more than 1 parameter due to assertions
     65  void (*_adapter_PTT)(void (*)(), void *, void *),
     66  void (*_adapter_T_PTT)(void (*)(), void *, void *, void *),
     67  long unsigned int _sizeof_T,
     68  long unsigned int _alignof_T,
     69  void *(*_assign_T_PTT)(void *, void *),
     70  void (*_ctor_PT)(void *),
     71  void (*_ctor_PTT)(void *, void *),
     72  void (*_dtor_PT)(void *),
     73  void *x
     74);
     75
     76void f(
     77  void (*_adapter_PTT)(void (*)(), void *, void *),
     78  void (*_adapter_T_PTT)(void (*)(), void *, void *, void *),
     79  long unsigned int _sizeof_T,
     80  long unsigned int _alignof_T,
     81  void *(*_assign_TT)(void *, void *),
     82  void (*_ctor_T)(void *),
     83  void (*_ctor_TT)(void *, void *),
     84  void (*_dtor_T)(void *),
     85  void *x
     86){
     87  void *y = __builtin_alloca(_sizeof_T);
     88  // constructor call elided
     89
     90  // generic layout computation elided
     91  long unsigned int _sizeof_BoxT = ...;
     92  void *z = __builtin_alloca(_sizeof_BoxT);
     93  // constructor call elided
     94
     95  _dtor_BoxT(  // ^?{}(&z); -- _dtor_BoxT has > 1 arguments
     96    _adapter_PTT,
     97    _adapter_T_PTT,
     98    _sizeof_T,
     99    _alignof_T,
     100    _assign_TT,
     101    _ctor_T,
     102    _ctor_TT,
     103    _dtor_T,
     104    z
     105  );
     106  _dtor_T(y);  // ^?{}(&y); -- _dtor_T is a function pointer
     107}
     108\end{cfacode}
     109Further 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.
     110
     111For function call temporaries, new scopes have to be added for destructor ordering to remain consistent.
     112In particular, the translator currently destroys argument and return value temporary objects as soon as the statement they were created for ends.
     113In order for this behaviour to be maintained, new scopes have to be added around every statement that contains a function call.
     114Since a nested expression can raise an exception, care must be taken when destroying temporary objects.
     115One way to achieve this is to split statements at every function call, to provide the correct scoping to destroy objects as necessary.
     116For example,
     117\begin{cfacode}
     118struct S { ... };
     119void ?{}(S *, S);
     120void ^?{}(S *);
     121
     122S f();
     123S g(S);
     124
     125g(f());
     126\end{cfacode}
     127would generate
     128\begin{cfacode}
     129struct S { ... };
     130void _ctor_S(struct S *, struct S);
     131void _dtor_S(struct S *);
     132
     133{
     134  __attribute__((cleanup(_dtor_S))) struct S _tmp1 = f();
     135  __attribute__((cleanup(_dtor_S))) struct S _tmp2 =
     136    (_ctor_S(&_tmp2, _tmp1), _tmp2);
     137  __attribute__((cleanup(_dtor_S))) struct S _tmp3 = g(_tmp2);
     138} // destroy _tmp3, _tmp2, _tmp1
     139\end{cfacode}
     140Note 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.
     141This 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.
     142Since this copy is wholly unnecessary, it is easily optimized away.
     143
     144A 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.
     145\begin{cfacode}
     146struct S { ... };
     147void _ctor_S(struct S *, struct S);
     148void _dtor_S(struct S *);
     149
     150struct __tmp_bundle_S {
     151  bool valid;
     152  struct S value;
     153};
     154
     155void _dtor_tmpS(struct __tmp_bundle_S * ret) {
     156  if (ret->valid) {
     157    _dtor_S(&ret->value);
     158  }
     159}
     160
     161{
     162  __attribute__((cleanup(_dtor_tmpS))) struct __tmp_bundle_S _tmp1 = { 0 };
     163  __attribute__((cleanup(_dtor_tmpS))) struct __tmp_bundle_S _tmp2 = { 0 };
     164  __attribute__((cleanup(_dtor_tmpS))) struct __tmp_bundle_S _tmp3 = { 0 };
     165  _tmp2.value = g(
     166    (_ctor_S(
     167      &_tmp2.value,
     168      (_tmp1.value = f(), _tmp1.valid = 1, _tmp1.value)
     169    ), _tmp2.valid = 1, _tmp2.value)
     170  ), _tmp3.valid = 1, _tmp3.value;
     171} // destroy _tmp3, _tmp2, _tmp1
     172\end{cfacode}
     173In particular, the boolean is set immediately after argument construction and immediately after return value copy.
     174The boolean is checked as a part of the @cleanup@ routine, forwarding to the object's destructor if the object is valid.
     175One such type and @cleanup@ routine needs to be generated for every type used in a function parameter or return value.
     176
     177The former approach generates much simpler code, however splitting expressions requires care to ensure that expression evaluation order does not change.
     178Expression 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.
     179More investigation is needed to determine whether the translator's current design can easily handle proper expression ordering.
     180
     181As discussed in Section \ref{s:implicit_copy_construction}, return values are destructed with a different @this@ pointer than they are constructed with.
     182This problem can be easily fixed once a full \CFA compiler is built, since it would have full control over the call/return mechanism.
     183In 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.
     184
     185Currently, the special functions are always auto-generated, except for generic types where the type parameter does not have assertions for the corresponding operation.
     186For example,
     187\begin{cfacode}
     188forall(dtype T | sized(T) | { void ?{}(T *); })
     189struct S { T x; };
     190\end{cfacode}
     191will only auto-generate the default constructor for @S@, since the member @x@ is missing the other 3 special functions.
     192Once 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.
     193For example,
     194\begin{cfacode}
     195struct A {};
     196void ?{}(A *) = delete;
     197struct S { A x; };  // does not generate void ?{}(S *);
     198\end{cfacode}
     199
     200Unmanaged objects and their interactions with the managed \CFA environment are an open problem that deserves greater attention.
     201In particular, the interactions between unmanaged objects and copy semantics are subtle and can easily lead to errors.
     202It is possible that the compiler should mark some of these situations as errors by default, and possibly conditionally emit warnings for some situations.
     203Another possibility is to construct, destruct, and assign unmanaged objects using the intrinsic and auto-generated functions.
     204A more thorough examination of the design space for this problem is required.
     205
     206Currently, the \CFA translator does not support any warnings.
     207Ideally, the translator should support optional warnings in the case where it can detect that an object has been constructed twice.
     208For 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.
     209\begin{cfacode}
     210struct B { ... };
     211struct A {
     212        B x, y, z;
     213};
     214void ?{}(A * a, B x) {
     215        // y, z implicitly default constructed
     216        (&a->x){ ... }; // explicitly construct x
     217} // constructs an entire A
     218void ?{}(A * a) {
     219        (&a->y){}; // initialize y
     220        a{ (B){ ... } }; // forwarding constructor call
     221                         // initializes entire object, including y
     222}
     223\end{cfacode}
     224
     225Finally, while constructors provide a mechanism for establishing invariants, there is currently no mechanism for maintaining invariants without resorting to opaque types.
     226That is, structure fields can be accessed and modified by any block of code without restriction, so while it's possible to ensure that an object is initially set to a valid state, it isn't possible to ensure that it remains in a consistent state throughout its lifetime.
     227A 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.
     228This approach could be added to \CFA, but it requires an idiomatic way of specifying what code is privileged.
     229One possibility is to tie access control into an eventual module system.
    21230
    22231\subsection{Tuples}
    23 
    24 % TODO: named return values are not currently implemented in CFA - tie in with named tuples?
    25 
    26 % TODO: tuples are allowed in expressions, exact meaning is defined by operator overloading (e.g. can add tuples). An important caveat to note is that it is currently impossible to allow adding two triples but prevent adding a pair with a quadruple (single flattening/structuring conversions are implicit, only total number of components matters). May be able to solve this with more nuanced conversion rules
     232Named result values are planned, but not yet implemented.
     233This feature ties nicely into named tuples, as seen in D and Swift.
     234
     235Currently, tuple flattening and structuring conversions are 0-cost.
     236This 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.
     237Adding an appropriate cost function to tuple conversions will allow tuples to interact with the rest of the programming language more cohesively.
    27238
    28239\subsection{Variadic Functions}
    29 % TODO: look into 'nicer' expansion syntax
    30 
    31 % TODO: consider more sophisticated argument matching algorithms, e.g. forall(ttype Params) void f(Params, Params); f(1,2); f(1,2,3,4); => f([1], [2]); f([1,2], [3,4]); => okay if Params can be bound to a type that is consistent throughout the expression's type
    32 
    33 
     240Use of @ttype@ functions currently relies heavily on recursion.
     241\CC has opened variadic templates up so that recursion isn't strictly necessary in some cases, and it would be interesting to see if any such cases can be applied to \CFA.
     242
     243\CC supports variadic templated data types, making it possible to express arbitrary length tuples, arbitrary parameter function objects, and more with generic types.
     244Currently, \CFA does not support @ttype@-parameter generic types, though there does not appear to be a technical reason that it cannot.
     245Notably, 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.
  • doc/rob_thesis/ctordtor.tex

    rc51b5a3 rf92aa32  
    33%======================================================================
    44
    5 % TODO: as an experiment, implement Andrei Alexandrescu's ScopeGuard http://www.drdobbs.com/cpp/generic-change-the-way-you-write-excepti/184403758?pgno=2
     5% TODO now: as an experiment, implement Andrei Alexandrescu's ScopeGuard http://www.drdobbs.com/cpp/generic-change-the-way-you-write-excepti/184403758?pgno=2
    66% doesn't seem possible to do this without allowing ttype on generic structs?
    7 
    8 % If a Cforall constructor is in scope, C style initialization is
    9 % disabled by default.
    10 % * initialization rule: if any constructor is in scope for type T, try
    11 %   to find a matching constructor for the call. If there are no
    12 %   constructors in scope for type T, then attempt to fall back on
    13 %   C-style initialization.
    14 % + if this rule was not in place, it would be easy to accidentally
    15 %   use C-style initialization in certain cases, which could lead to
    16 %   subtle errors [2]
    17 % - this means we need special syntax if we want to allow users to force
    18 %   a C-style initialization (to give users more control)
    19 % - two different declarations in the same scope can be implicitly
    20 %   initialized differently. That is, there may be two objects of type
    21 %   T that are initialized differently because there is a constructor
    22 %   definition between them. This is not technically specific to
    23 %   constructors.
    24 
    25 % C-style initializers can be accessed with @= syntax
    26 % + provides a way to get around the requirement of using a constructor
    27 %   (for advanced programmers only)
    28 % - can break invariants in the type => unsafe
    29 % * provides a way of asserting that a variable is an instance of a
    30 %   C struct (i.e. a POD struct), and so will not be implicitly
    31 %   destructed (this can be useful at times, maybe mitigates the need
    32 %   for move semantics?) [3]
    33 % + can modernize a code base one step at a time
    34 
    35 % Cforall constructors can be used in expressions to initialize any
    36 % piece of memory.
    37 % + malloc() { ... } calls the appropriate constructor on the newly
    38 %   allocated space; the argument is moved into the constructor call
    39 %   without taking its address [4]
    40 % - with the above form, there is still no way to ensure that
    41 %   dynamically allocated objects are constructed. To resolve this,
    42 %   we might want a stronger "new" function which always calls the
    43 %   constructor, although how we accomplish that is currently still
    44 %   unresolved (compiler magic vs. better variadic functions?)
    45 % + This can be used as a placement syntax [5]
    46 % - can call the constructor on an object more than once, which could
    47 %   cause resource leaks and reinitialize const fields (can try to
    48 %   detect and prevent this in some cases)
    49 %   * compiler always tries to implicitly insert a ctor/dtor pair for
    50 %     non-@= objects.
    51 %     * For POD objects, this will resolve to an autogenerated or
    52 %       intrinsic function.
    53 %     * Intrinsic functions are not automatically called. Autogenerated
    54 %       are, because they may call a non-autogenerated function.
    55 %     * destructors are automatically inserted at appropriate branches
    56 %       (e.g. return, break, continue, goto) and at the end of the block
    57 %       in which they are declared.
    58 %   * For @= objects, the compiler never tries to interfere and insert
    59 %     constructor and destructor calls for that object. Copy constructor
    60 %     calls do not count, because the object is not the target of the copy
    61 %     constructor.
    62 
    63 % A constructor is declared with the name ?{}
    64 % + combines the look of C initializers with the precedent of ?() being
    65 %   the name for the function call operator
    66 % + it is possible to easily search for all constructors in a project
    67 %   and immediately know that a function is a constructor by seeing the
    68 %   name "?{}"
    69 
    70 % A destructor is declared with the name ^?{}
    71 % + name mirrors a constructor's name, with an extra symbol to
    72 %   distinguish it
    73 % - the symbol '~' cannot be used due to parsing conflicts with the
    74 %   unary '~' (bitwise negation) operator - this conflict exists because
    75 %   we want to allow users to write ^x{}; to destruct x, rather than
    76 %   ^?{}(&x);
    77 
    78 % The first argument of a constructor must be a pointer. The constructed
    79 % type is the base type of the pointer. E.g. void ?{}(T *) is a default
    80 % constructor for a T.
    81 % + can name the argument whatever you like, so not constrained by
    82 %   language keyword "this" or "self", etc.
    83 % - have to explicitly qualify all object members to initialize them
    84 %   (e.g. this->x = 0, rather than just x = 0)
    85 
    86 % Destructors can take arguments other than just the destructed pointer
    87 % * open research problem: not sure how useful this is
    88 
    89 % Pointer constructors
    90 % + can construct separately compiled objects (opaque types) [6]
    91 % + orthogonal design, follows directly from the definition of the first
    92 %   argument of a constructor
    93 % - may require copy constructor or move constructor (or equivalent)
    94 %   for correct implementation, which may not be obvious to everyone
    95 % + required feature for the prelude to specify as much behavior as possible
    96 %   (similar to pointer assignment operators in this respect)
    97 
    98 % Designations can only be used for C-style initialization
    99 % * designation for constructors is equivalent to designation for any
    100 %   general function call. Since a function prototype can be redeclared
    101 %   many times, with arguments named differently each time (or not at
    102 %   all!), this is considered to be an undesirable feature. We could
    103 %   construct some set of rules to allow this behaviour, but it is
    104 %   probably more trouble than it's worth, and no matter what we choose,
    105 %   it is not likely to be obvious to most people.
    106 
    107 % Constructing an anonymous member [7]
    108 % + same as with calling any other function on an anonymous member
    109 %   (implicit conversion by the compiler)
    110 % - may be some cases where this is ambiguous => clarify with a cast
    111 %   (try to design APIs to avoid sharing function signatures between
    112 %   composed types to avoid this)
    113 
    114 % Default Constructors and Destructors are called implicitly
    115 % + cannot forget to construct or destruct an object
    116 % - requires special syntax to specify that an object is not to be
    117 %   constructed (@=)
    118 % * an object will not be implicitly constructed OR destructed if
    119 %   explicitly initialized like a C object (@= syntax)
    120 % * an object will be destructed if there are no constructors in scope
    121 %   (even though it is initialized like a C object) [8]
    122 
    123 % An object which changes from POD type to non POD type will not change
    124 % the semantics of a type containing it by composition
    125 % * That is, constructors will not be regenerated at the point where
    126 %   an object changes from POD type to non POD type, because this could
    127 %   cause a cascade of constructors being regenerated for many other
    128 %   types. Further, there is precedence for this behaviour in other
    129 %   facets of Cforall's design, such as how nested functions interact.
    130 % * This behaviour can be simplified in a language without declaration
    131 %   before use, because a type can be classified as POD or non POD
    132 %   (rather than potentially changing between the two at some point) at
    133 %   at the global scope (which is likely the most common case)
    134 % * [9]
    135 
    136 % Changes to polymorphic type classes
    137 % * dtype and ftype remain the same
    138 % * forall(otype T) is currently essentially the same as
    139 %   forall(dtype T | { @size(T); void ?=?(T *, T); }).
    140 %   The big addition is that you can declare an object of type T, rather
    141 %   than just a pointer to an object of type T since you know the size,
    142 %   and you can assign into a T.
    143 %   * this definition is changed to add default constructor and
    144 %     destructor declarations, to remain consistent with what type meant
    145 %     before the introduction of constructors and destructors.
    146 %     * that is, forall(type T) is now essentially the same as
    147 %       forall(dtype T | { @size(T); void ?=?(T *, T);
    148 %                          void ?{}(T *); void ^?{}(T *); })
    149 %     + this is required to make generic types work correctly in
    150 %       polymorphic functions
    151 %     ? since declaring a constructor invalidates the autogenerated
    152 %       routines, it is possible for a type to have constructors, but
    153 %       not default constructors. That is, it might be the case that
    154 %       you want to write a polymorphic function for a type which has
    155 %       a size, but non-default constructors? Some options:
    156 %       * declaring a constructor as a part of the assertions list for
    157 %         a type declaration invalidates the default, so
    158 %         forall(otype T | { void ?{}(T *, int); })
    159 %         really means
    160 %         forall(dtype T | { @size(T); void ?=?(T *, T);
    161 %                            void ?{}(T *, int); void ^?{}(T *); })
    162 %       * force users to fully declare the assertions list like the
    163 %         above in this case (this seems very undesirable)
    164 %       * add another type class with the current desugaring of type
    165 %         (just size and assignment)
    166 %       * provide some way of subtracting from an existing assertions
    167 %         list (this might be useful to have in general)
    168 
    169 % Implementation issues:
    170 % Changes to prelude/autogen or built in defaults?
    171 % * pointer ctors/dtors [prelude]
    172 %   * other pointer type routines are declared in the prelude, and this
    173 %     doesn't seem like it should be any different
    174 % * basic type ctors/dtors [prelude]
    175 %   * other basic type routines are declared in the prelude, and this
    176 %     doesn't seem like it should be any different
    177 % ? aggregate types [undecided, but leaning towards autogenerate]
    178 %   * prelude
    179 %     * routines specific to aggregate types cannot be predeclared in
    180 %       the prelude because we don't know the name of every
    181 %       aggregate type in the entire program
    182 %   * autogenerate
    183 %     + default assignment operator is already autogenerated for
    184 %       aggregate types
    185 %       * this seems to lead us in the direction of autogenerating,
    186 %         because we may have a struct which contains other objects
    187 %         that require construction [10]. If we choose not to
    188 %         autogenerate in this case, then objects which are part of
    189 %         other objects by composition will not be constructed unless
    190 %         a constructor for the outer type is explicitly defined
    191 %       * in this case, we would always autogenerate the appropriate
    192 %         constructor(s) for an aggregate type, but just like with
    193 %         basic types, pointer types, and enum types, the constructor
    194 %         call can be elided when when it is not necessary.
    195 %     + constructors will have to be explicitly autogenerated
    196 %       in the case where they are required for a polymorphic function,
    197 %       when no user defined constructor is in scope, which may make it
    198 %       easiest to always autogenerate all appropriate constructors
    199 %     - n+2 constructors would have to be generated for a POD type
    200 %       * one constructor for each number of valid arguments [0, n],
    201 %         plus the copy constructor
    202 %         * this is taking a simplified approach: in C, it is possible
    203 %           to omit the enclosing braces in a declaration, which would
    204 %           lead to a combinatorial explosion of generated constructors.
    205 %           In the interest of keeping things tractable, Cforall may be
    206 %           incompatible with C in this case. [11]
    207 %       * for non-POD types, only autogenerate the default and copy
    208 %         constructors
    209 %       * alternative: generate only the default constructor and
    210 %         special case initialization for any other constructor when
    211 %         only the autogenerated one exists
    212 %         - this is not very sensible, as by the previous point, these
    213 %           constructors may be needed for polymorphic functions
    214 %           anyway.
    215 %     - must somehow distinguish in resolver between autogenerated and
    216 %       user defined constructors (autogenerated should never be chosen
    217 %       when a user defined option exists [check first parameter], even
    218 %       if full signature differs) (this may also have applications
    219 %       to other autogenerated routines?)
    220 %     - this scheme does not naturally support designation (i.e. general
    221 %       functions calls do not support designation), thus these cases
    222 %       will have to be treated specially in either case
    223 %   * defaults
    224 %     * i.e. hardcode a new set of rules for some "appropriate" default
    225 %       behaviour for
    226 %     + when resolving an initialization expression, explicitly check to
    227 %       see if any constructors are in scope. If yes, attempt to resolve
    228 %       to a constructor, and produce an error message if a match is not
    229 %       found. If there are no constructors in scope, resolve to
    230 %       initializing each field individually (C-style)
    231 %     + does not attempt to autogenerate constructors for POD types,
    232 %       which can be seen as a space optimization for the program
    233 %       binary
    234 %     - as stated previously, a polymorphic routine may require these
    235 %       autogenerated constructors, so this doesn't seem like a big win,
    236 %       because this leads to more complicated logic and tracking of
    237 %       which constructors have already been generated
    238 %     - even though a constructor is not explicitly declared or used
    239 %       polymorphically, we might still need one for all uses of a
    240 %       struct (e.g. in the case of composition).
    241 %   * the biggest tradeoff in autogenerating vs. defaulting appears to
    242 %     be in where and how the special code to check if constructors are
    243 %     present is handled. It appears that there are more reasons to
    244 %     autogenerate than not.
    245 
    246 % --- examples
    247 % [1] As an example of using constructors polymorphically, consider a
    248 % slight modification on the foldl example I put on the mailing list a
    249 % few months ago:
    250 
    251 % context iterable(type collection, type element, type iterator) {
    252 %   void ?{}(iterator *, collection); // used to be makeIterator, but can
    253 %                             // idiomatically use constructor
    254 %   int hasNext(iterator);
    255 %   iterator ++?(iterator *);
    256 %   lvalue element *?(iterator);
    257 % };
    258 
    259 
    260 % forall(type collection, type element, type result, type iterator
    261 %   | iterable(collection, element, iterator))
    262 % result foldl(collection c, result acc,
    263 %     result (*reduce)(result, element)) {
    264 %   iterator it = { c };
    265 %   while (hasNext(it)) {
    266 %     acc = reduce(acc, *it);
    267 %     ++it;
    268 %   }
    269 %   return acc;
    270 % }
    271 
    272 % Now foldl makes use of the knowledge that the iterator type has a
    273 % single argument constructor which takes the collection to iterate
    274 % over. This pattern allows polymorphic code to look more natural
    275 % (constructors are generally preferred to named initializer/creation
    276 % routines, e.g. "makeIterator")
    277 
    278 % [2] An example of some potentially dangerous code that we don't want
    279 % to let easily slip through the cracks - if this is really what you
    280 % want, then use @= syntax for the second declaration to quiet the
    281 % compiler.
    282 
    283 % struct A { int x, y, z; }
    284 % ?{}(A *, int);
    285 % ?{}(A *, int, int, int);
    286 
    287 % A a1 = { 1 };         // uses ?{}(A *, int);
    288 % A a2 = { 2, 3 };      // C-style initialization -> no invariants!
    289 % A a3 = { 4, 5, 6 };   // uses ?{}(A *, int, int, int);
    290 
    291 % [3] Since @= syntax creates a C object (essentially a POD, as far as
    292 % the compiler is concerned), the object will not be destructed
    293 % implicitly when it leaves scope, nor will it be copy constructed when
    294 % it is returned. In this case, a memcpy should be equivalent to a move.
    295 
    296 % // Box.h
    297 % struct Box;
    298 % void ?{}(Box **, int};
    299 % void ^?{}(Box **);
    300 % Box * make_fortytwo();
    301 
    302 % // Box.cfa
    303 % Box * make_fortytwo() {
    304 %   Box *b @= {};
    305 %   (&b){ 42 }; // construct explicitly
    306 %   return b; // no destruction, essentially a move?
    307 % }
    308 
    309 % [4] Cforall's typesafe malloc can be composed with constructor
    310 % expressions. It is possible for a user to define their own functions
    311 % similar to malloc and achieve the same effects (e.g. Aaron's example
    312 % of an arena allocator)
    313 
    314 % // CFA malloc
    315 % forall(type T)
    316 % T * malloc() { return (T *)malloc(sizeof(T)); }
    317 
    318 % struct A { int x, y, z; };
    319 % void ?{}(A *, int);
    320 
    321 % int foo(){
    322 %   ...
    323 %   // desugars to:
    324 %   // A * a = ?{}(malloc(), 123);
    325 %   A * a = malloc() { 123 };
    326 %   ...
    327 % }
    328 
    329 % [5] Aaron's example of combining function calls with constructor
    330 % syntax to perform an operation similar to C++'s std::vector::emplace
    331 % (i.e. to construct a new element in place, without the need to
    332 % copy)
    333 
    334 % forall(type T)
    335 % struct vector {
    336 %   T * elem;
    337 %   int len;
    338 %   ...
    339 % };
    340 
    341 % ...
    342 % forall(type T)
    343 % T * vector_new(vector(T) * v) {
    344 %   // reallocate if needed
    345 %   return &v->elem[len++];
    346 % }
    347 
    348 % int main() {
    349 %   vector(int) * v = ...
    350 %   vector_new(v){ 42 };  // add element to the end of vector
    351 % }
    352 
    353 % [6] Pointer Constructors. It could be useful to use the existing
    354 % constructor syntax even more uniformly for ADTs. With this, ADTs can
    355 % be initialized in the same manor as any other object in a polymorphic
    356 % function.
    357 
    358 % // vector.h
    359 % forall(type T) struct vector;
    360 % forall(type T) void ?{}(vector(T) **);
    361 % // adds an element to the end
    362 % forall(type T) vector(T) * ?+?(vector(T) *, T);
    363 
    364 % // vector.cfa
    365 % // don't want to expose the implementation to the user and/or don't
    366 % // want to recompile the entire program if the struct definition
    367 % // changes
    368 
    369 % forall(type T) struct vector {
    370 %   T * elem;
    371 %   int len;
    372 %   int capacity;
    373 % };
    374 
    375 % forall(type T) void resize(vector(T) ** v) { ... }
    376 
    377 % forall(type T) void ?{}(vector(T) ** v) {
    378 %   vector(T) * vect = *v = malloc();
    379 %   vect->capacity = 10;
    380 %   vect->len = 0;
    381 %   vect->elem = malloc(vect->capacity);
    382 % }
    383 
    384 % forall(type T) vector(T) * ?+?(vector(T) *v, T elem) {
    385 %   if (v->len == v->capacity) resize(&v);
    386 %   v->elem[v->len++] = elem;
    387 % }
    388 
    389 % // main.cfa
    390 % #include "adt.h"
    391 % forall(type T | { T ?+?(T, int); }
    392 % T sumRange(int lower, int upper) {
    393 %   T x;    // default construct
    394 %   for (int i = lower; i <= upper; i++) {
    395 %     x = x + i;
    396 %   }
    397 %   return x;
    398 % }
    399 
    400 % int main() {
    401 %   vector(int) * numbers = sumRange(1, 10);
    402 %   // numbers is now a vector containing [1..10]
    403 
    404 %   int sum = sumRange(1, 10);
    405 %   // sum is now an int containing the value 55
    406 % }
    407 
    408 % [7] The current proposal is to use the plan 9 model of inheritance.
    409 % Under this model, all of the members of an unnamed struct instance
    410 % become members of the containing struct. In addition, an object
    411 % can be passed as an argument to a function expecting one of its
    412 % base structs.
    413 
    414 % struct Point {
    415 %   double x;
    416 %   double y;
    417 % };
    418 
    419 % struct ColoredPoint {
    420 %   Point;        // anonymous member (no identifier)
    421 %                 // => a ColoredPoint has an x and y of type double
    422 %   int color;
    423 % };
    424 
    425 % ColoredPoint cp = ...;
    426 % cp.x = 10.3;    // x from Point is accessed directly
    427 % cp.color = 0x33aaff; // color is accessed normally
    428 % foo(cp);        // cp can be used directly as a Point
    429 
    430 % void ?{}(Point *p, double x, double y) {
    431 %   p->x = x;
    432 %   p->y = y;
    433 % }
    434 
    435 % void ?{}(ColoredPoint *cp, double x, double y, int color) {
    436 %   (&cp){ x, y };  // unambiguous, no ?{}(ColoredPoint*,double,double)
    437 %   cp->color = color;
    438 % }
    439 
    440 % struct Size {
    441 %   double width;
    442 %   double height;
    443 % };
    444 
    445 % void ?{}(Size *s, double w, double h) {
    446 %   p->width = w;
    447 %   p->height = h;
    448 % }
    449 
    450 % struct Foo {
    451 %   Point;
    452 %   Size;
    453 % }
    454 
    455 % ?{}(Foo &f, double x, double y, double w, double h) {
    456 %   // (&F,x,y) is ambiguous => is it ?{}(Point*,double,double) or
    457 %   // ?{}(Size*,double,double)? Solve with a cast:
    458 %   ((Point*)&F){ x, y };
    459 %   ((Size*)&F){ w, h };
    460 % }
    461 
    462 % [8] Destructors will be called on objects that were not constructed.
    463 
    464 % struct A { ... };
    465 % ^?{}(A *);
    466 % {
    467 %   A x;
    468 %   A y @= {};
    469 % } // x is destructed, even though it wasn't constructed
    470 %   // y is not destructed, because it is explicitly a C object
    471 
    472 
    473 % [9] A type's constructor is generated at declaration time using
    474 % current information about an object's members. This is analogous to
    475 % the treatment of other operators. For example, an object's assignment
    476 % operator will not change to call the override of a member's assignment
    477 % operator unless the object's assignment is also explicitly overridden.
    478 % This problem can potentially be treated differently in Do, since each
    479 % compilation unit is passed over at least twice (once to gather
    480 % symbol information, once to generate code - this is necessary to
    481 % achieve the "No declarations" goal)
    482 
    483 % struct A { ... };
    484 % struct B { A x; };
    485 % ...
    486 % void ?{}(A *);  // from this point on, A objects will be constructed
    487 % B b1;           // b1 and b1.x are both NOT constructed, because B
    488 %                 // objects are not constructed
    489 % void ?{}(B *);  // from this point on, B objects will be constructed
    490 % B b2;           // b2 and b2.x are both constructed
    491 
    492 % struct C { A x; };
    493 % // implicit definition of ?{}(C*), because C is not a POD type since
    494 % // it contains a non-POD type by composition
    495 % C c;            // c and c.x are both constructed
    496 
    497 % [10] Requiring construction by composition
    498 
    499 % struct A {
    500 %   ...
    501 % };
    502 
    503 % // declared ctor disables default c-style initialization of
    504 % // A objects; A is no longer a POD type
    505 % void ?{}(A *);
    506 
    507 % struct B {
    508 %   A x;
    509 % };
    510 
    511 % // B objects can not be C-style initialized, because A objects
    512 % // must be constructed => B objects are transitively not POD types
    513 % B b; // b.x must be constructed, but B is not constructible
    514 %      // => must autogenerate ?{}(B *) after struct B definition,
    515 %      // which calls ?{}(&b.x)
    516 
    517 % [11] Explosion in the number of generated constructors, due to strange
    518 % C semantics.
    519 
    520 % struct A { int x, y; };
    521 % struct B { A u, v, w; };
    522 
    523 % A a = { 0, 0 };
    524 
    525 % // in C, you are allowed to do this
    526 % B b1 = { 1, 2, 3, 4, 5, 6 };
    527 % B b2 = { 1, 2, 3 };
    528 % B b3 = { a, a, a };
    529 % B b4 = { a, 5, 4, a };
    530 % B b5 = { 1, 2, a, 3 };
    531 
    532 % // we want to disallow b1, b2, b4, and b5 in Cforall.
    533 % // In particular, we will autogenerate these constructors:
    534 % void ?{}(A *);             // default/0 parameters
    535 % void ?{}(A *, int);        // 1 parameter
    536 % void ?{}(A *, int, int);   // 2 parameters
    537 % void ?{}(A *, const A *);  // copy constructor
    538 
    539 % void ?{}(B *);             // default/0 parameters
    540 % void ?{}(B *, A);          // 1 parameter
    541 % void ?{}(B *, A, A);       // 2 parameters
    542 % void ?{}(B *, A, A, A);    // 3 parameters
    543 % void ?{}(B *, const B *);  // copy constructor
    544 
    545 % // we will not generate constructors for every valid combination
    546 % // of members in C. For example, we will not generate
    547 % void ?{}(B *, int, int, int, int, int, int);   // b1 would need this
    548 % void ?{}(B *, int, int, int);                  // b2 would need this
    549 % void ?{}(B *, A, int, int, A);                 // b4 would need this
    550 % void ?{}(B *, int, int, A, int);               // b5 would need this
    551 % // and so on
    5527
    5538Since \CFA is a true systems language, it does not provide a garbage collector.
     
    55712
    55813This chapter details the design of constructors and destructors in \CFA, along with their current implementation in the translator.
    559 Generated code samples have been edited to provide comments for clarity and to save on space.
     14Generated code samples have been edited for clarity and brevity.
    56015
    56116\section{Design Criteria}
     
    57934Use of uninitialized variables yields undefined behaviour, which is a common source of errors in C programs.
    58035
    581 Declaration initialization is insufficient, because it permits uninitialized variables to exist and because it does not allow for the insertion of arbitrary code before a variable is live.
     36Initialization of a declaration is strictly optional, permitting uninitialized variables to exist.
     37Furthermore, declaration initialization is limited to expressions, so there is no way to insert arbitrary code before a variable is live, without delaying the declaration.
    58238Many C compilers give good warnings for uninitialized variables most of the time, but they cannot in all cases.
    58339\begin{cfacode}
     
    59248Other languages are able to give errors in the case of uninitialized variable use, but due to backwards compatibility concerns, this is not the case in \CFA.
    59349
    594 In C, constructors and destructors are often mimicked by providing routines that create and teardown objects, where the teardown function is typically only necessary if the type modifies the execution environment.
     50In C, constructors and destructors are often mimicked by providing routines that create and tear down objects, where the tear down function is typically only necessary if the type modifies the execution environment.
    59551\begin{cfacode}
    59652struct array_int {
     
    61874Furthermore, even with this idiom it is easy to make mistakes, such as forgetting to destroy an object or destroying it multiple times.
    61975
    620 A constructor provides a way of ensuring that the necessary aspects of object initialization is performed, from setting up invariants to providing compile-time checks for appropriate initialization parameters.
     76A 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.
    62177This 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.
    62278Since 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.
     
    658114In other words, a default constructor is a constructor that takes a single argument: the @this@ parameter.
    659115
    660 In \CFA, a destructor is a function much like a constructor, except that its name is \lstinline!^?{}!.
     116In \CFA, a destructor is a function much like a constructor, except that its name is \lstinline!^?{}! and it take only one argument.
    661117A destructor for the @Array@ type can be defined as such.
    662118\begin{cfacode}
     
    701157
    702158It is possible to define a constructor that takes any combination of parameters to provide additional initialization options.
    703 For example, a reasonable extension to the array type would be a constructor that allocates the array to a given initial capacity and initializes the array to a given @fill@ value.
     159For example, a reasonable extension to the array type would be a constructor that allocates the array to a given initial capacity and initializes the elements of the array to a given @fill@ value.
    704160\begin{cfacode}
    705161void ?{}(Array * arr, int capacity, int fill) {
     
    812268One of these three syntactic forms should appeal to either C or \CC programmers using \CFA.
    813269
     270\subsection{Constructor Expressions}
     271In \CFA, it is possible to use a constructor as an expression.
     272Like other operators, the function name @?{}@ matches its operator syntax.
     273For example, @(&x){}@ calls the default constructor on the variable @x@, and produces @&x@ as a result.
     274A key example for this capability is the use of constructor expressions to initialize the result of a call to standard C routine @malloc@.
     275\begin{cfacode}
     276struct X { ... };
     277void ?{}(X *, double);
     278X * x = malloc(sizeof(X)){ 1.5 };
     279\end{cfacode}
     280In this example, @malloc@ dynamically allocates storage and initializes it using a constructor, all before assigning it into the variable @x@.
     281If 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.
     282\begin{cfacode}
     283X * x = malloc(sizeof(X));
     284x{ 1.5 };
     285\end{cfacode}
     286Not only is this verbose, but it is also more error prone, since this form allows maintenance code to easily sneak in between the initialization of @x@ and the initialization of the memory that @x@ points to.
     287This feature is implemented via a transformation producing the value of the first argument of the constructor, since constructors do not themselves have a return value.
     288Since this transformation results in two instances of the subexpression, care is taken to allocate a temporary variable to hold the result of the subexpression in the case where the subexpression may contain side effects.
     289The previous example generates the following code.
     290\begin{cfacode}
     291struct X *_tmp_ctor;
     292struct X *x = ?{}(  // construct result of malloc
     293  _tmp_ctor=malloc(sizeof(struct X)), // store result of malloc
     294  1.5
     295), _tmp_ctor; // produce constructed result of malloc
     296\end{cfacode}
     297It 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.
     298
     299It is also possible to use operator syntax with destructors.
     300Unlike constructors, operator syntax with destructors is a statement and thus does not produce a value, since the destructed object is invalidated by the use of a destructor.
     301For example, \lstinline!^(&x){}! calls the destructor on the variable @x@.
     302
    814303\subsection{Function Generation}
    815 In \CFA, every type is defined to have the core set of four functions described previously.
     304In \CFA, every type is defined to have the core set of four special functions described previously.
    816305Having these functions exist for every type greatly simplifies the semantics of the language, since most operations can simply be defined directly in terms of function calls.
    817306In addition to simplifying the definition of the language, it also simplifies the analysis that the translator must perform.
     
    826315
    827316The generated functions for enumerations are the simplest.
    828 Since enumerations in C are essentially just another integral type, the generated functions behave in the same way that the builtin functions for the basic types work.
     317Since enumerations in C are essentially just another integral type, the generated functions behave in the same way that the built-in functions for the basic types work.
    829318For example, given the enumeration
    830319\begin{cfacode}
     
    839328}
    840329void ?{}(enum Colour *_dst, enum Colour _src){
    841   (*_dst)=_src;  // bitwise copy
     330  *_dst=_src;  // bitwise copy
    842331}
    843332void ^?{}(enum Colour *_dst){
     
    845334}
    846335enum Colour ?=?(enum Colour *_dst, enum Colour _src){
    847   return (*_dst)=_src; // bitwise copy
     336  return *_dst=_src; // bitwise copy
    848337}
    849338\end{cfacode}
     
    903392For copy constructor and assignment operations, a bitwise @memcpy@ is applied.
    904393In standard C, a union can also be initialized using a value of the same type as its first member, and so a corresponding field constructor is generated to perform a bitwise @memcpy@ of the object.
    905 An alterantive to this design is to always construct and destruct the first member of a union, to match with the C semantics of initializing the first member of the union.
     394An alternative to this design is to always construct and destruct the first member of a union, to match with the C semantics of initializing the first member of the union.
    906395This approach ultimately feels subtle and unsafe.
    907396Another option is to, like \CC, disallow unions from containing members that are themselves managed types.
     
    1000489Instead, @a2->x@ is initialized to @0@ as if it were a C object, because of the explicit initializer.
    1001490
    1002 In addition to freedom, \ateq provides a simple path to migrating legacy C code to Cforall, in that objects can be moved from C-style initialization to \CFA gradually and individually.
     491In addition to freedom, \ateq provides a simple path to migrating legacy C code to \CFA, in that objects can be moved from C-style initialization to \CFA gradually and individually.
    1003492It 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.
    1004493It is recommended that most objects be managed by sensible constructors and destructors, except where absolutely necessary.
     
    1026515When defining a constructor or destructor for a struct @S@, any members that are not explicitly constructed or destructed are implicitly constructed or destructed automatically.
    1027516If an explicit call is present, then that call is taken in preference to any implicitly generated call.
    1028 A consequence of this rule is that it is possible, unlike \CC, to precisely control the order of construction and destruction of subobjects on a per-constructor basis, whereas in \CC subobject initialization and destruction is always performed based on the declaration order.
     517A consequence of this rule is that it is possible, unlike \CC, to precisely control the order of construction and destruction of sub-objects on a per-constructor basis, whereas in \CC sub-object initialization and destruction is always performed based on the declaration order.
    1029518\begin{cfacode}
    1030519struct A {
     
    1045534}
    1046535\end{cfacode}
    1047 Finally, it is illegal for a subobject to be explicitly constructed for the first time after it is used for the first time.
     536Finally, it is illegal for a sub-object to be explicitly constructed for the first time after it is used for the first time.
    1048537If the translator cannot be reasonably sure that an object is constructed prior to its first use, but is constructed afterward, an error is emitted.
    1049 More specifically, the translator searches the body of a constructor to ensure that every subobject is initialized.
     538More specifically, the translator searches the body of a constructor to ensure that every sub-object is initialized.
    1050539\begin{cfacode}
    1051540void ?{}(A * a, double x) {
     
    1054543}
    1055544\end{cfacode}
    1056 However, if the translator sees a subobject used within the body of a constructor, but does not see a constructor call that uses the subobject 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).
     545However, 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).
    1057546\begin{cfacode}
    1058547void ?{}(A * a) {
     
    1070559} // z, y, w implicitly destructed, in this order
    1071560\end{cfacode}
    1072 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. % TODO: this is basically always wrong. if anything, I should check that such a constructor does not initialize any members, otherwise it'll always initialize the member twice (once locally, once by the called constructor). This might be okay in some situations, but it deserves a warning at the very least.
     561If 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.
    1073562To override this rule, \ateq can be used to force the translator to trust the programmer's discretion.
    1074563This form of \ateq is not yet implemented.
     
    1102591};
    1103592\end{cfacode}
    1104 In C, nesting initializers means that the programmer intends to initialize subobjects with the nested initializers.
     593In C, nesting initializers means that the programmer intends to initialize sub-objects with the nested initializers.
    1105594The reason for this omission is to both simplify the mental model for using constructors, and to make initialization simpler for the expression resolver.
    1106595If this were allowed, it would be necessary for the expression resolver to decide whether each argument to the constructor call could initialize to some argument in one of the available constructors, making the problem highly recursive and potentially much more expensive.
     
    1125614}
    1126615\end{cfacode}
    1127 % TODO: in CFA if the array dimension is empty, no object constructors are added -- need to fix this.
    1128616The body of @A@ has been omitted, since only the constructor interfaces are important.
    1129617
     
    1153641    if (i == 2) return; // destruct x, y
    1154642  } // destruct y
    1155 }
     643} // destruct x
    1156644\end{cfacode}
    1157645
     
    1169657Since a destructor call is automatically inserted at the end of the block, nothing special needs to happen to destruct @x@ in the case where control reaches the end of the loop.
    1170658In the case where @i@ is @2@, the continue statement runs the loop update expression and attempts to begin the next iteration of the loop.
    1171 Since continue is a C statement, which does not understand destructors, a destructor call is added just before the continue statement to ensure that @x@ is destructed.
     659Since continue is a C statement, which does not understand destructors, it is transformed into a @goto@ statement that branches to the end of the loop, just before the block's destructors, to ensure that @x@ is destructed.
    1172660When @i@ is @3@, the break statement moves control to just past the end of the loop.
    1173 Like the previous case, a destructor call for @x@ is inserted just before the break statement.
    1174 
    1175 \CFA also supports labelled break and continue statements, which allow more precise manipulation of control flow.
    1176 Labelled break and continue allow the programmer to specify which control structure to target by using a label attached to a control structure.
     661Unlike the previous case, the destructor for @x@ cannot be reused, so a destructor call for @x@ is inserted just before the break statement.
     662
     663\CFA also supports labeled break and continue statements, which allow more precise manipulation of control flow.
     664Labeled break and continue allow the programmer to specify which control structure to target by using a label attached to a control structure.
    1177665\begin{cfacode}[emph={L1,L2}, emphstyle=\color{red}]
    1178666L1: for (int i = 0; i < 10; i++) {
     
    1189677\end{cfacode}
    1190678The statement @continue L1@ begins the next iteration of the outer for-loop.
    1191 Since the semantics of continue require the loop update expression to execute, control branches to the \emph{end} of the outer for loop, meaning that the block destructor for @x@ can be reused, and it is only necessary to generate the destructor for @y@.
    1192 % TODO: "why not do this all the time? fix or justify"
    1193 Break, on the other hand, requires jumping out of the loop, so the destructors for both @x@ and @y@ are generated and inserted before the @break L1@ statement.
     679Since the semantics of continue require the loop update expression to execute, control branches to the end of the outer for loop, meaning that the block destructor for @x@ can be reused, and it is only necessary to generate the destructor for @y@.
     680Break, on the other hand, requires jumping out of both loops, so the destructors for both @x@ and @y@ are generated and inserted before the @break L1@ statement.
    1194681
    1195682Finally, an example which demonstrates goto.
     
    1238725}
    1239726\end{cfacode}
    1240 Labelled break and continue are implemented in \CFA in terms of goto statements, so the more constrained forms are precisely goverened by these rules.
     727All break and continue statements are implemented in \CFA in terms of goto statements, so the more constrained forms are precisely governed by these rules.
    1241728
    1242729The next example demonstrates the error case.
     
    1255742
    1256743\subsection{Implicit Copy Construction}
     744\label{s:implicit_copy_construction}
    1257745When a function is called, the arguments supplied to the call are subject to implicit copy construction (and destruction of the generated temporary), and the return value is subject to destruction.
    1258746When a value is returned from a function, the copy constructor is called to pass the value back to the call site.
    1259 Exempt from these rules are intrinsic and builtin functions.
     747Exempt from these rules are intrinsic and built-in functions.
    1260748It 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.
    1261749That is, since the parameter is not marked as an unmanaged object using \ateq, it will 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.
     
    1318806It 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.
    1319807
    1320 A known issue with this implementation is that the return value of a function is not guaranteed to have the same address for its entire lifetime.
    1321 Specifically, 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.
     808A 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.
     809In 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.
    1322810This approach works out most of the time, because typically destructors need to only access the fields of the object and recursively destroy.
    1323811It is currently the case that constructors and destructors that use the @this@ pointer as a unique identifier to store data externally do not work correctly for return value objects.
    1324 Thus, it is not safe to rely on an object's @this@ pointer to remain constant throughout execution of the program.
     812Thus, it is currently not safe to rely on an object's @this@ pointer to remain constant throughout execution of the program.
    1325813\begin{cfacode}
    1326814A * external_data[32];
     
    1350838\end{cfacode}
    1351839In the above example, a global array of pointers is used to keep track of all of the allocated @A@ objects.
    1352 Due to copying on return, the current object being destructed does not exist in the array if an @A@ object is ever returned by value from a function.
     840Due to copying on return, the current object being destructed does not exist in the array if an @A@ object is ever returned by value from a function, such as in @makeA@.
    1353841
    1354842This problem could be solved in the translator by changing the function signatures so that the return value is moved into the parameter list.
     
    1399887\end{cfacode}
    1400888An alternative is to instead make the attribute \emph{identifiable}, which states that objects of this type use the @this@ parameter as an identity.
    1401 This strikes more closely to the visibile problem, in that only types marked as identifiable would need to have the return value moved into the parameter list, and every other type could remain the same.
     889This strikes more closely to the visible problem, in that only types marked as identifiable would need to have the return value moved into the parameter list, and every other type could remain the same.
    1402890Furthermore, no restrictions would need to be placed on whether objects can be constructed.
    1403891\begin{cfacode}
     
    1409897\end{cfacode}
    1410898
    1411 Ultimately, this is the type of transformation that a real compiler would make when generating assembly code.
    1412 Since a compiler has full control over its calling conventions, it can seamlessly allow passing the return parameter without outwardly changing the signature of a routine.
    1413 As such, it has been decided that this issue is not currently a priority.
     899Ultimately, both of these are patchwork solutions.
     900Since a real compiler has full control over its calling conventions, it can seamlessly allow passing the return parameter without outwardly changing the signature of a routine.
     901As such, it has been decided that this issue is not currently a priority and will be fixed when a full \CFA compiler is implemented.
    1414902
    1415903\section{Implementation}
     
    15341022It is, however, guaranteed that any global objects in the standard library are initialized prior to the initialization of any object in the user program.
    15351023
    1536 This feature is implemented in the \CFA translator by grouping every global constructor call into a function with the GCC attribute \emph{constructor}, which performs most of the heavy lifting. % TODO: CITE: https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#Common-Function-Attributes
     1024This feature is implemented in the \CFA translator by grouping every global constructor call into a function with the GCC attribute \emph{constructor}, which performs most of the heavy lifting \cite[6.31.1]{GCCExtensions}.
    15371025A similar function is generated with the \emph{destructor} attribute, which handles all global destructor calls.
    15381026At the time of writing, initialization routines in the library are specified with priority \emph{101}, which is the highest priority level that GCC allows, whereas initialization routines in the user's code are implicitly given the default priority level, which ensures they have a lower priority than any code with a specified priority level.
    1539 This mechanism allows arbitrarily complicated initialization to occur before any user code runs, making it possible for library designers to initialize their modules without requiring the user to call specific startup or teardown routines.
     1027This mechanism allows arbitrarily complicated initialization to occur before any user code runs, making it possible for library designers to initialize their modules without requiring the user to call specific startup or tear-down routines.
    15401028
    15411029For example, given the following global declarations.
     
    15651053%   https://gcc.gnu.org/onlinedocs/gcc/C_002b_002b-Attributes.html#C_002b_002b-Attributes
    15661054% suggestion: implement this in CFA by picking objects with a specified priority and pulling them into their own init functions (could even group them by priority level -> map<int, list<ObjectDecl*>>) and pull init_priority forward into constructor and destructor attributes with the same priority level
    1567 GCC provides an attribute @init_priority@, which specifies allows specifying the relative priority for initialization of global objects on a per-object basis in \CC.
     1055GCC provides an attribute @init_priority@, which allows specifying the relative priority for initialization of global objects on a per-object basis in \CC.
    15681056A similar attribute can be implemented in \CFA by pulling marked objects into global constructor/destructor-attribute functions with the specified priority.
    15691057For example,
     
    15871075\subsection{Static Local Variables}
    15881076In standard C, it is possible to mark variables that are local to a function with the @static@ storage class.
    1589 Unlike normal local variables, a @static@ local variable is defined to live for the entire duration of the program, so that each call to the function has access to the same variable with the same address and value as it had in the previous call to the function. % TODO: mention dynamic loading caveat??
     1077Unlike normal local variables, a @static@ local variable is defined to live for the entire duration of the program, so that each call to the function has access to the same variable with the same address and value as it had in the previous call to the function.
    15901078Much like global variables, in C @static@ variables can only be initialized to a \emph{compile-time constant value} so that a compiler is able to create storage for the variable and initialize it at compile-time.
    15911079
     
    15991087Construction of @static@ local objects is implemented via an accompanying @static bool@ variable, which records whether the variable has already been constructed.
    16001088A conditional branch checks the value of the companion @bool@, and if the variable has not yet been constructed then the object is constructed.
    1601 The object's destructor is scheduled to be run when the program terminates using @atexit@, and the companion @bool@'s value is set so that subsequent invocations of the function do not reconstruct the object.
     1089The object's destructor is scheduled to be run when the program terminates using @atexit@ \footnote{When using the dynamic linker, it is possible to dynamically load and unload a shared library. Since glibc 2.2.3 \cite{atexit}, functions registered with @atexit@ within the shared library are called when unloading the shared library. As such, static local objects can be destructed using this mechanism even in shared libraries on Linux systems.}, and the companion @bool@'s value is set so that subsequent invocations of the function do not reconstruct the object.
    16021090Since the parameter to @atexit@ is a parameter-less function, some additional tweaking is required.
    16031091First, the @static@ variable must be hoisted up to global scope and uniquely renamed to prevent name clashes with other global objects.
     
    16051093Finally, the newly generated function is registered with @atexit@, instead of registering the destructor directly.
    16061094Since @atexit@ calls functions in the reverse order in which they are registered, @static@ local variables are guaranteed to be destructed in the reverse order that they are constructed, which may differ between multiple executions of the same program.
    1607 
    16081095Extending the previous example
    16091096\begin{cfacode}
     
    16561143\end{cfacode}
    16571144
    1658 % TODO: move this section forward?? maybe just after constructor syntax? would need to remove _tmp_cp_ret0, since copy constructors are not discussed yet, but this might not be a big issue.
    1659 \subsection{Constructor Expressions}
    1660 In \CFA, it is possible to use a constructor as an expression.
    1661 Like other operators, the function name @?{}@ matches its operator syntax.
    1662 For example, @(&x){}@ calls the default constructor on the variable @x@, and produces @&x@ as a result.
    1663 A key example for this capability is the use of constructor expressions to initialize the result of a call to standard C routine @malloc@.
    1664 \begin{cfacode}
    1665 struct X { ... };
    1666 void ?{}(X *, double);
    1667 X * x = malloc(sizeof(X)){ 1.5 };
    1668 \end{cfacode}
    1669 In this example, @malloc@ dynamically allocates storage and initializes it using a constructor, all before assigning it into the variable @x@.
    1670 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.
    1671 \begin{cfacode}
    1672 X * x = malloc(sizeof(X));
    1673 x{ 1.5 };
    1674 \end{cfacode}
    1675 Not only is this verbose, but it is also more error prone, since this form allows maintenance code to easily sneak in between the initialization of @x@ and the initialization of the memory that @x@ points to.
    1676 This feature is implemented via a transformation produceing the value of the first argument of the constructor, since constructors do not themslves have a return value.
    1677 Since this transformation results in two instances of the subexpression, care is taken to allocate a temporary variable to hold the result of the subexpression in the case where the subexpression may contain side effects.
    1678 The previous example generates the following code.
    1679 \begin{cfacode}
    1680 struct X *_tmp_ctor;
    1681 struct X *x = ?{}((_tmp_ctor=((_tmp_cp_ret0=
    1682   malloc(sizeof(struct X))), _tmp_cp_ret0))), 1.5), _tmp_ctor);
    1683 \end{cfacode}
    1684 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.
    1685 
    1686 It is also possible to use operator syntax with destructors.
    1687 Unlike constructors, operator syntax with destructors is a statement and thus does not produce a value, since the destructed object is invalidated by the use of a destructor.
    1688 For example, \lstinline!^(&x){}! calls the destructor on the variable @x@.
     1145\subsection{Polymorphism}
     1146As mentioned in section \ref{sub:polymorphism}, \CFA currently has 3 type-classes that are used to designate polymorphic data types: @otype@, @dtype@, and @ftype@.
     1147In previous versions of \CFA, @otype@ was syntactic sugar for @dtype@ with known size/alignment information and an assignment function.
     1148That is,
     1149\begin{cfacode}
     1150forall(otype T)
     1151void f(T);
     1152\end{cfacode}
     1153was equivalent to
     1154\begin{cfacode}
     1155forall(dtype T | sized(T) | { T ?=?(T *, T); })
     1156void f(T);
     1157\end{cfacode}
     1158This allows easily specifying constraints that are common to all complete object types very simply.
     1159
     1160Now that \CFA has constructors and destructors, more of a complete object's behaviour can be specified by than was previously possible.
     1161As such, @otype@ has been augmented to include assertions for a default constructor, copy constructor, and destructor.
     1162That is, the previous example is now equivalent to
     1163\begin{cfacode}
     1164forall(dtype T | sized(T) | { T ?=?(T *, T); void ?{}(T *); void ?{}(T *, T); void ^?{}(T *); })
     1165void f(T);
     1166\end{cfacode}
     1167This allows @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.
     1168A 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.
  • doc/rob_thesis/intro.tex

    rc51b5a3 rf92aa32  
    55\section{\CFA Background}
    66\label{s:background}
    7 \CFA is a modern non-object-oriented extension to the C programming language.
     7\CFA \footnote{Pronounced ``C-for-all'', and written \CFA or Cforall.} is a modern non-object-oriented extension to the C programming language.
    88As it is an extension of C, there is already a wealth of existing C code and principles that govern the design of the language.
    99Among the goals set out in the original design of \CFA, four points stand out \cite{Bilson03}.
     
    2929A a1 = { 1, .y:7, 6 };
    3030A a2[4] = { [2]:a0, [0]:a1, { .z:3 } };
    31 // equvialent to
     31// equivalent to
    3232// A a0 = { 0, 8, 0, 1 };
    3333// A a1 = { 1, 0, 7, 6 };
     
    3636Designations allow specifying the field to initialize by name, rather than by position.
    3737Any field not explicitly initialized is initialized as if it had static storage duration \cite[p.~141]{C11}.
    38 A designator specifies the current object for initialization, and as such any undesignated subobjects pick up where the last initialization left off.
    39 For example, in the initialization of @a1@, the initializer of @y@ is @7@, and the unnamed initializer @6@ initializes the next subobject, @z@.
    40 Later initializers override earlier initializers, so a subobject for which there is more than one initializer is only initailized by its last initializer.
     38A designator specifies the current object for initialization, and as such any undesignated sub-objects pick up where the last initialization left off.
     39For example, in the initialization of @a1@, the initializer of @y@ is @7@, and the unnamed initializer @6@ initializes the next sub-object, @z@.
     40Later initializers override earlier initializers, so a sub-object for which there is more than one initializer is only initialized by its last initializer.
    4141These semantics can be seen in the initialization of @a0@, where @x@ is designated twice, and thus initialized to @8@.
    4242Note 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.
     
    116116Both solutions are syntactically unnatural.
    117117
    118 In \CFA, it is possible to directly declare a function returning mutliple values.
     118In \CFA, it is possible to directly declare a function returning multiple values.
    119119This extension provides important semantic information to the caller, since return values are only for output.
    120120\begin{cfacode}
     
    308308S * s = malloc();       // malloc(sizeof(S))
    309309\end{cfacode}
    310 The built-in trait @sized@ ensures that size and alignment information for @T@ is available to @malloc@ through @sizeof@ and @_Alignof@ expressions respectively.
     310The 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.
    311311In 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.
    312312
     
    371371Note, these invariants are internal to the type's correct behaviour.
    372372
    373 Types also have external invarients with state of the execution environment, including the heap, the open file-table, the state of global variables, etc.
     373Types also have external invariants with the state of the execution environment, including the heap, the open-file table, the state of global variables, etc.
    374374Since resources are finite and shared (concurrency), it is important to ensure that objects clean up properly when they are finished, restoring the execution environment to a stable state so that new objects can reuse resources.
    375375
     
    382382The program stack grows and shrinks automatically with each function call, as needed for local variables.
    383383However, whenever a program needs a variable to outlive the block it is created in, the storage must be allocated dynamically with @malloc@ and later released with @free@.
    384 This pattern is extended to more complex objects, such as files and sockets, which also outlive the block where they are created, but at their core is resource management.
     384This pattern is extended to more complex objects, such as files and sockets, which can also outlive the block where they are created, and thus require their own resource management.
    385385Once allocated storage escapes\footnote{In garbage collected languages, such as Java, escape analysis \cite{Choi:1999:EAJ:320385.320386} is used to determine when dynamically allocated objects are strictly contained within a function, which allows the optimizer to allocate them on the stack.} a block, the responsibility for deallocating the storage is not specified in a function's type, that is, that the return value is owned by the caller.
    386386This implicit convention is provided only through documentation about the expectations of functions.
    387387
    388388In other languages, a hybrid situation exists where resources escape the allocation block, but ownership is precisely controlled by the language.
    389 This pattern requires a strict interface and protocol for a data structure, where the protocol consists of a pre-initialization and a post-termination call, and all intervening access is done via interface routines.
    390 This kind of encapsulation is popular in object-oriented programming languages, and like the stack, it contains a significant portion of resource management cases.
     389This pattern requires a strict interface and protocol for a data structure, consisting of a pre-initialization and a post-termination call, and all intervening access is done via interface routines.
     390This kind of encapsulation is popular in object-oriented programming languages, and like the stack, it takes care of a significant portion of resource management cases.
    391391
    392392For example, \CC directly supports this pattern through class types and an idiom known as RAII \footnote{Resource Acquisition is Initialization} by means of constructors and destructors.
     
    397397RAII ensures that if all resources are acquired in a constructor and released in a destructor, there are no resource leaks, even in exceptional circumstances.
    398398A type with at least one non-trivial constructor or destructor is henceforth referred to as a \emph{managed type}.
    399 In the context of \CFA, a non-trivial constructor is either a user defined constructor or an auto generated constructor that calls a non-trivial constructor.
    400 
    401 For the remaining resource ownership cases, programmer must follow a brittle, explicit protocol for freeing resources or an implicit porotocol implemented via the programming language.
     399In the context of \CFA, a non-trivial constructor is either a user defined constructor or an auto-generated constructor that calls a non-trivial constructor.
     400
     401For the remaining resource ownership cases, programmer must follow a brittle, explicit protocol for freeing resources or an implicit protocol implemented via the programming language.
    402402
    403403In garbage collected languages, such as Java, resources are largely managed by the garbage collector.
     
    406406In particular, Java supports \emph{finalizers}, which are similar to destructors.
    407407Sadly, finalizers are only guaranteed to be called before an object is reclaimed by the garbage collector \cite[p.~373]{Java8}, which may not happen if memory use is not contentious.
    408 Due to operating-system resource-limits, this is unacceptable for many long running programs. % TODO: citation?
     408Due to operating-system resource-limits, this is unacceptable for many long running programs.
    409409Instead, the paradigm in Java requires programmers to manually keep track of all resources \emph{except} memory, leading many novices and experts alike to forget to close files, etc.
    410410Complicating the picture, uncaught exceptions can cause control flow to change dramatically, leaking a resource that appears on first glance to be released.
     
    452452Depending on when the exception is raised, both @out@ and @log@ are null, @log@ is null, or both are non-null, therefore, the cleanup for these variables at the end is appropriately guarded and conditionally executed to prevent null-pointer exceptions.
    453453
    454 % TODO: discuss Rust?
    455 % Like \CC, Rust \cite{Rust} provides RAII through constructors and destructors.
    456 % Smart pointers are deeply integrated in the Rust type-system.
     454While Rust \cite{Rust} does not enforce the use of a garbage collector, it does provide a manual memory management environment, with a strict ownership model that automatically frees allocated memory and prevents common memory management errors.
     455In particular, a variable has ownership over its associated value, which is freed automatically when the owner goes out of scope.
     456Furthermore, values are \emph{moved} by default on assignment, rather than copied, which invalidates the previous variable binding.
     457\begin{rustcode}
     458struct S {
     459  x: i32
     460}
     461let s = S { x: 123 };
     462let z = s;           // move, invalidate s
     463println!("{}", s.x); // error, s has been moved
     464\end{rustcode}
     465Types can be made copyable by implementing the @Copy@ trait.
     466
     467Rust allows multiple unowned views into an object through references, also known as borrows, provided that a reference does not outlive its referent.
     468A mutable reference is allowed only if it is the only reference to its referent, preventing data race errors and iterator invalidation errors.
     469\begin{rustcode}
     470let mut x = 10;
     471{
     472  let y = &x;
     473  let z = &x;
     474  println!("{} {}", y, z); // prints 10 10
     475}
     476{
     477  let y = &mut x;
     478  // let z1 = &x;     // not allowed, have mutable reference
     479  // let z2 = &mut x; // not allowed, have mutable reference
     480  *y = 5;
     481  println!("{}", y); // prints 5
     482}
     483println!("{}", x); // prints 5
     484\end{rustcode}
     485Since references are not owned, they do not release resources when they go out of scope.
     486There is no runtime cost imposed on these restrictions, since they are enforced at compile-time.
     487
     488Rust provides RAII through the @Drop@ trait, allowing arbitrary code to execute when the object goes out of scope, allowing Rust programs to automatically clean up auxiliary resources much like a \CC program.
     489\begin{rustcode}
     490struct S {
     491  name: &'static str
     492}
     493
     494impl Drop for S {  // RAII for S
     495  fn drop(&mut self) {
     496    println!("dropped {}", self.name);
     497  }
     498}
     499
     500{
     501  let x = S { name: "x" };
     502  let y = S { name: "y" };
     503} // prints "dropped y" "dropped x"
     504\end{rustcode}
    457505
    458506% D has constructors and destructors that are worth a mention (under classes) https://dlang.org/spec/spec.html
     
    462510The programming language, D, also manages resources with constructors and destructors \cite{D}.
    463511In D, @struct@s are stack allocated and managed via scoping like in \CC, whereas @class@es are managed automatically by the garbage collector.
    464 Like Java, using the garbage collector means that destructors may never be called, requiring the use of finally statements to ensure dynamically allocated resources that are not managed by the garbage collector, such as open files, are cleaned up.
     512Like 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.
    465513Since D supports RAII, it is possible to use the same techniques as in \CC to ensure that resources are released in a timely manner.
    466 Finally, D provides a scope guard statement, which allows an arbitrary statement to be executed at normal scope exit with \emph{success}, at exceptional scope exit with \emph{failure}, or at normal and exceptional scope exit with \emph{exit}. % TODO: cite? https://dlang.org/spec/statement.html#ScopeGuardStatement
     514Finally, D provides a scope guard statement, which allows an arbitrary statement to be executed at normal scope exit with \emph{success}, at exceptional scope exit with \emph{failure}, or at normal and exceptional scope exit with \emph{exit}. % https://dlang.org/spec/statement.html#ScopeGuardStatement
    467515It has been shown that the \emph{exit} form of the scope guard statement can be implemented in a library in \CC \cite{ExceptSafe}.
    468516
    469 To provide managed types in \CFA, new kinds of constructors and destructors are added to C and discussed in Chapter 2.
     517To provide managed types in \CFA, new kinds of constructors and destructors are added to \CFA and discussed in Chapter 2.
    470518
    471519\section{Tuples}
    472520\label{s:Tuples}
    473 In mathematics, tuples are finite-length sequences which, unlike sets, allow duplicate elements.
     521In mathematics, tuples are finite-length sequences which, unlike sets, are ordered and allow duplicate elements.
    474522In programming languages, tuples provide fixed-sized heterogeneous lists of elements.
    475523Many programming languages have tuple constructs, such as SETL, \KWC, ML, and Scala.
     
    523571Like \CC, D provides tuples through a library variadic template struct.
    524572In D, it is possible to name the fields of a tuple type, which creates a distinct type.
    525 % TODO: cite http://dlang.org/phobos/std_typecons.html
     573% http://dlang.org/phobos/std_typecons.html
    526574\begin{dcode}
    527575Tuple!(float, "x", float, "y") point2D;
     
    572620
    573621
    574 \Csharp also has tuples, but has similarly strange limitations, allowing tuples of size up to 7 components. % TODO: cite https://msdn.microsoft.com/en-us/library/system.tuple(v=vs.110).aspx
     622\Csharp also has tuples, but has similarly strange limitations, allowing tuples of size up to 7 components. % https://msdn.microsoft.com/en-us/library/system.tuple(v=vs.110).aspx
    575623The officially supported workaround for this shortcoming is to nest tuples in the 8th component.
    576624\Csharp allows accessing a component of a tuple by using the field @Item$N$@ for components 1 through 7, and @Rest@ for the nested tuple.
     
    585633In Swift, @Void@ is an alias for the empty tuple, and there are no single element tuples.
    586634
    587 % TODO: this statement feels like it's too strong
    588 Tuples as powerful as the above languages are added to C and discussed in Chapter 3.
     635Tuples comparable to those described above are added to \CFA and discussed in Chapter 3.
    589636
    590637\section{Variadic Functions}
     
    600647printf("%d %g %c %s", 10, 3.5, 'X', "a string");
    601648\end{cfacode}
    602 Through the use of a format string, @printf@ allows C programmers to print any of the standard C data types.
     649Through the use of a format string, C programmers can communicate argument type information to @printf@, allowing C programmers to print any of the standard C data types.
    603650Still, @printf@ is extremely limited, since the format codes are specified by the C standard, meaning users cannot define their own format codes to extend @printf@ for new data types or new formatting rules.
    604651
     
    692739The combination of these two issues greatly restricts the usefulness of variadic functions in Java.
    693740
    694 Type-safe variadic functions are added to C and discussed in Chapter 4.
     741Type-safe variadic functions are added to \CFA and discussed in Chapter 4.
  • doc/rob_thesis/thesis.bib

    rc51b5a3 rf92aa32  
    2424  year = 2011,
    2525  url = {http://www.oracle.com/technetwork/articles/java/trywithresources-401775.html},
     26  note = {\url{http://www.oracle.com/technetwork/articles/java/trywithresources-401775.html}},
    2627  urldate = {2017-04-03}
    2728}
     
    3334  year = 2000,
    3435  url = {http://www.drdobbs.com/cpp/generic-change-the-way-you-write-excepti/184403758},
     36  note = {\url{http://www.drdobbs.com/cpp/generic-change-the-way-you-write-excepti/184403758}},
    3537  urldate = {2017-04-03}
    3638}
     
    5355  pages = {1--6},
    5456  numpages = {6},
    55   url = {http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0144r0.pdf},
     57  note = {\url{http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0144r0.pdf}},
    5658}
     59
     60@manual{atexit,
     61  keywords  = {The Linux Programmer's Manual atexit},
     62  contributer = {rschlunt@uwaterloo.ca},
     63  title = {The Linux Programmer's Manual},
     64  organization= {The GNU Project},
     65  year  = 2017,
     66  note  = {\url{http://man7.org/linux/man-pages/man3/atexit.3.html}},
     67}
  • doc/rob_thesis/thesis.tex

    rc51b5a3 rf92aa32  
    6767}{xcolor}
    6868\documentclass[letterpaper,12pt,titlepage,oneside,final]{book}
     69
     70% For PDF, suitable for double-sided printing, change the PrintVersion variable below
     71% to "true" and use this \documentclass line instead of the one above:
     72% \documentclass[letterpaper,12pt,titlepage,openright,twoside,final]{book}
    6973
    7074\usepackage[T1]{fontenc}                                % allow Latin1 (extended ASCII) characters
     
    9296
    9397\interfootnotelinepenalty=10000
    94 
    95 % For PDF, suitable for double-sided printing, change the PrintVersion variable below
    96 % to "true" and use this \documentclass line instead of the one above:
    97 %\documentclass[letterpaper,12pt,titlepage,openright,twoside,final]{book}
    9898
    9999% Some LaTeX commands I define for my own nomenclature.
  • doc/rob_thesis/tuples.tex

    rc51b5a3 rf92aa32  
    22\chapter{Tuples}
    33%======================================================================
    4 
    5 \section{Introduction}
    6 % TODO: no passing input parameters by assignment, instead will have reference types => this is not a very C-like model and greatly complicates syntax for likely little gain (and would cause confusion with already supported return-by-reference)
    7 % TODO: benefits (conclusion) by Till: reduced number of variables and statements; no specified order of execution for multiple assignment (more optimzation freedom); can store parameter lists in variable; MRV routines (natural code); more convenient assignment statements; simple and efficient access of record fields; named return values more legible and efficient in use of storage
    84
    95\section{Multiple-Return-Value Functions}
     
    128This restriction results in code which emulates functions with multiple return values by \emph{aggregation} or by \emph{aliasing}.
    139In the former situation, the function designer creates a record type that combines all of the return values into a single type.
    14 For example, consider a function returning the most frequently occuring letter in a string, and its frequency.
    15 % TODO: consider simplifying the example!
    16 %   Two things I like about this example:
    17 %   * it uses different types to illustrate why an array is insufficient (this is not necessary, but is nice)
    18 %   * it's complicated enough to show the uninitialized pitfall that exists in the aliasing example.
    19 %   Still, it may be a touch too complicated. Is there a simpler example with these two properties?
     10For example, consider a function returning the most frequently occurring letter in a string, and its frequency.
     11This example is complex enough to illustrate that an array is insufficient, since arrays are homogeneous, and demonstrates a potential pitfall that exists with aliasing.
    2012\begin{cfacode}
    2113struct mf_ret {
     
    8779The expression resolution phase of the \CFA translator ensures that the correct form is used depending on the values being returned and the return type of the current function.
    8880A multiple-returning function with return type @T@ can return any expression that is implicitly convertible to @T@.
    89 Using the running example, the @most_frequent@ function can be written in using multiple return values as such,
     81Using the running example, the @most_frequent@ function can be written using multiple return values as such,
    9082\begin{cfacode}
    9183[int, char] most_frequent(const char * str) {
     
    282274These semantics allow cascading tuple assignment to work out naturally in any context where a tuple is permitted.
    283275These semantics are a change from the original tuple design in \KWC \cite{Till89}, wherein tuple assignment was a statement that allows cascading assignments as a special case.
    284 The \KWC semantics fix what was seen as a problem with assignment, wherein it can be used in many different locations, such as in function-call argument position. % TODO: remove??
     276Restricting tuple assignment to statements was an attempt to to fix what was seen as a problem with assignment, wherein it can be used in many different locations, such as in function-call argument position.
    285277While permitting assignment as an expression does introduce the potential for subtle complexities, it is impossible to remove assignment expressions from \CFA without affecting backwards compatibility.
    286278Furthermore, there are situations where permitting assignment as an expression improves readability by keeping code succinct and reducing repetition, and complicating the definition of tuple assignment puts a greater cognitive burden on the user.
     
    313305[S, S] z = x.0;        // uses (4), (4), copy constructor
    314306\end{cfacode}
    315 In this example, @x@ is initialized by the multiple constructor calls @?{}(&x.0, 3)@ and @?{}(&x.1, 6.28)@, while @y@ is initilaized by two default constructor calls @?{}(&y.0)@ and @?{}(&y.1)@.
     307In this example, @x@ is initialized by the multiple constructor calls @?{}(&x.0, 3)@ and @?{}(&x.1, 6.28)@, while @y@ is initialized by two default constructor calls @?{}(&y.0)@ and @?{}(&y.1)@.
    316308@z@ is initialized by mass copy constructor calls @?{}(&z.0, x.0)@ and @?{}(&z.1, x.0)@.
    317309Finally, @x@, @y@, and @z@ are destructed, i.e. the calls @^?{}(&x.0)@, @^?{}(&x.1)@, @^?{}(&y.0)@, @^?{}(&y.1)@, @^?{}(&z.0)@, and @^?{}(&z.1)@.
     
    392384z.y;  // ???
    393385\end{cfacode}
    394 One possiblity is for @s.1@ to select the second member of @s@.
     386One possibility is for @s.1@ to select the second member of @s@.
    395387Under this interpretation, it becomes possible to not only access members of a struct by name, but also by position.
    396388Likewise, it seems natural to open this mechanism to enumerations as well, wherein the left side would be a type, rather than an expression.
    397 One benefit of this interpretation is familiar, since it is extremely reminiscent of tuple-index expressions.
     389One benefit of this interpretation is familiarity, since it is extremely reminiscent of tuple-index expressions.
    398390On the other hand, it could be argued that this interpretation is brittle in that changing the order of members or adding new members to a structure becomes a brittle operation.
    399391This problem is less of a concern with tuples, since modifying a tuple affects only the code that directly uses the tuple, whereas modifying a structure has far reaching consequences for every instance of the structure.
    400392
    401 As for @z.y@, a one interpretation is to extend the meaning of member tuple expressions.
     393As for @z.y@, one interpretation is to extend the meaning of member tuple expressions.
    402394That is, currently the tuple must occur as the member, i.e. to the right of the dot.
    403395Allowing tuples to the left of the dot could distribute the member across the elements of the tuple, in much the same way that member tuple expressions distribute the aggregate across the member tuple.
     
    430422p1.0 + p1.1 + p2.0 + p2.1;  // equivalent
    431423\end{cfacode}
    432 In this simpler interpretation, a named tuple type carries with it a list of possibly empty identifiers.
     424In this simpler interpretation, a tuple type carries with it a list of possibly empty identifiers.
    433425This approach fits naturally with the named return-value feature, and would likely go a long way towards implementing it.
    434426
    435 Ultimately, the first two extensions introduce complexity into the model, with relatively little peceived benefit, and so were dropped from consideration.
     427Ultimately, the first two extensions introduce complexity into the model, with relatively little perceived benefit, and so were dropped from consideration.
    436428Named tuples are a potentially useful addition to the language, provided they can be parsed with a reasonable syntax.
    437429
     
    439431\section{Casting}
    440432In C, the cast operator is used to explicitly convert between types.
    441 In \CFA, the cast operator has a secondary use, which is type ascription.
     433In \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.
    442434That 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.
    443435\begin{cfacode}
     
    515507\end{cfacode}
    516508Note that due to the implicit tuple conversions, this function is not restricted to the addition of two triples.
     509A call to this plus operator type checks as long as a total of 6 non-tuple arguments are passed after flattening, and all of the arguments have a common type that can bind to @T@, with a pairwise @?+?@ over @T@.
    517510For example, these expressions also succeed and produce the same value.
    518 A call to this plus operator type checks as long as a total of 6 non-tuple arguments are passed after flattening, and all of the arguments have a common type that can bind to @T@, with a pairwise @?+?@ over @T@.
    519511\begin{cfacode}
    520512([x.0, x.1]) + ([x.2, 10, 20, 30]);  // x + ([10, 20, 30])
     
    522514\end{cfacode}
    523515This presents a potential problem if structure is important, as these three expressions look like they should have different meanings.
    524 Furthermore, these calls can be made ambiguous by adding seemingly different functions.
     516Furthermore, these calls can be made ambiguous by introducing seemingly different functions.
    525517\begin{cfacode}
    526518forall(otype T | { T ?+?(T, T); })
     
    630622g(h());
    631623\end{cfacode}
    632 Interally, this is converted to psuedo-\CFA
     624Internally, this is converted to pseudo-\CFA
    633625\begin{cfacode}
    634626void g(int, double);
    635627[int, double] h();
    636 lazy [int, double] unq<0> = h();
    637 g(unq<0>.0, unq<0>.1);
     628lazy [int, double] unq0 = h(); // deferred execution
     629g(unq0.0, unq0.1);             // execute h() once
    638630\end{cfacode}
    639631That is, the function @h@ is evaluated lazily and its result is stored for subsequent accesses.
     
    654646Every subsequent evaluation of the unique expression then results in an access to the stored result of the actual expression.
    655647
    656 Currently, the \CFA translator has a very broad, imprecise definition of impurity (side-effects), where any function call is assumed to be impure.
    657 This notion could be made more precise for certain intrinsic, autogenerated, and builtin functions, and could analyze function bodies, when they are available, to recursively detect impurity, to eliminate some unique expressions.
     648Currently, the \CFA translator has a very broad, imprecise definition of impurity (side-effects), where every function call is assumed to be impure.
     649This notion could be made more precise for certain intrinsic, auto-generated, and built-in functions, and could analyze function bodies, when they are available, to recursively detect impurity, to eliminate some unique expressions.
    658650It is possible that lazy evaluation could be exposed to the user through a lazy keyword with little additional effort.
    659651
  • doc/rob_thesis/variadic.tex

    rc51b5a3 rf92aa32  
    33%======================================================================
    44
    5 \section{Design Criteria} % TOOD: better section name???
     5\section{Design Criteria} % TODO: better section name???
    66C provides variadic functions through the manipulation of @va_list@ objects.
    77A variadic function is one which contains at least one parameter, followed by @...@ as the last token in the parameter list.
    88In particular, some form of \emph{argument descriptor} is needed to inform the function of the number of arguments and their types.
    99Two common argument descriptors are format strings or counter parameters.
    10 It is important to note that both of these mechanisms are inherently redundant, because they require the user to specify information that the compiler knows explicitly.
     10It 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.
    1111This required repetition is error prone, because it is easy for the user to add or remove arguments without updating the argument descriptor.
    1212In addition, C requires the programmer to hard code all of the possible expected types.
     
    6363Likewise, when inferring assertion @g@, an exact match is found.
    6464
    65 This approach is strict with respect to argument structure by nature, which makes it syntactically awkward to use in ways that the existing tuple design is not.
    66 For example, consider a @new@ function that allocates memory using @malloc@ and constructs the result, using arbitrary arguments.
     65This approach is strict with respect to argument structure, by nature, which makes it syntactically awkward to use in ways that the existing tuple design is not.
     66For example, consider a @new@ function that allocates memory using @malloc@, and constructs the result using arbitrary arguments.
    6767\begin{cfacode}
    6868struct Array;
     
    110110In order to call (1), @10@ is matched with @x@, and the argument resolution moves on to the argument pack @rest@, which consumes the remainder of the argument list and @Params@ is bound to @[20, 30]@.
    111111In order to finish the resolution of @sum@, an assertion parameter that matches @int sum(int, int)@ is required.
    112 Like in the previous iteration, (0) is not a valid candiate, so (1) is examined with @Params@ bound to @[int]@, requiring the assertion @int sum(int)@.
     112Like in the previous iteration, (0) is not a valid candidate, so (1) is examined with @Params@ bound to @[int]@, requiring the assertion @int sum(int)@.
    113113Next, (0) fails, and to satisfy (1) @Params@ is bound to @[]@, requiring an assertion @int sum()@.
    114114Finally, (0) matches and (1) fails, which terminates the recursion.
     
    173173A notable limitation of this approach is that it heavily relies on recursive assertions.
    174174The \CFA translator imposes a limitation on the depth of the recursion for assertion satisfaction.
    175 Currently, the limit is set to 4, which means that the first iteration of the @sum@ function is limited to at most 5 arguments, while the second iteration can support up to 6 arguments.
     175Currently, the limit is set to 4, which means that the first version of the @sum@ function is limited to at most 5 arguments, while the second version can support up to 6 arguments.
    176176The limit is set low due to inefficiencies in the current implementation of the \CFA expression resolver.
    177177There is ongoing work to improve the performance of the resolver, and with noticeable gains, the limit can be relaxed to allow longer argument lists to @ttype@ functions.
    178178
    179179C variadic syntax and @ttype@ polymorphism probably should not be mixed, since it is not clear where to draw the line to decide which arguments belong where.
    180 Furthermore, it might be desirable to disallow polymorphic functions to use C variadic syntax to encourage a Cforall style.
     180Furthermore, it might be desirable to disallow polymorphic functions to use C variadic syntax to encourage a \CFA style.
    181181Aside from calling C variadic functions, it is not obvious that there is anything that can be done with C variadics that could not also be done with @ttype@ parameters.
    182182
Note: See TracChangeset for help on using the changeset viewer.