Changeset 223a633 for doc/theses


Ignore:
Timestamp:
Oct 15, 2020, 3:41:38 PM (4 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
b9537e6
Parents:
33c3ded (diff), 0b18db7 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:
doc/theses
Files:
10 added
3 edited
23 moved

Legend:

Unmodified
Added
Removed

  • doc/theses/andrew_beach_MMath/thesis.tex

    r33c3ded r223a633  
    3434\usepackage[toc,abbreviations]{glossaries-extra}
    3535
    36 % Main glossary entries -- definitions of relevant terminology
    37 \newglossaryentry{computer}
    38 {
    39 name=computer,
    40 description={A programmable machine that receives input data,
    41                stores and manipulates the data, and provides
    42                formatted output}
    43 }
    44 
    45 % Nomenclature glossary entries -- New definitions, or unusual terminology
    46 \newglossary*{nomenclature}{Nomenclature}
    47 \newglossaryentry{dingledorf}
    48 {
    49 type=nomenclature,
    50 name=dingledorf,
    51 description={A person of supposed average intelligence who makes incredibly
    52                brainless misjudgments}
    53 }
    54 
    55 % List of Abbreviations (abbreviations are from the glossaries-extra package)
    56 \newabbreviation{aaaaz}{AAAAZ}{American Association of Amature Astronomers
    57                and Zoologists}
    58 
    59 % List of Symbols
    60 \newglossary*{symbols}{List of Symbols}
    61 \newglossaryentry{rvec}
    62 {
    63 name={$\mathbf{v}$},
    64 sort={label},
    65 type=symbols,
    66 description={Random vector: a location in n-dimensional Cartesian space, where
    67                each dimensional component is determined by a random process}
    68 }
     36% Define all the glossaries.
     37\input{glossaries}
    6938
    7039% Generate the glossaries defined above.

  • doc/theses/fangren_yu_COOP_S20/Makefile

    r33c3ded r223a633  
    4646# File Dependencies #
    4747
    48 
    4948${DOCUMENT} : ${BASE}.ps
    5049        ps2pdf $<

  • doc/theses/fangren_yu_COOP_S20/Report.tex

    r33c3ded r223a633  
    1 \documentclass[twoside,12pt]{article}
     1\documentclass[twoside,11pt]{article}
    22
    33%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    … …  
    1111\usepackage[labelformat=simple,aboveskip=0pt,farskip=0pt]{subfig}
    1212\renewcommand{\thesubfigure}{\alph{subfigure})}
     13\usepackage[flushmargin]{footmisc}                                              % support label/reference in footnote
    1314\usepackage{latexsym}                                   % \Box glyph
    1415\usepackage{mathptmx}                                   % better math font with "times"
     16\usepackage[toc]{appendix}                                                              % article does not have appendix
    1517\usepackage[usenames]{color}
    1618\input{common}                                          % common CFA document macros
    1719\usepackage[dvips,plainpages=false,pdfpagelabels,pdfpagemode=UseNone,colorlinks=true,pagebackref=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pagebackref=true,breaklinks=true]{hyperref}
    1820\usepackage{breakurl}
     21\urlstyle{sf}
     22
     23% reduce spacing
     24\setlist[itemize]{topsep=5pt,parsep=0pt}% global
     25\setlist[enumerate]{topsep=5pt,parsep=0pt}% global
    1926
    2027\usepackage[pagewise]{lineno}
    … …  
    2633\renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
    2734\newcommand{\NOTE}{\textbf{NOTE}}
     35\newcommand{\TODO}[1]{{\color{Purple}#1}}
    2836
    2937\setlength{\topmargin}{-0.45in}                                                 % move running title into header
    … …  
    3240%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    3341
    34 \CFADefaults
     42\CFAStyle                                                                                               % CFA code-style for all languages
    3543\lstset{
    36 language=C++,                                                                                   % make C++ the default language
    37 escapechar=\$,                                                                                  % LaTeX escape in CFA code
    38 moredelim=**[is][\color{red}]{`}{`},
     44language=C++,moredelim=**[is][\color{red}]{@}{@}                % make C++ the default language
    3945}% lstset
    40 \lstMakeShortInline@%
    4146\lstnewenvironment{C++}[1][]                            % use C++ style
    42 {\lstset{language=C++,moredelim=**[is][\protect\color{red}]{`}{`},#1}}
    43 {}
     47{\lstset{language=C++,moredelim=**[is][\color{red}]{@}{@}}\lstset{#1}}{}
    4448
    4549%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    … …  
    8488\section{Overview}
    8589
    86 cfa-cc is the reference compiler for the \CFA programming language, which is a non-
    87 object-oriented extension to C.
    88 \CFA attempts to introduce productive modern programming language features to C
    89 while maintaining as much backward-compatibility as possible, so that most existing C
    90 programs can seamlessly work with \CFA.
    91 
    92 Since the \CFA project was dated back to the early 2000s, and only restarted in the past
    93 few years, there is a significant amount of legacy code in the current compiler codebase,
    94 with little proper documentation available. This becomes a difficulty while developing new
    95 features based on the previous implementations, and especially while diagnosing
    96 problems.
    97 
    98 Currently, the \CFA team is also facing another problem: bad compiler performance. For
    99 the development of a new programming language, writing a standard library is an
    100 important part. The incompetence of the compiler causes building the library files to take
    101 tens of minutes, making iterative development and testing almost impossible. There is
    102 ongoing effort to rewrite the core data structure of the compiler to overcome the
    103 performance issue, but many bugs may appear during the work, and lack of documentation
    104 makes debugging extremely difficult.
    105 
    106 This developer's reference will be continuously improved and eventually cover the
    107 compiler codebase. For now, the focus is mainly on the parts being rewritten, and also the
    108 performance bottleneck, namely the resolution algorithm. It is aimed to provide new
    109 developers to the project enough guidance and clarify the purposes and behavior of certain
    110 functions which are not mentioned in the previous \CFA research papers.
     90@cfa-cc@ is the reference compiler for the \CFA programming language, which is a non-object-oriented extension to C.
     91\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.
     92
     93Since 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.
     94The lack of documentation makes it difficult to develop new features from the current implementation and diagnose problems.
     95
     96Currently, the \CFA team is also facing poor compiler performance.
     97For the development of a new programming language, writing standard libraries is an important component.
     98The slow compiler causes building of the library files to take tens of minutes, making iterative development and testing almost impossible.
     99There 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.
     100
     101This developer's reference manual begins the documentation and should be continuously im\-proved until it eventually covers the entire compiler codebase.
     102For now, the focus is mainly on the parts being rewritten, and also the primary performance bottleneck, namely the resolution algorithm.
     103Its 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}.
    111104
    112105
    113106\section{Compiler Framework}
    114107
     108\CFA source code is first transformed into an abstract syntax tree (AST) by the parser before analyzed by the compiler.
     109
     110
    115111\subsection{AST Representation}
    116112
    117 Source code input is first transformed into abstract syntax tree (AST) representation by the
    118 parser before analyzed by the compiler.
    119 
    120 There are 4 major categories of AST nodes used by the compiler, along with some derived
    121 structures.
    122 
    123 \subsubsection{Declaration nodes}
     113
     114There are 4 major categories of AST nodes used by the compiler, along with some derived structures.
     115
     116\subsubsection{Declaration Nodes}
    124117
    125118A declaration node represents either of:
    126119\begin{itemize}
    127120\item
    128 Type declaration: struct, union, typedef or type parameter (see Appendix A.3)
    129 \item
    130 Variable declaration
    131 \item
    132 Function declaration
     121type declaration: @struct@, @union@, @typedef@ or type parameter (see \VRef[Appendix]{s:KindsTypeParameters})
     122\item
     123variable declaration
     124\item
     125function declaration
    133126\end{itemize}
    134127Declarations are introduced by standard C declarations, with the usual scoping rules.
    135 In addition, declarations can also be introduced by the forall clause (which is the origin
    136 of \CFA's name):
     128In addition, declarations can also be qualified by the \lstinline[language=CFA]@forall@ clause (which is the origin of \CFA's name):
    137129\begin{cfa}
    138 forall (<$\emph{TypeParameterList}$> | <$\emph{AssertionList}$>)
     130forall ( <$\emph{TypeParameterList}$> | <$\emph{AssertionList}$> )
    139131        $\emph{declaration}$
    140132\end{cfa}
    141 Type parameters in \CFA are similar to \CC template type parameters. The \CFA
    142 declaration
     133Type parameters in \CFA are similar to \CC template type parameters.
     134The \CFA declaration
    143135\begin{cfa}
    144136forall (dtype T) ...
    145137\end{cfa}
    146 behaves similarly as the \CC template declaration
     138behaves similarly to the \CC template declaration
    147139\begin{C++}
    148140template <typename T> ...
    149141\end{C++}
    150142
    151 Assertions are a distinctive feature of \CFA: contrary to the \CC template where
    152 arbitrary functions and operators can be used in a template definition, in a \CFA
    153 parametric function, operations on parameterized types must be declared in assertions.
    154 
     143Assertions are a distinctive feature of \CFA, similar to \emph{interfaces} in D and Go, and \emph{traits} in Rust.
     144Contrary 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.
    155145Consider the following \CC template:
    156146\begin{C++}
    157 template <typename T> int foo(T t) {
    158         return bar(t) + baz(t);
     147@template@ forall<typename T> T foo( T t ) {
     148        return t + t * t;
    159149}
    160150\end{C++}
    161 Unless bar and baz are also parametric functions taking any argument type, they must be
    162 declared in the assertions, or otherwise the code will not compile:
     151where there are no explicit requirements on the type @T@.
     152Therefore, the \CC compiler must deduce what operators are required during textual (macro) expansion of the template at each usage.
     153As a result, templates cannot be compiled.
     154\CFA assertions specify restrictions on type parameters:
    163155\begin{cfa}
    164 forall (dtype T | { int bar(T); int baz(t); }) int foo (T t) {
    165         return bar(t) + baz(t);
     156forall( dtype T | @{ T ?+?( T, T ); T ?*?( T, T ) }@ ) int foo ( T t ) {
     157        return t + t * t;
    166158}
    167159\end{cfa}
    168 Assertions are written using the usual function declaration syntax. The scope of type
    169 parameters and assertions is the following declaration.
    170 
    171 \subsubsection{Type nodes}
    172 
    173 A type node represents the type of an object or expression.
    174 Named types reference the corresponding type declarations. The type of a function is its
    175 function pointer type (same as standard C).
    176 With the addition of type parameters, named types may contain a list of parameter values
    177 (actual parameter types).
    178 
    179 \subsubsection{Statement nodes}
    180 
    181 Statement nodes represent the statements in the program, including basic expression
    182 statements, control flows and blocks.
     160Assertions are written using the usual \CFA function declaration syntax.
     161Only types with operators ``@+@'' and ``@*@'' work with this function, and the function prototype is sufficient to allow separate compilation.
     162
     163Type parameters and assertions are used in the following compiler data-structures.
     164
     165
     166\subsubsection{Type Nodes}
     167
     168Type nodes represent the type of an object or expression.
     169Named types reference the corresponding type declarations.
     170The type of a function is its function pointer type (same as standard C).
     171With the addition of type parameters, named types may contain a list of parameter values (actual parameter types).
     172
     173
     174\subsubsection{Statement Nodes}
     175
     176Statement nodes represent the executable statements in the program, including basic expression statements, control flows and blocks.
    183177Local declarations (within a block statement) are represented as declaration statements.
    184178
    185 \subsubsection{Expression nodes}
    186 
    187 Some expressions are represented differently in the compiler before and after resolution
    188 stage:
     179
     180\subsubsection{Expression Nodes}
     181
     182Some expressions are represented differently before and after the resolution stage:
    189183\begin{itemize}
    190184\item
    191 Name expressions: NameExpr pre-resolution, VariableExpr post-resolution
    192 \item
    193 Member expressions: UntypedMemberExpr pre-resolution, MemberExpr post-resolution
    194 \item
    195 Function call expressions (including overloadable operators): UntypedExpr pre-resolution, ApplicationExpr post-resolution
     185Name expressions: @NameExpr@ pre-resolution, @VariableExpr@ post-resolution
     186\item
     187Member expressions: @UntypedMemberExpr@ pre-resolution, @MemberExpr@ post-resolution
     188\item
     189\begin{sloppypar}
     190Function call expressions (including overloadable operators): @UntypedExpr@ pre-resolution, @ApplicationExpr@ post-resolution
     191\end{sloppypar}
    196192\end{itemize}
    197 The pre-resolution representations contain only the symbols. Post-resolution results link
    198 them to the actual variable and function declarations.
     193The pre-resolution representation contains only the symbols.
     194Post-resolution links them to the actual variable and function declarations.
    199195
    200196
    201197\subsection{Compilation Passes}
    202198
    203 Compilation steps are implemented as passes, which follows a general structural recursion
    204 pattern on the syntax tree.
    205 
    206 The basic work flow of compilation passes follows preorder and postorder traversal on
    207 tree data structure, implemented with visitor pattern, and can be loosely described with
    208 the following pseudocode:
    209 \begin{C++}
    210 Pass::visit (node_t node) {
    211         previsit(node);
    212         if (visit_children)
     199Compilation steps are implemented as passes, which follows a general structural recursion pattern on the syntax tree.
     200
     201The 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:
     202\begin{C++}
     203Pass::visit( node_t node ) {
     204        previsit( node );
     205        if ( visit_children )
    213206                for each child of node:
    214                         child.accept(this);
    215         postvisit(node);
     207                        child.accept( this );
     208        postvisit( node );
    216209}
    217210\end{C++}
    218 Operations in previsit() happen in preorder (top to bottom) and operations in
    219 postvisit() happen in postorder (bottom to top). The precise order of recursive
    220 operations on child nodes can be found in @Common/PassVisitor.impl.h@ (old) and
    221 @AST/Pass.impl.hpp@ (new).
    222 Implementations of compilation passes need to follow certain conventions:
     211Operations in @previsit@ happen in preorder (top to bottom) and operations in @postvisit@ happen in postorder (bottom to top).
     212The precise order of recursive operations on child nodes can be found in @Common/PassVisitor.impl.h@ (old) and @AST/Pass.impl.hpp@ (new).
     213
     214Implementations of compilation passes follow certain conventions:
    223215\begin{itemize}
    224216\item
    225 Passes \textbf{should not} directly override the visit method (Non-virtual Interface
    226 principle); if a pass desires different recursion behavior, it should set
    227 @visit_children@ to false and perform recursive calls manually within previsit or
    228 postvisit procedures. To enable this option, inherit from @WithShortCircuiting@ mixin.
    229 \item
    230 previsit may mutate the node but \textbf{must not} change the node type or return null.
    231 \item
    232 postvisit may mutate the node, reconstruct it to a different node type, or delete it by
    233 returning null.
     217Passes \textbf{should not} directly override the visit method (Non-virtual Interface principle);
     218if a pass desires different recursion behaviour, it should set @visit_children@ to false and perform recursive calls manually within previsit or postvisit procedures.
     219To enable this option, inherit from the @WithShortCircuiting@ mixin.
     220\item
     221previsit may mutate the node but \textbf{must not} change the node type or return @nullptr@.
     222\item
     223postvisit may mutate the node, reconstruct it to a different node type, or delete it by returning @nullptr@.
    234224\item
    235225If the previsit or postvisit method is not defined for a node type, the step is skipped.
    236 If the return type is declared as void, the original node is returned by default. These
    237 behaviors are controlled by template specialization rules; see
    238 @Common/PassVisitor.proto.h@ (old) and @AST/Pass.proto.hpp@ (new) for details.
     226If the return type is declared as @void@, the original node is returned by default.
     227These behaviours are controlled by template specialization rules;
     228see @Common/PassVisitor.proto.h@ (old) and @AST/@ @Pass.proto.hpp@ (new) for details.
    239229\end{itemize}
    240230Other useful mixin classes for compilation passes include:
    241231\begin{itemize}
    242232\item
    243 WithGuards allows saving values of variables and restore automatically upon exiting
    244 the current node.
    245 \item
    246 WithVisitorRef creates a wrapped entity of current pass (the actual argument
    247 passed to recursive calls internally) for explicit recursion, usually used together
    248 with WithShortCircuiting.
    249 \item
    250 WithSymbolTable gives a managed symbol table with built-in scoping rule handling
    251 (\eg on entering and exiting a block statement)
     233@WithGuards@ allows saving and restoring variable values automatically upon entering/exiting the current node.
     234\item
     235@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@.
     236\item
     237@WithSymbolTable@ gives a managed symbol table with built-in scoping-rule handling (\eg on entering and exiting a block statement)
    252238\end{itemize}
    253 \NOTE: If a pass extends the functionality of another existing pass, due to \CC overloading
    254 resolution rules, it \textbf{must} explicitly introduce the inherited previsit and postvisit procedures
    255 to its own scope, or otherwise they will not be picked up by template resolution:
     239\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:
    256240\begin{C++}
    257241class Pass2: public Pass1 {
    258         using Pass1::previsit;
    259         using Pass1::postvisit;
     242        @using Pass1::previsit;@
     243        @using Pass1::postvisit;@
    260244        // new procedures
    261245}
    … …  
    263247
    264248
    265 \subsection{Data Structure Change WIP (new-ast)}
    266 
    267 It has been observed that excessive copying of syntax tree structures accounts for a
    268 majority of computation cost and significantly slows down the compiler. In the previous
    269 implementation of the syntax tree, every internal node has a unique parent; therefore all
    270 copies are required to duplicate everything down to the bottom. A new, experimental
    271 re-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
    273 of common sub-structures and only makes copies when necessary.
    274 
    275 The 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
    277 used to detect sharing and allows optimization. For a purely functional (a.k.a. immutable)
    278 data structure, all mutations are modelled by shallow copies along the path of mutation.
     249\subsection{Data Structure Change (new-ast)}
     250
     251It has been observed that excessive copying of syntax tree structures accounts for a majority of computation cost and significantly slows down the compiler.
     252In the previous implementation of the syntax tree, every internal node has a unique parent;
     253therefore all copies are required to duplicate the entire subtree.
     254A 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.
     255
     256The 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.
     257Reference counting is used to detect sharing and allowing certain optimizations.
     258For a purely functional (immutable) data-structure, all mutations are modelled by shallow copies along the path of mutation.
    279259With reference counting optimization, unique nodes are allowed to be mutated in place.
    280 This however, may potentially introduce some complications and bugs; a few issues are
    281 discussed near the end of this section.
    282 
    283 \subsubsection{Source: AST/Node.hpp}
    284 
    285 class @ast::Node@ is the base class of all new-ast node classes, which implements
    286 reference counting mechanism. Two different counters are recorded: ``strong'' reference
    287 count for number of nodes semantically owning it; ``weak'' reference count for number of
    288 nodes holding a mere reference and only need to observe changes.
    289 class @ast::ptr_base@ is the smart pointer implementation and also takes care of
    290 resource management.
    291 
    292 Direct access through the smart pointer is read-only. A mutable access should be obtained
    293 by calling shallowCopy or mutate as below.
    294 
    295 Currently, the weak pointers are only used to reference declaration nodes from a named
    296 type, or a variable expression. Since declaration nodes are intended to denote unique
    297 entities in the program, weak pointers always point to unique (unshared) nodes. This may
    298 change in the future, and weak references to shared nodes may introduce some problems;
     260This however, may potentially introduce some complications and bugs;
     261a few issues are discussed near the end of this section.
     262
     263
     264\subsubsection{Source: \lstinline{AST/Node.hpp}}
     265
     266Class @ast::Node@ is the base class of all new-ast node classes, which implements reference counting mechanism.
     267Two different counters are recorded: ``strong'' reference count for number of nodes semantically owning it;
     268``weak'' reference count for number of nodes holding a mere reference and only need to observe changes.
     269Class @ast::ptr_base@ is the smart pointer implementation and also takes care of resource management.
     270
     271Direct access through the smart pointer is read-only.
     272A mutable access should be obtained by calling @shallowCopy@ or mutate as below.
     273
     274Currently, the weak pointers are only used to reference declaration nodes from a named type, or a variable expression.
     275Since declaration nodes are intended to denote unique entities in the program, weak pointers always point to unique (unshared) nodes.
     276This property may change in the future, and weak references to shared nodes may introduce some problems;
    299277see mutate function below.
    300278
    301 All node classes should always use smart pointers in the structure and should not use raw
    302 pointers.
    303 
     279All node classes should always use smart pointers in structure definitions versus raw pointers.
     280Function
    304281\begin{C++}
    305282void ast::Node::increment(ref_type ref)
    306283\end{C++}
    307 Increments this node's strong or weak reference count.
     284increments this node's strong or weak reference count.
     285Function
    308286\begin{C++}
    309287void ast::Node::decrement(ref_type ref, bool do_delete = true)
    310288\end{C++}
    311 Decrements this node's strong or weak reference count. If strong reference count reaches
    312 zero, the node is deleted by default.
    313 \NOTE: Setting @do_delete@ to false may result in a detached node. Subsequent code should
    314 manually delete the node or assign it to a strong pointer to prevent memory leak.
     289decrements this node's strong or weak reference count.
     290If strong reference count reaches zero, the node is deleted.
     291\NOTE: Setting @do_delete@ to false may result in a detached node.
     292Subsequent code should manually delete the node or assign it to a strong pointer to prevent memory leak.
     293
    315294Reference counting functions are internally called by @ast::ptr_base@.
     295Function
    316296\begin{C++}
    317297template<typename node_t>
    318298node_t * shallowCopy(const node_t * node)
    319299\end{C++}
    320 Returns a mutable, shallow copy of node: all child pointers are pointing to the same child
    321 nodes.
     300returns a mutable, shallow copy of node: all child pointers are pointing to the same child nodes.
     301Function
    322302\begin{C++}
    323303template<typename node_t>
    324304node_t * mutate(const node_t * node)
    325305\end{C++}
    326 If node is unique (strong reference count is 1), returns a mutable pointer to the same node.
    327 Otherwise, returns shallowCopy(node).
    328 It is an error to mutate a shared node that is weak-referenced. Currently this does not
    329 happen. The problem may appear once weak pointers to shared nodes (\eg expression
    330 nodes) 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
    333 issue is presented at the end of this section.
     306returns a mutable pointer to the same node, if the node is unique (strong reference count is 1);
     307otherwise, it returns @shallowCopy(node)@.
     308It is an error to mutate a shared node that is weak-referenced.
     309Currently this does not happen.
     310A problem may appear once weak pointers to shared nodes (\eg expression nodes) are used;
     311special care is needed.
     312
     313\NOTE: This naive uniqueness check may not be sufficient in some cases.
     314A discussion of the issue is presented at the end of this section.
     315Functions
    334316\begin{C++}
    335317template<typename node_t, typename parent_t, typename field_t, typename assn_t>
    336 const node_t * mutate_field(const node_t * node, field_t parent_t::*field, assn_t && val)
     318const node_t * mutate_field(const node_t * node, field_t parent_t::* field, assn_t && val)
    337319\end{C++}
    338320\begin{C++}
    … …  
    342324                field_t && val)
    343325\end{C++}
    344 Helpers for mutating a field on a node using pointer to member (creates shallow copy
    345 when necessary).
    346 
    347 \subsubsection{Issue: Undetected sharing}
    348 
    349 The @mutate@ behavior described above has a problem: deeper shared nodes may be
     326are helpers for mutating a field on a node using pointer to a member function (creates shallow copy when necessary).
     327
     328
     329\subsubsection{Issue: Undetected Sharing}
     330
     331The @mutate@ behaviour described above has a problem: deeper shared nodes may be
    350332mistakenly considered as unique. \VRef[Figure]{f:DeepNodeSharing} shows how the problem could arise:
    351333\begin{figure}
    … …  
    355337\label{f:DeepNodeSharing}
    356338\end{figure}
    357 Suppose that we are working on the tree rooted at P1, which
    358 is logically the chain P1-A-B and P2 is irrelevant, and then
    359 mutate(B) is called. The algorithm considers B as unique since
    360 it is only directly owned by A. However, the other tree P2-A-B
    361 indirectly shares the node B and is therefore wrongly mutated.
    362 
    363 To partly address this problem, if the mutation is called higher up the tree, a chain
    364 mutation helper can be used:
    365 
    366 \subsubsection{Source: AST/Chain.hpp}
    367 
     339Given the tree rooted at P1, which is logically the chain P1-A-B, and P2 is irrelevant, assume @mutate(B)@ is called.
     340The algorithm considers B as unique since it is only directly owned by A.
     341However, the other tree P2-A-B indirectly shares the node B and is therefore wrongly mutated.
     342
     343To partly address this problem, if the mutation is called higher up the tree, a chain mutation helper can be used.
     344
     345\subsubsection{Source: \lstinline{AST/Chain.hpp}}
     346
     347Function
    368348\begin{C++}
    369349template<typename node_t, Node::ref_type ref_t>
    370350auto chain_mutate(ptr_base<node_t, ref_t> & base)
    371351\end{C++}
    372 This function returns a chain mutator handle which takes pointer-to-member to go down
    373 the tree while creating shallow copies as necessary; see @struct _chain_mutator@ in the
    374 source code for details.
    375 
    376 For example, in the above diagram, if mutation of B is wanted while at P1, the call using
    377 @chain_mutate@ looks like the following:
     352returns a chain mutator handle that takes pointer-to-member to go down the tree, while creating shallow copies as necessary;
     353see @struct _chain_mutator@ in the source code for details.
     354
     355For example, in the above diagram, if mutation of B is wanted while at P1, the call using @chain_mutate@ looks like the following:
    378356\begin{C++}
    379357chain_mutate(P1.a)(&A.b) = new_value_of_b;
    380358\end{C++}
    381 Note that if some node in chain mutate is shared (therefore shallow copied), it implies that
    382 every node further down will also be copied, thus correctly executing the functional
    383 mutation algorithm. This example code creates copies of both A and B and performs
    384 mutation on the new nodes, so that the other tree P2-A-B is untouched.
    385 However, 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
    387 experimental use with the resolver algorithm, which mostly rebuilds the tree bottom-up,
    388 this issue does not actually happen. It should be addressed in the future when other
    389 compilation passes are migrated to new-ast and many of them contain procedural
    390 mutations, 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 ???
     359\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.
     360This 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.
     361However, if a pass traverses down to node B and performs mutation, for example, in @postvisit(B)@, information on sharing higher up is lost.
     362Since 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.
     363It 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.
     364
     365
    395366\section{Compiler Algorithm Documentation}
    396367
    397 This documentation currently covers most of the resolver, data structures used in variable
    398 and expression resolution, and a few directly related passes. Later passes involving code
    399 generation is not included yet; documentation for those will be done afterwards.
     368This compiler algorithm documentation covers most of the resolver, data structures used in variable and expression resolution, and a few directly related passes.
     369Later passes involving code generation are not included yet;
     370documentation for those will be done latter.
     371
    400372
    401373\subsection{Symbol Table}
    402374
    403 \NOTE: For historical reasons, the symbol table data structure was called ``indexer'' in the
    404 old implementation. Hereby we will be using the name SymbolTable everywhere.
    405 The symbol table stores a mapping from names to declarations and implements a similar
    406 name 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
    407 name space rule is that typedef aliases are no longer considered ordinary identifiers.
    408 In addition to C tag types (struct, union, enum), \CFA introduces another tag type, trait,
    409 which is a named collection of assertions.
    410 
    411 \subsubsection{Source: AST/SymbolTable.hpp}
    412 
    413 \subsubsection{Source: SymTab/Indexer.h}
    414 
     375\NOTE: For historical reasons, the symbol-table data-structure is called @indexer@ in the old implementation.
     376Hereby, the name is changed to @SymbolTable@.
     377The 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.}
     378The difference in name-space rule is that @typedef@ aliases are no longer considered ordinary identifiers.
     379In addition to C tag-types (@struct@, @union@, @enum@), \CFA introduces another tag type, @trait@, which is a named collection of assertions.
     380
     381
     382\subsubsection{Source: \lstinline{AST/SymbolTable.hpp}}
     383
     384Function
    415385\begin{C++}
    416386SymbolTable::addId(const DeclWithType * decl)
    417387\end{C++}
    418 Since \CFA allows overloading of variables and functions, ordinary identifier names need
    419 to 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
    420 making adaptations to \CFA specific features, mainly assertions and overloaded variables
    421 by type. Naming conflicts are handled by mangled names; lookup by name returns a list of
    422 declarations with the same literal identifier name.
    423 
     388provides name mangling of identifiers, since \CFA allows overloading of variables and functions.
     389The 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.
     390
     391Naming conflicts are handled by mangled names;
     392lookup by name returns a list of declarations with the same identifier name.
     393Functions
    424394\begin{C++}
    425395SymbolTable::addStruct(const StructDecl * decl)
    … …  
    428398SymbolTable::addTrait(const TraitDecl * decl)
    429399\end{C++}
    430 Adds a tag type declaration to the symbol table.
     400add a tag-type declaration to the symbol table.
     401Function
    431402\begin{C++}
    432403SymbolTable::addType(const NamedTypeDecl * decl)
    433404\end{C++}
    434 Adds a typedef alias to the symbol table.
    435 
    436 \textbf{C Incompatibility Note}: Since Cforall allows using struct, union and enum type names
    437 without the keywords, typedef names and tag type names cannot be disambiguated by
    438 syntax rules. Currently the compiler puts them together and disallows collision. The
    439 following program is valid C but not valid Cforall:
     405adds a @typedef@ alias to the symbol table.
     406
     407\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.
     408Currently the compiler puts them together and disallows collision.
     409The following program is valid C but invalid \CFA (and \CC):
    440410\begin{C++}
    441411struct A {};
     412typedef int A; // gcc: ok, cfa: Cannot redefine typedef A
     413struct A sa; // C disambiguates via struct prefix
     414A ia;
     415\end{C++}
     416In practices, such usage is extremely rare, and hence, this change (as in \CC) has minimal impact on existing C programs.
     417The declaration
     418\begin{C++}
     419struct A {};
     420typedef struct A A; // A is an alias for struct A
     421A a;
     422struct A b;
     423\end{C++}
     424is not an error because the alias name is identical to the original.
     425Finally, the following program is allowed in \CFA:
     426\begin{C++}
    442427typedef int A;
    443 // gcc: ok, cfa: Cannot redefine typedef A
    444 \end{C++}
    445 In actual practices however, such usage is extremely rare, and typedef struct A A; is
    446 not considered an error, but silently discarded. Therefore, we expect this change to have
    447 minimal impact on existing C programs.
    448 Meanwhile, the following program is allowed in Cforall:
    449 \begin{C++}
    450 typedef int A;
    451 void A();
     428void A(); // name mangled
    452429// gcc: A redeclared as different kind of symbol, cfa: ok
    453430\end{C++}
     431because the function name is mangled.
     432
    454433
    455434\subsection{Type Environment and Unification}
    456435
    457 The core of parametric type resolution algorithm.
    458 Type Environment organizes type parameters in \textbf{equivalent classes} and maps them to
    459 actual types. Unification is the algorithm that takes two (possibly parametric) types and
    460 parameter mappings and attempts to produce a common type by matching the type
    461 environments.
     436The following core ideas underlie the parametric type-resolution algorithm.
     437A type environment organizes type parameters into \textbf{equivalent classes} and maps them to actual types.
     438Unification 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.
    462439
    463440The unification algorithm is recursive in nature and runs in two different modes internally:
    464441\begin{itemize}
    465442\item
    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
    469 common type.
     443Exact unification mode requires equivalent parameters to match perfectly.
     444\item
     445Inexact unification mode allows equivalent parameters to be converted to a common type.
    470446\end{itemize}
    471 For 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 
    474 Within inexact mode, types are allowed to differ on their cv-qualifiers; additionally, if a
    475 type never appear either in parameter list or as the base type of a pointer, it may also be
    476 widened (i.e. safely converted). As Cforall currently does not implement subclassing similar
    477 to object-oriented languages, widening conversions are on primitive types only, for
    478 example the conversion from int to long.
    479 
    480 The need for two unification modes come from the fact that parametric types are
    481 considered compatible only if all parameters are exactly the same (not just compatible).
    482 Pointer types also behaves similarly; in fact, they may be viewed as a primitive kind of
    483 parametric types. @int*@ and @long*@ are different types, just like @vector(int)@ and
    484 @vector(long)@ are, for the parametric type @vector(T)@.
    485 
    486 The resolver should use the following ``@public@'' functions:\footnote{
    487 Actual code also tracks assertions on type parameters; those extra arguments are omitted here for
    488 conciseness.}
    489 
    490 
    491 \subsubsection{Source: ResolvExpr/Unify.cc}
    492 
    493 \begin{C++}
    494 bool unify(const Type *type1, const Type *type2, TypeEnvironment &env,
    495 OpenVarSet &openVars, const SymbolTable &symtab, Type *&commonType)
    496 \end{C++}
    497 Attempts to unify @type1@ and @type2@ with current type environment.
    498 
    499 If operation succeeds, @env@ is modified by combining the equivalence classes of matching
    500 parameters in @type1@ and @type2@, and their common type is written to commonType.
    501 
    502 If operation fails, returns false.
    503 \begin{C++}
    504 bool typesCompatible(const Type * type1, const Type * type2, const
    505 SymbolTable &symtab, const TypeEnvironment &env)
    506 bool typesCompatibleIgnoreQualifiers(const Type * type1, const Type *
    507 type2, const SymbolTable &symtab, const TypeEnvironment &env)
    508 \end{C++}
    509 
    510 Determines if type1 and type2 can possibly be the same type. The second version ignores
    511 the outermost cv-qualifiers if present.\footnote{
    512 In const \lstinline@int * const@, only the second \lstinline@const@ is ignored.}
    513 
    514 The call has no side effect.
    515 
    516 \NOTE: No attempts are made to widen the types (exact unification is used), although the
    517 function names may suggest otherwise. E.g. @typesCompatible(int, long)@ returns false.
     447For a pair of matching parameters (actually, their equivalent classes), if either side is open (not bound to a concrete type yet), they are combined.
     448
     449Within the inexact mode, types are allowed to differ on their cv-qualifiers (\eg @const@, @volatile@, \etc);
     450additionally, 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).
     451As \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@.
     452
     453The 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).
     454Pointer types also behaves similarly;
     455in fact, they may be viewed as a primitive kind of parametric types.
     456@int *@ and @long *@ are different types, just like @vector(int)@ and @vector(long)@ are, for the parametric type @*(T)@ / @vector(T)@, respectively.
     457
     458The resolver uses the following @public@ functions:\footnote{
     459Actual code also tracks assertions on type parameters; those extra arguments are omitted here for conciseness.}
     460
     461
     462\subsubsection{Source: \lstinline{ResolvExpr/Unify.cc}}
     463
     464Function
     465\begin{C++}
     466bool unify(const Type * type1, const Type * type2, TypeEnvironment & env,
     467        OpenVarSet & openVars, const SymbolTable & symtab, Type *& commonType)
     468\end{C++}
     469returns a boolean indicating if the unification succeeds or fails after attempting to unify @type1@ and @type2@ within current type environment.
     470If 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@.
     471If the unify fails, nothing changes.
     472Functions
     473\begin{C++}
     474bool typesCompatible(const Type * type1, const Type * type2, const SymbolTable & symtab,
     475        const TypeEnvironment & env)
     476bool typesCompatibleIgnoreQualifiers(const Type * type1, const Type * type2,
     477        const SymbolTable & symtab, const TypeEnvironment & env)
     478\end{C++}
     479return a boolean indicating if types @type1@ and @type2@ can possibly be the same type.
     480The second version ignores the outermost cv-qualifiers if present.\footnote{
     481In \lstinline@const int * const@, only the second \lstinline@const@ is ignored.}
     482These function have no side effects.
     483
     484\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.
    518485
    519486
    520487\subsection{Expression Resolution}
    521488
    522 The design of the current version of expression resolver is outlined in the Ph.D. Thesis from
    523 Aaron Moss~\cite{Moss19}.
    524 
     489The design of the current version of expression resolver is outlined in the Ph.D.\ thesis by Aaron Moss~\cite{Moss19}.
    525490A summary of the resolver algorithm for each expression type is presented below.
    526491
    527 All overloadable operators are modelled as function calls. For a function call,
    528 interpretations of the function and arguments are found recursively. Then the following
    529 steps produce a filtered list of valid interpretations:
     492All overloadable operators are modelled as function calls.
     493For a function call, interpretations of the function and arguments are found recursively.
     494Then the following steps produce a filtered list of valid interpretations:
    530495\begin{enumerate}
    531496\item
    532 From all possible combinations of interpretations of the function and arguments,
    533 those where argument types may be converted to function parameter types are
    534 considered valid.
     497From all possible combinations of interpretations of the function and arguments, those where argument types may be converted to function parameter types are considered valid.
    535498\item
    536499Valid interpretations with the minimum sum of argument costs are kept.
    537500\item
    538 Argument costs are then discarded; the actual cost for the function call expression is
    539 the sum of conversion costs from the argument types to parameter types.
    540 \item
    541 For each return type, the interpretations with satisfiable assertions are then sorted
    542 by actual cost computed in step 3. If for a given type, the minimum cost
    543 interpretations are not unique, it is said that for that return type the interpretation
    544 is ambiguous. If the minimum cost interpretation is unique but contains an
    545 ambiguous argument, it is also considered ambiguous.
     501\label{p:argcost}
     502Argument 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.
     503\item
     504\label{p:returntype}
     505For each return type, the interpretations with satisfiable assertions are then sorted by actual cost computed in step~\ref{p:argcost}.
     506If for a given type, the minimum cost interpretations are not unique, that return type is ambiguous.
     507If the minimum cost interpretation is unique but contains an ambiguous argument, it is also ambiguous.
    546508\end{enumerate}
    547 Therefore, for each return type, the resolver produces either of:
     509Therefore, for each return type, the resolver produces:
    548510\begin{itemize}
    549511\item
    550 No alternatives
    551 \item
    552 A single valid alternative
    553 \item
    554 An ambiguous alternative
     512no alternatives
     513\item
     514a single valid alternative
     515\item
     516an ambiguous alternative
    555517\end{itemize}
    556 Note that an ambiguous alternative may be discarded at the parent expressions because a
    557 different return type matches better for the parent expressions.
    558 
    559 The non-overloadable expressions in Cforall are: cast expressions, address-of (unary @&@)
    560 expressions, short-circuiting logical expressions (@&&@, @||@) and ternary conditional
    561 expression (@?:@).
    562 
    563 For a cast expression, the convertible argument types are kept. Then the result is selected
    564 by lowest argument cost, and further by lowest conversion cost to target type. If the lowest
    565 cost is still not unique, or an ambiguous argument interpretation is selected, the cast
    566 expression is ambiguous. In an expression statement, the top level expression is implicitly
    567 cast to void.
     518\NOTE: an ambiguous alternative may be discarded at the parent expressions because a different return type matches better for the parent expressions.
     519
     520The \emph{non}-overloadable expressions in \CFA are: cast expressions, address-of (unary @&@) expressions, short-circuiting logical expressions (@&&@, @||@) and ternary conditional expression (@?:@).
     521
     522For a cast expression, the convertible argument types are kept.
     523Then the result is selected by lowest argument cost, and further by lowest conversion cost to target type.
     524If the lowest cost is still not unique or an ambiguous argument interpretation is selected, the cast expression is ambiguous.
     525In an expression statement, the top level expression is implicitly cast to @void@.
    568526
    569527For an address-of expression, only lvalue results are kept and the minimum cost is selected.
    570528
    571 For logical expressions @&&@ and @||@, arguments are implicitly cast to bool, and follow the rule
    572 of cast expression as above.
    573 
    574 For the ternary conditional expression, the condition is implicitly cast to bool, and the
    575 branch expressions must have compatible types. Each pair of compatible branch
    576 expression types produce a possible interpretation, and the cost is defined as the sum of
    577 expression costs plus the sum of conversion costs to the common type.
    578 
    579 TODO: Write a specification for expression costs.
     529For logical expressions @&&@ and @||@, arguments are implicitly cast to @bool@, and follow the rules fr cast expression above.
     530
     531For the ternary conditional expression, the condition is implicitly cast to @bool@, and the branch expressions must have compatible types.
     532Each 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.
     533
     534
     535\subsection{Conversion and Application Cost}
     536
     537There were some unclear parts in the previous documentation in the cost system, as described in the Moss thesis~\cite{Moss19}, section 4.1.2.
     538Some clarification are presented in this section.
     539
     540\begin{enumerate}
     541\item
     542Conversion to a type denoted by parameter may incur additional cost if the match is not exact.
     543For example, if a function is declared to accept @(T, T)@ and receives @(int, long)@, @T@ is deducted @long@ and an additional widening conversion cost is added for @int@ to @T@.
     544
     545\item
     546The specialization level of a function is the sum of the least depth of an appearance of a type parameter (counting pointers, references and parameterized types), plus the number of assertions.
     547A higher specialization level is favoured if argument conversion costs are equal.
     548
     549\item
     550Coercion of pointer types is only allowed in explicit cast expressions;
     551the only allowed implicit pointer casts are adding qualifiers to the base type and cast to @void*@, and these counts as safe conversions.
     552Note that implicit cast from @void *@ to other pointer types is no longer valid, as opposed to standard C.
     553\end{enumerate}
    580554
    581555
    582556\subsection{Assertion Satisfaction}
    583557
    584 The resolver tries to satisfy assertions on expressions only when it is needed: either while
    585 selecting from multiple alternatives of a same result type for a function call (step 4 of
    586 resolving function calls), or upon reaching the top level of an expression statement.
    587 
    588 Unsatisfiable alternatives are discarded. Satisfiable alternatives receive \textbf{implicit
    589 parameters}: in Cforall, parametric functions are designed such that they can be compiled
    590 separately, as opposed to \CC templates which are only compiled at instantiation. Given a
    591 parametric function definition:
     558The 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.
     559
     560Unsatisfiable alternatives are discarded.
     561Satisfiable alternatives receive \textbf{implicit parameters}: in \CFA, parametric functions may be separately compiled, as opposed to \CC templates which are only compiled at instantiation.
     562Given the parametric function-definition:
    592563\begin{C++}
    593564forall (otype T | {void foo(T);})
    594565void bar (T t) { foo(t); }
    595566\end{C++}
    596 The function bar does not know which @foo@ to call when compiled without knowing the call
    597 site, so it requests a function pointer to be passed as an extra argument. At the call site,
    598 implicit parameters are automatically inserted by the compiler.
    599 
    600 \textbf{TODO}: Explain how recursive assertion satisfaction and polymorphic recursion work.
    601 
     567the 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.
     568At the call site, implicit parameters are automatically inserted by the compiler.
     569
     570Implementation of implicit parameters is discussed in \VRef[Appendix]{s:ImplementationParametricFunctions}.
    602571
    603572\section{Tests}
    … …  
    605574\subsection{Test Suites}
    606575
    607 Automatic test suites are located under the @tests/@ directory. A test case consists of an
    608 input CFA source file (name ending with @.cfa@), and an expected output file located
    609 in @.expect/@ directory relative to the source file, with the same file name ending with @.txt@.
    610 So a test named @tuple/tupleCast@ has the following files, for example:
     576Automatic test suites are located under the @tests/@ directory.
     577A 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@.
     578For example, the test named @tests/tuple/tupleCast.cfa@ has the following files, for example:
    611579\begin{C++}
    612580tests/
    613 ..     tuple/
    614 ......     .expect/
    615 ..........       tupleCast.txt
    616 ......     tupleCast.cfa
    617 \end{C++}
    618 If compilation fails, the error output is compared to the expect file. If compilation succeeds,
    619 the built program is run and its output compared to the expect file.
    620 To run the tests, execute the test script @test.py@ under the @tests/@ directory, with a list of
    621 test names to be run, or @--all@ to run all tests. The test script reports test cases
    622 fail/success, compilation time and program run time.
     581        tuple/
     582                .expect/
     583                        tupleCast.txt
     584                tupleCast.cfa
     585\end{C++}
     586If compilation fails, the error output is compared to the expect file.
     587If the compilation succeeds but does not generate an executable, the compilation output is compared to the expect file.
     588If the compilation succeeds and generates an executable, the executable is run and its output is compared to the expect file.
     589To 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.
     590The test script reports test cases fail/success, compilation time and program run time.
     591To see all the options available for @test.py@ using the @--help@ option.
    623592
    624593
    625594\subsection{Performance Reports}
    626595
    627 To turn on performance reports, pass @-S@ flag to the compiler.
    628 
    629 3 kinds of performance reports are available:
     596To turn on performance reports, pass the @-XCFA -S@ flag to the compiler.
     597Three kinds of performance reports are available:
    630598\begin{enumerate}
    631599\item
    … …  
    639607@Common/Stats/Counter.h@.
    640608\end{enumerate}
    641 It is suggested to run performance tests with optimized build (@g++@ flag @-O3@)
    642 
     609It is suggested to run performance tests with optimization (@g++@ flag @-O3@).
     610
     611
     612\appendix
     613\section{Appendix}
     614
     615\subsection{Kinds of Type Parameters}
     616\label{s:KindsTypeParameters}
     617
     618A type parameter in a @forall@ clause has 3 kinds:
     619\begin{enumerate}[listparindent=0pt]
     620\item
     621@dtype@: any data type (built-in or user defined) that is not a concrete type.
     622
     623A non-concrete type is an incomplete type such as an opaque type or pointer/reference with an implicit (pointer) size and implicitly generated reference and dereference operations.
     624\item
     625@otype@: any data type (built-in or user defined) that is concrete type.
     626
     627A concrete type is a complete type, \ie types that can be used to create a variable, which also implicitly asserts the existence of default and copy constructors, assignment, and destructor\footnote{\CFA implements the same automatic resource management (RAII) semantics as \CC.}.
     628% \item
     629% @ftype@: any function type.
     630%
     631% @ftype@ provides two purposes:
     632% \begin{itemize}
     633% \item
     634% Differentiate function pointer from data pointer because (in theory) some systems have different sizes for these pointers.
     635% \item
     636% Disallow a function pointer to match an overloaded data pointer, since variables and functions can have the same names.
     637% \end{itemize}
     638
     639\item
     640@ttype@: tuple (variadic) type.
     641
     642Restricted to the type for the last parameter in a function, it provides a type-safe way to implement variadic functions.
     643Note however, that it has certain restrictions, as described in the implementation section below.
     644\end{enumerate}
     645
     646
     647\subsection{GNU C Nested Functions}
     648
     649\CFA is designed to be mostly compatible with GNU C, an extension to ISO C99 and C11 standards. The \CFA compiler also implements some language features by GCC extensions, most notably nested functions.
     650
     651In ISO C, function definitions are not allowed to be nested. GCC allows nested functions with full lexical scoping. The following example is taken from GCC documentation\footnote{\url{https://gcc.gnu.org/onlinedocs/gcc/Nested-Functions.html}}:
     652\begin{C++}
     653void bar( int * array, int offset, int size ) {
     654        int access( int * array, int index ) { return array[index + offset]; }
     655        int i;
     656        /* ... */
     657        for ( i = 0; i < size; i++ )
     658                /* ... */ access (array, i) /* ... */
     659}
     660\end{C++}
     661GCC nested functions behave identically to \CC lambda functions with default by-reference capture (stack-allocated, lifetime ends upon exiting the declared block), while also possible to be passed as arguments with standard function pointer types.
     662
     663
     664\subsection{Implementation of Parametric Functions}
     665\label{s:ImplementationParametricFunctions}
     666
     667\CFA implements parametric functions using the implicit parameter approach: required assertions are passed to the callee by function pointers;
     668size of a parametric type must also be known if referenced directly (\ie not as a pointer).
     669
     670The implementation is similar to the one from Scala\footnote{\url{https://www.scala-lang.org/files/archive/spec/2.13/07-implicits.html}}, with some notable differences in resolution:
     671\begin{enumerate}
     672\item
     673All types, variables, and functions are candidates of implicit parameters
     674\item
     675The parameter (assertion) name must match the actual declarations.
     676\end{enumerate}
     677
     678For example, the \CFA function declaration
     679\begin{cfa}
     680forall( otype T | { int foo( T, int ); } )
     681int bar(T);
     682\end{cfa}
     683after implicit parameter expansion, has the actual signature\footnote{\textbf{otype} also requires the type to have constructor and destructor, which are the first two function pointers preceding the one for \textbf{foo}.}
     684\begin{C++}
     685int bar( T, size_t, void (*)(T&), void (*)(T&), int (*)(T, int) );
     686\end{C++}
     687The implicit parameter approach has an apparent issue: when the satisfying declaration is also parametric, it may require its own implicit parameters too.
     688That also causes the supplied implicit parameter to have a different \textbf{actual} type than the \textbf{nominal} type, so it cannot be passed directly.
     689Therefore, a wrapper with matching actual type must be created, and it is here where GCC nested functions are used internally by the compiler.
     690
     691Consider the following program:
     692\begin{cfa}
     693int assertion(int);
     694
     695forall( otype T | { int assertion(T); } )
     696void foo(T);
     697
     698forall(otype T | { void foo(T); } )
     699void bar(T t) {
     700        foo(t);
     701}
     702\end{cfa}
     703The \CFA compiler translates the program to non-parametric form\footnote{In the final code output, \lstinline@T@ needs to be replaced by an opaque type, and arguments must be accessed by a frame pointer offset table, due to the unknown sizes. The presented code here is simplified for better understanding.}
     704\begin{C++}
     705// ctor, dtor and size arguments are omitted
     706void foo(T, int (*)(T));
     707
     708void bar(T t, void (*foo)(T)) {
     709        foo(t);
     710}
     711\end{C++}
     712However, when @bar(1)@ is called, @foo@ cannot be directly provided as an argument:
     713\begin{C++}
     714bar(1, foo); // WRONG: foo has different actual type
     715\end{C++}
     716and an additional step is required:
     717\begin{C++}
     718{
     719        void _foo_wrapper(int t) {
     720                foo( t, assertion );
     721        }
     722        bar( 1, _foo_wrapper );
     723}
     724\end{C++}
     725Nested assertions and implicit parameter creation may continue indefinitely.
     726This issue is a limitation of implicit parameter implementation.
     727In particular, polymorphic variadic recursion must be structural (\ie the number of arguments decreases in any possible recursive calls), otherwise code generation gets into an infinite loop.
     728The \CFA compiler sets a limit on assertion depth and reports an error if assertion resolution does not terminate within the limit (as for \lstinline[language=C++]@templates@ in \CC).
    643729
    644730\bibliographystyle{plain}
Note: See TracChangeset for help on using the changeset viewer.