Index: .gitignore =================================================================== --- .gitignore (revision 950f7a72ccf248faed22f2bbd0d7542e24948798) +++ .gitignore (revision 7527e6365628dd566e55f6dbeaca1521c6718837) @@ -34,2 +34,7 @@ # generated by bison and lex from cfa.yy and lex.ll, respectively src/Parser/parser.output + +# generated by xfig for user manual +doc/user/Cdecl.tex +doc/user/pointer1.tex +doc/user/pointer2.tex Index: INSTALL =================================================================== --- INSTALL (revision 950f7a72ccf248faed22f2bbd0d7542e24948798) +++ INSTALL (revision 7527e6365628dd566e55f6dbeaca1521c6718837) @@ -3,6 +3,6 @@ Cforall is built using GNU Make and the GNU Autoconf system. It also requires -g++ version 4, bison and flex. On systems where GNU Make is the default make -it may suffice to build the system by entering the commands +g++ version >= 4.6, bison and flex. On systems where GNU Make is the default +make, the system is built by entering the commands: ./configure @@ -17,9 +17,9 @@ --prefix=/some/directory controls the path prefix common to all installed - cfa-cc components. Some components will be installed in /some/directory/bin, + cfa-cc components. Some components are installed in /some/directory/bin, others in /some/directory/lib. If unspecified, this defaults to /usr/local. - If you wish to use (a subdirectory of) your home directory, ${HOME}/some/dir - works, but it is important not to put quotes around the directory path; - Cforall may appear to build, but the installed version may not work properly. + To use (a subdirectory of) your home directory, ${HOME}/some/dir works, but + it is important not to put quotes around the directory path; Cforall may + appear to build, but the installed version may not work properly. --with-backend-compiler=PROGRAM specifies the installed path of gcc. It Index: Jenkins/FullBuild =================================================================== --- Jenkins/FullBuild (revision 950f7a72ccf248faed22f2bbd0d7542e24948798) +++ Jenkins/FullBuild (revision 7527e6365628dd566e55f6dbeaca1521c6718837) @@ -14,8 +14,13 @@ name: 'buildArchitecture', \ value: arch] \ - ] + ], \ + propagate: false echo(result.result) - echo(result.absoluteUrl) + + if(result.result != 'SUCCESS') { + sh("wget -q -O - ${result.absoluteUrl}/consoleText") + error(result.result) + } } @@ -32,4 +37,6 @@ checkout scm + collect_git_info() + //parse git logs to find what changed sh "git remote > ${out_dir}/GIT_REMOTE" @@ -41,5 +48,22 @@ } - sh "git push DoLang ${gitRefNewValue}:master" + //sh "GIT_SSH_COMMAND=\"ssh -v\" git push DoLang ${gitRefNewValue}:master" + echo('BUILD NOT PUSH SINCE DO-LANG SERVER WAS DOWN') +} + +//Helper routine to collect information about the git history +def collect_git_info() { + + //create the temporary output directory in case it doesn't already exist + def out_dir = pwd tmp: true + sh "mkdir -p ${out_dir}" + + //parse git logs to find what changed + dir("../Cforall_Full_Build@script") { + sh "git reflog > ${out_dir}/GIT_COMMIT" + } + git_reflog = readFile("${out_dir}/GIT_COMMIT") + gitRefOldValue = (git_reflog =~ /moving from (.+) to (.+)/)[0][1] + gitRefNewValue = (git_reflog =~ /moving from (.+) to (.+)/)[0][2] } @@ -49,4 +73,6 @@ node ('master') { + def err = null + try { //Prevent the build from exceeding 30 minutes @@ -78,12 +104,14 @@ //attach the build log to the email catch (Exception caughtError) { + echo('error caught') + //rethrow error later err = caughtError //Store the result of the build log - currentBuild.result = "${status_prefix} FAILURE".trim() + currentBuild.result = 'FAILURE' //Send email to notify the failure - promote_email(currentBuild.result) + promote_failure_email() } @@ -100,5 +128,7 @@ //Email notification on a full build failure -def promote_email(String status) { +def promote_failure_email() { + echo('notifying users') + //Since tokenizer doesn't work, figure stuff out from the environnement variables and command line //Configurations for email format @@ -113,5 +143,5 @@ - Status -------------------------------------------------------------- -PROMOTE FAILURE - ${status} +PROMOTE FAILURE """ Index: doc/LaTeXmacros/common.tex =================================================================== --- doc/LaTeXmacros/common.tex (revision 950f7a72ccf248faed22f2bbd0d7542e24948798) +++ doc/LaTeXmacros/common.tex (revision 7527e6365628dd566e55f6dbeaca1521c6718837) @@ -11,18 +11,16 @@ %% Created On : Sat Apr 9 10:06:17 2016 %% Last Modified By : Peter A. Buhr -%% Last Modified On : Tue Jul 12 20:37:57 2016 -%% Update Count : 206 +%% Last Modified On : Sun Aug 14 08:27:29 2016 +%% Update Count : 231 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \setlength{\textheight}{9in} %\oddsidemargin 0.0in -\renewcommand{\topfraction}{0.8} % float must be greater than X of the page before it is forced onto its own page -\renewcommand{\bottomfraction}{0.8} % float must be greater than X of the page before it is forced onto its own page +\renewcommand{\topfraction}{0.8} % float must be greater than X of the page before it is forced onto its own page +\renewcommand{\bottomfraction}{0.8} % float must be greater than X of the page before it is forced onto its own page \renewcommand{\floatpagefraction}{0.8} % float must be greater than X of the page before it is forced onto its own page -\renewcommand{\textfraction}{0.0} % the entire page maybe devoted to floats with no text on the page at all - -\lefthyphenmin=4 +\renewcommand{\textfraction}{0.0} % the entire page maybe devoted to floats with no text on the page at all + +\lefthyphenmin=4 % hyphen only after 4 characters \righthyphenmin=4 @@ -38,8 +36,9 @@ % Names used in the document. -\newcommand{\CFA}{C$\mathbf\forall$\xspace} % set language symbolic name -\newcommand{\CFL}{Cforall\xspace} % set language text name +\newcommand{\CFA}{C$\mathbf\forall$\xspace} % set language symbolic name +\newcommand{\CFL}{Cforall\xspace} % set language text name \newcommand{\CC}{\rm C\kern-.1em\hbox{+\kern-.25em+}\xspace} % CC symbolic name -\def\c11{ISO/IEC C} % C11 name (cannot have numbers in latex command name) +\newcommand{\CCeleven}{\rm C\kern-.1em\hbox{+\kern-.25em+}11\xspace} % C++11 symbolic name +\newcommand{\Celeven}{C11\xspace} % C11 symbolic name %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -51,5 +50,5 @@ \setlength{\parindentlnth}{\parindent} -\newlength{\gcolumnposn} +\newlength{\gcolumnposn} % temporary hack because lstlisting does handle tabs correctly \newlength{\columnposn} \setlength{\gcolumnposn}{2.5in} @@ -62,6 +61,6 @@ %\patchcmd{\lsthk@TextStyle}{\let\lst@DefEsc\@empty}{}{}{\errmessage{failed to patch}} -\usepackage{pslatex} % reduce size of san serif font -\usepackage{relsize} % must be after change to small or selects old size +\usepackage{pslatex} % reduce size of san serif font +\usepackage{relsize} % must be after change to small or selects old size % reduce size of chapter/section titles @@ -119,12 +118,13 @@ % inline text and lowercase index: \Index{inline and lowercase index text} +\newcommand{\Index}{\@ifstar\@sIndex\@Index} % inline text and as-in index: \Index[as-is index text]{inline text} +\newcommand{\@Index}[2][\@empty]{\lowercase{\def\temp{#2}}#2\ifx#1\@empty\index{\temp}\else\index{#1@{\protect#2}}\fi} % inline text but index with different as-is text: \Index[index text]{inline text} -\newcommand{\Index}{\@ifstar\@sIndex\@Index} -\newcommand{\@Index}[2][\@empty]{\lowercase{\def\temp{#2}}#2\ifx#1\@empty\index{\temp}\else\index{#1@{\protect#2}}\fi} \newcommand{\@sIndex}[2][\@empty]{#2\ifx#1\@empty\index{#2}\else\index{#1@{\protect#2}}\fi} -% cannot use © +% inline text and code index (cannot use ©) \newcommand{\Indexc}[1]{\lstinline$#1$\index{#1@\lstinline$#1$}} +% code index (cannot use ©) \newcommand{\indexc}[1]{\index{#1@\lstinline$#1$}} @@ -136,4 +136,25 @@ \newcommand{\@newterm}[2][\@empty]{\lowercase{\def\temp{#2}}{\newtermFontInline{#2}}\ifx#1\@empty\index{\temp}\else\index{#1@{\protect#2}}\fi} \newcommand{\@snewterm}[2][\@empty]{{\newtermFontInline{#2}}\ifx#1\@empty\index{#2}\else\index{#1@{\protect#2}}\fi} + +% Latin abbreviation +\newcommand{\abbrevFont}{\textit} % set empty for no italics +\newcommand*{\eg}{% + \@ifnextchar{,}{\abbrevFont{e}.\abbrevFont{g}.}% + {\@ifnextchar{:}{\abbrevFont{e}.\abbrevFont{g}.}% + {\abbrevFont{e}.\abbrevFont{g}.,\xspace}}% +}% +\newcommand*{\ie}{% + \@ifnextchar{,}{\abbrevFont{i}.\abbrevFont{e}.}% + {\@ifnextchar{:}{\abbrevFont{i}.\abbrevFont{e}.}% + {\abbrevFont{i}.\abbrevFont{e}.,\xspace}}% +}% +\newcommand*{\etc}{% + \@ifnextchar{.}{\abbrevFont{etc}}% + {\abbrevFont{etc}.\xspace}% +}% +\newcommand{\etal}{% + \@ifnextchar{.}{\abbrevFont{et~al}}% + {\abbrevFont{et al}.\xspace}% +}% \makeatother @@ -144,4 +165,5 @@ \endlist }% quote2 + \newenvironment{rationale}{% \begin{quote2}\noindent$\Box$\enspace @@ -187,5 +209,5 @@ \newcommand{\VPageref}[2][page]{\ifx#1\@empty\else{#1}\nobreakspace\fi\pageref{#2}} -% Go programming language +% Go programming language: https://github.com/julienc91/listings-golang/blob/master/listings-golang.sty \lstdefinelanguage{Golang}{ morekeywords=[1]{package,import,func,type,struct,return,defer,panic, recover,select,var,const,iota,},% @@ -203,9 +225,9 @@ } -% CFA programming language, based on ANSI C +% CFA programming language, based on ANSI C (with some gcc additions) \lstdefinelanguage{CFA}[ANSI]{C}{ morekeywords={_Alignas,_Alignof,__alignof,__alignof__,asm,__asm,__asm__,_At,_Atomic,__attribute,__attribute__,auto, _Bool,catch,catchResume,choose,_Complex,__complex,__complex__,__const,__const__,disable,dtype,enable,__extension__, - fallthru,finally,forall,ftype,_Generic,_Imaginary,inline,__label__,lvalue,_Noreturn,otype,restrict,_Static_assert, + fallthrough,fallthru,finally,forall,ftype,_Generic,_Imaginary,inline,__label__,lvalue,_Noreturn,otype,restrict,_Static_assert, _Thread_local,throw,throwResume,trait,try,typeof,__typeof,__typeof__,}, }% @@ -214,18 +236,18 @@ language=CFA, columns=fullflexible, -basicstyle=\linespread{0.9}\sf, -stringstyle=\tt, -tabsize=4, -xleftmargin=\parindentlnth, -extendedchars=true, -escapechar=§, -mathescape=true, -keepspaces=true, -showstringspaces=false, -showlines=true, -aboveskip=4pt, +basicstyle=\linespread{0.9}\sf, % reduce line spacing and use sanserif font +stringstyle=\tt, % use typewriter font +tabsize=4, % 4 space tabbing +xleftmargin=\parindentlnth, % indent code to paragraph indentation +extendedchars=true, % allow ASCII characters in the range 128-255 +escapechar=§, % escape to latex in CFA code +mathescape=true, % allow $...$ LaTeX math escapes in code +%keepspaces=true, % +showstringspaces=false, % do not show spaces with cup +showlines=true, % show blank lines at end of code +aboveskip=4pt, % spacing above/below code block belowskip=3pt, -moredelim=**[is][\color{red}]{®}{®}, % red highlighting -moredelim=**[is][\color{blue}]{ß}{ß}, % blue highlighting +moredelim=**[is][\color{red}]{®}{®}, % red highlighting +moredelim=**[is][\color{blue}]{ß}{ß}, % blue highlighting moredelim=**[is][\color{OliveGreen}]{¢}{¢}, % green highlighting moredelim=[is][\lstset{keywords={}}]{¶}{¶}, % temporarily turn off keywords @@ -233,5 +255,5 @@ literate={-}{\raisebox{-0.15ex}{\texttt{-}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1 {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 {_}{\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}}1 {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1 - {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {...}{$\dots$}2, + {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2, }% @@ -241,5 +263,5 @@ \renewcommand\thebibliography[1]{ \Oldthebibliography{#1} - \setlength{\parskip}{0pt} % reduce vertical spacing between references + \setlength{\parskip}{0pt} % reduce vertical spacing between references \setlength{\itemsep}{5pt plus 0.3ex} }% Index: doc/aaron_comp_II/.gitignore =================================================================== --- doc/aaron_comp_II/.gitignore (revision 7527e6365628dd566e55f6dbeaca1521c6718837) +++ doc/aaron_comp_II/.gitignore (revision 7527e6365628dd566e55f6dbeaca1521c6718837) @@ -0,0 +1,14 @@ +# generated by latex +*.aux +*.bbl +*.blg +*.brf +*.dvi +*.idx +*.ilg +*.ind +*.log +*.out +*.pdf +*.ps +*.toc Index: doc/aaron_comp_II/Makefile =================================================================== --- doc/aaron_comp_II/Makefile (revision 7527e6365628dd566e55f6dbeaca1521c6718837) +++ doc/aaron_comp_II/Makefile (revision 7527e6365628dd566e55f6dbeaca1521c6718837) @@ -0,0 +1,78 @@ +## Define the appropriate configuration variables. + +TeXLIB = .:../LaTeXmacros:../LaTeXmacros/listings:../LaTeXmacros/enumitem:../bibliography/: +LaTeX = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error +BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex + +## Define the text source files. + +SOURCES = ${addsuffix .tex, \ +comp_II \ +} + +FIGURES = ${addsuffix .tex, \ +} + +PICTURES = ${addsuffix .pstex, \ +} + +PROGRAMS = ${addsuffix .tex, \ +} + +GRAPHS = ${addsuffix .tex, \ +} + +## Define the documents that need to be made. + +DOCUMENT = comp_II.pdf + +# Directives # + +all : ${DOCUMENT} + +clean : + rm -f *.bbl *.aux *.dvi *.idx *.ilg *.ind *.brf *.out *.log *.toc *.blg *.pstex_t *.cf \ + ${FIGURES} ${PICTURES} ${PROGRAMS} ${GRAPHS} ${basename ${DOCUMENT}}.ps ${DOCUMENT} + +# File Dependencies # + +${DOCUMENT} : ${basename ${DOCUMENT}}.ps + ps2pdf $< + +${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi + dvips $< -o $@ + +${basename ${DOCUMENT}}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex \ + ../LaTeXmacros/common.tex ../LaTeXmacros/indexstyle ../bibliography/cfa.bib + # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run. + if [ ! -r ${basename $@}.ind ] ; then touch ${basename $@}.ind ; fi + # Must have *.aux file containing citations for bibtex + if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi + -${BibTeX} ${basename $@} + # Some citations reference others so run steps again to resolve these citations + ${LaTeX} ${basename $@}.tex + -${BibTeX} ${basename $@} + # Make index from *.aux entries and input index at end of document + makeindex -s ../LaTeXmacros/indexstyle ${basename $@}.idx + ${LaTeX} ${basename $@}.tex + # Run again to get index title into table of contents + ${LaTeX} ${basename $@}.tex + +predefined : + sed -f predefined.sed ${basename ${DOCUMENT}}.tex > ${basename $@}.cf + +## Define the default recipes. + +%.tex : %.fig + fig2dev -L eepic $< > $@ + +%.ps : %.fig + fig2dev -L ps $< > $@ + +%.pstex : %.fig + fig2dev -L pstex $< > $@ + fig2dev -L pstex_t -p $@ $< > $@_t + +# Local Variables: # +# compile-command: "make" # +# End: # Index: doc/aaron_comp_II/comp_II.tex =================================================================== --- doc/aaron_comp_II/comp_II.tex (revision 7527e6365628dd566e55f6dbeaca1521c6718837) +++ doc/aaron_comp_II/comp_II.tex (revision 7527e6365628dd566e55f6dbeaca1521c6718837) @@ -0,0 +1,603 @@ +% inline code ©...© (copyright symbol) emacs: C-q M-) +% red highlighting ®...® (registered trademark symbol) emacs: C-q M-. +% blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_ +% green highlighting ¢...¢ (cent symbol) emacs: C-q M-" +% LaTex escape §...§ (section symbol) emacs: C-q M-' +% keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^ +% math escape $...$ (dollar symbol) + +\documentclass[twoside,11pt]{article} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +% Latex packages used in the document (copied from CFA user manual). +\usepackage[T1]{fontenc} % allow Latin1 (extended ASCII) characters +\usepackage{textcomp} +\usepackage[latin1]{inputenc} +\usepackage{fullpage,times,comment} +\usepackage{epic,eepic} +\usepackage{upquote} % switch curled `'" to straight +\usepackage{calc} +\usepackage{xspace} +\usepackage{graphicx} +\usepackage{varioref} % extended references +\usepackage{listings} % format program code +\usepackage[flushmargin]{footmisc} % support label/reference in footnote +\usepackage{latexsym} % \Box glyph +\usepackage{mathptmx} % better math font with "times" +\usepackage[usenames]{color} +\usepackage[pagewise]{lineno} +\renewcommand{\linenumberfont}{\scriptsize\sffamily} +\input{common} % bespoke macros used in the document +\usepackage[dvips,plainpages=false,pdfpagelabels,pdfpagemode=UseNone,colorlinks=true,pagebackref=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pagebackref=true,breaklinks=true]{hyperref} +\usepackage{breakurl} +\renewcommand{\UrlFont}{\small\sf} + +\setlength{\topmargin}{-0.45in} % move running title into header +\setlength{\headsep}{0.25in} + +\usepackage{caption} +\usepackage{subcaption} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\newsavebox{\LstBox} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\title{ +\Huge \vspace*{1in} Efficient Type Resolution in \CFA \\ +\huge \vspace*{0.25in} PhD Comprehensive II Research Proposal +\vspace*{1in} +} + +\author{ +\huge Aaron Moss \\ +\Large \vspace*{0.1in} \texttt{a3moss@uwaterloo.ca} \\ +\Large Cheriton School of Computer Science \\ +\Large University of Waterloo +} + +\date{ +\today +} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\newcommand{\bigO}[1]{O\!\left( #1 \right)} + +\begin{document} +\pagestyle{headings} +% changed after setting pagestyle +\renewcommand{\sectionmark}[1]{\markboth{\thesection\quad #1}{\thesection\quad #1}} +\renewcommand{\subsectionmark}[1]{\markboth{\thesubsection\quad #1}{\thesubsection\quad #1}} +\pagenumbering{roman} +\linenumbers % comment out to turn off line numbering + +\maketitle +\thispagestyle{empty} + +\clearpage +\thispagestyle{plain} +\pdfbookmark[1]{Contents}{section} +\tableofcontents + +\clearpage +\thispagestyle{plain} +\pagenumbering{arabic} + +\section{Introduction} + +\CFA\footnote{Pronounced ``C-for-all'', and written \CFA or \CFL.} is an evolutionary modernization of the C programming language currently being designed and built at the University of Waterloo by a team led by Peter Buhr. +\CFA both fixes existing design problems and adds multiple new features to C, including name overloading, user-defined operators, parametric-polymorphic routines, and type constructors and destructors, among others. +The new features make \CFA significantly more powerful and expressive than C, but impose a significant compile-time cost, particularly in the expression resolver, which must evaluate the typing rules of a much more complex type-system. + +The primary goal of this research project is to develop a sufficiently performant expression resolution algorithm, experimentally validate its performance, and integrate it into CFA, the \CFA reference compiler. +Secondary goals of this project include the development of various new language features for \CFA: parametric-polymorphic (``generic'') types have already been designed and implemented, and reference types and user-defined conversions are under design consideration. +An experimental performance-testing architecture for resolution algorithms is under development to determine the relative performance of different expression resolution algorithms, as well as the compile-time cost of adding various new features to the \CFA type-system. +More broadly, this research should provide valuable data for implementers of compilers for other programming languages with similarly powerful static type-systems. + +\section{\CFA} + +To make the scope of the proposed expression resolution problem more explicit, it is necessary to define the features of both C and \CFA (both current and proposed) that affect this algorithm. +In some cases the interactions of multiple features make expression resolution a significantly more complex problem than any individual feature would; in other cases a feature that does not by itself add any complexity to expression resolution triggers previously rare edge cases more frequently. + +It is important to note that \CFA is not an object-oriented language. +\CFA does have a system of (possibly implicit) type conversions derived from C's type conversions; while these conversions may be thought of as something like an inheritance hierarchy the underlying semantics are significantly different and such an analogy is loose at best. +Particularly, \CFA has no concept of ``subclass'', and thus no need to integrate an inheritance-based form of polymorphism with its parametric and overloading-based polymorphism. +The graph structure of the \CFA type conversions is also markedly different than an inheritance graph; it has neither a top nor a bottom type, and does not satisfy the lattice properties typical of inheritance graphs. + +\subsection{Polymorphic Functions} +The most significant feature \CFA adds is parametric-polymorphic functions. +Such functions are written using a ©forall© clause (which gives the language its name): +\begin{lstlisting} +®forall(otype T)® +T identity(T x) { + return x; +} + +int forty_two = identity(42); // T is bound to int, forty_two == 42 +\end{lstlisting} +The ©identity© function above can be applied to any complete object type (or ``©otype©''). +The type variable ©T© is transformed into a set of additional implicit parameters to ©identity© which encode sufficient information about ©T© to create and return a variable of that type. +The current \CFA implementation passes the size and alignment of the type represented by an ©otype© parameter, as well as an assignment operator, constructor, copy constructor and destructor. +Here, the runtime cost of polymorphism is spread over each polymorphic call, due to passing more arguments to polymorphic functions; preliminary experiments have shown this overhead to be similar to \CC virtual function calls. +Determining if packaging all polymorphic arguments to a function into a virtual function table would reduce the runtime overhead of polymorphic calls is an open research question. + +Since bare polymorphic types do not provide a great range of available operations, \CFA also provides a \emph{type assertion} mechanism to provide further information about a type: +\begin{lstlisting} +forall(otype T ®| { T twice(T); }®) +T four_times(T x) { + return twice( twice(x) ); +} + +double twice(double d) { return d * 2.0; } // (1) + +double magic = four_times(10.5); // T is bound to double, uses (1) to satisfy type assertion +\end{lstlisting} +These type assertions may be either variable or function declarations that depend on a polymorphic type variable. +©four_times© can only be called with an argument for which there exists a function named ©twice© that can take that argument and return another value of the same type; a pointer to the appropriate ©twice© function is passed as an additional implicit parameter to the call to ©four_times©. + +Monomorphic specializations of polymorphic functions can themselves be used to satisfy type assertions. +For instance, ©twice© could have been defined using the \CFA syntax for operator overloading as: +\begin{lstlisting} +forall(otype S | { ®S ?+?(S, S);® }) +S twice(S x) { return x + x; } // (2) +\end{lstlisting} +This version of ©twice© works for any type ©S© that has an addition operator defined for it, and it could have been used to satisfy the type assertion on ©four_times©. +The compiler accomplishes this by creating a wrapper function calling ©twice // (2)© with ©S© bound to ©double©, then providing this wrapper function to ©four_times©\footnote{©twice // (2)© could also have had a type parameter named ©T©; \CFA specifies renaming of the type parameters, which would avoid the name conflict with the type variable ©T© of ©four_times©.}. + +Finding appropriate functions to satisfy type assertions is essentially a recursive case of expression resolution, as it takes a name (that of the type assertion) and attempts to match it to a suitable declaration in the current scope. +If a polymorphic function can be used to satisfy one of its own type assertions, this recursion may not terminate, as it is possible that function is examined as a candidate for its own type assertion unboundedly repeatedly. +To avoid infinite loops, the current CFA compiler imposes a fixed limit on the possible depth of recursion, similar to that employed by most \CC compilers for template expansion; this restriction means that there are some semantically well-typed expressions that cannot be resolved by CFA. +One area of potential improvement this project proposes to investigate is the possibility of using the compiler's knowledge of the current set of declarations to more precicely determine when further type assertion satisfaction recursion does not produce a well-typed expression. + +\subsubsection{Traits} +\CFA provides \emph{traits} as a means to name a group of type assertions, as in the example below: +\begin{lstlisting} +®trait has_magnitude(otype T)® { + bool ?value; +} +\end{lstlisting} + +In the example above, ©(list_iterator, int)© satisfies ©pointer_like© by the given function, and ©(list_iterator, list)© also satisfies ©pointer_like© by the built-in pointer dereference operator. +While a nominal-inheritance system with associated types could model one of those two relationships by making ©El© an associated type of ©Ptr© in the ©pointer_like© implementation, few such systems could model both relationships simultaneously. + +The flexibility of \CFA's implicit trait satisfaction mechanism provides programmers with a great deal of power, but also blocks some optimization approaches for expression resolution. +The ability of types to begin to or cease to satisfy traits when declarations go into or out of scope makes caching of trait satisfaction judgements difficult, and the ability of traits to take multiple type parameters could lead to a combinatorial explosion of work in any attempt to pre-compute trait satisfaction relationships. +On the other hand, the addition of a nominal inheritance mechanism to \CFA's type system or replacement of \CFA's trait satisfaction system with a more object-oriented inheritance model and investigation of possible expression resolution optimizations for such a system may be an interesting avenue of further research. + +\subsection{Name Overloading} +In C, no more than one variable or function in the same scope may share the same name\footnote{Technically, C has multiple separated namespaces, one holding ©struct©, ©union©, and ©enum© tags, one holding labels, one holding typedef names, variable, function, and enumerator identifiers, and one for each ©struct© or ©union© type holding the field names.}, and variable or function declarations in inner scopes with the same name as a declaration in an outer scope hide the outer declaration. +This makes finding the proper declaration to match to a variable expression or function application a simple matter of symbol table lookup, which can be easily and efficiently implemented. +\CFA, on the other hand, allows overloading of variable and function names, so long as the overloaded declarations do not have the same type, avoiding the multiplication of variable and function names for different types common in the C standard library, as in the following example: +\begin{lstlisting} +#include + +int max(int a, int b) { return a < b ? b : a; } // (1) +double max(double a, double b) { return a < b ? b : a; } // (2) + +int max = INT_MAX; // (3) +double max = DBL_MAX; // (4) + +max(7, -max); // uses (1) and (3), by matching int type of 7 +max(max, 3.14); // uses (2) and (4), by matching double type of 3.14 + +max(max, -max); // ERROR: ambiguous +int m = max(max, -max); // uses (1) and (3) twice, by return type +\end{lstlisting} + +The presence of name overloading in \CFA means that simple table lookup is insufficient to match identifiers to declarations, and a type matching algorithm must be part of expression resolution. + +\subsection{Implicit Conversions} +In addition to the multiple interpretations of an expression produced by name overloading, \CFA also supports all of the implicit conversions present in C, producing further candidate interpretations for expressions. +C does not have a traditionally-defined inheritance hierarchy of types, but the C standard's rules for the ``usual arithmetic conversions'' define which of the built-in types are implicitly convertable to which other types, and the relative cost of any pair of such conversions from a single source type. +\CFA adds to the usual arithmetic conversions rules for determining the cost of binding a polymorphic type variable in a function call; such bindings are cheaper than any \emph{unsafe} (narrowing) conversion, \eg ©int© to ©char©, but more expensive than any \emph{safe} (widening) conversion, \eg ©int© to ©double©. + +The expression resolution problem, then, is to find the unique minimal-cost interpretation of each expression in the program, where all identifiers must be matched to a declaration and implicit conversions or polymorphic bindings of the result of an expression may increase the cost of the expression. +Note that which subexpression interpretation is minimal-cost may require contextual information to disambiguate. +For instance, in the example in the previous subsection, ©max(max, -max)© cannot be unambiguously resolved, but ©int m = max(max, -max);© has a single minimal-cost resolution. +©int m = (int)max((double)max, -(double)max)© is also be a valid interpretation, but is not minimal-cost due to the unsafe cast from the ©double© result of ©max© to ©int© (the two ©double© casts function as type ascriptions selecting ©double max© rather than casts from ©int max© to ©double©, and as such are zero-cost). + +\subsubsection{User-generated Implicit Conversions} +One possible additional feature to \CFA included in this research proposal is \emph{user-generated implicit conversions}. +Such a conversion system should be simple for programmers to utilize, and fit naturally with the existing design of implicit conversions in C; ideally it would also be sufficiently powerful to encode C's usual arithmetic conversions itself, so that \CFA only has one set of rules for conversions. + +Ditchfield~\cite{Ditchfield:conversions} has laid out a framework for using polymorphic-conversion-constructor functions to create a directed acyclic graph (DAG) of conversions. +A monomorphic variant of these functions can be used to mark a conversion arc in the DAG as only usable as the final step in a conversion. +With these two types of conversion arcs, separate DAGs can be created for the safe and the unsafe conversions, and conversion cost can be represented as path length through the DAG. +\begin{figure}[h] +\centering +\includegraphics{conversion_dag} +\caption{A portion of the implicit conversion DAG for built-in types.} +\end{figure} +As can be seen in the example DAG above, there are either safe or unsafe paths between each of the arithmetic types listed; the ``final'' arcs are important both to avoid creating cycles in the signed-unsigned conversions, and to disambiguate potential diamond conversions (\eg, if the ©int© to ©unsigned int© conversion was not marked final there would be two length-two paths from ©int© to ©unsigned long©, and it would be impossible to choose which one; however, since the ©unsigned int© to ©unsigned long© arc can not be traversed after the final ©int© to ©unsigned int© arc, there is a single unambiguous conversion path from ©int© to ©unsigned long©). + +Open research questions on this topic include: +\begin{itemize} +\item Can a conversion graph be generated that represents each allowable conversion in C with a unique minimal-length path such that the path lengths accurately represent the relative costs of the conversions? +\item Can such a graph representation can be usefully augmented to include user-defined types as well as built-in types? +\item Can the graph can be efficiently represented and used in the expression resolver? +\end{itemize} + +\subsection{Constructors and Destructors} +Rob Shluntz, a current member of the \CFA research team, has added constructors and destructors to \CFA. +Each type has an overridable default-generated zero-argument constructor, copy constructor, assignment operator, and destructor; for ©struct© types these functions each call their equivalents on each field of the ©struct©. +This affects expression resolution because an ©otype© type variable ©T© implicitly adds four type assertions, one for each of these four functions, so assertion resolution is pervasive in \CFA polymorphic functions, even those without any explicit type assertions. +The following example shows the implicitly-generated code in green: +\begin{lstlisting} +struct kv { + int key; + char *value; +}; + +¢void ?{}(kv *this) { + ?{}(&this->key); + ?{}(&this->value); +} +void ?{}(kv *this, kv that) { + ?{}(&this->key, that.key); + ?{}(&this->value, that.value); +} +kv ?=?(kv *this, kv that) { + ?=?(&this->key, that.key); + ?=?(&this->value, that.value); + return *this; +} +void ^?{}(kv *this) { + ^?{}(&this->key); + ^?{}(&this->value); +}¢ + +forall(otype T ¢| { void ?{}(T*); void ?{}(T*, T); T ?=?(T*, T); void ^?{}(T*); }¢) +void foo(T); +\end{lstlisting} + +\subsection{Generic Types} +I have already added a generic type capability to \CFA, designed to efficiently and naturally integrate with \CFA's existing polymorphic functions. +A generic type can be declared by placing a ©forall© specifier on a ©struct© or ©union© declaration, and instantiated using a parenthesized list of types after the type name: +\begin{lstlisting} +forall(otype R, otype S) struct pair { + R first; + S second; +}; + +forall(otype T) +T value( pair(const char*, T) *p ) { return p->second; } + +pair(const char*, int) p = { "magic", 42 }; +int magic = value( &p ); +\end{lstlisting} +For \emph{concrete} generic types, that is, those where none of the type parameters depend on polymorphic type variables (like ©pair(const char*, int)© above), the struct is essentially template expanded to a new struct type; for \emph{polymorphic} generic types (such as ©pair(const char*, T)© above), member access is handled by a runtime calculation of the field offset, based on the size and alignment information of the polymorphic parameter type. +The default-generated constructors, destructor and assignment operator for a generic type are polymorphic functions with the same list of type parameters as the generic type definition. + +Aside from giving users the ability to create more parameterized types than just the built-in pointer, array and function types, the combination of generic types with polymorphic functions and implicit conversions makes the edge case where the resolver may enter an infinite loop much more common, as in the following code example: +\begin{lstlisting} +forall(otype T) struct box { T x; }; + +void f(void*); // (1) + +forall(otype S) +void f(box(S)* b) { // (2) + f(®(void*)0®); +} +\end{lstlisting} + +The loop in the resolver happens as follows: +\begin{itemize} +\item Since there is an implicit conversion from ©void*© to any pointer type, the highlighted expression can be interpreted as either a ©void*©, matching ©f // (1)©, or a ©box(S)*© for some type ©S©, matching ©f // (2)©. +\item To determine the cost of the ©box(S)© interpretation, a type must be found for ©S© which satisfies the ©otype© implicit type assertions (assignment operator, default and copy constructors, and destructor); one option is ©box(S2)© for some type ©S2©. +\item The assignment operator, default and copy constructors, and destructor of ©box(T)© are also polymorphic functions, each of which require the type parameter ©T© to have an assignment operator, default and copy constructors, and destructor. When choosing an interpretation for ©S2©, one option is ©box(S3)©, for some type ©S3©. +\item The previous step repeats until stopped, with four times as much work performed at each step. +\end{itemize} +This problem can occur in any resolution context where a polymorphic function that can satisfy its own type assertions is required for a possible interpretation of an expression with no constraints on its type, and is thus not limited to combinations of generic types with ©void*© conversions, though constructors for generic types often satisfy their own assertions and a polymorphic conversion such as the ©void*© conversion to a polymorphic variable can create an expression with no constraints on its type. +As discussed above, the \CFA expression resolver must handle this possible infinite recursion somehow, and it occurs fairly naturally in code like the above that uses generic types. + +\subsection{Tuple Types} +\CFA adds \emph{tuple types} to C, a syntactic facility for referring to lists of values anonymously or with a single identifier. +An identifier may name a tuple, and a function may return one. +Particularly relevantly for resolution, a tuple may be implicitly \emph{destructured} into a list of values, as in the call to ©swap© below: +\begin{lstlisting} +[char, char] x = [ '!', '?' ]; +int x = 42; + +forall(otype T) [T, T] swap( T a, T b ) { return [b, a]; } + +x = swap( x ); // destructure [char, char] x into two elements of parameter list +// cannot use int x for parameter, not enough arguments to swap +\end{lstlisting} +Tuple destructuring means that the mapping from the position of a subexpression in the argument list to the position of a paramter in the function declaration is not straightforward, as some arguments may be expandable to different numbers of parameters, like ©x© above. + +\subsection{Reference Types} +I have been designing \emph{reference types} for \CFA, in collaboration with the rest of the \CFA research team. +Given some type ©T©, a ©T&© (``reference to ©T©'') is essentially an automatically dereferenced pointer; with these semantics most of the C standard's discussions of lvalues can be expressed in terms of references instead, with the benefit of being able to express the difference between the reference and non-reference version of a type in user code. +References preserve C's existing qualifier-dropping lvalue-to-rvalue conversion (\eg a ©const volatile int&© can be implicitly converted to a bare ©int©); the reference proposal also adds a rvalue-to-lvalue conversion to \CFA, implemented by storing the value in a new compiler-generated temporary and passing a reference to the temporary. +These two conversions can chain, producing a qualifier-dropping conversion for references, for instance converting a reference to a ©const int© into a reference to a non-©const int© by copying the originally refered to value into a fresh temporary and taking a reference to this temporary, as below: +\begin{lstlisting} +const int magic = 42; + +void inc_print( int& x ) { printf("%d\n", ++x); } + +print_inc( magic ); // legal; implicitly generated code in green below: + +¢int tmp = magic;¢ // copies to safely strip const-qualifier +¢print_inc( tmp );¢ // tmp is incremented, magic is unchanged +\end{lstlisting} +These reference conversions may also chain with the other implicit type conversions. +The main implication of this for expression resolution is the multiplication of available implicit conversions, though in a restricted context that may be able to be treated efficiently as a special case. + +\subsection{Special Literal Types} +Another proposal currently under consideration for the \CFA type-system is assigning special types to the literal values ©0© and ©1©. +Implicit conversions from these types allow ©0© and ©1© to be considered as values of many different types, depending on context, allowing expression desugarings like ©if ( x ) {}© $\Rightarrow$ ©if ( x != 0 ) {}© to be implemented efficiently and precicely. +This approach is a generalization of C's existing behaviour of treating ©0© as either an integer zero or a null pointer constant, and treating either of those values as boolean false. +The main implication for expression resolution is that the frequently encountered expressions ©0© and ©1© may have a large number of valid interpretations. + +\subsection{Deleted Function Declarations} +One final proposal for \CFA with an impact on the expression resolver is \emph{deleted function declarations}; in \CCeleven, a function declaration can be deleted as below: +\begin{lstlisting} +int somefn(char) = delete; +\end{lstlisting} +This feature is typically used in \CCeleven to make a type non-copyable by deleting its copy constructor and assignment operator, or forbidding some interpretations of a polymorphic function by specifically deleting the forbidden overloads. +To add a similar feature to \CFA would involve including the deleted function declarations in expression resolution along with the normal declarations, but producing a compiler error if the deleted function was the best resolution. +How conflicts should be handled between resolution of an expression to both a deleted and a non-deleted function is a small but open research question. + +\section{Expression Resolution} +The expression resolution problem is determining an optimal match between some combination of argument interpretations and the parameter list of some overloaded instance of a function; the argument interpretations are produced by recursive invocations of expression resolution, where the base case is zero-argument functions (which are, for purposes of this discussion, semantically equivalent to named variables or constant literal expressions). +Assuming that the matching between a function's parameter list and a combination of argument interpretations can be done in $\bigO{p^k}$ time, where $p$ is the number of parameters and $k$ is some positive number, if there are $\bigO{i}$ valid interpretations for each subexpression, there will be $\bigO{i}$ candidate functions and $\bigO{i^p}$ possible argument combinations for each expression, so for a single recursive call expression resolution takes $\bigO{i^{p+1} \cdot p^k}$ time if it must compare all combinations, or $\bigO{i(p+1) \cdot p^k}$ time if argument-parameter matches can be chosen independently of each other. +Given these bounds, resolution of a single top-level expression tree of depth $d$ takes $\bigO{i^{p+1} \cdot p^{k \cdot d}}$ time under full-combination matching, or $\bigO{i(p+1) \cdot p^{k \cdot d}}$ time for independent-parameter matching\footnote{A call tree has leaves at depth $\bigO{d}$, and each internal node has $\bigO{p}$ fan-out, producing $\bigO{p^d}$ total recursive calls.}. + +Expression resolution is somewhat unavoidably exponential in $d$, the depth of the expression tree, and if arguments cannot be matched to parameters independently of each other, expression resolution is also exponential in $p$. +However, both $d$ and $p$ are fixed by the programmer, and generally bounded by reasonably small constants. +$k$, on the other hand, is mostly dependent on the representation of types in the system and the efficiency of type assertion checking; if a candidate argument combination can be compared to a function parameter list in linear time in the length of the list (\ie $k = 1$), then the $p^{k \cdot d}$ factor is linear in the input size of the source code for the expression, otherwise the resolution algorithm exibits sub-linear performance scaling on code containing more-deeply nested expressions. +The number of valid interpretations of any subexpression, $i$, is bounded by the number of types in the system, which is possibly infinite, though practical resolution algorithms for \CFA must be able to place some finite bound on $i$, possibly at the expense of type-system completeness. + +The research goal of this project is to develop a performant expression resolver for \CFA; this analysis suggests three primary areas of investigation to accomplish that end. +The first area of investigation is efficient argument-parameter matching; Bilson~\cite{Bilson03} mentions significant optimization opportunities available in the current literature to improve on the existing CFA compiler. +%TODO: look up and lit review +The second area of investigation is minimizing dependencies between argument-parameter matches; the current CFA compiler attempts to match entire argument combinations against functions at once, potentially attempting to match the same argument against the same parameter multiple times. +Whether the feature set of \CFA admits an expression resolution algorithm where arguments can be matched to parameters independently of other arguments in the same function application is an area of open research; polymorphic type paramters produce enough of a cross-argument dependency that the problem is not trivial. +If cross-argument resolution dependencies cannot be completely eliminated, effective caching strategies to reduce duplicated work between equivalent argument-parameter matches in different combinations may mitigate the asymptotic defecits of the whole-combination matching approach. +The final area of investigation is heuristics and algorithmic approaches to reduce the number of argument interpretations considered in the common case; if argument-parameter matches cannot be made independent, even small reductions in $i$ should yield significant reductions in the $i^{p+1}$ resolver runtime factor. + +The discussion below presents a number of largely orthagonal axes for expression resolution algorithm design to be investigated, noting prior work where applicable. +Though some of the proposed improvements to the expression resolution algorithm are based on heuristics rather than asymptoticly superior algorithms, it should be noted that programmers often employ idioms and other programming patterns to reduce the mental burden of producing correct code, and if these patterns can be identified and exploited by the compiler then the significant reduction in expression resolution time for common, idiomatic expressions should result in lower total compilation time even for code including difficult-to-resolve expressions that push the expression resolver to its theoretical worst case. + +\subsection{Argument-Parameter Matching} +The first axis for consideration is argument-parameter matching direction --- whether the type matching for a candidate function to a set of candidate arguments is directed by the argument types or the parameter types. +For programming languages without implicit conversions, argument-parameter matching is essentially the entirety of the expression resolution problem, and is generally referred to as ``overload resolution'' in the literature. +All expression resolution algorithms form a DAG of interpretations, some explicitly, some implicitly; in this DAG, arcs point from function-call interpretations to argument interpretations, as below: +\begin{figure}[h] +\centering +\begin{subfigure}[h]{2in} +\begin{lstlisting} +int *p; // $p_i$ +char *p; // $p_c$ + +double *f(int*, int*); // $f_d$ +char *f(char*, int*); // $f_c$ + +f( f( p, p ), p ); +\end{lstlisting} +\end{subfigure}~\begin{subfigure}[h]{2in} +\includegraphics{resolution_dag} +\end{subfigure} +\caption{Resolution DAG for a simple expression. Functions that do not have a valid argument matching are covered with an \textsf{X}.}\label{fig:res_dag} +\end{figure} + +Note that some interpretations may be part of more than one super-interpretation, as with $p_i$ in the bottom row, while some valid subexpression interpretations, like $f_d$ in the middle row, are not used in any interpretation of their containing expression. + +\subsubsection{Argument-directed (Bottom-up)} +Baker's algorithm for expression resolution~\cite{Baker82} pre-computes argument candidates, from the leaves of the expression tree up. +For each candidate function, Baker attempts to match argument types to parameter types in sequence, failing if any parameter cannot be matched. + +Bilson~\cite{Bilson03} similarly pre-computes argument candidates in the original \CFA compiler, but then explicitly enumerates all possible argument combinations for a multi-parameter function; these argument combinations are matched to the parameter types of the candidate function as a unit rather than individual arguments. +This approach is less efficient than Baker's approach, as the same argument may be compared to the same parameter many times, but allows a more straightforward handling of polymorphic type-binding and multiple return-types. +It is possible the efficiency losses here relative to Baker could be significantly reduced by keeping a memoized cache of argument-parameter type comparisons and reading previously-seen argument-parameter matches from this cache rather than recomputing them. + +\subsubsection{Parameter-directed (Top-down)} +Unlike Baker and Bilson, Cormack's algorithm~\cite{Cormack81} requests argument candidates that match the type of each parameter of each candidate function, from the top-level expression down; memoization of these requests is presented as an optimization. +As presented, this algorithm requires the result of the expression to have a known type, though an algorithm based on Cormack's could reasonably request a candidate set of any return type, though such a set may be quite large. + +\subsubsection{Hybrid} +This proposal includes the investigation of hybrid top-down/bottom-up argument-parameter matching. +A reasonable hybrid approach might take a top-down approach when the expression to be matched has a fixed type, and a bottom-up approach in untyped contexts. +This approach may involve switching from one type to another at different levels of the expression tree. +For instance: +\begin{lstlisting} +forall(otype T) +int f(T x); // (1) + +void* f(char y); // (2) + +int x = f( f( '!' ) ); +\end{lstlisting} +The outer call to ©f© must have a return type that is (implicitly convertable to) ©int©, so a top-down approach is used to select \textit{(1)} as the proper interpretation of ©f©. \textit{(1)}'s parameter ©x©, however, is an unbound type variable, and can thus take a value of any complete type, providing no guidance for the choice of candidate for the inner call to ©f©. The leaf expression ©'!'©, however, determines a zero-cost interpretation of the inner ©f© as \textit{(2)}, providing a minimal-cost expression resolution where ©T© is bound to ©void*©. + +Deciding when to switch between bottom-up and top-down resolution to minimize wasted work in a hybrid algorithm is a necessarily heuristic process, and though finding good heuristics for which subexpressions to swich matching strategies on is an open question, one reasonable approach might be to set a threshold $t$ for the number of candidate functions, and to use top-down resolution for any subexpression with fewer than $t$ candidate functions, to minimize the number of unmatchable argument interpretations computed, but to use bottom-up resolution for any subexpression with at least $t$ candidate functions, to reduce duplication in argument interpretation computation between the different candidate functions. + +Ganzinger and Ripken~\cite{Ganzinger80} propose an approach (later refined by Pennello~\etal~\cite{Pennello80}) that uses a top-down filtering pass followed by a bottom-up filtering pass to reduce the number of candidate interpretations; they prove that for the Ada programming language a small number of such iterations is sufficient to converge to a solution for the expression resolution problem. +Persch~\etal~\cite{PW:overload} developed a similar two-pass approach where the bottom-up pass is followed by the top-down pass. +These algorithms differ from the hybrid approach under investigation in that they take multiple passes over the expression tree to yield a solution, and also in that they apply both filtering heuristics to all expression nodes; \CFA's polymorphic functions and implicit conversions make the approach of filtering out invalid types taken by all of these algorithms infeasible. + +\subsubsection{Common Subexpression Caching} +With any of these argument-parameter approaches, it may be a useful optimization to cache the resolution results for common subexpressions; in Figure~\ref{fig:res_dag} this optimization would result in the list of interpretations $[p_c, p_i]$ for ©p© only being calculated once, and re-used for each of the three instances of ©p©. + +\subsection{Implicit Conversion Application} +With the exception of Bilson, the authors mentioned above do not account for implicit conversions in their algorithms\footnote{Baker does briefly comment on an approach for handling implicit conversions, but does not provide an implementable algorithm.}; all assume that there is at most one valid interpretation of a given expression for each distinct type. +Integrating implicit conversion handling into the presented argument-parameter matching algorithms thus provides some choice of implementation approach. + +Inference of polymorphic type variables can be considered a form of implicit conversion application, where monomorphic types are implicitly converted to instances of some polymorphic type\footnote{This ``conversion'' may not be implemented in any explicit way at runtime, but does need to be handled by the expression resolver as an inexact match between argument and parameter types.}. +This form of implicit conversion is particularly common in functional languages; Haskell's type classes~\cite{typeclass} are a particularly well-studied variant of this inference. +However, type classes arguably do not allow name overloading, as (at least in the Haskell implmentation) identifiers belonging to type classes may not be overloaded in any other context than an implementation of that type class; this provides a single (possibly polymorphic) interpretation of any identifier, simplifing the expression resolution problem relative to \CFA. +\CC~\cite{ANSI98:C++} includes both name overloading and implicit conversions in its expression resolution specification, though unlike \CFA it does complete type-checking on a generated monomorphization of template functions, where \CFA simply checks a list of type constraints. +The upcoming Concepts standard~\cite{C++concepts} defines a system of type constraints similar in principle to \CFA's. +Cormack and Wright~\cite{Cormack90} present an algorithm which integrates overload resolution with a polymorphic type inference approach very similar to \CFA's. +However, their algorithm does not account for implicit conversions other than polymorphic type binding and their discussion of their overload resolution algorithm is not sufficiently detailed to classify it with the other argument-parameter matching approaches\footnote{Their overload resolution algorithm is possibly a variant of Ganzinger and Ripken~\cite{Ganzinger80} or Pennello~\etal~\cite{Pennello80}, modified to allow for polymorphic type binding.}. + +\subsubsection{On Parameters} +Bilson does account for implicit conversions in his algorithm, but it is unclear if the approach is optimal. +His algorithm integrates checking for valid implicit conversions into the argument-parameter-matching step, essentially trading more expensive matching for a smaller number of argument interpretations. +This approach may result in the same subexpression being checked for a type match with the same type multiple times, though again memoization may mitigate this cost, and this approach does not generate implicit conversions that are not useful to match the containing function. +Calculating implicit conversions on parameters pairs naturally with a top-down approach to expression resolution, though it can also be used in a bottom-up approach, as Bilson demonstrates. + +\subsubsection{On Arguments} +Another approach is to generate a set of possible implicit conversions for each set of interpretations of a given argument. +This approach has the benefit of detecting ambiguous interpretations of arguments at the level of the argument rather than its containing call, never finds more than one interpretation of the argument with a given type, and re-uses calculation of implicit conversions between function candidates. +On the other hand, this approach may unncessarily generate argument interpretations that never match any parameter, wasting work. +Further, in the presence of tuple types this approach may lead to a combinatorial explosion of argument interpretations considered, unless the tuple can be considered as a sequence of elements rather than a unified whole. +Calculating implicit conversions on arguments is a viable approach for bottom-up expression resolution, though it may be difficult to apply in a top-down approach due to the presence of a target type for the expression interpretation. + +\subsection{Candidate Set Generation} +All the algorithms discussed to this point generate the complete set of candidate argument interpretations before attempting to match the containing function call expression. +However, given that the top-level expression interpretation that is ultimately chosen is the minimal-cost valid interpretation, any consideration of non-minimal-cost interpretations is in some sense wasted work. +Under the assumption that that programmers generally write function calls with relatively low-cost interpretations, a possible work-saving heuristic is to generate only the lowest-cost argument interpretations first, attempt to find a valid top-level interpretation using them, and only if that fails generate the next higher-cost argument interpretations. + +\subsubsection{Eager} +Within the eager approach taken by the existing top-down and bottom-up algorithms, there are still variants to explore. +Cormack and Baker do not account for implict conversions, and thus do not account for the possibility of multiple valid interpretations with distinct costs; Bilson, on the other hand, sorts the list of interpretations to aid in finding minimal-cost interpretations. +Sorting the lists of argument or function call interpretations by cost at some point during resolution may provide useful opportunities to short-circuit expression evaluation when a minimal-cost interpretation is found, though it is unclear if this short-circuiting behaviour justifies the cost of the sort. + +\subsubsection{Lazy} +In the presence of implicit conversions, many argument interpretations may match a given parameter by application of an appropriate implicit conversion. +However, if programmers actually use relatively few implicit conversions, then the ``on arguments'' approach to implicit conversions generates a large number of high-cost interpretations that may never be used. +Even if the ``on parameters'' approach to implicit conversions is used, eager generation of interpretations spends extra time attempting possibly expensive polymorphic or conversion-based matches in cases where an exact monomorphic interpretation exists. + +The essence of the lazy approach to candidate set generation is to wrap the matching algorithm into the element generator of a lazy list, only generating as few elements at a time to ensure the next-smallest-cost interpretation has been generated. +Assuming argument interpretations are provided to the parameter matching algorithm in sorted order, a sorted list of function call interpretations can be produced by generating combinations of arguments sorted by total cost\footnote{I have already developed a lazy $n$-way combination generation algorithm to perform this task.}, then generating function call interpretations in the order suggested by this list. +The function call interpretation chosen may have costs of its own, for instance polymorphic type binding, so in some cases a number of argument combinations (any combination whose marginal cost does not exceed the cost of the function call interpretation itself) may need to be considered to determine the next-smallest-cost function call interpretation. +Ideally, this candidate generation approach leads to very few unused candidates being generated (in the expected case where the programmer has, in fact, provided a validly-typable program), but it is an open question whether or not the overheads of lazy generation exceed the benefit produced from considering fewer interpretations. + +\subsubsection{Stepwise Lazy} +As a compromise between the trade-offs of the eager and lazy approaches, I also propose to investigate a ``stepwise lazy'' approach, where all the interpretations for some ``step'' are eagerly generated, then the interpretations in the later steps are only generated on demand. +Under this approach the \CFA resolver could, for instance, try expression interpretations in the following order: +\begin{enumerate} +\item Interpretations with no polymorphic type binding or implicit conversions. +\item Interpretations containing no polymorphic type binding and at least one safe implicit conversion. +\item Interpretations containing polymorphic type binding, but only safe implicit conversions. +\item Interpretations containing at least one unsafe implicit conversion. +\end{enumerate} +If a valid expression interpretation is found in one step, it is guaranteed to be lower-cost than any interpretation in a later step (by the structure of \CFA interpretation costs), so no further steps need be considered. +This approach may save significant amounts of work, especially given that the first steps avoid potentially expensive handling of implicit conversions and type assertion satisfaction entirely, and cover a large proportion of common monomorphic code. + +%\subsection{Parameter-Directed} +%\textbf{TODO: Richard's algorithm isn't Baker (Cormack?), disentangle from this section \ldots}. +%The expression resolution algorithm used by the existing iteration of CFA is based on Baker's\cite{Baker82} algorithm for overload resolution in Ada. +%The essential idea of this algorithm is to first find the possible interpretations of the most deeply nested subexpressions, then to use these interpretations to recursively generate valid interpretations of their superexpressions. +%To simplify matters, the only expressions considered in this discussion of the algorithm are function application and literal expressions; other expression types can generally be considered to be variants of one of these for the purposes of the resolver, \eg variables are essentially zero-argument functions. +%If we consider expressions as graph nodes with arcs connecting them to their subexpressions, these expressions form a DAG, generated by the algorithm from the bottom up. +%Literal expressions are represented by leaf nodes, annotated with the type of the expression, while a function application will have a reference to the function declaration chosen, as well as arcs to the interpretation nodes for its argument expressions; functions are annotated with their return type (or types, in the case of multiple return values). +% +%\textbf{TODO: Figure} +% +%Baker's algorithm was designed to account for name overloading; Richard Bilson\cite{Bilson03} extended this algorithm to also handle polymorphic functions, implicit conversions and multiple return types when designing the original \CFA compiler. +%The core of the algorithm is a function which Baker refers to as $gen\_calls$. +%$gen\_calls$ takes as arguments the name of a function $f$ and a list containing the set of possible subexpression interpretations $S_j$ for each argument of the function and returns a set of possible interpretations of calling that function on those arguments. +%The subexpression interpretations are generally either singleton sets generated by the single valid interpretation of a literal expression, or the results of a previous call to $gen\_calls$. +%If there are no valid interpretations of an expression, the set returned by $gen\_calls$ will be empty, at which point resolution can cease, since each subexpression must have at least one valid interpretation to produce an interpretation of the whole expression. +%On the other hand, if for some type $T$ there is more than one valid interpretation of an expression with type $T$, all interpretations of that expression with type $T$ can be collapsed into a single \emph{ambiguous expression} of type $T$, since the only way to disambiguate expressions is by their return types. +%If a subexpression interpretation is ambiguous, than any expression interpretation containing it will also be ambiguous. +%In the variant of this algorithm including implicit conversions, the interpretation of an expression as type $T$ is ambiguous only if there is more than one \emph{minimal-cost} interpretation of the expression as type $T$, as cheaper expressions are always chosen in preference to more expensive ones. +% +%Given this description of the behaviour of $gen\_calls$, its implementation is quite straightforward: for each function declaration $f_i$ matching the name of the function, consider each of the parameter types $p_j$ of $f_i$, attempting to match the type of an element of $S_j$ to $p_j$ (this may include checking of implicit conversions). +%If no such element can be found, there is no valid interpretation of the expression using $f_i$, while if more than one such (minimal-cost) element is found than an ambiguous interpretation with the result type of $f_i$ is produced. +%In the \CFA variant, which includes polymorphic functions, it is possible that a single polymorphic function definition $f_i$ can produce multiple valid interpretations by different choices of type variable bindings; these interpretations are unambiguous so long as the return type of $f_i$ is different for each type binding. +%If all the parameters $p_j$ of $f_i$ can be uniquely matched to a candidate interpretation, then a valid interpretation based on $f_i$ and those $p_j$ is produced. +%$gen\_calls$ collects the produced interpretations for each $f_i$ and returns them; a top level expression is invalid if this list is empty, ambiguous if there is more than one (minimal-cost) result, or if this single result is ambiguous, and valid otherwise. +% +%In this implementation, resolution of a single top-level expression takes time $O(\ldots)$, where \ldots. \textbf{TODO:} \textit{Look at 2.3.1 in Richard's thesis when working out complexity; I think he does get the Baker algorithm wrong on combinations though, maybe\ldots} +% +%\textbf{TODO: Basic Lit Review} \textit{Look at 2.4 in Richard's thesis for any possible more-recent citations of Baker\ldots} \textit{Look back at Baker's related work for other papers that look similar to what you're doing, then check their citations as well\ldots} \textit{Look at Richard's citations in 2.3.2 w.r.t. type data structures\ldots} +%\textit{CormackWright90 seems to describe a solution for the same problem, mostly focused on how to find the implicit parameters} + +\section{Proposal} +Baker~\cite{Baker82} discussed various expression resolution algorithms that can handle name overloading, but left experimental comparison of those algorithms to future work; Bilson~\cite{Bilson03} described one extension of Baker's algorithm to handle implicit conversions, but did not fully explore the space of algorithmic approaches to handle both overloaded names and implicit conversions. +This project is intended to experimentally test a number of expression resolution algorithms that are powerful enough to handle the \CFA type-system, including both name overloading and implicit conversions. +This comparison closes Baker's open research question, as well as potentially improving Bilson's \CFA compiler. + +Rather than testing all of these algorithms in-place in the \CFA compiler, a resolver prototype is being developed which acts on a simplified input language encapsulating the essential details of the \CFA type-system\footnote{Note this simplified input language is not a usable programming language.}. +Multiple variants of this resolver prototype will be implemented, each encapsulating a different expression resolution variant, sharing as much code as feasible. +These variants will be instrumented to test runtime performance, and run on a variety of input files; the input files may be generated programmatically or from exisiting code in \CFA or similar languages. +These experimental results should make it possible to determine the algorithm likely to be most performant in practical use, and replace CFA's existing expression resolver. + +The experimental results will also provide some empirical sense of the compile-time cost of various language features by comparing the results of the most performant resolver variant that supports a feature with the most performant resolver variant that does not support that feature, a useful capability to guide language design. +As an example, there are currently multiple open proposals for how implicit conversions should interact with polymorphic type binding in \CFA, each with distinct levels of expressive power; if the resolver prototype is modified to support each proposal, the optimal algorithm for each proposal can be compared, providing an empirical demonstration of the trade-off between expressive power and compiler runtime. + +This proposed project should provide valuable data on how to implement a performant compiler for modern programming languages such as \CFA with powerful static type-systems, specifically targeting the feature interaction between name overloading and implicit conversions. +This work is not limited in applicability to \CFA, but may also be useful for supporting efficient compilation of the upcoming Concepts standard~\cite{C++concepts} for \CC template constraints, for instance. + +\appendix +\section{Completion Timeline} +The following is a preliminary estimate of the time necessary to complete the major components of this research project: +\begin{center} +\begin{tabular}{ | r @{--} l | p{4in} | } +\hline May 2015 & April 2016 & Project familiarization and generic types design and implementation. \\ +\hline May 2016 & April 2017 & Design and implement resolver prototype and run performance experiments. \\ +\hline May 2017 & August 2017 & Integrate new language features and best-performing resolver prototype into CFA. \\ +\hline September 2017 & January 2018 & Thesis writing and defense. \\ +\hline +\end{tabular} +\end{center} + +\addcontentsline{toc}{section}{\refname} +\bibliographystyle{plain} +\bibliography{cfa} + +%\addcontentsline{toc}{section}{\indexname} % add index name to table of contents +%\begin{theindex} +%Italic page numbers give the location of the main entry for the referenced term. +%Plain page numbers denote uses of the indexed term. +%Entries for grammar non-terminals are italicized. +%A typewriter font is used for grammar terminals and program identifiers. +%\indexspace +%\input{comp_II.ind} +%\end{theindex} + +\end{document} Index: doc/bibliography/cfa.bib =================================================================== --- doc/bibliography/cfa.bib (revision 950f7a72ccf248faed22f2bbd0d7542e24948798) +++ doc/bibliography/cfa.bib (revision 7527e6365628dd566e55f6dbeaca1521c6718837) @@ -832,4 +832,15 @@ address = {http://www.iso.org}, year = 2012, +} + +@manual{C++Concepts, + keywords = {ISO/IEC TS 19217:2015}, + contributer = {a3moss@uwaterloo.ca}, + key = {C++ Concepts}, + title = {Information technology -- Programming languages -- {C}{\kern-.1em\hbox{\large\texttt{+\kern-.25em+}}} Extensions for concepts}, + organization = {International Standard ISO/IEC TS 19217:2015}, + publisher = {International Standard Organization}, + address = {http://www.iso.org}, + year = 2015 } @@ -1623,4 +1634,15 @@ year = 1974, } + +@unpublished{Ditchfield:conversions, + contributer = {a3moss@uwaterloo.ca}, + author = {Glen Ditchfield}, + title = {Conversions for {Cforall}}, + note = {\href{http://plg.uwaterloo.ca/~cforall/Conversions/index.html}{http://\-plg.uwaterloo.ca/\-\textasciitilde cforall/\-Conversions/\-index.html}}, + month = {Nov}, + year = {2002}, + urldate = {28 July 2016}, +} + @techreport{Dijkstra65, @@ -4663,4 +4685,23 @@ } +@article{Ganzinger80, + contributer = {a3moss@uwaterloo.ca}, + author = {Ganzinger, Harald and Ripken, Knut}, + title = {Operator Identification in {ADA}: Formal Specification, Complexity, and Concrete Implementation}, + journal = {SIGPLAN Notices}, + issue_date = {February 1980}, + volume = {15}, + number = {2}, + month = feb, + year = {1980}, + issn = {0362-1340}, + pages = {30--42}, + numpages = {13}, + url = {http://doi.acm.org/10.1145/947586.947589}, + doi = {10.1145/947586.947589}, + publisher = {ACM}, + address = {New York, NY, USA} +} + @article{Ford82, keywords = {}, @@ -5829,4 +5870,23 @@ } +@article{Pennello80, + contributer = {a3moss@uwaterloo.ca}, + author = {Pennello, Tom and DeRemer, Frank and Meyers, Richard}, + title = {A Simplified Operator Identification Scheme for {Ada}}, + journal = {SIGPLAN Notices}, + issue_date = {July-August 1980}, + volume = {15}, + number = {7 and 8}, + month = jul, + year = {1980}, + issn = {0362-1340}, + pages = {82--87}, + numpages = {6}, + url = {http://doi.acm.org/10.1145/947680.947688}, + doi = {10.1145/947680.947688}, + publisher = {ACM}, + address = {New York, NY, USA}, +} + @inproceedings{Dice10, keywords = {hardware, synchronization, transactional memory}, Index: doc/user/user.tex =================================================================== --- doc/user/user.tex (revision 950f7a72ccf248faed22f2bbd0d7542e24948798) +++ doc/user/user.tex (revision 7527e6365628dd566e55f6dbeaca1521c6718837) @@ -11,6 +11,6 @@ %% Created On : Wed Apr 6 14:53:29 2016 %% Last Modified By : Peter A. Buhr -%% Last Modified On : Wed Jul 13 08:14:39 2016 -%% Update Count : 1247 +%% Last Modified On : Sun Aug 14 08:23:06 2016 +%% Update Count : 1323 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -211,5 +211,5 @@ however, it largely extended the language, and did not address many existing problems.\footnote{% Two important existing problems addressed were changing the type of character literals from ©int© to ©char© and enumerator from ©int© to the type of its enumerators.} -\Index*{Fortran}~\cite{Fortran08}, \Index*{Ada}~\cite{Ada12}, and \Index*{Cobol}~\cite{Cobol14} are examples of programming languages that took an evolutionary approach, where modern language features (e.g., objects, concurrency) are added and problems fixed within the framework of the existing language. +\Index*{Fortran}~\cite{Fortran08}, \Index*{Ada}~\cite{Ada12}, and \Index*{Cobol}~\cite{Cobol14} are examples of programming languages that took an evolutionary approach, where modern language features (\eg objects, concurrency) are added and problems fixed within the framework of the existing language. \Index*{Java}~\cite{Java8}, \Index*{Go}~\cite{Go}, \Index*{Rust}~\cite{Rust} and \Index*{D}~\cite{D} are examples of the revolutionary approach for modernizing C/\CC, resulting in a new language rather than an extension of the descendent. These languages have different syntax and semantics from C, and do not interoperate directly with C, largely because of garbage collection. @@ -226,4 +226,5 @@ \section{Interoperability} +\label{s:Interoperability} \CFA is designed to integrate well with existing C programs and libraries. @@ -265,5 +266,5 @@ \section[Compiling CFA Program]{Compiling \CFA Program} -The command ©cfa© is used to compile \CFA program(s), and is based on the GNU \Indexc{gcc} command, e.g.: +The command ©cfa© is used to compile \CFA program(s), and is based on the GNU \Indexc{gcc} command, \eg: \begin{lstlisting} cfa§\indexc{cfa}\index{compilation!cfa@©cfa©}§ [ gcc-options ] C/§\CFA§-files [ assembler/loader-files ] @@ -314,4 +315,9 @@ The \CFA compilation message is printed at the beginning of a compilation. \textbf{This option is the default.} + +\item +\Indexc{-no-include-stdhdr}\index{compilation option!-no-include-stdhdr@©-no-include-stdhdr©} +Do not supply ©extern "C"© wrappers for \Celeven standard include files (see~\VRef{s:StandardHeaders}). +\textbf{This option is \emph{not} the default.} \end{description} @@ -350,5 +356,5 @@ \section{Underscores in Constants} -Numeric constants are extended to allow \Index{underscore}s within constants\index{constant!underscore}, e.g.: +Numeric constants are extended to allow \Index{underscore}s within constants\index{constant!underscore}, \eg: \begin{lstlisting} 2®_®147®_®483®_®648; §\C{// decimal constant}§ @@ -366,8 +372,8 @@ \begin{enumerate} \item -A sequence of underscores is disallowed, e.g., ©12__34© is invalid. +A sequence of underscores is disallowed, \eg ©12__34© is invalid. \item Underscores may only appear within a sequence of digits (regardless of the digit radix). -In other words, an underscore cannot start or end a sequence of digits, e.g., ©_1©, ©1_© and ©_1_© are invalid (actually, the 1st and 3rd examples are identifier names). +In other words, an underscore cannot start or end a sequence of digits, \eg ©_1©, ©1_© and ©_1_© are invalid (actually, the 1st and 3rd examples are identifier names). \item A numeric prefix may end with an underscore; @@ -498,5 +504,5 @@ \end{quote2} -All type qualifiers, e.g., ©const©, ©volatile©, etc., are used in the normal way with the new declarations and also appear left to right, e.g.: +All type qualifiers, \eg ©const©, ©volatile©, etc., are used in the normal way with the new declarations and also appear left to right, \eg: \begin{quote2} \begin{tabular}{@{}l@{\hspace{1em}}l@{\hspace{1em}}l@{}} @@ -518,6 +524,6 @@ \end{tabular} \end{quote2} -All declaration qualifiers, e.g., ©extern©, ©static©, etc., are used in the normal way with the new declarations but can only appear at the start of a \CFA routine declaration,\footnote{\label{StorageClassSpecifier} -The placement of a storage-class specifier other than at the beginning of the declaration specifiers in a declaration is an obsolescent feature.~\cite[\S~6.11.5(1)]{C11}} e.g.: +All declaration qualifiers, \eg ©extern©, ©static©, etc., are used in the normal way with the new declarations but can only appear at the start of a \CFA routine declaration,\footnote{\label{StorageClassSpecifier} +The placement of a storage-class specifier other than at the beginning of the declaration specifiers in a declaration is an obsolescent feature.~\cite[\S~6.11.5(1)]{C11}} \eg: \begin{quote2} \begin{tabular}{@{}l@{\hspace{3em}}l@{\hspace{2em}}l@{}} @@ -542,5 +548,5 @@ Unsupported are K\&R C declarations where the base type defaults to ©int©, if no type is specified,\footnote{ At least one type specifier shall be given in the declaration specifiers in each declaration, and in the specifier-qualifier list in each structure declaration and type name~\cite[\S~6.7.2(2)]{C11}} -e.g.: +\eg: \begin{lstlisting} x; §\C{// int x}§ @@ -612,5 +618,5 @@ A \Index{pointer}/\Index{reference} is a generalization of a variable name, i.e., a mutable address that can point to more than one memory location during its lifetime. (Similarly, an integer variable can contain multiple integer literals during its lifetime versus an integer constant representing a single literal during its lifetime and may not occupy storage as the literal is embedded directly into instructions.) -Hence, a pointer occupies memory to store its current address, and the pointer's value is loaded by dereferencing, e.g.: +Hence, a pointer occupies memory to store its current address, and the pointer's value is loaded by dereferencing, \eg: \begin{quote2} \begin{tabular}{@{}ll@{}} @@ -669,5 +675,5 @@ Except for auto-dereferencing by the compiler, this reference example is the same as the previous pointer example. Hence, a reference behaves like the variable name for the current variable it is pointing-to. -The simplest way to understand a reference is to imagine the compiler inserting a dereference operator before the reference variable for each reference qualifier in a declaration, e.g.: +The simplest way to understand a reference is to imagine the compiler inserting a dereference operator before the reference variable for each reference qualifier in a declaration, \eg: \begin{lstlisting} r2 = ((r1 + r2) * (r3 - r1)) / (r3 - 15); @@ -677,5 +683,5 @@ ®*®r2 = ((®*®r1 + ®*®r2) ®*® (®**®r3 - ®*®r1)) / (®**®r3 - 15); \end{lstlisting} -When a reference operation appears beside a dereference operation, e.g., ©&*©, they cancel out.\footnote{ +When a reference operation appears beside a dereference operation, \eg ©&*©, they cancel out.\footnote{ The unary ©&© operator yields the address of its operand. If the operand has type ``type'', the result has type ``pointer to type''. @@ -721,9 +727,27 @@ ®&®crc = &cx; §\C{// error, cannot change crc}§ \end{lstlisting} -Hence, for type ©& const©, there is no pointer assignment, so ©&rc = &x© is disallowed, and \emph{the address value cannot be ©0© unless an arbitrary pointer is assigned to the reference}, e.g.: +Hence, for type ©& const©, there is no pointer assignment, so ©&rc = &x© is disallowed, and \emph{the address value cannot be ©0© unless an arbitrary pointer is assigned to the reference}, \eg: \begin{lstlisting} int & const r = *0; §\C{// where 0 is the int * zero}§ \end{lstlisting} Otherwise, the compiler is managing the addresses for type ©& const© not the programmer, and by a programming discipline of only using references with references, address errors can be prevented. +Finally, the position of the ©const© qualifier \emph{after} the pointer/reference qualifier causes confuse for C programmers. +The ©const© qualifier cannot be moved before the pointer/reference qualifier for C style-declarations; +\CFA-style declarations attempt to address this issue: +\begin{quote2} +\begin{tabular}{@{}l@{\hspace{3em}}l@{}} +\multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ +\begin{lstlisting} +®const® * ®const® * const int ccp; +®const® & ®const® & const int ccr; +\end{lstlisting} +& +\begin{lstlisting} +const int * ®const® * ®const® ccp; + +\end{lstlisting} +\end{tabular} +\end{quote2} +where the \CFA declaration is read left-to-right (see \VRef{s:Declarations}). \Index{Initialization} is different than \Index{assignment} because initialization occurs on the empty (uninitialized) storage on an object, while assignment occurs on possibly initialized storage of an object. @@ -783,7 +807,33 @@ +\section{Backquote Identifiers} +\label{s:BackquoteIdentifiers} + +\CFA accommodates keyword clashes by syntactic transformations using the \CFA backquote escape-mechanism: +\begin{lstlisting} +int `otype` = 3; // make keyword an identifier +double `choose` = 3.5; +\end{lstlisting} +Programs can be converted easily by enclosing keyword identifiers in backquotes, and the backquotes can be removed later when the identifier name is changed to an non-keyword name. +Clashes in C header files (see~\VRef{s:StandardHeaders}) can be handled automatically using the preprocessor, ©#include_next© and ©-I filename©: +\begin{lstlisting} +// include file uses the CFA keyword "otype". +#if ! defined( otype ) // nesting ? +#define otype `otype` +#define __CFA_BFD_H__ +#endif // ! otype + +#include_next // must have internal check for multiple expansion + +#if defined( otype ) && defined( __CFA_BFD_H__ ) // reset only if set +#undef otype +#undef __CFA_BFD_H__ +#endif // otype && __CFA_BFD_H__ +\end{lstlisting} + + \section{Type Operators} -The new declaration syntax can be used in other contexts where types are required, e.g., casts and the pseudo-routine ©sizeof©: +The new declaration syntax can be used in other contexts where types are required, \eg casts and the pseudo-routine ©sizeof©: \begin{quote2} \begin{tabular}{@{}l@{\hspace{3em}}l@{}} @@ -805,5 +855,5 @@ \CFA also supports a new syntax for routine definition, as well as ISO C and K\&R routine syntax. -The point of the new syntax is to allow returning multiple values from a routine~\cite{Galletly96,CLU}, e.g.: +The point of the new syntax is to allow returning multiple values from a routine~\cite{Galletly96,CLU}, \eg: \begin{lstlisting} ®[ int o1, int o2, char o3 ]® f( int i1, char i2, char i3 ) { @@ -817,5 +867,5 @@ \Index*{Michael Tiemann}, with help from \Index*{Doug Lea}, provided named return values in g++, circa 1989.} The value of each local return variable is automatically returned at routine termination. -Declaration qualifiers can only appear at the start of a routine definition, e.g.: +Declaration qualifiers can only appear at the start of a routine definition, \eg: \begin{lstlisting} ®extern® [ int x ] g( int y ) {§\,§} @@ -849,5 +899,5 @@ The inability to use \CFA declarations in these two contexts is probably a blessing because it precludes programmers from arbitrarily switching between declarations forms within a declaration contexts. -C-style declarations can be used to declare parameters for \CFA style routine definitions, e.g.: +C-style declarations can be used to declare parameters for \CFA style routine definitions, \eg: \begin{lstlisting} [ int ] f( * int, int * ); §\C{// returns an integer, accepts 2 pointers to integers}§ @@ -898,5 +948,5 @@ The syntax of the new routine prototype declaration follows directly from the new routine definition syntax; -as well, parameter names are optional, e.g.: +as well, parameter names are optional, \eg: \begin{lstlisting} [ int x ] f (); §\C{// returning int with no parameters}§ @@ -906,5 +956,5 @@ \end{lstlisting} This syntax allows a prototype declaration to be created by cutting and pasting source text from the routine definition header (or vice versa). -It is possible to declare multiple routine-prototypes in a single declaration, but the entire type specification is distributed across \emph{all} routine names in the declaration list (see~\VRef{s:Declarations}), e.g.: +It is possible to declare multiple routine-prototypes in a single declaration, but the entire type specification is distributed across \emph{all} routine names in the declaration list (see~\VRef{s:Declarations}), \eg: \begin{quote2} \begin{tabular}{@{}l@{\hspace{3em}}l@{}} @@ -919,5 +969,5 @@ \end{tabular} \end{quote2} -Declaration qualifiers can only appear at the start of a \CFA routine declaration,\footref{StorageClassSpecifier} e.g.: +Declaration qualifiers can only appear at the start of a \CFA routine declaration,\footref{StorageClassSpecifier} \eg: \begin{lstlisting} extern [ int ] f (int); @@ -928,5 +978,5 @@ \section{Routine Pointers} -The syntax for pointers to \CFA routines specifies the pointer name on the right, e.g.: +The syntax for pointers to \CFA routines specifies the pointer name on the right, \eg: \begin{lstlisting} * [ int x ] () fp; §\C{// pointer to routine returning int with no parameters}§ @@ -987,5 +1037,22 @@ Alternatively, prototype definitions can be eliminated by using a two-pass compilation, and implicitly creating header files for exports. The former is easy to do, while the latter is more complex. -Currently, \CFA does \emph{not} attempt to support named arguments. + +Furthermore, named arguments do not work well in a \CFA-style programming-languages because they potentially introduces a new criteria for type matching. +For example, it is technically possible to disambiguate between these two overloaded definitions of ©f© based on named arguments at the call site: +\begin{lstlisting} +int f( int i, int j ); +int f( int x, double y ); + +f( j : 3, i : 4 ); §\C{// 1st f}§ +f( x : 7, y : 8.1 ); §\C{// 2nd f}§ +f( 4, 5 ); §\C{// ambiguous call}§ +\end{lstlisting} +However, named arguments compound routine resolution in conjunction with conversions: +\begin{lstlisting} +f( i : 3, 5.7 ); §\C{// ambiguous call ?}§ +\end{lstlisting} +Depending on the cost associated with named arguments, this call could be resolvable or ambiguous. +Adding named argument into the routine resolution algorithm does not seem worth the complexity. +Therefore, \CFA does \emph{not} attempt to support named arguments. \item[Default Arguments] @@ -997,16 +1064,16 @@ the allowable positional calls are: \begin{lstlisting} -p(); §\C{// rewrite $\Rightarrow$ p( 1, 2, 3 )}§ -p( 4 ); §\C{// rewrite $\Rightarrow$ p( 4, 2, 3 )}§ -p( 4, 4 ); §\C{// rewrite $\Rightarrow$ p( 4, 4, 3 )}§ -p( 4, 4, 4 ); §\C{// rewrite $\Rightarrow$ p( 4, 4, 4 )}§ +p(); §\C{// rewrite $\Rightarrow$ p( 1, 2, 3 )}§ +p( 4 ); §\C{// rewrite $\Rightarrow$ p( 4, 2, 3 )}§ +p( 4, 4 ); §\C{// rewrite $\Rightarrow$ p( 4, 4, 3 )}§ +p( 4, 4, 4 ); §\C{// rewrite $\Rightarrow$ p( 4, 4, 4 )}§ // empty arguments -p( , 4, 4 ); §\C{// rewrite $\Rightarrow$ p( 1, 4, 4 )}§ -p( 4, , 4 ); §\C{// rewrite $\Rightarrow$ p( 4, 2, 4 )}§ -p( 4, 4, ); §\C{// rewrite $\Rightarrow$ p( 4, 4, 3 )}§ -p( 4, , ); §\C{// rewrite $\Rightarrow$ p( 4, 2, 3 )}§ -p( , 4, ); §\C{// rewrite $\Rightarrow$ p( 1, 4, 3 )}§ -p( , , 4 ); §\C{// rewrite $\Rightarrow$ p( 1, 2, 4 )}§ -p( , , ); §\C{// rewrite $\Rightarrow$ p( 1, 2, 3 )}§ +p( , 4, 4 ); §\C{// rewrite $\Rightarrow$ p( 1, 4, 4 )}§ +p( 4, , 4 ); §\C{// rewrite $\Rightarrow$ p( 4, 2, 4 )}§ +p( 4, 4, ); §\C{// rewrite $\Rightarrow$ p( 4, 4, 3 )}§ +p( 4, , ); §\C{// rewrite $\Rightarrow$ p( 4, 2, 3 )}§ +p( , 4, ); §\C{// rewrite $\Rightarrow$ p( 1, 4, 3 )}§ +p( , , 4 ); §\C{// rewrite $\Rightarrow$ p( 1, 2, 4 )}§ +p( , , ); §\C{// rewrite $\Rightarrow$ p( 1, 2, 3 )}§ \end{lstlisting} Here the missing arguments are inserted from the default values in the parameter list. @@ -1043,12 +1110,12 @@ The conflict occurs because both named and ellipse arguments must appear after positional arguments, giving two possibilities: \begin{lstlisting} -p( /* positional */, . . ., /* named */ ); -p( /* positional */, /* named */, . . . ); -\end{lstlisting} -While it is possible to implement both approaches, the first possibly is more complex than the second, e.g.: -\begin{lstlisting} -p( int x, int y, int z, . . . ); -p( 1, 4, 5, 6, z : 3, y : 2 ); §\C{// assume p( /* positional */, . . ., /* named */ );}§ -p( 1, z : 3, y : 2, 4, 5, 6 ); §\C{// assume p( /* positional */, /* named */, . . . );}§ +p( /* positional */, ... , /* named */ ); +p( /* positional */, /* named */, ... ); +\end{lstlisting} +While it is possible to implement both approaches, the first possibly is more complex than the second, \eg: +\begin{lstlisting} +p( int x, int y, int z, ... ); +p( 1, 4, 5, 6, z : 3, y : 2 ); §\C{// assume p( /* positional */, ... , /* named */ );}§ +p( 1, z : 3, y : 2, 4, 5, 6 ); §\C{// assume p( /* positional */, /* named */, ... );}§ \end{lstlisting} In the first call, it is necessary for the programmer to conceptually rewrite the call, changing named arguments into positional, before knowing where the ellipse arguments begin. @@ -1056,9 +1123,9 @@ In the second call, the named arguments separate the positional and ellipse arguments, making it trivial to read the call. -The problem is exacerbated with default arguments, e.g.: -\begin{lstlisting} -void p( int x, int y = 2, int z = 3. . . ); -p( 1, 4, 5, 6, z : 3 ); §\C{// assume p( /* positional */, . . ., /* named */ );}§ -p( 1, z : 3, 4, 5, 6 ); §\C{// assume p( /* positional */, /* named */, . . . );}§ +The problem is exacerbated with default arguments, \eg: +\begin{lstlisting} +void p( int x, int y = 2, int z = 3... ); +p( 1, 4, 5, 6, z : 3 ); §\C{// assume p( /* positional */, ... , /* named */ );}§ +p( 1, z : 3, 4, 5, 6 ); §\C{// assume p( /* positional */, /* named */, ... );}§ \end{lstlisting} The first call is an error because arguments 4 and 5 are actually positional not ellipse arguments; @@ -1105,6 +1172,7 @@ \subsection{Type Nesting} -\CFA allows \Index{type nesting}, and type qualification of the nested types (see \VRef[Figure]{f:TypeNestingQualification}), where as C hoists\index{type hoisting} (refactors) nested types into the enclosing scope and has no type qualification. +\CFA allows \Index{type nesting}, and type qualification of the nested typres (see \VRef[Figure]{f:TypeNestingQualification}), where as C hoists\index{type hoisting} (refactors) nested types into the enclosing scope and has no type qualification. \begin{figure} +\centering \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}} \\ @@ -1264,5 +1332,5 @@ As mentioned, tuples can appear in contexts requiring a list of value, such as an argument list of a routine call. -In unambiguous situations, the tuple brackets may be omitted, e.g., a tuple that appears as an argument may have its +In unambiguous situations, the tuple brackets may be omitted, \eg a tuple that appears as an argument may have its square brackets omitted for convenience; therefore, the following routine invocations are equivalent: \begin{lstlisting} @@ -1303,5 +1371,5 @@ Type qualifiers, i.e., const and volatile, may modify a tuple type. -The meaning is the same as for a type qualifier modifying an aggregate type [Int99, x 6.5.2.3(7),x 6.7.3(11)], i.e., the qualifier is distributed across all of the types in the tuple, e.g.: +The meaning is the same as for a type qualifier modifying an aggregate type [Int99, x 6.5.2.3(7),x 6.7.3(11)], i.e., the qualifier is distributed across all of the types in the tuple, \eg: \begin{lstlisting} const volatile [ int, float, const int ] x; @@ -1311,5 +1379,5 @@ [ const volatile int, const volatile float, const volatile int ] x; \end{lstlisting} -Declaration qualifiers can only appear at the start of a \CFA tuple declaration4, e.g.: +Declaration qualifiers can only appear at the start of a \CFA tuple declaration4, \eg: \begin{lstlisting} extern [ int, int ] w1; @@ -1319,5 +1387,5 @@ Unfortunately, C's syntax for subscripts precluded treating them as tuples. The C subscript list has the form ©[i][j]...© and not ©[i, j, ...]©. -Therefore, there is no syntactic way for a routine returning multiple values to specify the different subscript values, e.g., ©f[g()]© always means a single subscript value because there is only one set of brackets. +Therefore, there is no syntactic way for a routine returning multiple values to specify the different subscript values, \eg ©f[g()]© always means a single subscript value because there is only one set of brackets. Fixing this requires a major change to C because the syntactic form ©M[i, j, k]© already has a particular meaning: ©i, j, k© is a comma expression. \end{rationale} @@ -1373,5 +1441,5 @@ Mass assignment has the following form: \begin{lstlisting} -[ §\emph{lvalue}§, ..., §\emph{lvalue}§ ] = §\emph{expr}§; +[ §\emph{lvalue}§, ... , §\emph{lvalue}§ ] = §\emph{expr}§; \end{lstlisting} \index{lvalue} @@ -1380,5 +1448,5 @@ Clearly, the types of the entities being assigned must be type compatible with the value of the expression. -Mass assignment has parallel semantics, e.g., the statement: +Mass assignment has parallel semantics, \eg the statement: \begin{lstlisting} [ x, y, z ] = 1.5; @@ -1413,5 +1481,5 @@ Multiple assignment has the following form: \begin{lstlisting} -[ §\emph{lvalue}§, . . ., §\emph{lvalue}§ ] = [ §\emph{expr}§, . . ., §\emph{expr}§ ]; +[ §\emph{lvalue}§, ... , §\emph{lvalue}§ ] = [ §\emph{expr}§, ... , §\emph{expr}§ ]; \end{lstlisting} \index{lvalue} @@ -1469,21 +1537,21 @@ \section{Unnamed Structure Fields} -C requires each field of a structure to have a name, except for a bit field associated with a basic type, e.g.: +C requires each field of a structure to have a name, except for a bit field associated with a basic type, \eg: \begin{lstlisting} struct { - int f1; // named field - int f2 : 4; // named field with bit field size - int : 3; // unnamed field for basic type with bit field size - int ; // disallowed, unnamed field - int *; // disallowed, unnamed field - int (*)(int); // disallowed, unnamed field + int f1; §\C{// named field}§ + int f2 : 4; §\C{// named field with bit field size}§ + int : 3; §\C{// unnamed field for basic type with bit field size}§ + int ; §\C{// disallowed, unnamed field}§ + int *; §\C{// disallowed, unnamed field}§ + int (*)(int); §\C{// disallowed, unnamed field}§ }; \end{lstlisting} This requirement is relaxed by making the field name optional for all field declarations; therefore, all the field declarations in the example are allowed. As for unnamed bit fields, an unnamed field is used for padding a structure to a particular size. -A list of unnamed fields is also supported, e.g.: +A list of unnamed fields is also supported, \eg: \begin{lstlisting} struct { - int , , ; // 3 unnamed fields + int , , ; §\C{// 3 unnamed fields}§ } \end{lstlisting} @@ -1498,5 +1566,5 @@ §\emph{expr}§ -> [ §\emph{fieldlist}§ ] \end{lstlisting} -\emph{expr} is any expression yielding a value of type record, e.g., ©struct©, ©union©. +\emph{expr} is any expression yielding a value of type record, \eg ©struct©, ©union©. Each element of \emph{ fieldlist} is an element of the record specified by \emph{expr}. A record-field tuple may be used anywhere a tuple can be used. An example of the use of a record-field tuple is @@ -1760,9 +1828,8 @@ } \end{lstlisting} -While the declaration of the local variable ©y© is useful and its scope is across all ©case© clauses, the initialization for such a variable is defined to never be executed because control always transfers over it. -Furthermore, any statements before the first ©case© clause can only be executed if labelled and transferred to using a ©goto©, either from outside or inside of the ©switch©. -As mentioned, transfer into control structures should be forbidden; -transfers from within the ©switch© body using a ©goto© are equally unpalatable. -As well, the declaration of ©z© is cannot occur after the ©case© because a label can only be attached to a statement, and without a fall through to case 3, ©z© is uninitialized. +While the declaration of the local variable ©y© is useful with a scope across all ©case© clauses, the initialization for such a variable is defined to never be executed because control always transfers over it. +Furthermore, any statements before the first ©case© clause can only be executed if labelled and transferred to using a ©goto©, either from outside or inside of the ©switch©, both of which are problematic. +As well, the declaration of ©z© cannot occur after the ©case© because a label can only be attached to a statement, and without a fall through to case 3, ©z© is uninitialized. +The key observation is that the ©switch© statement branches into control structure, i.e., there are multiple entry points into its statement body. \end{enumerate} @@ -1778,15 +1845,19 @@ and there is only a medium amount of fall-through from one ©case© clause to the next, and most of these result from a list of case values executing common code, rather than a sequence of case actions that compound. \end{itemize} -These observations help to put the suggested changes to the ©switch© into perspective. +These observations help to put the \CFA changes to the ©switch© into perspective. \begin{enumerate} \item Eliminating default fall-through has the greatest potential for affecting existing code. -However, even if fall-through is removed, most ©switch© statements would continue to work because of the explicit transfers already present at the end of each ©case© clause, the common placement of the ©default© clause at the end of the case list, and the most common use of fall-through, i.e., a list of ©case© clauses executing common code, e.g.: -\begin{lstlisting} +However, even if fall-through is removed, most ©switch© statements would continue to work because of the explicit transfers already present at the end of each ©case© clause, the common placement of the ©default© clause at the end of the case list, and the most common use of fall-through, i.e., a list of ©case© clauses executing common code, \eg: + \begin{lstlisting} case 1: case 2: case 3: ... \end{lstlisting} still work. Nevertheless, reversing the default action would have a non-trivial effect on case actions that compound, such as the above example of processing shell arguments. -Therefore, to preserve backwards compatibility, it is necessary to introduce a new kind of ©switch© statement, called ©choose©, with no implicit fall-through semantics and an explicit fall-through if the last statement of a case-clause ends with the new keyword ©fallthru©, e.g.: +<<<<<<< HEAD +Therefore, to preserve backwards compatibility, it is necessary to introduce a new kind of ©switch© statement, called ©choose©, with no implicit fall-through semantics and an explicit fall-through if the last statement of a case-clause ends with the new keyword ©fallthru©, \eg: +======= +Therefore, to preserve backwards compatibility, it is necessary to introduce a new kind of ©switch© statement, called ©choose©, with no implicit fall-through semantics and an explicit fall-through if the last statement of a case-clause ends with the new keyword ©fallthrough©/©fallthru©, e.g.: +>>>>>>> 080615890f586cb9954c252b55cab47f52c25758 \begin{lstlisting} ®choose® ( i ) { @@ -1815,16 +1886,16 @@ Therefore, no change is made for this issue. \item -Dealing with unreachable code in a ©switch©/©choose© body is solved by restricting declarations and associated initialization to the start of statement body, which is executed \emph{before} the transfer to the appropriate ©case© clause.\footnote{ -Essentially, these declarations are hoisted before the statement and both declarations and statement are surrounded by a compound statement.} and precluding statements before the first ©case© clause. -Further declaration in the statement body are disallowed. +Dealing with unreachable code in a ©switch©/©choose© body is solved by restricting declarations and associated initialization to the start of statement body, which is executed \emph{before} the transfer to the appropriate ©case© clause\footnote{ +Essentially, these declarations are hoisted before the ©switch©/©choose© statement and both declarations and statement are surrounded by a compound statement.} and precluding statements before the first ©case© clause. +Further declarations at the same nesting level as the statement body are disallowed to ensure every transfer into the body is sound. \begin{lstlisting} switch ( x ) { - ®int i = 0;® §\C{// allowed}§ + ®int i = 0;® §\C{// allowed only at start}§ case 0: ... - ®int i = 0;® §\C{// disallowed}§ + ®int j = 0;® §\C{// disallowed}§ case 1: { - ®int i = 0;® §\C{// allowed in any compound statement}§ + ®int k = 0;® §\C{// allowed at different nesting levels}§ ... } @@ -1846,7 +1917,7 @@ \begin{lstlisting} switch ( i ) { - ®case 1, 3, 5®: + case ®1, 3, 5®: ... - ®case 2, 4, 6®: + case ®2, 4, 6®: ... } @@ -1879,7 +1950,7 @@ \begin{lstlisting} switch ( i ) { - ®case 1~5:® + case ®1~5:® ... - ®case 10~15:® + case ®10~15:® ... } @@ -1888,7 +1959,7 @@ \begin{lstlisting} switch ( i ) - case 1 ... 5: + case ®1 ... 5®: ... - case 10 ... 15: + case ®10 ... 15®: ... } @@ -2707,6 +2778,6 @@ Like the \Index*[C++]{\CC} lexical problem with closing template-syntax, e.g, ©Foo>®©, this issue can be solved with a more powerful lexer/parser. -There are several ambiguous cases with operator identifiers, e.g., ©int *?*?()©, where the string ©*?*?© can be lexed as ©*©/©?*?© or ©*?©/©*?©. -Since it is common practise to put a unary operator juxtaposed to an identifier, e.g., ©*i©, users will be annoyed if they cannot do this with respect to operator identifiers. +There are several ambiguous cases with operator identifiers, \eg ©int *?*?()©, where the string ©*?*?© can be lexed as ©*©/©?*?© or ©*?©/©*?©. +Since it is common practise to put a unary operator juxtaposed to an identifier, \eg ©*i©, users will be annoyed if they cannot do this with respect to operator identifiers. Even with this special hack, there are 5 general cases that cannot be handled. The first case is for the function-call identifier ©?()©: @@ -2773,5 +2844,5 @@ This means that a function requiring mutual exclusion could block if the lock is already held by another thread. Blocking on a monitor lock does not block the kernel thread, it simply blocks the user thread, which yields its kernel thread while waiting to obtain the lock. -If multiple mutex parameters are specified, they will be locked in parameter order (i.e. first parameter is locked first) and unlocked in the +If multiple mutex parameters are specified, they will be locked in parameter order (\ie first parameter is locked first) and unlocked in the reverse order. \begin{lstlisting} @@ -4350,29 +4421,9 @@ \begin{description} \item[Change:] add new keywords \\ -New keywords are added to \CFA. +New keywords are added to \CFA (see~\VRef{s:NewKeywords}). \item[Rationale:] keywords added to implement new semantics of \CFA. \item[Effect on original feature:] change to semantics of well-defined feature. \\ Any ISO C programs using these keywords as identifiers are invalid \CFA programs. -\item[Difficulty of converting:] keyword clashes are accommodated by syntactic transformations using the \CFA backquote escape-mechanism: -\begin{lstlisting} -int `otype` = 3; // make keyword an identifier -double `choose` = 3.5; -\end{lstlisting} -Programs can be converted automatically by enclosing keyword identifiers in backquotes, and the backquotes can be remove later when the identifier name is changed. -Clashes in C system libraries (include files) can be handled automatically using preprocessor, ©#include_next© and ©-Ifilename©: -\begin{lstlisting} -// include file uses the CFA keyword "otype". -#if ! defined( otype ) // nesting ? -#define otype `otype` -#define __CFA_BFD_H__ -#endif // ! otype - -#include_next // must have internal check for multiple expansion - -#if defined( otype ) && defined( __CFA_BFD_H__ ) // reset only if set -#undef otype -#undef __CFA_BFD_H__ -#endif // otype && __CFA_BFD_H__ -\end{lstlisting} +\item[Difficulty of converting:] keyword clashes are accommodated by syntactic transformations using the \CFA backquote escape-mechanism (see~\VRef{s:BackquoteIdentifiers}): \item[How widely used:] clashes among new \CFA keywords and existing identifiers are rare. \end{description} @@ -4384,5 +4435,5 @@ int rtn( int i ); int rtn( char c ); -rtn( 'x' ); // programmer expects 2nd rtn to be called +rtn( 'x' ); §\C{// programmer expects 2nd rtn to be called}§ \end{lstlisting} \item[Rationale:] it is more intuitive for the call to ©rtn© to match the second version of definition of ©rtn© rather than the first. @@ -4406,6 +4457,6 @@ \item[Change:] make string literals ©const©: \begin{lstlisting} -char * p = "abc"; // valid in C, deprecated in §\CFA§ -char * q = expr ? "abc" : "de"; // valid in C, invalid in §\CFA§ +char * p = "abc"; §\C{// valid in C, deprecated in \CFA}§ +char * q = expr ? "abc" : "de"; §\C{// valid in C, invalid in \CFA}§ \end{lstlisting} The type of a string literal is changed from ©[] char© to ©const [] char©. @@ -4414,5 +4465,5 @@ \begin{lstlisting} char * p = "abc"; -p[0] = 'w'; // segment fault or change constant literal +p[0] = 'w'; §\C{// segment fault or change constant literal}§ \end{lstlisting} The same problem occurs when passing a string literal to a routine that changes its argument. @@ -4426,7 +4477,7 @@ \item[Change:] remove \newterm{tentative definitions}, which only occurs at file scope: \begin{lstlisting} -int i; // forward definition -int *j = ®&i®; // forward reference, valid in C, invalid in §\CFA§ -int i = 0; // definition +int i; §\C{// forward definition}§ +int *j = ®&i®; §\C{// forward reference, valid in C, invalid in \CFA}§ +int i = 0; §\C{// definition}§ \end{lstlisting} is valid in C, and invalid in \CFA because duplicate overloaded object definitions at the same scope level are disallowed. @@ -4434,7 +4485,7 @@ \begin{lstlisting} struct X { int i; struct X *next; }; -static struct X a; // forward definition -static struct X b = { 0, ®&a® }; // forward reference, valid in C, invalid in §\CFA§ -static struct X a = { 1, &b }; // definition +static struct X a; §\C{// forward definition}§ +static struct X b = { 0, ®&a® }; §\C{// forward reference, valid in C, invalid in \CFA}§ +static struct X a = { 1, &b }; §\C{// definition}§ \end{lstlisting} \item[Rationale:] avoids having different initialization rules for builtin types and userdefined types. @@ -4446,30 +4497,27 @@ \item \begin{description} -\item[Change:] have ©struct© introduce a scope for nested types -In C, the name of the nested types belongs to the same scope as the name of the outermost enclosing -Example: +\item[Change:] have ©struct© introduce a scope for nested types: \begin{lstlisting} enum ®Colour® { R, G, B, Y, C, M }; struct Person { - enum ®Colour® { R, G, B }; // nested type - struct Face { // nested type - ®Colour® Eyes, Hair; // type defined outside (1 level) + enum ®Colour® { R, G, B }; §\C{// nested type}§ + struct Face { §\C{// nested type}§ + ®Colour® Eyes, Hair; §\C{// type defined outside (1 level)}§ }; - ß.ß®Colour® shirt; // type defined outside (top level) - ®Colour® pants; // type defined same level - Face looks[10]; // type defined same level + ß.ß®Colour® shirt; §\C{// type defined outside (top level)}§ + ®Colour® pants; §\C{// type defined same level}§ + Face looks[10]; §\C{// type defined same level}§ }; -®Colour® c = R; // type/enum defined same level -Personß.ß®Colour® pc = Personß.ßR; // type/enum defined inside -Personß.ßFace pretty; // type defined inside -\end{lstlisting} +®Colour® c = R; §\C{// type/enum defined same level}§ +Personß.ß®Colour® pc = Personß.ßR; §\C{// type/enum defined inside}§ +Personß.ßFace pretty; §\C{// type defined inside}§ +\end{lstlisting} +In C, the name of the nested types belongs to the same scope as the name of the outermost enclosing structure, i.e., the nested types are hoisted to the scope of the outer-most type, which is not useful and confusing. +\CFA is C \emph{incompatible} on this issue, and provides semantics similar to \Index*[C++]{\CC}. +Nested types are not hoisted and can be referenced using the field selection operator ``©.©'', unlike the \CC scope-resolution operator ``©::©''. \item[Rationale:] ©struct© scope is crucial to \CFA as an information structuring and hiding mechanism. \item[Effect on original feature:] change to semantics of well-defined feature. \item[Difficulty of converting:] Semantic transformation. \item[How widely used:] C programs rarely have nest types because they are equivalent to the hoisted version. - -\CFA is C \emph{incompatible} on this issue, and provides semantics similar to \Index*[C++]{\CC}. -Nested types are not hoisted and can be referenced using the field selection operator ``©.©'', unlike the \CC scope-resolution operator ``©::©''. -Given that nested types in C are equivalent to not using them, i.e., they are essentially useless, it is unlikely there are any realistic usages that break because of this incompatibility. \end{description} @@ -4480,5 +4528,5 @@ \item[Difficulty of converting:] Semantic transformation. To make the struct type name visible in the scope of the enclosing struct, the struct tag could be declared in the scope of the enclosing struct, before the enclosing struct is defined. Example: \begin{lstlisting} -struct Y; // struct Y and struct X are at the same scope +struct Y; §\C{// struct Y and struct X are at the same scope}§ struct X { struct Y { /* ... */ } y; @@ -4501,4 +4549,44 @@ +\section{New Keywords} +\label{s:NewKeywords} + +\begin{quote2} +\begin{tabular}{lll} +©catch© & ©fallthrough© & ©otype© \\ +©catchResume© & ©fallthru© & ©throw© \\ +©choose© & ©finally© & ©throwResume© \\ +©disable© & ©forall© & ©trait© \\ +©dtype© & ©ftype© & ©try© \\ +©enable© & ©lvalue© & \\ +\end{tabular} +\end{quote2} + + +\section{Standard Headers} +\label{s:StandardHeaders} + +C prescribes the following standard header-files~\cite[\S~7.1.2]{C11}: +\begin{quote2} +\begin{minipage}{\linewidth} +\begin{tabular}{lll} +assert.h & math.h & stdlib.h \\ +complex.h & setjmp.h & stdnoreturn.h \\ +ctype.h & signal.h & string.h \\ +errno.h & stdalign.h & tgmath.h \\ +fenv.h & stdarg.h & threads.h \\ +float.h & stdatomic.h & time.h \\ +inttypes.h & stdbool.h & uchar.h \\ +iso646.h & stddef.h & wchar.h \\ +limits.h & stdint.h & wctype.h \\ +locale.h & stdio.h & unistd.h\footnote{\CFA extension} +\end{tabular} +\end{minipage} +\end{quote2} +For the prescribed head-files, \CFA implicitly wraps their includes in an ©extern "C"©; +hence, names in these include files are not mangled\index{mangling!name} (see~\VRef{s:Interoperability}). +All other C header files must be explicitly wrapped in ©extern "C"© to prevent name mangling. + + \section{I/O Library} \label{s:IOLibrary} @@ -4570,5 +4658,6 @@ %$ \begin{lstlisting}[mathescape=off] -sout | "x (" | 1 | "x [" | 2 | "x {" | 3 | "x $" | 4 | "x £" | 5 | "x ¥" | 6 | "x ¡" | 7 | "x ¿" | 8 | "x «" | 9 | endl; +sout | "x (" | 1 | "x [" | 2 | "x {" | 3 | "x $" | 4 | "x £" | 5 | "x ¥" | 6 | "x ¡" | 7 + | "x ¿" | 8 | "x «" | 9 | endl; \end{lstlisting} %$ @@ -4580,6 +4669,6 @@ A seperator does not appear after a C string ending with the (extended) \Index{ASCII}\index{ASCII!extended} characters: ©,.:;!?)]}%¢»© \begin{lstlisting}[belowskip=0pt] -sout | 1 | ", x" | 2 | ". x" | 3 | ": x" | 4 | "; x" | 5 | "! x" | 6 | "? x" | 7 | ") x" | 8 | "] x" | 9 | "} x" - | 10 | "% x" | 11 | "¢ x" | 12 | "» x" | endl; +sout | 1 | ", x" | 2 | ". x" | 3 | ": x" | 4 | "; x" | 5 | "! x" | 6 | "? x" | 7 + | ") x" | 8 | "] x" | 9 | "} x" | 10 | "% x" | 11 | "¢ x" | 12 | "» x" | endl; \end{lstlisting} \begin{lstlisting}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt] @@ -4597,5 +4686,5 @@ The following \CC-style \Index{manipulator}s allow further control over implicit seperation. \begin{lstlisting}[mathescape=off,belowskip=0pt] -sout | sepOn | 1 | 2 | 3 | sepOn | endl; // separator at start of line +sout | sepOn | 1 | 2 | 3 | sepOn | endl; §\C{// separator at start of line}§ \end{lstlisting} \begin{lstlisting}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt] @@ -4603,5 +4692,5 @@ \end{lstlisting} \begin{lstlisting}[mathescape=off,aboveskip=0pt,belowskip=0pt] -sout | 1 | sepOff | 2 | 3 | endl; // turn off implicit separator temporarily +sout | 1 | sepOff | 2 | 3 | endl; §\C{// turn off implicit separator temporarily}§ \end{lstlisting} \begin{lstlisting}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt] @@ -4609,5 +4698,5 @@ \end{lstlisting} \begin{lstlisting}[mathescape=off,aboveskip=0pt,belowskip=0pt] -sout | sepDisable | 1 | 2 | 3 | endl; // turn off implicit separation, affects all subsequent prints +sout | sepDisable | 1 | 2 | 3 | endl; §\C{// turn off implicit separation, affects all subsequent prints}§ \end{lstlisting} \begin{lstlisting}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt] @@ -4615,5 +4704,5 @@ \end{lstlisting} \begin{lstlisting}[mathescape=off,aboveskip=0pt,belowskip=0pt] -sout | 1 | sepOn | 2 | 3 | endl; // turn on implicit separator temporarily +sout | 1 | sepOn | 2 | 3 | endl; §\C{// turn on implicit separator temporarily}§ \end{lstlisting} \begin{lstlisting}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt] @@ -4621,5 +4710,5 @@ \end{lstlisting} \begin{lstlisting}[mathescape=off,aboveskip=0pt,belowskip=0pt] -sout | sepEnable | 1 | 2 | 3 | endl; // turn on implicit separation, affects all subsequent prints +sout | sepEnable | 1 | 2 | 3 | endl; §\C{// turn on implicit separation, affects all subsequent prints}§ \end{lstlisting} \begin{lstlisting}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt] @@ -4627,5 +4716,5 @@ \end{lstlisting} \begin{lstlisting}[mathescape=off,aboveskip=0pt,aboveskip=0pt,belowskip=0pt] -sepSet( sout, ", $" ); // change separator from " " to ", $" +sepSet( sout, ", $" ); §\C{// change separator from " " to ", \$"}§ sout | 1 | 2 | 3 | endl; \end{lstlisting} @@ -4673,4 +4762,5 @@ \subsection{malloc} +\leavevmode \begin{lstlisting}[aboveskip=0pt,belowskip=0pt] forall( otype T ) T * malloc( void );§\indexc{malloc}§ @@ -4689,8 +4779,9 @@ forall( otype T ) T * memset( T * ptr ); // remove when default value available \end{lstlisting} -\ + \subsection{ato / strto} +\leavevmode \begin{lstlisting}[aboveskip=0pt,belowskip=0pt] int ato( const char * ptr );§\indexc{ato}§ @@ -4720,9 +4811,9 @@ long double _Complex strto( const char * sptr, char ** eptr ); \end{lstlisting} -\ \subsection{bsearch / qsort} +\leavevmode \begin{lstlisting}[aboveskip=0pt,belowskip=0pt] forall( otype T | { int ?( stmt ) || dynamic_cast< CompoundStmt * >( stmt ) || - dynamic_cast< WhileStmt * >( stmt ) || dynamic_cast< ForStmt * > ( stmt ) || dynamic_cast< SwitchStmt *>( stmt ); - } - - void CodeGenerator::extension( Expression *expr ) { + dynamic_cast< WhileStmt * >( stmt ) || dynamic_cast< ForStmt * >( stmt ) || dynamic_cast< SwitchStmt *>( stmt ); + } + + void CodeGenerator::extension( Expression * expr ) { if ( expr->get_extension() ) { output << "__extension__ "; @@ -54,5 +54,5 @@ } // extension - void CodeGenerator::extension( Declaration *decl ) { + void CodeGenerator::extension( Declaration * decl ) { if ( decl->get_extension() ) { output << "__extension__ "; @@ -73,5 +73,5 @@ } - ostream & operator<<( ostream & output, CodeGenerator::LabelPrinter &printLabels ) { + ostream & operator<<( ostream & output, CodeGenerator::LabelPrinter & printLabels ) { std::list< Label > & labs = *printLabels.labels; // l.unique(); // assumes a sorted list. Why not use set? Does order matter? @@ -79,21 +79,21 @@ output << l.get_name() + ": "; printLabels.cg.genAttributes( l.get_attributes() ); - } + } // for return output; } - CodeGenerator::CodeGenerator( std::ostream &os ) : indent( *this), cur_indent( 0 ), insideFunction( false ), output( os ), printLabels( *this ) { } - - CodeGenerator::CodeGenerator( std::ostream &os, std::string init, int indentation, bool infunp ) + CodeGenerator::CodeGenerator( std::ostream & os ) : indent( *this), cur_indent( 0 ), insideFunction( false ), output( os ), printLabels( *this ) {} + + CodeGenerator::CodeGenerator( std::ostream & os, std::string init, int indentation, bool infunp ) : indent( *this), cur_indent( indentation ), insideFunction( infunp ), output( os ), printLabels( *this ) { //output << std::string( init ); } - CodeGenerator::CodeGenerator( std::ostream &os, char *init, int indentation, bool infunp ) + CodeGenerator::CodeGenerator( std::ostream & os, char * init, int indentation, bool infunp ) : indent( *this ), cur_indent( indentation ), insideFunction( infunp ), output( os ), printLabels( *this ) { //output << std::string( init ); } - string mangleName( DeclarationWithType *decl ) { + string mangleName( DeclarationWithType * decl ) { if ( decl->get_mangleName() != "" ) { // need to incorporate scope level in order to differentiate names for destructors @@ -112,14 +112,14 @@ genCommaList( attr->get_parameters().begin(), attr->get_parameters().end() ); output << ")"; - } + } // if output << ","; - } + } // for output << ")) "; - } + } // if } //*** Declarations - void CodeGenerator::visit( FunctionDecl *functionDecl ) { + void CodeGenerator::visit( FunctionDecl * functionDecl ) { extension( functionDecl ); genAttributes( functionDecl->get_attributes() ); @@ -146,6 +146,8 @@ } - void CodeGenerator::visit( ObjectDecl *objectDecl ) { + void CodeGenerator::visit( ObjectDecl * objectDecl ) { extension( objectDecl ); + genAttributes( objectDecl->get_attributes() ); + handleStorageClass( objectDecl ); output << genType( objectDecl->get_type(), mangleName( objectDecl ) ); @@ -155,4 +157,5 @@ objectDecl->get_init()->accept( *this ); } // if + if ( objectDecl->get_bitfieldWidth() ) { output << ":"; @@ -161,20 +164,20 @@ } - void CodeGenerator::handleAggregate( AggregateDecl *aggDecl ) { + void CodeGenerator::handleAggregate( AggregateDecl * aggDecl ) { if ( aggDecl->get_name() != "" ) output << aggDecl->get_name(); - std::list< Declaration * > &memb = aggDecl->get_members(); + std::list< Declaration * > & memb = aggDecl->get_members(); if ( ! memb.empty() ) { // if ( aggDecl->has_body() ) { -// std::list< Declaration * > &memb = aggDecl->get_members(); +// std::list< Declaration * > & memb = aggDecl->get_members(); output << " {" << endl; cur_indent += CodeGenerator::tabsize; - for ( std::list< Declaration* >::iterator i = memb.begin(); i != memb.end(); i++) { + for ( std::list< Declaration* >::iterator i = memb.begin(); i != memb.end(); i++ ) { output << indent; (*i)->accept( *this ); output << ";" << endl; - } + } // for cur_indent -= CodeGenerator::tabsize; @@ -184,5 +187,5 @@ } - void CodeGenerator::visit( StructDecl *structDecl ) { + void CodeGenerator::visit( StructDecl * structDecl ) { extension( structDecl ); output << "struct "; @@ -190,5 +193,5 @@ } - void CodeGenerator::visit( UnionDecl *unionDecl ) { + void CodeGenerator::visit( UnionDecl * unionDecl ) { extension( unionDecl ); output << "union "; @@ -196,5 +199,5 @@ } - void CodeGenerator::visit( EnumDecl *enumDecl ) { + void CodeGenerator::visit( EnumDecl * enumDecl ) { extension( enumDecl ); output << "enum "; @@ -210,5 +213,5 @@ cur_indent += CodeGenerator::tabsize; for ( std::list< Declaration* >::iterator i = memb.begin(); i != memb.end(); i++) { - ObjectDecl *obj = dynamic_cast< ObjectDecl* >( *i ); + ObjectDecl * obj = dynamic_cast< ObjectDecl* >( *i ); assert( obj ); output << indent << mangleName( obj ); @@ -226,7 +229,7 @@ } - void CodeGenerator::visit( TraitDecl *traitDecl ) {} - - void CodeGenerator::visit( TypedefDecl *typeDecl ) { + void CodeGenerator::visit( TraitDecl * traitDecl ) {} + + void CodeGenerator::visit( TypedefDecl * typeDecl ) { assert( false && "Typedefs are removed and substituted in earlier passes." ); //output << "typedef "; @@ -234,5 +237,5 @@ } - void CodeGenerator::visit( TypeDecl *typeDecl ) { + void CodeGenerator::visit( TypeDecl * typeDecl ) { // really, we should mutate this into something that isn't a TypeDecl but that requires large-scale changes, // still to be done @@ -257,34 +260,34 @@ (*iter)->accept( *this ); output << "]"; - } - } + } // if + } // for output << " = "; } - void CodeGenerator::visit( SingleInit *init ) { + void CodeGenerator::visit( SingleInit * init ) { printDesignators( init->get_designators() ); init->get_value()->accept( *this ); } - void CodeGenerator::visit( ListInit *init ) { + void CodeGenerator::visit( ListInit * init ) { printDesignators( init->get_designators() ); output << "{ "; - if ( init->begin_initializers() == init->end_initializers() ) { + if ( init->begin() == init->end() ) { // illegal to leave initializer list empty for scalar initializers, but always legal to have 0 output << "0"; } else { - genCommaList( init->begin_initializers(), init->end_initializers() ); - } + genCommaList( init->begin(), init->end() ); + } // if output << " }"; } - void CodeGenerator::visit( Constant *constant ) { + void CodeGenerator::visit( Constant * constant ) { output << constant->get_value() ; } //*** Expressions - void CodeGenerator::visit( ApplicationExpr *applicationExpr ) { + void CodeGenerator::visit( ApplicationExpr * applicationExpr ) { extension( applicationExpr ); - if ( VariableExpr *varExpr = dynamic_cast< VariableExpr* >( applicationExpr->get_function() ) ) { + if ( VariableExpr * varExpr = dynamic_cast< VariableExpr* >( applicationExpr->get_function() ) ) { OperatorInfo opInfo; if ( varExpr->get_var()->get_linkage() == LinkageSpec::Intrinsic && operatorLookup( varExpr->get_var()->get_name(), opInfo ) ) { @@ -298,10 +301,10 @@ { assert( arg != applicationExpr->get_args().end() ); - if ( AddressExpr *addrExpr = dynamic_cast< AddressExpr * >( *arg ) ) { + if ( AddressExpr * addrExpr = dynamic_cast< AddressExpr * >( *arg ) ) { // remove & from first assignment/ctor argument *arg = addrExpr->get_arg(); } else { // no address-of operator, so must be a pointer - add dereference - UntypedExpr *newExpr = new UntypedExpr( new NameExpr( "*?" ) ); + UntypedExpr * newExpr = new UntypedExpr( new NameExpr( "*?" ) ); newExpr->get_args().push_back( *arg ); assert( (*arg)->get_results().size() == 1 ); @@ -317,5 +320,5 @@ // do nothing ; - } + } // switch switch ( opInfo.type ) { @@ -351,5 +354,5 @@ // no constructors with 0 or more than 2 parameters assert( false ); - } + } // if break; @@ -385,5 +388,5 @@ // there are no intrinsic definitions of 0/1 or label addresses as functions assert( false ); - } + } // switch } else { varExpr->accept( *this ); @@ -400,7 +403,7 @@ } - void CodeGenerator::visit( UntypedExpr *untypedExpr ) { + void CodeGenerator::visit( UntypedExpr * untypedExpr ) { extension( untypedExpr ); - if ( NameExpr *nameExpr = dynamic_cast< NameExpr* >( untypedExpr->get_function() ) ) { + if ( NameExpr * nameExpr = dynamic_cast< NameExpr* >( untypedExpr->get_function() ) ) { OperatorInfo opInfo; if ( operatorLookup( nameExpr->get_name(), opInfo ) ) { @@ -417,5 +420,4 @@ case OT_CALL: assert( false ); - case OT_CTOR: @@ -437,5 +439,5 @@ // no constructors with 0 or more than 2 parameters assert( false ); - } + } // if break; @@ -470,10 +472,17 @@ // there are no intrinsic definitions of 0 or 1 as functions assert( false ); - } + } // switch } else { - nameExpr->accept( *this ); - output << "("; - genCommaList( untypedExpr->get_args().begin(), untypedExpr->get_args().end() ); - output << ")"; + if ( nameExpr->get_name() == "..." ) { // case V1 ... V2 or case V1~V2 + assert( untypedExpr->get_args().size() == 2 ); + (*untypedExpr->get_args().begin())->accept( *this ); + output << " ... "; + (*--untypedExpr->get_args().end())->accept( *this ); + } else { // builtin routines + nameExpr->accept( *this ); + output << "("; + genCommaList( untypedExpr->get_args().begin(), untypedExpr->get_args().end() ); + output << ")"; + } // if } // if } else { @@ -485,5 +494,11 @@ } - void CodeGenerator::visit( NameExpr *nameExpr ) { + void CodeGenerator::visit( RangeExpr * rangeExpr ) { + rangeExpr->get_low()->accept( *this ); + output << " ... "; + rangeExpr->get_high()->accept( *this ); + } + + void CodeGenerator::visit( NameExpr * nameExpr ) { extension( nameExpr ); OperatorInfo opInfo; @@ -496,9 +511,9 @@ } - void CodeGenerator::visit( AddressExpr *addressExpr ) { + void CodeGenerator::visit( AddressExpr * addressExpr ) { extension( addressExpr ); output << "(&"; // this hack makes sure that we don't convert "constant_zero" to "0" if we're taking its address - if ( VariableExpr *variableExpr = dynamic_cast< VariableExpr* >( addressExpr->get_arg() ) ) { + if ( VariableExpr * variableExpr = dynamic_cast< VariableExpr* >( addressExpr->get_arg() ) ) { output << mangleName( variableExpr->get_var() ); } else { @@ -508,5 +523,5 @@ } - void CodeGenerator::visit( CastExpr *castExpr ) { + void CodeGenerator::visit( CastExpr * castExpr ) { extension( castExpr ); output << "("; @@ -521,14 +536,14 @@ // otherwise, the cast is to an lvalue type, so the cast should be dropped, since the result of a cast is // never an lvalue in C - } + } // if castExpr->get_arg()->accept( *this ); output << ")"; } - void CodeGenerator::visit( UntypedMemberExpr *memberExpr ) { + void CodeGenerator::visit( UntypedMemberExpr * memberExpr ) { assert( false ); } - void CodeGenerator::visit( MemberExpr *memberExpr ) { + void CodeGenerator::visit( MemberExpr * memberExpr ) { extension( memberExpr ); memberExpr->get_aggregate()->accept( *this ); @@ -536,5 +551,5 @@ } - void CodeGenerator::visit( VariableExpr *variableExpr ) { + void CodeGenerator::visit( VariableExpr * variableExpr ) { extension( variableExpr ); OperatorInfo opInfo; @@ -546,5 +561,5 @@ } - void CodeGenerator::visit( ConstantExpr *constantExpr ) { + void CodeGenerator::visit( ConstantExpr * constantExpr ) { assert( constantExpr->get_constant() ); extension( constantExpr ); @@ -552,5 +567,5 @@ } - void CodeGenerator::visit( SizeofExpr *sizeofExpr ) { + void CodeGenerator::visit( SizeofExpr * sizeofExpr ) { extension( sizeofExpr ); output << "sizeof("; @@ -563,5 +578,5 @@ } - void CodeGenerator::visit( AlignofExpr *alignofExpr ) { + void CodeGenerator::visit( AlignofExpr * alignofExpr ) { // use GCC extension to avoid bumping std to C11 extension( alignofExpr ); @@ -575,9 +590,9 @@ } - void CodeGenerator::visit( UntypedOffsetofExpr *offsetofExpr ) { + void CodeGenerator::visit( UntypedOffsetofExpr * offsetofExpr ) { assert( false && "UntypedOffsetofExpr should not reach code generation." ); } - void CodeGenerator::visit( OffsetofExpr *offsetofExpr ) { + void CodeGenerator::visit( OffsetofExpr * offsetofExpr ) { // use GCC builtin output << "__builtin_offsetof("; @@ -587,9 +602,9 @@ } - void CodeGenerator::visit( OffsetPackExpr *offsetPackExpr ) { + void CodeGenerator::visit( OffsetPackExpr * offsetPackExpr ) { assert( false && "OffsetPackExpr should not reach code generation." ); } - void CodeGenerator::visit( LogicalExpr *logicalExpr ) { + void CodeGenerator::visit( LogicalExpr * logicalExpr ) { extension( logicalExpr ); output << "("; @@ -604,5 +619,5 @@ } - void CodeGenerator::visit( ConditionalExpr *conditionalExpr ) { + void CodeGenerator::visit( ConditionalExpr * conditionalExpr ) { extension( conditionalExpr ); output << "("; @@ -615,5 +630,5 @@ } - void CodeGenerator::visit( CommaExpr *commaExpr ) { + void CodeGenerator::visit( CommaExpr * commaExpr ) { extension( commaExpr ); output << "("; @@ -624,9 +639,9 @@ } - void CodeGenerator::visit( TupleExpr *tupleExpr ) {} - - void CodeGenerator::visit( TypeExpr *typeExpr ) {} - - void CodeGenerator::visit( AsmExpr *asmExpr ) { + void CodeGenerator::visit( TupleExpr * tupleExpr ) {} + + void CodeGenerator::visit( TypeExpr * typeExpr ) {} + + void CodeGenerator::visit( AsmExpr * asmExpr ) { if ( asmExpr->get_inout() ) { output << "[ "; @@ -641,5 +656,5 @@ //*** Statements - void CodeGenerator::visit( CompoundStmt *compoundStmt ) { + void CodeGenerator::visit( CompoundStmt * compoundStmt ) { std::list ks = compoundStmt->get_kids(); output << "{" << endl; @@ -654,6 +669,6 @@ if ( wantSpacing( *i ) ) { output << endl; - } - } + } // if + } // for cur_indent -= CodeGenerator::tabsize; @@ -661,5 +676,5 @@ } - void CodeGenerator::visit( ExprStmt *exprStmt ) { + void CodeGenerator::visit( ExprStmt * exprStmt ) { assert( exprStmt ); // cast the top-level expression to void to reduce gcc warnings. @@ -669,5 +684,5 @@ } - void CodeGenerator::visit( AsmStmt *asmStmt ) { + void CodeGenerator::visit( AsmStmt * asmStmt ) { output << "asm "; if ( asmStmt->get_voltile() ) output << "volatile "; @@ -692,5 +707,5 @@ } - void CodeGenerator::visit( IfStmt *ifStmt ) { + void CodeGenerator::visit( IfStmt * ifStmt ) { output << "if ( "; ifStmt->get_condition()->accept( *this ); @@ -705,5 +720,5 @@ } - void CodeGenerator::visit( SwitchStmt *switchStmt ) { + void CodeGenerator::visit( SwitchStmt * switchStmt ) { output << "switch ( " ; switchStmt->get_condition()->accept( *this ); @@ -712,13 +727,10 @@ output << "{" << std::endl; cur_indent += CodeGenerator::tabsize; - - acceptAll( switchStmt->get_branches(), *this ); - + acceptAll( switchStmt->get_statements(), *this ); cur_indent -= CodeGenerator::tabsize; - output << indent << "}"; } - void CodeGenerator::visit( CaseStmt *caseStmt ) { + void CodeGenerator::visit( CaseStmt * caseStmt ) { output << indent; if ( caseStmt->isDefault()) { @@ -737,9 +749,9 @@ (*i)->accept( *this ); output << endl; - } + } // for cur_indent -= CodeGenerator::tabsize; } - void CodeGenerator::visit( BranchStmt *branchStmt ) { + void CodeGenerator::visit( BranchStmt * branchStmt ) { switch ( branchStmt->get_type()) { case BranchStmt::Goto: @@ -759,10 +771,10 @@ output << "continue"; break; - } + } // switch output << ";"; } - void CodeGenerator::visit( ReturnStmt *returnStmt ) { + void CodeGenerator::visit( ReturnStmt * returnStmt ) { output << "return "; maybeAccept( returnStmt->get_expr(), *this ); @@ -770,5 +782,5 @@ } - void CodeGenerator::visit( WhileStmt *whileStmt ) { + void CodeGenerator::visit( WhileStmt * whileStmt ) { if ( whileStmt->get_isDoWhile() ) { output << "do" ; @@ -792,5 +804,5 @@ } - void CodeGenerator::visit( ForStmt *forStmt ) { + void CodeGenerator::visit( ForStmt * forStmt ) { // initialization is always hoisted, so don't bother doing anything with that output << "for (;"; @@ -798,5 +810,5 @@ if ( forStmt->get_condition() != 0 ) { forStmt->get_condition()->accept( *this ); - } + } // if output << ";"; @@ -805,5 +817,5 @@ Expression * expr = new CastExpr( forStmt->get_increment() ); expr->accept( *this ); - } + } // if output << ") "; @@ -814,10 +826,10 @@ } - void CodeGenerator::visit( NullStmt *nullStmt ) { + void CodeGenerator::visit( NullStmt * nullStmt ) { //output << indent << CodeGenerator::printLabels( nullStmt->get_labels() ); output << "/* null statement */ ;"; } - void CodeGenerator::visit( DeclStmt *declStmt ) { + void CodeGenerator::visit( DeclStmt * declStmt ) { declStmt->get_decl()->accept( *this ); @@ -827,5 +839,5 @@ } - void CodeGenerator::handleStorageClass( Declaration *decl ) { + void CodeGenerator::handleStorageClass( Declaration * decl ) { switch ( decl->get_storageClass() ) { case DeclarationNode::Extern: Index: src/CodeGen/CodeGenerator.h =================================================================== --- src/CodeGen/CodeGenerator.h (revision 950f7a72ccf248faed22f2bbd0d7542e24948798) +++ src/CodeGen/CodeGenerator.h (revision 7527e6365628dd566e55f6dbeaca1521c6718837) @@ -10,6 +10,6 @@ // Created On : Mon May 18 07:44:20 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Jul 4 17:12:40 2016 -// Update Count : 34 +// Last Modified On : Thu Aug 4 13:37:07 2016 +// Update Count : 38 // @@ -54,4 +54,5 @@ virtual void visit( ApplicationExpr *applicationExpr ); virtual void visit( UntypedExpr *untypedExpr ); + virtual void visit( RangeExpr * rangeExpr ); virtual void visit( NameExpr *nameExpr ); virtual void visit( AddressExpr *addressExpr ); @@ -118,5 +119,5 @@ void handleAggregate( AggregateDecl *aggDecl ); void handleTypedef( NamedTypeDecl *namedType ); - }; + }; // CodeGenerator template< class Iterator > Index: c/ControlStruct/CaseRangeMutator.cc =================================================================== --- src/ControlStruct/CaseRangeMutator.cc (revision 950f7a72ccf248faed22f2bbd0d7542e24948798) +++ (revision ) @@ -1,192 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// CaseRangeMutator.cc -- -// -// Author : Rodolfo G. Esteves -// Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Tue Jul 12 17:35:13 2016 -// Update Count : 9 -// - -#include -#include -#include -#include - -#include "Common/utility.h" - -#include "SynTree/Statement.h" -#include "SynTree/Expression.h" -#include "SynTree/Constant.h" -#include "SynTree/Type.h" -#include "CaseRangeMutator.h" - -namespace ControlStruct { - Statement *CaseRangeMutator::mutate( SwitchStmt *switchStmt ) { - std::list< Statement * > &cases = switchStmt->get_branches(); - - // a `for' would be more natural... all this contortions are because `replace' invalidates the iterator - std::list< Statement * >::iterator i = cases.begin(); - while ( i != cases.end() ) { - (*i )->acceptMutator( *this ); - - if ( ! newCaseLabels.empty() ) { - std::list< Statement * > newCases; - - // transform( newCaseLabels.begin(), newCaseLabels.end(), bnd1st( ptr_fun( ctor< CaseStmt, Label, Expression * > ) ) ); - - for ( std::list< Expression * >::iterator j = newCaseLabels.begin(); - j != newCaseLabels.end(); j++ ) { - std::list