Changeset 29db723


Ignore:
Timestamp:
Mar 8, 2018, 11:04:14 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:
81e8ab0, e59f0bf
Parents:
deb52a0
Message:

additional changes

Location:
doc
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • doc/bibliography/pl.bib

    rdeb52a0 r29db723  
    60616061}
    60626062
     6063@article{Nickolls08,
     6064    author      = {Nickolls, John and Buck, Ian and Garland, Michael and Skadron, Kevin},
     6065    title       = {Scalable Parallel Programming with CUDA},
     6066    journal     = {Queue},
     6067    volume      = {6},
     6068    number      = {2},
     6069    month       = mar,
     6070    year        = 2008,
     6071    pages       = {40-53},
     6072    publisher   = {ACM},
     6073    address     = {New York, NY, USA},
     6074}
     6075
    60636076@inproceedings{Leissa14,
    6064   title={Sierra: a SIMD extension for C++},
    6065   author={Lei{\ss}a, Roland and Haffner, Immanuel and Hack, Sebastian},
    6066   booktitle={Proceedings of the 2014 Workshop on Workshop on programming models for SIMD/Vector processing},
    6067   pages={17--24},
    6068   year={2014},
    6069   organization={ACM}
     6077    title       = {Sierra: a SIMD extension for C++},
     6078    author      = {Lei{\ss}a, Roland and Haffner, Immanuel and Hack, Sebastian},
     6079    booktitle   = {Proceedings of the 2014 Workshop on Workshop on programming models for SIMD/Vector processing},
     6080    pages       = {17--24},
     6081    year        = {2014},
     6082    organization= {ACM}
    60706083}
    60716084
     
    63106323@article{Smith98,
    63116324    keywords    = {Polymorphic C},
    6312     contributor = {a3moss@uwaterloo.ca},
     6325    contributor = {a3moss@uwaterloo.ca},
    63136326    title       = {A sound polymorphic type system for a dialect of C},
    63146327    author      = {Smith, Geoffrey and Volpano, Dennis},
  • doc/papers/general/Paper.tex

    rdeb52a0 r29db723  
    146146% replace/adjust listing characters that look bad in sanserif
    147147literate={-}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1
    148         {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 {@}{\small{@}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
    149         {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex\textgreater}2,
     148        {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 {@}{\small{@}}1 {<}{\small{\textless}}1 {>}{\small{\textgreater}}1  % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
     149        {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex{\small\textgreater}}2,
    150150moredelim=**[is][\color{red}]{`}{`},
    151151}% lstset
     
    436436One approach is to write bespoke data-structures for each context in which they are needed.
    437437While this approach is flexible and supports integration with the C type-checker and tooling, it is also tedious and error-prone, especially for more complex data structures.
    438 A second approach is to use @void *@ based polymorphism, \eg the C standard-library functions @bsearch@ and @qsort@, which allow reuse of code with common functionality.
     438A second approach is to use @void *@-based polymorphism, \eg the C standard-library functions @bsearch@ and @qsort@, which allow reuse of code with common functionality.
    439439However, basing all polymorphism on @void *@ eliminates the type-checker's ability to ensure that argument types are properly matched, often requiring a number of extra function parameters, pointer indirection, and dynamic allocation that is not otherwise needed.
    440440A third approach to generic code is to use preprocessor macros, which does allow the generated code to be both generic and type-checked, but errors may be difficult to interpret.
     
    526526Results of these layout functions are cached so that they are only computed once per type per function. %, as in the example below for @pair@.
    527527Layout functions also allow generic types to be used in a function definition without reflecting them in the function signature.
    528 For instance, a function that strips duplicate values from an unsorted @vector(T)@ would likely have a pointer to the vector as its only explicit parameter, but use some sort of @set(T)@ internally to test for duplicate values.
     528For instance, a function that strips duplicate values from an unsorted @vector(T)@ likely has a pointer to the vector as its only explicit parameter, but uses some sort of @set(T)@ internally to test for duplicate values.
    529529This function could acquire the layout for @set(T)@ by calling its layout function with the layout of @T@ implicitly passed into the function.
    530530
     
    796796Since @void@ is effectively a 0-element tuple, (3) discards the first and third return values, which is effectively equivalent to @[(int)(g().1.0), (int)(g().1.1)]@).
    797797
    798 Note that a cast is not a function call in \CFA, so flattening and structuring conversions do not occur for cast expressions\footnote{User-defined conversions have been considered, but for compatibility with C and the existing use of casts as type ascription, any future design for such conversions would require more precise matching of types than allowed for function arguments and parameters.}.
     798Note that a cast is not a function call in \CFA, so flattening and structuring conversions do not occur for cast expressions\footnote{User-defined conversions have been considered, but for compatibility with C and the existing use of casts as type ascription, any future design for such conversions requires more precise matching of types than allowed for function arguments and parameters.}.
    799799As such, (4) is invalid because the cast target type contains 4 components, while the source type contains only 3.
    800800Similarly, (5) is invalid because the cast @([int, int, int])(g().1)@ is invalid.
     
    11591159  case 4:
    11601160        ... `fallthrough common;`
    1161   common:
     1161  common: // below fallthrough and at same level as case clauses
    11621162        ...      // common code for cases 3 and 4
    11631163        // implicit break
     
    11671167\lstMakeShortInline@%
    11681168\end{cquote}
    1169 The target label may be case @default@.
     1169The target label must be below the @fallthrough@, \ie @fallthrough@ cannot form a loop, and the label may not be nested in a control structor, \ie it must be at the same level as the @case@ clauses;
     1170the target label may be case @default@.
    11701171
    11711172Collectively, these control-structure enhancements reduce programmer burden and increase readability and safety.
     
    14471448struct T { double m, n; };
    14481449int C::f( T & t ) {                                                     $\C{// multiple aggregate parameters}$
    1449         c; i; d;                                                                $\C{\color{red}// this-\textgreater.c, this-\textgreater.i, this-\textgreater.d}$
     1450        c; i; d;                                                                $\C{\color{red}// this--{\small\textgreater}.c, this--{\small\textgreater}.i, this--{\small\textgreater}.d}$
    14501451        `t.`m; `t.`n;                                                   $\C{// must qualify}$
    14511452}
     
    15321533                S * sp = &sv;
    15331534                with ( *sp ) {                                          $\C{computed reference}$
    1534                         i = 3; j = 4;                                   $\C{\color{red}// sp-{\textgreater}i, sp-{\textgreater}j}$
     1535                        i = 3; j = 4;                                   $\C{\color{red}// sp--{\small\textgreater}i, sp--{\small\textgreater}j}$
    15351536                }
    15361537                i = 2; j = 3;                                           $\C{\color{red}// sr.i, sr.j}$
     
    25252526The \CFA interface wraps GMP functions into operator functions to make programming with multi-precision integers identical to using fixed-sized integers.
    25262527The \CFA type name for multi-precision signed-integers is @Int@ and the header file is @gmp@.
    2527 The following multi-precision factorial programs contrast using GMP with the \CFA and C interfaces.
    2528 \begin{cquote}
     2528Figure~\ref{f:GMPInterface} shows a multi-precision factorial-program contrasting the GMP interface in \CFA and C.
     2529
     2530\begin{figure}
     2531\centering
    25292532\lstDeleteShortInline@%
    25302533\begin{tabular}{@{}l@{\hspace{\parindentlnth}}@{\hspace{\parindentlnth}}l@{}}
     
    25572560\end{tabular}
    25582561\lstMakeShortInline@%
    2559 \end{cquote}
     2562\caption{GMP Interface \CFA versus C}
     2563\label{f:GMPInterface}
     2564\end{figure}
    25602565
    25612566
     
    25662571In fact, \CFA's features for generic programming can enable faster runtime execution than idiomatic @void *@-based C code.
    25672572This claim is demonstrated through a set of generic-code-based micro-benchmarks in C, \CFA, and \CC (see stack implementations in Appendix~\ref{sec:BenchmarkStackImplementation}).
    2568 Since all these languages share a subset essentially comprising standard C, maximal-performance benchmarks would show little runtime variance, differing only in length and clarity of source code.
    2569 A more illustrative benchmark measures the costs of idiomatic usage of each language's features.
     2573Since all these languages share a subset essentially comprising standard C, maximal-performance benchmarks should show little runtime variance, differing only in length and clarity of source code.
     2574A more illustrative comparison measures the costs of idiomatic usage of each language's features.
    25702575Figure~\ref{fig:BenchmarkTest} shows the \CFA benchmark tests for a generic stack based on a singly linked-list.
    2571 The benchmark test is similar for C and \CC.
     2576The benchmark test is similar for the other languages.
    25722577The experiment uses element types @int@ and @pair(short, char)@, and pushes $N=40M$ elements on a generic stack, copies the stack, clears one of the stacks, and finds the maximum value in the other stack.
    25732578
     
    26212626\begin{tabular}{rrrrr}
    26222627                                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      & \CT{\CCV}             \\ \hline
    2623 maximum memory usage (MB)                       & 10001         & 2502          & 2503          & 11253                 \\
     2628maximum memory usage (MB)                       & 10,001        & 2,502         & 2,503         & 11,253                \\
    26242629source code size (lines)                        & 187           & 186           & 133           & 303                   \\
    26252630redundant type annotations (lines)      & 25            & 0                     & 2                     & 16                    \\
     
    26452650Raw line-count, however, is a fairly rough measure of code complexity;
    26462651another important factor is how much type information the programmer must manually specify, especially where that information is not checked by the compiler.
    2647 Such unchecked type information produces a heavier documentation burden and increased potential for runtime bugs, and is much less common in \CFA than C, with its manually specified function pointer arguments and format codes, or \CCV, with its extensive use of un-type-checked downcasts (\eg @object@ to @integer@ when popping a stack, or @object@ to @printable@ when printing the elements of a @pair@).
    2648 To quantify this, the ``redundant type annotations'' line in Table~\ref{tab:eval} counts the number of lines on which the type of a known variable is re-specified, either as a format specifier, explicit downcast, type-specific function, or by name in a @sizeof@, struct literal, or @new@ expression.
     2652Such unchecked type information produces a heavier documentation burden and increased potential for runtime bugs, and is much less common in \CFA than C, with its manually specified function pointer arguments and format codes, or \CCV, with its extensive use of untype-checked downcasts, \eg @object@ to @integer@ when popping a stack.
     2653To quantify this manual typing, the ``redundant type annotations'' line in Table~\ref{tab:eval} counts the number of lines on which the type of a known variable is respecified, either as a format specifier, explicit downcast, type-specific function, or by name in a @sizeof@, struct literal, or @new@ expression.
    26492654The \CC benchmark uses two redundant type annotations to create a new stack nodes, while the C and \CCV benchmarks have several such annotations spread throughout their code.
    2650 The \CFA benchmark was able to eliminate all redundant type annotations through use of the polymorphic @alloc@ function discussed in Section~\ref{sec:libraries}.
     2655The \CFA benchmark is able to eliminate all redundant type annotations through use of the polymorphic @alloc@ function discussed in Section~\ref{sec:libraries}.
     2656
    26512657
    26522658\section{Related Work}
     2659
    26532660
    26542661\subsection{Polymorphism}
     
    27082715Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML~\cite{sml} and~\cite{Scala}, which decompose tuples using pattern matching.
    27092716
     2717
    27102718\subsection{C Extensions}
    27112719
    2712 \CC is the best known C-based language, and similar to \CFA in that both are extensions to C with source and runtime backwards compatibility.
    2713 \CC and \CFA have been extensively compared in this paper, but the key difference between their design philosophies is that \CFA aims to be easy for C programmers to understand, by maintaining a procedural paradigm and avoiding complex interactions between extension features.
     2720\CC is the best known C-based language, and is similar to \CFA in that both are extensions to C with source and runtime backwards compatibility.
     2721Specific difference between \CFA and \CC have been identified in prior sections, with a final observation that \CFA has equal or few tokens to express the same notion in several cases.
     2722The key difference between design philosophies is that \CFA is easier for C programmers to understand, by maintaining a procedural paradigm and avoiding complex interactions among extensions.
    27142723\CC, on the other hand, has multiple overlapping features (such as the three forms of polymorphism), many of which have complex interactions with its object-oriented design.
    2715 As such, though \CC provides good runtime performance and compatibility with C, it has a steep learning curve for even experienced C programmers.
    2716 
    2717 There are many other C extension languages with less usage and dramatic changes than \CC.
     2724As a result, \CC has a steep learning curve for even experienced C programmers, especially when attempting to maintain performance equivalent to C legacy code.
     2725
     2726There are several other C extension-languages with less usage and even more dramatic changes than \CC.
    27182727Objective-C and Cyclone are two other extensions to C with different design goals than \CFA, as discussed above.
    2719 Many other languages extend C with more focused single features.
    2720 CUDA\cite{CUDA}, ispc\cite{Pharr12}, and Sierra\cite{Leissa14} add data-parallel primitives to C or \CC; such features have not yet been added to \CFA, but are not precluded by the design.
    2721 Other C extensions attempt to provide a more memory-safe C;\TODO{find some} type-checked polymorphism in \CFA covers many of C's memory-safety holes, but more aggressive approaches such as annotating all pointer types with their nullability are contradictory to \CFA's backwards compatibility goals.
    2722 
    2723 % \subsection{Control Structures / Declarations / Literals}
    2724 
    2725 % Java has default fall through like C/\CC.
    2726 % Pascal/Ada/Go/Rust do not have default fall through.
    2727 % \Csharp does not have fall through but still requires a break.
    2728 % Python uses dictionary mapping. \\
    2729 % \CFA choose is like Rust match.
    2730 
    2731 % Java has labelled break/continue. \\
    2732 % Languages with and without exception handling.
    2733 
    2734 % Alternative C declarations. \\
    2735 % Different references \\
    2736 % Constructors/destructors
    2737 
    2738 % 0/1 Literals \\
    2739 % user defined: D, Objective-C
     2728Other languages extend C with more focused features.
     2729CUDA~\cite{Nickolls08}, ispc~\cite{Pharr12}, and Sierra~\cite{Leissa14} add data-parallel primitives to C or \CC;
     2730such features have not yet been added to \CFA, but are not precluded by the design.
     2731Finaly, some C extensions (or suggested extensions) attempt to provide a more memory-safe C~\cite{Boehm88};
     2732type-checked polymorphism in \CFA covers several of C's memory-safety holes, but more aggressive approaches such as annotating all pointer types with their nullability are contradictory to \CFA's backwards compatibility goals.
     2733
     2734
     2735\begin{comment}
     2736\subsection{Control Structures / Declarations / Literals}
     2737
     2738Java has default fall through like C/\CC.
     2739Pascal/Ada/Go/Rust do not have default fall through.
     2740\Csharp does not have fall through but still requires a break.
     2741Python uses dictionary mapping. \\
     2742\CFA choose is like Rust match.
     2743
     2744Java has labelled break/continue. \\
     2745Languages with and without exception handling.
     2746
     2747Alternative C declarations. \\
     2748Different references \\
     2749Constructors/destructors
     2750
     27510/1 Literals \\
     2752user defined: D, Objective-C
     2753\end{comment}
     2754
    27402755
    27412756\section{Conclusion and Future Work}
     
    27842799
    27852800\smallskip\noindent
     2801C
     2802\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     2803struct stack_node {
     2804        void * value;
     2805        struct stack_node * next;
     2806};
     2807struct stack { struct stack_node* head; };
     2808struct stack new_stack() { return (struct stack){ NULL }; /***/ }
     2809void copy_stack( struct stack * s, const struct stack * t, void * (*copy)( const void * ) ) {
     2810        struct stack_node ** crnt = &s->head;
     2811        for ( struct stack_node * next = t->head; next; next = next->next ) {
     2812                *crnt = malloc( sizeof(struct stack_node) ); /***/
     2813                (*crnt)->value = copy( next->value );
     2814                crnt = &(*crnt)->next;
     2815        }
     2816        *crnt = NULL;
     2817}
     2818_Bool stack_empty( const struct stack * s ) { return s->head == NULL; }
     2819void push_stack( struct stack * s, void * value ) {
     2820        struct stack_node * n = malloc( sizeof(struct stack_node) ); /***/
     2821        *n = (struct stack_node){ value, s->head }; /***/
     2822        s->head = n;
     2823}
     2824void * pop_stack( struct stack * s ) {
     2825        struct stack_node * n = s->head;
     2826        s->head = n->next;
     2827        void * x = n->value;
     2828        free( n );
     2829        return x;
     2830}
     2831void clear_stack( struct stack * s, void (*free_el)( void * ) ) {
     2832        for ( struct stack_node * next = s->head; next; ) {
     2833                struct stack_node * crnt = next;
     2834                next = crnt->next;
     2835                free_el( crnt->value );
     2836                free( crnt );
     2837        }
     2838        s->head = NULL;
     2839}
     2840\end{cfa}
     2841
     2842\medskip\noindent
    27862843\CFA
    27872844\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     
    28172874        stack_node(T) * n = head;
    28182875        head = n->next;
    2819         T x = n->value;
     2876        T v = n->value;
    28202877        ^(*n){};
    28212878        free( n );
    2822         return x;
     2879        return v;
    28232880}
    28242881forall( otype T ) void clear( stack(T) & s ) with( s ) {
     
    28402897                T value;
    28412898                node * next;
    2842                 node( const T & v, node * n = nullptr ) : value(v), next(n) {}
     2899                node( const T & v, node * n = nullptr ) : value( v), next( n) {}
    28432900        };
    28442901        node * head;
    2845         void copy(const stack<T> & o) {
     2902        void copy( const stack<T> & o) {
    28462903                node ** crnt = &head;
    28472904                for ( node * next = o.head;; next; next = next->next ) {
     
    28512908                *crnt = nullptr;
    28522909        }
    2853         stack() : head(nullptr) {}
    2854         stack(const stack<T> & o) { copy(o); }
    2855         stack(stack<T> && o) : head(o.head) { o.head = nullptr; }
     2910        stack() : head( nullptr) {}
     2911        stack( const stack<T> & o) { copy( o); }
     2912        stack( stack<T> && o) : head( o.head) { o.head = nullptr; }
    28562913        ~stack() { clear(); }
    2857         stack & operator= (const stack<T> & o) {
     2914        stack & operator= ( const stack<T> & o) {
    28582915                if ( this == &o ) return *this;
    28592916                clear();
    2860                 copy(o);
     2917                copy( o);
    28612918                return *this;
    28622919        }
    2863         stack & operator= (stack<T> && o) {
     2920        stack & operator= ( stack<T> && o) {
    28642921                if ( this == &o ) return *this;
    28652922                head = o.head;
     
    28682925        }
    28692926        bool empty() const { return head == nullptr; }
    2870         void push(const T & value) { head = new node{ value, head };  /***/ }
     2927        void push( const T & value) { head = new node{ value, head };  /***/ }
    28712928        T pop() {
    28722929                node * n = head;
    28732930                head = n->next;
    2874                 T x = std::move(n->value);
     2931                T x = std::move( n->value);
    28752932                delete n;
    28762933                return x;
     
    28882945
    28892946\medskip\noindent
    2890 C
    2891 \begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    2892 struct stack_node {
    2893         void * value;
    2894         struct stack_node * next;
    2895 };
    2896 struct stack { struct stack_node* head; };
    2897 struct stack new_stack() { return (struct stack){ NULL }; /***/ }
    2898 void copy_stack(struct stack * s, const struct stack * t, void * (*copy)(const void *)) {
    2899         struct stack_node ** crnt = &s->head;
    2900         for ( struct stack_node * next = t->head; next; next = next->next ) {
    2901                 *crnt = malloc(sizeof(struct stack_node)); /***/
    2902                 (*crnt)->value = copy(next->value);
    2903                 crnt = &(*crnt)->next;
    2904         }
    2905         *crnt = NULL;
    2906 }
    2907 _Bool stack_empty(const struct stack * s) { return s->head == NULL; }
    2908 void push_stack(struct stack * s, void * value) {
    2909         struct stack_node * n = malloc(sizeof(struct stack_node)); /***/
    2910         *n = (struct stack_node){ value, s->head }; /***/
    2911         s->head = n;
    2912 }
    2913 void * pop_stack(struct stack * s) {
    2914         struct stack_node * n = s->head;
    2915         s->head = n->next;
    2916         void * x = n->value;
    2917         free(n);
    2918         return x;
    2919 }
    2920 void clear_stack(struct stack * s, void (*free_el)(void *)) {
    2921         for ( struct stack_node * next = s->head; next; ) {
    2922                 struct stack_node * crnt = next;
    2923                 next = crnt->next;
    2924                 free_el(crnt->value);
    2925                 free(crnt);
    2926         }
    2927         s->head = NULL;
    2928 }
    2929 \end{cfa}
    2930 
    2931 \medskip\noindent
    29322947\CCV
    29332948\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     
    29392954        };
    29402955        node* head;
    2941         void copy(const stack & o) {
     2956        void copy( const stack & o ) {
    29422957                node ** crnt = &head;
    29432958                for ( node * next = o.head; next; next = next->next ) {
     
    29472962                *crnt = nullptr;
    29482963        }
    2949         stack() : head(nullptr) {}
    2950         stack(const stack & o) { copy(o); }
    2951         stack(stack && o) : head(o.head) { o.head = nullptr; }
     2964        stack() : head( nullptr ) {}
     2965        stack( const stack & o ) { copy( o ); }
     2966        stack( stack && o ) : head( o.head ) { o.head = nullptr; }
    29522967        ~stack() { clear(); }
    2953         stack & operator= (const stack & o) {
     2968        stack & operator= ( const stack & o ) {
    29542969                if ( this == &o ) return *this;
    29552970                clear();
    2956                 copy(o);
     2971                copy( o );
    29572972                return *this;
    29582973        }
    2959         stack & operator= (stack && o) {
     2974        stack & operator= ( stack && o ) {
    29602975                if ( this == &o ) return *this;
    29612976                head = o.head;
     
    29642979        }
    29652980        bool empty() const { return head == nullptr; }
    2966         void push(const object & value) { head = new node{ value, head }; /***/ }
     2981        void push( const object & value ) { head = new node{ value, head }; /***/ }
    29672982        ptr<object> pop() {
    29682983                node * n = head;
    29692984                head = n->next;
    2970                 ptr<object> x = std::move(n->value);
     2985                ptr<object> x = std::move( n->value );
    29712986                delete n;
    29722987                return x;
  • doc/papers/general/evaluation/cfa-stack.c

    rdeb52a0 r29db723  
    22#include "cfa-stack.h"
    33
    4 forall(otype T) struct stack_node {
     4forall( otype T ) struct stack_node {
    55        T value;
    66        stack_node(T) * next;
    77};
    88
    9 forall(otype T) void ?{}( stack(T) & s ) { (s.head){ 0 }; }
     9forall( otype T ) void ?{}( stack(T) & s ) { (s.head){ 0 }; }
    1010
    11 forall(otype T) void ?{}( stack(T) & s, stack(T) t ) {
     11forall( otype T ) void ?{}( stack(T) & s, stack(T) t ) {
    1212        stack_node(T) ** crnt = &s.head;
    1313        for ( stack_node(T) * next = t.head; next; next = next->next ) {
     
    1919}
    2020
    21 forall(otype T) stack(T) ?=?( stack(T) & s, stack(T) t ) {
     21forall( otype T ) stack(T) ?=?( stack(T) & s, stack(T) t ) {
    2222        if ( s.head == t.head ) return s;
    2323        clear( s );
     
    2626}
    2727
    28 forall(otype T) void ^?{}( stack(T) & s) { clear( s ); }
     28forall( otype T ) void ^?{}( stack(T) & s) { clear( s ); }
    2929
    30 forall(otype T) _Bool empty( const stack(T) & s ) { return s.head == 0; }
     30forall( otype T ) _Bool empty( const stack(T) & s ) { return s.head == 0; }
    3131
    32 forall(otype T) void push( stack(T) & s, T value ) with( s ) {
    33         stack_node(T)* n = alloc();
     32forall( otype T ) void push( stack(T) & s, T value ) with( s ) {
     33        stack_node(T) * n = alloc();
    3434        (*n){ value, head };
    3535        head = n;
    3636}
    3737
    38 forall(otype T) T pop( stack(T) & s ) with( s ) {
     38forall( otype T ) T pop( stack(T) & s ) with( s ) {
    3939        stack_node(T) * n = head;
    4040        head = n->next;
    41         T x = n->value;
     41        T v = n->value;
    4242        ^(*n){};
    4343        free( n );
    44         return x;
     44        return v;
    4545}
    4646
    47 forall(otype T) void clear( stack(T) & s ) with( s ) {
     47forall( otype T ) void clear( stack(T) & s ) with( s ) {
    4848        for ( stack_node(T) * next = head; next; ) {
    4949                stack_node(T) * crnt = next;
  • doc/papers/general/evaluation/cfa-stack.h

    rdeb52a0 r29db723  
    11#pragma once
    22
    3 forall(otype T) struct stack_node;
    4 forall(otype T) struct stack {
     3forall( otype T ) struct stack_node;
     4forall( otype T ) struct stack {
    55        stack_node(T) * head;
    66};
    77
    8 forall(otype T) void ?{}( stack(T) & s );
    9 forall(otype T) void ?{}( stack(T) & s, stack(T) t );
    10 forall(otype T) stack(T) ?=?( stack(T) & s, stack(T) t );
    11 forall(otype T) void ^?{}( stack(T) & s);
     8forall( otype T ) void ?{}( stack(T) & s );
     9forall( otype T ) void ?{}( stack(T) & s, stack(T) t );
     10forall( otype T ) stack(T) ?=?( stack(T) & s, stack(T) t );
     11forall( otype T ) void ^?{}( stack(T) & s);
    1212
    13 forall(otype T) _Bool empty( const stack(T) & s );
    14 forall(otype T) void push( stack(T) & s, T value );
    15 forall(otype T) T pop( stack(T) & s );
    16 forall(otype T) void clear( stack(T) & s );
     13forall( otype T ) _Bool empty( const stack(T) & s );
     14forall( otype T ) void push( stack(T) & s, T value );
     15forall( otype T ) T pop( stack(T) & s );
     16forall( otype T ) void clear( stack(T) & s );
  • doc/papers/general/evaluation/timing.gp

    rdeb52a0 r29db723  
    2222SCALE=1000
    2323set ylabel "seconds"
     24set yrange [0:10]
     25
     26set label "26.5" at 7.125,10.5
    2427
    2528# set datafile separator ","
Note: See TracChangeset for help on using the changeset viewer.