Storage Tutorial

CFL has a set of functions for modifying storage. Some are intended for containers (prvalue, glvalue and noxvalue), others for function arguments (move and copy). Then there are functions to modify functions themselves (prfn and glfn). The names refer to the C++ expression value categories defined by the language in section [basic.lval].

Default Storage

C++ is infamous for its manual memory management. Yet there is an underlying simple automatic management called Scope-based Resource Management (SBRM). It is a special case of RAII¹ using only automatic variables and temporaries. Automatic variables are created in the stack frame at their place of definition, and destroyed when the program flow reaches the end of the enclosing lexical scope, in the reverse order of creation. In its appearance to the user, it is similar to that of scripted languages.

Assuming only automatic variables and temporaries, a function can safely call by reference instead of by value - both for variable and temporary value arguments. The lifetime of a temporary is extended until the end of the full expression, which includes evaluating and returning from the function.

Containers on the other hand, which store values, must store temporaries by value. Previously defined automatic variables can safely be stored by reference, as the container is guaranteed to expire before any such value referenced inside.

This is the default in CFL: functions pass all arguments by reference, and containers store only temporaries by value and all other arguments by reference. Assuming SBRM, this is the strategy of least copies while ensuring correct value lifetime.

There are cases when this strategy is not optimal. Consider a temporary container holding a temporary value. At its point of definition, the container store the temporary by value, unknowingly the container itself is also a temporary. However, the caller does know it would be enough to store the value by reference in the container, saving one copy, as both the container and its inner value are guaranteed to last until the end of the expression.

This storage strategy also applies to bound values in partial application of functions. CFL captures temporaries by value and variables by reference. While consistent with the implied storage of SBRM, it differs from the default capture by value in std::bind and lambda expressions.

The rationale for the choice of default storage in CFL is primarily to extend SBRM into container elements without altering its storage rules. Another reason is optimizing for large data sets with a least copies strategy.

Expression Value Categories

Every expression in a C++ program belongs to one of the categories specified by the language in section [basic.lval].

Using a value defined in a previous expression is an lvalue. A temporary is a prvalue. std::move yields an xvalue, and std::forward a glvalue. Not included in this graph is the cv qualification of a value, its restrictions regarding mutability and shared write access.

The required storage for a value can be deduced from its expression category: lvalues are stored by reference and rvalues by value. The cv qualification of the rvalue decides whether it may be move constructed (non-const) or must be copy constructed (const). Constant rvalue references typically occur in collective operations when a temporary value argument is accessed multiple times.

Container Elements

In CFL, the value category and cv qualification of a container is transferred accessing its inner value - similar to how cv qualification and references are transferred accessing class members, as prescribed by the language specification.

struct A { int m; } const a {0};

typedef decltype ((a.m))             T; // int const &
typedef decltype ((std::move (a).m)) U; // int const &&
typedef decltype ((A {0}.m))         V; // int

However, CFL does not transform member references to lvalue references, as described in section [expr.ref] paragraph 4. Container inner rvalue references are returned as rvalue references in CFL, not as lvalue references. Although an undesired deviation from the language rules, promoting the appeared life-time of the referenced value from expiring to non-expiring was considered worse.

Modify Container Storage

The storage for the elements of a container may be modified using functions prvalue, glvalue or noxvalue. As the name suggests, prvalue converts all elements of a container to prvalues. Consider the container tuple_c (similar to std::tuple) containing a reference to a value:

int i {0};

tuple_c <char, int &> u ('a', i);

auto v = prvalue (u); // tuple_c <char, int>

Whether a conversion to pure prvalues is necessary depends on the situation, and it is the user’s responsibility to ensure no dangling references are left inside a container. Now, the default SBRM storage of CFL guarantees references are not dangling, but the fact CFL captures by reference requires some caution by the user. Consider a local variable captured by reference but with the intention to be returned to an outer scope:

auto f ()
{
    int i = rand ();
    auto g = plus (1__, i); // closure_c <..., int &>
    return prvalue (g);     // closure_c <..., int  >
}

