Index: doc/generic_types/generic_types.tex =================================================================== --- doc/generic_types/generic_types.tex (revision 95448f1e9cef1312f404625850e6cab6ad970153) +++ doc/generic_types/generic_types.tex (revision 6a86a0abb435b309d7e6353af17bf713dccd18bb) @@ -148,5 +148,5 @@ \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; such functions are written using a @forall@ clause (which gives 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; such functions are written using a @forall@ clause (which gives the language its name): \begin{lstlisting} forall(otype T) @@ -174,6 +174,6 @@ forall(otype S | { S ?+?(S, S); }) S twice(S x) { return x + x; } // (2) -\end{lstlisting} -This version of @twice@ works for any type @S@ that has an addition operator defined for it, and it could have been used to satisfy the type assertion on @four_times@. +\end{lstlisting} +This version of @twice@ works for any type @S@ that has an addition operator defined for it, and it could have been used to satisfy the type assertion on @four_times@. The translator accomplishes this polymorphism by creating a wrapper function calling @twice // (2)@ with @S@ bound to @double@, then providing this wrapper function to @four_times@\footnote{\lstinline@twice // (2)@ could also have had a type parameter named \lstinline@T@; \CFA{} specifies renaming of the type parameters, which would avoid the name conflict with the type variable \lstinline@T@ of \lstinline@four_times@.}. @@ -196,5 +196,5 @@ forall(otype M | has_magnitude(M)) M max_magnitude( M a, M b ) { - return abs(a) < abs(b) ? b : a; + return abs(a) < abs(b) ? b : a; } \end{lstlisting} @@ -213,9 +213,9 @@ Given the information provided for an @otype@, variables of polymorphic type can be treated as if they were a complete struct type -- they can be stack-allocated using the @alloca@ compiler builtin, default or copy-initialized, assigned, and deleted. As an example, the @abs@ function above produces generated code something like the following (simplified for clarity and brevity): \begin{lstlisting} -void abs( size_t _sizeof_M, size_t _alignof_M, - void (*_ctor_M)(void*), void (*_copy_M)(void*, void*), - void (*_assign_M)(void*, void*), void (*_dtor_M)(void*), - bool (*_lt_M)(void*, void*), void (*_neg_M)(void*, void*), - void (*_ctor_M_zero)(void*, int), +void abs( size_t _sizeof_M, size_t _alignof_M, + void (*_ctor_M)(void*), void (*_copy_M)(void*, void*), + void (*_assign_M)(void*, void*), void (*_dtor_M)(void*), + bool (*_lt_M)(void*, void*), void (*_neg_M)(void*, void*), + void (*_ctor_M_zero)(void*, int), void* m, void* _rtn ) { // polymorphic parameter and return passed as void* // M zero = { 0 }; @@ -223,5 +223,5 @@ _ctor_M_zero(zero, 0); // initialize using zero_t constructor // return m < zero ? -m : m; - void *_tmp = alloca(_sizeof_M) + void *_tmp = alloca(_sizeof_M); _copy_M( _rtn, // copy-initialize return value _lt_M( m, zero ) ? // check condition @@ -323,5 +323,5 @@ In some cases the offset arrays cannot be statically generated. For instance, modularity is generally provided in C by including an opaque forward-declaration of a struct and associated accessor and mutator routines in a header file, with the actual implementations in a separately-compiled \texttt{.c} file. \CFA{} supports this pattern for generic types, and in this instance the caller does not know the actual layout or size of the dynamic generic type, and only holds it by pointer. The \CFA{} translator automatically generates \emph{layout functions} for cases where the size, alignment, and offset array of a generic struct cannot be passed in to a function from that function's caller. These layout functions take as arguments pointers to size and alignment variables and a caller-allocated array of member offsets, as well as the size and alignment of all @sized@ parameters to the generic struct (un-@sized@ parameters are forbidden from the language from being used in a context that affects layout). Results of these layout functions are cached so that they are only computed once per type per function.%, as in the example below for @pair@. % \begin{lstlisting} -% static inline void _layoutof_pair(size_t* _szeof_pair, size_t* _alignof_pair, size_t* _offsetof_pair, +% static inline void _layoutof_pair(size_t* _szeof_pair, size_t* _alignof_pair, size_t* _offsetof_pair, % size_t _szeof_R, size_t _alignof_R, size_t _szeof_S, size_t _alignof_S) { % *_szeof_pair = 0; // default values @@ -332,5 +332,5 @@ % *_szeof_pair += _szeof_R; % if ( *_alignof_pair < _alignof_R ) *_alignof_pair = _alignof_R; - + % // padding, offset, size, and alignment of second field % if ( *_szeof_pair & (_alignof_S - 1) ) @@ -754,5 +754,5 @@ f(x.field_0, (_tuple2){ x.field_1, 'z' }); \end{lstlisting} -Note that due to flattening, @x@ used in the argument position is converted into the list of its fields. In the call to @f@, a the second and third argument components are structured into a tuple argument. Similarly, tuple member expressions are recursively expanded into a list of member access expressions. +Note that due to flattening, @x@ used in the argument position is converted into the list of its fields. In the call to @f@, the second and third argument components are structured into a tuple argument. Similarly, tuple member expressions are recursively expanded into a list of member access expressions. Expressions that may contain side effects are made into \emph{unique expressions} before being expanded by the flattening conversion. Each unique expression is assigned an identifier and is guaranteed to be executed exactly once: @@ -774,5 +774,5 @@ ); \end{lstlisting} -Since argument evaluation order is not specified by the C programming language, this scheme is built to work regardless of evaluation order. The first time a unique expression is executed, the actual expression is evaluated and the accompanying boolean is true to true. Every subsequent evaluation of the unique expression then results in an access to the stored result of the actual expression. Tuple member expressions also take advantage of unique expressions in the case of possible impurity. +Since argument evaluation order is not specified by the C programming language, this scheme is built to work regardless of evaluation order. The first time a unique expression is executed, the actual expression is evaluated and the accompanying boolean is set to true. Every subsequent evaluation of the unique expression then results in an access to the stored result of the actual expression. Tuple member expressions also take advantage of unique expressions in the case of possible impurity. Currently, the \CFA{} translator has a very broad, imprecise definition of impurity, where any function call is assumed to be impure. This notion could be made more precise for certain intrinsic, auto-generated, and builtin functions, and could analyze function bodies when they are available to recursively detect impurity, to eliminate some unique expressions.