Changeset 2ff78aa


Ignore:
Timestamp:
Sep 29, 2020, 1:50:22 PM (13 months ago)
Author:
Fangren Yu <f37yu@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast-unique-expr
Children:
08e8851
Parents:
6cc913e
Message:

update documentation, added sections for cost and appendix

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/fangren_yu_COOP_S20/Report.tex

    r6cc913e r2ff78aa  
    112112\begin{itemize}
    113113\item
    114 type declaration: @struct@, @union@, @typedef@ or type parameter \TODO{(see Appendix A.3)}
     114type declaration: @struct@, @union@, @typedef@ or type parameter (see Appendix A.1)
    115115\item
    116116variable declaration
     
    374374
    375375\subsubsection{Source: \lstinline{AST/SymbolTable.hpp}}
    376 
    377 \TODO{Add something here}
    378 
    379 
    380376\subsubsection{Source: \lstinline{SymTab/Indexer.h}}
    381377
     
    530526Each 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.
    531527
    532 \TODO{Write a specification for expression costs.}
     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}
    533542
    534543
     
    547556At the call site, implicit parameters are automatically inserted by the compiler.
    548557
    549 \TODO{Explain how recursive assertion satisfaction and polymorphic recursion work.}
    550 
     558Implementation of implicit parameters is discussed in Appendix A.3.
    551559
    552560\section{Tests}
     
    589597It is suggested to run performance tests with optimization (@g++@ flag @-O3@).
    590598
     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.
    591703
    592704\bibliographystyle{plain}
Note: See TracChangeset for help on using the changeset viewer.