Index: doc/theses/fangren_yu_MMath/content1.tex =================================================================== --- doc/theses/fangren_yu_MMath/content1.tex (revision 29075d1e4c22e096eb350d86267c83b273bb0de7) +++ doc/theses/fangren_yu_MMath/content1.tex (revision 7c80a869f88c3730d39d4639d2681dec3b8b85b6) @@ -1,6 +1,6 @@ -\chapter{Recent Features Introduced to \CFA} +\chapter{\CFA Features and Type System Interactions} \label{c:content1} -This chapter discusses some recent additions to the \CFA language and their interactions with the type system. +This chapter discusses \CFA feature introduced over time by multiple people and their interactions with the type system. @@ -17,6 +17,8 @@ Succinctly, if the address changes often, use a pointer; if the value changes often, use a reference. -Note, \CC made its reference address immutable starting a \emph{belief} that immutability is a fundamental aspect of a reference's pointer. -The results is asymmetry semantics between the pointer and reference. +Java has mutable references but no pointers. +\CC has mutable pointers but immutable references; +hence, references match with functional programming. +However, the consequence is asymmetry semantics between the pointer and reference. \CFA adopts a uniform policy between pointers and references where mutability is a separate property made at the declaration. @@ -36,5 +38,5 @@ Like pointers, reference can be cascaded, \ie a reference to a reference, \eg @&& r2@.\footnote{ \CC uses \lstinline{&&} for rvalue reference, a feature for move semantics and handling the \lstinline{const} Hell problem.} -Usage of a reference variable automatically performs the same number of dereferences as the number of references in its declaration, \eg @r3@ becomes @***r3@. +Usage of a reference variable automatically performs the same number of dereferences as the number of references in its declaration, \eg @r2@ becomes @**r2@. Finally, to reassign a reference's address needs a mechanism to stop the auto-referencing, which is accomplished by using a single reference to cancel all the auto-dereferencing, \eg @&r3 = &y@ resets @r3@'s address to point to @y@. \CFA's reference type (including multi-de/references) is powerful enough to describe the lvalue rules in C by types only. @@ -66,21 +68,37 @@ int x = 3; $\C{// mutable}$ const int cx = 5; $\C{// immutable}$ -int * const cp = &x, $\C{// immutable pointer}$ +int * const cp = &x, $\C{// immutable pointer pointer/reference}$ & const cr = cx; -const int * const ccp = &cx, $\C{// immutable value and pointer}$ +const int * const ccp = &cx, $\C{// immutable value and pointer/reference}$ & const ccr = cx; -// pointer +\end{cfa} +\begin{cquote} +\setlength{\tabcolsep}{26pt} +\begin{tabular}{@{}lll@{}} +pointer & reference & \\ +\begin{cfa} *cp = 7; -cp = &x; $\C{// error, assignment of read-only variable}$ -*ccp = 7; $\C{// error, assignment of read-only location}$ -ccp = &cx; $\C{// error, assignment of read-only variable}$ -// reference +cp = &x; +*ccp = 7; +ccp = &cx; +\end{cfa} +& +\begin{cfa} cr = 7; -cr = &x; $\C{// error, assignment of read-only variable}$ -*ccr = 7; $\C{// error, assignment of read-only location}$ -ccr = &cx; $\C{// error, assignment of read-only variable}$ -\end{cfa} +cr = &x; +*ccr = 7; +ccr = &cx; +\end{cfa} +& +\begin{cfa} +// allowed +// error, assignment of read-only variable +// error, assignment of read-only location +// error, assignment of read-only variable +\end{cfa} +\end{tabular} +\end{cquote} Interestingly, C does not give a warning/error if a @const@ pointer is not initialized, while \CC does. -Hence, type @& const@ is similar to \CC reference, but \CFA does not preclude initialization with a non-variable address. +Hence, type @& const@ is similar to a \CC reference, but \CFA does not preclude initialization with a non-variable address. For example, in system's programming, there are cases where an immutable address is initialized to a specific memory location. \begin{cfa} @@ -96,9 +114,9 @@ However, there is an inherent ambiguity for auto-dereferencing: every argument expression involving a reference variable can potentially mean passing the reference's value or address. Without any restrictions, this ambiguity limits the behaviour of reference types in \CFA polymorphic functions, where a type @T@ can bind to a reference or non-reference type. -This ambiguity prevents the type system treating reference types the same way as other types in many cases even if type variables could be bound to reference types. +This ambiguity prevents the type system treating reference types the same way as other types, even if type variables could be bound to reference types. The reason is that \CFA uses a common \emph{object trait}\label{p:objecttrait} (constructor, destructor and assignment operators) to handle passing dynamic concrete type arguments into polymorphic functions, and the reference types are handled differently in these contexts so they do not satisfy this common interface. Moreover, there is also some discrepancy in how the reference types are treated in initialization and assignment expressions. -For example, in line 3 of the previous example code \see{\VPageref{p:refexamples}}: +For example, in line 3 of the example code on \VPageref{p:refexamples}: \begin{cfa} int @&@ r1 = x, @&&@ r2 = r1, @&&&@ r3 = r2; $\C{// references to x}$ @@ -129,8 +147,8 @@ vector( int @&@ ) vec; $\C{// vector of references to ints}$ \end{cfa} -While it is possible to write a reference type as the argument to a generic type, it is disallowed in assertion checking, if the generic type requires the object trait \see{\VPageref{p:objecttrait}} for the type argument (a fairly common use case). +While it is possible to write a reference type as the argument to a generic type, it is disallowed in assertion checking, if the generic type requires the object trait \see{\VPageref{p:objecttrait}} for the type argument, a fairly common use case. Even if the object trait can be made optional, the current type system often misbehaves by adding undesirable auto-dereference on the referenced-to value rather than the reference variable itself, as intended. Some tweaks are necessary to accommodate reference types in polymorphic contexts and it is unclear what can or cannot be achieved. -Currently, there are contexts where \CFA programmer must use pointer types, giving up the benefits of auto-dereference operations and better syntax with reference types. +Currently, there are contexts where \CFA programmer is forced to use a pointer type, giving up the benefits of auto-dereference operations and better syntax with reference types. @@ -165,5 +183,5 @@ Along with making returning multiple values a first-class feature, tuples were extended to simplify a number of other common context that normally require multiple statements and/or additional declarations, all of which reduces coding time and errors. \begin{cfa} -[x, y, z] = 3; $\C[2in]{// x = 3; y = 3; z = 3, where types are different}$ +[x, y, z] = 3; $\C[2in]{// x = 3; y = 3; z = 3, where types may be different}$ [x, y] = [y, x]; $\C{// int tmp = x; x = y; y = tmp;}$ void bar( int, int, int ); @@ -212,5 +230,5 @@ bar( t2 ); $\C{// bar defined above}$ \end{cfa} -\VRef[Figure]{f:Nesting} shows The difference is nesting of structures and tuples. +\VRef[Figure]{f:Nesting} shows the difference is nesting of structures and tuples. The left \CC nested-structure is named so it is not flattened. The middle C/\CC nested-structure is unnamed and flattened, causing an error because @i@ and @j@ are duplication names. @@ -220,5 +238,5 @@ \begin{figure} -\setlength{\tabcolsep}{15pt} +\setlength{\tabcolsep}{20pt} \begin{tabular}{@{}ll@{\hspace{90pt}}l@{}} \multicolumn{1}{c}{\CC} & \multicolumn{1}{c}{C/\CC} & \multicolumn{1}{c}{tuple} \\ @@ -273,6 +291,6 @@ As noted, tradition languages manipulate multiple values by in/out parameters and/or structures. K-W C adopted the structure for tuple values or variables, and as needed, the fields are extracted by field access operations. -As well, For the tuple-assignment implementation, the left-hand tuple expression is expanded into assignments of each component, creating temporary variables to avoid unexpected side effects. -For example, the tuple value returned from @foo@ is a structure, and its fields are individually assigned to a left-hand tuple, @x@, @y@, @z@, or copied directly into a corresponding tuple variable. +As well, for the tuple-assignment implementation, the left-hand tuple expression is expanded into assignments of each component, creating temporary variables to avoid unexpected side effects. +For example, the tuple value returned from @foo@ is a structure, and its fields are individually assigned to a left-hand tuple, @x@, @y@, @z@, \emph{or} copied directly into a corresponding tuple variable. In the second implementation of \CFA tuples by Rodolfo Gabriel Esteves~\cite{Esteves04}, a different strategy is taken to handle MVR functions. @@ -286,38 +304,45 @@ [x, y] = gives_two(); \end{cfa} -The Till K-W C implementation translates the program to: +\VRef[Figure]{f:AlternateTupleImplementation} shows the two implementation approaches. +In the left approach, the return statement is rewritten to pack the return values into a structure, which is returned by value, and the structure fields are indiviually assigned to the left-hand side of the assignment. +In the right approach, the return statement is rewritten as direct assignments into the passed-in argument addresses. +The right imlementation looks more concise and saves unnecessary copying. +The downside is indirection within @gives_two@ to access values, unless values get hoisted into registers for some period of time, which is common. + +\begin{figure} +\begin{cquote} +\setlength{\tabcolsep}{20pt} +\begin{tabular}{@{}ll@{}} +Till K-W C implementation & Rodolfo \CFA implementation \\ \begin{cfa} struct _tuple2 { int _0; int _1; } -struct _tuple2 gives_two() { ... struct _tuple2 ret = { r1, r2 }, return ret; } +struct _tuple2 gives_two() { + ... struct _tuple2 ret = { r1, r2 }; + return ret; +} int x, y; struct _tuple2 _tmp = gives_two(); x = _tmp._0; y = _tmp._1; \end{cfa} -while the Rodolfo implementation translates it to: -\begin{cfa} -void gives_two( int * r1, int * r2 ) { ... *r1 = ...; *r2 = ...; return; } +& +\begin{cfa} + +void gives_two( int * r1, int * r2 ) { + ... *r1 = ...; *r2 = ...; + return; +} int x, y; + gives_two( &x, &y ); \end{cfa} -and inside the body of the function @gives_two@, the return statement is rewritten as assignments into the passed-in argument addresses. -This implementation looks more concise, and in the case of returning values having nontrivial types, \eg aggregates, this implementation saves unnecessary copying. -For example, -\begin{cfa} -[ x, y ] gives_two(); -int x, y; -[ x, y ] = gives_two(); -\end{cfa} -becomes -\begin{cfa} -void gives_two( int &, int & ); -int x, y; -gives_two( x, y ); -\end{cfa} -eliminiating any copying in or out of the call. -The downside is indirection within @gives_two@ to access values, unless values get hoisted into registers for some period of time, which is common. +\end{tabular} +\end{cquote} +\caption{Alternate Tuple Implementation} +\label{f:AlternateTupleImplementation} +\end{figure} Interestingly, in the third implementation of \CFA tuples by Robert Schluntz~\cite[\S~3]{Schluntz17}, the MVR functions revert back to structure based, where it remains in the current version of \CFA. The reason for the reversion was to have a uniform approach for tuple values/variables making tuples first-class types in \CFA, \ie allow tuples with corresponding tuple variables. -This extension was possible, because in parallel with Schluntz's work, generic types were being added independently by Moss~\cite{Moss19}, and the tuple variables leveraged the same implementation techniques as the generic variables. +This extension was possible, because in parallel with Schluntz's work, generic types were added independently by Moss~\cite{Moss19}, and the tuple variables leveraged the same implementation techniques as the generic variables. \PAB{I'm not sure about the connection here. Do you have an example of what you mean?} @@ -339,5 +364,5 @@ \begin{cfa} void f( int, int ); -void f( [int, int] ); +void f( @[@ int, int @]@ ); f( 3, 4 ); // ambiguous call \end{cfa} @@ -358,7 +383,7 @@ the call to @f@ can be interpreted as @T = [1]@ and @U = [2, 3, 4, 5]@, or @T = [1, 2]@ and @U = [3, 4, 5]@, and so on. The restriction ensures type checking remains tractable and does not take too long to compute. -Therefore, tuple types are never present in any fixed-argument function calls. - -Finally, a type-safe variadic argument signature was added by Robert Schluntz~\cite[\S~4.1.2]{Schluntz17} using @forall@ and a new tuple parameter-type, denoted by the keyword @ttype @ in Schluntz's implementation, but changed to the ellipsis syntax similar to \CC's template parameter pack. +Therefore, tuple types are never present in any fixed-argument function calls, because of the flattening. + +Finally, a type-safe variadic argument signature was added by Robert Schluntz~\cite[\S~4.1.2]{Schluntz17} using @forall@ and a new tuple parameter-type, denoted by the keyword @ttype@ in Schluntz's implementation, but changed to the ellipsis syntax similar to \CC's template parameter pack. For C variadics, \eg @va_list@, the number and types of the arguments must be conveyed in some way, \eg @printf@ uses a format string indicating the number and types of the arguments. \VRef[Figure]{f:CVariadicMaxFunction} shows an $N$ argument @maxd@ function using the C untyped @va_list@ interface. @@ -370,5 +395,5 @@ \begin{figure} \begin{cfa} -double maxd( int @count@, ... ) { +double maxd( int @count@, @...@ ) { // ellipse parameter double max = 0; va_list args; @@ -566,5 +591,5 @@ struct U u; u.k; u.l; \end{cfa} -and the hoisted type names can clash with global types names. +and the hoisted type names can clash with global type names. For good reasons, \CC chose to change this semantics: \begin{cquote} @@ -584,4 +609,8 @@ \end{cfa} \CFA chose to adopt the \CC non-compatible change for nested types, since \CC's change has already forced certain coding changes in C libraries that must be parsed by \CC. +\CFA also added the ability to access from a variable through a type to a field. +\begin{cfa} +struct S s; @s.T@.i; @s.U@.k; +\end{cfa} % https://gcc.gnu.org/onlinedocs/gcc/Unnamed-Fields.html @@ -604,39 +633,53 @@ \end{cfa} Note, the position of the substructure is normally unimportant, unless there is some form of memory or @union@ overlay. -Like the anonymous nested types, the aggregate field names are hoisted into @struct S@, so there is direct access, \eg @s.x@ and @s.i@. -However, like the implicit C hoisting of nested structures, the field names must be unique and the type names are now at a different scope level, unlike type nesting in \CC. -In addition, a pointer to a structure is automatically converted to a pointer to an anonymous field for assignments and function calls, providing containment inheritance with implicit subtyping, \ie @U@ $\subset$ @S@ and @W@ $\subset$ @S@. -For example: +Like an anonymous nested type, a named nested Plan-9 type has its field names hoisted into @struct S@, so there is direct access, \eg @s.x@ and @s.i@. +Hence, the field names must be unique, unlike \CC nested types, but the type names are at a nested scope level, unlike type nesting in C. +In addition, a pointer to a structure is automatically converted to a pointer to an anonymous field for assignments and function calls, providing containment inheritance with implicit subtyping, \ie @U@ $\subset$ @S@ and @W@ $\subset$ @S@, \eg: \begin{cfa} void f( union U * u ); void g( struct W * ); -union U * up; -struct W * wp; -struct S * sp; -up = sp; $\C{// assign pointer to U in S}$ -wp = sp; $\C{// assign pointer to W in S}$ +union U * up; struct W * wp; struct S * sp; +up = &s; $\C{// assign pointer to U in S}$ +wp = &s; $\C{// assign pointer to W in S}$ f( &s ); $\C{// pass pointer to U in S}$ g( &s ); $\C{// pass pointer to W in S}$ \end{cfa} - -\CFA extends the Plan-9 substructure by allowing polymorphism for values and pointers. -The extended substructure is denoted using @inline@, allowing backwards compatibility to existing Plan-9 features. +Note, there is no value assignment, such as, @w = s@, to copy the @W@ field from @S@. + +Unfortunately, the Plan-9 designers did not lookahead to other useful features, specifically nested types. +This nested type compiles in \CC and \CFA. +\begin{cfa} +struct R { + @struct T;@ $\C[2in]{// forward declaration, conflicts with Plan-9 syntax}$ + struct S { $\C{// nested types, mutually recursive reference}\CRT$ + S * sp; T * tp; ... + }; + struct T { + S * sp; T * tp; ... + }; +}; +\end{cfa} +Note, the syntax for the forward declaration conflicts with the Plan-9 declaration syntax. + +\CFA extends the Plan-9 substructure by allowing polymorphism for values and pointers, where the extended substructure is denoted using @inline@. \begin{cfa} struct S { - @inline@ W; $\C{// extended Plan-9 substructure}$ + @inline@ struct W; $\C{// extended Plan-9 substructure}$ unsigned int tag; @inline@ U; $\C{// extended Plan-9 substructure}$ } s; \end{cfa} -Note, like \CC, \CFA allows optional prefixing of type names with their kind, \eg @struct@, @union@, and @enum@, unless there is ambiguity with variable names in the same scope. -The following shows both value and pointer polymorphism. +Note, the declaration of @U@ is not prefixed with @union@. +Like \CC, \CFA allows optional prefixing of type names with their kind, \eg @struct@, @union@, and @enum@, unless there is ambiguity with variable names in the same scope. +In addition, a semi-non-compatible change is made so that Plan-9 syntax means a forward declaration in a nested type. +Since the Plan-9 extension is not part of C and rarely used, this change has minimal impact. +Hence, all Plan-9 semantics are denoted by the @inline@ qualifier, which good ``eye-candy'' when reading a structure definition to spot Plan-9 definitions. +Finally, the following code shows the value and pointer polymorphism. \begin{cfa} void f( U, U * ); $\C{// value, pointer}$ void g( W, W * ); $\C{// value, pointer}$ -U u, * up; -S s, * sp; -W w, * wp; -u = s; up = sp; $\C{// value, pointer}$ -w = s; wp = sp; $\C{// value, pointer}$ +U u, * up; S s, * sp; W w, * wp; +u = s; up = sp; $\C{// value, pointer}$ +w = s; wp = sp; $\C{// value, pointer}$ f( s, &s ); $\C{// value, pointer}$ g( s, &s ); $\C{// value, pointer}$ @@ -645,12 +688,9 @@ In general, non-standard C features (@gcc@) do not need any special treatment, as they are directly passed through to the C compiler. However, the Plan-9 semantics allow implicit conversions from the outer type to the inner type, which means the \CFA type resolver must take this information into account. -Therefore, the \CFA translator must implement the Plan-9 features and insert necessary type conversions into the translated code output. +Therefore, the \CFA resolver must implement the Plan-9 features and insert necessary type conversions into the translated code output. In the current version of \CFA, this is the only kind of implicit type conversion other than the standard C conversions. -Since variable overloading is possible in \CFA, \CFA's implementation of Plan-9 polymorphism allows duplicate field names. -When an outer field and an embedded field have the same name and type, the inner field is shadowed and cannot be accessed directly by name. -While such definitions are allowed, duplicate field names is not good practice in general and should be avoided if possible. -Plan-9 fields can be nested, and a struct definition can contain multiple Plan-9 embedded fields. -In particular, the \newterm{diamond pattern}~\cite[\S~6.1]{Stroustrup89}\cite[\S~4]{Cargill91} can occur and result in a nested field to be embedded twice. +Plan-9 polymorphism can result in duplicate field names. +For example, the \newterm{diamond pattern}~\cite[\S~6.1]{Stroustrup89}\cite[\S~4]{Cargill91} can result in nested fields being embedded twice. \begin{cfa} struct A { int x; }; @@ -658,9 +698,21 @@ struct C { inline A; }; struct D { - inline B; - inline C; -}; -D d; -\end{cfa} -In the above example, the expression @d.x@ becomes ambiguous, since it can refer to the indirectly embedded field either from @B@ or from @C@. -It is still possible to disambiguate the expression by first casting the outer struct to one of the directly embedded type, such as @((B)d).x@. + inline B; // B.x + inline C; // C.x +} d; +\end{cfa} +Because the @inline@ structures are flattened, the expression @d.x@ is ambiguous, as it can refer to the embedded field either from @B@ or @C@. +@gcc@ generates a syntax error about the duplicate member @x@. +The equivalent \CC definition compiles: +\begin{c++} +struct A { int x; }; +struct B : public A {}; +struct C : public A {}; +struct D : @public B, C@ { // multiple inheritance +} d; +\end{c++} +and again the expression @d.x@ is ambiguous. +While \CC has no direct syntax to disambiguate @x@, \ie @d.B.x@ or @d.C.x@, it is possible with casts, @((B)d).x@ or @((C)d).x@. +Like \CC, \CFA compiles the Plan-9 version and provides direct syntax and casts to disambiguate @x@. +While ambiguous definitions are allowed, duplicate field names is poor practice and should be avoided if possible. +However, when a programmer does not control all code, this problem can occur and a naming workaround should exist.