Changeset 0111dc7


Ignore:
Timestamp:
Apr 13, 2017, 8:29:38 PM (4 years ago)
Author:
Rob Schluntz <rschlunt@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
1a16e9d
Parents:
c87eb50
Message:

penultimate thesis draft

Location:
doc/rob_thesis
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • doc/rob_thesis/conclusions.tex

    rc87eb50 r0111dc7  
    22\chapter{Conclusions}
    33%======================================================================
     4
     5Adding resource management and tuples to \CFA has been a challenging design, engineering, and implementation exercise.
     6On the surface, the work may appear as a rehash of similar mechanisms in \CC.
     7However, every added feature is different than its \CC counterpart, often with extended functionality, better integration with C and its programmers, and always supports separate compilation.
     8All of these new features are being used by the \CFA development-team to build the \CFA runtime system.
    49
    510\section{Constructors and Destructors}
     
    1823
    1924\section{Variadic Functions}
    20 Type-safe variadic functions of a similar feel to variadic templates are added to \CFA.
     25Type-safe variadic functions, with a similar feel to variadic templates, are added to \CFA.
    2126The new variadic functions can express complicated recursive algorithms.
    2227Unlike variadic templates, it is possible to write @new@ as a library routine and to separately compile @ttype@ polymorphic functions.
     
    2934The design space is currently being explored with the goal of finding an alternative to move semantics that provides necessary performance benefits, while reducing the amount of repetition required to create a new type, along with the cognitive burden placed on the user.
    3035
     36% One technique being evaluated is whether named return-values can be used to eliminate unnecessary temporaries \cite{Buhr94a}.
     37% For example,
     38% \begin{cfacode}
     39% struct A { ... };
     40% [A x] f(A x);
     41% [A y] g(A y);
     42% [A z] h(A z);
     43
     44% struct A a1, a2;
     45% a2 = h(g(f(a1)));
     46% \end{cfacode}
     47% Here, since both @f@'s argument and return value have the same name and type, the compiler can infer that @f@ returns its argument.
     48% With this knowledge, the compiler can reuse the storage for the argument to @f@ as the argument to @g@.  % TODO: cite Till thesis?
     49
    3150Exception handling is among the features expected to be added to \CFA in the near future.
    3251For exception handling to properly interact with the rest of the language, it must ensure all RAII guarantees continue to be met.
     
    4463This mechanism is known and understood by GCC, so that the destructor is properly called in any situation where a variable goes out of scope, including function returns, branches, and built-in GCC exception handling mechanisms using libunwind.
    4564
    46 A caveat of this approach is that the @cleanup@ attribute only permits a name that refers to a function that consumes a single argument of type @T *@ for a variable of type @T@.
    47 This means that any destructor that consumes multiple arguments (\eg, because it is polymorphic) or any destructor that is a function pointer (\eg, because it is an assertion parameter) must be called through a local thunk.
     65A caveat of this approach is that the @cleanup@ attribute only permits a function that consumes a single argument of type @T *@ for a variable of type @T@.
     66This restriction means that any destructor that consumes multiple arguments (\eg, because it is polymorphic) or any destructor that is a function pointer (\eg, because it is an assertion parameter) must be called through a local thunk.
    4867For example,
    4968\begin{cfacode}
     
    5271  T x;
    5372};
    54 forall(otype T) void ^?{}(Box(T) * x);
     73forall(otype T) void ^?{}(Box(T) * x); // has implicit parameters
    5574
    5675forall(otype T)
    5776void f(T x) {
    58   T y = x;
    59   Box(T) z = { x };
     77  T y = x;  // destructor is a function-pointer parameter
     78  Box(T) z = { x }; // destructor has multiple parameters
    6079}
    6180\end{cfacode}
     
    148167void _dtor_S(struct S *);
    149168
    150 struct __tmp_bundle_S {
     169struct _tmp_bundle_S {
    151170  bool valid;
    152171  struct S value;
    153172};
    154173
    155 void _dtor_tmpS(struct __tmp_bundle_S * ret) {
     174void _dtor_tmpS(struct _tmp_bundle_S * ret) {
    156175  if (ret->valid) {
    157176    _dtor_S(&ret->value);
     
    160179
    161180{
    162   __attribute__((cleanup(_dtor_tmpS))) struct __tmp_bundle_S _tmp1 = { 0 };
    163   __attribute__((cleanup(_dtor_tmpS))) struct __tmp_bundle_S _tmp2 = { 0 };
    164   __attribute__((cleanup(_dtor_tmpS))) struct __tmp_bundle_S _tmp3 = { 0 };
     181  __attribute__((cleanup(_dtor_tmpS))) struct _tmp_bundle_S _tmp1 = { 0 };
     182  __attribute__((cleanup(_dtor_tmpS))) struct _tmp_bundle_S _tmp2 = { 0 };
     183  __attribute__((cleanup(_dtor_tmpS))) struct _tmp_bundle_S _tmp3 = { 0 };
    165184  _tmp2.value = g(
    166185    (_ctor_S(
     
    189208struct S { T x; };
    190209\end{cfacode}
    191 will only auto-generate the default constructor for @S@, since the member @x@ is missing the other 3 special functions.
     210only auto-generates the default constructor for @S@, since the member @x@ is missing the other 3 special functions.
    192211Once deleted functions have been added, function generation can make use of this information to disable generation of special functions when a member has a deleted function.
    193212For example,
     
    210229struct B { ... };
    211230struct A {
    212         B x, y, z;
     231  B x, y, z;
    213232};
    214233void ?{}(A * a, B x) {
    215         // y, z implicitly default constructed
    216         (&a->x){ ... }; // explicitly construct x
     234  // y, z implicitly default constructed
     235  (&a->x){ ... }; // explicitly construct x
    217236} // constructs an entire A
    218237void ?{}(A * a) {
    219         (&a->y){}; // initialize y
    220         a{ (B){ ... } }; // forwarding constructor call
    221                          // initializes entire object, including y
     238  (&a->y){}; // initialize y
     239  a{ (B){ ... } }; // forwarding constructor call
     240                   // initializes entire object, including y
    222241}
    223242\end{cfacode}
    224243
    225244Finally, while constructors provide a mechanism for establishing invariants, there is currently no mechanism for maintaining invariants without resorting to opaque types.
    226 That is, structure fields can be accessed and modified by any block of code without restriction, so while it's possible to ensure that an object is initially set to a valid state, it isn't possible to ensure that it remains in a consistent state throughout its lifetime.
     245That is, structure fields can be accessed and modified by any block of code without restriction, so while it is possible to ensure that an object is initially set to a valid state, it is not possible to ensure that it remains in a consistent state throughout its lifetime.
    227246A popular technique for ensuring consistency in object-oriented programming languages is to provide access modifiers such as @private@, which provides compile-time checks that only privileged code accesses private data.
    228247This approach could be added to \CFA, but it requires an idiomatic way of specifying what code is privileged.
     
    239258\subsection{Variadic Functions}
    240259Use of @ttype@ functions currently relies heavily on recursion.
    241 \CC has opened variadic templates up so that recursion isn't strictly necessary in some cases, and it would be interesting to see if any such cases can be applied to \CFA.
    242 
    243 \CC supports variadic templated data types, making it possible to express arbitrary length tuples, arbitrary parameter function objects, and more with generic types.
    244 Currently, \CFA does not support @ttype@-parameter generic types, though there does not appear to be a technical reason that it cannot.
     260\CC has opened variadic templates up so that recursion is not strictly necessary in some cases, and it would be interesting to see if any such cases can be applied to \CFA.
     261
     262\CC supports variadic templated data-types, making it possible to express arbitrary length tuples, arbitrary parameter function objects, and more with generic types.
     263Currently, \CFA does not support @ttype@-parameter generic-types, though there does not appear to be a technical reason that it cannot.
    245264Notably, opening up support for this makes it possible to implement the exit form of scope guard (see section \ref{s:ResMgmt}), making it possible to call arbitrary functions at scope exit in idiomatic \CFA.
  • doc/rob_thesis/ctordtor.tex

    rc87eb50 r0111dc7  
    291291struct X *_tmp_ctor;
    292292struct X *x = ?{}(  // construct result of malloc
    293   _tmp_ctor=malloc_T(sizeof(struct X), _Alignof(struct X)), // store result of malloc
     293  _tmp_ctor=malloc_T( // store result of malloc
     294    sizeof(struct X),
     295    _Alignof(struct X)
     296  ),
    294297  1.5
    295298), _tmp_ctor; // produce constructed result of malloc
     
    500503  S s0, s1 = { 0 }, s2 = { 0, 2 }, s3 = s2;  // okay
    501504  {
    502     void ?{}(S * s, int i) { s->x = i*2; } // locally hide autogen constructors
     505    void ?{}(S * s, int i) { s->x = i*2; } // locally hide autogen ctors
    503506    S s4;  // error, no default constructor
    504507    S s5 = { 3 };  // okay, local constructor
     
    577580As 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.
    578581
     582\begin{sloppypar}
    579583In addition, constructor calls do not support unnamed nesting.
    580584\begin{cfacode}
     
    594598That 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@.
    595599In 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.
     600\end{sloppypar}
    596601
    597602More precisely, constructor calls cannot have a nesting depth greater than the number of array dimensions in the type of the initialized object, plus one.
     
    877882This means that in general, function signatures would have to be rewritten, and in a select few cases the signatures would not be rewritten.
    878883\begin{cfacode}
    879 __attribute__((manageable)) struct A { ... };   // can declare constructors
    880 __attribute__((unmanageable)) struct B { ... }; // cannot declare constructors
    881 struct C { ... };                               // can declare constructors
     884__attribute__((manageable)) struct A { ... };   // can declare ctors
     885__attribute__((unmanageable)) struct B { ... }; // cannot declare ctors
     886struct C { ... };                               // can declare ctors
    882887
    883888A f();  // rewritten void f(A *);
     
    889894Furthermore, no restrictions would need to be placed on whether objects can be constructed.
    890895\begin{cfacode}
    891 __attribute__((identifiable)) struct A { ... };  // can declare constructors
    892 struct B { ... };                                // can declare constructors
     896__attribute__((identifiable)) struct A { ... };  // can declare ctors
     897struct B { ... };                                // can declare ctors
    893898
    894899A f();  // rewritten void f(A *);
  • doc/rob_thesis/intro.tex

    rc87eb50 r0111dc7  
    326326Invariants help a programmer to reason about code correctness and prove properties of programs.
    327327
     328\begin{sloppypar}
    328329In object-oriented programming languages, type invariants are typically established in a constructor and maintained throughout the object's lifetime.
    329330These assertions are typically achieved through a combination of access-control modifiers and a restricted interface.
    330331Typically, 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.
    331332It 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.
     333\end{sloppypar}
    332334
    333335In C, the @assert@ macro is often used to ensure invariants are true.
     
    617619Tuples support named access and subscript access, among a few other operations.
    618620\begin{scalacode}
    619 val a = new Tuple3[Int, String, Double](0, "Text", 2.1) // explicit creation
    620 val b = (6, 'a', 1.1f)       // syntactic sugar for Tuple3[Int, Char, Float]
     621val a = new Tuple3(0, "Text", 2.1) // explicit creation
     622val b = (6, 'a', 1.1f)       // syntactic sugar: Tuple3[Int, Char, Float]
    621623val (i, _, d) = triple       // extractor syntax, ignore middle element
    622624
     
    661663Still, @printf@ is extremely limited, since the format codes are specified by the C standard, meaning users cannot define their own format codes to extend @printf@ for new data types or new formatting rules.
    662664
     665\begin{sloppypar}
    663666C provides manipulation of variadic arguments through the @va_list@ data type, which abstracts details of the manipulation of variadic arguments.
    664667Since the variadic arguments are untyped, it is up to the function to interpret any data that is passed in.
     
    695698Furthermore, if the user makes a mistake, compile-time checking is typically restricted to standard format codes and their corresponding types.
    696699In general, this means that C's variadic functions are not type-safe, making them difficult to use properly.
     700\end{sloppypar}
    697701
    698702% When arguments are passed to a variadic function, they undergo \emph{default argument promotions}.
  • doc/rob_thesis/thesis-frontpgs.tex

    rc87eb50 r0111dc7  
    2424
    2525        \Large
    26         Rob Schluntz \\
     26        Robert Schluntz \\
    2727
    2828        \vspace*{3.0cm}
     
    4343        \vspace*{1.0cm}
    4444
    45         \copyright\ Rob Schluntz 2017 \\
     45        \copyright\ Robert Schluntz 2017 \\
    4646        \end{center}
    4747\end{titlepage}
     
    7777
    7878\CFA is a modern, non-object-oriented extension of the C programming language.
    79 This thesis introduces two fundamental language features: tuples and constructors/destructors, as well as improved variadic functions.
     79This thesis addresses several critical deficiencies of C, notably: resource management, a limited function-return mechanism, and unsafe variadic functions.
     80To solve these problems, two fundamental language features are introduced: tuples and constructors/destructors.
    8081While these features exist in prior programming languages, the contribution of this work is engineering these features into a highly complex type system.
     82C is an established language with a dedicated user-base.
     83An important goal is to add new features in a way that naturally feels like C, to appeal to this core user-base, and due to huge amounts of legacy code, maintaining backwards compatibility is crucial.
    8184
    8285\cleardoublepage
    8386%\newpage
    8487
    85 % A C K N O W L E D G E M E N T S
    86 % -------------------------------
     88% % A C K N O W L E D G E M E N T S
     89% % -------------------------------
    8790
    88 \begin{center}\textbf{Acknowledgements}\end{center}
     91% \begin{center}\textbf{Acknowledgements}\end{center}
    8992
    90 % I would like to thank all the little people who made this possible.
    91 TODO
    92 \cleardoublepage
    93 %\newpage
     93% % I would like to thank all the little people who made this possible.
     94% TODO
     95% \cleardoublepage
     96% %\newpage
    9497
    95 % D E D I C A T I O N
    96 % -------------------
     98% % D E D I C A T I O N
     99% % -------------------
    97100
    98 \begin{center}\textbf{Dedication}\end{center}
     101% \begin{center}\textbf{Dedication}\end{center}
    99102
    100 % This is dedicated to the one I love.
    101 TODO
    102 \cleardoublepage
    103 %\newpage
     103% % This is dedicated to the one I love.
     104% TODO
     105% \cleardoublepage
     106% %\newpage
    104107
    105108% T A B L E   O F   C O N T E N T S
     
    119122%\newpage
    120123
    121 % L I S T   O F   F I G U R E S
    122 % -----------------------------
    123 \addcontentsline{toc}{chapter}{List of Figures}
    124 \listoffigures
    125 \cleardoublepage
    126 \phantomsection         % allows hyperref to link to the correct page
    127 %\newpage
     124% % L I S T   O F   F I G U R E S
     125% % -----------------------------
     126% \addcontentsline{toc}{chapter}{List of Figures}
     127% \listoffigures
     128% \cleardoublepage
     129% \phantomsection               % allows hyperref to link to the correct page
     130% %\newpage
    128131
    129132% L I S T   O F   S Y M B O L S
  • doc/rob_thesis/thesis.tex

    rc87eb50 r0111dc7  
    136136    pdffitwindow=false,     % window fit to page when opened
    137137    pdfstartview={FitH},    % fits the width of the page to the window
    138     pdftitle={uWaterloo\ LaTeX\ Thesis\ Template},    % title: CHANGE THIS TEXT!
     138    pdftitle={Resource Management and Tuples in \CFA},    % title: CHANGE THIS TEXT!
    139139    pdfauthor={Rob Schluntz},    % author: CHANGE THIS TEXT! and uncomment this line
    140140%    pdfsubject={Subject},  % subject: CHANGE THIS TEXT! and uncomment this line
  • doc/rob_thesis/tuples.tex

    rc87eb50 r0111dc7  
    209209In the call to @f@, @x@ is implicitly flattened so that the components of @x@ are passed as the two arguments to @f@.
    210210For the call to @g@, the values @y@ and @10@ are structured into a single argument of type @[int, int]@ to match the type of the parameter of @g@.
    211 Finally, in the call to @h@, @y@ is flattened to yield an argument list of length 3, of which the first component of @x@ is passed as the first parameter of @h@, and the second component of @x@ and @y@ are structured into the second argument of type @[int, int]@.
     211Finally, in the call to @h@, @x@ is flattened to yield an argument list of length 3, of which the first component of @x@ is passed as the first parameter of @h@, and the second component of @x@ and @y@ are structured into the second argument of type @[int, int]@.
    212212The flexible structure of tuples permits a simple and expressive function-call syntax to work seamlessly with both single- and multiple-return-value functions, and with any number of arguments of arbitrarily complex structure.
    213213
     
    675675// [x, y, z] = 1.5;
    676676_tuple3_(int, double, int) _tmp_stmtexpr_ret0;
    677 ({
     677({ // GNU C statement expression
    678678  // assign LHS address temporaries
    679679  int *__massassign_L0 = &x;    // ?{}
     
    690690    int *__multassign_L2 = (int *)&_tmp_stmtexpr_ret0.2;       // ?{}
    691691
    692     // assign RHS value temporaries and perform mass assignment to L0, L1, L2
    693     int __multassign_R0 = (*__massassign_L0=(int)__massassign_R0);   // ?{}
    694     double __multassign_R1 = (*__massassign_L1=__massassign_R0);     // ?{}
    695     int __multassign_R2 = (*__massassign_L2=(int)__massassign_R0);   // ?{}
     692    // assign RHS value temporaries and mass-assign to L0, L1, L2
     693    int __multassign_R0 = (*__massassign_L0=(int)__massassign_R0); // ?{}
     694    double __multassign_R1 = (*__massassign_L1=__massassign_R0);   // ?{}
     695    int __multassign_R2 = (*__massassign_L2=(int)__massassign_R0); // ?{}
    696696
    697697    // perform construction of statement expr return variable using
     
    742742      _tmp_cp_ret0 :
    743743      (_tmp_cp_ret0=f(), _unq0_finished_=1, _tmp_cp_ret0)).1; // ?{}
    744   ({ // tuple destruction - destruct f() return temporary - tuple destruction
     744  ({ // tuple destruction - destruct f() return temporary
    745745    // assign LHS address temporaries
    746746    double *__massassign_L3 = (double *)&_tmp_cp_ret0.0;  // ?{}
     
    758758    int *__multassign_L5 = (int *)&_tmp_stmtexpr_ret0.2;       // ?{}
    759759
    760     // assign RHS value temporaries and perform multiple assignment to L0, L1, L2
     760    // assign RHS value temporaries and multiple-assign to L0, L1, L2
    761761    int __multassign_R3 = (*__multassign_L0=(int)__multassign_R0);  // ?{}
    762762    double __multassign_R4 = (*__multassign_L1=__multassign_R1);    // ?{}
  • doc/rob_thesis/variadic.tex

    rc87eb50 r0111dc7  
    418418  *_p0; // ^?{}
    419419}
    420 void _thunk4(struct _conc__tuple2_0 _p0){ // void print([int, const char *])
     420void _thunk4(struct _conc__tuple2_0 _p0){
     421        // void print([int, const char *])
    421422  struct _tuple1_ { // _tuple1_(T0)
    422423    void *field_0;
     
    428429    print_string(_pp0.field_0);  // print(rest.0)
    429430  }
    430   void _adapter_i_pii_(void (*_adaptee)(), void *_ret, void *_p0, void *_p1){
     431  void _adapter_i_pii_(
     432    void (*_adaptee)(),
     433    void *_ret,
     434    void *_p0,
     435    void *_p1
     436  ){
    431437    *(int *)_ret=((int (*)(int *, int))_adaptee)(_p0, *(int *)_p1);
    432438  }
     
    438444  }
    439445  void _adapter_tuple1_5_(void (*_adaptee)(), void *_p0){
    440     ((void (*)(struct _conc__tuple1_1 ))_adaptee)(*(struct _conc__tuple1_1 *)_p0);
     446    ((void (*)(struct _conc__tuple1_1 ))_adaptee)(
     447      *(struct _conc__tuple1_1 *)_p0
     448    );
    441449  }
    442450  print_variadic(
     
    449457    sizeof(struct _conc__tuple1_1),
    450458    __alignof__(struct _conc__tuple1_1),
    451     (void *(*)(void *, void *))_assign_i,     // int ?=?(int *, int)
    452     (void (*)(void *))_ctor_i,                // void ?{}(int *)
    453     (void (*)(void *, void *))_ctor_ii,       // void ?{}(int *, int)
    454     (void (*)(void *))_dtor_ii,               // void ^?{}(int *)
    455     (void (*)(void *))print_int,              // void print(int)
    456     (void (*)(void *))&_thunk5,               // void print([const char *])
    457     &_p0.field_0,                             // rest.0
    458     &(struct _conc__tuple1_1 ){ _p0.field_1 } // [rest.1]
     459    (void *(*)(void *, void *))_assign_i,    // int ?=?(int *, int)
     460    (void (*)(void *))_ctor_i,               // void ?{}(int *)
     461    (void (*)(void *, void *))_ctor_ii,      // void ?{}(int *, int)
     462    (void (*)(void *))_dtor_ii,              // void ^?{}(int *)
     463    (void (*)(void *))print_int,             // void print(int)
     464    (void (*)(void *))&_thunk5,              // void print([const char *])
     465    &_p0.field_0,                            // rest.0
     466    &(struct _conc__tuple1_1 ){ _p0.field_1 }// [rest.1]
    459467  );
    460468}
     
    480488}
    481489void _adapter_pstring_string(void (*_adaptee)(), void *_p0, void *_p1){
    482   ((void (*)(const char **, const char *))_adaptee)(_p0, *(const char **)_p1);
     490  ((void (*)(const char **, const char *))_adaptee)(
     491    _p0,
     492    *(const char **)_p1
     493  );
    483494}
    484495void _adapter_string_(void (*_adaptee)(), void *_p0){
     
    486497}
    487498void _adapter_tuple2_0_(void (*_adaptee)(), void *_p0){
    488   ((void (*)(struct _conc__tuple2_0 ))_adaptee)(*(struct _conc__tuple2_0 *)_p0);
     499  ((void (*)(struct _conc__tuple2_0 ))_adaptee)(
     500    *(struct _conc__tuple2_0 *)_p0
     501  );
    489502}
    490503print_variadic(
     
    497510  sizeof(struct _conc__tuple2_0 ),
    498511  __alignof__(struct _conc__tuple2_0 ),
    499   (void *(*)(void *, void *))&_thunk0, // const char * ?=?(const char **, const char *)
    500   (void (*)(void *))&_thunk1,          // void ?{}(const char **)
    501   (void (*)(void *, void *))&_thunk2,  // void ?{}(const char **, const char *)
    502   (void (*)(void *))&_thunk3,          // void ^?{}(const char **)
    503   (void (*)(void *))print_string,      // void print(const char *)
    504   (void (*)(void *))&_thunk4,          // void print([int, const char *])
     512  &_thunk0,    // const char * ?=?(const char **, const char *)
     513  &_thunk1,     // void ?{}(const char **)
     514  &_thunk2,     // void ?{}(const char **, const char *)
     515  &_thunk3,     // void ^?{}(const char **)
     516  print_string, // void print(const char *)
     517  &_thunk4,     // void print([int, const char *])
    505518  &_temp0,                             // "x = "
    506519  (({  // copy construct tuple argument to print
Note: See TracChangeset for help on using the changeset viewer.