Thoughts on Scott’s “Red Code / Green Code” Talk

Scott Meyers recently gave an interesting talk at NWCPP. Thanks to Kevin Frei’s recording skills and hardware, you can watch the video here.

Scott’s topic was "Red Code / Green Code: Generalizing const." Here’s the abstract:

C++ compilers allow non-const code to call const code, but going the other way requires a cast.  In this talk, Scott describes an approach he’s been pursuing to generalize this notion to arbitrary criteria.  For example, thread-safe code should only call other thread-safe code (unless you explicitly permit it on a per-call basis).  Ditto for exception-safe code, code not "contaminated" by some open source license, or any other constraint you choose.  The approach is based on template metaprogramming (TMP), and the implementation uses the Boost metaprogramming library (Boost.MPL), so constraint violations are, wherever possible, detected during compilation.

(Nit: I think the "const" analogy is a slight red herring. See the Coda at the bottom of this post for a brief discussion.)

Motivation and summary

The motivation is that it might be nice to be able to define categories of constraints on code, and have a convention to enforce that constrained code can’t implicitly call unconstrained code. Scott gives the example that you might want to prevent LGPL’d code from implicitly calling non-LGPL’d code if that would make the non-LGPL’d code subject to LPGL virally. Similarly, you might want to prevent reviewed code from implicitly calling unreviewed code; and so on. Note that these constraints overlap; you can have any combination of LGPL’d/non-LGPL’d and reviewed/unreviewed code.

The basic technique Scott describes is to define a tag type, which is similar to the technique used in standard C++ iostreams to mark iterator categories. You just define some empty types (all we’re doing is generating names):

struct ThreadSafe {};
struct LGPLed {};
struct Reviewed {};
// etc.

Then you arrange for each function to declare its constraints at compile time, for example to say that "my function is LGPL’d" or "my function is Reviewed" or any combination thereof. Scott showed how to conveniently use MPL compile-time collections to write a group of constraints. He provides this general helper template:

template<typename Constraints>
struct CallConstraints {
  …
}

Then the callers and callees all traffick in CallConstraints<mpl::vector<ExceptionSafe,Reviewed>>, CallConstraints<mpl::vector<ThreadSafe, LGPLed>>, and so on. Scott also provides ways to opt out or deliberately loosen constraints, via helpers IgnoreConstraints and eraseVal<MyConstraints, SomeConstraint>. He also provides an includes metafunction that you can use to see if one set of constraints is compatible with another set.

But where do you put these constraints, and how do you pass and check them? Scott presented several ways (see the talk for details), but they all had serious drawbacks. Here’s a quick summary of the primary alternative he presented: The idea is to make each participating function that wants to declare constraints a template, and write its constraints inside the function. For example:

template<typename CallerConstraints>
void f( Params params ) {
  typedef mpl::vector<ExceptionSafe> MyConstraints;
  BOOST_MPL_ASSERT(( includes<MyConstraints, CallerConstraints> ) );
  …
}

That’s the basic pattern. When you call another constrained function, you pass along your constraint type, and optionally explicitly relax constraints if you want to loosen them. For example:

template<typename CallerConstraints>
void g() {
  typedef mpl::vector<ExceptionSafe, Reviewed> MyConstraints;
  BOOST_MPL_ASSERT(( includes<MyConstraints, CallerConstraints> ));
  …
  // try to call the other function
  f<MyConstraints>( params );  // error, trying to call unreviewed code from reviewed code
  f<eraseVal<MyConstraints,Reviewed>>( params ); // ok, ignore Reviewed constraint
  f<IgnoreConstraints>( params ); // ok, explicitly ignore constraints entirely
}

This has a number of drawbacks:

  • Virtual functions vs. compile-time checking: This doesn’t (directly) work for virtual functions, because templates can’t be virtual. See Scott’s talk for details about ways to trade that off against a different design, namely the NVI pattern, or a different drawback, namely run-time checking.
  • Template explosion: Every participating function is required to become a template (or to add a new template parameter). That’s more than merely inconvenient; for one thing, it means we have to put every function in a header file (or else wrap it with a template that does the constraints checking and then passes through to the normal function, which is tedious duplication). The other serious problem is that the function template is now going to have to be instantiated once for each unique combination of caller constraints, including even constraints that are added in the future and have nothing to do with this function, even though each instantiation generates identical code.
  • Separate checking: The constraints aren’t part of the type of the function, and so we have to compile the body of the function to determine whether the constraints are compatible. In short, we’re not leveraging the type system as much as we might wish to do.

