Changes in / [69addb4:87b9332]
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/fangren_yu_COOP_S20/Report.tex
r69addb4 r87b9332 13 13 \usepackage{latexsym} % \Box glyph 14 14 \usepackage{mathptmx} % better math font with "times" 15 \usepackage{appendix}16 15 \usepackage[usenames]{color} 17 16 \input{common} % common CFA document macros 18 17 \usepackage[dvips,plainpages=false,pdfpagelabels,pdfpagemode=UseNone,colorlinks=true,pagebackref=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pagebackref=true,breaklinks=true]{hyperref} 19 18 \usepackage{breakurl} 20 \urlstyle{sf}21 22 % reduce spacing23 \setlist[itemize]{topsep=5pt,parsep=0pt}% global24 \setlist[enumerate]{topsep=5pt,parsep=0pt}% global25 19 26 20 \usepackage[pagewise]{lineno} … … 118 112 \begin{itemize} 119 113 \item 120 type declaration: @struct@, @union@, @typedef@ or type parameter (see \VRef[Appendix]{s:KindsTypeParameters})114 type declaration: @struct@, @union@, @typedef@ or type parameter (see Appendix A.1) 121 115 \item 122 116 variable declaration … … 380 374 381 375 \subsubsection{Source: \lstinline{AST/SymbolTable.hpp}} 382 383 384 376 \subsubsection{Source: \lstinline{SymTab/Indexer.h}} 385 377 … … 534 526 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. 535 527 536 537 528 \subsection{Conversion and Application Cost} 538 539 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. 540 Some clarification are presented in this section. 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. 541 530 542 531 \begin{enumerate} 543 532 \item 544 Conversion to a type denoted by parameter may incur additional cost if the match is not exact. 545 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@. 546 547 \item 548 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. 549 A higher specialization level is favoured if argument conversion costs are equal. 550 551 \item 552 Coercion of pointer types is only allowed in explicit cast expressions; 553 the only allowed implicit pointer casts are adding qualifiers to the base type and cast to @void*@, and these counts as safe conversions. 554 Note that implicit cast from @void *@ to other pointer types is no longer valid, as opposed to standard C. 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 555 541 \end{enumerate} 556 542 … … 570 556 At the call site, implicit parameters are automatically inserted by the compiler. 571 557 572 Implementation of implicit parameters is discussed in \VRef[Appendix]{s:ImplementationParametricFunctions}.558 Implementation of implicit parameters is discussed in Appendix A.3. 573 559 574 560 \section{Tests} … … 611 597 It is suggested to run performance tests with optimization (@g++@ flag @-O3@). 612 598 613 614 \begin{appendices}[toc,titletoc]615 599 \section{Appendix} 616 600 617 618 601 \subsection{Kinds of Type Parameters} 619 \label{s:KindsTypeParameters} 620 621 A 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 626 There is also a difference between opaque types (incomplete types, \ie those with only a forward declaration) and concrete types. 627 Only 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 636 Differentiate function pointer from data pointer because (in theory) some systems have different sizes for these pointers. 637 \item 638 Disallow 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. 645 Note however, that it has certain restrictions, as described in the implementation section below. 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 646 611 \end{enumerate} 647 612 648 649 613 \subsection{GNU C Nested Functions} 650 614 … … 652 616 653 617 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}}: 654 \begin{C++} 655 void 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) /* ... */ 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) /* ... */ 661 628 } 662 629 \end{C++} 663 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. 664 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. 665 632 666 633 \subsection{Implementation of Parametric Functions} 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; 670 size of a parametric type must also be known if referenced directly (\ie not as a pointer). 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). 671 635 672 636 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: … … 677 641 The parameter (assertion) name must match the actual declarations. 678 642 \item 679 Currently, assertions are all functions. 680 Note that since \CFA has variable overloading, implicit value parameters might also be supported in the future. 643 Currently, assertions are all functions. Note that since \CFA has variable overloading, implicit value parameters might also be supported in the future. 681 644 \end{enumerate} 682 645 683 646 For example, the \CFA function declaration 647 684 648 \begin{cfa} 685 forall( otype T | { int foo( T, int ); })649 forall(otype T | {int foo(T, int);}) 686 650 int bar(T); 687 651 \end{cfa} 652 688 653 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}.} 689 \begin{C++} 690 int bar( T, size_t, void (*)(T&), void (*)(T&), int (*)(T, int) ); 691 \end{C++} 692 The implicit parameter approach has an apparent issue: when the satisfying declaration is also parametric, it may require its own implicit parameters too. 693 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. 694 The refore, a wrapper with matching actual type must be created, and it is here where GCC nested functions areused internally by the compiler.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. 695 660 696 661 Consider the following program: … … 698 663 int assertion(int); 699 664 700 forall ( otype T | { int assertion(T); })665 forall (otype T | {int assertion(T);}) 701 666 void foo(T); 702 667 703 forall (otype T | { void foo(T); })668 forall (otype T | {void foo(T);}) 704 669 void bar(T t) { 705 670 foo(t); 706 671 } 707 672 \end{cfa} 708 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.} 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 709 676 \begin{C++} 710 677 // ctor, dtor and size arguments are omitted … … 715 682 } 716 683 \end{C++} 684 717 685 However, when @bar(1)@ is called, @foo@ cannot be directly provided as an argument: 686 718 687 \begin{C++} 719 688 bar(1, foo); // WRONG: foo has different actual type 720 689 \end{C++} 690 721 691 and an additional step is required: 692 722 693 \begin{C++} 723 694 { 724 695 void _foo_wrapper(int t) { 725 foo( t, assertion);696 foo(t, assertion); 726 697 } 727 bar( 1, _foo_wrapper);698 bar(1, _foo_wrapper); 728 699 } 729 700 \end{C++} 730 Nested assertions and implicit parameter creation may continue indefinitely. 731 This issue is a limitation of implicit parameter implementation. 732 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. 733 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). 734 \end{appendices} 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. 735 703 736 704 \bibliographystyle{plain}
Note: See TracChangeset
for help on using the changeset viewer.