ISO/IEC JTC1 SC22 WG14 N1483 - 2010-05-29
Lawrence Crowl, crowl@google.com, Lawrence@Crowl.org
Introduction
Terminology
Lambda Expressions
Primary versus Postfix
Indicator
Empty Closure Parameter Lists
Return Type Specification
Return Type Inference
Label Scope
Capture Semantics
Capture by Value
Mutable Closures
Value Capture Address
Capture by Reference
Capture Lifetime
Multiple Locations
Concurrency
Capture Sharing
Lambda Substitutability
Nested Capture
Frame Pointer
Recommendations
Mixed Capture
Passing Closure Objects
Parameters of Closure Type
Closures as Function Pointer
Summary
The C++ standards committee developed a facility for lambda expressions. The resulting facility is embodied in the C++ Final Committee Draft N3092. The C committee has a proposal to add a similar facility, N1451. Some interpretation of N1451 is based on text in N1370 and N1457.
This paper compares the C++ facility to the proposed C facility. Direct C/C++ compatibility in lambda facilities is less important than in other areas, but even so I will make recommendations that increase the compatibility of the facilities.
The terminology in N1451 is a bit inconsistent due to a history that is somewhat incompatible with existing C terms. This paper adopts the following terminology, mostly from C++.
A lambda expression is a source language expression. Such expressions are executed. N1451 variously uses 'block', 'closure', and 'closure literal'. The term lambda expression may be shortened to lambda.
A closure object is the result of executing a lambda expression. Such objects are called sometime later. N1451 variously uses 'block', 'closure', and 'closure object'. The term closure object may be shortened to closure.
When execution of a lambda expression produces a closure, it will capture variables it references from outside the scope of the lambda expression.
The closure storage duration is the duration of variables explicitly associated with lambda expressions. C++ does not have such a storage duration, though much of the effect can be achieved in other ways.
Recommendation: Make the terminology consistent. Using the C++ terminology would be most helpful.
Both facilities provide similar, but incompatible, syntax for lambda expressions.
C++ places lamda expressions within primary-expression. N1451 places them within postfix-expression. This placement prevents calling a lambda expression immediately. While this limitation is not major, it seems unnecessary and could cause problems when function macros expand to lambda expressions.
Recommendation: For generality and consistency with C++, place lambda expressions within primary-expression.
N1451 begins lambda expressions with '^'.
C++ begins lambda expressions with '['.
Both are taking advantage of the fact
that those characters could formerly
never be a prefix of primary-expression.
C++ has its syntax to enable detailed specification
of the set of captured variables.
That is, a C++ lambda expression begins with
[ lambda-captureopt ].
Recommendation: We defer recommendations to the final section.
Both proposals permit not specifying the argument list when it is empty.
Both proposals permit specifying (void) as the argument list
when it is empty.
Only C++ permits specifying () as the argument list
when it is empty.
Recommendation:
No change.
The lack of support for () in C
to specify an empty parameter list
is consistent with the rest of the language.
Programmers writing common code
have a common syntax in the alternative forms.
C++ specifies the return type following the parameter list
with '->'type.
N1451 section 8 is unclear on the proposed syntax.
However, its examples indicate that
it is intended to precede the parameter list.
It remains unclear how to specify pointer return types.
Other documents say the intent was syntax
is similar to an abstract declarator for pointer to function.
Recommendation: Fully specify the syntax, preferably in a manner compatible with C++.
Both C++ and N1451 will infer the return type from a lambda body consisting of a single statement that is a return statement. Both C++ and N1451 define a void return type for a lambda body that has no return statements, or that have all of their return statements without expressions. C++ and N1451 differ when the body consists of something else, i.e. a non-return statement and a return statement with an expression or both a return statement without an expression and a return statement with an expression. In C++, such lambda expressions always have type void and the return statement with an expression is ill-formed. In N1451, the return type is inferred from the return statements. Unfortunately, N1451 fails to specify the semantics when two return statements have different expression types, or when the lambda expression executes none of the return statements. The C++ committee chose not to address such semantics in C++0x by implicitly defining them as ill-formed. Because all lambda expression with "complicated" return type inference are ill-formed, a post-C++0x language could make such expressions well-formed without altering the semantics of C++0x programs.
Recommendation: There are three exclusive recommendations, in order from most preferred to least preferred.
Adopt the approach of C++. Infer a non-void return type only for lambda-expression bodies of a single statement that is a return statement.
If a lambda-expression body has a return statement with an expression, require that all return statements have expressions and that all those expressions have identical type and that the compound statement comprising the body end with a return statement. Such a definition is least likely to cause any incompatiblity with C++. Note, however, that I have not verified that it will not cause an incompatibility.
Fully specify the semantics. This will entail risk of incompatibility with C++.
In both C++ and N1451, lambda-expression bodies are not in the same statement label space as the enclosing function. That is, one can only leave the lambda via a return.
The execution of a lambda expression yields a closure object. That object captures the variables it references from outer scopes. The detailed semantics of variable capture are crucial to the nature and use of lambda expressions.
In both C++ and N1451, static duration variables are not captured. They are always accessed normally.
In N1451, the use in a lambda expression of a regular variable defined outside of the lambda expression will implicitly capture that variable as a const value. That is,
int v = 3; ... ^{ v = 4; } ...
is ill-formed
because within the lambda expression, v is const.
C++ provides a similar facility when programmers specify a default value capture. The equivalent C++ code is:
int v = 3; ... [=]{ v = 4; } ...
where the '=' specifies default value capture.
This code also has a const error.
C++ also provides for specifing that value captures are non-const by specifying that the closure object is mutable.
int v = 3; ... [=]() mutable { v = 4; } ...
Recommendation: No change unless the C committee desires mutable value captures. However, if it does desire mutable value captures, it should use the same syntax.
In C++, taking the address of a value-captured variable will yield the address of the location for the captured value, not the original variable.
int v = 3; int vp = &v; ... [=]() { assert( vp != &v ); } ...
N1451 does not prohibit taking the address of variables captured by value. However, N1451 is unclear on whether or not the C semantics are the same as the C++ semantics. The implementation description in N1457 indicates that the semantics are the same.
Recommendation: Clarify that the address of a value capture variable is that of the copied value, not the original variable.
In N1451, the use in a lambda expression
of a closure-storage-duration (__block) variable
defined outside of the lambda expression
will implicitly capture a reference to that variable.
That is,
__block int v = 3; ... ^{ v = 4; } ...
is well-formed.
In C++, the closest equivalent code is:
int v = 3; ... [&]{ v = 4; } ...
where the '&' specifies the reference capture.
However, there are significant differences in semantics.
In C++, a closure object containing a reference to its containing scope
may not be invoked
after the block statement containing v has exited.
That is, the lifetime of the captured v
is exactly the lifetime of the original v.
In contrast, in N1451,
the lifetime of v may be extended
by the explicit use of a Block_copy
operation on a closure object refering to v.
While the detailed semantics
of Block_copy and Block_release
in section 10 of N1451 are unclear,
supporting papers
indicate that the backing store for the closure
is copied at most once,
when necessary to move it out of automatic storage into heap storage.
An implication is that Block_copy and Block_release
are primarily reference count operations.
C++ programs can work around the lifetime limitation,
and match the effective semantics of closure storage duration
by defining local shared_ptr variables to heap storage
rather than defining simple local variable.
However, the syntax is awkward
and clearly slower than the N1451 proposal.
Furthermore,
the shared_ptr facility
seems beyond the scope of C,
making the workaround inapplicable to C
without significant additional standards work.
In C++, there is only one memory location for v.
In contrast, in N1451,
there are potentially two memory locations,
one on the stack and one in free store.
This choice has several consequences.
First, one cannot take the address of a closure-storage-duration variable. Code that might otherwise wish to pass the address of a variable to another function cannot, but instead must allocate free store, copy the block variable to the free store, and then pass the address of the free store to the other function. This proceedure seems clumsy given that C passes variables by reference via explicitly taking their address.
Second, one cannot have a closure-storage-duration array variable because the array name immediately decays to a pointer. This restriction is significant because one would very much like to capture arrays by reference. The workaround in N1451 is to explicitly create a separate variable to hold the reference. However, there seems to be no restriction on arrays within structs, which yields all the same problems.
int x[3]; int xp = x; ... [&]{ xp[1] = 4; } ...
One consequence of the multiple locations for a closure is that at some point closures switch from one location to another. This switch is unprotected, which means that closures cannot be executed concurrently. One of the design goals of C++ lambda was to enable concurrent execution.
Recommendation: Permit concurrent execution of closures.
In N1451,
the __block variables have read/write sharing
between multiple 'copies' of a closure,
even when those closures persist
beyond the lifetime of the function that created the closure.
In C++, the only read/write sharing of capture variables
is those within the original function scope,
and hence will not be available after the function terminates.
One principle of C++ lambda design was that one should be able to relatively easily replace a control statement with a call to a function taking a closure. For example, given the function,
double stuff( int n, const double[][4] a, const double[][4] b,
double[][4] c, double d )
{
double r[4] = { 0.0, 0.0, 0.0, 0.0 };
double s = 0.0;
for ( int i = 0; i < n; i++ ) {
for ( int j = 0; j < 4; j++ ) {
double t = a[i][j] + d*b[i][j];
c[i][j] = t;
r[j] += t;
s += t;
}
}
return s + r[0]*r[1]*r[2]*r[3];
}
one should be able to rewrite the for statements into calls to a for_range function. This rewrite is straightforward in C++, as the contents of the body need not change at all.
double stuff( int n, const double[][4] a, const double[][4] b,
double[][4] c, double d )
{
double r[4] = { 0.0, 0.0, 0.0, 0.0 };
double s = 0.0;
for_range( 0, n, [&]( int i ){
for_range( 0, 4, [&]( int j ){
double t = a[i][j] + d*b[i][j];
c[i][j] = t;
r[j] += t;
s += t;
} );
} );
return s + r[0]*r[1]*r[2]*r[3];
}
In contrast, the rewrite in N1451 is not as straightforward.
The aspects that are not straightforward
are marked as inserted below.
Note in particular the change in variable name
from r to rp.
double stuff( int n, const double[][4] a, const double[][4] b,
double[][4] c, double d )
{
double r[4] = { 0.0, 0.0, 0.0, 0.0 };
double *rp = r;
__block double s = 0.0;
for_range( 0, n, ^( int i ){
for_range( 0, 4, ^( int j ){
double t = a[i][j] + d*b[i][j];
c[i][j] = t;
rp[j] += t;
s += t;
} );
} );
return s + r[0]*r[1]*r[2]*r[3];
}
This last example brings up a question.
Does the inner lambda allocate a new memory location for s
distinct from the location allocated for the inner block?
N1451 is silent on the issue,
but the implementation model suggests that it is a new location.
In which case,
the code must replace the __block s
with yet another temporary pointer.
Recommendation: Define the semantics of nested lambda expressions.
In C++, a reference capture implies a pointer into the frame of the enclosing function, or into the frame of an enclosing closure should the reference capture be within a nested lambda. In N1451, the reference is not into the frame, but is to a separately allocated area. In C++, the multiple references can be optimized into a single frame pointer. In N1451, the same effect is achieved with a "block pointer".
The pointer replacement workaround and address restrictions suggest that closure-storage-duration variables are ill-suited to the C language. Thier semantics are best matched to languages in which variables are references, like Smalltalk. In contrast, in C variables are objects. So, the C committee should carefully consider the semantics it chooses for reference captures.
In N1451, programmers obtain mixed capture by specially declaring variables they wish to capture by reference and letting the others be capture by value by default.
__block int v = 3; int w = 4; ... ^{ v = w+1; } ...
In C++, programmers achieve the same effect by declaring references in the lambda expression.
int v = 3; int w = 4; ... [=,&v]{ v = w+1; } ...
C++ requires redundant specification of reference captures when there are multiple lambda expressions,
int v = 3; int w = 4; ... [=,&v]{ v = w+1; } ... ... [=,&v]{ v = w-1; } ...
but also enables capturing a single variable differently in multiple lambdas.
int v = 3; int w = 4; ... [=,&v]{ v = w+1; } ... ... [=,&w]{ w = v-1; } ...
Lambda expressions are not terribly useful unless their closure objects can be passed as arguments to functions.
In N1451,
passing closures is achieved
via a new syntax for specifying closure object types.
It follows function-pointer syntax
but with '^'
instead of '*'.
int func( int (^closure)(int) ) { return closure(); }
In constrast, C++ makes use of a the standard library's generic template class for 'callable' objects.
int func( function<int(int)> closure ) { return closure(); }
This generic function
has considerable generality,
more than is needed for closure objects.
It was chosen because it suited the need
and was already in use.
Both of these specifications could potentially be available in both languages.
A parameter of closure type based on C++ expression syntax,
int func( [](int)->int closure ) { return closure; }
or
int func( []closure(int)->int ) { return closure; }
is also possible, though not yet verified. However, this syntax would be slightly misleading in that the empty lambda-capture in the parameter declaration should not require an empty lambda-capture in expressions passed to that function.
Recommendation:
If the C committee does not adopt the C++ function syntax
for parameters of closure type,
it should choose a syntax that C++ can adopt.
It appears that syntax could be either the N1451 proposal
or, to a lesser extent, a syntax based on C++ lambda expressions.
C++ defines a lambda expression with an empty capture to convert to a function pointer. This facility enables programmers to use lambda expressions with existing function-pointer interfaces. That is, in the example in N1370 of a block qsort,
qsort_b(array, nItems, size, ^int (void *item1, void *item2) { ... });
C++ can call the existing qsort function:
qsort(array, nItems, size, [](void *item1, void *item2) { ... });
Recommendation: Provide a facility for using limited lambda expressions as arguments to function-pointer parameters.
The existing C++ facility has no means to specify that the function pointer so obtained is to an extern "C" function.
Recommendation: C++ should add a syntax to specify that a lambda expression converts to an extern "C" function pointer.
The C proposal N1451 provides a new syntax for lambda expressions. While details of the proposal are unclear, it is clear that there are both significant commonalities and significant differences. The syntax is in many places a shallow inconsistency. More deeply, the model of reference capture seems inherently incompatible. The N1451 model seems more appropriate to Smalltalk, from whence it originated, than to C/C++. If the C commitee chooses to modify the proposal to be more inline with C++, then syntactic changes to both C and C++ would provide considerable value to working programmers, who often fail to appreciate any differences in approach.