Changeset 7493339 for doc/rob_thesis
- Timestamp:
- Apr 3, 2017, 7:04:30 PM (8 years ago)
- 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
- Location:
- doc/rob_thesis
- Files:
-
- 7 added
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/rob_thesis/conclusions.tex
rae6cc8b r7493339 4 4 5 5 Conclusion 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 2 2 \chapter{Constructors and Destructors} 3 3 %====================================================================== 4 5 % TODO: discuss move semantics; they haven't been implemented, but could be. Currently looking at alternative models. (future work)6 4 7 5 % TODO: as an experiment, implement Andrei Alexandrescu's ScopeGuard http://www.drdobbs.com/cpp/generic-change-the-way-you-write-excepti/184403758?pgno=2 … … 553 551 % // and so on 554 552 555 556 557 % TODO: talk somewhere about compound literals?558 559 553 Since \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.554 As well, \CFA is not an object-oriented programming language, i.e., structures cannot have routine members. 561 555 Nevertheless, one important goal is to reduce programming complexity and increase safety. 562 556 To 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 refactor565 % Manual resource management is difficult.566 % Part of the difficulty results from not having any guarantees about the current state of an object.567 % Objects can be internally composed of pointers that may reference resources which may or may not need to be manually released, and keeping track of that state for each object can be difficult for the end user.568 569 % Constructors and destructors provide a mechanism to bookend the lifetime of an object, allowing the designer of a type to establish invariants for objects of that type.570 % Constructors guarantee that object initialization code is run before the object can be used, while destructors provide a mechanism that is guaranteed to be run immediately before an object's lifetime ends.571 % Constructors and destructors can help to simplify resource management when used in a disciplined way.572 % In particular, when all resources are acquired in a constructor, and all resources are released in a destructor, no resource leaks are possible.573 % This pattern is a popular idiom in several languages, such as \CC, known as RAII (Resource Acquisition Is Initialization).574 557 575 558 This chapter details the design of constructors and destructors in \CFA, along with their current implementation in the translator. … … 592 575 Next, @x@ is assigned the value of @y@. 593 576 In 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).577 The key difference between assignment and initialization being that assignment occurs on a live object (i.e., an object that contains data). 595 578 It 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 579 Use of uninitialized variables yields undefined behaviour, which is a common source of errors in C programs. 580 581 Declaration initialization is insufficient, because it permits uninitialized variables to exist and because it does not allow for the insertion of arbitrary code before a variable is live. 582 Many C compilers give good warnings for uninitialized variables most of the time, but they cannot in all cases. 583 \begin{cfacode} 584 int f(int *); // output parameter: never reads, only writes 585 int g(int *); // input parameter: never writes, only reads, 586 // so requires initialized variable 603 587 604 588 int x, y; 605 589 f(&x); // okay - only writes to x 606 g(&y); // will usey uninitialized607 \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 bethe case in \CFA.590 g(&y); // uses y uninitialized 591 \end{cfacode} 592 Other 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. 609 593 610 594 In C, constructors and destructors are often mimicked by providing routines that create and teardown objects, where the teardown function is typically only necessary if the type modifies the execution environment. … … 614 598 }; 615 599 struct array_int create_array(int sz) { 616 return (struct array_int) { malloc(sizeof(int)*sz) };600 return (struct array_int) { calloc(sizeof(int)*sz) }; 617 601 } 618 602 void destroy_rh(struct resource_holder * rh) { … … 639 623 640 624 In \CFA, a constructor is a function with the name @?{}@. 625 Like other operators in \CFA, the name represents the syntax used to call the constructor, e.g., @struct S = { ... };@. 641 626 Every 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). 642 627 The @this@ parameter must have a pointer type, whose base type is the type of object that the function constructs. … … 655 640 656 641 In 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 .642 It 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. 658 643 In \CFA, the user can define a constructor to handle initialization of @Array@ objects. 659 644 … … 671 656 This 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. 672 657 This 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.658 In other words, a default constructor is a constructor that takes a single argument: the @this@ parameter. 674 659 675 660 In \CFA, a destructor is a function much like a constructor, except that its name is \lstinline!^?{}!. … … 680 665 } 681 666 \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. 667 The destructor is automatically called at deallocation for all objects of type @Array@. 668 Hence, the memory associated with an @Array@ is automatically freed when the object's lifetime ends. 683 669 The exact guarantees made by \CFA with respect to the calling of destructors are discussed in section \ref{sub:implicit_dtor}. 684 670 … … 691 677 \end{cfacode} 692 678 By 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@.679 On line 2, @z@ is initialized with the value of @x@, while on line 3, @y@ is assigned the value of @x@. 694 680 The 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. 695 681 In particular, these cases cannot be handled the same way because in the former case @z@ does not currently own an array, while @y@ does. … … 712 698 The first function is called a \emph{copy constructor}, because it constructs its argument by copying the values from another object of the same type. 713 699 The second function is the standard copy-assignment operator. 714 The se four functions are special in that they control the state of most objects.700 The four functions (default constructor, destructor, copy constructor, and assignment operator) are special in that they safely control the state of most objects. 715 701 716 702 It is possible to define a constructor that takes any combination of parameters to provide additional initialization options. … … 729 715 Array x, y = { 20, 0xdeadbeef }, z = y; 730 716 \end{cfacode} 717 731 718 In \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. 732 719 One 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. … … 748 735 Destructors are implicitly called in reverse declaration-order so that objects with dependencies are destructed before the objects they are dependent on. 749 736 750 \subsection{ Syntax}751 \label{sub:syntax} % TODO: finish this section737 \subsection{Calling Syntax} 738 \label{sub:syntax} 752 739 There are several ways to construct an object in \CFA. 753 740 As previously introduced, every variable is automatically constructed at its definition, which is the most natural way to construct an object. … … 773 760 A * y = malloc(); // copy construct: ?{}(&y, malloc()) 774 761 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 778 765 ^?{}(y); // explicit destroy y 779 766 … … 781 768 // implicit ^?{}(&x); 782 769 \end{cfacode} 783 Calling a constructor or destructor directly is a flexible feature that allows complete control over the management of a piece ofstorage.770 Calling a constructor or destructor directly is a flexible feature that allows complete control over the management of storage. 784 771 In particular, constructors double as a placement syntax. 785 772 \begin{cfacode} … … 804 791 Finally, constructors and destructors support \emph{operator syntax}. 805 792 Like 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. 793 This syntactic form is similar to the new initialization syntax in \CCeleven, except that it is used in expression contexts, rather than declaration contexts. 806 794 \begin{cfacode} 807 795 struct A { ... }; … … 822 810 Destructor operator syntax is actually an statement, and requires parentheses for symmetry with constructor syntax. 823 811 812 One of these three syntactic forms should appeal to either C or \CC programmers using \CFA. 813 824 814 \subsection{Function Generation} 825 815 In \CFA, every type is defined to have the core set of four functions described previously. … … 833 823 There are several options for user-defined types: structures, unions, and enumerations. 834 824 To 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 continueto work correctly in every context where \CFA expects these functions to exist, since they are generated for every complete type.825 By 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. 836 826 837 827 The generated functions for enumerations are the simplest. 838 828 Since enumerations in C are essentially just another integral type, the generated functions behave in the same way that the builtin functions for the basic types work. 839 % TODO: examples for enums840 829 For example, given the enumeration 841 830 \begin{cfacode} … … 860 849 \end{cfacode} 861 850 In 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.851 The existing generated routines are sufficient to express this restriction, since they are currently set up to take in values of that enumeration type. 863 852 Changes 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.853 In 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. 865 854 866 855 For structures, the situation is more complicated. 867 Fora 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 constructthem, and so on.869 For example given the structdefinition856 Given 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$@. 857 That is, a default constructor for @S@ default constructs the members of @S@, the copy constructor copy constructs them, and so on. 858 For example, given the structure definition 870 859 \begin{cfacode} 871 860 struct A { … … 893 882 } 894 883 \end{cfacode} 895 It is important to note that the destructors are called in reverse declaration order to resolveconflicts in the event there are dependencies among members.884 It is important to note that the destructors are called in reverse declaration order to prevent conflicts in the event there are dependencies among members. 896 885 897 886 In 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 memberlist.887 The field constructors are constructors that consume a prefix of the structure's member-list. 899 888 That 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 struct s 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 }@.889 The 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 }@. 901 890 Extending the previous example, the following constructors are implicitly generated for @A@. 902 891 \begin{cfacode} … … 911 900 \end{cfacode} 912 901 913 For unions, the default constructor and destructor do nothing, as it is not obvious which member if anyshould be constructed.902 For unions, the default constructor and destructor do nothing, as it is not obvious which member, if any, should be constructed. 914 903 For copy constructor and assignment operations, a bitwise @memcpy@ is applied. 915 904 In 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. … … 947 936 948 937 % 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 anyif 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.938 In \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. 950 939 This restriction could easily be added into \CFA once \emph{deleted} functions are added. 951 940 … … 970 959 Here, @&s@ and @&s2@ are cast to unqualified pointer types. 971 960 This 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. 961 This applies only to implicitly generated constructor calls. 962 Hence, explicitly re-initializing qualified objects with a constructor requires an explicit cast. 963 964 As discussed in Section \ref{sub:c_background}, compound literals create unnamed objects. 965 This mechanism can continue to be used seamlessly in \CFA with managed types to create temporary objects. 966 The 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. 967 For example, 968 \begin{cfacode} 969 struct A { int x; }; 970 void ?{}(A *, int, int); 971 { 972 int x = (A){ 10, 20 }.x; 973 } 974 \end{cfacode} 975 is equivalent to 976 \begin{cfacode} 977 struct A { int x, y; }; 978 void ?{}(A *, int, int); 979 { 980 A _tmp; 981 ?{}(&_tmp, 10, 20); 982 int x = _tmp.x; 983 ^?{}(&tmp); 984 } 985 \end{cfacode} 973 986 974 987 Unlike \CC, \CFA provides an escape hatch that allows a user to decide at an object's definition whether it should be managed or not. … … 984 997 A a2 @= { 0 }; // unmanaged 985 998 \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. 999 In 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. 1000 Instead, @a2->x@ is initialized to @0@ as if it were a C object, because of the explicit initializer. 989 1001 990 1002 In addition to freedom, \ateq provides a simple path to migrating legacy C code to Cforall, in that objects can be moved from C-style initialization to \CFA gradually and individually. … … 992 1004 It is recommended that most objects be managed by sensible constructors and destructors, except where absolutely necessary. 993 1005 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 unlessthe 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 Th is 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??1006 When 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. 1007 Furthermore, if the user declares any constructor, then the intrinsic/generated default constructor is also hidden, precluding default construction. 1008 These 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++}. 997 1009 \begin{cfacode} 998 1010 struct S { int x, y; }; … … 1001 1013 S s0, s1 = { 0 }, s2 = { 0, 2 }, s3 = s2; // okay 1002 1014 { 1003 void ?{}(S * s, int i) { s->x = i*2; } 1015 void ?{}(S * s, int i) { s->x = i*2; } // locally hide autogen constructors 1004 1016 S s4; // error 1005 1017 S s5 = { 3 }; // okay … … 1058 1070 } // z, y, w implicitly destructed, in this order 1059 1071 \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).1072 If at any point, the @this@ parameter is passed directly as the target of another constructor, then it is assumed that constructor handles the initialization of all of the object's members and no implicit constructor calls are added. % TODO: this is basically always wrong. if anything, I should check that such a constructor does not initialize any members, otherwise it'll always initialize the member twice (once locally, once by the called constructor). This might be okay in some situations, but it deserves a warning at the very least. 1061 1073 To override this rule, \ateq can be used to force the translator to trust the programmer's discretion. 1062 1074 This form of \ateq is not yet implemented. … … 1064 1076 Despite great effort, some forms of C syntax do not work well with constructors in \CFA. 1065 1077 In 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.1068 1078 \begin{cfacode} 1069 1079 // all legal forward declarations in C … … 1076 1086 f(b:10, a:20, c:30); // which parameter is which? 1077 1087 \end{cfacode} 1088 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. 1089 Furthermore, a function prototype can be repeated an arbitrary number of times, each time using different names. 1078 1090 As 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 1092 In addition, constructor calls do not support unnamed nesting. 1093 \begin{cfacode} 1094 struct B { int x; }; 1095 struct C { int y; }; 1096 struct A { B b; C c; }; 1097 void ?{}(A *, B); 1098 void ?{}(A *, C); 1099 1100 A a = { 1101 { 10 }, // construct B? - invalid 1102 }; 1103 \end{cfacode} 1104 In C, nesting initializers means that the programmer intends to initialize subobjects with the nested initializers. 1105 The reason for this omission is to both simplify the mental model for using constructors, and to make initialization simpler for the expression resolver. 1106 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. 1107 That 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@. 1108 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. 1109 1110 More precisely, constructor calls cannot have a nesting depth greater than the number of array components in the type of the initialized object, plus one. 1082 1111 For example, 1083 1112 \begin{cfacode} … … 1098 1127 % TODO: in CFA if the array dimension is empty, no object constructors are added -- need to fix this. 1099 1128 The 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 1105 1130 It should be noted that unmanaged objects can still make use of designations and nested initializers in \CFA. 1131 It 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. 1106 1132 1107 1133 \subsection{Implicit Destructors} … … 1130 1156 \end{cfacode} 1131 1157 1132 %% having this feels excessive, but it's here if necessary1133 % 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 1173 1158 The next example illustrates the use of simple continue and break statements and the manner that they interact with implicit destructors. 1174 1159 \begin{cfacode} … … 1183 1168 \end{cfacode} 1184 1169 Since 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 attemp s to begin the next iteration of the loop.1170 In the case where @i@ is @2@, the continue statement runs the loop update expression and attempts to begin the next iteration of the loop. 1186 1171 Since continue is a C statement, which does not understand destructors, a destructor call is added just before the continue statement to ensure that @x@ is destructed. 1187 1172 When @i@ is @3@, the break statement moves control to just past the end of the loop. … … 1193 1178 L1: for (int i = 0; i < 10; i++) { 1194 1179 A x; 1195 L2:for (int j = 0; j < 10; j++) {1180 for (int j = 0; j < 10; j++) { 1196 1181 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) { 1202 1183 continue L1; // destruct y 1203 1184 } else if (i == 2) { … … 1209 1190 The statement @continue L1@ begins the next iteration of the outer for-loop. 1210 1191 Since the semantics of continue require the loop update expression to execute, control branches to the \emph{end} of the outer for loop, meaning that the block destructor for @x@ can be reused, and it is only necessary to generate the destructor for @y@. 1192 % TODO: "why not do this all the time? fix or justify" 1211 1193 Break, on the other hand, requires jumping out of the loop, so the destructors for both @x@ and @y@ are generated and inserted before the @break L1@ statement. 1212 1194 … … 1277 1259 Exempt from these rules are intrinsic and builtin functions. 1278 1260 It 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. 1261 That 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. 1279 1262 This 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. 1280 1263 \begin{cfacode} … … 1284 1267 void ^?{}(A *); 1285 1268 1286 A f(A x) {1287 return x; 1269 A identity(A x) { // pass by value => need local copy 1270 return x; // return by value => make call-site copy 1288 1271 } 1289 1272 1290 1273 A y, z @= {}; 1291 identity(y); 1292 identity(z); 1274 identity(y); // copy construct y into x 1275 identity(z); // copy construct z into x 1293 1276 \end{cfacode} 1294 1277 Note 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.1296 1278 1297 1279 This generates the following 1298 1280 \begin{cfacode} 1299 1281 struct 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 1302 1284 return _retval_f; 1303 1285 } 1304 1286 1305 1287 struct 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 1289 struct A z = { 0 }; // C default 1290 1291 struct A _tmp_cp1; // argument 1 1292 struct 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 1299 struct A _tmp_cp2; // argument 1 1300 struct 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 1320 1306 ^?{}(&y); 1321 1307 \end{cfacode} 1308 1309 A 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} 1311 identity(z@); // do not copy construct argument 1312 // - will copy construct/destruct return value 1313 A@ 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} 1318 It 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. 1322 1319 1323 1320 A known issue with this implementation is that the return value of a function is not guaranteed to have the same address for its entire lifetime. 1324 1321 Specifically, since @_retval_f@ is allocated and constructed in @f@ then returned by value, the internal data is bitwise copied into the caller's stack frame. 1325 1322 This 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 willnot work correctly for return value objects.1327 Thus is itnot safe to rely on an object's @this@ pointer to remain constant throughout execution of the program.1323 It is currently the case that constructors and destructors that use the @this@ pointer as a unique identifier to store data externally do not work correctly for return value objects. 1324 Thus, it is not safe to rely on an object's @this@ pointer to remain constant throughout execution of the program. 1328 1325 \begin{cfacode} 1329 1326 A * external_data[32]; … … 1341 1338 } 1342 1339 } 1340 1341 A makeA() { 1342 A x; // stores &x in external_data 1343 return x; 1344 } 1345 makeA(); // return temporary has a different address than x 1346 // equivalent to: 1347 // A _tmp; 1348 // _tmp = makeA(), _tmp; 1349 // ^?{}(&_tmp); 1343 1350 \end{cfacode} 1344 1351 In 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 willnot 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.1352 Due to copying on return, the current object being destructed does not exist in the array if an @A@ object is ever returned by value from a function. 1353 1354 This problem could be solved in the translator by changing the function signatures so that the return value is moved into the parameter list. 1348 1355 For example, the translator could restructure the code like so 1349 1356 \begin{cfacode} … … 1363 1370 \end{cfacode} 1364 1371 This 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 whichreturn by value, as discussed in \cite{Bilson03}.1372 It is worth pointing out that this kind of signature rewriting already occurs in polymorphic functions that return by value, as discussed in \cite{Bilson03}. 1366 1373 A 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. 1367 1374 \begin{cfacode} 1368 1375 struct A { int v; }; 1369 A x; // unmanaged 1376 A x; // unmanaged, since only trivial constructors are available 1370 1377 { 1371 1378 void ?{}(A * a) { ... } … … 1375 1382 A z; // unmanaged 1376 1383 \end{cfacode} 1377 Hence there is not enough information to determine at function declaration to determinewhether 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.1384 Hence 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. 1378 1385 Even 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 is n'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 whichspecifies 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.1386 Furthermore, it is not possible to overload C functions, so using @extern "C"@ to declare functions is of limited use. 1387 1388 It 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. 1382 1389 Ideally, structs should be manageable by default, since otherwise the default case becomes more verbose. 1383 1390 This means that in general, function signatures would have to be rewritten, and in a select few cases the signatures would not be rewritten. … … 1408 1415 \section{Implementation} 1409 1416 \subsection{Array Initialization} 1410 Arrays are a special case in the C type 1417 Arrays are a special case in the C type-system. 1411 1418 C 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. 1412 1419 Instead, \CFA defines the initialization and destruction of an array recursively. … … 1525 1532 By default, objects within a translation unit are constructed in declaration order, and destructed in the reverse order. 1526 1533 The 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 basis1528 % https://gcc.gnu.org/onlinedocs/gcc/C_002b_002b-Attributes.html#C_002b_002b-Attributes1529 % 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 level1530 1534 It is, however, guaranteed that any global objects in the standard library are initialized prior to the initialization of any object in the user program. 1531 1535 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-Attributes1536 This feature is implemented in the \CFA translator by grouping every global constructor call into a function with the GCC attribute \emph{constructor}, which performs most of the heavy lifting. % TODO: CITE: https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#Common-Function-Attributes 1533 1537 A similar function is generated with the \emph{destructor} attribute, which handles all global destructor calls. 1534 1538 At 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. … … 1559 1563 \end{cfacode} 1560 1564 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 1567 GCC provides an attribute @init_priority@, which specifies allows specifying the relative priority for initialization of global objects on a per-object basis in \CC. 1568 A similar attribute can be implemented in \CFA by pulling marked objects into global constructor/destructor-attribute functions with the specified priority. 1569 For example, 1570 \begin{cfacode} 1571 struct A { ... }; 1572 void ?{}(A *, int); 1573 void ^?{}(A *); 1574 __attribute__((init_priority(200))) A x = { 123 }; 1575 \end{cfacode} 1576 would generate 1577 \begin{cfacode} 1578 A 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 1561 1587 \subsection{Static Local Variables} 1562 1588 In standard C, it is possible to mark variables that are local to a function with the @static@ storage class. 1563 1589 Unlike normal local variables, a @static@ local variable is defined to live for the entire duration of the program, so that each call to the function has access to the same variable with the same address and value as it had in the previous call to the function. % TODO: mention dynamic loading caveat?? 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.1590 Much 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. 1565 1591 1566 1592 Yet again, this rule is too restrictive for a language with constructors and destructors. … … 1573 1599 Construction of @static@ local objects is implemented via an accompanying @static bool@ variable, which records whether the variable has already been constructed. 1574 1600 A 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 willnot reconstruct the object.1601 The object's destructor is scheduled to be run when the program terminates using @atexit@, and the companion @bool@'s value is set so that subsequent invocations of the function do not reconstruct the object. 1576 1602 Since the parameter to @atexit@ is a parameter-less function, some additional tweaking is required. 1577 1603 First, the @static@ variable must be hoisted up to global scope and uniquely renamed to prevent name clashes with other global objects. … … 1630 1656 \end{cfacode} 1631 1657 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. 1632 1659 \subsection{Constructor Expressions} 1633 1660 In \CFA, it is possible to use a constructor as an expression. 1634 1661 Like other operators, the function name @?{}@ matches its operator syntax. 1635 1662 For example, @(&x){}@ calls the default constructor on the variable @x@, and produces @&x@ as a result. 1636 The significance of constructors as expressions rather than as statements is that the result of a constructor expression can be used as part of a larger expression. 1637 A key example is the use of constructor expressions to initialize the result of a call to standard C routine @malloc@. 1663 A key example for this capability is the use of constructor expressions to initialize the result of a call to standard C routine @malloc@. 1638 1664 \begin{cfacode} 1639 1665 struct X { ... }; -
doc/rob_thesis/intro.tex
rae6cc8b r7493339 5 5 \section{\CFA Background} 6 6 \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. 8 8 As it is an extension of C, there is already a wealth of existing C code and principles that govern the design of the language. 9 9 Among the goals set out in the original design of \CFA, four points stand out \cite{Bilson03}. … … 16 16 Therefore, these design principles must be kept in mind throughout the design and development of new language features. 17 17 In 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?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. 19 19 20 20 \subsection{C Background} … … 39 39 For example, in the initialization of @a1@, the initializer of @y@ is @7@, and the unnamed initializer @6@ initializes the next subobject, @z@. 40 40 Later initializers override earlier initializers, so a subobject for which there is more than one initializer is only initailized by its last initializer. 41 Th is 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 .41 These semantics 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, because this syntax is one of the few places that conflicts with the new language features. 43 43 44 44 C also provides \emph{compound literal} expressions, which provide a first-class mechanism for creating unnamed objects. … … 91 91 92 92 There 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 t 0package multiple return-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 to package multiple return-values. 94 94 \begin{cfacode} 95 95 int f(int * ret) { // returns a value through parameter ret … … 102 102 \end{cfacode} 103 103 The 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. 104 The latter approach: 104 105 \begin{cfacode} 105 106 struct A { … … 112 113 ... res3.x ... res3.y ... // use result values 113 114 \end{cfacode} 114 The latter approachrequires the caller to either learn the field names of the structure or learn the names of helper routines to access the individual return values.115 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. 115 116 Both solutions are syntactically unnatural. 116 117 117 118 In \CFA, it is possible to directly declare a function returning mutliple values. 118 This provides important semantic information to the caller, since return values are only for output.119 \begin{cfacode} 120 [int, int] f() { // don't need to create anew type119 This 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 121 122 return [123, 37]; 122 123 } 123 124 \end{cfacode} 124 However, the ability to return multiple values requires a syntax for accepting the results from a function. 125 However, the ability to return multiple values is useless without a syntax for accepting the results from the function. 126 125 127 In standard C, return values are most commonly assigned directly into local variables, or are used as the arguments to another function call. 126 128 \CFA allows both of these contexts to accept multiple return values. … … 148 150 g(f()); // selects (2) 149 151 \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.152 In 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. 153 A similar reasoning holds calling the function @g@. 152 154 153 155 In \CFA, overloading also applies to operator names, known as \emph{operator overloading}. … … 166 168 bool ?<?(A x, A y); 167 169 \end{cfacode} 168 Notably, the only difference i n this example is syntax.170 Notably, the only difference is syntax. 169 171 Most of the operators supported by \CC for operator overloading are also supported in \CFA. 170 172 Of notable exception are the logical operators (e.g. @||@), the sequence operator (i.e. @,@), and the member-access operators (e.g. @.@ and \lstinline{->}). … … 172 174 Finally, \CFA also permits overloading variable identifiers. 173 175 This feature is not available in \CC. 174 \begin{cfacode} % TODO: pick something better than x? max, zero, one?176 \begin{cfacode} 175 177 struct Rational { int numer, denom; }; 176 178 int x = 3; // (1) … … 186 188 In this example, there are three definitions of the variable @x@. 187 189 Based on the context, \CFA attempts to choose the variable whose type best matches the expression context. 190 When used judiciously, this feature allows names like @MAX@, @MIN@, and @PI@ to apply across many types. 188 191 189 192 Finally, the values @0@ and @1@ have special status in standard C. … … 197 200 } 198 201 \end{cfacode} 199 Every if 202 Every 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. 200 203 Due 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 204 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. 202 205 \begin{cfacode} 203 206 // lvalue is similar to returning a reference in C++ … … 293 296 This 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. 294 297 298 An interesting application of return-type resolution and polymorphism is with type-safe @malloc@. 299 \begin{cfacode} 300 forall(dtype T | sized(T)) 301 T * malloc() { 302 return (T*)malloc(sizeof(T)); // call C malloc 303 } 304 int * x = malloc(); // malloc(sizeof(int)) 305 double * y = malloc(); // malloc(sizeof(double)) 306 307 struct S { ... }; 308 S * s = malloc(); // malloc(sizeof(S)) 309 \end{cfacode} 310 The built-in trait @sized@ ensures that size and alignment information for @T@ is available to @malloc@ through @sizeof@ and @_Alignof@ expressions respectively. 311 In 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 295 313 \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. 314 An \emph{invariant} is a logical assertion that is true for some duration of a program's execution. 300 315 Invariants help a programmer to reason about code correctness and prove properties of programs. 301 316 302 317 In object-oriented programming languages, type invariants are typically established in a constructor and maintained throughout the object's lifetime. 303 Th is istypically achieved through a combination of access control modifiers and a restricted interface.318 These assertions are typically achieved through a combination of access control modifiers and a restricted interface. 304 319 Typically, 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. 305 320 It 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. … … 307 322 In C, the @assert@ macro is often used to ensure invariants are true. 308 323 Using @assert@, the programmer can check a condition and abort execution if the condition is not true. 309 This is a powerful tool thatforces the programmer to deal with logical inconsistencies as they occur.324 This powerful tool forces the programmer to deal with logical inconsistencies as they occur. 310 325 For 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. 311 326 \begin{cfacode} … … 354 369 \end{dcode} 355 370 The 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. 371 Note, these invariants are internal to the type's correct behaviour. 372 373 Types also have external invarients with state of the execution environment, including the heap, the open file-table, the state of global variables, etc. 374 Since 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. 359 375 360 376 \section{Resource Management} … … 367 383 However, whenever a program needs a variable to outlive the block it is created in, the storage must be allocated dynamically with @malloc@ and later released with @free@. 368 384 This pattern is extended to more complex objects, such as files and sockets, which also outlive the block where they are created, but at their core is resource management. 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.385 Once 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. 370 386 This implicit convention is provided only through documentation about the expectations of functions. 371 387 … … 380 396 On the other hand, destructors provide a simple mechanism for tearing down an object and resetting the environment in which the object lived. 381 397 RAII 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 bereferred to as a \emph{managed type}.398 A type with at least one non-trivial constructor or destructor is henceforth referred to as a \emph{managed type}. 383 399 In the context of \CFA, a non-trivial constructor is either a user defined constructor or an auto generated constructor that calls a non-trivial constructor. 384 400 … … 389 405 There are many kinds of resources that the garbage collector does not understand, such as sockets, open files, and database connections. 390 406 In 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/2386739392 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.407 Sadly, finalizers are only guaranteed to be called before an object is reclaimed by the garbage collector \cite[p.~373]{Java8}, which may not happen if memory use is not contentious. 408 Due to operating-system resource-limits, this is unacceptable for many long running programs. % TODO: citation? 409 Instead, 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. 410 Complicating the picture, uncaught exceptions can cause control flow to change dramatically, leaking a resource that appears on first glance to be released. 395 411 \begin{javacode} 396 412 void write(String filename, String msg) throws Exception { … … 403 419 } 404 420 \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. 421 Any 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. 407 422 \begin{javacode} 408 423 public void write(String filename, String msg) throws Exception { … … 422 437 \end{javacode} 423 438 In 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?439 Furthermore, 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}. 425 440 \begin{javacode} 426 441 public void write(String filename, String msg) throws Exception { 427 try ( 442 try ( // try-with-resources 428 443 FileOutputStream out = new FileOutputStream(filename); 429 444 FileOutputStream log = new FileOutputStream("log.txt"); … … 434 449 } 435 450 \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. 451 Variables 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. 452 Depending 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. 437 457 438 458 % D has constructors and destructors that are worth a mention (under classes) https://dlang.org/spec/spec.html … … 444 464 Like Java, using the garbage collector means that destructors may never be called, requiring the use of finally statements to ensure dynamically allocated resources that are not managed by the garbage collector, such as open files, are cleaned up. 445 465 Since 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) 466 Finally, D provides a scope guard statement, which allows an arbitrary statement to be executed at normal scope exit with \emph{success}, at exceptional scope exit with \emph{failure}, or at normal and exceptional scope exit with \emph{exit}. % TODO: cite? https://dlang.org/spec/statement.html#ScopeGuardStatement 467 It has been shown that the \emph{exit} form of the scope guard statement can be implemented in a library in \CC \cite{ExceptSafe}. 468 469 To provide managed types in \CFA, new kinds of constructors and destructors are added to C and discussed in Chapter 2. 452 470 453 471 \section{Tuples} 454 472 \label{s:Tuples} 455 473 In mathematics, tuples are finite-length sequences which, unlike sets, allow duplicate elements. 456 In programming languages, tuples are a construct thatprovide fixed-sized heterogeneous lists of elements.474 In programming languages, tuples provide fixed-sized heterogeneous lists of elements. 457 475 Many programming languages have tuple constructs, such as SETL, \KWC, ML, and Scala. 458 476 … … 462 480 Adding tuples to \CFA has previously been explored by Esteves \cite{Esteves04}. 463 481 464 The design of tuples in \KWC took much of its inspiration from SETL .482 The design of tuples in \KWC took much of its inspiration from SETL \cite{SETL}. 465 483 SETL is a high-level mathematical programming language, with tuples being one of the primary data types. 466 484 Tuples in SETL allow a number of operations, including subscripting, dynamic expansion, and multiple assignment. … … 470 488 \begin{cppcode} 471 489 tuple<int, int, int> triple(10, 20, 30); 472 get<1>(triple); // access component 1 => 30490 get<1>(triple); // access component 1 => 20 473 491 474 492 tuple<int, double> f(); … … 482 500 Tuples are simple data structures with few specific operations. 483 501 In 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 assigningthe results of a tuple-returning function into separate local variables, without requiring a temporary variable.502 Another 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. 485 503 Tuples also support lexicographic comparisons, making it simple to write aggregate comparators using @std::tie@. 486 504 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.pdf505 There 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. 488 506 \begin{cppcode} 489 507 tuple<int, double> f(); … … 500 518 Structured bindings allow unpacking any struct with all public non-static data members into fresh local variables. 501 519 The 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.520 This 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. 503 521 Furthermore, structured bindings are not a full replacement for @std::tie@, as it always declares new variables. 504 522 505 523 Like \CC, D provides tuples through a library variadic template struct. 506 524 In 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} 508 527 Tuple!(float, "x", float, "y") point2D; 509 Tuple!(float, float) float2; // different type s528 Tuple!(float, float) float2; // different type from point2D 510 529 511 530 point2D[0]; // access first element … … 521 540 The @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. 522 541 523 Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML .542 Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML \cite{sml}. 524 543 A function in SML always accepts exactly one argument. 525 544 There are two ways to mimic multiple argument functions: the first through currying and the second by accepting tuple arguments. … … 535 554 Tuples are a foundational tool in SML, allowing the creation of arbitrarily complex structured data types. 536 555 537 Scala, like \CC, provides tuple types through the standard library .556 Scala, like \CC, provides tuple types through the standard library \cite{Scala}. 538 557 Scala provides tuples of size 1 through 22 inclusive through generic data structures. 539 558 Tuples support named access and subscript access, among a few other operations. … … 547 566 \end{scalacode} 548 567 In 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 does n't cause problems since large tuples are uncommon.568 The 22-element restriction is an odd and arbitrary choice, but in practice it does not cause problems since large tuples are uncommon. 550 569 Subscript 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. 551 570 The 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. … … 553 572 554 573 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).aspx574 \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 556 575 The officially supported workaround for this shortcoming is to nest tuples in the 8th component. 557 576 \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. 558 577 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. 578 In Python \cite{Python}, tuples are immutable sequences that provide packing and unpacking operations. 562 579 While the tuple itself is immutable, and thus does not allow the assignment of components, there is nothing preventing a component from being internally mutable. 563 580 The components of a tuple can be accessed by unpacking into multiple variables, indexing, or via field name, like D. 564 581 Tuples support multiple assignment through a combination of packing and unpacking, in addition to the common sequence operations. 565 582 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. 583 Swift \cite{Swift}, like D, provides named tuples, with components accessed by name, index, or via extractors. 568 584 Tuples are primarily used for returning multiple values from a function. 569 585 In 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 588 Tuples as powerful as the above languages are added to C and discussed in Chapter 3. 570 589 571 590 \section{Variadic Functions} … … 641 660 A parameter pack matches 0 or more elements, which can be types or expressions depending on the context. 642 661 Like 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 anyany type provided there is a corresponding @print@ routine, making variadic templates fully open to extension, unlike variadic functions in C.662 That 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. 644 663 645 664 Recent \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. … … 672 691 Unfortunately, Java's use of nominal inheritance means that types must explicitly inherit from classes or interfaces in order to be considered a subclass. 673 692 The combination of these two issues greatly restricts the usefulness of variadic functions in Java. 693 694 Type-safe variadic functions are added to C and discussed in Chapter 4. -
doc/rob_thesis/thesis-frontpgs.tex
rae6cc8b r7493339 76 76 \begin{center}\textbf{Abstract}\end{center} 77 77 78 % \CFA is a modern extension tothe 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. 79 This thesis introduces two fundamental language features: tuples and constructors/destructors, as well as improved variadic functions. 80 While these features exist in prior programming languages, the contribution of this work is engineering these features into a highly complex type system. 81 81 82 82 \cleardoublepage -
doc/rob_thesis/thesis.tex
rae6cc8b r7493339 71 71 \usepackage{textcomp} 72 72 % \usepackage[utf8]{inputenc} 73 \usepackage[latin1]{inputenc}73 % \usepackage[latin1]{inputenc} 74 74 \usepackage{fullpage,times,comment} 75 75 % \usepackage{epic,eepic} … … 225 225 \input{tuples} 226 226 227 \input{variadic} 228 227 229 \input{conclusions} 228 230 … … 282 284 \addcontentsline{toc}{chapter}{\textbf{References}} 283 285 284 \bibliography{cfa }286 \bibliography{cfa,thesis} 285 287 % Tip 5: You can create multiple .bib files to organize your references. 286 288 % Just list them all in the \bibliogaphy command, separated by commas (no spaces). -
doc/rob_thesis/tuples.tex
rae6cc8b r7493339 4 4 5 5 \section{Introduction} 6 % TODO: named return values are not currently implemented in CFA - tie in with named tuples? (future work) 7 % TODO: no passing input parameters by assignment, instead will have reference types => this is not a very C-like model and greatly complicates syntax for likely little gain (and would cause confusion with already supported return-by-rerefence) 8 % TODO: tuples are allowed in expressions, exact meaning is defined by operator overloading (e.g. can add tuples). An important caveat to note is that it is currently impossible to allow adding two triples but prevent adding a pair with a quadruple (single flattening/structuring conversions are implicit, only total number of components matters). May be able to solve this with more nuanced conversion rules (future work) 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) 9 7 % TODO: benefits (conclusion) by Till: reduced number of variables and statements; no specified order of execution for multiple assignment (more optimzation freedom); can store parameter lists in variable; MRV routines (natural code); more convenient assignment statements; simple and efficient access of record fields; named return values more legible and efficient in use of storage 10 8 … … 73 71 const char * str = "hello world"; 74 72 char ch; // pre-allocate return value 75 int freq = most_frequent(str, &ch); // pass return value as parameter73 int freq = most_frequent(str, &ch); // pass return value as out parameter 76 74 printf("%s -- %d %c\n", str, freq, ch); 77 75 \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. 76 Notably, 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. 80 77 Also, 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. 81 78 Furthermore, 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. … … 109 106 } 110 107 \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 .108 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, which precludes the bug seen with out parameters. 112 109 113 110 The addition of multiple-return-value functions necessitates a syntax for accepting multiple values at the call-site. … … 136 133 In this case, there is only one option for a function named @most_frequent@ that takes a string as input. 137 134 This function returns two values, one @int@ and one @char@. 138 There are four options for a function named @process@, but only two whichaccept two arguments, and of those the best match is (3), which is also an exact match.135 There 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. 139 136 This 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. 140 137 … … 148 145 The previous expression has 3 \emph{components}. 149 146 Each 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 (...?)151 147 The order of evaluation of the components in a tuple expression is unspecified, to allow a compiler the greatest flexibility for program optimization. 152 148 It is, however, guaranteed that each component of a tuple expression is evaluated for side-effects, even if the result is not used. 153 149 Multiple-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.156 150 157 151 \subsection{Tuple Variables} … … 166 160 These variables can be used in any of the contexts where a tuple expression is allowed, such as in the @printf@ function call. 167 161 As 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 extractedwith a simple assignment, as in previous examples.162 One way to access the individual components is with a simple assignment, as in previous examples. 169 163 \begin{cfacode} 170 164 int freq; … … 254 248 \label{s:TupleAssignment} 255 249 An 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 MassAssignment, respectively.250 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 \emph{Multiple} and \emph{Mass} Assignment, respectively. 257 251 \begin{cfacode} 258 252 int x; … … 272 266 A mass assignment assigns the value $R$ to each $L_i$. 273 267 For a mass assignment to be valid, @?=?(&$L_i$, $R$)@ must be a well-typed expression. 274 Th is differsfrom 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.268 These 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. 275 269 For 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@. 276 270 On 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. … … 288 282 These semantics allow cascading tuple assignment to work out naturally in any context where a tuple is permitted. 289 283 These 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 Th is 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.284 The \KWC semantics fix what was seen as a problem with assignment, wherein it can be used in many different locations, such as in function-call argument position. % TODO: remove?? 291 285 While 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. 292 286 Furthermore, 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. … … 315 309 void ?{}(S *, S); // (4) 316 310 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 320 314 \end{cfacode} 321 315 In this example, @x@ is initialized by the multiple constructor calls @?{}(&x.0, 3)@ and @?{}(&x.1, 6.28)@, while @y@ is initilaized by two default constructor calls @?{}(&y.0)@ and @?{}(&y.1)@. … … 339 333 S s = t; 340 334 \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.335 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. 342 336 343 337 \section{Member-Access Tuple Expression} … … 354 348 Then the type of @a.[x, y, z]@ is @[T_x, T_y, T_z]@. 355 349 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.).350 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.). 357 351 \begin{cfacode} 358 352 [int, int, long, double] x; … … 384 378 Since \CFA permits these tuple-access expressions using structures, unions, and tuples, \emph{member tuple expression} or \emph{field tuple expression} is more appropriate. 385 379 386 It could bepossible to extend member-access expressions further.380 It is possible to extend member-access expressions further. 387 381 Currently, 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. 388 382 In the interest of orthogonal design, \CFA could apply some meaning to the remaining combinations as well. … … 403 397 One benefit of this interpretation is familiar, since it is extremely reminiscent of tuple-index expressions. 404 398 On 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 withevery instance of the structure.406 407 As for @z.y@, a natural interpretation would beto extend the meaning of member tuple expressions.399 This 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 401 As for @z.y@, a one interpretation is to extend the meaning of member tuple expressions. 408 402 That is, currently the tuple must occur as the member, i.e. to the right of the dot. 409 403 Allowing 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. 410 404 In 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.405 It 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. 412 406 Perhaps 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. 413 407 The 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. 414 408 415 Supposing this feature works as described, it would be necessary to specify an ordering for the expansion of member access expressions versus membertuple expressions.409 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. 416 410 \begin{cfacode} 417 411 struct { int x, y; }; … … 426 420 \end{cfacode} 427 421 Depending 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. 422 As such, a specific ordering would need to be imposed to make this feature useful. 423 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. 424 425 A second possibility is for \CFA to have named tuples, as they exist in Swift and D. 426 \begin{cfacode} 427 typedef [int x, int y] Point2D; 428 Point2D p1, p2; 429 p1.x + p1.y + p2.x + p2.y; 430 p1.0 + p1.1 + p2.0 + p2.1; // equivalent 431 \end{cfacode} 432 In this simpler interpretation, a named tuple type carries with it a list of possibly empty identifiers. 433 This approach fits naturally with the named return-value feature, and would likely go a long way towards implementing it. 434 435 Ultimately, the first two extensions introduce complexity into the model, with relatively little peceived benefit, and so were dropped from consideration. 436 Named tuples are a potentially useful addition to the language, provided they can be parsed with a reasonable syntax. 437 432 438 433 439 \section{Casting} … … 442 448 (int)f(); // choose (2) 443 449 \end{cfacode} 444 Since casting is a fundamental operation in \CFA, casts shouldbe given a meaningful interpretation in the context of tuples.450 Since casting is a fundamental operation in \CFA, casts need to be given a meaningful interpretation in the context of tuples. 445 451 Taking a look at standard C provides some guidance with respect to the way casts should work with tuples. 446 452 \begin{cfacode}[numbers=left] … … 448 454 void g(); 449 455 450 (void)f(); 451 (int)g(); 456 (void)f(); // valid, ignore results 457 (int)g(); // invalid, void cannot be converted to int 452 458 453 459 struct A { int x; }; 454 (struct A)f(); 460 (struct A)f(); // invalid 455 461 \end{cfacode} 456 462 In C, line 4 is a valid cast, which calls @f@ and discards its result. 457 463 On 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 whichhave the same or fewer number of components may be valid.464 Finally, line 8 is also invalid, because in C casts only provide conversion between scalar types \cite[p.~91]{C11}. 465 For 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. 460 466 461 467 Formally, 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$. … … 509 515 \end{cfacode} 510 516 Note 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]); 517 For example, these expressions also succeed and produce the same value. 518 A call to this plus operator type checks as long as a total of 6 non-tuple arguments are passed after flattening, and all of the arguments have a common type that can bind to @T@, with a pairwise @?+?@ over @T@. 519 \begin{cfacode} 520 ([x.0, x.1]) + ([x.2, 10, 20, 30]); // x + ([10, 20, 30]) 521 x.0 + ([x.1, x.2, 10, 20, 30]); // x + ([10, 20, 30]) 516 522 \end{cfacode} 517 523 This 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.524 Furthermore, these calls can be made ambiguous by adding seemingly different functions. 519 525 \begin{cfacode} 520 526 forall(otype T | { T ?+?(T, T); }) … … 524 530 \end{cfacode} 525 531 It 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, th is isa 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.532 Still, these semantics are a deficiency of the current argument matching algorithm, and depending on the function, differing return values may not always be appropriate. 533 These issues could be rectified by applying an appropriate cost to the structuring and flattening conversions, which are currently 0-cost conversions. 528 534 Care would be needed in this case to ensure that exact matches do not incur such a cost. 529 535 \begin{cfacode} … … 536 542 \end{cfacode} 537 543 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).544 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). 539 545 This decision presents a conflict with the flexibility of tuples. 540 546 \subsection{Assertion Inference} … … 617 623 In the call to @f@, the second and third argument components are structured into a tuple argument. 618 624 619 Expressions whichmay contain side effects are made into \emph{unique expressions} before being expanded by the flattening conversion.625 Expressions that may contain side effects are made into \emph{unique expressions} before being expanded by the flattening conversion. 620 626 Each unique expression is assigned an identifier and is guaranteed to be executed exactly once. 621 627 \begin{cfacode} … … 624 630 g(h()); 625 631 \end{cfacode} 626 Interally, this is converted to 632 Interally, this is converted to psuedo-\CFA 627 633 \begin{cfacode} 628 634 void g(int, double); 629 635 [int, double] h(); 630 let unq<0> = f() : g(unq<0>.0, unq<0>.1); // notation? 631 \end{cfacode} 636 lazy [int, double] unq<0> = h(); 637 g(unq<0>.0, unq<0>.1); 638 \end{cfacode} 639 That is, the function @h@ is evaluated lazily and its result is stored for subsequent accesses. 632 640 Ultimately, unique expressions are converted into two variables and an expression. 633 641 \begin{cfacode} … … 638 646 [int, double] _unq0; 639 647 g( 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, 642 650 ); 643 651 \end{cfacode} … … 646 654 Every subsequent evaluation of the unique expression then results in an access to the stored result of the actual expression. 647 655 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 availableto 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.656 Currently, the \CFA translator has a very broad, imprecise definition of impurity (side-effects), where any function call is assumed to be impure. 657 This notion could be made more precise for certain intrinsic, autogenerated, and builtin functions, and could analyze function bodies, when they are available, to recursively detect impurity, to eliminate some unique expressions. 658 It is possible that lazy evaluation could be exposed to the user through a lazy keyword with little additional effort. 651 659 652 660 Tuple member expressions are recursively expanded into a list of member access expressions. … … 655 663 x.[0, 1.[0, 2]]; 656 664 \end{cfacode} 657 Which becomes665 which becomes 658 666 \begin{cfacode} 659 667 [x.0, [x.1.0, x.1.2]]; 660 668 \end{cfacode} 661 Tuple 669 Tuple-member expressions also take advantage of unique expressions in the case of possible impurity. 662 670 663 671 Finally, the various kinds of tuple assignment, constructors, and destructors generate GNU C statement expressions. … … 711 719 }); 712 720 \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.721 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. 714 722 $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. 715 723 A nested statement expression is generated that performs the individual assignments and constructs the return value using the results of the individual assignments. … … 785 793 The 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. 786 794 There 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 type806 N--;807 }808 va_end(args);809 return ret;810 }811 sum(3, 10, 20, 30); // need to keep counter in sync812 \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 like886 \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 simply904 \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 Params925 | 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 R946 | 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 elements967 }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 malloc1000 }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 malloc1017 }1018 \end{cfacode}1019 Generates the following1020 \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 *p1031 ){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 following1056 \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 new1066 struct S *_tmp_cp_ret1; // return value from new1067 void _thunk0( // ?{}(S *, [int, int])1068 struct S *_p0,1069 struct _conc__tuple2_0 _p11070 ){1071 _ctor_S(_p0, _p1.field_0, _p1.field_1); // restructure tuple parameter1072 }1073 void _adapter(void (*_adaptee)(), void *_p0, void *_p1){1074 // apply adaptee to arguments after casting to actual types1075 ((void (*)(struct S *, struct _conc__tuple2_0))_adaptee)(1076 _p0,1077 *(struct _conc__tuple2_0 *)_p11078 );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 new1089 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 new1098 ({ // destroy argument temporary1099 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@ function1108 \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 Generates1117 \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 *rest1135 ){1136 void *_tmp_cp0 = __builtin_alloca(_sizeof_T);1137 _adapterF_2tT__P( // print(arg)1138 ((void (*)())print_T),1139 (_adapterF_P2tT2tT__MP( // copy construct argument1140 ((void (*)())_ctor_TT),1141 _tmp_cp0,1142 arg1143 ), _tmp_cp0)1144 );1145 _dtor_T(_tmp_cp0); // destroy argument temporary1146 _adapterF_7tParams__P( // print(rest)1147 ((void (*)())print_Params),1148 rest1149 );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 print1155 \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 following1162 \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.01235 &(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 *_p11251 ){1252 *(const char **)_ret=1253 ((const char *(*)(const char **, const char *))_adaptee)(1254 _p0,1255 *(const char **)_p11256 );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 print1284 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 temporary1293 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.