source: doc/theses/fangren_yu_MMath/content1.tex @ 048dde4

\chapter{\CFA Features and Type System Interactions}
\label{c:content1}

This chapter discusses \CFA features introduced over time by multiple people and their interactions with the type system.


\section{Reference Types}

Reference types were added to \CFA by Robert Schluntz and Aaron Moss~\cite{Moss18}.
The \CFA reference type generalizes the \CC reference type (and its equivalent in other modern programming languages) by providing both mutable and immutable forms and cascading referencing and dereferencing.
Specifically, \CFA attempts to extend programmer intuition about pointers to references.
That is, use a pointer when its primary purpose is manipulating the address of storage, \eg a top/head/tail pointer or link field in a mutable data structure.
Here, manipulating the pointer address is the primary operation, while dereferencing the pointer to its value is the secondary operation.
For example, \emph{within} a data structure, \eg stack or queue, all operations involve pointer addresses and the pointer may never be dereferenced because the referenced object is opaque.
Alternatively, use a reference when its primary purpose is to alias a value, \eg a function parameter that does not copy the argument (performance reason).
Here, manipulating the value is the primary operation, while changing the pointer address is the secondary operation.
Succinctly, if the address changes often, use a pointer;
if the value changes often, use a reference.
Java has mutable references but no pointers.
\CC has mutable pointers but immutable references;
here, references match with functional programming.
However, the consequence is asymmetric semantics between pointer and reference.
\CFA adopts a uniform policy between pointers and references where mutability is a separate property made at the declaration.