Here g would contain a dangling reference to local variable i, if returned from f unmodified.

noxvalue refers to “no xvalue”, and corresponds to the default storage in CFL, transforming all xvalue references inside a container to prvalues. References to lvalues are left untouched, as well as prvalues.

char c {'a'};
int i {0};

tuple_c <char &, int &&> u (c, move (i));

auto v = noxvalue (u); // tuple_c <char &, int>

An argument container like u would normally be the result of a previous manipulation of storage.

Finally, glvalue just forwards a container, leaving its inner values untouched.

Modify Function Arguments

In CFL, function arguments are always passed by reference, and almost always as forwarding references². Whether an argument eventually is copied or not, is therefore not explicitly expressed in the function signature, but left to its implementation.

Similar to std::move, the CFL functions move and copy modifying argument storage, do not actually create any new values, but rather indicate to the recipient if the argument may expire or not. And, if an expiring value needs to be retained after the full expression has ended, whether it can be move constructed or must be copy constructed. In practice, move just casts a value to an rvalue reference, and copy to a const rvalue reference. Note, this is a shallow operation, whereas prvalue and noxvalue descend into container elements.

The function tuple (similar, but not equivalent to std::make_tuple), produces a container of type tuple_c.

int u {0};

tuple ('a', u);        // tuple_c <char, int &>
tuple ('a', move (u)); // tuple_c <char, int>

First the default storage is used, saving the prvalue 'a' by value and the lvalue reference u by reference. Then the storage for u is changed using move, storing by value instead.

Modify Functions

The storage for individual arguments can be modified using move and copy as above, or for the function itself using prfn and glfn.

int u {0};

prfn (tuple) ('a', u); // tuple_c <char, int>
glfn (tuple) ('a', u); // tuple_c <char &&, int &>

prfn (tuple) corresponds to std::make_tuple and glfn (tuple) to std::forward_as_tuple. Note how prfn and glfn acts on the function, not the arguments. Regular functions and lambda expressions can not be modified with prfn and glfn, but most CFL functions can. In particular, the storage method for closures may be altered:

      bind  (tuple, 'a', u); // closure_c <tuple &, char   , int &>
prfn (bind) (tuple, 'a', u); // closure_c <tuple  , char   , int  >
glfn (bind) (tuple, 'a', u); // closure_c <tuple &, char &&, int &>

The first example uses the default storage in CFL, the second stores by value and the third by reference.

The storage for the shorthand form for partial function application, as supported by most CFL functions, may be modified similarly, with an important difference regarding the storage for the function itself:

      tuple  (1__, u); // closure_c <tuple &, 1__   , int & >
prfn (tuple) (1__, u); // closure_c <tuple &, 1__   , int   >
glfn (tuple) (1__, 0); // closure_c <tuple &, 1__ &&, int &&>

In the second case, tuple is stored by reference in the closure, not by value. In practice, this affects only stateful functions serving as first argument in a shorthand bind expression. Internally the closure seeks to use the empty base optimization and silently converts references to empty objects to prvalues. So both tuple and 1__ are actually always stored as (empty) prvalues. For clarity, note how 0 and not u is bound in the third case.

As well behaved functions, also closures themselves respond to such manipulation, then affecting the free variables. To change storage for already captured values, use prvalue and noxvalue as above. Note how prfn and glfn below acts on the closure, instead of the function tuple as above.

auto f = prfn (tuple (1__, u)); // closure <prfn (tuple), 1__, int &>
auto g = glfn (tuple (1__, u)); // closure <glfn (tuple), 1__, int &>

f (1); // tuple_c <int   , int  >
g (1); // tuple_c <int &&, int &>

When invoked, f now stores the previously bound lvalue reference to u by value in the returned tuple container. Conversely, when invoked, g stores the provided temporary argument int {1} by reference.

Resource Acquisition Is Initialization ↩
Roughly, pass by reference and keep value category and cv qualification.↩