Changeset 38e20a80 for doc/theses/jiada_liang_MMath/background.tex

Timestamp:

Jul 29, 2024, 1:32:10 PM (5 weeks ago)

Author:

JiadaL <j82liang@…>

Branches:

master

Children:

ce02877

Parents:

5aeb1a9

Message:

update thesis

File:

• doc/theses/jiada_liang_MMath/background.tex (modified) (1 diff)

doc/theses/jiada_liang_MMath/background.tex

@@ -401 +401 @@
 
 \subsection{Conversion Cost}
-In C, functions argument and parameter type does not need to be exact match, and the compiler performs an @implicit conversion@ on argument.
-\begin{cfa}
-void foo(double i);
-foo(42);
-\end{cfa}
-The implicit conversion in C is relatively simple because of the abscence of overloading, with the exception of binary operators, for which the 
-compiler needs to find a common type of both operands and the result. The pattern is known as "usual arithmetic conversions".
-
-\CFA generalizes C implicit conversion to function overloading as a concept of @conversion cost@.
-Initially designed by Bilson, conversion cost is a 3-tuple, @(unsafe, poly, safe)@, where unsafe is the number of narrowing conversion,
-poly is the count of polymorphics type binding, and safe is the sum of the degree of widening conversion. Every 
-basic type in \CFA has been assigned with a @distance to Byte@, or @distance@, and the degree of widening conversion is the difference between two distances.
-
-Aaron extends conversion cost to a 7-tuple, 
-@@(unsafe, poly, safe, sign, vars, specialization, reference)@@. The summary of Aaron's cost model is the following:
+\label{s:ConversionCost}
+In C, function call arguments and function parameters do not need to be a exact match. When types mismatch, C performs an \newterm{implicit conversion} 
+on argument to parameter type. The process is trivial with the exception on binary operators;  When types of operands are different, 
+C nees to decide which operands need implicit conversion. C defines the resolution pattern as "usual arithmetic conversion", 
+in which C looks for a \newterm{common type} between operands, and convert either one or both operands to the common type. 
+Loosely defined, a common type is a the smallest type in terms of size of representation that both operands can be converted into without losing their precision.
+Such conversion is called "widening" or "safe conversion".
+
+C binary operators can be restated as 2-arity functions that overloaded with different parameters. "Usual arithmetic conversion" is to find a overloaded 
+instance that for both arguments, the conversion to parameter type is a widening conversion to the smallest type.
+
+\CFA generalizes "usual arithmetic conversion" to \newterm{conversion cost}. In the first design by Bilson, conversion cost is a 3-tuple,
+@(unsafe, poly, safe)@, where @unsafe@ the number of unsafe (narrorow conversion) from argument to parameter, 
+@poly@ is the number of polymorphic function parameter, 
+and @safe@ is sum of degree of safe (widening) conversion.
+Sum of degree is a method to quantify C's integer and floating-point rank. 
+Every pair of widening conversion types has been assigned with a \newterm{distance}, and distance between the two same type is 0.
+For example, the distance from char to int is 2, distance from integer to long is 1, and distance from int to long long int is 2.
+The distance does not mirror C's rank system. For example, the rank of char and signed char are the same in C, but the distance from char to signed char is assigned with 1.
+@safe@ cost is summing all pair of argument to parameter safe conversion distance.
+Among the three in Bilson's model, @unsafe@ is the most significant cost and @safe@ is the least significant one, with an implication that \CFA always choose 
+a candidate with the lowest @unsafe@ if possible.
+
+Assume the overloaded function @foo@ is called with two @int@ parameter. The cost for every overloaded @foo@ has been list along:
+\begin{cfa}
+void foo(char, char);                           // (2, 0, 0)
+void foo(char, int);                            // (1, 0, 0)
+forall(T, V) void foo(T, V);            // (0, 2, 0)
+forall(T)        void foo(T, T);                // (0, 2, 0)
+forall(T)        void foo(T, int);              // (0, 1, 0)
+void foo(long long, long);                      // (0, 0, 3)
+void foo(long, long);                           // (0, 0, 2)
+void foo(int, long);                            // (0, 0, 1)
+
+int i, j; foo(i, j);
+\end{cfa}
+The overloaded instances are ordered from the highest to the lowest cost, and \CFA select the last candidate.
+
+In the later iteration of \CFA, Schluntz and Aaron expanded conversion cost to a 7-tuple with 4 additional categories, 
+@@(unsafe, poly, safe, sign, vars, specialization, reference)@@.
+with interpretation listed below:
 \begin{itemize}
-\item Unsafe is the number of argument that implicitly convert to a type with high rank.
-\item Poly accounts for number of polymorphics binding in the function declaration.
-\item Safe is sum of distance (add reference/appendix later).
+\item Unsafe
+\item Poly 
+\item Safe
 \item Sign is the number of sign/unsign variable conversion.
-\item Vars is the number of polymorphics type declared in @forall@.
-\item Specialization is opposite number of function declared in @forall@. More function declared implies more constraint on polymorphics type, and therefore has the lower cost.
-\item Reference is number of lvalue-to-rvalue conversion.
+\item Vars is the number of polymorphics type variable.
+\item Specialization is negative value of the number of type assertion.
+\item Reference is number of reference-to-rvalue conversion.
 \end{itemize}
+The extended conversion cost models looks for candidates that are more specific and less generic.
+@Var@s was introduced by Aaron to disambugate @forall(T, V) void foo(T, V)@ and @forall(T) void foo(T, T)@. The extra type parameter @V@ 
+makes it more generic and less specific. More generic type means less constraints on types of its parameters. \CFA is in favor of candidates with more 
+restrictions on polymorphism so @forall(T) void foo(T, T)@ has lower cost. @Specialization@ is a value that always less than or equal to zero. For every type assertion in @forall@ clause, \CFA subtracts one from 
+@specialization@, starting from zero. More type assertions often means more constraints on argument type, and making the function less generic.
+
+\CFA defines two special cost value: @zero@ and @infinite@ A conversion cost is @zero@ when argument and parameter has exact match, and a conversion cost is @infinite@ when 
+there is no defined conversion between two types. For example, the conversion cost from int to a struct type S is @infinite@.