Changeset 14cbfad
- Timestamp:
- Feb 17, 2018, 2:08:03 PM (7 years ago)
- Branches:
- ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
- Children:
- c0b4db0
- Parents:
- 93401f8
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/papers/general/Paper.tex
r93401f8 r14cbfad 233 233 234 234 C already has a limited form of ad-hoc polymorphism in the form of its basic arithmetic operators, which apply to a variety of different types using identical syntax. 235 \CFA extends the built-in operator overloading by allowing users to define overloads for any function, not just operators, and even any variable; Section~\ref{sec:libraries} includes a number of examples of how this overloading simplifies \CFA programming relative to C. 235 \CFA extends the built-in operator overloading by allowing users to define overloads for any function, not just operators, and even any variable; 236 Section~\ref{sec:libraries} includes a number of examples of how this overloading simplifies \CFA programming relative to C. 236 237 Code generation for these overloaded functions and variables is implemented by the usual approach of mangling the identifier names to include a representation of their type, while \CFA decides which overload to apply based on the same ``usual arithmetic conversions'' used in C to disambiguate operator overloads. 237 238 As an example: … … 254 255 The macro wrapping the generic expression imposes some limitations; as an example, it could not implement the example above, because the variables @max@ would collide with the functions @max@. 255 256 Ergonomic limitations of @_Generic@ include the necessity to put a fixed list of supported types in a single place and manually dispatch to appropriate overloads, as well as possible namespace pollution from the functions dispatched to, which must all have distinct names. 257 258 % http://fanf.livejournal.com/144696.html 259 % http://www.robertgamble.net/2012/01/c11-generic-selections.html 260 % https://abissell.com/2014/01/16/c11s-_generic-keyword-macro-applications-and-performance-impacts/ 261 256 262 257 263 \subsection{\texorpdfstring{\LstKeywordStyle{forall} Functions}{forall Functions}} … … 290 296 void * bsearch( const void * key, const void * base, size_t nmemb, size_t size, 291 297 int (* compar)( const void *, const void * )); 298 292 299 int comp( const void * t1, const void * t2 ) { return *(double *)t1 < *(double *)t2 ? -1 : 293 300 *(double *)t2 < *(double *)t1 ? 1 : 0; } 301 294 302 double key = 5.0, vals[10] = { /* 10 sorted float values */ }; 295 303 double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp ); $\C{// search sorted array}$ … … 300 308 int comp( const void * t1, const void * t2 ) { /* as above with double changed to T */ } 301 309 return (T *)bsearch( &key, arr, size, sizeof(T), comp ); } 310 302 311 forall( otype T | { int ?<?( T, T ); } ) unsigned int bsearch( T key, const T * arr, size_t size ) { 303 312 T * result = bsearch( key, arr, size ); $\C{// call first version}$ 304 313 return result ? result - arr : size; } $\C{// pointer subtraction includes sizeof(T)}$ 314 305 315 double * val = bsearch( 5.0, vals, 10 ); $\C{// selection based on return type}$ 306 316 int posn = bsearch( 5.0, vals, 10 ); … … 311 321 \CC's type-system cannot disambiguate between the two versions of @bsearch@ because it does not use the return type in overload resolution, nor can \CC separately compile a templated @bsearch@. 312 322 313 \CFA has replacement libraries condensing hundreds of existing C functions into tens of \CFA overloaded functions, all without rewriting the actual computations .323 \CFA has replacement libraries condensing hundreds of existing C functions into tens of \CFA overloaded functions, all without rewriting the actual computations (see Section~\ref{sec:libraries}). 314 324 For example, it is possible to write a type-safe \CFA wrapper @malloc@ based on the C @malloc@: 315 325 \begin{lstlisting} … … 346 356 \CFA provides \newterm{traits} to name a group of type assertions, where the trait name allows specifying the same set of assertions in multiple locations, preventing repetition mistakes at each function declaration: 347 357 \begin{lstlisting} 348 trait summable( otype T ) {358 trait `summable`( otype T ) { 349 359 void ?{}( T *, zero_t ); $\C{// constructor from 0 literal}$ 350 360 T ?+?( T, T ); $\C{// assortment of additions}$ … … 352 362 T ++?( T * ); 353 363 T ?++( T * ); }; 364 354 365 forall( otype T `| summable( T )` ) T sum( T a[$\,$], size_t size ) { // use trait 355 366 `T` total = { `0` }; $\C{// instantiate T from 0 by calling its constructor}$ … … 425 436 forall( otype T ) T value( pair( const char *, T ) p ) { return p.second; } 426 437 forall( dtype F, otype T ) T value_p( pair( F *, T * ) p ) { return * p.second; } 438 427 439 pair( const char *, int ) p = { "magic", 42 }; 428 440 int magic = value( p ); … … 1150 1162 @case@ clauses are made disjoint by the @break@ statement. 1151 1163 While the ability to fall through \emph{is} a useful form of control flow, it does not match well with programmer intuition, resulting in many errors from missing @break@ statements. 1152 \CFA provides a newcontrol structure, @choose@, which mimics @switch@, but reverses the meaning of fall through:1164 For backwards compatibility, \CFA provides a \emph{new} control structure, @choose@, which mimics @switch@, but reverses the meaning of fall through: 1153 1165 \begin{cquote} 1154 1166 \lstDeleteShortInline@% … … 1157 1169 \begin{cfa} 1158 1170 `choose` ( day ) { 1159 case Mon~Thu: 1160 // program 1161 1162 case Fri: 1163 // program 1171 case Mon~Thu: // program 1172 1173 case Fri: // program 1164 1174 wallet += pay; 1165 1175 `fallthrough;` 1166 case Sat: 1167 // party 1176 case Sat: // party 1168 1177 wallet -= party; 1169 1178 1170 case Sun: 1171 // rest 1172 1173 default: 1174 // error 1179 case Sun: // rest 1180 1181 default: // error 1175 1182 } 1176 1183 \end{cfa} … … 1178 1185 \begin{cfa} 1179 1186 switch ( day ) { 1180 case Mon: case Tue: case Wed: case Thu: 1181 // program 1187 case Mon: case Tue: case Wed: case Thu: // program 1182 1188 `break;` 1183 case Fri: 1184 // program 1189 case Fri: // program 1185 1190 wallet += pay; 1186 1191 1187 case Sat: 1188 // party 1192 case Sat: // party 1189 1193 wallet -= party; 1190 1194 `break;` 1191 case Sun: 1192 // rest 1195 case Sun: // rest 1193 1196 `break;` 1194 default: 1195 // error 1197 default: // error 1196 1198 } 1197 1199 \end{cfa} … … 1228 1230 \label{s:WithClauseStatement} 1229 1231 1230 Grouping heterogen ous data into \newterm{aggregate}s (structure/union) is a common programming practice, and an aggregate can be further organized into more complex structures, such as arrays and containers:1232 Grouping heterogeneous data into \newterm{aggregate}s (structure/union) is a common programming practice, and an aggregate can be further organized into more complex structures, such as arrays and containers: 1231 1233 \begin{cfa} 1232 1234 struct S { $\C{// aggregate}$ … … 1243 1245 } 1244 1246 \end{cfa} 1247 which extends to multiple levels of qualification for nested aggregates. 1245 1248 A similar situation occurs in object-oriented programming, \eg \CC: 1246 1249 \begin{C++} … … 1249 1252 int i; 1250 1253 double d; 1251 int mem() { $\C{// implicit "this" parameter}$1254 int f() { $\C{// implicit "this" parameter}$ 1252 1255 `this->`c; `this->`i; `this->`d; $\C{// access containing fields}$ 1253 1256 } 1254 1257 } 1255 1258 \end{C++} 1256 Nesting of member routines in a \lstinline[language=C++]@class@ allows eliding \lstinline[language=C++]@this->@ because of lexical scoping.1259 Object-oriented nesting of member routines in a \lstinline[language=C++]@class@ allows eliding \lstinline[language=C++]@this->@ because of lexical scoping. 1257 1260 However, for other aggregate parameters, qualification is necessary: 1258 1261 \begin{cfa} 1259 1262 struct T { double m, n; }; 1260 int C:: mem( T & t ) {$\C{// multiple aggregate parameters}$1263 int C::f( T & t ) { $\C{// multiple aggregate parameters}$ 1261 1264 c; i; d; $\C{\color{red}// this-\textgreater.c, this-\textgreater.i, this-\textgreater.d}$ 1262 1265 `t.`m; `t.`n; $\C{// must qualify}$ … … 1264 1267 \end{cfa} 1265 1268 1266 % In object-oriented programming, there is an implicit first parameter, often names @self@ or @this@, which is elided. 1267 % In any programming language, some functions have a naturally close relationship with a particular data type. 1268 % Object-oriented programming allows this close relationship to be codified in the language by making such functions \newterm{class methods} of their related data type. 1269 % Class methods have certain privileges with respect to their associated data type, notably un-prefixed access to the fields of that data type. 1270 % 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. 1271 % 1272 % \TODO{Fill out section. Be sure to mention arbitrary expressions in with-blocks, recent change driven by Thierry to prioritize field name over parameters.} 1273 1274 To simplify the programmer experience, \CFA provides a @with@ clause/statement (see Pascal~\cite[\S~4.F]{Pascal}) to elide aggregate qualification to fields by opening a scope containing the field identifiers. 1269 To simplify the programmer experience, \CFA provides a @with@ statement (see Pascal~\cite[\S~4.F]{Pascal}) to elide aggregate qualification to fields by opening a scope containing the field identifiers. 1275 1270 Hence, the qualified fields become variables with the side-effect that it is easier to optimizing field references in a block. 1276 1271 \begin{cfa} 1277 void f( S s ) `with( s )` { $\C{// with clause}$ 1278 c; i; d; $\C{\color{red}// s.c, s.i, s.d}$ 1279 } 1280 \end{cfa} 1281 and the equivalence for object-style programming is: 1282 \begin{cfa} 1283 int mem( S & this ) `with( this )` { $\C{// with clause}$ 1272 void f( S & this ) `with ( this )` { $\C{// with statement}$ 1284 1273 c; i; d; $\C{\color{red}// this.c, this.i, this.d}$ 1285 1274 } … … 1287 1276 with the generality of opening multiple aggregate-parameters: 1288 1277 \begin{cfa} 1289 int mem( S & s, T & t ) `with( s, t )` {$\C{// multiple aggregate parameters}$1278 int f( S & s, T & t ) `with ( s, t )` { $\C{// multiple aggregate parameters}$ 1290 1279 c; i; d; $\C{\color{red}// s.c, s.i, s.d}$ 1291 1280 m; n; $\C{\color{red}// t.m, t.n}$ … … 1293 1282 \end{cfa} 1294 1283 1295 In detail, the @with@ clause/statement has the form:1284 In detail, the @with@ statement has the form: 1296 1285 \begin{cfa} 1297 1286 $\emph{with-statement}$: … … 1305 1294 1306 1295 All expressions in the expression list are open in ``parallel'' within the compound statement. 1307 This semantic is different from Pascal, which nests the openings .1308 The difference between parallel and nesting occurs for fields with the same name but differenttype:1309 \begin{cfa} 1310 struct S { int i; int j; double m; } s, w;1311 struct T { int i; int k; int m} t, w;1312 with ( s, t ) {1313 j + k; $\C{// unambiguous, s.j + t. m}$1296 This semantic is different from Pascal, which nests the openings from left to right. 1297 The difference between parallel and nesting occurs for fields with the same name and type: 1298 \begin{cfa} 1299 struct S { int `i`; int j; double m; } s, w; 1300 struct T { int `i`; int k; int m; } t, w; 1301 with ( s, t ) { 1302 j + k; $\C{// unambiguous, s.j + t.k}$ 1314 1303 m = 5.0; $\C{// unambiguous, t.m = 5.0}$ 1315 1304 m = 1; $\C{// unambiguous, s.m = 1}$ 1316 int a = s.i + m; $\C{// unambiguous, a = s.i + t.i}$ 1317 int b = s.i + t.i; $\C{// unambiguous, qualification}$ 1318 sout | (double)m | endl; $\C{// unambiguous, cast}$ 1319 i; $\C{// ambiguous}$ 1320 } 1321 \end{cfa} 1322 \CFA's ability to overload variables means usages of field with the same names can be automatically disambiguated, eliminating most qualification. 1305 int a = m; $\C{// unambiguous, a = s.i }$ 1306 double b = m; $\C{// unambiguous, b = t.m}$ 1307 int c = s.i + t.i; $\C{// unambiguous, qualification}$ 1308 (double)m; $\C{// unambiguous, cast}$ 1309 } 1310 \end{cfa} 1311 For parallel semantics, both @s.i@ and @t.i@ are visible, so @i@ is ambiguous without qualification; 1312 for nested semantics, @t.i@ hides @s.i@, so @i@ implies @t.i@. 1313 \CFA's ability to overload variables means fields with the same name but different types are automatically disambiguated, eliminating most qualification when opening multiple aggregates. 1323 1314 Qualification or a cast is used to disambiguate. 1324 A cast may be necessary to disambiguate between the overload variables in a @with@ expression: 1325 \begin{cfa} 1326 with( w ) { ... } $\C{// ambiguous, same name and no context}$ 1327 with( (S)w ) { ... } $\C{// unambiguous}$ 1328 \end{cfa} 1329 1315 1316 There is an interesting problem between parameters and the routine @with@, \eg: 1317 \begin{cfa} 1318 void ?{}( S & s, int i ) with ( s ) { $\C{// constructor}$ 1319 `s.i = i;` j = 3; m = 5.5; 1320 } 1321 \end{cfa} 1322 Here, the assignment @s.i = i@ means @s.i = s.i@, which is meaningless, and there is no mechanism to qualify the parameter @i@, making the assignment impossible using the routine @with@. 1323 To solve this problem, parameters are treated like an initialized aggregate: 1324 \begin{cfa} 1325 struct Params { 1326 S & s; 1327 int i; 1328 } params; 1329 \end{cfa} 1330 and implicitly opened \emph{after} a routine open, to give them higher priority: 1331 \begin{cfa} 1332 void ?{}( S & s, int i ) with ( s ) `with( $\emph{\color{red}params}$ )` { 1333 s.i = i; j = 3; m = 5.5; 1334 } 1335 \end{cfa} 1336 Finally, a cast may be used to disambiguate among overload variables in a @with@ expression: 1337 \begin{cfa} 1338 with ( w ) { ... } $\C{// ambiguous, same name and no context}$ 1339 with ( (S)w ) { ... } $\C{// unambiguous, cast}$ 1340 \end{cfa} 1341 and @with@ expressions may be pointers and references (see Section~\ref{s:References}) to aggregates: 1330 1342 \begin{cfa} 1331 1343 struct S { int i, j; } sv; 1332 with ( sv ) {1344 with ( sv ) { $\C{variable}$ 1333 1345 S & sr = sv; 1334 with ( sr ) {1346 with ( sr ) { $\C{reference}$ 1335 1347 S * sp = &sv; 1336 with ( *sp ) {1348 with ( *sp ) { $\C{pointer}$ 1337 1349 i = 3; j = 4; $\C{\color{red}// sp-{\textgreater}i, sp-{\textgreater}j}$ 1338 1350 } … … 1343 1355 \end{cfa} 1344 1356 1345 The statement form is used within a block:1346 \begin{cfa}1347 int foo() {1348 struct S1 { ... } s1;1349 struct S2 { ... } s2;1350 `with( s1 )` { $\C{// with statement}$1351 // access fields of s1 without qualification1352 `with( s2 )` { $\C{// nesting}$1353 // access fields of s1 and s2 without qualification1354 }1355 }1356 `with( s1, s2 )` {1357 // access unambiguous fields of s1 and s2 without qualification1358 }1359 }1360 \end{cfa}1361 1357 1362 1358 % \subsection{Exception Handling ???} 1359 1363 1360 1364 1361 \section{Declarations} … … 1615 1612 1616 1613 \subsection{References} 1614 \label{s:References} 1617 1615 1618 1616 All variables in C have an \newterm{address}, a \newterm{value}, and a \newterm{type};
Note: See TracChangeset
for help on using the changeset viewer.