Comparing Lambda in
C Proposal N1451 and C++ FCD N3092

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

Introduction

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.

Terminology

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++.

lambda expression

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.

closure object

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.

variable capture

When execution of a lambda expression produces a closure, it will capture variables it references from outside the scope of the lambda expression.

closure storage duration

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.

Lambda Expressions

Both facilities provide similar, but incompatible, syntax for lambda expressions.

Primary versus Postfix

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.

Indicator

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.

Empty Closure Parameter Lists

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.

Return Type Specification

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++.

Return Type Inference

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.

  1. 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.

  2. 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.

  3. Fully specify the semantics. This will entail risk of incompatibility with C++.

Label Scope

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.

Capture Semantics

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.

Capture by Value

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.

Mutable Closures

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.

Value Capture Address

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.

Capture by Reference

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.

Capture Lifetime

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.

Multiple Locations

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; } ...

Concurrency

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.

Capture Sharing

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.

Lambda Substitutability

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];
}

Nested Capture

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.

Frame Pointer

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".

Recommendations

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.

Mixed Capture

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; } ...

Passing Closure Objects

Lambda expressions are not terribly useful unless their closure objects can be passed as arguments to functions.

Parameters of Closure Type

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.

Closures as Function Pointer

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.

Summary

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.