Changeset 1526e86 for doc/theses


Ignore:
Timestamp:
Sep 30, 2020, 1:50:18 PM (13 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast-unique-expr
Children:
69addb4
Parents:
08e8851
Message:

small updates and some more questions

File:
1 edited

Legend:

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

    r08e8851 r1526e86  
    1313\usepackage{latexsym}                                   % \Box glyph
    1414\usepackage{mathptmx}                                   % better math font with "times"
     15\usepackage{appendix}
    1516\usepackage[usenames]{color}
    1617\input{common}                                          % common CFA document macros
    1718\usepackage[dvips,plainpages=false,pdfpagelabels,pdfpagemode=UseNone,colorlinks=true,pagebackref=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pagebackref=true,breaklinks=true]{hyperref}
    1819\usepackage{breakurl}
     20\urlstyle{sf}
     21
     22% reduce spacing
     23\setlist[itemize]{topsep=5pt,parsep=0pt}% global
     24\setlist[enumerate]{topsep=5pt,parsep=0pt}% global
    1925
    2026\usepackage[pagewise]{lineno}
     
    112118\begin{itemize}
    113119\item
    114 type declaration: @struct@, @union@, @typedef@ or type parameter (see Appendix A.1)
     120type declaration: @struct@, @union@, @typedef@ or type parameter (see \VRef[Appendix]{s:KindsTypeParameters})
    115121\item
    116122variable declaration
     
    374380
    375381\subsubsection{Source: \lstinline{AST/SymbolTable.hpp}}
     382
     383
    376384\subsubsection{Source: \lstinline{SymTab/Indexer.h}}
    377385
     
    526534Each 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.
    527535
     536
    528537\subsection{Conversion and Application Cost}
    529 There 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.
     538
     539There were some unclear parts in the previous documentation in the cost system, as described in the Moss thesis~\cite{Moss19}, section 4.1.2.
     540Some clarification are presented in this section.
    530541
    531542\begin{enumerate}
    532543\item
    533 Conversion 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
    536 The 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
    539 Coercion 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 
     544Conversion to a type denoted by parameter may incur additional cost if the match is not exact.
     545For 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@.
     546
     547\item
     548The 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.
     549A higher specialization level is favoured if argument conversion costs are equal.
     550
     551\item
     552Coercion of pointer types is only allowed in explicit cast expressions;
     553the only allowed implicit pointer casts are adding qualifiers to the base type and cast to @void*@, and these counts as safe conversions.
     554Note that implicit cast from @void *@ to other pointer types is no longer valid, as opposed to standard C.
    541555\end{enumerate}
    542556
     
    556570At the call site, implicit parameters are automatically inserted by the compiler.
    557571
    558 Implementation of implicit parameters is discussed in Appendix A.3.
     572Implementation of implicit parameters is discussed in \VRef[Appendix]{s:ImplementationParametricFunctions}.
    559573
    560574\section{Tests}
     
    597611It is suggested to run performance tests with optimization (@g++@ flag @-O3@).
    598612
     613
     614\begin{appendices}[toc,titletoc]
    599615\section{Appendix}
    600616
     617
    601618\subsection{Kinds of Type Parameters}
    602 The 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 
     619\label{s:KindsTypeParameters}
     620
     621A type parameter in a @forall@ clause has three possible kinds:
     622\begin{enumerate}[listparindent=0pt]
     623\item
     624@dtype@: any data type (built-in or user defined).
     625
     626There is also a difference between opaque types (incomplete types, \ie those with only a forward declaration) and concrete types.
     627Only concrete types can be directly used as a variable type.
     628
     629\CFA provides the @otype@ shorthand to require a type parameter be concrete, which also implicitly asserts the existence of its default and copy constructors, assignment, and destructor\footnote{\CFA implements the same automatic resource management (RAII) semantics as \CC.}.
     630\item
     631@ftype@: any function type.
     632
     633@ftype@ provides two purposes:
     634\begin{itemize}
     635\item
     636Differentiate function pointer from data pointer because (in theory) some systems have different sizes for these pointers.
     637\item
     638Disallow a function pointer to match an overloaded data pointer, since variables and functions can have the same names.
     639\end{itemize}
     640
     641\item
     642@ttype@: tuple (variadic) type.
     643
     644@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.
     645Note however, that it has certain restrictions, as described in the implementation section below.
    611646\end{enumerate}
    612647
     648
    613649\subsection{GNU C Nested Functions}
    614650
     
    616652
    617653In 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++}
    620 bar (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) /* ... */
     654\begin{C++}
     655void bar( int * array, int offset, int size ) {
     656        int access( int * array, int index ) { return array[index + offset]; }
     657        int i;
     658        /* ... */
     659        for ( i = 0; i < size; i++ )
     660                /* ... */ access (array, i) /* ... */
    628661}
    629662\end{C++}
    630 
    631 GCC 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.
     663GCC 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.
     664
    632665
    633666\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).
     667\label{s:ImplementationParametricFunctions}
     668
     669\CFA implements parametric functions using the implicit parameter approach: required assertions are passed to the callee by function pointers;
     670size of a parametric type must also be known if referenced directly (\ie not as a pointer).
    635671
    636672The 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:
     
    641677The parameter (assertion) name must match the actual declarations.
    642678\item
    643 Currently, assertions are all functions. Note that since \CFA has variable overloading, implicit value parameters might also be supported in the future.
     679Currently, assertions are all functions.
     680Note that since \CFA has variable overloading, implicit value parameters might also be supported in the future.
    644681\end{enumerate}
    645682
    646683For example, the \CFA function declaration
    647 
    648684\begin{cfa}
    649 forall(otype T | {int foo(T, int);})
     685forall( otype T | { int foo( T, int ); } )
    650686int bar(T);
    651687\end{cfa}
    652 
    653688after 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++}
    656 int bar(T, size_t, void (*)(T&), void (*)(T&), int (*)(T, int));
    657 \end{C++}
    658 
    659 The 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.
     689\begin{C++}
     690int bar( T, size_t, void (*)(T&), void (*)(T&), int (*)(T, int) );
     691\end{C++}
     692The implicit parameter approach has an apparent issue: when the satisfying declaration is also parametric, it may require its own implicit parameters too.
     693That also causes the supplied implicit parameter to have a different \textbf{actual} type than the \textbf{nominal} type, so it cannot be passed directly.
     694Therefore, a wrapper with matching actual type must be created, and it is here where GCC nested functions are used internally by the compiler.
    660695
    661696Consider the following program:
     
    663698int assertion(int);
    664699
    665 forall (otype T | {int assertion(T);})
     700forall( otype T | { int assertion(T); } )
    666701void foo(T);
    667702
    668 forall (otype T | {void foo(T);})
     703forall(otype T | { void foo(T); } )
    669704void bar(T t) {
    670705        foo(t);
    671706}
    672707\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 
     708The \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.}
    676709\begin{C++}
    677710// ctor, dtor and size arguments are omitted
     
    682715}
    683716\end{C++}
    684 
    685717However, when @bar(1)@ is called, @foo@ cannot be directly provided as an argument:
    686 
    687718\begin{C++}
    688719bar(1, foo); // WRONG: foo has different actual type
    689720\end{C++}
    690 
    691721and an additional step is required:
    692 
    693722\begin{C++}
    694723{
    695724        void _foo_wrapper(int t) {
    696                 foo(t, assertion);
     725                foo( t, assertion );
    697726        }
    698         bar(1, _foo_wrapper);
     727        bar( 1, _foo_wrapper );
    699728}
    700729\end{C++}
    701 
    702 Nested 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.
     730Nested assertions and implicit parameter creation may continue indefinitely.
     731This issue is a limitation of implicit parameter implementation.
     732In 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.
     733The \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).
     734\end{appendices}
    703735
    704736\bibliographystyle{plain}
Note: See TracChangeset for help on using the changeset viewer.