source: doc/theses/fangren_yu_COOP_S20/Report.tex @ 2ff78aa

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since 2ff78aa was 2ff78aa, checked in by Fangren Yu <f37yu@…>, 14 months ago

update documentation, added sections for cost and appendix

  • Property mode set to 100644
File size: 34.5 KB
Line 
1\documentclass[twoside,12pt]{article}
2
3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
4
5% Latex packages used in the document.
6\usepackage{fullpage,times,comment}
7\usepackage{epic,eepic}
8\usepackage{upquote}                                                                    % switch curled `'" to straight
9\usepackage{calc}
10\usepackage{varioref}                                                                   % extended references
11\usepackage[labelformat=simple,aboveskip=0pt,farskip=0pt]{subfig}
12\renewcommand{\thesubfigure}{\alph{subfigure})}
13\usepackage{latexsym}                                   % \Box glyph
14\usepackage{mathptmx}                                   % better math font with "times"
15\usepackage[usenames]{color}
16\input{common}                                          % common CFA document macros
17\usepackage[dvips,plainpages=false,pdfpagelabels,pdfpagemode=UseNone,colorlinks=true,pagebackref=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pagebackref=true,breaklinks=true]{hyperref}
18\usepackage{breakurl}
19
20\usepackage[pagewise]{lineno}
21\renewcommand{\linenumberfont}{\scriptsize\sffamily}
22
23% Default underscore is too low and wide. Cannot use lstlisting "literate" as replacing underscore
24% removes it as a variable-name character so keywords in variables are highlighted. MUST APPEAR
25% AFTER HYPERREF.
26\renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
27\newcommand{\NOTE}{\textbf{NOTE}}
28\newcommand{\TODO}[1]{{\color{Purple}#1}}
29
30\setlength{\topmargin}{-0.45in}                                                 % move running title into header
31\setlength{\headsep}{0.25in}
32
33%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
34
35\CFADefaults
36\lstset{
37language=C++,                                                                                   % make C++ the default language
38}% lstset
39\lstnewenvironment{C++}[1][]                            % use C++ style
40{\lstset{language=C++,moredelim=**[is][\color{red}]{@}{@},#1}}{}
41
42%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
43
44\setcounter{secnumdepth}{3}                             % number subsubsections
45\setcounter{tocdepth}{3}                                % subsubsections in table of contents
46\makeindex
47
48%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
49
50\title{\Huge
51cfa-cc Developer's Reference
52}% title
53
54\author{\LARGE
55Fangren Yu
56}% author
57
58\date{
59\today
60}% date
61
62%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
63
64\begin{document}
65\pagestyle{headings}
66% changed after setting pagestyle
67\renewcommand{\sectionmark}[1]{\markboth{\thesection\quad #1}{\thesection\quad #1}}
68\renewcommand{\subsectionmark}[1]{\markboth{\thesubsection\quad #1}{\thesubsection\quad #1}}
69\pagenumbering{roman}
70\linenumbers                                            % comment out to turn off line numbering
71
72\maketitle
73\pdfbookmark[1]{Contents}{section}
74\tableofcontents
75
76\clearpage
77\thispagestyle{plain}
78\pagenumbering{arabic}
79
80
81\section{Overview}
82
83cfa-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
86Since 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.
87The lack of documentation makes it difficult to develop new features from the current implementation and diagnose problems.
88
89Currently, the \CFA team is also facing poor compiler performance.
90For the development of a new programming language, writing standard libraries is an important component.
91The slow compiler causes building of the library files to take tens of minutes, making iterative development and testing almost impossible.
92There 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
94This developer's reference manual begins the documentation and should be continuously im\-proved until it eventually covers the entire compiler codebase.
95For now, the focus is mainly on the parts being rewritten, and also the primary performance bottleneck, namely the resolution algorithm.
96Its 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}.
97
98
99\section{Compiler Framework}
100
101\CFA source code is first transformed into an abstract syntax tree (AST) by the parser before analyzed by the compiler.
102
103
104\subsection{AST Representation}
105
106
107There are 4 major categories of AST nodes used by the compiler, along with some derived structures.
108
109\subsubsection{Declaration Nodes}
110
111A declaration node represents either of:
112\begin{itemize}
113\item
114type declaration: @struct@, @union@, @typedef@ or type parameter (see Appendix A.1)
115\item
116variable declaration
117\item
118function declaration
119\end{itemize}
120Declarations are introduced by standard C declarations, with the usual scoping rules.
121In addition, declarations can also be qualified by the \lstinline[language=CFA]@forall@ clause (which is the origin of \CFA's name):
122\begin{cfa}
123forall ( <$\emph{TypeParameterList}$> | <$\emph{AssertionList}$> )
124        $\emph{declaration}$
125\end{cfa}
126Type parameters in \CFA are similar to \CC template type parameters.
127The \CFA declaration
128\begin{cfa}
129forall (dtype T) ...
130\end{cfa}
131behaves similarly to the \CC template declaration
132\begin{C++}
133template <typename T> ...
134\end{C++}
135
136Assertions are a distinctive feature of \CFA, similar to \emph{interfaces} in D and Go, and \emph{traits} in Rust.
137Contrary 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.
138Consider the following \CC template:
139\begin{C++}
140@template@ forall<typename T> T foo( T t ) {
141        return t + t * t;
142}
143\end{C++}
144where there are no explicit requirements on the type @T@.
145Therefore, the \CC compiler must deduce what operators are required during textual (macro) expansion of the template at each usage.
146As a result, templates cannot be compiled.
147\CFA assertions specify restrictions on type parameters:
148\begin{cfa}
149forall( dtype T | @{ T ?+?( T, T ); T ?*?( T, T ) }@ ) int foo ( T t ) {
150        return t + t * t;
151}
152\end{cfa}
153Assertions are written using the usual \CFA function declaration syntax.
154Only types with operators ``@+@'' and ``@*@'' work with this function, and the function prototype is sufficient to allow separate compilation.
155
156Type parameters and assertions are used in the following compiler data-structures.
157
158
159\subsubsection{Type Nodes}
160
161Type nodes represent the type of an object or expression.
162Named types reference the corresponding type declarations.
163The type of a function is its function pointer type (same as standard C).
164With the addition of type parameters, named types may contain a list of parameter values (actual parameter types).
165
166
167\subsubsection{Statement Nodes}
168
169Statement nodes represent the executable statements in the program, including basic expression statements, control flows and blocks.
170Local declarations (within a block statement) are represented as declaration statements.
171
172
173\subsubsection{Expression Nodes}
174
175Some expressions are represented differently before and after the resolution stage:
176\begin{itemize}
177\item
178Name expressions: @NameExpr@ pre-resolution, @VariableExpr@ post-resolution
179\item
180Member expressions: @UntypedMemberExpr@ pre-resolution, @MemberExpr@ post-resolution
181\item
182\begin{sloppypar}
183Function call expressions (including overloadable operators): @UntypedExpr@ pre-resolution, @ApplicationExpr@ post-resolution
184\end{sloppypar}
185\end{itemize}
186The pre-resolution representation contains only the symbols.
187Post-resolution links them to the actual variable and function declarations.
188
189
190\subsection{Compilation Passes}
191
192Compilation steps are implemented as passes, which follows a general structural recursion pattern on the syntax tree.
193
194The 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++}
196Pass::visit( node_t node ) {
197        previsit( node );
198        if ( visit_children )
199                for each child of node:
200                        child.accept( this );
201        postvisit( node );
202}
203\end{C++}
204Operations in @previsit@ happen in preorder (top to bottom) and operations in @postvisit@ happen in postorder (bottom to top).
205The precise order of recursive operations on child nodes can be found in @Common/PassVisitor.impl.h@ (old) and @AST/Pass.impl.hpp@ (new).
206
207Implementations of compilation passes follow certain conventions:
208\begin{itemize}
209\item
210Passes \textbf{should not} directly override the visit method (Non-virtual Interface principle);
211if a pass desires different recursion behaviour, it should set @visit_children@ to false and perform recursive calls manually within previsit or postvisit procedures.
212To enable this option, inherit from the @WithShortCircuiting@ mixin.
213\item
214previsit may mutate the node but \textbf{must not} change the node type or return @nullptr@.
215\item
216postvisit may mutate the node, reconstruct it to a different node type, or delete it by returning @nullptr@.
217\item
218If the previsit or postvisit method is not defined for a node type, the step is skipped.
219If the return type is declared as @void@, the original node is returned by default.
220These behaviours are controlled by template specialization rules;
221see @Common/PassVisitor.proto.h@ (old) and @AST/@ @Pass.proto.hpp@ (new) for details.
222\end{itemize}
223Other useful mixin classes for compilation passes include:
224\begin{itemize}
225\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)
231\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:
233\begin{C++}
234class Pass2: public Pass1 {
235        @using Pass1::previsit;@
236        @using Pass1::postvisit;@
237        // new procedures
238}
239\end{C++}
240
241
242\subsection{Data Structure Change (new-ast)}
243
244It has been observed that excessive copying of syntax tree structures accounts for a majority of computation cost and significantly slows down the compiler.
245In the previous implementation of the syntax tree, every internal node has a unique parent;
246therefore all copies are required to duplicate the entire subtree.
247A 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
249The 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.
250Reference counting is used to detect sharing and allowing certain optimizations.
251For a purely functional (immutable) data-structure, all mutations are modelled by shallow copies along the path of mutation.
252With reference counting optimization, unique nodes are allowed to be mutated in place.
253This however, may potentially introduce some complications and bugs;
254a few issues are discussed near the end of this section.
255
256
257\subsubsection{Source: \lstinline{AST/Node.hpp}}
258
259Class @ast::Node@ is the base class of all new-ast node classes, which implements reference counting mechanism.
260Two 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.
262Class @ast::ptr_base@ is the smart pointer implementation and also takes care of resource management.
263
264Direct access through the smart pointer is read-only.
265A mutable access should be obtained by calling @shallowCopy@ or mutate as below.
266
267Currently, the weak pointers are only used to reference declaration nodes from a named type, or a variable expression.
268Since declaration nodes are intended to denote unique entities in the program, weak pointers always point to unique (unshared) nodes.
269This property may change in the future, and weak references to shared nodes may introduce some problems;
270see mutate function below.
271
272All node classes should always use smart pointers in structure definitions versus raw pointers.
273Function
274\begin{C++}
275void ast::Node::increment(ref_type ref)
276\end{C++}
277increments this node's strong or weak reference count.
278Function
279\begin{C++}
280void ast::Node::decrement(ref_type ref, bool do_delete = true)
281\end{C++}
282decrements this node's strong or weak reference count.
283If strong reference count reaches zero, the node is deleted.
284\NOTE: Setting @do_delete@ to false may result in a detached node.
285Subsequent code should manually delete the node or assign it to a strong pointer to prevent memory leak.
286
287Reference counting functions are internally called by @ast::ptr_base@.
288Function
289\begin{C++}
290template<typename node_t>
291node_t * shallowCopy(const node_t * node)
292\end{C++}
293returns a mutable, shallow copy of node: all child pointers are pointing to the same child nodes.
294Function
295\begin{C++}
296template<typename node_t>
297node_t * mutate(const node_t * node)
298\end{C++}
299returns a mutable pointer to the same node, if the node is unique (strong reference count is 1);
300otherwise, it returns @shallowCopy(node)@.
301It is an error to mutate a shared node that is weak-referenced.
302Currently this does not happen.
303A problem may appear once weak pointers to shared nodes (\eg expression nodes) are used;
304special care is needed.
305
306\NOTE: This naive uniqueness check may not be sufficient in some cases.
307A discussion of the issue is presented at the end of this section.
308Functions
309\begin{C++}
310template<typename node_t, typename parent_t, typename field_t, typename assn_t>
311const node_t * mutate_field(const node_t * node, field_t parent_t::* field, assn_t && val)
312\end{C++}
313\begin{C++}
314template<typename node_t, typename parent_t, typename coll_t, typename ind_t,
315                typename field_t>
316const node_t * mutate_field_index(const node_t * node, coll_t parent_t::* field, ind_t i,
317                field_t && val)
318\end{C++}
319are 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
324The @mutate@ behaviour described above has a problem: deeper shared nodes may be
325mistakenly considered as unique. \VRef[Figure]{f:DeepNodeSharing} shows how the problem could arise:
326\begin{figure}
327\centering
328\input{DeepNodeSharing}
329\caption{Deep sharing of nodes}
330\label{f:DeepNodeSharing}
331\end{figure}
332Given the tree rooted at P1, which is logically the chain P1-A-B, and P2 is irrelevant, assume @mutate(B)@ is called.
333The algorithm considers B as unique since it is only directly owned by A.
334However, the other tree P2-A-B indirectly shares the node B and is therefore wrongly mutated.
335
336To 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
340Function
341\begin{C++}
342template<typename node_t, Node::ref_type ref_t>
343auto chain_mutate(ptr_base<node_t, ref_t> & base)
344\end{C++}
345returns a chain mutator handle that takes pointer-to-member to go down the tree, while creating shallow copies as necessary;
346see @struct _chain_mutator@ in the source code for details.
347
348For example, in the above diagram, if mutation of B is wanted while at P1, the call using @chain_mutate@ looks like the following:
349\begin{C++}
350chain_mutate(P1.a)(&A.b) = new_value_of_b;
351\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.
353This 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.
354However, if a pass traverses down to node B and performs mutation, for example, in @postvisit(B)@, information on sharing higher up is lost.
355Since 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.
356It 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
359\section{Compiler Algorithm Documentation}
360
361This compiler algorithm documentation covers most of the resolver, data structures used in variable and expression resolution, and a few directly related passes.
362Later passes involving code generation are not included yet;
363documentation for those will be done latter.
364
365
366\subsection{Symbol Table}
367
368\NOTE: For historical reasons, the symbol-table data-structure is called @indexer@ in the old implementation.
369Hereby, the name is changed to @SymbolTable@.
370The 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.}
371The difference in name-space rule is that @typedef@ aliases are no longer considered ordinary identifiers.
372In 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\subsubsection{Source: \lstinline{SymTab/Indexer.h}}
377
378Function
379\begin{C++}
380SymbolTable::addId(const DeclWithType * decl)
381\end{C++}
382provides name mangling of identifiers, since \CFA allows overloading of variables and functions.
383The 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.
384
385Naming conflicts are handled by mangled names;
386lookup by name returns a list of declarations with the same identifier name.
387Functions
388\begin{C++}
389SymbolTable::addStruct(const StructDecl * decl)
390SymbolTable::addUnion(const UnionDecl * decl)
391SymbolTable::addEnum(const EnumDecl * decl)
392SymbolTable::addTrait(const TraitDecl * decl)
393\end{C++}
394add a tag-type declaration to the symbol table.
395Function
396\begin{C++}
397SymbolTable::addType(const NamedTypeDecl * decl)
398\end{C++}
399adds a @typedef@ alias to the symbol table.
400
401\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.
402Currently the compiler puts them together and disallows collision.
403The following program is valid C but invalid \CFA (and \CC):
404\begin{C++}
405struct A {};
406typedef int A; // gcc: ok, cfa: Cannot redefine typedef A
407struct A sa; // C disambiguates via struct prefix
408A ia;
409\end{C++}
410In practices, such usage is extremely rare, and hence, this change (as in \CC) has minimal impact on existing C programs.
411The declaration
412\begin{C++}
413struct A {};
414typedef struct A A; // A is an alias for struct A
415A a;
416struct A b;
417\end{C++}
418is not an error because the alias name is identical to the original.
419Finally, the following program is allowed in \CFA:
420\begin{C++}
421typedef int A;
422void A(); // name mangled
423// gcc: A redeclared as different kind of symbol, cfa: ok
424\end{C++}
425because the function name is mangled.
426
427
428\subsection{Type Environment and Unification}
429
430The following core ideas underlie the parametric type-resolution algorithm.
431A type environment organizes type parameters into \textbf{equivalent classes} and maps them to actual types.
432Unification 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.
433
434The unification algorithm is recursive in nature and runs in two different modes internally:
435\begin{itemize}
436\item
437Exact unification mode requires equivalent parameters to match perfectly.
438\item
439Inexact unification mode allows equivalent parameters to be converted to a common type.
440\end{itemize}
441For a pair of matching parameters (actually, their equivalent classes), if either side is open (not bound to a concrete type yet), they are combined.
442
443Within the inexact mode, types are allowed to differ on their cv-qualifiers (\eg @const@, @volatile@, \etc);
444additionally, 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).
445As \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@.
446
447The 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).
448Pointer types also behaves similarly;
449in fact, they may be viewed as a primitive kind of parametric types.
450@int *@ and @long *@ are different types, just like @vector(int)@ and @vector(long)@ are, for the parametric type @*(T)@ / @vector(T)@, respectively.
451
452The resolver uses the following @public@ functions:\footnote{
453Actual code also tracks assertions on type parameters; those extra arguments are omitted here for conciseness.}
454
455
456\subsubsection{Source: \lstinline{ResolvExpr/Unify.cc}}
457
458Function
459\begin{C++}
460bool unify(const Type * type1, const Type * type2, TypeEnvironment & env,
461        OpenVarSet & openVars, const SymbolTable & symtab, Type *& commonType)
462\end{C++}
463returns a boolean indicating if the unification succeeds or fails after attempting to unify @type1@ and @type2@ within current type environment.
464If 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@.
465If the unify fails, nothing changes.
466Functions
467\begin{C++}
468bool typesCompatible(const Type * type1, const Type * type2, const SymbolTable & symtab,
469        const TypeEnvironment & env)
470bool typesCompatibleIgnoreQualifiers(const Type * type1, const Type * type2,
471        const SymbolTable & symtab, const TypeEnvironment & env)
472\end{C++}
473return a boolean indicating if types @type1@ and @type2@ can possibly be the same type.
474The second version ignores the outermost cv-qualifiers if present.\footnote{
475In \lstinline@const int * const@, only the second \lstinline@const@ is ignored.}
476These function have no side effects.
477
478\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.
479
480
481\subsection{Expression Resolution}
482
483The design of the current version of expression resolver is outlined in the Ph.D.\ thesis by Aaron Moss~\cite{Moss19}.
484A summary of the resolver algorithm for each expression type is presented below.
485
486All overloadable operators are modelled as function calls.
487For a function call, interpretations of the function and arguments are found recursively.
488Then the following steps produce a filtered list of valid interpretations:
489\begin{enumerate}
490\item
491From all possible combinations of interpretations of the function and arguments, those where argument types may be converted to function parameter types are considered valid.
492\item
493Valid interpretations with the minimum sum of argument costs are kept.
494\item
495\label{p:argcost}
496Argument 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.
497\item
498\label{p:returntype}
499For each return type, the interpretations with satisfiable assertions are then sorted by actual cost computed in step~\ref{p:argcost}.
500If for a given type, the minimum cost interpretations are not unique, that return type is ambiguous.
501If the minimum cost interpretation is unique but contains an ambiguous argument, it is also ambiguous.
502\end{enumerate}
503Therefore, for each return type, the resolver produces:
504\begin{itemize}
505\item
506no alternatives
507\item
508a single valid alternative
509\item
510an ambiguous alternative
511\end{itemize}
512\NOTE: an ambiguous alternative may be discarded at the parent expressions because a different return type matches better for the parent expressions.
513
514The \emph{non}-overloadable expressions in \CFA are: cast expressions, address-of (unary @&@) expressions, short-circuiting logical expressions (@&&@, @||@) and ternary conditional expression (@?:@).
515
516For a cast expression, the convertible argument types are kept.
517Then the result is selected by lowest argument cost, and further by lowest conversion cost to target type.
518If the lowest cost is still not unique or an ambiguous argument interpretation is selected, the cast expression is ambiguous.
519In an expression statement, the top level expression is implicitly cast to @void@.
520
521For an address-of expression, only lvalue results are kept and the minimum cost is selected.
522
523For logical expressions @&&@ and @||@, arguments are implicitly cast to @bool@, and follow the rules fr cast expression above.
524
525For the ternary conditional expression, the condition is implicitly cast to @bool@, and the branch expressions must have compatible types.
526Each 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.
527
528\subsection{Conversion and Application Cost}
529There were some unclear parts in the previous documentation of cost system, as described in the Moss thesis \cite{Moss19}, section 4.1.2. Some clarification are presented in this section.
530
531\begin{enumerate}
532\item
533Conversion to a type denoted by parameter may incur additional cost if the match is not exact. For 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@.
534
535\item
536The specialization level of a function is the sum of the least depth of an appearance of type parameter (counting pointers, references and parameterized types), plus the number of assertions. A higher specialization level is favored if conversion cost of arguments are equal.
537
538\item
539Coercion of pointer types is only allowed in explicit cast expressions; the only allowed implicit pointer casts are adding qualifiers to the base type and cast to @void*@, and those counts as safe conversions. Note that implicit cast from @void*@ to other pointer types is no longer valid, as opposed to standard C.
540
541\end{enumerate}
542
543
544\subsection{Assertion Satisfaction}
545
546The 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.
547
548Unsatisfiable alternatives are discarded.
549Satisfiable alternatives receive \textbf{implicit parameters}: in \CFA, parametric functions may be separately compiled, as opposed to \CC templates which are only compiled at instantiation.
550Given the parametric function-definition:
551\begin{C++}
552forall (otype T | {void foo(T);})
553void bar (T t) { foo(t); }
554\end{C++}
555the 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.
556At the call site, implicit parameters are automatically inserted by the compiler.
557
558Implementation of implicit parameters is discussed in Appendix A.3.
559
560\section{Tests}
561
562\subsection{Test Suites}
563
564Automatic test suites are located under the @tests/@ directory.
565A 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@.
566For example, the test named @tests/tuple/tupleCast.cfa@ has the following files, for example:
567\begin{C++}
568tests/
569        tuple/
570                .expect/
571                        tupleCast.txt
572                tupleCast.cfa
573\end{C++}
574If compilation fails, the error output is compared to the expect file.
575If the compilation succeeds but does not generate an executable, the compilation output is compared to the expect file.
576If the compilation succeeds and generates an executable, the executable is run and its output is compared to the expect file.
577To 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.
578The test script reports test cases fail/success, compilation time and program run time.
579To see all the options available for @test.py@ using the @--help@ option.
580
581
582\subsection{Performance Reports}
583
584To turn on performance reports, pass the @-XCFA -S@ flag to the compiler.
585Three kinds of performance reports are available:
586\begin{enumerate}
587\item
588Time, reports time spent in each compilation step
589\item
590Heap, reports number of dynamic memory allocations, total bytes allocated, and
591maximum heap memory usage
592\item
593Counters, for certain predefined statistics; counters can be registered anywhere in
594the compiler as a static object, and the interface can be found at
595@Common/Stats/Counter.h@.
596\end{enumerate}
597It is suggested to run performance tests with optimization (@g++@ flag @-O3@).
598
599\section{Appendix}
600
601\subsection{Kinds of Type Parameters}
602The type parameters in a @forall@ clause has three different kinds:
603\begin{enumerate}
604\item
605@dtype@: any data type (built-in or user defined). There is also a difference between opaque types (incomplete types, those with only a forward declaration) and concrete types. Only concrete types can be directly used as a variable type. \CFA provides the @otype@ shorthand to require a type parameter as concrete, which also implicitly asserts the existence of its constructor and destructor\footnote{\CFA implements the same automatic resource management (RAII) semantics as \CC.}.
606\item
607@ftype@: any function type. Since @ftype@ does not provide any information about parameter types of a function, it is rarely used. The main purpose of introducing @ftype@ is to disallow a function to match a pointer overload, since variables and functions can have the same names.
608\item
609@ttype@: tuple (variadic) type. @ttype@ parameter may only appear as type of the last parameter in a function, and it provides a type-safe way to implement variadic functions. Note however, that it has certain restrictions, as described in the implementation section below.
610
611\end{enumerate}
612
613\subsection{GNU C Nested Functions}
614
615\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.
616
617In 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}}:
618
619\begin{C++}
620bar (int *array, int offset, int size)
621{
622  int access (int *array, int index)
623    { return array[index + offset]; }
624  int i;
625  /* ... */
626  for (i = 0; i < size; i++)
627    /* ... */ access (array, i) /* ... */
628}
629\end{C++}
630
631GCC nested functions behave identically to \CC lambda functions with default by-reference capture (stack-allocated, lifetime ends upon exiting the block declared in), while also possible to be passed as arguments with standard function pointer types.
632
633\subsection{Implementation of Parametric Functions}
634\CFA implements parametric functions using the implicit parameter approach: required assertions are passed to the callee by function pointers; size of a parametric type must also be known if referenced directly (i.e. not as a pointer).
635
636The 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:
637\begin{enumerate}
638\item
639All types are function declarations are candidates of implicit parameters.
640\item
641The parameter (assertion) name must match the actual declarations.
642\item
643Currently, assertions are all functions. Note that since \CFA has variable overloading, implicit value parameters might also be supported in the future.
644\end{enumerate}
645
646For example, the \CFA function declaration
647
648\begin{cfa}
649forall(otype T | {int foo(T, int);})
650int bar(T);
651\end{cfa}
652
653after 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}.}
654
655\begin{C++}
656int bar(T, size_t, void (*)(T&), void (*)(T&), int (*)(T, int));
657\end{C++}
658
659The implicit parameter approach has an apparent issue: when the satisfying declaration is also parametric, it may require its own implicit parameters too. That also causes the supplied implicit parameter to have a different \textbf{actual} type than the \textbf{nominal} type, so it cannot be passed directly. Therefore, a wrapper with matching actual type must be created, and here it is where GCC nested function is used internally by the compiler.
660
661Consider the following program:
662\begin{cfa}
663int assertion(int);
664
665forall (otype T | {int assertion(T);})
666void foo(T);
667
668forall (otype T | {void foo(T);})
669void bar(T t) {
670        foo(t);
671}
672\end{cfa}
673
674\CFA compiler translates the program to non-parametric form\footnote{In the final code output, 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.}
675
676\begin{C++}
677// ctor, dtor and size arguments are omitted
678void foo(T, int (*)(T));
679
680void bar(T t, void (*foo)(T)) {
681        foo(t);
682}
683\end{C++}
684
685However, when @bar(1)@ is called, @foo@ cannot be directly provided as an argument:
686
687\begin{C++}
688bar(1, foo); // WRONG: foo has different actual type
689\end{C++}
690
691and an additional step is required:
692
693\begin{C++}
694{
695        void _foo_wrapper(int t) {
696                foo(t, assertion);
697        }
698        bar(1, _foo_wrapper);
699}
700\end{C++}
701
702Nested assertions and implicit parameter creation may continue indefinitely. This is a limitation of implicit parameter implementation. In particular, polymorphic variadic recursion must be structural (i.e. number of arguments decreases in any possible recursive calls), otherwise code generation gets into an infinite loop. \CFA compiler sets a limit on assertion depth and reports an error if assertion resolution does not terminate within the limit.
703
704\bibliographystyle{plain}
705\bibliography{pl}
706
707
708\end{document}
709
710% Local Variables: %
711% tab-width: 4 %
712% fill-column: 100 %
713% compile-command: "make" %
714% End: %
Note: See TracBrowser for help on using the repository browser.