An inquiry into CPL values

by Max Galkin

Christopher Strachey and CPL are sometimes mentioned in the discussions of C++ value categories, though usually just briefly and for dubious reasons: C++ value categories are defined in a specific fashion different from Strachey’s blueprints, and some even say that the analogy is downright confusing. I’ve attempted to get a better understanding of the issue, and this post summarizes my findings.

“The terms “lvalue” and “rvalue” are deep in C++’s genes. They were introduced by Christopher Strachey for CPL [Strachey,196?], the ancestor to BCPL. Dennis Ritchie used “lvalue” to describe C (e.g. see [K&R,1978]), but left out “rvalue”, considering “lvalue” and “not lvalue” sufficient. I did the same for early definitions of C++ (e.g. see [Stroustrup,1986] and [Ellis,1989]). The terms “lvalue” and “rvalue” are “all over” the draft C++ standard. Clearly, this is not terminology to mess with without serious reason and great care.” — B. Stroustroup: “New” Value Terminology

“The terminology of “lvalues” and “rvalues” is confusing because their history is confusing.  (By the way, they’re just pronounced as “L values” and “R values”, although they’re written as single words.)  These concepts originally came from C, and then were elaborated upon by C++.  To save time, I’ll skip over their history, including why they’re called “lvalues” and “rvalues”, and I’ll go directly to how they work in C++98/03.  (Okay, it’s not a big secret: “L” stands for “left” and “R” stands for “right”.  But the concepts have evolved since the names were chosen, and the names aren’t very accurate anymore.  Instead of going through the whole history lesson, you can consider the names to be arbitrary like “up quark” and “down quark”, and you won’t lose anything.)

C++03 3.10/1 says: “Every expression is either an lvalue or an rvalue.”  It’s important to remember that lvalueness versus rvalueness is a property of expressions, not of objects.

Lvalues name objects that persist beyond a single expression.  For example, obj , *ptr ,ptr[index] , and ++x are all lvalues.

Rvalues are temporaries that evaporate at the end of the full-expression in which they live (“at the semicolon”).  For example, 1729 , x + y , std::string(“meow”) , and x++ are all rvalues.” — S.T. Lavavej “Rvalue References: C++0x Features in VC10, Part 2”

But why even bother reading about CPL and its concepts?

Well, at least for 2 reasons:

  • first, naturalistic: CPL has never been completely finished, but a compiler for a small subset of it (BCPL) focused on system programming was eventually implemented, then after a couple more mutations the language turned into C and then C++, so there is a direct relation between CPL and C++ in the evolutionary sense, and it’s interesting to trace the path of the inherited characteristics and, (maybe not so) surprisingly, discover that many modern C++ features are merely the newly “re-discovered” items from the Strachey’s ideal language “wish list” from the 60’s;
  • second, pragmatic: Strachey’s concepts of R-values and L-values, in my opinion, are simpler, more fundamental and more universal than “rvalues” and “lvalues” of C++, and they uncover some important semantics underlying expression evaluation in most programming languages (C++ included). From here on I’ll use terms R-value and L-value to refer to the concepts introduced in [Strachey, 1967], and terms rvalue, lvalue, prvalue, glvalue, xvalue as described in [Stroustrup, 2010].

If you’ve ever struggled to understand the precise semantics of C++ value categories you’ll be surprised by the simplicity of Strachey’s definitions. His L-values and R-values can be explained with a single example. Imagine you have an array A and you make the most trivial assignment “A[i] = A[i]” — the left-hand side of the assignment is “literally” the same as the right-hand side of the assignment, nevertheless “A[i]” means 2 different things in these 2 occurrences: “A[i]” on the left stands for the “place” to store the value, and “A[i]” on the right stands for the “value” itself. To formalize that distinction, Strachey said that on the left-hand side of the assignment we evaluate the L-value of “A[i]” and on the right-hand side we evaluate the R-value of “A[i]”. L-value of an expression can be thought of as an address, or more universally as a “location” of the value in the “idealized storage” of the computer, and R-value is the value itself stored in that location in the storage.

This simple duality uncovers several fundamental design decisions in the language at hand:

1. The language has mutable values — in a pure functional language we wouldn’t need 2 kinds of values, as there is no “mutating” assignment and there would be really no concept of a “location” of a value, nor any way to “put” a given value into a particular “location”.