Another minor drawback is that each user has to write the static assertions himself.

My humble contribution (sketch)

I enjoyed Scott’s motivation, and during his talk I thought of a simpler way to pass and check these constraints. I chatted with him about it afterwards, and he’s added it to his talk notes (which should go live at the above talk link over the next few days).

Here’s the idea that occurred to me: What if we make the constraints part of the function signature by passing them as an additional normal parameter, and do the check on the conversion from Constraints<Caller> to Constraints<Callee>? Here’s a sketch of how you’d use it:

void f( Params params, Constraints<ExceptionSafe> myConstraints ) {
  …
}void g( Constraints<ExceptionSafe, Reviewed> myConstraints ) {
  …
  // try to call the other function
  f( params, myConstraints );  // error, trying to call unreviewed code from reviewed code
  f( params, myConstraints::erase<Reviewed>() ); // ok, ignore Reviewed constraint
  f( params, IgnoreConstraints ); // ok, explicitly ignore constraints entirely
}

This has none of the drawbacks of the other alternatives:

  • It incurs zero or near-zero space and time overhead: No extra template expansions, no run-time checking, and possibly even no space overhead because a constraint’s information payload is all in its compile-time type (a constraint object itself is empty).
  • It doesn’t require users to make all their functions templates: Just add a normal parameter.
  • It works naturally with virtual functions: A derived override must have constraints compatible with
    the base function, and that follows naturally in that it must match the signature, now including the constraints, of the base. (Future-proofing note: If C++ is ever extended to allow contravariant parameters on virtual functions, that would dovetail perfectly with this technique because derived functions can be less constrained than base functions).
  • It supports separate compilation and separate checking, by making the constraint part of the function’s type.

We could enable the above technique by bundling up the functionality inside just one Constraints template that would look something like this (sketch only):

// This is pseudocode.
//
class IgnoreConstraints { }; // just a helper

template<C1 = Unused, C2 = Unused, … CN = Unused> // could get rid of this redundancy with C++09 variadic templates
struct Constraints {
  typedef mpl::vector<C1, C2, …, CN> CSet;

  // Use the conversion operation as our hook to perform the check.
  //
  template<typename CallerConstraints>
  Constraints( const Constraints<CallerConstraints>& ){
    BOOST_MPL_ASSERT(( includes<CSet, Constraints<CallerConstraints>::CSet> ));
  }

  // Allow the caller to explicitly ignore constraints by doing no checks
  // on the conversion from the helper type.
  //
  Constraints( const IgnoreConstraints& ) { }

  // … provide erase by duplicating Scott’s eraseVal on CSet…
};

Scott has added notes to his slides showing this approach, and intends to write a real article about this. I’ll leave it to him to write a complete implementation based on the above or some variation thereof; this is just to sketch the idea.

Thanks, Scott, for a very interesting talk!

Coda: On the "const-ness" of code

The talk description starts with:

C++ compilers allow non-const code to call const code, but going the other way requires a cast.

This reference to const-ness is intended to be a helpful analogy in the sense that a const member function can’t directly call a non-const member function of the same class. But really that’s the only situation where you could at a stretch say something like "non-const code can’t call const code." The reason this analogy doesn’t really match what the actual (good and useful!) topic of this talk and technique is that const is about data, not code.

In particular, an object can be const, but a function can’t be const. Not ever. Now, at this point someone may immediately object, "Herb, you fool! Of course a function can be const! What about…" and go on to scribble a code example like:

class X {
public:
  void f( const Y& y, int i ) const { // "const code"?
g( y, i ); // error — "can’t call non-const code from const code" ?
  }
  void g( const Y& y, int i ) { } // "non-const code"?
};

"And so clearly," said someone might triumphantly conclude, "here X::f is const code, and X::g is non-const code, right?"

Alas, no. The only difference the const makes is that the implicit this parameter has type const X* in X::f as opposed to type X* in X::g. It is true that X::f can’t call X::g without a cast, but that has nothing to do with "const-ness of code" but rather the constness of data — you can’t implicitly convert a const X* to an X*. To drive the point home, note that the above code is in virtually every way the same as if we’d written f and g as non-member friends and named the parameter explicitly:

void f( const X* this_, const Y& y, int i ) { // "const code"?
g( this_, y, i ); // error: can’t convert const X* to X*
}
void g( X* this_, const Y& y, int i ) { } // "non-const code"?

