Changeset cab8cac


Ignore:
Timestamp:
Apr 18, 2017, 12:52:51 PM (8 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
de4ce0e, f7b0d71
Parents:
d87ade9 (diff), 3bdd6f5 (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:
3 edited

Legend:

Unmodified
Added
Removed
  • doc/bibliography/cfa.bib

    rd87ade9 rcab8cac  
    36503650    contributer = {pabuhr@plg},
    36513651    author      = {James Gosling and Bill Joy and Guy Steele and Gilad Bracha and Alex Buckley},
    3652     title       = {{Java} Language Specification},
     3652    title       = {{Java} Language Spec.},
    36533653    organization= {Oracle},
    36543654    publisher   = {Oracle},
  • doc/generic_types/evaluation/timing.gp

    rd87ade9 rcab8cac  
    11# set terminal pdfcairo linewidth 3 size 6,3
    22# set output "timing.pdf"
    3 set terminal pslatex size 6.25,2.25 color solid
     3set terminal pslatex size 6.25,2.125 color solid
    44set output "timing.tex"
    55
  • doc/generic_types/generic_types.tex

    rd87ade9 rcab8cac  
    99
    1010\makeatletter
     11% Default underscore is too low and wide. Cannot use lstlisting "literate" as replacing underscore
     12% removes it as a variable-name character so keyworks in variables are highlighted
     13\DeclareTextCommandDefault{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}}
     14
    1115% parindent is relative, i.e., toggled on/off in environments like itemize, so store the value for
    1216% use rather than use \parident directly.
     
    1418\setlength{\parindentlnth}{\parindent}
    1519
    16 \newlength{\gcolumnposn}                                % temporary hack because lstlisting does handle tabs correctly
     20\newlength{\gcolumnposn}                                % temporary hack because lstlisting does not handle tabs correctly
    1721\newlength{\columnposn}
    1822\setlength{\gcolumnposn}{2.75in}
     
    2125\newcommand{\CRT}{\global\columnposn=\gcolumnposn}
    2226
    23 \newcommand{\TODO}[1]{\textbf{TODO}: {\itshape #1}} % TODO included
    24 %\newcommand{\TODO}[1]{} % TODO elided
    2527% Latin abbreviation
    2628\newcommand{\abbrevFont}{\textit}       % set empty for no italics
     
    4345                {\abbrevFont{et al}.\xspace}%
    4446}%
    45 % \newcommand{\eg}{\textit{e}.\textit{g}.,\xspace}
    46 % \newcommand{\ie}{\textit{i}.\textit{e}.,\xspace}
    47 % \newcommand{\etc}{\textit{etc}.,\xspace}
    4847\makeatother
    4948
     
    5655\newcommand{\CCtwenty}{\rm C\kern-.1em\hbox{+\kern-.25em+}20\xspace} % C++20 symbolic name
    5756\newcommand{\CCV}{\rm C\kern-.1em\hbox{+\kern-.25em+}obj\xspace} % C++ virtual symbolic name
    58 \newcommand{\CS}{C\raisebox{-0.7ex}{\Large$^\sharp$}\xspace}
     57\newcommand{\Csharp}{C\raisebox{-0.7ex}{\Large$^\sharp$}\xspace} % C# symbolic name
    5958\newcommand{\Textbf}[1]{{\color{red}\textbf{#1}}}
     59\newcommand{\TODO}[1]{\textbf{TODO}: {\itshape #1}} % TODO included
     60%\newcommand{\TODO}[1]{} % TODO elided
    6061
    6162% CFA programming language, based on ANSI C (with some gcc additions)
     
    8283belowskip=3pt,
    8384% replace/adjust listing characters that look bad in sanserif
    84 literate={-}{\raisebox{-0.15ex}{\texttt{-}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1
    85         {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1%{_}{\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
    86         {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2,
     85literate={-}{\makebox[1.4ex][c]{\raisebox{0.5ex}{\rule{1.2ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1
     86        {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
     87        {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1.4ex][c]{\raisebox{0.5ex}{\rule{1.2ex}{0.1ex}}}\kern-0.3ex\textgreater}2,
    8788moredelim=**[is][\color{red}]{`}{`},
    8889}% lstset
     
    159160The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from commercial operating-systems to hobby projects.
    160161This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more.
    161 The \citet{TIOBE} ranks the top 5 most popular programming languages as: Java 16\%, \Textbf{C 7\%}, \Textbf{\CC 5\%}, \CS 4\%, Python 4\% = 36\%, where the next 50 languages are less than 3\% each with a long tail.
     162The \citet{TIOBE} ranks the top 5 most popular programming languages as: Java 16\%, \Textbf{C 7\%}, \Textbf{\CC 5\%}, \Csharp 4\%, Python 4\% = 36\%, where the next 50 languages are less than 3\% each with a long tail.
    162163The top 3 rankings over the past 30 years are:
    163164\lstDeleteShortInline@%
     
    185186\CC is used similarly, but has the disadvantages of multiple legacy design-choices that cannot be updated and active divergence of the language model from C, requiring significant effort and training to incrementally add \CC to a C-based project.
    186187
    187 \CFA is currently implemented as a source-to-source translator from \CFA to the GCC-dialect of C~\citep{GCCExtensions}, allowing it to leverage the portability and code optimizations provided by GCC, meeting goals (1)-(3).
     188\CFA is currently implemented as a source-to-source translator from \CFA to the GCC-dialect of C~\citep{GCCExtensions}, allowing it to leverage the portability and code optimizations provided by GCC, meeting goals (1)--(3).
    188189Ultimately, a compiler is necessary for advanced features and optimal performance.
    189190
     
    273274
    274275Finally, \CFA allows variable overloading:
    275 %\lstDeleteShortInline@%
    276 %\par\smallskip
    277 %\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
    278276\begin{lstlisting}
    279277short int MAX = ...;   int MAX = ...;  double MAX = ...;
    280278short int s = MAX;    int i = MAX;    double d = MAX;   $\C{// select correct MAX}$
    281279\end{lstlisting}
    282 %\end{lstlisting}
    283 %&
    284 %\begin{lstlisting}
    285 %\end{tabular}
    286 %\smallskip\par\noindent
    287 %\lstMakeShortInline@%
    288280Here, the single name @MAX@ replaces all the C type-specific names: @SHRT_MAX@, @INT_MAX@, @DBL_MAX@.
    289281As well, restricted constant overloading is allowed for the values @0@ and @1@, which have special status in C, \eg the value @0@ is both an integer and a pointer literal, so its meaning depends on context.
     
    464456}
    465457\end{lstlisting}
    466 %       int c = cmp( a->first, b->first );
    467 %       if ( c == 0 ) c = cmp( a->second, b->second );
    468 %       return c;
    469458Since @pair(T *, T * )@ is a concrete type, there are no implicit parameters passed to @lexcmp@, so the generated code is identical to a function written in standard C using @void *@, yet the \CFA version is type-checked to ensure the fields of both pairs and the arguments to the comparison function match in type.
    470459
     
    612601double y = 3.5;
    613602[int, double] z;
    614 z = [x, y];             $\C{// multiple assignment}$
    615 [x, y] = z;             $\C{// multiple assignment}$
    616 z = 10;                 $\C{// mass assignment}$
    617 [y, x] = 3.14;  $\C{// mass assignment}$
     603z = [x, y];                                                                     $\C{// multiple assignment}$
     604[x, y] = z;                                                                     $\C{// multiple assignment}$
     605z = 10;                                                                         $\C{// mass assignment}$
     606[y, x] = 3.14;                                                          $\C{// mass assignment}$
    618607\end{lstlisting}
    619608%\end{lstlisting}
     
    652641[int, int, long, double] x;
    653642void f( double, long );
    654 x.[0, 1] = x.[1, 0];    $\C{// rearrange: [x.0, x.1] = [x.1, x.0]}$
    655 f( x.[0, 3] );            $\C{// drop: f(x.0, x.3)}$
    656 [int, int, int] y = x.[2, 0, 2]; $\C{// duplicate: [y.0, y.1, y.2] = [x.2, x.0.x.2]}$
     643x.[0, 1] = x.[1, 0];                                            $\C{// rearrange: [x.0, x.1] = [x.1, x.0]}$
     644f( x.[0, 3] );                                                          $\C{// drop: f(x.0, x.3)}$
     645[int, int, int] y = x.[2, 0, 2];                        $\C{// duplicate: [y.0, y.1, y.2] = [x.2, x.0.x.2]}$
    657646\end{lstlisting}
    658647%\end{lstlisting}
     
    851840\begin{lstlisting}
    852841forall(dtype T0, dtype T1 | sized(T0) | sized(T1)) struct _tuple2 {
    853         T0 field_0;                     $\C{// generated before the first 2-tuple}$
     842        T0 field_0;                                                             $\C{// generated before the first 2-tuple}$
    854843        T1 field_1;
    855844};
     
    857846        _tuple2(double, double) x;
    858847        forall(dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2)) struct _tuple3 {
    859                 T0 field_0;             $\C{// generated before the first 3-tuple}$
     848                T0 field_0;                                                     $\C{// generated before the first 3-tuple}$
    860849                T1 field_1;
    861850                T2 field_2;
     
    10231012\section{Related Work}
    10241013
    1025 % \subsection{Polymorphism}
     1014
     1015\subsection{Polymorphism}
    10261016
    10271017\CC is the most similar language to \CFA;
     
    10411031In \CFA terms, all Cyclone polymorphism must be dtype-static.
    10421032While the Cyclone design provides the efficiency benefits discussed in Section~\ref{sec:generic-apps} for dtype-static polymorphism, it is more restrictive than \CFA's general model.
    1043 \citet{Smith98} present Polymorphic C, an ML dialect with polymorphic functions and C-like syntax and pointer types; it lacks many of C's features, however, most notably struct types, and so is not a practical C replacement.
     1033\citet{Smith98} present Polymorphic C, an ML dialect with polymorphic functions and C-like syntax and pointer types; it lacks many of C's features, however, most notably structure types, and so is not a practical C replacement.
    10441034
    10451035\citet{obj-c-book} is an industrially successful extension to C.
    10461036However, Objective-C is a radical departure from C, using an object-oriented model with message-passing.
    1047 Objective-C did not support type-checked generics until recently \citep{xcode7}, historically using less-efficient runtime checking of object types.
     1037Objective-C did not support type-checked generics until recently \citet{xcode7}, historically using less-efficient runtime checking of object types.
    10481038The~\citet{GObject} framework also adds object-oriented programming with runtime type-checking and reference-counting garbage-collection to C;
    10491039these features are more intrusive additions than those provided by \CFA, in addition to the runtime overhead of reference-counting.
    10501040\citet{Vala} compiles to GObject-based C, adding the burden of learning a separate language syntax to the aforementioned demerits of GObject as a modernization path for existing C code-bases.
    1051 Java~\citep{Java8} included generic types in Java~5 which are type-checked at compilation and type-erased at runtime, similar to \CFA's.
     1041Java~\citep{Java8} included generic types in Java~5, which are type-checked at compilation and type-erased at runtime, similar to \CFA's.
    10521042However, in Java, each object carries its own table of method pointers, while \CFA passes the method pointers separately to maintain a C-compatible layout.
    10531043Java is also a garbage-collected, object-oriented language, with the associated resource usage and C-interoperability burdens.
     
    10631053\CFA, with its more modest safety features, allows direct ports of C code while maintaining the idiomatic style of the original source.
    10641054
    1065 % \subsection{Tuples/Variadics}
     1055
     1056\subsection{Tuples/Variadics}
    10661057
    10671058Many programming languages have some form of tuple construct and/or variadic functions, \eg SETL, C, KW-C, \CC, D, Go, Java, ML, and Scala.
     
    11071098
    11081099\begin{acks}
    1109 The authors would like to recognize the design assistance of Glen Ditchfield, Richard Bilson, and Thierry Delisle on the features described in this paper. They also thank Magnus Madsen and three anonymous reviewers for valuable editorial feedback.
    1110 
    1111 This work is supported in part by a corporate partnership with \grantsponsor{Huawei}{Huawei Ltd.}{http://www.huawei.com}\ and the first author's \grantsponsor{NSERC-PGS}{NSERC PGS D}{http://www.nserc-crsng.gc.ca/Students-Etudiants/PG-CS/BellandPostgrad-BelletSuperieures_eng.asp} scholarship.
     1100The authors would like to recognize the design assistance of Glen Ditchfield, Richard Bilson, and Thierry Delisle on the features described in this paper, and thank Magnus Madsen and the three anonymous reviewers for valuable feedback.
     1101This work is supported in part by a corporate partnership with \grantsponsor{Huawei}{Huawei Ltd.}{http://www.huawei.com}, and Aaron Moss and Peter Buhr are funded by the \grantsponsor{Natural Sciences and Engineering Research Council} of Canada.
     1102% the first author's \grantsponsor{NSERC-PGS}{NSERC PGS D}{http://www.nserc-crsng.gc.ca/Students-Etudiants/PG-CS/BellandPostgrad-BelletSuperieures_eng.asp} scholarship.
    11121103\end{acks}
    11131104
     
    11231114
    11241115\lstset{basicstyle=\linespread{0.9}\sf\small}
    1125 
    1126 \begin{comment}
    1127 \CFA
    1128 \begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    1129 forall(otype T) struct stack_node;
    1130 forall(otype T) struct stack { stack_node(T) * head; };
    1131 forall(otype T) void ?{}(stack(T) * s);
    1132 forall(otype T) void ?{}(stack(T) * s, stack(T) t);
    1133 forall(otype T) stack(T) ?=?(stack(T) * s, stack(T) t);
    1134 forall(otype T) void ^?{}(stack(T) * s);
    1135 forall(otype T) _Bool empty(const stack(T) * s);
    1136 forall(otype T) void push(stack(T) * s, T value);
    1137 forall(otype T) T pop(stack(T) * s);
    1138 forall(otype T) void clear(stack(T) * s);
    1139 
    1140 void print( FILE * out, const char * x );
    1141 void print( FILE * out, _Bool x );
    1142 void print( FILE * out, char x );
    1143 void print( FILE * out, int x );
    1144 forall(otype T, ttype Params | { void print( FILE *, T ); void print( FILE *, Params ); })
    1145         void print( FILE * out, T arg, Params rest );
    1146 forall(otype R, otype S | { void print( FILE *, R ); void print( FILE *, S ); })
    1147         void print( FILE * out, pair(R, S) x );
    1148 \end{lstlisting}
    1149 
    1150 \medskip\noindent
    1151 \CC
    1152 \begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    1153 std::pair
    1154 std::forward_list wrapped in std::stack interface
    1155 
    1156 template<typename T> void print(ostream & out, const T & x) { out << x; }
    1157 template<> void print<bool>(ostream & out, const bool & x) { out << (x ? "true" : "false"); }
    1158 template<> void print<char>(ostream & out, const char & x ) { out << "'" << x << "'"; }
    1159 template<typename R, typename S> ostream & operator<< (ostream & out, const pair<R, S>& x) {
    1160         out << "["; print(out, x.first); out << ", "; print(out, x.second); return out << "]"; }
    1161 template<typename T, typename... Args> void print(ostream & out, const T & arg, const Args &... rest) {
    1162         out << arg;     print(out, rest...); }
    1163 \end{lstlisting}
    1164 
    1165 \medskip\noindent
    1166 C
    1167 \begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    1168 struct pair { void * first, second; };
    1169 struct pair * new_pair( void * first, void * second );
    1170 struct pair * copy_pair( const struct pair * src,
    1171         void * (*copy_first)( const void * ), void * (*copy_second)( const void * ) );
    1172 void free_pair( struct pair * p, void (*free_first)( void * ), void (*free_second)( void * ) );
    1173 int cmp_pair( const struct pair * a, const struct pair * b,
    1174         int (*cmp_first)( const void *, const void * ), int (*cmp_second)( const void *, const void * ) );
    1175 
    1176 struct stack_node;
    1177 struct stack { struct stack_node * head; };
    1178 struct stack new_stack();
    1179 void copy_stack( struct stack * dst, const struct stack * src, void * (*copy)( const void * ) );
    1180 void clear_stack( struct stack * s, void (*free_el)( void * ) );
    1181 _Bool stack_empty( const struct stack * s );
    1182 void push_stack( struct stack * s, void * value );
    1183 void * pop_stack( struct stack * s );
    1184 
    1185 void print_string( FILE * out, const char * x );
    1186 void print_bool( FILE * out, _Bool x );
    1187 void print_char( FILE * out, char x );
    1188 void print_int( FILE * out, int x );
    1189 void print( FILE * out, const char * fmt, ... );
    1190 \end{lstlisting}
    1191 \end{comment}
    11921116
    11931117Throughout, @/***/@ designates a counted redundant type annotation.
Note: See TracChangeset for help on using the changeset viewer.