The following examples shows how pointers and references are treated uniformly in \CFA.
\begin{cfa}[numbers=left,numberblanklines=false]
int x = 1, y = 2, z = 3;$\label{p:refexamples}$
int * p1 = &x, ** p2 = &p1,  *** p3 = &p2,      $\C{// pointers to x}$
        @&@ r1 = x,  @&&@ r2 = r1,   @&&&@ r3 = r2;     $\C{// references to x}$
int * p4 = &z, & r4 = z;

*p1 = 3; **p2 = 3; ***p3 = 3;                           $\C{// different ways to change x to 3}$
 r1 =  3;       r2 = 3;         r3 = 3;                         $\C{// change x: implicit dereference *r1, **r2, ***r3}$
**p3 = &y;      *p3 = &p4;                                              $\C{// change p1, p2}$
// cancel implicit dereferences (&*)**r3, (&(&*)*)*r3, &(&*)r4
@&@r3 = @&@y; @&&@r3 = @&&@r4;                          $\C{// change r1, r2}$
\end{cfa}
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 @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.
As a result, the \CFA type checker now works on just types without using the notion of lvalue in an expression.
(\CFA internals still use lvalue for code generation purposes.)

The current reference typing rules in \CFA are summarized as follows:
\begin{enumerate}
    \item For a variable $x$ with declared type $T$, the variable-expression $x$ has type reference to $T$, even if $T$ itself is a reference type.
    \item For an expression $e$ with type $T\ \&_1...\&_n$, \ie $T$ followed by $n$ references, where $T$ is not a reference type, the expression $\&T$ (address of $T$) has type $T *$ followed by $n - 1$ references.
    \item For an expression $e$ with type $T *\&_1...\&_n$, \ie $T *$  followed by $n$ references, the expression $* T$ (dereference $T$) has type $T$ followed by $n + 1$ references.
        This rule is the reverse of the previous rule, such that address-of and dereference operators are perfect inverses.
    \item When matching argument and parameter types at a function call, the number of references on the argument type is stripped off to match the number of references on the parameter type.\footnote{
        \CFA handles the \lstinline{const} Hell problem by allowing rvalue expressions to be converted to reference values by implicitly creating a temporary variable, with some restrictions.
        As well, there is a warning that the output nature of the reference is lost.
        Hence, a single function handles \lstinline{const} and non-\lstinline{const} as constness is handled at the call site.}
        In an assignment context, the left-hand-side operand-type is always reduced to a single reference.
\end{enumerate}
Under this ruleset, a type parameter is never bound to a reference type in a function-call context.
\begin{cfa}
forall( T ) void f( T & );
int & x;
f( x );  // implicit dereference
\end{cfa}
The call applies an implicit dereference once to @x@ so the call is typed @f( int & )@ with @T = int@, rather than with @T = int &@.

As for a pointer type, a reference type may have qualifiers, where @const@ is most common.
\begin{cfa}
int x = 3; $\C{// mutable}$
const int cx = 5; $\C{// immutable}$
int * const cp = &x, $\C{// immutable pointer pointer/reference}$
        & const cr = cx;
const int * const ccp = &cx, $\C{// immutable value and pointer/reference}$
                        & const ccr = cx;
\end{cfa}
\begin{cquote}
\setlength{\tabcolsep}{26pt}
\begin{tabular}{@{}lll@{}}
pointer & reference & \\
\begin{cfa}
*cp = 7;
cp = &x;
*ccp = 7;
ccp = &cx;
\end{cfa}
&
\begin{cfa}
cr = 7;
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 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}
int & const mem_map = *0xe45bbc67@p@; $\C{// hardware mapped registers ('p' for pointer)}$
\end{cfa}
Finally, qualification is generalized across all pointer/reference declarations.
\begin{cfa}
const * const * const * const ccccp = ...
const & const & const & const ccccr = ...
\end{cfa}

In the initial \CFA reference design, the goal was to make the reference type a \emph{real} data type \vs a restricted \CC reference, which is mostly used for choosing the argument-passing method, \ie by-value or by-reference.
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.
For example, in
\begin{cfa}
int & x;
forall( T ) void foo( T );
forall( T ) void bar( T & );
foo( x ); $\C{// means pass by value}$
bar( x ); $\C{// means pass by reference}$
\end{cfa}
the call to @foo@ must pass @x@ by value, implying auto-dereference, while the call to @bar@ must pass @x@ by reference, implying no auto-dereference.
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, 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 example code on \VPageref{p:refexamples}:
\begin{cfa}
int @&@ r1 = x,  @&&@ r2 = r1,   @&&&@ r3 = r2; $\C{// references to x}$
\end{cfa}
each initialization expression is implicitly dereferenced to match the types, \eg @&x@, because an address is always required and a variable normally returns its value;
\CC does the same implicit dereference when initializing its reference variables.
For lines 6 and 9 of the previous example code:
\begin{cfa}
 r1 =  3;       r2 = 3;   r3 = 3;                               $\C{// change x: implicit dereference *r1, **r2, ***r3}$
@&@r3 = @&@y; @&&@r3 = @&&@r4;                          $\C{// change r1, r2}$
\end{cfa}
there are no actual assignment operators defined for reference types that can be overloaded;
instead, all reference assignments are handled by semantic actions in the type system.
In fact, the reassignment of reference variables is setup internally to use the assignment operators for pointer types.
Finally, there is an annoying issue (although purely syntactic) for setting a mutable reference to a specific address like null, @int & r1 = *0p@, which looks like dereferencing a null pointer.
Here, the expression is rewritten as @int & r1 = &(*0p)@, like the variable dereference of @x@ above.
However, the implicit @&@ needs to be cancelled for an address, which is done with the @*@, \ie @&*@ cancel each other, giving @0p@.
Therefore, the dereferencing operation does not actually happen and the expression is translated into directly initializing the reference variable with the address.
Note, the same explicit reference is used in \CC to set a reference variable to null.
\begin{c++}
int & ip = @*@(int *)nullptr;
\end{c++}
which is used in certain systems-programming situations.

When generic types were introduced to \CFA~\cite{Moss19}, some thought was given to allow reference types as type arguments.
\begin{cfa}
forall( T ) struct vector { T t; }; $\C{// generic type}$
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.
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 the \CFA programmer is forced to use a pointer type, giving up the benefits of auto-dereference operations and better syntax with reference types.


\section{Tuple Types}

The addition of tuples to \CFA can be traced back to the original design by David Till in \mbox{K-W C}~\cite{Till89,Buhr94a}, a predecessor project of \CFA.
The primary purpose of tuples is to eliminate output parameters or creating an aggregate type to return multiple values from a function, called a multiple-value-returning (MVR) function.
Traditionally, returning multiple values is accomplished via (in/)output parameters or packing the results in a structure.
The following examples show these two techniques for a function returning three values.
\begin{cquote}
\begin{tabular}{@{}l@{\hspace{20pt}}l@{}}
\begin{cfa}
int foo( int &p1, int &p2 );  // in/out parameters
int x, y = 3, z = 4;
x = foo( y, z );  // return 3 values: 1 out, 2 in/out
\end{cfa}
&
\begin{cfa}
struct Ret { int x, y, z; } ret;
Ret foo( int p1, int p2 );  // return structure
ret = foo( 3, 4 );  // return 3 values: 3 out
\end{cfa}
\end{tabular}
\end{cquote}
Like Go, K-W C allows direct return of multiple values into a tuple.
\begin{cfa}
@[int, int, int]@ foo( int p1, int p2 );
@[x, y, z]@ = foo( 3, 4 );  // return 3 values into a tuple
\end{cfa}
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 may be different}$
[x, y] = [y, x]; $\C{// int tmp = x; x = y; y = tmp;}$
void bar( int, int, int );
bar( foo( 3, 4 ) ); $\C{// int t0, t1, t2; [t0, t1, t2] = foo( 3, 4 ); bar( t0, t1, t2 );}$
x = foo( 3, 4 )@.1@; $\C{//  int t0, t1, t2; [t0, t1, t2] = foo( 3, 4 ); x = t1;}\CRT$
\end{cfa}
For the call to @bar@, the three results (tuple value) from @foo@ are \newterm{flattened} into individual arguments.
Flattening is how tuples interact with parameter and subscript lists, and with other tuples, \eg:
\begin{cfa}
[ [ x, y ], z, [a, b, c] ] = [2, [3, 4], foo( 3, 4) ]  $\C{// structured}$
[ x, y, z, a, b, c] = [2, 3, 4, foo( 3, 4) ]  $\C{// flattened, where foo results are t0, t1, t2}$
\end{cfa}
Note, in most cases, a tuple is just compile-time syntactic-sugar for a number of individual assignments statements and possibly temporary variables.
Only when returning a tuple from a function is there the notion of a tuple value.

Overloading in the \CFA type-system must support complex composition of tuples and C type conversions using a costing scheme giving lower cost to widening conversions that do not truncate a value.
\begin{cfa}
[ int, int ] foo$\(_1\)$( int );                        $\C{// overloaded foo functions}$
[ double ] foo$\(_2\)$( int );
void bar( int, double, double );
bar( @foo@( 3 ), @foo@( 3 ) );
\end{cfa}
The type resolver only has the tuple return types to resolve the call to @bar@ as the @foo@ parameters are identical.
The resultion involves unifying the flattened @foo@ return values with @bar@'s parameter list.
However, no combination of @foo@s is an exact match with @bar@'s parameters;
thus, the resolver applies C conversions to obtain a best match.
The resulting minimal cost expression is @bar( foo@$_1$@( 3 ), foo@$_2$@( 3 ) )@, where the two possible coversions are (@int@, {\color{red}@int@}, @double@) to (@int@, {\color{red}@double@}, @double@) with a safe (widening) conversion from @int@ to @double@ versus ({\color{red}@double@}, {\color{red}@int@}, {\color{red}@int@}) to ({\color{red}@int@}, {\color{red}@double@}, {\color{red}@double@}) with one unsafe (narrowing) conversion from @double@ to @int@ and two safe conversions from @int@ to @double@.
Go provides a simplified mechanism where only one tuple returning function call is allowed and there are no implicit type conversions.
\begin{lstlisting}[language=Go]
func foo( int ) ( int, int, int ) { return 3, 7, 8 }
func bar( int, int, int ) { ... } // types must match
bar( foo( 3 ) ) // only one tuple returning call 
\end{lstlisting}
Hence, programers cannot take advantage of the full power of tuples but type match is straightforward.

K-W C also supported tuple variables, but with a strong distinction between tuples and tuple values/variables.
\begin{quote}
Note that tuple variables are not themselves tuples.
Tuple variables reference contiguous areas of storage, in which tuple values are stored;
tuple variables and tuple values are entities which appear during program execution.
Tuples, on the other hand, are compile-time constructs;
they are lists of expressions, whose values may not be stored contiguously.~\cite[p.~30]{Till89}
\end{quote}
Fundamentally, a tuple value/variable is just a structure (contiguous areas) with an alternate (tuple) interface.
A tuple value/variable is assignable (like structures), its fields can be accessed using position rather than name qualification, and it can interact with regular tuples.
\begin{cfa}
[ int, int, int ] t1, t2;
t1 = t2;                        $\C{// tuple assignment}$
t1@.1@ = t2@.0@;        $\C{// position qualification}$
int x, y, z;
t1 = [ x, y, z ];       $\C{// interact with regular tuples}$
[ x, y, z ] = t1;
bar( t2 );                      $\C{// bar defined above}$
\end{cfa}
\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.
The right \CFA nested tuple cannot be named and is flattened.
C allows named nested-structures, but they have issues \see{\VRef{s:inlineSubstructure}}.
Note, it is common in C to have an unnamed @union@ so its fields do not require qualification.

\begin{figure}
\setlength{\tabcolsep}{20pt}
\begin{tabular}{@{}ll@{\hspace{90pt}}l@{}}
\multicolumn{1}{c}{\CC} & \multicolumn{1}{c}{C/\CC} & \multicolumn{1}{c}{tuple} \\
\begin{cfa}
struct S {
        struct @T@ { // not flattened
                int i, j;
        };
        int i, j;
};
\end{cfa}
&
\begin{cfa}
struct S2 {
        struct ${\color{red}/* unnamed */}$ { // flatten
                int i, j;
        };
        int i, j;
};
\end{cfa}
&
\begin{cfa}
[
        [ // flatten
                1, 2
        ]
        1, 2
]
\end{cfa}
\end{tabular}
\caption{Nesting}
\label{f:Nesting}
\end{figure}

The primary issues for tuples in the \CFA type system are polymorphism and conversions.
Specifically, does it make sense to have a generic (polymorphic) tuple type, as is possible for a structure?
\begin{cfa}
forall( T, S ) [ T, S ] GT; // polymorphic tuple type
GT( int, char ) @gt@;
GT( int, double ) @gt@;
@gt@ = [ 3, 'a' ];  // select correct gt
@gt@ = [ 3, 3.5 ];
\end{cfa}
and what is the cost model for C conversions across multiple values?
\begin{cfa}
gt = [ 'a', 3L ];  // select correct gt
\end{cfa}


\section{Tuple Implementation}

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@, \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.
The return values are converted to output parameters passed in by pointers.
When the return values of a MVR function are directly used in an assignment expression, the addresses of the left-hand operands can be directly passed into the function;
composition of MVR functions is handled by creating temporaries for the returns.
For example, given a function returning two values:
\begin{cfa}
[int, int] gives_two() { int r1, r2; ... return [ r1, r2 ]; }
int x, y;
[x, y] = gives_two();
\end{cfa}
\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 individually 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 upside of the right implementation is consistence and no 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 & Esteves \CFA implementation \\
\begin{cfa}
struct _tuple2 { int _0; int _1; }
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}
&
\begin{cfa}

void gives_two( int * r1, int * r2 ) {
        ... *r1 = ...; *r2 = ...;
        return;
}
int x, y;

gives_two( &x, &y );
\end{cfa}
\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 is a uniform approach for tuple values/variables making tuples first-class types in \CFA, \ie allow tuples with corresponding tuple variables.
This reversion 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 for generic variables~\cite[\S~3.7]{Schluntz17}.
For example, these two tuples:
\begin{cfa}
[double, double] x;
[int, double, int] y;
\end{cfa}
are transformed internally into two generic structures:
\begin{cfa}
forall( T0 &, & T1 | sized( T0 ) | sized( T1 ) )
struct _tuple2_ {
        T0 field_0 ;   T1 field_1 ;
};
forall( T0 &, T1 &, T2 & | sized( T0 ) | sized( T1 ) | sized( T2 ) )
struct _tuple3_ {
        T0 field_0 ;   T1 field_1 ;   T2 field_2 ;
};
\end{cfa}
and the declarations become instances of these generic structure types:
\begin{cfa}
_tuple2_( double, double ) x;
_tuple3_( int, double, int ) y;
\end{cfa}
Now types @_tuple2_@ and @_tuple3_@ are available for any further 2 or 3 tuple-types in the translation unit, simplifying internal code transformations by memoizing a small set of tuple structures.
Ultimately, these generic types are lowered to specific C structures during code generation.
Scala, like \CC, provides tuple types through a library using this structural expansion, \eg Scala provides tuple sizes 1 through 22 via hand-coded generic data-structures.

However, after experience gained building the \CFA runtime system, making tuple-types first-class seems to add little benefit.
The main reason is that tuples usages are largely unstructured,
\begin{cfa}
[int, int] foo( int, int ); $\C[2in]{// unstructured function}$
typedef [int, int] Pair; $\C{// tuple type}$
Pair bar( Pair ); $\C{// structured function}$
int x = 3, y = 4;
[x, y] = foo( x, y ); $\C{// unstructured call}$
Pair ret = [3, 4]; $\C{// tuple variable}$
ret = bar( ret ); $\C{// structured call}\CRT$
\end{cfa}
Basically, creating the tuple-type @Pair@ is largely equivalent to creating a @struct@ type, and creating more types and names defeats the simplicity that tuples are trying to achieve.
Furthermore, since operator overloading in \CFA is implemented by treating operators as overloadable functions, tuple types are very rarely used in a structured way.
When a tuple-type expression appears in a function call (except assignment expressions, which are handled differently by mass- or multiple-assignment expansions), it is always flattened, and the tuple structure of function parameter is not considered a part of the function signatures.
For example, these two prototypes for @foo@:
\begin{cfa}
void f( int, int );
void f( @[@ int, int @]@ );
f( 3, 4 );  // ambiguous call
\end{cfa}
have the same signature (a function taking two @int@s and returning nothing), and therefore invalid overloads.
Note, the ambiguity error occurs at the call rather than at the second declaration of @f@, because it is possible to have multiple equivalent prototype definitions of a function.
Furthermore, ordinary polymorphic type-parameters are not allowed to have tuple types.
\begin{cfa}
forall( T ) T foo( T );
int x, y, z;
[x, y, z] = foo( [x, y, z] );  // substitute tuple type for T
\end{cfa}
Without this restriction, the expression resolution algorithm can create too many argument-parameter matching options.
For example, with multiple type parameters,
\begin{cfa}
forall( T, U ) void f( T, U );
f( [1, 2, 3, 4] );
\end{cfa}
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, because of the flattening.

\begin{comment}
Date: Mon, 13 Jan 2025 10:09:06 -0500
Subject: Re: structure / tuple
To: "Peter A. Buhr" <pabuhr@uwaterloo.ca>
CC: Andrew Beach <ajbeach@uwaterloo.ca>,
        Michael Brooks <mlbrooks@uwaterloo.ca>,
        Fangren Yu <f37yu@uwaterloo.ca>, Jiada Liang <j82liang@uwaterloo.ca>,
        Alvin Zhang <alvin.zhang@uwaterloo.ca>,
        Kyoung Seo <lseo@plg.uwaterloo.ca>
From: Gregor Richards <gregor.richards@uwaterloo.ca>

Languages support tuples to abbreviate syntax where the meaning of several
values is obvious from context, such as returns from functions, or where the
effort of creating a dedicated type is not worth the reward of using that type
in exactly one location. The positions always have meanings which could be
given names, and are only not given names for brevity. Whether that brevity is
a good idea or not is the programmer's problem to deal with. I don't think
there's any pragmatic value to tuples beyond brevity. (From a theoretical
perspective, having the empty tuple is useful for type-theoretical reasons, and
tuples are usually easier to reason about than structures, but that only
applies to theoretical reasoning, not to actual programming.)

Your distinction unstructured tuples could just as well be made for structs as
well, if you had named arguments (or named returns?).  Personally, I think that
having these be a syntactic distinction is a mistake. Other languages return
fully codified tuples, and if you immediately destructure them, even the most
naive optimizer will manage to never create an actual tuple in memory. In my
opinion, since tuples are for brevity, they should always be declared with your
"unstructured" syntax, and it's up to the optimizer to realize when you've
never stored them. But, you live closer to the metal in CFA than most
languages, so perhaps communicating that intent is of sufficient value.

The only value of tuples beyond that is to make it possible for annoying
students to use std::pair in place of ever creating their own class hierarchy
or naming things. Then again, I hear that that is one of the hard problems in
computer science.

With valediction,
  - Gregor Richards

On 1/13/25 09:11, Peter A. Buhr wrote:
> The CFA team has been discussing the difference between a structure and
> tuple.  Basically, a structure has named fields and a tuple has anonymous
> fields. As a result, structure access uses field names and tuple access uses
> position.
>
>    struct S { int i, j, k ; };
>    S s;
>    s.i; s.j; // field access
>
>    tuple T { int, int };
>    T t;
>    t.0; t.1; // position access, zero origin
>    t[0]; t[1]; // alternate access
>
> Hence the difference is small.
>
> In CFA, we differentiate between unstructured and structured tuples. An
> unstructured tuple is a lexical grouping of potentially disjoint variables.
>
>    [ int, int, int ] f();
>    void g( int, int, int );
>    x, y, z = f(); // Go unstructured tuple, flatten tuple
>    g( foo() ); // flatten tuple
>
> Here, the tuple returned from f is flattened into disjoint variables.  A
> structured tuple is like above and has contiguous memory.
>
> CFA has fancy unstructured stuff like
>
>    s.[i,k] += 1; // add 1 to each field
>    t.[1,0] = 1; // don't think this works but could
>
> which is just an unstructured tuple access (sugar).
>
> What is your opinion of structures and tuples since the difference is
> small. Why do many languages support both features? Are we missing some
> important aspect of tuples that differentiates them from structures?  Is CFA
> unique in having both unstructured and structured tuples?
\end{comment}

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.
\begin{cfa}
int printf( const char * format, ${\color{red}\LARGE ...}$ );  // variadic list of variables to print
\end{cfa}
\VRef[Figure]{f:CVariadicMaxFunction} shows an $N$ argument @maxd@ function using the C untyped @va_list@ interface.
In the example, the first argument is the number of following arguments, and the following arguments are assumed to be @double@;
looping is used to traverse the argument pack from left to right.
The @va_list@ interface is walking up the stack (by address) looking at the arguments pushed by the caller.
(Magic knowledge is needed for arguments pushed using registers.)

\begin{figure}
\begin{cfa}
double maxd( int @count@, @...@ ) { // ellipse parameter
        double max = 0;
        va_list args;
        va_start( args, count );
        for ( int i = 0; i < count; i += 1 ) {
                double num = va_arg( args, double );
                if ( num > max ) max = num;
        }
        va_end(args);
        return max;
}
printf( "%g\n", maxd( @4@, 25.0, 27.3, 26.9, 25.7 ) );
\end{cfa}
\caption{C Variadic Maximum Function}
\label{f:CVariadicMaxFunction}
\end{figure}

There are two common patterns for using variadic functions in \CFA.
\begin{enumerate}[leftmargin=*]
\item
Argument forwarding to another function, \eg:
\begin{cfa}
forall( T *, TT ... | { @void ?{}( T &, TT );@ } ) // constructor assertion
T * new( TT tp ) { return ((T *)malloc())@{@ tp @}@; }  // call constructor on storage
\end{cfa}
Note, the assertion on @T@ requires it to have a constructor @?{}@.
The function @new@ calls @malloc@ to obtain storage and then invokes @T@'s constructor passing the tuple pack by flattening it over the constructor's arguments, \eg:
\begin{cfa}
struct S { int i, j; };
void ?{}( S & s, int i, int j ) { s.[ i, j ] = [ i, j ]; }  // constructor
S * sp = new( 3, 4 );  // flatten [3, 4] into call ?{}( 3, 4 );
\end{cfa}
\item
Structural recursion for processing the argument-pack values one at a time, \eg:
\begin{cfa}
forall( T | { int ?<?( T, T ); } )
T max( T v1, T v2 ) { return v1 < v2 ? v2 : v1; }
$\vspace{-10pt}$
forall( T, TT ... | { T max( T, T ); T max( TT ); } )
T max( T arg, TT args ) { return max( arg, max( args ) ); }
\end{cfa}
The first non-recursive @max@ function is the polymorphic base-case for the recursion, \ie, find the maximum of two identically typed values with a less-than (@<@) operator.
The second recursive @max@ function takes two parameters, @T@ and the @TT@ tuple pack, handling all argument lengths greater than two.
The recursive function computes the maximum for the first argument and the maximum value of the rest of the tuple pack.
The call of @max@ with one argument is the recursive call, where the tuple pack is converted into two arguments by taking the first value (lisp @car@) from the tuple pack as the first argument (flattening) and the remaining pack becomes the second argument (lisp @cdr@).
The recursion stops when the argument pack is empty.
For example, @max( 2, 3, 4 )@ matches with the recursive function, which performs @return max( 2, max( [3, 4] ) )@ and one more step yields @return max( 2, max( 3, 4 ) )@, so the tuple pack is empty.
\end{enumerate}

As an aside, polymorphic functions are precise with respect to their parameter types, \eg @max@ states all argument values must be the same type, which logically makes sense.
However, this precision precludes normal C conversions among the base types, \eg, this mix-mode call @max( 2h, 2l, 3.0f, 3.0ld )@ fails because the types are not the same.
Unfortunately, this failure violates programmer intuition because there are specialized two-argument non-polymorphic versions of @max@ that work, \eg @max( 3, 3.5 )@.
Allowing C conversions for polymorphic types will require a significant change to the type resolver.

Currently in \CFA, variadic polymorphic functions are the only place tuple types are used.
And because \CFA compiles polymorphic functions versus template expansion, many wrapper functions are generated to implement both user-defined generic-types and polymorphism with variadics.
Fortunately, the only permitted operations on polymorphic function parameters are given by the list of assertion (trait) functions.
Nevertheless, this small set of functions eventually needs to be called with flattened tuple arguments.
Unfortunately, packing the variadic arguments into a rigid @struct@ type and generating all the required wrapper functions is significant work and largely wasted because most are never called.
Interested readers can refer to pages 77-80 of Robert Schluntz's thesis to see how verbose the translator output is to implement a simple variadic call with 3 arguments.
As the number of arguments increases, \eg a call with 5 arguments, the translator generates a concrete @struct@ types for a 4-tuple and a 3-tuple along with all the polymorphic type data for them.
An alternative approach is to put the variadic arguments into an array, along with an offset array to retrieve each individual argument.
This method is similar to how the C @va_list@ object is used (and how \CFA accesses polymorphic fields in a generic type), but the \CFA variadics generate the required type information to guarantee type safety (like the @printf@ format string).
For example, given the following heterogeneous, variadic, typed @print@ and usage:
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\begin{cfa}
forall( T, TT ... | { void print( T ); void print( TT ); } )
void print( T arg , TT rest ) {
        print( arg );
        print( rest );
}
\end{cfa}
&
\begin{cfa}
void print( int i ) { printf( "%d ", i ); }
void print( double d ) { printf( "%g ", d ); }
... // other types
int i = 3 ; double d = 3.5;
print( i, d );
\end{cfa}
\end{tabular}
\end{cquote}
it would look like the following using the offset-array implementation approach.
\begin{cfa}
void print( T arg, char * _data_rest, size_t * _offset_rest ) {
        print( arg );
        print( *((typeof rest.0)*) _data_rest,  $\C{// first element of rest}$
                  _data_rest + _offset_rest[0],  $\C{// remainder of data}$
                  _offset_rest + 1);  $\C{// remainder of offset array}$
}
\end{cfa}
where the fixed-arg polymorphism for @T@ can be handled by the standard @void *@-based \CFA polymorphic calling conventions, and the type information can be deduced at the call site.
Note, the variadic @print@ supports heterogeneous types because the polymorphic @T@ is not returned (unlike variadic @max@), so there is no cascade of type relationships.

Turning tuples into first-class values in \CFA does have a few benefits, namely allowing pointers to tuples and arrays of tuples to exist.
However, it seems unlikely that these types have realistic use cases that cannot be achieved with structures.
And having a pointer-to-tuple type potentially forbids the simple offset-array implementation of variadic polymorphism.
For example, in the case where a type assertion requests the pointer type @TT *@ in the above example, it forces the tuple type to be a @struct@, and thus incurring a high cost.
My conclusion is that tuples should not be structured (first-class), rather they should be unstructured.
This agrees with Rodolfo's original description:
\begin{quote}
As such, their [tuples] use does not enforce a particular memory layout, and in particular, does not guarantee that the components of a tuple occupy a contiguous region of memory.~\cite[pp.~74--75]{Esteves04}
\end{quote}
allowing the simplified implementations for MVR and variadic functions.

Finally, a missing feature for tuples is using an MVR in an initialization context.
Currently, this feature is \emph{only} possible when declaring a tuple variable.
\begin{cfa}
[int, int] ret = gives_two();  $\C{// no constructor call (unstructured)}$
Pair ret = gives_two();  $\C{// constructor call (structured)}$
\end{cfa}
However, this forces the programer to use a tuple variable and possibly a tuple type to support a constructor, when they actually want separate variables with separate constructors.
And as stated previously, type variables (structured tuples) are rare in general \CFA programming so far.
To address this issue, while retaining the ability to leverage constructors, I proposed the following new tuple-like declaration syntax.
\begin{cfa}
[ int x, int y ] = gives_two();
\end{cfa}
where the semantics is:
\begin{cfa}
T t0, t1;
[ t0, t1 ] = gives_two();
T x = t0;  // constructor call
T y = t1;  // constructor call
\end{cfa}
and the implementation performs as much copy elision as possible.
Currently, this new declaration form is parsed by \CFA, showing its syntax is viable, but it is unimplemented because of downstream resolver issues.


\section{\lstinline{inline} Substructure}
\label{s:inlineSubstructure}

As mentioned, C allows an anonymous aggregate type (@struct@ or @union@) to be embedded (nested) within another one \see{\VRef[Figure]{f:Nesting}}, \eg a tagged union.
\begin{cfa}
struct S {
        unsigned int tag;
        union { // anonymous nested aggregate
                int x;  double y;  char z;
        };
} s;
\end{cfa}
Here, the @union@ combines its field into a common block of storage, and because there is no variable-name overloading in C, all of the union field names must be unique.
Furthermore, because the union is unnamed, these field-names are hoisted into the @struct@, giving direct access, \eg @s.x@;
hence, the union field names must be unique with the structure field names.
The same semantics applies to a nested anonymous @struct@:
\begin{cquote}
\begin{tabular}{@{}l@{\hspace{35pt}}l@{}}
original & rewritten \\
\begin{cfa}
struct S {
        struct { int i, j; };
        struct { int k, l; };
};
\end{cfa}
&
\begin{cfa}
struct S {
        int i, j;
        int k, l;
};
\end{cfa}
\end{tabular}
\end{cquote}
However, unlike the union which provides storage sharing, there is no semantic difference between the nested anonymous structure and its rewritten counterpart.
Hence, the nested anonymous structure provides no useful capability.

Nested \emph{named} aggregates are allowed in C but there is no qualification operator, like the \CC type operator `@::@', to access an inner type.
\emph{To compensate for the missing type operator, all named nested aggregates are hoisted to global scope, regardless of the nesting depth, and type usages within the nested type are replaced with global type name.}
Hoisting nested types can result in name collisions among types at the global level, which defeats the purpose of nesting the type.
\VRef[Figure]{f:NestedNamedAggregate} shows the nested type @T@ is hoisted to the global scope and the declaration rewrites within structure @S@.
Hence, the possible accesses are:
\begin{cfa}
struct S s;
s.i = 1;
s.t.i = 2;
s.w = (struct T){ 7, 8 };
struct T x = { 5, 6 }; // use (un)nested type name
s.t = (struct T){ 2, 3 };
\end{cfa}
where @T@ is used without qualification even though it is nested in @S@.
It is for these reasons that nested types are not used in C, and if used, are extremely confusing.

\begin{figure}
\begin{cquote}
\begin{tabular}{@{}l@{\hspace{35pt}}l@{}}
original & rewritten \\
\begin{cfa}
struct S {
        @struct T@ {
                int i, j;
        } t; // warning without declaration
        struct T w;
        int k;
};

\end{cfa}
&
\begin{cfa}
@struct T@ {
        int i, j;
};
struct S {
        @struct T t@;
        struct T w;
        int k;
};
\end{cfa}
\end{tabular}
\end{cquote}
\caption{Nested Named Aggregate}
\label{f:NestedNamedAggregate}
\end{figure}

For good reasons, \CC chose to change this semantics:
\begin{cquote}
\begin{description}[leftmargin=*,topsep=0pt,itemsep=0pt,parsep=0pt]
\item[Change:] A struct is a scope in C++, not in C.
\item[Rationale:] Class scope is crucial to C++, and a struct is a class.
\item[Effect on original feature:] Change to semantics of well-defined feature.
\item[Difficulty of converting:] Semantic transformation.
\item[How widely used:] C programs use @struct@ extremely frequently, but the change is only noticeable when @struct@, enumeration, or enumerator names are referred to outside the @struct@.
The latter is probably rare.
\end{description}
\hfill ISO/IEC 14882:1998 (\CC Programming Language Standard)~\cite[C.1.2.3.3]{ANSI98:C++}
\end{cquote}
\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.i@;  @s.T@.i;
\end{cfa}
See the use case for this feature at the end of this section.

% https://gcc.gnu.org/onlinedocs/gcc/Unnamed-Fields.html

A polymorphic extension to nested aggregates appears in the Plan-9 C dialect, used in the Bell Labs' Plan-9 research operating-system.
The feature is called \newterm{unnamed substructures}~\cite[\S~3.3]{Thompson90new}, which continues to be supported by @gcc@ and @clang@ using the extension (@-fplan9-extensions@).
The goal is to provided the same effect as a nested aggregate with the aggregate type defined elsewhere, which requires it be named.
\begin{cfa}
union U {  $\C{// unnested named}$
        int x;  double y;  char z;
} u;
struct W {
        int i;  double j;  char k;
} w;
struct S {
        @struct W;@  $\C{// Plan-9 substructure}$
        unsigned int tag;
        @union U;@  $\C{// Plan-9 substructure}$
} s;
\end{cfa}
Note, the position of the substructure is normally unimportant, unless there is some form of memory or @union@ overlay.
Like an anonymous nested type, a named Plan-9 nested 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 = &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}
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@ struct W;  $\C{// extended Plan-9 substructure}$
        unsigned int tag;
        @inline@ U;  $\C{// extended Plan-9 substructure}$
} s;
\end{cfa}
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 is 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}$
f( s, &s ); $\C{// value, pointer}$
g( s, &s ); $\C{// value, pointer}$
\end{cfa}

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 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 arithmetic conversions.

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; };
struct B { inline A; };
struct C { inline A; };
struct D {
        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 qualification 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 must exist.