Index: doc/LaTeXmacros/common.tex =================================================================== --- doc/LaTeXmacros/common.tex (revision b0708ea1d4154f03985b857d92b904acdaf5f4eb) +++ doc/LaTeXmacros/common.tex (revision 522f71c6e05f60c340ba930b21cb01a7e58519fa) @@ -11,6 +11,6 @@ %% Created On : Sat Apr 9 10:06:17 2016 %% Last Modified By : Peter A. Buhr -%% Last Modified On : Sun Nov 3 09:11:30 2024 -%% Update Count : 684 +%% Last Modified On : Fri Dec 27 13:44:46 2024 +%% Update Count : 686 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -32,5 +32,5 @@ %\renewcommand{\labelitemi}{{\raisebox{0.25ex}{\footnotesize$\bullet$}}} \setlist[enumerate]{parsep=0.25ex,itemsep=0.25ex,listparindent=\parindent}% global -\setlist[enumerate,2]{leftmargin=\parindent,labelsep=*,align=parleft,label=\alph*.}% local +\setlist[enumerate,2]{labelsep=*,align=parleft}% local \setlist[description]{itemsep=0pt,listparindent=\parindent,leftmargin=\parindent,labelsep=1.5ex} Index: doc/theses/fangren_yu_MMath/content2.tex =================================================================== --- doc/theses/fangren_yu_MMath/content2.tex (revision b0708ea1d4154f03985b857d92b904acdaf5f4eb) +++ doc/theses/fangren_yu_MMath/content2.tex (revision 522f71c6e05f60c340ba930b21cb01a7e58519fa) @@ -2,12 +2,13 @@ \label{c:content2} -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 associated restrictions, and C's multiple implicit type-conversions must be respected. -This generality leads to internal complexity and correspondingly higher compilation cost. +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; +in addition, C's multiple implicit type-conversions must be respected. +This generality leads to internal complexity and correspondingly higher compilation cost directly related to type resolution. The reason is that the type resolver must analyze \emph{each} component of an expression with many possible forms of overloading, type restrictions, and conversions. -Designing a ruleset that behaves as expected, \ie matches with C programmer expectations, and implementing an efficient algorithm is a very challenging task. +Designing a ruleset that behaves as expected, \ie matches C programmer expectations, and implementing an efficient algorithm is a very challenging task. My first work on the \CFA type-system was as a co-op student. At that time, compiling a medium-sized \CFA program using advanced polymorphism took multiple minutes (5+ minutes)~\cite[\S~5]{Yu20}. -After finding and fixing the following resolution problems: +I found a number of type-resolution problems, which resulted in the following changes to the type-resolution algorithm. \begin{enumerate}[itemsep=0pt] \item @@ -22,6 +23,6 @@ skip pruning on expressions for function types \end{enumerate} -\VRef[Table]{t:SelectedFileByCompilerBuild} shows the improvement of selected tests with accumulated reductions in compile time across each of the 5 fixes. -The large reduction in compilation times, significantly improved the development of the \CFA's runtime because of its frequent compilation cycles. +\VRef[Table]{t:SelectedFileByCompilerBuild} shows improvements for selected tests with accumulated reductions in compile time across each of the 5 fixes. +The large reduction in compilation time significantly improved the development of the \CFA's runtime because of its frequent compilation cycles. \begin{table}[htb] @@ -44,5 +45,5 @@ @test/thread@ & 210.9 & 73.5 & 17.0 & 15.1 & 12.6 & 11.8 \\ \end{tabular} -\smallskip +\medskip \newline Results are average of 5 runs (3 runs if time exceeds 100 seconds) @@ -59,102 +60,147 @@ \section{Expression Cost-Model} -\CFA has been using an expression cost-model to resolve ambiguity of overloaded expressions from the very beginning. +\CFA has been using a total-order expression cost-model to resolve ambiguity of overloaded expressions from the very beginning. Most \CFA operators can be overloaded in \CFA\footnote{ -Excluding the comma operator, short-circuit logical operators \lstinline{&&} and \lstinline{||} (control structures) and ternary conditional operator \lstinline{?} (control structure). -While \CC overloads the short-circuit logical operators, the overloaded operators do not exhibit the short-circuit semantics, which is confusing.}; -hence, they are treated the same way as other function calls, and the same rules for overload resolution must apply to them as well. - -In \CFA, candidates of an overloaded expression are ranked by numerical cost elements, that accounts for the type conversions needed from the argument type to the corresponding declared function parameter type, as well as the polymorphic types and restrictions introduces by the @forall@ clause. -Currently the expression cost used in \CFA has the following components, ranked from higher to lower by importance: +\CFA excludes overloading the comma operator, short-circuit logical operators \lstinline{&&} and \lstinline{||} (control structures), and ternary conditional operator \lstinline{?} (control structure). +\CC overloads the comma and short-circuit logical operators, where the overloaded short-circuit operators do not exhibit short-circuit semantics, which is confusing.}; +hence, they are treated the same way as other function calls with the same rules for overload resolution. + +In \CFA, candidates of an overloaded expression are ranked by numerical cost elements, which account any type conversions needed from a call-site argument type to the matching function parameter type, as well as polymorphic types and restrictions introduced by the @forall@ clause. +Currently, the expression cost has the following components, ranked from highest to lowest. \begin{enumerate} -\item \textbf{Unsafe} cost representing a narrowing conversion of arithmetic types, e.g. -@int@ to @short@, and qualifier-dropping conversions for pointer and reference types; -\item \textbf{Polymorphic} cost where the function parameter type is or contains a polymorphic type variable; -\item \textbf{Safe} cost representing a widening conversion e.g. -@short@ to @int@, qualifier-adding conversions for pointer and reference types, and value conversion for enumeration constants. -\item \textbf{Variable} cost that counts the number of polymorphic variables, if any, introduced by the forall clause in the function declaration; -\item \textbf{Specialization} cost that counts the number of restrictions introduced by the type assertions. -\end{enumerate} -The comparison of cost tuple is by lexicographical order, starting from the highest importance term (unsafe cost) and the lower one has lower cost, with ties going to the second term (polymorphic cost) and so on. -At a sub-expression level, the lowest cost candidate for each result type is included as a possible interpretation of the expression; at the top level all possible interpretations of different types are considered and the overall lowest cost is selected as the final interpretation of the expression. - -In many languages that support function and operator overloading, such as \CC and Java, a partial ordering system decides which interpretation of the expression gets selected, which means that sometimes the candidates are incomparable (none of those are considered a better match) and only when one candidate is considered better than all others (maximal with respect to the partial order) is the expression unambiguous. - -In \CFA trying to use such a system is problematic because of the presence of return type overloading of functions, and overloading of variables. -The resolution algorithms used in \CC and Java are greedy, as they select the best match for each sub-expression without considering the higher level ones, and therefore at each step of resolution, the arguments are already given unique interpretations, so the ordering only needs to consider comparing different sets of conversion targets (function parameter types) on the same set of input. -However, in \CFA expression resolution considers multiple interpretations of argument sub-expressions with different types, so it is possible that both the selected function and the set of arguments are different, and cannot be compared if we choose to use some kind of partial ordering system. -Since this situation can arise quite often in \CFA, even in the simplest form such as an expression \textbf{f(a)} where both the function name \textbf{f} and variable name \textbf{a} are overloaded. -We do not want the resolution algorithm to report too many expressions as ambiguous (which would therefore be compilation errors) and restrict the flexibility of \CFA by too much. -The previous documentations and papers on \CFA expression resolution never explained why such a cost system is used; this could be a plausible guess of the original motivation of introducing the cost system to \CFA. - -On the contrary, using such a cost-based model can sometimes make \CFA expression resolution too permissive; the system will always attempt to select the lowest cost option, and only when there are multiple options tied at the lowest cost it reports the expression as ambiguous. -With so many elements in the cost tuple, ties are expected to be uncommon. -Other than the case of multiple exact matches which would all have cost of zero, incomparable candidates under a partial ordering of being more specific can often have different expression costs since different kinds of implicit conversions are involved, resulting in seemingly arbitrary overload selections. +\item \textbf{Unsafe} cost representing a narrowing conversion of arithmetic types, \eg @int@ to @short@, and qualifier-dropping conversions for pointer and reference types. +\item \textbf{Polymorphic} cost for a function parameter type that is or contains a polymorphic type variable. +\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. +\item \textbf{Variable} cost that counts the number of polymorphic variables, if any, introduced by the @forall@ clause in the function declaration. +\item \textbf{Specialization} cost counting the number of restrictions introduced by type assertions. +\end{enumerate} +The comparison of cost tuple is by lexicographical order, from unsafe (highest) to specialization (lowest), with ties moving to the next lowest item. +At a subexpression level, the lowest cost candidate for each result type is included as a possible interpretation of the expression; +at 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. +Glen 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 language. +This 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}. +Moss's work began to show problems with the underlying costing model; +these design issues are part of this work. + +\begin{comment} +From: Richard Bilson +Date: Tue, 10 Dec 2024 09:54:59 -0500 +Subject: Re: cost model +To: "Peter A. Buhr" + +I didn't invent it although I may have refined it somewhat. The idea of the +conversion cost is from Glen's thesis, see for instance page 90 + +On Tue, Dec 10, 2024 at 9:35AM Peter A. Buhr wrote: +> Cforall has a costing model based on an N-tuple using lexicographical ordering. +> (unsafe, polymorphic, safe, variable, specialization) +> +> Did you invent this costing model as a cheap and cheerful way to encode Glen's +> type system? + +From: Richard Bilson +Date: Tue, 10 Dec 2024 17:04:26 -0500 +Subject: Re: cost model +To: "Peter A. Buhr" + +Yes, I think that's fair to say. + +On Tue, Dec 10, 2024 at 2:22PM Peter A. Buhr wrote: +> Found it thanks. But Glen never implemented anything (small examples). So it +> feels like you took his conversion-cost idea and created an implementation table +> with the lexicographical comparison. +\end{comment} + +In many languages that support function/method overloading, such as \CC and Java, a partial-order system decides which interpretation of the expression gets selected. +Hence, sometimes the candidates are incomparable (none are considered a better match), and only when one candidate is considered better than all others (maximal with respect to the partial order) is the expression unambiguous. +Specifically, the resolution algorithms used in \CC and Java are greedy, as they select the best match for each sub-expression without considering the higher level ones, and therefore at each step of resolution, the arguments are already given unique interpretations, so the ordering only needs to consider comparing different sets of conversion targets (function parameter types) on the same set of input. +\begin{cfa} +@generate a C++ example here@ +\end{cfa} + +In \CFA, trying to use such a system is problematic because of the presence of return-type overloading of functions and variable. +Specifically, \CFA expression resolution considers multiple interpretations of argument subexpressions with different types, \eg: +\begin{cfa} +@generate a CFA example here@ +\end{cfa} +so it is possible that both the selected function and the set of arguments are different, and cannot be compared with a partial-ordering system. +This situation arises often in \CFA, even in the simple expression @f(x)@, where both the function name @f@ and variable name @x@ are overloaded. Ada is another programming language that has overloading based on return type. Although Ada also allows implicit type conversions of function arguments, it is fairly conservative on resolving ambiguities. -There are only two "preference" rules in Ada overload resolution, one for primitive arithmetic operators and one for universal access types (analogous to void* in C); any other cases where an expression have multiple legal interpretations are considered ambiguous. +\begin{cfa} +@generate an Ada example here@ +\end{cfa} +There are only two preference rules in Ada overload resolution, one for primitive arithmetic operators and one for universal access types (analogous to @void *@ in C); +any other cases where an expression has multiple legal interpretations are considered ambiguous. The current overload resolution system for \CFA is on the other end of the spectrum, as it tries to order every legal interpretations of an expression and chooses the best one according to cost, occasionally giving unexpected results. +Interestingly, the \CFA cost-based model can sometimes make expression resolution too permissive because it always attempts to select the lowest cost option, and only when there are multiple options tied at the lowest cost does it report the expression is ambiguous. +The reason is that there are so many elements in the cost tuple, the type system ``tries too hard to discover a match'', and therefore, ties are uncommon. +Other than the case of multiple exact matches, where all have cost zero, incomparable candidates under a partial ordering of being more specific can often have different expression costs since different kinds of implicit conversions are involved, resulting in seemingly arbitrary overload selections. + 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. -Here are those three cases: -\begin{enumerate} -\item Polymorphic exact match versus non-polymorphic inexact match: consider the following declarations - -\begin{cfa} -forall (T) void f (T); // 1 -void f (long); // 2 - -f (42); // currently selects 2 -\end{cfa} -Under the current cost model, option 1 incurs a polymorphic cost from matching the argument type \textbf{int} to type variable \textbf{T}, and option 2 incurs a safe cost from integer promotion of type \textbf{int} to \textbf{long}. +\begin{enumerate}[leftmargin=*] +\item Polymorphic exact match versus non-polymorphic inexact match. +\begin{cfa} +forall( T ) void f( T ); $\C[2.5in]{// 1}$ +void f( long ); $\C{// 2}$ +f( 42 ); $\C{// currently selects 2}\CRT$ +\end{cfa} +Under the current cost model, option 1 incurs a polymorphic cost from matching the argument type @int@ to type variable @T@, and option 2 incurs a safe cost from integer promotion of type @int@ to @long@. Since polymorphic cost is ranked above safe conversion cost, option 2 is considered to have lower cost and gets selected. - -In contrast, the template deduction and overload resolution rules in \CC selects option 1 instead (converting forall to the equivalent function template declaration). -\CC performs template argument deduction and overload candidate ranking in two separate steps: in the first step the type parameters are deduced for each primary function template, and if the corresponding template instantiation succeeds, the resulting function prototype is added to the resolution candidate set. -In the second step the implicit conversions (if any) applied to argument types are compared after taking away top-level qualifiers and references, and it prefers an exact match, followed by basic type promotions (roughly corresponds to safe conversion in \CFA), and then other kinds of conversions (roughly corresponds to unsafe conversion in \CFA). +In contrast, the template deduction and overload resolution rules in \CC selects option 1 (converting @forall@ to the equivalent function template declaration). +\CC performs template argument deduction and overload candidate ranking in two separate steps. +\begin{itemize} +\item +In the first step, the type parameters are deduced for each primary function template, and if the corresponding template instantiation succeeds, the resulting function prototype is added to the resolution candidate set. +\item +In the second step, the implicit conversions (if any) applied to argument types are compared after taking away top-level qualifiers and references. +It then prefers an exact match, followed by basic type promotions (roughly corresponds to safe conversion in \CFA), and then other kinds of conversions (roughly corresponds to unsafe conversion in \CFA). Only when the type conversions are the same does it prioritize a non-template candidate. -In this example, option 1 produces the prototype void f(int) which gives an exact match and therefore takes priority. -The \CC resolution rules effectively makes option 2 a specialization that only applies to type \textbf{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 \textbf{long}. -Such a discrepancy could be explained as a design decision that since \CFA polymorphic functions are real entities and are separately compiled, calling them would require passing type information and thus have an actual runtime cost. - -\item Having a lower total polymorphic cost does not always mean a function is more specialized. -The following example is taken from Aaron Moss's thesis, which discusses some improvements to the \CFA expression cost model, where he claims the following function prototypes are increasingly more constrained: - -\begin{cfa} -forall(T, U) void f(T, U); //1, polymorphic -forall(T) void f(T, T); //2, less polymorphic -forall(T) void f(T, int); //3, even less polymorphic -forall(T) void f(T*, int); //4, least polymorphic -\end{cfa} - +\end{itemize} +In this example, option 1 produces the prototype @void f( int )@, which gives an exact match and therefore takes priority. +The \CC resolution rules effectively makes 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@. +This difference could be explained as compensating for \CFA polymorphic functions being separately compiled versus template inlining; +hence, calling them requires passing type information and assertions increasing the runtime cost. +\item +Having a lower total polymorphic cost does not always mean a function is more specialized. +The following example is from Moss's thesis, which discusses some improvements to the \CFA cost-model. +He claims the following function prototypes are increasingly more constrained: +\begin{cfa} +forall( T, U ) void f( T, U ); $\C[2.75in]{// 1 polymorphic}$ +forall( T ) void f( T, T ); $\C{// 2 less polymorphic}$ +forall( T ) void f( T, int ); $\C{// 3 even less polymorphic}$ +forall( T ) void f( T *, int ); $\C{// 4 least polymorphic}\CRT$ +\end{cfa} This argument is not entirely correct. -Although it is true that both the sequence 1,2 and 1,3,4 are increasingly more constrained on the argument types, the option 2 is not comparable to either of option 3 or 4; they actually describe independent constraints on the two arguments. -In natural language, option 3 says that the second argument must have type \textbf{int}, while option 2 says that the two arguments must have the same type. -These two constraints can independently be satisfied, therefore neither should be considered a better match when trying to resolve a call to f with argument types (int, int), and reporting such an expression as ambiguous is the most appropriate action. -This is a limitation of using a numerical cost value as it cannot these logically complicated cases. - -\item Finally, the introduction of generic types means that it may require more type variables to describe a more specific type and that means simply counting the number of polymorphic type variables is no longer correct in general to order the function candidates as being more constrained. -Suppose we have a generic pair type defined and writing a function that takes an arbitrary pair would require using two type variables -\begin{cfa} -forall (T,U) void f (pair(T,U)); // 1 -\end{cfa} -and compare that with a function that takes any type at all: -\begin{cfa} -forall (T) void f (T); // 2 -\end{cfa} - -Passing a pair variable to f gives a cost of 1 poly, 2 variable for the pair overload, and a cost of 1 poly, 1 variable for the unconstrained overload. -Clearly we would like the former to be chosen but the cost model cannot handle that correctly. - -\end{enumerate} - -These inconsistencies do not seem to be easily solvable and currently the \CFA codebase has to work around with these known defects. -One potential path that could possibly be taken is a mix of the conversion cost and \CC-like partial ordering of specializations. -Observe that in the \CFA cost tuple, the first three elements (unsafe, polymorphic and safe conversions) are related to the argument types, while the other elements (polymorphic variable and assertion counts) are properties of the function declarations independent of the arguments. -This means it may be reasonable to have an ordering that compares the argument conversion costs first and uses the partial ordering of specializations as a tiebreaker. -The algorithm used by \CC template specialization ordering can be applied for \CFA with some slight modifications. - +Although it is true that both the sequence 1, 2 and 1, 3, 4 are increasingly more constrained on the argument types, option 2 is not comparable to either of option 3 or 4; +they actually describe independent constraints on the two arguments. +Specifically, option 2 says the two arguments must have the same type, while option 3 states the second argument must have type @int@, +Because two constraints can independently be satisfied, neither should be considered a better match when trying to resolve a call to @f@ with argument types @(int, int)@; +reporting such an expression as ambiguous is more appropriate. +The example illustrates the limitation of using a numerical cost value as it cannot represent these complicated cases. +\item +A generic type can require more type variables to describe a more specific type. +For example, a generic function taking a @pair@-type, requires two type variables. +\begin{cfa} +forall( T, U ) void f( pair( T, U ) ); $\C[2.75in]{// 1}$ +\end{cfa} +Add a function taking any type. +\begin{cfa} +forall( T ) void f( T ); $\C{// 2}\CRT$ +\end{cfa} +Passing a @pair@ variable to @f@ gives a cost of 1 poly, 2 variable for the @pair@ overload, versus a cost of 1 poly, 1 variable for the unconstrained overload. +Programmer expectation is to select the former, but the cost model selects the latter; +either could work. +As a result, simply counting the number of polymorphic type variables is no longer correct to order the function candidates as being more constrained. +\end{enumerate} + +These inconsistencies are not easily solvable in the current cost-model, meaning the currently \CFA codebase has to workaround these defects. +One potential solution is to mix the conversion cost and \CC-like partial ordering of specializations. +For 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. +Using this observation, it is reasonable to have an ordering that compares the argument/parameter conversion costs first and uses the partial ordering of specializations as a tiebreaker. +Hence, the \CC template-specialization ordering can be applied to \CFA with a slight modification. At the meantime, some other improvements have been made to the expression cost system. @@ -162,63 +208,139 @@ While implementing the change, there are also two detailed issues that need to be addressed for the new rules to fully work. -The first one deals with an idiom commonly used in \CFA that would cause a lot of overloads to have equal costs. -These kinds of expressions are so ubiquitous in \CFA code that we do not want them to be deemed ambiguous in the language. -Many C library functions have multiple versions for different argument types, for example there are absolute value functions defined for basic arithmetic types with different names, since C does not support any kind of overloading: -\begin{cfa} -int abs (int); -long labs (long); -double fabs (double); -float fabsf (float); -\end{cfa} -It is cumbersome for the programmers to remember all these different function names and select the correct ones, and even worse, if the incorrect version is picked, the program still compiles but with undesired conversions, which can sometimes even change the result, such as using the int version for floating point argument. -In \CFA all of these functions are renamed to simply @abs@. -This causes multiple overloads to have the same total cost when some conversion is needed. -For example @long x = abs(42);@ could be either calling @long abs(long)@ with the argument 42 converted to @long@ or calling @int abs(int)@ and converting the result to @long@. -In this example the choice could be arbitrary because both yields identical results. -In some other cases, the choice can have an actual impact on the final result. -While testing the effects of using the updated cost rule we found this piece of code in \CFA standard library: -\begin{cfa} -static inline __readyQ_avg_t __to_readyQ_avg(unsigned long long intsc) { - if(unlikely(0 == intsc)) return 0.0; - else return log2(intsc); // implicit conversion happens here -} // __readyQ_avg_t is defined to be double -\end{cfa} -This is a helper function for performance logging that calculate the geometric mean of a counter value, and it does so by summing up the logarithm value of the counter. -The function @log2@ is similarly overloaded in \CFA for both integer and floating point types, however in this case, the integer overload returns an integer, so the fractional part of logarithm is truncated. -With the previous cost rules the integer version of @log2@ is selected, and when experimenting the updated cost rules this got picked up as an ambiguous expression at first. -I reported this issue to the author of library code and got the reply that the expectation was that \CFA would choose the floating point overload, by the return type overloading selection. -This mistake went unnoticed since it is only inside a performance logging function and does not serve any critical purposes, and the only effect it has caused is that the performance data becomes inaccurate as the fractional parts got truncated before the sum. -Investigating this example leads to the decision that matching the return type higher up in the expression tree is prioritized, in case the total expression cost is equal. - -Another change addresses the issue that C arithmetic expressions have unique meanings governed by the arithmetic promotion rules, however in \CFA they are all modelled as function calls for overload resolution purposes. -The previous, partially greedy resolution rules will pick the locally optimal match and it matches the C rules naturally. -Care needs to be taken to maintain the C semantics when switching to the total expression cost approach. - - -This problem is already partially recognized, when Aaron Moss suggested overload resolution by total cost, in the form of handling cast expressions. -To quote directly the example: - -If a cast argument has an unambiguous interpretation as a conversion argument then it must be interpreted as such, even if the ascription interpretation would have a lower overall cost. +The first deals with a common idiom in \CFA that creates many overloads with equal cost. +Many C library functions have multiple versions for different argument types. +For example, the absolute-value function is defined for basic arithmetic types with different names, since C does not support overloading. +\begin{cquote} +\begin{tabular}{@{}lll@{}} +\begin{cfa} +int abs( int ); +long labs( long ); +long long int llabs( long long int ); +\end{cfa} +& +\begin{cfa} +double fabs( double ); +float fabsf( float ); +long double fabsl( long double ); +\end{cfa} +& +\begin{cfa} +cabs, cabsf, $and$ cabsl +$for$ _Complex + +\end{cfa} +\end{tabular} +\end{cquote} +It is cumbersome for programmers to remember these function names and select the correct one. +If an incorrect version is picked, the program compiles but with potential negative consequences such as using an integral version with a floating-point argument. +In \CFA, these functions are wrapped by functions with the overloaded name @abs@, which results in multiple overloads with the same total cost when some conversion is needed. +For example, @long x = abs( 42 )@ resolves to @long abs( long )@ with @int@ argument 42 converted to @long@ or @int abs( int )@ converting the result to @long@. +In this example, the choice could be arbitrary because both yield identical results. +However, for @int i = abs( -9223372036854775807LL )@, the result is @-1@, suggesting some kind of type error rather than silently generating a logically incorrect result. +There are multiple overload groupings of C functions into a single \CFA name, so usage should not report an ambiguity or warning unless there is a significant chance of error. + +While testing the effects of the updated cost rule, the following example was found in the \CFA standard library. +\begin{cfa} +static inline double __to_readyQ_avg( unsigned long long intsc ) { + if ( unlikely( 0 == intsc ) ) return 0.0; + else return log2( @intsc@ ); // implicit conversion happens here +} +\end{cfa} +This helper function is used for performance logging as part of computing a geometric; +it is called during summing of logarithmic values. +However, the function name @log2@ is overloaded in \CFA for both integer and floating point types. +In this case, the integer overload returns an integral result, truncating any small fractional part of the logarithm, so the sum is slightly incorrect. +When experimenting with the updated cost rules, it flagged the @log2@ call as an ambiguous expression. +When asked, the developer expected the floating-point overload because of return-type overloading. +This mistake went unnoticed because the truncated component was insignificant in the performance logging. +\PAB{Not sure I understand this: The conclusion is that matching the return type higher up in the expression tree is better, in cases where the total expression cost is equal.} + +Another change addresses the issue that C arithmetic expressions have unique meanings governed by its arithmetic conversion rules. +\begin{enumerate}[leftmargin=*,topsep=5pt,itemsep=4pt] +\item +First, if the corresponding real type of either operand is @long double@, the other operand is converted, without change of type domain, to a type whose corresponding real type is @long double@. +\item +Otherwise, if the corresponding real type of either operand is @double@, the other operand is converted, without change of type domain, to a type whose corresponding real type is @double@. +\item +Otherwise, if the corresponding real type of either operand is @float@, the other operand is converted, without change of type domain, to a type whose corresponding real type is @float@.\footnote{ +For example, addition of a \lstinline{double _Complex} and a \lstinline{float} entails just the conversion of the \lstinline{float} operand to \lstinline{double} (and yields a \lstinline{double _Complex} result).} +\item +Otherwise, the integer promotions are performed on both operands. +Then the following rules are applied to the promoted operands: +\begin{enumerate}[topsep=5pt,itemsep=4pt] +\item +If both operands have the same type, then no further conversion is needed. +\item +Otherwise, if both operands have signed integer types or both have unsigned integer types, the operand with the type of lesser integer conversion rank is converted to the type of the operand with greater rank. +\item +\label{p:SignedToUnsignedSafe} +Otherwise, if the operand that has unsigned integer type has rank greater or equal to the rank of the type of the other operand, then the operand with signed integer type is converted to the type of the operand with unsigned integer type. +\item +\label{p:UnsignedToSignedUnsafe} +Otherwise, if the type of the operand with signed integer type can represent all of the values of the type of the operand with unsigned integer type, then the operand with unsigned integer type is converted to the type of the operand with signed integer type. +\item +\label{p:Miscellaneous} +Otherwise, both operands are converted to the unsigned integer type corresponding to the type of the operand with signed integer type. + +\hfill\cite[\S~6.3.1.8]{C11} +\end{enumerate} +\end{enumerate} +\VRef[Figure]{f:CExpressionConversions} shows the C arithmetic conversions graphically. +\VRef[Rule]{p:SignedToUnsignedSafe} says an unsigned type is safely convertible to an signed type with greater rank, while \VRef[rule]{p:UnsignedToSignedUnsafe} says a signed type is unsafely convertible to an unsigned type. +Therefore, these two rules cover every possible case. +\VRef[Rule]{p:Miscellaneous} is the catch-all to accommodate any kinds of exotic integral representations. +These conversions are applied greedily at local points within an expression. +Because there is no overloading in C, except for builtin operators, no cost model is needed to differentiate among alternatives that could result in ambiguous matches. + +\begin{figure} +\input{C_expression_conversion.pstex_t} +\caption{C Expression Conversions: T1 operator T2} +\label{f:CExpressionConversions} + +\smallskip +\input{CFA_curr_arithmetic_conversion.pstex_t} +\caption{\CFA Total-Ordering Expression Conversions} +\label{f:CFACurrArithmeticConversions} + +\smallskip +\input{CFA_arithmetic_conversion.pstex_t} +\caption{\CFA Partial-Ordering Expression Conversions} +\label{f:CFAArithmeticConversions} +\end{figure} + +\VRef[Figure]{f:CFACurrArithmeticConversions} shows the current \CFA total-order arithmetic-conversions graphically. +Here, the unsafe cost of signed to unsigned is factored into the ranking, so the safe conversion is selected over an unsafe one. +Furthermore, an integral option is taken before considering a floating option. +This model locally matches the C approach, but provides an ordering when there are many overloaded alternative. +However, as Moss pointed out overload resolution by total cost has problems, \eg handling cast expressions. +\begin{cquote} +\ldots if a cast argument has an unambiguous interpretation as a conversion argument then it must be interpreted as such, even if the ascription interpretation would have a lower overall cost. This is demonstrated in the following example, adapted from the C standard library: \begin{cfa} unsigned long long x; -(unsigned)(x >> 32); -\end{cfa} +(unsigned)( x >> 32 ); +\end{cfa} +\vspace{5pt} In C semantics, this example is unambiguously upcasting 32 to @unsigned long long@, performing the shift, then downcasting the result to @unsigned@, at cost (1, 0, 3, 1, 0, 0, 0). -If ascription were allowed to be a first-class interpretation of a cast expression, it would be cheaper to select the @unsigned@ interpretation of @?>>?@ by downcasting x to @unsigned@ and upcasting 32 to @unsigned@, at a total cost of (1, 0, 1, 1, 0, 0, 0). -However, this break from C semantics is not backwards compatible, so to maintain C compatibility, the \CFA resolver selects the lowest-cost interpretation of the cast argument for which a conversion or coercion to the target type exists (upcasting to @unsigned long long@ in the example above, due to the lack of unsafe downcasts), using the cost of the conversion itself only as a tie-breaker. - +If ascription were allowed to be a first-class interpretation of a cast expression, it would be cheaper to select the @unsigned@ interpretation of @?>>?@ by downcasting @x@ to @unsigned@ and upcasting 32 to @unsigned@, at a total cost of (1, 0, 1, 1, 0, 0, 0). +\PAB{This example feels incorrect. Assume a word size of 4 bits (long long). Given the value 1001, shift it >> 2, gives 10, which fits in a half word (int). Now truncate 1001 to a halfword 01 and shift it >> 2, gives 00. So the lower-cost alternative does generate the correct result. Basically truncation is an unsafe operation and hence has a huge negative cost.} +However, this break from C semantics is not backwards compatible, so to maintain C compatibility, the \CFA resolver selects the lowest-cost interpretation of the cast argument for which a conversion or coercion to the target type exists (upcasting to @unsigned long long@ in the example above, due to the lack of unsafe downcasts), using the cost of the conversion itself only as a tie-breaker.\cite[pp.~46-47]{Moss19} +\end{cquote} However, a cast expression is not necessary to have such inconsistency to C semantics. -With any implicit argument-parameter type conversion in function calls we can replicate this issue without an explicit cast. -For example +An implicit argument-parameter type conversion in a function calls can replicate this issue without an explicit cast. \begin{cfa} unsigned long long x; -void f (unsigned); -f (x >> 32); -\end{cfa} -This has the same effect as using an explicit cast to coerce the type of expression @x >> 32@ to @unsigned@. -This shows that fundamentally the problem is not coming from the cast expressions, but modelling the C built-in operators as overloaded functions. -A different rule is enforced in selecting the built-in function candidates to fix this problem. -If an expression has any legal interpretations as a C built-in operation, only the lowest cost one is kept, regardless of the result types. +void f( unsigned ); +f( x >> 32 ); +\end{cfa} +The argument generation has the same effect as using an explicit cast to coerce the type of expression @x >> 32@ to @unsigned@. +This example shows the problem is not coming from the cast expressions, but from modelling the C builtin operators as overloaded functions. +As a result, a different rule is used to select the builtin function candidates to fix this problem: +if an expression has any legal interpretations as a C builtin operation, only the lowest cost one is kept, regardless of the result type. + +\VRef[Figure]{f:CFAArithmeticConversions} shows an alternative \CFA partial-order arithmetic-conversions graphically. +The idea here is to first look for the best integral alternative because integral calculations are exact and cheap. +If no integral solution is found, than there are different rules to select among floating-point alternatives. +This approach reduces the search space by partitioning: only look at integral operations, and then only look at float-point operations. @@ -227,10 +349,11 @@ Type unification is the algorithm that assigns values to each (free) type parameters such that the types of the provided arguments and function parameters match. - -\CFA does not attempt to do any type \textit{inference}: it has no anonymous functions (i.e. -lambdas, commonly found in functional programming and also used in \CC and Java), and the variable types must all be explicitly defined (no auto typing). -This makes the unification problem more tractable in \CFA as the argument types at each call site are usually all specified. -There is a single exception case, which happens when the function return type contains a free type variable that does not occur in any of the argument types, and subsequently passed into the parent expression. -A top level expression whose type still contains an unbounded type variable is considered ill-formed as such expression is inherently ambiguous. +\CFA does not attempt to do any type \textit{inference} \see{\VRef{s:IntoTypeInferencing}}: it has no anonymous functions (\ie lambdas, commonly found in functional programming and also used in \CC and Java), and the variable types must all be explicitly defined (no auto typing). +This restriction makes the unification problem more tractable in \CFA, as the argument types at each call site are usually all specified. +There is a single exception case when the function return type contains a free type variable that does not occur in any of the argument types, and subsequently passed into the parent expression. +\begin{cfa} +example ... does malloc work here +\end{cfa} +A top level expression whose type still contains an unbounded type variable is considered ill-formed as such an expression is inherently ambiguous. The unification algorithm in \CFA is originally presented in Richard Bilson's thesis and it has remained as the basis of the algorithm currently in use. @@ -238,5 +361,5 @@ To summarize, the \CFA type unification has two minor variants: an \textit{exact} mode and an \textit{inexact} mode. The inexact mode is applied at top level argument-parameter matching, and attempts to find an assignment to the type variables such that the argument types can be converted to parameter types with minimal cost as defined in the previous section. -The exact mode is required since the type matching algorithm operates recursively and the inner types often have to match exactly, for example there is no common type for the pointer types \textbf{int*} and \textbf{long*} while there is for \textbf{int} and \textbf{long}. +The exact mode is required since the type matching algorithm operates recursively and the inner types often have to match exactly, for example there is no common type for the pointer types \textbf{int*} and \textbf{long*} while there is for @int@ and @long@. With the introduction of generic record types, the parameters must match exactly as well; currently there are no covariance or contravariance supported for the generics. @@ -252,10 +375,10 @@ On each invocation the types to be operate on can be determined from the arguments provided, and therefore there should not be a need to pass a polymorphic function pointer, which can take any type in principle. -For example, consider a polymorphic function that takes one argument of type \textbf{T} and another pointer to a subroutine +For example, consider a polymorphic function that takes one argument of type @T@ and another pointer to a subroutine \begin{cfa} forall (T) void f (T x, forall (U) void (*g) (U)); \end{cfa} -Making \textbf{g} polymorphic in this context would almost certainly be unnecessary, since it can only be called inside the body of \textbf{f} and the types of the argument would have been known anyways, although it can potentially depend on \textbf{T}. -Moreover, requesting a function parameter to be able to potentially work on any input type at all would always impose too much constraint on the arguments, as it only needs to make each calls inside the body of \textbf{f} valid. +Making @g@ polymorphic in this context would almost certainly be unnecessary, since it can only be called inside the body of @f@ and the types of the argument would have been known anyways, although it can potentially depend on @T@. +Moreover, requesting a function parameter to be able to potentially work on any input type at all would always impose too much constraint on the arguments, as it only needs to make each calls inside the body of @f@ valid. Rewriting the prototype to @@ -263,12 +386,11 @@ forall (T) void f (T x, void (*g) (T)); \end{cfa} -will be sufficient (or potentially, some compound type synthesized from \textbf{T}), in which case \textbf{g} is no longer a polymorphic type on itself. -The "monomorphization" conversion is readily supported in \CFA, either by explicitly assigning a polymorphic function name to a compatible function pointer type, or implicitly done in deducing assertion parameters (which will be discussed in the next section). +will be sufficient (or potentially, some compound type synthesized from @T@), in which case @g@ is no longer a polymorphic type on itself. +The ``monomorphization'' conversion is readily supported in \CFA, either by explicitly assigning a polymorphic function name to a compatible function pointer type, or implicitly done in deducing assertion parameters (which will be discussed in the next section). Such technique can be directly applied to argument passing, which is essentially just assignment to function parameter variables. -There might be some edge cases where the supplied subroutine \textbf{g} is called on arguments of different types inside the body of \textbf{f} and so declared as polymorphic, but such use case is rare and the benefit of allowing such constructs seems to be minimal in practice. - - -The result of this change is that the unification algorithm no longer needs to distinguish "open" and "closed" type variables, as the latter is not allowed to exist. -The only type variables that need to be handled are those introduced by the \textbf{forall} clause from the function prototype. +There might be some edge cases where the supplied subroutine @g@ is called on arguments of different types inside the body of @f@ and so declared as polymorphic, but such use case is rare and the benefit of allowing such constructs seems to be minimal in practice. + +The result of this change is that the unification algorithm no longer needs to distinguish open and closed type-variables, as the latter is not allowed to exist. +The only type variables that need to be handled are those introduced by the @forall@ clause from the function prototype. The subtype relationship between function types is now also rendered redundant since none of the function parameter or return types can be polymorphic, and no basic types or non-polymorphic function types are subtypes of any other type. Therefore the goal of (exact) type unification now simply becomes finding a substitution that produces identical types. @@ -336,5 +458,5 @@ Suppose an unbound type variable @T@ appears in two assertions, one can be uniquely resolved and allow the type @T@ to be inferred immediately, and another has many ways to be resolved, each results in @T@ being bound to a different concrete type. If the first assertion is examined first by the algorithm, the deducted type can then be utilized in resolving the second assertion and eliminate many incorrect options without producing the list of candidates pending further checks. -In practice, this have a significant impact when an unbound type @T@ is declared to satisfy the basic "object assertions"\footnote{The term is borrowed from object-oriented languages although \CFA is not object-oriented in principle.} of having a default constructor, destructor, and copy assignment operations. +In practice, this have a significant impact when an unbound type @T@ is declared to satisfy the basic \emph{object assertions}\footnote{The term is borrowed from object-oriented languages although \CFA is not object-oriented in principle.} of having a default constructor, destructor, and copy assignment operations. Since they are defined for every type currently in scope, there are often hundreds or even thousands of matches to these functions with an unspecified operand type, and in most of the cases the value of @T@ can be deduced by resolving another assertion first, which then allows specific object lifetime functions to be looked up since they are sorted internally by the operand type, and greatly reduces the number of wasted resolution attempts. Index: doc/theses/fangren_yu_MMath/intro.tex =================================================================== --- doc/theses/fangren_yu_MMath/intro.tex (revision b0708ea1d4154f03985b857d92b904acdaf5f4eb) +++ doc/theses/fangren_yu_MMath/intro.tex (revision 522f71c6e05f60c340ba930b21cb01a7e58519fa) @@ -165,4 +165,5 @@ \section{Type Inferencing} +\label{s:IntoTypeInferencing} Every variable has a type, but association between them can occur in different ways: Index: doc/theses/fangren_yu_MMath/pictures/CFA_arithmetic_conversion.fig =================================================================== --- doc/theses/fangren_yu_MMath/pictures/CFA_arithmetic_conversion.fig (revision 522f71c6e05f60c340ba930b21cb01a7e58519fa) +++ doc/theses/fangren_yu_MMath/pictures/CFA_arithmetic_conversion.fig (revision 522f71c6e05f60c340ba930b21cb01a7e58519fa) @@ -0,0 +1,148 @@ +#FIG 3.2 Produced by xfig version 3.2.7b +Landscape +Center +Inches +Letter +100.00 +Single +-2 +1200 2 +6 6675 1200 8775 2325 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 7500 2100 7500 1875 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 7500 1650 7500 1425 +4 1 0 50 -1 4 12 0.0000 2 195 1560 7500 1800 double \\_Complex\001 +4 1 0 50 -1 4 12 0.0000 2 195 1365 7500 2250 float \\_Complex\001 +4 1 0 50 -1 4 12 0.0000 2 195 1980 7725 1350 long double \\_Complex\001 +-6 +6 1275 1350 2775 3375 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2175 1800 2175 1575 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2175 2250 2175 2025 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2175 2700 2175 2475 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2175 3150 2175 2925 +4 1 0 50 -1 4 12 0.0000 2 195 1410 2025 1500 signed long long\001 +4 1 0 50 -1 4 12 0.0000 2 195 990 2175 1950 signed long\001 +4 1 0 50 -1 4 12 0.0000 2 195 840 2175 2400 signed int\001 +4 1 0 50 -1 4 12 0.0000 2 195 1065 2175 2850 signed short\001 +4 1 0 50 -1 4 12 0.0000 2 195 1005 2175 3300 signed char\001 +-6 +2 1 0 1 4 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2775 1425 3300 1275 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3300 1650 2775 1500 +2 1 0 1 4 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2775 1875 3300 1725 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3300 2100 2775 1950 +2 1 0 1 4 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2775 2325 3300 2175 +2 1 0 1 4 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2775 2775 3300 2625 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3300 2550 2775 2400 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3300 3000 2775 2850 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 1650 3975 1425 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 2100 3975 1875 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 2550 3975 2325 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 3000 3975 2775 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 3450 3975 3225 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4875 1725 5325 1800 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4950 1275 5325 1650 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4875 2175 5325 2100 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5775 2100 5775 1875 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5775 1650 5775 1425 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6300 1725 6750 1725 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6300 2175 6750 2175 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6300 1275 6750 1275 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4875 2400 5325 2250 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4875 2625 5325 2325 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5775 2550 5775 2325 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4875 2850 5325 2700 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4875 3000 5325 2775 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2925 1500 5325 1725 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 1200 3525 1200 975 +2 1 0 1 4 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2775 3225 3300 3075 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 3150 4650 3075 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2923 1901 5325 1875 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2923 2327 5325 2175 +4 1 0 50 -1 4 12 0.0000 2 195 1200 3975 1800 unsigned long\001 +4 1 0 50 -1 4 12 0.0000 2 195 1050 3975 2250 unsigned int\001 +4 1 0 50 -1 4 12 0.0000 2 195 1275 3975 2700 unsigned short\001 +4 1 0 50 -1 4 12 0.0000 2 195 1215 3975 3150 unsigned char\001 +4 1 0 50 -1 4 12 0.0000 2 180 555 3975 3675 \\_Bool\001 +4 0 0 50 -1 4 12 0.0000 2 165 270 4125 3450 0,1\001 +4 1 0 50 -1 4 12 0.0000 2 195 1620 4125 1350 unsigned long long\001 +4 1 0 50 -1 4 12 0.0000 2 195 990 5775 1350 long double\001 +4 1 0 50 -1 4 12 0.0000 2 150 570 5775 1800 double\001 +4 1 0 50 -1 4 12 0.0000 2 150 375 5775 2250 float\001 +4 1 0 50 -1 4 12 0.0000 2 150 870 5850 2700 short float\001 +4 1 0 50 -1 0 12 0.0000 2 135 360 1200 3750 rank\001 +4 1 0 50 -1 4 12 0.0000 2 150 375 5325 3225 char\001 Index: doc/theses/fangren_yu_MMath/pictures/CFA_curr_arithmetic_conversion.fig =================================================================== --- doc/theses/fangren_yu_MMath/pictures/CFA_curr_arithmetic_conversion.fig (revision 522f71c6e05f60c340ba930b21cb01a7e58519fa) +++ doc/theses/fangren_yu_MMath/pictures/CFA_curr_arithmetic_conversion.fig (revision 522f71c6e05f60c340ba930b21cb01a7e58519fa) @@ -0,0 +1,118 @@ +#FIG 3.2 Produced by xfig version 3.2.7b +Landscape +Center +Inches +Letter +100.00 +Single +-2 +1200 2 +6 1350 2625 2850 4650 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2250 3075 2250 2850 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2250 3525 2250 3300 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2250 3975 2250 3750 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2250 4425 2250 4200 +4 1 0 50 -1 4 12 0.0000 2 195 1410 2100 2775 signed long long\001 +4 1 0 50 -1 4 12 0.0000 2 195 990 2250 3225 signed long\001 +4 1 0 50 -1 4 12 0.0000 2 195 840 2250 3675 signed int\001 +4 1 0 50 -1 4 12 0.0000 2 195 1065 2250 4125 signed short\001 +4 1 0 50 -1 4 12 0.0000 2 195 1005 2250 4575 signed char\001 +-6 +2 1 0 1 4 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2850 2700 3300 2475 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3300 2850 2850 2775 +2 1 0 1 4 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2850 3150 3300 2925 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3300 3300 2850 3225 +2 1 0 1 4 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2850 3600 3300 3375 +2 1 0 1 4 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2850 4050 3300 3825 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3300 3750 2850 3675 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3300 4200 2850 4125 +2 1 0 1 4 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2850 4500 3300 4275 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 2850 3975 2625 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 3300 3975 3075 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 3750 3975 3525 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 4200 3975 3975 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 4650 3975 4425 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 4275 4650 4275 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 1275 4650 1275 825 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 2400 3975 1950 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2250 2625 2250 1950 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2250 1725 2250 1500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2250 1275 2250 1050 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2775 1350 3225 1350 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2775 1800 3225 1800 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2775 900 3225 900 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 1725 3975 1500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 1275 3975 1050 +4 1 0 50 -1 0 12 0.0000 2 135 360 1275 4875 rank\001 +4 1 0 50 -1 4 12 0.0000 2 195 1200 3975 3000 unsigned long\001 +4 1 0 50 -1 4 12 0.0000 2 195 1050 3975 3450 unsigned int\001 +4 1 0 50 -1 4 12 0.0000 2 195 1275 3975 3900 unsigned short\001 +4 1 0 50 -1 4 12 0.0000 2 195 1215 3975 4350 unsigned char\001 +4 1 0 50 -1 4 12 0.0000 2 180 555 3975 4875 \\_Bool\001 +4 0 0 50 -1 4 12 0.0000 2 165 270 4125 4650 0,1\001 +4 1 0 50 -1 4 12 0.0000 2 195 1620 4125 2550 unsigned long long\001 +4 1 0 50 -1 4 12 0.0000 2 150 375 5400 4350 char\001 +4 1 0 50 -1 4 12 0.0000 2 195 990 2250 975 long double\001 +4 1 0 50 -1 4 12 0.0000 2 150 570 2250 1425 double\001 +4 1 0 50 -1 4 12 0.0000 2 150 375 2250 1875 float\001 +4 1 0 50 -1 4 12 0.0000 2 195 1560 3975 1425 double \\_Complex\001 +4 1 0 50 -1 4 12 0.0000 2 195 1365 3975 1875 float \\_Complex\001 +4 1 0 50 -1 4 12 0.0000 2 195 1980 4200 975 long double \\_Complex\001 Index: doc/theses/fangren_yu_MMath/pictures/C_expression_conversion.fig =================================================================== --- doc/theses/fangren_yu_MMath/pictures/C_expression_conversion.fig (revision 522f71c6e05f60c340ba930b21cb01a7e58519fa) +++ doc/theses/fangren_yu_MMath/pictures/C_expression_conversion.fig (revision 522f71c6e05f60c340ba930b21cb01a7e58519fa) @@ -0,0 +1,123 @@ +#FIG 3.2 Produced by xfig version 3.2.7b +Landscape +Center +Inches +Letter +100.00 +Single +-2 +1200 2 +2 1 0 1 4 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3000 1275 3300 1275 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3300 1650 3000 1350 +2 1 0 1 4 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3000 1725 3300 1725 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3300 2100 3000 1800 +2 1 0 1 4 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3000 2175 3300 2175 +2 1 0 1 4 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3000 2625 3300 2625 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3300 2550 3000 2250 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3300 3000 3000 2700 +2 1 0 1 4 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3000 3075 3300 3075 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 1650 3975 1425 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 2100 3975 1875 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 2550 3975 2325 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 3000 3975 2775 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3975 3450 3975 3225 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5325 2325 5625 1875 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5325 2325 5625 2325 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5325 2325 5625 2775 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4875 3075 4575 3075 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6150 2700 6150 2475 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6150 2250 6150 2025 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2400 1650 2400 1425 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2400 2100 2400 1875 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2400 2550 2400 2325 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2400 3000 2400 2775 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 1425 3450 1425 1200 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 4 + 5250 1200 5325 1200 5325 3675 5250 3675 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 4 + 6675 1200 6750 1200 6750 3675 6675 3675 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6750 2325 7050 1875 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6750 2325 7050 2325 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6750 2325 7050 2775 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 7875 2700 7875 2475 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 7875 2250 7875 2025 +4 1 0 50 -1 4 12 0.0000 2 195 1200 3975 1800 unsigned long\001 +4 1 0 50 -1 4 12 0.0000 2 195 1050 3975 2250 unsigned int\001 +4 1 0 50 -1 4 12 0.0000 2 195 1275 3975 2700 unsigned short\001 +4 1 0 50 -1 4 12 0.0000 2 195 1215 3975 3150 unsigned char\001 +4 1 0 50 -1 4 12 0.0000 2 180 555 3975 3675 \\_Bool\001 +4 0 0 50 -1 4 12 0.0000 2 165 270 4125 3450 0,1\001 +4 1 0 50 -1 4 12 0.0000 2 195 1620 4125 1350 unsigned long long\001 +4 1 0 50 -1 4 12 0.0000 2 150 375 5100 3150 char\001 +4 1 0 50 -1 4 12 0.0000 2 195 990 6150 1950 long double\001 +4 1 0 50 -1 4 12 0.0000 2 150 570 6150 2400 double\001 +4 1 0 50 -1 4 12 0.0000 2 150 375 6150 2850 float\001 +4 1 0 50 -1 4 12 0.0000 2 195 1410 2250 1350 signed long long\001 +4 1 0 50 -1 4 12 0.0000 2 195 990 2400 1800 signed long\001 +4 1 0 50 -1 4 12 0.0000 2 195 840 2400 2250 signed int\001 +4 1 0 50 -1 4 12 0.0000 2 195 1065 2400 2700 signed short\001 +4 1 0 50 -1 4 12 0.0000 2 195 1005 2400 3150 signed char\001 +4 1 0 50 -1 0 12 0.0000 2 135 360 1425 3675 rank\001 +4 1 0 50 -1 4 12 0.0000 2 195 1560 7875 2400 double \\_Complex\001 +4 1 0 50 -1 4 12 0.0000 2 195 1365 7875 2850 float \\_Complex\001 +4 1 0 50 -1 4 12 0.0000 2 195 1980 7950 1950 long double \\_Complex\001