Index: doc/papers/general/Paper.tex =================================================================== --- doc/papers/general/Paper.tex (revision d7d4702ef66e24b3a78f5bb33e48550ba92013e0) +++ doc/papers/general/Paper.tex (revision d03fa6d2b592bc1c03258a84dc1546317a6f8f84) @@ -39,7 +39,10 @@ \newcommand{\TODO}[1]{\textbf{TODO}: {\itshape #1}} % TODO included %\newcommand{\TODO}[1]{} % TODO elided + % Default underscore is too low and wide. Cannot use lstlisting "literate" as replacing underscore -% removes it as a variable-name character so keyworks in variables are highlighted -\DeclareTextCommandDefault{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}} +% removes it as a variable-name character so keywords in variables are highlighted. MUST APPEAR +% AFTER HYPERREF. +%\DeclareTextCommandDefault{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}} +\renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}} \makeatletter @@ -49,30 +52,42 @@ \setlength{\parindentlnth}{\parindent} +\newcommand{\LstKeywordStyle}[1]{{\lst@basicstyle{\lst@keywordstyle{#1}}}} +\newcommand{\LstCommentStyle}[1]{{\lst@basicstyle{\lst@commentstyle{#1}}}} + \newlength{\gcolumnposn} % temporary hack because lstlisting does not handle tabs correctly \newlength{\columnposn} \setlength{\gcolumnposn}{2.75in} \setlength{\columnposn}{\gcolumnposn} -\newcommand{\C}[2][\@empty]{\ifx#1\@empty\else\global\setlength{\columnposn}{#1}\global\columnposn=\columnposn\fi\hfill\makebox[\textwidth-\columnposn][l]{\lst@commentstyle{#2}}} +\newcommand{\C}[2][\@empty]{\ifx#1\@empty\else\global\setlength{\columnposn}{#1}\global\columnposn=\columnposn\fi\hfill\makebox[\textwidth-\columnposn][l]{\lst@basicstyle{\LstCommentStyle{#2}}}} \newcommand{\CRT}{\global\columnposn=\gcolumnposn} % Latin abbreviation \newcommand{\abbrevFont}{\textit} % set empty for no italics +\newcommand{\EG}{\abbrevFont{e}.\abbrevFont{g}.} \newcommand*{\eg}{% - \@ifnextchar{,}{\abbrevFont{e}.\abbrevFont{g}.}% - {\@ifnextchar{:}{\abbrevFont{e}.\abbrevFont{g}.}% - {\abbrevFont{e}.\abbrevFont{g}.,\xspace}}% + \@ifnextchar{,}{\EG}% + {\@ifnextchar{:}{\EG}% + {\EG,\xspace}}% }% +\newcommand{\IE}{\abbrevFont{i}.\abbrevFont{e}.} \newcommand*{\ie}{% - \@ifnextchar{,}{\abbrevFont{i}.\abbrevFont{e}.}% - {\@ifnextchar{:}{\abbrevFont{i}.\abbrevFont{e}.}% - {\abbrevFont{i}.\abbrevFont{e}.,\xspace}}% + \@ifnextchar{,}{\IE}% + {\@ifnextchar{:}{\IE}% + {\IE,\xspace}}% }% +\newcommand{\ETC}{\abbrevFont{etc}} \newcommand*{\etc}{% - \@ifnextchar{.}{\abbrevFont{etc}}% - {\abbrevFont{etc}.\xspace}% + \@ifnextchar{.}{\ETC}% + {\ETC\xspace}% }% -\newcommand{\etal}{% - \@ifnextchar{.}{\abbrevFont{et~al}}% - {\abbrevFont{et al}.\xspace}% +\newcommand{\ETAL}{\abbrevFont{et}\hspace{2pt}\abbrevFont{al}} +\newcommand*{\etal}{% + \@ifnextchar{.}{\protect\ETAL}% + {\abbrevFont{\protect\ETAL}.\xspace}% +}% +\newcommand{\VIZ}{\abbrevFont{viz}} +\newcommand*{\viz}{% + \@ifnextchar{.}{\VIZ}% + {\abbrevFont{\VIZ}.\xspace}% }% \makeatother @@ -80,8 +95,12 @@ % 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__, - fallthrough,fallthru,finally,forall,ftype,_Generic,_Imaginary,inline,__label__,lvalue,_Noreturn,one_t,otype,restrict,_Static_assert, - _Thread_local,throw,throwResume,trait,try,ttype,typeof,__typeof,__typeof__,zero_t}, + morekeywords={ + _Alignas, _Alignof, __alignof, __alignof__, asm, __asm, __asm__, _At, __attribute, + __attribute__, auto, _Bool, catch, catchResume, choose, _Complex, __complex, __complex__, + __const, __const__, disable, dtype, enable, __extension__, fallthrough, fallthru, + finally, forall, ftype, _Generic, _Imaginary, inline, __label__, lvalue, _Noreturn, one_t, + otype, restrict, _Static_assert, throw, throwResume, trait, try, ttype, typeof, __typeof, + __typeof__, virtual, with, zero_t}, + moredirectives={defined,include_next}% }% @@ -91,5 +110,5 @@ basicstyle=\linespread{0.9}\sf, % reduce line spacing and use sanserif font stringstyle=\tt, % use typewriter font -tabsize=4, % 4 space tabbing +tabsize=5, % N space tabbing xleftmargin=\parindentlnth, % indent code to paragraph indentation %mathescape=true, % LaTeX math escape in CFA code $...$ @@ -101,7 +120,7 @@ belowskip=3pt, % replace/adjust listing characters that look bad in sanserif -literate={-}{\makebox[1.4ex][c]{\raisebox{0.5ex}{\rule{1.2ex}{0.06ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1 +literate={-}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1 {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1 - {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1.4ex][c]{\raisebox{0.5ex}{\rule{1.2ex}{0.06ex}}}\kern-0.3ex\textgreater}2, + {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex\textgreater}2, moredelim=**[is][\color{red}]{`}{`}, }% lstset @@ -109,4 +128,12 @@ % inline code @...@ \lstMakeShortInline@% + +\lstnewenvironment{cfa}[1][] +{\CFA\lstset{#1}} +{} +\lstnewenvironment{C++}[1][] % use C++ style +{\lstset{language=C++,moredelim=**[is][\protect\color{red}]{`}{`},#1}} +{} + \title{Generic and Tuple Types with Efficient Dynamic Layout in \protect\CFA} @@ -148,5 +175,5 @@ The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from commercial operating-systems to hobby projects. This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more. -The TIOBE\cite{TIOBE} ranks the top 5 most popular programming languages as: Java 16\%, \Textbf{C 7\%}, \Textbf{\CC 5\%}, \Csharp 4\%, Python 4\% = 36\%, where the next 50 languages are less than 3\% each with a long tail. +The TIOBE~\cite{TIOBE} ranks the top 5 most popular programming languages as: Java 16\%, \Textbf{C 7\%}, \Textbf{\CC 5\%}, \Csharp 4\%, Python 4\% = 36\%, where the next 50 languages are less than 3\% each with a long tail. The top 3 rankings over the past 30 years are: \lstDeleteShortInline@% @@ -185,5 +212,5 @@ \label{sec:poly-fns} -\CFA{}\hspace{1pt}'s polymorphism was originally formalized by Ditchfield\cite{Ditchfield92}, and first implemented by Bilson\cite{Bilson03}. +\CFA{}\hspace{1pt}'s polymorphism was originally formalized by Ditchfield~\cite{Ditchfield92}, and first implemented by Bilson~\cite{Bilson03}. The signature feature of \CFA is parametric-polymorphic functions~\cite{forceone:impl,Cormack90,Duggan96} with functions generalized using a @forall@ clause (giving the language its name): \begin{lstlisting} @@ -337,4 +364,5 @@ % 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. + \section{Generic Types} @@ -465,4 +493,5 @@ However, the \CFA type-checker ensures matching types are used by all calls to @?+?@, preventing nonsensical computations like adding a length to a volume. + \section{Tuples} \label{sec:tuples} @@ -728,5 +757,5 @@ \end{lstlisting} Hence, function parameter and return lists are flattened for the purposes of type unification allowing the example to pass expression resolution. -This relaxation is possible by extending the thunk scheme described by Bilson\cite{Bilson03}. +This relaxation is possible by extending the thunk scheme described by Bilson~\cite{Bilson03}. Whenever a candidate's parameter structure does not exactly match the formal parameter's structure, a thunk is generated to specialize calls to the actual function: \begin{lstlisting} @@ -899,5 +928,226 @@ \end{comment} -\section{Improved Procedural Paradigm} + +\section{Control Structures} + + +\subsection{\texorpdfstring{Labelled \LstKeywordStyle{continue} / \LstKeywordStyle{break}}{Labelled continue / break}} + +While C provides @continue@ and @break@ statements for altering control flow, both are restricted to one level of nesting for a particular control structure. +Unfortunately, this restriction forces programmers to use @goto@ to achieve the equivalent control-flow for more than one level of nesting. +To prevent having to switch to the @goto@, \CFA extends the @continue@ and @break@ with a target label to support static multi-level exit~\cite{Buhr85}, as in Java. +For both @continue@ and @break@, the target label must be directly associated with a @for@, @while@ or @do@ statement; +for @break@, the target label can also be associated with a @switch@, @if@ or compound (@{}@) statement. +Figure~\ref{f:MultiLevelExit} shows @continue@ and @break@ indicating the specific control structure, and the corresponding C program using only @goto@ and labels. +The innermost loop has 7 exit points, which cause continuation or termination of one or more of the 7 nested control-structures. + +\begin{figure} +\lstDeleteShortInline@% +\begin{tabular}{@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{}} +\multicolumn{1}{@{\hspace{\parindentlnth}}c@{\hspace{\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{@{\hspace{\parindentlnth}}c}{\textbf{C}} \\ +\begin{lstlisting} +`LC:` { + ... $declarations$ ... + `LS:` switch ( ... ) { + case 3: + `LIF:` if ( ... ) { + `LF:` for ( ... ) { + `LW:` while ( ... ) { + ... break `LC`; ... + ... break `LS`; ... + ... break `LIF`; ... + ... continue `LF;` ... + ... break `LF`; ... + ... continue `LW`; ... + ... break `LW`; ... + } // while + } // for + } else { + ... break `LIF`; ... + } // if + } // switch +} // compound +\end{lstlisting} +& +\begin{lstlisting} +{ + ... $declarations$ ... + switch ( ... ) { + case 3: + if ( ... ) { + for ( ... ) { + while ( ... ) { + ... goto `LC`; ... + ... goto `LS`; ... + ... goto `LIF`; ... + ... goto `LFC`; ... + ... goto `LFB`; ... + ... goto `LWC`; ... + ... goto `LWB`; ... + `LWC`: ; } `LWB:` ; + `LFC:` ; } `LFB:` ; + } else { + ... goto `LIF`; ... + } `L3:` ; + } `LS:` ; +} `LC:` ; +\end{lstlisting} +& +\begin{lstlisting} + + + + + + + +// terminate compound +// terminate switch +// terminate if +// continue loop +// terminate loop +// continue loop +// terminate loop + + + +// terminate if + + + +\end{lstlisting} +\end{tabular} +\lstMakeShortInline@% +\caption{Multi-level Exit} +\label{f:MultiLevelExit} +\end{figure} + +Both labelled @continue@ and @break@ are a @goto@ restricted in the following ways: +\begin{itemize} +\item +They cannot create a loop, which means only the looping constructs cause looping. +This restriction means all situations resulting in repeated execution are clearly delineated. +\item +They cannot branch into a control structure. +This restriction prevents missing declarations and/or initializations at the start of a control structure resulting in undefined behaviour. +\end{itemize} +The advantage of the labelled @continue@/@break@ is allowing static multi-level exits without having to use the @goto@ statement, and tying control flow to the target control structure rather than an arbitrary point in a program. +Furthermore, the location of the label at the \emph{beginning} of the target control structure informs the reader (eye candy) that complex control-flow is occurring in the body of the control structure. +With @goto@, the label is at the end of the control structure, which fails to convey this important clue early enough to the reader. +Finally, using an explicit target for the transfer instead of an implicit target allows new constructs to be added or removed without affecting existing constructs. +The implicit targets of the current @continue@ and @break@, \ie the closest enclosing loop or @switch@, change as certain constructs are added or removed. + + +\subsection{\texorpdfstring{\LstKeywordStyle{with} Clause / Statement}{with Clause / Statement}} +\label{s:WithClauseStatement} + +In any programming language, some functions have a naturally close relationship with a particular data type. +Object-oriented programming allows this close relationship to be codified in the language by making such functions \emph{class methods} of their related data type. +Class methods have certain privileges with respect to their associated data type, notably un-prefixed access to the fields of that data type. +When writing C functions in an object-oriented style, this un-prefixed access is swiftly missed, as access to fields of a @Foo* f@ requires an extra three characters @f->@ every time, which disrupts coding flow and clutters the produced code. + +\TODO{Fill out section. Be sure to mention arbitrary expressions in with-blocks, recent change driven by Thierry to prioritize field name over parameters.} + + +In object-oriented programming, there is an implicit first parameter, often names @self@ or @this@, which is elided. +\begin{C++} +class C { + int i, j; + int mem() { $\C{\color{red}// implicit "this" parameter}$ + i = 1; $\C{\color{red}// this->i}$ + j = 2; $\C{\color{red}// this->j}$ + } +} +\end{C++} +Since CFA is non-object-oriented, the equivalent object-oriented program looks like: +\begin{cfa} +struct S { int i, j; }; +int mem( S & `this` ) { $\C{// explicit "this" parameter}$ + `this.`i = 1; $\C{// "this" is not elided}$ + `this.`j = 2; +} +\end{cfa} +but it is cumbersome having to write "this." many times in a member. + +\CFA provides a @with@ clause/statement (see Pascal~\cite[\S~4.F]{Pascal}) to elided the "@this.@" by opening a scope containing field identifiers, changing the qualified fields into variables and giving an opportunity for optimizing qualified references. +\begin{cfa} +int mem( S &this ) `with this` { $\C{// with clause}$ + i = 1; $\C{\color{red}// this.i}$ + j = 2; $\C{\color{red}// this.j}$ +} +\end{cfa} +which extends to multiple routine parameters: +\begin{cfa} +struct T { double m, n; }; +int mem2( S & this1, T & this2 ) `with this1, this2` { + i = 1; j = 2; + m = 1.0; n = 2.0; +} +\end{cfa} + +The statement form is used within a block: +\begin{cfa} +int foo() { + struct S1 { ... } s1; + struct S2 { ... } s2; + `with s1` { $\C{// with statement}$ + // access fields of s1 without qualification + `with s2` { $\C{// nesting}$ + // access fields of s1 and s2 without qualification + } + } + `with s1, s2` { + // access unambiguous fields of s1 and s2 without qualification + } +} +\end{cfa} + +When opening multiple structures, fields with the same name and type are ambiguous and must be fully qualified. +For fields with the same name but different type, context/cast can be used to disambiguate. +\begin{cfa} +struct S { int i; int j; double m; } a, c; +struct T { int i; int k; int m } b, c; +`with a, b` { + j + k; $\C{// unambiguous, unique names define unique types}$ + i; $\C{// ambiguous, same name and type}$ + a.i + b.i; $\C{// unambiguous, qualification defines unique names}$ + m; $\C{// ambiguous, same name and no context to define unique type}$ + m = 5.0; $\C{// unambiguous, same name and context defines unique type}$ + m = 1; $\C{// unambiguous, same name and context defines unique type}$ +} +`with c` { ... } $\C{// ambiguous, same name and no context}$ +`with (S)c` { ... } $\C{// unambiguous, same name and cast defines unique type}$ +\end{cfa} + +The components in the "with" clause + + with a, b, c { ... } + +serve 2 purposes: each component provides a type and object. The type must be a +structure type. Enumerations are already opened, and I think a union is opened +to some extent, too. (Or is that just unnamed unions?) The object is the target +that the naked structure-fields apply to. The components are open in "parallel" +at the scope of the "with" clause/statement, so opening "a" does not affect +opening "b", etc. This semantic is different from Pascal, which nests the +openings. + +Having said the above, it seems reasonable to allow a "with" component to be an +expression. The type is the static expression-type and the object is the result +of the expression. Again, the type must be an aggregate. Expressions require +parenthesis around the components. + + with( a, b, c ) { ... } + +Does this now make sense? + +Having written more CFA code, it is becoming clear to me that I *really* want +the "with" to be implemented because I hate having to type all those object +names for fields. It's a great way to drive people away from the language. + + +\subsection{Exception Handling ???} + + +\section{Declarations} It is important to the design team that \CFA subjectively ``feel like'' C to user programmers. @@ -906,4 +1156,13 @@ Nonetheless, some features of object-oriented languages are undeniably convienient, and the \CFA design team has attempted to adapt them to a procedural paradigm so as to incorporate their benefits into \CFA; two of these features are resource management and name scoping. + +\subsection{Alternative Declaration Syntax} + + +\subsection{References} + +\TODO{Pull draft text from user manual; make sure to discuss nested references and rebind operator drawn from lvalue-addressof operator} + + \subsection{Constructors and Destructors} @@ -914,16 +1173,42 @@ \TODO{Fill out section. Mention field-constructors and at-equal escape hatch to C-style initialization. Probably pull some text from Rob's thesis for first draft.} -\subsection{with Statement} - -In any programming language, some functions have a naturally close relationship with a particular data type. -Object-oriented programming allows this close relationship to be codified in the language by making such functions \emph{class methods} of their related data type. -Class methods have certain privileges with respect to their associated data type, notably un-prefixed access to the fields of that data type. -When writing C functions in an object-oriented style, this un-prefixed access is swiftly missed, as access to fields of a @Foo* f@ requires an extra three characters @f->@ every time, which disrupts coding flow and clutters the produced code. - -\TODO{Fill out section. Be sure to mention arbitrary expressions in with-blocks, recent change driven by Thierry to prioritize field name over parameters.} - -\section{References} - -\TODO{Pull draft text from user manual; make sure to discuss nested references and rebind operator drawn from lvalue-addressof operator} + +\subsection{Default Parameters} + + +\section{Literals} + + +\subsection{0/1} + + +\subsection{Units} + +Alternative call syntax (literal argument before routine name) to convert basic literals into user literals. + +{\lstset{language=CFA,deletedelim=**[is][]{`}{`},moredelim=**[is][\color{red}]{@}{@}} +\begin{lstlisting} +struct Weight { double stones; }; + +void ?{}( Weight & w ) { w.stones = 0; } $\C{// operations}$ +void ?{}( Weight & w, double w ) { w.stones = w; } +Weight ?+?( Weight l, Weight r ) { return (Weight){ l.stones + r.stones }; } + +Weight @?`st@( double w ) { return (Weight){ w }; } $\C{// backquote for units}$ +Weight @?`lb@( double w ) { return (Weight){ w / 14.0 }; } +Weight @?`kg@( double w ) { return (Weight) { w * 0.1575}; } + +int main() { + Weight w, hw = { 14 }; $\C{// 14 stone}$ + w = 11@`st@ + 1@`lb@; + w = 70.3@`kg@; + w = 155@`lb@; + w = 0x_9b_u@`lb@; $\C{// hexadecimal unsigned weight (155)}$ + w = 0_233@`lb@; $\C{// octal weight (155)}$ + w = 5@`st@ + 8@`kg@ + 25@`lb@ + hw; +} +\end{lstlisting} +}% + \section{Evaluation}