Changeset d52a55b for doc/papers/general


Ignore:
Timestamp:
May 3, 2018, 12:25:25 PM (7 years ago)
Author:
Peter A. Buhr <pabuhr@…>
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, with_gc
Children:
637dd9c
Parents:
01b8ccf1
Message:

description of CFA translator

File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/papers/general/Paper.tex

    r01b8ccf1 rd52a55b  
    228228Nevertheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive.
    229229
    230 \CFA (pronounced ``C-for-all'', and written \CFA or Cforall) is an evolutionary extension of the C programming language that aims to add modern language features to C, while maintaining both source and runtime compatibility with C and a familiar programming model for programmers.
     230\CFA (pronounced ``C-for-all'', and written \CFA or Cforall) is an evolutionary extension of the C programming language that adds modern language-features to C, while maintaining both source and runtime compatibility with C and a familiar programming model for programmers.
    231231The four key design goals for \CFA~\cite{Bilson03} are:
    232232(1) The behaviour of standard C code must remain the same when translated by a \CFA compiler as when translated by a C compiler;
    … …  
    237237\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.
    238238
     239All languages features discussed in this paper are working, except some advanced exception-handling features.
     240Not discussed in this paper are the integrated concurrency-constructs and user-level threading-library~\cite{Delisle18}.
    239241\CFA is an \emph{open-source} project implemented as an source-to-source translator from \CFA to the gcc-dialect of C~\cite{GCCExtensions}, allowing it to leverage the portability and code optimizations provided by gcc, meeting goals (1)--(3).
    240242Ultimately, a compiler is necessary for advanced features and optimal performance.
    241 All features discussed in this paper are working, unless otherwise stated as under construction.
     243% @plg2[9]% cd cfa-cc/src; cloc ArgTweak CodeGen CodeTools Common Concurrency ControlStruct Designators GenPoly InitTweak MakeLibCfa.cc MakeLibCfa.h Parser ResolvExpr SymTab SynTree Tuples driver prelude main.cc
     244% -------------------------------------------------------------------------------
     245% Language                     files          blank        comment           code
     246% -------------------------------------------------------------------------------
     247% C++                            108           5420           5232          34961
     248% C/C++ Header                    86           2379           2450           8464
     249% Teamcenter def                   2            115             65           1387
     250% make                             5            168             87           1052
     251% C                               20            109            403            488
     252% awk                              1             12             26            121
     253% sed                              1              0              0              6
     254% -------------------------------------------------------------------------------
     255% SUM:                           223           8203           8263          46479
     256% -------------------------------------------------------------------------------
     257The \CFA translator is 200+ files and 46,000+ lines of code written in C/\CC.
     258Starting with a translator versus a compiler makes it easier and faster to generate and debug C object-code rather than intermediate, assembler or machine code.
     259The translator design is based on the \emph{visitor pattern}, allowing multiple passes over the abstract code-tree, which works well for incrementally adding new feature through additional visitor passes.
     260At the heart of the translator is the type resolver, which handles the polymorphic routine/type overload-resolution.
     261% @plg2[8]% cd cfa-cc/src; cloc libcfa
     262% -------------------------------------------------------------------------------
     263% Language                     files          blank        comment           code
     264% -------------------------------------------------------------------------------
     265% C                               35           1256           1240           9116
     266% C/C++ Header                    54            358           1106           1198
     267% make                             2            201            325           1167
     268% C++                              3             18             17            124
     269% Assembly                         3             56             97            111
     270% Bourne Shell                     2              2              0             25
     271% awk                              1              4              0             22
     272% -------------------------------------------------------------------------------
     273% SUM:                           100           1895           2785          11763
     274% -------------------------------------------------------------------------------
     275The \CFA runtime system is 100+ files and 11,000+ lines of code, written in \CFA.
     276Currently, the \CFA runtime is the largest \emph{user} of \CFA providing a vehicle to test the language features and implementation.
     277% @plg2[6]% cd cfa-cc/src; cloc tests examples benchmark
     278% -------------------------------------------------------------------------------
     279% Language                     files          blank        comment           code
     280% -------------------------------------------------------------------------------
     281% C                              237          12260           2869          23286
     282% make                             8            464            245           2838
     283% C/C++ Header                    22            225            175            785
     284% Python                           5            131             93            420
     285% C++                             10             48              5            201
     286% Lua                              2             31              4            126
     287% Java                             4              5              0             80
     288% Go                               2             11              9             40
     289% -------------------------------------------------------------------------------
     290% SUM:                           290          13175           3400          27776
     291% -------------------------------------------------------------------------------
     292The \CFA tests are 290+ files and 27,000+ lines of code.
     293The tests illustrate syntactic and semantic features in \CFA, plus a growing number of runtime benchmarks.
     294The tests check for correctness and are used for daily regression testing of commits (3800+).
    242295
    243296Finally, it is impossible to describe a programming language without usages before definitions.
    … …  
    260313There are only two hard things in Computer Science: cache invalidation and \emph{naming things} -- Phil Karlton
    261314\end{quote}
     315\vspace{-10pt}
    262316C already has a limited form of ad-hoc polymorphism in the form of its basic arithmetic operators, which apply to a variety of different types using identical syntax.
    263317\CFA extends the built-in operator overloading by allowing users to define overloads for any function, not just operators, and even any variable;
    … …  
    354408
    355409\CFA has replacement libraries condensing hundreds of existing C functions into tens of \CFA overloaded functions, all without rewriting the actual computations (see Section~\ref{sec:libraries}).
    356 For example, it is possible to write a type-safe \CFA wrapper @malloc@ based on the C @malloc@:
     410For example, it is possible to write a type-safe \CFA wrapper @malloc@ based on the C @malloc@, where the return type supplies the type/size of the allocation, which is impossible in most type systems.
    357411\begin{cfa}
    358412forall( dtype T | sized(T) ) T * malloc( void ) { return (T *)malloc( sizeof(T) ); }
    359 int * ip = malloc();                                            $\C{// select type and size from left-hand side}$
    360 double * dp = malloc();
    361 struct S {...} * sp = malloc();
    362 \end{cfa}
    363 where the return type supplies the type/size of the allocation, which is impossible in most type systems.
     413// select type and size from left-hand side
     414int * ip = malloc();  double * dp = malloc();  struct S {...} * sp = malloc();
     415\end{cfa}
    364416
    365417Call-site inferencing and nested functions provide a localized form of inheritance.
    … …  
    373425}
    374426\end{cfa}
    375 Within the block, the nested version of @?<?@ performs @?>?@ and this local version overrides the built-in @?<?@ so it is passed to @qsort@.
     427The local version of @?<?@ performs @?>?@ overriding the built-in @?<?@ so it is passed to @qsort@.
    376428Hence, programmers can easily form local environments, adding and modifying appropriate functions, to maximize reuse of other existing functions and types.
    377429
    … …  
    382434        inline {                                                                        $\C{// nested distribution block, add forall/inline to declarations}$
    383435                void push( stack(`T`) & s, `T` value ) ...      $\C{// generic operations}$
    384                 T pop( stack(`T`) & s ) ...
    385436        }
    386437}
    … …  
    388439
    389440
     441\vspace*{-2pt}
    390442\subsection{Traits}
    391443
    392444\CFA provides \newterm{traits} to name a group of type assertions, where the trait name allows specifying the same set of assertions in multiple locations, preventing repetition mistakes at each function declaration:
     445
    393446\begin{cquote}
    394447\lstDeleteShortInline@%
    … …  
    462515
    463516
     517\vspace*{-2pt}
    464518\section{Generic Types}
    465519
    … …  
    474528
    475529\CC, Java, and other languages use \newterm{generic types} to produce type-safe abstract data-types.
    476 \CFA also implements generic types that integrate efficiently and naturally with the existing polymorphic functions, while retaining backwards compatibility with C and providing separate compilation.
     530\CFA generic types integrate efficiently and naturally with the existing polymorphic functions, while retaining backwards compatibility with C and providing separate compilation.
    477531However, for known concrete parameters, the generic-type definition can be inlined, like \CC templates.
    478532
    … …  
    480534\begin{cquote}
    481535\lstDeleteShortInline@%
    482 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
     536\begin{tabular}{@{}l|@{\hspace{2\parindentlnth}}l@{}}
    483537\begin{cfa}
    484538forall( otype R, otype S ) struct pair {
    … …  
    13731427resume( $\emph{alternate-stack}$ )
    13741428\end{cfa}
    1375 These overloads of @resume@ raise the specified exception or the currently propagating exception (reresume) at another \CFA coroutine or task\footnote{\CFA coroutine and concurrency features are discussed in a separately submitted paper.}~\cite{Delisle18}.
     1429These overloads of @resume@ raise the specified exception or the currently propagating exception (reresume) at another \CFA coroutine or task~\cite{Delisle18}.
    13761430Nonlocal raise is restricted to resumption to provide the exception handler the greatest flexibility because processing the exception does not unwind its stack, allowing it to continue after the handler returns.
    13771431
    … …  
    20402094
    20412095
     2096\begin{comment}
    20422097\subsection{Integral Suffixes}
    20432098
    … …  
    20732128\lstMakeShortInline@%
    20742129\end{cquote}
     2130\end{comment}
    20752131
    20762132
    … …  
    27652821data-parallel features have not yet been added to \CFA, but are easily incorporated within its design, while concurrency primitives similar to those in $\mu$\CC have already been added~\cite{Delisle18}.
    27662822Finally, CCured~\cite{Necula02} and Ironclad \CC~\cite{DeLozier13} attempt to provide a more memory-safe C by annotating pointer types with garbage collection information; type-checked polymorphism in \CFA covers several of C's memory-safety issues, but more aggressive approaches such as annotating all pointer types with their nullability or requiring runtime garbage collection are contradictory to \CFA's backwards compatibility goals.
    2767 
    2768 
    2769 \begin{comment}
    2770 \subsection{Control Structures / Declarations / Literals}
    2771 
    2772 Java has default fall through like C/\CC.
    2773 Pascal/Ada/Go/Rust do not have default fall through.
    2774 \Csharp does not have fall through but still requires a break.
    2775 Python uses dictionary mapping. \\
    2776 \CFA choose is like Rust match.
    2777 
    2778 Java has labelled break/continue. \\
    2779 Languages with and without exception handling.
    2780 
    2781 Alternative C declarations. \\
    2782 Different references \\
    2783 Constructors/destructors
    2784 
    2785 0/1 Literals \\
    2786 user defined: D, Objective-C
    2787 \end{comment}
    27882823
    27892824
Note: See TracChangeset for help on using the changeset viewer.