Changeset 7493339


Ignore:
Timestamp:
Apr 3, 2017, 7:04:30 PM (7 years ago)
Author:
Rob Schluntz <rschlunt@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
fbd7ad6
Parents:
ae6cc8b
Message:

incorporate Peter's feedback, handle many TODOs

Location:
doc/rob_thesis
Files:
7 added
6 edited

Legend:

Unmodified
Added
Removed
  • doc/rob_thesis/conclusions.tex

    rae6cc8b r7493339  
    44
    55Conclusion paragraphs.
     6
     7\section{Future Work}
     8
     9\subsection{Constructors and Destructors}
     10% TODO: discuss move semantics; they haven't been implemented, but could be. Currently looking at alternative models.
     11
     12% TODO: discuss exceptions
     13
     14% TODO: fix return value destruction in full compiler
     15
     16% TODO: once deleted functions are added, unions can have deleted standard functions, like C++11 (may not need to mention this again...)
     17
     18% TODO: better study and fix the ways @= objects interact with the rest of the world (e.g. provide @= equivalent for assignment, or otherwise have @= objects default to using intrinsic/autogen ops?)
     19
     20
     21
     22\subsection{Tuples}
     23
     24% TODO: named return values are not currently implemented in CFA - tie in with named tuples?
     25
     26% TODO: tuples are allowed in expressions, exact meaning is defined by operator overloading (e.g. can add tuples). An important caveat to note is that it is currently impossible to allow adding two triples but prevent adding a pair with a quadruple (single flattening/structuring conversions are implicit, only total number of components matters). May be able to solve this with more nuanced conversion rules
     27
     28\subsection{Variadic Functions}
     29% TODO: look into 'nicer' expansion syntax
     30
     31% TODO: consider more sophisticated argument matching algorithms, e.g. forall(ttype Params) void f(Params, Params); f(1,2); f(1,2,3,4); => f([1], [2]); f([1,2], [3,4]); => okay if Params can be bound to a type that is consistent throughout the expression's type
     32
     33
  • doc/rob_thesis/ctordtor.tex

    rae6cc8b r7493339  
    22\chapter{Constructors and Destructors}
    33%======================================================================
    4 
    5 % TODO: discuss move semantics; they haven't been implemented, but could be. Currently looking at alternative models. (future work)
    64
    75% TODO: as an experiment, implement Andrei Alexandrescu's ScopeGuard http://www.drdobbs.com/cpp/generic-change-the-way-you-write-excepti/184403758?pgno=2
     
    553551% // and so on
    554552
    555 
    556 
    557 % TODO: talk somewhere about compound literals?
    558 
    559553Since \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.
     554As well, \CFA is not an object-oriented programming language, i.e., structures cannot have routine members.
    561555Nevertheless, one important goal is to reduce programming complexity and increase safety.
    562556To that end, \CFA provides support for implicit pre/post-execution of routines for objects, via constructors and destructors.
    563 
    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).
    574557
    575558This chapter details the design of constructors and destructors in \CFA, along with their current implementation in the translator.
     
    592575Next, @x@ is assigned the value of @y@.
    593576In 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).
     577The key difference between assignment and initialization being that assignment occurs on a live object (i.e., an object that contains data).
    595578It 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
     579Use of uninitialized variables yields undefined behaviour, which is a common source of errors in C programs.
     580
     581Declaration initialization is insufficient, because it permits uninitialized variables to exist and because it does not allow for the insertion of arbitrary code before a variable is live.
     582Many C compilers give good warnings for uninitialized variables most of the time, but they cannot in all cases.
     583\begin{cfacode}
     584int f(int *);  // output parameter: never reads, only writes
     585int g(int *);  // input parameter: never writes, only reads,
     586               // so requires initialized variable
    603587
    604588int x, y;
    605589f(&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.
     590g(&y);  // uses y uninitialized
     591\end{cfacode}
     592Other 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.
    609593
    610594In 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.
     
    614598};
    615599struct array_int create_array(int sz) {
    616   return (struct array_int) { malloc(sizeof(int)*sz) };
     600  return (struct array_int) { calloc(sizeof(int)*sz) };
    617601}
    618602void destroy_rh(struct resource_holder * rh) {
     
    639623
    640624In \CFA, a constructor is a function with the name @?{}@.
     625Like other operators in \CFA, the name represents the syntax used to call the constructor, e.g., @struct S = { ... };@.
    641626Every 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).
    642627The @this@ parameter must have a pointer type, whose base type is the type of object that the function constructs.
     
    655640
    656641In 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.
     642It 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.
    658643In \CFA, the user can define a constructor to handle initialization of @Array@ objects.
    659644
     
    671656This 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.
    672657This 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.
     658In other words, a default constructor is a constructor that takes a single argument: the @this@ parameter.
    674659
    675660In \CFA, a destructor is a function much like a constructor, except that its name is \lstinline!^?{}!.
     
    680665}
    681666\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.
     667The destructor is automatically called at deallocation for all objects of type @Array@.
     668Hence, the memory associated with an @Array@ is automatically freed when the object's lifetime ends.
    683669The exact guarantees made by \CFA with respect to the calling of destructors are discussed in section \ref{sub:implicit_dtor}.
    684670
     
    691677\end{cfacode}
    692678By 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@.
     679On line 2, @z@ is initialized with the value of @x@, while on line 3, @y@ is assigned the value of @x@.
    694680The 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.
    695681In particular, these cases cannot be handled the same way because in the former case @z@ does not currently own an array, while @y@ does.
     
    712698The first function is called a \emph{copy constructor}, because it constructs its argument by copying the values from another object of the same type.
    713699The second function is the standard copy-assignment operator.
    714 These four functions are special in that they control the state of most objects.
     700The four functions (default constructor, destructor, copy constructor, and assignment operator) are special in that they safely control the state of most objects.
    715701
    716702It is possible to define a constructor that takes any combination of parameters to provide additional initialization options.
     
    729715Array x, y = { 20, 0xdeadbeef }, z = y;
    730716\end{cfacode}
     717
    731718In \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.
    732719One 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.
     
    748735Destructors are implicitly called in reverse declaration-order so that objects with dependencies are destructed before the objects they are dependent on.
    749736
    750 \subsection{Syntax}
    751 \label{sub:syntax} % TODO: finish this section
     737\subsection{Calling Syntax}
     738\label{sub:syntax}
    752739There are several ways to construct an object in \CFA.
    753740As previously introduced, every variable is automatically constructed at its definition, which is the most natural way to construct an object.
     
    773760A * y = malloc();  // copy construct: ?{}(&y, malloc())
    774761
    775 ?{}(&x);    // explicit construct x
    776 ?{}(y, x);  // explit construct y from x
    777 ^?{}(&x);   // explicit destroy x
     762?{}(&x);    // explicit construct x, second construction
     763?{}(y, x);  // explit construct y from x, second construction
     764^?{}(&x);   // explicit destroy x, in different order
    778765^?{}(y);    // explicit destroy y
    779766
     
    781768// implicit ^?{}(&x);
    782769\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.
     770Calling a constructor or destructor directly is a flexible feature that allows complete control over the management of storage.
    784771In particular, constructors double as a placement syntax.
    785772\begin{cfacode}
     
    804791Finally, constructors and destructors support \emph{operator syntax}.
    805792Like 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.
     793This syntactic form is similar to the new initialization syntax in \CCeleven, except that it is used in expression contexts, rather than declaration contexts.
    806794\begin{cfacode}
    807795struct A { ... };
     
    822810Destructor operator syntax is actually an statement, and requires parentheses for symmetry with constructor syntax.
    823811
     812One of these three syntactic forms should appeal to either C or \CC programmers using \CFA.
     813
    824814\subsection{Function Generation}
    825815In \CFA, every type is defined to have the core set of four functions described previously.
     
    833823There are several options for user-defined types: structures, unions, and enumerations.
    834824To 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.
     825By 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.
    836826
    837827The generated functions for enumerations are the simplest.
    838828Since 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
    840829For example, given the enumeration
    841830\begin{cfacode}
     
    860849\end{cfacode}
    861850In 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.
     851The existing generated routines are sufficient to express this restriction, since they are currently set up to take in values of that enumeration type.
    863852Changes 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.
     853In 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.
    865854
    866855For 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
     856Given 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$@.
     857That is, a default constructor for @S@ default constructs the members of @S@, the copy constructor copy constructs them, and so on.
     858For example, given the structure definition
    870859\begin{cfacode}
    871860struct A {
     
    893882}
    894883\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.
     884It is important to note that the destructors are called in reverse declaration order to prevent conflicts in the event there are dependencies among members.
    896885
    897886In 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.
     887The field constructors are constructors that consume a prefix of the structure's member-list.
    899888That 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 }@.
     889The 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 }@.
    901890Extending the previous example, the following constructors are implicitly generated for @A@.
    902891\begin{cfacode}
     
    911900\end{cfacode}
    912901
    913 For unions, the default constructor and destructor do nothing, as it is not obvious which member if any should be constructed.
     902For unions, the default constructor and destructor do nothing, as it is not obvious which member, if any, should be constructed.
    914903For copy constructor and assignment operations, a bitwise @memcpy@ is applied.
    915904In 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.
     
    947936
    948937% 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.
     938In \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.
    950939This restriction could easily be added into \CFA once \emph{deleted} functions are added.
    951940
     
    970959Here, @&s@ and @&s2@ are cast to unqualified pointer types.
    971960This 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.
     961This applies only to implicitly generated constructor calls.
     962Hence, explicitly re-initializing qualified objects with a constructor requires an explicit cast.
     963
     964As discussed in Section \ref{sub:c_background}, compound literals create unnamed objects.
     965This mechanism can continue to be used seamlessly in \CFA with managed types to create temporary objects.
     966The 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.
     967For example,
     968\begin{cfacode}
     969struct A { int x; };
     970void ?{}(A *, int, int);
     971{
     972  int x = (A){ 10, 20 }.x;
     973}
     974\end{cfacode}
     975is equivalent to
     976\begin{cfacode}
     977struct A { int x, y; };
     978void ?{}(A *, int, int);
     979{
     980  A _tmp;
     981  ?{}(&_tmp, 10, 20);
     982  int x = _tmp.x;
     983  ^?{}(&tmp);
     984}
     985\end{cfacode}
    973986
    974987Unlike \CC, \CFA provides an escape hatch that allows a user to decide at an object's definition whether it should be managed or not.
     
    984997A a2 @= { 0 };  // unmanaged
    985998\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.
     999In 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.
     1000Instead, @a2->x@ is initialized to @0@ as if it were a C object, because of the explicit initializer.
    9891001
    9901002In 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.
     
    9921004It is recommended that most objects be managed by sensible constructors and destructors, except where absolutely necessary.
    9931005
    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??
     1006When 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.
     1007Furthermore, if the user declares any constructor, then the intrinsic/generated default constructor is also hidden, precluding default construction.
     1008These 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++}.
    9971009\begin{cfacode}
    9981010struct S { int x, y; };
     
    10011013  S s0, s1 = { 0 }, s2 = { 0, 2 }, s3 = s2;  // okay
    10021014  {
    1003     void ?{}(S * s, int i) { s->x = i*2; }
     1015    void ?{}(S * s, int i) { s->x = i*2; } // locally hide autogen constructors
    10041016    S s4;  // error
    10051017    S s5 = { 3 };  // okay
     
    10581070} // z, y, w implicitly destructed, in this order
    10591071\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).
     1072If at any point, the @this@ parameter is passed directly as the target of another constructor, then it is assumed that constructor handles the initialization of all of the object's members and no implicit constructor calls are added. % TODO: this is basically always wrong. if anything, I should check that such a constructor does not initialize any members, otherwise it'll always initialize the member twice (once locally, once by the called constructor). This might be okay in some situations, but it deserves a warning at the very least.
    10611073To override this rule, \ateq can be used to force the translator to trust the programmer's discretion.
    10621074This form of \ateq is not yet implemented.
     
    10641076Despite great effort, some forms of C syntax do not work well with constructors in \CFA.
    10651077In 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.
    10681078\begin{cfacode}
    10691079// all legal forward declarations in C
     
    10761086f(b:10, a:20, c:30);  // which parameter is which?
    10771087\end{cfacode}
     1088In 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.
     1089Furthermore, a function prototype can be repeated an arbitrary number of times, each time using different names.
    10781090As 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.
     1091
     1092In addition, constructor calls do not support unnamed nesting.
     1093\begin{cfacode}
     1094struct B { int x; };
     1095struct C { int y; };
     1096struct A { B b; C c; };
     1097void ?{}(A *, B);
     1098void ?{}(A *, C);
     1099
     1100A a = {
     1101  { 10 },  // construct B? - invalid
     1102};
     1103\end{cfacode}
     1104In C, nesting initializers means that the programmer intends to initialize subobjects with the nested initializers.
     1105The reason for this omission is to both simplify the mental model for using constructors, and to make initialization simpler for the expression resolver.
     1106If 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.
     1107That 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@.
     1108In 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.
     1109
     1110More precisely, constructor calls cannot have a nesting depth greater than the number of array components in the type of the initialized object, plus one.
    10821111For example,
    10831112\begin{cfacode}
     
    10981127% TODO: in CFA if the array dimension is empty, no object constructors are added -- need to fix this.
    10991128The 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.
     1129
    11051130It should be noted that unmanaged objects can still make use of designations and nested initializers in \CFA.
     1131It 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.
    11061132
    11071133\subsection{Implicit Destructors}
     
    11301156\end{cfacode}
    11311157
    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}
    1172 
    11731158The next example illustrates the use of simple continue and break statements and the manner that they interact with implicit destructors.
    11741159\begin{cfacode}
     
    11831168\end{cfacode}
    11841169Since 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.
     1170In the case where @i@ is @2@, the continue statement runs the loop update expression and attempts to begin the next iteration of the loop.
    11861171Since 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.
    11871172When @i@ is @3@, the break statement moves control to just past the end of the loop.
     
    11931178L1: for (int i = 0; i < 10; i++) {
    11941179  A x;
    1195   L2: for (int j = 0; j < 10; j++) {
     1180  for (int j = 0; j < 10; j++) {
    11961181    A y;
    1197     if (j == 0) {
    1198       continue;    // destruct y
    1199     } else if (j == 1) {
    1200       break;       // destruct y
    1201     } else if (i == 1) {
     1182    if (i == 1) {
    12021183      continue L1; // destruct y
    12031184    } else if (i == 2) {
     
    12091190The statement @continue L1@ begins the next iteration of the outer for-loop.
    12101191Since the semantics of continue require the loop update expression to execute, control branches to the \emph{end} of the outer for loop, meaning that the block destructor for @x@ can be reused, and it is only necessary to generate the destructor for @y@.
     1192% TODO: "why not do this all the time? fix or justify"
    12111193Break, 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.
    12121194
     
    12771259Exempt from these rules are intrinsic and builtin functions.
    12781260It 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.
     1261That 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.
    12791262This 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.
    12801263\begin{cfacode}
     
    12841267void ^?{}(A *);
    12851268
    1286 A f(A x) {
    1287   return x;
     1269A identity(A x) { // pass by value => need local copy
     1270  return x;       // return by value => make call-site copy
    12881271}
    12891272
    12901273A y, z @= {};
    1291 identity(y);
    1292 identity(z);
     1274identity(y);  // copy construct y into x
     1275identity(z);  // copy construct z into x
    12931276\end{cfacode}
    12941277Note 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.
    12961278
    12971279This generates the following
    12981280\begin{cfacode}
    12991281struct A f(struct A x){
    1300   struct A _retval_f;
    1301   ?{}((&_retval_f), x);
     1282  struct A _retval_f;    // return value
     1283  ?{}((&_retval_f), x);  // copy construct return value
    13021284  return _retval_f;
    13031285}
    13041286
    13051287struct 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
     1288?{}(&y);                 // default construct
     1289struct A z = { 0 };      // C default
     1290
     1291struct A _tmp_cp1;       // argument 1
     1292struct A _tmp_cp_ret0;   // return value
     1293_tmp_cp_ret0=f(
     1294  (?{}(&_tmp_cp1, y) , _tmp_cp1)  // argument is a comma expression
     1295), _tmp_cp_ret0;         // return value for cascading
     1296^?{}(&_tmp_cp_ret0);     // destruct return value
     1297^?{}(&_tmp_cp1);         // destruct argument 1
     1298
     1299struct A _tmp_cp2;       // argument 1
     1300struct A _tmp_cp_ret1;   // return value
     1301_tmp_cp_ret1=f(
     1302  (?{}(&_tmp_cp2, z), _tmp_cp2)  // argument is a common expression
     1303), _tmp_cp_ret1;         // return value for cascading
     1304^?{}(&_tmp_cp_ret1);     // destruct return value
     1305^?{}(&_tmp_cp2);         // destruct argument 1
    13201306^?{}(&y);
    13211307\end{cfacode}
     1308
     1309A 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.
     1310\begin{cfacode}
     1311identity(z@);  // do not copy construct argument
     1312               // - will copy construct/destruct return value
     1313A@ identity_nocopy(A @ x) {  // argument not copy constructed or destructed
     1314  return x;  // not copy constructed
     1315             // return type marked @ => not destructed
     1316}
     1317\end{cfacode}
     1318It 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.
    13221319
    13231320A 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.
    13241321Specifically, 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.
    13251322This 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.
     1323It 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.
     1324Thus, it is not safe to rely on an object's @this@ pointer to remain constant throughout execution of the program.
    13281325\begin{cfacode}
    13291326A * external_data[32];
     
    13411338  }
    13421339}
     1340
     1341A makeA() {
     1342  A x;  // stores &x in external_data
     1343  return x;
     1344}
     1345makeA();  // return temporary has a different address than x
     1346// equivalent to:
     1347//   A _tmp;
     1348//   _tmp = makeA(), _tmp;
     1349//   ^?{}(&_tmp);
    13431350\end{cfacode}
    13441351In 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.
     1352Due 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.
     1353
     1354This problem could be solved in the translator by changing the function signatures so that the return value is moved into the parameter list.
    13481355For example, the translator could restructure the code like so
    13491356\begin{cfacode}
     
    13631370\end{cfacode}
    13641371This 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}.
     1372It is worth pointing out that this kind of signature rewriting already occurs in polymorphic functions that return by value, as discussed in \cite{Bilson03}.
    13661373A 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.
    13671374\begin{cfacode}
    13681375struct A { int v; };
    1369 A x; // unmanaged
     1376A x; // unmanaged, since only trivial constructors are available
    13701377{
    13711378  void ?{}(A * a) { ... }
     
    13751382A z; // unmanaged
    13761383\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.
     1384Hence 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.
    13781385Even 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.
     1386Furthermore, it is not possible to overload C functions, so using @extern "C"@ to declare functions is of limited use.
     1387
     1388It 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.
    13821389Ideally, structs should be manageable by default, since otherwise the default case becomes more verbose.
    13831390This means that in general, function signatures would have to be rewritten, and in a select few cases the signatures would not be rewritten.
     
    14081415\section{Implementation}
    14091416\subsection{Array Initialization}
    1410 Arrays are a special case in the C type system.
     1417Arrays are a special case in the C type-system.
    14111418C 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.
    14121419Instead, \CFA defines the initialization and destruction of an array recursively.
     
    15251532By default, objects within a translation unit are constructed in declaration order, and destructed in the reverse order.
    15261533The 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
    15301534It is, however, guaranteed that any global objects in the standard library are initialized prior to the initialization of any object in the user program.
    15311535
    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
     1536This feature is implemented in the \CFA translator by grouping every global constructor call into a function with the GCC attribute \emph{constructor}, which performs most of the heavy lifting. % TODO: CITE: https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#Common-Function-Attributes
    15331537A similar function is generated with the \emph{destructor} attribute, which handles all global destructor calls.
    15341538At 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.
     
    15591563\end{cfacode}
    15601564
     1565%   https://gcc.gnu.org/onlinedocs/gcc/C_002b_002b-Attributes.html#C_002b_002b-Attributes
     1566% 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
     1567GCC provides an attribute @init_priority@, which specifies allows specifying the relative priority for initialization of global objects on a per-object basis in \CC.
     1568A similar attribute can be implemented in \CFA by pulling marked objects into global constructor/destructor-attribute functions with the specified priority.
     1569For example,
     1570\begin{cfacode}
     1571struct A { ... };
     1572void ?{}(A *, int);
     1573void ^?{}(A *);
     1574__attribute__((init_priority(200))) A x = { 123 };
     1575\end{cfacode}
     1576would generate
     1577\begin{cfacode}
     1578A x;
     1579__attribute__((constructor(200))) __init_x() {
     1580  ?{}(&x, 123);  // construct x with priority 200
     1581}
     1582__attribute__((destructor(200))) __destroy_x() {
     1583  ?{}(&x);       // destruct x with priority 200
     1584}
     1585\end{cfacode}
     1586
    15611587\subsection{Static Local Variables}
    15621588In standard C, it is possible to mark variables that are local to a function with the @static@ storage class.
    15631589Unlike 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.
     1590Much 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.
    15651591
    15661592Yet again, this rule is too restrictive for a language with constructors and destructors.
     
    15731599Construction of @static@ local objects is implemented via an accompanying @static bool@ variable, which records whether the variable has already been constructed.
    15741600A 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.
     1601The object's destructor is scheduled to be run when the program terminates using @atexit@, and the companion @bool@'s value is set so that subsequent invocations of the function do not reconstruct the object.
    15761602Since the parameter to @atexit@ is a parameter-less function, some additional tweaking is required.
    15771603First, the @static@ variable must be hoisted up to global scope and uniquely renamed to prevent name clashes with other global objects.
     
    16301656\end{cfacode}
    16311657
     1658% TODO: move this section forward?? maybe just after constructor syntax? would need to remove _tmp_cp_ret0, since copy constructors are not discussed yet, but this might not be a big issue.
    16321659\subsection{Constructor Expressions}
    16331660In \CFA, it is possible to use a constructor as an expression.
    16341661Like other operators, the function name @?{}@ matches its operator syntax.
    16351662For 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@.
     1663A key example for this capability is the use of constructor expressions to initialize the result of a call to standard C routine @malloc@.
    16381664\begin{cfacode}
    16391665struct X { ... };
  • doc/rob_thesis/intro.tex

    rae6cc8b r7493339  
    55\section{\CFA Background}
    66\label{s:background}
    7 \CFA is a modern extension to the C programming language.
     7\CFA 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}
     
    3939For example, in the initialization of @a1@, the initializer of @y@ is @7@, and the unnamed initializer @6@ initializes the next subobject, @z@.
    4040Later 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.
     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
    117118In \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
     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 to @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 invarients with 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}
     
    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@.
    368384This 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.
     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
     
    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}.
     398A type with at least one non-trivial constructor or destructor is henceforth referred to as a \emph{managed type}.
    383399In 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.
    384400
     
    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. % TODO: citation?
     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
     454% TODO: discuss Rust?
     455% Like \CC, Rust \cite{Rust} provides RAII through constructors and destructors.
     456% Smart pointers are deeply integrated in the Rust type-system.
    437457
    438458% D has constructors and destructors that are worth a mention (under classes) https://dlang.org/spec/spec.html
     
    444464Like 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.
    445465Since 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)
     466Finally, D provides a scope guard statement, which allows an arbitrary statement to be executed at normal scope exit with \emph{success}, at exceptional scope exit with \emph{failure}, or at normal and exceptional scope exit with \emph{exit}. % TODO: cite? https://dlang.org/spec/statement.html#ScopeGuardStatement
     467It has been shown that the \emph{exit} form of the scope guard statement can be implemented in a library in \CC \cite{ExceptSafe}.
     468
     469To provide managed types in \CFA, new kinds of constructors and destructors are added to C and discussed in Chapter 2.
    452470
    453471\section{Tuples}
    454472\label{s:Tuples}
    455473In 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.
     474In programming languages, tuples provide fixed-sized heterogeneous lists of elements.
    457475Many programming languages have tuple constructs, such as SETL, \KWC, ML, and Scala.
    458476
     
    462480Adding tuples to \CFA has previously been explored by Esteves \cite{Esteves04}.
    463481
    464 The design of tuples in \KWC took much of its inspiration from SETL.
     482The design of tuples in \KWC took much of its inspiration from SETL \cite{SETL}.
    465483SETL is a high-level mathematical programming language, with tuples being one of the primary data types.
    466484Tuples in SETL allow a number of operations, including subscripting, dynamic expansion, and multiple assignment.
     
    470488\begin{cppcode}
    471489tuple<int, int, int> triple(10, 20, 30);
    472 get<1>(triple); // access component 1 => 30
     490get<1>(triple); // access component 1 => 20
    473491
    474492tuple<int, double> f();
     
    482500Tuples are simple data structures with few specific operations.
    483501In 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.
     502Another 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.
    485503Tuples also support lexicographic comparisons, making it simple to write aggregate comparators using @std::tie@.
    486504
    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
     505There 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.
    488506\begin{cppcode}
    489507tuple<int, double> f();
     
    500518Structured bindings allow unpacking any struct with all public non-static data members into fresh local variables.
    501519The 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.
     520This 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.
    503521Furthermore, structured bindings are not a full replacement for @std::tie@, as it always declares new variables.
    504522
    505523Like \CC, D provides tuples through a library variadic template struct.
    506524In 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
     525% TODO: cite http://dlang.org/phobos/std_typecons.html
     526\begin{dcode}
    508527Tuple!(float, "x", float, "y") point2D;
    509 Tuple!(float, float) float2;  // different types
     528Tuple!(float, float) float2;  // different type from point2D
    510529
    511530point2D[0]; // access first element
     
    521540The @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.
    522541
    523 Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML.
     542Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML \cite{sml}.
    524543A function in SML always accepts exactly one argument.
    525544There are two ways to mimic multiple argument functions: the first through currying and the second by accepting tuple arguments.
     
    535554Tuples are a foundational tool in SML, allowing the creation of arbitrarily complex structured data types.
    536555
    537 Scala, like \CC, provides tuple types through the standard library.
     556Scala, like \CC, provides tuple types through the standard library \cite{Scala}.
    538557Scala provides tuples of size 1 through 22 inclusive through generic data structures.
    539558Tuples support named access and subscript access, among a few other operations.
     
    547566\end{scalacode}
    548567In 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.
     568The 22-element restriction is an odd and arbitrary choice, but in practice it does not cause problems since large tuples are uncommon.
    550569Subscript 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.
    551570The 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.
     
    553572
    554573
    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
     574\Csharp also has tuples, but has similarly strange limitations, allowing tuples of size up to 7 components. % TODO: cite https://msdn.microsoft.com/en-us/library/system.tuple(v=vs.110).aspx
    556575The officially supported workaround for this shortcoming is to nest tuples in the 8th component.
    557576\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.
    558577
    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.
     578In Python \cite{Python}, tuples are immutable sequences that provide packing and unpacking operations.
    562579While the tuple itself is immutable, and thus does not allow the assignment of components, there is nothing preventing a component from being internally mutable.
    563580The components of a tuple can be accessed by unpacking into multiple variables, indexing, or via field name, like D.
    564581Tuples support multiple assignment through a combination of packing and unpacking, in addition to the common sequence operations.
    565582
    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.
     583Swift \cite{Swift}, like D, provides named tuples, with components accessed by name, index, or via extractors.
    568584Tuples are primarily used for returning multiple values from a function.
    569585In Swift, @Void@ is an alias for the empty tuple, and there are no single element tuples.
     586
     587% TODO: this statement feels like it's too strong
     588Tuples as powerful as the above languages are added to C and discussed in Chapter 3.
    570589
    571590\section{Variadic Functions}
     
    641660A parameter pack matches 0 or more elements, which can be types or expressions depending on the context.
    642661Like 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.
     662That 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.
    644663
    645664Recent \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.
     
    672691Unfortunately, Java's use of nominal inheritance means that types must explicitly inherit from classes or interfaces in order to be considered a subclass.
    673692The combination of these two issues greatly restricts the usefulness of variadic functions in Java.
     693
     694Type-safe variadic functions are added to C and discussed in Chapter 4.
  • doc/rob_thesis/thesis-frontpgs.tex

    rae6cc8b r7493339  
    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

    rae6cc8b r7493339  
    7171\usepackage{textcomp}
    7272% \usepackage[utf8]{inputenc}
    73 \usepackage[latin1]{inputenc}
     73% \usepackage[latin1]{inputenc}
    7474\usepackage{fullpage,times,comment}
    7575% \usepackage{epic,eepic}
     
    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

    rae6cc8b r7493339  
    44
    55\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)
     6% TODO: no passing input parameters by assignment, instead will have reference types => this is not a very C-like model and greatly complicates syntax for likely little gain (and would cause confusion with already supported return-by-reference)
    97% 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
    108
     
    7371const char * str = "hello world";
    7472char ch;                            // pre-allocate return value
    75 int freq = most_frequent(str, &ch); // pass return value as parameter
     73int freq = most_frequent(str, &ch); // pass return value as out parameter
    7674printf("%s -- %d %c\n", str, freq, ch);
    7775\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.
     76Notably, 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.
    8077Also, 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.
    8178Furthermore, 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.
     
    109106}
    110107\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.
     108This 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.
    112109
    113110The addition of multiple-return-value functions necessitates a syntax for accepting multiple values at the call-site.
     
    136133In this case, there is only one option for a function named @most_frequent@ that takes a string as input.
    137134This 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.
     135There 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.
    139136This 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.
    140137
     
    148145The previous expression has 3 \emph{components}.
    149146Each 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 (...?)
    151147The order of evaluation of the components in a tuple expression is unspecified, to allow a compiler the greatest flexibility for program optimization.
    152148It is, however, guaranteed that each component of a tuple expression is evaluated for side-effects, even if the result is not used.
    153149Multiple-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.
    156150
    157151\subsection{Tuple Variables}
     
    166160These variables can be used in any of the contexts where a tuple expression is allowed, such as in the @printf@ function call.
    167161As 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.
     162One way to access the individual components is with a simple assignment, as in previous examples.
    169163\begin{cfacode}
    170164int freq;
     
    254248\label{s:TupleAssignment}
    255249An 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.
     250There 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.
    257251\begin{cfacode}
    258252int x;
     
    272266A mass assignment assigns the value $R$ to each $L_i$.
    273267For 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.
     268These 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.
    275269For 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@.
    276270On 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.
     
    288282These semantics allow cascading tuple assignment to work out naturally in any context where a tuple is permitted.
    289283These 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.
     284The \KWC semantics fix what was seen as a problem with assignment, wherein it can be used in many different locations, such as in function-call argument position. % TODO: remove??
    291285While 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.
    292286Furthermore, 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.
     
    315309void ?{}(S *, S);      // (4)
    316310
    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)
     311[S, S] x = [3, 6.28];  // uses (2), (3), specialized constructors
     312[S, S] y;              // uses (1), (1), default constructor
     313[S, S] z = x.0;        // uses (4), (4), copy constructor
    320314\end{cfacode}
    321315In 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)@.
     
    339333S s = t;
    340334\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.
     335The 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.
    342336
    343337\section{Member-Access Tuple Expression}
     
    354348Then the type of @a.[x, y, z]@ is @[T_x, T_y, T_z]@.
    355349
    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.).
     350Since 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.).
    357351\begin{cfacode}
    358352[int, int, long, double] x;
     
    384378Since \CFA permits these tuple-access expressions using structures, unions, and tuples, \emph{member tuple expression} or \emph{field tuple expression} is more appropriate.
    385379
    386 It could be possible to extend member-access expressions further.
     380It is possible to extend member-access expressions further.
    387381Currently, 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.
    388382In the interest of orthogonal design, \CFA could apply some meaning to the remaining combinations as well.
     
    403397One benefit of this interpretation is familiar, since it is extremely reminiscent of tuple-index expressions.
    404398On 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.
     399This 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.
     400
     401As for @z.y@, a one interpretation is to extend the meaning of member tuple expressions.
    408402That is, currently the tuple must occur as the member, i.e. to the right of the dot.
    409403Allowing 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.
    410404In 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.
     405It 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.
    412406Perhaps 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.
    413407The 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.
    414408
    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.
     409Supposing this feature works as described, it would be necessary to specify an ordering for the expansion of member-access expressions versus member-tuple expressions.
    416410\begin{cfacode}
    417411struct { int x, y; };
     
    426420\end{cfacode}
    427421Depending 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.
     422As such, a specific ordering would need to be imposed to make this feature useful.
     423Furthermore, 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.
     424
     425A second possibility is for \CFA to have named tuples, as they exist in Swift and D.
     426\begin{cfacode}
     427typedef [int x, int y] Point2D;
     428Point2D p1, p2;
     429p1.x + p1.y + p2.x + p2.y;
     430p1.0 + p1.1 + p2.0 + p2.1;  // equivalent
     431\end{cfacode}
     432In this simpler interpretation, a named tuple type carries with it a list of possibly empty identifiers.
     433This approach fits naturally with the named return-value feature, and would likely go a long way towards implementing it.
     434
     435Ultimately, the first two extensions introduce complexity into the model, with relatively little peceived benefit, and so were dropped from consideration.
     436Named tuples are a potentially useful addition to the language, provided they can be parsed with a reasonable syntax.
     437
    432438
    433439\section{Casting}
     
    442448(int)f();  // choose (2)
    443449\end{cfacode}
    444 Since casting is a fundamental operation in \CFA, casts should be given a meaningful interpretation in the context of tuples.
     450Since casting is a fundamental operation in \CFA, casts need to be given a meaningful interpretation in the context of tuples.
    445451Taking a look at standard C provides some guidance with respect to the way casts should work with tuples.
    446452\begin{cfacode}[numbers=left]
     
    448454void g();
    449455
    450 (void)f();
    451 (int)g();
     456(void)f();  // valid, ignore results
     457(int)g();   // invalid, void cannot be converted to int
    452458
    453459struct A { int x; };
    454 (struct A)f();
     460(struct A)f();  // invalid
    455461\end{cfacode}
    456462In C, line 4 is a valid cast, which calls @f@ and discards its result.
    457463On 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.
     464Finally, line 8 is also invalid, because in C casts only provide conversion between scalar types \cite[p.~91]{C11}.
     465For 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.
    460466
    461467Formally, 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$.
     
    509515\end{cfacode}
    510516Note 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]);
     517For example, these expressions also succeed and produce the same value.
     518A 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@.
     519\begin{cfacode}
     520([x.0, x.1]) + ([x.2, 10, 20, 30]);  // x + ([10, 20, 30])
     521x.0 + ([x.1, x.2, 10, 20, 30]);      // x + ([10, 20, 30])
    516522\end{cfacode}
    517523This 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.
     524Furthermore, these calls can be made ambiguous by adding seemingly different functions.
    519525\begin{cfacode}
    520526forall(otype T | { T ?+?(T, T); })
     
    524530\end{cfacode}
    525531It 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.
     532Still, these semantics are a deficiency of the current argument matching algorithm, and depending on the function, differing return values may not always be appropriate.
     533These issues could be rectified by applying an appropriate cost to the structuring and flattening conversions, which are currently 0-cost conversions.
    528534Care would be needed in this case to ensure that exact matches do not incur such a cost.
    529535\begin{cfacode}
     
    536542\end{cfacode}
    537543
    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).
     544Until 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).
    539545This decision presents a conflict with the flexibility of tuples.
    540546\subsection{Assertion Inference}
     
    617623In the call to @f@, the second and third argument components are structured into a tuple argument.
    618624
    619 Expressions which may contain side effects are made into \emph{unique expressions} before being expanded by the flattening conversion.
     625Expressions that may contain side effects are made into \emph{unique expressions} before being expanded by the flattening conversion.
    620626Each unique expression is assigned an identifier and is guaranteed to be executed exactly once.
    621627\begin{cfacode}
     
    624630g(h());
    625631\end{cfacode}
    626 Interally, this is converted to
     632Interally, this is converted to psuedo-\CFA
    627633\begin{cfacode}
    628634void g(int, double);
    629635[int, double] h();
    630 let unq<0> = f() : g(unq<0>.0, unq<0>.1);  // notation?
    631 \end{cfacode}
     636lazy [int, double] unq<0> = h();
     637g(unq<0>.0, unq<0>.1);
     638\end{cfacode}
     639That is, the function @h@ is evaluated lazily and its result is stored for subsequent accesses.
    632640Ultimately, unique expressions are converted into two variables and an expression.
    633641\begin{cfacode}
     
    638646[int, double] _unq0;
    639647g(
    640   (_unq0_finished_ ? _unq0 : (_unq0 = f(), _unq0_finished_ = 1, _unq0)).0,
    641   (_unq0_finished_ ? _unq0 : (_unq0 = f(), _unq0_finished_ = 1, _unq0)).1,
     648  (_unq0_finished_ ? _unq0 : (_unq0 = h(), _unq0_finished_ = 1, _unq0)).0,
     649  (_unq0_finished_ ? _unq0 : (_unq0 = h(), _unq0_finished_ = 1, _unq0)).1,
    642650);
    643651\end{cfacode}
     
    646654Every subsequent evaluation of the unique expression then results in an access to the stored result of the actual expression.
    647655
    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.
     656Currently, the \CFA translator has a very broad, imprecise definition of impurity (side-effects), where any function call is assumed to be impure.
     657This 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.
     658It is possible that lazy evaluation could be exposed to the user through a lazy keyword with little additional effort.
    651659
    652660Tuple member expressions are recursively expanded into a list of member access expressions.
     
    655663x.[0, 1.[0, 2]];
    656664\end{cfacode}
    657 Which becomes
     665which becomes
    658666\begin{cfacode}
    659667[x.0, [x.1.0, x.1.2]];
    660668\end{cfacode}
    661 Tuple member expressions also take advantage of unique expressions in the case of possible impurity.
     669Tuple-member expressions also take advantage of unique expressions in the case of possible impurity.
    662670
    663671Finally, the various kinds of tuple assignment, constructors, and destructors generate GNU C statement expressions.
     
    711719});
    712720\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.
     721A 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.
    714722$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.
    715723A nested statement expression is generated that performs the individual assignments and constructs the return value using the results of the individual assignments.
     
    785793The 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.
    786794There 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}
Note: See TracChangeset for help on using the changeset viewer.