Changeset 7042c60
- Timestamp:
- Apr 25, 2024, 3:48:17 PM (7 months ago)
- Branches:
- master
- Children:
- eb7586e
- Parents:
- cf191ac (diff), 55c97e4 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)
links above to see all the changes relative to each parent. - Files:
-
- 1 added
- 1 deleted
- 46 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/LaTeXmacros/common.sty
rcf191ac r7042c60 11 11 %% Created On : Sat Apr 9 10:06:17 2016 12 12 %% Last Modified By : Peter A. Buhr 13 %% Last Modified On : Sun Feb 25 23:30:09202414 %% Update Count : 6 4513 %% Last Modified On : Thu Apr 18 09:14:02 2024 14 %% Update Count : 657 15 15 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 16 16 … … 108 108 \renewcommand\subparagraph{\@startsection{subparagraph}{4}{\z@}{-1.5ex \@plus -1ex \@minus -.2ex}{-1em}{\normalfont\normalsize\bfseries\itshape}} 109 109 110 % index macros111 110 \newcommand{\italic}[1]{\emph{\hyperpage{#1}}} 112 111 \newcommand{\Definition}[1]{\textbf{\hyperpage{#1}}} 113 \newcommand{\see}[1]{(see #1)} 112 \newcommand{\see}{\protect\@ifstar\@ssee\@see} 113 \newcommand{\@ssee}[1]{(See #1)} 114 \newcommand{\@see}[1]{(see #1)} 115 116 % index macros 114 117 115 118 % Define some commands that produce formatted index entries suitable for cross-references. … … 152 155 \newcommand{\newtermFontInline}{\emph} 153 156 \newcommand{\newterm}{\protect\@ifstar\@snewterm\@newterm} 157 \newcommand{\@snewterm}[2][\@empty]{{\newtermFontInline{#2}}\ifx#1\@empty\index{#2}\else\index{#1@{\protect#2}}\fi} 154 158 \newcommand{\@newterm}[2][\@empty]{\lowercase{\def\temp{#2}}{\newtermFontInline{#2}}\ifx#1\@empty\index{\temp}\else\index{#1@{\protect#2}}\fi} 155 \newcommand{\@snewterm}[2][\@empty]{{\newtermFontInline{#2}}\ifx#1\@empty\index{#2}\else\index{#1@{\protect#2}}\fi}156 159 157 160 % \snake{<identifier>} … … 202 205 203 206 \newenvironment{cquote}{% 204 \list{}{\ lstset{resetmargins=true,aboveskip=0pt,belowskip=0pt}\topsep=4pt\parsep=0pt\leftmargin=\parindentlnth\rightmargin\leftmargin}%207 \list{}{\topsep=\lst@aboveskip\parskip=0pt\partopsep=0pt\itemsep=0pt\parsep=0pt\listparindent=0pt\leftmargin=\parindentlnth\rightmargin=0pt}% 205 208 \item\relax 209 \lstset{resetmargins=true} 206 210 }{% 207 211 \endlist … … 345 349 \fi% 346 350 351 \usepackage{tabularx} % if @ is used for lstMakeShortInline, allows @{} 352 347 353 % Local Variables: % 348 354 % tab-width: 4 % -
doc/LaTeXmacros/common.tex
rcf191ac r7042c60 11 11 %% Created On : Sat Apr 9 10:06:17 2016 12 12 %% Last Modified By : Peter A. Buhr 13 %% Last Modified On : Mon Feb 26 08:06:05202414 %% Update Count : 6 1513 %% Last Modified On : Thu Apr 18 09:15:38 2024 14 %% Update Count : 664 15 15 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 16 16 … … 109 109 \renewcommand\subparagraph{\@startsection{subparagraph}{4}{\z@}{-1.5ex \@plus -1ex \@minus -.2ex}{-1em}{\normalfont\normalsize\bfseries\itshape}} 110 110 111 % index macros112 111 \newcommand{\italic}[1]{\emph{\hyperpage{#1}}} 113 112 \newcommand{\Definition}[1]{\textbf{\hyperpage{#1}}} 114 \newcommand{\see}[1]{(see #1)} 113 \newcommand{\see}{\protect\@ifstar\@ssee\@see} 114 \newcommand{\@ssee}[1]{(See #1)} 115 \newcommand{\@see}[1]{(see #1)} 116 117 % index macros 115 118 116 119 % Define some commands that produce formatted index entries suitable for cross-references. … … 153 156 \newcommand{\newtermFontInline}{\emph} 154 157 \newcommand{\newterm}{\protect\@ifstar\@snewterm\@newterm} 158 \newcommand{\@snewterm}[2][\@empty]{{\newtermFontInline{#2}}\ifx#1\@empty\index{#2}\else\index{#1@{\protect#2}}\fi} 155 159 \newcommand{\@newterm}[2][\@empty]{\lowercase{\def\temp{#2}}{\newtermFontInline{#2}}\ifx#1\@empty\index{\temp}\else\index{#1@{\protect#2}}\fi} 156 \newcommand{\@snewterm}[2][\@empty]{{\newtermFontInline{#2}}\ifx#1\@empty\index{#2}\else\index{#1@{\protect#2}}\fi}157 160 158 161 % \snake{<identifier>} … … 201 204 \newcommand{\VS}{\abbrevFont{vs}} 202 205 \newcommand{\vs}{\VS\CheckPeriod} 203 \makeatother204 206 205 207 \newenvironment{cquote}{% 206 \list{}{\ lstset{resetmargins=true,aboveskip=0pt,belowskip=0pt}\topsep=4pt\parsep=0pt\leftmargin=\parindentlnth\rightmargin\leftmargin}%208 \list{}{\topsep=\lst@aboveskip\parskip=0pt\partopsep=0pt\itemsep=0pt\parsep=0pt\listparindent=0pt\leftmargin=\parindentlnth\rightmargin=0pt}% 207 209 \item\relax 210 \lstset{resetmargins=true} 208 211 }{% 209 212 \endlist 210 213 }% cquote 214 \makeatother 211 215 212 216 \newenvironment{rationale}{% … … 349 353 \fi% 350 354 355 \usepackage{tabularx} % if @ is used for lstMakeShortInline, allows @{} 356 351 357 % Local Variables: % 352 358 % tab-width: 4 % -
doc/LaTeXmacros/lstlang.sty
rcf191ac r7042c60 8 8 %% Created On : Sat May 13 16:34:42 2017 9 9 %% Last Modified By : Peter A. Buhr 10 %% Last Modified On : Tue Mar 12 17:29:58202411 %% Update Count : 4 210 %% Last Modified On : Mon Apr 15 11:28:44 2024 11 %% Update Count : 43 12 12 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 13 13 … … 116 116 alignas, _Alignas, alignof, _Alignof, __alignof, __alignof__, and, asm, __asm, __asm__, _Atomic, __attribute, __attribute__, 117 117 __auto_type, basetypeof, _Bool, catch, catchResume, choose, coerce, corun, cofor, _Complex, __complex, __complex__, 118 __const, __const__, continue, _Decimal32, _Decimal64, _Decimal128, disable, dtype, enable, exception, __extension__,118 __const, __const__, continue, coroutine, _Decimal32, _Decimal64, _Decimal128, disable, dtype, enable, exception, __extension__, 119 119 fallthrough, fallthru, finally, fixup, __float80, float80, __float128, float128, _Float16, _Float32, _Float32x, _Float64, 120 120 _Float64x, _Float128, _Float128x, forall, fortran, ftype, generator, _Generic, _Imaginary, __imag, __imag__, inline, -
doc/bibliography/pl.bib
rcf191ac r7042c60 519 519 year = 1963, 520 520 pages = {1-17}, 521 } 522 523 @misc{AlgolW, 524 keywords = {AlgolW}, 525 contributer = {pabuhr@plg}, 526 author = {Henry Bauer and Sheldon Becker and Susan L. Graham and Edwin Satterthwaite and Richard L. Sites}, 527 title = {{Algol W} Language Description}, 528 month = jun, 529 year = 1972, 530 howpublished= {\url{https://www.algol60.org/docsW/algolw.pdf}}, 521 531 } 522 532 -
doc/theses/jiada_liang_MMath/CFAenum.tex
rcf191ac r7042c60 137 137 \section{Pure Enumerators} 138 138 139 An empty enumerator type, @enum()@, implies the enumerators are pure symbols without values but set properties;139 An empty enumerator type, @enum()@, implies the enumerators are opaque symbols without values but set properties; 140 140 hence, there is no default conversion to @int@. 141 141 -
doc/theses/jiada_liang_MMath/Makefile
rcf191ac r7042c60 13 13 BibSRC = ${wildcard *.bib} 14 14 15 TeXLIB = .:${LaTMac}:${Build}: 16 BibLIB = .:${BibRep}: 15 TeXLIB = .:${LaTMac}:${Build}: # common latex macros 16 BibLIB = .:${BibRep}: # common citation repository 17 17 18 18 MAKEFLAGS = --no-print-directory # --silent -
doc/theses/jiada_liang_MMath/background.tex
rcf191ac r7042c60 1 1 \chapter{Background} 2 \lstnewenvironment{clang}[1][]{\lstset{language=[ANSI]C,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{}3 2 4 3 \CFA is a backwards-compatible extension of the C programming language. … … 48 47 49 48 \section{C Enumeration} 49 \label{s:CEnumeration} 50 50 51 The C enumeration has the following syntax and semantics. 51 The C enumeration has the following syntax~\cite[\S~6.7.2.2]{C11}. 52 \begin{clang}[identifierstyle=\linespread{0.9}\it] 53 $\it enum$-specifier: 54 enum identifier$\(_{opt}\)$ { enumerator-list } 55 enum identifier$\(_{opt}\)$ { enumerator-list , } 56 enum identifier 57 enumerator-list: 58 enumerator 59 enumerator-list , enumerator 60 enumerator: 61 enumeration-constant 62 enumeration-constant = constant-expression 63 \end{clang} 64 The terms \emph{enumeration} and \emph{enumerator} used in this work \see{\VRef{s:Terminology}} come from the grammar. 65 The C enumeration semantics is discussed using examples. 66 67 An unnamed enumeration is used to provide secondary renaming, like a @const@ declaration in other languages. 68 \begin{clang} 69 enum { Size = 20, Pi = 3.14159 }; // unnamed enumeration $\(\Rightarrow\)$ no ordering 70 \end{clang} 71 This declaration form is not an enumeration even though it is declared using an @enum@ because it has none of the following enumeration properties. 72 73 A \emph{named} enumeration type is an actual enumeration. 52 74 \begin{clang} 53 75 enum Weekday { Mon, Tue, Wed, Thu@ = 10@, Fri, Sat, Sun, }; -
doc/theses/jiada_liang_MMath/intro.tex
rcf191ac r7042c60 1 1 \chapter{Introduction} 2 2 3 All types in a programming language must have a set of constants, and these constants have \Newterm{primary names}, \eg integral types have constants @-1@, @17@, @12345@, \etc. 4 Constants can be overloaded among types, \eg @0@ is a null pointer for all pointer types, and the value zero for integral and floating-point types. 3 All types in a programming language must have a set of constants, and these constants have \Newterm{primary names}, \eg integral types have constants @-1@, @17@, @0xff@, floating-point types have constants @5.3@, @2.3E-5@, @0xff.ffp0@, character types have constants @'a'@, @"abc\n"@, \mbox{\lstinline{u8"}\texttt{\guillemotleft{na\"{i}ve}\guillemotright}\lstinline{"}}, \etc. 4 Con\-stants can be overloaded among types, \eg @0@ is a null pointer for all pointer types, and the value zero for integral and floating-point types. 5 (In \CFA, the primary constants @0@ and @1@ can be overloaded for any type.) 5 6 Hence, each primary constant has a symbolic name referring to its internal representation, and these names are dictated by language syntax related to types. 6 In theory, there are an infinite set of primary names per type.7 8 \Newterm{Secondary naming} is a common practice in mathematics and engineering, \eg $\pi$, $\tau$ (2$\pi$), $\phi$ (golden ratio), MHz (1E6), and in general situations, \eg specific times (noon, New Years), cities (Big Apple), flowers (Lily), \etc.7 In theory, there are an infinite set of primary constant names per type. 8 9 \Newterm{Secondary naming} is a common practice in mathematics, engineering and computer science, \eg $\pi$, $\tau$ (2$\pi$), $\phi$ (golden ratio), MB (megabyte, 1E6), and in general situations, \eg specific times (noon, New Years), cities (Big Apple), flowers (Lily), \etc. 9 10 Many programming languages capture this important software-engineering capability through a mechanism called \Newterm{constant} or \Newterm{literal} naming, where a secondary name is aliased to a primary name. 10 In some cases, secondary naming is \Newterm{pure}, where the matching internal representation can be chosen arbitrarily, and only equality operations are available, \eg @O_RDONLY@, @O_WRONLY@, @O_CREAT@, @O_TRUNC@, @O_APPEND@. 11 (The names the thing.) 11 Its purpose is for readability and to eliminate duplication of the primary constant throughout a program. 12 For example, a meaningful secondary name replaces a primary name throughout a program; 13 thereafter, changing the binding of the secondary to primary name automatically distributes the rebinding, preventing errors. 14 In some cases, secondary naming is \Newterm{opaque}, where the matching internal representation can be chosen arbitrarily, and only equality operations are available, \eg @O_RDONLY@, @O_WRONLY@, @O_CREAT@, @O_TRUNC@, @O_APPEND@. 12 15 Because a secondary name is a constant, it cannot appear in a mutable context, \eg \mbox{$\pi$ \lstinline{= 42}} is meaningless, and a constant has no address, \ie it is an \Newterm{rvalue}\footnote{ 13 16 The term rvalue defines an expression that can only appear on the right-hand side of an assignment expression.}. 14 17 15 Secondary names can form an (ordered) set, \eg days of theweek, months of a year, floors of a building (basement, ground, 1st), colours in a rainbow, \etc.18 Secondary names can form an (ordered) set, \eg days of a week, months of a year, floors of a building (basement, ground, 1st), colours in a rainbow, \etc. 16 19 Many programming languages capture these groupings through a mechanism called an \Newterm{enumeration}. 17 20 \begin{quote} 18 21 enumerate (verb, transitive). 19 22 To count, ascertain the number of; 20 \emph{more 21 usually, to mention (a number of things or persons) separately, as if for the 22 purpose of counting}; 23 to specify as in a list or catalogue.~\cite{OED} 23 more usually, to mention (a number of things or persons) separately, as if for the purpose of counting; 24 to specify as in a list or catalogue.~\cite{OEDenumerate} 24 25 \end{quote} 25 Within an enumeration set, the enumeration names must be unique, and instances of an enumerated type are restricted to hold only the secondary names.26 Within an enumeration set, the enumeration names must be unique, and instances of an enumerated type are \emph{often} restricted to hold only the secondary names. 26 27 It is possible to enumerate among set names without having an ordering among the set elements. 27 28 For example, the week, the weekdays, the weekend, and every second day of the week. … … 29 30 for ( cursor in Mon, Tue, Wed, Thu, Fri, Sat, Sun } ... $\C[3.75in]{// week}$ 30 31 for ( cursor in Mon, Tue, Wed, Thu, Fri } ... $\C{// weekday}$ 31 for ( cursor in Thu, Fri} ... $\C{// weekend}$32 for ( cursor in Sat, Sun } ... $\C{// weekend}$ 32 33 for ( cursor in Mon, Wed, Fri, Sun } ... $\C{// every second day of week}\CRT$ 33 34 \end{cfa} 34 This independence from internal representation allows multiple names to have the same representation (eight note, quaver), giving synonyms.35 This independence from internal representation allows multiple names to have the same representation (eighth note, quaver), giving synonyms. 35 36 A set can have a partial or total ordering, making it possible to compare set elements, \eg Monday is before Friday and Friday is after. 36 Ordering allows iterating among the enumeration set using relational operators and advancement, \eg 37 Ordering allows iterating among the enumeration set using relational operators and advancement, \eg: 37 38 \begin{cfa} 38 39 for ( cursor = Monday; cursor @<=@ Friday; cursor = @succ@( cursor ) ) ... 39 40 \end{cfa} 40 Here the internal representations for the secondary names are \emph{generated} rather than listing a subset of names. 41 Here the internal representation for the secondary names are logically \emph{generated} rather than listing a subset of names. 42 43 Hence, the fundamental aspects of an enumeration are: 44 \begin{enumerate} 45 \item 46 \begin{sloppypar} 47 It provides a finite set of secondary names, which become its primary constants. 48 This differentiates an enumeration from general types with an infinite set 49 of primary constants. 50 \end{sloppypar} 51 \item 52 The secondary names are constants, which follows transitively from their binding (aliasing) to primary names, which are constants. 53 \item 54 Defines a type for generating instants (variables). 55 \item 56 For safety, an enumeration instance should be restricted to hold only its type's secondary names. 57 \item 58 There is a mechanism for \emph{enumerating} over the secondary names, where the ordering can be implicit from the type, explicitly listed, or generated arithmetically. 59 \end{enumerate} 41 60 42 61 43 62 \section{Terminology} 44 45 The term \Newterm{enumeration} defines the set of secondary names, and the term \Newterm{enumerator} represents an arbitrary secondary name. 46 As well, an enumerated type has three fundamental properties, \Newterm{label}, \Newterm{order}, and \Newterm{value}. 63 \label{s:Terminology} 64 65 The term \Newterm{enumeration} defines a type with a set of secondary names, and the term \Newterm{enumerator} represents an arbitrary secondary name \see{\VRef{s:CEnumeration} for the name derivation}. 66 As well, an enumerated type can have three fundamental properties, \Newterm{label}, \Newterm{order}, and \Newterm{value}. 47 67 \begin{cquote} 48 68 \sf\setlength{\tabcolsep}{3pt} 49 69 \begin{tabular}{rcccccccr} 50 70 \it\color{red}enumeration & \multicolumn{8}{c}{\it\color{red}enumerators} \\ 51 $\downarrow$\hspace*{ 25pt} & \multicolumn{8}{c}{$\downarrow$} \\52 @enum@ Week \{ & Mon, & Tue, & Wed, & Thu, & Fri, & Sat, & Sun = 42& \}; \\71 $\downarrow$\hspace*{15pt} & \multicolumn{8}{c}{$\downarrow$} \\ 72 @enum@ Week \{ & Mon, & Tue, & Wed, & Thu, & Fri, & Sat, & Sun {\color{red}= 42} & \}; \\ 53 73 \it\color{red}label & Mon & Tue & Wed & Thu & Fri & Sat & Sun & \\ 54 74 \it\color{red}order & 0 & 1 & 2 & 3 & 4 & 5 & 6 & \\ 55 \it\color{red}value & 0 & 1 & 2 & 3 & 4 & 5 & 42&75 \it\color{red}value & 0 & 1 & 2 & 3 & 4 & 5 & {\color{red}42} & 56 76 \end{tabular} 57 77 \end{cquote} … … 72 92 \section{Motivation} 73 93 74 Some programming languages only provide secondary renaming, which can be simulated by an enumeration without ordering. 75 \begin{cfa} 76 const Size = 20, Pi = 3.14159; 77 enum { Size = 20, Pi = 3.14159 }; // unnamed enumeration $\(\Rightarrow\)$ no ordering 78 \end{cfa} 79 In both cases, it is possible to compare the secondary names, \eg @Size < Pi@, if that is meaningful; 80 however, without an enumeration type-name, it is impossible to create an iterator cursor. 81 82 Secondary renaming can similate an enumeration, but with extra effort. 94 Many programming languages provide an enumeration-like mechanism, which may or may not cover the previous five fundamental enumeration aspects. 95 Hence, the term \emph{enumeration} can be confusing and misunderstood. 96 Furthermore, some languages conjoin the enumeration with other type features, making it difficult to tease apart which featuring is being used. 97 This section discusses some language features that are sometimes called an enumeration but do not provide all enumeration aspects. 98 99 100 \subsection{Aliasing} 101 102 Some languages provide simple secondary aliasing (renaming), \eg: 103 \begin{cfa} 104 const Size = 20, Pi = 3.14159, Name = "Jane"; 105 \end{cfa} 106 The secondary name is logically replaced in the program text by its corresponding primary name. 107 Therefore, it is possible to compare the secondary names, \eg @Size < Pi@, only because the primary constants allow it, whereas \eg @Pi < Name@ might be disallowed depending on the language. 108 109 Aliasing is not macro substitution, \eg @#define Size 20@, where a name is replaced by its value \emph{before} compilation, so the name is invisible to the programming language. 110 With aliasing, each secondary name is part of the language, and hence, participates fully, such as name overloading in the type system. 111 Aliasing is not an immutable variable, \eg: 112 \begin{cfa} 113 extern @const@ int Size = 20; 114 extern void foo( @const@ int @&@ size ); 115 foo( Size ); // take the address of (reference) Size 116 \end{cfa} 117 Taking the address of an immutable variable makes it an \Newterm{lvalue}, which implies it has storage. 118 With separate compilation, it is necessary to choose one translation unit to perform the initialization. 119 If aliasing does require storage, its address and initialization are opaque (compiler only), similar to \CC rvalue reference @&&@. 120 121 Aliasing does provide readability and automatic resubstitution. 122 It also provides simple enumeration properties, but with extra effort. 83 123 \begin{cfa} 84 124 const Mon = 1, Tue = 2, Wed = 3, Thu = 4, Fri = 5, Sat = 6, Sun = 7; 85 125 \end{cfa} 86 Furthermore, reorderingthe enumerators requires manual renumbering.126 Any reordering of the enumerators requires manual renumbering. 87 127 \begin{cfa} 88 128 const Sun = 1, Mon = 2, Tue = 3, Wed = 4, Thu = 5, Fri = 6, Sat = 7; 89 129 \end{cfa} 90 Finally, there is no common type to create a type-checked instance or iterator cursor. 91 Hence, there is only a weak equivalence between secondary naming and enumerations, justifying the enumeration type in a programming language. 92 93 A variant (algebraic) type is often promoted as a kind of enumeration, \ie a varient type can simulate an enumeration. 94 A variant type is a tagged-union, where the possible types may be heterogeneous. 95 \begin{cfa} 96 @variant@ Variant { 97 @int tag;@ // optional/implicit: 0 => int, 1 => double, 2 => S 98 @union {@ // implicit 99 case int i; 100 case double d; 101 case struct S { int i, j; } s; 102 @};@ 103 }; 104 \end{cfa} 105 Crucially, the union implies instance storage is shared by all of the variant types. 106 Hence, a variant is dynamically typed, as in a dynamic-typed programming-language, but the set of types is statically bound, similar to some aspects of dynamic gradual-typing~\cite{Gradual Typing}. 107 Knowing which type is in a variant instance is crucial for correctness. 108 Occasionally, it is possible to statically determine all regions where each variant type is used, so a tag and runtime checking is unnecessary; 109 otherwise, a tag is required to denote the particular type in the variant and the tag checked at runtime using some form of type pattern-matching. 110 111 The tag can be implicitly set by the compiler on assignment, or explicitly set by the program\-mer. 112 Type pattern-matching is then used to dynamically test the tag and branch to a section of code to safely manipulate the value, \eg: 113 \begin{cfa}[morekeywords={match}] 114 Variant v = 3; // implicitly set tag to 0 115 @match@( v ) { // know the type or test the tag 116 case int { /* only access i field in v */ } 117 case double { /* only access d field in v */ } 118 case S { /* only access s field in v */ } 119 } 120 \end{cfa} 121 For safety, either all variant types must be listed or a @default@ case must exist with no field accesses. 122 123 To simulate an enumeration with a variant, the tag is \emph{re-purposed} for either ordering or value and the variant types are omitted. 124 \begin{cfa} 125 variant Weekday { 126 int tag; // implicit 0 => Mon, ..., 6 => Sun 127 @case Mon;@ // no type 128 ... 129 @case Sun;@ 130 }; 131 \end{cfa} 132 The type system ensures tag setting and testing are correctly done. 133 However, the enumeration operations are limited to the available tag operations, \eg pattern matching. 134 \begin{cfa} 135 Week week = Mon; 136 if ( @dynamic_cast(Mon)@week ) ... // test tag == Mon 137 \end{cfa} 138 While enumerating among tag names is possible: 139 \begin{cfa}[morekeywords={in}] 140 for ( cursor in Mon, Wed, Fri, Sun ) ... 141 \end{cfa} 142 ordering for iteration would require a \emph{magic} extension, such as a special @enum@ variant, because it has no meaning for a regular variant, \ie @int@ < @double@. 143 144 However, if a special @enum@ variant allows the tags to be heterogeneously typed, ordering must fall back on case positioning, as many types have incomparable values. 145 Iterating using tag ordering and heterogeneous types, also requires pattern matching. 146 \begin{cfa}[morekeywords={match}] 147 for ( cursor = Mon; cursor <= Fri; cursor = succ( cursor) ) { 148 match( cursor ) { 149 case Mon { /* access special type for Mon */ } 150 ... 151 case Fri { /* access special type for Fri */ } 152 default 153 } 154 } 155 \end{cfa} 156 If the variant type is changed by adding/removing types or the loop range changes, the pattern matching must be adjusted. 157 As well, if the start/stop values are dynamic, it may be impossible to statically determine if all variant types are listed. 158 159 Re-purposing the notion of enumerating into variant types is ill formed and confusing. 160 Hence, there is only a weak equivalence between an enumeration and variant type, justifying the enumeration type in a programming language. 130 For these reasons, aliasing is sometimes called an enumeration. 131 However, there is no type to create a type-checked instance or iterator cursor, so there is no ability for enumerating. 132 Hence, there are multiple enumeration aspects not provided by aliasing, justifying a separate enumeration type in a programming language. 133 134 135 \subsection{Algebraic Data Type} 136 137 An algebraic data type (ADT)\footnote{ADT is overloaded with abstract data type.} is another language feature often linked with enumeration, where an ADT conjoins an arbitrary type, possibly a \lstinline[language=C++]{class} or @union@, and a named constructor. 138 For example, in Haskell: 139 \begin{haskell} 140 data S = S { i::Int, d::Double } $\C{// structure}$ 141 data @Foo@ = A Int | B Double | C S $\C{// ADT, composed of three types}$ 142 foo = A 3; $\C{// type Foo is inferred}$ 143 bar = B 3.5 144 baz = C S{ i = 7, d = 7.5 } 145 \end{haskell} 146 the ADT has three variants (constructors), @A@, @B@, @C@ with associated types @Int@, @Double@, and @S@. 147 The constructors create an initialized value of the specific type that is bound to the immutable variables @foo@, @bar@, and @baz@. 148 Hence, the ADT @Foo@ is like a union containing values of the associated types, and a constructor name is used to access the value using dynamic pattern-matching. 149 \begin{cquote} 150 \setlength{\tabcolsep}{15pt} 151 \begin{tabular}{@{}ll@{}} 152 \begin{haskell} 153 prtfoo val = -- function 154 -- pattern match on constructor 155 case val of 156 @A@ a -> print a 157 @B@ b -> print b 158 @C@ (S i d) -> do 159 print i 160 print d 161 \end{haskell} 162 & 163 \begin{haskell} 164 main = do 165 prtfoo foo 166 prtfoo bar 167 prtfoo baz 168 3 169 3.5 170 7 171 7.5 172 \end{haskell} 173 \end{tabular} 174 \end{cquote} 175 For safety, most languages require all assocaited types to be listed or a default case with no field accesses. 176 177 A less frequent case is multiple constructors with the same type. 178 \begin{haskell} 179 data Bar = X Int | Y Int | Z Int; 180 foo = X 3; 181 bar = Y 3; 182 baz = Z 5; 183 \end{haskell} 184 Here, the constructor name gives different meaning to the values in the common \lstinline[language=Haskell]{Int} type, \eg the value @3@ has different interpretations depending on the constructor name in the pattern matching. 185 186 Note, the term \Newterm{variant} is often associated with ADTs. 187 However, there are multiple languages with a @variant@ type that is not an ADT \see{Algol68~\cite{Algol68} or \CC \lstinline{variant}}. 188 In these languages, the variant is often a union using RTTI tags, which cannot be used to simulate an enumeration. 189 Hence, in this work the term variant is not a synonym for ADT. 190 191 % https://downloads.haskell.org/ghc/latest/docs/libraries/base-4.19.1.0-179c/GHC-Enum.html 192 % https://hackage.haskell.org/package/base-4.19.1.0/docs/GHC-Enum.html 193 194 The association between ADT and enumeration occurs if all the constructors have a unit (empty) type, \eg @struct unit {}@. 195 Note, the unit type is not the same as \lstinline{void}, \eg: 196 \begin{cfa} 197 void foo( void ); 198 struct unit {} u; // empty type 199 unit bar( unit ); 200 foo( foo() ); // void argument does not match with void parameter 201 bar( bar( u ) ); // unit argument does match with unit parameter 202 \end{cfa} 203 204 For example, in the Haskell ADT: 205 \begin{haskell} 206 data Week = Mon | Tue | Wed | Thu | Fri | Sat | Sun deriving(Enum, Eq, Show) 207 \end{haskell} 208 the default type for each constructor is the unit type, and deriving from @Enum@ enforces no other type, @Eq@ allows equality comparison, and @Show@ is for printing. 209 The nullary constructors for the unit types are numbered left-to-right from $0$ to @maxBound@$- 1$, and provides enumerating operations @succ@, @pred@, @enumFrom@ @enumFromTo@. 210 \VRef[Figure]{f:HaskellEnumeration} shows enumeration comparison and iterating (enumerating). 211 212 \begin{figure} 213 \begin{cquote} 214 \setlength{\tabcolsep}{15pt} 215 \begin{tabular}{@{}ll@{}} 216 \begin{haskell} 217 day = Tue 218 main = do 219 if day == Tue then 220 print day 221 else 222 putStr "not Tue" 223 print (enumFrom Mon) -- week 224 print (enumFromTo Mon Fri) -- weekday 225 print (enumFromTo Sat Sun) -- weekend 226 \end{haskell} 227 & 228 \begin{haskell} 229 Tue 230 [Mon,Tue,Wed,Thu,Fri,Sat,Sun] 231 [Mon,Tue,Wed,Thu,Fri] 232 [Sat,Sun] 233 234 235 236 237 238 \end{haskell} 239 \end{tabular} 240 \end{cquote} 241 \caption{Haskell Enumeration} 242 \label{f:HaskellEnumeration} 243 \end{figure} 244 245 The key observation is the dichotomy between an ADT and enumeration: the ADT uses the associated type resulting in a union-like data structure, and the enumeration does not use the associated type, and hence, is not a union. 246 While the enumeration is constructed using the ADT mechanism, it is so restricted it is not really an ADT. 247 Furthermore, a general ADT cannot be an enumeration because the constructors generate different values making enumerating meaningless. 248 While functional programming languages regularly repurpose the ADT type into an enumeration type, this process seems contrived and confusing. 249 Hence, there is only a weak equivalence between an enumeration and ADT, justifying a separate enumeration type in a programming language. 161 250 162 251 163 252 \section{Contributions} 164 253 165 The goal of this work is to to extend the simple and unsafe enumeration type in the C programming-language into a sophisticated and safe type in the \CFA programming-language, while maintainbackwards compatibility with C.254 The goal of this work is to to extend the simple and unsafe enumeration type in the C programming-language into a complex and safe enumeration type in the \CFA programming-language, while maintaining backwards compatibility with C. 166 255 On the surface, enumerations seem like a simple type. 167 256 However, when extended with advanced features, enumerations become complex for both the type system and the runtime implementation. 168 257 258 The contribution of this work are: 169 259 \begin{enumerate} 170 260 \item … … 175 265 typing 176 266 \item 177 subset 267 subseting 178 268 \item 179 269 inheritance -
doc/theses/jiada_liang_MMath/relatedwork.tex
rcf191ac r7042c60 23 23 \section{Pascal} 24 24 \label{s:Pascal} 25 \lstnewenvironment{pascal}[1][]{\lstset{language=pascal,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{}26 25 27 26 Classic Pascal has the \lstinline[language=pascal]{const} declaration binding a name to a constant literal/expression. … … 51 50 52 51 \section{Ada} 53 \lstnewenvironment{ada}[1][]{\lstset{language=[2005]Ada,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},literate={'}{\ttfamily'\!}1}\lstset{#1}}{} 54 55 A n Ada enumeration type is an ordered list of constants, called \Newterm{literals} (enumerators).52 53 An Ada enumeration type is a set of ordered unscoped identifiers (enumerators) bound to \emph{unique} \Newterm{literals}.\footnote{% 54 Ada is \emph{case-insensitive} so identifiers may appear in multiple forms and still be the same, \eg \lstinline{Mon}, \lstinline{moN}, and \lstinline{MON} (a questionable design decision).} 56 55 \begin{ada} 57 type RGB is ( Red, Green, Blue ); -- 3literals (enumerators)56 type Week is ( Mon, Tue, Wed, Thu, Fri, Sat, Sun ); -- literals (enumerators) 58 57 \end{ada} 59 58 Object initialization and assignment are restricted to the enumerators of this type. 60 Enumerators without an explicitly designated constant value are auto-initialized: from left to right, starting at zero or the next explicitly initialized constant, incrementing by 1. 61 To explicitly set enumerator values, \emph{all} enumerators must be set in \emph{ascending} order, \ie there is no auto-initialization. 59 While Ada enumerators are unscoped, like C, Ada enumerators are overloadable. 62 60 \begin{ada} 63 type RGB is ( Red, Green, Blue ); 64 @for RGB use ( Red => 10, Green => 20, Blue => 30 );@ -- ascending order 65 \end{ada} 66 Hence, the position, value, label tuples are: 67 \begin{ada} 68 (0, 10, RED) (1, 20, GREEN) (2, 30, BLUE) 69 \end{ada} 70 Note, Ada is case-\emph{insensitive} so names may appear in multiple forms and still be the same, \eg @Red@ and @RED@ (a questionable design decision). 71 72 Like C, Ada enumerators are unscoped, \ie enumerators declared inside of an enum are visible (projected) into the enclosing scope. 73 The enumeration operators are the ordering operators, @=@, @<@, @<=@, @=@, @/=@, @>=@, @>@, where the ordering relationship is given implicitly by the sequence of enumerators, which is always ascending. 74 75 Ada enumerators are overloadable. 76 \begin{ada} 61 type RGB is ( @Red@, @Green@, Blue ); 77 62 type Traffic_Light is ( @Red@, Yellow, @Green@ ); 78 63 \end{ada} 79 Like \CFA, Ada uses an advanced type-resolution algorithm, including the left-hand side of assignment, to disambiguate among overloaded names.64 Like \CFA, Ada uses an advanced type-resolution algorithm, including the left-hand side of assignment, to disambiguate among overloaded identifiers. 80 65 \VRef[Figure]{f:AdaEnumeration} shows how ambiguity is handled using a cast, \ie \lstinline[language=ada]{RGB'(Red)}. 81 66 … … 102 87 \end{figure} 103 88 104 Ada provides an alias mechanism, \lstinline[language=ada]{renames}, for aliasing types, which is useful to shorten package names. 89 Enumerators without initialization are auto-initialized from left to right, starting at zero, incrementing by 1. 90 Enumerators with initialization must set \emph{all} enumerators in \emph{ascending} order, \ie there is no auto-initialization. 91 \begin{ada} 92 type Week is ( Mon, Tue, Wed, Thu, Fri, Sat, Sun ); 93 for Week use ( Mon => 0, Tue => 1, Wed => 2, Thu => @10@, Fri => 11, Sat => 14, Sun => 15 ); 94 \end{ada} 95 The enumeration operators are the equality and relational operators, @=@, @/=@, @<@, @<=@, @=@, @/=@, @>=@, @>@, where the ordering relationship is given implicitly by the sequence of acsending enumerators. 96 97 Ada provides an alias mechanism, \lstinline[language=ada]{renames}, for aliasing types, which is useful to shorten package identifiers. 105 98 \begin{ada} 106 99 OtherRed : RGB renames Red; … … 113 106 There are three pairs of inverse enumeration pseudo-functions (attributes): @'Pos@ and @'Val@, @'Enum_Rep@ and @'Enum_Val@, and @'Image@ and @'Value@, 114 107 \begin{cquote} 115 \lstDeleteShortInline@116 108 \setlength{\tabcolsep}{15pt} 117 109 \begin{tabular}{@{}ll@{}} … … 128 120 \end{ada} 129 121 \end{tabular} 130 \lstMakeShortInline@131 122 \end{cquote} 132 123 These attributes are important for IO. … … 138 129 \end{ada} 139 130 which is syntactic sugar for the label and not character literals from the predefined type @Character@. 140 The purpose is strictly readability using character literals rather than names.131 The purpose is strictly readability using character literals rather than identifiers. 141 132 \begin{ada} 142 133 Op : Operator := '+'; … … 171 162 An enumeration type can be used in the Ada \lstinline[language=ada]{case} (all enumerators must appear or a default) or iterating constructs. 172 163 \begin{cquote} 173 \lstDeleteShortInline@174 164 \setlength{\tabcolsep}{15pt} 175 165 \begin{tabular}{@{}ll@{}} … … 211 201 \end{ada} 212 202 \end{tabular} 213 \lstMakeShortInline@214 203 \end{cquote} 215 204 … … 225 214 \section{\CC} 226 215 \label{s:C++RelatedWork} 227 \lstnewenvironment{c++}[1][]{\lstset{language=[GNU]C++,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{}228 216 229 217 \CC has the equivalent of Pascal typed @const@ declarations \see{\VRef{s:Pascal}}, with static and dynamic initialization. 230 218 \begin{c++} 231 const auto one = 0 + 1; $\C{// static in tialization}$219 const auto one = 0 + 1; $\C{// static initialization}$ 232 220 const auto NULL = nullptr; 233 221 const auto PI = 3.14159; … … 237 225 Sat = Fri + 1, Sun = Sat + 1; 238 226 int sa[Sun]; 239 const auto r = random(); $\C{// dynamic in tialization}$227 const auto r = random(); $\C{// dynamic initialization}$ 240 228 int da[r]; $\C{// VLA}$ 241 229 \end{c++} … … 319 307 \section{C\raisebox{-0.7ex}{\LARGE$^\sharp$}\xspace} % latex bug: cannot use \relsize{2} so use \LARGE 320 308 \label{s:Csharp} 321 \lstnewenvironment{csharp}[1][]{\lstset{language=[Sharp]C,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{}322 309 323 310 % https://www.tutorialsteacher.com/codeeditor?cid=cs-mk8Ojx … … 362 349 \begin{figure} 363 350 \centering 364 \lstDeleteShortInline@365 351 \begin{tabular}{@{}l|l@{}} 366 352 \multicolumn{1}{@{}c|}{non-object oriented} & \multicolumn{1}{c@{}}{object oriented} \\ … … 414 400 \end{csharp} 415 401 \end{tabular} 416 \lstMakeShortInline@417 402 \caption{\Csharp: Free Routine Versus Class Enumeration} 418 403 \label{CsharpFreeVersusClass} … … 421 406 422 407 \section{Golang} 423 \lstnewenvironment{Go}[1][]{\lstset{language=Go,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{}424 408 425 409 Golang provides pseudo-enumeration similar to classic Pascal \lstinline[language=pascal]{const}, binding a name to a constant literal/expression. … … 429 413 const ( S = 0; T; USA = "USA"; U; V = 3.1; W ) $\C{// type change, implicit/explicit: 0 0 USA USA 3.1 3.1}$ 430 414 \end{Go} 431 Constant names are unscoped and must be unique (no overloading).415 Constant identifiers are unscoped and must be unique (no overloading). 432 416 The first enumerator \emph{must} be explicitly initialized; 433 417 subsequent enumerators can be implicitly or explicitly initialized. … … 459 443 Basic switch and looping are possible. 460 444 \begin{cquote} 461 \lstDeleteShortInline@462 445 \setlength{\tabcolsep}{15pt} 463 446 \begin{tabular}{@{}ll@{}} … … 482 465 \end{Go} 483 466 \end{tabular} 484 \lstMakeShortInline@485 467 \end{cquote} 486 468 However, the loop prints the values from 0 to 13 because there is no actual enumeration. … … 488 470 489 471 \section{Java} 490 \lstnewenvironment{Java}[1][]{\lstset{language=Java,morekeywords={enum,assert,strictfp},491 escapechar=\$,moredelim=**[is][\color{red}]{!}{!},}\lstset{#1}}{}492 472 493 473 Every enumeration in Java is an enumeration class. … … 513 493 \begin{figure} 514 494 \centering 515 \lstDeleteShortInline@516 495 \begin{tabular}{@{}l|l@{}} 517 496 \multicolumn{1}{@{}c|}{non-object oriented} & \multicolumn{1}{c@{}}{object oriented} \\ … … 553 532 \end{Java} 554 533 \end{tabular} 555 \lstMakeShortInline@556 534 \caption{Java: Free Routine Versus Class Enumeration} 557 535 \label{f:JavaFreeVersusClass} … … 606 584 607 585 \section{Rust} 608 \lstnewenvironment{rust}[1][]{\lstset{language=Rust,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} 586 % https://doc.rust-lang.org/reference/items/enumerations.html 609 587 610 588 Rust provides a scoped enumeration based on variant types. … … 652 630 653 631 \section{Swift} 654 \lstnewenvironment{swift}[1][]{\lstset{language=Swift,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{}655 632 656 633 % https://www.programiz.com/swift/online-compiler … … 1010 987 1011 988 1012 \section{Python} 1013 \lstnewenvironment{python}[1][]{\lstset{language=Python,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} 1014 1015 A Python enumeration is a set of symbolic names bound to \emph{unique} values. 1016 They are similar to global variables, but offer a more useful @repr()@, grouping, type-safety, and additional features. 1017 Enumerations inherits from the @Enum@ class, \eg: 1018 \begin{python} 1019 class Weekday(@Enum@): Mon = 1; Tue = 2; Wed = 3; Thu = 4; Fri = 5; Sat = 6; Sun = 7 1020 class RGB(@Enum@): Red = 1; Green = 2; Blue = 3 1021 \end{python} 1022 1023 Depending on the nature of the enum a member's value may or may not be important, but either way that value can be used to get the corresponding member: 1024 \begin{python} 1025 print( repr( Weekday( 3 ) ) ) 1026 <Weekday.Wed: 3> 1027 \end{python} 1028 As you can see, the @repr()@ of a member shows the enum name, the member name, and the value. 1029 The @str()@ of a member shows only the enum name and member name: 1030 \begin{python} 1031 print( str( Weekday.Thu ), Weekday.Thu ) 1032 Weekday.Thu Weekday.Thu 1033 \end{python} 1034 The type of an enumeration member is the enum it belongs to: 1035 \begin{python} 1036 print( type( Weekday.Thu ) ) 1037 <enum 'Weekday'> 1038 print( isinstance(Weekday.Fri, Weekday) ) 1039 True 1040 \end{python} 1041 Enum members have an attribute that contains just their name: 1042 \begin{python} 1043 print(Weekday.TUESDAY.name) 1044 TUESDAY 1045 \end{python} 1046 Likewise, they have an attribute for their value: 1047 \begin{python} 1048 Weekday.WEDNESDAY.value 1049 3 1050 \end{python} 1051 1052 Unlike many languages that treat enumerations solely as name/value pairs, Python @Enum@s can have behavior added. 1053 For example, @datetime.date@ has two methods for returning the weekday: @weekday()@ and @isoweekday()@. 1054 The difference is that one of them counts from 0-6 and the other from 1-7. 1055 Rather than keep track of that ourselves we can add a method to the @Weekday@ enum to extract the day from the date instance and return the matching enum member: 1056 \begin{python} 1057 class Weekday(Enum): Mon = 1; Tue = 2; Wed = 3; Thu = 10; Fri = 15; Sat = 16; Sun = 17 1058 $@$classmethod 1059 def from_date(cls, date): 1060 return cls(date.isoweekday()) 1061 \end{python} 1062 Now we can find out what today is! Observe: 1063 \begin{python} 1064 >>> from datetime import date 1065 >>> Weekday.from_date(date.today()) 1066 <Weekday.TUESDAY: 2> 1067 \end{python} 1068 Of course, if you're reading this on some other day, you'll see that day instead. 1069 1070 This Weekday enum is great if our variable only needs one day, but what if we need several? Maybe we're writing a function to plot chores during a week, and don't want to use a @list@ -- we could use a different type of @Enum@: 1071 \begin{python} 1072 from enum import Flag 1073 class WeekdayF(@Flag@): Mon = @1@; Tue = @2@; Wed = @4@; Thu = @8@; Fri = @16@; Sat = @32@; Sun = @64@ 1074 \end{python} 1075 We've changed two things: we're inherited from @Flag@, and the values are all powers of 2. 989 \section{Python 3.13} 990 % https://docs.python.org/3/howto/enum.html 991 992 Python is a dynamically-typed reflexive programming language with multiple versions, and hence, it is possible to extend existing or build new language features within the language. 993 As a result, discussing Python enumerations is a moving target, because if a features does not exist, if can often be created with varying levels of complexity. 994 Nevertheless, an attempt has been made to discuss core enumeration features that come with Python 3.13. 995 996 A Python enumeration type is a set of ordered scoped identifiers (enumerators) bound to \emph{unique} values. 997 An enumeration is not a basic type; 998 it is a @class@ inheriting from the @Enum@ class, where the enumerators must be explicitly initialized, \eg: 999 \begin{python} 1000 class Week(@Enum@): Mon = 1; Tue = 2; Wed = 3; Thu = 4; Fri = 5; Sat = 6; Sun = 7 1001 \end{python} 1002 and/or explicitly auto initialized, \eg: 1003 \begin{python} 1004 class Week(Enum): Mon = 1; Tue = 2; Wed = 3; Thu = 10; Fri = @auto()@; Sat = 4; Sun = @auto()@ 1005 \end{python} 1006 where @auto@ increments by 1 from the previous enumerator value. 1007 Object initialization and assignment are restricted to the enumerators of this type. 1008 An enumerator initialized with same value is an alias and invisible at the enumeration level, \ie the alias it substituted for its aliasee. 1009 \begin{python} 1010 class Week(Enum): Mon = 1; Tue = 2; Wed = 3; Thu = 10; Fri = @10@; Sat = @10@; Sun = @10@ 1011 \end{python} 1012 Here, the enumeration has only 4 enumerators and 3 aliases. 1013 An alias is only visible by dropping down to the @class@ level and asking for class members. 1014 @Enum@ only supports equality comparison between enumerator values; 1015 the extended class @OrderedEnum@ adds relational operators @<@, @<=@, @>@, and @>=@. 1016 1017 There are bidirectional enumeration pseudo-functions for label and value, but there is no concept of access using ordering (position). 1018 \begin{cquote} 1019 \setlength{\tabcolsep}{15pt} 1020 \begin{tabular}{@{}ll@{}} 1021 \begin{python} 1022 Week.Thu.value == 10; 1023 Week.Thu.name == 'Thu'; 1024 \end{python} 1025 & 1026 \begin{python} 1027 Week( 10 ) == Thu 1028 Week['Thu'].value = 10 1029 \end{python} 1030 \end{tabular} 1031 \end{cquote} 1032 1033 As an enumeration is a \lstinline[language=python]{class}, its own methods. 1034 \begin{python} 1035 class Week(Enum): 1036 Mon = 1; Tue = 2; Wed = 3; Thu = 4; Fri = 5; Sat = 6; Sun = 7 1037 $\\@$classmethod 1038 def today(cls, date): 1039 return cls(date.isoweekday()) 1040 print( "today:", Week.today(date.today())) 1041 today: Week.Mon 1042 \end{python} 1043 The method @today@ retrieves the day of the week and uses it as an index to print out the corresponding label of @Week@. 1076 1044 1077 1045 @Flag@ allows combining several members into a single variable: 1078 1046 \begin{python} 1079 print( repr(Week dayF.Sat | WeekdayF.Sun) )1080 <Week dayF.Sun|Sat: 96>1047 print( repr(WeekF.Sat | WeekF.Sun) ) 1048 <WeekF.Sun|Sat: 96> 1081 1049 \end{python} 1082 1050 You can even iterate over a @Flag@ variable: … … 1084 1052 for day in weekend: 1085 1053 print(day) 1086 Week day.SATURDAY1087 Week day.SUNDAY1054 WeekF.Sat 1055 WeekF.Sun 1088 1056 \end{python} 1089 1057 Okay, let's get some chores set up: 1090 1058 \begin{python} 1091 1059 >>> chores_for_ethan = { 1092 ... 'feed the cat': Week day.MONDAY | Weekday.WEDNESDAY | Weekday.FRIDAY,1093 ... 'do the dishes': Week day.TUESDAY | Weekday.THURSDAY,1094 ... 'answer SO questions': Week day.SATURDAY,1060 ... 'feed the cat': Week.MONDAY | Week.WEDNESDAY | Week.FRIDAY, 1061 ... 'do the dishes': Week.TUESDAY | Week.THURSDAY, 1062 ... 'answer SO questions': Week.SATURDAY, 1095 1063 ... } 1096 1064 \end{python} … … 1101 1069 ... if day in days: 1102 1070 ... print(chore) 1103 >>> show_chores(chores_for_ethan, Week day.SATURDAY)1071 >>> show_chores(chores_for_ethan, Week.SATURDAY) 1104 1072 answer SO questions 1105 1073 \end{python} 1106 In cases where the actual values of the members do not matter, you can save yourself some work and use @auto()@ for the values: 1107 \begin{python} 1108 >>> from enum import auto 1109 >>> class Weekday(Flag): 1110 ... MONDAY = auto() 1111 ... TUESDAY = auto() 1112 ... WEDNESDAY = auto() 1113 ... THURSDAY = auto() 1114 ... FRIDAY = auto() 1115 ... SATURDAY = auto() 1116 ... SUNDAY = auto() 1117 ... WEEKEND = SATURDAY | SUNDAY 1074 Auto incrmenet for @Flag@ is by powers of 2. 1075 \begin{python} 1076 class WeekF(Flag): Mon = auto(); Tue = auto(); Wed = auto(); Thu = auto(); Fri = auto(); \ 1077 Sat = auto(); Sun = auto(); Weekend = Sat | Sun 1078 for d in WeekF: 1079 print( f"{d.name}: {d.value}", end=" ") 1080 Mon: 1 Tue: 2 Wed: 4 Thu: 8 Fri: 16 Sat: 32 Sun: 64 WeekA.Weekend 1118 1081 \end{python} 1119 1082 … … 1123 1086 @Enum@ allows such access: 1124 1087 \begin{python} 1125 >>> Color(1) 1126 <Color.RED: 1> 1127 >>> Color(3) 1128 <Color.BLUE: 3> 1088 print(RGB(1), RGB(3), ) 1089 RGB.RED RGB.GREEN 1129 1090 \end{python} 1130 1091 If you want to access enum members by name, use item access: 1131 1092 \begin{python} 1132 Color['RED'] 1133 <Color.RED: 1> 1134 1135 Color['GREEN'] 1136 <Color.GREEN: 2> 1093 print( RGBa['RED'], RGBa['GREEN'] ) 1094 RGB.RED RGB.GREEN 1137 1095 \end{python} 1138 1096 If you have an enum member and need its name or value: 1139 1097 \begin{python} 1140 >>> member = Color.RED 1141 >>> member.name 1142 'RED' 1143 >>> member.value 1144 1 1145 \end{python} 1146 1147 \subsection{Duplicating enum members and values} 1148 1149 An enum member can have other names associated with it. 1150 Given two entries @A@ and @B@ with the same value (and @A@ defined first), @B@ is an alias for the member @A@. 1151 By-value lookup of the value of @A@ will return the member @A@. 1152 By-name lookup of @A@ will return the member @A@. 1153 By-name lookup of @B@ will also return the member @A@: 1154 \begin{python} 1155 class Shape(Enum): SQUARE = 2; DIAMOND = 1; CIRCLE = 3; ALIAS_FOR_SQUARE = 2 1156 >>> Shape.SQUARE 1157 <Shape.SQUARE: 2> 1158 >>> Shape.ALIAS_FOR_SQUARE 1159 <Shape.SQUARE: 2> 1160 >>> Shape(2) 1161 <Shape.SQUARE: 2> 1162 \end{python} 1163 1164 Note: Attempting to create a member with the same name as an already defined attribute (another member, a method, etc.) or attempting to create an attribute with the same name as a member is not allowed. 1098 member = RGBa.RED 1099 print( f"{member.name} {member.value}" ) 1100 RED 1 1101 \end{python} 1102 1165 1103 1166 1104 \subsection{Ensuring unique enumeration values} … … 1207 1145 >>> list(Shape) 1208 1146 [<Shape.SQUARE: 2>, <Shape.DIAMOND: 1>, <Shape.CIRCLE: 3>] 1209 >>> list(Week day)1210 [<Week day.MONDAY: 1>, <Weekday.TUESDAY: 2>, <Weekday.WEDNESDAY: 4>, <Weekday.THURSDAY: 8>,1211 <Week day.FRIDAY: 16>, <Weekday.SATURDAY: 32>, <Weekday.SUNDAY: 64>]1212 \end{python} 1213 Note that the aliases @Shape.ALIAS_FOR_SQUARE@ and @Week day.WEEKEND@ aren't shown.1147 >>> list(Week) 1148 [<Week.MONDAY: 1>, <Week.TUESDAY: 2>, <Week.WEDNESDAY: 4>, <Week.THURSDAY: 8>, 1149 <Week.FRIDAY: 16>, <Week.SATURDAY: 32>, <Week.SUNDAY: 64>] 1150 \end{python} 1151 Note that the aliases @Shape.ALIAS_FOR_SQUARE@ and @Week.WEEKEND@ aren't shown. 1214 1152 1215 1153 The special attribute @__members__@ is a read-only ordered mapping of names to members. … … 2212 2150 2213 2151 \section{OCaml} 2214 \lstnewenvironment{ocaml}[1][]{\lstset{language=OCaml,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{}2215 2152 2216 2153 % https://ocaml.org/docs/basic-data-types#enumerated-data-types … … 2218 2155 2219 2156 OCaml provides a variant (union) type, where multiple heterogeneously-typed objects share the same storage. 2220 The simplest form of the variant type is a list of nullary datatype constructors, which is like an unscoped, pure enumeration. 2221 2222 (I think the value of a ocaml variants are types not object, so I am not sure about this line) 2157 The simplest form of the variant type is a list of nullary datatype constructors, which is like an unscoped, opaque enumeration. 2158 2223 2159 OCaml provides a variant (union) type, which is an aggregation of heterogeneous types. 2224 A basic variant is a list of nullary datatype constructors, which is like an unscoped, pure enumeration.2160 A basic variant is a list of nullary datatype constructors, which is like an unscoped, opaque enumeration. 2225 2161 \begin{ocaml} 2226 2162 type weekday = Mon | Tue | Wed | Thu | Fri | Sat | Sun … … 2246 2182 type colour = Red | Green of @string@ | Blue of @int * float@ 2247 2183 \end{ocaml} 2248 A variant with parameter is stored in a memory block, prefixed by an int tag and has its parameters stores as words in the block. 2184 A variant with parameter is stored in a memory block, prefixed by an int tag and has its parameters stores as words in the block. 2249 2185 @colour@ is a summation of a nullary type, a unary product type of @string@, and a cross product of @int@ and @float@. 2250 2186 (Mathematically, a @Blue@ value is a Cartesian product of the types @int@ type and @float@.) … … 2259 2195 @Red, abc, 1 1.5@ 2260 2196 \end{ocaml} 2261 2262 2197 2263 2198 A variant type can have a recursive definition. … … 2280 2215 2281 2216 In summary, an OCaml variant is a singleton value rather than a set of possibly ordered values, and hence, has no notion of enumerabilty. 2282 Therefore it is not an enumeration, except for the simple pure (nullary) case.2217 Therefore it is not an enumeration, except for the simple opaque (nullary) case. 2283 2218 2284 2219 \begin{comment} … … 2466 2401 With valediction, 2467 2402 - Gregor Richards 2403 2404 2405 Date: Tue, 16 Apr 2024 11:04:51 -0400 2406 Subject: Re: C unnamed enumeration 2407 To: "Peter A. Buhr" <pabuhr@uwaterloo.ca> 2408 CC: <ajbeach@uwaterloo.ca>, <j82liang@uwaterloo.ca>, <mlbrooks@uwaterloo.ca>, 2409 <f37yu@uwaterloo.ca> 2410 From: Gregor Richards <gregor.richards@uwaterloo.ca> 2411 2412 On 4/16/24 09:55, Peter A. Buhr wrote: 2413 > So what is a variant? Is it a set of tag names, which might be a union or is it 2414 > a union, which might have tag names? 2415 2416 Your tagless variant bears no resemblance to variants in any functional 2417 programming language. A variant is a tag AND a union. You might not need to put 2418 anything in the union, in which case it's a pointless union, but the named tag 2419 is absolutely mandatory. That's the thing that varies. 2420 2421 I was unaware of std::variant. As far as functional languages are concerned, 2422 std::variant IS NOT A VARIANT. Perhaps it would be best to use the term ADT for 2423 the functional language concept, because that term has no other meanings. 2424 2425 An ADT cannot not have a named tag. That's meaningless. The tag is the data 2426 constructor, which is the thing you actually define when you define an ADT. It 2427 is strictly the union that's optional. 2428 2429 With valediction, 2430 - Gregor Richards 2468 2431 \end{comment} 2469 2432 … … 2487 2450 \hline 2488 2451 \hline 2489 pure & & & & & & & & & & & & & \CM \\2452 opaque & & & & & & & & & & & & & \CM \\ 2490 2453 \hline 2491 2454 typed & & & & & & & & & & & @int@ & integral & @T@ \\ -
doc/theses/jiada_liang_MMath/uw-ethesis.bib
rcf191ac r7042c60 2 2 % For use with BibTeX 3 3 4 Oxford English Dictionary, s.v. ``enumerate (v.), sense 3,'' September 2023, https://doi.org/10.1093/OED/1113960777. 5 @misc{OEDenumerate, 6 keywords = {enumerate}, 7 key = {enumerate}, 8 title = {enumerate (v.), sense 3}, 9 author = {Oxford English Dictionary}, 10 howpublished= {\url{https://doi.org/10.1093/OED/1113960777}}, 11 month = sep, 12 year = 2023, 13 } -
doc/theses/jiada_liang_MMath/uw-ethesis.tex
rcf191ac r7042c60 95 95 \CFAStyle % CFA code-style 96 96 \lstset{language=cfa,belowskip=-1pt} % set default language to CFA 97 \lstnewenvironment{ada}[1][]{\lstset{language=[2005]Ada,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},literate={'}{\ttfamily'\!}1}\lstset{#1}}{} 98 \lstnewenvironment{c++}[1][]{\lstset{language=[GNU]C++,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} 99 \lstnewenvironment{pascal}[1][]{\lstset{language=pascal,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} 100 \lstnewenvironment{csharp}[1][]{\lstset{language=[Sharp]C,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} 101 \lstnewenvironment{clang}[1][]{\lstset{language=[ANSI]C,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} 102 \lstnewenvironment{Go}[1][]{\lstset{language=Go,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} 103 \lstnewenvironment{haskell}[1][]{\lstset{language=Haskell,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} 104 \lstnewenvironment{Java}[1][]{\lstset{language=Java,morekeywords={enum,assert,strictfp}, 105 escapechar=\$,moredelim=**[is][\color{red}]{!}{!},}\lstset{#1}}{} 106 \lstnewenvironment{rust}[1][]{\lstset{language=Rust,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} 107 \lstnewenvironment{swift}[1][]{\lstset{language=Swift,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} 108 \lstnewenvironment{python}[1][]{\lstset{language=Python,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} 109 \lstnewenvironment{ocaml}[1][]{\lstset{language=OCaml,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{} 110 111 \newsavebox{\myboxA} 112 \newsavebox{\myboxB} 97 113 98 114 \newcommand{\newtermFont}{\emph} -
doc/uC++toCFA/Makefile
rcf191ac r7042c60 56 56 dvips ${Build}/$< -o $@ 57 57 58 ${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \59 ${Macros}/ common.sty ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib build/version | ${Build}58 ${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${Macros}/common.tex ${Macros}/common.sty \ 59 ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib build/version | ${Build} 60 60 # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run. 61 61 if [ ! -r ${basename $@}.ind ] ; then touch ${Build}/${basename $@}.ind ; fi -
doc/uC++toCFA/uC++toCFA.tex
rcf191ac r7042c60 11 11 %% Created On : Wed Apr 6 14:53:29 2016 12 12 %% Last Modified By : Peter A. Buhr 13 %% Last Modified On : Thu Jan 11 14:46:14202414 %% Update Count : 59 4213 %% Last Modified On : Sat Apr 13 11:11:39 2024 14 %% Update Count : 5969 15 15 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 16 16 … … 141 141 \CFA uses parametric polymorphism and allows overloading of variables and routines: 142 142 \begin{cfa} 143 int i; char i; double i; // overload name i143 int i; char i; double i; $\C[2in]{// overload name i}$ 144 144 int i(); double i(); char i(); 145 i += 1; $\C[1.5in]{// int i}$146 i += 1.0; $\C{// double i}$147 i += 'a'; $\C{// char i}$148 int j = i(); $\C{// int i()}$149 double j = i(); $\C{// double i();}$150 char j = i(); $\C{// char i()}\CRT$145 i += 1; $\C{// int i}$ 146 i += 1.0; $\C{// double i}$ 147 i += 'a'; $\C{// char i}$ 148 int j = i(); $\C{// int i()}$ 149 double j = i(); $\C{// double i();}$ 150 char j = i(); $\C{// char i()}\CRT$ 151 151 \end{cfa} 152 152 \CFA has rebindable references. 153 154 \begin{cquote} 155 \begin{tabular}{l|l} 156 \multicolumn{2}{l}{\lstinline{ int x = 1, y = 2, * p1x = &x, * p1y = &y, ** p2i = &p1x,}} \\ 157 \multicolumn{2}{l}{\lstinline{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ && r1x = x, & r1y = y, && r2i = r1x;}} \\ 153 \begin{cquote} 154 \begin{tabular}{@{}l|l@{}} 155 \multicolumn{2}{@{}l}{\lstinline{ int x = 1, y = 2, * p1x = &x, * p1y = &y, ** p2i = &p1x,}} \\ 156 \multicolumn{2}{@{}l}{\lstinline{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ && r1x = x, & r1y = y, && r2i = r1x;}} \\ 158 157 \begin{uC++} 159 158 **p2i = 3; … … 201 200 202 201 \CFA output streams automatically separate values and insert a newline at the end of the print. 203 204 \begin{cquote} 205 \begin{tabular}{l|l} 202 \begin{cquote} 203 \begin{tabular}{@{}l|l@{}} 206 204 \begin{uC++} 207 205 #include <@iostream@> … … 226 224 227 225 \begin{cquote} 228 \begin{tabular}{ l|l}226 \begin{tabular}{@{}l|l@{}} 229 227 \begin{uC++} 230 228 for ( @;;@ ) { ... } / while ( @true@ ) { ... } … … 280 278 Currently, \CFA uses macros @ExceptionDecl@ and @ExceptionInst@ to declare and instantiate an exception. 281 279 \begin{cquote} 282 \begin{tabular}{ l|ll}280 \begin{tabular}{@{}l|ll@{}} 283 281 \begin{uC++} 284 282 … … 321 319 322 320 \begin{cquote} 323 \begin{tabular}{ l|ll}321 \begin{tabular}{@{}l|ll@{}} 324 322 \begin{uC++} 325 323 … … 360 358 361 359 \begin{cquote} 362 \begin{tabular}{ l|l}360 \begin{tabular}{@{}l|l@{}} 363 361 \begin{uC++} 364 362 struct S { … … 383 381 384 382 \begin{cquote} 385 \begin{tabular}{ l|l}386 \multicolumn{2}{ l}{\lstinline{string s1, s2;}} \\383 \begin{tabular}{@{}l|l@{}} 384 \multicolumn{2}{@{}l@{}}{\lstinline{string s1, s2;}} \\ 387 385 \begin{uC++} 388 386 s1 = "hi"; … … 425 423 426 424 \begin{cquote} 427 \begin{tabular}{ l|l}425 \begin{tabular}{@{}l|l@{}} 428 426 \begin{uC++} 429 427 struct S { … … 456 454 457 455 \begin{cquote} 458 \begin{tabular}{ l|l}456 \begin{tabular}{@{}l|l@{}} 459 457 \begin{uC++} 460 458 … … 493 491 494 492 \begin{cquote} 495 \begin{tabular}{ l|ll}493 \begin{tabular}{@{}l|ll@{}} 496 494 \begin{uC++} 497 495 … … 532 530 533 531 \begin{cquote} 534 \begin{tabular}{ l|ll}532 \begin{tabular}{@{}l|ll@{}} 535 533 \begin{uC++} 536 534 … … 567 565 568 566 \begin{cquote} 569 \begin{tabular}{ l|ll}567 \begin{tabular}{@{}l|ll@{}} 570 568 \begin{uC++} 571 569 … … 604 602 605 603 \begin{cquote} 606 \begin{tabular}{ l|ll}604 \begin{tabular}{@{}l|ll@{}} 607 605 \begin{uC++} 608 606 -
doc/user/Makefile
rcf191ac r7042c60 60 60 dvips ${Build}/$< -o $@ 61 61 62 ${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \63 ${Macros}/ common.sty ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib build/version | ${Build}62 ${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${Macros}/common.tex ${Macros}/common.sty \ 63 ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib build/version | ${Build} 64 64 # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run. 65 65 if [ ! -r ${basename $@}.ind ] ; then touch ${Build}/${basename $@}.ind ; fi … … 73 73 makeindex -s ${Macros}/indexstyle ${Build}/${basename $@}.idx 74 74 # Run again to finish citations 75 ${LaTeX} ${basename $@}.tex75 # ${LaTeX} ${basename $@}.tex 76 76 # Run again to get index title into table of contents 77 77 # ${LaTeX} ${basename $@}.tex -
doc/user/user.tex
rcf191ac r7042c60 11 11 %% Created On : Wed Apr 6 14:53:29 2016 12 12 %% Last Modified By : Peter A. Buhr 13 %% Last Modified On : Mon Feb 12 11:50:26202414 %% Update Count : 6 19913 %% Last Modified On : Tue Apr 23 14:13:10 2024 14 %% Update Count : 6623 15 15 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 16 16 … … 69 69 \lstset{language=CFA} % CFA default lnaguage 70 70 \lstnewenvironment{C++}[1][] % use C++ style 71 {\lstset{language=C++, moredelim=**[is][\protect\color{red}]{®}{®},#1}}71 {\lstset{language=C++,escapechar=§,moredelim=**[is][\protect\color{red}]{®}{®},#1}} 72 72 {} 73 73 … … 130 130 \vspace*{\fill} 131 131 \noindent 132 \copyright\,2016, 2018, 2021 \CFA Project \\ \\132 \copyright\,2016, 2018, 2021, 2024 \CFA Project \\ \\ 133 133 \noindent 134 134 This work is licensed under the Creative Commons Attribution 4.0 International License. … … 312 312 For example, it is possible to write a type-safe \CFA wrapper ©malloc© based on the C ©malloc©: 313 313 \begin{cfa} 314 forall( dtype T| sized(T) ) T * malloc( void ) { return (T *)malloc( sizeof(T) ); }314 forall( T & | sized(T) ) T * malloc( void ) { return (T *)malloc( sizeof(T) ); } 315 315 int * ip = malloc(); §\C{// select type and size from left-hand side}§ 316 316 double * dp = malloc(); … … 1023 1023 while () { sout | "empty"; break; } 1024 1024 do { sout | "empty"; break; } while (); 1025 for () { sout | "empty"; break; } §\C{sout | nl | nlOff;}§1026 1027 for ( 0 ) { sout | "A"; } sout | "zero"; 1028 for ( 1 ) { sout | "A"; } 1029 for ( 10 ) { sout | "A"; } 1030 for ( ~= 10 ) { sout | "A"; } 1031 for ( 1 ~= 10 ~ 2 ) { sout | "B"; } 1032 for ( 1 -~= 10 ~ 2 ) { sout | "C"; } 1033 for ( 0.5 ~ 5.5 ) { sout | "D"; } 1034 for ( 0.5 -~ 5.5 ) { sout | "E"; } 1035 for ( i; 10 ) { sout | i; } 1036 for ( i; ~= 10 ) { sout | i; } 1037 for ( i; 1 ~= 10 ~ 2 ) { sout | i; } 1038 for ( i; 1 -~= 10 ~ 2 ) { sout | i; } 1039 for ( i; 0.5 ~ 5.5 ) { sout | i; } 1040 for ( i; 0.5 -~ 5.5 ) { sout | i; } 1041 for ( ui; 2u ~= 10u ~ 2u ) { sout | ui; } 1042 for ( ui; 2u -~= 10u ~ 2u ) { sout | ui; } 1025 for () { sout | "empty"; break; } §\C[3in]{sout | nl | nlOff;}§ 1026 1027 for ( 0 ) { sout | "A"; } sout | "zero"; §\C{sout | nl;}§ 1028 for ( 1 ) { sout | "A"; } §\C{sout | nl;}§ 1029 for ( 10 ) { sout | "A"; } §\C{sout | nl;}§ 1030 for ( ~= 10 ) { sout | "A"; } §\C{sout | nl;}§ 1031 for ( 1 ~= 10 ~ 2 ) { sout | "B"; } §\C{sout | nl;}§ 1032 for ( 1 -~= 10 ~ 2 ) { sout | "C"; } §\C{sout | nl;}§ 1033 for ( 0.5 ~ 5.5 ) { sout | "D"; } §\C{sout | nl;}§ 1034 for ( 0.5 -~ 5.5 ) { sout | "E"; } §\C{sout | nl;}§ 1035 for ( i; 10 ) { sout | i; } §\C{sout | nl;}§ 1036 for ( i; ~= 10 ) { sout | i; } §\C{sout | nl;}§ 1037 for ( i; 1 ~= 10 ~ 2 ) { sout | i; } §\C{sout | nl;}§ 1038 for ( i; 1 -~= 10 ~ 2 ) { sout | i; } §\C{sout | nl;}§ 1039 for ( i; 0.5 ~ 5.5 ) { sout | i; } §\C{sout | nl;}§ 1040 for ( i; 0.5 -~ 5.5 ) { sout | i; } §\C{sout | nl;}§ 1041 for ( ui; 2u ~= 10u ~ 2u ) { sout | ui; } §\C{sout | nl;}§ 1042 for ( ui; 2u -~= 10u ~ 2u ) { sout | ui; } §\C{sout | nl | nl | nl;}§ 1043 1043 1044 1044 enum { N = 10 }; 1045 for ( N ) { sout | "N"; } 1046 for ( i; N ) { sout | i; } 1047 for ( i; -~ N ) { sout | i; } 1045 for ( N ) { sout | "N"; } §\C{sout | nl;}§ 1046 for ( i; N ) { sout | i; } §\C{sout | nl;}§ 1047 for ( i; -~ N ) { sout | i; } §\C{sout | nl | nl | nl;}§ 1048 1048 1049 1049 const int low = 3, high = 10, inc = 2; 1050 for ( i; low ~ high ~ inc + 1 ) { sout | i; } 1051 for ( i; 1 ~ @ ) { if ( i > 10 ) break; sout | i; } 1052 for ( i; @ -~ 10 ) { if ( i < 0 ) break; sout | i; } 1053 for ( i; 2 ~ @ ~ 2 ) { if ( i > 10 ) break; sout | i; } 1050 for ( i; low ~ high ~ inc + 1 ) { sout | i; } §\C{sout | nl;}§ 1051 for ( i; 1 ~ @ ) { if ( i > 10 ) break; sout | i; } §\C{sout | nl;}§ 1052 for ( i; @ -~ 10 ) { if ( i < 0 ) break; sout | i; } §\C{sout | nl;}§ 1053 for ( i; 2 ~ @ ~ 2 ) { if ( i > 10 ) break; sout | i; } §\C{sout | nl;}§ 1054 1054 for ( i; 2.1 ~ @ ~ @ ) { if ( i > 10.5 ) break; sout | i; i += 1.7; } §\C{sout | nl;}§ 1055 1055 for ( i; @ -~ 10 ~ 2 ) { if ( i < 0 ) break; sout | i; } §\C{sout | nl;}§ 1056 1056 for ( i; 12.1 ~ @ ~ @ ) { if ( i < 2.5 ) break; sout | i; i -= 1.7; } §\C{sout | nl;}§ 1057 for ( i; 5 : j; -5 ~ @ ) { sout | i | j; } 1058 for ( i; 5 : j; @ -~ -5 ) { sout | i | j; } 1059 for ( i; 5 : j; -5 ~ @ ~ 2 ) { sout | i | j; } 1060 for ( i; 5 : j; @ -~ -5 ~ 2 ) { sout | i | j; } 1061 for ( i; 5 : j; -5 ~ @ ) { sout | i | j; } 1062 for ( i; 5 : j; @ -~ -5 ) { sout | i | j; } 1063 for ( i; 5 : j; -5 ~ @ ~ 2 ) { sout | i | j; } 1064 for ( i; 5 : j; @ -~ -5 ~ 2 ) { sout | i | j; } 1057 for ( i; 5 : j; -5 ~ @ ) { sout | i | j; } §\C{sout | nl;}§ 1058 for ( i; 5 : j; @ -~ -5 ) { sout | i | j; } §\C{sout | nl;}§ 1059 for ( i; 5 : j; -5 ~ @ ~ 2 ) { sout | i | j; } §\C{sout | nl;}§ 1060 for ( i; 5 : j; @ -~ -5 ~ 2 ) { sout | i | j; } §\C{sout | nl;}§ 1061 for ( i; 5 : j; -5 ~ @ ) { sout | i | j; } §\C{sout | nl;}§ 1062 for ( i; 5 : j; @ -~ -5 ) { sout | i | j; } §\C{sout | nl;}§ 1063 for ( i; 5 : j; -5 ~ @ ~ 2 ) { sout | i | j; } §\C{sout | nl;}§ 1064 for ( i; 5 : j; @ -~ -5 ~ 2 ) { sout | i | j; } §\C{sout | nl;}§ 1065 1065 for ( i; 5 : j; @ -~ -5 ~ 2 : k; 1.5 ~ @ ) { sout | i | j | k; } §\C{sout | nl;}§ 1066 1066 for ( i; 5 : j; @ -~ -5 ~ 2 : k; 1.5 ~ @ ) { sout | i | j | k; } §\C{sout | nl;}§ 1067 for ( i; 5 : k; 1.5 ~ @ : j; @ -~ -5 ~ 2 ) { sout | i | j | k; } §\C{sout | nl;} §1067 for ( i; 5 : k; 1.5 ~ @ : j; @ -~ -5 ~ 2 ) { sout | i | j | k; } §\C{sout | nl;}\CRT§ 1068 1068 \end{cfa} 1069 1069 & … … 2960 2960 The string ``©int (*f(x))[ 5 ]©'' declares a K\&R style routine of type returning a pointer to an array of 5 integers, while the string ``©[ 5 ] int x©'' declares a \CFA style parameter ©x© of type array of 5 integers. 2961 2961 Since the strings overlap starting with the open bracket, ©[©, there is an ambiguous interpretation for the string. 2962 2962 2963 As well, \CFA-style declarations cannot be used to declare parameters for C-style routine-definitions because of the following ambiguity: 2963 2964 \begin{cfa} … … 2965 2966 int f( int (* foo) ); §\C{// foo is redefined as a parameter name}§ 2966 2967 \end{cfa} 2967 The string ``©int (* foo)©'' declares a C-style named-parameter of type pointer to an integer (the parenthesis are superfluous), while the same string declares a \CFA style unnamed parameter of type routine returning integer with unnamed parameter of type pointer to foo.2968 The string ``©int (* foo)©'' declares a C-style named-parameter of type pointer to an integer (the parenthesis are superfluous), while the same string declares a \CFA style unnamed parameter of type routine returning integer with unnamed parameter of type pointer to ©foo©. 2968 2969 The redefinition of a type name in a parameter list is the only context in C where the character ©*© can appear to the left of a type name, and \CFA relies on all type qualifier characters appearing to the right of the type name. 2969 2970 The inability to use \CFA declarations in these two contexts is probably a blessing because it precludes programmers from arbitrarily switching between declarations forms within a declaration contexts. … … 3055 3056 static [ int ] g ( int ); 3056 3057 \end{cfa} 3058 3059 3060 \subsection{Postfix Function} 3061 \label{s:PostfixFunction} 3062 \index{postfix function} 3063 3064 \CFA provides an alternative call syntax where the argument appears before the function name. 3065 The syntax uses the backquote ©`© to separate the parameters/arguments and function name: ©?`© denotes a postfix-function name, \eg ©int ?`h( int s )© and ©`© denotes a postfix-function call, \eg ©0`h© meaning ©h( 0 )©. 3066 \begin{cquote} 3067 \begin{tabular}{@{}l|l|l|l@{}} 3068 postfix function & constant argument call & variable argument call & postfix function pointer \\ 3069 \hline 3070 \begin{cfa} 3071 int ?`h( int s ); 3072 int ?`h( double s ); 3073 int ?`m( char c ); 3074 int ?`m( const char * s ); 3075 int ?`t( int a, int b, int c ); 3076 \end{cfa} 3077 & 3078 \begin{cfa} 3079 0`h; 3080 3.5`h; 3081 '1'`m; 3082 "123" "456"`m; 3083 [1, 2, 3]`t; 3084 \end{cfa} 3085 & 3086 \begin{cfa} 3087 int i = 7; 3088 i`h; 3089 (i + 3)`h; 3090 (i + 3.5)`h; 3091 \end{cfa} 3092 & 3093 \begin{cfa} 3094 int (* ?`p)( int i ); 3095 ?`p = ?`h; 3096 3`p; 3097 i`p; 3098 (i + 3)`p; 3099 \end{cfa} 3100 \end{tabular} 3101 \end{cquote} 3102 Note, to pass \emph{multiple} arguments to a postfix function requires a \Index{tuple}, \eg ©[1, 2, 3]`t©, which forms a single argument that is flattened into the multiple arguments \see{\VRef{s:Tuple}}. 3103 Similarly, if the argument is an expression, it must be parenthesized, \eg ©(i + 3)`h©, or only the last operand of the expression is the argument, \eg ©i + (3`h)©. 3104 3105 \VRef[Figure]{f:UnitsComparison} shows a common usage for postfix functions: converting basic literals into user literals. 3106 \see*{\VRef{s:DynamicStorageManagement} for other uses for postfix functions.} 3107 The \CFA example (left) stores a mass in units of stones (1 stone = 14 lb or 6.35 kg) and provides an addition operator (imagine a full set of arithmetic operators). 3108 The three postfixing function names ©st©, ©lb©, and ©kg©, represent units stones, pounds, and kilograms, respectively. 3109 Each name has two forms that bidirectional convert: a value of a specified unit to stones, \eg ©w = 14`lb© $\Rightarrow$ ©w == 1© stone or a ©Weight© from stones back to specific units, \eg ©w`lb© (1 stone) to ©14©. 3110 All arithmetic operations manipulate stones and the postfix operations convert to the different units. 3111 A similar group of postfix functions provide user constants for converting time units into nanoseconds, which is the basic time unit, \eg ©ns©, ©us©, ©ms©, ©s©, ©m©, ©h©, ©d©, and ©w©, for nanosecond, microsecond, millisecond, second, minute, hour, day, and week, respectively. 3112 (Note, month is not a fixed period of time nor is year because of leap years.) 3113 3114 \begin{figure} 3115 \centering 3116 \begin{tabular}{@{}l|l@{}} 3117 \multicolumn{1}{@{}c|}{\textbf{\CFA Postfix Routine}} & \multicolumn{1}{c@{}}{\textbf{\CC User Literals}} \\ 3118 \hline 3119 \begin{cfa} 3120 struct Weight { 3121 double stones; 3122 }; 3123 3124 3125 Weight ?+?( Weight l, Weight r ) { 3126 return l.stones + r.stones; 3127 } 3128 Weight ®?`st®( double w ) { return w; } 3129 double ®?`st®( Weight w ) { return w.stones; } 3130 Weight ®?`lb®( double w ) { return w / 14.0; } 3131 double ®?`lb®( Weight w ) { return w.stones * 14.0; } 3132 Weight ®?`kg®( double w ) { return w / 6.35; } 3133 double ®?`kg®( Weight w ) { return w.stones * 6.35; } 3134 int main() { 3135 Weight w, heavy = { 20 }; // stones 3136 w = 155®`lb®; 3137 w = 0b_1111®`st®; 3138 w = 0_233®`lb®; 3139 w = 0x_9b®`kg®; 3140 w = 5.5®`st® + 8®`kg® + 25.01®`lb® + heavy; 3141 } 3142 \end{cfa} 3143 & 3144 \begin{C++} 3145 struct Weight { 3146 double stones; 3147 Weight() {} 3148 Weight( double w ) { stones = w; } 3149 }; 3150 Weight operator+( Weight l, Weight r ) { 3151 return l.stones + r.stones; 3152 } 3153 Weight operator®""_st®( long double w ) { return w; } 3154 Weight operator®""_lb®( long double w ) { return w / 14.0; } 3155 Weight operator®""_kg®( long double w ) { return w / 6.35; } 3156 Weight operator®""_st®( unsigned long long int w ) { return w; } 3157 Weight operator®""_lb®( unsigned long long int w ) { return w / 14.0; } 3158 Weight operator®""_kg®( unsigned long long int w ) { return w / 6.35; } 3159 int main() { 3160 Weight w, heavy = { 20 }; // stones 3161 w = 155®_lb®; 3162 w = 0b1111®_st®; 3163 w = 0'233®_lb®; // quote separator 3164 w = 0x9b®_kg®; 3165 w = 5.5®_st® + 8®_kg® + 25.01®_lb® + heavy; 3166 } 3167 \end{C++} 3168 \end{tabular} 3169 3170 \begin{comment} 3171 Time : comparison of time units. \\ 3172 \begin{tabular}{@{}ll@{}} 3173 \CFA & \CC \\ 3174 \begin{cfa} 3175 #include <fstream.hfa> 3176 #include <time.hfa> 3177 3178 3179 Duration s = 1`h + 2 * 10`m + 70`s / 10; 3180 sout | "1 hour + 2*10 min + 70/10 sec = " | s | "seconds"; 3181 sout | "Dividing that by 2 minutes gives" | s / 2`m; 3182 sout | "Dividing that by 2 gives" | s / 2 | "seconds\n"; 3183 sout | s | "seconds is" 3184 | s`h | "hours," 3185 | (s % 1`h)`m | "minutes," 3186 | (s % 1`m)`s | "seconds"; 3187 \end{cfa} 3188 & 3189 \begin{C++} 3190 #include <iostream> 3191 #include <chrono> 3192 using namespace std; 3193 using namespace std::chrono; 3194 seconds s = hours(1) + 2 * minutes(10) + seconds(70) / 10; 3195 cout << "1 hour + 2*10 min + 70/10 sec = " << s.count() << " seconds\n"; 3196 cout << "Dividing that by 2 minutes gives " << s / minutes(2) << '\n'; 3197 cout << "Dividing that by 2 gives " << (s / 2).count() << " seconds\n"; 3198 cout << s.count() << " seconds is " 3199 << duration_cast<hours>( s ).count() << " hours, " 3200 << duration_cast<minutes>( s % hours(1) ).count() << " minutes, " 3201 << duration_cast<seconds>( s % minutes(1) ).count() << " seconds\n"; 3202 \end{C++} 3203 \end{tabular} 3204 \end{comment} 3205 3206 \caption{Units: Stone, Pound, Kilogram Comparison} 3207 \label{f:UnitsComparison} 3208 \end{figure} 3209 3210 The \CC example (right) provides a \emph{restricted} capability via user literals. 3211 The \lstinline[language=C++]{operator ""} only takes a constant argument (\ie no variable argument), and the constant type must be the highest-level constant-type, \eg ©long double© for all floating-point constants. 3212 As well, there is no constant conversion, \ie ©int© to ©double© constants, so integral constants are handled by a separate set of routines, with maximal integral type ©unsigned long long int©. 3213 Finally, there is no mechanism to use this syntax for a bidirectional conversion because \lstinline[language=C++]{operator ""} does not accept variable arguments. 3057 3214 3058 3215 … … 3389 3546 3390 3547 \section{Tuple} 3548 \label{s:Tuple} 3391 3549 3392 3550 In C and \CFA, lists of elements appear in several contexts, such as the parameter list of a routine call. … … 3809 3967 \subsection{Polymorphism} 3810 3968 3811 Due to the implicit flattening and structuring conversions involved in argument passing, ©otype© and ©dtype©parameters are restricted to matching only with non-tuple types.3969 Due to the implicit flattening and structuring conversions involved in argument passing, object and opaque parameters are restricted to matching only with non-tuple types. 3812 3970 The integration of polymorphism, type assertions, and monomorphic specialization of tuple-assertions are a primary contribution of this thesis to the design of tuples. 3813 3971 \begin{cfa} 3814 forall(T, dtype U)3972 forall(T, U &) 3815 3973 void f(T x, U * y); 3816 3974 … … 4047 4205 [ §\emph{lvalue}§, ... , §\emph{lvalue}§ ] = §\emph{expr}§; 4048 4206 \end{cfa} 4049 \index{lvalue} 4050 The left-hand side is a tuple of \LstBasicStyle{\emph{lvalues}}, which is a list of expressions each yielding an address, \ie any data object that can appear on the left-hand side of a conventional assignment statement. 4207 The left-hand side is a tuple of \LstBasicStyle{\emph{\Index{lvalue}}}s, which is a list of expressions each yielding an address, \ie any data object that can appear on the left-hand side of a conventional assignment statement. 4051 4208 \LstBasicStyle{\emph{expr}} is any standard arithmetic expression. 4052 4209 Clearly, the types of the entities being assigned must be type compatible with the value of the expression. … … 4086 4243 Multiple assignment has the following form: 4087 4244 \begin{cfa} 4088 [ §\emph{lvalue}§, ... , §\emph{lvalue}§ ] = [ §\emph{expr}§, ... , §\emph{expr}§ ]; 4089 \end{cfa} 4090 \index{lvalue} 4091 The left-hand side is a tuple of \emph{lvalues}, and the right-hand side is a tuple of \emph{expr}s. 4092 Each \emph{expr} appearing on the right-hand side of a multiple assignment statement is assigned to the corresponding \emph{lvalues} on the left-hand side of the statement using parallel semantics for each assignment. 4245 [ §\emph{lvalue}§, ... , §\emph{lvalue}§ ] = [ §\emph{expr}§, ... , §\emph{expr}§ ];§ 4246 \end{cfa} 4247 The left-hand side is a tuple of \LstBasicStyle{\emph{\Index{lvalue}}}s, and the right-hand side is a tuple of \LstBasicStyle{\emph{expr}}s. 4248 Each \LstBasicStyle{\emph{expr}} appearing on the right-hand side of a multiple assignment statement is assigned to the corresponding \LstBasicStyle{\emph{lvalues}} on the left-hand side of the statement using parallel semantics for each assignment. 4093 4249 An example of multiple assignment is: 4094 4250 \begin{cfa} … … 4925 5081 sout | '1' | '2' | '3'; 4926 5082 sout | 1 | "" | 2 | "" | 3; 4927 sout | "x (" | 1 | "x [" | 2 | "x {" | 3 | "x =" | 4 | "x $" | 5 | "x £" | 6 | "x Â¥"4928 | 7 | "x ¡" | 8 | "x ¿" | 9 | "x «" | 10;5083 sout | "x (" | 1 | "x [" | 2 | "x {" | 3 | "x =" | 4 | "x $" | 5 | "x £" | 6 | "x ¥" 5084 | 7 | "x ¡" | 8 | "x ¿" | 9 | "x «" | 10; 4929 5085 sout | 1 | ", x" | 2 | ". x" | 3 | "; x" | 4 | "! x" | 5 | "? x" | 6 | "% x" 4930 | 7 | " ¢ x" | 8 | "» x" | 9 | ") x" | 10 | "] x" | 11 | "} x";5086 | 7 | "¢ x" | 8 | "» x" | 9 | ") x" | 10 | "] x" | 11 | "} x"; 4931 5087 sout | "x`" | 1 | "`x'" | 2 | "'x\"" | 3 | "\"x:" | 4 | ":x " | 5 | " x\t" | 6 | "\tx"; 4932 5088 sout | "x ( " | 1 | " ) x" | 2 | " , x" | 3 | " :x: " | 4; … … 7775 7931 \item[Rationale:] increase type safety 7776 7932 \item[Effect on original feature:] deletion of semantically well-defined feature. 7777 \item[Difficulty of converting:] requires adding a cast \see{\VRef{s: StorageManagement} for better alternatives}:7933 \item[Difficulty of converting:] requires adding a cast \see{\VRef{s:DynamicStorageManagement} for better alternatives}: 7778 7934 \begin{cfa} 7779 7935 int * b = (int *)malloc( sizeof(int) ); … … 7987 8143 \section{Standard Library} 7988 8144 \label{s:StandardLibrary} 7989 7990 The \CFA standard-library wraps explicitly-polymorphic C routines into implicitly-polymorphic versions. 7991 7992 7993 \subsection{Storage Management} 7994 \label{s:StorageManagement} 7995 7996 The 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. 7997 7998 C storage management provides the following capabilities: 7999 \begin{description} 8000 \item[filled] 8001 after allocation with a specified character or value. 8145 \index{standard library} 8146 8147 The \CFA standard-library extends existing C library routines by adding new function, wrapping existing explicitly-polymorphic C routines into implicitly-polymorphic versions, and adding new \CFA extensions. 8148 8149 8150 \subsection{Dynamic Storage-Management} 8151 \label{s:DynamicStorageManagement} 8152 \index{dynamic storage-management}\index{storage management} 8153 8154 Dynamic storage-management in C is based on explicit allocation and deallocation (©malloc©/©free©). 8155 Programmer's must manage all allocated storage via its address (pointer) and subsequently deallocate the storage via this address. 8156 Storage that is not deallocated becomes inaccessible, called a \newterm{memory leak}, which can only be detected at program termination. 8157 Storage freed twice is an error, called a \newterm{duplicate free}, which can sometimes be detected. 8158 Storage used after it is deallocated is an error, called using a \newterm{dangling pointer}, which can sometimes be detected. 8159 8160 8161 \subsubsection{C Interface} 8162 8163 C dynamic storage-management provides the following properties. 8164 \begin{description}[leftmargin=*] 8165 \item[fill] 8166 storage after an allocation with a specified character or value. 8167 \item[align] 8168 an allocation on a specified memory boundary, \eg, an address multiple of 64 or 128 for cache-line purposes. 8169 \item[scale] 8170 an allocation size to the specified number of array elements. 8171 An array may be filled, resized, or aligned. 8002 8172 \item[resize] 8003 8173 an existing allocation to decreased or increased its size. 8004 In either case, new storage may or may not be allocated and, if there is a new allocation, as much data from the existing allocation is copied into the new allocation. 8005 For an increase in storage size, new storage after the copied data may be filled. 8006 \item[align] 8007 an allocation on a specified memory boundary, \eg, an address multiple of 64 or 128 for cache-line purposes. 8008 \item[array] 8009 the allocation size is scaled to the specified number of array elements. 8010 An array may be filled, resized, or aligned. 8174 In either direction, new storage may or may not be allocated, but if there is a new allocation, as much data from the existing allocation is copied into the new allocation. 8175 When new storage is allocated, it may be aligned and storage after copied data may be filled. 8011 8176 \end{description} 8012 \VRef[Table]{t:AllocationVersusCapabilities} shows allocation routines supporting different combinations of storage-management capabilities. 8177 \VRef[Table]{t:AllocationVersusProperties} shows different combinations of storage-management properties provided by the C and \CFA allocation routines. 8178 8013 8179 \begin{table} 8180 \caption{Allocation Routines versus Storage-Management Properties} 8181 \label{t:AllocationVersusProperties} 8014 8182 \centering 8015 8183 \begin{minipage}{0.75\textwidth} 8016 8184 \begin{tabular}{@{}r|l|l|l|l|l@{}} 8017 \multicolumn{1}{c}{}& & \multicolumn{1}{c|}{fill} & resize & alignment & array\\8185 & \multicolumn{1}{c|}{routine} & \multicolumn{1}{c|}{\textbf{fill}} & \textbf{alignment} & \textbf{scale} & \textbf{resize} \\ 8018 8186 \hline 8019 8187 C & ©malloc© & no & no & no & no \\ 8020 & ©calloc© & yes (0 only) & no & no & yes \\ 8021 & ©realloc© & copy & yes & no & no \\ 8022 & ©memalign© & no & no & yes & no \\ 8023 & ©aligned_alloc©\footnote{Same as ©memalign© but size is an integral multiple of alignment, which is universally ignored.} 8024 & no & no & yes & no \\ 8025 & ©posix_memalign© & no & no & yes & no \\ 8026 & ©valloc© & no & no & yes (page size)& no \\ 8188 & ©calloc© & yes (0 only) & no & yes & no \\ 8189 & ©realloc© & copy & no & no & yes \\ 8190 & ©reallocarray© & copy & no & yes & yes \\ 8191 & ©memalign© & no & yes & no & no \\ 8192 & ©aligned_alloc©\footnote{Same as ©memalign© but size is an integral multiple of alignment.} 8193 & no & yes & no & no \\ 8194 & ©posix_memalign© & no & yes & no & no \\ 8195 & ©valloc© & no & yes (page size)& no & no \\ 8027 8196 & ©pvalloc©\footnote{Same as ©valloc© but rounds size to multiple of page size.} 8028 & no & no & yes (page size)& no \\ 8029 \hline 8030 \CFA & ©cmemalign© & yes (0 only) & no & yes & yes \\ 8031 & ©realloc© & copy & yes & yes & no \\ 8032 & ©alloc© & no & yes & no & yes \\ 8033 & ©alloc_set© & yes & yes & no & yes \\ 8034 & ©alloc_align© & no & yes & yes & yes \\ 8035 & ©alloc_align_set© & yes & yes & yes & yes \\ 8197 & no & yes (page size)& no & no \\ 8198 \hline 8199 \CFA & ©cmemalign© & yes (0 only) & yes & yes & no \\ 8200 & ©resize© & no copy & yes & no & yes \\ 8201 & ©realloc© & copy & yes & no & yes \\ 8202 & ©alloc©\footnote{Multiple overloads with different parameters.} 8203 & yes & yes & yes & yes 8036 8204 \end{tabular} 8037 8205 \end{minipage} 8038 \caption{Allocation Routines versus Storage-Management Capabilities} 8039 \label{t:AllocationVersusCapabilities} 8206 \vspace*{-10pt} 8040 8207 \end{table} 8041 8208 8042 \CFA memory management extends the type safety of all allocations by using the type of the left-hand-side type to determine the allocation size and return a matching type for the new storage. 8043 Type-safe allocation is provided for all C allocation routines and new \CFA allocation routines, \eg in 8044 \begin{cfa} 8045 int * ip = (int *)malloc( sizeof(int) ); §\C{// C}§ 8046 int * ip = malloc(); §\C{// \CFA type-safe version of C malloc}§ 8047 int * ip = alloc(); §\C{// \CFA type-safe uniform alloc}§ 8048 \end{cfa} 8049 the latter two allocations determine the allocation size from the type of ©p© (©int©) and cast the pointer to the allocated storage to ©int *©. 8050 8051 \CFA memory management extends allocation safety by implicitly honouring all alignment requirements, \eg in 8052 \begin{cfa} 8053 struct S { int i; } __attribute__(( aligned( 128 ) )); // cache-line alignment 8054 S * sp = malloc(); §\C{// honour type alignment}§ 8055 \end{cfa} 8056 the storage allocation is implicitly aligned to 128 rather than the default 16. 8057 The alignment check is performed at compile time so there is no runtime cost. 8058 8059 \CFA memory management extends the resize capability with the notion of \newterm{sticky properties}. 8060 Hence, initial allocation capabilities are remembered and maintained when resize requires copying. 8061 For example, an initial alignment and fill capability are preserved during a resize copy so the copy has the same alignment and extended storage is filled. 8062 Without sticky properties it is dangerous to use ©realloc©, resulting in an idiom of manually performing the reallocation to maintain correctness. 8063 \begin{cfa} 8064 8065 \end{cfa} 8066 8067 \CFA memory management extends allocation to support constructors for initialization of allocated storage, \eg in 8068 \begin{cfa} 8069 struct S { int i; }; §\C{// cache-line alignment}§ 8070 void ?{}( S & s, int i ) { s.i = i; } 8071 // assume ?|? operator for printing an S 8072 8073 S & sp = *®new®( 3 ); §\C{// call constructor after allocation}§ 8074 sout | sp.i; 8075 ®delete®( &sp ); 8076 8077 S * spa = ®anew®( 10, 5 ); §\C{// allocate array and initialize each array element}§ 8078 for ( i; 10 ) sout | spa[i] | nonl; 8079 sout | nl; 8080 ®adelete®( 10, spa ); 8209 8210 \subsubsection{\CFA Interface} 8211 8212 \CFA dynamic memory management: 8213 \begin{enumerate}[leftmargin=\parindent] 8214 \item 8215 extends type safety of all allocation routines by using the left-hand assignment type to determine the allocation size and alignment, and return a matching type for the new storage, which removes many common allocation errors. 8216 \begin{cfa} 8217 int * ip = (int *)malloc( sizeof(int) ); §\C[2.3in]{// C}§ 8218 int * ip = malloc(); §\C{// \CFA type-safe call of C malloc}§ 8219 int * ip = calloc(); §\C{// \CFA type-safe call of C calloc}§ 8220 struct __attribute__(( aligned(128) )) spinlock { ... }; // cache alignment 8221 spinlock * slp = malloc(); §\C{// correct size, alignment, and return type}\CRT§ 8222 \end{cfa} 8223 Here, the alignment of the ©ip© storage is 16 (default) and 128 for ©slp©. 8224 8225 \item 8226 introduces the notion of \newterm{sticky properties} used in resizing. 8227 All initial allocation properties are remembered and maintained for use should resize require new storage. 8228 For example, the initial alignment and fill properties in the initial allocation 8229 \begin{cfa} 8230 struct __attribute__(( aligned(4096) )) S { ... }; 8231 S * sp = calloc( 10 ); §\C{// align 4K and zero fill}§ 8232 sp = reallocarray( sp, 100 ); §\C{// preserve 4K alignment and zero fill new storage}§ 8233 \end{cfa} 8234 are preserved in the resize so the new storage has the same alignment and extra storage after the data copy is zero filled. 8235 Without sticky properties it is dangerous to resize, resulting in the C idiom of manually performing the reallocation to maintain correctness, which is error prone. 8236 8237 \item 8238 provides resizing without data copying, which is useful to repurpose an existing block of storage, rather than freeing the old storage and performing a new allocation. 8239 A resize can take advantage of unused storage after the data to preventing a free/reallocation step altogether. 8240 8241 \item 8242 provides ©free©/©delete© functions that delete a variable number of allocations. 8243 \begin{cfa} 8244 int * ip = malloc(), * jp = malloc(), * kp = malloc(); 8245 double * xp = malloc(), * yp = malloc(), * zp = malloc(); 8246 free( ®ip, jp, kp, xp, yp, zp® ); §\C{// multiple deallocations}§ 8247 \end{cfa} 8248 8249 \item 8250 supports constructors for initialization of allocated storage and destructors for deallocation (like \CC). 8251 \begin{cfa} 8252 struct S { int v; }; §\C{// default constructors}§ 8253 void ^?{}( S & ) { ... } §\C{// destructor}§ 8254 S & sp = *®new®( 3 ); §\C{// allocate and call constructor}§ 8255 sout | sp.v; 8256 ®delete®( &sp ); §\C{// call destructor}§ 8257 S * spa1 = ®anew®( 10, 5 ), * spa2 = ®anew®( 10, 8 ); §\C{// allocate array and call constructor for each array element}§ 8258 for ( i; 10 ) sout | spa1[i].v | spa2[i].v | nonl; sout | nl; 8259 ®adelete®( spa1, spa2 ); §\C{// call destructors on all array objects}§ 8260 8261 3 8262 5 8 5 8 5 8 5 8 5 8 5 8 5 8 5 8 5 8 5 8 8081 8263 \end{cfa} 8082 8264 Allocation routines ©new©/©anew© allocate a variable/array and initialize storage using the allocated type's constructor. 8083 8265 Note, the matching deallocation routines ©delete©/©adelete©. 8084 8085 \leavevmode 8266 \CC only supports the default constructor for intializing array elements. 8267 \begin{C++} 8268 S * sp = new S[10]®{5}®; §\C{// disallowed}§ 8269 \end{C++} 8270 \end{enumerate} 8271 8272 In addition, \CFA provides a new allocator interface to further increase orthogonality and usability of dynamic-memory allocation. 8273 This interface helps programmers in three ways. 8274 \begin{enumerate} 8275 \item 8276 naming: \CFA regular and ©ttype© polymorphism (similar to \CC variadic templates) is used to encapsulate a wide range of allocation functionality into a single routine name, so programmers do not have to remember multiple routine names for different kinds of dynamic allocations. 8277 \item 8278 named arguments: individual allocation properties are specified using postfix function call \see{\VRef{s:PostfixFunction}}, so programmers do not have to remember parameter positions in allocation calls. 8279 \item 8280 safe usage: like the \CFA's C-interface, programmers do not have to specify object size or cast allocation results. 8281 \end{enumerate} 8282 8283 The polymorphic functions 8284 \begin{cfa} 8285 T * alloc( ... ); 8286 T * alloc( size_t dim, ... ); 8287 \end{cfa} 8288 are overloaded with a variable number of allocation properties. 8289 These allocation properties can be passed as named arguments when calling the \Indexc{alloc} routine. 8290 A call without parameters returns an uninitialized dynamically allocated object of type ©T© (\Indexc{malloc}). 8291 A call with only the dimension (dim) parameter returns an uninitialized dynamically allocated array of objects with type ©T© (\Indexc{aalloc}). 8292 The variable number of arguments consist of allocation properties to specialize the allocation. 8293 The properties ©resize© and ©realloc© are associated with an existing allocation variable indicating how its storage is modified. 8294 8295 The following allocation property functions may be combined and appear in any order as arguments to ©alloc©, 8296 \begin{itemize} 8297 \item 8298 ©T_align ?`align( size_t alignment )© to align an allocation. 8299 The alignment parameter must be $\ge$ the default alignment (©libAlign()© in \CFA) and a power of two, \eg the following return a dynamic object and object array aligned on a 256 and 4096-byte boundary. 8300 \begin{cfa} 8301 int * i0 = alloc( ®256`align® ); sout | i0 | nl; 8302 int * i1 = alloc( 3, ®4096`align® ); for (i; 3 ) sout | &i1[i] | nonl; sout | nl; 8303 free( i0, i1 ); 8304 8305 0x5555565699®00® // 256 alignment 8306 0x55555656c®000® 0x5656c004 0x5656c008 // 4K array alignment 8307 \end{cfa} 8308 8309 \item 8310 ©T_fill(T) ?`fill( /* various types */ )© to initialize storage. 8311 There are three ways to fill storage: 8312 \begin{enumerate} 8313 \item 8314 A ©char© fills every byte of each object. 8315 \item 8316 An object of the returned type fills each object. 8317 \item 8318 An object array pointer fills some or all of the corresponding object array. 8319 \end{enumerate} 8320 For example: 8321 \begin{cfa}[numbers=left] 8322 int * i0 = alloc( ®0n`fill® ); sout | *i0 | nl; // 0n disambiguates 0p 8323 int * i1 = alloc( ®5`fill® ); sout | *i1 | nl; 8324 int * i2 = alloc( ®'\xfe'`fill® ); sout | hex( *i2 ) | nl; 8325 int * i3 = alloc( 5, ®5`fill® ); for ( i; 5 ) sout | i3[i] | nonl; sout | nl; 8326 int * i4 = alloc( 5, ®0xdeadbeefN`fill® ); for ( i; 5 ) sout | hex( i4[i] ) | nonl; sout | nl; 8327 int * i5 = alloc( 5, ®i3`fill® ); for ( i; 5 ) sout | i5[i] | nonl; sout | nl; // completely fill from i3 8328 int * i6 = alloc( 5, ®[i3, 3]`fill® ); for ( i; 5 ) sout | i6[i] | nonl; sout | nl; // partial fill from i3 8329 free( i0, i1, i2, i3, i4, i5, i6 ); 8330 \end{cfa} 8331 \begin{lstlisting}[numbers=left] 8332 0 8333 5 8334 0xfefefefe 8335 5 5 5 5 5 8336 0xdeadbeef 0xdeadbeef 0xdeadbeef 0xdeadbeef 0xdeadbeef 8337 5 5 5 5 5 8338 5 5 5 -555819298 -555819298 // two undefined values 8339 \end{lstlisting} 8340 Examples 1 to 3 fill an object with a value or characters. 8341 Examples 4 to 7 fill an array of objects with values, another array, or part of an array. 8342 8343 \item 8344 ©S_resize(T) ?`resize( void * oaddr )© used to resize, realign, and fill, where the old object data is not copied to the new object. 8345 The old object type may be different from the new object type, since the values are not used. 8346 For example: 8347 \begin{cfa}[numbers=left] 8348 int * ip = alloc( ®5`fill® ); sout | ip | *ip; 8349 ip = alloc( ®ip`resize®, ®256`align®, ®7`fill® ); sout | ip | *ip; 8350 double * dp = alloc( ®ip`resize®, ®4096`align®, ®13.5`fill® ); sout | dp | *dp; 8351 free( dp ); // DO NOT FREE ip AS ITS STORAGE IS MOVED TO dp 8352 \end{cfa} 8353 \begin{lstlisting}[numbers=left] 8354 0x555555580a80 5 8355 0x555555581100 7 8356 0x555555587000 13.5 8357 \end{lstlisting} 8358 Examples 2 to 3 change the alignment, fill, and size for the initial storage of ©i©. 8359 8360 \begin{cfa}[numbers=left] 8361 int * ia = alloc( 5, ®5`fill® ); sout | ia | nonl; for ( i; 5 ) sout | ia[i] | nonl; sout | nl; 8362 ia = alloc( 10, ®ia`resize®, ®7`fill® ); sout | ia | nonl; for ( i; 10 ) sout | ia[i] | nonl; sout | nl; 8363 ia = alloc( 5, ®ia`resize®, ®512`align®, ®13`fill® ); sout | ia | nonl; for ( i; 5 ) sout | ia[i] | nonl; sout | nl;; 8364 ia = alloc( 3, ®ia`resize®, ®4096`align®, ®2`fill® ); for ( i; 3 ) sout | &ia[i] | ia[i] | nonl; sout | nl; 8365 free( ia ); 8366 \end{cfa} 8367 \begin{lstlisting}[numbers=left] 8368 0x55555656d540 5 5 5 5 5 8369 0x55555656d480 7 7 7 7 7 7 7 7 7 7 8370 0x55555656fe00 13 13 13 13 13 8371 0x555556570000 2 0x555556570004 2 0x555556570008 2 8372 \end{lstlisting} 8373 Examples 2 to 4 change the array size, alignment, and fill initializes all storage because no data is copied. 8374 8375 \item 8376 ©S_realloc(T) ?`realloc( T * a ))© 8377 used to resize, realign, and fill, where the old object data is copied to the new object. 8378 The old object type must be the same as the new object type, since the value is used. 8379 Note, for ©fill©, only the extra space after copying the data from the old object is filled with the given parameter. 8380 For example: 8381 \begin{cfa}[numbers=left] 8382 int * ip = alloc( ®5`fill® ); sout | ip | *ip; 8383 ip = alloc( ®ip`realloc®, ®256`align® ); sout | ip | *ip; 8384 ip = alloc( ®ip`realloc®, ®4096`align®, ®13`fill® ); sout | ip | *ip; 8385 free( ip ); 8386 \end{cfa} 8387 \begin{lstlisting}[numbers=left] 8388 0x55555556d5c0 5 8389 0x555555570000 5 8390 0x555555571000 5 8391 \end{lstlisting} 8392 Examples 2 to 3 change the alignment for the initial storage of ©i©. 8393 The ©13`fill© in example 3 does nothing because no new storage is added. 8394 8395 \begin{cfa}[numbers=left] 8396 int * ia = alloc( 5, ®5`fill® ); sout | ia | nonl; for ( i; 5 ) sout | ia[i] | nonl; sout | nl; 8397 ia = alloc( 10, ®ia`realloc®, ®7`fill® ); sout | ia | nonl; for ( i; 10 ) sout | ia[i] | nonl; sout | nl; 8398 ia = alloc( 5, ®ia`realloc®, ®512`align®, ®13`fill® ); sout | ia | nonl; for ( i; 5 ) sout | ia[i] | nonl; sout | nl;; 8399 ia = alloc( 3, ®ia`realloc®, ®4096`align®, ®2`fill® ); for ( i; 3 ) sout | &ia[i] | ia[i] | nonl; sout | nl; 8400 free( ia ); 8401 \end{cfa} 8402 \begin{lstlisting}[numbers=left] 8403 0x55555656d540 5 5 5 5 5 8404 0x55555656d480 7 7 7 7 7 7 7 7 7 7 8405 0x555556570e00 5 5 5 5 5 8406 0x5555556571000 5 0x555556571004 5 0x555556571008 5 8407 \end{lstlisting} 8408 Examples 2 to 4 change the array size, alignment, and fill does no initialization after the copied data, as no new storage is added. 8409 \end{itemize} 8410 8411 \medskip 8086 8412 \begin{cfa}[aboveskip=0pt,belowskip=0pt] 8087 8413 extern "C" { 8088 // C unsafe allocation 8089 void * malloc( size_t size );§\indexc{malloc}§ 8090 void * calloc( size_t dim, size_t size );§\indexc{calloc}§ 8091 void * realloc( void * ptr, size_t size );§\indexc{realloc}§ 8092 void * memalign( size_t align, size_t size );§\indexc{memalign}§ 8093 void * aligned_alloc( size_t align, size_t size );§\indexc{aligned_alloc}§ 8094 int posix_memalign( void ** ptr, size_t align, size_t size );§\indexc{posix_memalign}§ 8095 void * cmemalign( size_t alignment, size_t noOfElems, size_t elemSize );§\indexc{cmemalign}§ // CFA 8096 8097 // C unsafe initialization/copy 8098 void * memset( void * dest, int c, size_t size );§\indexc{memset}§ 8099 void * memcpy( void * dest, const void * src, size_t size );§\indexc{memcpy}§ 8100 } 8101 8102 void * realloc( void * oaddr, size_t nalign, size_t size ); // CFA heap 8103 8104 forall( dtype T | sized(T) ) { 8105 // §\CFA§ safe equivalents, i.e., implicit size specification 8106 T * malloc( void ); 8107 T * calloc( size_t dim ); 8108 T * realloc( T * ptr, size_t size ); 8109 T * memalign( size_t align ); 8110 T * cmemalign( size_t align, size_t dim ); 8111 T * aligned_alloc( size_t align ); 8112 int posix_memalign( T ** ptr, size_t align ); 8414 // New C allocation operations. 8415 void * aalloc( size_t dim, size_t elemSize );§\indexc{aalloc}§ 8416 void * resize( void * oaddr, size_t size );§\indexc{resize}§ 8417 void * amemalign( size_t align, size_t dim, size_t elemSize );§\indexc{amemalign}§ 8418 void * cmemalign( size_t align, size_t dim, size_t elemSize );§\indexc{cmemalign}§ 8419 size_t malloc_alignment( void * addr );§\indexc{malloc_alignment}§ 8420 bool malloc_zero_fill( void * addr );§\indexc{malloc_zero_fill}§ 8421 size_t malloc_size( void * addr );§\indexc{malloc_size}§ 8422 int malloc_stats_fd( int fd );§\indexc{malloc_stats_fd}§ 8423 size_t malloc_expansion();§\indexc{malloc_expansion}§ §\C{// heap expansion size (bytes)}§ 8424 size_t malloc_mmap_start();§\indexc{malloc_mmap_start}§ §\C{// crossover allocation size from sbrk to mmap}§ 8425 size_t malloc_unfreed();§\indexc{malloc_unfreed()}§ §\C{// heap unfreed size (bytes)}§ 8426 void malloc_stats_clear();§\indexc{malloc_stats_clear}§ §\C{// clear heap statistics}§ 8427 } 8428 8429 // New allocation operations. 8430 void * resize( void * oaddr, size_t alignment, size_t size ); 8431 void * realloc( void * oaddr, size_t alignment, size_t size ); 8432 void * reallocarray( void * oaddr, size_t nalign, size_t dim, size_t elemSize ); 8433 8434 forall( T & | sized(T) ) { 8435 // §\CFA§ safe equivalents, i.e., implicit size specification, eliminate return-type cast 8436 T * malloc( void );§\indexc{malloc}§ 8437 T * aalloc( size_t dim );§\indexc{aalloc}§ 8438 T * calloc( size_t dim );§\indexc{calloc}§ 8439 T * resize( T * ptr, size_t size );§\indexc{resize}§ 8440 T * resize( T * ptr, size_t alignment, size_t size ); 8441 T * realloc( T * ptr, size_t size );§\indexc{realloc}§ 8442 T * realloc( T * ptr, size_t alignment, size_t size ); 8443 T * reallocarray( T * ptr, size_t dim );§\indexc{reallocarray}§ 8444 T * reallocarray( T * ptr, size_t alignment, size_t dim ); 8445 T * memalign( size_t align );§\indexc{memalign}§ 8446 T * amemalign( size_t align, size_t dim );§\indexc{amemalign}§ 8447 T * cmemalign( size_t align, size_t dim );§\indexc{aalloc}§ 8448 T * aligned_alloc( size_t align );§\indexc{aligned_alloc}§ 8449 int posix_memalign( T ** ptr, size_t align );§\indexc{posix_memalign}§ 8450 T * valloc( void );§\indexc{valloc}§ 8451 T * pvalloc( void );§\indexc{pvalloc}§ 8113 8452 8114 8453 // §\CFA§ safe general allocation, fill, resize, alignment, array 8115 T * alloc( void );§\indexc{alloc}§ §\C[3.5in]{// variable, T size}§ 8116 T * alloc( size_t dim ); §\C{// array[dim], T size elements}§ 8117 T * alloc( T ptr[], size_t dim ); §\C{// realloc array[dim], T size elements}§ 8118 8119 T * alloc_set( char fill );§\indexc{alloc_set}§ §\C{// variable, T size, fill bytes with value}§ 8120 T * alloc_set( T fill ); §\C{// variable, T size, fill with value}§ 8121 T * alloc_set( size_t dim, char fill ); §\C{// array[dim], T size elements, fill bytes with value}§ 8122 T * alloc_set( size_t dim, T fill ); §\C{// array[dim], T size elements, fill elements with value}§ 8123 T * alloc_set( size_t dim, const T fill[] ); §\C{// array[dim], T size elements, fill elements with array}§ 8124 T * alloc_set( T ptr[], size_t dim, char fill ); §\C{// realloc array[dim], T size elements, fill bytes with value}§ 8125 8126 T * alloc_align( size_t align ); §\C{// aligned variable, T size}§ 8127 T * alloc_align( size_t align, size_t dim ); §\C{// aligned array[dim], T size elements}§ 8128 T * alloc_align( T ptr[], size_t align ); §\C{// realloc new aligned array}§ 8129 T * alloc_align( T ptr[], size_t align, size_t dim ); §\C{// realloc new aligned array[dim]}§ 8130 8131 T * alloc_align_set( size_t align, char fill ); §\C{// aligned variable, T size, fill bytes with value}§ 8132 T * alloc_align_set( size_t align, T fill ); §\C{// aligned variable, T size, fill with value}§ 8133 T * alloc_align_set( size_t align, size_t dim, char fill ); §\C{// aligned array[dim], T size elements, fill bytes with value}§ 8134 T * alloc_align_set( size_t align, size_t dim, T fill ); §\C{// aligned array[dim], T size elements, fill elements with value}§ 8135 T * alloc_align_set( size_t align, size_t dim, const T fill[] ); §\C{// aligned array[dim], T size elements, fill elements with array}§ 8136 T * alloc_align_set( T ptr[], size_t align, size_t dim, char fill ); §\C{// realloc new aligned array[dim], fill new bytes with value}§ 8137 8138 // §\CFA§ safe initialization/copy, i.e., implicit size specification 8139 T * memset( T * dest, char fill );§\indexc{memset}§ 8140 T * memcpy( T * dest, const T * src );§\indexc{memcpy}§ 8141 8142 // §\CFA§ safe initialization/copy, i.e., implicit size specification, array types 8143 T * amemset( T dest[], char fill, size_t dim ); 8454 T * alloc( ... );§\indexc{alloc}§ §\C{// variable, T size}§ 8455 T * alloc( size_t dim, ... ); 8456 T_align ?`align( size_t alignment );§\indexc{align}§ 8457 T_fill(T) ?`fill( /* various types */ );§\indexc{fill}§ 8458 T_resize ?`resize( void * oaddr );§\indexc{resize}§ 8459 T_realloc ?`realloc( void * oaddr ));§\indexc{realloc}§ 8460 } 8461 8462 forall( T &, List ... ) void free( T * ptr, ... ) // deallocation list 8463 8464 // §\CFA§ allocation/deallocation and constructor/destructor, non-array types 8465 forall( T &, Parms ... | { void ?{}( T &, Parms ); } ) T * new( Parms ... );§\indexc{new}§ 8466 forall( T &, List ... | { void ^?{}( T & ); void delete( List ... ); } );§\indexc{delete}§ 8467 // §\CFA§ allocation/deallocation and constructor/destructor, array types 8468 forall( T & | sized(T), Parms ... | { void ?{}( T &, Parms ); } ) T * anew( size_t dim, Parms ... );§\indexc{anew}§ 8469 forall( T & | sized(T) | { void ^?{}( T & ); }, List ... } ) void adelete( T arr[], List ... );§\indexc{adelete}§ 8470 \end{cfa} 8471 8472 8473 \subsection{Memory Set and Copy} 8474 8475 Like safe memory allocation, \CFA provides safe block initialization and copy. 8476 While objects should be initialized/copied with constructors/assignment, block operations can be very performant. 8477 In certain cases the compiler generates block copy operations, such as assigning structures ©s = t©, however C arrays cannot be assigned. 8478 \begin{cquote} 8479 \begin{cfa}[aboveskip=0pt,belowskip=0pt] 8480 struct S { int i, j, k; }; 8481 S s, t, *sp = &s, * tp = &t, sa[10], ta[10]; 8482 \end{cfa} 8483 \noindent 8484 \begin{tabular}{@{}l|l@{}} 8485 \multicolumn{1}{@{}c|}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}} \\ 8486 \begin{cfa}[aboveskip=0pt,belowskip=0pt] 8487 memset( s, '\0' ); 8488 memset( sp, '\0' ); 8489 8490 memcpy( s, t ); 8491 memcpy( sp, tp ); 8492 8493 amemset( sa, '\0', 10 ); 8494 amemcpy( sa, ta, 10 ); 8495 \end{cfa} 8496 & 8497 \begin{cfa}[aboveskip=0pt,belowskip=0pt] 8498 memset( &s, '\0', sizeof(s) ); 8499 memset( sp, '\0', sizeof(s) ); 8500 8501 memcpy( &s, &t, sizeof(s) ); 8502 memcpy( sp, tp, sizeof(s) ); 8503 8504 memset( sa, '\0', sizeof(sa) ); 8505 memcpy( sa, ta, sizeof(sa) ); 8506 \end{cfa} 8507 \end{tabular} 8508 \end{cquote} 8509 These operations provide uniformity between reference and pointer, so object dereferencing, '©&©', is unnecessary. 8510 8511 \begin{cfa} 8512 static inline forall( T & | sized(T) ) { 8513 // CFA safe initialization/copy, i.e., implicit size specification, non-array types 8514 T * memset( T * dest, char fill );§\indexc{memset}§ §\C{// all combinations of pointer/reference}§ 8515 T * memset( T & dest, char fill ); 8516 8517 T * memcpy( T * dest, const T * src );§\indexc{memcpy}§ §\C{// all combinations of pointer/reference}§ 8518 T * memcpy( T & dest, const T & src ); 8519 T * memcpy( T * dest, const T & src ); 8520 T * memcpy( T & dest, const T * src ); 8521 8522 // CFA safe initialization/copy, i.e., implicit size specification, array types 8523 T * amemset( T dest[], char fill, size_t dim );§\indexc{memcpy}§ 8144 8524 T * amemcpy( T dest[], const T src[], size_t dim ); 8145 8525 } 8146 8147 // §\CFA§ allocation/deallocation and constructor/destructor, non-array types8148 forall( dtype T | sized(T), ttype Params | { void ?{}( T &, Params ); } ) T * new( Params p );§\indexc{new}§8149 forall( dtype T | sized(T) | { void ^?{}( T & ); } ) void delete( T * ptr );§\indexc{delete}§8150 forall( dtype T, ttype Params | sized(T) | { void ^?{}( T & ); void delete( Params ); } )8151 void delete( T * ptr, Params rest );8152 8153 // §\CFA§ allocation/deallocation and constructor/destructor, array types8154 forall( dtype T | sized(T), ttype Params | { void ?{}( T &, Params ); } ) T * anew( size_t dim, Params p );§\indexc{anew}§8155 forall( dtype T | sized(T) | { void ^?{}( T & ); } ) void adelete( size_t dim, T arr[] );§\indexc{adelete}§8156 forall( dtype T | sized(T) | { void ^?{}( T & ); }, ttype Params | { void adelete( Params ); } )8157 void adelete( size_t dim, T arr[], Params rest );8158 8526 \end{cfa} 8159 8527 … … 9290 9658 Int sqrt( Int oper ); 9291 9659 9292 forall( dtype istype| istream( istype ) ) istype * ?|?( istype * is, Int * mp ); §\C{// I/O}§9293 forall( dtype ostype| ostream( ostype ) ) ostype * ?|?( ostype * os, Int mp );9660 forall( istype & | istream( istype ) ) istype * ?|?( istype * is, Int * mp ); §\C{// I/O}§ 9661 forall( ostype & | ostream( ostype ) ) ostype * ?|?( ostype * os, Int mp ); 9294 9662 \end{cfa} 9295 9663 \VRef[Figure]{f:MultiPrecisionFactorials} shows \CFA and C factorial programs using the GMP interfaces. … … 9299 9667 \begin{cquote} 9300 9668 \begin{tabular}{@{}l@{\hspace{\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}} 9301 \multicolumn{1}{@{}c|@{\hspace{\parindentlnth}}}{\textbf{ C}} & \multicolumn{1}{@{\hspace{\parindentlnth}}c@{}}{\textbf{\CFA}} \\9669 \multicolumn{1}{@{}c|@{\hspace{\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{@{\hspace{\parindentlnth}}c@{}}{\textbf{C}} \\ 9302 9670 \hline 9671 \begin{cfa} 9672 #include <gmp.hfa>§\indexc{gmp}§ 9673 int main( void ) { 9674 sout | "Factorial Numbers"; 9675 ®Int® fact = 1; 9676 9677 sout | 0 | fact; 9678 for ( i; 40 ) { 9679 fact *= i; 9680 sout | i | fact; 9681 } 9682 } 9683 \end{cfa} 9684 & 9303 9685 \begin{cfa} 9304 9686 #include <gmp.h>§\indexc{gmp.h}§ … … 9311 9693 ®mpz_mul_ui®( fact, fact, i ); 9312 9694 ®gmp_printf®( "%d %Zd\n", i, fact ); 9313 }9314 }9315 \end{cfa}9316 &9317 \begin{cfa}9318 #include <gmp.hfa>§\indexc{gmp}§9319 int main( void ) {9320 sout | "Factorial Numbers";9321 Int fact = 1;9322 9323 sout | 0 | fact;9324 for ( i; 40 ) {9325 fact *= i;9326 sout | i | fact;9327 9695 } 9328 9696 } … … 9419 9787 Rational narrow( double f, long int md ); 9420 9788 9421 forall( dtype istype| istream( istype ) ) istype * ?|?( istype *, Rational * ); // I/O9422 forall( dtype ostype| ostream( ostype ) ) ostype * ?|?( ostype *, Rational );9789 forall( istype & | istream( istype ) ) istype * ?|?( istype *, Rational * ); // I/O 9790 forall( ostype & | ostream( ostype ) ) ostype * ?|?( ostype *, Rational ); 9423 9791 \end{cfa} 9424 9792 … … 9440 9808 \end{document} 9441 9809 9810 From: Michael Leslie Brooks <mlbrooks@uwaterloo.ca> 9811 To: Peter Buhr <pabuhr@uwaterloo.ca>, 9812 Andrew James Beach 9813 <ajbeach@uwaterloo.ca>, 9814 Fangren Yu <f37yu@uwaterloo.ca>, Jiada Liang 9815 <j82liang@uwaterloo.ca> 9816 Subject: The White House on Memory-Safe programming 9817 Date: Mon, 4 Mar 2024 16:49:53 +0000 9818 9819 I heard tell of this announcement last night. Haven't read the actual report yet. 9820 9821 Most mainstream article I can find: https://me.pcmag.com/en/security/22413/white-house-to-developers-using-c-or-c-invites-cybersecurity-risks 9822 Less fluffy summary: https://www.developer-tech.com/news/2024/feb/27/white-house-urges-adoption-memory-safe-programming-languages/ 9823 Horse's Mouth: https://www.whitehouse.gov/wp-content/uploads/2024/02/Final-ONCD-Technical-Report.pdf 9824 "This report focuses on the programming language as a primary building block, and explores hardware architecture and formal methods as complementary approaches" 9825 9826 A contrary analysis: https://hackaday.com/2024/02/29/the-white-house-memory-safety-appeal-is-a-security-red-herring/ 9827 9442 9828 % Local Variables: % 9443 9829 % tab-width: 4 % -
libcfa/src/concurrency/actor.hfa
rcf191ac r7042c60 299 299 300 300 if ( seperate_clus ) { 301 cluster = alloc();301 this.cluster = alloc(); 302 302 (*cluster){}; 303 303 } else cluster = active_cluster(); … … 360 360 adelete( worker_req_queues ); 361 361 adelete( processors ); 362 if ( seperate_clus ) delete( cluster );362 if ( seperate_clus ) delete( this.cluster ); 363 363 364 364 #ifdef ACTOR_STATS // print formatted stats -
libcfa/src/concurrency/kernel/fwd.hfa
rcf191ac r7042c60 374 374 // since if that is the case, the oneshot was fulfilled (unparking this thread) 375 375 // and the oneshot should not be needed any more 376 __attribute__((unused)) struct oneshot * was = this.ptr;376 struct oneshot * was __attribute__((unused)) = this.ptr; // used in option verify 377 377 /* paranoid */ verifyf( was == future_FULFILLED, "Expected this.ptr to be 1p, was %p\n", was ); 378 378 -
libcfa/src/device/cpu.cfa
rcf191ac r7042c60 239 239 // Returns a 2D array of instances of size [cpu count][cache levels] 240 240 // where cache level doesn't include instruction caches 241 raw_cache_instance ** build_raw_cache_table(unsigned cpus_c, idx_range_t cpus, unsigned idxs, unsigned cache_levels) 242 { 241 raw_cache_instance ** build_raw_cache_table(unsigned cpus_c, idx_range_t cpus, unsigned idxs, unsigned cache_levels) { 243 242 raw_cache_instance ** raw = alloc(cpus_c, '\0'`fill); 244 243 -
libcfa/src/iostream.hfa
rcf191ac r7042c60 10 10 // Created On : Wed May 27 17:56:53 2015 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Tue Feb 6 18:35:54202413 // Update Count : 74 312 // Last Modified On : Sun Apr 21 07:32:19 2024 13 // Update Count : 744 14 14 // 15 15 … … 160 160 161 161 // tuples 162 forall( ostype &, T, Params... | writeable( T, ostype ) | { ostype & ?|?( ostype &, Params); } ) {163 ostype & ?|?( ostype & os, T arg, Paramsrest );164 void ?|?( ostype & os, T arg, Paramsrest );162 forall( ostype &, T, List ... | writeable( T, ostype ) | { ostype & ?|?( ostype &, List ); } ) { 163 ostype & ?|?( ostype & os, T arg, List rest ); 164 void ?|?( ostype & os, T arg, List rest ); 165 165 } // distribution 166 166 -
libcfa/src/stdlib.cfa
rcf191ac r7042c60 10 10 // Created On : Thu Jan 28 17:10:29 2016 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Sun Mar 17 08:25:32 202413 // Update Count : 69912 // Last Modified On : Sun Apr 21 16:17:22 2024 13 // Update Count : 700 14 14 // 15 15 … … 31 31 // Cforall allocation/deallocation and constructor/destructor, array types 32 32 33 forall( T & | sized(T), TT... | { void ?{}( T &, TT); } )34 T * anew( size_t dim, TTp ) {33 forall( T & | sized(T), Parms ... | { void ?{}( T &, Parms ); } ) 34 T * anew( size_t dim, Parms p ) { 35 35 T * arr = alloc( dim ); 36 36 for ( i; dim ) { … … 51 51 } // adelete 52 52 53 forall( T & | sized(T) | { void ^?{}( T & ); }, TT... | { void adelete( TT); } )54 void adelete( T arr[], TTrest ) {53 forall( T & | sized(T) | { void ^?{}( T & ); }, List ... | { void adelete( List ); } ) 54 void adelete( T arr[], List rest ) { 55 55 if ( arr ) { // ignore null 56 56 size_t dim = malloc_size( arr ) / sizeof( T ); -
libcfa/src/stdlib.hfa
rcf191ac r7042c60 10 10 // Created On : Thu Jan 28 17:12:35 2016 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Mon Apr 15 22:11:51 202413 // Update Count : 81712 // Last Modified On : Tue Apr 23 14:05:21 2024 13 // Update Count : 963 14 14 // 15 15 … … 47 47 48 48 static inline forall( T & | sized(T) ) { 49 // CFA safe equivalents, i.e., implicit size specification 49 // CFA safe equivalents, i.e., implicit size specification, eliminate return-type cast 50 50 51 51 T * malloc( void ) { … … 64 64 } // calloc 65 65 66 T * resize( T * ptr, size_t size ) { // CFA resize67 if ( _Alignof(T) <= libAlign() ) return (T *)resize( (void *)ptr, size ); // C FAresize66 T * resize( T * ptr, size_t size ) { 67 if ( _Alignof(T) <= libAlign() ) return (T *)resize( (void *)ptr, size ); // C resize 68 68 else return (T *)resize( (void *)ptr, _Alignof(T), size ); // CFA resize 69 } // resize 70 71 T * resize( T * ptr, size_t alignment, size_t size ) { 72 return (T *)resize( (void *)ptr, alignment, size ); // CFA resize 69 73 } // resize 70 74 … … 74 78 } // realloc 75 79 80 T * realloc( T * ptr, size_t alignment, size_t size ) { 81 return (T *)realloc( (void *)ptr, alignment, size ); // CFA realloc 82 } // realloc 83 76 84 T * reallocarray( T * ptr, size_t dim ) { // CFA reallocarray 77 85 if ( _Alignof(T) <= libAlign() ) return (T *)reallocarray( (void *)ptr, dim, sizeof(T) ); // C reallocarray … … 79 87 } // realloc 80 88 89 T * reallocarray( T * ptr, size_t alignment, size_t dim ) { 90 return (T *)reallocarray( (void *)ptr, alignment, dim ); // CFA reallocarray 91 } // realloc 92 81 93 T * memalign( size_t align ) { 82 94 return (T *)memalign( align, sizeof(T) ); // C memalign … … 87 99 } // amemalign 88 100 89 T * cmemalign( size_t align, size_t dim 101 T * cmemalign( size_t align, size_t dim ) { 90 102 return (T *)cmemalign( align, dim, sizeof(T) ); // CFA cmemalign 91 103 } // cmemalign … … 109 121 110 122 /* 111 FIX ME : fix alloc interface after Ticker Number 214 is resolved, define and add union to S_fill. Then, modify postfix-fill functions to support T * with nmemb, char, and T object of any size. Finally, change alloc_internal. 123 FIX ME : fix alloc interface after Ticker Number 214 is resolved, define and add union to S_fill. Then, modify 124 postfix-fill functions to support T * with nmemb, char, and T object of any size. Finally, change alloc_internal. 112 125 Or, just follow the instructions below for that. 113 126 … … 153 166 */ 154 167 155 typedef struct S_align { inline size_t; } T_align; 156 typedef struct S_resize { inline void *; } T_resize; 157 158 forall( T & ) { 159 struct S_fill { char tag; char c; size_t size; T * at; char t[50]; }; 160 struct S_realloc { inline T *; }; 168 #pragma GCC diagnostic push 169 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized" 170 #pragma GCC diagnostic ignored "-Wuninitialized" 171 172 struct T_align { size_t align; }; 173 struct T_resize { void * addr; }; 174 struct T_realloc { void * addr; }; 175 forall( T & ) struct T_fill { 176 // 'N' => no fill, 'c' => fill with character c, 'a' => fill first N array elements from another array, 177 // 'A' => fill all array elements from another array, 'T' => fill using a T value. 178 char tag; 179 size_t nelem; // number of elements copied from "at" (used with tag 'a') 180 // union { 181 char c; 182 T * at; 183 char t[64]; // T t; 184 // }; 185 }; 186 187 #pragma GCC diagnostic pop 188 189 static inline { 190 T_align ?`align( size_t a ) { return (T_align){ a }; } 191 T_resize ?`resize( void * a ) { return (T_resize){ a }; } 192 T_realloc ?`realloc( void * a ) { return (T_realloc){ a }; } 161 193 } 162 194 163 static inline T_align ?`align( size_t a ) { return (T_align){a}; }164 static inline T_resize ?`resize( void * a ) { return (T_resize){a}; }165 166 extern "C" ssize_t write(int fd, const void *buf, size_t count);167 195 static inline forall( T & | sized(T) ) { 168 S_fill(T) ?`fill ( T t ) { 169 S_fill(T) ret = { 't' }; 196 T_fill(T) ?`fill( char c ) { return (T_fill(T)){ 'c', 0, c }; } 197 T_fill(T) ?`fill( T t ) { 198 T_fill(T) ret = { 'T' }; 170 199 size_t size = sizeof(T); 171 200 if ( size > sizeof(ret.t) ) { … … 175 204 return ret; 176 205 } 177 S_fill(T) ?`fill ( zero_t ) = void; // FIX ME: remove this once ticket 214 is resolved 178 S_fill(T) ?`fill ( T * a ) { return (S_fill(T)){ 'T', '0', 0, a }; } // FIX ME: remove this once ticket 214 is resolved 179 S_fill(T) ?`fill ( char c ) { return (S_fill(T)){ 'c', c }; } 180 S_fill(T) ?`fill ( T a[], size_t nmemb ) { return (S_fill(T)){ 'a', '0', nmemb * sizeof(T), a }; } 181 182 S_realloc(T) ?`realloc ( T * a ) { return (S_realloc(T)){a}; } 183 184 T * alloc_internal$( void * Resize, T * Realloc, size_t Align, size_t Dim, S_fill(T) Fill ) { 185 T * ptr = NULL; 186 size_t size = sizeof(T); 206 T_fill(T) ?`fill( T a[] ) { return (T_fill(T)){ 'A', 0, '\0', a }; } // FIX ME: remove this once ticket 214 is resolved 207 T_fill(T) ?`fill( T a[], size_t nelem ) { return (T_fill(T)){ 'a', nelem * sizeof(T), '\0', a }; } 208 209 // private interface 210 T * alloc_internal$( size_t Dim, T_resize Resize, T_realloc Realloc, size_t Align, T_fill(T) Fill ) { 211 T * ptr; 212 size_t tsize = sizeof(T); 187 213 size_t copy_end = 0; 188 214 189 if ( Resize ) {190 ptr = (T *)(void *)resize( (void *)Resize, Align, Dim *size );191 } else if ( Realloc ) {192 if ( Fill.tag != ' 0' ) copy_end = min(malloc_size( Realloc ), Dim *size );193 ptr = (T *)(void *)realloc( (void *)Realloc, Align, Dim *size );215 if ( Resize.addr ) { 216 ptr = (T *)(void *)resize( Resize.addr, Align, Dim * tsize ); 217 } else if ( Realloc.addr ) { 218 if ( Fill.tag != 'N' ) copy_end = min(malloc_size( Realloc.addr ), Dim * tsize ); 219 ptr = (T *)(void *)realloc( Realloc.addr, Align, Dim * tsize ); 194 220 } else { 195 ptr = (T *)(void *) memalign( Align, Dim *size );196 } 221 ptr = (T *)(void *)memalign( Align, Dim * tsize ); 222 } // if 197 223 198 224 if ( Fill.tag == 'c' ) { 199 memset( (char *)ptr + copy_end, (int)Fill.c, Dim * size - copy_end ); 200 } else if ( Fill.tag == 't' ) { 201 for ( i; copy_end ~ Dim * size ~ size ) { 202 #pragma GCC diagnostic push 203 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized" 204 assert( size <= sizeof(Fill.t) ); 205 memcpy( (char *)ptr + i, &Fill.t, size ); 206 #pragma GCC diagnostic pop 207 } 225 memset( (char *)ptr + copy_end, (int)Fill.c, Dim * tsize - copy_end ); 226 } else if ( Fill.tag == 'T' ) { 227 for ( i; copy_end ~ Dim * tsize ~ tsize ) { 228 assert( tsize <= sizeof(Fill.t) ); 229 memcpy( (char *)ptr + i, &Fill.t, tsize ); 230 } // for 208 231 } else if ( Fill.tag == 'a' ) { 209 memcpy( (char *)ptr + copy_end, Fill.at, min(Dim * size - copy_end, Fill.size) ); 210 } else if ( Fill.tag == 'T' ) { 211 memcpy( (char *)ptr + copy_end, Fill.at, Dim * size ); 212 } 213 232 memcpy( (char *)ptr + copy_end, Fill.at, min( Dim * tsize - copy_end, Fill.nelem ) ); 233 } else if ( Fill.tag == 'A' ) { 234 memcpy( (char *)ptr + copy_end, Fill.at, Dim * tsize ); 235 } // if 214 236 return ptr; 215 237 } // alloc_internal$ 216 238 217 forall( TT ... | { T * alloc_internal$( void *, T *, size_t, size_t, S_fill(T), TT ); } ) { 218 T * alloc_internal$( void *, T *, size_t Align, size_t Dim, S_fill(T) Fill, T_resize Resize, TT rest ) { 219 return alloc_internal$( Resize, (T*)0p, Align, Dim, Fill, rest); 239 // Dim is a fixed (optional first) parameter, and hence is not set using a postfix function. A dummy parameter is 240 // being overwritten by the postfix argument in the ttype. 241 forall( List ... | { T * alloc_internal$( size_t Dim, T_resize Resize, T_realloc Realloc, size_t Align, T_fill(T) Fill, List ); } ) { 242 // middle interface 243 T * alloc_internal$( size_t Dim, T_resize dummy, T_realloc Realloc, size_t Align, T_fill(T) Fill, T_resize Resize, List rest ) { 244 return alloc_internal$( Dim, Resize, (T_realloc){0p}, Align, Fill, rest ); 220 245 } 221 222 T * alloc_internal$( void *, T *, size_t Align, size_t Dim, S_fill(T) Fill, S_realloc(T) Realloc, TT rest ) { 223 return alloc_internal$( (void*)0p, Realloc, Align, Dim, Fill, rest); 246 T * alloc_internal$( size_t Dim, T_resize Resize, T_realloc dummy, size_t Align, T_fill(T) Fill, T_realloc Realloc, List rest ) { 247 return alloc_internal$( Dim, (T_resize){0p}, Realloc, Align, Fill, rest ); 224 248 } 225 226 T * alloc_internal$( void * Resize, T * Realloc, size_t, size_t Dim, S_fill(T) Fill, T_align Align, TT rest ) { 227 return alloc_internal$( Resize, Realloc, Align, Dim, Fill, rest); 249 T * alloc_internal$( size_t Dim, T_resize Resize, T_realloc Realloc, size_t dummy, T_fill(T) Fill, T_align Align, List rest ) { 250 return alloc_internal$( Dim, Resize, Realloc, Align.align, Fill, rest ); 228 251 } 229 230 T * alloc_internal$( void * Resize, T * Realloc, size_t Align, size_t Dim, S_fill(T), S_fill(T) Fill, TT rest ) { 231 return alloc_internal$( Resize, Realloc, Align, Dim, Fill, rest ); 252 T * alloc_internal$( size_t Dim, T_resize Resize, T_realloc Realloc, size_t Align, T_fill(T) dummy, T_fill(T) Fill, List rest ) { 253 return alloc_internal$( Dim, Resize, Realloc, Align, Fill, rest ); 232 254 } 233 234 T * alloc( TT all) {235 return alloc_internal$( ( void*)0p, (T*)0p, (_Alignof(T) > libAlign() ? _Alignof(T) : libAlign()), (size_t)1, (S_fill(T)){'0'}, all);255 // public interface 256 T * alloc( List rest ) { 257 return alloc_internal$( (size_t)1, (T_resize){0p}, (T_realloc){0p}, (_Alignof(T) > libAlign() ? _Alignof(T) : libAlign()), (T_fill(T)){'N'}, rest ); 236 258 } 237 238 T * alloc( size_t dim, TT all ) { 239 return alloc_internal$( (void*)0p, (T*)0p, (_Alignof(T) > libAlign() ? _Alignof(T) : libAlign()), dim, (S_fill(T)){'0'}, all ); 259 T * alloc( size_t Dim, List rest ) { 260 return alloc_internal$( Dim, (T_resize){0p}, (T_realloc){0p}, (_Alignof(T) > libAlign() ? _Alignof(T) : libAlign()), (T_fill(T)){'N'}, rest ); 240 261 } 241 } // distribution TT262 } // distribution List 242 263 } // distribution T 243 264 244 265 static inline forall( T & | sized(T) ) { 245 266 // CFA safe initialization/copy, i.e., implicit size specification, non-array types 246 T * memset( T * dest, char fill ) { 247 return (T *)memset( dest, fill, sizeof(T) ); 267 T * memset( T * dest, char fill ) { // all combinations of pointer/reference 268 return (T *)memset( dest, fill, sizeof(T) ); // C memset 248 269 } // memset 249 250 T * memcpy( T * dest, const T * src ) { 251 return (T *)memcpy( dest, src, sizeof(T) ); 270 T * memset( T & dest, char fill ) { 271 return (T *)memset( &dest, fill, sizeof(T) ); // C memset 272 } // memset 273 274 T * memcpy( T * dest, const T * src ) { // all combinations of pointer/reference 275 return (T *)memcpy( dest, src, sizeof(T) ); // C memcpy 276 } // memcpy 277 T * memcpy( T & dest, const T & src ) { 278 return (T *)memcpy( &dest, &src, sizeof(T) ); // C memcpy 279 } // memcpy 280 T * memcpy( T * dest, const T & src ) { 281 return (T *)memcpy( dest, &src, sizeof(T) ); // C memcpy 282 } // memcpy 283 T * memcpy( T & dest, const T * src ) { 284 return (T *)memcpy( &dest, src, sizeof(T) ); // C memcpy 252 285 } // memcpy 253 286 … … 263 296 264 297 // CFA deallocation for multiple objects 265 static inline forall( T & ) // FIX ME, problems with 0p in list298 static inline forall( T & ) 266 299 void free( T * ptr ) { 267 300 free( (void *)ptr ); // C free 268 301 } // free 269 static inline forall( T &, TT ... | { void free( TT); } )270 void free( T * ptr, TTrest ) {302 static inline forall( T &, List ... | { void free( List ); } ) 303 void free( T * ptr, List rest ) { 271 304 free( ptr ); 272 305 free( rest ); … … 274 307 275 308 // CFA allocation/deallocation and constructor/destructor, non-array types 276 static inline forall( T & | sized(T), TT ... | { void ?{}( T &, TT); } )277 T * new( TTp ) {309 static inline forall( T & | sized(T), Parms ... | { void ?{}( T &, Parms ); } ) 310 T * new( Parms p ) { 278 311 return &(*(T *)malloc()){ p }; // run constructor 279 312 } // new … … 287 320 free( ptr ); // always call free 288 321 } // delete 289 static inline forall( T &, TT ... | { void ^?{}( T & ); void delete( TT); } )290 void delete( T * ptr, TTrest ) {322 static inline forall( T &, List ... | { void ^?{}( T & ); void delete( List ); } ) 323 void delete( T * ptr, List rest ) { 291 324 delete( ptr ); 292 325 delete( rest ); … … 294 327 295 328 // CFA allocation/deallocation and constructor/destructor, array types 296 forall( T & | sized(T), TT ... | { void ?{}( T &, TT ); } ) T * anew( size_t dim, TTp );329 forall( T & | sized(T), Parms ... | { void ?{}( T &, Parms ); } ) T * anew( size_t dim, Parms p ); 297 330 forall( T & | sized(T) | { void ^?{}( T & ); } ) void adelete( T arr[] ); 298 forall( T & | sized(T) | { void ^?{}( T & ); }, TT ... | { void adelete( TT ); } ) void adelete( T arr[], TT rest ); 331 forall( T & | sized(T) | { void ^?{}( T & ); }, List ... | { void adelete( List ); } ) void adelete( T arr[], List rest ); 332 299 333 //--------------------------------------- 300 334 -
src/AST/Pass.hpp
rcf191ac r7042c60 113 113 static auto read( node_type const * node, Args&&... args ) { 114 114 Pass<core_t> visitor( std::forward<Args>( args )... ); 115 auto const * temp = node->accept( visitor );116 assert( temp == node );117 return visitor.get_result();118 }119 120 // Versions of the above for older compilers.121 template< typename... Args >122 static void run( TranslationUnit & decls ) {123 Pass<core_t> visitor;124 accept_all( decls, visitor );125 }126 127 template< typename node_type, typename... Args >128 static auto read( node_type const * node ) {129 Pass<core_t> visitor;130 115 auto const * temp = node->accept( visitor ); 131 116 assert( temp == node ); -
src/AST/Print.cpp
rcf191ac r7042c60 1579 1579 preprint( node ); 1580 1580 os << "enum attr "; 1581 1582 1583 1584 1585 1586 1587 1581 if ( node->attr == ast::EnumAttribute::Label ) { 1582 os << "Label "; 1583 } else if ( node->attr == ast::EnumAttribute::Value ) { 1584 os << "Value "; 1585 } else { 1586 os << "Posn "; 1587 } 1588 1588 (*(node->instance)).accept( *this ); 1589 1589 return node; -
src/AST/Type.hpp
rcf191ac r7042c60 31 31 // Must be included in *all* AST classes; should be #undef'd at the end of the file 32 32 #define MUTATE_FRIEND \ 33 33 template<typename node_t> friend node_t * mutate(const node_t * node); \ 34 34 template<typename node_t> friend node_t * shallowCopy(const node_t * node); 35 35 … … 322 322 public: 323 323 readonly<EnumInstType> instance; 324 324 EnumAttribute attr; 325 325 const Type * accept( Visitor & v ) const override { return v.visit( this ); } 326 326 EnumAttrType( const EnumInstType * instance, EnumAttribute attr = EnumAttribute::Posn ) 327 327 : instance(instance), attr(attr) {} 328 329 330 331 328 329 bool match( const ast::EnumAttrType * other) const { 330 return instance->base->name == other->instance->base->name && attr == other->attr; 331 } 332 332 private: 333 333 EnumAttrType * clone() const override { return new EnumAttrType{ *this }; } -
src/BasicTypes-gen.cc
rcf191ac r7042c60 415 415 code << "\t" << BYMK << endl; 416 416 code << "\t#define BT ast::BasicKind::" << endl; 417 code << "\tstatic const BTKind commonTypes[BT NUMBER_OF_BASIC_TYPES][BT NUMBER_OF_BASIC_TYPES] = { // nearest common ancestor" << endl417 code << "\tstatic const ast::BasicKind commonTypes[BT NUMBER_OF_BASIC_TYPES][BT NUMBER_OF_BASIC_TYPES] = { // nearest common ancestor" << endl 418 418 << "\t\t/*\t\t "; 419 419 for ( int r = 0; r < NUMBER_OF_BASIC_TYPES; r += 1 ) { // titles -
src/CodeGen/CodeGenerator.cpp
rcf191ac r7042c60 167 167 ast::Pass<CodeGenerator> subCG( acc, subOptions ); 168 168 // Add the forall clause. 169 // TODO: These probably should be removed by now and the assert used.170 169 if ( !decl->type_params.empty() ) { 171 170 assertf( !options.genC, "FunctionDecl forall should not reach code generation." ); … … 174 173 acc << ")" << std::endl; 175 174 } 175 // The forall clause should be printed early as part of the preamble. 176 output << acc.str(); 177 acc.str(""); 176 178 177 179 acc << mangleName( decl ); -
src/Common/PersistentMap.h
rcf191ac r7042c60 23 23 #include <utility> // for forward, move 24 24 25 /// Wraps a hash table in a persistent data structure, using a technique based 26 /// on the persistent array in Conchon & Filliatre "A Persistent Union-Find 25 /// Wraps a hash table in a persistent data structure, using a technique based 26 /// on the persistent array in Conchon & Filliatre "A Persistent Union-Find 27 27 /// Data Structure" 28 28 29 29 template<typename Key, typename Val, 30 31 class PersistentMap 30 typename Hash = std::hash<Key>, typename Eq = std::equal_to<Key>> 31 class PersistentMap 32 32 : public std::enable_shared_from_this<PersistentMap<Key, Val, Hash, Eq>> { 33 33 public: … … 38 38 39 39 /// Types of version nodes 40 enum Mode { 40 enum Mode { 41 41 BASE, ///< Root node of version tree 42 42 REM, ///< Key removal node … … 63 63 Ptr base; ///< Modified map 64 64 Key key; ///< Key removed 65 65 66 66 template<typename P, typename K> 67 67 Rem(P&& p, K&& k) : base(std::forward<P>(p)), key(std::forward<K>(k)) {} … … 155 155 auto it = base_map.find( self.key ); 156 156 157 base->template init<Ins>( 157 base->template init<Ins>( 158 158 mut_this->shared_from_this(), std::move(self.key), std::move(it->second) ); 159 159 base->mode = INS; … … 175 175 auto it = base_map.find( self.key ); 176 176 177 base->template init<Ins>( 177 base->template init<Ins>( 178 178 mut_this->shared_from_this(), std::move(self.key), std::move(it->second) ); 179 179 base->mode = UPD; … … 267 267 Ptr erase(const Key& k) { 268 268 reroot(); 269 269 270 270 // exit early if key does not exist in map 271 271 if ( ! as<Base>().count( k ) ) return this->shared_from_this(); -
src/Common/VectorMap.h
rcf191ac r7042c60 36 36 typedef const value_type* pointer; 37 37 typedef const const_value_type* const_pointer; 38 39 class iterator : public std::iterator< std::random_access_iterator_tag, 40 value_type, 41 difference_type, 42 pointer, 43 reference > { 44 friend class VectorMap; 45 friend class const_iterator; 46 38 39 class iterator : public std::iterator< 40 std::random_access_iterator_tag, 41 value_type, difference_type, pointer, reference > { 42 friend class VectorMap; 43 friend class const_iterator; 44 47 45 value_type data; 48 46 … … 99 97 return data.first == o.data.first && &data.second == &o.data.second; 100 98 } 101 99 102 100 bool operator!= (const iterator& that) const { return !(*this == that); } 103 101 … … 111 109 }; 112 110 113 class const_iterator : public std::iterator< std::bidirectional_iterator_tag, 114 const_value_type, 115 difference_type, 116 const_pointer, 117 const_reference > { 118 friend class VectorMap; 111 class const_iterator : public std::iterator< 112 std::bidirectional_iterator_tag, 113 const_value_type, difference_type, const_pointer, const_reference > { 114 friend class VectorMap; 119 115 const_value_type data; 120 116 … … 181 177 return data.first == o.data.first && &data.second == &o.data.second; 182 178 } 183 179 184 180 bool operator!= (const const_iterator& that) const { return !(*this == that); } 185 181 … … 233 229 234 230 template<typename T> 235 typename VectorMap<T>::iterator operator+ (typename VectorMap<T>::difference_type i, 236 const typename VectorMap<T>::iterator& it) { 231 typename VectorMap<T>::iterator operator+( 232 typename VectorMap<T>::difference_type i, 233 const typename VectorMap<T>::iterator& it) { 237 234 return it + i; 238 235 } 239 236 240 237 template<typename T> 241 typename VectorMap<T>::const_iterator operator+ (typename VectorMap<T>::difference_type i, 242 const typename VectorMap<T>::const_iterator& it) { 238 typename VectorMap<T>::const_iterator operator+( 239 typename VectorMap<T>::difference_type i, 240 const typename VectorMap<T>::const_iterator& it) { 243 241 return it + i; 244 242 } -
src/Concurrency/Actors.cpp
rcf191ac r7042c60 28 28 29 29 struct CollectactorStructDecls : public ast::WithGuards { 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 } 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 auto actorIter = actorStructDecls.find( node->aggr() ); 78 79 80 81 82 83 84 85 86 30 unordered_set<const StructDecl *> & actorStructDecls; 31 unordered_set<const StructDecl *> & messageStructDecls; 32 const StructDecl ** requestDecl; 33 const EnumDecl ** allocationDecl; 34 const StructDecl ** actorDecl; 35 const StructDecl ** msgDecl; 36 StructDecl * parentDecl; 37 bool insideStruct = false; 38 bool namedDecl = false; 39 40 // finds and sets a ptr to the allocation enum, which is needed in the next pass 41 void previsit( const EnumDecl * decl ) { 42 if( decl->name == "allocation" ) *allocationDecl = decl; 43 } 44 45 // finds and sets a ptr to the actor, message, and request structs, which are needed in the next pass 46 void previsit( const StructDecl * decl ) { 47 if ( !decl->body ) return; 48 if ( decl->name == "actor" ) { 49 actorStructDecls.insert( decl ); // skip inserting fwd decl 50 *actorDecl = decl; 51 } else if( decl->name == "message" ) { 52 messageStructDecls.insert( decl ); // skip inserting fwd decl 53 *msgDecl = decl; 54 } else if( decl->name == "request" ) *requestDecl = decl; 55 else { 56 GuardValue(insideStruct); 57 insideStruct = true; 58 parentDecl = mutate( decl ); 59 } 60 } 61 62 // this catches structs of the form: 63 // struct dummy_actor { actor a; }; 64 // since they should be: 65 // struct dummy_actor { inline actor; }; 66 void previsit ( const ObjectDecl * decl ) { 67 if ( insideStruct && ! decl->name.empty() ) { 68 GuardValue(namedDecl); 69 namedDecl = true; 70 } 71 } 72 73 // this collects the derived actor and message struct decl ptrs 74 void postvisit( const StructInstType * node ) { 75 if ( ! *actorDecl || ! *msgDecl ) return; 76 if ( insideStruct && !namedDecl ) { 77 auto actorIter = actorStructDecls.find( node->aggr() ); 78 if ( actorIter != actorStructDecls.end() ) { 79 actorStructDecls.insert( parentDecl ); 80 return; 81 } 82 auto messageIter = messageStructDecls.find( node->aggr() ); 83 if ( messageIter != messageStructDecls.end() ) { 84 messageStructDecls.insert( parentDecl ); 85 } 86 } 87 87 } 88 88 89 89 public: 90 91 const StructDecl ** requestDecl, const EnumDecl ** allocationDecl, const StructDecl ** actorDecl, const StructDecl ** msgDecl ) 92 : actorStructDecls( actorStructDecls ), messageStructDecls( messageStructDecls ), requestDecl( requestDecl ), 93 90 CollectactorStructDecls( unordered_set<const StructDecl *> & actorStructDecls, unordered_set<const StructDecl *> & messageStructDecls, 91 const StructDecl ** requestDecl, const EnumDecl ** allocationDecl, const StructDecl ** actorDecl, const StructDecl ** msgDecl ) 92 : actorStructDecls( actorStructDecls ), messageStructDecls( messageStructDecls ), requestDecl( requestDecl ), 93 allocationDecl( allocationDecl ), actorDecl(actorDecl), msgDecl(msgDecl) {} 94 94 }; 95 95 … … 97 97 class FwdDeclTable { 98 98 99 100 struct FwdDeclData { 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 99 // tracks which decls we have seen so that we can hoist the FunctionDecl to the highest point possible 100 struct FwdDeclData { 101 const StructDecl * actorDecl; 102 const StructDecl * msgDecl; 103 FunctionDecl * fwdDecl; 104 bool actorFound; 105 bool msgFound; 106 107 bool readyToInsert() { return actorFound && msgFound; } 108 bool foundActor() { actorFound = true; return readyToInsert(); } 109 bool foundMsg() { msgFound = true; return readyToInsert(); } 110 111 FwdDeclData( const StructDecl * actorDecl, const StructDecl * msgDecl, FunctionDecl * fwdDecl ) : 112 actorDecl(actorDecl), msgDecl(msgDecl), fwdDecl(fwdDecl), actorFound(false), msgFound(false) {} 113 }; 114 115 // map indexed by actor struct ptr 116 // value is map of all FwdDeclData that contains said actor struct ptr 117 // inner map is indexed by the message struct ptr of FwdDeclData 118 unordered_map<const StructDecl *, unordered_map<const StructDecl *, FwdDeclData *>> actorMap; 119 120 // this map is the same except the outer map is indexed by message ptr and the inner is indexed by actor ptr 121 unordered_map<const StructDecl *, unordered_map<const StructDecl *, FwdDeclData *>> msgMap; 122 123 void insert( const StructDecl * decl, const StructDecl * otherDecl, unordered_map<const StructDecl *, unordered_map<const StructDecl *, FwdDeclData *>> & map, FwdDeclData * data ) { 124 auto iter = map.find( decl ); 125 if ( iter != map.end() ) { // if decl exists in map append data to existing inner map 126 iter->second.emplace( make_pair( otherDecl, data ) ); 127 } else { // else create inner map for key 128 map.emplace( make_pair( decl, unordered_map<const StructDecl *, FwdDeclData *>( { make_pair( otherDecl, data ) } ) ) ); 129 } 130 } 131 131 132 132 public: 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 133 // insert decl into table so that we can fwd declare it later (average cost: O(1)) 134 void insertDecl( const StructDecl * actorDecl, const StructDecl * msgDecl, FunctionDecl * fwdDecl ) { 135 FwdDeclData * declToInsert = new FwdDeclData( actorDecl, msgDecl, fwdDecl ); 136 insert( actorDecl, msgDecl, actorMap, declToInsert ); 137 insert( msgDecl, actorDecl, msgMap, declToInsert ); 138 } 139 140 // returns list of decls to insert after current struct decl 141 // Over the entire pass the runtime of this routine is O(r) where r is the # of receive routines 142 list<FunctionDecl *> updateDecl( const StructDecl * decl, bool isMsg ) { 143 unordered_map<const StructDecl *, unordered_map<const StructDecl *, FwdDeclData *>> & map = isMsg ? msgMap : actorMap; 144 unordered_map<const StructDecl *, unordered_map<const StructDecl *, FwdDeclData *>> & otherMap = isMsg ? actorMap : msgMap; 145 auto iter = map.find( decl ); 146 list<FunctionDecl *> toInsertAfter; // this is populated with decls that are ready to insert 147 if ( iter == map.end() ) return toInsertAfter; 148 149 // iterate over inner map 150 unordered_map<const StructDecl *, FwdDeclData *> & currInnerMap = iter->second; 151 for ( auto innerIter = currInnerMap.begin(); innerIter != currInnerMap.end(); ) { 152 FwdDeclData * currentDatum = innerIter->second; 153 bool readyToInsert = isMsg ? currentDatum->foundMsg() : currentDatum->foundActor(); 154 if ( ! readyToInsert ) { ++innerIter; continue; } 155 156 // readyToInsert is true so we are good to insert the forward decl of the message fn 157 toInsertAfter.push_back( currentDatum->fwdDecl ); 158 159 // need to remove from other map before deleting 160 // find inner map in other map ( other map is actor map if original is msg map and vice versa ) 161 const StructDecl * otherDecl = isMsg ? currentDatum->actorDecl : currentDatum->msgDecl; 162 auto otherMapIter = otherMap.find( otherDecl ); 163 164 unordered_map<const StructDecl *, FwdDeclData *> & otherInnerMap = otherMapIter->second; 165 166 // find the FwdDeclData we need to remove in the other inner map 167 auto otherInnerIter = otherInnerMap.find( decl ); 168 169 // remove references to deleted FwdDeclData from current inner map 170 innerIter = currInnerMap.erase( innerIter ); // this does the increment so no explicit inc needed 171 172 // remove references to deleted FwdDeclData from other inner map 173 otherInnerMap.erase( otherInnerIter ); 174 175 // if other inner map is now empty, remove key from other outer map 176 if ( otherInnerMap.empty() ) 177 otherMap.erase( otherDecl ); 178 179 // now we are safe to delete the FwdDeclData since we are done with it 180 // and we have removed all references to it from our data structures 181 delete currentDatum; 182 } 183 184 // if current inner map is now empty, remove key from outer map. 185 // Have to do this after iterating for safety 186 if ( currInnerMap.empty() ) 187 map.erase( decl ); 188 189 return toInsertAfter; 190 } 191 191 }; 192 192 193 193 // generates the definitions of send operators for actors 194 // collects data needed for next pass that does the circular defn resolution 194 // collects data needed for next pass that does the circular defn resolution 195 195 // for message send operators (via table above) 196 196 struct GenFuncsCreateTables : public ast::WithDeclsToAdd<> { 197 198 199 200 201 202 203 204 205 197 unordered_set<const StructDecl *> & actorStructDecls; 198 unordered_set<const StructDecl *> & messageStructDecls; 199 const StructDecl ** requestDecl; 200 const EnumDecl ** allocationDecl; 201 const StructDecl ** actorDecl; 202 const StructDecl ** msgDecl; 203 FwdDeclTable & forwardDecls; 204 205 // generates the operator for actor message sends 206 206 void postvisit( const FunctionDecl * decl ) { 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 UntypedExpr::createAssign( decl->location, 238 239 240 241 242 243 244 245 UntypedExpr::createAssign( decl->location, 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 */ 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 // More readable synonymous code: 358 359 360 361 362 363 364 365 366 new SingleInit( decl->location, 367 368 369 370 371 372 373 374 207 // return if not of the form receive( param1, param2 ) or if it is a forward decl 208 if ( decl->name != "receive" || decl->params.size() != 2 || !decl->stmts ) return; 209 210 // the params should be references 211 const ReferenceType * derivedActorRef = dynamic_cast<const ReferenceType *>(decl->params.at(0)->get_type()); 212 const ReferenceType * derivedMsgRef = dynamic_cast<const ReferenceType *>(decl->params.at(1)->get_type()); 213 if ( !derivedActorRef || !derivedMsgRef ) return; 214 215 // the references should be to struct instances 216 const StructInstType * arg1InstType = dynamic_cast<const StructInstType *>(derivedActorRef->base.get()); 217 const StructInstType * arg2InstType = dynamic_cast<const StructInstType *>(derivedMsgRef->base.get()); 218 if ( !arg1InstType || !arg2InstType ) return; 219 220 // If the struct instances are derived actor and message types then generate the message send routine 221 auto actorIter = actorStructDecls.find( arg1InstType->aggr() ); 222 auto messageIter = messageStructDecls.find( arg2InstType->aggr() ); 223 if ( actorIter != actorStructDecls.end() && messageIter != messageStructDecls.end() ) { 224 ////////////////////////////////////////////////////////////////////// 225 // The following generates this wrapper for all receive(derived_actor &, derived_msg &) functions 226 /* base_actor and base_msg are output params 227 static inline allocation __CFA_receive_wrap( derived_actor & receiver, derived_msg & msg, actor ** base_actor, message ** base_msg ) { 228 base_actor = &receiver; 229 base_msg = &msg; 230 return receive( receiver, msg ); 231 } 232 */ 233 CompoundStmt * wrapBody = new CompoundStmt( decl->location ); 234 235 // generates: base_actor = &receiver; 236 wrapBody->push_back( new ExprStmt( decl->location, 237 UntypedExpr::createAssign( decl->location, 238 UntypedExpr::createDeref( decl->location, new NameExpr( decl->location, "base_actor" ) ), 239 new AddressExpr( decl->location, new NameExpr( decl->location, "receiver" ) ) 240 ) 241 )); 242 243 // generates: base_msg = &msg; 244 wrapBody->push_back( new ExprStmt( decl->location, 245 UntypedExpr::createAssign( decl->location, 246 UntypedExpr::createDeref( decl->location, new NameExpr( decl->location, "base_msg" ) ), 247 new AddressExpr( decl->location, new NameExpr( decl->location, "msg" ) ) 248 ) 249 )); 250 251 // generates: return receive( receiver, msg ); 252 wrapBody->push_back( new ReturnStmt( decl->location, 253 new UntypedExpr ( decl->location, 254 new NameExpr( decl->location, "receive" ), 255 { 256 new NameExpr( decl->location, "receiver" ), 257 new NameExpr( decl->location, "msg" ) 258 } 259 ) 260 )); 261 262 // create receive wrapper to extract base message and actor pointer 263 // put it all together into the complete function decl from above 264 FunctionDecl * receiveWrapper = new FunctionDecl( 265 decl->location, 266 "__CFA_receive_wrap", 267 { 268 new ObjectDecl( 269 decl->location, 270 "receiver", 271 ast::deepCopy( derivedActorRef ) 272 ), 273 new ObjectDecl( 274 decl->location, 275 "msg", 276 ast::deepCopy( derivedMsgRef ) 277 ), 278 new ObjectDecl( 279 decl->location, 280 "base_actor", 281 new PointerType( new PointerType( new StructInstType( *actorDecl ) ) ) 282 ), 283 new ObjectDecl( 284 decl->location, 285 "base_msg", 286 new PointerType( new PointerType( new StructInstType( *msgDecl ) ) ) 287 ) 288 }, // params 289 { 290 new ObjectDecl( 291 decl->location, 292 "__CFA_receive_wrap_ret", 293 new EnumInstType( *allocationDecl ) 294 ) 295 }, 296 wrapBody, // body 297 { Storage::Static }, // storage 298 Linkage::Cforall, // linkage 299 {}, // attributes 300 { Function::Inline } 301 ); 302 303 declsToAddAfter.push_back( receiveWrapper ); 304 305 ////////////////////////////////////////////////////////////////////// 306 // The following generates this send message operator routine for all receive(derived_actor &, derived_msg &) functions 307 /* 308 static inline derived_actor & ?|?( derived_actor & receiver, derived_msg & msg ) { 309 request new_req; 310 allocation (*my_work_fn)( derived_actor &, derived_msg & ) = receive; 311 __receive_fn fn = (__receive_fn)my_work_fn; 312 new_req{ &receiver, &msg, fn }; 313 send( receiver, new_req ); 314 return receiver; 315 } 316 */ 317 CompoundStmt * sendBody = new CompoundStmt( decl->location ); 318 319 // Generates: request new_req; 320 sendBody->push_back( new DeclStmt( 321 decl->location, 322 new ObjectDecl( 323 decl->location, 324 "new_req", 325 new StructInstType( *requestDecl ) 326 ) 327 )); 328 329 // Function type is: allocation (*)( derived_actor &, derived_msg &, actor **, message ** ) 330 FunctionType * derivedReceive = new FunctionType(); 331 derivedReceive->params.push_back( ast::deepCopy( derivedActorRef ) ); 332 derivedReceive->params.push_back( ast::deepCopy( derivedMsgRef ) ); 333 derivedReceive->params.push_back( new PointerType( new PointerType( new StructInstType( *actorDecl ) ) ) ); 334 derivedReceive->params.push_back( new PointerType( new PointerType( new StructInstType( *msgDecl ) ) ) ); 335 derivedReceive->returns.push_back( new EnumInstType( *allocationDecl ) ); 336 337 // Generates: allocation (*my_work_fn)( derived_actor &, derived_msg &, actor **, message ** ) = receive; 338 sendBody->push_back( new DeclStmt( 339 decl->location, 340 new ObjectDecl( 341 decl->location, 342 "my_work_fn", 343 new PointerType( derivedReceive ), 344 new SingleInit( decl->location, new NameExpr( decl->location, "__CFA_receive_wrap" ) ) 345 ) 346 )); 347 348 // Function type is: allocation (*)( actor &, message & ) 349 FunctionType * genericReceive = new FunctionType(); 350 genericReceive->params.push_back( new ReferenceType( new StructInstType( *actorDecl ) ) ); 351 genericReceive->params.push_back( new ReferenceType( new StructInstType( *msgDecl ) ) ); 352 genericReceive->params.push_back( new PointerType( new PointerType( new StructInstType( *actorDecl ) ) ) ); 353 genericReceive->params.push_back( new PointerType( new PointerType( new StructInstType( *msgDecl ) ) ) ); 354 genericReceive->returns.push_back( new EnumInstType( *allocationDecl ) ); 355 356 // Generates: allocation (*fn)( actor &, message & ) = (allocation (*)( actor &, message & ))my_work_fn; 357 // More readable synonymous code: 358 // typedef allocation (*__receive_fn)(actor &, message &); 359 // __receive_fn fn = (__receive_fn)my_work_fn; 360 sendBody->push_back( new DeclStmt( 361 decl->location, 362 new ObjectDecl( 363 decl->location, 364 "fn", 365 new PointerType( genericReceive ), 366 new SingleInit( decl->location, 367 new CastExpr( decl->location, new NameExpr( decl->location, "my_work_fn" ), new PointerType( genericReceive ), ExplicitCast ) 368 ) 369 ) 370 )); 371 372 // Generates: new_req{ (actor *)&receiver, (message *)&msg, fn }; 373 sendBody->push_back( new ExprStmt( 374 decl->location, 375 375 new UntypedExpr ( 376 decl->location, 376 decl->location, 377 377 new NameExpr( decl->location, "?{}" ), 378 378 { 379 379 new NameExpr( decl->location, "new_req" ), 380 381 382 380 new CastExpr( decl->location, new AddressExpr( new NameExpr( decl->location, "receiver" ) ), new PointerType( new StructInstType( *actorDecl ) ), ExplicitCast ), 381 new CastExpr( decl->location, new AddressExpr( new NameExpr( decl->location, "msg" ) ), new PointerType( new StructInstType( *msgDecl ) ), ExplicitCast ), 382 new NameExpr( decl->location, "fn" ) 383 383 } 384 384 ) 385 385 )); 386 386 387 388 389 387 // Generates: send( receiver, new_req ); 388 sendBody->push_back( new ExprStmt( 389 decl->location, 390 390 new UntypedExpr ( 391 391 decl->location, 392 392 new NameExpr( decl->location, "send" ), 393 393 { 394 394 { 395 396 397 395 new NameExpr( decl->location, "receiver" ), 396 new NameExpr( decl->location, "new_req" ) 397 } 398 398 } 399 399 ) 400 400 )); 401 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 402 // Generates: return receiver; 403 sendBody->push_back( new ReturnStmt( decl->location, new NameExpr( decl->location, "receiver" ) ) ); 404 405 // put it all together into the complete function decl from above 406 FunctionDecl * sendOperatorFunction = new FunctionDecl( 407 decl->location, 408 "?|?", 409 { 410 new ObjectDecl( 411 decl->location, 412 "receiver", 413 ast::deepCopy( derivedActorRef ) 414 ), 415 new ObjectDecl( 416 decl->location, 417 "msg", 418 ast::deepCopy( derivedMsgRef ) 419 ) 420 }, // params 421 { 422 new ObjectDecl( 423 decl->location, 424 "receiver_ret", 425 ast::deepCopy( derivedActorRef ) 426 ) 427 }, 428 nullptr, // body 429 { Storage::Static }, // storage 430 Linkage::Cforall, // linkage 431 {}, // attributes 432 { Function::Inline } 433 ); 434 435 // forward decls to resolve use before decl problem for '|' routines 436 forwardDecls.insertDecl( *actorIter, *messageIter , ast::deepCopy( sendOperatorFunction ) ); 437 438 sendOperatorFunction->stmts = sendBody; 439 declsToAddAfter.push_back( sendOperatorFunction ); 440 } 441 441 } 442 442 443 443 public: 444 445 const StructDecl ** requestDecl, const EnumDecl ** allocationDecl, const StructDecl ** actorDecl, const StructDecl ** msgDecl, 446 FwdDeclTable & forwardDecls ) : actorStructDecls(actorStructDecls), messageStructDecls(messageStructDecls), 447 444 GenFuncsCreateTables( unordered_set<const StructDecl *> & actorStructDecls, unordered_set<const StructDecl *> & messageStructDecls, 445 const StructDecl ** requestDecl, const EnumDecl ** allocationDecl, const StructDecl ** actorDecl, const StructDecl ** msgDecl, 446 FwdDeclTable & forwardDecls ) : actorStructDecls(actorStructDecls), messageStructDecls(messageStructDecls), 447 requestDecl(requestDecl), allocationDecl(allocationDecl), actorDecl(actorDecl), msgDecl(msgDecl), forwardDecls(forwardDecls) {} 448 448 }; 449 449 … … 452 452 // generates the forward declarations of the send operator for actor routines 453 453 struct FwdDeclOperator : public ast::WithDeclsToAdd<> { 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 454 unordered_set<const StructDecl *> & actorStructDecls; 455 unordered_set<const StructDecl *> & messageStructDecls; 456 FwdDeclTable & forwardDecls; 457 458 // handles forward declaring the message operator 459 void postvisit( const StructDecl * decl ) { 460 list<FunctionDecl *> toAddAfter; 461 auto actorIter = actorStructDecls.find( decl ); 462 if ( actorIter != actorStructDecls.end() ) { // this is a derived actor decl 463 // get list of fwd decls that we can now insert 464 toAddAfter = forwardDecls.updateDecl( decl, false ); 465 466 // get rid of decl from actorStructDecls since we no longer need it 467 actorStructDecls.erase( actorIter ); 468 } else { 469 auto messageIter = messageStructDecls.find( decl ); 470 if ( messageIter == messageStructDecls.end() ) return; 471 472 toAddAfter = forwardDecls.updateDecl( decl, true ); 473 474 // get rid of decl from messageStructDecls since we no longer need it 475 messageStructDecls.erase( messageIter ); 476 } 477 478 // add the fwd decls to declsToAddAfter 479 for ( FunctionDecl * func : toAddAfter ) { 480 declsToAddAfter.push_back( func ); 481 } 482 } 483 483 484 484 public: 485 FwdDeclOperator( unordered_set<const StructDecl *> & actorStructDecls, unordered_set<const StructDecl *> & messageStructDecls, 486 485 FwdDeclOperator( unordered_set<const StructDecl *> & actorStructDecls, unordered_set<const StructDecl *> & messageStructDecls, 486 FwdDeclTable & forwardDecls ) : actorStructDecls(actorStructDecls), messageStructDecls(messageStructDecls), forwardDecls(forwardDecls) {} 487 487 }; 488 488 489 489 void implementActors( TranslationUnit & translationUnit ) { 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 Pass<CollectactorStructDecls>::run( translationUnit, actorStructDecls, messageStructDecls, requestDecl, 511 512 513 514 if ( !allocationDeclPtr || !requestDeclPtr || !actorDeclPtr || !msgDeclPtr ) 515 516 517 518 519 Pass<GenFuncsCreateTables>::run( translationUnit, actorStructDecls, messageStructDecls, requestDecl, 520 521 522 523 490 // unordered_maps to collect all derived actor and message types 491 unordered_set<const StructDecl *> actorStructDecls; 492 unordered_set<const StructDecl *> messageStructDecls; 493 FwdDeclTable forwardDecls; 494 495 // for storing through the passes 496 // these are populated with various important struct decls 497 const StructDecl * requestDeclPtr = nullptr; 498 const EnumDecl * allocationDeclPtr = nullptr; 499 const StructDecl * actorDeclPtr = nullptr; 500 const StructDecl * msgDeclPtr = nullptr; 501 502 // double pointer to modify local ptrs above 503 const StructDecl ** requestDecl = &requestDeclPtr; 504 const EnumDecl ** allocationDecl = &allocationDeclPtr; 505 const StructDecl ** actorDecl = &actorDeclPtr; 506 const StructDecl ** msgDecl = &msgDeclPtr; 507 508 // first pass collects ptrs to allocation enum, request type, and generic receive fn typedef 509 // also populates maps of all derived actors and messages 510 Pass<CollectactorStructDecls>::run( translationUnit, actorStructDecls, messageStructDecls, requestDecl, 511 allocationDecl, actorDecl, msgDecl ); 512 513 // check that we have found all the decls we need from <actor.hfa>, if not no need to run the rest of this pass 514 if ( !allocationDeclPtr || !requestDeclPtr || !actorDeclPtr || !msgDeclPtr ) 515 return; 516 517 // second pass locates all receive() routines that overload the generic receive fn 518 // it then generates the appropriate operator '|' send routines for the receive routines 519 Pass<GenFuncsCreateTables>::run( translationUnit, actorStructDecls, messageStructDecls, requestDecl, 520 allocationDecl, actorDecl, msgDecl, forwardDecls ); 521 522 // The third pass forward declares operator '|' send routines 523 Pass<FwdDeclOperator>::run( translationUnit, actorStructDecls, messageStructDecls, forwardDecls ); 524 524 } 525 526 525 527 526 } // namespace Concurrency -
src/Concurrency/Corun.cpp
rcf191ac r7042c60 26 26 27 27 struct CorunKeyword : public WithDeclsToAdd<>, public WithStmtsToAdd<> { 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 fnBody->push_back( new DeclStmt( loc, 90 91 92 93 94 95 new CastExpr( loc, 96 new NameExpr( loc, coforArgName ), 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 new SingleInit( loc, 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 new SingleInit( loc, 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 28 UniqueName CorunFnNamer = "__CFA_corun_lambda_"s; 29 UniqueName CoforFnNamer = "__CFA_cofor_lambda_"s; 30 // UniqueName CoforFnVarNamer = "__CFA_cofor_lambda_var"s; 31 UniqueName RunnerBlockNamer = "__CFA_corun_block_"s; 32 33 string coforArgName = "__CFA_cofor_lambda_arg"; 34 string numProcsName = "__CFA_cofor_num_procs"; 35 string currProcsName = "__CFA_cofor_curr_procs"; 36 string thdArrName = "__CFA_cofor_thread_array"; 37 string loopTempName = "__CFA_cofor_loop_temp"; 38 39 40 const StructDecl * runnerBlockDecl = nullptr; 41 const StructDecl * coforRunnerDecl = nullptr; 42 43 // Finds runner_block (corun task) and cofor_runner (cofor task) decls 44 void previsit( const StructDecl * decl ) { 45 if ( !decl->body ) { 46 return; 47 } else if ( "runner_block" == decl->name ) { 48 assert( !runnerBlockDecl ); 49 runnerBlockDecl = decl; 50 } else if ( "cofor_runner" == decl->name ) { 51 assert( !coforRunnerDecl ); 52 coforRunnerDecl = decl; 53 } 54 } 55 56 // codegen for cofor statements 57 Stmt * postvisit( const CoforStmt * stmt ) { 58 if ( !runnerBlockDecl || !coforRunnerDecl ) 59 SemanticError( stmt->location, "To use cofor statements add #include <cofor.hfa>" ); 60 61 if ( stmt->inits.size() != 1 ) 62 SemanticError( stmt->location, "Cofor statements must have a single initializer in the loop control" ); 63 64 if ( !stmt->body ) 65 return nullptr; 66 67 const CodeLocation & loc = stmt->location; 68 const string fnName = CoforFnNamer.newName(); 69 70 CompoundStmt * body = new CompoundStmt( loc ); 71 72 // push back cofor initializer to generated body 73 body->push_back( deepCopy( stmt->inits.at(0) ) ); 74 75 CompoundStmt * fnBody = new CompoundStmt( loc ); 76 77 const DeclStmt * declStmtPtr = dynamic_cast<const DeclStmt *>(stmt->inits.at(0).get()); 78 if ( ! declStmtPtr ) 79 SemanticError( stmt->location, "Cofor statement initializer is somehow not a decl statement?" ); 80 81 const Decl * declPtr = dynamic_cast<const Decl *>(declStmtPtr->decl.get()); 82 if ( ! declPtr ) 83 SemanticError( stmt->location, "Cofor statement initializer is somehow not a decl?" ); 84 85 Type * initType = new TypeofType( new NameExpr( loc, declPtr->name ) ); 86 87 // Generates: 88 // typeof(init) __CFA_cofor_lambda_var = *((typeof(init) *)val); 89 fnBody->push_back( new DeclStmt( loc, 90 new ObjectDecl( loc, 91 declPtr->name, 92 initType, 93 new SingleInit( loc, 94 UntypedExpr::createDeref( loc, 95 new CastExpr( loc, 96 new NameExpr( loc, coforArgName ), 97 new PointerType( initType ), ExplicitCast 98 ) 99 ) 100 ) 101 ) 102 )); 103 104 // push rest of cofor body into loop lambda 105 fnBody->push_back( deepCopy( stmt->body ) ); 106 107 // Generates: 108 // void __CFA_cofor_lambda_() { 109 // typeof(init) __CFA_cofor_lambda_var = *((typeof(init) *)val); 110 // stmt->body; 111 // } 112 Stmt * coforLambda = new DeclStmt( loc, 113 new FunctionDecl( loc, 114 fnName, // name 115 { 116 new ObjectDecl( loc, 117 coforArgName, 118 new ast::PointerType( new ast::VoidType() ) 119 ) 120 }, // params 121 {}, // return 122 fnBody // body 123 ) 124 ); 125 body->push_back( coforLambda ); 126 127 // Generates: 128 // unsigned __CFA_cofor_num_procs = get_proc_count(); 129 body->push_back( new DeclStmt( loc, 130 new ObjectDecl( loc, 131 numProcsName, 132 new BasicType( BasicKind::UnsignedInt ), 133 new SingleInit( loc, 134 new UntypedExpr( loc, 135 new NameExpr( loc, "get_proc_count" ), 136 {} 137 ) 138 ) 139 ) 140 ) 141 ); 142 143 // Generates: 144 // unsigned __CFA_cofor_curr_procs = 0; 145 body->push_back( new DeclStmt( loc, 146 new ObjectDecl( loc, 147 currProcsName, 148 new BasicType( BasicKind::UnsignedInt ), 149 new SingleInit( loc, ConstantExpr::from_int( loc, 0 ) ) 150 ) 151 ) 152 ); 153 154 // Generates: 155 // unsigned cofor_runner __CFA_cofor_thread_array[nprocs]; 156 body->push_back( new DeclStmt( loc, 157 new ObjectDecl( loc, 158 thdArrName, 159 new ast::ArrayType( 160 new StructInstType( coforRunnerDecl ), 161 new NameExpr( loc, numProcsName ), 162 ast::FixedLen, 163 ast::DynamicDim 164 ) 165 ) 166 ) 167 ); 168 169 // Generates: 170 // start_runners( __CFA_cofor_thread_array, __CFA_cofor_num_procs, __CFA_cofor_lambda_ ); 171 body->push_back( new ExprStmt( loc, 172 new UntypedExpr( loc, 173 new NameExpr( loc, "start_runners" ), 174 { 175 new NameExpr( loc, thdArrName ), 176 new NameExpr( loc, numProcsName ), 177 new NameExpr( loc, fnName ) 178 } 179 ) 180 )); 181 182 // Generates: 183 // typeof(initializer) * __CFA_cofor_loop_temp = malloc(); 184 CompoundStmt * forLoopBody = new CompoundStmt( loc ); 185 forLoopBody->push_back( new DeclStmt( loc, 186 new ObjectDecl( loc, 187 loopTempName, 188 new PointerType( initType ), 189 new SingleInit( loc, 190 new UntypedExpr( loc, 191 new NameExpr( loc, "malloc" ), 192 {} 193 ) 194 ) 195 ) 196 ) 197 ); 198 199 // Generates: 200 // *__CFA_cofor_loop_temp = initializer; 201 forLoopBody->push_back( new ExprStmt( loc, 202 UntypedExpr::createAssign( loc, 203 UntypedExpr::createDeref( loc, new NameExpr( loc, loopTempName ) ), 204 new NameExpr( loc, declPtr->name ) 205 ) 206 )); 207 208 // Generates: 209 // send_work( __CFA_cofor_thread_array, __CFA_cofor_num_procs, 210 // __CFA_cofor_curr_procs, __CFA_cofor_loop_temp ); 211 forLoopBody->push_back( new ExprStmt( loc, 212 new UntypedExpr( loc, 213 new NameExpr( loc, "send_work" ), 214 { 215 new NameExpr( loc, thdArrName ), 216 new NameExpr( loc, numProcsName ), 217 new NameExpr( loc, currProcsName ), 218 new NameExpr( loc, loopTempName ) 219 } 220 ) 221 )); 222 223 body->push_back( new ForStmt( loc, 224 {}, 225 deepCopy( stmt->cond ), 226 deepCopy( stmt->inc ), 227 forLoopBody 228 )); 229 230 // Generates: 231 // end_runners( __CFA_cofor_thread_array, __CFA_cofor_num_procs ); 232 body->push_back( new ExprStmt( loc, 233 new UntypedExpr( loc, 234 new NameExpr( loc, "end_runners" ), 235 { 236 new NameExpr( loc, thdArrName ), 237 new NameExpr( loc, numProcsName ) 238 } 239 ) 240 )); 241 242 return body; 243 } 244 245 // codegen for corun statements 246 Stmt * postvisit( const CorunStmt * stmt ) { 247 if ( !runnerBlockDecl || !coforRunnerDecl ) 248 SemanticError( stmt->location, "To use corun statements add #include <cofor.hfa>" ); 249 250 if ( !stmt->stmt ) 251 return nullptr; 252 253 const CodeLocation & loc = stmt->location; 254 const string fnName = CorunFnNamer.newName(); 255 const string objName = RunnerBlockNamer.newName(); 256 257 // Generates: 258 // void __CFA_corun_lambda_() { ... stmt->stmt ... } 259 Stmt * runnerLambda = new DeclStmt( loc, 260 new FunctionDecl( loc, 261 fnName, // name 262 {}, // params 263 {}, // return 264 new CompoundStmt( loc, { deepCopy(stmt->stmt) } ) // body 265 ) 266 ); 267 268 // Generates: 269 // runner_block __CFA_corun_block_; 270 Stmt * objDecl = new DeclStmt( loc, 271 new ObjectDecl( loc, 272 objName, 273 new StructInstType( runnerBlockDecl ) 274 ) 275 ); 276 277 // Generates: 278 // __CFA_corun_block_{ __CFA_corun_lambda_ }; 279 Stmt * threadStart = new ExprStmt( loc, 280 new UntypedExpr ( loc, 281 new NameExpr( loc, "?{}" ), 282 { 283 new NameExpr( loc, objName ), 284 new NameExpr( loc, fnName ) 285 } 286 ) 287 ); 288 289 stmtsToAddBefore.push_back( runnerLambda ); 290 stmtsToAddBefore.push_back( objDecl ); 291 292 return threadStart; 293 } 294 294 }; 295 295 296 296 void implementCorun( TranslationUnit & translationUnit ) { 297 297 Pass<CorunKeyword>::run( translationUnit ); 298 298 } 299 299 -
src/Concurrency/Keywords.cpp
rcf191ac r7042c60 991 991 ast::CompoundStmt * body = 992 992 new ast::CompoundStmt( stmt->location, { stmt->stmt } ); 993 993 994 994 return addStatements( body, stmt->mutexObjs );; 995 995 } … … 1180 1180 1181 1181 // generates a cast to the void ptr to the appropriate lock type and dereferences it before calling lock or unlock on it 1182 // used to undo the type erasure done by storing all the lock pointers as void 1182 // used to undo the type erasure done by storing all the lock pointers as void 1183 1183 ast::ExprStmt * MutexKeyword::genVirtLockUnlockExpr( const std::string & fnName, ast::ptr<ast::Expr> expr, const CodeLocation & location, ast::Expr * param ) { 1184 1184 return new ast::ExprStmt( location, … … 1187 1187 ast::UntypedExpr::createDeref( 1188 1188 location, 1189 new ast::CastExpr( location, 1189 new ast::CastExpr( location, 1190 1190 param, 1191 1191 new ast::PointerType( new ast::TypeofType( new ast::UntypedExpr( … … 1208 1208 //adds an if/elif clause for each lock to assign type from void ptr based on ptr address 1209 1209 for ( long unsigned int i = 0; i < args.size(); i++ ) { 1210 1210 1211 1211 ast::UntypedExpr * ifCond = new ast::UntypedExpr( location, 1212 1212 new ast::NameExpr( location, "?==?" ), { … … 1216 1216 ); 1217 1217 1218 ast::IfStmt * currLockIf = new ast::IfStmt( 1218 ast::IfStmt * currLockIf = new ast::IfStmt( 1219 1219 location, 1220 1220 ifCond, 1221 1221 genVirtLockUnlockExpr( fnName, args.at(i), location, ast::deepCopy( thisParam ) ) 1222 1222 ); 1223 1223 1224 1224 if ( i == 0 ) { 1225 1225 outerLockIf = currLockIf; … … 1235 1235 1236 1236 void flattenTuple( const ast::UntypedTupleExpr * tuple, std::vector<ast::ptr<ast::Expr>> & output ) { 1237 1238 1239 1240 1241 1237 for ( auto & expr : tuple->exprs ) { 1238 const ast::UntypedTupleExpr * innerTuple = dynamic_cast<const ast::UntypedTupleExpr *>(expr.get()); 1239 if ( innerTuple ) flattenTuple( innerTuple, output ); 1240 else output.emplace_back( ast::deepCopy( expr )); 1241 } 1242 1242 } 1243 1243 … … 1255 1255 // std::string unlockFnName = mutex_func_namer.newName(); 1256 1256 1257 1258 1259 1260 1261 1262 1263 1257 // If any arguments to the mutex stmt are tuples, flatten them 1258 std::vector<ast::ptr<ast::Expr>> flattenedArgs; 1259 for ( auto & arg : args ) { 1260 const ast::UntypedTupleExpr * tuple = dynamic_cast<const ast::UntypedTupleExpr *>(args.at(0).get()); 1261 if ( tuple ) flattenTuple( tuple, flattenedArgs ); 1262 else flattenedArgs.emplace_back( ast::deepCopy( arg )); 1263 } 1264 1264 1265 1265 // Make pointer to the monitors. … … 1302 1302 // adds a nested try stmt for each lock we are locking 1303 1303 for ( long unsigned int i = 0; i < flattenedArgs.size(); i++ ) { 1304 ast::UntypedExpr * innerAccess = new ast::UntypedExpr( 1304 ast::UntypedExpr * innerAccess = new ast::UntypedExpr( 1305 1305 location, 1306 1306 new ast::NameExpr( location,"?[?]" ), { … … 1426 1426 // ); 1427 1427 1428 // ast::IfStmt * currLockIf = new ast::IfStmt( 1428 // ast::IfStmt * currLockIf = new ast::IfStmt( 1429 1429 // location, 1430 1430 // ast::deepCopy( ifCond ), … … 1432 1432 // ); 1433 1433 1434 // ast::IfStmt * currUnlockIf = new ast::IfStmt( 1434 // ast::IfStmt * currUnlockIf = new ast::IfStmt( 1435 1435 // location, 1436 1436 // ifCond, 1437 1437 // genVirtLockUnlockExpr( "unlock", args.at(i), location, ast::deepCopy( thisParam ) ) 1438 1438 // ); 1439 1439 1440 1440 // if ( i == 0 ) { 1441 1441 // outerLockIf = currLockIf; … … 1450 1450 // lastUnlockIf = currUnlockIf; 1451 1451 // } 1452 1452 1453 1453 // // add pointer typing if/elifs to body of routines 1454 1454 // lock_decl->stmts = new ast::CompoundStmt( location, { outerLockIf } ); -
src/Concurrency/Waituntil.cpp
rcf191ac r7042c60 31 31 /* So this is what this pass dones: 32 32 { 33 when ( condA ) waituntil( A ){ doA(); } 34 or when ( condB ) waituntil( B ){ doB(); } 35 33 when ( condA ) waituntil( A ){ doA(); } 34 or when ( condB ) waituntil( B ){ doB(); } 35 and when ( condC ) waituntil( C ) { doC(); } 36 36 } 37 37 || … … 42 42 Generates these two routines: 43 43 static inline bool is_full_sat_1( int * clause_statuses ) { 44 return clause_statuses[0] 45 46 44 return clause_statuses[0] 45 || clause_statuses[1] 46 && clause_statuses[2]; 47 47 } 48 48 49 49 static inline bool is_done_sat_1( int * clause_statuses ) { 50 51 52 50 return has_run(clause_statuses[0]) 51 || has_run(clause_statuses[1]) 52 && has_run(clause_statuses[2]); 53 53 } 54 54 55 55 Replaces the waituntil statement above with the following code: 56 56 { 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 ... repeat ^ for B and C ... 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 doA(); 127 128 57 // used with atomic_dec/inc to get binary semaphore behaviour 58 int park_counter = 0; 59 60 // status (one for each clause) 61 int clause_statuses[3] = { 0 }; 62 63 bool whenA = condA; 64 bool whenB = condB; 65 bool whenC = condC; 66 67 if ( !whenB ) clause_statuses[1] = __SELECT_RUN; 68 if ( !whenC ) clause_statuses[2] = __SELECT_RUN; 69 70 // some other conditional settors for clause_statuses are set here, see genSubtreeAssign and related routines 71 72 // three blocks 73 // for each block, create, setup, then register select_node 74 select_node clause1; 75 select_node clause2; 76 select_node clause3; 77 78 try { 79 if ( whenA ) { register_select(A, clause1); setup_clause( clause1, &clause_statuses[0], &park_counter ); } 80 ... repeat ^ for B and C ... 81 82 // if else clause is defined a separate branch can occur here to set initial values, see genWhenStateConditions 83 84 // loop & park until done 85 while( !is_full_sat_1( clause_statuses ) ) { 86 87 // binary sem P(); 88 if ( __atomic_sub_fetch( &park_counter, 1, __ATOMIC_SEQ_CST) < 0 ) 89 park(); 90 91 // execute any blocks available with status set to 0 92 for ( int i = 0; i < 3; i++ ) { 93 if (clause_statuses[i] == __SELECT_SAT) { 94 switch (i) { 95 case 0: 96 try { 97 on_selected( A, clause1 ); 98 doA(); 99 } 100 finally { clause_statuses[i] = __SELECT_RUN; unregister_select(A, clause1); } 101 break; 102 case 1: 103 ... same gen as A but for B and clause2 ... 104 break; 105 case 2: 106 ... same gen as A but for C and clause3 ... 107 break; 108 } 109 } 110 } 111 } 112 113 // ensure that the blocks that triggered is_full_sat_1 are run 114 // by running every un-run block that is SAT from the start until 115 // the predicate is SAT when considering RUN status = true 116 for ( int i = 0; i < 3; i++ ) { 117 if (is_done_sat_1( clause_statuses )) break; 118 if (clause_statuses[i] == __SELECT_SAT) 119 ... Same if body here as in loop above ... 120 } 121 } finally { 122 // the unregister and on_selected calls are needed to support primitives where the acquire has side effects 123 // so the corresponding block MUST be run for those primitives to not lose state (example is channels) 124 if ( !has_run(clause_statuses[0]) && whenA && unregister_select(A, clause1) ) 125 on_selected( A, clause1 ) 126 doA(); 127 ... repeat if above for B and C ... 128 } 129 129 } 130 130 … … 134 134 135 135 class GenerateWaitUntilCore final { 136 136 vector<FunctionDecl *> & satFns; 137 137 UniqueName namer_sat = "__is_full_sat_"s; 138 138 UniqueName namer_run = "__is_run_sat_"s; 139 139 UniqueName namer_park = "__park_counter_"s; 140 140 UniqueName namer_status = "__clause_statuses_"s; 141 141 UniqueName namer_node = "__clause_"s; 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 // This first set of routines are all used to do the complicated job of 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 142 UniqueName namer_target = "__clause_target_"s; 143 UniqueName namer_when = "__when_cond_"s; 144 UniqueName namer_label = "__waituntil_label_"s; 145 146 string idxName = "__CFA_clause_idx_"; 147 148 struct ClauseData { 149 string nodeName; 150 string targetName; 151 string whenName; 152 int index; 153 string & statusName; 154 ClauseData( int index, string & statusName ) : index(index), statusName(statusName) {} 155 }; 156 157 const StructDecl * selectNodeDecl = nullptr; 158 159 // This first set of routines are all used to do the complicated job of 160 // dealing with how to set predicate statuses with certain when_conds T/F 161 // so that the when_cond == F effectively makes that clause "disappear" 162 void updateAmbiguousWhen( WaitUntilStmt::ClauseNode * currNode, bool andAbove, bool orAbove, bool andBelow, bool orBelow ); 163 void paintWhenTree( WaitUntilStmt::ClauseNode * currNode, bool andAbove, bool orAbove, bool & andBelow, bool & orBelow ); 164 bool paintWhenTree( WaitUntilStmt::ClauseNode * currNode ); 165 void collectWhens( WaitUntilStmt::ClauseNode * currNode, vector<pair<int, WaitUntilStmt::ClauseNode *>> & ambigIdxs, vector<int> & andIdxs, int & index, bool parentAmbig, bool parentAnd ); 166 void collectWhens( WaitUntilStmt::ClauseNode * currNode, vector<pair<int, WaitUntilStmt::ClauseNode *>> & ambigIdxs, vector<int> & andIdxs ); 167 void updateWhenState( WaitUntilStmt::ClauseNode * currNode ); 168 void genSubtreeAssign( const WaitUntilStmt * stmt, WaitUntilStmt::ClauseNode * currNode, bool status, int & idx, CompoundStmt * retStmt, vector<ClauseData *> & clauseData ); 169 void genStatusAssign( const WaitUntilStmt * stmt, WaitUntilStmt::ClauseNode * currNode, int & idx, CompoundStmt * retStmt, vector<ClauseData *> & clauseData ); 170 CompoundStmt * getStatusAssignment( const WaitUntilStmt * stmt, vector<ClauseData *> & clauseData ); 171 Stmt * genWhenStateConditions( const WaitUntilStmt * stmt, vector<ClauseData *> & clauseData, vector<pair<int, WaitUntilStmt::ClauseNode *>> & ambigClauses, vector<pair<int, WaitUntilStmt::ClauseNode *>>::size_type ambigIdx ); 172 173 // These routines are just code-gen helpers 174 void addPredicates( const WaitUntilStmt * stmt, string & satName, string & runName ); 175 void setUpClause( const WhenClause * clause, ClauseData * data, string & pCountName, CompoundStmt * body ); 176 CompoundStmt * genStatusCheckFor( const WaitUntilStmt * stmt, vector<ClauseData *> & clauseData, string & predName ); 177 Expr * genSelectTraitCall( const WhenClause * clause, const ClauseData * data, string fnName ); 178 CompoundStmt * genStmtBlock( const WhenClause * clause, const ClauseData * data ); 179 Stmt * genElseClauseBranch( const WaitUntilStmt * stmt, string & runName, string & arrName, vector<ClauseData *> & clauseData ); 180 Stmt * genNoElseClauseBranch( const WaitUntilStmt * stmt, string & runName, string & arrName, string & pCountName, vector<ClauseData *> & clauseData ); 181 void genClauseInits( const WaitUntilStmt * stmt, vector<ClauseData *> & clauseData, CompoundStmt * body, string & statusName, string & elseWhenName ); 182 Stmt * recursiveOrIfGen( const WaitUntilStmt * stmt, vector<ClauseData *> & data, vector<ClauseData*>::size_type idx, string & elseWhenName ); 183 Stmt * buildOrCaseSwitch( const WaitUntilStmt * stmt, string & statusName, vector<ClauseData *> & data ); 184 Stmt * genAllOr( const WaitUntilStmt * stmt ); 185 185 186 186 public: 187 187 void previsit( const StructDecl * decl ); 188 188 Stmt * postvisit( const WaitUntilStmt * stmt ); 189 189 GenerateWaitUntilCore( vector<FunctionDecl *> & satFns ): satFns(satFns) {} 190 190 }; 191 191 192 192 // Finds select_node decl 193 193 void GenerateWaitUntilCore::previsit( const StructDecl * decl ) { 194 194 if ( !decl->body ) { 195 195 return; 196 196 } else if ( "select_node" == decl->name ) { … … 201 201 202 202 void GenerateWaitUntilCore::updateAmbiguousWhen( WaitUntilStmt::ClauseNode * currNode, bool andAbove, bool orAbove, bool andBelow, bool orBelow ) { 203 204 205 206 207 203 // all children when-ambiguous 204 if ( currNode->left->ambiguousWhen && currNode->right->ambiguousWhen ) 205 // true iff an ancestor/descendant has a different operation 206 currNode->ambiguousWhen = (orAbove || orBelow) && (andBelow || andAbove); 207 // ambiguousWhen is initially false so theres no need to set it here 208 208 } 209 209 … … 215 215 // - All of its descendent clauses are optional, i.e. they have a when_cond defined on the WhenClause 216 216 void GenerateWaitUntilCore::paintWhenTree( WaitUntilStmt::ClauseNode * currNode, bool andAbove, bool orAbove, bool & andBelow, bool & orBelow ) { 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243