Ignore:
Timestamp:
Dec 7, 2024, 6:47:05 PM (11 days ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
master
Children:
0b98381
Parents:
9861ef2
Message:

thesis proofreading

File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/fangren_yu_MMath/content2.tex

    r9861ef2 rb4c6e10  
    22\label{c:content2}
    33
    4 \CFA's type system is powerful but fairly complicated, which leads to higher compilation cost.
    5 The compiler needs to analyze each expression with many possible forms of overloading.
    6 Variables can be overloaded in \CFA, and functions can be overloaded by the argument types as well as the return types.
    7 Combined with the polymorphism introduced by forall clauses and generic types, the complexity of expression analysis can go up very quickly.
    8 Designing a rule set that behaves mostly as expected, and implementing it as an efficient algorithm for actual use, are both very challenging tasks.
    9 As the \CFA translator's performance improves to a level that can compile a mid-sized program in a reasonable amount of time, the development of \CFA's standard library also speeds up and many new features utilizing the expressiveness of \CFA's type system has been implemented, such as generic container types similar to those in \CC's standard template library.
    10 During the process of development, many weaknesses and design flaws of \CFA type system have been discovered.
    11 Some of those problems arise from the newly introduced language features described in the previous chapter, and fixing those unexpected interactions with the type system is especially difficult.
    12 This chapter describes the type resolution rules currently in use and some major problems that have been identified.
    13 Not all of those problems have got solutions yet, because fixing them may require redesigning parts of the \CFA language at a larger scale.
    14 
    15 
    16 \section{Expression Cost Model}
    17 
    18 \CFA has been using an expression cost model to resolve ambiguity of overloaded expressions from the very beginning.
    19 Since most operators can be overloaded in \CFA (excluding a few operators that have special semantics, such as the comma operator, and the short-circuit logical operators \&\& and ||, which require the operands to be evaluated in order), they are treated the same way as other function calls and the same rules for overload resolution must apply to them as well.
    20 
    21 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.
     4The \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.
     5This generality leads to internal complexity and correspondingly higher compilation cost.
     6The reason is that the type resolver must analyze \emph{each} component of an expression with many possible forms of overloading, type restrictions, and conversions.
     7Designing a ruleset that behaves as expected, \ie matches with C programmer expectations, and implementing an efficient algorithm is a very challenging task.
     8
     9My first work on the \CFA type-system was as a co-op student.
     10At that time, compiling a medium-sized \CFA program using advanced polymorphism took multiple minutes (5+ minutes)~\cite[\S~5]{Yu20}.
     11After finding and fixing the following resolution problems:
     12\begin{enumerate}[itemsep=0pt]
     13\item
     14new AST data structure
     15\item
     16special symbol table and argument-dependent lookup
     17\item
     18late assertion-satisfaction
     19\item
     20revised function-type representation
     21\item
     22skip pruning on expressions for function types
     23\end{enumerate}
     24\VRef[Table]{t:SelectedFileByCompilerBuild} shows the improvement of selected tests with accumulated reductions in compile time across each of the 5 fixes.
     25The large reduction in compilation times, significantly improved the development of the \CFA's runtime because of its frequent compilation cycles.
     26
     27\begin{table}[htb]
     28\centering
     29\caption{Compile time of selected files by compiler build in seconds}
     30\label{t:SelectedFileByCompilerBuild}
     31\lstset{deletekeywords={mutex,thread}}
     32\setlength{\extrarowheight}{1pt}
     33\vspace*{-4pt}
     34\begin{tabular}{l|r|rrrrr}
     35                                & \multicolumn{1}{c|}{Original} & \multicolumn{5}{c}{Accumulative fixes}        \\
     36\cline{3-7}                             
     37Test case               & \multicolumn{1}{c|}{resolver} & \multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{3} & \multicolumn{1}{c}{4} & \multicolumn{1}{c}{5} \\
     38\hline
     39@lib/fstream@   & 86.4  & 25.2  & 10.8  & 9.5   & 7.8   & 7.1   \\
     40@lib/mutex@             & 210.4 & 77.4  & 16.7  & 15.1  & 12.6  & 11.7  \\
     41@lib/vector@    & 17.2  & 8.9   & 3.1   & 2.8   & 2.4   & 2.2   \\
     42@lib/stdlib@    & 16.6  & 8.3   & 3.2   & 2.9   & 2.6   & 2.4   \\
     43@test/io2@              & 300.8 & 53.6  & 43.2  & 27.9  & 19.1  & 16.3  \\
     44@test/thread@   & 210.9 & 73.5  & 17.0  & 15.1  & 12.6  & 11.8  \\
     45\end{tabular}
     46\smallskip
     47\newline
     48Results are average of 5 runs (3 runs if time exceeds 100 seconds)
     49\end{table}
     50
     51Since then, many new features utilizing the expressiveness of \CFA's type system have been implemented, such as generic container types similar to those in \CC's standard template library.
     52During the development of multiple \CFA programs and libraries, more weaknesses and design flaws have been discovered within the type system.
     53Some of those problems arise from the newly introduced language features described in the previous chapter.
     54In addition, fixing unexpected interactions within the type system has presented challenges.
     55This chapter describes in detail the type-resolution rules currently in use and some major problems that have been identified.
     56Not all of those problems have solutions, because fixing them may require redesigning parts of the \CFA type system at a larger scale, which correspondingly affects the language design.
     57
     58
     59\section{Expression Cost-Model}
     60
     61\CFA has been using an expression cost-model to resolve ambiguity of overloaded expressions from the very beginning.
     62Most \CFA operators can be overloaded in \CFA\footnote{
     63Excluding the comma operator, short-circuit logical operators \lstinline{&&} and \lstinline{||} (control structures) and ternary conditional operator \lstinline{?} (control structure).
     64While \CC overloads the short-circuit logical operators, the overloaded operators do not exhibit the short-circuit semantics, which is confusing.};
     65hence, they are treated the same way as other function calls, and the same rules for overload resolution must apply to them as well.
     66
     67In \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.
    2268Currently the expression cost used in \CFA has the following components, ranked from higher to lower by importance:
    2369\begin{enumerate}
Note: See TracChangeset for help on using the changeset viewer.