Index: Jenkinsfile =================================================================== --- Jenkinsfile (revision f6f0cca3f172613989f420c40761026fe191b651) +++ Jenkinsfile (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -260,7 +260,12 @@ def install_dir = pwd tmp: true + //Output compiler version to help with debug + echo """C++ Compiler :""" + sh "which ${compiler.cpp_cc} && ${compiler.cpp_cc} --version" + echo """C Compiler :""" + sh "which ${compiler.cfa_cc} && ${compiler.cfa_cc} --version" + //Configure the conpilation (Output is not relevant) - //Use the current directory as the installation target so nothing - //escapes the sandbox + //Use the current directory as the installation target so nothing escapes the sandbox //Also specify the compiler by hand sh "./configure CXX=${compiler.cpp_cc} ${architecture} --with-backend-compiler=${compiler.cfa_cc} --prefix=${install_dir} --enable-silent-rules --quiet" Index: doc/bibliography/pl.bib =================================================================== --- doc/bibliography/pl.bib (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/bibliography/pl.bib (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -137,6 +137,5 @@ @article{Nierstrasz87, - keywords = {Hybrid, active objects, object-oriented languages, - object-based languages, delegation, concurrency}, + keywords = {Hybrid, active objects, object-oriented languages, object-based languages, delegation, concurrency}, contributer = {pabuhr@plg}, author = {O. M. Nierstrasz}, @@ -782,5 +781,5 @@ howpublished= {\href{http://www.boost.org/doc/libs/1_61_0/libs/coroutine/doc/html/index.html} {{http://www.boost.org/\-doc/\-libs/1\_61\_0/\-libs/\-coroutine/\-doc/\-html/\-index.html}}}, - note = {Accessed: 2016-09}, + optnote = {Accessed: 2016-09}, } @@ -855,10 +854,10 @@ keywords = {ANSI C 89}, contributer = {gjditchfield@plg}, - title = {American National Standard for Information Systems -- Programming Language -- {C}}, + author = {C90}, + title = {Programming Languages -- {C}}, organization= {American National Standards Institute}, - address = {1430 Broadway, New York, New York 10018}, - month = dec, - year = 1989, - note = {X3.159-1989} + address = {New York, NY, U.S.A.}, + year = 1990, + note = {ANSI/ISO 9899-1990} } @@ -888,5 +887,5 @@ title = {\textsf{C}{$\mathbf{\forall}$} Features}, howpublished= {\url{https://plg.uwaterloo.ca/~cforall/features}}, - note = {Accessed: 2018-01-01}, + optnote = {Accessed: 2018-01-01}, } @@ -900,4 +899,22 @@ address = {Waterloo, Ontario, Canada, N2L 3G1}, note = {\href{http://plg.uwaterloo.ca/theses/EstevesThesis.pdf}{http://\-plg.uwaterloo.ca/\-theses/\-EstevesThesis.pdf}}, +} + +@misc{CFAStackEvaluation, + author = {Aaron Moss}, + title = {\textsf{C}$\mathbf{\forall}$ Stack Evaluation Programs}, + year = 2018, + howpublished= {\href{https://plg.uwaterloo.ca/~cforall/evaluation.zip}{https://plg.uwaterloo.ca/\-\-$\sim$cforall/\-StackEvaluation.zip}}, + optnote = {[Accessed May 2018]}, +} + +@article{Moss18, + keywords = {concurrency, C++}, + contributer = {pabuhr@plg}, + author = {Aaron Moss and Robert Schluntz and Peter A. Buhr}, + title = {\textsf{C}$\mathbf{\forall}$ : Adding Modern Programming Language Features to C}, + year = 2018, + journal = spe, + note = {Accepted, to appear}, } @@ -1640,4 +1657,16 @@ } +@misc{Taylor10, + keywords = {const, poisoning}, + contributer = {pabuhr@plg}, + author = {Ian Lance Taylor}, + title = {const}, + month = oct, + year = 2010, + howpublished= {\href{https://www.airs.com/blog/archives/428} + {https://www.airs.com/\-blog/\-archives/\-428}}, + optnote = {Accessed: 2018-05}, +} + @phdthesis{Ditchfield92, keywords = {C, parametric polymorphism, overloading}, @@ -2755,10 +2784,10 @@ @misc{GCCExtensions, contributer = {a3moss@uwaterloo.ca}, - key = {{GNU}}, + key = {C Extensions}, author = {{C Extensions}}, title = {Extensions to the {C} Language Family}, year = 2014, howpublished= {\href{https://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/C-Extensions.html}{https://\-gcc.gnu.org/\-onlinedocs/\-gcc-4.7.2/\-gcc/\-C\-Extensions.html}}, - note = {Accessed: 2017-04-02}, + optnote = {Accessed: 2017-04-02}, } @@ -2947,4 +2976,13 @@ month = jul, year = 1987, volume = 4, number = 4, pages = {9-16} +} + +@misc{Sutter05c, + contributer = {pabuhr@plg}, + title = {The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software}, + author = {Herb Sutter}, + howpublished= {\url{http://www.gotw.ca/publications/concurrency-ddj.htm}}, + year = {2005}, + note = {originally Dr. Dobb's Journal 30(3)}, } @@ -3137,5 +3175,5 @@ year = 2014, howpublished= {https://developer.gnome.org/gobject/stable/}, - note = {Accessed: 2017-04}, + optnote = {Accessed: 2017-04}, } @@ -3209,4 +3247,14 @@ % H + +@manual{Haskell10, + keywords = {Haskell}, + contributer = {pabuhr@plg}, + author = {Haskell}, + title = {Haskell 2010 Language Report}, + edition = {{S}imon {M}arlow}, + year = 2010, + note = {\href{https://haskell.org/definition/haskell2010.pdf}{https://haskell.org/\-definition/\-haskell2010.pdf}}, +} @article{Michael04a, @@ -3760,5 +3808,5 @@ keywords = {concurrency, critical section}, contributer = {pabuhr@plg}, - author = {Dominic Duggan and Gordon V. Cormack and John Ophel}, + author = {Dominic Duggan and G. V. Cormack and John Ophel}, title = {Kinded Type Inference for Parametric Overloading}, journal = acta, @@ -4685,5 +4733,5 @@ year = 2015, howpublished= {\href{https://developer.apple.com/library/content/documentation/General/Conceptual/DevPedia-CocoaCore/ObjectiveC.html}{https://developer.apple.com/\-library/\-content/\-documentation/\-General/\-Conceptual/\-DevPedia-\-CocoaCore/\-ObjectiveC.html}}, - note = {Accessed: 2018-03} + optnote = {Accessed: 2018-03} } @@ -4695,5 +4743,5 @@ year = 2015, howpublished= {\href{https://developer.apple.com/library/content/documentation/Xcode/Conceptual/RN-Xcode-Archive/Chapters/xc7_release_notes.html}{https://developer.apple.com/\-library/\-content/\-documentation/\-Xcode/\-Conceptual/\-RN-Xcode-Archive/\-Chapters/\-xc7\_release\_notes.html}}, - note = {Accessed: 2017-04} + optnote = {Accessed: 2017-04} } @@ -5757,5 +5805,5 @@ keywords = {Cyclone, existential types, polymorphism, type variables}, contributer = {a3moss@plg}, - author = {Dan Grossman}, + author = {D. Grossman}, title = {Quantified Types in an Imperative Language}, journal = toplas, @@ -6762,5 +6810,5 @@ title = {{TIOBE} Index}, howpublished= {\href{http://www.tiobe.com/tiobe_index}{http://\-www.tiobe.com/\-tiobe\_index}}, - note = {Accessed: 2018-09}, + optnote = {Accessed: 2018-09}, } @@ -7087,5 +7135,5 @@ year = 2017, howpublished= {\url{https://wiki.gnome.org/Projects/Vala/Manual}}, - note = {Accessed: 2017-04} + optnote = {Accessed: 2017-04} } Index: doc/papers/AMA/AMA-stix/Documents/README.txt =================================================================== --- doc/papers/AMA/AMA-stix/Documents/README.txt (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/AMA/AMA-stix/Documents/README.txt (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -13,12 +13,5 @@ % NJDnatbib.sty --> NJD natbib reference package. % Stix-Fonts (folder) --> Stix font files - -% MiKTeX 2.9 (Freeware software) is required to install STIX/LATO fonts -% Download MiKTeX installer & instructions from the below URLs - https://miktex.org/download - Instructions to install the basic MiKTeX installer - https://miktex.org/howto/install-miktex - -% Execute(double click) --> Windows-Stix-fontinstaller.exe from Stix-Fonts folder (This EXE file will install fonts to local drive) (please rename Windows-Stix-fontinstaller.e_xe to Windows-Stix-fontinstaller.exe) +% Execute(double click) --> Windows-Stix-fontinstaller.exe from Stix-Fonts folder (This EXE file will install fonts to local drive) % Still shows font error, please do the following % Start-->run--> type "mo_edmin.exe" and press enter Index: doc/papers/AMA/AMA-stix/ama/WileyNJD-AMA.bst =================================================================== --- doc/papers/AMA/AMA-stix/ama/WileyNJD-AMA.bst (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/AMA/AMA-stix/ama/WileyNJD-AMA.bst (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -502,5 +502,5 @@ editor empty$ { booktitle emphasize * } - { " " * format.editors * " " * booktitle emphasize * ", " * } + { " " * format.editors * " " * booktitle emphasize * ", " * } if$ } @@ -691,4 +691,5 @@ { format.journal emphasize "journal" output.check format.date add.semicolon "year" output.check + blank.sep format.volume output format.number output @@ -824,5 +825,7 @@ new.block format.pages output + new.block organization output + new.block publisher output inproformat.date "year" output.check @@ -863,4 +866,5 @@ { new.block organization new.block address new.block.checkb organization output + new.block address output } @@ -883,4 +887,5 @@ new.block school "school" output.check + new.block address output format.date "year" output.check @@ -927,4 +932,5 @@ "PhD thesis" format.thesis.type output.nonnull school "school" output.check + new.block address output format.date "year" output.check Index: doc/papers/AMA/AMA-stix/ama/WileyNJD-v2.cls =================================================================== --- doc/papers/AMA/AMA-stix/ama/WileyNJD-v2.cls (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/AMA/AMA-stix/ama/WileyNJD-v2.cls (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -484,6 +484,4 @@ \if@STIXLargeOneCol% \RequirePackage[not1,notextcomp,lcgreekalpha]{stix}% -\usepackage[scaled]{helvet} -\renewcommand\familydefault{\sfdefault} \usepackage[T1]{fontenc} \BXhsize=170mm% @@ -528,9 +526,9 @@ %\RequirePackage[not1,notextcomp,lcgreekalpha]{stix}% -\captionsetup[figure]{labelformat=simple, labelsep=space, skip=10pt, labelfont=bf} -\captionsetup[table]{labelformat=simple, labelsep=space, skip=10pt, labelfont=bf} -\renewcommand{\thefigure}{\arabic{figure}} - -\renewcommand{\thetable}{\arabic{table}} +\captionsetup[figure]{labelformat=simple, labelsep=none, skip=10pt, labelfont=bf} +\captionsetup[table]{labelformat=simple, labelsep=none, skip=10pt, labelfont=bf} +\renewcommand{\thefigure}{\arabic{figure}\enspace } + +\renewcommand{\thetable}{\arabic{table}\enspace } \renewcommand\figurename{\textbf{FIGURE}}%% @@ -966,5 +964,5 @@ % Footnotes % -%\renewcommand\thefootnote{\@fnsymbol\c@footnote}% +%%\renewcommand\thefootnote{\@fnsymbol\c@footnote}% @@ -1279,7 +1277,7 @@ \if@font@stix% - \def\footnotetextfont{\sffamily\fontsize{8bp}{10bp}\selectfont}\else% + \def\footnotetextfont{\rmfamily\fontsize{8bp}{10bp}\selectfont}\else% %% - \def\footnotetextfont{\sffamily\fontsize{6bp}{8bp}\selectfont} + \def\footnotetextfont{\rmfamily\fontsize{6bp}{8bp}\selectfont} \fi% % @@ -1294,5 +1292,5 @@ \DeclareRobustCommand\sfitseries{\not@math@alphabet\sfitseries\normalfont\fontseries{m}\fontshape{it}\selectfont} \DeclareTextFontCommand{\textsfi}{\sfitseries} -\DeclareOldFontCommand{\rm}{\normalfont\sffamily}{\mathrm} +\DeclareOldFontCommand{\rm}{\normalfont\rmfamily}{\mathrm} \DeclareOldFontCommand{\sf}{\normalfont\sffamily}{\mathsf} \DeclareOldFontCommand{\tt}{\normalfont\ttfamily}{\mathtt} @@ -1322,5 +1320,5 @@ \renewcommand\normalsize{% \if@font@stix% - \@setfontsize\normalsize{9bp}{12bp}% + \@setfontsize\normalsize{10bp}{13bp}% \else% \@setfontsize\normalsize{8bp}{13bp}% @@ -1414,54 +1412,54 @@ \gdef\@stix@font@defn{% % -% \def\infoboxfont{\fontfamily{tim}\fontsize{8}{8}\selectfont}% + \def\infoboxfont{\fontfamily{tim}\fontsize{8}{8}\selectfont}% % -% \def\watermarkfont{\reset@font\fontfamily{\ffdefault}\fontsize{45}{45}\bfseries\selectfont} + \def\watermarkfont{\reset@font\fontfamily{\ffdefault}\fontsize{45}{45}\bfseries\selectfont} % - \def\pagenumfont{\sffamily\fontsize{7}{9}\bfseries\selectfont}% - \def\cnmpagenumfont{\sffamily\fontsize{7}{9}\selectfont\bfseries}% -%%% \def\runningheadfont{\sffamily\fontsize{7}{9}\scshape\selectfont}% - \def\runningheadfont{\sffamily\fontsize{7}{9}\selectfont}%New updations 19aug2016 - \def\runningfootfont{\sffamily\fontsize{7}{9}\selectfont}% - \def\titlepageheadfont{\sffamily\fontsize{7}{9}\selectfont}% + \def\pagenumfont{\rmfamily\fontsize{7}{9}\bfseries\selectfont}% + \def\cnmpagenumfont{\rmfamily\fontsize{7}{9}\selectfont\bfseries}% +%%% \def\runningheadfont{\rmfamily\fontsize{7}{9}\scshape\selectfont}% + \def\runningheadfont{\rmfamily\fontsize{7}{9}\selectfont}%New updations 19aug2016 + \def\runningfootfont{\rmfamily\fontsize{7}{9}\selectfont}% + \def\titlepageheadfont{\rmfamily\fontsize{7}{9}\selectfont}% % - \def\BRarttypefont{\reset@font\sffamily\fontsize{18}{18}\fontseries{b}\selectfont}% - \def\pubheadfont{\reset@font\sffamily\fontsize{7}{9}\fontseries{b}\selectfont}% - \def\arttypefont{\sffamily\fontsize{9}{9}\fontseries{b}\selectfont}% - \def\SParttypefont{\sffamily\fontsize{9}{12}\fontseries{b}\selectfont}% - \def\titlefont{\sffamily\fontsize{18}{23}\bfseries\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\subtitlefont{\sffamily\fontsize{16}{21}\bfseries\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\Authorfont{\sffamily\fontsize{12}{18}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\absheadfont{\hsize\abs@colii@hsize\sffamily\fontsize{10}{10}\fontseries{b}\selectfont\bfseries\leftskip7\p@\rightskip\leftskip}% LN20FEB2016 - \def\legalstatementfont{\sffamily\fontsize{7}{10}\selectfont\leftskip0\p@\rightskip\leftskip}% - \def\BRsectionfont{\sffamily\fontsize{10}{16}\fontseries{b}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\sectionfont{\sffamily\fontsize{12}{13}\fontseries{b}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\subsectionfont{\sffamily\fontsize{12}{13}\bfseries\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\subsubsectionfont{\sffamily\fontsize{12}{13}\bfseries\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\paragraphfont{\sffamily\fontsize{10.5}{13}\fontseries{b}\selectfont}% - \def\subparagraphfont{\sffamily\fontsize{10}{13}\fontseries{b}\selectfont}% - \def\appsectionfont{\sffamily\fontsize{10}{13}\fontseries{b}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\BRarttypefont{\reset@font\rmfamily\fontsize{18}{18}\fontseries{b}\selectfont}% + \def\pubheadfont{\reset@font\rmfamily\fontsize{7}{9}\fontseries{b}\selectfont}% + \def\arttypefont{\rmfamily\fontsize{9}{9}\fontseries{b}\selectfont}% + \def\SParttypefont{\rmfamily\fontsize{9}{12}\fontseries{b}\selectfont}% + \def\titlefont{\rmfamily\fontsize{18}{23}\bfseries\selectfont\leftskip\z@\rightskip\z@ plus1fil\let\mathbcal\titmathbcal}% + \def\subtitlefont{\rmfamily\fontsize{16}{21}\bfseries\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\Authorfont{\rmfamily\fontsize{12}{18}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\absheadfont{\hsize\abs@colii@hsize\rmfamily\fontsize{10}{10}\fontseries{b}\selectfont\bfseries\leftskip7\p@\rightskip\leftskip}% LN20FEB2016 + \def\legalstatementfont{\rmfamily\fontsize{7}{10}\selectfont\leftskip0\p@\rightskip\leftskip}% + \def\BRsectionfont{\rmfamily\fontsize{10}{16}\fontseries{b}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\sectionfont{\rmfamily\fontsize{12}{13}\fontseries{b}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\subsectionfont{\rmfamily\fontsize{12}{13}\bfseries\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\subsubsectionfont{\rmfamily\fontsize{12}{13}\bfseries\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\paragraphfont{\rmfamily\fontsize{10.5}{13}\fontseries{b}\selectfont}% + \def\subparagraphfont{\rmfamily\fontsize{10}{13}\fontseries{b}\selectfont}% + \def\appsectionfont{\rmfamily\fontsize{10}{13}\fontseries{b}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% % - \def\boxheadfont{\sffamily\fontsize{10}{13}\fontseries{b}\selectfont} - \def\boxtitlefont{\sffamily\fontsize{10}{13}\bfseries\selectfont} + \def\boxheadfont{\rmfamily\fontsize{10}{13}\fontseries{b}\selectfont} + \def\boxtitlefont{\rmfamily\fontsize{10}{13}\bfseries\selectfont} % - \def\GnSabsfont{\sffamily\fontsize{9}{15}\selectfont}% - \def\GnSabsfootfont{\reset@font\sffamily\fontsize{14}{0}\bfseries\selectfont}% + \def\GnSabsfont{\rmfamily\fontsize{9}{15}\selectfont}% + \def\GnSabsfootfont{\reset@font\rmfamily\fontsize{14}{0}\bfseries\selectfont}% % - \def\suppinfofont{\noindent\sffamily}% + \def\suppinfofont{\noindent\rmfamily}% \def\suppinfoheadfont{\noindent\fontsize{10}{13}\fontseries{b}\selectfont}% - \def\suppinfocaptionfont{\noindent\sffamily}% + \def\suppinfocaptionfont{\noindent\rmfamily}% % - \def\figurenumfont{\sffamily\fontsize{9bp}{12}\fontseries{b}\selectfont}% - \def\figurecaptionfont{\sffamily\fontsize{8.5bp}{12}\selectfont} + \def\figurenumfont{\rmfamily\fontsize{9bp}{12}\fontseries{b}\selectfont}% + \def\figurecaptionfont{\rmfamily\fontsize{8.5bp}{12}\selectfont} \def\bwfiginfofont{\fontfamily{tim}\fontsize{10bp}{10bp}\selectfont}% % - \def\tablenumfont{\sffamily\fontsize{9bp}{11.5bp}\fontseries{b}\selectfont}% - \def\keypointheadfont{\reset@font\sffamily\fontsize{10bp}{13bp}\fontseries{b}\selectfont}% - \def\tablecaptionfont{\sffamily\fontsize{8.5bp}{12bp}\selectfont} - \def\tablebodyfont{\sffamily\fontsize{8.5bp}{11.5bp}\selectfont} - \def\tablecolheadfont{\sffamily\fontsize{8.5bp}{11.5bp}\selectfont\bfseries} - \def\tablefootnotefont{\sffamily\fontsize{7.5bp}{10.5bp}\selectfont} + \def\tablenumfont{\rmfamily\fontsize{9bp}{11.5bp}\fontseries{b}\selectfont}% + \def\keypointheadfont{\reset@font\rmfamily\fontsize{10bp}{13bp}\fontseries{b}\selectfont}% + \def\tablecaptionfont{\rmfamily\fontsize{8.5bp}{12bp}\selectfont} + \def\tablebodyfont{\rmfamily\fontsize{8.5bp}{11.5bp}\selectfont} + \def\tablecolheadfont{\rmfamily\fontsize{8.5bp}{11.5bp}\selectfont\bfseries} + \def\tablefootnotefont{\rmfamily\fontsize{7.5bp}{10.5bp}\selectfont} % -%% \def\footnotetextfont{\sffamily\fontsize{8bp}{10bp}\selectfont} +%% \def\footnotetextfont{\rmfamily\fontsize{8bp}{10bp}\selectfont} % \def\listfont{\normalsize}% @@ -1473,74 +1471,74 @@ % \def\ackheadfont{\fontsize{10}{13}\selectfont\fontseries{b}\selectfont} - \def\addressfont{\hsize\abs@coli@hsize\sffamily\fontsize{8}{11}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\corresfont{\hsize\abs@coli@hsize\sffamily\fontsize{8}{11}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\FIfont{\hsize\abs@coli@hsize\sffamily\fontsize{8}{11}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\JELfont{\hsize\abs@coli@hsize\sffamily\fontsize{8}{11}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\keywordsheadfont{\hsize\abs@colii@hsize\sffamily\fontsize{8}{8}\selectfont\ifAbstractexist\leftskip7\p@\rightskip\leftskip\fi}% - \def\abstractfont{\hsize\abs@colii@hsize\sffamily\fontsize{9}{14}\selectfont\leftskip7\p@\rightskip\leftskip}% - \def\keywordsfont{\sffamily\fontsize{8}{13}\selectfont\ifAbstractexist\leftskip7\p@\rightskip\leftskip\fi}% + \def\addressfont{\hsize\abs@coli@hsize\rmfamily\fontsize{8}{11}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\corresfont{\hsize\abs@coli@hsize\rmfamily\fontsize{8}{11}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\FIfont{\hsize\abs@coli@hsize\rmfamily\fontsize{8}{11}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\JELfont{\hsize\abs@coli@hsize\rmfamily\fontsize{8}{11}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\keywordsheadfont{\hsize\abs@colii@hsize\rmfamily\fontsize{8}{8}\selectfont\ifAbstractexist\leftskip7\p@\rightskip\leftskip\fi}% + \def\abstractfont{\hsize\abs@colii@hsize\rmfamily\fontsize{10}{15}\selectfont\leftskip7\p@\rightskip\leftskip}% + \def\keywordsfont{\rmfamily\fontsize{8}{13}\selectfont\ifAbstractexist\leftskip7\p@\rightskip\leftskip\fi}% % }% \gdef\@lato@font@defn{% % -% \def\infoboxfont{\fontfamily{tim}\fontsize{8}{8}\selectfont}% + \def\infoboxfont{\fontfamily{tim}\fontsize{8}{8}\selectfont}% % -% \def\watermarkfont{\reset@font\fontfamily{\ffdefault}\fontsize{45}{45}\bfseries\selectfont} + \def\watermarkfont{\reset@font\fontfamily{\ffdefault}\fontsize{45}{45}\bfseries\selectfont} % - \def\pagenumfont{\sffamily\fontsize{7}{9}\bfseries\selectfont}% - \def\cnmpagenumfont{\sffamily\fontsize{7}{9}\selectfont\bfseries}% -%%% \def\runningheadfont{\sffamily\fontsize{7}{9}\scshape\selectfont}% - \def\runningheadfont{\sffamily\fontsize{7}{9}\selectfont}%New updations 19aug2016 - \def\runningfootfont{\sffamily\fontsize{7}{9}\selectfont}% - \def\titlepageheadfont{\sffamily\fontsize{7}{9}\selectfont}% + \def\pagenumfont{\rmfamily\fontsize{7}{9}\bfseries\selectfont}% + \def\cnmpagenumfont{\rmfamily\fontsize{7}{9}\selectfont\bfseries}% +%%% \def\runningheadfont{\rmfamily\fontsize{7}{9}\scshape\selectfont}% + \def\runningheadfont{\rmfamily\fontsize{7}{9}\selectfont}%New updations 19aug2016 + \def\runningfootfont{\rmfamily\fontsize{7}{9}\selectfont}% + \def\titlepageheadfont{\rmfamily\fontsize{7}{9}\selectfont}% % - \def\BRarttypefont{\reset@font\sffamily\fontsize{18}{18}\fontseries{b}\selectfont}% - \def\pubheadfont{\reset@font\sffamily\fontsize{7}{9}\fontseries{b}\selectfont}% - \def\arttypefont{\sffamily\fontsize{9}{9}\fontseries{b}\selectfont}% - \def\SParttypefont{\sffamily\fontsize{9}{12}\fontseries{b}\selectfont}% - \def\titlefont{\sffamily\fontsize{18}{23}\bfseries\selectfont\leftskip\z@\rightskip\z@ plus1fil\let\mathbcal\titmathbcal}% - \def\subtitlefont{\sffamily\fontsize{16}{21}\bfseries\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\Authorfont{\sffamily\fontsize{12}{18}\selectfont\bfseries\leftskip\z@\rightskip\z@ plus1fil}% - \def\addressfont{\hsize\abs@coli@hsize\sffamily\fontsize{7}{10}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\corresfont{\hsize\abs@coli@hsize\sffamily\fontsize{7}{10}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\BRarttypefont{\reset@font\rmfamily\fontsize{18}{18}\fontseries{b}\selectfont}% + \def\pubheadfont{\reset@font\rmfamily\fontsize{7}{9}\fontseries{b}\selectfont}% + \def\arttypefont{\rmfamily\fontsize{9}{9}\fontseries{b}\selectfont}% + \def\SParttypefont{\rmfamily\fontsize{9}{12}\fontseries{b}\selectfont}% + \def\titlefont{\rmfamily\fontsize{18}{23}\bfseries\selectfont\leftskip\z@\rightskip\z@ plus1fil\let\mathbcal\titmathbcal}% + \def\subtitlefont{\rmfamily\fontsize{16}{21}\bfseries\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\Authorfont{\rmfamily\fontsize{12}{18}\selectfont\bfseries\leftskip\z@\rightskip\z@ plus1fil}% + \def\addressfont{\hsize\abs@coli@hsize\rmfamily\fontsize{7}{10}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\corresfont{\hsize\abs@coli@hsize\rmfamily\fontsize{7}{10}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% % - \def\FIfont{\hsize\abs@coli@hsize\sffamily\fontsize{7}{10}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\JELfont{\hsize\abs@coli@hsize\sffamily\fontsize{7}{10}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\abstractfont{\hsize\abs@colii@hsize\sffamily\fontsize{8}{13}\selectfont\leftskip7\p@\rightskip\leftskip}% - \def\keywordsheadfont{\hsize\abs@colii@hsize\sffamily\fontsize{7}{7}\selectfont\ifAbstractexist\leftskip7\p@\rightskip\leftskip\fi}% - \def\absheadfont{\hsize\abs@colii@hsize\sffamily\fontsize{10}{10}\fontseries{b}\selectfont\bfseries\leftskip7\p@\rightskip\leftskip}% LN20FEB2016 - \def\keywordsfont{\sffamily\fontsize{8}{13}\selectfont\ifAbstractexist\leftskip7\p@\rightskip\leftskip\fi}% - \def\legalstatementfont{\sffamily\fontsize{7}{10}\selectfont\leftskip0\p@\rightskip\leftskip}% + \def\FIfont{\hsize\abs@coli@hsize\rmfamily\fontsize{7}{10}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\JELfont{\hsize\abs@coli@hsize\rmfamily\fontsize{7}{10}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\abstractfont{\hsize\abs@colii@hsize\rmfamily\fontsize{8}{13}\selectfont\leftskip7\p@\rightskip\leftskip}% + \def\keywordsheadfont{\hsize\abs@colii@hsize\rmfamily\fontsize{7}{7}\selectfont\ifAbstractexist\leftskip7\p@\rightskip\leftskip\fi}% + \def\absheadfont{\hsize\abs@colii@hsize\rmfamily\fontsize{10}{10}\fontseries{b}\selectfont\bfseries\leftskip7\p@\rightskip\leftskip}% LN20FEB2016 + \def\keywordsfont{\rmfamily\fontsize{8}{13}\selectfont\ifAbstractexist\leftskip7\p@\rightskip\leftskip\fi}% + \def\legalstatementfont{\rmfamily\fontsize{7}{10}\selectfont\leftskip0\p@\rightskip\leftskip}% % - \def\BRsectionfont{\sffamily\fontsize{10}{16}\fontseries{b}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\sectionfont{\sffamily\fontsize{10}{13}\fontseries{b}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\subsectionfont{\sffamily\fontsize{10}{14}\bfseries\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\subsubsectionfont{\sffamily\fontsize{9}{12.5}\bfseries\selectfont\leftskip\z@\rightskip\z@ plus1fil}% - \def\paragraphfont{\sffamily\fontsize{8.5}{13}\fontseries{b}\selectfont}% - \def\subparagraphfont{\sffamily\fontsize{8.5}{13}\fontseries{b}\selectfont}% - \def\appsectionfont{\sffamily\fontsize{8}{11}\fontseries{b}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\BRsectionfont{\rmfamily\fontsize{10}{16}\fontseries{b}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\sectionfont{\rmfamily\fontsize{10}{13}\fontseries{b}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\subsectionfont{\rmfamily\fontsize{10}{14}\bfseries\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\subsubsectionfont{\rmfamily\fontsize{9}{12.5}\bfseries\selectfont\leftskip\z@\rightskip\z@ plus1fil}% + \def\paragraphfont{\rmfamily\fontsize{8.5}{13}\fontseries{b}\selectfont}% + \def\subparagraphfont{\rmfamily\fontsize{8.5}{13}\fontseries{b}\selectfont}% + \def\appsectionfont{\rmfamily\fontsize{8}{11}\fontseries{b}\selectfont\leftskip\z@\rightskip\z@ plus1fil}% % - \def\boxheadfont{\sffamily\fontsize{8}{10}\fontseries{b}\selectfont} - \def\boxtitlefont{\sffamily\fontsize{8}{10}\bfseries\selectfont} + \def\boxheadfont{\rmfamily\fontsize{8}{10}\fontseries{b}\selectfont} + \def\boxtitlefont{\rmfamily\fontsize{8}{10}\bfseries\selectfont} % - \def\GnSabsfont{\sffamily\fontsize{9}{15}\selectfont}% - \def\GnSabsfootfont{\reset@font\sffamily\fontsize{14}{0}\bfseries\selectfont}% + \def\GnSabsfont{\rmfamily\fontsize{9}{15}\selectfont}% + \def\GnSabsfootfont{\reset@font\rmfamily\fontsize{14}{0}\bfseries\selectfont}% % - \def\suppinfofont{\noindent\sffamily}% + \def\suppinfofont{\noindent\rmfamily}% \def\suppinfoheadfont{\noindent\fontsize{8}{13}\fontseries{b}\selectfont}% - \def\suppinfocaptionfont{\noindent\sffamily}% + \def\suppinfocaptionfont{\noindent\rmfamily}% % - \def\figurenumfont{\sffamily\fontsize{7bp}{9}\fontseries{b}\selectfont}% - \def\figurecaptionfont{\sffamily\fontsize{8bp}{11}\selectfont} + \def\figurenumfont{\rmfamily\fontsize{7bp}{9}\fontseries{b}\selectfont}% + \def\figurecaptionfont{\rmfamily\fontsize{8bp}{11}\selectfont} \def\bwfiginfofont{\fontfamily{tim}\fontsize{10bp}{10bp}\selectfont}% % - \def\tablenumfont{\sffamily\fontsize{7bp}{9bp}\fontseries{b}\selectfont}% - \def\keypointheadfont{\reset@font\sffamily\fontsize{9bp}{11bp}\fontseries{b}\selectfont}% - \def\tablecaptionfont{\sffamily\fontsize{8bp}{9bp}\selectfont} - \def\tablebodyfont{\sffamily\fontsize{7.5bp}{9bp}\selectfont} - \def\tablecolheadfont{\sffamily\fontsize{7.5bp}{9bp}\selectfont\bfseries} - \def\tablefootnotefont{\sffamily\fontsize{7.5bp}{9bp}\selectfont} + \def\tablenumfont{\rmfamily\fontsize{7bp}{9bp}\fontseries{b}\selectfont}% + \def\keypointheadfont{\reset@font\rmfamily\fontsize{9bp}{11bp}\fontseries{b}\selectfont}% + \def\tablecaptionfont{\rmfamily\fontsize{8bp}{9bp}\selectfont} + \def\tablebodyfont{\rmfamily\fontsize{7.5bp}{9bp}\selectfont} + \def\tablecolheadfont{\rmfamily\fontsize{7.5bp}{9bp}\selectfont\bfseries} + \def\tablefootnotefont{\rmfamily\fontsize{7.5bp}{9bp}\selectfont} % -%% \def\footnotetextfont{\sffamily\fontsize{8bp}{10bp}\selectfont} +%% \def\footnotetextfont{\rmfamily\fontsize{8bp}{10bp}\selectfont} % \def\listfont{\normalsize}% @@ -3249,6 +3247,6 @@ \fi \fi% - \renewcommand\thefigure{\@Alph\c@section\arabic{figure}}% - \renewcommand\thetable{\@Alph\c@section\arabic{table}}% + \renewcommand\thefigure{\@Alph\c@section\arabic{figure}\enspace }% + \renewcommand\thetable{\@Alph\c@section\arabic{table}\enspace }% \renewcommand\theequation{\@Alph\c@section\arabic{equation}}% }{% Index: doc/papers/concurrency/Makefile =================================================================== --- doc/papers/concurrency/Makefile (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/concurrency/Makefile (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -75,17 +75,17 @@ mkdir -p ${Build} -${BASE}.out.ps: - ln -fs build/Paper.out.ps . +${BASE}.out.ps: ${Build} + ln -fs ${Build}/Paper.out.ps . WileyNJD-AMA.bst: ln -fs ../AMA/AMA-stix/ama/WileyNJD-AMA.bst . -%.tex : %.fig +%.tex : %.fig ${Build} fig2dev -L eepic $< > ${Build}/$@ -%.ps : %.fig +%.ps : %.fig ${Build} fig2dev -L ps $< > ${Build}/$@ -%.pstex : %.fig +%.pstex : %.fig ${Build} fig2dev -L pstex $< > ${Build}/$@ fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t Index: doc/papers/concurrency/Paper.tex =================================================================== --- doc/papers/concurrency/Paper.tex (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/concurrency/Paper.tex (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -22,5 +22,5 @@ \captionsetup{justification=raggedright,singlelinecheck=false} \usepackage{siunitx} -\sisetup{ binary-units=true } +\sisetup{binary-units=true} \hypersetup{breaklinks=true} @@ -32,5 +32,5 @@ \renewcommand{\linenumberfont}{\scriptsize\sffamily} -\renewcommand{\textfraction}{0.0} % the entire page maybe devoted to floats with no text on the page at all +\renewcommand{\textfraction}{0.0} % the entire page maybe devoted to floats with no text on the page at all \lefthyphenmin=3 % hyphen only after 4 characters @@ -70,4 +70,9 @@ %\DeclareTextCommandDefault{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}} \renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}} +%\def\myCHarFont{\fontencoding{T1}\selectfont}% +% \def\{{\ttfamily\upshape\myCHarFont \char`\}}}% + +\renewcommand*{\thefootnote}{\Alph{footnote}} % hack because fnsymbol does not work +%\renewcommand*{\thefootnote}{\fnsymbol{footnote}} \makeatletter @@ -85,4 +90,5 @@ \setlength{\gcolumnposn}{3.5in} \setlength{\columnposn}{\gcolumnposn} + \newcommand{\C}[2][\@empty]{\ifx#1\@empty\else\global\setlength{\columnposn}{#1}\global\columnposn=\columnposn\fi\hfill\makebox[\textwidth-\columnposn][l]{\lst@basicstyle{\LstCommentStyle{#2}}}} \newcommand{\CRT}{\global\columnposn=\gcolumnposn} @@ -170,5 +176,6 @@ literate={-}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptstyle\land\,$}}1 {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1 - {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex{\textgreater}}2, + {<}{\textrm{\textless}}1 {>}{\textrm{\textgreater}}1 + {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0.5ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex{\textrm{\textgreater}}}2, moredelim=**[is][\color{red}]{`}{`}, }% lstset @@ -212,4 +219,10 @@ \lstMakeShortInline@% +\let\OLDthebibliography\thebibliography +\renewcommand\thebibliography[1]{ + \OLDthebibliography{#1} + \setlength{\parskip}{0pt} + \setlength{\itemsep}{4pt plus 0.3ex} +} \title{\texorpdfstring{Concurrency in \protect\CFA}{Concurrency in Cforall}} @@ -228,5 +241,5 @@ \CFA is a modern, polymorphic, \emph{non-object-oriented} extension of the C programming language. This paper discusses the design of the concurrency and parallelism features in \CFA, and the concurrent runtime-system. -These features are created from scratch as ISO C lacks concurrency, relying largely on pthreads library. +These features are created from scratch as ISO C lacks concurrency, relying largely on the pthreads library. Coroutines and lightweight (user) threads are introduced into the language. In addition, monitors are added as a high-level mechanism for mutual exclusion and synchronization. @@ -244,9 +257,6 @@ \maketitle -% ====================================================================== -% ====================================================================== + \section{Introduction} -% ====================================================================== -% ====================================================================== This paper provides a minimal concurrency \newterm{Abstract Program Interface} (API) that is simple, efficient and can be used to build other concurrency features. @@ -254,234 +264,321 @@ An easier approach for programmers is to support higher-level constructs as the basis of concurrency. Indeed, for highly productive concurrent programming, high-level approaches are much more popular~\cite{Hochstein05}. -Examples of high-level approaches are task based~\cite{TBB}, message passing~\cite{Erlang,MPI}, and implicit threading~\cite{OpenMP}. - -This paper uses the following terminology. +Examples of high-level approaches are task (work) based~\cite{TBB}, implicit threading~\cite{OpenMP}, monitors~\cite{Java}, channels~\cite{CSP,Go}, and message passing~\cite{Erlang,MPI}. + +The following terminology is used. A \newterm{thread} is a fundamental unit of execution that runs a sequence of code and requires a stack to maintain state. Multiple simultaneous threads give rise to \newterm{concurrency}, which requires locking to ensure safe communication and access to shared data. % Correspondingly, concurrency is defined as the concepts and challenges that occur when multiple independent (sharing memory, timing dependencies, \etc) concurrent threads are introduced. -\newterm{Locking}, and by extension locks, are defined as a mechanism to prevent progress of threads to provide safety. +\newterm{Locking}, and by extension \newterm{locks}, are defined as a mechanism to prevent progress of threads to provide safety. \newterm{Parallelism} is running multiple threads simultaneously. Parallelism implies \emph{actual} simultaneous execution, where concurrency only requires \emph{apparent} simultaneous execution. -As such, parallelism only affects performance, which is observed through differences in space and/or time. - -Hence, there are two problems to be solved in the design of concurrency for a programming language: concurrency and parallelism. +As such, parallelism only affects performance, which is observed through differences in space and/or time at runtime. + +Hence, there are two problems to be solved: concurrency and parallelism. While these two concepts are often combined, they are distinct, requiring different tools~\cite[\S~2]{Buhr05a}. Concurrency tools handle synchronization and mutual exclusion, while parallelism tools handle performance, cost and resource utilization. The proposed concurrency API is implemented in a dialect of C, called \CFA. -The paper discusses how the language features are added to the \CFA translator with respect to parsing, semantic, and type checking, and the corresponding high-perforamnce runtime-library to implement the concurrency features. - -% ====================================================================== -% ====================================================================== +The paper discusses how the language features are added to the \CFA translator with respect to parsing, semantic, and type checking, and the corresponding high-performance runtime-library to implement the concurrency features. + + \section{\CFA Overview} -% ====================================================================== -% ====================================================================== The following is a quick introduction to the \CFA language, specifically tailored to the features needed to support concurrency. -Most of the following code examples can be found on the \CFA website~\cite{Cforall}. - -\CFA is an extension of ISO-C, and therefore, supports all of the same paradigms as C. +Extended versions and explanation of the following code examples are available at the \CFA website~\cite{Cforall} or in Moss~\etal~\cite{Moss18}. + +\CFA is an extension of ISO-C, and hence, supports all C paradigms. %It is a non-object-oriented system-language, meaning most of the major abstractions have either no runtime overhead or can be opted out easily. -Like C, the basics of \CFA revolve around structures and routines, which are thin abstractions over machine code. -The vast majority of the code produced by the \CFA translator respects memory layouts and calling conventions laid out by C. -Interestingly, while \CFA is not an object-oriented language, lacking the concept of a receiver (\eg @this@) and inheritance, it does have some notion of objects\footnote{C defines the term objects as : ``region of data storage in the execution environment, the contents of which can represent -values''~\cite[3.15]{C11}}, most importantly construction and destruction of objects. +Like C, the basics of \CFA revolve around structures and functions. +Virtually all of the code generated by the \CFA translator respects C memory layouts and calling conventions. +While \CFA is not an object-oriented language, lacking the concept of a receiver (\eg @this@) and nominal inheritance-relationships, C does have a notion of objects: ``region of data storage in the execution environment, the contents of which can represent values''~\cite[3.15]{C11}. +While some \CFA features are common in object-oriented programming-languages, they are an independent capability allowing \CFA to adopt them while retaining a procedural paradigm. \subsection{References} -Like \CC, \CFA introduces rebind-able references providing multiple dereferencing as an alternative to pointers. -In regards to concurrency, the semantic difference between pointers and references are not particularly relevant, but since this document uses mostly references, here is a quick overview of the semantics: -\begin{cfa} -int x, y, z; -int * p1 = &x, ** p2 = &p1, *** p3 = &p2, $\C{// pointers to x}$ - & r1 = x, && r2 = r1, &&& r3 = r2; $\C{// references to x}$ - -*p1 = 3; **p2 = 3; ***p3 = 3; $\C{// change x}$ - r1 = 3; r2 = 3; r3 = 3; $\C{// change x}$ -**p3 = &y; *p3 = &z; $\C{// change p1, p2}$ -&&r3 = &y; &r3 = &z; $\C{// change p1, p2}$ -int & ar[3] = {x, y, z}; $\C{// initialize array of references}$ - -typeof( ar[1]) p; $\C{// is int, referenced object type}$ -typeof(&ar[1]) q; $\C{// is int \&, reference type}$ -sizeof( ar[1]) == sizeof(int); $\C{// is true, referenced object size}$ -sizeof(&ar[1]) == sizeof(int *); $\C{// is true, reference size}$ -\end{cfa} -The important take away from this code example is that a reference offers a handle to an object, much like a pointer, but which is automatically dereferenced for convenience. - -% ====================================================================== +\CFA provides multi-level rebindable references, as an alternative to pointers, which significantly reduces syntactic noise. +\begin{cfa} +int x = 1, y = 2, z = 3; +int * p1 = &x, ** p2 = &p1, *** p3 = &p2, $\C{// pointers to x}$ + `&` r1 = x, `&&` r2 = r1, `&&&` r3 = r2; $\C{// references to x}$ +int * p4 = &z, `&` r4 = z; + +*p1 = 3; **p2 = 3; ***p3 = 3; // change x +r1 = 3; r2 = 3; r3 = 3; // change x: implicit dereferences *r1, **r2, ***r3 +**p3 = &y; *p3 = &p4; // change p1, p2 +`&`r3 = &y; `&&`r3 = &`&`r4; // change r1, r2: cancel implicit dereferences (&*)**r3, (&(&*)*)*r3, &(&*)r4 +\end{cfa} +A reference is a handle to an object, like a pointer, but is automatically dereferenced the specified number of levels. +Referencing (address-of @&@) a reference variable cancels one of the implicit dereferences, until there are no more implicit references, after which normal expression behaviour applies. + + +\subsection{\texorpdfstring{\protect\lstinline{with} Statement}{with Statement}} +\label{s:WithStatement} + +Heterogeneous data is aggregated into a structure/union. +To reduce syntactic noise, \CFA provides a @with@ statement (see Pascal~\cite[\S~4.F]{Pascal}) to elide aggregate field-qualification by opening a scope containing the field identifiers. +\begin{cquote} +\vspace*{-\baselineskip}%??? +\lstDeleteShortInline@% +\begin{cfa} +struct S { char c; int i; double d; }; +struct T { double m, n; }; +// multiple aggregate parameters +\end{cfa} +\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}|@{\hspace{2\parindentlnth}}l@{}} +\begin{cfa} +void f( S & s, T & t ) { + `s.`c; `s.`i; `s.`d; + `t.`m; `t.`n; +} +\end{cfa} +& +\begin{cfa} +void f( S & s, T & t ) `with ( s, t )` { + c; i; d; // no qualification + m; n; +} +\end{cfa} +\end{tabular} +\lstMakeShortInline@% +\end{cquote} +Object-oriented programming languages only provide implicit qualification for the receiver. + +In detail, the @with@ statement has the form: +\begin{cfa} +$\emph{with-statement}$: + 'with' '(' $\emph{expression-list}$ ')' $\emph{compound-statement}$ +\end{cfa} +and may appear as the body of a function or nested within a function body. +Each expression in the expression-list provides a type and object. +The type must be an aggregate type. +(Enumerations are already opened.) +The object is the implicit qualifier for the open structure-fields. +All expressions in the expression list are open in parallel within the compound statement, which is different from Pascal, which nests the openings from left to right. + + \subsection{Overloading} -Another important feature of \CFA is function overloading as in Java and \CC, where routines with the same name are selected based on the number and type of the arguments. -As well, \CFA uses the return type as part of the selection criteria, as in Ada~\cite{Ada}. -For routines with multiple parameters and returns, the selection is complex. +\CFA maximizes the ability to reuse names via overloading to aggressively address the naming problem. +Both variables and functions may be overloaded, where selection is based on types, and number of returns (as in Ada~\cite{Ada}) and arguments. +\begin{cquote} +\vspace*{-\baselineskip}%??? +\lstDeleteShortInline@% +\begin{cfa} +// selection based on type +\end{cfa} +\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}|@{\hspace{2\parindentlnth}}l@{}} +\begin{cfa} +const short int `MIN` = -32768; +const int `MIN` = -2147483648; +const long int `MIN` = -9223372036854775808L; +\end{cfa} +& +\begin{cfa} +short int si = `MIN`; +int i = `MIN`; +long int li = `MIN`; +\end{cfa} +\end{tabular} \begin{cfa} // selection based on type and number of parameters -void f(void); $\C{// (1)}$ -void f(char); $\C{// (2)}$ -void f(int, double); $\C{// (3)}$ -f(); $\C{// select (1)}$ -f('a'); $\C{// select (2)}$ -f(3, 5.2); $\C{// select (3)}$ - -// selection based on type and number of returns -char f(int); $\C{// (1)}$ -double f(int); $\C{// (2)}$ -char c = f(3); $\C{// select (1)}$ -double d = f(4); $\C{// select (2)}$ -\end{cfa} -This feature is particularly important for concurrency since the runtime system relies on creating different types to represent concurrency objects. -Therefore, overloading is necessary to prevent the need for long prefixes and other naming conventions that prevent name clashes. -As seen in section \ref{basics}, routine @main@ is an example that benefits from overloading. - -% ====================================================================== +\end{cfa} +\begin{tabular}{@{}l@{\hspace{2.7\parindentlnth}}|@{\hspace{2\parindentlnth}}l@{}} +\begin{cfa} +void `f`( void ); +void `f`( char ); +void `f`( int, double ); +\end{cfa} +& +\begin{cfa} +`f`(); +`f`( 'a' ); +`f`( 3, 5.2 ); +\end{cfa} +\end{tabular} +\begin{cfa} +// selection based on type and number of returns +\end{cfa} +\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}|@{\hspace{2\parindentlnth}}l@{}} +\begin{cfa} +char `f`( int ); +double `f`( int ); +[char, double] `f`( int ); +\end{cfa} +& +\begin{cfa} +char c = `f`( 3 ); +double d = `f`( 3 ); +[d, c] = `f`( 3 ); +\end{cfa} +\end{tabular} +\lstMakeShortInline@% +\end{cquote} +Overloading is important for \CFA concurrency since the runtime system relies on creating different types to represent concurrency objects. +Therefore, overloading is necessary to prevent the need for long prefixes and other naming conventions to prevent name clashes. +As seen in Section~\ref{basics}, function @main@ is heavily overloaded. + +Variable overloading is useful in the parallel semantics of the @with@ statement for fields with the same name: +\begin{cfa} +struct S { int `i`; int j; double m; } s; +struct T { int `i`; int k; int m; } t; +with ( s, t ) { + j + k; $\C{// unambiguous, s.j + t.k}$ + m = 5.0; $\C{// unambiguous, s.m = 5.0}$ + m = 1; $\C{// unambiguous, t.m = 1}$ + int a = m; $\C{// unambiguous, a = t.m }$ + double b = m; $\C{// unambiguous, b = s.m}$ + int c = `s.i` + `t.i`; $\C{// unambiguous, qualification}$ + (double)m; $\C{// unambiguous, cast s.m}$ +} +\end{cfa} +For parallel semantics, both @s.i@ and @t.i@ are visible the same type, so only @i@ is ambiguous without qualification. + + \subsection{Operators} + Overloading also extends to operators. -The syntax for denoting operator-overloading is to name a routine with the symbol of the operator and question marks where the arguments of the operation appear, \eg: -\begin{cfa} -int ++? (int op); $\C{// unary prefix increment}$ -int ?++ (int op); $\C{// unary postfix increment}$ -int ?+? (int op1, int op2); $\C{// binary plus}$ -int ?<=?(int op1, int op2); $\C{// binary less than}$ -int ?=? (int & op1, int op2); $\C{// binary assignment}$ -int ?+=?(int & op1, int op2); $\C{// binary plus-assignment}$ - -struct S {int i, j;}; -S ?+?(S op1, S op2) { $\C{// add two structures}$ +Operator-overloading syntax names a routine with the operator symbol and question marks for the operands: +\begin{cquote} +\lstDeleteShortInline@% +\begin{tabular}{@{}ll@{\hspace{\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}} +\begin{cfa} +int ++? (int op); +int ?++ (int op); +int `?+?` (int op1, int op2); +int ?<=?(int op1, int op2); +int ?=? (int & op1, int op2); +int ?+=?(int & op1, int op2); +\end{cfa} +& +\begin{cfa} +// unary prefix increment +// unary postfix increment +// binary plus +// binary less than +// binary assignment +// binary plus-assignment +\end{cfa} +& +\begin{cfa} +struct S { int i, j; }; +S `?+?`( S op1, S op2) { // add two structures return (S){op1.i + op2.i, op1.j + op2.j}; } S s1 = {1, 2}, s2 = {2, 3}, s3; -s3 = s1 + s2; $\C{// compute sum: s3 == {2, 5}}$ -\end{cfa} -While concurrency does not use operator overloading directly, this feature is more important as an introduction for the syntax of constructors. - -% ====================================================================== -\subsection{Constructors/Destructors} -Object lifetime is often a challenge in concurrency. \CFA uses the approach of giving concurrent meaning to object lifetime as a means of synchronization and/or mutual exclusion. -Since \CFA relies heavily on the lifetime of objects, constructors and destructors is a core feature required for concurrency and parallelism. \CFA uses the following syntax for constructors and destructors: -\begin{cfa} -struct S { - size_t size; - int * ia; -}; -void ?{}(S & s, int asize) { $\C{// constructor operator}$ - s.size = asize; $\C{// initialize fields}$ - s.ia = calloc(size, sizeof(S)); -} -void ^?{}(S & s) { $\C{// destructor operator}$ - free(ia); $\C{// de-initialization fields}$ -} -int main() { - S x = {10}, y = {100}; $\C{// implicit calls: ?\{\}(x, 10), ?\{\}(y, 100)}$ - ... $\C{// use x and y}$ - ^x{}; ^y{}; $\C{// explicit calls to de-initialize}$ - x{20}; y{200}; $\C{// explicit calls to reinitialize}$ - ... $\C{// reuse x and y}$ -} $\C{// implicit calls: \^?\{\}(y), \^?\{\}(x)}$ -\end{cfa} -The language guarantees that every object and all their fields are constructed. -Like \CC, construction of an object is automatically done on allocation and destruction of the object is done on deallocation. -Allocation and deallocation can occur on the stack or on the heap. -\begin{cfa} -{ - struct S s = {10}; $\C{// allocation, call constructor}$ - ... -} $\C{// deallocation, call destructor}$ -struct S * s = new(); $\C{// allocation, call constructor}$ -... -delete(s); $\C{// deallocation, call destructor}$ -\end{cfa} -Note that like \CC, \CFA introduces @new@ and @delete@, which behave like @malloc@ and @free@ in addition to constructing and destructing objects, after calling @malloc@ and before calling @free@, respectively. - -% ====================================================================== +s3 = s1 `+` s2; // compute sum: s3 == {2, 5} +\end{cfa} +\end{tabular} +\lstMakeShortInline@% +\end{cquote} +While concurrency does not use operator overloading directly, it provides an introduction for the syntax of constructors. + + \subsection{Parametric Polymorphism} \label{s:ParametricPolymorphism} -Routines in \CFA can also be reused for multiple types. -This capability is done using the @forall@ clauses, which allow separately compiled routines to support generic usage over multiple types. + +The signature feature of \CFA is parametric-polymorphic functions~\cite{} with functions generalized using a @forall@ clause (giving the language its name), which allow separately compiled routines to support generic usage over multiple types. For example, the following sum function works for any type that supports construction from 0 and addition: \begin{cfa} -// constraint type, 0 and + -forall(otype T | { void ?{}(T *, zero_t); T ?+?(T, T); }) -T sum(T a[ ], size_t size) { - T total = 0; $\C{// construct T from 0}$ - for(size_t i = 0; i < size; i++) - total = total + a[i]; $\C{// select appropriate +}$ +forall( otype T | { void `?{}`( T *, zero_t ); T `?+?`( T, T ); } ) // constraint type, 0 and + +T sum( T a[$\,$], size_t size ) { + `T` total = { `0` }; $\C{// initialize by 0 constructor}$ + for ( size_t i = 0; i < size; i += 1 ) + total = total `+` a[i]; $\C{// select appropriate +}$ return total; } - S sa[5]; -int i = sum(sa, 5); $\C{// use S's 0 construction and +}$ -\end{cfa} - -Since writing constraints on types can become cumbersome for more constrained functions, \CFA also has the concept of traits. -Traits are named collection of constraints that can be used both instead and in addition to regular constraints: -\begin{cfa} -trait summable( otype T ) { - void ?{}(T *, zero_t); $\C{// constructor from 0 literal}$ - T ?+?(T, T); $\C{// assortment of additions}$ - T ?+=?(T *, T); - T ++?(T *); - T ?++(T *); +int i = sum( sa, 5 ); $\C{// use S's 0 construction and +}$ +\end{cfa} + +\CFA provides \newterm{traits} to name a group of type assertions, where the trait name allows specifying the same set of assertions in multiple locations, preventing repetition mistakes at each function declaration: +\begin{cfa} +trait `sumable`( otype T ) { + void `?{}`( T &, zero_t ); $\C{// 0 literal constructor}$ + T `?+?`( T, T ); $\C{// assortment of additions}$ + T ?+=?( T &, T ); + T ++?( T & ); + T ?++( T & ); }; -forall( otype T | summable(T) ) $\C{// use trait}$ -T sum(T a[], size_t size); -\end{cfa} - -Note that the type use for assertions can be either an @otype@ or a @dtype@. -Types declared as @otype@ refer to ``complete'' objects, \ie objects with a size, a default constructor, a copy constructor, a destructor and an assignment operator. -Using @dtype@, on the other hand, has none of these assumptions but is extremely restrictive, it only guarantees the object is addressable. - -% ====================================================================== -\subsection{with Clause/Statement} -Since \CFA lacks the concept of a receiver, certain functions end up needing to repeat variable names often. -To remove this inconvenience, \CFA provides the @with@ statement, which opens an aggregate scope making its fields directly accessible (like Pascal). -\begin{cfa} -struct S { int i, j; }; -int mem(S & this) with (this) $\C{// with clause}$ - i = 1; $\C{// this->i}$ - j = 2; $\C{// this->j}$ -} -int foo() { - struct S1 { ... } s1; - struct S2 { ... } s2; - with (s1) $\C{// with statement}$ - { - // access fields of s1 without qualification - with (s2) $\C{// nesting}$ - { - // access fields of s1 and s2 without qualification - } - } - with (s1, s2) $\C{// scopes open in parallel}$ - { - // access fields of s1 and s2 without qualification - } -} -\end{cfa} - -For more information on \CFA see \cite{cforall-ug,Schluntz17,www-cfa}. - -% ====================================================================== -% ====================================================================== +forall( otype T `| sumable( T )` ) $\C{// use trait}$ +T sum( T a[$\,$], size_t size ); +\end{cfa} + +Assertions can be @otype@ or @dtype@. +@otype@ refers to a ``complete'' object, \ie an object has a size, default constructor, copy constructor, destructor and an assignment operator. +@dtype@ only guarantees an object has a size and alignment. + +Using the return type for discrimination, it is possible to write a type-safe @alloc@ based on the C @malloc@: +\begin{cfa} +forall( dtype T | sized(T) ) T * alloc( void ) { return (T *)malloc( sizeof(T) ); } +int * ip = alloc(); $\C{// select type and size from left-hand side}$ +double * dp = alloc(); +struct S {...} * sp = alloc(); +\end{cfa} +where the return type supplies the type/size of the allocation, which is impossible in most type systems. + + +\subsection{Constructors / Destructors} + +Object lifetime is a challenge in non-managed programming languages. +\CFA responds with \CC-like constructors and destructors: +\begin{cfa} +struct VLA { int len, * data; }; $\C{// variable length array of integers}$ +void ?{}( VLA & vla ) with ( vla ) { len = 10; data = alloc( len ); } $\C{// default constructor}$ +void ?{}( VLA & vla, int size, char fill ) with ( vla ) { len = size; data = alloc( len, fill ); } // initialization +void ?{}( VLA & vla, VLA other ) { vla.len = other.len; vla.data = other.data; } $\C{// copy, shallow}$ +void ^?{}( VLA & vla ) with ( vla ) { free( data ); } $\C{// destructor}$ +{ + VLA x, y = { 20, 0x01 }, z = y; $\C{// z points to y}$ + // x{}; y{ 20, 0x01 }; z{ z, y }; + ^x{}; $\C{// deallocate x}$ + x{}; $\C{// reallocate x}$ + z{ 5, 0xff }; $\C{// reallocate z, not pointing to y}$ + ^y{}; $\C{// deallocate y}$ + y{ x }; $\C{// reallocate y, points to x}$ + x{}; $\C{// reallocate x, not pointing to y}$ + // ^z{}; ^y{}; ^x{}; +} +\end{cfa} +Like \CC, construction is implicit on allocation (stack/heap) and destruction is implicit on deallocation. +The object and all their fields are constructed/destructed. +\CFA also provides @new@ and @delete@, which behave like @malloc@ and @free@, in addition to constructing and destructing objects: +\begin{cfa} +{ struct S s = {10}; $\C{// allocation, call constructor}$ + ... +} $\C{// deallocation, call destructor}$ +struct S * s = new(); $\C{// allocation, call constructor}$ +... +delete( s ); $\C{// deallocation, call destructor}$ +\end{cfa} +\CFA concurrency uses object lifetime as a means of synchronization and/or mutual exclusion. + + \section{Concurrency Basics}\label{basics} -% ====================================================================== -% ====================================================================== - -At its core, concurrency is based on having multiple call-stacks and scheduling among threads of execution executing on these stacks. -Multiple call stacks (or contexts) and a single thread of execution does \emph{not} imply concurrency. -Execution with a single thread and multiple stacks where the thread is deterministically self-scheduling across the stacks is called \newterm{coroutining}; -execution with a single thread and multiple stacks but where the thread is scheduled by an oracle (non-deterministic from the thread's perspective) across the stacks is called concurrency~\cite[\S~3]{Buhr05a}. -Therefore, a minimal concurrency system can be achieved using coroutines (see Section \ref{coroutine}), which instead of context-switching among each other, always defer to an oracle for where to context-switch next. - -While coroutines can execute on the caller's stack-frame, stack-full coroutines allow full generality and are sufficient as the basis for concurrency. -The aforementioned oracle is a scheduler and the whole system now follows a cooperative threading-model (a.k.a., non-preemptive scheduling). -The oracle/scheduler can either be a stack-less or stack-full entity and correspondingly require one or two context-switches to run a different coroutine. -In any case, a subset of concurrency related challenges start to appear. -For the complete set of concurrency challenges to occur, the only feature missing is preemption. - -A scheduler introduces order of execution uncertainty, while preemption introduces uncertainty about where context switches occur. -Mutual exclusion and synchronization are ways of limiting non-determinism in a concurrent system. -Now it is important to understand that uncertainty is desirable; uncertainty can be used by runtime systems to significantly increase performance and is often the basis of giving a user the illusion that tasks are running in parallel. + +At its core, concurrency is based on multiple call-stacks and scheduling threads executing on these stacks. +Multiple call stacks (or contexts) and a single thread of execution, called \newterm{coroutining}~\cite{Conway63,Marlin80}, does \emph{not} imply concurrency~\cite[\S~2]{Buhr05a}. +In coroutining, the single thread is self-scheduling across the stacks, so execution is deterministic, \ie given fixed inputs, the execution path to the outputs is fixed and predictable. +A \newterm{stackless} coroutine executes on the caller's stack~\cite{Python} but this approach is restrictive, \eg preventing modularization and supporting only iterator/generator-style programming; +a \newterm{stackfull} coroutine executes on its own stack, allowing full generality. +Only stackfull coroutines are a stepping-stone to concurrency. + +The transition to concurrency, even for execution with a single thread and multiple stacks, occurs when coroutines also context switch to a scheduling oracle, introducing non-determinism from the coroutine perspective~\cite[\S~3]{Buhr05a}. +Therefore, a minimal concurrency system is possible using coroutines (see Section \ref{coroutine}) in conjunction with a scheduler to decide where to context switch next. +The resulting execution system now follows a cooperative threading-model, called \newterm{non-preemptive scheduling}. + +Because the scheduler is special, it can either be a stackless or stackfull coroutine. +For stackless, the scheduler performs scheduling on the stack of the current coroutine and switches directly to the next coroutine, so there is one context switch. +For stackfull, the current coroutine switches to the scheduler, which performs scheduling, and it then switches to the next coroutine, so there are two context switches. +A stackfull scheduler is often used for simplicity and security, even through there is a slightly higher runtime-cost. + +Regardless of the approach used, a subset of concurrency related challenges start to appear. +For the complete set of concurrency challenges to occur, the missing feature is \newterm{preemption}, where context switching occurs randomly between any two instructions, often based on a timer interrupt, called \newterm{preemptive scheduling}. +While a scheduler introduces uncertainty in the order of execution, preemption introduces uncertainty where context switches occur. +Interestingly, uncertainty is necessary for the runtime (operating) system to give the illusion of parallelism on a single processor and increase performance on multiple processors. +The reason is that only the runtime has complete knowledge about resources and how to best utilized them. +However, the introduction of unrestricted non-determinism results in the need for \newterm{mutual exclusion} and \newterm{synchronization} to restrict non-determinism for correctness; +otherwise, it is impossible to write meaningful programs. Optimal performance in concurrent applications is often obtained by having as much non-determinism as correctness allows. @@ -489,41 +586,40 @@ \subsection{\protect\CFA's Thread Building Blocks} -One of the important features that are missing in C is threading\footnote{While the C11 standard defines a ``threads.h'' header, it is minimal and defined as optional. +An important missing feature in C is threading\footnote{While the C11 standard defines a ``threads.h'' header, it is minimal and defined as optional. As such, library support for threading is far from widespread. At the time of writing the paper, neither \protect\lstinline|gcc| nor \protect\lstinline|clang| support ``threads.h'' in their standard libraries.}. -On modern architectures, a lack of threading is unacceptable~\cite{Sutter05, Sutter05b}, and therefore modern programming languages must have the proper tools to allow users to write efficient concurrent programs to take advantage of parallelism. +On modern architectures, a lack of threading is unacceptable~\cite{Sutter05, Sutter05b}, and therefore existing and new programming languages must have tools for writing efficient concurrent programs to take advantage of parallelism. As an extension of C, \CFA needs to express these concepts in a way that is as natural as possible to programmers familiar with imperative languages. -And being a system-level language means programmers expect to choose precisely which features they need and which cost they are willing to pay. +Furthermore, because C is a system-level language, programmers expect to choose precisely which features they need and which cost they are willing to pay. +Hence, concurrent programs should be written using high-level mechanisms, and only step down to lower-level mechanisms when performance bottlenecks are encountered. \subsection{Coroutines: A Stepping Stone}\label{coroutine} -While the focus of this proposal is concurrency and parallelism, it is important to address coroutines, which are a significant building block of a concurrency system. -\newterm{Coroutine}s are generalized routines with points where execution is suspended and resumed at a later time. -Suspend/resume is a context switche and coroutines have other context-management operations. -Many design challenges of threads are partially present in designing coroutines, which makes the design effort relevant. -The core \textbf{api} of coroutines has two features: independent call-stacks and @suspend@/@resume@. - -A coroutine handles the class of problems that need to retain state between calls (\eg plugin, device driver, finite-state machine). -For example, a problem made easier with coroutines is unbounded generators, \eg generating an infinite sequence of Fibonacci numbers: +While the focus of this discussion is concurrency and parallelism, it is important to address coroutines, which are a significant building block of a concurrency system. +Coroutines are generalized routines allowing execution to be temporarily suspend and later resumed. +Hence, unlike a normal routine, a coroutine may not terminate when it returns to its caller, allowing it to be restarted with the values and execution location present at the point of suspension. +This capability is accomplish via the coroutine's stack, where suspend/resume context switch among stacks. +Because threading design-challenges are present in coroutines, their design effort is relevant, and this effort can be easily exposed to programmers giving them a useful new programming paradigm because a coroutine handles the class of problems that need to retain state between calls, \eg plugins, device drivers, and finite-state machines. +Therefore, the core \CFA coroutine-API for has two fundamental features: independent call-stacks and @suspend@/@resume@ operations. + +For example, a problem made easier with coroutines is unbounded generators, \eg generating an infinite sequence of Fibonacci numbers, where Figure~\ref{f:C-fibonacci} shows conventional approaches for writing a Fibonacci generator in C. \begin{displaymath} -f(n) = \left \{ +\mathsf{fib}(n) = \left \{ \begin{array}{ll} -0 & n = 0 \\ -1 & n = 1 \\ -f(n-1) + f(n-2) & n \ge 2 \\ +0 & n = 0 \\ +1 & n = 1 \\ +\mathsf{fib}(n-1) + \mathsf{fib}(n-2) & n \ge 2 \\ \end{array} \right. \end{displaymath} -Figure~\ref{f:C-fibonacci} shows conventional approaches for writing a Fibonacci generator in C. - Figure~\ref{f:GlobalVariables} illustrates the following problems: -unencapsulated global variables necessary to retain state between calls; -only one fibonacci generator can run at a time; -execution state must be explicitly retained. +unique unencapsulated global variables necessary to retain state between calls; +only one Fibonacci generator; +execution state must be explicitly retained via explicit state variables. Figure~\ref{f:ExternalState} addresses these issues: unencapsulated program global variables become encapsulated structure variables; -multiple fibonacci generators can run at a time by declaring multiple fibonacci objects; -explicit execution state is removed by precomputing the first two Fibonacci numbers and returning $f(n-2)$. +unique global variables are replaced by multiple Fibonacci objects; +explicit execution state is removed by precomputing the first two Fibonacci numbers and returning $\mathsf{fib}(n-2)$. \begin{figure} @@ -585,5 +681,5 @@ \begin{lstlisting}[aboveskip=0pt,belowskip=0pt] `coroutine` Fib { int fn; }; -void main( Fib & f ) with( f ) { +void main( Fib & fib ) with( fib ) { int f1, f2; fn = 0; f1 = fn; `suspend()`; @@ -609,5 +705,5 @@ \begin{lstlisting}[aboveskip=0pt,belowskip=0pt] `coroutine` Fib { int ret; }; -void main( Fib & f ) with( f ) { +void main( Fib & f ) with( fib ) { int fn, f1 = 1, f2 = 0; for ( ;; ) { @@ -636,65 +732,130 @@ \end{figure} -Figure~\ref{f:Coroutine3States} creates a @coroutine@ type, which provides communication for multiple interface functions, and the \newterm{coroutine main}, which runs on the coroutine stack. -\begin{cfa} -`coroutine C { char c; int i; _Bool s; };` $\C{// used for communication}$ -void ?{}( C & c ) { s = false; } $\C{// constructor}$ -void main( C & cor ) with( cor ) { $\C{// actual coroutine}$ - while ( ! s ) // process c - if ( v == ... ) s = false; -} -// interface functions -char cont( C & cor, char ch ) { c = ch; resume( cor ); return c; } -_Bool stop( C & cor, int v ) { s = true; i = v; resume( cor ); return s; } -\end{cfa} - -encapsulates the Fibonacci state in the shows is an example of a solution to the Fibonacci problem using \CFA coroutines, where the coroutine stack holds sufficient state for the next generation. -This solution has the advantage of having very strong decoupling between how the sequence is generated and how it is used. -Indeed, this version is as easy to use as the @fibonacci_state@ solution, while the implementation is very similar to the @fibonacci_func@ example. - -Figure~\ref{f:fmt-line} shows the @Format@ coroutine for restructuring text into groups of character blocks of fixed size. -The example takes advantage of resuming coroutines in the constructor to simplify the code and highlights the idea that interesting control flow can occur in the constructor. +Using a coroutine, it is possible to express the Fibonacci formula directly without any of the C problems. +Figure~\ref{f:Coroutine3States} creates a @coroutine@ type: +\begin{cfa} +`coroutine` Fib { int fn; }; +\end{cfa} +which provides communication, @fn@, for the \newterm{coroutine main}, @main@, which runs on the coroutine stack, and possibly multiple interface functions, @next@. +Like the structure in Figure~\ref{f:ExternalState}, the coroutine type allows multiple instances, where instances of this type are passed to the (overloaded) coroutine main. +The coroutine main's stack holds the state for the next generation, @f1@ and @f2@, and the code has the three suspend points, representing the three states in the Fibonacci formula, to context switch back to the caller's resume. +The interface function, @next@, takes a Fibonacci instance and context switches to it using @resume@; +on return, the Fibonacci field, @fn@, contains the next value in the sequence, which is returned. +The first @resume@ is special because it cocalls the coroutine at its coroutine main and allocates the stack; +when the coroutine main returns, its stack is deallocated. +Hence, @Fib@ is an object at creation, transitions to a coroutine on its first resume, and transitions back to an object when the coroutine main finishes. +Figure~\ref{f:Coroutine1State} shows the coroutine version of the C version in Figure~\ref{f:ExternalState}. +Coroutine generators are called \newterm{output coroutines} because values are returned by the coroutine. + +Figure~\ref{f:CFAFmt} shows an \newterm{input coroutine}, @Format@, for restructuring text into groups of character blocks of fixed size. +For example, the input of the left is reformatted into the output on the right. +\begin{quote} +\tt +\begin{tabular}{@{}l|l@{}} +\multicolumn{1}{c|}{\textbf{\textrm{input}}} & \multicolumn{1}{c}{\textbf{\textrm{output}}} \\ +abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz +& +\begin{tabular}[t]{@{}lllll@{}} +abcd & efgh & ijkl & mnop & qrst \\ +uvwx & yzab & cdef & ghij & klmn \\ +opqr & stuv & wxyz & & +\end{tabular} +\end{tabular} +\end{quote} +The example takes advantage of resuming coroutines in the constructor to prime the coroutine loops so the first character sent for formatting appears inside the nested loops. +The destruction provides a newline if formatted text ends with a full line. +Figure~\ref{f:CFmt} shows the C equivalent formatter, where the loops of the coroutine are flatten (linearized) and rechecked on each call because execution location is not retained between calls. \begin{figure} -\begin{cfa}[xleftmargin=4\parindentlnth] +\centering +\newbox\myboxA +\begin{lrbox}{\myboxA} +\begin{lstlisting}[aboveskip=0pt,belowskip=0pt] `coroutine` Format { - char ch; $\C{// used for communication}$ - int g, b; $\C{// global because used in destructor}$ + char ch; // used for communication + int g, b; // global because used in destructor }; -void ?{}( Format & fmt ) { `resume( fmt );` } $\C{// prime (start) coroutine}$ -void ^?{}( Format & fmt ) with( fmt ) { if ( g != 0 || b != 0 ) sout | endl; } void main( Format & fmt ) with( fmt ) { - for ( ;; ) { $\C{// for as many characters}$ - for ( g = 0; g < 5; g += 1 ) { $\C{// groups of 5 blocks}$ - for ( b = 0; b < 4; b += 1 ) { $\C{// blocks of 4 characters}$ + for ( ;; ) { + for ( g = 0; g < 5; g += 1 ) { // group + for ( b = 0; b < 4; b += 1 ) { // block `suspend();` - sout | ch; $\C{// print character}$ + sout | ch; // separator } - sout | " "; $\C{// print block separator}$ + sout | " "; // separator } - sout | endl; $\C{// print group separator}$ + sout | endl; } } -void prt( Format & fmt, char ch ) { - fmt.ch = ch; +void ?{}( Format & fmt ) { `resume( fmt );` } +void ^?{}( Format & fmt ) with( fmt ) { + if ( g != 0 || b != 0 ) sout | endl; +} +void format( Format & fmt ) { `resume( fmt );` } int main() { Format fmt; + eof: for ( ;; ) { + sin | fmt.ch; + if ( eof( sin ) ) break eof; + format( fmt ); + } +} +\end{lstlisting} +\end{lrbox} + +\newbox\myboxB +\begin{lrbox}{\myboxB} +\begin{lstlisting}[aboveskip=0pt,belowskip=0pt] +struct Format { char ch; - for ( ;; ) { $\C{// read until end of file}$ - sin | ch; $\C{// read one character}$ - if ( eof( sin ) ) break; $\C{// eof ?}$ - prt( fmt, ch ); $\C{// push character for formatting}$ + int g, b; +}; +void format( struct Format * fmt ) { + if ( fmt->ch != -1 ) { // not EOF + printf( "%c", fmt->ch ); + fmt->b += 1; + if ( fmt->b == 4 ) { // block + printf( " " ); // separator + fmt->b = 0; + fmt->g += 1; + } + if ( fmt->g == 5 ) { // group + printf( "\n" ); // separator + fmt->g = 0; + } + } else { + if ( fmt->g != 0 || fmt->b != 0 ) printf( "\n" ); } } -\end{cfa} +int main() { + struct Format fmt = { 0, 0, 0 }; + for ( ;; ) { + scanf( "%c", &fmt.ch ); + if ( feof( stdin ) ) break; + format( &fmt ); + } + fmt.ch = -1; + format( &fmt ); +} +\end{lstlisting} +\end{lrbox} +\subfloat[\CFA Coroutine]{\label{f:CFAFmt}\usebox\myboxA} +\qquad +\subfloat[C Linearized]{\label{f:CFmt}\usebox\myboxB} \caption{Formatting text into lines of 5 blocks of 4 characters.} \label{f:fmt-line} \end{figure} +The previous examples are \newterm{asymmetric (semi) coroutine}s because one coroutine always calls a resuming function for another coroutine, and the resumed coroutine always suspends back to its last resumer, similar to call/return for normal functions. +However, there is no stack growth because @resume@/@suspend@ context switch to an existing stack frames rather than create a new one. +\newterm{Symmetric (full) coroutine}s have a coroutine call a resuming function for another coroutine, which eventually forms a cycle. +(The trivial cycle is a coroutine resuming itself.) +This control flow is similar to recursion for normal routines, but again there is no stack growth from the context switch. + \begin{figure} \centering -\lstset{language=CFA,escapechar={},moredelim=**[is][\protect\color{red}]{`}{`}} +\lstset{language=CFA,escapechar={},moredelim=**[is][\protect\color{red}]{`}{`}}% allow $ \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} \begin{cfa} @@ -728,5 +889,4 @@ Prod prod; Cons cons = { prod }; - srandom( getpid() ); start( prod, 5, cons ); } @@ -765,5 +925,4 @@ `resume( cons );` } - \end{cfa} \end{tabular} @@ -771,4 +930,31 @@ \label{f:ProdCons} \end{figure} + +Figure~\ref{f:ProdCons} shows a producer/consumer symmetric-coroutine performing bi-directional communication. +Since the solution involves a full-coroutining cycle, the program main creates one coroutine in isolation, passes this coroutine to its partner, and closes the cycle at the call to @start@. +The @start@ function communicates both the number of elements to be produced and the consumer into the producer's coroutine structure. +Then the @resume@ to @prod@ creates @prod@'s stack with a frame for @prod@'s coroutine main at the top, and context switches to it. +@prod@'s coroutine main starts, creates local variables that are retained between coroutine activations, and executes $N$ iterations, each generating two random vales, calling the consumer to deliver the values, and printing the status returned from the consumer. + +The producer call to @delivery@ transfers values into the consumer's communication variables, resumes the consumer, and returns the consumer status. +For the first resume, @cons@'s stack is initialized, creating local variables retained between subsequent activations of the coroutine. +The consumer iterates until the @done@ flag is set, prints, increments status, and calls back to the producer's @payment@ member, and on return prints the receipt from the producer and increments the money for the next payment. +The call from the consumer to the producer's @payment@ member introduces the cycle between producer and consumer. +When @payment@ is called, the consumer copies values into the producer's communication variable and a resume is executed. +The context switch restarts the producer at the point where it was last context switched and it continues in member @delivery@ after the resume. + +The @delivery@ member returns the status value in @prod@'s @main@ member, where the status is printed. +The loop then repeats calling @delivery@, where each call resumes the consumer coroutine. +The context switch to the consumer continues in @payment@. +The consumer increments and returns the receipt to the call in @cons@'s @main@ member. +The loop then repeats calling @payment@, where each call resumes the producer coroutine. + +After iterating $N$ times, the producer calls @stop@. +The @done@ flag is set to stop the consumer's execution and a resume is executed. +The context switch restarts @cons@ in @payment@ and it returns with the last receipt. +The consumer terminates its loops because @done@ is true, its @main@ terminates, so @cons@ transitions from a coroutine back to an object, and @prod@ reactivates after the resume in @stop@. +The @stop@ member returns and @prod@'s @main@ member terminates. +The program main restarts after the resume in @start@. +The @start@ member returns and the program main terminates. @@ -3415,4 +3601,5 @@ \bibliography{pl,local} + \end{document} Index: doc/papers/general/.gitignore =================================================================== --- doc/papers/general/.gitignore (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/general/.gitignore (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -8,2 +8,3 @@ Paper.out.ps WileyNJD-AMA.bst +evaluation.zip Index: doc/papers/general/Makefile =================================================================== --- doc/papers/general/Makefile (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/general/Makefile (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -45,4 +45,10 @@ @rm -frv ${DOCUMENT} ${BASE}.ps WileyNJD-AMA.bst ${BASE}.out.ps ${Build} +Paper.zip : + zip -x general/.gitignore -x general/"*AMA*" -x general/Paper.out.ps -x general/Paper.tex.plain -x general/evaluation.zip -x general/mail -x general/response -x general/test.c -x general/evaluation.zip -x general/Paper.tex.plain -x general/Paper.ps -x general/Paper.pdf -x general/"*build*" -x general/evaluation/.gitignore -x general/evaluation/timing.xlsx -r Paper.zip general + +evaluation.zip : + zip -x evaluation/.gitignore -x evaluation/timing.xlsx -x evaluation/timing.dat -r evaluation.zip evaluation + # File Dependencies # @@ -66,23 +72,23 @@ ## Define the default recipes. -${Build}: +${Build} : mkdir -p ${Build} -${BASE}.out.ps: - ln -fs build/Paper.out.ps . +${BASE}.out.ps : ${Build} + ln -fs ${Build}/Paper.out.ps . -WileyNJD-AMA.bst: +WileyNJD-AMA.bst : ln -fs ../AMA/AMA-stix/ama/WileyNJD-AMA.bst . -${GRAPHS} : timing.gp timing.dat +${GRAPHS} : ${Build} timing.gp timing.dat gnuplot -e Build="'${Build}/'" evaluation/timing.gp -%.tex : %.fig +%.tex : %.fig ${Build} fig2dev -L eepic $< > ${Build}/$@ -%.ps : %.fig +%.ps : %.fig ${Build} fig2dev -L ps $< > ${Build}/$@ -%.pstex : %.fig +%.pstex : %.fig ${Build} fig2dev -L pstex $< > ${Build}/$@ fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t Index: doc/papers/general/Paper.tex =================================================================== --- doc/papers/general/Paper.tex (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/general/Paper.tex (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -54,4 +54,6 @@ \newcommand{\TODO}[1]{} % TODO elided +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + % Default underscore is too low and wide. Cannot use lstlisting "literate" as replacing underscore % removes it as a variable-name character so keywords in variables are highlighted. MUST APPEAR @@ -60,4 +62,7 @@ \renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}} +\renewcommand*{\thefootnote}{\Alph{footnote}} % hack because fnsymbol does not work +%\renewcommand*{\thefootnote}{\fnsymbol{footnote}} + \makeatletter % parindent is relative, i.e., toggled on/off in environments like itemize, so store the value for @@ -74,4 +79,5 @@ \setlength{\gcolumnposn}{3.5in} \setlength{\columnposn}{\gcolumnposn} + \newcommand{\C}[2][\@empty]{\ifx#1\@empty\else\global\setlength{\columnposn}{#1}\global\columnposn=\columnposn\fi\hfill\makebox[\textwidth-\columnposn][l]{\lst@basicstyle{\LstCommentStyle{#2}}}} \newcommand{\CRT}{\global\columnposn=\gcolumnposn} @@ -159,5 +165,6 @@ literate={-}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptstyle\land\,$}}1 {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1 - {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex{\textgreater}}2, + {<}{\textrm{\textless}}1 {>}{\textrm{\textgreater}}1 + {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0.5ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex{\textrm{\textgreater}}}2, moredelim=**[is][\color{red}]{`}{`}, }% lstset @@ -173,4 +180,10 @@ \lstMakeShortInline@% +\let\OLDthebibliography\thebibliography +\renewcommand\thebibliography[1]{ + \OLDthebibliography{#1} + \setlength{\parskip}{0pt} + \setlength{\itemsep}{4pt plus 0.3ex} +} \title{\texorpdfstring{\protect\CFA : Adding Modern Programming Language Features to C}{Cforall : Adding Modern Programming Language Features to C}} @@ -190,8 +203,9 @@ The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from commercial operating-systems to hobby projects. This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more. -Nevertheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive. - -The goal of the \CFA project is to create an extension of C that provides modern safety and productivity features while still ensuring strong backwards compatibility with C and its programmers. -Prior projects have attempted similar goals but failed to honour C programming-style; for instance, adding object-oriented or functional programming with garbage collection is a non-starter for many C developers. +Nevertheless, C, first standardized almost forty years ago, lacks many features that make programming in more modern languages safer and more productive. + +The goal of the \CFA project (pronounced ``C-for-all'') is to create an extension of C that provides modern safety and productivity features while still ensuring strong backwards compatibility with C and its programmers. +Prior projects have attempted similar goals but failed to honour C programming-style; +for instance, adding object-oriented or functional programming with garbage collection is a non-starter for many C developers. Specifically, \CFA is designed to have an orthogonal feature-set based closely on the C programming paradigm, so that \CFA features can be added \emph{incrementally} to existing C code-bases, and C programmers can learn \CFA extensions on an as-needed basis, preserving investment in existing code and programmers. This paper presents a quick tour of \CFA features showing how their design avoids shortcomings of similar features in C and other C-like languages. @@ -227,7 +241,7 @@ Love it or hate it, C is extremely popular, highly used, and one of the few systems languages. In many cases, \CC is often used solely as a better C. -Nevertheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive. - -\CFA (pronounced ``C-for-all'', and written \CFA or Cforall) is an evolutionary extension of the C programming language that aims to add modern language features to C, while maintaining both source and runtime compatibility with C and a familiar programming model for programmers. +Nevertheless, C, first standardized almost forty years ago~\cite{ANSI89:C}, lacks many features that make programming in more modern languages safer and more productive. + +\CFA (pronounced ``C-for-all'', and written \CFA or Cforall) is an evolutionary extension of the C programming language that adds modern language-features to C, while maintaining both source and runtime compatibility with C and a familiar programming model for programmers. The four key design goals for \CFA~\cite{Bilson03} are: (1) The behaviour of standard C code must remain the same when translated by a \CFA compiler as when translated by a C compiler; @@ -238,7 +252,60 @@ \CC is used similarly, but has the disadvantages of multiple legacy design-choices that cannot be updated and active divergence of the language model from C, requiring significant effort and training to incrementally add \CC to a C-based project. -\CFA is currently implemented as a source-to-source translator from \CFA to the gcc-dialect of C~\cite{GCCExtensions}, allowing it to leverage the portability and code optimizations provided by gcc, meeting goals (1)--(3). +All languages features discussed in this paper are working, except some advanced exception-handling features. +Not discussed in this paper are the integrated concurrency-constructs and user-level threading-library~\cite{Delisle18}. +\CFA is an \emph{open-source} project implemented as a source-to-source translator from \CFA to the gcc-dialect of C~\cite{GCCExtensions}, allowing it to leverage the portability and code optimizations provided by gcc, meeting goals (1)--(3). Ultimately, a compiler is necessary for advanced features and optimal performance. -All features discussed in this paper are working, unless otherwise stated as under construction. +% @plg2[9]% cd cfa-cc/src; cloc ArgTweak CodeGen CodeTools Common Concurrency ControlStruct Designators GenPoly InitTweak MakeLibCfa.cc MakeLibCfa.h Parser ResolvExpr SymTab SynTree Tuples driver prelude main.cc +% ------------------------------------------------------------------------------- +% Language files blank comment code +% ------------------------------------------------------------------------------- +% C++ 108 5420 5232 34961 +% C/C++ Header 86 2379 2450 8464 +% Teamcenter def 2 115 65 1387 +% make 5 168 87 1052 +% C 20 109 403 488 +% awk 1 12 26 121 +% sed 1 0 0 6 +% ------------------------------------------------------------------------------- +% SUM: 223 8203 8263 46479 +% ------------------------------------------------------------------------------- +The \CFA translator is 200+ files and 46,000+ lines of code written in C/\CC. +Starting with a translator versus a compiler makes it easier and faster to generate and debug C object-code rather than intermediate, assembler or machine code. +The translator design is based on the \emph{visitor pattern}, allowing multiple passes over the abstract code-tree, which works well for incrementally adding new feature through additional visitor passes. +At the heart of the translator is the type resolver, which handles the polymorphic routine/type overload-resolution. +% @plg2[8]% cd cfa-cc/src; cloc libcfa +% ------------------------------------------------------------------------------- +% Language files blank comment code +% ------------------------------------------------------------------------------- +% C 35 1256 1240 9116 +% C/C++ Header 54 358 1106 1198 +% make 2 201 325 1167 +% C++ 3 18 17 124 +% Assembly 3 56 97 111 +% Bourne Shell 2 2 0 25 +% awk 1 4 0 22 +% ------------------------------------------------------------------------------- +% SUM: 100 1895 2785 11763 +% ------------------------------------------------------------------------------- +The \CFA runtime system is 100+ files and 11,000+ lines of code, written in \CFA. +Currently, the \CFA runtime is the largest \emph{user} of \CFA providing a vehicle to test the language features and implementation. +% @plg2[6]% cd cfa-cc/src; cloc tests examples benchmark +% ------------------------------------------------------------------------------- +% Language files blank comment code +% ------------------------------------------------------------------------------- +% C 237 12260 2869 23286 +% make 8 464 245 2838 +% C/C++ Header 22 225 175 785 +% Python 5 131 93 420 +% C++ 10 48 5 201 +% Lua 2 31 4 126 +% Java 4 5 0 80 +% Go 2 11 9 40 +% ------------------------------------------------------------------------------- +% SUM: 290 13175 3400 27776 +% ------------------------------------------------------------------------------- +The \CFA tests are 290+ files and 27,000+ lines of code. +The tests illustrate syntactic and semantic features in \CFA, plus a growing number of runtime benchmarks. +The tests check for correctness and are used for daily regression testing of 3800+ commits. Finally, it is impossible to describe a programming language without usages before definitions. @@ -261,4 +328,5 @@ There are only two hard things in Computer Science: cache invalidation and \emph{naming things} -- Phil Karlton \end{quote} +\vspace{-9pt} C already has a limited form of ad-hoc polymorphism in the form of its basic arithmetic operators, which apply to a variety of different types using identical syntax. \CFA extends the built-in operator overloading by allowing users to define overloads for any function, not just operators, and even any variable; @@ -266,14 +334,13 @@ Code generation for these overloaded functions and variables is implemented by the usual approach of mangling the identifier names to include a representation of their type, while \CFA decides which overload to apply based on the same ``usual arithmetic conversions'' used in C to disambiguate operator overloads. As an example: - -\begin{cfa} -int max = 2147483647; $\C[4in]{// (1)}$ -double max = 1.7976931348623157E+308; $\C{// (2)}$ +\begin{cfa} +int max = 2147483647; $\C[4in]{// (1)}$ +double max = 1.7976931348623157E+308; $\C{// (2)}$ int max( int a, int b ) { return a < b ? b : a; } $\C{// (3)}$ double max( double a, double b ) { return a < b ? b : a; } $\C{// (4)}\CRT$ -max( 7, -max ); $\C[2.75in]{// uses (3) and (1), by matching int from constant 7}$ +max( 7, -max ); $\C{// uses (3) and (1), by matching int from constant 7}$ max( max, 3.14 ); $\C{// uses (4) and (2), by matching double from constant 3.14}$ -max( max, -max ); $\C{// ERROR: ambiguous}$ -int m = max( max, -max ); $\C{// uses (3) and (1) twice, by matching return type}\CRT$ +max( max, -max ); $\C{// ERROR, ambiguous}$ +int m = max( max, -max ); $\C{// uses (3) and (1) twice, by matching return type}$ \end{cfa} @@ -284,10 +351,10 @@ As is shown later, there are a number of situations where \CFA takes advantage of available type information to disambiguate, where other programming languages generate ambiguities. -\Celeven added @_Generic@ expressions, which is used in preprocessor macros to provide a form of ad-hoc polymorphism; +\Celeven added @_Generic@ expressions~\cite[\S~6.5.1.1]{C11}, which is used with preprocessor macros to provide ad-hoc polymorphism; however, this polymorphism is both functionally and ergonomically inferior to \CFA name overloading. The macro wrapping the generic expression imposes some limitations; \eg, it cannot implement the example above, because the variables @max@ are ambiguous with the functions @max@. Ergonomic limitations of @_Generic@ include the necessity to put a fixed list of supported types in a single place and manually dispatch to appropriate overloads, as well as possible namespace pollution from the dispatch functions, which must all have distinct names. -For backwards compatibility, \CFA supports @_Generic@ expressions, but it is an unnecessary mechanism. \TODO{actually implement that} +\CFA supports @_Generic@ expressions for backwards compatibility, but it is an unnecessary mechanism. \TODO{actually implement that} % http://fanf.livejournal.com/144696.html @@ -317,10 +384,10 @@ \begin{cfa} forall( otype T `| { T ?+?(T, T); }` ) T twice( T x ) { return x `+` x; } $\C{// ? denotes operands}$ -int val = twice( twice( 3.7 ) ); +int val = twice( twice( 3.7 ) ); $\C{// val == 14}$ \end{cfa} which works for any type @T@ with a matching addition operator. The polymorphism is achieved by creating a wrapper function for calling @+@ with @T@ bound to @double@, then passing this function to the first call of @twice@. There is now the option of using the same @twice@ and converting the result to @int@ on assignment, or creating another @twice@ with type parameter @T@ bound to @int@ because \CFA uses the return type~\cite{Cormack81,Baker82,Ada} in its type analysis. -The first approach has a late conversion from @double@ to @int@ on the final assignment, while the second has an eager conversion to @int@. +The first approach has a late conversion from @double@ to @int@ on the final assignment, while the second has an early conversion to @int@. \CFA minimizes the number of conversions and their potential to lose information, so it selects the first approach, which corresponds with C-programmer intuition. @@ -329,5 +396,6 @@ A simple example is leveraging the existing type-unsafe (@void *@) C @bsearch@ to binary search a sorted float array: \begin{cfa} -void * bsearch( const void * key, const void * base, size_t nmemb, size_t size, int (* compar)( const void *, const void * )); +void * bsearch( const void * key, const void * base, size_t nmemb, size_t size, + int (* compar)( const void *, const void * )); int comp( const void * t1, const void * t2 ) { return *(double *)t1 < *(double *)t2 ? -1 : *(double *)t2 < *(double *)t1 ? 1 : 0; @@ -355,12 +423,10 @@ \CFA has replacement libraries condensing hundreds of existing C functions into tens of \CFA overloaded functions, all without rewriting the actual computations (see Section~\ref{sec:libraries}). -For example, it is possible to write a type-safe \CFA wrapper @malloc@ based on the C @malloc@: +For example, it is possible to write a type-safe \CFA wrapper @malloc@ based on the C @malloc@, where the return type supplies the type/size of the allocation, which is impossible in most type systems. \begin{cfa} forall( dtype T | sized(T) ) T * malloc( void ) { return (T *)malloc( sizeof(T) ); } -int * ip = malloc(); $\C{// select type and size from left-hand side}$ -double * dp = malloc(); -struct S {...} * sp = malloc(); -\end{cfa} -where the return type supplies the type/size of the allocation, which is impossible in most type systems. +// select type and size from left-hand side +int * ip = malloc(); double * dp = malloc(); struct S {...} * sp = malloc(); +\end{cfa} Call-site inferencing and nested functions provide a localized form of inheritance. @@ -369,41 +435,56 @@ \begin{cfa} forall( otype T | { int ?` y; } $\C{// locally override behaviour}$ - qsort( vals, size ); $\C{// descending sort}$ -} -\end{cfa} -Within the block, the nested version of @??@ and this local version overrides the built-in @??@ overriding the built-in @?`c; `this->`i; `this->`d; $\C{// access containing fields}$ - } -} -\end{C++} -Object-oriented nesting of member functions in a \lstinline[language=C++]@class/struct@ allows eliding \lstinline[language=C++]@this->@ because of lexical scoping. -However, for other aggregate parameters, qualification is necessary: -\begin{cfa} +Heterogeneous data is often aggregated into a structure/union. +To reduce syntactic noise, \CFA provides a @with@ statement (see Pascal~\cite[\S~4.F]{Pascal}) to elide aggregate field-qualification by opening a scope containing the field identifiers. +\begin{cquote} +\vspace*{-\baselineskip}%??? +\lstDeleteShortInline@% +\begin{cfa} +struct S { char c; int i; double d; }; struct T { double m, n; }; -int S::f( T & t ) { $\C{// multiple aggregate parameters}$ - c; i; d; $\C{\color{red}// this--{\textgreater}.c, this--{\textgreater}.i, this--{\textgreater}.d}$ - `t.`m; `t.`n; $\C{// must qualify}$ -} -\end{cfa} - -To simplify the programmer experience, \CFA provides a @with@ statement (see Pascal~\cite[\S~4.F]{Pascal}) to elide aggregate qualification to fields by opening a scope containing the field identifiers. -Hence, the qualified fields become variables with the side-effect that it is easier to optimizing field references in a block. -\begin{cfa} -void f( S & this ) `with ( this )` { $\C{// with statement}$ - c; i; d; $\C{\color{red}// this.c, this.i, this.d}$ -} -\end{cfa} -with the generality of opening multiple aggregate-parameters: -\begin{cfa} -void f( S & s, T & t ) `with ( s, t )` { $\C{// multiple aggregate parameters}$ - c; i; d; $\C{\color{red}// s.c, s.i, s.d}$ - m; n; $\C{\color{red}// t.m, t.n}$ -} -\end{cfa} +// multiple aggregate parameters +\end{cfa} +\begin{tabular}{@{}l@{\hspace{\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}} +\begin{cfa} +void f( S & s, T & t ) { + `s.`c; `s.`i; `s.`d; + `t.`m; `t.`n; +} +\end{cfa} +& +\begin{cfa} +void f( S & s, T & t ) `with ( s, t )` { + c; i; d; // no qualification + m; n; +} +\end{cfa} +\end{tabular} +\lstMakeShortInline@% +\end{cquote} +Object-oriented programming languages only provide implicit qualification for the receiver. In detail, the @with@ statement has the form: @@ -1474,6 +1532,5 @@ The object is the implicit qualifier for the open structure-fields. -All expressions in the expression list are open in parallel within the compound statement. -This semantic is different from Pascal, which nests the openings from left to right. +All expressions in the expression list are open in parallel within the compound statement, which is different from Pascal, which nests the openings from left to right. The difference between parallel and nesting occurs for fields with the same name and type: \begin{cfa} @@ -1482,10 +1539,10 @@ with ( s, t ) { j + k; $\C{// unambiguous, s.j + t.k}$ - m = 5.0; $\C{// unambiguous, t.m = 5.0}$ - m = 1; $\C{// unambiguous, s.m = 1}$ - int a = m; $\C{// unambiguous, a = s.i }$ - double b = m; $\C{// unambiguous, b = t.m}$ + m = 5.0; $\C{// unambiguous, s.m = 5.0}$ + m = 1; $\C{// unambiguous, t.m = 1}$ + int a = m; $\C{// unambiguous, a = t.m }$ + double b = m; $\C{// unambiguous, b = s.m}$ int c = s.i + t.i; $\C{// unambiguous, qualification}$ - (double)m; $\C{// unambiguous, cast}$ + (double)m; $\C{// unambiguous, cast s.m}$ } \end{cfa} @@ -1511,7 +1568,7 @@ and implicitly opened \emph{after} a function-body open, to give them higher priority: \begin{cfa} -void ?{}( S & s, int `i` ) with ( s ) `with( $\emph{\color{red}params}$ )` { +void ?{}( S & s, int `i` ) with ( s ) `{` `with( $\emph{\color{red}params}$ )` { s.i = `i`; j = 3; m = 5.5; -} +} `}` \end{cfa} Finally, a cast may be used to disambiguate among overload variables in a @with@ expression: @@ -1581,5 +1638,5 @@ \lstDeleteShortInline@% \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}} -\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ +\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}} \\ \begin{cfa} `[5] *` int x1; @@ -1609,12 +1666,12 @@ \lstDeleteShortInline@% \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} -\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ +\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}} \\ \begin{cfa} `*` int x, y; -int y; -\end{cfa} -& -\begin{cfa} -int `*`x, `*`y; +int z; +\end{cfa} +& +\begin{cfa} +int `*`x, `*`y, z; \end{cfa} @@ -1622,5 +1679,6 @@ \lstMakeShortInline@% \end{cquote} -The downside of the \CFA semantics is the need to separate regular and pointer declarations. +% The downside of the \CFA semantics is the need to separate regular and pointer declarations. +The separation of regular and pointer declarations by \CFA declarations enforces greater clarity with only slightly more syntax. \begin{comment} @@ -1629,5 +1687,5 @@ \lstDeleteShortInline@% \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}} -\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{C}} \\ +\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{C}} \\ \begin{cfa} [ 5 ] int z; @@ -1671,5 +1729,5 @@ \lstDeleteShortInline@% \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}} -\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{C}} \\ +\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{C}} \\ \begin{cfa} extern const * const int x; @@ -1696,5 +1754,5 @@ \lstDeleteShortInline@% \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} -\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ +\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}} \\ \begin{cfa} y = (* int)x; @@ -1724,5 +1782,5 @@ \lstDeleteShortInline@% \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} -\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ +\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}} \\ \begin{cfa} [double] foo(), foo( int ), foo( double ) {...} @@ -1742,10 +1800,7 @@ * [ * int ] ( int y ) gp; $\C{// pointer to function returning pointer to int with int parameter}$ * [ ] ( int, char ) hp; $\C{// pointer to function returning no result with int and char parameters}$ -* [ * int, int ] ( int ) jp; $\C{// pointer to function returning pointer to int and int with int parameter}$ -\end{cfa} -Note, a function name cannot be specified: -\begin{cfa} -* [ int x ] f () fp; $\C{// function name "f" is disallowed}\CRT$ -\end{cfa} +* [ * int, int ] ( int ) jp; $\C{// pointer to function returning pointer to int and int with int parameter}\CRT$ +\end{cfa} +Note, the name of the function pointer is specified last, as for other variable declarations. Finally, new \CFA declarations may appear together with C declarations in the same program block, but cannot be mixed within a specific declaration. @@ -1804,21 +1859,6 @@ This provides a much more orthogonal design for library implementors, obviating the need for workarounds such as @std::reference_wrapper@. Secondly, \CFA references are rebindable, whereas \CC references have a fixed address. -\newsavebox{\LstBox} -\begin{lrbox}{\LstBox} -\lstset{basicstyle=\footnotesize\linespread{0.9}\sf} -\begin{cfa} -int & r = *new( int ); -... $\C{// non-null reference}$ -delete &r; $\C{// unmanaged (programmer) memory-management}$ -r += 1; $\C{// undefined reference}$ -\end{cfa} -\end{lrbox} Rebinding allows \CFA references to be default-initialized (\eg to a null pointer\footnote{ -While effort has been made into non-null reference checking in \CC and Java, the exercise seems moot for any non-managed languages (C/\CC), given that it only handles one of many different error situations: -\begin{cquote} -\usebox{\LstBox} -\end{cquote} -}% -) and point to different addresses throughout their lifetime, like pointers. +While effort has been made into non-null reference checking in \CC and Java, the exercise seems moot for any non-managed languages (C/\CC), given that it only handles one of many different error situations, \eg using a pointer after its storage is deleted.}) and point to different addresses throughout their lifetime, like pointers. Rebinding is accomplished by extending the existing syntax and semantics of the address-of operator in C. @@ -1832,5 +1872,5 @@ \begin{itemize} \item -if @R@ is an rvalue of type {@T &@$_1 \cdots$@ &@$_r$} where $r \ge 1$ references (@&@ symbols) than @&R@ has type {@T `*`&@$_{\color{red}2} \cdots$@ &@$_{\color{red}r}$}, \\ \ie @T@ pointer with $r-1$ references (@&@ symbols). +if @R@ is an rvalue of type {@T &@$_1 \cdots$@ &@$_r$} where $r \ge 1$ references (@&@ symbols) then @&R@ has type {@T `*`&@$_{\color{red}2} \cdots$@ &@$_{\color{red}r}$}, \\ \ie @T@ pointer with $r-1$ references (@&@ symbols). \item @@ -1866,5 +1906,5 @@ \end{cfa} This allows complex values to be succinctly and efficiently passed to functions, without the syntactic overhead of explicit definition of a temporary variable or the runtime cost of pass-by-value. -\CC allows a similar binding, but only for @const@ references; the more general semantics of \CFA are an attempt to avoid the \newterm{const hell} problem, in which addition of a @const@ qualifier to one reference requires a cascading chain of added qualifiers. +\CC allows a similar binding, but only for @const@ references; the more general semantics of \CFA are an attempt to avoid the \newterm{const poisoning} problem~\cite{Taylor10}, in which addition of a @const@ qualifier to one reference requires a cascading chain of added qualifiers. @@ -1880,5 +1920,4 @@ \begin{tabular}{@{}l@{\hspace{3em}}l|l@{}} \multicolumn{1}{c@{\hspace{3em}}}{\textbf{C Type Nesting}} & \multicolumn{1}{c|}{\textbf{C Implicit Hoisting}} & \multicolumn{1}{c}{\textbf{\CFA}} \\ -\hline \begin{cfa} struct S { @@ -1960,16 +1999,16 @@ The symbol \lstinline+^+ is used for the destructor name because it was the last binary operator that could be used in a unary context.}. The name @{}@ comes from the syntax for the initializer: @struct S { int i, j; } s = `{` 2, 3 `}`@. -Like other \CFA operators, these names represent the syntax used to call the constructor or destructor, \eg @?{}(x, ...)@ or @^{}(x, ...)@. +Like other \CFA operators, these names represent the syntax used to explicitly call the constructor or destructor, \eg @s{...}@ or @^s{...}@. The constructor and destructor have return type @void@, and the first parameter is a reference to the object type to be constructed or destructed. While the first parameter is informally called the @this@ parameter, as in object-oriented languages, any variable name may be used. -Both constructors and destructors allow additional parametes after the @this@ parameter for specifying values for initialization/de-initialization\footnote{ +Both constructors and destructors allow additional parameters after the @this@ parameter for specifying values for initialization/de-initialization\footnote{ Destruction parameters are useful for specifying storage-management actions, such as de-initialize but not deallocate.}. \begin{cfa} -struct VLA { int len, * data; }; +struct VLA { int len, * data; }; $\C{// variable length array of integers}$ void ?{}( VLA & vla ) with ( vla ) { len = 10; data = alloc( len ); } $\C{// default constructor}$ void ^?{}( VLA & vla ) with ( vla ) { free( data ); } $\C{// destructor}$ { - VLA x; $\C{// implicit: ?\{\}( x );}$ -} $\C{// implicit: ?\^{}\{\}( x );}$ + VLA x; $\C{// implicit:\ \ x\{\};}$ +} $\C{// implicit:\ \textasciicircum{}x\{\};}$ \end{cfa} @VLA@ is a \newterm{managed type}\footnote{ @@ -1996,11 +2035,11 @@ appropriate care is taken to not recursively call the copy constructor when initializing the second parameter. -\CFA constructors may be explicitly call, like Java, and destructors may be explicitly called, like \CC. +\CFA constructors may be explicitly called, like Java, and destructors may be explicitly called, like \CC. Explicit calls to constructors double as a \CC-style \emph{placement syntax}, useful for construction of member fields in user-defined constructors and reuse of existing storage allocations. -While existing call syntax works for explicit calls to constructors and destructors, \CFA also provides a more concise \newterm{operator syntax} for both: +Like the other operators in \CFA, there is a concise syntax for constructor/destructor function calls: \begin{cfa} { VLA x, y = { 20, 0x01 }, z = y; $\C{// z points to y}$ - // ?{}( x ); ?{}( y, 20, 0x01 ); ?{}( z, y ); + // x{}; y{ 20, 0x01 }; z{ z, y }; ^x{}; $\C{// deallocate x}$ x{}; $\C{// reallocate x}$ @@ -2009,5 +2048,5 @@ y{ x }; $\C{// reallocate y, points to x}$ x{}; $\C{// reallocate x, not pointing to y}$ - // ^?{}(z); ^?{}(y); ^?{}(x); + // ^z{}; ^y{}; ^x{}; } \end{cfa} @@ -2030,5 +2069,5 @@ In these cases, \CFA provides the initialization syntax \lstinline|S x `@=` {}|, and the object becomes unmanaged, so implicit constructor and destructor calls are not generated. Any C initializer can be the right-hand side of an \lstinline|@=| initializer, \eg \lstinline|VLA a @= { 0, 0x0 }|, with the usual C initialization semantics. -The same syntax can be used in a compound literal, \eg \lstinline|a = VLA`@`{ 0, 0x0 }|, to create a C-style literal. +The same syntax can be used in a compound literal, \eg \lstinline|a = (VLA)`@`{ 0, 0x0 }|, to create a C-style literal. The point of \lstinline|@=| is to provide a migration path from legacy C code to \CFA, by providing a mechanism to incrementally convert to implicit initialization. @@ -2046,4 +2085,5 @@ +\begin{comment} \subsection{Integral Suffixes} @@ -2079,4 +2119,5 @@ \lstMakeShortInline@% \end{cquote} +\end{comment} @@ -2084,5 +2125,5 @@ In C, @0@ has the special property that it is the only ``false'' value; -from the standard, any value that compares equal to @0@ is false, while any value that compares unequal to @0@ is true. +by the standard, any value that compares equal to @0@ is false, while any value that compares unequal to @0@ is true. As such, an expression @x@ in any boolean context (such as the condition of an @if@ or @while@ statement, or the arguments to @&&@, @||@, or @?:@\,) can be rewritten as @x != 0@ without changing its semantics. Operator overloading in \CFA provides a natural means to implement this truth-value comparison for arbitrary types, but the C type system is not precise enough to distinguish an equality comparison with @0@ from an equality comparison with an arbitrary integer or pointer. @@ -2119,5 +2160,5 @@ \lstDeleteShortInline@% \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}} -\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{postfix function}} & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{constant}} & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{variable/expression}} & \multicolumn{1}{c}{\textbf{postfix pointer}} \\ +\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{postfix function}} & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{constant}} & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{variable/expression}} & \multicolumn{1}{c@{}}{\textbf{postfix pointer}} \\ \begin{cfa} int |?`h|( int s ); @@ -2164,6 +2205,6 @@ \lstset{language=CFA,moredelim=**[is][\color{red}]{|}{|},deletedelim=**[is][]{`}{`}} \lstDeleteShortInline@% -\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} -\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{\CC}} \\ +\begin{tabular}{@{}l@{\hspace{1.25\parindentlnth}}l@{}} +\multicolumn{1}{@{}c@{\hspace{1.25\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{\CC}} \\ \begin{cfa} struct W { @@ -2209,5 +2250,5 @@ W w, heavy = { 20 }; w = 155|_lb|; - w = 0b1111|_lb|; // error, binary unsupported + // binary unsupported w = 0${\color{red}\LstBasicStyle{'}}$233|_lb|; // quote separator w = 0x9b|_kg|; @@ -2239,5 +2280,5 @@ \lstDeleteShortInline@% \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} -\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{Definition}} & \multicolumn{1}{c}{\textbf{Usage}} \\ +\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{Definition}} & \multicolumn{1}{c@{}}{\textbf{Usage}} \\ \begin{cfa} const short int `MIN` = -32768; @@ -2257,6 +2298,6 @@ \begin{cquote} \lstDeleteShortInline@% -\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} -\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ +\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}} +\multicolumn{1}{@{}c@{\hspace{\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}} \\ \begin{cfa} MIN @@ -2267,6 +2308,6 @@ & \begin{cfa} -SCHAR_MIN, CHAR_MIN, SHRT_MIN, INT_MIN, LONG_MIN, LLONG_MIN, FLT_MIN, DBL_MIN, LDBL_MIN -SCHAR_MAX, UCHAR_MAX, SHRT_MAX, INT_MAX, LONG_MAX, LLONG_MAX, FLT_MAX, DBL_MAX, LDBL_MAX +CHAR_MIN, SHRT_MIN, INT_MIN, LONG_MIN, LLONG_MIN, FLT_MIN, DBL_MIN, LDBL_MIN +UCHAR_MAX, SHRT_MAX, INT_MAX, LONG_MAX, LLONG_MAX, FLT_MAX, DBL_MAX, LDBL_MAX M_PI, M_PIl M_E, M_El @@ -2284,5 +2325,5 @@ \lstDeleteShortInline@% \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} -\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{Definition}} & \multicolumn{1}{c}{\textbf{Usage}} \\ +\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{Definition}} & \multicolumn{1}{c@{}}{\textbf{Usage}} \\ \begin{cfa} float `log`( float x ); @@ -2303,5 +2344,5 @@ \lstDeleteShortInline@% \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} -\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ +\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}} \\ \begin{cfa} log @@ -2331,5 +2372,5 @@ \lstDeleteShortInline@% \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} -\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{Definition}} & \multicolumn{1}{c}{\textbf{Usage}} \\ +\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{Definition}} & \multicolumn{1}{c@{}}{\textbf{Usage}} \\ \begin{cfa} unsigned int `abs`( int ); @@ -2350,5 +2391,5 @@ \lstDeleteShortInline@% \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} -\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ +\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}} \\ \begin{cfa} abs @@ -2373,5 +2414,5 @@ an allocation with a specified character. \item[resize] -an existing allocation to decreased or increased its size. +an existing allocation to decrease or increase its size. 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. For an increase in storage size, new storage after the copied data may be filled. @@ -2387,4 +2428,6 @@ \begin{table} +\caption{Storage-Management Operations} +\label{t:StorageManagementOperations} \centering \lstDeleteShortInline@% @@ -2406,12 +2449,9 @@ \lstDeleteShortInline~% \lstMakeShortInline@% -\caption{Storage-Management Operations} -\label{t:StorageManagementOperations} \end{table} \begin{figure} \centering -\begin{cquote} -\begin{cfa}[aboveskip=0pt] +\begin{cfa}[aboveskip=0pt,xleftmargin=0pt] size_t dim = 10; $\C{// array dimension}$ char fill = '\xff'; $\C{// initialization fill value}$ @@ -2419,7 +2459,7 @@ \end{cfa} \lstDeleteShortInline@% -\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} -\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ -\begin{cfa} +\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}} +\multicolumn{1}{@{}c@{\hspace{\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}} \\ +\begin{cfa}[xleftmargin=-10pt] ip = alloc(); ip = alloc( fill ); @@ -2436,19 +2476,18 @@ & \begin{cfa} -ip = (int *)malloc( sizeof( int ) ); -ip = (int *)malloc( sizeof( int ) ); memset( ip, fill, sizeof( int ) ); -ip = (int *)malloc( dim * sizeof( int ) ); -ip = (int *)malloc( sizeof( int ) ); memset( ip, fill, dim * sizeof( int ) ); -ip = (int *)realloc( ip, 2 * dim * sizeof( int ) ); -ip = (int *)realloc( ip, 4 * dim * sizeof( int ) ); memset( ip, fill, 4 * dim * sizeof( int ) ); - -ip = memalign( 16, sizeof( int ) ); -ip = memalign( 16, sizeof( int ) ); memset( ip, fill, sizeof( int ) ); -ip = memalign( 16, dim * sizeof( int ) ); -ip = memalign( 16, dim * sizeof( int ) ); memset( ip, fill, dim * sizeof( int ) ); -\end{cfa} -\end{tabular} -\lstMakeShortInline@% -\end{cquote} +ip = (int *)malloc( sizeof(int) ); +ip = (int *)malloc( sizeof(int) ); memset( ip, fill, sizeof(int) ); +ip = (int *)malloc( dim * sizeof(int) ); +ip = (int *)malloc( sizeof(int) ); memset( ip, fill, dim * sizeof(int) ); +ip = (int *)realloc( ip, 2 * dim * sizeof(int) ); +ip = (int *)realloc( ip, 4 * dim * sizeof(int) ); memset( ip, fill, 4 * dim * sizeof(int)); + +ip = memalign( 16, sizeof(int) ); +ip = memalign( 16, sizeof(int) ); memset( ip, fill, sizeof(int) ); +ip = memalign( 16, dim * sizeof(int) ); +ip = memalign( 16, dim * sizeof(int) ); memset( ip, fill, dim * sizeof(int) ); +\end{cfa} +\end{tabular} +\lstMakeShortInline@% \caption{\CFA versus C Storage-Allocation} \label{f:StorageAllocation} @@ -2463,5 +2502,5 @@ S * as = anew( dim, 2, 3 ); $\C{// each array element initialized to 2, 3}$ \end{cfa} -Note, \CC can only initialization array elements via the default constructor. +Note, \CC can only initialize array elements via the default constructor. Finally, the \CFA memory-allocator has \newterm{sticky properties} for dynamic storage: fill and alignment are remembered with an object's storage in the heap. @@ -2480,5 +2519,5 @@ \lstDeleteShortInline@% \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} -\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{\CC}} \\ +\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{\CC}} \\ \begin{cfa} int x = 1, y = 2, z = 3; @@ -2535,5 +2574,5 @@ \end{cquote} There is a weak similarity between the \CFA logical-or operator and the Shell pipe-operator for moving data, where data flows in the correct direction for input but the opposite direction for output. - +\begin{comment} The implicit separator character (space/blank) is a separator not a terminator. The rules for implicitly adding the separator are: @@ -2554,4 +2593,5 @@ }% \end{itemize} +\end{comment} There are functions to set and get the separator string, and manipulators to toggle separation on and off in the middle of output. @@ -2568,6 +2608,6 @@ \centering \lstDeleteShortInline@% -\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}@{\hspace{2\parindentlnth}}l@{}} -\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{@{\hspace{2\parindentlnth}}c}{\textbf{C}} \\ +\begin{tabular}{@{}l@{\hspace{3\parindentlnth}}l@{}} +\multicolumn{1}{@{}c@{\hspace{3\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}} \\ \begin{cfa} #include @@ -2602,10 +2642,13 @@ -\section{Evaluation} +\section{Polymorphism Evaluation} \label{sec:eval} -Though \CFA provides significant added functionality over C, these features have a low runtime penalty. -In fact, \CFA's features for generic programming can enable faster runtime execution than idiomatic @void *@-based C code. -This claim is demonstrated through a set of generic-code-based micro-benchmarks in C, \CFA, and \CC (see stack implementations in Appendix~\ref{sec:BenchmarkStackImplementation}). +\CFA adds parametric polymorphism to C. +A runtime evaluation is performed to compare the cost of alternative styles of polymorphism. +The goal is to compare just the underlying mechanism for implementing different kinds of polymorphism. +% Though \CFA provides significant added functionality over C, these features have a low runtime penalty. +% In fact, it is shown that \CFA's generic programming can enable faster runtime execution than idiomatic @void *@-based C code. +The experiment is a set of generic-stack micro-benchmarks~\cite{CFAStackEvaluation} in C, \CFA, and \CC (see implementations in Appendix~\ref{sec:BenchmarkStackImplementations}). Since all these languages share a subset essentially comprising standard C, maximal-performance benchmarks should show little runtime variance, differing only in length and clarity of source code. A more illustrative comparison measures the costs of idiomatic usage of each language's features. @@ -2638,13 +2681,13 @@ \end{figure} -The structure of each benchmark implemented is: C with @void *@-based polymorphism, \CFA with the presented features, \CC with templates, and \CC using only class inheritance for polymorphism, called \CCV. +The structure of each benchmark implemented is: C with @void *@-based polymorphism, \CFA with parametric polymorphism, \CC with templates, and \CC using only class inheritance for polymorphism, called \CCV. The \CCV variant illustrates an alternative object-oriented idiom where all objects inherit from a base @object@ class, mimicking a Java-like interface; hence runtime checks are necessary to safely down-cast objects. The most notable difference among the implementations is in memory layout of generic types: \CFA and \CC inline the stack and pair elements into corresponding list and pair nodes, while C and \CCV lack such a capability and instead must store generic objects via pointers to separately-allocated objects. -Note that the C benchmark uses unchecked casts as there is no runtime mechanism to perform such checks, while \CFA and \CC provide type-safety statically. +Note, the C benchmark uses unchecked casts as C has no runtime mechanism to perform such checks, while \CFA and \CC provide type-safety statically. Figure~\ref{fig:eval} and Table~\ref{tab:eval} show the results of running the benchmark in Figure~\ref{fig:BenchmarkTest} and its C, \CC, and \CCV equivalents. The graph plots the median of 5 consecutive runs of each program, with an initial warm-up run omitted. -All code is compiled at \texttt{-O2} by gcc or g++ 6.3.0, with all \CC code compiled as \CCfourteen. +All code is compiled at \texttt{-O2} by gcc or g++ 6.4.0, with all \CC code compiled as \CCfourteen. The benchmarks are run on an Ubuntu 16.04 workstation with 16 GB of RAM and a 6-core AMD FX-6300 CPU with 3.5 GHz maximum clock frequency. @@ -2657,12 +2700,12 @@ \begin{table} -\centering \caption{Properties of benchmark code} \label{tab:eval} +\centering \newcommand{\CT}[1]{\multicolumn{1}{c}{#1}} \begin{tabular}{rrrrr} & \CT{C} & \CT{\CFA} & \CT{\CC} & \CT{\CCV} \\ \hline maximum memory usage (MB) & 10,001 & 2,502 & 2,503 & 11,253 \\ -source code size (lines) & 196 & 186 & 125 & 290 \\ +source code size (lines) & 201 & 191 & 125 & 294 \\ redundant type annotations (lines) & 27 & 0 & 2 & 16 \\ binary size (KB) & 14 & 257 & 14 & 37 \\ @@ -2672,8 +2715,9 @@ The C and \CCV variants are generally the slowest with the largest memory footprint, because of their less-efficient memory layout and the pointer-indirection necessary to implement generic types; this inefficiency is exacerbated by the second level of generic types in the pair benchmarks. -By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair of @short@ and @char@ because the storage layout is equivalent, with the inlined libraries (\ie no separate compilation) and greater maturity of the \CC compiler contributing to its lead. +By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair because of equivalent storage layout, with the inlined libraries (\ie no separate compilation) and greater maturity of the \CC compiler contributing to its lead. \CCV is slower than C largely due to the cost of runtime type-checking of down-casts (implemented with @dynamic_cast@); -The outlier in the graph for \CFA, pop @pair@, results from the complexity of the generated-C polymorphic code. -The gcc compiler is unable to optimize some dead code and condense nested calls; a compiler designed for \CFA could easily perform these optimizations. +The outlier for \CFA, pop @pair@, results from the complexity of the generated-C polymorphic code. +The gcc compiler is unable to optimize some dead code and condense nested calls; +a compiler designed for \CFA could easily perform these optimizations. Finally, the binary size for \CFA is larger because of static linking with the \CFA libraries. @@ -2687,9 +2731,11 @@ Line-count is a fairly rough measure of code complexity; another important factor is how much type information the programmer must specify manually, especially where that information is not compiler-checked. -Such unchecked type information produces a heavier documentation burden and increased potential for runtime bugs, and is much less common in \CFA than C, with its manually specified function pointer arguments and format codes, or \CCV, with its extensive use of untype-checked downcasts, \eg @object@ to @integer@ when popping a stack. +Such unchecked type information produces a heavier documentation burden and increased potential for runtime bugs, and is much less common in \CFA than C, with its manually specified function pointer arguments and format codes, or \CCV, with its extensive use of un-type-checked downcasts, \eg @object@ to @integer@ when popping a stack. To quantify this manual typing, the ``redundant type annotations'' line in Table~\ref{tab:eval} counts the number of lines on which the type of a known variable is respecified, either as a format specifier, explicit downcast, type-specific function, or by name in a @sizeof@, struct literal, or @new@ expression. The \CC benchmark uses two redundant type annotations to create a new stack nodes, while the C and \CCV benchmarks have several such annotations spread throughout their code. The \CFA benchmark is able to eliminate all redundant type annotations through use of the polymorphic @alloc@ function discussed in Section~\ref{sec:libraries}. +We conjecture these results scale across most generic data-types as the underlying polymorphism implement is constant. + \section{Related Work} @@ -2697,4 +2743,11 @@ \subsection{Polymorphism} + +ML~\cite{ML} was the first language to support parametric polymorphism. +Like \CFA, it supports universal type parameters, but not the use of assertions and traits to constrain type arguments. +Haskell~\cite{Haskell10} combines ML-style polymorphism, polymorphic data types, and type inference with the notion of type classes, collections of overloadable methods that correspond in intent to traits in \CFA. +Unlike \CFA, Haskell requires an explicit association between types and their classes that specifies the implementation of operations. +These associations determine the functions that are assertion arguments for particular combinations of class and type, in contrast to \CFA where the assertion arguments are selected at function call sites based upon the set of operations in scope at that point. +Haskell also severely restricts the use of overloading: an overloaded name can only be associated with a single class, and methods with overloaded names can only be defined as part of instance declarations. \CC provides three disjoint polymorphic extensions to C: overloading, inheritance, and templates. @@ -2750,5 +2803,5 @@ Go does not have tuples but supports MRVF. Java's variadic functions appear similar to C's but are type-safe using homogeneous arrays, which are less useful than \CFA's heterogeneously-typed variadic functions. -Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML~\cite{sml} and~\cite{Scala}, which decompose tuples using pattern matching. +Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML~\cite{sml}, Haskell, and Scala~\cite{Scala}, which decompose tuples using pattern matching. @@ -2767,25 +2820,4 @@ data-parallel features have not yet been added to \CFA, but are easily incorporated within its design, while concurrency primitives similar to those in $\mu$\CC have already been added~\cite{Delisle18}. Finally, CCured~\cite{Necula02} and Ironclad \CC~\cite{DeLozier13} attempt to provide a more memory-safe C by annotating pointer types with garbage collection information; type-checked polymorphism in \CFA covers several of C's memory-safety issues, but more aggressive approaches such as annotating all pointer types with their nullability or requiring runtime garbage collection are contradictory to \CFA's backwards compatibility goals. - - -\begin{comment} -\subsection{Control Structures / Declarations / Literals} - -Java has default fall through like C/\CC. -Pascal/Ada/Go/Rust do not have default fall through. -\Csharp does not have fall through but still requires a break. -Python uses dictionary mapping. \\ -\CFA choose is like Rust match. - -Java has labelled break/continue. \\ -Languages with and without exception handling. - -Alternative C declarations. \\ -Different references \\ -Constructors/destructors - -0/1 Literals \\ -user defined: D, Objective-C -\end{comment} @@ -2802,10 +2834,8 @@ Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable. -There is ongoing work on a wide range of \CFA features, including arrays with size, runtime type-information, virtual functions, user-defined conversions, concurrent primitives, and modules. -While all examples in the paper compile and run, a public beta-release of \CFA will take another 8--12 months to finalize these extensions. -There are also interesting future directions for the polymorphism design. -Notably, \CC template functions trade compile time and code bloat for optimal runtime of individual instantiations of polymorphic functions. -\CFA polymorphic functions use dynamic virtual-dispatch; -the runtime overhead of this approach is low, but not as low as inlining, and it may be beneficial to provide a mechanism for performance-sensitive code. +While all examples in the paper compile and run, a public beta-release of \CFA will take 6--8 months to reduce compilation time, provide better debugging, and add a few more libraries. +There is also new work on a number of \CFA features, including arrays with size, runtime type-information, virtual functions, user-defined conversions, and modules. +While \CFA polymorphic functions use dynamic virtual-dispatch with low runtime overhead (see Section~\ref{sec:eval}), it is not as low as \CC template-inlining. +Hence it may be beneficial to provide a mechanism for performance-sensitive code. Two promising approaches are an @inline@ annotation at polymorphic function call sites to create a template-specialization of the function (provided the code is visible) or placing an @inline@ annotation on polymorphic function-definitions to instantiate a specialized version for some set of types (\CC template specialization). These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code-bloat. @@ -2816,46 +2846,60 @@ The authors would like to recognize the design assistance of Glen Ditchfield, Richard Bilson, Thierry Delisle, Andrew Beach and Brice Dobry on the features described in this paper, and thank Magnus Madsen for feedback on the writing. -This work is supported by a corporate partnership with Huawei Ltd.\ (\url{http://www.huawei.com}), and Aaron Moss and Peter Buhr are partially funded by the Natural Sciences and Engineering Research Council of Canada. - - +Funding for this project has been provided by Huawei Ltd.\ (\url{http://www.huawei.com}), and Aaron Moss and Peter Buhr are partially funded by the Natural Sciences and Engineering Research Council of Canada. + +{% +\fontsize{9bp}{12bp}\selectfont% \bibliography{pl} - +}% \appendix -\section{Benchmark Stack Implementation} -\label{sec:BenchmarkStackImplementation} - -Throughout, @/***/@ designates a counted redundant type annotation; code reformatted for brevity. - -\smallskip\noindent -C -\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt] -struct stack_node { +\section{Benchmark Stack Implementations} +\label{sec:BenchmarkStackImplementations} + +Throughout, @/***/@ designates a counted redundant type annotation; code reformatted slightly for brevity. + + +\subsection{C} + +\begin{flushleft} +\lstDeleteShortInline@% +\begin{tabular}{@{}l@{\hspace{1.8\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}} +\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt] +typedef struct node { void * value; - struct stack_node * next; -}; -struct stack { struct stack_node* head; }; -void clear_stack( struct stack * s, void (*free_el)( void * ) ) { - for ( struct stack_node * next = s->head; next; ) { - struct stack_node * crnt = next; - next = crnt->next; - free_el( crnt->value ); - free( crnt ); + struct node * next; +} node; +typedef struct stack { + struct node * head; +} stack; +void copy_stack( stack * s, const stack * t, + void * (*copy)( const void * ) ) { + node ** cr = &s->head; + for (node * nx = t->head; nx; nx = nx->next) { + *cr = malloc( sizeof(node) ); /***/ + (*cr)->value = copy( nx->value ); + cr = &(*cr)->next; + } + *cr = NULL; +} +void clear_stack( stack * s, void (* free_el)( void * ) ) { + for ( node * nx = s->head; nx; ) { + node * cr = nx; + nx = cr->next; + free_el( cr->value ); + free( cr ); } s->head = NULL; } -struct stack new_stack() { return (struct stack){ NULL }; /***/ } -void copy_stack( struct stack * s, const struct stack * t, void * (*copy)( const void * ) ) { - struct stack_node ** crnt = &s->head; - for ( struct stack_node * next = t->head; next; next = next->next ) { - *crnt = malloc( sizeof(struct stack_node) ); /***/ - (*crnt)->value = copy( next->value ); - crnt = &(*crnt)->next; - } - *crnt = NULL; -} -struct stack * assign_stack( struct stack * s, const struct stack * t, - void * (*copy_el)( const void * ), void (*free_el)( void * ) ) { +\end{cfa} +& +\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt] +stack new_stack() { + return (stack){ NULL }; /***/ +} +stack * assign_stack( stack * s, const stack * t, + void * (*copy_el)( const void * ), + void (*free_el)( void * ) ) { if ( s->head == t->head ) return s; clear_stack( s, free_el ); /***/ @@ -2863,12 +2907,14 @@ return s; } -_Bool stack_empty( const struct stack * s ) { return s->head == NULL; } -void push_stack( struct stack * s, void * v ) { - struct stack_node * n = malloc( sizeof(struct stack_node) ); /***/ - *n = (struct stack_node){ v, s->head }; /***/ +_Bool stack_empty( const stack * s ) { + return s->head == NULL; +} +void push_stack( stack * s, void * v ) { + node * n = malloc( sizeof(node) ); /***/ + *n = (node){ v, s->head }; /***/ s->head = n; } -void * pop_stack( struct stack * s ) { - struct stack_node * n = s->head; +void * pop_stack( stack * s ) { + node * n = s->head; s->head = n->next; void * v = n->value; @@ -2877,81 +2923,46 @@ } \end{cfa} - -\medskip\noindent -\CFA -\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt] -forall( otype T ) struct stack_node { - T value; - stack_node(T) * next; -}; -forall( otype T ) struct stack { stack_node(T) * head; }; -forall( otype T ) void clear( stack(T) & s ) with( s ) { - for ( stack_node(T) * next = head; next; ) { - stack_node(T) * crnt = next; - next = crnt->next; - ^(*crnt){}; - free(crnt); +\end{tabular} +\lstMakeShortInline@% +\end{flushleft} + + +\subsection{\CFA} +\label{s:CforallStack} + +\begin{flushleft} +\lstDeleteShortInline@% +\begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}} +\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt] +forall( otype T ) { + struct node { + T value; + node(T) * next; + }; + struct stack { node(T) * head; }; + void ?{}( stack(T) & s, stack(T) t ) { // copy + node(T) ** cr = &s.head; + for ( node(T) * nx = t.head; nx; nx = nx->next ) { + *cr = alloc(); + ((*cr)->value){ nx->value }; + cr = &(*cr)->next; + } + *cr = 0; } - head = 0; -} -forall( otype T ) void ?{}( stack(T) & s ) { (s.head){ 0 }; } -forall( otype T ) void ?{}( stack(T) & s, stack(T) t ) { - stack_node(T) ** crnt = &s.head; - for ( stack_node(T) * next = t.head; next; next = next->next ) { - *crnt = alloc(); - ((*crnt)->value){ next->value }; - crnt = &(*crnt)->next; - } - *crnt = 0; -} -forall( otype T ) stack(T) ?=?( stack(T) & s, stack(T) t ) { - if ( s.head == t.head ) return s; - clear( s ); - s{ t }; - return s; -} -forall( otype T ) void ^?{}( stack(T) & s) { clear( s ); } -forall( otype T ) _Bool empty( const stack(T) & s ) { return s.head == 0; } -forall( otype T ) void push( stack(T) & s, T value ) with( s ) { - stack_node(T) * n = alloc(); - (*n){ value, head }; - head = n; -} -forall( otype T ) T pop( stack(T) & s ) with( s ) { - stack_node(T) * n = head; - head = n->next; - T v = n->value; - ^(*n){}; - free( n ); - return v; -} -\end{cfa} - -\begin{comment} -forall( otype T ) { - struct stack_node { - T value; - stack_node(T) * next; - }; - struct stack { stack_node(T) * head; }; void clear( stack(T) & s ) with( s ) { - for ( stack_node(T) * next = head; next; ) { - stack_node(T) * crnt = next; - next = crnt->next; - ^(*crnt){}; - free(crnt); + for ( node(T) * nx = head; nx; ) { + node(T) * cr = nx; + nx = cr->next; + ^(*cr){}; + free( cr ); } head = 0; } + +\end{cfa} +& +\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt] void ?{}( stack(T) & s ) { (s.head){ 0 }; } - void ?{}( stack(T) & s, stack(T) t ) { - stack_node(T) ** crnt = &s.head; - for ( stack_node(T) * next = t.head; next; next = next->next ) { - *crnt = alloc(); - ((*crnt)->value){ next->value }; - crnt = &(*crnt)->next; - } - *crnt = 0; - } + void ^?{}( stack(T) & s) { clear( s ); } stack(T) ?=?( stack(T) & s, stack(T) t ) { if ( s.head == t.head ) return s; @@ -2960,13 +2971,14 @@ return s; } - void ^?{}( stack(T) & s) { clear( s ); } - _Bool empty( const stack(T) & s ) { return s.head == 0; } + _Bool empty( const stack(T) & s ) { + return s.head == 0; + } void push( stack(T) & s, T value ) with( s ) { - stack_node(T) * n = alloc(); + node(T) * n = alloc(); (*n){ value, head }; head = n; } T pop( stack(T) & s ) with( s ) { - stack_node(T) * n = head; + node(T) * n = head; head = n->next; T v = n->value; @@ -2976,36 +2988,47 @@ } } -\end{comment} - -\medskip\noindent -\CC -\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt] +\end{cfa} +\end{tabular} +\lstMakeShortInline@% +\end{flushleft} + + +\subsection{\CC} + +\begin{flushleft} +\lstDeleteShortInline@% +\begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}} +\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt] template struct stack { struct node { T value; node * next; - node( const T & v, node * n = nullptr ) : value( v ), next( n ) {} + node( const T & v, node * n = nullptr ) : + value( v ), next( n ) {} }; node * head; - stack() : head( nullptr ) {} - stack( const stack & o ) { copy( o ); } + void copy( const stack & o ) { + node ** cr = &head; + for ( node * nx = o.head; nx; nx = nx->next ) { + *cr = new node{ nx->value }; /***/ + cr = &(*cr)->next; + } + *cr = nullptr; + } void clear() { - for ( node * next = head; next; ) { - node * crnt = next; - next = crnt->next; - delete crnt; + for ( node * nx = head; nx; ) { + node * cr = nx; + nx = cr->next; + delete cr; } head = nullptr; } - void copy( const stack & o ) { - node ** crnt = &head; - for ( node * next = o.head; next; next = next->next ) { - *crnt = new node{ next->value }; /***/ - crnt = &(*crnt)->next; - } - *crnt = nullptr; - } +\end{cfa} +& +\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt] + stack() : head( nullptr ) {} + stack( const stack & o ) { copy( o ); } ~stack() { clear(); } - stack & operator= ( const stack & o ) { + stack & operator=( const stack & o ) { if ( this == &o ) return *this; clear(); @@ -3013,6 +3036,10 @@ return *this; } - bool empty() const { return head == nullptr; } - void push( const T & value ) { head = new node{ value, head }; /***/ } + bool empty() const { + return head == nullptr; + } + void push( const T & value ) { + head = new node{ value, head }; /***/ + } T pop() { node * n = head; @@ -3023,36 +3050,48 @@ } }; -\end{cfa} - -\medskip\noindent -\CCV -\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt] + +\end{cfa} +\end{tabular} +\lstMakeShortInline@% +\end{flushleft} + + +\subsection{\CCV} + +\begin{flushleft} +\lstDeleteShortInline@% +\begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}} +\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt] struct stack { struct node { ptr value; node * next; - node( const object & v, node * n = nullptr ) : value( v.new_copy() ), next( n ) {} + node( const object & v, node * n = nullptr ) : + value( v.new_copy() ), next( n ) {} }; node * head; + void copy( const stack & o ) { + node ** cr = &head; + for ( node * nx = o.head; nx; nx = nx->next ) { + *cr = new node{ *nx->value }; /***/ + cr = &(*cr)->next; + } + *cr = nullptr; + } void clear() { - for ( node * next = head; next; ) { - node * crnt = next; - next = crnt->next; - delete crnt; + for ( node * nx = head; nx; ) { + node * cr = nx; + nx = cr->next; + delete cr; } head = nullptr; } - void copy( const stack & o ) { - node ** crnt = &head; - for ( node * next = o.head; next; next = next->next ) { - *crnt = new node{ *next->value }; /***/ - crnt = &(*crnt)->next; - } - *crnt = nullptr; - } +\end{cfa} +& +\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt] stack() : head( nullptr ) {} stack( const stack & o ) { copy( o ); } ~stack() { clear(); } - stack & operator= ( const stack & o ) { + stack & operator=( const stack & o ) { if ( this == &o ) return *this; clear(); @@ -3060,6 +3099,10 @@ return *this; } - bool empty() const { return head == nullptr; } - void push( const object & value ) { head = new node{ value, head }; /***/ } + bool empty() const { + return head == nullptr; + } + void push( const object & value ) { + head = new node{ value, head }; /***/ + } ptr pop() { node * n = head; @@ -3070,5 +3113,9 @@ } }; -\end{cfa} + +\end{cfa} +\end{tabular} +\lstMakeShortInline@% +\end{flushleft} Index: doc/papers/general/evaluation/c-bench.c =================================================================== --- doc/papers/general/evaluation/c-bench.c (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/general/evaluation/c-bench.c (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -5,12 +5,12 @@ #include "c-stack.h" -char* new_char( char c ) { - char* q = malloc(sizeof(char)); /***/ +char * new_char( char c ) { + char* q = malloc( sizeof(char) ); /***/ *q = c; return q; } -short* new_short( short s ) { - short* q = malloc(sizeof(short)); /***/ +short * new_short( short s ) { + short* q = malloc( sizeof(short) ); /***/ *q = s; return q; @@ -18,14 +18,14 @@ int* new_int( int i ) { - int* q = malloc(sizeof(int)); /***/ + int* q = malloc( sizeof(int) ); /***/ *q = i; return q; } -void* copy_char( const void* p ) { return new_char( *(const char*)p ); } /***/ -void* copy_short( const void* p ) { return new_short( *(const short*)p ); } /***/ -void* copy_int( const void* p ) { return new_int( *(const int*)p ); } /***/ -void* copy_pair_short_char( const void* p ) { return copy_pair( p, copy_short, copy_char ); } /***/ -void free_pair_short_char( void* p ) { free_pair( p, free, free ); } /***/ +void * copy_char( const void * p ) { return new_char( *(const char*)p ); } /***/ +void * copy_short( const void * p ) { return new_short( *(const short*)p ); } /***/ +void * copy_int( const void * p ) { return new_int( *(const int*)p ); } /***/ +void * copy_pair_short_char( const void * p ) { return copy_pair( p, copy_short, copy_char ); } /***/ +void free_pair_short_char( void * p ) { free_pair( p, free, free ); } /***/ int cmp_char( const void* a, const void* b ) { /***/ @@ -37,5 +37,5 @@ } -int main(int argc, char** argv) { +int main(int argc, char * argv[] ) { int maxi = 0, vali = 42; struct stack si = new_stack(), ti; Index: doc/papers/general/evaluation/c-pair.c =================================================================== --- doc/papers/general/evaluation/c-pair.c (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/general/evaluation/c-pair.c (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -2,25 +2,25 @@ #include "c-pair.h" -struct pair* new_pair(void* first, void* second) { - struct pair* p = malloc(sizeof(struct pair)); /***/ - *p = (struct pair){ first, second }; /***/ +pair * new_pair( void * first, void * second ) { + pair * p = malloc( sizeof(pair) ); /***/ + *p = (pair){ first, second }; /***/ return p; } -struct pair* copy_pair(const struct pair* src, - void* (*copy_first)(const void*), void* (*copy_second)(const void*)) { +pair * copy_pair( const pair * src, + void * (* copy_first)(const void* ), void * (* copy_second)(const void *)) { return new_pair( copy_first(src->first), copy_second(src->second) ); } -void free_pair(struct pair* p, void (*free_first)(void*), void (*free_second)(void*)) { - free_first(p->first); - free_second(p->second); - free(p); +void free_pair( pair * p, void (* free_first)(void *), void (* free_second)(void *)) { + free_first( p->first ); + free_second( p->second ); + free( p ); } -int cmp_pair(const struct pair* a, const struct pair* b, - int (*cmp_first)(const void*, const void*), int (*cmp_second)(const void*, const void*)) { - int c = cmp_first(a->first, b->first); - if ( c == 0 ) c = cmp_second(a->second, b->second); +int cmp_pair( const pair * a, const pair * b, + int (* cmp_first)(const void *, const void *), int (* cmp_second)(const void *, const void *)) { + int c = cmp_first( a->first, b->first ); + if ( c == 0 ) c = cmp_second( a->second, b->second ); return c; } Index: doc/papers/general/evaluation/c-pair.h =================================================================== --- doc/papers/general/evaluation/c-pair.h (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/general/evaluation/c-pair.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -1,16 +1,16 @@ #pragma once -struct pair { - void* first; - void* second; -}; +typedef struct pair { + void * first; + void * second; +} pair; -struct pair* new_pair(void* first, void* second); +pair * new_pair( void * first, void * second ); -struct pair* copy_pair(const struct pair* src, - void* (*copy_first)(const void*), void* (*copy_second)(const void*)); +pair * copy_pair( const pair * src, + void * (* copy_first)(const void *), void * (* copy_second)(const void *)); -void free_pair(struct pair* p, void (*free_first)(void*), void (*free_second)(void*)); +void free_pair( pair * p, void (* free_first)(void *), void (* free_second)(void *)); -int cmp_pair(const struct pair* a, const struct pair* b, - int (*cmp_first)(const void*, const void*), int (*cmp_second)(const void*, const void*)); +int cmp_pair( const pair * a, const pair * b, + int (* cmp_first)(const void *, const void *), int (* cmp_second)(const void *, const void *)); Index: doc/papers/general/evaluation/c-print.c =================================================================== --- doc/papers/general/evaluation/c-print.c (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/general/evaluation/c-print.c (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -4,44 +4,44 @@ #include "c-print.h" -void print_string(FILE* out, const char* x) { fprintf(out, "%s", x); } +void print_string( FILE * out, const char * x ) { fprintf( out, "%s", x ); } -void print_bool(FILE* out, _Bool x) { fprintf(out, "%s", x ? "true" : "false"); } +void print_bool( FILE * out, _Bool x ) { fprintf( out, "%s", x ? "true" : "false" ); } -void print_char(FILE* out, char x) { - if ( 0x20 <= x && x <= 0x7E ) { fprintf(out, "'%c'", x); } - else { fprintf(out, "'\\%x'", x); } +void print_char( FILE * out, char x ) { + if ( 0x20 <= x && x <= 0x7E ) { fprintf( out, "'%c'", x ); } + else { fprintf( out, "'\\%x'", x ); } } -void print_int(FILE* out, int x) { fprintf(out, "%d", x); } +void print_int( FILE * out, int x ) { fprintf( out, "%d", x ); } -void print_fmt(FILE* out, char fmt, void* p) { +void print_fmt( FILE * out, char fmt, void * p ) { switch( fmt ) { - case 's': print_string(out, (const char*)p); break; /***/ - case 'b': print_bool(out, *(_Bool*)p); break; /***/ - case 'c': print_char(out, *(char*)p); break; /***/ - case 'd': print_int(out, *(int*)p); break; /***/ + case 's': print_string( out, (const char*)p ); break; /***/ + case 'b': print_bool( out, *(_Bool*)p ); break; /***/ + case 'c': print_char( out, *(char*)p ); break; /***/ + case 'd': print_int( out, *(int*)p ); break; /***/ } } -void print(FILE* out, const char* fmt, ...) { +void print( FILE * out, const char * fmt, ... ) { va_list args; va_start(args, fmt); - for (const char* it = fmt; *it; ++it) { + for ( const char * it = fmt; *it; ++it ) { switch( *it ) { - case 's': print_string(out, va_arg(args, const char*)); break; /***/ - case 'b': print_bool(out, va_arg(args, int)); break; /***/ - case 'c': print_char(out, va_arg(args, int)); break; /***/ - case 'd': print_int(out, va_arg(args, int)); break; /***/ + case 's': print_string( out, va_arg( args, const char * ) ); break; /***/ + case 'b': print_bool( out, va_arg( args, int ) ); break; /***/ + case 'c': print_char( out, va_arg( args, int ) ); break; /***/ + case 'd': print_int( out, va_arg( args, int ) ); break; /***/ case 'p': { - const struct pair x = va_arg(args, const struct pair); /***/ - fprintf(out, "["); - print_fmt(out, *++it, x.first); /***/ - fprintf(out, ", "); - print_fmt(out, *++it, x.second); /***/ - fprintf(out, "]"); + const struct pair x = va_arg( args, const struct pair ); /***/ + fprintf( out, "[" ); + print_fmt( out, *++it, x.first ); /***/ + fprintf( out, ", " ); + print_fmt( out, *++it, x.second ); /***/ + fprintf( out, "]" ); break; } } } - va_end(args); + va_end( args ); } Index: doc/papers/general/evaluation/c-print.h =================================================================== --- doc/papers/general/evaluation/c-print.h (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/general/evaluation/c-print.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -2,8 +2,8 @@ #include -void print_string(FILE* out, const char* x); -void print_bool(FILE* out, _Bool x); -void print_char(FILE* out, char x); -void print_int(FILE* out, int x); +void print_string( FILE * out, const char * x ); +void print_bool( FILE * out, _Bool x ); +void print_char( FILE * out, char x ); +void print_int( FILE * out, int x ); -void print(FILE* out, const char* fmt, ...); +void print( FILE * out, const char * fmt, ... ); Index: doc/papers/general/evaluation/c-stack.c =================================================================== --- doc/papers/general/evaluation/c-stack.c (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/general/evaluation/c-stack.c (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -2,31 +2,34 @@ #include "c-stack.h" -struct stack_node { +typedef struct node { void * value; - struct stack_node * next; -}; + struct node * next; +} node; -void clear_stack( struct stack * s, void (*free_el)( void * ) ) { - for ( struct stack_node * next = s->head; next; ) { - struct stack_node * crnt = next; - next = crnt->next; - free_el( crnt->value ); - free( crnt ); +void copy_stack( stack * s, const stack * t, void * (*copy)( const void * ) ) { + node ** cr = &s->head; + for ( node * nx = t->head; nx; nx = nx->next ) { + *cr = malloc( sizeof(node) ); /***/ + (*cr)->value = copy( nx->value ); + cr = &(*cr)->next; + } + *cr = NULL; +} + +void clear_stack( stack * s, void (* free_el)( void * ) ) { + for ( node * nx = s->head; nx; ) { + node * cr = nx; + nx = cr->next; + free_el( cr->value ); + free( cr ); } s->head = NULL; } -struct stack new_stack() { return (struct stack){ NULL }; /***/ } +stack new_stack() { + return (stack){ NULL }; /***/ +} -void copy_stack( struct stack * s, const struct stack * t, void * (*copy)( const void * ) ) { - struct stack_node ** crnt = &s->head; - for ( struct stack_node * next = t->head; next; next = next->next ) { - *crnt = malloc( sizeof(struct stack_node) ); /***/ - (*crnt)->value = copy( next->value ); - crnt = &(*crnt)->next; - } - *crnt = NULL; -} -struct stack * assign_stack( struct stack * s, const struct stack * t, +stack * assign_stack( stack * s, const stack * t, void * (*copy_el)( const void * ), void (*free_el)( void * ) ) { if ( s->head == t->head ) return s; @@ -36,14 +39,16 @@ } -_Bool stack_empty( const struct stack * s ) { return s->head == NULL; } +_Bool stack_empty( const stack * s ) { + return s->head == NULL; +} -void push_stack( struct stack * s, void * v ) { - struct stack_node * n = malloc( sizeof(struct stack_node) ); /***/ - *n = (struct stack_node){ v, s->head }; /***/ +void push_stack( stack * s, void * v ) { + node * n = malloc( sizeof(node) ); /***/ + *n = (node){ v, s->head }; /***/ s->head = n; } -void * pop_stack( struct stack * s ) { - struct stack_node * n = s->head; +void * pop_stack( stack * s ) { + node * n = s->head; s->head = n->next; void * v = n->value; Index: doc/papers/general/evaluation/c-stack.h =================================================================== --- doc/papers/general/evaluation/c-stack.h (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/general/evaluation/c-stack.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -1,16 +1,16 @@ #pragma once -struct stack_node; -struct stack { - struct stack_node* head; -}; +struct node; +typedef struct stack { + struct node * head; +} stack; -struct stack new_stack(); -void copy_stack(struct stack* dst, const struct stack* src, void* (*copy)(const void*)); -struct stack* assign_stack(struct stack* dst, const struct stack* src, - void* (*copy_el)(const void*), void (*free_el)(void*)); -void clear_stack(struct stack* s, void (*free_el)(void*)); +void copy_stack(stack * dst, const stack * src, void * (* copy)(const void *)); +void clear_stack(stack * s, void (*free_el)(void *)); +stack new_stack(); +stack * assign_stack( stack * dst, const stack * src, + void * (* copy_el)(const void *), void (* free_el)(void *)); -_Bool stack_empty(const struct stack* s); -void push_stack(struct stack* s, void* value); -void* pop_stack(struct stack* s); +_Bool stack_empty( const stack * s ); +void push_stack( stack * s, void * value ); +void * pop_stack( stack * s ); Index: doc/papers/general/evaluation/cfa-stack.c =================================================================== --- doc/papers/general/evaluation/cfa-stack.c (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/general/evaluation/cfa-stack.c (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -2,54 +2,57 @@ #include "cfa-stack.h" -forall( otype T ) struct stack_node { - T value; - stack_node(T) * next; -}; +forall( otype T ) { + struct node { + T value; + node(T) * next; + }; -forall( otype T ) void clear( stack(T) & s ) with( s ) { - for ( stack_node(T) * next = head; next; ) { - stack_node(T) * crnt = next; - next = crnt->next; - ^(*crnt){}; - free(crnt); + void ?{}( stack(T) & s, stack(T) t ) { // copy + node(T) ** cr = &s.head; + for ( node(T) * nx = t.head; nx; nx = nx->next ) { + *cr = alloc(); + ((*cr)->value){ nx->value }; + cr = &(*cr)->next; + } + *cr = 0; } - head = 0; + + void clear( stack(T) & s ) with( s ) { + for ( node(T) * nx = head; nx; ) { + node(T) * cr = nx; + nx = cr->next; + ^(*cr){}; + free( cr ); + } + head = 0; + } + + void ?{}( stack(T) & s ) { (s.head){ 0 }; } + void ^?{}( stack(T) & s) { clear( s ); } + + stack(T) ?=?( stack(T) & s, stack(T) t ) { + if ( s.head == t.head ) return s; + clear( s ); + s{ t }; + return s; + } + + _Bool empty( const stack(T) & s ) { + return s.head == 0; + } + + void push( stack(T) & s, T value ) with( s ) { + node(T) * n = alloc(); + (*n){ value, head }; + head = n; + } + + T pop( stack(T) & s ) with( s ) { + node(T) * n = head; + head = n->next; + T v = n->value; + ^(*n){}; + free( n ); + return v; + } } - -forall( otype T ) void ?{}( stack(T) & s ) { (s.head){ 0 }; } - -forall( otype T ) void ?{}( stack(T) & s, stack(T) t ) { - stack_node(T) ** crnt = &s.head; - for ( stack_node(T) * next = t.head; next; next = next->next ) { - *crnt = alloc(); - ((*crnt)->value){ next->value }; - crnt = &(*crnt)->next; - } - *crnt = 0; -} - -forall( otype T ) stack(T) ?=?( stack(T) & s, stack(T) t ) { - if ( s.head == t.head ) return s; - clear( s ); - s{ t }; - return s; -} - -forall( otype T ) void ^?{}( stack(T) & s) { clear( s ); } - -forall( otype T ) _Bool empty( const stack(T) & s ) { return s.head == 0; } - -forall( otype T ) void push( stack(T) & s, T value ) with( s ) { - stack_node(T) * n = alloc(); - (*n){ value, head }; - head = n; -} - -forall( otype T ) T pop( stack(T) & s ) with( s ) { - stack_node(T) * n = head; - head = n->next; - T v = n->value; - ^(*n){}; - free( n ); - return v; -} Index: doc/papers/general/evaluation/cfa-stack.h =================================================================== --- doc/papers/general/evaluation/cfa-stack.h (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/general/evaluation/cfa-stack.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -1,16 +1,18 @@ #pragma once -forall( otype T ) struct stack_node; -forall( otype T ) struct stack { - stack_node(T) * head; -}; +forall( otype T ) { + struct node; + struct stack { + node(T) * head; + }; -forall( otype T ) void ?{}( stack(T) & s ); -forall( otype T ) void ?{}( stack(T) & s, stack(T) t ); -forall( otype T ) stack(T) ?=?( stack(T) & s, stack(T) t ); -forall( otype T ) void ^?{}( stack(T) & s); + void ?{}( stack(T) & s, stack(T) t ); + void clear( stack(T) & s ); + void ?{}( stack(T) & s ); + void ^?{}( stack(T) & s); -forall( otype T ) _Bool empty( const stack(T) & s ); -forall( otype T ) void push( stack(T) & s, T value ); -forall( otype T ) T pop( stack(T) & s ); -forall( otype T ) void clear( stack(T) & s ); + stack(T) ?=?( stack(T) & s, stack(T) t ); + _Bool empty( const stack(T) & s ); + void push( stack(T) & s, T value ); + T pop( stack(T) & s ); +} Index: doc/papers/general/evaluation/cpp-stack.hpp =================================================================== --- doc/papers/general/evaluation/cpp-stack.hpp (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/general/evaluation/cpp-stack.hpp (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -10,28 +10,27 @@ node * head; - stack() : head( nullptr ) {} - stack( const stack & o ) { copy( o ); } + void copy( const stack & o ) { + node ** cr = &head; + for ( node * nx = o.head; nx; nx = nx->next ) { + *cr = new node{ nx->value }; /***/ + cr = &(*cr)->next; + } + *cr = nullptr; + } void clear() { - for ( node * next = head; next; ) { - node * crnt = next; - next = crnt->next; - delete crnt; + for ( node * nx = head; nx; ) { + node * cr = nx; + nx = cr->next; + delete cr; } head = nullptr; } - void copy( const stack & o ) { - node ** crnt = &head; - for ( node * next = o.head; next; next = next->next ) { - *crnt = new node{ next->value }; /***/ - crnt = &(*crnt)->next; - } - *crnt = nullptr; - } - + stack() : head( nullptr ) {} + stack( const stack & o ) { copy( o ); } ~stack() { clear(); } - stack & operator= ( const stack & o ) { + stack & operator=( const stack & o ) { if ( this == &o ) return *this; clear(); @@ -40,7 +39,11 @@ } - bool empty() const { return head == nullptr; } + bool empty() const { + return head == nullptr; + } - void push( const T & value ) { head = new node{ value, head }; /***/ } + void push( const T & value ) { + head = new node{ value, head }; /***/ + } T pop() { Index: doc/papers/general/evaluation/cpp-vstack.cpp =================================================================== --- doc/papers/general/evaluation/cpp-vstack.cpp (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/general/evaluation/cpp-vstack.cpp (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -4,20 +4,20 @@ stack::node::node( const object & v, node * n ) : value( v.new_copy() ), next( n ) {} +void stack::copy( const stack & o ) { + node ** cr = &head; + for ( node * nx = o.head; nx; nx = nx->next ) { + *cr = new node{ *nx->value }; /***/ + cr = &(*cr)->next; + } + *cr = nullptr; +} + void stack::clear() { - for ( node * next = head; next; ) { - node * crnt = next; - next = crnt->next; - delete crnt; + for ( node * nx = head; nx; ) { + node * cr = nx; + nx = cr->next; + delete cr; } head = nullptr; -} - -void stack::copy( const stack & o ) { - node ** crnt = &head; - for ( node * next = o.head; next; next = next->next ) { - *crnt = new node{ *next->value }; /***/ - crnt = &(*crnt)->next; - } - *crnt = nullptr; } @@ -33,7 +33,11 @@ } -bool stack::empty() const { return head == nullptr; } +bool stack::empty() const { + return head == nullptr; +} -void stack::push( const object & value ) { head = new node{ value, head }; /***/ } +void stack::push( const object & value ) { + head = new node{ value, head }; /***/ +} ptr stack::pop() { Index: doc/papers/general/evaluation/cpp-vstack.hpp =================================================================== --- doc/papers/general/evaluation/cpp-vstack.hpp (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/general/evaluation/cpp-vstack.hpp (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -10,6 +10,6 @@ node * head; + void copy( const stack & o ); void clear(); - void copy( const stack & o ); stack(); Index: doc/papers/general/evaluation/timing.dat =================================================================== --- doc/papers/general/evaluation/timing.dat (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/general/evaluation/timing.dat (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -1,9 +1,10 @@ "400 million repetitions" "C" "\\CFA{}" "\\CC{}" "\\CC{obj}" -"push\nint" 3002 2459 1542 3269 -"copy\nint" 2985 2057 1539 3083 -"clear\nint" 1374 827 756 1469 -"pop\nint" 1416 1221 760 5098 -"push\npair" 4214 2752 950 6873 -"copy\npair" 6127 2105 987 7293 -"clear\npair" 2881 885 751 3460 -"pop\npair" 3046 5434 822 24962 +"push\nint" 2911 2034 1504 3246 +"copy\nint" 2953 1622 1526 3075 +"clear\nint" 1397 754 753 1452 +"pop\nint" 1446 1203 760 5016 +"push\npair" 3673 2297 955 6971 +"copy\npair" 6027 1183 998 7204 +"clear\npair" 2840 773 748 3511 +"pop\npair" 3025 5414 813 23867 + Index: doc/papers/general/evaluation/timing.gp =================================================================== --- doc/papers/general/evaluation/timing.gp (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/papers/general/evaluation/timing.gp (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -24,6 +24,6 @@ set yrange [0:10] -set label "25.0" at 7.125,10.5 - +set label "23.9" at 7.125,10.5 +set style fill pattern 4 border lt -1 # set datafile separator "," plot for [COL=2:5] 'evaluation/timing.dat' using (column(COL)/SCALE):xticlabels(1) title columnheader Index: doc/papers/general/response =================================================================== --- doc/papers/general/response (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) +++ doc/papers/general/response (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -0,0 +1,379 @@ +Date: Thu, 19 Apr 2018 17:01:14 -0400 (EDT) +From: "Software: Practice and Experience" +Reply-To: judithbishop@outlook.com +To: a3moss@uwaterloo.ca, rschlunt@uwaterloo.ca, pabuhr@uwaterloo.ca +Subject: Software: Practice and Experience - Decision on Manuscript ID SPE-18-0065 + +19-Apr-2018 + +Dear Dr Buhr, + +Many thanks for submitting SPE-18-0065 entitled "Cforall : Adding Modern Programming +Language Features to C" to Software: Practice and Experience. The paper has now +been reviewed and the comments of the referee(s) are included at the bottom of +this letter. + +I am delighted to inform you that the referee(s) have recommended publication, +but also suggest some minor revisions to your manuscript. Therefore, I invite +you to respond to the referee(s)' comments and revise your manuscript. All of +the referees' comments are important, but I would like you to pay special +attention to the following general points: + +1. If there is any more evaluation that a stack, please add it. +2. How is the compiler implemented? +3. What features are actually implemented? +4. The article lacks some related work. such as Haskell, ML etc. +5. Most of the content in Section 10 RELATED WORK appears to belong to Section 1 INTRODUCTION as a Subsection or as a new Section after Section 1. +6. Many references are not properly formatted +7. A statement about any presence or absence of conflicts of interest with Huawei should be explicitly added. + +The paper is long by SPE standards (33 pages). We have a maximum of 40 +pages. Please do not extend the paper beyond 35 pages. If necessary, find ways +to cut the examples or text. If you have an accompanying website for the system +where some examples are stored, please mention it. + +You have 42 days from the date of this email to submit your revision. If you +are unable to complete the revision within this time, please contact me to +request a short extension. + +You can upload your revised manuscript and submit it through your Author +Center. Log into https://mc.manuscriptcentral.com/spe and enter your Author +Center, where you will find your manuscript title listed under "Manuscripts +with Decisions". + +When submitting your revised manuscript, you will be able to respond to the +comments made by the referee(s) in the space provided. You can use this space +to document any changes you make to the original manuscript. + +If you feel that your paper could benefit from English language polishing, you +may wish to consider having your paper professionally edited for English +language by a service such as Wiley's at +http://wileyeditingservices.com. Please note that while this service will +greatly improve the readability of your paper, it does not guarantee acceptance +of your paper by the journal. + +Once again, thank you for submitting your manuscript to Software: Practice and Experience. I look forward to receiving your revision. + +Sincerely, + +Dr Judith Bishop +Editor, Software: Practice and Experience +judithbishop@outlook.com + + +We have attempted to response to all the issues raised by the Editor and referee's comments. For two +of the issues, we have "pushed back", with an explanation. Specifically, moving the related work +forward, and moving text from Section 9 into the captions of Table2 and Figure 10. Our reasons for +not making these changes are address below. Finally, as pointed out below, there are a couple of +issues with the Wiley LaTeX macros that we worked around as best as possible. + + The paper is long by SPE standards (33 pages). We have a maximum of 40 pages. Please do not + extend the paper beyond 35 pages. If necessary, find ways to cut the examples or text. If you + have an accompanying website for the system where some examples are stored, please mention it. + +The paper is 35 pages using the supplied Wiley LaTeX macros. + + +Referee(s)' Comments to Author: + +Reviewing: 1 + + Most of the content in Section 10 RELATED WORK appears to belong to Section 1 INTRODUCTION as a + Subsection or as a new Section after Section 1. (Please also see #4.1 below.) Remaining + discussion that cannot be moved earlier can become a DISCUSSION Section or a Subsection within + the last Section of the paper. + +Sometimes it is appropriate to put related work at the start of a paper and sometimes at the +end. For this paper, it seems appropriate to put the related work at the end of the paper. The +purpose of the related work in this paper is two fold: to introduce prior work and to contrast it +with Cforall. Only at the end of the paper does the reader have sufficient knowledge about Cforall +to make detailed contrasts with other programming languages possible. If the related work is moved +to the end of the introduction, the reader knows nothing about Cforall so talking about other +programming languages in isolation makes little sense, especially non-C-related languages, like +Java, Go, Rust, Haskell. We see no easy way to separate the related work into a general discussion +at the start and a specific discussion at the end. We explicitly attempt to deal with the reader's +anticipation at the end of the introduction: + + Finally, it is impossible to describe a programming language without usages before definitions. + Therefore, syntax and semantics appear before explanations; hence, patience is necessary until + details are presented. + + + 2.1 More information should be moved from the text and added to Figure 10 and Table 2 so that + readers can understand the comparison quickly. Imagine a reader read the summary and jump + directly to these two display elements. Questions would be raised about the binary size and pop + pair result of Cforall and it would take time to find answers in the text. + +This suggestion is an alternative writing style. The experiment is complex enough that it is +unlikely a reader could jump to the table/graph and understand the experiment without putting a +substantive amount of the text from Section 9 into the table and figure, which the reader then has +to read anyway. In fact, we prefer a writing style where the reader does not have to look at the +table/figure to understand the experiment and the results, i.e., the table/figure are only there to +complement the discussion. + + + 2.2 The pronunciation of ("C-for-all") should be provided in the summary (page 1 line 22) so that + people not having an access to the full-text can see it. + +Done. + + + 2.3 Error comment in the code should be written with the same capitalization and it will be + helpful if you say specifically compilation error or runtime error. (Please see attached + annotated manuscript.) + +Fixed. All errors in the paper are compilation errors because they are related to the type system. + + + 2.4 It is possible to provide a bit more information in Appendix A e.g. how many lines/bytes of + code and some details about software/hardware can be added/moved here. The aim is to provide + sufficient information for readers to reproduce the results and to appreciate the context of the + comparison. + +Table 2 indicates the source-code size in lines of code. The third paragraph of Section 9 gives +precise details of the software/hardware used in the experiments. + + 3. Practical information about the work + + There are three separate pieces of information on pages 2 ("All features discussed in this paper + are working, unless otherwise stated as under construction."), + +This sentence is replace with: + + All languages features discussed in this paper are working, except some advanced exception-handling + features. + +and Section 5.4 Exception Handling states: + + The following framework for Cforall exception handling is in place, excluding some runtime + type-information and virtual functions. + + + page 4 ("Under construction is a mechanism to distribute...") + +The feature on page 4 is now complete. + + + and page 33 ("There is ongoing work on a wide range ... ") + +This sentence is replace to indicate the ongoing work is future work. + + While all examples in the paper compile and run, a public beta-release of Cforall will take 6-8 + months to reduce compilation time, provide better debugging, and add a few more libraries. There + is also new work on a number of Cforall features, including arrays with size, runtime + type-information, virtual functions, user-defined conversions, and modules. + + + My recommendation is to move them to an appendix so that the length is preserved. + +There is nothing to move into an appendix, except 3 sentences. We do not intend to discuss these +items in this paper. + + + 3.1 Any under construction work (only small part of page 4) should not be mingled into the main + part of the manuscript. + +See above. + + + 3.2 Instructions on how to access/use the working functionality of Cforall should be given. + +We will indicate release of Cforall in a public location, when we believe the code base is +acceptable. In the interim, we have made public all the experimental code from section 9, and there +is a reference in the paper to access this code. We can make a private beta-copy of Cforall +available to the SP&E editor for distribution to the referees so they can verify our claims. + + 3.3 Planned work should be given a specific time of completion/release not just "8-12 months". + +Software development is not a rigorous engineering discipline. Given our small research +development-team and the size of the project, we cannot give a specific time for completion of +anything associated with the project. Having said that, we have reduced our expected time for +Cforall release to 6-8 months as work is progressing well. + + + 4.1 The impression after reading Section 1 INTRODUCTION is that the referencing is poor. It is + not until Section 10 RELATED WORK where majority of the prior literature are discussed. Please + consider moving the content and improve citations - at least cite all main variations of C + languages. + +See point 1. + + + 4.2 I also would like to see citations at these specific places: Page 2 after Phil Karlton, page + 22 after const hell problem. + +The Phil-Karlton quote is an urban legend without a specific academic citation: + + https://skeptics.stackexchange.com/questions/19836/has-phil-karlton-ever-said-there-are-only-two-hard-things-in-computer-science + +The term "const hell" is replaced with "const poisoning" with a citation. + + + 5.1 Footnotes and citations will need to have different schemes - number and perhaps letter. + +Switched to letters. SP&E uses symbol footnotes but this macros fails with their macros: + + \renewcommand*{\thefootnote}{\fnsymbol{footnote}} + + + 5.2 Many references are not properly formatted e.g. date is incomplete, extra/missing white + spaces, extra dots, use of page number or section number as part of superscript ref + number. Please refer to attached document. + +Agreed. The bibtex BST macros are at fault. I have fixed some issues but I cannot fix them all as my +BST macro-knowledge is limited. + + + 5.3 Typos: + - Page 3 "eager" should be "earlier" + +Fixed. + + - Page 4 "vals" should be "arr" + +Actually it is "vals", and the example is changed so it is clear why. + + - Page 21 "than" should be "then" + +Fixed. + + + 6. Conflict of interest + I see that the work is partially supported by Huawei. Perhaps statement about any presence or + absence of conflicts of interest should be explicitly added. Please get a clear direction on this + from the editor of the journal. + +The paper now states the project is open-source, hence there is no conflict of interest with the +funding received from Huawei. + + +Reviewing: 2 + +Comments to the Author + + Overloading requires the compiler to mangle a function's signature into its name in the object + file. I'm pretty sure that this will complicate the build process of mixed Cforall/C projects. + +There is no complexity with building Cforall/C programs, and there is an existence proof because C++ +has name mangling for overloading and has no problem interacting with C. + + + I found the evaluation underwhelming. There were only ~200 LoC ported from C to Cforall. This + is too less to encounter potential caveats Cforall's type system might impose. + +We have clarified that the evaluation is not for the type system, but rather the underlying +implementation approach for the parametric polymorphism. Section 9 now starts: + + Cforall adds parametric polymorphism to C. A runtime evaluation is performed to compare the cost + of alternative styles of polymorphism. The goal is to compare just the underlying mechanism for + implementing different kinds of polymorphism. + +and ends with: + + We conjecture these results scale across most generic data-types as the underlying polymorphic + implement is constant. + + + Also, how is the compiler implemented? I guess, Cforall is a source-to-source compiler (from + Cforall to C). But this is left in the dark. What features are actually implemented? + +The following paragraph has been added to the introduction to address this comment: + + All languages features discussed in this paper are working, except some advanced exception-handling + features. Not discussed in this paper are the integrated concurrency-constructs and user-level + threading-library~\cite{Delisle18}. Cforall is an open-source project implemented as an + source-to-source translator from Cforall to the gcc-dialect of C~\cite{GCCExtensions}, allowing it + to leverage the portability and code optimizations provided by gcc, meeting goals (1)--(3). + Ultimately, a compiler is necessary for advanced features and optimal performance. The Cforall + translator is 200+ files and 46,000+ lines of code written in C/C++. Starting with a translator + versus a compiler makes it easier and faster to generate and debug C object-code rather than + intermediate, assembler or machine code. The translator design is based on the visitor pattern, + allowing multiple passes over the abstract code-tree, which works well for incrementally adding new + feature through additional visitor passes. At the heart of the translator is the type resolver, + which handles the polymorphic routine/type overload-resolution. The Cforall runtime system is 100+ + files and 11,000+ lines of code, written in Cforall. Currently, the Cforall runtime is the largest + user of Cforall providing a vehicle to test the language features and implementation. The Cforall + tests are 290+ files and 27,000+ lines of code. The tests illustrate syntactic and semantic + features in Cforall, plus a growing number of runtime benchmarks. The tests check for correctness + and are used for daily regression testing of commits (3800+). + + + Furthermore, the article lacks some related work. Many proposed features are present in + functional languages such as Haskell, ML etc. In particular, the dealing of parametric + polymorphism reminds me of Haskell. + +The following paragraph has been added at the start of Section 10.1: + + ML~\cite{ML} was the first language to support parametric polymorphism. Like Cforall, it supports + universal type parameters, but not the use of assertions and traits to constrain type arguments. + Haskell~\cite{Haskell10} combines ML-style polymorphism, polymorphic data types, and type inference + with the notion of type classes, collections of overloadable methods that correspond in intent to + traits in Cforall. Unlike Cforall, Haskell requires an explicit association between types and + their classes that specifies the implementation of operations. These associations determine the + functions that are assertion arguments for particular combinations of class and type, in contrast + to Cforall where the assertion arguments are selected at function call sites based upon the set of + operations in scope at that point. Haskell also severely restricts the use of overloading: an + overloaded name can only be associated with a single class, and methods with overloaded names can + only be defined as part of instance declarations. + + + Cforall's approach to tuples is also quite similar to many functional languages. + +At the end of Section 10.2, we state: + + Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML, + Haskell}, and Scala, which decompose tuples using pattern matching. + + +From: Judith Bishop +To: "Peter A. Buhr" +Subject: RE: Software: Practice and Experience - Decision on Manuscript ID + SPE-18-0065 +Date: Tue, 24 Apr 2018 16:45:51 +0000 +Accept-Language: em-US + +Hi Peter + +Great to hear from you. I am also glad your paper got through, as it is in the +mainline of the SPE scope. + +It is important to mention that the software is open source. People really +value that. In the acknowledgements, you can refer to Huawei for funding. It is +quite normal to have industrial funding, and in fact it is a plus. + +I think that sorts out the comment from the referee. + +Looking forward to your revised submission. + +Kind regards + +Judith Bishop +Extraordinary Professor, Computer Science +Stellenbosch University, South Africa +082 301 5220 / 021 671 5133 +judithbishop@outlook.com LinkedIn + +-----Original Message----- +From: Peter A. Buhr +Sent: Tuesday, April 24, 2018 6:25 PM +To: judithbishop@outlook.com +Cc: a3moss@uwaterloo.ca; rschlunt@uwaterloo.ca +Subject: Re: Software: Practice and Experience - Decision on Manuscript ID SPE-18-0065 + +Hi Judy! Hope all is well. + +We are over-the-moon to get our paper accepted at SP&E, and we are actively +working on your and the referee's comments. + +One comment where we need assistance is: + + 7. A statement about any presence or absence of conflicts of interest with + Huawei should be explicitly added. + +We forgotten to mention in the paper that our project is open-source. So Huawei +was funding an open-source project. In fact, the Huawei funding ends soon, so +there will be no direct affiliation in a couple of months, although there are a +few people at Huawei who remain very interested in the project. + +So does stating that the Cforall project is an open-source project deal with +the issue of conflict of interest? Index: doc/refrat/Makefile =================================================================== --- doc/refrat/Makefile (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/refrat/Makefile (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -34,4 +34,5 @@ DOCUMENT = refrat.pdf +BASE = ${basename ${DOCUMENT}} # Directives # @@ -42,15 +43,15 @@ clean : - @rm -frv ${DOCUMENT} ${basename ${DOCUMENT}}.ps ${Build} + @rm -frv ${DOCUMENT} ${BASE}.ps ${Build} # File Dependencies # -${DOCUMENT} : ${basename ${DOCUMENT}}.ps +${DOCUMENT} : ${BASE}.ps ps2pdf $< -${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi +${BASE}.ps : ${BASE}.dvi dvips ${Build}/$< -o $@ -${basename ${DOCUMENT}}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ +${BASE}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ ${Macros}/common.tex ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run. @@ -70,5 +71,5 @@ predefined : - sed -f predefined.sed ${basename ${DOCUMENT}}.tex > ${basename $@}.cf + sed -f predefined.sed ${BASE}.tex > ${basename $@}.cf ## Define the default recipes. @@ -77,11 +78,11 @@ mkdir -p ${Build} -%.tex : %.fig +%.tex : %.fig ${Build} fig2dev -L eepic $< > ${Build}/$@ -%.ps : %.fig +%.ps : %.fig ${Build} fig2dev -L ps $< > ${Build}/$@ -%.pstex : %.fig +%.pstex : %.fig ${Build} fig2dev -L pstex $< > ${Build}/$@ fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t Index: doc/user/Makefile =================================================================== --- doc/user/Makefile (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/user/Makefile (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -38,4 +38,5 @@ DOCUMENT = user.pdf +BASE = ${basename ${DOCUMENT}} # Directives # @@ -46,15 +47,15 @@ clean : - @rm -frv ${DOCUMENT} ${basename ${DOCUMENT}}.ps ${Build} + @rm -frv ${DOCUMENT} ${BASE}.ps ${Build} # File Dependencies # -${DOCUMENT} : ${basename ${DOCUMENT}}.ps +${DOCUMENT} : ${BASE}.ps ps2pdf $< -${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi +${BASE}.ps : ${BASE}.dvi dvips ${Build}/$< -o $@ -${basename ${DOCUMENT}}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ +${BASE}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ ${Macros}/common.tex ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run. @@ -78,11 +79,11 @@ mkdir -p ${Build} -%.tex : %.fig +%.tex : %.fig ${Build} fig2dev -L eepic $< > ${Build}/$@ -%.ps : %.fig +%.ps : %.fig ${Build} fig2dev -L ps $< > ${Build}/$@ -%.pstex : %.fig +%.pstex : %.fig ${Build} fig2dev -L pstex $< > ${Build}/$@ fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t Index: doc/user/user.tex =================================================================== --- doc/user/user.tex (revision f6f0cca3f172613989f420c40761026fe191b651) +++ doc/user/user.tex (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -11,6 +11,6 @@ %% Created On : Wed Apr 6 14:53:29 2016 %% Last Modified By : Peter A. Buhr -%% Last Modified On : Sat Apr 14 19:04:30 2018 -%% Update Count : 3318 +%% Last Modified On : Sun May 6 10:33:53 2018 +%% Update Count : 3319 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -1642,5 +1642,5 @@ \begin{itemize} \item -if ©R© is an \Index{rvalue} of type ©T &$_1$...&$_r$© where $r \ge 1$ references (©&© symbols) than ©&R© has type ©T ®*®&$_{\color{red}2}$...&$_{\color{red}r}$©, \ie ©T© pointer with $r-1$ references (©&© symbols). +if ©R© is an \Index{rvalue} of type ©T &$_1$...&$_r$© where $r \ge 1$ references (©&© symbols) then ©&R© has type ©T ®*®&$_{\color{red}2}$...&$_{\color{red}r}$©, \ie ©T© pointer with $r-1$ references (©&© symbols). \item Index: src/CodeGen/CodeGenerator.cc =================================================================== --- src/CodeGen/CodeGenerator.cc (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/CodeGen/CodeGenerator.cc (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -10,6 +10,6 @@ // Created On : Mon May 18 07:44:20 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Sun Sep 3 20:42:52 2017 -// Update Count : 490 +// Last Modified On : Sat May 5 09:08:32 2018 +// Update Count : 494 // #include "CodeGenerator.h" @@ -370,5 +370,5 @@ void CodeGenerator::postvisit( Constant * constant ) { - output << constant->get_value() ; + output << constant->get_value(); } @@ -587,5 +587,5 @@ output << "("; if ( castExpr->get_result()->isVoid() ) { - output << "(void)" ; + output << "(void)"; } else { // at least one result type of cast. @@ -878,5 +878,5 @@ } // for } // if - output << " );" ; + output << " );"; } @@ -886,5 +886,9 @@ output << "( "; if ( asmStmt->get_instruction() ) asmStmt->get_instruction()->accept( *visitor ); - output << " )" ; + output << " )"; + } + + void CodeGenerator::postvisit( DirectiveStmt * dirStmt ) { + output << endl << dirStmt->directive; // endl prevents spaces before directive } @@ -903,5 +907,5 @@ void CodeGenerator::postvisit( SwitchStmt * switchStmt ) { - output << "switch ( " ; + output << "switch ( "; switchStmt->get_condition()->accept( *visitor ); output << " ) "; @@ -929,5 +933,5 @@ ++indent; for ( std::list::iterator i = sts.begin(); i != sts.end(); i++) { - output << indent << printLabels( (*i)->get_labels() ) ; + output << indent << printLabels( (*i)->get_labels() ) ; (*i)->accept( *visitor ); output << endl; @@ -1066,7 +1070,7 @@ void CodeGenerator::postvisit( WhileStmt * whileStmt ) { if ( whileStmt->get_isDoWhile() ) { - output << "do" ; - } else { - output << "while (" ; + output << "do"; + } else { + output << "while ("; whileStmt->get_condition()->accept( *visitor ); output << ")"; @@ -1080,5 +1084,5 @@ if ( whileStmt->get_isDoWhile() ) { - output << " while (" ; + output << " while ("; whileStmt->get_condition()->accept( *visitor ); output << ");"; Index: src/CodeGen/CodeGenerator.h =================================================================== --- src/CodeGen/CodeGenerator.h (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/CodeGen/CodeGenerator.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -99,4 +99,5 @@ void postvisit( ExprStmt * ); void postvisit( AsmStmt * ); + void postvisit( DirectiveStmt * ); void postvisit( AsmDecl * ); // special: statement in declaration context void postvisit( IfStmt * ); Index: src/CodeGen/FixNames.cc =================================================================== --- src/CodeGen/FixNames.cc (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/CodeGen/FixNames.cc (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -55,5 +55,5 @@ auto && name = SymTab::Mangler::mangle( mainDecl ); // std::cerr << name << std::endl; - return name; + return std::move(name); } std::string mangle_main_args() { @@ -78,5 +78,5 @@ auto&& name = SymTab::Mangler::mangle( mainDecl ); // std::cerr << name << std::endl; - return name; + return std::move(name); } Index: src/Common/Heap.cc =================================================================== --- src/Common/Heap.cc (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) +++ src/Common/Heap.cc (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -0,0 +1,187 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2018 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Heap.cc -- +// +// Author : Thierry Delisle +// Created On : Thu May 3 16:16:10 2018 +// Last Modified By : Peter A. Buhr +// Last Modified On : Fri May 4 17:27:31 2018 +// Update Count : 28 +// + +#include +#include +#include +#include +#include +#include + +//#define WITH_HEAP_STATISTICS + +namespace HeapStats { +#if !defined( WITH_HEAP_STATISTICS ) + void newPass( const char * const ) {} + + void printStats() {} +#else + struct StatBlock { + const char * name = nullptr; + size_t mallocs = 0; + size_t frees = 0; + }; + + StatBlock passes[100] = {{ "Pre-Parse", 0, 0 }}; + const size_t passes_size = sizeof(passes) / sizeof(passes[0]); + size_t passes_cnt = 1; + + void newPass( const char * const name ) { + passes[passes_cnt].name = name; + passes[passes_cnt].mallocs = 0; + passes[passes_cnt].frees = 0; + passes_cnt++; + + assertf(passes_cnt < passes_size, "Too many passes for HeapStats, increase the size of the array in Heap.h"); + } + + void print(size_t value, size_t total) { + std::cerr << std::setw(12) << value; + std::cerr << "(" << std::setw(3); + std::cerr << (value == 0 ? 0 : value * 100 / total); + std::cerr << "%) | "; + } + + void print(const StatBlock& stat, size_t nc, size_t total_mallocs, size_t total_frees) { + std::cerr << std::setw(nc) << stat.name; + std::cerr << " | "; + + print(stat.mallocs, total_mallocs); + print(stat.frees , total_frees ); + std::cerr << "\n"; + } + + void print(char c, size_t nc) { + for(size_t i = 0; i < nc; i++) { + std::cerr << c; + } + std::cerr << '\n'; + } + + void printStats() { + size_t nc = 0; + size_t total_mallocs = 0; + size_t total_frees = 0; + for(size_t i = 0; i < passes_cnt; i++) { + nc = std::max(nc, std::strlen(passes[i].name)); + total_mallocs += passes[i].mallocs; + total_frees += passes[i].frees; + } + size_t nct = nc + 44; + + const char * const title = "Heap Usage Statistic"; + print('=', nct); + for(size_t i = 0; i < (nct - std::strlen(title)) / 2; i++) std::cerr << ' '; + std::cerr << title << std::endl; + print('-', nct); + std::cerr << std::setw(nc) << "Pass"; + std::cerr << " | Malloc Count | Free Count |" << std::endl; + + print('-', nct); + for(size_t i = 0; i < passes_cnt; i++) { + print(passes[i], nc, total_mallocs, total_frees); + } + print('-', nct); + print({"Sum", total_mallocs, total_frees}, nc, total_mallocs, total_frees); + + } + +#include +#include +#include +#include +#include +#include + extern "C" { +#include +#include + } + +//============================================================================================= +// Interposing helpers +//============================================================================================= + + typedef void (* generic_fptr_t)(void); + generic_fptr_t interpose_symbol( const char * symbol, const char * version ) { + const char * error; + + static void * library; + if ( ! library ) { +#if defined( RTLD_NEXT ) + library = RTLD_NEXT; +#else + // missing RTLD_NEXT => must hard-code library name, assuming libstdc++ + library = dlopen( "libc.so.6", RTLD_LAZY ); + error = dlerror(); + if ( error ) { + std::cerr << "interpose_symbol : failed to open libc, " << error << std::endl; + abort(); + } +#endif // RTLD_NEXT + } // if + + generic_fptr_t fptr; + +#if defined( _GNU_SOURCE ) + if ( version ) { + fptr = (generic_fptr_t)dlvsym( library, symbol, version ); + } else { + fptr = (generic_fptr_t)dlsym( library, symbol ); + } +#else + fptr = (generic_fptr_t)dlsym( library, symbol ); +#endif // _GNU_SOURCE + + error = dlerror(); + if ( error ) { + std::cerr << "interpose_symbol : internal error, " << error << std::endl; + abort(); + } + + return fptr; + } + + extern "C" { + void * malloc( size_t size ) __attribute__((malloc)); + void * malloc( size_t size ) { + static auto __malloc = reinterpret_cast(interpose_symbol( "malloc", nullptr )); + if( passes_cnt > 0 ) passes[passes_cnt - 1].mallocs++; + return __malloc( size ); + } + + void free( void * ptr ) { + static auto __free = reinterpret_cast(interpose_symbol( "free", nullptr )); + if( passes_cnt > 0 ) passes[passes_cnt - 1].frees++; + return __free( ptr ); + } + + void * calloc( size_t nelem, size_t size ) { + static auto __calloc = reinterpret_cast(interpose_symbol( "calloc", nullptr )); + if( passes_cnt > 0 ) passes[passes_cnt - 1].mallocs++; + return __calloc( nelem, size ); + } + + void * realloc( void * ptr, size_t size ) { + static auto __realloc = reinterpret_cast(interpose_symbol( "realloc", nullptr )); + void * s = __realloc( ptr, size ); + if ( s != ptr && passes_cnt > 0 ) { // did realloc get new storage ? + passes[passes_cnt - 1].mallocs++; + passes[passes_cnt - 1].frees++; + } // if + return s; + } + } +#endif +} Index: src/Common/Heap.h =================================================================== --- src/Common/Heap.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) +++ src/Common/Heap.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -0,0 +1,21 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2018 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Heap.h -- +// +// Author : Thierry Delisle +// Created On : Thu May 3 16:16:10 2018 +// Last Modified By : Peter A. Buhr +// Last Modified On : Fri May 4 14:34:08 2018 +// Update Count : 3 +// + +#pragma once + +namespace HeapStats { + void newPass( const char * const name ); + void printStats(); +} Index: src/Common/PassVisitor.h =================================================================== --- src/Common/PassVisitor.h (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/Common/PassVisitor.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -71,4 +71,5 @@ virtual void visit( ExprStmt * exprStmt ) override final; virtual void visit( AsmStmt * asmStmt ) override final; + virtual void visit( DirectiveStmt * dirStmt ) override final; virtual void visit( IfStmt * ifStmt ) override final; virtual void visit( WhileStmt * whileStmt ) override final; @@ -170,4 +171,5 @@ virtual Statement * mutate( ExprStmt * exprStmt ) override final; virtual Statement * mutate( AsmStmt * asmStmt ) override final; + virtual Statement * mutate( DirectiveStmt * dirStmt ) override final; virtual Statement * mutate( IfStmt * ifStmt ) override final; virtual Statement * mutate( WhileStmt * whileStmt ) override final; Index: src/Common/PassVisitor.impl.h =================================================================== --- src/Common/PassVisitor.impl.h (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/Common/PassVisitor.impl.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -690,6 +690,6 @@ VISIT_START( node ); - maybeAccept_impl( node->condition, *this ); - maybeAccept_impl( node->message , *this ); + node->condition = visitExpression( node->condition ); + maybeAccept_impl( node->message, *this ); VISIT_END( node ); @@ -700,6 +700,6 @@ MUTATE_START( node ); - maybeMutate_impl( node->condition, *this ); - maybeMutate_impl( node->message , *this ); + node->condition = mutateExpression( node->condition ); + maybeMutate_impl( node->message, *this ); MUTATE_END( StaticAssertDecl, node ); @@ -772,4 +772,20 @@ maybeMutate_impl( node->input, *this ); maybeMutate_impl( node->clobber, *this ); + + MUTATE_END( Statement, node ); +} + +//-------------------------------------------------------------------------- +// AsmStmt +template< typename pass_type > +void PassVisitor< pass_type >::visit( DirectiveStmt * node ) { + VISIT_START( node ) + + VISIT_END( node ); +} + +template< typename pass_type > +Statement * PassVisitor< pass_type >::mutate( DirectiveStmt * node ) { + MUTATE_START( node ); MUTATE_END( Statement, node ); Index: src/Common/PassVisitor.proto.h =================================================================== --- src/Common/PassVisitor.proto.h (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/Common/PassVisitor.proto.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -47,5 +47,5 @@ operator bool() { return m_ref ? *m_ref : true; } - bool operator=( bool val ) { return *m_ref = val; } + bool operator=( bool val ) { assert(m_ref); return *m_ref = val; } private: @@ -53,7 +53,7 @@ friend class ChildrenGuard; - bool * set( bool & val ) { + bool * set( bool * val ) { bool * prev = m_ref; - m_ref = &val; + m_ref = val; return prev; } @@ -67,5 +67,5 @@ ChildrenGuard( bool_ref * ref ) : m_val ( true ) - , m_prev( ref ? ref->set( m_val ) : nullptr ) + , m_prev( ref ? ref->set( &m_val ) : nullptr ) , m_ref ( ref ) {} @@ -73,5 +73,5 @@ ~ChildrenGuard() { if( m_ref ) { - m_ref->set( *m_prev ); + m_ref->set( m_prev ); } } Index: src/Common/SemanticError.cc =================================================================== --- src/Common/SemanticError.cc (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/Common/SemanticError.cc (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -7,20 +7,68 @@ // SemanticError.cc -- // -// Author : Richard C. Bilson +// Author : Thierry Delisle // Created On : Mon May 18 07:44:20 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Tue Aug 29 18:17:35 2017 -// Update Count : 3 +// Last Modified On : Wed May 16 15:01:20 2018 +// Update Count : 9 // #include #include // for fileno, stderr +#include #include // for isatty #include // for basic_ostream, operator<<, ostream #include // for list, _List_iterator #include // for string, operator<<, operator+, to_string +#include #include "Common/utility.h" // for to_string, CodeLocation (ptr only) #include "SemanticError.h" + +//----------------------------------------------------------------------------- +// Severity Handling +std::vector & get_severities() { + static std::vector severities; + if(severities.empty()) { + severities.reserve((size_t)Warning::NUMBER_OF_WARNINGS); + for ( const auto w : WarningFormats ) { + severities.push_back( w.default_severity ); + } // for + } + return severities; +} + +void SemanticWarning_SuppressAll() { + for( auto & s : get_severities() ) { + s = Severity::Suppress; + } +} + +void SemanticWarning_EnableAll() { + for( auto & s : get_severities() ) { + s = Severity::Warn; + } +} + +void SemanticWarning_WarningAsError() { + for( auto & s : get_severities() ) { + if(s == Severity::Warn) s = Severity::Error; + } +} + +void SemanticWarning_Set(const char * const name, Severity s) { + size_t idx = 0; + for ( const auto & w : WarningFormats ) { + if ( std::strcmp( name, w.name ) == 0 ) { + get_severities()[idx] = s; + break; + } + idx++; + } +} + +//----------------------------------------------------------------------------- +// Semantic Error +bool SemanticErrorThrow = false; SemanticErrorException::SemanticErrorException( CodeLocation location, std::string error ) { @@ -48,4 +96,5 @@ void SemanticError( CodeLocation location, std::string error ) { + SemanticErrorThrow = true; throw SemanticErrorException(location, error); } @@ -69,5 +118,5 @@ void SemanticWarningImpl( CodeLocation location, Warning warning, const char * const fmt, ... ) { - Severity severity = WarningFormats[(int)warning].severity; + Severity severity = get_severities()[(int)warning]; switch(severity) { case Severity::Suppress : Index: src/Common/SemanticError.h =================================================================== --- src/Common/SemanticError.h (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/Common/SemanticError.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -7,9 +7,9 @@ // SemanticError.h -- // -// Author : Richard C. Bilson +// Author : Thierry Delisle // Created On : Mon May 18 07:44:20 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Apr 19 17:52:03 2018 -// Update Count : 19 +// Last Modified On : Wed May 16 15:01:23 2018 +// Update Count : 30 // @@ -17,7 +17,10 @@ #include "ErrorObjects.h" +#include //----------------------------------------------------------------------------- // Errors + +extern bool SemanticErrorThrow; __attribute__((noreturn)) void SemanticError( CodeLocation location, std::string error ); @@ -46,10 +49,10 @@ const char * const name; const char * const message; - mutable Severity severity; + const Severity default_severity; }; -constexpr const WarningData WarningFormats[] = { - {"self-assign" , "self assignment of expression: %s" , Severity::Warn}, - {"reference-conversion", "rvalue to reference conversion of rvalue: %s", Severity::Warn}, +constexpr WarningData WarningFormats[] = { + {"self-assign" , "self assignment of expression: %s" , Severity::Warn}, + {"reference-conversion" , "rvalue to reference conversion of rvalue: %s" , Severity::Warn}, {"qualifiers-zero_t-one_t", "questionable use of type qualifier %s with %s", Severity::Warn}, }; @@ -71,4 +74,16 @@ void SemanticWarningImpl (CodeLocation loc, Warning warn, const char * const fmt, ...) __attribute__((format(printf, 3, 4))); +void SemanticWarning_SuppressAll (); +void SemanticWarning_EnableAll (); +void SemanticWarning_WarningAsError(); +void SemanticWarning_Set (const char * const name, Severity s); + +// SKULLDUGGERY: cfa.cc is built before SemanticError.cc but needs this routine. +static inline bool SemanticWarning_Exist(const char * const name) { + for ( const auto & w : WarningFormats ) { + if ( std::strcmp( name, w.name ) == 0 ) return true; + } + return false; +} //----------------------------------------------------------------------------- Index: src/Common/module.mk =================================================================== --- src/Common/module.mk (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/Common/module.mk (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -19,3 +19,4 @@ Common/DebugMalloc.cc \ Common/GC.cc \ - Common/Assert.cc + Common/Assert.cc \ + Common/Heap.cc Index: src/Common/utility.h =================================================================== --- src/Common/utility.h (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/Common/utility.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -10,6 +10,6 @@ // Created On : Mon May 18 07:44:20 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Fri Apr 20 22:35:33 2018 -// Update Count : 38 +// Last Modified On : Sun May 6 22:24:16 2018 +// Update Count : 40 // @@ -438,13 +438,18 @@ template -inline constexpr T ilog2(const T & t) { - if ( std::is_integral::value ) { +inline +#if defined(__GNUC__) && __GNUC__ > 4 +constexpr +#endif +T ilog2(const T & t) { + if(std::is_integral::value) { const constexpr int r = sizeof(t) * __CHAR_BIT__ - 1; - if ( sizeof(T) == sizeof(unsigned int ) ) return r - __builtin_clz( t ); - if ( sizeof(T) == sizeof(unsigned long) ) return r - __builtin_clzl( t ); - if ( sizeof(T) == sizeof(unsigned long long) ) return r - __builtin_clzll( t ); - } // if + if( sizeof(T) == sizeof(unsigned int) ) return r - __builtin_clz ( t ); + if( sizeof(T) == sizeof(unsigned long) ) return r - __builtin_clzl ( t ); + if( sizeof(T) == sizeof(unsigned long long) ) return r - __builtin_clzll( t ); + } + assert(false); return -1; -} // ilong2 +} // ilog2 Index: src/InitTweak/FixInit.cc =================================================================== --- src/InitTweak/FixInit.cc (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/InitTweak/FixInit.cc (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -385,5 +385,5 @@ void SelfAssignChecker::previsit( ApplicationExpr * appExpr ) { DeclarationWithType * function = getFunction( appExpr ); - if ( isAssignment( function ) ) { + if ( function->name == "?=?" ) { // doesn't use isAssignment, because ?+=?, etc. should not count as self-assignment if ( appExpr->args.size() == 2 ) { // check for structural similarity (same variable use, ignore casts, etc. - but does not look too deeply, anything looking like a function is off limits) Index: src/Makefile.in =================================================================== --- src/Makefile.in (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/Makefile.in (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -165,4 +165,5 @@ Common/driver_cfa_cpp-GC.$(OBJEXT) \ Common/driver_cfa_cpp-Assert.$(OBJEXT) \ + Common/driver_cfa_cpp-Heap.$(OBJEXT) \ ControlStruct/driver_cfa_cpp-LabelGenerator.$(OBJEXT) \ ControlStruct/driver_cfa_cpp-LabelFixer.$(OBJEXT) \ @@ -488,7 +489,8 @@ Concurrency/Waitfor.cc Common/SemanticError.cc \ Common/UniqueName.cc Common/DebugMalloc.cc Common/GC.cc \ - Common/Assert.cc ControlStruct/LabelGenerator.cc \ - ControlStruct/LabelFixer.cc ControlStruct/MLEMutator.cc \ - ControlStruct/Mutate.cc ControlStruct/ForExprMutator.cc \ + Common/Assert.cc Common/Heap.cc \ + ControlStruct/LabelGenerator.cc ControlStruct/LabelFixer.cc \ + ControlStruct/MLEMutator.cc ControlStruct/Mutate.cc \ + ControlStruct/ForExprMutator.cc \ ControlStruct/ExceptTranslate.cc GenPoly/Box.cc \ GenPoly/GenPoly.cc GenPoly/ScrubTyVars.cc GenPoly/Lvalue.cc \ @@ -677,4 +679,6 @@ Common/$(DEPDIR)/$(am__dirstamp) Common/driver_cfa_cpp-Assert.$(OBJEXT): Common/$(am__dirstamp) \ + Common/$(DEPDIR)/$(am__dirstamp) +Common/driver_cfa_cpp-Heap.$(OBJEXT): Common/$(am__dirstamp) \ Common/$(DEPDIR)/$(am__dirstamp) ControlStruct/$(am__dirstamp): @@ -981,4 +985,5 @@ @AMDEP_TRUE@@am__include@ @am__quote@Common/$(DEPDIR)/driver_cfa_cpp-DebugMalloc.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@Common/$(DEPDIR)/driver_cfa_cpp-GC.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@Common/$(DEPDIR)/driver_cfa_cpp-Heap.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@Common/$(DEPDIR)/driver_cfa_cpp-SemanticError.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@Common/$(DEPDIR)/driver_cfa_cpp-UniqueName.Po@am__quote@ @@ -1331,4 +1336,18 @@ @am__fastdepCXX_FALSE@ $(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o Common/driver_cfa_cpp-Assert.obj `if test -f 'Common/Assert.cc'; then $(CYGPATH_W) 'Common/Assert.cc'; else $(CYGPATH_W) '$(srcdir)/Common/Assert.cc'; fi` +Common/driver_cfa_cpp-Heap.o: Common/Heap.cc +@am__fastdepCXX_TRUE@ $(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT Common/driver_cfa_cpp-Heap.o -MD -MP -MF Common/$(DEPDIR)/driver_cfa_cpp-Heap.Tpo -c -o Common/driver_cfa_cpp-Heap.o `test -f 'Common/Heap.cc' || echo '$(srcdir)/'`Common/Heap.cc +@am__fastdepCXX_TRUE@ $(AM_V_at)$(am__mv) Common/$(DEPDIR)/driver_cfa_cpp-Heap.Tpo Common/$(DEPDIR)/driver_cfa_cpp-Heap.Po +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ $(AM_V_CXX)source='Common/Heap.cc' object='Common/driver_cfa_cpp-Heap.o' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCXX_FALSE@ $(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o Common/driver_cfa_cpp-Heap.o `test -f 'Common/Heap.cc' || echo '$(srcdir)/'`Common/Heap.cc + +Common/driver_cfa_cpp-Heap.obj: Common/Heap.cc +@am__fastdepCXX_TRUE@ $(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT Common/driver_cfa_cpp-Heap.obj -MD -MP -MF Common/$(DEPDIR)/driver_cfa_cpp-Heap.Tpo -c -o Common/driver_cfa_cpp-Heap.obj `if test -f 'Common/Heap.cc'; then $(CYGPATH_W) 'Common/Heap.cc'; else $(CYGPATH_W) '$(srcdir)/Common/Heap.cc'; fi` +@am__fastdepCXX_TRUE@ $(AM_V_at)$(am__mv) Common/$(DEPDIR)/driver_cfa_cpp-Heap.Tpo Common/$(DEPDIR)/driver_cfa_cpp-Heap.Po +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ $(AM_V_CXX)source='Common/Heap.cc' object='Common/driver_cfa_cpp-Heap.obj' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCXX_FALSE@ $(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o Common/driver_cfa_cpp-Heap.obj `if test -f 'Common/Heap.cc'; then $(CYGPATH_W) 'Common/Heap.cc'; else $(CYGPATH_W) '$(srcdir)/Common/Heap.cc'; fi` + ControlStruct/driver_cfa_cpp-LabelGenerator.o: ControlStruct/LabelGenerator.cc @am__fastdepCXX_TRUE@ $(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT ControlStruct/driver_cfa_cpp-LabelGenerator.o -MD -MP -MF ControlStruct/$(DEPDIR)/driver_cfa_cpp-LabelGenerator.Tpo -c -o ControlStruct/driver_cfa_cpp-LabelGenerator.o `test -f 'ControlStruct/LabelGenerator.cc' || echo '$(srcdir)/'`ControlStruct/LabelGenerator.cc Index: src/Parser/DeclarationNode.cc =================================================================== --- src/Parser/DeclarationNode.cc (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/Parser/DeclarationNode.cc (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -10,6 +10,6 @@ // Created On : Sat May 16 12:34:05 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Fri Apr 20 22:37:20 2018 -// Update Count : 1063 +// Last Modified On : Wed May 16 09:37:17 2018 +// Update Count : 1070 // @@ -526,5 +526,5 @@ DeclarationNode * DeclarationNode::addQualifiers( DeclarationNode * q ) { - if ( ! q ) { delete q; return this; } // empty qualifier + if ( ! q ) { return this; } // empty qualifier checkSpecifiers( q ); @@ -560,7 +560,6 @@ checkQualifiers( type, q->type ); - if ( (builtin == Zero || builtin == One) && error.length() == 0 ) { + if ( (builtin == Zero || builtin == One) && q->type->qualifiers.val != 0 && error.length() == 0 ) { SemanticWarning( yylloc, Warning::BadQualifiersZeroOne, Type::QualifiersNames[ilog2( q->type->qualifiers.val )], builtinTypeNames[builtin] ); -// appendError( error, string( "questionable qualifiers" ) ); } // if addQualifiersToType( q->type, type ); @@ -782,5 +781,5 @@ DeclarationNode * DeclarationNode::addPointer( DeclarationNode * p ) { if ( p ) { - assert( p->type->kind == TypeData::Pointer || TypeData::Reference ); + assert( p->type->kind == TypeData::Pointer || p->type->kind == TypeData::Reference ); setBase( p->type ); p->type = nullptr; Index: src/Parser/ParseNode.h =================================================================== --- src/Parser/ParseNode.h (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/Parser/ParseNode.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -10,6 +10,6 @@ // Created On : Sat May 16 13:28:16 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Feb 22 17:49:31 2018 -// Update Count : 827 +// Last Modified On : Mon Apr 30 09:19:17 2018 +// Update Count : 831 // @@ -332,5 +332,5 @@ bool hasEllipsis; LinkageSpec::Spec linkage; - Expression *asmName; + Expression * asmName; std::list< Attribute * > attributes; InitializerNode * initializer; @@ -416,5 +416,6 @@ Statement * build_finally( StatementNode * stmt ); Statement * build_compound( StatementNode * first ); -Statement * build_asmstmt( bool voltile, Expression * instruction, ExpressionNode * output = nullptr, ExpressionNode * input = nullptr, ExpressionNode * clobber = nullptr, LabelNode * gotolabels = nullptr ); +Statement * build_asm( bool voltile, Expression * instruction, ExpressionNode * output = nullptr, ExpressionNode * input = nullptr, ExpressionNode * clobber = nullptr, LabelNode * gotolabels = nullptr ); +Statement * build_directive( std::string * directive ); WaitForStmt * build_waitfor( ExpressionNode * target, StatementNode * stmt, ExpressionNode * when ); WaitForStmt * build_waitfor( ExpressionNode * target, StatementNode * stmt, ExpressionNode * when, WaitForStmt * existing ); Index: src/Parser/StatementNode.cc =================================================================== --- src/Parser/StatementNode.cc (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/Parser/StatementNode.cc (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -10,10 +10,11 @@ // Created On : Sat May 16 14:59:41 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Mar 8 14:31:32 2018 -// Update Count : 348 +// Last Modified On : Mon Apr 30 09:21:16 2018 +// Update Count : 354 // #include // for assert, strict_dynamic_cast, assertf #include // for list +#include // for unique_ptr #include // for string @@ -32,9 +33,9 @@ -StatementNode::StatementNode( DeclarationNode *decl ) { +StatementNode::StatementNode( DeclarationNode * decl ) { assert( decl ); - DeclarationNode *agg = decl->extractAggregate(); + DeclarationNode * agg = decl->extractAggregate(); if ( agg ) { - StatementNode *nextStmt = new StatementNode( new DeclStmt( maybeBuild< Declaration >( decl ) ) ); + StatementNode * nextStmt = new StatementNode( new DeclStmt( maybeBuild< Declaration >( decl ) ) ); set_next( nextStmt ); if ( decl->get_next() ) { @@ -52,14 +53,14 @@ } // StatementNode::StatementNode -StatementNode *StatementNode::append_last_case( StatementNode *stmt ) { - StatementNode *prev = this; +StatementNode * StatementNode::append_last_case( StatementNode * stmt ) { + StatementNode * prev = this; // find end of list and maintain previous pointer for ( StatementNode * curr = prev; curr != nullptr; curr = (StatementNode *)curr->get_next() ) { - StatementNode *node = strict_dynamic_cast< StatementNode * >(curr); + StatementNode * node = strict_dynamic_cast< StatementNode * >(curr); assert( dynamic_cast< CaseStmt * >(node->stmt) ); prev = curr; } // for // convert from StatementNode list to Statement list - StatementNode *node = dynamic_cast< StatementNode * >(prev); + StatementNode * node = dynamic_cast< StatementNode * >(prev); std::list< Statement * > stmts; buildMoveList( stmt, stmts ); @@ -70,6 +71,6 @@ } -Statement *build_expr( ExpressionNode *ctl ) { - Expression *e = maybeMoveBuild< Expression >( ctl ); +Statement * build_expr( ExpressionNode * ctl ) { + Expression * e = maybeMoveBuild< Expression >( ctl ); if ( e ) @@ -79,6 +80,6 @@ } -Statement *build_if( IfCtl * ctl, StatementNode *then_stmt, StatementNode *else_stmt ) { - Statement *thenb, *elseb = 0; +Statement * build_if( IfCtl * ctl, StatementNode * then_stmt, StatementNode * else_stmt ) { + Statement * thenb, * elseb = 0; std::list< Statement * > branches; buildMoveList< Statement, StatementNode >( then_stmt, branches ); @@ -115,5 +116,5 @@ } -Statement *build_switch( bool isSwitch, ExpressionNode *ctl, StatementNode *stmt ) { +Statement * build_switch( bool isSwitch, ExpressionNode * ctl, StatementNode * stmt ) { std::list< Statement * > branches; buildMoveList< Statement, StatementNode >( stmt, branches ); @@ -130,14 +131,14 @@ return new SwitchStmt( maybeMoveBuild< Expression >(ctl), branches ); } -Statement *build_case( ExpressionNode *ctl ) { +Statement * build_case( ExpressionNode * ctl ) { std::list< Statement * > branches; return new CaseStmt( maybeMoveBuild< Expression >(ctl), branches ); } -Statement *build_default() { +Statement * build_default() { std::list< Statement * > branches; return new CaseStmt( nullptr, branches, true ); } -Statement *build_while( ExpressionNode *ctl, StatementNode *stmt, bool kind ) { +Statement * build_while( ExpressionNode * ctl, StatementNode * stmt, bool kind ) { std::list< Statement * > branches; buildMoveList< Statement, StatementNode >( stmt, branches ); @@ -146,5 +147,5 @@ } -Statement *build_for( ForCtl *forctl, StatementNode *stmt ) { +Statement * build_for( ForCtl * forctl, StatementNode * stmt ) { std::list< Statement * > branches; buildMoveList< Statement, StatementNode >( stmt, branches ); @@ -156,9 +157,9 @@ } // if - Expression *cond = 0; + Expression * cond = 0; if ( forctl->condition != 0 ) cond = notZeroExpr( maybeMoveBuild< Expression >(forctl->condition) ); - Expression *incr = 0; + Expression * incr = 0; if ( forctl->change != 0 ) incr = maybeMoveBuild< Expression >(forctl->change); @@ -168,18 +169,18 @@ } -Statement *build_branch( BranchStmt::Type kind ) { +Statement * build_branch( BranchStmt::Type kind ) { Statement * ret = new BranchStmt( "", kind ); return ret; } -Statement *build_branch( std::string *identifier, BranchStmt::Type kind ) { - Statement * ret = new BranchStmt( *identifier, kind ); +Statement * build_branch( std::string * identifier, BranchStmt::Type kind ) { + Statement * ret = new BranchStmt( * identifier, kind ); delete identifier; // allocated by lexer return ret; } -Statement *build_computedgoto( ExpressionNode *ctl ) { +Statement * build_computedgoto( ExpressionNode * ctl ) { return new BranchStmt( maybeMoveBuild< Expression >(ctl), BranchStmt::Goto ); } -Statement *build_return( ExpressionNode *ctl ) { +Statement * build_return( ExpressionNode * ctl ) { std::list< Expression * > exps; buildMoveList( ctl, exps ); @@ -187,5 +188,5 @@ } -Statement *build_throw( ExpressionNode *ctl ) { +Statement * build_throw( ExpressionNode * ctl ) { std::list< Expression * > exps; buildMoveList( ctl, exps ); @@ -194,5 +195,5 @@ } -Statement *build_resume( ExpressionNode *ctl ) { +Statement * build_resume( ExpressionNode * ctl ) { std::list< Expression * > exps; buildMoveList( ctl, exps ); @@ -201,5 +202,5 @@ } -Statement *build_resume_at( ExpressionNode *ctl, ExpressionNode *target ) { +Statement * build_resume_at( ExpressionNode * ctl, ExpressionNode * target ) { (void)ctl; (void)target; @@ -207,12 +208,12 @@ } -Statement *build_try( StatementNode *try_stmt, StatementNode *catch_stmt, StatementNode *finally_stmt ) { +Statement * build_try( StatementNode * try_stmt, StatementNode * catch_stmt, StatementNode * finally_stmt ) { std::list< CatchStmt * > branches; buildMoveList< CatchStmt, StatementNode >( catch_stmt, branches ); - CompoundStmt *tryBlock = strict_dynamic_cast< CompoundStmt * >(maybeMoveBuild< Statement >(try_stmt)); - FinallyStmt *finallyBlock = dynamic_cast< FinallyStmt * >(maybeMoveBuild< Statement >(finally_stmt) ); + CompoundStmt * tryBlock = strict_dynamic_cast< CompoundStmt * >(maybeMoveBuild< Statement >(try_stmt)); + FinallyStmt * finallyBlock = dynamic_cast< FinallyStmt * >(maybeMoveBuild< Statement >(finally_stmt) ); return new TryStmt( tryBlock, branches, finallyBlock ); } -Statement *build_catch( CatchStmt::Kind kind, DeclarationNode *decl, ExpressionNode *cond, StatementNode *body ) { +Statement * build_catch( CatchStmt::Kind kind, DeclarationNode * decl, ExpressionNode * cond, StatementNode * body ) { std::list< Statement * > branches; buildMoveList< Statement, StatementNode >( body, branches ); @@ -220,5 +221,5 @@ return new CatchStmt( kind, maybeMoveBuild< Declaration >(decl), maybeMoveBuild< Expression >(cond), branches.front() ); } -Statement *build_finally( StatementNode *stmt ) { +Statement * build_finally( StatementNode * stmt ) { std::list< Statement * > branches; buildMoveList< Statement, StatementNode >( stmt, branches ); @@ -303,11 +304,11 @@ } -Statement *build_compound( StatementNode *first ) { - CompoundStmt *cs = new CompoundStmt(); +Statement * build_compound( StatementNode * first ) { + CompoundStmt * cs = new CompoundStmt(); buildMoveList( first, cs->get_kids() ); return cs; } -Statement *build_asmstmt( bool voltile, Expression *instruction, ExpressionNode *output, ExpressionNode *input, ExpressionNode *clobber, LabelNode *gotolabels ) { +Statement * build_asm( bool voltile, Expression * instruction, ExpressionNode * output, ExpressionNode * input, ExpressionNode * clobber, LabelNode * gotolabels ) { std::list< Expression * > out, in; std::list< ConstantExpr * > clob; @@ -317,4 +318,8 @@ buildMoveList( clobber, clob ); return new AsmStmt( voltile, instruction, out, in, clob, gotolabels ? gotolabels->labels : noLabels ); +} + +Statement * build_directive( string * directive ) { + return new DirectiveStmt( *directive ); } Index: src/Parser/TypeData.cc =================================================================== --- src/Parser/TypeData.cc (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/Parser/TypeData.cc (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -10,6 +10,6 @@ // Created On : Sat May 16 15:12:51 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Tue Apr 17 23:00:52 2018 -// Update Count : 602 +// Last Modified On : Thu Apr 26 13:46:07 2018 +// Update Count : 603 // @@ -62,4 +62,5 @@ enumeration.constants = nullptr; enumeration.body = false; + break; case Aggregate: // aggregate = new Aggregate_t; Index: src/Parser/lex.ll =================================================================== --- src/Parser/lex.ll (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/Parser/lex.ll (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -10,6 +10,6 @@ * Created On : Sat Sep 22 08:58:10 2001 * Last Modified By : Peter A. Buhr - * Last Modified On : Fri Apr 6 15:16:15 2018 - * Update Count : 670 + * Last Modified On : Thu May 3 13:42:40 2018 + * Update Count : 676 */ @@ -174,6 +174,6 @@ } - /* ignore preprocessor directives (for now) */ -^{h_white}*"#"[^\n]*"\n" ; + /* preprocessor-style directives */ +^{h_white}*"#"[^\n]*"\n" { RETURN_VAL( DIRECTIVE ); } /* ignore C style comments (ALSO HANDLED BY CPP) */ Index: src/Parser/parser.yy =================================================================== --- src/Parser/parser.yy (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/Parser/parser.yy (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -10,6 +10,6 @@ // Created On : Sat Sep 1 20:22:55 2001 // Last Modified By : Peter A. Buhr -// Last Modified On : Tue Apr 17 17:10:30 2018 -// Update Count : 3144 +// Last Modified On : Fri May 11 17:51:38 2018 +// Update Count : 3261 // @@ -133,5 +133,5 @@ } // build_postfix_name -bool forall = false; // aggregate have one or more forall qualifiers ? +bool forall = false, xxx = false; // aggregate have one or more forall qualifiers ? // https://www.gnu.org/software/bison/manual/bison.html#Location-Type @@ -208,4 +208,5 @@ %token ATTR_IDENTIFIER ATTR_TYPEDEFname ATTR_TYPEGENname %token INTEGERconstant CHARACTERconstant STRINGliteral +%token DIRECTIVE // Floating point constant is broken into three kinds of tokens because of the ambiguity with tuple indexing and // overloading constants 0/1, e.g., x.1 is lexed as (x)(.1), where (.1) is a factional constant, but is semantically @@ -282,5 +283,5 @@ %type aggregate_type aggregate_type_nobody -%type assertion assertion_list_opt +%type assertion assertion_list assertion_list_opt %type bit_subrange_size_opt bit_subrange_size @@ -301,5 +302,5 @@ %type field_declaration field_declaration_list field_declarator field_declaring_list -%type field field_list field_name fraction_constants +%type field field_list field_name fraction_constants_opt %type external_function_definition function_definition function_array function_declarator function_no_ptr function_ptr @@ -498,6 +499,8 @@ | type_name '.' no_attr_identifier // CFA, nested type { SemanticError( yylloc, "Qualified names are currently unimplemented." ); $$ = nullptr; } +// { $$ = nullptr; } | type_name '.' '[' push field_list pop ']' // CFA, nested type / tuple field selector { SemanticError( yylloc, "Qualified names are currently unimplemented." ); $$ = nullptr; } +// { $$ = nullptr; } | GENERIC '(' assignment_expression ',' generic_assoc_list ')' // C11 { SemanticError( yylloc, "_Generic is currently unimplemented." ); $$ = nullptr; } @@ -532,16 +535,18 @@ | postfix_expression '.' no_attr_identifier { $$ = new ExpressionNode( build_fieldSel( $1, build_varref( $3 ) ) ); } + | postfix_expression '.' INTEGERconstant // CFA, tuple index + { $$ = new ExpressionNode( build_fieldSel( $1, build_constantInteger( *$3 ) ) ); } + | postfix_expression FLOATING_FRACTIONconstant // CFA, tuple index + { $$ = new ExpressionNode( build_fieldSel( $1, build_field_name_FLOATING_FRACTIONconstant( *$2 ) ) ); } | postfix_expression '.' '[' push field_list pop ']' // CFA, tuple field selector { $$ = new ExpressionNode( build_fieldSel( $1, build_tuple( $5 ) ) ); } - | postfix_expression FLOATING_FRACTIONconstant // CFA, tuple index - { $$ = new ExpressionNode( build_fieldSel( $1, build_field_name_FLOATING_FRACTIONconstant( *$2 ) ) ); } | postfix_expression ARROW no_attr_identifier { $$ = new ExpressionNode( build_pfieldSel( $1, *$3 == "0" || *$3 == "1" ? build_constantInteger( *$3 ) : build_varref( $3 ) ) ); } - | postfix_expression ARROW '[' push field_list pop ']' // CFA, tuple field selector - { $$ = new ExpressionNode( build_pfieldSel( $1, build_tuple( $5 ) ) ); } | postfix_expression ARROW INTEGERconstant // CFA, tuple index { $$ = new ExpressionNode( build_pfieldSel( $1, build_constantInteger( *$3 ) ) ); } + | postfix_expression ARROW '[' push field_list pop ']' // CFA, tuple field selector + { $$ = new ExpressionNode( build_pfieldSel( $1, build_tuple( $5 ) ) ); } | postfix_expression ICR { $$ = new ExpressionNode( build_unary_ptr( OperKinds::IncrPost, $1 ) ); } @@ -596,9 +601,9 @@ field_name: - INTEGERconstant fraction_constants + INTEGERconstant fraction_constants_opt { $$ = new ExpressionNode( build_field_name_fraction_constants( build_constantInteger( *$1 ), $2 ) ); } - | FLOATINGconstant fraction_constants + | FLOATINGconstant fraction_constants_opt { $$ = new ExpressionNode( build_field_name_fraction_constants( build_field_name_FLOATINGconstant( *$1 ), $2 ) ); } - | no_attr_identifier fraction_constants + | no_attr_identifier fraction_constants_opt { $$ = new ExpressionNode( build_field_name_fraction_constants( build_varref( $1 ), $2 ) ); @@ -606,8 +611,8 @@ ; -fraction_constants: +fraction_constants_opt: // empty { $$ = nullptr; } - | fraction_constants FLOATING_FRACTIONconstant + | fraction_constants_opt FLOATING_FRACTIONconstant { Expression * constant = build_field_name_FLOATING_FRACTIONconstant( *$2 ); @@ -875,4 +880,6 @@ { SemanticError( yylloc, "enable/disable statement is currently unimplemented." ); $$ = nullptr; } | asm_statement + | DIRECTIVE + { $$ = new StatementNode( build_directive( $1 ) ); } ; @@ -1204,13 +1211,13 @@ asm_statement: ASM asm_volatile_opt '(' string_literal ')' ';' - { $$ = new StatementNode( build_asmstmt( $2, $4, 0 ) ); } + { $$ = new StatementNode( build_asm( $2, $4, 0 ) ); } | ASM asm_volatile_opt '(' string_literal ':' asm_operands_opt ')' ';' // remaining GCC - { $$ = new StatementNode( build_asmstmt( $2, $4, $6 ) ); } + { $$ = new StatementNode( build_asm( $2, $4, $6 ) ); } | ASM asm_volatile_opt '(' string_literal ':' asm_operands_opt ':' asm_operands_opt ')' ';' - { $$ = new StatementNode( build_asmstmt( $2, $4, $6, $8 ) ); } + { $$ = new StatementNode( build_asm( $2, $4, $6, $8 ) ); } | ASM asm_volatile_opt '(' string_literal ':' asm_operands_opt ':' asm_operands_opt ':' asm_clobbers_list_opt ')' ';' - { $$ = new StatementNode( build_asmstmt( $2, $4, $6, $8, $10 ) ); } + { $$ = new StatementNode( build_asm( $2, $4, $6, $8, $10 ) ); } | ASM asm_volatile_opt GOTO '(' string_literal ':' ':' asm_operands_opt ':' asm_clobbers_list_opt ':' label_list ')' ';' - { $$ = new StatementNode( build_asmstmt( $2, $5, 0, $8, $10, $12 ) ); } + { $$ = new StatementNode( build_asm( $2, $5, 0, $8, $10, $12 ) ); } ; @@ -1866,4 +1873,6 @@ { typedefTable.makeTypedef( *$3 ); + if ( forall ) typedefTable.changeKind( *$3, TypedefTable::TG ); // possibly update + forall = false; // reset $$ = DeclarationNode::newAggregate( $1, $3, nullptr, nullptr, false )->addQualifiers( $2 ); } @@ -2235,4 +2244,6 @@ { $$ = DeclarationNode::newTypeParam( $1, $2 )->addTypeInitializer( $4 )->addAssertions( $5 ); } | type_specifier identifier_parameter_declarator + | assertion_list + { $$ = DeclarationNode::newTypeParam( DeclarationNode::Dtype, new string( DeclarationNode::anonymous.newName() ) )->addAssertions( $1 ); } ; @@ -2251,5 +2262,10 @@ // empty { $$ = nullptr; } - | assertion_list_opt assertion + | assertion_list + ; + +assertion_list: // CFA + assertion + | assertion_list assertion { $$ = $1 ? $1->appendList( $2 ) : $2; } ; @@ -2378,6 +2394,8 @@ external_definition_list: external_definition - | external_definition_list push external_definition - { $$ = $1 ? $1->appendList( $3 ) : $3; } + | external_definition_list + { forall = xxx; } + push external_definition + { $$ = $1 ? $1->appendList( $4 ) : $4; } ; @@ -2393,5 +2411,5 @@ | ASM '(' string_literal ')' ';' // GCC, global assembler statement { - $$ = DeclarationNode::newAsmStmt( new StatementNode( build_asmstmt( false, $3, 0 ) ) ); + $$ = DeclarationNode::newAsmStmt( new StatementNode( build_asm( false, $3, 0 ) ) ); } | EXTERN STRINGliteral // C++-style linkage specifier @@ -2411,5 +2429,52 @@ $$ = $2; } - | type_qualifier_list '{' external_definition_list '}' // CFA, namespace + | type_qualifier_list + { + if ( $1->type->forall ) xxx = forall = true; // remember generic type + } + push '{' external_definition_list '}' // CFA, namespace + { + for ( DeclarationNode * iter = $5; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) { + if ( isMangled( iter->linkage ) ) { // ignore extern "C" + iter->addQualifiers( $1->clone() ); + } // if + } // for + xxx = false; + delete $1; + $$ = $5; + } + | declaration_qualifier_list + { + if ( $1->type->forall ) xxx = forall = true; // remember generic type + } + push '{' external_definition_list '}' // CFA, namespace + { + for ( DeclarationNode * iter = $5; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) { + if ( isMangled( iter->linkage ) ) { // ignore extern "C" + iter->addQualifiers( $1->clone() ); + } // if + } // for + xxx = false; + delete $1; + $$ = $5; + } + | declaration_qualifier_list type_qualifier_list + { + // forall must be in the type_qualifier_list + if ( $2->type->forall ) xxx = forall = true; // remember generic type + } + push '{' external_definition_list '}' // CFA, namespace + { + for ( DeclarationNode * iter = $6; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) { + if ( isMangled( iter->linkage ) && isMangled( $2->linkage ) ) { // ignore extern "C" + iter->addQualifiers( $1->clone() ); + iter->addQualifiers( $2->clone() ); + } // if + } // for + xxx = false; + delete $1; + delete $2; + $$ = $6; + } ; @@ -2437,7 +2502,7 @@ with_clause_opt: // empty - { $$ = nullptr; } + { $$ = nullptr; forall = false; } | WITH '(' tuple_expression_list ')' - { $$ = $3; } + { $$ = $3; forall = false; } ; Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/ResolvExpr/AlternativeFinder.cc (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -453,7 +453,7 @@ /// Adds type variables to the open variable set and marks their assertions void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) { - for ( Type::ForallList::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) { + for ( Type::ForallList::const_iterator tyvar = type->forall.begin(); tyvar != type->forall.end(); ++tyvar ) { unifiableVars[ (*tyvar)->get_name() ] = TypeDecl::Data{ *tyvar }; - for ( std::list< DeclarationWithType* >::iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) { + for ( std::list< DeclarationWithType* >::iterator assert = (*tyvar)->assertions.begin(); assert != (*tyvar)->assertions.end(); ++assert ) { needAssertions[ *assert ].isUsed = true; } Index: src/ResolvExpr/AlternativeFinder.h =================================================================== --- src/ResolvExpr/AlternativeFinder.h (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/ResolvExpr/AlternativeFinder.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -126,4 +126,7 @@ void printAlts( const AltList &list, std::ostream &os, unsigned int indentAmt = 0 ); + /// Adds type variables to the open variable set and marks their assertions + void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ); + template< typename InputIterator > void simpleCombineEnvironments( InputIterator begin, InputIterator end, TypeEnvironment &result ) { Index: src/ResolvExpr/Resolver.cc =================================================================== --- src/ResolvExpr/Resolver.cc (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/ResolvExpr/Resolver.cc (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -493,4 +493,8 @@ } + if(clause.target.arguments.empty()) { + SemanticError( stmt->location, "Waitfor clause must have at least one mutex parameter"); + } + // Find all alternatives for all arguments in canonical form std::vector< AlternativeFinder > argAlternatives; @@ -541,5 +545,9 @@ OpenVarSet openVars; AssertionSet resultNeed, resultHave; - TypeEnvironment resultEnv; + TypeEnvironment resultEnv( func.env ); + makeUnifiableVars( function, openVars, resultNeed ); + // add all type variables as open variables now so that those not used in the parameter + // list are still considered open. + resultEnv.add( function->forall ); // Load type variables from arguemnts into one shared space @@ -557,4 +565,6 @@ auto param_end = function->parameters.end(); + int n_mutex_arg = 0; + // For every arguments of its set, check if it matches one of the parameter // The order is important @@ -565,15 +575,19 @@ // We ran out of parameters but still have arguments // this function doesn't match - SemanticError( function, "candidate function not viable: too many mutex arguments\n" ); + SemanticError( function, toString("candidate function not viable: too many mutex arguments, expected ", n_mutex_arg, "\n" )); } + n_mutex_arg++; + // Check if the argument matches the parameter type in the current scope - if( ! unify( (*param)->get_type(), arg.expr->get_result(), resultEnv, resultNeed, resultHave, openVars, this->indexer ) ) { + if( ! unify( arg.expr->get_result(), (*param)->get_type(), resultEnv, resultNeed, resultHave, openVars, this->indexer ) ) { // Type doesn't match stringstream ss; ss << "candidate function not viable: no known convertion from '"; + (*param)->get_type()->print( ss ); + ss << "' to '"; arg.expr->get_result()->print( ss ); - ss << "' to '"; - (*param)->get_type()->print( ss ); + ss << "' with env '"; + resultEnv.print(ss); ss << "'\n"; SemanticError( function, ss.str() ); @@ -589,5 +603,5 @@ // We ran out of arguments but still have parameters left // this function doesn't match - SemanticError( function, "candidate function not viable: too few mutex arguments\n" ); + SemanticError( function, toString("candidate function not viable: too few mutex arguments, expected ", n_mutex_arg, "\n" )); } Index: src/SymTab/Autogen.cc =================================================================== --- src/SymTab/Autogen.cc (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/SymTab/Autogen.cc (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -9,7 +9,7 @@ // Author : Rob Schluntz // Created On : Thu Mar 03 15:45:56 2016 -// Last Modified By : Andrew Beach -// Last Modified On : Fri Jul 14 16:41:00 2017 -// Update Count : 62 +// Last Modified By : Peter A. Buhr +// Last Modified On : Fri Apr 27 14:39:06 2018 +// Update Count : 63 // @@ -330,5 +330,5 @@ definitions.push_back( dcl ); indexer.addId( dcl ); - } catch ( SemanticErrorException err ) { + } catch ( SemanticErrorException & ) { // okay if decl does not resolve - that means the function should not be generated } Index: src/SymTab/Mangler.cc =================================================================== --- src/SymTab/Mangler.cc (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/SymTab/Mangler.cc (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -178,5 +178,5 @@ printQualifiers( pointerType ); mangleName << "P"; - maybeAccept( pointerType->get_base(), *visitor ); + maybeAccept( pointerType->base, *visitor ); } @@ -185,5 +185,5 @@ printQualifiers( arrayType ); mangleName << "A0"; - maybeAccept( arrayType->get_base(), *visitor ); + maybeAccept( arrayType->base, *visitor ); } @@ -191,5 +191,5 @@ printQualifiers( refType ); mangleName << "R"; - maybeAccept( refType->get_base(), *visitor ); + maybeAccept( refType->base, *visitor ); } Index: src/SynTree/Mutator.h =================================================================== --- src/SynTree/Mutator.h (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/SynTree/Mutator.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -39,4 +39,5 @@ virtual Statement * mutate( ExprStmt * exprStmt ) = 0; virtual Statement * mutate( AsmStmt * asmStmt ) = 0; + virtual Statement * mutate( DirectiveStmt * dirStmt ) = 0; virtual Statement * mutate( IfStmt * ifStmt ) = 0; virtual Statement * mutate( WhileStmt * whileStmt ) = 0; Index: src/SynTree/Statement.cc =================================================================== --- src/SynTree/Statement.cc (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/SynTree/Statement.cc (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -81,4 +81,11 @@ +DirectiveStmt::DirectiveStmt( const std::string & directive ) : Statement(), directive( directive ) {} + +void DirectiveStmt::print( std::ostream &os, Indenter ) const { + os << "GCC Directive:" << directive << endl; +} + + const char *BranchStmt::brType[] = { "Goto", "Break", "Continue" }; @@ -370,6 +377,34 @@ void WaitForStmt::print( std::ostream &os, Indenter indent ) const { os << "Waitfor Statement" << endl; - os << indent << "... with block:" << endl << indent+1; - // block->print( os, indent + 4 ); + indent += 1; + for( auto & clause : clauses ) { + os << indent << "target function :"; + if(clause.target.function) { clause.target.function->print(os, indent + 1); } + os << endl << indent << "with arguments :" << endl; + for( auto & thing : clause.target.arguments) { + if(thing) { thing->print(os, indent + 1); } + } + os << indent << " with statment :" << endl; + if(clause.statement) { clause.statement->print(os, indent + 1); } + + os << indent << " with condition :" << endl; + if(clause.condition) { clause.condition->print(os, indent + 1); } + } + + os << indent << " timeout of :" << endl; + if(timeout.time) { timeout.time->print(os, indent + 1); } + + os << indent << " with statment :" << endl; + if(timeout.statement) { timeout.statement->print(os, indent + 1); } + + os << indent << " with condition :" << endl; + if(timeout.condition) { timeout.condition->print(os, indent + 1); } + + + os << indent << " else :" << endl; + if(orelse.statement) { orelse.statement->print(os, indent + 1); } + + os << indent << " with condition :" << endl; + if(orelse.condition) { orelse.condition->print(os, indent + 1); } } Index: src/SynTree/Statement.h =================================================================== --- src/SynTree/Statement.h (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/SynTree/Statement.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -122,4 +122,17 @@ }; +class DirectiveStmt : public Statement { + public: + std::string directive; + + DirectiveStmt( const std::string & ); + virtual ~DirectiveStmt(){} + + virtual DirectiveStmt * clone() const { return new DirectiveStmt( *this ); } + virtual void accept( Visitor & v ) { v.visit( this ); } + virtual Statement * acceptMutator( Mutator & m ) { return m.mutate( this ); } + virtual void print( std::ostream & os, Indenter indent = {} ) const; +}; + class IfStmt : public Statement { public: Index: src/SynTree/SynTree.h =================================================================== --- src/SynTree/SynTree.h (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/SynTree/SynTree.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -44,4 +44,5 @@ class ExprStmt; class AsmStmt; +class DirectiveStmt; class IfStmt; class WhileStmt; Index: src/SynTree/Visitor.h =================================================================== --- src/SynTree/Visitor.h (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/SynTree/Visitor.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -41,4 +41,5 @@ virtual void visit( ExprStmt * exprStmt ) = 0; virtual void visit( AsmStmt * asmStmt ) = 0; + virtual void visit( DirectiveStmt * directiveStmt ) = 0; virtual void visit( IfStmt * ifStmt ) = 0; virtual void visit( WhileStmt * whileStmt ) = 0; Index: src/benchmark/Makefile.am =================================================================== --- src/benchmark/Makefile.am (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/benchmark/Makefile.am (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -43,5 +43,5 @@ %.runquiet : - @+make $(basename $@) + @+make $(basename $@) CFLAGS="-w" @taskset -c 1 ./a.out @rm -f a.out Index: src/benchmark/Makefile.in =================================================================== --- src/benchmark/Makefile.in (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/benchmark/Makefile.in (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -459,5 +459,5 @@ %.runquiet : - @+make $(basename $@) + @+make $(basename $@) CFLAGS="-w" @taskset -c 1 ./a.out @rm -f a.out Index: src/benchmark/bench.h =================================================================== --- src/benchmark/bench.h (revision f6f0cca3f172613989f420c40761026fe191b651) +++ src/benchmark/bench.h (revision ff29f0885c5ef43cc494cdb91326ef1813825a32) @@ -6,13 +6,14 @@ #include #include // sysconf - #include // times +#if ! defined(__cforall) #include -#if defined(__cforall) + #include +#else } -//#include +#include