Index: doc/proposals/tagged-struct.txt =================================================================== --- doc/proposals/tagged-struct.txt (revision cc3e4d0fba2ab4dcc1616c82569b8f30a199e333) +++ doc/proposals/tagged-struct.txt (revision d33bc7cf35bb09492981e1dc6d31b0c998fbf5f0) @@ -3,5 +3,5 @@ Tagged structures allow for dynamic casting between types in a hierarchy. Children (rather pointers to) can be up-cast to their parents, a safe -conversion that may recive language level support or even be implicate. +conversion that may recive language level support or even be implicit. Parents can be down cast to their children, which might fail if the underlying object is not of the child type, or a child of that. @@ -11,9 +11,7 @@ function call. -Tags cannot be used on unions. This is because the different sides interact -with the casts rather badly. There is a similarity with tagged unions still. -Tagged structures also carry data to identify which out of several -possibilies the object actually is. Although the possibilies are dynamic in -this case. +The name tagged structure comes from tagged union, which carries a value to +say which of the possible values is currently stored in the union. The idea +here is similar, however the possibilities are more open ended. @@ -23,5 +21,5 @@ The keywords can change (although they currently reflect the concept name -closely). More formally, in terms of grammer this adds: +closely). More formally, in terms of grammar this adds: struct-or-union-specifier @@ -48,17 +46,16 @@ parent type object. -If the type field is given a simple name, then the user can easily access the -type object. This might be useful depending on what sort of data is in the -type object, especially if the data can be added to by the user in some way. -Ironically one way to accomplish that is to make the type objects tagged -themselves, but that recursion might not have a base case. +The type field could be hidden (as best as C can hide it) or it could be +visible to the user with easy access to allow the user to examine the type +object directly. -If the name is mangled and direct access to type objects is still wanted, then -a function could be used to access the type object. Say get_type or get_tag -instead of type or tag. +Direct access is more useful if the data on the type-objects can change, other +wise the build in function could handle all cases. Perhaps each root object +can specify a type object to use or the type objects are themselves tagged, +although there may not be a base case with the latter. -If the data on the type object is set, than providing direct access may be -unnessary. Instead the libraries or base code might be able to implement -everything the data is for. +In the simplest case the type object is a pointer to the parent type object. +Additional data could be added, such as a name, or a function pointer to the +destructor. @@ -84,2 +81,15 @@ bug#11 might require `bool dynamic_cast(T ** dst, U * src)` instead. + + +Tagging Unions (Extention): + +Using this system as is does not really work if used on unions directly. +No new options to the union can be added, as they must be able to upcast. +Similarly, if options are removed, writing to an upcast union is invalid. +To allow for growth each option would have to be a structure itself. + +Which brings us to "tagget struct union", ie. a union of tagged structures +as opposed to tagging the union itself. This extention acts as a constraint. +If unions are declared tagged instead of creating a new tagged type, all +possible values of the union must be of that tagged type or a child type. Index: doc/user/user.tex =================================================================== --- doc/user/user.tex (revision cc3e4d0fba2ab4dcc1616c82569b8f30a199e333) +++ doc/user/user.tex (revision d33bc7cf35bb09492981e1dc6d31b0c998fbf5f0) @@ -11,6 +11,6 @@ %% Created On : Wed Apr 6 14:53:29 2016 %% Last Modified By : Peter A. Buhr -%% Last Modified On : Tue Jun 13 11:50:27 2017 -%% Update Count : 2403 +%% Last Modified On : Fri Jun 16 12:00:01 2017 +%% Update Count : 2433 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -43,5 +43,5 @@ \usepackage[pagewise]{lineno} \renewcommand{\linenumberfont}{\scriptsize\sffamily} -\input{common} % bespoke macros used in the document +\input{common} % common CFA document macros \usepackage[dvips,plainpages=false,pdfpagelabels,pdfpagemode=UseNone,colorlinks=true,pagebackref=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pagebackref=true,breaklinks=true]{hyperref} \usepackage{breakurl} @@ -110,5 +110,5 @@ \renewcommand{\subsectionmark}[1]{\markboth{\thesubsection\quad #1}{\thesubsection\quad #1}} \pagenumbering{roman} -\linenumbers % comment out to turn off line numbering +%\linenumbers % comment out to turn off line numbering \maketitle @@ -881,4 +881,84 @@ +\subsection{Initialization} + +\Index{Initialization} is different than \Index{assignment} because initialization occurs on the empty (uninitialized) storage on an object, while assignment occurs on possibly initialized storage of an object. +There are three initialization contexts in \CFA: declaration initialization, argument/parameter binding, return/temporary binding. +Because the object being initialized has no value, there is only one meaningful semantics with respect to address duality: it must mean address as there is no pointed-to value. +In contrast, the left-hand side of assignment has an address that has a duality. +Therefore, for pointer/reference initialization, the initializing value must be an address not a value. +\begin{cfa} +int * p = &x; §\C{// assign address of x}§ +®int * p = x;® §\C{// assign value of x}§ +int & r = x; §\C{// must have address of x}§ +\end{cfa} +Like the previous example with C pointer-arithmetic, it is unlikely assigning the value of ©x© into a pointer is meaningful (again, a warning is usually given). +Therefore, for safety, this context requires an address, so it is superfluous to require explicitly taking the address of the initialization object, even though the type is incorrect. +Note, this is strictly a convenience and safety feature for a programmer. +Hence, \CFA allows ©r© to be assigned ©x© because it infers a reference for ©x©, by implicitly inserting a address-of operator, ©&©, and it is an error to put an ©&© because the types no longer match due to the implicit dereference. +Unfortunately, C allows ©p© to be assigned with ©&x© (address) or ©x© (value), but most compilers warn about the latter assignment as being potentially incorrect. +Similarly, when a reference type is used for a parameter/return type, the call-site argument does not require a reference operator for the same reason. +\begin{cfa} +int & f( int & r ); §\C{// reference parameter and return}§ +z = f( x ) + f( y ); §\C{// reference operator added, temporaries needed for call results}§ +\end{cfa} +Within routine ©f©, it is possible to change the argument by changing the corresponding parameter, and parameter ©r© can be locally reassigned within ©f©. +Since operator routine ©?+?© takes its arguments by value, the references returned from ©f© are used to initialize compiler generated temporaries with value semantics that copy from the references. +\begin{cfa} +int temp1 = f( x ), temp2 = f( y ); +z = temp1 + temp2; +\end{cfa} +This \Index{implicit referencing} is crucial for reducing the syntactic burden for programmers when using references; +otherwise references have the same syntactic burden as pointers in these contexts. + +When a pointer/reference parameter has a ©const© value (immutable), it is possible to pass literals and expressions. +\begin{cfa} +void f( ®const® int & cr ); +void g( ®const® int * cp ); +f( 3 ); g( ®&®3 ); +f( x + y ); g( ®&®(x + y) ); +\end{cfa} +Here, the compiler passes the address to the literal 3 or the temporary for the expression ©x + y©, knowing the argument cannot be changed through the parameter. +The ©&© before the constant/expression for the pointer-type parameter (©g©) is a \CFA extension necessary to type match and is a common requirement before a variable in C (\eg ©scanf©). +Importantly, ©&3© may not be equal to ©&3©, where the references occur across calls because the temporaries maybe different on each call. + +\CFA \emph{extends} this semantics to a mutable pointer/reference parameter, and the compiler implicitly creates the necessary temporary (copying the argument), which is subsequently pointed-to by the reference parameter and can be changed.\footnote{ +If whole program analysis is possible, and shows the parameter is not assigned, \ie it is ©const©, the temporary is unnecessary.} +\begin{cfa} +void f( int & r ); +void g( int * p ); +f( 3 ); g( ®&®3 ); §\C{// compiler implicit generates temporaries}§ +f( x + y ); g( ®&®(x + y) ); §\C{// compiler implicit generates temporaries}§ +\end{cfa} +Essentially, there is an implicit \Index{rvalue} to \Index{lvalue} conversion in this case.\footnote{ +This conversion attempts to address the \newterm{const hell} problem, when the innocent addition of a ©const© qualifier causes a cascade of type failures, requiring an unknown number of additional ©const© qualifiers, until it is discovered a ©const© qualifier cannot be added and all the ©const© qualifiers must be removed.} +The implicit conversion allows seamless calls to any routine without having to explicitly name/copy the literal/expression to allow the call. + +%\CFA attempts to handle pointers and references in a uniform, symmetric manner. +Finally, C handles \Index{routine object}s in an inconsistent way. +A routine object is both a pointer and a reference (\Index{particle and wave}). +\begin{cfa} +void f( int i ); +void (*fp)( int ); §\C{// routine pointer}§ +fp = f; §\C{// reference initialization}§ +fp = &f; §\C{// pointer initialization}§ +fp = *f; §\C{// reference initialization}§ +fp(3); §\C{// reference invocation}§ +(*fp)(3); §\C{// pointer invocation}§ +\end{cfa} +While C's treatment of routine objects has similarity to inferring a reference type in initialization contexts, the examples are assignment not initialization, and all possible forms of assignment are possible (©f©, ©&f©, ©*f©) without regard for type. +Instead, a routine object should be referenced by a ©const© reference: +\begin{cfa} +®const® void (®&® fr)( int ) = f; §\C{// routine reference}§ +fr = ... §\C{// error, cannot change code}§ +&fr = ...; §\C{// changing routine reference}§ +fr( 3 ); §\C{// reference call to f}§ +(*fr)(3); §\C{// error, incorrect type}§ +\end{cfa} +because the value of the routine object is a routine literal, \ie the routine code is normally immutable during execution.\footnote{ +Dynamic code rewriting is possible but only in special circumstances.} +\CFA allows this additional use of references for routine objects in an attempt to give a more consistent meaning for them. + + \subsection{Address-of Semantics} @@ -958,98 +1038,5 @@ -\subsection{Initialization} - -\Index{Initialization} is different than \Index{assignment} because initialization occurs on the empty (uninitialized) storage on an object, while assignment occurs on possibly initialized storage of an object. -There are three initialization contexts in \CFA: declaration initialization, argument/parameter binding, return/temporary binding. -Because the object being initialized has no value, there is only one meaningful semantics with respect to address duality: it must mean address as there is no pointed-to value. -In contrast, the left-hand side of assignment has an address that has a duality. -Therefore, for pointer/reference initialization, the initializing value must be an address not a value. -\begin{cfa} -int * p = &x; §\C{// assign address of x}§ -®int * p = x;® §\C{// assign value of x}§ -int & r = x; §\C{// must have address of x}§ -\end{cfa} -Like the previous example with C pointer-arithmetic, it is unlikely assigning the value of ©x© into a pointer is meaningful (again, a warning is usually given). -Therefore, for safety, this context requires an address, so it is superfluous to require explicitly taking the address of the initialization object, even though the type is incorrect. -Note, this is strictly a convenience and safety feature for a programmer. -Hence, \CFA allows ©r© to be assigned ©x© because it infers a reference for ©x©, by implicitly inserting a address-of operator, ©&©, and it is an error to put an ©&© because the types no longer match due to the implicit dereference. -Unfortunately, C allows ©p© to be assigned with ©&x© (address) or ©x© (value), but most compilers warn about the latter assignment as being potentially incorrect. -Similarly, when a reference type is used for a parameter/return type, the call-site argument does not require a reference operator for the same reason. -\begin{cfa} -int & f( int & r ); §\C{// reference parameter and return}§ -z = f( x ) + f( y ); §\C{// reference operator added, temporaries needed for call results}§ -\end{cfa} -Within routine ©f©, it is possible to change the argument by changing the corresponding parameter, and parameter ©r© can be locally reassigned within ©f©. -Since operator routine ©?+?© takes its arguments by value, the references returned from ©f© are used to initialize compiler generated temporaries with value semantics that copy from the references. -\begin{cfa} -int temp1 = f( x ), temp2 = f( y ); -z = temp1 + temp2; -\end{cfa} -This \Index{implicit referencing} is crucial for reducing the syntactic burden for programmers when using references; -otherwise references have the same syntactic burden as pointers in these contexts. - -When a pointer/reference parameter has a ©const© value (immutable), it is possible to pass literals and expressions. -\begin{cfa} -void f( ®const® int & cr ); -void g( ®const® int * cp ); -f( 3 ); g( ®&®3 ); -f( x + y ); g( ®&®(x + y) ); -\end{cfa} -Here, the compiler passes the address to the literal 3 or the temporary for the expression ©x + y©, knowing the argument cannot be changed through the parameter. -The ©&© before the constant/expression for the pointer-type parameter (©g©) is a \CFA extension necessary to type match and is a common requirement before a variable in C (\eg ©scanf©). -Importantly, ©&3© may not be equal to ©&3©, where the references occur across calls because the temporaries maybe different on each call. - -\CFA \emph{extends} this semantics to a mutable pointer/reference parameter, and the compiler implicitly creates the necessary temporary (copying the argument), which is subsequently pointed-to by the reference parameter and can be changed.\footnote{ -If whole program analysis is possible, and shows the parameter is not assigned, \ie it is ©const©, the temporary is unnecessary.} -\begin{cfa} -void f( int & r ); -void g( int * p ); -f( 3 ); g( ®&®3 ); §\C{// compiler implicit generates temporaries}§ -f( x + y ); g( ®&®(x + y) ); §\C{// compiler implicit generates temporaries}§ -\end{cfa} -Essentially, there is an implicit \Index{rvalue} to \Index{lvalue} conversion in this case.\footnote{ -This conversion attempts to address the \newterm{const hell} problem, when the innocent addition of a ©const© qualifier causes a cascade of type failures, requiring an unknown number of additional ©const© qualifiers, until it is discovered a ©const© qualifier cannot be added and all the ©const© qualifiers must be removed.} -The implicit conversion allows seamless calls to any routine without having to explicitly name/copy the literal/expression to allow the call. - -%\CFA attempts to handle pointers and references in a uniform, symmetric manner. -Finally, C handles \Index{routine object}s in an inconsistent way. -A routine object is both a pointer and a reference (\Index{particle and wave}). -\begin{cfa} -void f( int i ); -void (*fp)( int ); §\C{// routine pointer}§ -fp = f; §\C{// reference initialization}§ -fp = &f; §\C{// pointer initialization}§ -fp = *f; §\C{// reference initialization}§ -fp(3); §\C{// reference invocation}§ -(*fp)(3); §\C{// pointer invocation}§ -\end{cfa} -While C's treatment of routine objects has similarity to inferring a reference type in initialization contexts, the examples are assignment not initialization, and all possible forms of assignment are possible (©f©, ©&f©, ©*f©) without regard for type. -Instead, a routine object should be referenced by a ©const© reference: -\begin{cfa} -®const® void (®&® fr)( int ) = f; §\C{// routine reference}§ -fr = ... §\C{// error, cannot change code}§ -&fr = ...; §\C{// changing routine reference}§ -fr( 3 ); §\C{// reference call to f}§ -(*fr)(3); §\C{// error, incorrect type}§ -\end{cfa} -because the value of the routine object is a routine literal, \ie the routine code is normally immutable during execution.\footnote{ -Dynamic code rewriting is possible but only in special circumstances.} -\CFA allows this additional use of references for routine objects in an attempt to give a more consistent meaning for them. - - - \begin{comment} -\section{References} - -By introducing references in parameter types, users are given an easy way to pass a value by reference, without the need for NULL pointer checks. -In structures, a reference can replace a pointer to an object that should always have a valid value. -When a structure contains a reference, all of its constructors must initialize the reference and all instances of this structure must initialize it upon definition. - -The syntax for using references in \CFA is the same as \CC with the exception of reference initialization. -Use ©&© to specify a reference, and access references just like regular objects, not like pointers (use dot notation to access fields). -When initializing a reference, \CFA uses a different syntax which differentiates reference initialization from assignment to a reference. -The ©&© is used on both sides of the expression to clarify that the address of the reference is being set to the address of the variable to which it refers. - - From: Richard Bilson Date: Wed, 13 Jul 2016 01:58:58 +0000 @@ -1213,5 +1200,5 @@ \section{Routine Definition} -\CFA also supports a new syntax for routine definition, as well as ISO C and K\&R routine syntax. +\CFA also supports a new syntax for routine definition, as well as \Celeven and K\&R routine syntax. The point of the new syntax is to allow returning multiple values from a routine~\cite{Galletly96,CLU}, \eg: \begin{cfa} @@ -1233,6 +1220,6 @@ in both cases the type is assumed to be void as opposed to old style C defaults of int return type and unknown parameter types, respectively, as in: \begin{cfa} -[§\,§] g(); §\C{// no input or output parameters}§ -[ void ] g( void ); §\C{// no input or output parameters}§ +[§\,§] g(); §\C{// no input or output parameters}§ +[ void ] g( void ); §\C{// no input or output parameters}§ \end{cfa} @@ -1252,5 +1239,5 @@ \begin{cfa} typedef int foo; -int f( int (* foo) ); §\C{// foo is redefined as a parameter name}§ +int f( int (* foo) ); §\C{// foo is redefined as a parameter name}§ \end{cfa} The string ``©int (* foo)©'' declares a C-style named-parameter of type pointer to an integer (the parenthesis are superfluous), while the same string declares a \CFA style unnamed parameter of type routine returning integer with unnamed parameter of type pointer to foo. @@ -1260,12 +1247,12 @@ C-style declarations can be used to declare parameters for \CFA style routine definitions, \eg: \begin{cfa} -[ int ] f( * int, int * ); §\C{// returns an integer, accepts 2 pointers to integers}§ -[ * int, int * ] f( int ); §\C{// returns 2 pointers to integers, accepts an integer}§ +[ int ] f( * int, int * ); §\C{// returns an integer, accepts 2 pointers to integers}§ +[ * int, int * ] f( int ); §\C{// returns 2 pointers to integers, accepts an integer}§ \end{cfa} The reason for allowing both declaration styles in the new context is for backwards compatibility with existing preprocessor macros that generate C-style declaration-syntax, as in: \begin{cfa} #define ptoa( n, d ) int (*n)[ d ] -int f( ptoa( p, 5 ) ) ... §\C{// expands to int f( int (*p)[ 5 ] )}§ -[ int ] f( ptoa( p, 5 ) ) ... §\C{// expands to [ int ] f( int (*p)[ 5 ] )}§ +int f( ptoa( p, 5 ) ) ... §\C{// expands to int f( int (*p)[ 5 ] )}§ +[ int ] f( ptoa( p, 5 ) ) ... §\C{// expands to [ int ] f( int (*p)[ 5 ] )}§ \end{cfa} Again, programmers are highly encouraged to use one declaration form or the other, rather than mixing the forms. @@ -1289,5 +1276,5 @@ int z; ... x = 0; ... y = z; ... - ®return;® §\C{// implicitly return x, y}§ + ®return;® §\C{// implicitly return x, y}§ } \end{cfa} @@ -1299,7 +1286,24 @@ [ int x, int y ] f() { ... -} §\C{// implicitly return x, y}§ +} §\C{// implicitly return x, y}§ \end{cfa} In this case, the current values of ©x© and ©y© are returned to the calling routine just as if a ©return© had been encountered. + +Named return values may be used in conjunction with named parameter values; +specifically, a return and parameter can have the same name. +\begin{cfa} +[ int x, int y ] f( int, x, int y ) { + ... +} §\C{// implicitly return x, y}§ +\end{cfa} +This notation allows the compiler to eliminate temporary variables in nested routine calls. +\begin{cfa} +[ int x, int y ] f( int, x, int y ); §\C{// prototype declaration}§ +int a, b; +[a, b] = f( f( f( a, b ) ) ); +\end{cfa} +While the compiler normally ignores parameters names in prototype declarations, here they are used to eliminate temporary return-values by inferring that the results of each call are the inputs of the next call, and ultimately, the left-hand side of the assignment. +Hence, even without the body of routine ©f© (separate compilation), it is possible to perform a global optimization across routine calls. +The compiler warns about naming inconsistencies between routine prototype and definition in this case, and behaviour is \Index{undefined} if the programmer is inconsistent. @@ -1309,8 +1313,8 @@ as well, parameter names are optional, \eg: \begin{cfa} -[ int x ] f (); §\C{// returning int with no parameters}§ -[ * int ] g (int y); §\C{// returning pointer to int with int parameter}§ -[ ] h (int,char); §\C{// returning no result with int and char parameters}§ -[ * int,int ] j (int); §\C{// returning pointer to int and int, with int parameter}§ +[ int x ] f (); §\C{// returning int with no parameters}§ +[ * int ] g (int y); §\C{// returning pointer to int with int parameter}§ +[ ] h ( int, char ); §\C{// returning no result with int and char parameters}§ +[ * int, int ] j ( int ); §\C{// returning pointer to int and int, with int parameter}§ \end{cfa} This syntax allows a prototype declaration to be created by cutting and pasting source text from the routine definition header (or vice versa). @@ -1320,9 +1324,9 @@ \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ \begin{cfa} -[ int ] f(int), g; +[ int ] f( int ), g; \end{cfa} & \begin{cfa} -int f(int), g(int); +int f( int ), g( int ); \end{cfa} \end{tabular} @@ -1330,6 +1334,6 @@ Declaration qualifiers can only appear at the start of a \CFA routine declaration,\footref{StorageClassSpecifier} \eg: \begin{cfa} -extern [ int ] f (int); -static [ int ] g (int); +extern [ int ] f ( int ); +static [ int ] g ( int ); \end{cfa} @@ -1339,13 +1343,13 @@ The syntax for pointers to \CFA routines specifies the pointer name on the right, \eg: \begin{cfa} -* [ int x ] () fp; §\C{// pointer to routine returning int with no parameters}§ -* [ * int ] (int y) gp; §\C{// pointer to routine returning pointer to int with int parameter}§ -* [ ] (int,char) hp; §\C{// pointer to routine returning no result with int and char parameters}§ -* [ * int,int ] (int) jp; §\C{// pointer to routine returning pointer to int and int, with int parameter}§ +* [ int x ] () fp; §\C{// pointer to routine returning int with no parameters}§ +* [ * int ] (int y) gp; §\C{// pointer to routine returning pointer to int with int parameter}§ +* [ ] (int,char) hp; §\C{// pointer to routine returning no result with int and char parameters}§ +* [ * int,int ] ( int ) jp; §\C{// pointer to routine returning pointer to int and int, with int parameter}§ \end{cfa} While parameter names are optional, \emph{a routine name cannot be specified}; for example, the following is incorrect: \begin{cfa} -* [ int x ] f () fp; §\C{// routine name "f" is not allowed}§ +* [ int x ] f () fp; §\C{// routine name "f" is not allowed}§ \end{cfa} @@ -1534,5 +1538,5 @@ int ; §\C{// disallowed, unnamed field}§ int *; §\C{// disallowed, unnamed field}§ - int (*)(int); §\C{// disallowed, unnamed field}§ + int (*)( int ); §\C{// disallowed, unnamed field}§ }; \end{cfa} @@ -1657,5 +1661,5 @@ } int main() { - * [int](int) fp = foo(); §\C{// int (*fp)(int)}§ + * [int]( int ) fp = foo(); §\C{// int (*fp)( int )}§ sout | fp( 3 ) | endl; } @@ -2778,5 +2782,5 @@ -\subsection{Constructors and Destructors} +\section{Constructors and Destructors} \CFA supports C initialization of structures, but it also adds constructors for more advanced initialization. @@ -3109,4 +3113,5 @@ +\begin{comment} \section{Generics} @@ -3315,4 +3320,5 @@ } \end{cfa} +\end{comment} @@ -3374,5 +3380,4 @@ Complex *p3 = new(0.5, 1.0); // allocate + 2 param constructor } - \end{cfa} @@ -3386,4 +3391,5 @@ +\begin{comment} \subsection{Unsafe C Constructs} @@ -3396,11 +3402,8 @@ The exact set of unsafe C constructs that will be disallowed in \CFA has not yet been decided, but is sure to include pointer arithmetic, pointer casting, etc. Once the full set is decided, the rules will be listed here. +\end{comment} \section{Concurrency} - -Today's processors for nearly all use cases, ranging from embedded systems to large cloud computing servers, are composed of multiple cores, often heterogeneous. -As machines grow in complexity, it becomes more difficult for a program to make the most use of the hardware available. -\CFA includes built-in concurrency features to enable high performance and improve programmer productivity on these multi-/many-core machines. Concurrency support in \CFA is implemented on top of a highly efficient runtime system of light-weight, M:N, user level threads. @@ -3409,15 +3412,56 @@ This enables a very familiar interface to all programmers, even those with no parallel programming experience. It also allows the compiler to do static type checking of all communication, a very important safety feature. -This controlled communication with type safety has some similarities with channels in \Index*{Go}, and can actually implement -channels exactly, as well as create additional communication patterns that channels cannot. +This controlled communication with type safety has some similarities with channels in \Index*{Go}, and can actually implement channels exactly, as well as create additional communication patterns that channels cannot. Mutex objects, monitors, are used to contain mutual exclusion within an object and synchronization across concurrent threads. -Three new keywords are added to support these features: - -monitor creates a structure with implicit locking when accessing fields - -mutex implies use of a monitor requiring the implicit locking - -task creates a type with implicit locking, separate stack, and a thread +\begin{figure} +\begin{cfa} +#include +#include + +coroutine Fibonacci { + int fn; §\C{// used for communication}§ +}; +void ?{}( Fibonacci * this ) { + this->fn = 0; +} +void main( Fibonacci * this ) { + int fn1, fn2; §\C{// retained between resumes}§ + this->fn = 0; §\C{// case 0}§ + fn1 = this->fn; + suspend(); §\C{// return to last resume}§ + + this->fn = 1; §\C{// case 1}§ + fn2 = fn1; + fn1 = this->fn; + suspend(); §\C{// return to last resume}§ + + for ( ;; ) { §\C{// general case}§ + this->fn = fn1 + fn2; + fn2 = fn1; + fn1 = this->fn; + suspend(); §\C{// return to last resume}§ + } // for +} +int next( Fibonacci * this ) { + resume( this ); §\C{// transfer to last suspend}§ + return this->fn; +} +int main() { + Fibonacci f1, f2; + for ( int i = 1; i <= 10; i += 1 ) { + sout | next( &f1 ) | ' ' | next( &f2 ) | endl; + } // for +} +\end{cfa} +\caption{Fibonacci Coroutine} +\label{f:FibonacciCoroutine} +\end{figure} + + +\subsection{Coroutine} + +\Index{Coroutines} are the precursor to tasks. +\VRef[Figure]{f:FibonacciCoroutine} shows a coroutine that computes the \Index*{Fibonacci} numbers. @@ -3434,4 +3478,51 @@ \end{cfa} +\begin{figure} +\begin{cfa} +#include +#include +#include +#include + +monitor global_t { + int value; +}; + +void ?{}(global_t * this) { + this->value = 0; +} + +static global_t global; + +void increment3( global_t * mutex this ) { + this->value += 1; +} +void increment2( global_t * mutex this ) { + increment3( this ); +} +void increment( global_t * mutex this ) { + increment2( this ); +} + +thread MyThread {}; + +void main( MyThread* this ) { + for(int i = 0; i < 1_000_000; i++) { + increment( &global ); + } +} +int main(int argc, char* argv[]) { + processor p; + { + MyThread f[4]; + } + sout | global.value | endl; +} +\end{cfa} +\caption{Atomic-Counter Monitor} +\caption{f:AtomicCounterMonitor} +\end{figure} + +\begin{comment} Since a monitor structure includes an implicit locking mechanism, it does not make sense to copy a monitor; it is always passed by reference. @@ -3480,4 +3571,5 @@ } \end{cfa} +\end{comment} @@ -3487,4 +3579,53 @@ A task provides mutual exclusion like a monitor, and also has its own execution state and a thread of control. Similar to a monitor, a task is defined like a structure: + +\begin{figure} +\begin{cfa} +#include +#include +#include +#include + +thread First { signal_once * lock; }; +thread Second { signal_once * lock; }; + +void ?{}( First * this, signal_once* lock ) { this->lock = lock; } +void ?{}( Second * this, signal_once* lock ) { this->lock = lock; } + +void main( First * this ) { + for ( int i = 0; i < 10; i += 1 ) { + sout | "First : Suspend No." | i + 1 | endl; + yield(); + } + signal( this->lock ); +} + +void main( Second * this ) { + wait( this->lock ); + for ( int i = 0; i < 10; i += 1 ) { + sout | "Second : Suspend No." | i + 1 | endl; + yield(); + } +} + +int main( void ) { + signal_once lock; + sout | "User main begin" | endl; + { + processor p; + { + First f = { &lock }; + Second s = { &lock }; + } + } + sout | "User main end" | endl; +} +\end{cfa} +\caption{Simple Tasks} +\label{f:SimpleTasks} +\end{figure} + + +\begin{comment} \begin{cfa} type Adder = task { @@ -3540,5 +3681,4 @@ \end{cfa} - \subsection{Cooperative Scheduling} @@ -3653,9 +3793,10 @@ } \end{cfa} - - +\end{comment} + + +\begin{comment} \section{Modules and Packages } -\begin{comment} High-level encapsulation is useful for organizing code into reusable units, and accelerating compilation speed. \CFA provides a convenient mechanism for creating, building and sharing groups of functionality that enhances productivity and improves compile time. @@ -4321,4 +4462,5 @@ +\begin{comment} \subsection[Comparing Key Features of CFA]{Comparing Key Features of \CFA} @@ -4698,5 +4840,4 @@ -\begin{comment} \subsubsection{Modules / Packages} @@ -4778,5 +4919,4 @@ } \end{cfa} -\end{comment} @@ -4939,7 +5079,8 @@ \subsection{Summary of Language Comparison} - - -\subsubsection[C++]{\CC} +\end{comment} + + +\subsection[C++]{\CC} \Index*[C++]{\CC{}} is a general-purpose programming language. @@ -4962,5 +5103,5 @@ -\subsubsection{Go} +\subsection{Go} \Index*{Go}, also commonly referred to as golang, is a programming language developed at Google in 2007 [.]. @@ -4978,5 +5119,5 @@ -\subsubsection{Rust} +\subsection{Rust} \Index*{Rust} is a general-purpose, multi-paradigm, compiled programming language developed by Mozilla Research. @@ -4992,5 +5133,5 @@ -\subsubsection{D} +\subsection{D} The \Index*{D} programming language is an object-oriented, imperative, multi-paradigm system programming @@ -5104,5 +5245,5 @@ \item[Rationale:] keywords added to implement new semantics of \CFA. \item[Effect on original feature:] change to semantics of well-defined feature. \\ -Any ISO C programs using these keywords as identifiers are invalid \CFA programs. +Any \Celeven programs using these keywords as identifiers are invalid \CFA programs. \item[Difficulty of converting:] keyword clashes are accommodated by syntactic transformations using the \CFA backquote escape-mechanism (see~\VRef{s:BackquoteIdentifiers}). \item[How widely used:] clashes among new \CFA keywords and existing identifiers are rare. Index: src/Common/PassVisitor.h =================================================================== --- src/Common/PassVisitor.h (revision cc3e4d0fba2ab4dcc1616c82569b8f30a199e333) +++ src/Common/PassVisitor.h (revision d33bc7cf35bb09492981e1dc6d31b0c998fbf5f0) @@ -253,3 +253,48 @@ } +class WithTypeSubstitution { +protected: + WithTypeSubstitution() = default; + ~WithTypeSubstitution() = default; + +public: + TypeSubstitution * env; +}; + +class WithStmtsToAdd { +protected: + WithStmtsToAdd() = default; + ~WithStmtsToAdd() = default; + +public: + std::list< Statement* > stmtsToAddBefore; + std::list< Statement* > stmtsToAddAfter; +}; + +class WithShortCircuiting { +protected: + WithShortCircuiting() = default; + ~WithShortCircuiting() = default; + +public: + bool skip_children; +}; + +class WithScopes { +protected: + WithScopes() = default; + ~WithScopes() = default; + +public: + at_cleanup_t at_cleanup; + + template< typename T > + void GuardValue( T& val ) { + at_cleanup( [ val ]( void * newVal ) { + * static_cast< T * >( newVal ) = val; + }, static_cast< void * >( & val ) ); + } +}; + + #include "PassVisitor.impl.h" Index: src/InitTweak/GenInit.cc =================================================================== --- src/InitTweak/GenInit.cc (revision cc3e4d0fba2ab4dcc1616c82569b8f30a199e333) +++ src/InitTweak/GenInit.cc (revision d33bc7cf35bb09492981e1dc6d31b0c998fbf5f0) @@ -44,5 +44,5 @@ } - class ReturnFixer { + class ReturnFixer : public WithStmtsToAdd, public WithScopes { public: /// consistently allocates a temporary variable for the return value @@ -53,7 +53,4 @@ void premutate( FunctionDecl *functionDecl ); void premutate( ReturnStmt * returnStmt ); - - at_cleanup_t at_cleanup; - std::list< Statement * > stmtsToAddBefore; protected: @@ -160,6 +157,6 @@ void ReturnFixer::premutate( FunctionDecl *functionDecl ) { - GuardValue( this, ftype ); - GuardValue( this, funcName ); + GuardValue( ftype ); + GuardValue( funcName ); ftype = functionDecl->get_functionType();