Changeset 1526e86

Timestamp:

Sep 30, 2020, 1:50:18 PM (4 years ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

69addb4

Parents:

08e8851

Message:

small updates and some more questions

File:

• doc/theses/fangren_yu_COOP_S20/Report.tex (modified) (10 diffs)

doc/theses/fangren_yu_COOP_S20/Report.tex

@@ -13 +13 @@
 \usepackage{latexsym}                                   % \Box glyph
 \usepackage{mathptmx}                                   % better math font with "times"
+\usepackage{appendix}
 \usepackage[usenames]{color}
 \input{common}                                          % common CFA document macros
 \usepackage[dvips,plainpages=false,pdfpagelabels,pdfpagemode=UseNone,colorlinks=true,pagebackref=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pagebackref=true,breaklinks=true]{hyperref}
 \usepackage{breakurl}
+\urlstyle{sf}
+
+% reduce spacing
+\setlist[itemize]{topsep=5pt,parsep=0pt}% global
+\setlist[enumerate]{topsep=5pt,parsep=0pt}% global
 
 \usepackage[pagewise]{lineno}
@@ -112 +118 @@
 \begin{itemize}
 \item
-type declaration: @struct@, @union@, @typedef@ or type parameter (see Appendix A.1)
+type declaration: @struct@, @union@, @typedef@ or type parameter (see \VRef[Appendix]{s:KindsTypeParameters})
 \item
 variable declaration
@@ -374 +380 @@
 
 \subsubsection{Source: \lstinline{AST/SymbolTable.hpp}}
+
+
 \subsubsection{Source: \lstinline{SymTab/Indexer.h}}
 
@@ -526 +534 @@
 Each pair of compatible branch expression types produce a possible interpretation, and the cost is defined as the sum of the expression costs plus the sum of conversion costs to the common type.
 
+
 \subsection{Conversion and Application Cost}
-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.
+
+There were some unclear parts in the previous documentation in the cost system, as described in the Moss thesis~\cite{Moss19}, section 4.1.2.
+Some clarification are presented in this section.
 
 \begin{enumerate}
 \item
-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@.
-
-\item
-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.
-
-\item
-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. 
-
+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@.
+
+\item
+The 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.
+A higher specialization level is favoured if argument conversion costs are equal.
+
+\item
+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 these counts as safe conversions.
+Note that implicit cast from @void *@ to other pointer types is no longer valid, as opposed to standard C. 
 \end{enumerate}
 
@@ -556 +570 @@
 At the call site, implicit parameters are automatically inserted by the compiler.
 
-Implementation of implicit parameters is discussed in Appendix A.3.
+Implementation of implicit parameters is discussed in \VRef[Appendix]{s:ImplementationParametricFunctions}.
 
 \section{Tests}
@@ -597 +611 @@
 It is suggested to run performance tests with optimization (@g++@ flag @-O3@).
 
+
+\begin{appendices}[toc,titletoc]
 \section{Appendix}
 
+
 \subsection{Kinds of Type Parameters}
-The type parameters in a @forall@ clause has three different kinds:
-\begin{enumerate}
-\item
-@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.}.
-\item
-@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.
-\item
-@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.
-
+\label{s:KindsTypeParameters}
+
+A type parameter in a @forall@ clause has three possible kinds:
+\begin{enumerate}[listparindent=0pt]
+\item
+@dtype@: any data type (built-in or user defined).
+
+There is also a difference between opaque types (incomplete types, \ie 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 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.}.
+\item
+@ftype@: any function type.
+
+@ftype@ provides two purposes:
+\begin{itemize}
+\item
+Differentiate function pointer from data pointer because (in theory) some systems have different sizes for these pointers.
+\item
+Disallow a function pointer to match an overloaded data pointer, since variables and functions can have the same names.
+\end{itemize}
+
+\item
+@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.
 \end{enumerate}
 
+
 \subsection{GNU C Nested Functions}
 
@@ -616 +652 @@
 
 In 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}}:
-
-\begin{C++}
-bar (int *array, int offset, int size)
-{
-  int access (int *array, int index)
-    { return array[index + offset]; }
-  int i;
-  /* ... */
-  for (i = 0; i < size; i++)
-    /* ... */ access (array, i) /* ... */
+\begin{C++}
+void bar( int * array, int offset, int size ) {
+        int access( int * array, int index ) { return array[index + offset]; }
+        int i;
+        /* ... */
+        for ( i = 0; i < size; i++ )
+                /* ... */ access (array, i) /* ... */
 }
 \end{C++}
-
-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.
+GCC 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.
+
 
 \subsection{Implementation of Parametric Functions}
-\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). 
+\label{s:ImplementationParametricFunctions}
+
+\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 (\ie not as a pointer). 
 
 The 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:
@@ -641 +677 @@
 The parameter (assertion) name must match the actual declarations.
 \item
-Currently, assertions are all functions. Note that since \CFA has variable overloading, implicit value parameters might also be supported in the future.
+Currently, assertions are all functions.
+Note that since \CFA has variable overloading, implicit value parameters might also be supported in the future.
 \end{enumerate}
 
 For example, the \CFA function declaration
-
 \begin{cfa}
-forall(otype T | {int foo(T, int);})
+forall( otype T | { int foo( T, int ); } )
 int bar(T);
 \end{cfa}
-
 after 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}.}
-
-\begin{C++}
-int bar(T, size_t, void (*)(T&), void (*)(T&), int (*)(T, int));
-\end{C++}
-
-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.
+\begin{C++}
+int bar( T, size_t, void (*)(T&), void (*)(T&), int (*)(T, int) );
+\end{C++}
+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 it is here where GCC nested functions are used internally by the compiler.
 
 Consider the following program:
@@ -663 +698 @@
 int assertion(int);
 
-forall (otype T | {int assertion(T);})
+forall( otype T | { int assertion(T); } )
 void foo(T);
 
-forall (otype T | {void foo(T);})
+forall(otype T | { void foo(T); } )
 void bar(T t) {
         foo(t);
 }
 \end{cfa}
-
-\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.}
-
+The \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.}
 \begin{C++}
 // ctor, dtor and size arguments are omitted
@@ -682 +715 @@
 }
 \end{C++}
-
 However, when @bar(1)@ is called, @foo@ cannot be directly provided as an argument:
-
 \begin{C++}
 bar(1, foo); // WRONG: foo has different actual type
 \end{C++}
-
 and an additional step is required:
-
 \begin{C++}
 {
         void _foo_wrapper(int t) {
-                foo(t, assertion);
+                foo( t, assertion );
         }
-        bar(1, _foo_wrapper);
+        bar( 1, _foo_wrapper );
 }
 \end{C++}
-
-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.
+Nested assertions and implicit parameter creation may continue indefinitely.
+This issue is a limitation of implicit parameter implementation.
+In 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.
+The \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).
+\end{appendices}
 
 \bibliographystyle{plain}