Changeset f674479


Ignore:
Timestamp:
Apr 11, 2017, 4:20:51 PM (5 years ago)
Author:
Peter A. Buhr <pabuhr@…>
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:
da1c772
Parents:
a0fc78a (diff), 32bcef7 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg2:software/cfa/cfa-cc

Files:
10 added
16 edited

Legend:

Unmodified
Added
Removed
  • doc/generic_types/generic_types.tex

    ra0fc78a rf674479  
    228228\end{lstlisting}
    229229Within the block, the nested version of @<@ performs @>@ and this local version overrides the built-in @<@ so it is passed to @qsort@.
    230 Hence, programmers can easily form a local environments, adding and modifying appropriate functions, to maximize reuse of other existing functions and types.
     230Hence, programmers can easily form local environments, adding and modifying appropriate functions, to maximize reuse of other existing functions and types.
    231231
    232232Finally, \CFA allows variable overloading:
  • doc/rob_thesis/cfa-format.tex

    ra0fc78a rf674479  
    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

    ra0fc78a rf674479  
    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.
     24
     25\section{Future Work}
     26\subsection{Constructors and Destructors}
     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.
     230
     231\subsection{Tuples}
     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.
     238
     239\subsection{Variadic Functions}
     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

    ra0fc78a rf674479  
    33%======================================================================
    44
    5 % TODO: discuss move semantics; they haven't been implemented, but could be. Currently looking at alternative models. (future work)
    6 
    7 % 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
    86% doesn't seem possible to do this without allowing ttype on generic structs?
    97
    10 % If a Cforall constructor is in scope, C style initialization is
    11 % disabled by default.
    12 % * initialization rule: if any constructor is in scope for type T, try
    13 %   to find a matching constructor for the call. If there are no
    14 %   constructors in scope for type T, then attempt to fall back on
    15 %   C-style initialization.
    16 % + if this rule was not in place, it would be easy to accidentally
    17 %   use C-style initialization in certain cases, which could lead to
    18 %   subtle errors [2]
    19 % - this means we need special syntax if we want to allow users to force
    20 %   a C-style initialization (to give users more control)
    21 % - two different declarations in the same scope can be implicitly
    22 %   initialized differently. That is, there may be two objects of type
    23 %   T that are initialized differently because there is a constructor
    24 %   definition between them. This is not technically specific to
    25 %   constructors.
    26 
    27 % C-style initializers can be accessed with @= syntax
    28 % + provides a way to get around the requirement of using a constructor
    29 %   (for advanced programmers only)
    30 % - can break invariants in the type => unsafe
    31 % * provides a way of asserting that a variable is an instance of a
    32 %   C struct (i.e. a POD struct), and so will not be implicitly
    33 %   destructed (this can be useful at times, maybe mitigates the need
    34 %   for move semantics?) [3]
    35 % + can modernize a code base one step at a time
    36 
    37 % Cforall constructors can be used in expressions to initialize any
    38 % piece of memory.
    39 % + malloc() { ... } calls the appropriate constructor on the newly
    40 %   allocated space; the argument is moved into the constructor call
    41 %   without taking its address [4]
    42 % - with the above form, there is still no way to ensure that
    43 %   dynamically allocated objects are constructed. To resolve this,
    44 %   we might want a stronger "new" function which always calls the
    45 %   constructor, although how we accomplish that is currently still
    46 %   unresolved (compiler magic vs. better variadic functions?)
    47 % + This can be used as a placement syntax [5]
    48 % - can call the constructor on an object more than once, which could
    49 %   cause resource leaks and reinitialize const fields (can try to
    50 %   detect and prevent this in some cases)
    51 %   * compiler always tries to implicitly insert a ctor/dtor pair for
    52 %     non-@= objects.
    53 %     * For POD objects, this will resolve to an autogenerated or
    54 %       intrinsic function.
    55 %     * Intrinsic functions are not automatically called. Autogenerated
    56 %       are, because they may call a non-autogenerated function.
    57 %     * destructors are automatically inserted at appropriate branches
    58 %       (e.g. return, break, continue, goto) and at the end of the block
    59 %       in which they are declared.
    60 %   * For @= objects, the compiler never tries to interfere and insert
    61 %     constructor and destructor calls for that object. Copy constructor
    62 %     calls do not count, because the object is not the target of the copy
    63 %     constructor.
    64 
    65 % A constructor is declared with the name ?{}
    66 % + combines the look of C initializers with the precedent of ?() being
    67 %   the name for the function call operator
    68 % + it is possible to easily search for all constructors in a project
    69 %   and immediately know that a function is a constructor by seeing the
    70 %   name "?{}"
    71 
    72 % A destructor is declared with the name ^?{}
    73 % + name mirrors a constructor's name, with an extra symbol to
    74 %   distinguish it
    75 % - the symbol '~' cannot be used due to parsing conflicts with the
    76 %   unary '~' (bitwise negation) operator - this conflict exists because
    77 %   we want to allow users to write ^x{}; to destruct x, rather than
    78 %   ^?{}(&x);
    79 
    80 % The first argument of a constructor must be a pointer. The constructed
    81 % type is the base type of the pointer. E.g. void ?{}(T *) is a default
    82 % constructor for a T.
    83 % + can name the argument whatever you like, so not constrained by
    84 %   language keyword "this" or "self", etc.
    85 % - have to explicitly qualify all object members to initialize them
    86 %   (e.g. this->x = 0, rather than just x = 0)
    87 
    88 % Destructors can take arguments other than just the destructed pointer
    89 % * open research problem: not sure how useful this is
    90 
    91 % Pointer constructors
    92 % + can construct separately compiled objects (opaque types) [6]
    93 % + orthogonal design, follows directly from the definition of the first
    94 %   argument of a constructor
    95 % - may require copy constructor or move constructor (or equivalent)
    96 %   for correct implementation, which may not be obvious to everyone
    97 % + required feature for the prelude to specify as much behavior as possible
    98 %   (similar to pointer assignment operators in this respect)
    99 
    100 % Designations can only be used for C-style initialization
    101 % * designation for constructors is equivalent to designation for any
    102 %   general function call. Since a function prototype can be redeclared
    103 %   many times, with arguments named differently each time (or not at
    104 %   all!), this is considered to be an undesirable feature. We could
    105 %   construct some set of rules to allow this behaviour, but it is
    106 %   probably more trouble than it's worth, and no matter what we choose,
    107 %   it is not likely to be obvious to most people.
    108 
    109 % Constructing an anonymous member [7]
    110 % + same as with calling any other function on an anonymous member
    111 %   (implicit conversion by the compiler)
    112 % - may be some cases where this is ambiguous => clarify with a cast
    113 %   (try to design APIs to avoid sharing function signatures between
    114 %   composed types to avoid this)
    115 
    116 % Default Constructors and Destructors are called implicitly
    117 % + cannot forget to construct or destruct an object
    118 % - requires special syntax to specify that an object is not to be
    119 %   constructed (@=)
    120 % * an object will not be implicitly constructed OR destructed if
    121 %   explicitly initialized like a C object (@= syntax)
    122 % * an object will be destructed if there are no constructors in scope
    123 %   (even though it is initialized like a C object) [8]
    124 
    125 % An object which changes from POD type to non POD type will not change
    126 % the semantics of a type containing it by composition
    127 % * That is, constructors will not be regenerated at the point where
    128 %   an object changes from POD type to non POD type, because this could
    129 %   cause a cascade of constructors being regenerated for many other
    130 %   types. Further, there is precedence for this behaviour in other
    131 %   facets of Cforall's design, such as how nested functions interact.
    132 % * This behaviour can be simplified in a language without declaration
    133 %   before use, because a type can be classified as POD or non POD
    134 %   (rather than potentially changing between the two at some point) at
    135 %   at the global scope (which is likely the most common case)
    136 % * [9]
    137 
    138 % Changes to polymorphic type classes
    139 % * dtype and ftype remain the same
    140 % * forall(otype T) is currently essentially the same as
    141 %   forall(dtype T | { @size(T); void ?=?(T *, T); }).
    142 %   The big addition is that you can declare an object of type T, rather
    143 %   than just a pointer to an object of type T since you know the size,
    144 %   and you can assign into a T.
    145 %   * this definition is changed to add default constructor and
    146 %     destructor declarations, to remain consistent with what type meant
    147 %     before the introduction of constructors and destructors.
    148 %     * that is, forall(type T) is now essentially the same as
    149 %       forall(dtype T | { @size(T); void ?=?(T *, T);
    150 %                          void ?{}(T *); void ^?{}(T *); })
    151 %     + this is required to make generic types work correctly in
    152 %       polymorphic functions
    153 %     ? since declaring a constructor invalidates the autogenerated
    154 %       routines, it is possible for a type to have constructors, but
    155 %       not default constructors. That is, it might be the case that
    156 %       you want to write a polymorphic function for a type which has
    157 %       a size, but non-default constructors? Some options:
    158 %       * declaring a constructor as a part of the assertions list for
    159 %         a type declaration invalidates the default, so
    160 %         forall(otype T | { void ?{}(T *, int); })
    161 %         really means
    162 %         forall(dtype T | { @size(T); void ?=?(T *, T);
    163 %                            void ?{}(T *, int); void ^?{}(T *); })
    164 %       * force users to fully declare the assertions list like the
    165 %         above in this case (this seems very undesirable)
    166 %       * add another type class with the current desugaring of type
    167 %         (just size and assignment)
    168 %       * provide some way of subtracting from an existing assertions
    169 %         list (this might be useful to have in general)
    170 
    171 % Implementation issues:
    172 % Changes to prelude/autogen or built in defaults?
    173 % * pointer ctors/dtors [prelude]
    174 %   * other pointer type routines are declared in the prelude, and this
    175 %     doesn't seem like it should be any different
    176 % * basic type ctors/dtors [prelude]
    177 %   * other basic type routines are declared in the prelude, and this
    178 %     doesn't seem like it should be any different
    179 % ? aggregate types [undecided, but leaning towards autogenerate]
    180 %   * prelude
    181 %     * routines specific to aggregate types cannot be predeclared in
    182 %       the prelude because we don't know the name of every
    183 %       aggregate type in the entire program
    184 %   * autogenerate
    185 %     + default assignment operator is already autogenerated for
    186 %       aggregate types
    187 %       * this seems to lead us in the direction of autogenerating,
    188 %         because we may have a struct which contains other objects
    189 %         that require construction [10]. If we choose not to
    190 %         autogenerate in this case, then objects which are part of
    191 %         other objects by composition will not be constructed unless
    192 %         a constructor for the outer type is explicitly defined
    193 %       * in this case, we would always autogenerate the appropriate
    194 %         constructor(s) for an aggregate type, but just like with
    195 %         basic types, pointer types, and enum types, the constructor
    196 %         call can be elided when when it is not necessary.
    197 %     + constructors will have to be explicitly autogenerated
    198 %       in the case where they are required for a polymorphic function,
    199 %       when no user defined constructor is in scope, which may make it
    200 %       easiest to always autogenerate all appropriate constructors
    201 %     - n+2 constructors would have to be generated for a POD type
    202 %       * one constructor for each number of valid arguments [0, n],
    203 %         plus the copy constructor
    204 %         * this is taking a simplified approach: in C, it is possible
    205 %           to omit the enclosing braces in a declaration, which would
    206 %           lead to a combinatorial explosion of generated constructors.
    207 %           In the interest of keeping things tractable, Cforall may be
    208 %           incompatible with C in this case. [11]
    209 %       * for non-POD types, only autogenerate the default and copy
    210 %         constructors
    211 %       * alternative: generate only the default constructor and
    212 %         special case initialization for any other constructor when
    213 %         only the autogenerated one exists
    214 %         - this is not very sensible, as by the previous point, these
    215 %           constructors may be needed for polymorphic functions
    216 %           anyway.
    217 %     - must somehow distinguish in resolver between autogenerated and
    218 %       user defined constructors (autogenerated should never be chosen
    219 %       when a user defined option exists [check first parameter], even
    220 %       if full signature differs) (this may also have applications
    221 %       to other autogenerated routines?)
    222 %     - this scheme does not naturally support designation (i.e. general
    223 %       functions calls do not support designation), thus these cases
    224 %       will have to be treated specially in either case
    225 %   * defaults
    226 %     * i.e. hardcode a new set of rules for some "appropriate" default
    227 %       behaviour for
    228 %     + when resolving an initialization expression, explicitly check to
    229 %       see if any constructors are in scope. If yes, attempt to resolve
    230 %       to a constructor, and produce an error message if a match is not
    231 %       found. If there are no constructors in scope, resolve to
    232 %       initializing each field individually (C-style)
    233 %     + does not attempt to autogenerate constructors for POD types,
    234 %       which can be seen as a space optimization for the program
    235 %       binary
    236 %     - as stated previously, a polymorphic routine may require these
    237 %       autogenerated constructors, so this doesn't seem like a big win,
    238 %       because this leads to more complicated logic and tracking of
    239 %       which constructors have already been generated
    240 %     - even though a constructor is not explicitly declared or used
    241 %       polymorphically, we might still need one for all uses of a
    242 %       struct (e.g. in the case of composition).
    243 %   * the biggest tradeoff in autogenerating vs. defaulting appears to
    244 %     be in where and how the special code to check if constructors are
    245 %     present is handled. It appears that there are more reasons to
    246 %     autogenerate than not.
    247 
    248 % --- examples
    249 % [1] As an example of using constructors polymorphically, consider a
    250 % slight modification on the foldl example I put on the mailing list a
    251 % few months ago:
    252 
    253 % context iterable(type collection, type element, type iterator) {
    254 %   void ?{}(iterator *, collection); // used to be makeIterator, but can
    255 %                             // idiomatically use constructor
    256 %   int hasNext(iterator);
    257 %   iterator ++?(iterator *);
    258 %   lvalue element *?(iterator);
    259 % };
    260 
    261 
    262 % forall(type collection, type element, type result, type iterator
    263 %   | iterable(collection, element, iterator))
    264 % result foldl(collection c, result acc,
    265 %     result (*reduce)(result, element)) {
    266 %   iterator it = { c };
    267 %   while (hasNext(it)) {
    268 %     acc = reduce(acc, *it);
    269 %     ++it;
    270 %   }
    271 %   return acc;
    272 % }
    273 
    274 % Now foldl makes use of the knowledge that the iterator type has a
    275 % single argument constructor which takes the collection to iterate
    276 % over. This pattern allows polymorphic code to look more natural
    277 % (constructors are generally preferred to named initializer/creation
    278 % routines, e.g. "makeIterator")
    279 
    280 % [2] An example of some potentially dangerous code that we don't want
    281 % to let easily slip through the cracks - if this is really what you
    282 % want, then use @= syntax for the second declaration to quiet the
    283 % compiler.
    284 
    285 % struct A { int x, y, z; }
    286 % ?{}(A *, int);
    287 % ?{}(A *, int, int, int);
    288 
    289 % A a1 = { 1 };         // uses ?{}(A *, int);
    290 % A a2 = { 2, 3 };      // C-style initialization -> no invariants!
    291 % A a3 = { 4, 5, 6 };   // uses ?{}(A *, int, int, int);
    292 
    293 % [3] Since @= syntax creates a C object (essentially a POD, as far as
    294 % the compiler is concerned), the object will not be destructed
    295 % implicitly when it leaves scope, nor will it be copy constructed when
    296 % it is returned. In this case, a memcpy should be equivalent to a move.
    297 
    298 % // Box.h
    299 % struct Box;
    300 % void ?{}(Box **, int};
    301 % void ^?{}(Box **);
    302 % Box * make_fortytwo();
    303 
    304 % // Box.cfa
    305 % Box * make_fortytwo() {
    306 %   Box *b @= {};
    307 %   (&b){ 42 }; // construct explicitly
    308 %   return b; // no destruction, essentially a move?
    309 % }
    310 
    311 % [4] Cforall's typesafe malloc can be composed with constructor
    312 % expressions. It is possible for a user to define their own functions
    313 % similar to malloc and achieve the same effects (e.g. Aaron's example
    314 % of an arena allocator)
    315 
    316 % // CFA malloc
    317 % forall(type T)
    318 % T * malloc() { return (T *)malloc(sizeof(T)); }
    319 
    320 % struct A { int x, y, z; };
    321 % void ?{}(A *, int);
    322 
    323 % int foo(){
    324 %   ...
    325 %   // desugars to:
    326 %   // A * a = ?{}(malloc(), 123);
    327 %   A * a = malloc() { 123 };
    328 %   ...
    329 % }
    330 
    331 % [5] Aaron's example of combining function calls with constructor
    332 % syntax to perform an operation similar to C++'s std::vector::emplace
    333 % (i.e. to construct a new element in place, without the need to
    334 % copy)
    335 
    336 % forall(type T)
    337 % struct vector {
    338 %   T * elem;
    339 %   int len;
    340 %   ...
    341 % };
    342 
    343 % ...
    344 % forall(type T)
    345 % T * vector_new(vector(T) * v) {
    346 %   // reallocate if needed
    347 %   return &v->elem[len++];
    348 % }
    349 
    350 % int main() {
    351 %   vector(int) * v = ...
    352 %   vector_new(v){ 42 };  // add element to the end of vector
    353 % }
    354 
    355 % [6] Pointer Constructors. It could be useful to use the existing
    356 % constructor syntax even more uniformly for ADTs. With this, ADTs can
    357 % be initialized in the same manor as any other object in a polymorphic
    358 % function.
    359 
    360 % // vector.h
    361 % forall(type T) struct vector;
    362 % forall(type T) void ?{}(vector(T) **);
    363 % // adds an element to the end
    364 % forall(type T) vector(T) * ?+?(vector(T) *, T);
    365 
    366 % // vector.cfa
    367 % // don't want to expose the implementation to the user and/or don't
    368 % // want to recompile the entire program if the struct definition
    369 % // changes
    370 
    371 % forall(type T) struct vector {
    372 %   T * elem;
    373 %   int len;
    374 %   int capacity;
    375 % };
    376 
    377 % forall(type T) void resize(vector(T) ** v) { ... }
    378 
    379 % forall(type T) void ?{}(vector(T) ** v) {
    380 %   vector(T) * vect = *v = malloc();
    381 %   vect->capacity = 10;
    382 %   vect->len = 0;
    383 %   vect->elem = malloc(vect->capacity);
    384 % }
    385 
    386 % forall(type T) vector(T) * ?+?(vector(T) *v, T elem) {
    387 %   if (v->len == v->capacity) resize(&v);
    388 %   v->elem[v->len++] = elem;
    389 % }
    390 
    391 % // main.cfa
    392 % #include "adt.h"
    393 % forall(type T | { T ?+?(T, int); }
    394 % T sumRange(int lower, int upper) {
    395 %   T x;    // default construct
    396 %   for (int i = lower; i <= upper; i++) {
    397 %     x = x + i;
    398 %   }
    399 %   return x;
    400 % }
    401 
    402 % int main() {
    403 %   vector(int) * numbers = sumRange(1, 10);
    404 %   // numbers is now a vector containing [1..10]
    405 
    406 %   int sum = sumRange(1, 10);
    407 %   // sum is now an int containing the value 55
    408 % }
    409 
    410 % [7] The current proposal is to use the plan 9 model of inheritance.
    411 % Under this model, all of the members of an unnamed struct instance
    412 % become members of the containing struct. In addition, an object
    413 % can be passed as an argument to a function expecting one of its
    414 % base structs.
    415 
    416 % struct Point {
    417 %   double x;
    418 %   double y;
    419 % };
    420 
    421 % struct ColoredPoint {
    422 %   Point;        // anonymous member (no identifier)
    423 %                 // => a ColoredPoint has an x and y of type double
    424 %   int color;
    425 % };
    426 
    427 % ColoredPoint cp = ...;
    428 % cp.x = 10.3;    // x from Point is accessed directly
    429 % cp.color = 0x33aaff; // color is accessed normally
    430 % foo(cp);        // cp can be used directly as a Point
    431 
    432 % void ?{}(Point *p, double x, double y) {
    433 %   p->x = x;
    434 %   p->y = y;
    435 % }
    436 
    437 % void ?{}(ColoredPoint *cp, double x, double y, int color) {
    438 %   (&cp){ x, y };  // unambiguous, no ?{}(ColoredPoint*,double,double)
    439 %   cp->color = color;
    440 % }
    441 
    442 % struct Size {
    443 %   double width;
    444 %   double height;
    445 % };
    446 
    447 % void ?{}(Size *s, double w, double h) {
    448 %   p->width = w;
    449 %   p->height = h;
    450 % }
    451 
    452 % struct Foo {
    453 %   Point;
    454 %   Size;
    455 % }
    456 
    457 % ?{}(Foo &f, double x, double y, double w, double h) {
    458 %   // (&F,x,y) is ambiguous => is it ?{}(Point*,double,double) or
    459 %   // ?{}(Size*,double,double)? Solve with a cast:
    460 %   ((Point*)&F){ x, y };
    461 %   ((Size*)&F){ w, h };
    462 % }
    463 
    464 % [8] Destructors will be called on objects that were not constructed.
    465 
    466 % struct A { ... };
    467 % ^?{}(A *);
    468 % {
    469 %   A x;
    470 %   A y @= {};
    471 % } // x is destructed, even though it wasn't constructed
    472 %   // y is not destructed, because it is explicitly a C object
    473 
    474 
    475 % [9] A type's constructor is generated at declaration time using
    476 % current information about an object's members. This is analogous to
    477 % the treatment of other operators. For example, an object's assignment
    478 % operator will not change to call the override of a member's assignment
    479 % operator unless the object's assignment is also explicitly overridden.
    480 % This problem can potentially be treated differently in Do, since each
    481 % compilation unit is passed over at least twice (once to gather
    482 % symbol information, once to generate code - this is necessary to
    483 % achieve the "No declarations" goal)
    484 
    485 % struct A { ... };
    486 % struct B { A x; };
    487 % ...
    488 % void ?{}(A *);  // from this point on, A objects will be constructed
    489 % B b1;           // b1 and b1.x are both NOT constructed, because B
    490 %                 // objects are not constructed
    491 % void ?{}(B *);  // from this point on, B objects will be constructed
    492 % B b2;           // b2 and b2.x are both constructed
    493 
    494 % struct C { A x; };
    495 % // implicit definition of ?{}(C*), because C is not a POD type since
    496 % // it contains a non-POD type by composition
    497 % C c;            // c and c.x are both constructed
    498 
    499 % [10] Requiring construction by composition
    500 
    501 % struct A {
    502 %   ...
    503 % };
    504 
    505 % // declared ctor disables default c-style initialization of
    506 % // A objects; A is no longer a POD type
    507 % void ?{}(A *);
    508 
    509 % struct B {
    510 %   A x;
    511 % };
    512 
    513 % // B objects can not be C-style initialized, because A objects
    514 % // must be constructed => B objects are transitively not POD types
    515 % B b; // b.x must be constructed, but B is not constructible
    516 %      // => must autogenerate ?{}(B *) after struct B definition,
    517 %      // which calls ?{}(&b.x)
    518 
    519 % [11] Explosion in the number of generated constructors, due to strange
    520 % C semantics.
    521 
    522 % struct A { int x, y; };
    523 % struct B { A u, v, w; };
    524 
    525 % A a = { 0, 0 };
    526 
    527 % // in C, you are allowed to do this
    528 % B b1 = { 1, 2, 3, 4, 5, 6 };
    529 % B b2 = { 1, 2, 3 };
    530 % B b3 = { a, a, a };
    531 % B b4 = { a, 5, 4, a };
    532 % B b5 = { 1, 2, a, 3 };
    533 
    534 % // we want to disallow b1, b2, b4, and b5 in Cforall.
    535 % // In particular, we will autogenerate these constructors:
    536 % void ?{}(A *);             // default/0 parameters
    537 % void ?{}(A *, int);        // 1 parameter
    538 % void ?{}(A *, int, int);   // 2 parameters
    539 % void ?{}(A *, const A *);  // copy constructor
    540 
    541 % void ?{}(B *);             // default/0 parameters
    542 % void ?{}(B *, A);          // 1 parameter
    543 % void ?{}(B *, A, A);       // 2 parameters
    544 % void ?{}(B *, A, A, A);    // 3 parameters
    545 % void ?{}(B *, const B *);  // copy constructor
    546 
    547 % // we will not generate constructors for every valid combination
    548 % // of members in C. For example, we will not generate
    549 % void ?{}(B *, int, int, int, int, int, int);   // b1 would need this
    550 % void ?{}(B *, int, int, int);                  // b2 would need this
    551 % void ?{}(B *, A, int, int, A);                 // b4 would need this
    552 % void ?{}(B *, int, int, A, int);               // b5 would need this
    553 % // and so on
    554 
    555 
    556 
    557 % TODO: talk somewhere about compound literals?
    558 
    5598Since \CFA is a true systems language, it does not provide a garbage collector.
    560 As well, \CFA is not an object-oriented programming language, i.e. structures cannot have routine members.
     9As well, \CFA is not an object-oriented programming language, i.e., structures cannot have routine members.
    56110Nevertheless, one important goal is to reduce programming complexity and increase safety.
    56211To that end, \CFA provides support for implicit pre/post-execution of routines for objects, via constructors and destructors.
    56312
    564 % TODO: this is old. remove or refactor
    565 % Manual resource management is difficult.
    566 % Part of the difficulty results from not having any guarantees about the current state of an object.
    567 % Objects can be internally composed of pointers that may reference resources which may or may not need to be manually released, and keeping track of that state for each object can be difficult for the end user.
    568 
    569 % Constructors and destructors provide a mechanism to bookend the lifetime of an object, allowing the designer of a type to establish invariants for objects of that type.
    570 % Constructors guarantee that object initialization code is run before the object can be used, while destructors provide a mechanism that is guaranteed to be run immediately before an object's lifetime ends.
    571 % Constructors and destructors can help to simplify resource management when used in a disciplined way.
    572 % In particular, when all resources are acquired in a constructor, and all resources are released in a destructor, no resource leaks are possible.
    573 % This pattern is a popular idiom in several languages, such as \CC, known as RAII (Resource Acquisition Is Initialization).
    574 
    57513This chapter details the design of constructors and destructors in \CFA, along with their current implementation in the translator.
    576 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.
    57715
    57816\section{Design Criteria}
     
    59230Next, @x@ is assigned the value of @y@.
    59331In the last line, @z@ is implicitly initialized to 0 since it is marked @static@.
    594 The key difference between assignment and initialization being that assignment occurs on a live object (i.e. an object that contains data).
     32The key difference between assignment and initialization being that assignment occurs on a live object (i.e., an object that contains data).
    59533It is important to note that this means @x@ could have been used uninitialized prior to being assigned, while @y@ could not be used uninitialized.
    596 Use of uninitialized variables yields undefined behaviour, which is a common source of errors in C programs. % TODO: *citation*
    597 
    598 Declaration initialization is insufficient, because it permits uninitialized variables to exist and because it does not allow for the insertion of arbitrary code before the variable is live.
    599 Many C compilers give good warnings most of the time, but they cannot in all cases.
    600 \begin{cfacode}
    601 int f(int *);  // never reads the parameter, only writes
    602 int g(int *);  // reads the parameter - expects an initialized variable
     34Use of uninitialized variables yields undefined behaviour, which is a common source of errors in C programs.
     35
     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.
     38Many C compilers give good warnings for uninitialized variables most of the time, but they cannot in all cases.
     39\begin{cfacode}
     40int f(int *);  // output parameter: never reads, only writes
     41int g(int *);  // input parameter: never writes, only reads,
     42               // so requires initialized variable
    60343
    60444int x, y;
    60545f(&x);  // okay - only writes to x
    606 g(&y);  // will use y uninitialized
    607 \end{cfacode}
    608 Other languages are able to give errors in the case of uninitialized variable use, but due to backwards compatibility concerns, this cannot be the case in \CFA.
    609 
    610 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.
     46g(&y);  // uses y uninitialized
     47\end{cfacode}
     48Other 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.
     49
     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.
    61151\begin{cfacode}
    61252struct array_int {
     
    61454};
    61555struct array_int create_array(int sz) {
    616   return (struct array_int) { malloc(sizeof(int)*sz) };
     56  return (struct array_int) { calloc(sizeof(int)*sz) };
    61757}
    61858void destroy_rh(struct resource_holder * rh) {
     
    63474Furthermore, even with this idiom it is easy to make mistakes, such as forgetting to destroy an object or destroying it multiple times.
    63575
    636 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.
    63777This 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.
    63878Since 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.
    63979
    64080In \CFA, a constructor is a function with the name @?{}@.
     81Like other operators in \CFA, the name represents the syntax used to call the constructor, e.g., @struct S = { ... };@.
    64182Every constructor must have a return type of @void@ and at least one parameter, the first of which is colloquially referred to as the \emph{this} parameter, as in many object-oriented programming-languages (however, a programmer can give it an arbitrary name).
    64283The @this@ parameter must have a pointer type, whose base type is the type of object that the function constructs.
     
    65596
    65697In C, if the user creates an @Array@ object, the fields @data@ and @len@ are uninitialized, unless an explicit initializer list is present.
    657 It is the user's responsibility to remember to initialize both of the fields to sensible values.
     98It is the user's responsibility to remember to initialize both of the fields to sensible values, since there are no implicit checks for invalid values or reasonable defaults.
    65899In \CFA, the user can define a constructor to handle initialization of @Array@ objects.
    659100
     
    671112This constructor initializes @x@ so that its @length@ field has the value 10, and its @data@ field holds a pointer to a block of memory large enough to hold 10 @int@s, and sets the value of each element of the array to 0.
    672113This particular form of constructor is called the \emph{default constructor}, because it is called on an object defined without an initializer.
    673 In other words, a default constructor is a constructor that takes a single argument, the @this@ parameter.
    674 
    675 In \CFA, a destructor is a function much like a constructor, except that its name is \lstinline!^?{}!.
     114In other words, a default constructor is a constructor that takes a single argument: the @this@ parameter.
     115
     116In \CFA, a destructor is a function much like a constructor, except that its name is \lstinline!^?{}! and it take only one argument.
    676117A destructor for the @Array@ type can be defined as such.
    677118\begin{cfacode}
     
    680121}
    681122\end{cfacode}
    682 Since the destructor is automatically called at deallocation for all objects of type @Array@, the memory associated with an @Array@ is automatically freed when the object's lifetime ends.
     123The destructor is automatically called at deallocation for all objects of type @Array@.
     124Hence, the memory associated with an @Array@ is automatically freed when the object's lifetime ends.
    683125The exact guarantees made by \CFA with respect to the calling of destructors are discussed in section \ref{sub:implicit_dtor}.
    684126
     
    691133\end{cfacode}
    692134By the previous definition of the default constructor for @Array@, @x@ and @y@ are initialized to valid arrays of length 10 after their respective definitions.
    693 On line 3, @z@ is initialized with the value of @x@, while on line @4@, @y@ is assigned the value of @x@.
     135On line 2, @z@ is initialized with the value of @x@, while on line 3, @y@ is assigned the value of @x@.
    694136The key distinction between initialization and assignment is that a value to be initialized does not hold any meaningful values, whereas an object to be assigned might.
    695137In particular, these cases cannot be handled the same way because in the former case @z@ does not currently own an array, while @y@ does.
     
    712154The first function is called a \emph{copy constructor}, because it constructs its argument by copying the values from another object of the same type.
    713155The second function is the standard copy-assignment operator.
    714 These four functions are special in that they control the state of most objects.
     156The four functions (default constructor, destructor, copy constructor, and assignment operator) are special in that they safely control the state of most objects.
    715157
    716158It is possible to define a constructor that takes any combination of parameters to provide additional initialization options.
    717 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.
    718160\begin{cfacode}
    719161void ?{}(Array * arr, int capacity, int fill) {
     
    729171Array x, y = { 20, 0xdeadbeef }, z = y;
    730172\end{cfacode}
     173
    731174In \CFA, constructor calls look just like C initializers, which allows them to be inserted into legacy C code with minimal code changes, and also provides a very simple syntax that veteran C programmers are familiar with.
    732175One downside of reusing C initialization syntax is that it isn't possible to determine whether an object is constructed just by looking at its declaration, since that requires knowledge of whether the type is managed at that point.
     
    748191Destructors are implicitly called in reverse declaration-order so that objects with dependencies are destructed before the objects they are dependent on.
    749192
    750 \subsection{Syntax}
    751 \label{sub:syntax} % TODO: finish this section
     193\subsection{Calling Syntax}
     194\label{sub:syntax}
    752195There are several ways to construct an object in \CFA.
    753196As previously introduced, every variable is automatically constructed at its definition, which is the most natural way to construct an object.
     
    773216A * y = malloc();  // copy construct: ?{}(&y, malloc())
    774217
    775 ?{}(&x);    // explicit construct x
    776 ?{}(y, x);  // explit construct y from x
    777 ^?{}(&x);   // explicit destroy x
     218?{}(&x);    // explicit construct x, second construction
     219?{}(y, x);  // explit construct y from x, second construction
     220^?{}(&x);   // explicit destroy x, in different order
    778221^?{}(y);    // explicit destroy y
    779222
     
    781224// implicit ^?{}(&x);
    782225\end{cfacode}
    783 Calling a constructor or destructor directly is a flexible feature that allows complete control over the management of a piece of storage.
     226Calling a constructor or destructor directly is a flexible feature that allows complete control over the management of storage.
    784227In particular, constructors double as a placement syntax.
    785228\begin{cfacode}
     
    804247Finally, constructors and destructors support \emph{operator syntax}.
    805248Like other operators in \CFA, the function name mirrors the use-case, in that the first $N$ arguments fill in the place of the question mark.
     249This syntactic form is similar to the new initialization syntax in \CCeleven, except that it is used in expression contexts, rather than declaration contexts.
    806250\begin{cfacode}
    807251struct A { ... };
     
    822266Destructor operator syntax is actually an statement, and requires parentheses for symmetry with constructor syntax.
    823267
     268One of these three syntactic forms should appeal to either C or \CC programmers using \CFA.
     269
     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
    824303\subsection{Function Generation}
    825 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.
    826305Having 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.
    827306In addition to simplifying the definition of the language, it also simplifies the analysis that the translator must perform.
     
    833312There are several options for user-defined types: structures, unions, and enumerations.
    834313To aid in ease of use, the standard set of four functions is automatically generated for a user-defined type after its definition is completed.
    835 By auto-generating these functions, it is ensured that legacy C code will continue to work correctly in every context where \CFA expects these functions to exist, since they are generated for every complete type.
     314By auto-generating these functions, it is ensured that legacy C code continues to work correctly in every context where \CFA expects these functions to exist, since they are generated for every complete type.
    836315
    837316The generated functions for enumerations are the simplest.
    838 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.
    839 % TODO: examples for enums
     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.
    840318For example, given the enumeration
    841319\begin{cfacode}
     
    850328}
    851329void ?{}(enum Colour *_dst, enum Colour _src){
    852   (*_dst)=_src;  // bitwise copy
     330  *_dst=_src;  // bitwise copy
    853331}
    854332void ^?{}(enum Colour *_dst){
     
    856334}
    857335enum Colour ?=?(enum Colour *_dst, enum Colour _src){
    858   return (*_dst)=_src; // bitwise copy
     336  return *_dst=_src; // bitwise copy
    859337}
    860338\end{cfacode}
    861339In the future, \CFA will introduce strongly-typed enumerations, like those in \CC.
    862 The existing generated routines will be sufficient to express this restriction, since they are currently set up to take in values of that enumeration type.
     340The existing generated routines are sufficient to express this restriction, since they are currently set up to take in values of that enumeration type.
    863341Changes related to this feature only need to affect the expression resolution phase, where more strict rules will be applied to prevent implicit conversions from integral types to enumeration types, but should continue to permit conversions from enumeration types to @int@.
    864 In this way, it will still be possible to add an @int@ to an enumeration, but the resulting value will be an @int@, meaning that it won't be possible to reassign the value into an enumeration without a cast.
     342In this way, it is still possible to add an @int@ to an enumeration, but the resulting value is an @int@, meaning it cannot be reassigned to an enumeration without a cast.
    865343
    866344For structures, the situation is more complicated.
    867 For a structure @S@ with members @M$_0$@, @M$_1$@, ... @M$_{N-1}$@, each function @f@ in the standard set calls \lstinline{f(s->M$_i$, ...)} for each @$i$@.
    868 That is, a default constructor for @S@ default constructs the members of @S@, the copy constructor with copy construct them, and so on.
    869 For example given the struct definition
     345Given a structure @S@ with members @M$_0$@, @M$_1$@, ... @M$_{N-1}$@, each function @f@ in the standard set calls \lstinline{f(s->M$_i$, ...)} for each @$i$@.
     346That is, a default constructor for @S@ default constructs the members of @S@, the copy constructor copy constructs them, and so on.
     347For example, given the structure definition
    870348\begin{cfacode}
    871349struct A {
     
    893371}
    894372\end{cfacode}
    895 It is important to note that the destructors are called in reverse declaration order to resolve conflicts in the event there are dependencies among members.
     373It is important to note that the destructors are called in reverse declaration order to prevent conflicts in the event there are dependencies among members.
    896374
    897375In addition to the standard set, a set of \emph{field constructors} is also generated for structures.
    898 The field constructors are constructors that consume a prefix of the struct's member list.
     376The field constructors are constructors that consume a prefix of the structure's member-list.
    899377That is, $N$ constructors are built of the form @void ?{}(S *, T$_{\text{M}_0}$)@, @void ?{}(S *, T$_{\text{M}_0}$, T$_{\text{M}_1}$)@, ..., @void ?{}(S *, T$_{\text{M}_0}$, T$_{\text{M}_1}$, ..., T$_{\text{M}_{N-1}}$)@, where members are copy constructed if they have a corresponding positional argument and are default constructed otherwise.
    900 The addition of field constructors allows structs in \CFA to be used naturally in the same ways that they could be used in C (i.e. to initialize any prefix of the struct), e.g., @A a0 = { b }, a1 = { b, c }@.
     378The addition of field constructors allows structures in \CFA to be used naturally in the same ways as used in C (i.e., to initialize any prefix of the structure), e.g., @A a0 = { b }, a1 = { b, c }@.
    901379Extending the previous example, the following constructors are implicitly generated for @A@.
    902380\begin{cfacode}
     
    911389\end{cfacode}
    912390
    913 For unions, the default constructor and destructor do nothing, as it is not obvious which member if any should be constructed.
     391For unions, the default constructor and destructor do nothing, as it is not obvious which member, if any, should be constructed.
    914392For copy constructor and assignment operations, a bitwise @memcpy@ is applied.
    915393In 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.
    916 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.
    917395This approach ultimately feels subtle and unsafe.
    918396Another option is to, like \CC, disallow unions from containing members that are themselves managed types.
     
    947425
    948426% This feature works in the \CFA model, since constructors are simply special functions and can be called explicitly, unlike in \CC. % this sentence isn't really true => placement new
    949 In \CCeleven, this restriction has been loosened to allow unions with managed members, with the caveat that any if there are any members with a user-defined operation, then that operation is not implicitly defined, forcing the user to define the operation if necessary.
     427In \CCeleven, unions may have managed members, with the caveat that if there are any members with a user-defined operation, then that operation is not implicitly defined, forcing the user to define the operation if necessary.
    950428This restriction could easily be added into \CFA once \emph{deleted} functions are added.
    951429
     
    970448Here, @&s@ and @&s2@ are cast to unqualified pointer types.
    971449This mechanism allows the same constructors and destructors to be used for qualified objects as for unqualified objects.
    972 Since this applies only to implicitly generated constructor calls, the language does not allow qualified objects to be re-initialized with a constructor without an explicit cast.
     450This applies only to implicitly generated constructor calls.
     451Hence, explicitly re-initializing qualified objects with a constructor requires an explicit cast.
     452
     453As discussed in Section \ref{sub:c_background}, compound literals create unnamed objects.
     454This mechanism can continue to be used seamlessly in \CFA with managed types to create temporary objects.
     455The object created by a compound literal is constructed using the provided brace-enclosed initializer-list, and is destructed at the end of the scope it is used in.
     456For example,
     457\begin{cfacode}
     458struct A { int x; };
     459void ?{}(A *, int, int);
     460{
     461  int x = (A){ 10, 20 }.x;
     462}
     463\end{cfacode}
     464is equivalent to
     465\begin{cfacode}
     466struct A { int x, y; };
     467void ?{}(A *, int, int);
     468{
     469  A _tmp;
     470  ?{}(&_tmp, 10, 20);
     471  int x = _tmp.x;
     472  ^?{}(&tmp);
     473}
     474\end{cfacode}
    973475
    974476Unlike \CC, \CFA provides an escape hatch that allows a user to decide at an object's definition whether it should be managed or not.
     
    984486A a2 @= { 0 };  // unmanaged
    985487\end{cfacode}
    986 In this example, @a1@ is a managed object, and thus is default constructed and destructed at the end of @a1@'s lifetime, while @a2@ is an unmanaged object and is not implicitly constructed or destructed.
    987 Instead, @a2->x@ is initialized to @0@ as if it were a C object, due to the explicit initializer.
    988 Existing constructors are ignored when \ateq is used, so that any valid C initializer is able to initialize the object.
    989 
    990 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.
     488In this example, @a1@ is a managed object, and thus is default constructed and destructed at the start/end of @a1@'s lifetime, while @a2@ is an unmanaged object and is not implicitly constructed or destructed.
     489Instead, @a2->x@ is initialized to @0@ as if it were a C object, because of the explicit initializer.
     490
     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.
    991492It 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.
    992493It is recommended that most objects be managed by sensible constructors and destructors, except where absolutely necessary.
    993494
    994 When the user declares any constructor or destructor, the corresponding intrinsic/generated function and all field constructors for that type are hidden, so that they will not be found during expression resolution unless the user-defined function goes out of scope.
    995 Furthermore, if the user declares any constructor, then the intrinsic/generated default constructor is also hidden, making it so that objects of a type may not be default constructable.
    996 This closely mirrors the rule for implicit declaration of constructors in \CC, wherein the default constructor is implicitly declared if there is no user-declared constructor. % TODO: cite C++98 page 186??
     495When a user declares any constructor or destructor, the corresponding intrinsic/generated function and all field constructors for that type are hidden, so that they are not found during expression resolution until the user-defined function goes out of scope.
     496Furthermore, if the user declares any constructor, then the intrinsic/generated default constructor is also hidden, precluding default construction.
     497These semantics closely mirror the rule for implicit declaration of constructors in \CC, wherein the default constructor is implicitly declared if there is no user-declared constructor \cite[p.~186]{ANSI98:C++}.
    997498\begin{cfacode}
    998499struct S { int x, y; };
     
    1001502  S s0, s1 = { 0 }, s2 = { 0, 2 }, s3 = s2;  // okay
    1002503  {
    1003     void ?{}(S * s, int i) { s->x = i*2; }
     504    void ?{}(S * s, int i) { s->x = i*2; } // locally hide autogen constructors
    1004505    S s4;  // error
    1005506    S s5 = { 3 };  // okay
     
    1014515When defining a constructor or destructor for a struct @S@, any members that are not explicitly constructed or destructed are implicitly constructed or destructed automatically.
    1015516If an explicit call is present, then that call is taken in preference to any implicitly generated call.
    1016 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.
    1017518\begin{cfacode}
    1018519struct A {
     
    1033534}
    1034535\end{cfacode}
    1035 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.
    1036537If the translator cannot be reasonably sure that an object is constructed prior to its first use, but is constructed afterward, an error is emitted.
    1037 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.
    1038539\begin{cfacode}
    1039540void ?{}(A * a, double x) {
     
    1042543}
    1043544\end{cfacode}
    1044 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).
    1045546\begin{cfacode}
    1046547void ?{}(A * a) {
     
    1058559} // z, y, w implicitly destructed, in this order
    1059560\end{cfacode}
    1060 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: confirm that this is correct. It might be possible to get subtle errors if you initialize some members then call another constructor... -- in fact, 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).
     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.
    1061562To override this rule, \ateq can be used to force the translator to trust the programmer's discretion.
    1062563This form of \ateq is not yet implemented.
     
    1064565Despite great effort, some forms of C syntax do not work well with constructors in \CFA.
    1065566In particular, constructor calls cannot contain designations (see \ref{sub:c_background}), since this is equivalent to allowing designations on the arguments to arbitrary function calls.
    1066 In C, function prototypes are permitted to have arbitrary parameter names, including no names at all, which may have no connection to the actual names used at function definition.
    1067 Furthermore, a function prototype can be repeated an arbitrary number of times, each time using different names.
    1068567\begin{cfacode}
    1069568// all legal forward declarations in C
     
    1076575f(b:10, a:20, c:30);  // which parameter is which?
    1077576\end{cfacode}
     577In C, function prototypes are permitted to have arbitrary parameter names, including no names at all, which may have no connection to the actual names used at function definition.
     578Furthermore, a function prototype can be repeated an arbitrary number of times, each time using different names.
    1078579As a result, it was decided that any attempt to resolve designated function calls with C's function prototype rules would be brittle, and thus it is not sensible to allow designations in constructor calls.
    1079 % Many other languages do allow named arguments, such as Python and Scala, but they do not allow multiple arbitrarily named forward declarations of a function.
    1080 
    1081 In addition, constructor calls cannot have a nesting depth greater than the number of array components in the type of the initialized object, plus one.
     580
     581In addition, constructor calls do not support unnamed nesting.
     582\begin{cfacode}
     583struct B { int x; };
     584struct C { int y; };
     585struct A { B b; C c; };
     586void ?{}(A *, B);
     587void ?{}(A *, C);
     588
     589A a = {
     590  { 10 },  // construct B? - invalid
     591};
     592\end{cfacode}
     593In C, nesting initializers means that the programmer intends to initialize sub-objects with the nested initializers.
     594The reason for this omission is to both simplify the mental model for using constructors, and to make initialization simpler for the expression resolver.
     595If 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.
     596That is, in the previous example the line marked as an error could mean construct using @?{}(A *, B)@ or with @?{}(A *, C)@, since the inner initializer @{ 10 }@ could be taken as an intermediate object of type @B@ or @C@.
     597In practice, however, there could be many objects that can be constructed from a given @int@ (or, indeed, any arbitrary parameter list), and thus a complete solution to this problem would require fully exploring all possibilities.
     598
     599More precisely, constructor calls cannot have a nesting depth greater than the number of array components in the type of the initialized object, plus one.
    1082600For example,
    1083601\begin{cfacode}
     
    1096614}
    1097615\end{cfacode}
    1098 % TODO: in CFA if the array dimension is empty, no object constructors are added -- need to fix this.
    1099616The body of @A@ has been omitted, since only the constructor interfaces are important.
    1100 In C, having a greater nesting depth means that the programmer intends to initialize subobjects with the nested initializer.
    1101 The reason for this omission is to both simplify the mental model for using constructors, and to make initialization simpler for the expression resolver.
    1102 If 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.
    1103 That is, in the previous example the line marked as an error could mean construct using @?{}(A *, A, A)@, since the inner initializer @{ 11 }@ could be taken as an intermediate object of type @A@ constructed with @?{}(A *, int)@.
    1104 In practice, however, there could be many objects that can be constructed from a given @int@ (or, indeed, any arbitrary parameter list), and thus a complete solution to this problem would require fully exploring all possibilities.
     617
    1105618It should be noted that unmanaged objects can still make use of designations and nested initializers in \CFA.
     619It is simple to overcome this limitation for managed objects by making use of compound literals, so that the arguments to the constructor call are explicitly typed.
    1106620
    1107621\subsection{Implicit Destructors}
     
    1127641    if (i == 2) return; // destruct x, y
    1128642  } // destruct y
    1129 }
    1130 \end{cfacode}
    1131 
    1132 %% having this feels excessive, but it's here if necessary
    1133 % This procedure generates the following code.
    1134 % \begin{cfacode}
    1135 % void f(int i){
    1136 %   struct A x;
    1137 %   ?{}(&x);
    1138 %   {
    1139 %     struct A y;
    1140 %     ?{}(&y);
    1141 %     {
    1142 %       struct A z;
    1143 %       ?{}(&z);
    1144 %       {
    1145 %         if ((i==0)!=0) {
    1146 %           ^?{}(&z);
    1147 %           ^?{}(&y);
    1148 %           ^?{}(&x);
    1149 %           return;
    1150 %         }
    1151 %       }
    1152 %       if (((i==1)!=0) {
    1153 %           ^?{}(&z);
    1154 %           ^?{}(&y);
    1155 %           ^?{}(&x);
    1156 %           return ;
    1157 %       }
    1158 %       ^?{}(&z);
    1159 %     }
    1160 
    1161 %     if ((i==2)!=0) {
    1162 %       ^?{}(&y);
    1163 %       ^?{}(&x);
    1164 %       return;
    1165 %     }
    1166 %     ^?{}(&y);
    1167 %   }
    1168 
    1169 %   ^?{}(&x);
    1170 % }
    1171 % \end{cfacode}
     643} // destruct x
     644\end{cfacode}
    1172645
    1173646The next example illustrates the use of simple continue and break statements and the manner that they interact with implicit destructors.
     
    1183656\end{cfacode}
    1184657Since 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.
    1185 In the case where @i@ is @2@, the continue statement runs the loop update expression and attemps to begin the next iteration of the loop.
    1186 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.
     658In the case where @i@ is @2@, the continue statement runs the loop update expression and attempts to begin the next iteration of the loop.
     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.
    1187660When @i@ is @3@, the break statement moves control to just past the end of the loop.
    1188 Like the previous case, a destructor call for @x@ is inserted just before the break statement.
    1189 
    1190 \CFA also supports labelled break and continue statements, which allow more precise manipulation of control flow.
    1191 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.
    1192665\begin{cfacode}[emph={L1,L2}, emphstyle=\color{red}]
    1193666L1: for (int i = 0; i < 10; i++) {
    1194667  A x;
    1195   L2: for (int j = 0; j < 10; j++) {
     668  for (int j = 0; j < 10; j++) {
    1196669    A y;
    1197     if (j == 0) {
    1198       continue;    // destruct y
    1199     } else if (j == 1) {
    1200       break;       // destruct y
    1201     } else if (i == 1) {
     670    if (i == 1) {
    1202671      continue L1; // destruct y
    1203672    } else if (i == 2) {
     
    1208677\end{cfacode}
    1209678The statement @continue L1@ begins the next iteration of the outer for-loop.
    1210 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@.
    1211 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.
    1212681
    1213682Finally, an example which demonstrates goto.
     
    1256725}
    1257726\end{cfacode}
    1258 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.
    1259728
    1260729The next example demonstrates the error case.
     
    1273742
    1274743\subsection{Implicit Copy Construction}
     744\label{s:implicit_copy_construction}
    1275745When 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.
    1276746When a value is returned from a function, the copy constructor is called to pass the value back to the call site.
    1277 Exempt from these rules are intrinsic and builtin functions.
     747Exempt from these rules are intrinsic and built-in functions.
    1278748It 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.
     749That 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.
    1279750This is an important detail to bear in mind when using unmanaged objects, and could produce unexpected results when mixed with objects that are explicitly constructed.
    1280751\begin{cfacode}
     
    1284755void ^?{}(A *);
    1285756
    1286 A f(A x) {
    1287   return x;
     757A identity(A x) { // pass by value => need local copy
     758  return x;       // return by value => make call-site copy
    1288759}
    1289760
    1290761A y, z @= {};
    1291 identity(y);
    1292 identity(z);
     762identity(y);  // copy construct y into x
     763identity(z);  // copy construct z into x
    1293764\end{cfacode}
    1294765Note that @z@ is copy constructed into a temporary variable to be passed as an argument, which is also destructed after the call.
    1295 A special syntactic form, such as a variant of \ateq, could be implemented to specify at the call site that an argument should not be copy constructed, to regain some control for the C programmer.
    1296766
    1297767This generates the following
    1298768\begin{cfacode}
    1299769struct A f(struct A x){
    1300   struct A _retval_f;
    1301   ?{}((&_retval_f), x);
     770  struct A _retval_f;    // return value
     771  ?{}((&_retval_f), x);  // copy construct return value
    1302772  return _retval_f;
    1303773}
    1304774
    1305775struct A y;
    1306 ?{}(&y);
    1307 struct A z = { 0 };
    1308 
    1309 struct A _tmp_cp1;     // argument 1
    1310 struct A _tmp_cp_ret0; // return value
    1311 _tmp_cp_ret0=f((?{}(&_tmp_cp1, y) , _tmp_cp1)), _tmp_cp_ret0;
    1312 ^?{}(&_tmp_cp_ret0);   // return value
    1313 ^?{}(&_tmp_cp1);       // argument 1
    1314 
    1315 struct A _tmp_cp2;     // argument 1
    1316 struct A _tmp_cp_ret1; // return value
    1317 _tmp_cp_ret1=f((?{}(&_tmp_cp2, z), _tmp_cp2)), _tmp_cp_ret1;
    1318 ^?{}(&_tmp_cp_ret1);   // return value
    1319 ^?{}(&_tmp_cp2);       // argument 1
     776?{}(&y);                 // default construct
     777struct A z = { 0 };      // C default
     778
     779struct A _tmp_cp1;       // argument 1
     780struct A _tmp_cp_ret0;   // return value
     781_tmp_cp_ret0=f(
     782  (?{}(&_tmp_cp1, y) , _tmp_cp1)  // argument is a comma expression
     783), _tmp_cp_ret0;         // return value for cascading
     784^?{}(&_tmp_cp_ret0);     // destruct return value
     785^?{}(&_tmp_cp1);         // destruct argument 1
     786
     787struct A _tmp_cp2;       // argument 1
     788struct A _tmp_cp_ret1;   // return value
     789_tmp_cp_ret1=f(
     790  (?{}(&_tmp_cp2, z), _tmp_cp2)  // argument is a common expression
     791), _tmp_cp_ret1;         // return value for cascading
     792^?{}(&_tmp_cp_ret1);     // destruct return value
     793^?{}(&_tmp_cp2);         // destruct argument 1
    1320794^?{}(&y);
    1321795\end{cfacode}
    1322796
    1323 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.
    1324 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.
     797A special syntactic form, such as a variant of \ateq, can be implemented to specify at the call site that an argument should not be copy constructed, to regain some control for the C programmer.
     798\begin{cfacode}
     799identity(z@);  // do not copy construct argument
     800               // - will copy construct/destruct return value
     801A@ identity_nocopy(A @ x) {  // argument not copy constructed or destructed
     802  return x;  // not copy constructed
     803             // return type marked @ => not destructed
     804}
     805\end{cfacode}
     806It 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.
     807
     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.
    1325810This approach works out most of the time, because typically destructors need to only access the fields of the object and recursively destroy.
    1326 It is currently the case that constructors and destructors which use the @this@ pointer as a unique identifier to store data externally will not work correctly for return value objects.
    1327 Thus is it not safe to rely on an object's @this@ pointer to remain constant throughout execution of the program.
     811It 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.
     812Thus, it is currently not safe to rely on an object's @this@ pointer to remain constant throughout execution of the program.
    1328813\begin{cfacode}
    1329814A * external_data[32];
     
    1341826  }
    1342827}
     828
     829A makeA() {
     830  A x;  // stores &x in external_data
     831  return x;
     832}
     833makeA();  // return temporary has a different address than x
     834// equivalent to:
     835//   A _tmp;
     836//   _tmp = makeA(), _tmp;
     837//   ^?{}(&_tmp);
    1343838\end{cfacode}
    1344839In the above example, a global array of pointers is used to keep track of all of the allocated @A@ objects.
    1345 Due to copying on return, the current object being destructed will not exist in the array if an @A@ object is ever returned by value from a function.
    1346 
    1347 This problem could be solved in the translator by mutating the function signatures so that the return value is moved into the parameter list.
     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@.
     841
     842This problem could be solved in the translator by changing the function signatures so that the return value is moved into the parameter list.
    1348843For example, the translator could restructure the code like so
    1349844\begin{cfacode}
     
    1363858\end{cfacode}
    1364859This transformation provides @f@ with the address of the return variable so that it can be constructed into directly.
    1365 It is worth pointing out that this kind of signature rewriting already occurs in polymorphic functions which return by value, as discussed in \cite{Bilson03}.
     860It is worth pointing out that this kind of signature rewriting already occurs in polymorphic functions that return by value, as discussed in \cite{Bilson03}.
    1366861A key difference in this case is that every function would need to be rewritten like this, since types can switch between managed and unmanaged at different scope levels, e.g.
    1367862\begin{cfacode}
    1368863struct A { int v; };
    1369 A x; // unmanaged
     864A x; // unmanaged, since only trivial constructors are available
    1370865{
    1371866  void ?{}(A * a) { ... }
     
    1375870A z; // unmanaged
    1376871\end{cfacode}
    1377 Hence there is not enough information to determine at function declaration to determine whether a type is managed or not, and thus it is the case that all signatures have to be rewritten to account for possible copy constructor and destructor calls.
     872Hence there is not enough information to determine at function declaration whether a type is managed or not, and thus it is the case that all signatures have to be rewritten to account for possible copy constructor and destructor calls.
    1378873Even with this change, it would still be possible to declare backwards compatible function prototypes with an @extern "C"@ block, which allows for the definition of C-compatible functions within \CFA code, however this would require actual changes to the way code inside of an @extern "C"@ function is generated as compared with normal code generation.
    1379 Furthermore, it isn't possible to overload C functions, so using @extern "C"@ to declare functions is of limited use.
    1380 
    1381 It would be possible to regain some control by adding an attribute to structs which specifies whether they can be managed or not (perhaps \emph{manageable} or \emph{unmanageable}), and to emit an error in the case that a constructor or destructor is declared for an unmanageable type.
     874Furthermore, it is not possible to overload C functions, so using @extern "C"@ to declare functions is of limited use.
     875
     876It would be possible to regain some control by adding an attribute to structs that specifies whether they can be managed or not (perhaps \emph{manageable} or \emph{unmanageable}), and to emit an error in the case that a constructor or destructor is declared for an unmanageable type.
    1382877Ideally, structs should be manageable by default, since otherwise the default case becomes more verbose.
    1383878This means that in general, function signatures would have to be rewritten, and in a select few cases the signatures would not be rewritten.
     
    1392887\end{cfacode}
    1393888An alternative is to instead make the attribute \emph{identifiable}, which states that objects of this type use the @this@ parameter as an identity.
    1394 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.
    1395890Furthermore, no restrictions would need to be placed on whether objects can be constructed.
    1396891\begin{cfacode}
     
    1402897\end{cfacode}
    1403898
    1404 Ultimately, this is the type of transformation that a real compiler would make when generating assembly code.
    1405 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.
    1406 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.
    1407902
    1408903\section{Implementation}
    1409904\subsection{Array Initialization}
    1410 Arrays are a special case in the C type system.
     905Arrays are a special case in the C type-system.
    1411906C arrays do not carry around their size, making it impossible to write a standalone \CFA function that constructs or destructs an array while maintaining the standard interface for constructors and destructors.
    1412907Instead, \CFA defines the initialization and destruction of an array recursively.
     
    15251020By default, objects within a translation unit are constructed in declaration order, and destructed in the reverse order.
    15261021The default order of construction of objects amongst translation units is unspecified.
    1527 % TODO: not yet implemented, but g++ provides attribute init_priority, which allows specifying the order of global construction on a per object basis
    1528 %   https://gcc.gnu.org/onlinedocs/gcc/C_002b_002b-Attributes.html#C_002b_002b-Attributes
    1529 % 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
    15301022It is, however, guaranteed that any global objects in the standard library are initialized prior to the initialization of any object in the user program.
    15311023
    1532 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. % 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}.
    15331025A similar function is generated with the \emph{destructor} attribute, which handles all global destructor calls.
    15341026At 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.
    1535 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.
    15361028
    15371029For example, given the following global declarations.
     
    15591051\end{cfacode}
    15601052
     1053%   https://gcc.gnu.org/onlinedocs/gcc/C_002b_002b-Attributes.html#C_002b_002b-Attributes
     1054% 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
     1055GCC provides an attribute @init_priority@, which allows specifying the relative priority for initialization of global objects on a per-object basis in \CC.
     1056A similar attribute can be implemented in \CFA by pulling marked objects into global constructor/destructor-attribute functions with the specified priority.
     1057For example,
     1058\begin{cfacode}
     1059struct A { ... };
     1060void ?{}(A *, int);
     1061void ^?{}(A *);
     1062__attribute__((init_priority(200))) A x = { 123 };
     1063\end{cfacode}
     1064would generate
     1065\begin{cfacode}
     1066A x;
     1067__attribute__((constructor(200))) __init_x() {
     1068  ?{}(&x, 123);  // construct x with priority 200
     1069}
     1070__attribute__((destructor(200))) __destroy_x() {
     1071  ?{}(&x);       // destruct x with priority 200
     1072}
     1073\end{cfacode}
     1074
    15611075\subsection{Static Local Variables}
    15621076In standard C, it is possible to mark variables that are local to a function with the @static@ storage class.
    1563 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??
    1564 Much like global variables, in C @static@ variables must be initialized to a \emph{compile-time constant value} so that a compiler is able to create storage for the variable and initialize it before the program begins running.
     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.
     1078Much 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.
    15651079
    15661080Yet again, this rule is too restrictive for a language with constructors and destructors.
     
    15731087Construction of @static@ local objects is implemented via an accompanying @static bool@ variable, which records whether the variable has already been constructed.
    15741088A conditional branch checks the value of the companion @bool@, and if the variable has not yet been constructed then the object is constructed.
    1575 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 will 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.
    15761090Since the parameter to @atexit@ is a parameter-less function, some additional tweaking is required.
    15771091First, the @static@ variable must be hoisted up to global scope and uniquely renamed to prevent name clashes with other global objects.
     
    15791093Finally, the newly generated function is registered with @atexit@, instead of registering the destructor directly.
    15801094Since @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.
    1581 
    15821095Extending the previous example
    15831096\begin{cfacode}
     
    16301143\end{cfacode}
    16311144
    1632 \subsection{Constructor Expressions}
    1633 In \CFA, it is possible to use a constructor as an expression.
    1634 Like other operators, the function name @?{}@ matches its operator syntax.
    1635 For example, @(&x){}@ calls the default constructor on the variable @x@, and produces @&x@ as a result.
    1636 The significance of constructors as expressions rather than as statements is that the result of a constructor expression can be used as part of a larger expression.
    1637 A key example is the use of constructor expressions to initialize the result of a call to standard C routine @malloc@.
    1638 \begin{cfacode}
    1639 struct X { ... };
    1640 void ?{}(X *, double);
    1641 X * x = malloc(sizeof(X)){ 1.5 };
    1642 \end{cfacode}
    1643 In this example, @malloc@ dynamically allocates storage and initializes it using a constructor, all before assigning it into the variable @x@.
    1644 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.
    1645 \begin{cfacode}
    1646 X * x = malloc(sizeof(X));
    1647 x{ 1.5 };
    1648 \end{cfacode}
    1649 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.
    1650 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.
    1651 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.
    1652 The previous example generates the following code.
    1653 \begin{cfacode}
    1654 struct X *_tmp_ctor;
    1655 struct X *x = ?{}((_tmp_ctor=((_tmp_cp_ret0=
    1656   malloc(sizeof(struct X))), _tmp_cp_ret0))), 1.5), _tmp_ctor);
    1657 \end{cfacode}
    1658 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.
    1659 
    1660 It is also possible to use operator syntax with destructors.
    1661 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.
    1662 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

    ra0fc78a rf674479  
    55\section{\CFA Background}
    66\label{s:background}
    7 \CFA is a modern 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}.
     
    1616Therefore, these design principles must be kept in mind throughout the design and development of new language features.
    1717In order to appeal to existing C programmers, great care must be taken to ensure that new features naturally feel like C.
    18 The remainder of this section describes some of the important new features that currently exist in \CFA, to give the reader the necessary context in which the new features presented in this thesis must dovetail. % TODO: harmonize with?
     18The remainder of this section describes some of the important new features that currently exist in \CFA, to give the reader the necessary context in which the new features presented in this thesis must dovetail.
    1919
    2020\subsection{C Background}
     
    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.
    41 This can be seen in the initialization of @a0@, where @x@ is designated twice, and thus initialized to @8@.
    42 Note that in \CFA, designations use a colon separator, rather than an equals sign as in C.
     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.
     41These semantics can be seen in the initialization of @a0@, where @x@ is designated twice, and thus initialized to @8@.
     42Note 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.
    4343
    4444C also provides \emph{compound literal} expressions, which provide a first-class mechanism for creating unnamed objects.
     
    9191
    9292There are times when a function should logically return multiple values.
    93 Since a function in standard C can only return a single value, a programmer must either take in additional return values by address, or the function's designer must create a wrapper structure t0 package multiple return-values.
     93Since a function in standard C can only return a single value, a programmer must either take in additional return values by address, or the function's designer must create a wrapper structure to package multiple return-values.
    9494\begin{cfacode}
    9595int f(int * ret) {        // returns a value through parameter ret
     
    102102\end{cfacode}
    103103The former solution is awkward because it requires the caller to explicitly allocate memory for $n$ result variables, even if they are only temporary values used as a subexpression, or even not used at all.
     104The latter approach:
    104105\begin{cfacode}
    105106struct A {
     
    112113... res3.x ... res3.y ... // use result values
    113114\end{cfacode}
    114 The latter approach requires the caller to either learn the field names of the structure or learn the names of helper routines to access the individual return values.
     115requires the caller to either learn the field names of the structure or learn the names of helper routines to access the individual return values.
    115116Both solutions are syntactically unnatural.
    116117
    117 In \CFA, it is possible to directly declare a function returning mutliple values.
    118 This provides important semantic information to the caller, since return values are only for output.
    119 \begin{cfacode}
    120 [int, int] f() {       // don't need to create a new type
     118In \CFA, it is possible to directly declare a function returning multiple values.
     119This extension provides important semantic information to the caller, since return values are only for output.
     120\begin{cfacode}
     121[int, int] f() {       // no new type
    121122  return [123, 37];
    122123}
    123124\end{cfacode}
    124 However, the ability to return multiple values requires a syntax for accepting the results from a function.
     125However, the ability to return multiple values is useless without a syntax for accepting the results from the function.
     126
    125127In standard C, return values are most commonly assigned directly into local variables, or are used as the arguments to another function call.
    126128\CFA allows both of these contexts to accept multiple return values.
     
    148150  g(f());             // selects (2)
    149151  \end{cfacode}
    150 In this example, the only possible call to @f@ that can produce the two @int@s required by @g@ is the second option.
    151 A similar reasoning holds for assigning into multiple variables.
     152In this example, the only possible call to @f@ that can produce the two @int@s required for assigning into the variables @x@ and @y@ is the second option.
     153A similar reasoning holds calling the function @g@.
    152154
    153155In \CFA, overloading also applies to operator names, known as \emph{operator overloading}.
     
    166168  bool ?<?(A x, A y);
    167169  \end{cfacode}
    168 Notably, the only difference in this example is syntax.
     170Notably, the only difference is syntax.
    169171Most of the operators supported by \CC for operator overloading are also supported in \CFA.
    170172Of notable exception are the logical operators (e.g. @||@), the sequence operator (i.e. @,@), and the member-access operators (e.g. @.@ and \lstinline{->}).
     
    172174Finally, \CFA also permits overloading variable identifiers.
    173175This feature is not available in \CC.
    174   \begin{cfacode} % TODO: pick something better than x? max, zero, one?
     176  \begin{cfacode}
    175177  struct Rational { int numer, denom; };
    176178  int x = 3;               // (1)
     
    186188In this example, there are three definitions of the variable @x@.
    187189Based on the context, \CFA attempts to choose the variable whose type best matches the expression context.
     190When used judiciously, this feature allows names like @MAX@, @MIN@, and @PI@ to apply across many types.
    188191
    189192Finally, the values @0@ and @1@ have special status in standard C.
     
    197200}
    198201\end{cfacode}
    199 Every if statement in C compares the condition with @0@, and every increment and decrement operator is semantically equivalent to adding or subtracting the value @1@ and storing the result.
     202Every if- and iteration-statement in C compares the condition with @0@, and every increment and decrement operator is semantically equivalent to adding or subtracting the value @1@ and storing the result.
    200203Due to these rewrite rules, the values @0@ and @1@ have the types \zero and \one in \CFA, which allow for overloading various operations that connect to @0@ and @1@ \footnote{In the original design of \CFA, @0@ and @1@ were overloadable names \cite[p.~7]{cforall}.}.
    201 The types \zero and \one have special built in implicit conversions to the various integral types, and a conversion to pointer types for @0@, which allows standard C code involving @0@ and @1@ to work as normal.
     204The types \zero and \one have special built-in implicit conversions to the various integral types, and a conversion to pointer types for @0@, which allows standard C code involving @0@ and @1@ to work as normal.
    202205  \begin{cfacode}
    203206  // lvalue is similar to returning a reference in C++
     
    293296This capability allows specifying the same set of assertions in multiple locations, without the repetition and likelihood of mistakes that come with manually writing them out for each function declaration.
    294297
     298An interesting application of return-type resolution and polymorphism is with type-safe @malloc@.
     299\begin{cfacode}
     300forall(dtype T | sized(T))
     301T * malloc() {
     302  return (T*)malloc(sizeof(T)); // call C malloc
     303}
     304int * x = malloc();     // malloc(sizeof(int))
     305double * y = malloc();  // malloc(sizeof(double))
     306
     307struct S { ... };
     308S * s = malloc();       // malloc(sizeof(S))
     309\end{cfacode}
     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.
     311In 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.
     312
    295313\section{Invariants}
    296 % TODO: discuss software engineering benefits of ctor/dtors: {pre/post} conditions, invariants
    297 % an important invariant is the state of the environment (memory, resources)
    298 % some objects pass their contract to the object user
    299 An \emph{invariant} is a logical assertion that true for some duration of a program's execution.
     314An \emph{invariant} is a logical assertion that is true for some duration of a program's execution.
    300315Invariants help a programmer to reason about code correctness and prove properties of programs.
    301316
    302317In object-oriented programming languages, type invariants are typically established in a constructor and maintained throughout the object's lifetime.
    303 This is typically achieved through a combination of access control modifiers and a restricted interface.
     318These assertions are typically achieved through a combination of access control modifiers and a restricted interface.
    304319Typically, data which requires the maintenance of an invariant is hidden from external sources using the \emph{private} modifier, which restricts reads and writes to a select set of trusted routines, including member functions.
    305320It is these trusted routines that perform all modifications to internal data in a way that is consistent with the invariant, by ensuring that the invariant holds true at the end of the routine call.
     
    307322In C, the @assert@ macro is often used to ensure invariants are true.
    308323Using @assert@, the programmer can check a condition and abort execution if the condition is not true.
    309 This is a powerful tool that forces the programmer to deal with logical inconsistencies as they occur.
     324This powerful tool forces the programmer to deal with logical inconsistencies as they occur.
    310325For production, assertions can be removed by simply defining the preprocessor macro @NDEBUG@, making it simple to ensure that assertions are 0-cost for a performance intensive application.
    311326\begin{cfacode}
     
    354369\end{dcode}
    355370The D compiler is able to assume that assertions and invariants hold true and perform optimizations based on those assumptions.
    356 
    357 An important invariant is the state of the execution environment, including the heap, the open file table, the state of global variables, etc.
    358 Since resources are finite, it is important to ensure that objects clean up properly when they are finished, restoring the execution environment to a stable state so that new objects can reuse resources.
     371Note, these invariants are internal to the type's correct behaviour.
     372
     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.
     374Since 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.
    359375
    360376\section{Resource Management}
     
    366382The program stack grows and shrinks automatically with each function call, as needed for local variables.
    367383However, 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@.
    368 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.
    369 Once allocated storage escapes a block, the responsibility for deallocating the storage is not specified in a function's type, that is, that the return value is owned by the caller.
     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.
     385Once 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.
    370386This implicit convention is provided only through documentation about the expectations of functions.
    371387
    372388In other languages, a hybrid situation exists where resources escape the allocation block, but ownership is precisely controlled by the language.
    373 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.
    374 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.
    375391
    376392For 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.
     
    380396On the other hand, destructors provide a simple mechanism for tearing down an object and resetting the environment in which the object lived.
    381397RAII ensures that if all resources are acquired in a constructor and released in a destructor, there are no resource leaks, even in exceptional circumstances.
    382 A type with at least one non-trivial constructor or destructor will henceforth be referred to as a \emph{managed type}.
    383 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.
    384 
    385 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.
     398A type with at least one non-trivial constructor or destructor is henceforth referred to as a \emph{managed type}.
     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.
    386402
    387403In garbage collected languages, such as Java, resources are largely managed by the garbage collector.
     
    389405There are many kinds of resources that the garbage collector does not understand, such as sockets, open files, and database connections.
    390406In particular, Java supports \emph{finalizers}, which are similar to destructors.
    391 Sadly, finalizers come with far fewer guarantees, to the point where a completely conforming JVM may never call a single finalizer. % TODO: citation JVM spec; http://stackoverflow.com/a/2506514/2386739
    392 Due to operating system resource limits, this is unacceptable for many long running tasks. % TODO: citation?
    393 Instead, the paradigm in Java requires programmers manually keep track of all resource \emph{except} memory, leading many novices and experts alike to forget to close files, etc.
    394 Complicating the picture, uncaught exceptions can cause control flow to change dramatically, leaking a resource which appears on first glance to be closed.
     407Sadly, 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.
     408Due to operating-system resource-limits, this is unacceptable for many long running programs.
     409Instead, 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.
     410Complicating the picture, uncaught exceptions can cause control flow to change dramatically, leaking a resource that appears on first glance to be released.
    395411\begin{javacode}
    396412void write(String filename, String msg) throws Exception {
     
    403419}
    404420\end{javacode}
    405 Any line in this program can throw an exception.
    406 This leads to a profusion of finally blocks around many function bodies, since it isn't always clear when an exception may be thrown.
     421Any line in this program can throw an exception, which leads to a profusion of finally blocks around many function bodies, since it is not always clear when an exception may be thrown.
    407422\begin{javacode}
    408423public void write(String filename, String msg) throws Exception {
     
    422437\end{javacode}
    423438In Java 7, a new \emph{try-with-resources} construct was added to alleviate most of the pain of working with resources, but ultimately it still places the burden squarely on the user rather than on the library designer.
    424 Furthermore, for complete safety this pattern requires nested objects to be declared separately, otherwise resources which can throw an exception on close can leak nested resources. % TODO: cite oracle article http://www.oracle.com/technetwork/articles/java/trywithresources-401775.html?
     439Furthermore, for complete safety this pattern requires nested objects to be declared separately, otherwise resources that can throw an exception on close can leak nested resources \cite{TryWithResources}.
    425440\begin{javacode}
    426441public void write(String filename, String msg) throws Exception {
    427   try (
     442  try (  // try-with-resources
    428443    FileOutputStream out = new FileOutputStream(filename);
    429444    FileOutputStream log = new FileOutputStream("log.txt");
     
    434449}
    435450\end{javacode}
    436 On the other hand, the Java compiler generates more code if more resources are declared, meaning that users must be more familiar with each type and library designers must provide better documentation.
     451Variables declared as part of a try-with-resources statement must conform to the @AutoClosable@ interface, and the compiler implicitly calls @close@ on each of the variables at the end of the block.
     452Depending 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.
     453
     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}
    437505
    438506% D has constructors and destructors that are worth a mention (under classes) https://dlang.org/spec/spec.html
     
    442510The programming language, D, also manages resources with constructors and destructors \cite{D}.
    443511In D, @struct@s are stack allocated and managed via scoping like in \CC, whereas @class@es are managed automatically by the garbage collector.
    444 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.
    445513Since D supports RAII, it is possible to use the same techniques as in \CC to ensure that resources are released in a timely manner.
    446 Finally, D provides a scope guard statement, which allows an arbitrary statement to be executed at normal scope exit with \emph{success}, at exceptional scope exit with \emph{failure}, or at normal and exceptional scope exit with \emph{exit}. % cite? https://dlang.org/spec/statement.html#ScopeGuardStatement
    447 It has been shown that the \emph{exit} form of the scope guard statement can be implemented in a library in \CC. % cite: http://www.drdobbs.com/184403758
    448 
    449 % TODO: discussion of lexical scope vs. dynamic
    450 % see Peter's suggestions
    451 % RAII works in both cases. Guaranteed to work in stack case, works in heap case if root is deleted (but it's dangerous to rely on this, because of exceptions)
     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
     515It has been shown that the \emph{exit} form of the scope guard statement can be implemented in a library in \CC \cite{ExceptSafe}.
     516
     517To provide managed types in \CFA, new kinds of constructors and destructors are added to \CFA and discussed in Chapter 2.
    452518
    453519\section{Tuples}
    454520\label{s:Tuples}
    455 In mathematics, tuples are finite-length sequences which, unlike sets, allow duplicate elements.
    456 In programming languages, tuples are a construct that provide fixed-sized heterogeneous lists of elements.
     521In mathematics, tuples are finite-length sequences which, unlike sets, are ordered and allow duplicate elements.
     522In programming languages, tuples provide fixed-sized heterogeneous lists of elements.
    457523Many programming languages have tuple constructs, such as SETL, \KWC, ML, and Scala.
    458524
     
    462528Adding tuples to \CFA has previously been explored by Esteves \cite{Esteves04}.
    463529
    464 The design of tuples in \KWC took much of its inspiration from SETL.
     530The design of tuples in \KWC took much of its inspiration from SETL \cite{SETL}.
    465531SETL is a high-level mathematical programming language, with tuples being one of the primary data types.
    466532Tuples in SETL allow a number of operations, including subscripting, dynamic expansion, and multiple assignment.
     
    470536\begin{cppcode}
    471537tuple<int, int, int> triple(10, 20, 30);
    472 get<1>(triple); // access component 1 => 30
     538get<1>(triple); // access component 1 => 20
    473539
    474540tuple<int, double> f();
     
    482548Tuples are simple data structures with few specific operations.
    483549In particular, it is possible to access a component of a tuple using @std::get<N>@.
    484 Another interesting feature is @std::tie@, which creates a tuple of references, which allows assigning the results of a tuple-returning function into separate local variables, without requiring a temporary variable.
     550Another interesting feature is @std::tie@, which creates a tuple of references, allowing assignment of the results of a tuple-returning function into separate local variables, without requiring a temporary variable.
    485551Tuples also support lexicographic comparisons, making it simple to write aggregate comparators using @std::tie@.
    486552
    487 There is a proposal for \CCseventeen called \emph{structured bindings}, that introduces new syntax to eliminate the need to pre-declare variables and use @std::tie@ for binding the results from a function call. % TODO: cite http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0144r0.pdf
     553There is a proposal for \CCseventeen called \emph{structured bindings} \cite{StructuredBindings}, that introduces new syntax to eliminate the need to pre-declare variables and use @std::tie@ for binding the results from a function call.
    488554\begin{cppcode}
    489555tuple<int, double> f();
     
    500566Structured bindings allow unpacking any struct with all public non-static data members into fresh local variables.
    501567The use of @&@ allows declaring new variables as references, which is something that cannot be done with @std::tie@, since \CC references do not support rebinding.
    502 This extension requires the use of @auto@ to infer the types of the new variables, so complicated expressions with a non-obvious type must documented with some other mechanism.
     568This extension requires the use of @auto@ to infer the types of the new variables, so complicated expressions with a non-obvious type must be documented with some other mechanism.
    503569Furthermore, structured bindings are not a full replacement for @std::tie@, as it always declares new variables.
    504570
    505571Like \CC, D provides tuples through a library variadic template struct.
    506572In D, it is possible to name the fields of a tuple type, which creates a distinct type.
    507 \begin{dcode} % TODO: cite http://dlang.org/phobos/std_typecons.html
     573% http://dlang.org/phobos/std_typecons.html
     574\begin{dcode}
    508575Tuple!(float, "x", float, "y") point2D;
    509 Tuple!(float, float) float2;  // different types
     576Tuple!(float, float) float2;  // different type from point2D
    510577
    511578point2D[0]; // access first element
     
    521588The @expand@ method produces the components of the tuple as a list of separate values, making it possible to call a function that takes $N$ arguments using a tuple with $N$ components.
    522589
    523 Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML.
     590Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML \cite{sml}.
    524591A function in SML always accepts exactly one argument.
    525592There are two ways to mimic multiple argument functions: the first through currying and the second by accepting tuple arguments.
     
    535602Tuples are a foundational tool in SML, allowing the creation of arbitrarily complex structured data types.
    536603
    537 Scala, like \CC, provides tuple types through the standard library.
     604Scala, like \CC, provides tuple types through the standard library \cite{Scala}.
    538605Scala provides tuples of size 1 through 22 inclusive through generic data structures.
    539606Tuples support named access and subscript access, among a few other operations.
     
    547614\end{scalacode}
    548615In Scala, tuples are primarily used as simple data structures for carrying around multiple values or for returning multiple values from a function.
    549 The 22-element restriction is an odd and arbitrary choice, but in practice it doesn't cause problems since large tuples are uncommon.
     616The 22-element restriction is an odd and arbitrary choice, but in practice it does not cause problems since large tuples are uncommon.
    550617Subscript access is provided through the @productElement@ method, which returns a value of the top-type @Any@, since it is impossible to receive a more precise type from a general subscripting method due to type erasure.
    551618The disparity between named access beginning at @_1@ and subscript access starting at @0@ is likewise an oddity, but subscript access is typically avoided since it discards type information.
     
    553620
    554621
    555 \Csharp has similarly strange limitations, allowing tuples of size up to 7 components. % TODO: cite https://msdn.microsoft.com/en-us/library/system.tuple(v=vs.110).aspx
     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
    556623The officially supported workaround for this shortcoming is to nest tuples in the 8th component.
    557624\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.
    558625
    559 
    560 % TODO: cite 5.3 https://docs.python.org/3/tutorial/datastructures.html
    561 In Python, tuples are immutable sequences that provide packing and unpacking operations.
     626In Python \cite{Python}, tuples are immutable sequences that provide packing and unpacking operations.
    562627While the tuple itself is immutable, and thus does not allow the assignment of components, there is nothing preventing a component from being internally mutable.
    563628The components of a tuple can be accessed by unpacking into multiple variables, indexing, or via field name, like D.
    564629Tuples support multiple assignment through a combination of packing and unpacking, in addition to the common sequence operations.
    565630
    566 % TODO: cite https://developer.apple.com/library/content/documentation/Swift/Conceptual/Swift_Programming_Language/Types.html#//apple_ref/doc/uid/TP40014097-CH31-ID448
    567 Swift, like D, provides named tuples, with components accessed by name, index, or via extractors.
     631Swift \cite{Swift}, like D, provides named tuples, with components accessed by name, index, or via extractors.
    568632Tuples are primarily used for returning multiple values from a function.
    569633In Swift, @Void@ is an alias for the empty tuple, and there are no single element tuples.
     634
     635Tuples comparable to those described above are added to \CFA and discussed in Chapter 3.
    570636
    571637\section{Variadic Functions}
     
    581647printf("%d %g %c %s", 10, 3.5, 'X', "a string");
    582648\end{cfacode}
    583 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.
    584650Still, @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.
    585651
     
    641707A parameter pack matches 0 or more elements, which can be types or expressions depending on the context.
    642708Like other templates, variadic template functions rely on an implicit set of constraints on a type, in this example a @print@ routine.
    643 That is, it is possible to use the @f@ routine any any type provided there is a corresponding @print@ routine, making variadic templates fully open to extension, unlike variadic functions in C.
     709That is, it is possible to use the @f@ routine on any type provided there is a corresponding @print@ routine, making variadic templates fully open to extension, unlike variadic functions in C.
    644710
    645711Recent \CC standards (\CCfourteen, \CCseventeen) expand on the basic premise by allowing variadic template variables and providing convenient expansion syntax to remove the need for recursion in some cases, amongst other things.
     
    672738Unfortunately, Java's use of nominal inheritance means that types must explicitly inherit from classes or interfaces in order to be considered a subclass.
    673739The combination of these two issues greatly restricts the usefulness of variadic functions in Java.
     740
     741Type-safe variadic functions are added to \CFA and discussed in Chapter 4.
  • doc/rob_thesis/thesis-frontpgs.tex

    ra0fc78a rf674479  
    7676\begin{center}\textbf{Abstract}\end{center}
    7777
    78 % \CFA is a modern extension to the C programming language.
    79 % Some of the features of \CFA include parametric polymorphism, overloading, and .
    80 TODO
     78\CFA is a modern, non-object-oriented extension of the C programming language.
     79This thesis introduces two fundamental language features: tuples and constructors/destructors, as well as improved variadic functions.
     80While these features exist in prior programming languages, the contribution of this work is engineering these features into a highly complex type system.
    8181
    8282\cleardoublepage
  • doc/rob_thesis/thesis.tex

    ra0fc78a rf674479  
    6868\documentclass[letterpaper,12pt,titlepage,oneside,final]{book}
    6969
     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}
     73
    7074\usepackage[T1]{fontenc}                                % allow Latin1 (extended ASCII) characters
    7175\usepackage{textcomp}
    7276% \usepackage[utf8]{inputenc}
    73 \usepackage[latin1]{inputenc}
     77% \usepackage[latin1]{inputenc}
    7478\usepackage{fullpage,times,comment}
    7579% \usepackage{epic,eepic}
     
    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.
     
    225225\input{tuples}
    226226
     227\input{variadic}
     228
    227229\input{conclusions}
    228230
     
    282284\addcontentsline{toc}{chapter}{\textbf{References}}
    283285
    284 \bibliography{cfa}
     286\bibliography{cfa,thesis}
    285287% Tip 5: You can create multiple .bib files to organize your references.
    286288% Just list them all in the \bibliogaphy command, separated by commas (no spaces).
  • doc/rob_thesis/tuples.tex

    ra0fc78a rf674479  
    22\chapter{Tuples}
    33%======================================================================
    4 
    5 \section{Introduction}
    6 % TODO: named return values are not currently implemented in CFA - tie in with named tuples? (future work)
    7 % 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-rerefence)
    8 % 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 (future work)
    9 % 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
    104
    115\section{Multiple-Return-Value Functions}
     
    148This restriction results in code which emulates functions with multiple return values by \emph{aggregation} or by \emph{aliasing}.
    159In the former situation, the function designer creates a record type that combines all of the return values into a single type.
    16 For example, consider a function returning the most frequently occuring letter in a string, and its frequency.
    17 % TODO: consider simplifying the example!
    18 %   Two things I like about this example:
    19 %   * it uses different types to illustrate why an array is insufficient (this is not necessary, but is nice)
    20 %   * it's complicated enough to show the uninitialized pitfall that exists in the aliasing example.
    21 %   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.
    2212\begin{cfacode}
    2313struct mf_ret {
     
    7363const char * str = "hello world";
    7464char ch;                            // pre-allocate return value
    75 int freq = most_frequent(str, &ch); // pass return value as parameter
     65int freq = most_frequent(str, &ch); // pass return value as out parameter
    7666printf("%s -- %d %c\n", str, freq, ch);
    7767\end{cfacode}
    78 Notably, using this approach, the caller is directly responsible for allocating storage for the additional temporary return values.
    79 This complicates the call site with a sequence of variable declarations leading up to the call.
     68Notably, using this approach, the caller is directly responsible for allocating storage for the additional temporary return values, which complicates the call site with a sequence of variable declarations leading up to the call.
    8069Also, while a disciplined use of @const@ can give clues about whether a pointer parameter is going to be used as an out parameter, it is not immediately obvious from only the routine signature whether the callee expects such a parameter to be initialized before the call.
    8170Furthermore, while many C routines that accept pointers are designed so that it is safe to pass @NULL@ as a parameter, there are many C routines that are not null-safe.
     
    9079The 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.
    9180A multiple-returning function with return type @T@ can return any expression that is implicitly convertible to @T@.
    92 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,
    9382\begin{cfacode}
    9483[int, char] most_frequent(const char * str) {
     
    10998}
    11099\end{cfacode}
    111 This approach provides the benefits of compile-time checking for appropriate return statements as in aggregation, but without the required verbosity of declaring a new named type.
     100This approach provides the benefits of compile-time checking for appropriate return statements as in aggregation, but without the required verbosity of declaring a new named type, which precludes the bug seen with out parameters.
    112101
    113102The addition of multiple-return-value functions necessitates a syntax for accepting multiple values at the call-site.
     
    136125In this case, there is only one option for a function named @most_frequent@ that takes a string as input.
    137126This function returns two values, one @int@ and one @char@.
    138 There are four options for a function named @process@, but only two which accept two arguments, and of those the best match is (3), which is also an exact match.
     127There are four options for a function named @process@, but only two that accept two arguments, and of those the best match is (3), which is also an exact match.
    139128This expression first calls @most_frequent("hello world")@, which produces the values @3@ and @'l'@, which are fed directly to the first and second parameters of (3), respectively.
    140129
     
    148137The previous expression has 3 \emph{components}.
    149138Each component in a tuple expression can be any \CFA expression, including another tuple expression.
    150 % TODO: Tuple expressions can appear anywhere that any other expression can appear (...?)
    151139The order of evaluation of the components in a tuple expression is unspecified, to allow a compiler the greatest flexibility for program optimization.
    152140It is, however, guaranteed that each component of a tuple expression is evaluated for side-effects, even if the result is not used.
    153141Multiple-return-value functions can equivalently be called \emph{tuple-returning functions}.
    154 % TODO: does this statement still apply, and if so to what extent?
    155 %   Tuples are a compile-time phenomenon and have little to no run-time presence.
    156142
    157143\subsection{Tuple Variables}
     
    166152These variables can be used in any of the contexts where a tuple expression is allowed, such as in the @printf@ function call.
    167153As in the @process@ example, the components of the tuple value are passed as separate parameters to @printf@, allowing very simple printing of tuple expressions.
    168 If the individual components are required, they can be extracted with a simple assignment, as in previous examples.
     154One way to access the individual components is with a simple assignment, as in previous examples.
    169155\begin{cfacode}
    170156int freq;
     
    254240\label{s:TupleAssignment}
    255241An assignment where the left side of the assignment operator has a tuple type is called tuple assignment.
    256 There are two kinds of tuple assignment depending on whether the right side of the assignment operator has a tuple type or a non-tuple type, called Multiple and Mass Assignment, respectively.
     242There are two kinds of tuple assignment depending on whether the right side of the assignment operator has a tuple type or a non-tuple type, called \emph{Multiple} and \emph{Mass} Assignment, respectively.
    257243\begin{cfacode}
    258244int x;
     
    272258A mass assignment assigns the value $R$ to each $L_i$.
    273259For a mass assignment to be valid, @?=?(&$L_i$, $R$)@ must be a well-typed expression.
    274 This differs from C cascading assignment (e.g. @a=b=c@) in that conversions are applied to $R$ in each individual assignment, which prevents data loss from the chain of conversions that can happen during a cascading assignment.
     260These semantics differ from C cascading assignment (e.g. @a=b=c@) in that conversions are applied to $R$ in each individual assignment, which prevents data loss from the chain of conversions that can happen during a cascading assignment.
    275261For example, @[y, x] = 3.14@ performs the assignments @y = 3.14@ and @x = 3.14@, which results in the value @3.14@ in @y@ and the value @3@ in @x@.
    276262On the other hand, the C cascading assignment @y = x = 3.14@ performs the assignments @x = 3.14@ and @y = x@, which results in the value @3@ in @x@, and as a result the value @3@ in @y@ as well.
     
    288274These semantics allow cascading tuple assignment to work out naturally in any context where a tuple is permitted.
    289275These 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.
    290 This decision wa made in an attempt 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.
     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.
    291277While 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.
    292278Furthermore, 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.
     
    315301void ?{}(S *, S);      // (4)
    316302
    317 [S, S] x = [3, 6.28];  // uses (2), (3)
    318 [S, S] y;              // uses (1), (1)
    319 [S, S] z = x.0;        // uses (4), (4)
    320 \end{cfacode}
    321 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)@.
     303[S, S] x = [3, 6.28];  // uses (2), (3), specialized constructors
     304[S, S] y;              // uses (1), (1), default constructor
     305[S, S] z = x.0;        // uses (4), (4), copy constructor
     306\end{cfacode}
     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)@.
    322308@z@ is initialized by mass copy constructor calls @?{}(&z.0, x.0)@ and @?{}(&z.1, x.0)@.
    323309Finally, @x@, @y@, and @z@ are destructed, i.e. the calls @^?{}(&x.0)@, @^?{}(&x.1)@, @^?{}(&y.0)@, @^?{}(&y.1)@, @^?{}(&z.0)@, and @^?{}(&z.1)@.
     
    339325S s = t;
    340326\end{cfacode}
    341 The initialization of @s@ with @t@ works by default, because @t@ is flattened into its components, which satisfies the generated field constructor @?{}(S *, int, double)@ to initialize the first two values.
     327The initialization of @s@ with @t@ works by default because @t@ is flattened into its components, which satisfies the generated field constructor @?{}(S *, int, double)@ to initialize the first two values.
    342328
    343329\section{Member-Access Tuple Expression}
     
    354340Then the type of @a.[x, y, z]@ is @[T_x, T_y, T_z]@.
    355341
    356 Since tuple index expressions are a form of member-access expression, it is possible to use tuple-index expressions in conjunction with member tuple expressions to manually restructure a tuple (e.g. rearrange components, drop components, duplicate components, etc.).
     342Since tuple index expressions are a form of member-access expression, it is possible to use tuple-index expressions in conjunction with member tuple expressions to manually restructure a tuple (e.g., rearrange components, drop components, duplicate components, etc.).
    357343\begin{cfacode}
    358344[int, int, long, double] x;
     
    384370Since \CFA permits these tuple-access expressions using structures, unions, and tuples, \emph{member tuple expression} or \emph{field tuple expression} is more appropriate.
    385371
    386 It could be possible to extend member-access expressions further.
     372It is possible to extend member-access expressions further.
    387373Currently, a member-access expression whose member is a name requires that the aggregate is a structure or union, while a constant integer member requires the aggregate to be a tuple.
    388374In the interest of orthogonal design, \CFA could apply some meaning to the remaining combinations as well.
     
    398384z.y;  // ???
    399385\end{cfacode}
    400 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@.
    401387Under this interpretation, it becomes possible to not only access members of a struct by name, but also by position.
    402388Likewise, it seems natural to open this mechanism to enumerations as well, wherein the left side would be a type, rather than an expression.
    403 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.
    404390On 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.
    405 This problem is less of a concern with tuples, since modifying a tuple affects only the code which directly uses that tuple, whereas modifying a structure has far reaching consequences with every instance of the structure.
    406 
    407 As for @z.y@, a natural interpretation would be to extend the meaning of member tuple expressions.
     391This 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.
     392
     393As for @z.y@, one interpretation is to extend the meaning of member tuple expressions.
    408394That is, currently the tuple must occur as the member, i.e. to the right of the dot.
    409395Allowing 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.
    410396In this example, @z.y@ expands to @[z.0.y, z.1.y]@, allowing what is effectively a very limited compile-time field-sections map operation, where the argument must be a tuple containing only aggregates having a member named @y@.
    411 It is questionable how useful this would actually be in practice, since generally structures are not designed to have names in common with other structures, and further this could cause maintainability issues in that it encourages programmers to adopt very simple naming conventions, to maximize the amount of overlap between different types.
     397It is questionable how useful this would actually be in practice, since structures often do not have names in common with other structures, and further this could cause maintainability issues in that it encourages programmers to adopt very simple naming conventions to maximize the amount of overlap between different types.
    412398Perhaps more useful would be to allow arrays on the left side of the dot, which would likewise allow mapping a field access across the entire array, producing an array of the contained fields.
    413399The immediate problem with this idea is that C arrays do not carry around their size, which would make it impossible to use this extension for anything other than a simple stack allocated array.
    414400
    415 Supposing this feature works as described, it would be necessary to specify an ordering for the expansion of member access expressions versus member tuple expressions.
     401Supposing this feature works as described, it would be necessary to specify an ordering for the expansion of member-access expressions versus member-tuple expressions.
    416402\begin{cfacode}
    417403struct { int x, y; };
     
    426412\end{cfacode}
    427413Depending on exactly how the two tuples are combined, different results can be achieved.
    428 As such, a specific ordering would need to be imposed in order for this feature to be useful.
    429 Furthermore, this addition moves a member tuple expression's meaning from being clear statically to needing resolver support, since the member name needs to be distributed appropriately over each member of the tuple, which could itself be a tuple.
    430 
    431 Ultimately, both of these extensions introduce complexity into the model, with relatively little peceived benefit.
     414As such, a specific ordering would need to be imposed to make this feature useful.
     415Furthermore, this addition moves a member-tuple expression's meaning from being clear statically to needing resolver support, since the member name needs to be distributed appropriately over each member of the tuple, which could itself be a tuple.
     416
     417A second possibility is for \CFA to have named tuples, as they exist in Swift and D.
     418\begin{cfacode}
     419typedef [int x, int y] Point2D;
     420Point2D p1, p2;
     421p1.x + p1.y + p2.x + p2.y;
     422p1.0 + p1.1 + p2.0 + p2.1;  // equivalent
     423\end{cfacode}
     424In this simpler interpretation, a tuple type carries with it a list of possibly empty identifiers.
     425This approach fits naturally with the named return-value feature, and would likely go a long way towards implementing it.
     426
     427Ultimately, the first two extensions introduce complexity into the model, with relatively little perceived benefit, and so were dropped from consideration.
     428Named tuples are a potentially useful addition to the language, provided they can be parsed with a reasonable syntax.
     429
    432430
    433431\section{Casting}
    434432In C, the cast operator is used to explicitly convert between types.
    435 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.
    436434That 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.
    437435\begin{cfacode}
     
    442440(int)f();  // choose (2)
    443441\end{cfacode}
    444 Since casting is a fundamental operation in \CFA, casts should be given a meaningful interpretation in the context of tuples.
     442Since casting is a fundamental operation in \CFA, casts need to be given a meaningful interpretation in the context of tuples.
    445443Taking a look at standard C provides some guidance with respect to the way casts should work with tuples.
    446444\begin{cfacode}[numbers=left]
     
    448446void g();
    449447
    450 (void)f();
    451 (int)g();
     448(void)f();  // valid, ignore results
     449(int)g();   // invalid, void cannot be converted to int
    452450
    453451struct A { int x; };
    454 (struct A)f();
     452(struct A)f();  // invalid
    455453\end{cfacode}
    456454In C, line 4 is a valid cast, which calls @f@ and discards its result.
    457455On the other hand, line 5 is invalid, because @g@ does not produce a result, so requesting an @int@ to materialize from nothing is nonsensical.
    458 Finally, line 8 is also invalid, because in C casts only provide conversion between scalar types \cite{C11}.
    459 For consistency, this implies that any case wherein the number of components increases as a result of the cast is invalid, while casts which have the same or fewer number of components may be valid.
     456Finally, line 8 is also invalid, because in C casts only provide conversion between scalar types \cite[p.~91]{C11}.
     457For consistency, this implies that any case wherein the number of components increases as a result of the cast is invalid, while casts that have the same or fewer number of components may be valid.
    460458
    461459Formally, a cast to tuple type is valid when $T_n \leq S_m$, where $T_n$ is the number of components in the target type and $S_m$ is the number of components in the source type, and for each $i$ in $[0, n)$, $S_i$ can be cast to $T_i$.
     
    509507\end{cfacode}
    510508Note that due to the implicit tuple conversions, this function is not restricted to the addition of two triples.
    511 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 which can bind to @T@, with a pairwise @?+?@ over @T@.
    512 For example, these expressions will also succeed and produce the same value.
    513 \begin{cfacode}
    514 ([x.0, x.1]) + ([x.2, 10, 20, 30]);
    515 x.0 + ([x.1, x.2, 10, 20, 30]);
     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@.
     510For example, these expressions also succeed and produce the same value.
     511\begin{cfacode}
     512([x.0, x.1]) + ([x.2, 10, 20, 30]);  // x + ([10, 20, 30])
     513x.0 + ([x.1, x.2, 10, 20, 30]);      // x + ([10, 20, 30])
    516514\end{cfacode}
    517515This presents a potential problem if structure is important, as these three expressions look like they should have different meanings.
    518 Further, these calls can be made ambiguous by adding seemingly different functions.
     516Furthermore, these calls can be made ambiguous by introducing seemingly different functions.
    519517\begin{cfacode}
    520518forall(otype T | { T ?+?(T, T); })
     
    524522\end{cfacode}
    525523It is also important to note that these calls could be disambiguated if the function return types were different, as they likely would be for a reasonable implementation of @?+?@, since the return type is used in overload resolution.
    526 Still, this is a deficiency of the current argument matching algorithm, and depending on the function, differing return values may not always be appropriate.
    527 It's possible that this could be rectified by applying an appropriate cost to the structuring and flattening conversions, which are currently 0-cost conversions.
     524Still, these semantics are a deficiency of the current argument matching algorithm, and depending on the function, differing return values may not always be appropriate.
     525These issues could be rectified by applying an appropriate cost to the structuring and flattening conversions, which are currently 0-cost conversions.
    528526Care would be needed in this case to ensure that exact matches do not incur such a cost.
    529527\begin{cfacode}
     
    536534\end{cfacode}
    537535
    538 Until this point, it has been assumed that assertion arguments must match the parameter type exactly, modulo polymorphic specialization (i.e. no implicit conversions are applied to assertion arguments).
     536Until this point, it has been assumed that assertion arguments must match the parameter type exactly, modulo polymorphic specialization (i.e., no implicit conversions are applied to assertion arguments).
    539537This decision presents a conflict with the flexibility of tuples.
    540538\subsection{Assertion Inference}
     
    617615In the call to @f@, the second and third argument components are structured into a tuple argument.
    618616
    619 Expressions which may contain side effects are made into \emph{unique expressions} before being expanded by the flattening conversion.
     617Expressions that may contain side effects are made into \emph{unique expressions} before being expanded by the flattening conversion.
    620618Each unique expression is assigned an identifier and is guaranteed to be executed exactly once.
    621619\begin{cfacode}
     
    624622g(h());
    625623\end{cfacode}
    626 Interally, this is converted to
     624Internally, this is converted to pseudo-\CFA
    627625\begin{cfacode}
    628626void g(int, double);
    629627[int, double] h();
    630 let unq<0> = f() : g(unq<0>.0, unq<0>.1);  // notation?
    631 \end{cfacode}
     628lazy [int, double] unq0 = h(); // deferred execution
     629g(unq0.0, unq0.1);             // execute h() once
     630\end{cfacode}
     631That is, the function @h@ is evaluated lazily and its result is stored for subsequent accesses.
    632632Ultimately, unique expressions are converted into two variables and an expression.
    633633\begin{cfacode}
     
    638638[int, double] _unq0;
    639639g(
    640   (_unq0_finished_ ? _unq0 : (_unq0 = f(), _unq0_finished_ = 1, _unq0)).0,
    641   (_unq0_finished_ ? _unq0 : (_unq0 = f(), _unq0_finished_ = 1, _unq0)).1,
     640  (_unq0_finished_ ? _unq0 : (_unq0 = h(), _unq0_finished_ = 1, _unq0)).0,
     641  (_unq0_finished_ ? _unq0 : (_unq0 = h(), _unq0_finished_ = 1, _unq0)).1,
    642642);
    643643\end{cfacode}
     
    646646Every subsequent evaluation of the unique expression then results in an access to the stored result of the actual expression.
    647647
    648 Currently, the \CFA translator has a very broad, imprecise definition of impurity, where any function call is assumed to be impure.
    649 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.
    650 It's possible that unique expressions could be exposed to the user through a language feature, but it's not immediately obvious that there is a benefit to doing so.
     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.
     650It is possible that lazy evaluation could be exposed to the user through a lazy keyword with little additional effort.
    651651
    652652Tuple member expressions are recursively expanded into a list of member access expressions.
     
    655655x.[0, 1.[0, 2]];
    656656\end{cfacode}
    657 Which becomes
     657which becomes
    658658\begin{cfacode}
    659659[x.0, [x.1.0, x.1.2]];
    660660\end{cfacode}
    661 Tuple member expressions also take advantage of unique expressions in the case of possible impurity.
     661Tuple-member expressions also take advantage of unique expressions in the case of possible impurity.
    662662
    663663Finally, the various kinds of tuple assignment, constructors, and destructors generate GNU C statement expressions.
     
    711711});
    712712\end{cfacode}
    713 A variable is generated to store the value produced by a statement expression, since its fields may need to be constructed with a non-trivial constructor and it may need to be referred to multiple time, e.g. in a unique expression.
     713A variable is generated to store the value produced by a statement expression, since its fields may need to be constructed with a non-trivial constructor and it may need to be referred to multiple time, e.g., in a unique expression.
    714714$N$ LHS variables are generated and constructed using the address of the tuple components, and a single RHS variable is generated to store the value of the RHS without any loss of precision.
    715715A nested statement expression is generated that performs the individual assignments and constructs the return value using the results of the individual assignments.
     
    785785The use of statement expressions allows the translator to arbitrarily generate additional temporary variables as needed, but binds the implementation to a non-standard extension of the C language.
    786786There are other places where the \CFA translator makes use of GNU C extensions, such as its use of nested functions, so this is not a new restriction.
    787 
    788 \section{Variadic Functions}
    789 % TODO: should this maybe be its own chapter?
    790 C provides variadic functions through the manipulation of @va_list@ objects.
    791 A variadic function is one which contains at least one parameter, followed by @...@ as the last token in the parameter list.
    792 In particular, some form of \emph{argument descriptor} is needed to inform the function of the number of arguments and their types.
    793 Two common argument descriptors are format strings or and counter parameters.
    794 It's important to note that both of these mechanisms are inherently redundant, because they require the user to specify information that the compiler knows explicitly.
    795 This required repetition is error prone, because it's easy for the user to add or remove arguments without updating the argument descriptor.
    796 In addition, C requires the programmer to hard code all of the possible expected types.
    797 As a result, it is cumbersome to write a function that is open to extension.
    798 For example, a simple function which sums $N$ @int@s,
    799 \begin{cfacode}
    800 int sum(int N, ...) {
    801   va_list args;
    802   va_start(args, N);
    803   int ret = 0;
    804   while(N) {
    805     ret += va_arg(args, int);  // have to specify type
    806     N--;
    807   }
    808   va_end(args);
    809   return ret;
    810 }
    811 sum(3, 10, 20, 30);  // need to keep counter in sync
    812 \end{cfacode}
    813 The @va_list@ type is a special C data type that abstracts variadic argument manipulation.
    814 The @va_start@ macro initializes a @va_list@, given the last named parameter.
    815 Each use of the @va_arg@ macro allows access to the next variadic argument, given a type.
    816 Since the function signature does not provide any information on what types can be passed to a variadic function, the compiler does not perform any error checks on a variadic call.
    817 As such, it is possible to pass any value to the @sum@ function, including pointers, floating-point numbers, and structures.
    818 In the case where the provided type is not compatible with the argument's actual type after default argument promotions, or if too many arguments are accessed, the behaviour is undefined \cite{C11}.
    819 Furthermore, there is no way to perform the necessary error checks in the @sum@ function at run-time, since type information is not carried into the function body.
    820 Since they rely on programmer convention rather than compile-time checks, variadic functions are generally unsafe.
    821 
    822 In practice, compilers can provide warnings to help mitigate some of the problems.
    823 For example, GCC provides the @format@ attribute to specify that a function uses a format string, which allows the compiler to perform some checks related to the standard format specifiers.
    824 Unfortunately, this does not permit extensions to the format string syntax, so a programmer cannot extend the attribute to warn for mismatches with custom types.
    825 
    826 Needless to say, C's variadic functions are a deficient language feature.
    827 Two options were examined to provide better, type-safe variadic functions in \CFA.
    828 \subsection{Whole Tuple Matching}
    829 Option 1 is to change the argument matching algorithm, so that type parameters can match whole tuples, rather than just their components.
    830 This option could be implemented with two phases of argument matching when a function contains type parameters and the argument list contains tuple arguments.
    831 If flattening and structuring fail to produce a match, a second attempt at matching the function and argument combination is made where tuple arguments are not expanded and structure must match exactly, modulo non-tuple implicit conversions.
    832 For example:
    833 \begin{cfacode}
    834   forall(otype T, otype U | { T g(U); })
    835   void f(T, U);
    836 
    837   [int, int] g([int, int, int, int]);
    838 
    839   f([1, 2], [3, 4, 5, 6]);
    840 \end{cfacode}
    841 With flattening and structuring, the call is first transformed into @f(1, 2, 3, 4, 5, 6)@.
    842 Since the first argument of type @T@ does not have a tuple type, unification decides that @T=int@ and @1@ is matched as the first parameter.
    843 Likewise, @U@ does not have a tuple type, so @U=int@ and @2@ is accepted as the second parameter.
    844 There are now no remaining formal parameters, but there are remaining arguments and the function is not variadic, so the match fails.
    845 
    846 With the addition of an exact matching attempt, @T=[int,int]@ and @U=[int,int,int,int]@ and so the arguments type check.
    847 Likewise, when inferring assertion @g@, an exact match is found.
    848 
    849 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.
    850 For example, consider a @new@ function which allocates memory using @malloc@ and constructs the result, using arbitrary arguments.
    851 \begin{cfacode}
    852 struct Array;
    853 void ?{}(Array *, int, int, int);
    854 
    855 forall(dtype T, otype Params | sized(T) | { void ?{}(T *, Params); })
    856 T * new(Params p) {
    857   return malloc(){ p };
    858 }
    859 Array(int) * x = new([1, 2, 3]);
    860 \end{cfacode}
    861 The call to @new@ is not particularly appealing, since it requires the use of square brackets at the call-site, which is not required in any other function call.
    862 This shifts the burden from the compiler to the programmer, which is almost always wrong, and creates an odd inconsistency within the language.
    863 Similarly, in order to pass 0 variadic arguments, an explicit empty tuple must be passed into the argument list, otherwise the exact matching rule would not have an argument to bind against.
    864 
    865 It should be otherwise noted that the addition of an exact matching rule only affects the outcome for polymorphic type binding when tuples are involved.
    866 For non-tuple arguments, exact matching and flattening \& structuring are equivalent.
    867 For tuple arguments to a function without polymorphic formal parameters, flattening and structuring work whenever an exact match would have worked, since the tuple is flattened and implicitly restructured to its original structure.
    868 Thus there is nothing to be gained from permitting the exact matching rule to take effect when a function does not contain polymorphism and none of the arguments are tuples.
    869 
    870 Overall, this option takes a step in the right direction, but is contrary to the flexibility of the existing tuple design.
    871 
    872 \subsection{A New Typeclass}
    873 A second option is the addition of another kind of type parameter, @ttype@.
    874 Matching against a @ttype@ parameter consumes all remaining argument components and packages them into a tuple, binding to the resulting tuple of types.
    875 In a given parameter list, there should be at most one @ttype@ parameter that must occur last, otherwise the call can never resolve, given the previous rule.
    876 % TODO: a similar rule exists in C/C++ for "..."
    877 This idea essentially matches normal variadic semantics, with a strong feeling of similarity to \CCeleven variadic templates.
    878 As such, @ttype@ variables will also be referred to as argument packs.
    879 This is the option that has been added to \CFA.
    880 
    881 Like variadic templates, the main way to manipulate @ttype@ polymorphic functions is through recursion.
    882 Since nothing is known about a parameter pack by default, assertion parameters are key to doing anything meaningful.
    883 Unlike variadic templates, @ttype@ polymorphic functions can be separately compiled.
    884 
    885 For example, a simple translation of the C sum function using @ttype@ would look like
    886 \begin{cfacode}
    887 int sum(){ return 0; }        // (0)
    888 forall(ttype Params | { int sum(Params); })
    889 int sum(int x, Params rest) { // (1)
    890   return x+sum(rest);
    891 }
    892 sum(10, 20, 30);
    893 \end{cfacode}
    894 Since (0) does not accept any arguments, it is not a valid candidate function for the call @sum(10, 20, 30)@.
    895 In 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]@.
    896 In order to finish the resolution of @sum@, an assertion parameter which matches @int sum(int, int)@ is required.
    897 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)@.
    898 Next, (0) fails, and to satisfy (1) @Params@ is bound to @[]@, requiring an assertion @int sum()@.
    899 Finally, (0) matches and (1) fails, which terminates the recursion.
    900 Effectively, this traces as @sum(10, 20, 30)@ $\rightarrow$ @10+sum(20, 30)@ $\rightarrow$ @10+(20+sum(30))@ $\rightarrow$ @10+(20+(30+sum()))@ $\rightarrow$ @10+(20+(30+0))@.
    901 
    902 A point of note is that this version does not require any form of argument descriptor, since the \CFA type system keeps track of all of these details.
    903 It might be reasonable to take the @sum@ function a step further to enforce a minimum number of arguments, which could be done simply
    904 \begin{cfacode}
    905 int sum(int x, int y){
    906   return x+y;
    907 }
    908 forall(ttype Params | { int sum(int, Params); })
    909 int sum(int x, int y, Params rest) {
    910   return sum(x+y, rest);
    911 }
    912 sum(10, 20, 30);
    913 \end{cfacode}
    914 
    915 One more iteration permits the summation of any summable type, as long as all arguments are the same type.
    916 \begin{cfacode}
    917 trait summable(otype T) {
    918   T ?+?(T, T);
    919 };
    920 forall(otype R | summable(R))
    921 R sum(R x, R y){
    922   return x+y;
    923 }
    924 forall(otype R, ttype Params
    925   | summable(R)
    926   | { R sum(R, Params); })
    927 R sum(R x, R y, Params rest) {
    928   return sum(x+y, rest);
    929 }
    930 sum(3, 10, 20, 30);
    931 \end{cfacode}
    932 Unlike C, it is not necessary to hard code the expected type.
    933 This is naturally open to extension, in that any user-defined type with a @?+?@ operator is automatically able to be used with the @sum@ function.
    934 That is to say, the programmer who writes @sum@ does not need full program knowledge of every possible data type, unlike what is necessary to write an equivalent function using the standard C mechanisms.
    935 
    936 Going one last step, it is possible to achieve full generality in \CFA, allowing the summation of arbitrary lists of summable types.
    937 \begin{cfacode}
    938 trait summable(otype T1, otype T2, otype R) {
    939   R ?+?(T1, T2);
    940 };
    941 forall(otype T1, otype T2, otype R | summable(T1, T2, R))
    942 R sum(T1 x, T2 y) {
    943   return x+y;
    944 }
    945 forall(otype T1, otype T2, otype T3, ttype Params, otype R
    946   | summable(T1, T2, T3)
    947   | { R sum(T3, Params); })
    948 R sum(T1 x, T2 y, Params rest ) {
    949   return sum(x+y, rest);
    950 }
    951 sum(3, 10.5, 20, 30.3);
    952 \end{cfacode}
    953 The \CFA translator requires adding explicit @double ?+?(int, double)@ and @double ?+?(double, int)@ functions for this call to work, since implicit conversions are not supported for assertions.
    954 
    955 C 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.
    956 Furthermore, it might be desirable to disallow polymorphic functions to use C variadic syntax to encourage a Cforall style.
    957 Aside 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.
    958 
    959 Variadic templates in \CC require an ellipsis token to express that a parameter is a parameter pack and to expand a parameter pack.
    960 \CFA does not need an ellipsis in either case, since the type class @ttype@ is only used for variadics.
    961 An alternative design could have used an ellipsis combined with an existing type class.
    962 This approach was not taken because the largest benefit of the ellipsis token in \CC is the ability to expand a parameter pack within an expression, e.g. in fold expressions, which requires compile-time knowledge of the structure of the parameter pack, which is not available in \CFA.
    963 \begin{cppcode}
    964 template<typename... Args>
    965 void f(Args &... args) {
    966   g(&args...);  // expand to addresses of pack elements
    967 }
    968 \end{cppcode}
    969 As such, the addition of an ellipsis token would be purely an aesthetic change in \CFA today.
    970 
    971 It is possible to write a type-safe variadic print routine, which can replace @printf@
    972 \begin{cfacode}
    973 struct S { int x, y; };
    974 forall(otype T, ttype Params |
    975   { void print(T); void print(Params); })
    976 void print(T arg, Params rest) {
    977   print(arg);
    978   print(rest);
    979 }
    980 void print(char * x) { printf("%s", x); }
    981 void print(int x) { printf("%d", x);  }
    982 void print(S s) { print("{ ", s.x, ",", s.y, " }"); }
    983 print("s = ", (S){ 1, 2 }, "\n");
    984 \end{cfacode}
    985 This example routine showcases a variadic-template-like decomposition of the provided argument list.
    986 The individual @print@ routines allow printing a single element of a type.
    987 The polymorphic @print@ allows printing any list of types, as long as each individual type has a @print@ function.
    988 The individual print functions can be used to build up more complicated @print@ routines, such as for @S@, which is something that cannot be done with @printf@ in C.
    989 
    990 It is also possible to use @ttype@ polymorphism to provide arbitrary argument forwarding functions.
    991 For example, it is possible to write @new@ as a library function.
    992 Example 2: new (i.e. type-safe malloc + constructors)
    993 \begin{cfacode}
    994 struct Array;
    995 void ?{}(Array *, int, int, int);
    996 
    997 forall(dtype T, ttype Params | sized(T) | { void ?{}(T *, Params); })
    998 T * new(Params p) {
    999   return malloc(){ p }; // construct result of malloc
    1000 }
    1001 Array * x = new(1, 2, 3);
    1002 \end{cfacode}
    1003 The @new@ function provides the combination of type-safe @malloc@ with a constructor call, so that it becomes impossible to forget to construct dynamically allocated objects.
    1004 This provides the type-safety of @new@ in \CC, without the need to specify the allocated type, thanks to return-type inference.
    1005 
    1006 In the call to @new@, @Array@ is selected to match @T@, and @Params@ is expanded to match @[int, int, int, int]@. To satisfy the assertions, a constructor with an interface compatible with @void ?{}(Array *, int, int, int)@ must exist in the current scope.
    1007 
    1008 \subsection{Implementation}
    1009 
    1010 The definition of @new@
    1011 \begin{cfacode}
    1012 forall(dtype T | sized(T)) T * malloc();
    1013 
    1014 forall(dtype T, ttype Params | sized(T) | { void ?{}(T *, Params); })
    1015 T * new(Params p) {
    1016   return malloc(){ p }; // construct result of malloc
    1017 }
    1018 \end{cfacode}
    1019 Generates the following
    1020 \begin{cfacode}
    1021 void *malloc(long unsigned int _sizeof_T, long unsigned int _alignof_T);
    1022 
    1023 void *new(
    1024   void (*_adapter_)(void (*)(), void *, void *),
    1025   long unsigned int _sizeof_T,
    1026   long unsigned int _alignof_T,
    1027   long unsigned int _sizeof_Params,
    1028   long unsigned int _alignof_Params,
    1029   void (* _ctor_T)(void *, void *),
    1030   void *p
    1031 ){
    1032   void *_retval_new;
    1033   void *_tmp_cp_ret0;
    1034   void *_tmp_ctor_expr0;
    1035   _retval_new=
    1036     (_adapter_(_ctor_T,
    1037       (_tmp_ctor_expr0=(_tmp_cp_ret0=malloc(_sizeof_2tT, _alignof_2tT),
    1038         _tmp_cp_ret0)),
    1039       p),
    1040     _tmp_ctor_expr0); // ?{}
    1041   *(void **)&_tmp_cp_ret0; // ^?{}
    1042   return _retval_new;
    1043 }
    1044 \end{cfacode}
    1045 The constructor for @T@ is called indirectly through the adapter function on the result of @malloc@ and the parameter pack.
    1046 The variable that was allocated and constructed is then returned from @new@.
    1047 
    1048 A call to @new@
    1049 \begin{cfacode}
    1050 struct S { int x, y; };
    1051 void ?{}(S *, int, int);
    1052 
    1053 S * s = new(3, 4);
    1054 \end{cfacode}
    1055 Generates the following
    1056 \begin{cfacode}
    1057 struct _tuple2_ {  // _tuple2_(T0, T1)
    1058   void *field_0;
    1059   void *field_1;
    1060 };
    1061 struct _conc__tuple2_0 {  // _tuple2_(int, int)
    1062   int field_0;
    1063   int field_1;
    1064 };
    1065 struct _conc__tuple2_0 _tmp_cp1;  // tuple argument to new
    1066 struct S *_tmp_cp_ret1;           // return value from new
    1067 void _thunk0(  // ?{}(S *, [int, int])
    1068   struct S *_p0,
    1069   struct _conc__tuple2_0 _p1
    1070 ){
    1071   _ctor_S(_p0, _p1.field_0, _p1.field_1);  // restructure tuple parameter
    1072 }
    1073 void _adapter(void (*_adaptee)(), void *_p0, void *_p1){
    1074   // apply adaptee to arguments after casting to actual types
    1075   ((void (*)(struct S *, struct _conc__tuple2_0))_adaptee)(
    1076     _p0,
    1077     *(struct _conc__tuple2_0 *)_p1
    1078   );
    1079 }
    1080 struct S *s = (struct S *)(_tmp_cp_ret1=
    1081   new(
    1082     _adapter,
    1083     sizeof(struct S),
    1084     __alignof__(struct S),
    1085     sizeof(struct _conc__tuple2_0),
    1086     __alignof__(struct _conc__tuple2_0),
    1087     (void (*)(void *, void *))&_thunk0,
    1088     (({ // copy construct tuple argument to new
    1089       int *__multassign_L0 = (int *)&_tmp_cp1.field_0;
    1090       int *__multassign_L1 = (int *)&_tmp_cp1.field_1;
    1091       int __multassign_R0 = 3;
    1092       int __multassign_R1 = 4;
    1093       ((*__multassign_L0=__multassign_R0 /* ?{} */) ,
    1094        (*__multassign_L1=__multassign_R1 /* ?{} */));
    1095     }), &_tmp_cp1)
    1096   ), _tmp_cp_ret1);
    1097 *(struct S **)&_tmp_cp_ret1; // ^?{}  // destroy return value from new
    1098 ({  // destroy argument temporary
    1099   int *__massassign_L0 = (int *)&_tmp_cp1.field_0;
    1100   int *__massassign_L1 = (int *)&_tmp_cp1.field_1;
    1101   ((*__massassign_L0 /* ^?{} */) , (*__massassign_L1 /* ^?{} */));
    1102 });
    1103 \end{cfacode}
    1104 Of note, @_thunk0@ is generated to translate calls to @?{}(S *, [int, int])@ into calls to @?{}(S *, int, int)@.
    1105 The call to @new@ constructs a tuple argument using the supplied arguments.
    1106 
    1107 The @print@ function
    1108 \begin{cfacode}
    1109 forall(otype T, ttype Params |
    1110   { void print(T); void print(Params); })
    1111 void print(T arg, Params rest) {
    1112   print(arg);
    1113   print(rest);
    1114 }
    1115 \end{cfacode}
    1116 Generates
    1117 \begin{cfacode}
    1118 void print_variadic(
    1119   void (*_adapterF_7tParams__P)(void (*)(), void *),
    1120   void (*_adapterF_2tT__P)(void (*)(), void *),
    1121   void (*_adapterF_P2tT2tT__MP)(void (*)(), void *, void *),
    1122   void (*_adapterF2tT_P2tT2tT_P_MP)(void (*)(), void *, void *, void *),
    1123   long unsigned int _sizeof_T,
    1124   long unsigned int _alignof_T,
    1125   long unsigned int _sizeof_Params,
    1126   long unsigned int _alignof_Params,
    1127   void *(*_assign_TT)(void *, void *),
    1128   void (*_ctor_T)(void *),
    1129   void (*_ctor_TT)(void *, void *),
    1130   void (*_dtor_T)(void *),
    1131   void (*print_T)(void *),
    1132   void (*print_Params)(void *),
    1133   void *arg,
    1134   void *rest
    1135 ){
    1136   void *_tmp_cp0 = __builtin_alloca(_sizeof_T);
    1137   _adapterF_2tT__P(  // print(arg)
    1138     ((void (*)())print_T),
    1139     (_adapterF_P2tT2tT__MP( // copy construct argument
    1140       ((void (*)())_ctor_TT),
    1141       _tmp_cp0,
    1142       arg
    1143     ), _tmp_cp0)
    1144   );
    1145   _dtor_T(_tmp_cp0);  // destroy argument temporary
    1146   _adapterF_7tParams__P(  // print(rest)
    1147     ((void (*)())print_Params),
    1148     rest
    1149   );
    1150 }
    1151 \end{cfacode}
    1152 The @print_T@ routine is called indirectly through an adapter function with a copy constructed argument, followed by an indirect call to @print_Params@.
    1153 
    1154 A call to print
    1155 \begin{cfacode}
    1156 void print(const char * x) { printf("%s", x); }
    1157 void print(int x) { printf("%d", x);  }
    1158 
    1159 print("x = ", 123, ".\n");
    1160 \end{cfacode}
    1161 Generates the following
    1162 \begin{cfacode}
    1163 void print_string(const char *x){
    1164   int _tmp_cp_ret0;
    1165   (_tmp_cp_ret0=printf("%s", x)) , _tmp_cp_ret0;
    1166   *(int *)&_tmp_cp_ret0; // ^?{}
    1167 }
    1168 void print_int(int x){
    1169   int _tmp_cp_ret1;
    1170   (_tmp_cp_ret1=printf("%d", x)) , _tmp_cp_ret1;
    1171   *(int *)&_tmp_cp_ret1; // ^?{}
    1172 }
    1173 
    1174 struct _tuple2_ {  // _tuple2_(T0, T1)
    1175   void *field_0;
    1176   void *field_1;
    1177 };
    1178 struct _conc__tuple2_0 {  // _tuple2_(int, const char *)
    1179   int field_0;
    1180   const char *field_1;
    1181 };
    1182 struct _conc__tuple2_0 _tmp_cp6;  // _tuple2_(int, const char *)
    1183 const char *_thunk0(const char **_p0, const char *_p1){
    1184         // const char * ?=?(const char **, const char *)
    1185   return *_p0=_p1;
    1186 }
    1187 void _thunk1(const char **_p0){ // void ?{}(const char **)
    1188   *_p0; // ?{}
    1189 }
    1190 void _thunk2(const char **_p0, const char *_p1){
    1191         // void ?{}(const char **, const char *)
    1192   *_p0=_p1; // ?{}
    1193 }
    1194 void _thunk3(const char **_p0){ // void ^?{}(const char **)
    1195   *_p0; // ^?{}
    1196 }
    1197 void _thunk4(struct _conc__tuple2_0 _p0){ // void print([int, const char *])
    1198   struct _tuple1_ { // _tuple1_(T0)
    1199     void *field_0;
    1200   };
    1201   struct _conc__tuple1_1 { // _tuple1_(const char *)
    1202     const char *field_0;
    1203   };
    1204   void _thunk5(struct _conc__tuple1_1 _pp0){ // void print([const char *])
    1205     print_string(_pp0.field_0);  // print(rest.0)
    1206   }
    1207   void _adapter_i_pii_(void (*_adaptee)(), void *_ret, void *_p0, void *_p1){
    1208     *(int *)_ret=((int (*)(int *, int))_adaptee)(_p0, *(int *)_p1);
    1209   }
    1210   void _adapter_pii_(void (*_adaptee)(), void *_p0, void *_p1){
    1211     ((void (*)(int *, int ))_adaptee)(_p0, *(int *)_p1);
    1212   }
    1213   void _adapter_i_(void (*_adaptee)(), void *_p0){
    1214     ((void (*)(int))_adaptee)(*(int *)_p0);
    1215   }
    1216   void _adapter_tuple1_5_(void (*_adaptee)(), void *_p0){
    1217     ((void (*)(struct _conc__tuple1_1 ))_adaptee)(*(struct _conc__tuple1_1 *)_p0);
    1218   }
    1219   print_variadic(
    1220     _adapter_tuple1_5,
    1221     _adapter_i_,
    1222     _adapter_pii_,
    1223     _adapter_i_pii_,
    1224     sizeof(int),
    1225     __alignof__(int),
    1226     sizeof(struct _conc__tuple1_1),
    1227     __alignof__(struct _conc__tuple1_1),
    1228     (void *(*)(void *, void *))_assign_i,     // int ?=?(int *, int)
    1229     (void (*)(void *))_ctor_i,                // void ?{}(int *)
    1230     (void (*)(void *, void *))_ctor_ii,       // void ?{}(int *, int)
    1231     (void (*)(void *))_dtor_ii,               // void ^?{}(int *)
    1232     (void (*)(void *))print_int,              // void print(int)
    1233     (void (*)(void *))&_thunk5,               // void print([const char *])
    1234     &_p0.field_0,                             // rest.0
    1235     &(struct _conc__tuple1_1 ){ _p0.field_1 } // [rest.1]
    1236   );
    1237 }
    1238 struct _tuple1_ {  // _tuple1_(T0)
    1239   void *field_0;
    1240 };
    1241 struct _conc__tuple1_6 {  // _tuple_1(const char *)
    1242   const char *field_0;
    1243 };
    1244 const char *_temp0;
    1245 _temp0="x = ";
    1246 void _adapter_pstring_pstring_string(
    1247   void (*_adaptee)(),
    1248   void *_ret,
    1249   void *_p0,
    1250   void *_p1
    1251 ){
    1252   *(const char **)_ret=
    1253     ((const char *(*)(const char **, const char *))_adaptee)(
    1254       _p0,
    1255       *(const char **)_p1
    1256     );
    1257 }
    1258 void _adapter_pstring_string(void (*_adaptee)(), void *_p0, void *_p1){
    1259   ((void (*)(const char **, const char *))_adaptee)(_p0, *(const char **)_p1);
    1260 }
    1261 void _adapter_string_(void (*_adaptee)(), void *_p0){
    1262   ((void (*)(const char *))_adaptee)(*(const char **)_p0);
    1263 }
    1264 void _adapter_tuple2_0_(void (*_adaptee)(), void *_p0){
    1265   ((void (*)(struct _conc__tuple2_0 ))_adaptee)(*(struct _conc__tuple2_0 *)_p0);
    1266 }
    1267 print_variadic(
    1268   _adapter_tuple2_0_,
    1269   _adapter_string_,
    1270   _adapter_pstring_string_,
    1271   _adapter_pstring_pstring_string_,
    1272   sizeof(const char *),
    1273   __alignof__(const char *),
    1274   sizeof(struct _conc__tuple2_0 ),
    1275   __alignof__(struct _conc__tuple2_0 ),
    1276   (void *(*)(void *, void *))&_thunk0, // const char * ?=?(const char **, const char *)
    1277   (void (*)(void *))&_thunk1,          // void ?{}(const char **)
    1278   (void (*)(void *, void *))&_thunk2,  // void ?{}(const char **, const char *)
    1279   (void (*)(void *))&_thunk3,          // void ^?{}(const char **)
    1280   (void (*)(void *))print_string,      // void print(const char *)
    1281   (void (*)(void *))&_thunk4,          // void print([int, const char *])
    1282   &_temp0,                             // "x = "
    1283   (({  // copy construct tuple argument to print
    1284     int *__multassign_L0 = (int *)&_tmp_cp6.field_0;
    1285     const char **__multassign_L1 = (const char **)&_tmp_cp6.field_1;
    1286     int __multassign_R0 = 123;
    1287     const char *__multassign_R1 = ".\n";
    1288     ((*__multassign_L0=__multassign_R0 /* ?{} */),
    1289      (*__multassign_L1=__multassign_R1 /* ?{} */));
    1290   }), &_tmp_cp6)                        // [123, ".\n"]
    1291 );
    1292 ({  // destroy argument temporary
    1293   int *__massassign_L0 = (int *)&_tmp_cp6.field_0;
    1294   const char **__massassign_L1 = (const char **)&_tmp_cp6.field_1;
    1295   ((*__massassign_L0 /* ^?{} */) , (*__massassign_L1 /* ^?{} */));
    1296 });
    1297 \end{cfacode}
    1298 The type @_tuple2_@ is generated to allow passing the @rest@ argument to @print_variadic@.
    1299 Thunks 0 through 3 provide wrappers for the @otype@ parameters for @const char *@, while @_thunk4@ translates a call to @print([int, const char *])@ into a call to @print_variadic(int, [const char *])@.
    1300 This all builds to a call to @print_variadic@, with the appropriate copy construction of the tuple argument.
    1301 
    1302 \section{Future Work}
  • src/ControlStruct/LabelGenerator.cc

    ra0fc78a rf674479  
    2020#include "SynTree/Label.h"
    2121#include "SynTree/Attribute.h"
     22#include "SynTree/Statement.h"
    2223
    2324namespace ControlStruct {
     
    3132        }
    3233
    33         Label LabelGenerator::newLabel( std::string suffix ) {
     34        Label LabelGenerator::newLabel( std::string suffix, Statement * stmt ) {
    3435                std::ostringstream os;
    3536                os << "__L" << current++ << "__" << suffix;
     37                if ( stmt && ! stmt->get_labels().empty() ) {
     38                        os << "_" << stmt->get_labels().front() << "__";
     39                }
    3640                std::string ret = os.str();
    3741                Label l( ret );
  • src/ControlStruct/LabelGenerator.h

    ra0fc78a rf674479  
    55// file "LICENCE" distributed with Cforall.
    66//
    7 // LabelGenerator.h -- 
     7// LabelGenerator.h --
    88//
    99// Author           : Rodolfo G. Esteves
     
    2424          public:
    2525                static LabelGenerator *getGenerator();
    26                 Label newLabel(std::string suffix = "");
     26                Label newLabel(std::string suffix, Statement * stmt = nullptr);
    2727                void reset() { current = 0; }
    2828                void rewind() { current--; }
  • src/ControlStruct/MLEMutator.cc

    ra0fc78a rf674479  
    5656                bool labeledBlock = !(cmpndStmt->get_labels().empty());
    5757                if ( labeledBlock ) {
    58                         Label brkLabel = generator->newLabel("blockBreak");
     58                        Label brkLabel = generator->newLabel("blockBreak", cmpndStmt);
    5959                        enclosingControlStructures.push_back( Entry( cmpndStmt, brkLabel ) );
    6060                } // if
     
    8080                // whether brkLabel and contLabel are used with branch statements and will recursively do the same to nested
    8181                // loops
    82                 Label brkLabel = generator->newLabel("loopBreak");
    83                 Label contLabel = generator->newLabel("loopContinue");
     82                Label brkLabel = generator->newLabel("loopBreak", loopStmt);
     83                Label contLabel = generator->newLabel("loopContinue", loopStmt);
    8484                enclosingControlStructures.push_back( Entry( loopStmt, brkLabel, contLabel ) );
    8585                loopStmt->set_body ( loopStmt->get_body()->acceptMutator( *this ) );
    8686
     87                assert( ! enclosingControlStructures.empty() );
    8788                Entry &e = enclosingControlStructures.back();
    8889                // sanity check that the enclosing loops have been popped correctly
     
    108109                bool labeledBlock = !(ifStmt->get_labels().empty());
    109110                if ( labeledBlock ) {
    110                         Label brkLabel = generator->newLabel("blockBreak");
     111                        Label brkLabel = generator->newLabel("blockBreak", ifStmt);
    111112                        enclosingControlStructures.push_back( Entry( ifStmt, brkLabel ) );
    112113                } // if
    113114
    114115                Parent::mutate( ifStmt );
    115                
     116
    116117                if ( labeledBlock ) {
    117118                        if ( ! enclosingControlStructures.back().useBreakExit().empty() ) {
     
    126127        Statement *MLEMutator::handleSwitchStmt( SwitchClass *switchStmt ) {
    127128                // generate a label for breaking out of a labeled switch
    128                 Label brkLabel = generator->newLabel("switchBreak");
     129                Label brkLabel = generator->newLabel("switchBreak", switchStmt);
    129130                enclosingControlStructures.push_back( Entry(switchStmt, brkLabel) );
    130131                mutateAll( switchStmt->get_statements(), *this );
     
    158159
    159160                std::list< Entry >::reverse_iterator targetEntry;
    160                 if ( branchStmt->get_type() == BranchStmt::Goto ) {
    161                         return branchStmt;
    162                 } else if ( branchStmt->get_type() == BranchStmt::Continue) {
    163                         // continue target must be a loop
    164                         if ( branchStmt->get_target() == "" ) {
    165                                 targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), [](Entry &e) { return isLoop( e.get_controlStructure() ); } );
    166                         } else {
    167                                 // labelled continue - lookup label in table ot find attached control structure
    168                                 targetEntry = std::find( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), (*targetTable)[branchStmt->get_target()] );
    169                         } // if
    170                         if ( targetEntry == enclosingControlStructures.rend() || ! isLoop( targetEntry->get_controlStructure() ) ) {
    171                                 throw SemanticError( "'continue' target must be an enclosing loop: " + originalTarget );
    172                         } // if
    173                 } else if ( branchStmt->get_type() == BranchStmt::Break ) {
    174                         if ( enclosingControlStructures.empty() ) throw SemanticError( "'break' outside a loop, switch, or labelled block" );
    175                         targetEntry = enclosingControlStructures.rbegin();
    176                 } else {
    177                         assert( false );
    178                 } // if
    179 
    180                 if ( branchStmt->get_target() != "" && targetTable->find( branchStmt->get_target() ) == targetTable->end() ) {
    181                         throw SemanticError("The label defined in the exit loop statement does not exist: " + originalTarget );  // shouldn't happen (since that's already checked)
    182                 } // if
     161                switch ( branchStmt->get_type() ) {
     162                        case BranchStmt::Goto:
     163                                return branchStmt;
     164                        case BranchStmt::Continue:
     165                        case BranchStmt::Break: {
     166                                bool isContinue = branchStmt->get_type() == BranchStmt::Continue;
     167                                // unlabeled break/continue
     168                                if ( branchStmt->get_target() == "" ) {
     169                                        if ( isContinue ) {
     170                                                // continue target is outermost loop
     171                                                targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), [](Entry &e) { return isLoop( e.get_controlStructure() ); } );
     172                                        } else {
     173                                                // break target is outmost control structure
     174                                                if ( enclosingControlStructures.empty() ) throw SemanticError( "'break' outside a loop, switch, or labelled block" );
     175                                                targetEntry = enclosingControlStructures.rbegin();
     176                                        } // if
     177                                } else {
     178                                        // labeled break/continue - lookup label in table to find attached control structure
     179                                        targetEntry = std::find( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), (*targetTable)[branchStmt->get_target()] );
     180                                } // if
     181                                // ensure that selected target is valid
     182                                if ( targetEntry == enclosingControlStructures.rend() || (isContinue && ! isLoop( targetEntry->get_controlStructure() ) ) ) {
     183                                        throw SemanticError( toString( (isContinue ? "'continue'" : "'break'"), " target must be an enclosing ", (isContinue ? "loop: " : "control structure: "), originalTarget ) );
     184                                } // if
     185                                break;
     186                        }
     187                        default:
     188                                assert( false );
     189                } // switch
    183190
    184191                // branch error checks, get the appropriate label name and create a goto
     
    197204                } // switch
    198205
    199                 if ( branchStmt->get_target() == "" && branchStmt->get_type() != BranchStmt::Continue ) {
    200                         // unlabelled break/continue - can keep branch as break/continue for extra semantic information, but add
    201                         // exitLabel as its destination so that label passes can easily determine where the break/continue goes to
    202                         branchStmt->set_target( exitLabel );
    203                         return branchStmt;
    204                 } else {
    205                         // labelled break/continue - can't easily emulate this with break and continue, so transform into a goto
    206                         delete branchStmt;
    207                         return new BranchStmt( std::list<Label>(), exitLabel, BranchStmt::Goto );
    208                 } // if
     206                // transform break/continue statements into goto to simplify later handling of branches
     207                delete branchStmt;
     208                return new BranchStmt( std::list<Label>(), exitLabel, BranchStmt::Goto );
    209209        }
    210210
  • src/ResolvExpr/AlternativeFinder.cc

    ra0fc78a rf674479  
    211211        }
    212212
    213         // std::unordered_map< Expression *, UniqueExpr * > ;
     213        void AlternativeFinder::addAnonConversions( const Alternative & alt ) {
     214                // adds anonymous member interpretations whenever an aggregate value type is seen.
     215                Expression * expr = alt.expr->clone();
     216                std::unique_ptr< Expression > manager( expr ); // RAII for expr
     217                alt.env.apply( expr->get_result() );
     218                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( expr->get_result() ) ) {
     219                        NameExpr nameExpr( "" );
     220                        addAggMembers( structInst, expr, alt.cost+Cost( 0, 0, 1 ), alt.env, &nameExpr );
     221                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( expr->get_result() ) ) {
     222                        NameExpr nameExpr( "" );
     223                        addAggMembers( unionInst, expr, alt.cost+Cost( 0, 0, 1 ), alt.env, &nameExpr );
     224                } // if
     225        }
    214226
    215227        template< typename StructOrUnionType >
     
    220232                std::list< Declaration* > members;
    221233                aggInst->lookup( name, members );
     234
    222235                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
    223236                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
    224237                                alternatives.push_back( Alternative( new MemberExpr( dwt, expr->clone() ), env, newCost ) );
    225238                                renameTypes( alternatives.back().expr );
     239                                addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a member expression.
    226240                        } else {
    227241                                assert( false );
     
    730744                if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
    731745
     746                // compute conversionsion costs
    732747                for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) {
    733748                        Cost cvtCost = computeConversionCost( *withFunc, indexer );
     
    751766                        } // if
    752767                } // for
     768                // function may return struct or union value, in which case we need to add alternatives for implicit conversions to each of the anonymous members
     769                for ( const Alternative & alt : alternatives ) {
     770                        addAnonConversions( alt );
     771                }
     772
    753773                candidates.clear();
    754774                candidates.splice( candidates.end(), alternatives );
     
    885905                        )
    886906                        renameTypes( alternatives.back().expr );
    887                         if ( StructInstType *structInst = dynamic_cast< StructInstType* >( (*i)->get_type() ) ) {
    888                                 NameExpr nameExpr( "" );
    889                                 addAggMembers( structInst, &newExpr, Cost( 0, 0, 1 ), env, &nameExpr );
    890                         } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( (*i)->get_type() ) ) {
    891                                 NameExpr nameExpr( "" );
    892                                 addAggMembers( unionInst, &newExpr, Cost( 0, 0, 1 ), env, &nameExpr );
    893                         } // if
     907                        addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
    894908                } // for
    895909        }
  • src/ResolvExpr/AlternativeFinder.h

    ra0fc78a rf674479  
    7878                void findSubExprs( InputIterator begin, InputIterator end, OutputIterator out );
    7979
     80                /// Adds alternatives for anonymous members
     81                void addAnonConversions( const Alternative & alt );
    8082                /// Adds alternatives for member expressions, given the aggregate, conversion cost for that aggregate, and name of the member
    8183                template< typename StructOrUnionType > void addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member );
  • src/SymTab/Autogen.cc

    ra0fc78a rf674479  
    498498                makeUnionFieldsAssignment( srcParam, dstParam, back_inserter( funcDecl->get_statements()->get_kids() ) );
    499499                if ( returnVal ) {
    500                         if ( isDynamicLayout ) makeUnionFieldsAssignment( srcParam, returnVal, back_inserter( funcDecl->get_statements()->get_kids() ) );
    501                         else funcDecl->get_statements()->get_kids().push_back( new ReturnStmt( noLabels, new VariableExpr( srcParam ) ) );
     500                        funcDecl->get_statements()->get_kids().push_back( new ReturnStmt( noLabels, new VariableExpr( srcParam ) ) );
    502501                }
    503502        }
  • src/SymTab/Validate.cc

    ra0fc78a rf674479  
    208208        };
    209209
     210        class ArrayLength : public Visitor {
     211        public:
     212                /// for array types without an explicit length, compute the length and store it so that it
     213                /// is known to the rest of the phases. For example,
     214                ///   int x[] = { 1, 2, 3 };
     215                ///   int y[][2] = { { 1, 2, 3 }, { 1, 2, 3 } };
     216                /// here x and y are known at compile-time to have length 3, so change this into
     217                ///   int x[3] = { 1, 2, 3 };
     218                ///   int y[3][2] = { { 1, 2, 3 }, { 1, 2, 3 } };
     219                static void computeLength( std::list< Declaration * > & translationUnit );
     220
     221                virtual void visit( ObjectDecl * objDecl );
     222        };
     223
    210224        class CompoundLiteral final : public GenPoly::DeclMutator {
    211225                Type::StorageClasses storageClasses;
     
    235249                acceptAll( translationUnit, pass3 );
    236250                VerifyCtorDtorAssign::verify( translationUnit );
     251                ArrayLength::computeLength( translationUnit );
    237252        }
    238253
     
    869884                }
    870885        }
     886
     887        void ArrayLength::computeLength( std::list< Declaration * > & translationUnit ) {
     888                ArrayLength len;
     889                acceptAll( translationUnit, len );
     890        }
     891
     892        void ArrayLength::visit( ObjectDecl * objDecl ) {
     893                if ( ArrayType * at = dynamic_cast< ArrayType * >( objDecl->get_type() ) ) {
     894                        if ( at->get_dimension() != nullptr ) return;
     895                        if ( ListInit * init = dynamic_cast< ListInit * >( objDecl->get_init() ) ) {
     896                                at->set_dimension( new ConstantExpr( Constant::from_ulong( init->get_initializers().size() ) ) );
     897                        }
     898                }
     899        }
    871900} // namespace SymTab
    872901
  • src/SynTree/Expression.cc

    ra0fc78a rf674479  
    339339                        return TypeSubstitution( aggInst->get_baseParameters()->begin(), aggInst->get_baseParameters()->end(), aggInst->get_parameters().begin() );
    340340                } else {
    341                         assertf( false, "makeSub expects struct or union type for aggregate" );
     341                        assertf( false, "makeSub expects struct or union type for aggregate, but got: %s", toString( t ).c_str() );
    342342                }
    343343        }
Note: See TracChangeset for help on using the changeset viewer.