Changeset 493d73a for doc/papers


Ignore:
Timestamp:
Feb 14, 2018, 9:19:51 PM (6 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, resolv-new, with_gc
Children:
2dcb750
Parents:
cd310f7
Message:

update library discussion

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/papers/general/Paper.tex

    rcd310f7 r493d73a  
    66\usepackage{upquote}                                            % switch curled `'" to straight
    77\usepackage{listings}                                           % format program code
     8\usepackage{enumitem}
    89\usepackage[flushmargin]{footmisc}                      % support label/reference in footnote
    910\usepackage{rotating}
     
    10561057\begin{cquote}
    10571058\lstDeleteShortInline@%
    1058 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
    1059 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
     1059\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     1060\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
    10601061\begin{cfa}
    10611062case 2, 10, 34, 42:
     
    10711072\begin{cquote}
    10721073\lstDeleteShortInline@%
    1073 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
    1074 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
     1074\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     1075\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
    10751076\begin{cfa}
    10761077case 2~42:
     
    11231124\begin{cquote}
    11241125\lstDeleteShortInline@%
    1125 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
    1126 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
     1126\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     1127\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
    11271128\begin{cfa}
    11281129`choose` ( day ) {
     
    13791380\lstDeleteShortInline@%
    13801381\lstset{moredelim=**[is][\color{blue}]{+}{+}}
    1381 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
    1382 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
     1382\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     1383\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
    13831384\begin{cfa}
    13841385+[5] *+ `int` x1;
    13851386+* [5]+ `int` x2;
    1386 +[* [5] int]+ f`( int p )`;
     1387`[* [5] int]` f+( int p )+;
    13871388\end{cfa}
    13881389&
     
    13901391`int` +*+ x1 +[5]+;
    13911392`int` +(*+x2+)[5]+;
    1392 +int (*+f`( int p )`+)[5]+;
     1393`int (*`f+( int p )+`)[5]`;
    13931394\end{cfa}
    13941395\end{tabular}
     
    14011402\begin{cquote}
    14021403\lstDeleteShortInline@%
    1403 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
    1404 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
     1404\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     1405\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
    14051406\begin{cfa}
    14061407`*` int x, y;
     
    14161417\begin{cquote}
    14171418\lstDeleteShortInline@%
    1418 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
    1419 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
     1419\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     1420\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
    14201421\begin{cfa}
    14211422`*` int x;
     
    14341435\begin{cquote}
    14351436\lstDeleteShortInline@%
    1436 \begin{tabular}{@{}l@{\hspace{3em}}l@{\hspace{2em}}l@{}}
    1437 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c@{\hspace{2em}}}{\textbf{C}} \\
     1437\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{}}
     1438\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{C}}      \\
    14381439\begin{cfa}
    14391440[ 5 ] int z;
     
    14751476\begin{cquote}
    14761477\lstDeleteShortInline@%
    1477 \begin{tabular}{@{}l@{\hspace{1em}}l@{\hspace{1em}}l@{}}
    1478 \multicolumn{1}{c@{\hspace{1em}}}{\textbf{\CFA}}        & \multicolumn{1}{c@{\hspace{1em}}}{\textbf{C}} \\
     1478\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{}}
     1479\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{C}}      \\
    14791480\begin{cfa}
    14801481const * const int x;
     
    14981499\begin{cquote}
    14991500\lstDeleteShortInline@%
    1500 \begin{tabular}{@{}l@{\hspace{3em}}l@{\hspace{2em}}l@{}}
    1501 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c@{\hspace{2em}}}{\textbf{C}} \\
     1501\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{}}
     1502\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{C}}      \\
    15021503\begin{cfa}
    15031504extern [ 5 ] int x;
     
    15211522\begin{cquote}
    15221523\lstDeleteShortInline@%
    1523 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
    1524 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
     1524\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     1525\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
    15251526\begin{cfa}
    15261527y = (* int)x;
     
    15521553\begin{cquote}
    15531554\lstDeleteShortInline@%
    1554 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
    1555 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
     1555\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     1556\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
    15561557\begin{cfa}
    15571558[double] foo(), foo( int ), foo( double ) {...}
     
    18151816
    18161817As stated in Section~\ref{sec:poly-fns}, \CFA inherits a massive corpus of library code, where other programming languages must rewrite or provide fragile inter-language communication with C.
    1817 \CFA has replacement libraries condensing hundreds of existing C functions into tens of \CFA overloaded functions, all without rewriting the actual computations.
     1818\CFA has replacement libraries condensing hundreds of existing C routines into tens of \CFA overloaded routines, all without rewriting the actual computations.
    18181819In many cases, the interface is an inline wrapper providing overloading during compilation but zero cost at runtime.
    18191820The following sections give a gleams of the interface reduction to many C libraries.
     
    18241825
    18251826C library @limits.h@ provides lower and upper bound constants for the basic types.
    1826 \CFA name overloading is used to overload these constants, \eg:
     1827\CFA name overloading is used to condense these typed constants, \eg:
    18271828\begin{cquote}
    18281829\lstDeleteShortInline@%
    1829 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
    1830 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{Definition}}  & \multicolumn{1}{c}{\textbf{Usage}}    \\
     1830\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     1831\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{Definition}}       & \multicolumn{1}{c}{\textbf{Usage}}    \\
    18311832\begin{cfa}
    18321833const short int `MIN` = -32768;
     
    18461847\begin{cquote}
    18471848\lstDeleteShortInline@%
    1848 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
    1849 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
    1850 \begin{cfa}
    1851 MIN,
    1852 MAX,
    1853 M_PI,
     1849\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     1850\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
     1851\begin{cfa}
     1852MIN
     1853MAX
     1854M_PI
    18541855M_E
    18551856\end{cfa}
     
    18681869\subsection{Math}
    18691870
    1870 C library @math.h@ provides lower and upper bound constants for the basic types.
    1871 \CFA name overloading is used to overload these constants, \eg:
     1871C library @math.h@ provides many mathematical routines.
     1872\CFA routine overloading is used to condense these mathematical routines, \eg:
    18721873\begin{cquote}
    18731874\lstDeleteShortInline@%
    1874 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
    1875 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{Definition}}  & \multicolumn{1}{c}{\textbf{Usage}}    \\
     1875\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     1876\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{Definition}}       & \multicolumn{1}{c}{\textbf{Usage}}    \\
    18761877\begin{cfa}
    18771878float `log`( float x );
     
    18911892\begin{cquote}
    18921893\lstDeleteShortInline@%
    1893 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
    1894 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
    1895 \begin{cfa}
    1896 log,
    1897 sqrt,
     1894\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     1895\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
     1896\begin{cfa}
     1897log
     1898sqrt
    18981899sin
    18991900\end{cfa}
     
    19071908\lstMakeShortInline@%
    19081909\end{cquote}
     1910While \Celeven provides type-generic math~\cite[\S~7.25]{C11} in @tgmath.h@ to provide a similar mechanism, these macros are limited, matching a routine name with a single set of floating type(s).
     1911For example, it is not possible to overload @atan@ for both one and two arguments;
     1912instead the names @atan@ and @atan2@ are required.
     1913The key observation is that only a restricted set of type-generic macros are provided for a limited set of routine names, which do not generalize across the type system, as in \CFA.
    19091914
    19101915
    19111916\subsection{Standard}
    19121917
    1913 Library routines (@stdlib.h@) with multiple types.
     1918C library @stdlib.h@ provides many general routines.
     1919\CFA routine overloading is used to condense these utility routines, \eg:
    19141920\begin{cquote}
    19151921\lstDeleteShortInline@%
    1916 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
    1917 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{Definition}}  & \multicolumn{1}{c}{\textbf{Usage}}    \\
     1922\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     1923\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{Definition}}       & \multicolumn{1}{c}{\textbf{Usage}}    \\
    19181924\begin{cfa}
    19191925unsigned int `abs`( int );
     
    19301936\lstMakeShortInline@%
    19311937\end{cquote}
    1932 The result is a significant reduction in names to access math routines, \eg:
     1938The result is a significant reduction in names to access utility routines, \eg:
    19331939\begin{cquote}
    19341940\lstDeleteShortInline@%
    1935 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
    1936 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
    1937 \begin{cfa}
    1938 abs,
    1939 strto,
     1941\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     1942\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
     1943\begin{cfa}
     1944abs
     1945strto
    19401946random
    19411947\end{cfa}
     
    19521958The following shows one example where \CFA \emph{extends} an existing standard C interface to reduce complexity and provide safety.
    19531959C/\Celeven provide a number of complex and overlapping storage-management operation to support the following capabilities:
    1954 \begin{description}
     1960\begin{description}[itemsep=2pt,parsep=0pt]
    19551961\item[fill]
    19561962after allocation the storage is filled with a specified character.
     
    19661972\end{description}
    19671973Table~\ref{t:StorageManagementOperations} shows the capabilities provided by C/\Celeven allocation-routines and how all the capabilities can be combined into two \CFA routines.
    1968 \begin{table}[h]
     1974The following example contrasts \CFA and C storage-allocation operation performing the same operations with the same type safety:
     1975\begin{cquote}
     1976\begin{cfa}[aboveskip=0pt]
     1977size_t  dim = 10;
     1978char fill = '\xff';
     1979int * ip;
     1980\end{cfa}
     1981\lstDeleteShortInline@%
     1982\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     1983\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
     1984\begin{cfa}
     1985ip = alloc();
     1986ip = alloc( fill );
     1987ip = alloc( dim );
     1988ip = alloc( dim, fill );
     1989ip = alloc( ip, 2 * dim );
     1990ip = alloc( ip, 4 * dim, fill );
     1991
     1992ip = align_alloc( 16 );
     1993ip = align_alloc( 16, fill );
     1994ip = align_alloc( 16, dim );
     1995ip = align_alloc( 16, dim, fill );
     1996\end{cfa}
     1997&
     1998\begin{cfa}
     1999ip = (int *)malloc( sizeof( int ) );
     2000ip = (int *)malloc( sizeof( int ) ); memset( ip, fill, sizeof( int ) );
     2001ip = (int *)malloc( dim * sizeof( int ) );
     2002ip = (int *)malloc( sizeof( int ) ); memset( ip, fill, dim * sizeof( int ) );
     2003ip = (int *)realloc( ip, 2 * dim * sizeof( int ) );
     2004ip = (int *)realloc( ip, 4 * dim * sizeof( int ) ); memset( ip, fill, 4 * dim * sizeof( int ) );
     2005
     2006ip = memalign( 16, sizeof( int ) );
     2007ip = memalign( 16, sizeof( int ) ); memset( ip, fill, sizeof( int ) );
     2008ip = memalign( 16, dim * sizeof( int ) );
     2009ip = memalign( 16, dim * sizeof( int ) ); memset( ip, fill, dim * sizeof( int ) );
     2010\end{cfa}
     2011\end{tabular}
     2012\lstMakeShortInline@%
     2013\end{cquote}
     2014Variadic @new@ (see Section~\ref{sec:variadic-tuples}) cannot support the same overloading because extra parameters are for initialization.
     2015
     2016Finally, the \CFA memory-allocator has \newterm{sticky properties} for dynamically-allocated storage: fill and alignment are remembered with an object's storage.
     2017When a @realloc@ is performed, the sticky properties are respected, so that new storage is correctly aligned and initialized with the fill character.
     2018
     2019\begin{table}
    19692020\centering
    19702021\lstDeleteShortInline@%
     
    19812032C11             & ~aligned_alloc~       & no                    & no            & yes           & no    \\
    19822033\hline
    1983 \CFA    & ~alloc~                       & no/copy/yes   & no/yes        & no            & yes   \\
    1984                 & ~align_alloc~         & no/yes                & no            & yes           & yes   \\
     2034\CFA    & ~alloc~                       & yes/copy              & no/yes        & no            & yes   \\
     2035                & ~align_alloc~         & yes                   & no            & yes           & yes   \\
    19852036\end{tabular}
    19862037\lstDeleteShortInline~%
     
    19892040\label{t:StorageManagementOperations}
    19902041\end{table}
    1991 It is impossible to resize with alignment because the underlying @realloc@ allocates storage if more space is needed, and it does not honour alignment from the original allocation.
    19922042
    19932043
     
    20022052\begin{cquote}
    20032053\lstDeleteShortInline@%
    2004 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
    2005 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{\CC}}      \\
     2054\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     2055\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{\CC}}      \\
    20062056\begin{cfa}
    20072057int x = 1, y = 2, z = 3;
     
    20622112The implicit separator character (space/blank) is a separator not a terminator.
    20632113The rules for implicitly adding the separator are:
    2064 \begin{list}{\footnotesize$\bullet$}{\itemsep=2pt\parsep=0pt}
     2114\begin{itemize}[itemsep=2pt,parsep=0pt]
    20652115\item
    20662116A separator does not appear at the start or end of a line.
     
    20792129\item
    20802130There are routines to set and get the separator string, and manipulators to toggle separation on and off in the middle of output.
    2081 \end{list}
     2131\end{itemize}
    20822132The storage-management routines extend their C equivalents by overloading, alternate names, providing shallow type-safety, and removing the need to specify the allocation size for non-array types.
    20832133
Note: See TracChangeset for help on using the changeset viewer.