Changeset 8fe7a85


Ignore:
Timestamp:
May 12, 2025, 8:33:55 PM (5 months ago)
Author:
Fangren Yu <f37yu@…>
Branches:
master
Children:
edd11bd
Parents:
98c77b2
Message:

proofreading changes from Gregor

Location:
doc/theses/fangren_yu_MMath
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/fangren_yu_MMath/features.tex

    r98c77b2 r8fe7a85  
    1313Here, manipulating the pointer address is the primary operation, while dereferencing the pointer to its value is the secondary operation.
    1414For 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.
    15 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).
     15Alternatively, use a reference when its primary purpose is to alias a value, \eg a function parameter that does not copy the argument, for performance reasons.
    1616Here, manipulating the value is the primary operation, while changing the pointer address is the secondary operation.
    1717Succinctly, if the address changes often, use a pointer;
    … …  
    6464The call applies an implicit dereference once to @x@ so the call is typed @f( int & )@ with @T = int@, rather than with @T = int &@.
    6565
    66 As for a pointer type, a reference type may have qualifiers, where @const@ is most common.
     66As with a pointer type, a reference type may have qualifiers, where @const@ is most common.
    6767\begin{cfa}
    6868int x = 3; $\C{// mutable}$
    … …  
    188188@[x, y, z]@ = foo( 3, 4 );  // return 3 values into a tuple
    189189\end{cfa}
    190 Along with making returning multiple values a first-class feature, tuples were extended to simplify a number of other common contexts that normally require multiple statements and/or additional declarations, all of which reduces coding time and errors.
     190Along with making returning multiple values a first-class feature, tuples were extended to simplify a number of other common contexts that normally require multiple statements and/or additional declarations.
    191191\begin{cfa}
    192192[x, y, z] = 3; $\C[2in]{// x = 3; y = 3; z = 3, where types may be different}$
    … …  
    205205Only when returning a tuple from a function is there the notion of a tuple value.
    206206
    207 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.
     207Overloading in the \CFA type-system must support complex composition of tuples and C type conversions using a conversion cost scheme giving lower cost to widening conversions that do not truncate a value.
    208208\begin{cfa}
    209209[ int, int ] foo$\(_1\)$( int );                        $\C{// overloaded foo functions}$
    … …  
    223223bar( foo( 3 ) ) // only one tuple returning call
    224224\end{lstlisting}
    225 Hence, programers cannot take advantage of the full power of tuples but type match is straightforward.
     225Hence, programmers cannot take advantage of the full power of tuples but type match is straightforward.
    226226
    227227K-W C also supported tuple variables, but with a strong distinction between tuples and tuple values/variables.
    … …  
    356356\end{figure}
    357357
    358 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.
     358Interestingly, in the third implementation of \CFA tuples by Robert Schluntz~\cite[\S~3]{Schluntz17}, the MVR functions revert back to structure based, and this remains in the current version of \CFA.
    359359The 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.
    360360This 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}.
    … …  
    512512looping is used to traverse the argument pack from left to right.
    513513The @va_list@ interface is walking up the stack (by address) looking at the arguments pushed by the caller.
    514 (Magic knowledge is needed for arguments pushed using registers.)
     514(Compiler-specific ABI knowledge is needed for arguments pushed using registers.)
    515515
    516516\begin{figure}
    … …  
    683683
    684684Nested \emph{named} aggregates are allowed in C but there is no qualification operator, like the \CC type operator `@::@', to access an inner type.
    685 \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.}
     685To 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.
    686686Hoisting nested types can result in name collisions among types at the global level, which defeats the purpose of nesting the type.
    687687\VRef[Figure]{f:NestedNamedAggregate} shows the nested type @T@ is hoisted to the global scope and the declaration rewrites within structure @S@.
    … …  
    729729\end{figure}
    730730
    731 For good reasons, \CC chose to change this semantics:
     731\CC chose to change this semantics:
    732732\begin{cquote}
    733733\begin{description}[leftmargin=*,topsep=0pt,itemsep=0pt,parsep=0pt]
    … …  
    769769Like 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@.
    770770Hence, 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.
    771 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:
     771In 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@ $<:$ @S@ and @W@ $<:$ @S@, \eg:
    772772\begin{cfa}
    773773void f( union U * u );
    … …  
    781781Note, there is no value assignment, such as, @w = s@, to copy the @W@ field from @S@.
    782782
    783 Unfortunately, the Plan-9 designers did not lookahead to other useful features, specifically nested types.
     783Unfortunately, the Plan-9 designers did not look ahead to other useful features, specifically nested types.
    784784This nested type compiles in \CC and \CFA.
    785785\begin{cfa}
    … …  
    808808In addition, a semi-non-compatible change is made so that Plan-9 syntax means a forward declaration in a nested type.
    809809Since the Plan-9 extension is not part of C and rarely used, this change has minimal impact.
    810 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.
     810Hence, all Plan-9 semantics are denoted by the @inline@ qualifier, which clearly indicates the usage of Plan-9 definitions.
    811811Finally, the following code shows the value and pointer polymorphism.
    812812\begin{cfa}
    … …  
    847847\end{c++}
    848848and again the expression @d.x@ is ambiguous.
    849 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@.
     849While \CC has no direct syntax to disambiguate @x@, \eg @d.B.x@ or @d.C.x@, it is possible with casts, @((B)d).x@ or @((C)d).x@.
    850850Like \CC, \CFA compiles the Plan-9 version and provides direct qualification and casts to disambiguate @x@.
    851851While ambiguous definitions are allowed, duplicate field names are poor practice and should be avoided if possible.

  • doc/theses/fangren_yu_MMath/future.tex

    r98c77b2 r8fe7a85  
    88\section{Closed Trait Types}
    99
    10 Currently, \CFA does not have any closed types, as open type are the basis of its unique type-system, allowing new functions to be added at any time to override existing ones for trait satisfaction.
     10Currently, \CFA does not have any closed types, as open types are the basis of its unique type-system, allowing new functions to be added at any time to override existing ones for trait satisfaction.
    1111Locally-declared nested-functions,\footnote{
    1212Nested functions are not a feature in C but supported by \lstinline{gcc} for multiple decades and are used heavily in \CFA.}
    … …  
    1717Library implementers normally do not want users to override certain operations and cause the behaviour of polymorphic invocations to change.
    1818\item
    19 Caching and reusing resolution results in the compiler is effected, as newly introduced declarations can participate in assertion resolution;
     19Caching and reusing resolution results in the compiler is affected, as newly introduced declarations can participate in assertion resolution;
    2020as a result, previously invalid subexpressions suddenly become valid, or alternatively cause ambiguity in assertions.
    2121\end{enumerate}
    … …  
    7070\end{figure}
    7171
    72 A \CFA closed trait type is similar to a Haskell type class requiring an explicit instance declaration.
     72A \CFA closed trait type is planned to be working similarly to a Haskell type class that requires an explicit instance declaration.
    7373The syntax for the closed trait might look like:
    7474\begin{cfa}
    … …  
    9191
    9292\section{Associated Types}
     93\label{s:AssociatedTypes}
    9394
    9495The analysis presented in \VRef{s:AssertionSatisfaction} shows if all type parameters have to be bound before assertion resolution, the complexity of resolving assertions becomes much lower as every assertion parameter can be resolved independently.
    … …  
    159160\section{User-defined Conversions}
    160161
    161 Missing type-system feature is a scheme for user-defined conversions.
     162A missing type-system feature in \CFA is a scheme for user-defined conversions.
    162163Conversion means one type goes through an arbitrary complex process of changing its value to some meaningful value in another type.
    163164Because the conversion process can be arbitrarily complex, it requires the power of a function.

  • doc/theses/fangren_yu_MMath/resolution.tex

    r98c77b2 r8fe7a85  
    22\label{c:content2}
    33
    4 Recapping, the \CFA's type-system provides expressive polymorphism: variables can be overloaded, functions can be overloaded by argument and return types, tuple types, generic (polymorphic) functions and types (aggregates) can have multiple type parameters with assertion restrictions;
     4Recapping, \CFA's type-system provides expressive polymorphism: variables can be overloaded, functions can be overloaded by argument and return types, tuple types, generic (polymorphic) functions and types (aggregates) can have multiple type parameters with assertion restrictions;
    55in addition, C's multiple implicit type-conversions must be respected.
    66This generality leads to internal complexity and correspondingly higher compilation cost directly related to type resolution.
    … …  
    2424\end{enumerate}
    2525\VRef[Table]{t:SelectedFileByCompilerBuild} shows improvements for selected tests with accumulated reductions in compile time across each of the 5 fixes.
    26 To this day, the large reduction in compilation time significantly improves the development of the \CFA's runtime because of its frequent compilation cycles.
     26The large reduction in compilation time significantly improves the development of the \CFA's runtime because of its frequent compilation cycles.
    2727
    2828\begin{table}[htb]
    … …  
    8686
    8787\item \textbf{Safe} cost representing a widening conversion \eg @short@ to @int@, qualifier-adding conversions for pointer and reference types, and value conversion for enumeration constants.
    88 Even when conversions are safe, the fewest conversions it ranked better, \eg @short@ to @int@ versus @short@ to @long int@.
     88When all conversions are safe, closer conversions are ranked better, \eg @short@ to @int@ versus @short@ to @long int@.
    8989\begin{cfa}
    9090void f( long int p ); $\C[2.5in]{// 1}$
    … …  
    110110\end{cfa}
    111111\end{enumerate}
    112 Cost tuples are compared by lexicographical order, from unsafe (highest) to specialization (lowest), with ties moving to the next lowest item.
     112Cost tuples are compared in lexicographical order, from unsafe (highest) to specialization (lowest), with ties moving to the next lowest item.
    113113At a subexpression level, the lowest cost candidate for each result type is included as a possible interpretation of the expression;
    114114at the top level, all possible interpretations of different types are considered (generating a total ordering) and the overall lowest cost is selected as the final interpretation of the expression.
    115115Glen Ditchfield first proposed this costing model~\cite[\S~4.4.5]{Ditchfield92} to generate a resolution behaviour that is reasonable to C programmers based on existing conversions in the C programming language.
    116116This model carried over into the first implementation of the \CFA type-system by Richard Bilson~\cite[\S~2.2]{Bilson03}, and was extended but not redesigned by Aaron Moss~\cite[chap.~4]{Moss19}.
    117 Moss's work began to show problems with the underlying costing model;
     117Moss's work began to show problems with the underlying cost model;
    118118these design issues are part of this work.
    119119
    … …  
    171171Other than the case of multiple exact matches, where all have cost zero, incomparable candidates under a partial ordering can often have different expression costs since different kinds of implicit conversions are involved, resulting in seemingly arbitrary overload selections.
    172172
    173 There are currently at least three different situations where the polymorphic cost element of the cost model does not yield a candidate selection that is clearly justifiable, and one of them is straight up wrong.
     173There are currently at least three different situations where the polymorphic cost element of the cost model does not yield a candidate selection that is justifiable, and one of them is clearly wrong.
    174174\begin{enumerate}[leftmargin=*]
    175175\item Polymorphic exact match versus non-polymorphic inexact match.
    … …  
    193193\end{itemize}
    194194In this example, option 1 produces the prototype @void f( int )@, which gives an exact match and therefore takes priority.
    195 The \CC resolution rules effectively make option 2 a specialization that only applies to type @long@ exactly,\footnote{\CC does have explicit template specializations, however they do not participate directly in overload resolution and can sometimes lead to unintuitive results.} while the current \CFA rules make option 2 apply for all integral types below @long@.
     195The \CC resolution rules effectively make option 2 a specialization that only applies to type @long@ exactly,\footnote{\CC does have explicit template specializations, however they do not participate directly in overload resolution and can sometimes lead to unintuitive results.} while the current \CFA rules make option 2 apply for all integral types ranked lower than @long@ as well.
    196196This difference could be explained as compensating for \CFA polymorphic functions being separately compiled versus template inlining;
    197197hence, calling them requires passing type information and assertions increasing the runtime cost.
    … …  
    227227Passing a @pair@ variable to @f@
    228228\begin{cfa}
    229 pair p;
     229pair(int, double) p;
    230230f( p );
    231231\end{cfa}
    232232gives a cost of 1 poly, 2 variable for the @pair@ overload, versus a cost of 1 poly, 1 variable for the unconstrained overload.
    233233Programmer expectation is to select option 1 because of the exact match, but the cost model selects 2;
    234 while either could work, the type system should select a call that meets expectation of say the call is ambiguous, forcing the programmer to mediate.
     234it is not possible to write a specialization for @f@ that works on any pair type and gets selected by the type resolver as intended.
    235235As a result, simply counting the number of polymorphic type variables is no longer correct to order the function candidates as being more constrained.
    236236\end{enumerate}
    237237
    238 These inconsistencies are not easily solvable in the current cost-model, meaning the current \CFA codebase has to workaround these defects.
     238These inconsistencies are not easily solvable in the current cost-model, meaning that currently the \CFA codebase has to workaround these defects.
    239239One potential solution is to mix the conversion cost and \CC-like partial ordering of specializations.
    240240For example, observe that the first three elements (unsafe, polymorphic and safe conversions) in the \CFA cost-tuple are related to the argument/parameter types, while the other two elements (polymorphic variable and assertion counts) are properties of the function declaration.
    … …  
    469469
    470470
    471 In previous versions of \CFA, this number was set at 4; as the compiler becomes more optimized and capable of handling more complex expressions in a reasonable amount of time, I have increased the limit to 8 and it does not lead to problems.
     471In previous versions of \CFA, this number was set at 4; as the compiler has become more optimized and capable of handling more complex expressions in a reasonable amount of time, I have increased the limit to 8 and it has not led to problems.
    472472Only rarely is there a case where the infinite recursion produces an exponentially growing assertion set, causing minutes of time wasted before the limit is reached.
    473473Fortunately, it is very hard to generate this situation with realistic \CFA code, and the ones that have occurred have clear characteristics, which can be prevented by alternative approaches.
    … …  
    481481In many cases, these problems can be avoided by examining other assertions that provide insight on the desired type binding: if one assertion parameter can only be matched by a unique option, the type bindings can be updated confidently without the need for backtracking.
    482482
    483 The Moss algorithm currently used in \CFA was developed using a simplified type system that captures most of \CFA type system features.
     483The Moss algorithm currently used in \CFA was developed using a simplified type system that captures most of \CFA's type system features.
    484484The simulation results were then ported back to the actual language.
    485485The simulator used a mix of breadth- and depth-first search in a staged approach.
    … …  
    520520Currently, type resolution cannot do enough return-type inferencing while performing eager assertion resolution: the return type information is unknown before the parent expression is resolved, unless the expression is an initialization context where the variable type is known.
    521521By delaying the assertion resolution until the return type becomes known, this problem can be circumvented.
    522 The truly problematic case occurs if a type variable does not appear in either of the parameter or return types and only appears in assertions or variables (associate types).
     522The truly problematic case occurs if a type variable does not appear in either of the parameter or return types and only appears in assertions or variables (\newterm{associate types}).
    523523\begin{cfa}
    524524forall( T | { void foo( @T@ ) } ) int f( float ) {
    … …  
    527527\end{cfa}
    528528This case is rare so forcing every type variable to appear at least once in parameter or return types does not limit the expressiveness of \CFA type system to a significant extent.
    529 The next section presents a proposal for including type declarations in traits rather than having all type variables appear in the trait parameter list, which is provides equivalent functionality to an unbound type parameter in assertion variables, and also addresses some of the variable cost issue discussed in \VRef{s:ExpressionCostModel}.
     529\VRef{s:AssociatedTypes} presents a proposal for including type declarations in traits rather than having all type variables appear in the trait parameter list, which provides equivalent functionality to an unbound type parameter in assertion variables, and also addresses some of the variable cost issue discussed in \VRef{s:ExpressionCostModel}.
    530530
    531531
    … …  
    599599\end{enumerate}
    600600
    601 \CFA does attempt to incorporate upstream type information propagated from variable a declaration with initializer, since the type of the variable being initialized is known.
     601\CFA does attempt to incorporate upstream type information propagated from a variable declaration with initializer, since the type of the variable being initialized is known.
    602602However, the current type-environment representation is flawed in handling such type inferencing, when the return type in the initializer is polymorphic.
    603603Currently, an inefficient workaround is performed to create the necessary effect.
Note: See TracChangeset for help on using the changeset viewer.