Changeset 6603c1d for doc


Ignore:
Timestamp:
Aug 15, 2016, 10:18:22 AM (10 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, ctor, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, memory, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, stuck-waitfor-destruct, with_gc
Children:
b1848a0
Parents:
38736854 (diff), 797347f (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:
doc
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • doc/LaTeXmacros/common.tex

    r38736854 r6603c1d  
    1111%% Created On       : Sat Apr  9 10:06:17 2016
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Tue Aug  2 17:02:02 2016
    14 %% Update Count     : 228
     13%% Last Modified On : Sun Aug 14 08:27:29 2016
     14%% Update Count     : 231
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616
    … …  
    153153        {\abbrevFont{etc}.\xspace}%
    154154}%
     155\newcommand{\etal}{%
     156        \@ifnextchar{.}{\abbrevFont{et~al}}%
     157                {\abbrevFont{et al}.\xspace}%
     158}%
    155159\makeatother
    156160
    … …  
    251255literate={-}{\raisebox{-0.15ex}{\texttt{-}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1
    252256        {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 {_}{\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}}1 {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
    253         {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {...}{$\dots$}2,
     257        {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2,
    254258}%
    255259

  • doc/aaron_comp_II/comp_II.tex

    r38736854 r6603c1d  
    413413\subsection{Argument-Parameter Matching}
    414414The first axis for consideration is argument-parameter matching direction --- whether the type matching for a candidate function to a set of candidate arguments is directed by the argument types or the parameter types.
     415For programming languages without implicit conversions, argument-parameter matching is essentially the entirety of the expression resolution problem, and is generally referred to as ``overload resolution'' in the literature.
    415416All expression resolution algorithms form a DAG of interpretations, some explicitly, some implicitly; in this DAG, arcs point from function-call interpretations to argument interpretations, as below:
    416417\begin{figure}[h]
    … …  
    422423
    423424double *f(int*, int*); // $f_d$
    424 char *f(char*, char*); // $f_c$
     425char *f(char*, int*); // $f_c$
    425426
    426427f( f( p, p ), p );
    … …  
    463464Deciding when to switch between bottom-up and top-down resolution to minimize wasted work in a hybrid algorithm is a necessarily heuristic process, and though finding good heuristics for which subexpressions to swich matching strategies on is an open question, one reasonable approach might be to set a threshold $t$ for the number of candidate functions, and to use top-down resolution for any subexpression with fewer than $t$ candidate functions, to minimize the number of unmatchable argument interpretations computed, but to use bottom-up resolution for any subexpression with at least $t$ candidate functions, to reduce duplication in argument interpretation computation between the different candidate functions.
    464465
     466Ganzinger and Ripken~\cite{Ganzinger80} propose an approach (later refined by Pennello~\etal~\cite{Pennello80}) that uses a top-down filtering pass followed by a bottom-up filtering pass to reduce the number of candidate interpretations; they prove that for the Ada programming language a small number of such iterations is sufficient to converge to a solution for the expression resolution problem.
     467Persch~\etal~\cite{PW:overload} developed a similar two-pass approach where the bottom-up pass is followed by the top-down pass.
     468These algorithms differ from the hybrid approach under investigation in that they take multiple passes over the expression tree to yield a solution, and also in that they apply both filtering heuristics to all expression nodes; \CFA's polymorphic functions and implicit conversions make the approach of filtering out invalid types taken by all of these algorithms infeasible.
     469
    465470\subsubsection{Common Subexpression Caching}
    466471With any of these argument-parameter approaches, it may be a useful optimization to cache the resolution results for common subexpressions; in Figure~\ref{fig:res_dag} this optimization would result in the list of interpretations $[p_c, p_i]$ for ©p© only being calculated once, and re-used for each of the three instances of ©p©.
    467472
    468473\subsection{Implicit Conversion Application}
    469 Baker's and Cormack's algorithms do not account for implicit conversions\footnote{Baker does briefly comment on an approach for handling implicit conversions, but does not provide an implementable algorithm.}; both assume that there is at most one valid interpretation of a given expression for each distinct type.
    470 Integrating implicit conversion handling into their algorithms provides some choice of implementation approach.
     474With the exception of Bilson, the authors mentioned above do not account for implicit conversions in their algorithms\footnote{Baker does briefly comment on an approach for handling implicit conversions, but does not provide an implementable algorithm.}; all assume that there is at most one valid interpretation of a given expression for each distinct type.
     475Integrating implicit conversion handling into the presented argument-parameter matching algorithms thus provides some choice of implementation approach.
     476
     477Inference of polymorphic type variables can be considered a form of implicit conversion application, where monomorphic types are implicitly converted to instances of some polymorphic type\footnote{This ``conversion'' may not be implemented in any explicit way at runtime, but does need to be handled by the expression resolver as an inexact match between argument and parameter types.}.
     478This form of implicit conversion is particularly common in functional languages; Haskell's type classes~\cite{typeclass} are a particularly well-studied variant of this inference.
     479However, type classes arguably do not allow name overloading, as (at least in the Haskell implmentation) identifiers belonging to type classes may not be overloaded in any other context than an implementation of that type class; this provides a single (possibly polymorphic) interpretation of any identifier, simplifing the expression resolution problem relative to \CFA.
     480\CC~\cite{ANSI98:C++} includes both name overloading and implicit conversions in its expression resolution specification, though unlike \CFA it does complete type-checking on a generated monomorphization of template functions, where \CFA simply checks a list of type constraints.
     481The upcoming Concepts standard~\cite{C++concepts} defines a system of type constraints similar in principle to \CFA's.
     482Cormack and Wright~\cite{Cormack90} present an algorithm which integrates overload resolution with a polymorphic type inference approach very similar to \CFA's.
     483However, their algorithm does not account for implicit conversions other than polymorphic type binding and their discussion of their overload resolution algorithm is not sufficiently detailed to classify it with the other argument-parameter matching approaches\footnote{Their overload resolution algorithm is possibly a variant of Ganzinger and Ripken~\cite{Ganzinger80} or Pennello~\etal~\cite{Pennello80}, modified to allow for polymorphic type binding.}.
    471484
    472485\subsubsection{On Parameters}
    473 Bilson does account for implicit conversions in his algorithm, but it is unclear the approach is optimal.
     486Bilson does account for implicit conversions in his algorithm, but it is unclear if the approach is optimal.
    474487His algorithm integrates checking for valid implicit conversions into the argument-parameter-matching step, essentially trading more expensive matching for a smaller number of argument interpretations.
    475488This approach may result in the same subexpression being checked for a type match with the same type multiple times, though again memoization may mitigate this cost, and this approach does not generate implicit conversions that are not useful to match the containing function.
    … …  
    484497
    485498\subsection{Candidate Set Generation}
    486 Cormack, Baker and Bilson all generate the complete set of candidate argument interpretations before attempting to match the containing function call expression.
     499All the algorithms discussed to this point generate the complete set of candidate argument interpretations before attempting to match the containing function call expression.
    487500However, given that the top-level expression interpretation that is ultimately chosen is the minimal-cost valid interpretation, any consideration of non-minimal-cost interpretations is in some sense wasted work.
    488501Under the assumption that that programmers generally write function calls with relatively low-cost interpretations, a possible work-saving heuristic is to generate only the lowest-cost argument interpretations first, attempt to find a valid top-level interpretation using them, and only if that fails generate the next higher-cost argument interpretations.
    489502
    490503\subsubsection{Eager}
    491 Within the eager approach taken by Cormack, Baker and Bilson, there are still variants to explore.
     504Within the eager approach taken by the existing top-down and bottom-up algorithms, there are still variants to explore.
    492505Cormack and Baker do not account for implict conversions, and thus do not account for the possibility of multiple valid interpretations with distinct costs; Bilson, on the other hand, sorts the list of interpretations to aid in finding minimal-cost interpretations.
    493506Sorting the lists of argument or function call interpretations by cost at some point during resolution may provide useful opportunities to short-circuit expression evaluation when a minimal-cost interpretation is found, though it is unclear if this short-circuiting behaviour justifies the cost of the sort.
    … …  
    559572
    560573This proposed project should provide valuable data on how to implement a performant compiler for modern programming languages such as \CFA with powerful static type-systems, specifically targeting the feature interaction between name overloading and implicit conversions.
    561 This work is not limited in applicability to \CFA, but may also be useful for supporting efficient compilation of the upcoming ``Concepts'' standard~\cite{C++concepts} for \CC template constraints, for instance.
     574This work is not limited in applicability to \CFA, but may also be useful for supporting efficient compilation of the upcoming Concepts standard~\cite{C++concepts} for \CC template constraints, for instance.
    562575
    563576\appendix

  • doc/bibliography/cfa.bib

    r38736854 r6603c1d  
    46854685}
    46864686
     4687@article{Ganzinger80,
     4688        contributer = {a3moss@uwaterloo.ca},
     4689        author = {Ganzinger, Harald and Ripken, Knut},
     4690        title = {Operator Identification in {ADA}: Formal Specification, Complexity, and Concrete Implementation},
     4691        journal = {SIGPLAN Notices},
     4692        issue_date = {February 1980},
     4693        volume = {15},
     4694        number = {2},
     4695        month = feb,
     4696        year = {1980},
     4697        issn = {0362-1340},
     4698        pages = {30--42},
     4699        numpages = {13},
     4700        url = {http://doi.acm.org/10.1145/947586.947589},
     4701        doi = {10.1145/947586.947589},
     4702        publisher = {ACM},
     4703        address = {New York, NY, USA}
     4704}
     4705
    46874706@article{Ford82,
    46884707    keywords    = {},
    … …  
    58515870}
    58525871
     5872@article{Pennello80,
     5873        contributer = {a3moss@uwaterloo.ca},
     5874        author = {Pennello, Tom and DeRemer, Frank and Meyers, Richard},
     5875        title = {A Simplified Operator Identification Scheme for {Ada}},
     5876        journal = {SIGPLAN Notices},
     5877        issue_date = {July-August 1980},
     5878        volume = {15},
     5879        number = {7 and 8},
     5880        month = jul,
     5881        year = {1980},
     5882        issn = {0362-1340},
     5883        pages = {82--87},
     5884        numpages = {6},
     5885        url = {http://doi.acm.org/10.1145/947680.947688},
     5886        doi = {10.1145/947680.947688},
     5887        publisher = {ACM},
     5888        address = {New York, NY, USA},
     5889}
     5890
    58535891@inproceedings{Dice10,
    58545892    keywords    = {hardware, synchronization, transactional memory},

  • doc/user/user.tex

    r38736854 r6603c1d  
    1111%% Created On       : Wed Apr  6 14:53:29 2016
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Tue Aug  2 17:39:02 2016
    14 %% Update Count     : 1286
     13%% Last Modified On : Sun Aug 14 08:23:06 2016
     14%% Update Count     : 1323
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616
    … …  
    317317
    318318\item
    319 \Indexc{-no-include-std}\index{compilation option!-no-include-std@©-no-include-std©}
     319\Indexc{-no-include-stdhdr}\index{compilation option!-no-include-stdhdr@©-no-include-stdhdr©}
    320320Do not supply ©extern "C"© wrappers for \Celeven standard include files (see~\VRef{s:StandardHeaders}).
    321321\textbf{This option is \emph{not} the default.}
    … …  
    807807
    808808
     809\section{Backquote Identifiers}
     810\label{s:BackquoteIdentifiers}
     811
     812\CFA accommodates keyword clashes by syntactic transformations using the \CFA backquote escape-mechanism:
     813\begin{lstlisting}
     814int `otype` = 3;                                // make keyword an identifier
     815double `choose` = 3.5;
     816\end{lstlisting}
     817Programs can be converted easily by enclosing keyword identifiers in backquotes, and the backquotes can be removed later when the identifier name is changed to an non-keyword name.
     818Clashes in C header files (see~\VRef{s:StandardHeaders}) can be handled automatically using the preprocessor, ©#include_next© and ©-I filename©:
     819\begin{lstlisting}
     820// include file uses the CFA keyword "otype".
     821#if ! defined( otype )                  // nesting ?
     822#define otype `otype`
     823#define __CFA_BFD_H__
     824#endif // ! otype
     825
     826#include_next <bfd.h>                   // must have internal check for multiple expansion
     827
     828#if defined( otype ) && defined( __CFA_BFD_H__ )        // reset only if set
     829#undef otype
     830#undef __CFA_BFD_H__
     831#endif // otype && __CFA_BFD_H__
     832\end{lstlisting}
     833
     834
    809835\section{Type Operators}
    810836
    … …  
    10111037Alternatively, prototype definitions can be eliminated by using a two-pass compilation, and implicitly creating header files for exports.
    10121038The former is easy to do, while the latter is more complex.
    1013 Currently, \CFA does \emph{not} attempt to support named arguments.
     1039
     1040Furthermore, named arguments do not work well in a \CFA-style programming-languages because they potentially introduces a new criteria for type matching.
     1041For example, it is technically possible to disambiguate between these two overloaded definitions of ©f© based on named arguments at the call site:
     1042\begin{lstlisting}
     1043int f( int i, int j );
     1044int f( int x, double y );
     1045
     1046f( j : 3, i : 4 );                              §\C{// 1st f}§
     1047f( x : 7, y : 8.1 );                    §\C{// 2nd f}§
     1048f( 4, 5 );                                              §\C{// ambiguous call}§
     1049\end{lstlisting}
     1050However, named arguments compound routine resolution in conjunction with conversions:
     1051\begin{lstlisting}
     1052f( i : 3, 5.7 );                                §\C{// ambiguous call ?}§
     1053\end{lstlisting}
     1054Depending on the cost associated with named arguments, this call could be resolvable or ambiguous.
     1055Adding named argument into the routine resolution algorithm does not seem worth the complexity.
     1056Therefore, \CFA does \emph{not} attempt to support named arguments.
    10141057
    10151058\item[Default Arguments]
    … …  
    10211064the allowable positional calls are:
    10221065\begin{lstlisting}
    1023 p();                            §\C{// rewrite $\Rightarrow$ p( 1, 2, 3 )}§
    1024 p( 4 );                         §\C{// rewrite $\Rightarrow$ p( 4, 2, 3 )}§
    1025 p( 4, 4 );                      §\C{// rewrite $\Rightarrow$ p( 4, 4, 3 )}§
    1026 p( 4, 4, 4 );           §\C{// rewrite $\Rightarrow$ p( 4, 4, 4 )}§
     1066p();                                                    §\C{// rewrite $\Rightarrow$ p( 1, 2, 3 )}§
     1067p( 4 );                                                 §\C{// rewrite $\Rightarrow$ p( 4, 2, 3 )}§
     1068p( 4, 4 );                                              §\C{// rewrite $\Rightarrow$ p( 4, 4, 3 )}§
     1069p( 4, 4, 4 );                                   §\C{// rewrite $\Rightarrow$ p( 4, 4, 4 )}§
    10271070// empty arguments
    1028 p(  , 4, 4 );           §\C{// rewrite $\Rightarrow$ p( 1, 4, 4 )}§
    1029 p( 4,  , 4 );           §\C{// rewrite $\Rightarrow$ p( 4, 2, 4 )}§
    1030 p( 4, 4,   );           §\C{// rewrite $\Rightarrow$ p( 4, 4, 3 )}§
    1031 p( 4,  ,   );           §\C{// rewrite $\Rightarrow$ p( 4, 2, 3 )}§
    1032 p(  , 4,   );           §\C{// rewrite $\Rightarrow$ p( 1, 4, 3 )}§
    1033 p(  ,  , 4 );           §\C{// rewrite $\Rightarrow$ p( 1, 2, 4 )}§
    1034 p(  ,  ,   );           §\C{// rewrite $\Rightarrow$ p( 1, 2, 3 )}§
     1071p(  , 4, 4 );                                   §\C{// rewrite $\Rightarrow$ p( 1, 4, 4 )}§
     1072p( 4,  , 4 );                                   §\C{// rewrite $\Rightarrow$ p( 4, 2, 4 )}§
     1073p( 4, 4,   );                                   §\C{// rewrite $\Rightarrow$ p( 4, 4, 3 )}§
     1074p( 4,  ,   );                                   §\C{// rewrite $\Rightarrow$ p( 4, 2, 3 )}§
     1075p(  , 4,   );                                   §\C{// rewrite $\Rightarrow$ p( 1, 4, 3 )}§
     1076p(  ,  , 4 );                                   §\C{// rewrite $\Rightarrow$ p( 1, 2, 4 )}§
     1077p(  ,  ,   );                                   §\C{// rewrite $\Rightarrow$ p( 1, 2, 3 )}§
    10351078\end{lstlisting}
    10361079Here the missing arguments are inserted from the default values in the parameter list.
    … …  
    10671110The conflict occurs because both named and ellipse arguments must appear after positional arguments, giving two possibilities:
    10681111\begin{lstlisting}
    1069 p( /* positional */, . . ., /* named */ );
    1070 p( /* positional */, /* named */, . . . );
     1112p( /* positional */, ... , /* named */ );
     1113p( /* positional */, /* named */, ... );
    10711114\end{lstlisting}
    10721115While it is possible to implement both approaches, the first possibly is more complex than the second, \eg:
    10731116\begin{lstlisting}
    1074 p( int x, int y, int z, . . . );
    1075 p( 1, 4, 5, 6, z : 3, y : 2 ); §\C{// assume p( /* positional */, . . ., /* named */ );}§
    1076 p( 1, z : 3, y : 2, 4, 5, 6 ); §\C{// assume p( /* positional */, /* named */, . . . );}§
     1117p( int x, int y, int z, ... );
     1118p( 1, 4, 5, 6, z : 3, y : 2 ); §\C{// assume p( /* positional */, ... , /* named */ );}§
     1119p( 1, z : 3, y : 2, 4, 5, 6 ); §\C{// assume p( /* positional */, /* named */, ... );}§
    10771120\end{lstlisting}
    10781121In the first call, it is necessary for the programmer to conceptually rewrite the call, changing named arguments into positional, before knowing where the ellipse arguments begin.
    … …  
    10821125The problem is exacerbated with default arguments, \eg:
    10831126\begin{lstlisting}
    1084 void p( int x, int y = 2, int z = 3. . . );
    1085 p( 1, 4, 5, 6, z : 3 );         §\C{// assume p( /* positional */, . . ., /* named */ );}§
    1086 p( 1, z : 3, 4, 5, 6 );         §\C{// assume p( /* positional */, /* named */, . . . );}§
     1127void p( int x, int y = 2, int z = 3... );
     1128p( 1, 4, 5, 6, z : 3 );         §\C{// assume p( /* positional */, ... , /* named */ );}§
     1129p( 1, z : 3, 4, 5, 6 );         §\C{// assume p( /* positional */, /* named */, ... );}§
    10871130\end{lstlisting}
    10881131The first call is an error because arguments 4 and 5 are actually positional not ellipse arguments;
    … …  
    11291172\subsection{Type Nesting}
    11301173
    1131 \CFA allows \Index{type nesting}, and type qualification of the nested types (see \VRef[Figure]{f:TypeNestingQualification}), where as C hoists\index{type hoisting} (refactors) nested types into the enclosing scope and has no type qualification.
     1174\CFA allows \Index{type nesting}, and type qualification of the nested typres (see \VRef[Figure]{f:TypeNestingQualification}), where as C hoists\index{type hoisting} (refactors) nested types into the enclosing scope and has no type qualification.
    11321175\begin{figure}
     1176\centering
    11331177\begin{tabular}{@{}l@{\hspace{3em}}l|l@{}}
    11341178\multicolumn{1}{c@{\hspace{3em}}}{\textbf{C Type Nesting}}      & \multicolumn{1}{c}{\textbf{C Implicit Hoisting}}      & \multicolumn{1}{|c}{\textbf{\CFA}}    \\
    … …  
    13971441Mass assignment has the following form:
    13981442\begin{lstlisting}
    1399 [ §\emph{lvalue}§, ..., §\emph{lvalue}§ ] = §\emph{expr}§;
     1443[ §\emph{lvalue}§, ... , §\emph{lvalue}§ ] = §\emph{expr}§;
    14001444\end{lstlisting}
    14011445\index{lvalue}
    … …  
    14371481Multiple assignment has the following form:
    14381482\begin{lstlisting}
    1439 [ §\emph{lvalue}§, . . ., §\emph{lvalue}§ ] = [ §\emph{expr}§, . . ., §\emph{expr}§ ];
     1483[ §\emph{lvalue}§, ... , §\emph{lvalue}§ ] = [ §\emph{expr}§, ... , §\emph{expr}§ ];
    14401484\end{lstlisting}
    14411485\index{lvalue}
    … …  
    18731917\begin{lstlisting}
    18741918switch ( i ) {
    1875   ®case 1, 3, 5®:
     1919  case ®1, 3, 5®:
    18761920        ...
    1877   ®case 2, 4, 6®:
     1921  case ®2, 4, 6®:
    18781922        ...
    18791923}
    … …  
    19061950\begin{lstlisting}
    19071951switch ( i ) {
    1908   ®case 1~5:®
     1952  case ®1~5:®
    19091953        ...
    1910   ®case 10~15:®
     1954  case ®10~15:®
    19111955        ...
    19121956}
    … …  
    19151959\begin{lstlisting}
    19161960switch ( i )
    1917   case 1 ... 5:
     1961  case ®1 ... 5®:
    19181962        ...
    1919   case 10 ... 15:
     1963  case ®10 ... 15®:
    19201964        ...
    19211965}
    … …  
    43694413
    43704414
     4415\section{Incompatible}
     4416
     4417The following incompatibles exist between \CFA and C, and are similar to Annex C for \CC~\cite{ANSI14:C++}.
     4418
     4419\begin{enumerate}
     4420\item
     4421\begin{description}
     4422\item[Change:] add new keywords \\
     4423New keywords are added to \CFA (see~\VRef{s:NewKeywords}).
     4424\item[Rationale:] keywords added to implement new semantics of \CFA.
     4425\item[Effect on original feature:] change to semantics of well-defined feature. \\
     4426Any ISO C programs using these keywords as identifiers are invalid \CFA programs.
     4427\item[Difficulty of converting:] keyword clashes are accommodated by syntactic transformations using the \CFA backquote escape-mechanism (see~\VRef{s:BackquoteIdentifiers}):
     4428\item[How widely used:] clashes among new \CFA keywords and existing identifiers are rare.
     4429\end{description}
     4430
     4431\item
     4432\begin{description}
     4433\item[Change:] type of character literal ©int© to ©char© to allow more intuitive overloading:
     4434\begin{lstlisting}
     4435int rtn( int i );
     4436int rtn( char c );
     4437rtn( 'x' );                                             §\C{// programmer expects 2nd rtn to be called}§
     4438\end{lstlisting}
     4439\item[Rationale:] it is more intuitive for the call to ©rtn© to match the second version of definition of ©rtn© rather than the first.
     4440In particular, output of ©char© variable now print a character rather than the decimal ASCII value of the character.
     4441\begin{lstlisting}
     4442sout | 'x' | " " | (int)'x' | endl;
     4443x 120
     4444\end{lstlisting}
     4445Having to cast ©'x'© to ©char© is non-intuitive.
     4446\item[Effect on original feature:] change to semantics of well-defined feature that depend on:
     4447\begin{lstlisting}
     4448sizeof( 'x' ) == sizeof( int )
     4449\end{lstlisting}
     4450no long work the same in \CFA programs.
     4451\item[Difficulty of converting:] simple
     4452\item[How widely used:] programs that depend upon ©sizeof( 'x' )© are rare and can be changed to ©sizeof(char)©.
     4453\end{description}
     4454
     4455\item
     4456\begin{description}
     4457\item[Change:] make string literals ©const©:
     4458\begin{lstlisting}
     4459char * p = "abc";                               §\C{// valid in C, deprecated in \CFA}§
     4460char * q = expr ? "abc" : "de"; §\C{// valid in C, invalid in \CFA}§
     4461\end{lstlisting}
     4462The type of a string literal is changed from ©[] char© to ©const [] char©.
     4463Similarly, the type of a wide string literal is changed from ©[] wchar_t© to ©const [] wchar_t©.
     4464\item[Rationale:] This change is a safety issue:
     4465\begin{lstlisting}
     4466char * p = "abc";
     4467p[0] = 'w';                                             §\C{// segment fault or change constant literal}§
     4468\end{lstlisting}
     4469The same problem occurs when passing a string literal to a routine that changes its argument.
     4470\item[Effect on original feature:] change to semantics of well-defined feature.
     4471\item[Difficulty of converting:] simple syntactic transformation, because string literals can be converted to ©char *©.
     4472\item[How widely used:] programs that have a legitimate reason to treat string literals as pointers to potentially modifiable memory are rare.
     4473\end{description}
     4474
     4475\item
     4476\begin{description}
     4477\item[Change:] remove \newterm{tentative definitions}, which only occurs at file scope:
     4478\begin{lstlisting}
     4479int i;                                                  §\C{// forward definition}§
     4480int *j = ®&i®;                                  §\C{// forward reference, valid in C, invalid in \CFA}§
     4481int i = 0;                                              §\C{// definition}§
     4482\end{lstlisting}
     4483is valid in C, and invalid in \CFA because duplicate overloaded object definitions at the same scope level are disallowed.
     4484This change makes it impossible to define mutually referential file-local static objects, if initializers are restricted to the syntactic forms of C. For example,
     4485\begin{lstlisting}
     4486struct X { int i; struct X *next; };
     4487static struct X a;                              §\C{// forward definition}§
     4488static struct X b = { 0, ®&a® };        §\C{// forward reference, valid in C, invalid in \CFA}§
     4489static struct X a = { 1, &b };  §\C{// definition}§
     4490\end{lstlisting}
     4491\item[Rationale:] avoids having different initialization rules for builtin types and userdefined types.
     4492\item[Effect on original feature:] change to semantics of well-defined feature.
     4493\item[Difficulty of converting:] the initializer for one of a set of mutually-referential file-local static objects must invoke a routine call to achieve the initialization.
     4494\item[How widely used:] seldom
     4495\end{description}
     4496
     4497\item
     4498\begin{description}
     4499\item[Change:] have ©struct© introduce a scope for nested types:
     4500\begin{lstlisting}
     4501enum ®Colour® { R, G, B, Y, C, M };
     4502struct Person {
     4503        enum ®Colour® { R, G, B };      §\C{// nested type}§
     4504        struct Face {                           §\C{// nested type}§
     4505                ®Colour® Eyes, Hair;    §\C{// type defined outside (1 level)}§
     4506        };
     4507        ß.ß®Colour® shirt;                      §\C{// type defined outside (top level)}§
     4508        ®Colour® pants;                         §\C{// type defined same level}§
     4509        Face looks[10];                         §\C{// type defined same level}§
     4510};
     4511®Colour® c = R;                                 §\C{// type/enum defined same level}§
     4512Personß.ß®Colour® pc = Personß.ßR;      §\C{// type/enum defined inside}§
     4513Personß.ßFace pretty;                   §\C{// type defined inside}§
     4514\end{lstlisting}
     4515In C, the name of the nested types belongs to the same scope as the name of the outermost enclosing structure, i.e., the nested types are hoisted to the scope of the outer-most type, which is not useful and confusing.
     4516\CFA is C \emph{incompatible} on this issue, and provides semantics similar to \Index*[C++]{\CC}.
     4517Nested types are not hoisted and can be referenced using the field selection operator ``©.©'', unlike the \CC scope-resolution operator ``©::©''.
     4518\item[Rationale:] ©struct© scope is crucial to \CFA as an information structuring and hiding mechanism.
     4519\item[Effect on original feature:] change to semantics of well-defined feature.
     4520\item[Difficulty of converting:] Semantic transformation.
     4521\item[How widely used:] C programs rarely have nest types because they are equivalent to the hoisted version.
     4522\end{description}
     4523
     4524\item
     4525\begin{description}
     4526\item[Change:] In C++, the name of a nested class is local to its enclosing class.
     4527\item[Rationale:] C++ classes have member functions which require that classes establish scopes.
     4528\item[Difficulty of converting:] Semantic transformation. To make the struct type name visible in the scope of the enclosing struct, the struct tag could be declared in the scope of the enclosing struct, before the enclosing struct is defined. Example:
     4529\begin{lstlisting}
     4530struct Y;                                               §\C{// struct Y and struct X are at the same scope}§
     4531struct X {
     4532struct Y { /* ... */ } y;
     4533};
     4534\end{lstlisting}
     4535All the definitions of C struct types enclosed in other struct definitions and accessed outside the scope of the enclosing struct could be exported to the scope of the enclosing struct.
     4536Note: this is a consequence of the difference in scope rules, which is documented in 3.3.
     4537\item[How widely used:] Seldom.
     4538\end{description}
     4539
     4540\item
     4541\begin{description}
     4542\item[Change:] comma expression is disallowed as subscript
     4543\item[Rationale:] safety issue to prevent subscripting error for multidimensional arrays: ©x[i,j]© instead of ©x[i][j]©, and this syntactic form then taken by \CFA for new style arrays.
     4544\item[Effect on original feature:] change to semantics of well-defined feature.
     4545\item[Difficulty of converting:] semantic transformation of ©x[i,j]© to ©x[(i,j)]©
     4546\item[How widely used:] seldom.
     4547\end{description}
     4548\end{enumerate}
     4549
     4550
    43714551\section{New Keywords}
    43724552\label{s:NewKeywords}
    43734553
    43744554\begin{quote2}
    4375 \begin{tabular}{ll}
    4376 ©catch©                 & ©lvalue©              \\
    4377 ©catchResume©   &                               \\
    4378 ©choose©                & ©otype©               \\
    4379                                 &                               \\
    4380 ©disable©               & ©throw©               \\
    4381 ©dtype©                 & ©throwResume© \\
    4382                                 & ©trait©               \\
    4383 ©enable©                & ©try©                 \\
    4384                                 &                               \\
    4385 ©fallthrough©                                   \\
    4386 ©fallthru©                                              \\
    4387 ©finally©                                               \\
    4388 ©forall©                                                \\
    4389 ©ftype©                                                 \\
     4555\begin{tabular}{lll}
     4556©catch©                 & ©fallthrough© & ©otype©               \\
     4557©catchResume©   & ©fallthru©    & ©throw©               \\
     4558©choose©                & ©finally©             & ©throwResume© \\
     4559©disable©               & ©forall©              & ©trait©               \\
     4560©dtype©                 & ©ftype©               & ©try©                 \\
     4561©enable©                & ©lvalue©              &                               \\
    43904562\end{tabular}
    43914563\end{quote2}
    … …  
    43954567\label{s:StandardHeaders}
    43964568
    4397 C prescribes the following standard header-files:
     4569C prescribes the following standard header-files~\cite[\S~7.1.2]{C11}:
    43984570\begin{quote2}
    43994571\begin{minipage}{\linewidth}
    … …  
    44124584\end{minipage}
    44134585\end{quote2}
    4414 For the prescribed head-files, \CFA implicit wraps their includes in an ©extern "C"©;
     4586For the prescribed head-files, \CFA implicitly wraps their includes in an ©extern "C"©;
    44154587hence, names in these include files are not mangled\index{mangling!name} (see~\VRef{s:Interoperability}).
    44164588All other C header files must be explicitly wrapped in ©extern "C"© to prevent name mangling.
    4417 
    4418 
    4419 \section{Incompatible}
    4420 
    4421 The following incompatibles exist between \CFA and C, and are similar to Annex C for \CC~\cite{ANSI14:C++}.
    4422 
    4423 \begin{enumerate}
    4424 \item
    4425 \begin{description}
    4426 \item[Change:] add new keywords (see~\VRef{s:NewKeywords}) \\
    4427 New keywords are added to \CFA.
    4428 \item[Rationale:] keywords added to implement new semantics of \CFA.
    4429 \item[Effect on original feature:] change to semantics of well-defined feature. \\
    4430 Any ISO C programs using these keywords as identifiers are invalid \CFA programs.
    4431 \item[Difficulty of converting:] keyword clashes are accommodated by syntactic transformations using the \CFA backquote escape-mechanism:
    4432 \begin{lstlisting}
    4433 int `otype` = 3;                                // make keyword an identifier
    4434 double `choose` = 3.5;
    4435 \end{lstlisting}
    4436 Programs can be converted automatically by enclosing keyword identifiers in backquotes, and the backquotes can be remove later when the identifier name is changed.
    4437 Clashes in C system libraries (include files) can be handled automatically using preprocessor, ©#include_next© and ©-Ifilename©:
    4438 \begin{lstlisting}
    4439 // include file uses the CFA keyword "otype".
    4440 #if ! defined( otype )                  // nesting ?
    4441 #define otype `otype`
    4442 #define __CFA_BFD_H__
    4443 #endif // ! otype
    4444 
    4445 #include_next <bfd.h>                   // must have internal check for multiple expansion
    4446 
    4447 #if defined( otype ) && defined( __CFA_BFD_H__ )        // reset only if set
    4448 #undef otype
    4449 #undef __CFA_BFD_H__
    4450 #endif // otype && __CFA_BFD_H__
    4451 \end{lstlisting}
    4452 \item[How widely used:] clashes among new \CFA keywords and existing identifiers are rare.
    4453 \end{description}
    4454 
    4455 \item
    4456 \begin{description}
    4457 \item[Change:] type of character literal ©int© to ©char© to allow more intuitive overloading:
    4458 \begin{lstlisting}
    4459 int rtn( int i );
    4460 int rtn( char c );
    4461 rtn( 'x' );                                             // programmer expects 2nd rtn to be called
    4462 \end{lstlisting}
    4463 \item[Rationale:] it is more intuitive for the call to ©rtn© to match the second version of definition of ©rtn© rather than the first.
    4464 In particular, output of ©char© variable now print a character rather than the decimal ASCII value of the character.
    4465 \begin{lstlisting}
    4466 sout | 'x' | " " | (int)'x' | endl;
    4467 x 120
    4468 \end{lstlisting}
    4469 Having to cast ©'x'© to ©char© is non-intuitive.
    4470 \item[Effect on original feature:] change to semantics of well-defined feature that depend on:
    4471 \begin{lstlisting}
    4472 sizeof( 'x' ) == sizeof( int )
    4473 \end{lstlisting}
    4474 no long work the same in \CFA programs.
    4475 \item[Difficulty of converting:] simple
    4476 \item[How widely used:] programs that depend upon ©sizeof( 'x' )© are rare and can be changed to ©sizeof(char)©.
    4477 \end{description}
    4478 
    4479 \item
    4480 \begin{description}
    4481 \item[Change:] make string literals ©const©:
    4482 \begin{lstlisting}
    4483 char * p = "abc";                               // valid in C, deprecated in §\CFA§
    4484 char * q = expr ? "abc" : "de"; // valid in C, invalid in §\CFA§
    4485 \end{lstlisting}
    4486 The type of a string literal is changed from ©[] char© to ©const [] char©.
    4487 Similarly, the type of a wide string literal is changed from ©[] wchar_t© to ©const [] wchar_t©.
    4488 \item[Rationale:] This change is a safety issue:
    4489 \begin{lstlisting}
    4490 char * p = "abc";
    4491 p[0] = 'w';                                             // segment fault or change constant literal
    4492 \end{lstlisting}
    4493 The same problem occurs when passing a string literal to a routine that changes its argument.
    4494 \item[Effect on original feature:] change to semantics of well-defined feature.
    4495 \item[Difficulty of converting:] simple syntactic transformation, because string literals can be converted to ©char *©.
    4496 \item[How widely used:] programs that have a legitimate reason to treat string literals as pointers to potentially modifiable memory are rare.
    4497 \end{description}
    4498 
    4499 \item
    4500 \begin{description}
    4501 \item[Change:] remove \newterm{tentative definitions}, which only occurs at file scope:
    4502 \begin{lstlisting}
    4503 int i;                                                  // forward definition
    4504 int *j = ®&i®;                                  // forward reference, valid in C, invalid in §\CFA§
    4505 int i = 0;                                              // definition
    4506 \end{lstlisting}
    4507 is valid in C, and invalid in \CFA because duplicate overloaded object definitions at the same scope level are disallowed.
    4508 This change makes it impossible to define mutually referential file-local static objects, if initializers are restricted to the syntactic forms of C. For example,
    4509 \begin{lstlisting}
    4510 struct X { int i; struct X *next; };
    4511 static struct X a;                              // forward definition
    4512 static struct X b = { 0, ®&a® };        // forward reference, valid in C, invalid in §\CFA§
    4513 static struct X a = { 1, &b };  // definition
    4514 \end{lstlisting}
    4515 \item[Rationale:] avoids having different initialization rules for builtin types and userdefined types.
    4516 \item[Effect on original feature:] change to semantics of well-defined feature.
    4517 \item[Difficulty of converting:] the initializer for one of a set of mutually-referential file-local static objects must invoke a routine call to achieve the initialization.
    4518 \item[How widely used:] seldom
    4519 \end{description}
    4520 
    4521 \item
    4522 \begin{description}
    4523 \item[Change:] have ©struct© introduce a scope for nested types
    4524 In C, the name of the nested types belongs to the same scope as the name of the outermost enclosing
    4525 Example:
    4526 \begin{lstlisting}
    4527 enum ®Colour® { R, G, B, Y, C, M };
    4528 struct Person {
    4529         enum ®Colour® { R, G, B };      // nested type
    4530         struct Face {                           // nested type
    4531                 ®Colour® Eyes, Hair;            // type defined outside (1 level)
    4532         };
    4533         ß.ß®Colour® shirt;                              // type defined outside (top level)
    4534         ®Colour® pants;                         // type defined same level
    4535         Face looks[10];                         // type defined same level
    4536 };
    4537 ®Colour® c = R;                                 // type/enum defined same level
    4538 Personß.ß®Colour® pc = Personß.ßR;      // type/enum defined inside
    4539 Personß.ßFace pretty;                           // type defined inside
    4540 \end{lstlisting}
    4541 \item[Rationale:] ©struct© scope is crucial to \CFA as an information structuring and hiding mechanism.
    4542 \item[Effect on original feature:] change to semantics of well-defined feature.
    4543 \item[Difficulty of converting:] Semantic transformation.
    4544 \item[How widely used:] C programs rarely have nest types because they are equivalent to the hoisted version.
    4545 
    4546 \CFA is C \emph{incompatible} on this issue, and provides semantics similar to \Index*[C++]{\CC}.
    4547 Nested types are not hoisted and can be referenced using the field selection operator ``©.©'', unlike the \CC scope-resolution operator ``©::©''.
    4548 Given that nested types in C are equivalent to not using them, \ie they are essentially useless, it is unlikely there are any realistic usages that break because of this incompatibility.
    4549 \end{description}
    4550 
    4551 \item
    4552 \begin{description}
    4553 \item[Change:] In C++, the name of a nested class is local to its enclosing class.
    4554 \item[Rationale:] C++ classes have member functions which require that classes establish scopes.
    4555 \item[Difficulty of converting:] Semantic transformation. To make the struct type name visible in the scope of the enclosing struct, the struct tag could be declared in the scope of the enclosing struct, before the enclosing struct is defined. Example:
    4556 \begin{lstlisting}
    4557 struct Y; // struct Y and struct X are at the same scope
    4558 struct X {
    4559 struct Y { /* ... */ } y;
    4560 };
    4561 \end{lstlisting}
    4562 All the definitions of C struct types enclosed in other struct definitions and accessed outside the scope of the enclosing struct could be exported to the scope of the enclosing struct.
    4563 Note: this is a consequence of the difference in scope rules, which is documented in 3.3.
    4564 \item[How widely used:] Seldom.
    4565 \end{description}
    4566 
    4567 \item
    4568 \begin{description}
    4569 \item[Change:] comma expression is disallowed as subscript
    4570 \item[Rationale:] safety issue to prevent subscripting error for multidimensional arrays: ©x[i,j]© instead of ©x[i][j]©, and this syntactic form then taken by \CFA for new style arrays.
    4571 \item[Effect on original feature:] change to semantics of well-defined feature.
    4572 \item[Difficulty of converting:] semantic transformation of ©x[i,j]© to ©x[(i,j)]©
    4573 \item[How widely used:] seldom.
    4574 \end{description}
    4575 \end{enumerate}
    45764589
    45774590
    … …  
    47494762\subsection{malloc}
    47504763
     4764\leavevmode
    47514765\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    47524766forall( otype T ) T * malloc( void );§\indexc{malloc}§
    … …  
    47654779forall( otype T ) T * memset( T * ptr );                                // remove when default value available
    47664780\end{lstlisting}
    4767 \
     4781
    47684782
    47694783\subsection{ato / strto}
    47704784
     4785\leavevmode
    47714786\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    47724787int ato( const char * ptr );§\indexc{ato}§
    … …  
    47964811long double _Complex strto( const char * sptr, char ** eptr );
    47974812\end{lstlisting}
    4798 \
    47994813
    48004814
    48014815\subsection{bsearch / qsort}
    48024816
     4817\leavevmode
    48034818\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    48044819forall( otype T | { int ?<?( T, T ); } )
    … …  
    48084823void qsort( const T * arr, size_t dimension );§\indexc{qsort}§
    48094824\end{lstlisting}
    4810 \
    48114825
    48124826
    48134827\subsection{abs}
    48144828
     4829\leavevmode
    48154830\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    48164831char abs( char );§\indexc{abs}§
    … …  
    48254840long double abs( long double _Complex );
    48264841\end{lstlisting}
    4827 \
    48284842
    48294843
    48304844\subsection{random}
    48314845
     4846\leavevmode
    48324847\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    48334848void rand48seed( long int s );§\indexc{rand48seed}§
    … …  
    48434858long double _Complex rand48();
    48444859\end{lstlisting}
    4845 \
    48464860
    48474861
    48484862\subsection{min / max / clamp / swap}
    48494863
     4864\leavevmode
    48504865\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    48514866forall( otype T | { int ?<?( T, T ); } )
    … …  
    48614876void swap( T * t1, T * t2 );§\indexc{swap}§
    48624877\end{lstlisting}
    4863 \
    48644878
    48654879
    … …  
    48724886\subsection{General}
    48734887
     4888\leavevmode
    48744889\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    48754890float fabs( float );§\indexc{fabs}§
    … …  
    49174932long double nan( const char * );
    49184933\end{lstlisting}
    4919 \
    49204934
    49214935
    49224936\subsection{Exponential}
    49234937
     4938\leavevmode
    49244939\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    49254940float exp( float );§\indexc{exp}§
    … …  
    49744989long double logb( long double );
    49754990\end{lstlisting}
    4976 \
    49774991
    49784992
    49794993\subsection{Power}
    49804994
     4995\leavevmode
    49814996\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    49824997float sqrt( float );§\indexc{sqrt}§
    … …  
    50025017long double _Complex pow( long double _Complex, long double _Complex );
    50035018\end{lstlisting}
    5004 \
    50055019
    50065020
    50075021\subsection{Trigonometric}
    50085022
     5023\leavevmode
    50095024\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    50105025float sin( float );§\indexc{sin}§
    … …  
    50585073long double atan( long double, long double );
    50595074\end{lstlisting}
    5060 \
    50615075
    50625076
    50635077\subsection{Hyperbolic}
    50645078
     5079\leavevmode
    50655080\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    50665081float sinh( float );§\indexc{sinh}§
    … …  
    51065121long double _Complex atanh( long double _Complex );
    51075122\end{lstlisting}
    5108 \
    51095123
    51105124
    51115125\subsection{Error / Gamma}
    51125126
     5127\leavevmode
    51135128\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    51145129float erf( float );§\indexc{erf}§
    … …  
    51375152long double tgamma( long double );
    51385153\end{lstlisting}
    5139 \
    51405154
    51415155
    51425156\subsection{Nearest Integer}
    51435157
     5158\leavevmode
    51445159\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    51455160float floor( float );§\indexc{floor}§
    … …  
    51915206long long int llround( long double );
    51925207\end{lstlisting}
    5193 \
    51945208
    51955209
    51965210\subsection{Manipulation}
    51975211
     5212\leavevmode
    51985213\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    51995214float copysign( float, float );§\indexc{copysign}§
    … …  
    52325247long double scalbln( long double, long int );
    52335248\end{lstlisting}
    5234 \
    52355249
    52365250
Note: See TracChangeset for help on using the changeset viewer.