Now which function is "const" and which is "non-const"? There really is no such thing as a const function — its constness or non-constness depends (as it must) on which parameter we’re talking about:

  • Both functions "are const" with respect to their y parameter.
  • Neither function "is const" with respect to their i parameter.
  • Only f "is const" with respect to its this_ parameter.

Remember that const is always about data, not code. Const always applies to the declaration of an object of some type. A function can use const on any parameter to declare it won’t change the object you pass it in that position, but it’s still about the object, not about the code. True, for a member function you get to write const at the end if you want to, but that’s just syntactic sugar for putting it on the implicit this parameter; the fact that the const lexically gets tacked onto the function is just an artifact of the this parameter being hidden so that you can’t decorate the parameter directly.

But leaving analogies with const-ness aside, there’s real value in the idea of red code / green code which really is about distinguishing different kinds of code, whereas const is about distinguishing different views of data.

4 thoughts on “Thoughts on Scott’s “Red Code / Green Code” Talk

  1. "The motivation is that it might be nice to be able to define categories of constraints on code, and have a convention to enforce that unconstrained code can’t implicitly call constrained code."
    Isn’t this backwards?  I thought the game was to prevent constrained code (e.g., managed code) from implicitly calling unconstrained (i.e., unmanaged) code lest it be viewed as constrained in ways it isnot.  Similarly, in the case of thread-safe code.  [I’m ignoring the const example, of course.]
    I have an example in applicative programming.  If a function is regarded as pure (has no external side-effects), then that usually requires any function it is given to use to be pure as well.  (I can think of exceptions, but I think I’d want those to be allowed only in some explicit way, such as casting.  I’d never want to allow it to inject volatility into the operation of the pure procedure, though, since it effectively changes the semantics of the pure function.)  There is, however, no problem with impure function using pure ones.  
    Maybe I’ve tripped over a nomenclature ambiguity around what is meant by "constrained."
    I am not arguing against red code / green code at all.  That appears to be valuable and highly desirable.
  2. Nit:

    The implicit declaration for this in a member function of class X is X* const this or const X* const this. I agree the "red" code/"green" code stuff is quite different from "const" correctness.

    More serious stuff:

    The trouble with virtual functions actually raises a larger question: what kind of constraints are we talking about? (a) Are they constraints imposed by interfaces (read, classes with virtual functions) that the all its implementation must honor or (b) are they constraints between the caller and callee and the interface has nothing to do with. Your suggestion makes it former and Scott’s latter. But the answer appears to be "it depends". For example, (as far as I know) "LGPL" for an interface does not require its implementations LGPL’ed. So LGPL is not an interface constraint. On the other hand, thread-safety seems to be useful both as an interface-constraint or implementation constraint (if none of the callers are thread-safe, my implementation need not be. As an interface designer I cannot say if something should be thread-safe or not). Nevertheless, the idea is interesting, keep exploring.

    As an extension to Scott’s idea, it will be more useful attribute constraints to things larger than a function say a class or a bunch of classes. Usually, you design a class rather than a function in it to be thread-safe, you review implementation the entire class or decide the license terms for something much larger than a class.

    Thiru

  3. Orcmid: Yes, I mistyped that and fixed it a few minutes later, but you saw the original. The point is indeed that you don’t want constrained code to silently call into unconstrained code. The examples illustrated it in the correct direction.
  4. I think the analogy between red code / green code and constness is not as far-fetched as it might seem, specially considering the alternative rc/gc implementation you propose: your approach (which is IMHO superior to Scott’s formulations) boils down to passing permits around, much in the same way as constness is about passing const/non-const objects around. So, a const member function can be thought of as a function wih the following signature:
       void f(const X* this,Params params);
    which looks very similar to an exception-safe-constrained function:
      void f(Params params,Constraints<ExceptionSafe> myConstraints);
    So, both concepts are, in a sense, pretty much related. The one difference between rc/gc permits and constness is that permits hold no data, they are strictly syntactic constructs, while constness effectively classifies the data members of a class (and in a recursive manner) –maybe there’s some potential in investigating how rc/gc permits could be extended to apply to the data members of a class following the const model.
    Joaquín M López Muñoz
    Telefónica, Investigación y Desarrollo

Comments are closed.

In comments, use [code] [/code] for code blocks, and the same with angle brackets for code inside text paragraphs. I appreciate and try to acknowledge feedback on GotW articles; if you're suggesting an improvement for a GotW Solution post, please post under your real name (or include it in the comment text) if you would like to be acknowledged here and when the material is updated and expanded in future Exceptional C++ books.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s