Changes in / [6cc913e:954c954]


Ignore:
Location:
doc
Files:
1 deleted
3 edited

Legend:

Unmodified
Added
Removed

  • doc/LaTeXmacros/common.tex

    r6cc913e r954c954  
    1111%% Created On       : Sat Apr  9 10:06:17 2016
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Wed Sep 23 21:21:55 2020
    14 %% Update Count     : 454
     13%% Last Modified On : Fri Sep  4 13:56:52 2020
     14%% Update Count     : 383
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616
    … …  
    5555\newlength{\parindentlnth}
    5656\setlength{\parindentlnth}{\parindent}
     57
     58\newcommand{\LstBasicStyle}[1]{{\lst@basicstyle{#1}}}
     59\newcommand{\LstKeywordStyle}[1]{{\lst@basicstyle{\lst@keywordstyle{#1}}}}
     60\newcommand{\LstCommentStyle}[1]{{\lst@basicstyle{\lst@commentstyle{#1}}}}
     61
     62\newlength{\gcolumnposn}                                % temporary hack because lstlisting does not handle tabs correctly
     63\newlength{\columnposn}
     64\setlength{\gcolumnposn}{2.5in}
     65\setlength{\columnposn}{\gcolumnposn}
     66\newcommand{\C}[2][\@empty]{\ifx#1\@empty\else\global\setlength{\columnposn}{#1}\global\columnposn=\columnposn\fi\hfill\makebox[\textwidth-\columnposn][l]{\lst@basicstyle{\LstCommentStyle{#2}}}}
     67\newcommand{\CRT}{\global\columnposn=\gcolumnposn}
     68
     69% allow escape sequence in lstinline
     70%\usepackage{etoolbox}
     71%\patchcmd{\lsthk@TextStyle}{\let\lst@DefEsc\@empty}{}{}{\errmessage{failed to patch}}
    5772
    5873\usepackage{pslatex}                                    % reduce size of san serif font
    … …  
    229244\usepackage{listings}                                                                   % format program code
    230245\usepackage{lstlang}
    231 \makeatletter
    232 
    233 \newcommand{\LstBasicStyle}[1]{{\lst@basicstyle{#1}}}
    234 \newcommand{\LstKeywordStyle}[1]{{\lst@basicstyle{\lst@keywordstyle{#1}}}}
    235 \newcommand{\LstCommentStyle}[1]{{\lst@basicstyle{\lst@commentstyle{#1}}}}
    236 
    237 \newlength{\gcolumnposn}                                % temporary hack because lstlisting does not handle tabs correctly
    238 \newlength{\columnposn}
    239 \setlength{\gcolumnposn}{2.75in}
    240 \setlength{\columnposn}{\gcolumnposn}
    241 \newcommand{\C}[2][\@empty]{\ifx#1\@empty\else\global\setlength{\columnposn}{#1}\global\columnposn=\columnposn\fi\hfill\makebox[\textwidth-\columnposn][l]{\lst@basicstyle{\LstCommentStyle{#2}}}}
    242 \newcommand{\CRT}{\global\columnposn=\gcolumnposn}
    243 
    244 % allow escape sequence in lstinline
    245 %\usepackage{etoolbox}
    246 %\patchcmd{\lsthk@TextStyle}{\let\lst@DefEsc\@empty}{}{}{\errmessage{failed to patch}}
    247 
    248 % allow adding to lst literate
    249 \def\addToLiterate#1{\protect\edef\lst@literate{\unexpanded\expandafter{\lst@literate}\unexpanded{#1}}}
    250 \lst@Key{add to literate}{}{\addToLiterate{#1}}
    251 \makeatother
    252246
    253247\newcommand{\CFADefaults}{%
    … …  
    268262belowskip=3pt,
    269263% replace/adjust listing characters that look bad in sanserif
    270 literate={-}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.75ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1
     264literate={-}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1
    271265        {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
    272266        {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex\textgreater}2,
    273 }% lstset
    274 }% CFADefaults
    275 
    276 \ifdefined\CFALatin%
    277 \lstnewenvironment{cfa}[1][]{\CFADefaults
    278 \lstset{
    279 language=CFA,
    280 moredelim=**[is][\color{red}]{®}{®},    % red highlighting ®...® (registered trademark symbol) emacs: C-q M-.
     267moredelim=**[is][\color{red}]{?}{?},    % red highlighting ?...? (registered trademark symbol) emacs: C-q M-.
    281268moredelim=**[is][\color{blue}]{ß}{ß},   % blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_
    282269moredelim=**[is][\color{OliveGreen}]{¢}{¢}, % green highlighting ¢...¢ (cent symbol) emacs: C-q M-"
    283270moredelim=[is][\lstset{keywords={}}]{¶}{¶}, % keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^
    284 % replace/adjust listing characters that look bad in sanserif
    285 add to literate={`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
    286271}% lstset
    287 \lstset{#1}
    288 }{}
     272}% CFADefaults
     273\newcommand{\CFAStyle}{%
     274\CFADefaults
    289275% inline code ©...© (copyright symbol) emacs: C-q M-)
    290276\lstMakeShortInline©                                    % single-character for \lstinline
    291 \else% extra Latin-1 escape characters
    292 \lstset{
    293 language=CFA,
    294 escapechar=\$,                                                  % LaTeX escape in CFA code
    295 moredelim=**[is][\color{red}]{@}{@},    % red highlighting `...` (backtick symbol)
    296 }% lstset
    297 \lstnewenvironment{cfa}[1][]{\CFADefaults
    298 \lstset{
    299 language=CFA,
    300 escapechar=\$,                                                  % LaTeX escape in CFA code
    301 moredelim=**[is][\color{red}]{@}{@},    % red highlighting `...` (backtick symbol)
    302 }% lstset
    303 \lstset{#1}
    304 }{}
    305 % inline code @...@ (at symbol)
    306 \lstMakeShortInline@                                    % single-character for \lstinline
    307 \fi%
     277}% CFAStyle
     278
     279\lstnewenvironment{cfa}[1][]
     280{\CFADefaults\lstset{#1}}
     281{}
    308282
    309283% Local Variables: %

  • doc/LaTeXmacros/lstlang.sty

    r6cc913e r954c954  
    88%% Created On       : Sat May 13 16:34:42 2017
    99%% Last Modified By : Peter A. Buhr
    10 %% Last Modified On : Wed Sep 23 22:40:04 2020
    11 %% Update Count     : 24
     10%% Last Modified On : Tue Jan  8 14:40:33 2019
     11%% Update Count     : 21
    1212%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1313
    … …  
    115115                auto, _Bool, catch, catchResume, choose, _Complex, __complex, __complex__, __const, __const__,
    116116                coroutine, disable, dtype, enable, exception, __extension__, fallthrough, fallthru, finally,
    117                 __float80, float80, __float128, float128, forall, ftype, generator, _Generic, _Imaginary, __imag, __imag__,
     117                __float80, float80, __float128, float128, forall, ftype, _Generic, _Imaginary, __imag, __imag__,
    118118                inline, __inline, __inline__, __int128, int128, __label__, monitor, mutex, _Noreturn, one_t, or,
    119                 otype, restrict, __restrict, __restrict__, __signed, __signed__, _Static_assert, suspend, thread,
     119                otype, restrict, __restrict, __restrict__, __signed, __signed__, _Static_assert, thread,
    120120                _Thread_local, throw, throwResume, timeout, trait, try, ttype, typeof, __typeof, __typeof__,
    121121                virtual, __volatile, __volatile__, waitfor, when, with, zero_t,
    … …  
    125125
    126126% C++ programming language
    127 \lstdefinelanguage{C++}[ANSI]{C++}{
    128         morekeywords={nullptr,}
    129 }
     127\lstdefinelanguage{C++}[ANSI]{C++}{}
    130128
    131129% uC++ programming language, based on ANSI C++

  • doc/theses/fangren_yu_COOP_S20/Report.tex

    r6cc913e r954c954  
    2626\renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
    2727\newcommand{\NOTE}{\textbf{NOTE}}
    28 \newcommand{\TODO}[1]{{\color{Purple}#1}}
    2928
    3029\setlength{\topmargin}{-0.45in}                                                 % move running title into header
    … …  
    3635\lstset{
    3736language=C++,                                                                                   % make C++ the default language
     37escapechar=\$,                                                                                  % LaTeX escape in CFA code
     38moredelim=**[is][\color{red}]{`}{`},
    3839}% lstset
     40\lstMakeShortInline@%
    3941\lstnewenvironment{C++}[1][]                            % use C++ style
    40 {\lstset{language=C++,moredelim=**[is][\color{red}]{@}{@},#1}}{}
     42{\lstset{language=C++,moredelim=**[is][\protect\color{red}]{`}{`},#1}}
     43{}
    4144
    4245%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    … …  
    8184\section{Overview}
    8285
    83 cfa-cc is the reference compiler for the \CFA programming language, which is a non-object-oriented extension to C.
    84 \CFA attempts to introduce productive modern programming language features to C while maintaining as much backward-compatibility as possible, so that most existing C programs can seamlessly work with \CFA.
    85 
    86 Since the \CFA project dates back to the early 2000s, and only restarted in the past few years, there is a significant amount of legacy code in the current compiler codebase with little documentation.
    87 The lack of documentation makes it difficult to develop new features from the current implementation and diagnose problems.
    88 
    89 Currently, the \CFA team is also facing poor compiler performance.
    90 For the development of a new programming language, writing standard libraries is an important component.
    91 The slow compiler causes building of the library files to take tens of minutes, making iterative development and testing almost impossible.
    92 There is an ongoing effort to rewrite the core data-structure of the compiler to overcome the performance issue, but many bugs have appeared during this work, and lack of documentation is hampering debugging.
    93 
    94 This developer's reference manual begins the documentation and should be continuously im\-proved until it eventually covers the entire compiler codebase.
    95 For now, the focus is mainly on the parts being rewritten, and also the primary performance bottleneck, namely the resolution algorithm.
    96 Its aimed is to provide new project developers with guidance in understanding the codebase, and clarify the purpose and behaviour of certain functions that are not mentioned in the previous \CFA research papers~\cite{Bilson03,Ditchfield92,Moss19}.
     86cfa-cc is the reference compiler for the \CFA programming language, which is a non-
     87object-oriented extension to C.
     88\CFA attempts to introduce productive modern programming language features to C
     89while maintaining as much backward-compatibility as possible, so that most existing C
     90programs can seamlessly work with \CFA.
     91
     92Since the \CFA project was dated back to the early 2000s, and only restarted in the past
     93few years, there is a significant amount of legacy code in the current compiler codebase,
     94with little proper documentation available. This becomes a difficulty while developing new
     95features based on the previous implementations, and especially while diagnosing
     96problems.
     97
     98Currently, the \CFA team is also facing another problem: bad compiler performance. For
     99the development of a new programming language, writing a standard library is an
     100important part. The incompetence of the compiler causes building the library files to take
     101tens of minutes, making iterative development and testing almost impossible. There is
     102ongoing effort to rewrite the core data structure of the compiler to overcome the
     103performance issue, but many bugs may appear during the work, and lack of documentation
     104makes debugging extremely difficult.
     105
     106This developer's reference will be continuously improved and eventually cover the
     107compiler codebase. For now, the focus is mainly on the parts being rewritten, and also the
     108performance bottleneck, namely the resolution algorithm. It is aimed to provide new
     109developers to the project enough guidance and clarify the purposes and behavior of certain
     110functions which are not mentioned in the previous \CFA research papers.
    97111
    98112
    99113\section{Compiler Framework}
    100114
    101 \CFA source code is first transformed into an abstract syntax tree (AST) by the parser before analyzed by the compiler.
    102 
    103 
    104115\subsection{AST Representation}
    105116
    106 
    107 There are 4 major categories of AST nodes used by the compiler, along with some derived structures.
    108 
    109 \subsubsection{Declaration Nodes}
     117Source code input is first transformed into abstract syntax tree (AST) representation by the
     118parser before analyzed by the compiler.
     119
     120There are 4 major categories of AST nodes used by the compiler, along with some derived
     121structures.
     122
     123\subsubsection{Declaration nodes}
    110124
    111125A declaration node represents either of:
    112126\begin{itemize}
    113127\item
    114 type declaration: @struct@, @union@, @typedef@ or type parameter \TODO{(see Appendix A.3)}
    115 \item
    116 variable declaration
    117 \item
    118 function declaration
     128Type declaration: struct, union, typedef or type parameter (see Appendix A.3)
     129\item
     130Variable declaration
     131\item
     132Function declaration
    119133\end{itemize}
    120134Declarations are introduced by standard C declarations, with the usual scoping rules.
    121 In addition, declarations can also be qualified by the \lstinline[language=CFA]@forall@ clause (which is the origin of \CFA's name):
     135In addition, declarations can also be introduced by the forall clause (which is the origin
     136of \CFA's name):
    122137\begin{cfa}
    123 forall ( <$\emph{TypeParameterList}$> | <$\emph{AssertionList}$> )
     138forall (<$\emph{TypeParameterList}$> | <$\emph{AssertionList}$>)
    124139        $\emph{declaration}$
    125140\end{cfa}
    126 Type parameters in \CFA are similar to \CC template type parameters.
    127 The \CFA declaration
     141Type parameters in \CFA are similar to \CC template type parameters. The \CFA
     142declaration
    128143\begin{cfa}
    129144forall (dtype T) ...
    130145\end{cfa}
    131 behaves similarly to the \CC template declaration
     146behaves similarly as the \CC template declaration
    132147\begin{C++}
    133148template <typename T> ...
    134149\end{C++}
    135150
    136 Assertions are a distinctive feature of \CFA, similar to \emph{interfaces} in D and Go, and \emph{traits} in Rust.
    137 Contrary to the \CC template where arbitrary functions and operators can be used in a template definition, in a \CFA parametric function, operations on parameterized types must be declared in assertions.
     151Assertions are a distinctive feature of \CFA: contrary to the \CC template where
     152arbitrary functions and operators can be used in a template definition, in a \CFA
     153parametric function, operations on parameterized types must be declared in assertions.
     154
    138155Consider the following \CC template:
    139156\begin{C++}
    140 @template@ forall<typename T> T foo( T t ) {
    141         return t + t * t;
     157template <typename T> int foo(T t) {
     158        return bar(t) + baz(t);
    142159}
    143160\end{C++}
    144 where there are no explicit requirements on the type @T@.
    145 Therefore, the \CC compiler must deduce what operators are required during textual (macro) expansion of the template at each usage.
    146 As a result, templates cannot be compiled.
    147 \CFA assertions specify restrictions on type parameters:
     161Unless bar and baz are also parametric functions taking any argument type, they must be
     162declared in the assertions, or otherwise the code will not compile:
    148163\begin{cfa}
    149 forall( dtype T | @{ T ?+?( T, T ); T ?*?( T, T ) }@ ) int foo ( T t ) {
    150         return t + t * t;
     164forall (dtype T | { int bar(T); int baz(t); }) int foo (T t) {
     165        return bar(t) + baz(t);
    151166}
    152167\end{cfa}
    153 Assertions are written using the usual \CFA function declaration syntax.
    154 Only types with operators ``@+@'' and ``@*@'' work with this function, and the function prototype is sufficient to allow separate compilation.
    155 
    156 Type parameters and assertions are used in the following compiler data-structures.
    157 
    158 
    159 \subsubsection{Type Nodes}
    160 
    161 Type nodes represent the type of an object or expression.
    162 Named types reference the corresponding type declarations.
    163 The type of a function is its function pointer type (same as standard C).
    164 With the addition of type parameters, named types may contain a list of parameter values (actual parameter types).
    165 
    166 
    167 \subsubsection{Statement Nodes}
    168 
    169 Statement nodes represent the executable statements in the program, including basic expression statements, control flows and blocks.
     168Assertions are written using the usual function declaration syntax. The scope of type
     169parameters and assertions is the following declaration.
     170
     171\subsubsection{Type nodes}
     172
     173A type node represents the type of an object or expression.
     174Named types reference the corresponding type declarations. The type of a function is its
     175function pointer type (same as standard C).
     176With the addition of type parameters, named types may contain a list of parameter values
     177(actual parameter types).
     178
     179\subsubsection{Statement nodes}
     180
     181Statement nodes represent the statements in the program, including basic expression
     182statements, control flows and blocks.
    170183Local declarations (within a block statement) are represented as declaration statements.
    171184
    172 
    173 \subsubsection{Expression Nodes}
    174 
    175 Some expressions are represented differently before and after the resolution stage:
     185\subsubsection{Expression nodes}
     186
     187Some expressions are represented differently in the compiler before and after resolution
     188stage:
    176189\begin{itemize}
    177190\item
    178 Name expressions: @NameExpr@ pre-resolution, @VariableExpr@ post-resolution
    179 \item
    180 Member expressions: @UntypedMemberExpr@ pre-resolution, @MemberExpr@ post-resolution
    181 \item
    182 \begin{sloppypar}
    183 Function call expressions (including overloadable operators): @UntypedExpr@ pre-resolution, @ApplicationExpr@ post-resolution
    184 \end{sloppypar}
     191Name expressions: NameExpr pre-resolution, VariableExpr post-resolution
     192\item
     193Member expressions: UntypedMemberExpr pre-resolution, MemberExpr post-resolution
     194\item
     195Function call expressions (including overloadable operators): UntypedExpr pre-resolution, ApplicationExpr post-resolution
    185196\end{itemize}
    186 The pre-resolution representation contains only the symbols.
    187 Post-resolution links them to the actual variable and function declarations.
     197The pre-resolution representations contain only the symbols. Post-resolution results link
     198them to the actual variable and function declarations.
    188199
    189200
    190201\subsection{Compilation Passes}
    191202
    192 Compilation steps are implemented as passes, which follows a general structural recursion pattern on the syntax tree.
    193 
    194 The basic workflow of compilation passes follows preorder and postorder traversal on the AST data-structure, implemented with visitor pattern, and can be loosely described with the following pseudocode:
    195 \begin{C++}
    196 Pass::visit( node_t node ) {
    197         previsit( node );
    198         if ( visit_children )
     203Compilation steps are implemented as passes, which follows a general structural recursion
     204pattern on the syntax tree.
     205
     206The basic work flow of compilation passes follows preorder and postorder traversal on
     207tree data structure, implemented with visitor pattern, and can be loosely described with
     208the following pseudocode:
     209\begin{C++}
     210Pass::visit (node_t node) {
     211        previsit(node);
     212        if (visit_children)
    199213                for each child of node:
    200                         child.accept( this );
    201         postvisit( node );
     214                        child.accept(this);
     215        postvisit(node);
    202216}
    203217\end{C++}
    204 Operations in @previsit@ happen in preorder (top to bottom) and operations in @postvisit@ happen in postorder (bottom to top).
    205 The precise order of recursive operations on child nodes can be found in @Common/PassVisitor.impl.h@ (old) and @AST/Pass.impl.hpp@ (new).
    206 
    207 Implementations of compilation passes follow certain conventions:
     218Operations in previsit() happen in preorder (top to bottom) and operations in
     219postvisit() happen in postorder (bottom to top). The precise order of recursive
     220operations on child nodes can be found in @Common/PassVisitor.impl.h@ (old) and
     221@AST/Pass.impl.hpp@ (new).
     222Implementations of compilation passes need to follow certain conventions:
    208223\begin{itemize}
    209224\item
    210 Passes \textbf{should not} directly override the visit method (Non-virtual Interface principle);
    211 if a pass desires different recursion behaviour, it should set @visit_children@ to false and perform recursive calls manually within previsit or postvisit procedures.
    212 To enable this option, inherit from the @WithShortCircuiting@ mixin.
    213 \item
    214 previsit may mutate the node but \textbf{must not} change the node type or return @nullptr@.
    215 \item
    216 postvisit may mutate the node, reconstruct it to a different node type, or delete it by returning @nullptr@.
     225Passes \textbf{should not} directly override the visit method (Non-virtual Interface
     226principle); if a pass desires different recursion behavior, it should set
     227@visit_children@ to false and perform recursive calls manually within previsit or
     228postvisit procedures. To enable this option, inherit from @WithShortCircuiting@ mixin.
     229\item
     230previsit may mutate the node but \textbf{must not} change the node type or return null.
     231\item
     232postvisit may mutate the node, reconstruct it to a different node type, or delete it by
     233returning null.
    217234\item
    218235If the previsit or postvisit method is not defined for a node type, the step is skipped.
    219 If the return type is declared as @void@, the original node is returned by default.
    220 These behaviours are controlled by template specialization rules;
    221 see @Common/PassVisitor.proto.h@ (old) and @AST/@ @Pass.proto.hpp@ (new) for details.
     236If the return type is declared as void, the original node is returned by default. These
     237behaviors are controlled by template specialization rules; see
     238@Common/PassVisitor.proto.h@ (old) and @AST/Pass.proto.hpp@ (new) for details.
    222239\end{itemize}
    223240Other useful mixin classes for compilation passes include:
    224241\begin{itemize}
    225242\item
    226 @WithGuards@ allows saving and restoring variable values automatically upon entering/exiting the current node.
    227 \item
    228 @WithVisitorRef@ creates a wrapped entity for the current pass (the actual argument passed to recursive calls internally) for explicit recursion, usually used together with @WithShortCircuiting@.
    229 \item
    230 @WithSymbolTable@ gives a managed symbol table with built-in scoping-rule handling (\eg on entering and exiting a block statement)
     243WithGuards allows saving values of variables and restore automatically upon exiting
     244the current node.
     245\item
     246WithVisitorRef creates a wrapped entity of current pass (the actual argument
     247passed to recursive calls internally) for explicit recursion, usually used together
     248with WithShortCircuiting.
     249\item
     250WithSymbolTable gives a managed symbol table with built-in scoping rule handling
     251(\eg on entering and exiting a block statement)
    231252\end{itemize}
    232 \NOTE: If a pass extends the functionality of another existing pass, due to \CC overloading resolution rules, it \textbf{must} explicitly introduce the inherited previsit and postvisit procedures to its own scope, or otherwise they are not picked up by template resolution:
     253\NOTE: If a pass extends the functionality of another existing pass, due to \CC overloading
     254resolution rules, it \textbf{must} explicitly introduce the inherited previsit and postvisit procedures
     255to its own scope, or otherwise they will not be picked up by template resolution:
    233256\begin{C++}
    234257class Pass2: public Pass1 {
    235         @using Pass1::previsit;@
    236         @using Pass1::postvisit;@
     258        using Pass1::previsit;
     259        using Pass1::postvisit;
    237260        // new procedures
    238261}
    … …  
    240263
    241264
    242 \subsection{Data Structure Change (new-ast)}
    243 
    244 It has been observed that excessive copying of syntax tree structures accounts for a majority of computation cost and significantly slows down the compiler.
    245 In the previous implementation of the syntax tree, every internal node has a unique parent;
    246 therefore all copies are required to duplicate the entire subtree.
    247 A new, experimental re-implementation of the syntax tree (source under directory @AST/@ hereby referred to as ``new-ast'') attempts to overcome this issue with a functional approach that allows sharing of common sub-structures and only makes copies when necessary.
    248 
    249 The core of new-ast is a customized implementation of smart pointers, similar to @std::shared_ptr@ and @std::weak_ptr@ in the \CC standard library.
    250 Reference counting is used to detect sharing and allowing certain optimizations.
    251 For a purely functional (immutable) data-structure, all mutations are modelled by shallow copies along the path of mutation.
     265\subsection{Data Structure Change WIP (new-ast)}
     266
     267It has been observed that excessive copying of syntax tree structures accounts for a
     268majority of computation cost and significantly slows down the compiler. In the previous
     269implementation of the syntax tree, every internal node has a unique parent; therefore all
     270copies are required to duplicate everything down to the bottom. A new, experimental
     271re-implementation of the syntax tree (source under directory AST/ hereby referred to as
     272``new-ast'') attempts to overcome this issue with a functional approach that allows sharing
     273of common sub-structures and only makes copies when necessary.
     274
     275The core of new-ast is a customized implementation of smart pointers, similar to
     276@std::shared_ptr@ and @std::weak_ptr@ in \CC standard library. Reference counting is
     277used to detect sharing and allows optimization. For a purely functional (a.k.a. immutable)
     278data structure, all mutations are modelled by shallow copies along the path of mutation.
    252279With reference counting optimization, unique nodes are allowed to be mutated in place.
    253 This however, may potentially introduce some complications and bugs;
    254 a few issues are discussed near the end of this section.
    255 
    256 
    257 \subsubsection{Source: \lstinline{AST/Node.hpp}}
    258 
    259 Class @ast::Node@ is the base class of all new-ast node classes, which implements reference counting mechanism.
    260 Two different counters are recorded: ``strong'' reference count for number of nodes semantically owning it;
    261 ``weak'' reference count for number of nodes holding a mere reference and only need to observe changes.
    262 Class @ast::ptr_base@ is the smart pointer implementation and also takes care of resource management.
    263 
    264 Direct access through the smart pointer is read-only.
    265 A mutable access should be obtained by calling @shallowCopy@ or mutate as below.
    266 
    267 Currently, the weak pointers are only used to reference declaration nodes from a named type, or a variable expression.
    268 Since declaration nodes are intended to denote unique entities in the program, weak pointers always point to unique (unshared) nodes.
    269 This property may change in the future, and weak references to shared nodes may introduce some problems;
     280This however, may potentially introduce some complications and bugs; a few issues are
     281discussed near the end of this section.
     282
     283\subsubsection{Source: AST/Node.hpp}
     284
     285class @ast::Node@ is the base class of all new-ast node classes, which implements
     286reference counting mechanism. Two different counters are recorded: ``strong'' reference
     287count for number of nodes semantically owning it; ``weak'' reference count for number of
     288nodes holding a mere reference and only need to observe changes.
     289class @ast::ptr_base@ is the smart pointer implementation and also takes care of
     290resource management.
     291
     292Direct access through the smart pointer is read-only. A mutable access should be obtained
     293by calling shallowCopy or mutate as below.
     294
     295Currently, the weak pointers are only used to reference declaration nodes from a named
     296type, or a variable expression. Since declaration nodes are intended to denote unique
     297entities in the program, weak pointers always point to unique (unshared) nodes. This may
     298change in the future, and weak references to shared nodes may introduce some problems;
    270299see mutate function below.
    271300
    272 All node classes should always use smart pointers in structure definitions versus raw pointers.
    273 Function
     301All node classes should always use smart pointers in the structure and should not use raw
     302pointers.
     303
    274304\begin{C++}
    275305void ast::Node::increment(ref_type ref)
    276306\end{C++}
    277 increments this node's strong or weak reference count.
    278 Function
     307Increments this node's strong or weak reference count.
    279308\begin{C++}
    280309void ast::Node::decrement(ref_type ref, bool do_delete = true)
    281310\end{C++}
    282 decrements this node's strong or weak reference count.
    283 If strong reference count reaches zero, the node is deleted.
    284 \NOTE: Setting @do_delete@ to false may result in a detached node.
    285 Subsequent code should manually delete the node or assign it to a strong pointer to prevent memory leak.
    286 
     311Decrements this node's strong or weak reference count. If strong reference count reaches
     312zero, the node is deleted by default.
     313\NOTE: Setting @do_delete@ to false may result in a detached node. Subsequent code should
     314manually delete the node or assign it to a strong pointer to prevent memory leak.
    287315Reference counting functions are internally called by @ast::ptr_base@.
    288 Function
    289316\begin{C++}
    290317template<typename node_t>
    291318node_t * shallowCopy(const node_t * node)
    292319\end{C++}
    293 returns a mutable, shallow copy of node: all child pointers are pointing to the same child nodes.
    294 Function
     320Returns a mutable, shallow copy of node: all child pointers are pointing to the same child
     321nodes.
    295322\begin{C++}
    296323template<typename node_t>
    297324node_t * mutate(const node_t * node)
    298325\end{C++}
    299 returns a mutable pointer to the same node, if the node is unique (strong reference count is 1);
    300 otherwise, it returns @shallowCopy(node)@.
    301 It is an error to mutate a shared node that is weak-referenced.
    302 Currently this does not happen.
    303 A problem may appear once weak pointers to shared nodes (\eg expression nodes) are used;
    304 special care is needed.
    305 
    306 \NOTE: This naive uniqueness check may not be sufficient in some cases.
    307 A discussion of the issue is presented at the end of this section.
    308 Functions
     326If node is unique (strong reference count is 1), returns a mutable pointer to the same node.
     327Otherwise, returns shallowCopy(node).
     328It is an error to mutate a shared node that is weak-referenced. Currently this does not
     329happen. The problem may appear once weak pointers to shared nodes (\eg expression
     330nodes) are used; special care will be needed.
     331
     332\NOTE: This naive uniqueness check may not be sufficient in some cases. A discussion of the
     333issue is presented at the end of this section.
    309334\begin{C++}
    310335template<typename node_t, typename parent_t, typename field_t, typename assn_t>
    311 const node_t * mutate_field(const node_t * node, field_t parent_t::* field, assn_t && val)
     336const node_t * mutate_field(const node_t * node, field_t parent_t::*field, assn_t && val)
    312337\end{C++}
    313338\begin{C++}
    … …  
    317342                field_t && val)
    318343\end{C++}
    319 are helpers for mutating a field on a node using pointer to a member function (creates shallow copy when necessary).
    320 
    321 
    322 \subsubsection{Issue: Undetected Sharing}
    323 
    324 The @mutate@ behaviour described above has a problem: deeper shared nodes may be
     344Helpers for mutating a field on a node using pointer to member (creates shallow copy
     345when necessary).
     346
     347\subsubsection{Issue: Undetected sharing}
     348
     349The @mutate@ behavior described above has a problem: deeper shared nodes may be
    325350mistakenly considered as unique. \VRef[Figure]{f:DeepNodeSharing} shows how the problem could arise:
    326351\begin{figure}
    … …  
    330355\label{f:DeepNodeSharing}
    331356\end{figure}
    332 Given the tree rooted at P1, which is logically the chain P1-A-B, and P2 is irrelevant, assume @mutate(B)@ is called.
    333 The algorithm considers B as unique since it is only directly owned by A.
    334 However, the other tree P2-A-B indirectly shares the node B and is therefore wrongly mutated.
    335 
    336 To partly address this problem, if the mutation is called higher up the tree, a chain mutation helper can be used.
    337 
    338 \subsubsection{Source: \lstinline{AST/Chain.hpp}}
    339 
    340 Function
     357Suppose that we are working on the tree rooted at P1, which
     358is logically the chain P1-A-B and P2 is irrelevant, and then
     359mutate(B) is called. The algorithm considers B as unique since
     360it is only directly owned by A. However, the other tree P2-A-B
     361indirectly shares the node B and is therefore wrongly mutated.
     362
     363To partly address this problem, if the mutation is called higher up the tree, a chain
     364mutation helper can be used:
     365
     366\subsubsection{Source: AST/Chain.hpp}
     367
    341368\begin{C++}
    342369template<typename node_t, Node::ref_type ref_t>
    343370auto chain_mutate(ptr_base<node_t, ref_t> & base)
    344371\end{C++}
    345 returns a chain mutator handle that takes pointer-to-member to go down the tree, while creating shallow copies as necessary;
    346 see @struct _chain_mutator@ in the source code for details.
    347 
    348 For example, in the above diagram, if mutation of B is wanted while at P1, the call using @chain_mutate@ looks like the following:
     372This function returns a chain mutator handle which takes pointer-to-member to go down
     373the tree while creating shallow copies as necessary; see @struct _chain_mutator@ in the
     374source code for details.
     375
     376For example, in the above diagram, if mutation of B is wanted while at P1, the call using
     377@chain_mutate@ looks like the following:
    349378\begin{C++}
    350379chain_mutate(P1.a)(&A.b) = new_value_of_b;
    351380\end{C++}
    352 \NOTE: if some node in chain mutate is shared (therefore shallow copied), it implies that every node further down is also copied, thus correctly executing the functional mutation algorithm.
    353 This example code creates copies of both A and B and performs mutation on the new nodes, so that the other tree P2-A-B is untouched.
    354 However, if a pass traverses down to node B and performs mutation, for example, in @postvisit(B)@, information on sharing higher up is lost.
    355 Since the new-ast structure is only in experimental use with the resolver algorithm, which mostly rebuilds the tree bottom-up, this issue does not actually happen.
    356 It should be addressed in the future when other compilation passes are migrated to new-ast and many of them contain procedural mutations, where it might cause accidental mutations to other logically independent trees (\eg common sub-expression) and become a bug.
    357 
    358 
     381Note that if some node in chain mutate is shared (therefore shallow copied), it implies that
     382every node further down will also be copied, thus correctly executing the functional
     383mutation algorithm. This example code creates copies of both A and B and performs
     384mutation on the new nodes, so that the other tree P2-A-B is untouched.
     385However, if a pass traverses down to node B and performs mutation, for example, in
     386@postvisit(B)@, information on sharing higher up is lost. Since the new-ast structure is only in
     387experimental use with the resolver algorithm, which mostly rebuilds the tree bottom-up,
     388this issue does not actually happen. It should be addressed in the future when other
     389compilation passes are migrated to new-ast and many of them contain procedural
     390mutations, where it might cause accidental mutations to other logically independent trees
     391(\eg common sub-expression) and become a bug.
     392
     393
     394\vspace*{20pt} % FIX ME, spacing problem with this heading ???
    359395\section{Compiler Algorithm Documentation}
    360396
    361 This compiler algorithm documentation covers most of the resolver, data structures used in variable and expression resolution, and a few directly related passes.
    362 Later passes involving code generation are not included yet;
    363 documentation for those will be done latter.
    364 
     397This documentation currently covers most of the resolver, data structures used in variable
     398and expression resolution, and a few directly related passes. Later passes involving code
     399generation is not included yet; documentation for those will be done afterwards.
    365400
    366401\subsection{Symbol Table}
    367402
    368 \NOTE: For historical reasons, the symbol-table data-structure is called @indexer@ in the old implementation.
    369 Hereby, the name is changed to @SymbolTable@.
    370 The symbol table stores a mapping from names to declarations, implements a similar name-space separation rule, and provides the same scoping rules as standard C.\footnote{ISO/IEC 9899:1999, Sections 6.2.1 and 6.2.3.}
    371 The difference in name-space rule is that @typedef@ aliases are no longer considered ordinary identifiers.
    372 In addition to C tag-types (@struct@, @union@, @enum@), \CFA introduces another tag type, @trait@, which is a named collection of assertions.
    373 
    374 
    375 \subsubsection{Source: \lstinline{AST/SymbolTable.hpp}}
    376 
    377 \TODO{Add something here}
    378 
    379 
    380 \subsubsection{Source: \lstinline{SymTab/Indexer.h}}
    381 
    382 Function
     403\NOTE: For historical reasons, the symbol table data structure was called ``indexer'' in the
     404old implementation. Hereby we will be using the name SymbolTable everywhere.
     405The symbol table stores a mapping from names to declarations and implements a similar
     406name space separation rule, and the same scoping rules in standard C.\footnote{ISO/IEC 9899:1999, Sections 6.2.1 and 6.2.3} The difference in
     407name space rule is that typedef aliases are no longer considered ordinary identifiers.
     408In addition to C tag types (struct, union, enum), \CFA introduces another tag type, trait,
     409which is a named collection of assertions.
     410
     411\subsubsection{Source: AST/SymbolTable.hpp}
     412
     413\subsubsection{Source: SymTab/Indexer.h}
     414
    383415\begin{C++}
    384416SymbolTable::addId(const DeclWithType * decl)
    385417\end{C++}
    386 provides name mangling of identifiers, since \CFA allows overloading of variables and functions.
    387 The mangling scheme is closely based on the Itanium \CC ABI,\footnote{\url{https://itanium-cxx-abi.github.io/cxx-abi/abi.html}, Section 5.1} while making adaptations to \CFA specific features, mainly assertions and overloaded variables by type.
    388 
    389 Naming conflicts are handled by mangled names;
    390 lookup by name returns a list of declarations with the same identifier name.
    391 Functions
     418Since \CFA allows overloading of variables and functions, ordinary identifier names need
     419to be mangled. The mangling scheme is closely based on the Itanium \CC ABI,\footnote{\url{https://itanium-cxx-abi.github.io/cxx-abi/abi.html}, Section 5.1} while
     420making adaptations to \CFA specific features, mainly assertions and overloaded variables
     421by type. Naming conflicts are handled by mangled names; lookup by name returns a list of
     422declarations with the same literal identifier name.
     423
    392424\begin{C++}
    393425SymbolTable::addStruct(const StructDecl * decl)
    … …  
    396428SymbolTable::addTrait(const TraitDecl * decl)
    397429\end{C++}
    398 add a tag-type declaration to the symbol table.
    399 Function
     430Adds a tag type declaration to the symbol table.
    400431\begin{C++}
    401432SymbolTable::addType(const NamedTypeDecl * decl)
    402433\end{C++}
    403 adds a @typedef@ alias to the symbol table.
    404 
    405 \textbf{C Incompatibility Note}: Since \CFA allows using @struct@, @union@ and @enum@ type-names without a prefix keyword, as in \CC, @typedef@ names and tag-type names cannot be disambiguated by syntax rules.
    406 Currently the compiler puts them together and disallows collision.
    407 The following program is valid C but invalid \CFA (and \CC):
     434Adds a typedef alias to the symbol table.
     435
     436\textbf{C Incompatibility Note}: Since Cforall allows using struct, union and enum type names
     437without the keywords, typedef names and tag type names cannot be disambiguated by
     438syntax rules. Currently the compiler puts them together and disallows collision. The
     439following program is valid C but not valid Cforall:
    408440\begin{C++}
    409441struct A {};
    410 typedef int A; // gcc: ok, cfa: Cannot redefine typedef A
    411 struct A sa; // C disambiguates via struct prefix
    412 A ia;
    413 \end{C++}
    414 In practices, such usage is extremely rare, and hence, this change (as in \CC) has minimal impact on existing C programs.
    415 The declaration
    416 \begin{C++}
    417 struct A {};
    418 typedef struct A A; // A is an alias for struct A
    419 A a;
    420 struct A b;
    421 \end{C++}
    422 is not an error because the alias name is identical to the original.
    423 Finally, the following program is allowed in \CFA:
    424 \begin{C++}
    425442typedef int A;
    426 void A(); // name mangled
     443// gcc: ok, cfa: Cannot redefine typedef A
     444\end{C++}
     445In actual practices however, such usage is extremely rare, and typedef struct A A; is
     446not considered an error, but silently discarded. Therefore, we expect this change to have
     447minimal impact on existing C programs.
     448Meanwhile, the following program is allowed in Cforall:
     449\begin{C++}
     450typedef int A;
     451void A();
    427452// gcc: A redeclared as different kind of symbol, cfa: ok
    428453\end{C++}
    429 because the function name is mangled.
    430 
    431454
    432455\subsection{Type Environment and Unification}
    433456
    434 The following core ideas underlie the parametric type-resolution algorithm.
    435 A type environment organizes type parameters into \textbf{equivalent classes} and maps them to actual types.
    436 Unification is the algorithm that takes two (possibly parametric) types and parameter mappings, and attempts to produce a common type by matching information in the type environments.
     457The core of parametric type resolution algorithm.
     458Type Environment organizes type parameters in \textbf{equivalent classes} and maps them to
     459actual types. Unification is the algorithm that takes two (possibly parametric) types and
     460parameter mappings and attempts to produce a common type by matching the type
     461environments.
    437462
    438463The unification algorithm is recursive in nature and runs in two different modes internally:
    439464\begin{itemize}
    440465\item
    441 Exact unification mode requires equivalent parameters to match perfectly.
    442 \item
    443 Inexact unification mode allows equivalent parameters to be converted to a common type.
     466\textbf{Exact} unification mode requires equivalent parameters to match perfectly;
     467\item
     468\textbf{Inexact} unification mode allows equivalent parameters to be converted to a
     469common type.
    444470\end{itemize}
    445 For a pair of matching parameters (actually, their equivalent classes), if either side is open (not bound to a concrete type yet), they are combined.
    446 
    447 Within the inexact mode, types are allowed to differ on their cv-qualifiers (\eg @const@, @volatile@, \etc);
    448 additionally, if a type never appear either in a parameter list or as the base type of a pointer, it may also be widened (\ie safely converted).
    449 As \CFA currently does not implement subclassing as in object-oriented languages, widening conversions are only on the primitive types, \eg conversion from @int@ to @long int@.
    450 
    451 The need for two unification modes comes from the fact that parametric types are considered compatible only if all parameters are exactly the same (not just compatible).
    452 Pointer types also behaves similarly;
    453 in fact, they may be viewed as a primitive kind of parametric types.
    454 @int *@ and @long *@ are different types, just like @vector(int)@ and @vector(long)@ are, for the parametric type @*(T)@ / @vector(T)@, respectively.
    455 
    456 The resolver uses the following @public@ functions:\footnote{
    457 Actual code also tracks assertions on type parameters; those extra arguments are omitted here for conciseness.}
    458 
    459 
    460 \subsubsection{Source: \lstinline{ResolvExpr/Unify.cc}}
    461 
    462 Function
    463 \begin{C++}
    464 bool unify(const Type * type1, const Type * type2, TypeEnvironment & env,
    465         OpenVarSet & openVars, const SymbolTable & symtab, Type *& commonType)
    466 \end{C++}
    467 returns a boolean indicating if the unification succeeds or fails after attempting to unify @type1@ and @type2@ within current type environment.
    468 If the unify succeeds, @env@ is modified by combining the equivalence classes of matching parameters in @type1@ and @type2@, and their common type is written to @commonType@.
    469 If the unify fails, nothing changes.
    470 Functions
    471 \begin{C++}
    472 bool typesCompatible(const Type * type1, const Type * type2, const SymbolTable & symtab,
    473         const TypeEnvironment & env)
    474 bool typesCompatibleIgnoreQualifiers(const Type * type1, const Type * type2,
    475         const SymbolTable & symtab, const TypeEnvironment & env)
    476 \end{C++}
    477 return a boolean indicating if types @type1@ and @type2@ can possibly be the same type.
    478 The second version ignores the outermost cv-qualifiers if present.\footnote{
    479 In \lstinline@const int * const@, only the second \lstinline@const@ is ignored.}
    480 These function have no side effects.
    481 
    482 \NOTE: No attempt is made to widen the types (exact unification is used), although the function names may suggest otherwise, \eg @typesCompatible(int, long)@ returns false.
     471For a pair of matching parameters (actually, their equivalent classes), if either side is open
     472(not bound to a concrete type yet), they are simply combined.
     473
     474Within inexact mode, types are allowed to differ on their cv-qualifiers; additionally, if a
     475type never appear either in parameter list or as the base type of a pointer, it may also be
     476widened (i.e. safely converted). As Cforall currently does not implement subclassing similar
     477to object-oriented languages, widening conversions are on primitive types only, for
     478example the conversion from int to long.
     479
     480The need for two unification modes come from the fact that parametric types are
     481considered compatible only if all parameters are exactly the same (not just compatible).
     482Pointer types also behaves similarly; in fact, they may be viewed as a primitive kind of
     483parametric types. @int*@ and @long*@ are different types, just like @vector(int)@ and
     484@vector(long)@ are, for the parametric type @vector(T)@.
     485
     486The resolver should use the following ``@public@'' functions:\footnote{
     487Actual code also tracks assertions on type parameters; those extra arguments are omitted here for
     488conciseness.}
     489
     490
     491\subsubsection{Source: ResolvExpr/Unify.cc}
     492
     493\begin{C++}
     494bool unify(const Type *type1, const Type *type2, TypeEnvironment &env,
     495OpenVarSet &openVars, const SymbolTable &symtab, Type *&commonType)
     496\end{C++}
     497Attempts to unify @type1@ and @type2@ with current type environment.
     498
     499If operation succeeds, @env@ is modified by combining the equivalence classes of matching
     500parameters in @type1@ and @type2@, and their common type is written to commonType.
     501
     502If operation fails, returns false.
     503\begin{C++}
     504bool typesCompatible(const Type * type1, const Type * type2, const
     505SymbolTable &symtab, const TypeEnvironment &env)
     506bool typesCompatibleIgnoreQualifiers(const Type * type1, const Type *
     507type2, const SymbolTable &symtab, const TypeEnvironment &env)
     508\end{C++}
     509
     510Determines if type1 and type2 can possibly be the same type. The second version ignores
     511the outermost cv-qualifiers if present.\footnote{
     512In const \lstinline@int * const@, only the second \lstinline@const@ is ignored.}
     513
     514The call has no side effect.
     515
     516\NOTE: No attempts are made to widen the types (exact unification is used), although the
     517function names may suggest otherwise. E.g. @typesCompatible(int, long)@ returns false.
    483518
    484519
    485520\subsection{Expression Resolution}
    486521
    487 The design of the current version of expression resolver is outlined in the Ph.D.\ thesis by Aaron Moss~\cite{Moss19}.
     522The design of the current version of expression resolver is outlined in the Ph.D. Thesis from
     523Aaron Moss~\cite{Moss19}.
     524
    488525A summary of the resolver algorithm for each expression type is presented below.
    489526
    490 All overloadable operators are modelled as function calls.
    491 For a function call, interpretations of the function and arguments are found recursively.
    492 Then the following steps produce a filtered list of valid interpretations:
     527All overloadable operators are modelled as function calls. For a function call,
     528interpretations of the function and arguments are found recursively. Then the following
     529steps produce a filtered list of valid interpretations:
    493530\begin{enumerate}
    494531\item
    495 From all possible combinations of interpretations of the function and arguments, those where argument types may be converted to function parameter types are considered valid.
     532From all possible combinations of interpretations of the function and arguments,
     533those where argument types may be converted to function parameter types are
     534considered valid.
    496535\item
    497536Valid interpretations with the minimum sum of argument costs are kept.
    498537\item
    499 \label{p:argcost}
    500 Argument costs are then discarded; the actual cost for the function call expression is the sum of conversion costs from the argument types to parameter types.
    501 \item
    502 \label{p:returntype}
    503 For each return type, the interpretations with satisfiable assertions are then sorted by actual cost computed in step~\ref{p:argcost}.
    504 If for a given type, the minimum cost interpretations are not unique, that return type is ambiguous.
    505 If the minimum cost interpretation is unique but contains an ambiguous argument, it is also ambiguous.
     538Argument costs are then discarded; the actual cost for the function call expression is
     539the sum of conversion costs from the argument types to parameter types.
     540\item
     541For each return type, the interpretations with satisfiable assertions are then sorted
     542by actual cost computed in step 3. If for a given type, the minimum cost
     543interpretations are not unique, it is said that for that return type the interpretation
     544is ambiguous. If the minimum cost interpretation is unique but contains an
     545ambiguous argument, it is also considered ambiguous.
    506546\end{enumerate}
    507 Therefore, for each return type, the resolver produces:
     547Therefore, for each return type, the resolver produces either of:
    508548\begin{itemize}
    509549\item
    510 no alternatives
    511 \item
    512 a single valid alternative
    513 \item
    514 an ambiguous alternative
     550No alternatives
     551\item
     552A single valid alternative
     553\item
     554An ambiguous alternative
    515555\end{itemize}
    516 \NOTE: an ambiguous alternative may be discarded at the parent expressions because a different return type matches better for the parent expressions.
    517 
    518 The \emph{non}-overloadable expressions in \CFA are: cast expressions, address-of (unary @&@) expressions, short-circuiting logical expressions (@&&@, @||@) and ternary conditional expression (@?:@).
    519 
    520 For a cast expression, the convertible argument types are kept.
    521 Then the result is selected by lowest argument cost, and further by lowest conversion cost to target type.
    522 If the lowest cost is still not unique or an ambiguous argument interpretation is selected, the cast expression is ambiguous.
    523 In an expression statement, the top level expression is implicitly cast to @void@.
     556Note that an ambiguous alternative may be discarded at the parent expressions because a
     557different return type matches better for the parent expressions.
     558
     559The non-overloadable expressions in Cforall are: cast expressions, address-of (unary @&@)
     560expressions, short-circuiting logical expressions (@&&@, @||@) and ternary conditional
     561expression (@?:@).
     562
     563For a cast expression, the convertible argument types are kept. Then the result is selected
     564by lowest argument cost, and further by lowest conversion cost to target type. If the lowest
     565cost is still not unique, or an ambiguous argument interpretation is selected, the cast
     566expression is ambiguous. In an expression statement, the top level expression is implicitly
     567cast to void.
    524568
    525569For an address-of expression, only lvalue results are kept and the minimum cost is selected.
    526570
    527 For logical expressions @&&@ and @||@, arguments are implicitly cast to @bool@, and follow the rules fr cast expression above.
    528 
    529 For the ternary conditional expression, the condition is implicitly cast to @bool@, and the branch expressions must have compatible types.
    530 Each pair of compatible branch expression types produce a possible interpretation, and the cost is defined as the sum of the expression costs plus the sum of conversion costs to the common type.
    531 
    532 \TODO{Write a specification for expression costs.}
     571For logical expressions @&&@ and @||@, arguments are implicitly cast to bool, and follow the rule
     572of cast expression as above.
     573
     574For the ternary conditional expression, the condition is implicitly cast to bool, and the
     575branch expressions must have compatible types. Each pair of compatible branch
     576expression types produce a possible interpretation, and the cost is defined as the sum of
     577expression costs plus the sum of conversion costs to the common type.
     578
     579TODO: Write a specification for expression costs.
    533580
    534581
    535582\subsection{Assertion Satisfaction}
    536583
    537 The resolver tries to satisfy assertions on expressions only when it is needed: either while selecting from multiple alternatives of a same result type for a function call (step \ref{p:returntype} of resolving function calls) or upon reaching the top level of an expression statement.
    538 
    539 Unsatisfiable alternatives are discarded.
    540 Satisfiable alternatives receive \textbf{implicit parameters}: in \CFA, parametric functions may be separately compiled, as opposed to \CC templates which are only compiled at instantiation.
    541 Given the parametric function-definition:
     584The resolver tries to satisfy assertions on expressions only when it is needed: either while
     585selecting from multiple alternatives of a same result type for a function call (step 4 of
     586resolving function calls), or upon reaching the top level of an expression statement.
     587
     588Unsatisfiable alternatives are discarded. Satisfiable alternatives receive \textbf{implicit
     589parameters}: in Cforall, parametric functions are designed such that they can be compiled
     590separately, as opposed to \CC templates which are only compiled at instantiation. Given a
     591parametric function definition:
    542592\begin{C++}
    543593forall (otype T | {void foo(T);})
    544594void bar (T t) { foo(t); }
    545595\end{C++}
    546 the function @bar@ does not know which @foo@ to call when compiled without knowing the call site, so it requests a function pointer to be passed as an extra argument.
    547 At the call site, implicit parameters are automatically inserted by the compiler.
    548 
    549 \TODO{Explain how recursive assertion satisfaction and polymorphic recursion work.}
     596The function bar does not know which @foo@ to call when compiled without knowing the call
     597site, so it requests a function pointer to be passed as an extra argument. At the call site,
     598implicit parameters are automatically inserted by the compiler.
     599
     600\textbf{TODO}: Explain how recursive assertion satisfaction and polymorphic recursion work.
    550601
    551602
    … …  
    554605\subsection{Test Suites}
    555606
    556 Automatic test suites are located under the @tests/@ directory.
    557 A test case consists of an input CFA source file (suffix @.cfa@), and an expected output file located in the @tests/.expect/@ directory, with the same file name ending with suffix @.txt@.
    558 For example, the test named @tests/tuple/tupleCast.cfa@ has the following files, for example:
     607Automatic test suites are located under the @tests/@ directory. A test case consists of an
     608input CFA source file (name ending with @.cfa@), and an expected output file located
     609in @.expect/@ directory relative to the source file, with the same file name ending with @.txt@.
     610So a test named @tuple/tupleCast@ has the following files, for example:
    559611\begin{C++}
    560612tests/
    561         tuple/
    562                 .expect/
    563                         tupleCast.txt
    564                 tupleCast.cfa
    565 \end{C++}
    566 If compilation fails, the error output is compared to the expect file.
    567 If the compilation succeeds but does not generate an executable, the compilation output is compared to the expect file.
    568 If the compilation succeeds and generates an executable, the executable is run and its output is compared to the expect file.
    569 To run the tests, execute the test script @test.py@ under the @tests/@ directory, with a list of test names to be run, or @--all@ (or @make all-tests@) to run all tests.
    570 The test script reports test cases fail/success, compilation time and program run time.
    571 To see all the options available for @test.py@ using the @--help@ option.
     613..     tuple/
     614......     .expect/
     615..........       tupleCast.txt
     616......     tupleCast.cfa
     617\end{C++}
     618If compilation fails, the error output is compared to the expect file. If compilation succeeds,
     619the built program is run and its output compared to the expect file.
     620To run the tests, execute the test script @test.py@ under the @tests/@ directory, with a list of
     621test names to be run, or @--all@ to run all tests. The test script reports test cases
     622fail/success, compilation time and program run time.
    572623
    573624
    574625\subsection{Performance Reports}
    575626
    576 To turn on performance reports, pass the @-XCFA -S@ flag to the compiler.
    577 Three kinds of performance reports are available:
     627To turn on performance reports, pass @-S@ flag to the compiler.
     628
     6293 kinds of performance reports are available:
    578630\begin{enumerate}
    579631\item
    … …  
    587639@Common/Stats/Counter.h@.
    588640\end{enumerate}
    589 It is suggested to run performance tests with optimization (@g++@ flag @-O3@).
     641It is suggested to run performance tests with optimized build (@g++@ flag @-O3@)
    590642
    591643
Note: See TracChangeset for help on using the changeset viewer.