# Changeset 3895b8b5 for doc

Ignore:
Timestamp:
Apr 14, 2017, 12:41:06 PM (6 years ago)
Branches:
aaron-thesis, arm-eh, 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:
3fb7f5e, bbe856c
Parents:
1a16e9d
Message:

initial work on evaluatoin and related polymorphic work

Location:
doc
Files:
2 deleted
4 edited

Unmodified
Removed
• ## doc/bibliography/cfa.bib

 r1a16e9d @manual{obj-c-book, keywords = {objective-c}, contributor = {a3moss@uwaterloo.ca}, author = {{Apple Computer Inc.}}, title = {The {Objective-C} Programming Language}, publisher = {Apple Computer Inc.}, address = {Cupertino, CA}, year = 2003 keywords    = {objective-c}, contributor = {a3moss@uwaterloo.ca}, author      = {{Apple Computer}}, title       = {The {Objective-C} Programming Language}, organization= {Apple Computer Inc.}, address     = {Cupertino, CA}, year        = 2003 } year        = 1980, month       = nov, volume = 15, number = 11, pages = {47-56}, note        = {Proceedings of the ACM-SIGPLAN Symposium on the {Ada} Programming Language}, note        = {Proceedings of the ACM-SIGPLAN Symposium on the {Ada} Programming Language}, comment     = { The two-pass (bottom-up, then top-down) algorithm, with a proof keywords    = {Rust programming language}, contributer = {pabuhr@plg}, author      = {{Rust Programming Language}}, title       = {The {Rust} Programming Language}, organization= {The Rust Project Developers},
• ## doc/generic_types/Makefile

 r1a16e9d GRAPHS = ${addsuffix .tex, \ timing \ } #${DOCUMENT} : Makefile ${GRAPHS}${PROGRAMS} ${PICTURES}${FIGURES} ${SOURCES}${basename ${DOCUMENT}}.tex \${basename ${DOCUMENT}}.dvi : Makefile${GRAPHS} ${PROGRAMS}${PICTURES} ${FIGURES}${SOURCES} ${basename${DOCUMENT}}.tex \ ../LaTeXmacros/common.tex ../LaTeXmacros/indexstyle ../bibliography/cfa.bib ${basename${DOCUMENT}}.dvi : Makefile ${GRAPHS}${PROGRAMS} ${PICTURES}${FIGURES} ${SOURCES}${basename ${DOCUMENT}}.tex ../bibliography/cfa.bib # Conditionally create an empty *.idx (index) file for inclusion until makeindex is run. if [ ! -r${basename $@}.idx ] ; then touch${basename $@}.idx ; fi ## Define the default recipes.${GRAPHS} : evaluation/timing.gp evaluation/timing.csv gnuplot evaluation/timing.gp %.tex : %.fig fig2dev -L eepic $< >$@
• ## doc/generic_types/evaluation/timing.csv

 r1a16e9d "400 million repetitions","C","Cforall","C++","C++obj","units" "400 million repetitions","C","\\CFA{}","\\CC{}","\\CC{obj}","units" "push\nint",3379,2616,1928,3527,"ms" "copy\nint",3036,2268,1564,3182,"ms"
• ## doc/generic_types/generic_types.tex

 r1a16e9d \usepackage{upquote}                                                                    % switch curled '" to straight \usepackage{listings}                                                                   % format program code \usepackage{graphicx} \makeatletter \begin{abstract} The 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. This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more. Nonetheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive. The goal of the \CFA project is to create an extension of C that provides modern safety and productivity features while still ensuring strong backwards compatibility with C and its programmers. Prior projects have attempted similar goals but failed to honour C programming-style; for instance, adding object-oriented or functional programming with garbage collection is a non-starter for many C developers. Specifically, \CFA is designed to have an orthogonal feature-set based closely on the C programming paradigm, so that \CFA features can be added \emph{incrementally} to existing C code-bases, and C programmers can learn \CFA extensions on an as-needed basis, preserving investment in existing code and engineers. This paper describes two \CFA extensions, generic and tuple types, details how their design avoids shortcomings of similar features in C and other C-like languages, and presents experimental results validating the design. The 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. This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more. Nonetheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive. The goal of the \CFA project is to create an extension of C that provides modern safety and productivity features while still ensuring strong backwards compatibility with C and its programmers. Prior projects have attempted similar goals but failed to honour C programming-style; for instance, adding object-oriented or functional programming with garbage collection is a non-starter for many C developers. Specifically, \CFA is designed to have an orthogonal feature-set based closely on the C programming paradigm, so that \CFA features can be added \emph{incrementally} to existing C code-bases, and C programmers can learn \CFA extensions on an as-needed basis, preserving investment in existing code and engineers. This paper describes two \CFA extensions, generic and tuple types, details how their design avoids shortcomings of similar features in C and other C-like languages, and presents experimental results validating the design. \end{abstract} \section{Introduction and Background} The 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. This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more. 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. The top 3 rankings over the past 30 years are: The 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. This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more. 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. The top 3 rankings over the past 30 years are: \lstDeleteShortInline@% \begin{center} Nonetheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive. \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 compatibility with C and a familiar programming model for programmers. The four key design goals for \CFA~\citep{Bilson03} are: \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 compatibility with C and a familiar programming model for programmers. The four key design goals for \CFA~\citep{Bilson03} are: (1) The behaviour of standard C code must remain the same when translated by a \CFA compiler as when translated by a C compiler; (2) Standard C code must be as fast and as small when translated by a \CFA compiler as when translated by a C compiler; Unfortunately, \CC is actively diverging from C, so incremental additions require significant effort and training, coupled with multiple legacy design-choices that cannot be updated. \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). Ultimately, a compiler is necessary for advanced features and optimal performance. This paper identifies shortcomings in existing approaches to generic and variadic data types in C-like languages and presents a design for generic and variadic types avoiding those shortcomings. Specifically, the solution is both reusable and type-checked, as well as conforming to the design goals of \CFA with ergonomic use of existing C abstractions. The new constructs are empirically compared with both standard C and \CC; the results show the new design is comparable in performance. \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). Ultimately, a compiler is necessary for advanced features and optimal performance. This paper identifies shortcomings in existing approaches to generic and variadic data types in C-like languages and presents a design for generic and variadic types avoiding those shortcomings. Specifically, the solution is both reusable and type-checked, as well as conforming to the design goals of \CFA with ergonomic use of existing C abstractions. The new constructs are empirically compared with both standard C and \CC; the results show the new design is comparable in performance. \label{sec:poly-fns} \CFA's polymorphism was originally formalized by \citet{Ditchfield92}, and first implemented by \citet{Bilson03}. The signature feature of \CFA is parametric-polymorphic functions where functions are generalized using a @forall@ clause (giving the language its name): \CFA's polymorphism was originally formalized by \citet{Ditchfield92}, and first implemented by \citet{Bilson03}. The signature feature of \CFA is parametric-polymorphic functions where functions are generalized using a @forall@ clause (giving the language its name): \begin{lstlisting} forall( otype T ) T identity( T val ) { return val; } int forty_two = identity( 42 );                         $\C{// T is bound to int, forty\_two == 42}$ \end{lstlisting} The @identity@ function above can be applied to any complete \emph{object type} (or @otype@). The type variable @T@ is transformed into a set of additional implicit parameters encoding sufficient information about @T@ to create and return a variable of that type. The \CFA implementation passes the size and alignment of the type represented by an @otype@ parameter, as well as an assignment operator, constructor, copy constructor and destructor. If this extra information is not needed, \eg for a pointer, the type parameter can be declared as a \emph{data type} (or @dtype@). In \CFA, the polymorphism runtime-cost is spread over each polymorphic call, due to passing more arguments to polymorphic functions; preliminary experiments show this overhead is similar to \CC virtual-function calls. An advantage of this design is that, unlike \CC template-functions, \CFA polymorphic-functions are compatible with C \emph{separate compilation}, preventing compilation and code bloat. Since bare polymorphic-types provide only a narrow set of available operations, \CFA provides a \emph{type assertion} mechanism to provide further type information, where type assertions may be variable or function declarations that depend on a polymorphic type-variable. For example, the function @twice@ can be defined using the \CFA syntax for operator overloading: The @identity@ function above can be applied to any complete \emph{object type} (or @otype@). The type variable @T@ is transformed into a set of additional implicit parameters encoding sufficient information about @T@ to create and return a variable of that type. The \CFA implementation passes the size and alignment of the type represented by an @otype@ parameter, as well as an assignment operator, constructor, copy constructor and destructor. If this extra information is not needed, \eg for a pointer, the type parameter can be declared as a \emph{data type} (or @dtype@). In \CFA, the polymorphism runtime-cost is spread over each polymorphic call, due to passing more arguments to polymorphic functions; preliminary experiments show this overhead is similar to \CC virtual-function calls. An advantage of this design is that, unlike \CC template-functions, \CFA polymorphic-functions are compatible with C \emph{separate compilation}, preventing compilation and code bloat. Since bare polymorphic-types provide only a narrow set of available operations, \CFA provides a \emph{type assertion} mechanism to provide further type information, where type assertions may be variable or function declarations that depend on a polymorphic type-variable. For example, the function @twice@ can be defined using the \CFA syntax for operator overloading: \begin{lstlisting} forall( otype T | { T ?+?(T, T); }` ) T twice( T x ) { return x + x; } $\C{// ? denotes operands}$ int val = twice( twice( 3.7 ) ); \end{lstlisting} which works for any type @T@ with a matching addition operator. The polymorphism is achieved by creating a wrapper function for calling @+@ with @T@ bound to @double@, then passing this function to the first call of @twice@. There is now the option of using the same @twice@ and converting the result to @int@ on assignment, or creating another @twice@ with type parameter @T@ bound to @int@ because \CFA uses the return type, as in~\cite{Ada}, in its type analysis. The first approach has a late conversion from @double@ to @int@ on the final assignment, while the second has an eager conversion to @int@. \CFA minimizes the number of conversions and their potential to lose information, so it selects the first approach, which corresponds with C-programmer intuition. which works for any type @T@ with a matching addition operator. The polymorphism is achieved by creating a wrapper function for calling @+@ with @T@ bound to @double@, then passing this function to the first call of @twice@. There is now the option of using the same @twice@ and converting the result to @int@ on assignment, or creating another @twice@ with type parameter @T@ bound to @int@ because \CFA uses the return type, as in~\cite{Ada}, in its type analysis. The first approach has a late conversion from @double@ to @int@ on the final assignment, while the second has an eager conversion to @int@. \CFA minimizes the number of conversions and their potential to lose information, so it selects the first approach, which corresponds with C-programmer intuition. Crucial to the design of a new programming language are the libraries to access thousands of external software features. where the return type supplies the type/size of the allocation, which is impossible in most type systems. Call-site inferencing and nested functions provide a localized form of inheritance. For example, the \CFA @qsort@ only sorts in ascending order using @<@. However, it is trivial to locally change this behaviour: Call-site inferencing and nested functions provide a localized form of inheritance. For example, the \CFA @qsort@ only sorts in ascending order using @<@. However, it is trivial to locally change this behaviour: \begin{lstlisting} forall( otype T | { int ?
Note: See TracChangeset for help on using the changeset viewer.