2. We choose to not explicitly differentiate the evaluation of L-values and R-values in the syntax of the assignment (we write “A[i]” on both sides and we have a mere convention about which side stands for the destination place, and which side stands for the value). Strachey hints that it “just so happened” in his contemporary languages, and seems to work for practical purposes, but in the more formal parts of his notes he switches to another notation, where L and R evaluation mode is explicit.

3. The names of the variables in our languages (and indexed array elements) refer both to the value and to the “location” of the value in the machine’s “store”, i.e. they can be evaluated both in L-mode and in R-mode.

But “value assignment” operator is not the only place where the distinction between L-values and R-values matters:

  • we may want to assign an L-value (i.e. “bind” another name to the “location” of an existing name, evaluating L-value of an expression on the “right-hand side” of the “assignment”) — Strachey introduces special assignment syntax for this in CPL (because the value assignment evaluates the R-value of the right-hand side by definition);
  • for function arguments and for context variables captured in lambdas, we want to specify whether we take them by R-value or by L-value — for the first option Strachey uses the term “pass by value”, for the second — “pass by reference”.

We can find Strachey’s L-values and R-values in C++ too, conceptually, but lvalues and rvalues defined in the Standard have different semantics, and this is a source of confusion and misunderstanding. I think it is safe to say that C++ value terminology is substantially different from what Strachey has proposed in his lectures. In C++ non-const references sort-of behave as Strachey’s references: e.g. they bind to parameter L-values in function calls. But there are const references too, which can bind to rvalues. However, semantically, even when you pass by a const reference in C++ you’re still binding to L-values: we use const references to avoid copying the value, conceptually we pass its location instead, with a promise to not change the value stored there. Temporary objects, which belong to the category of rvalues, arguably live somewhere and have a location, though at some point in C++ history language designers decided that you shouldn’t be allowed to bind a mutable reference to their location, because it is error-prone in most normal use cases (btw, you can still see this legacy C++ behavior supported in MSVC even in 2015 as a “non-standard extension” that every sane developer must turn into a warning by using warnings level 4). The irony is that for move semantics in C++11 to work you need to obtain a mutable L-value of the temporary object — the value, which language designers tried to hide from developers before to not let them accidentally change a temporary object and make a “logical mistake”. This mutable L-value of the temporary object you can now get with what they called an rvalue reference. Note that rvalue reference can bind to some generalized lvalues (called xvalues). Note that you can also still bind to the const L-value of rvalues using a const lvalue reference. Note also that a named rvalue reference is an lvalue itself (and has an L-value). Pfffff. Go figure!

“We didn’t find any real constraints on the naming to guide us, so we picked ‘x’ for the center, the unknown, the strange, the xpert only, or even x-rated.” — B. Stroustroup: “New” Value Terminology

 

To conclude, let’s look at several code examples from Strachey’s notes illustrating operations on L-values and R-values envisioned for CPL, and compare them to the C++11 syntax achieving the same effect.

Introducing a new name, with a new L-value, and initializing it with a given R-value.

let x = 3
auto x = 3;

Mutating assignment, putting a given R-value into the given L-value.

x := A[i]
x = A[i];

L-value assignment, “binding” a new name to an existing L-value.

let z ≃ A[i]
auto& z = A[i];

Capturing an R-value of a free variable (capturing “by value”).

let a = 3
let f[x] = x + a
auto a = 3;
auto f = [=](int x){ return x + a; };

Capturing an L-value of a free variable (capturing “by reference”).

let a = 3
let f[x] ≡ x + a
auto a = 3;
auto f = [&](int x){ return x + a; };

 


 

References

[Strachey et al., 1963] D.W. Barron, J.N. Buxton, D.F. Hartley, E. Nixon, and C. Strachey. “The main features of CPL” The Computer Journal 6:2:134-143 (1963)  http://www.math.bas.bg/~bantchev/place/cpl/features.pdf

[Strachey, 1967] C. Strachey “Fundamental Concepts in Programming Languages” (http://www.itu.dk/courses/BPRD/E2009/fundamental-1967.pdf)

[Lavavej, 2009] S.T. Lavavej “Rvalue References: C++0x Features in VC10, Part 2”   http://blogs.msdn.com/b/vcblog/archive/2009/02/03/rvalue-references-c-0x-features-in-vc10-part-2.aspx

[Miller, 2010] William M. Miller. A Taxonomy of Expression Value Categories. N3055. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3055.pdf

[Stroustrup, 2010] B. Stroustroup: “New” Value Terminology, http://www.stroustrup.com/terminology.pdf