The concept of `Nil` in C++

Question

You remember from your undergrad lectures in algorithms that it's very handy to have a concept of Nil, which anything can be assigned to or compared with. (By the way I never did an undergrad in computer science.) In Python we can use None; in Scala there is Nothing (which is a subobject of everything if I'm understanding it correctly). But my question is, how can we have Nil in C++? Below are my thoughts.

We could define a singleton object using the Singleton Design Pattern, but my current impression is that most of you would wince at the very thought of that.

Or we could define a global or a static.

My problem is that in either of these cases, I can't think of a way of being able to assign any variable of any type to Nil, or being able to compare any object of any type with Nil. Python's None is useful because Python is dynamically typed; Scala's Nothing (not to be confused with Scala Nil, which means empty list) solves this elegantly because Nothing is a subobject of everything. So is there an elegant way of having Nil in C++?

Answer 1

No, there is no such thing as a universal nil value in C++. Verbatim, C++ types are unrelated and do not share common values.

You can achieve some form of shareable values by using inheritance, but you must do so explicitly, and it can only be done for user-defined types.

Answer 2

There are two related concepts what you describe as Nil: the unit type and the option type.

Unit Type

This is what NoneType is in Python and nullptr_t is in C++, it's just a special type that has a single value that conveys this specific behavior. Since Python is dynamically typed, any object can be compared against None but in C++ we can only do this for pointers:

void foo(T* obj) {
    if (obj == nullptr) {
        // Nil
    }
}

This is semantically identical to python's:

def foo(obj):
    if foo is None:
        # Nil

Option Type

Python does not have (or need) such a feature, but all the ML family do. This is implementable in C++ via boost::optional. This is a type-safe encapsulation of the idea that a particular object can maybe have a value, or not. This idea is more expressive in the functional family than it is in C++ though:

def foo(obj: Option[T]) = obj match {
    case None => // "Nil" case
    case Some(v) => // Actual value case
}

Although easy enough to understand in C++ too, once you see it:

void foo(boost::optional<T> const& obj) {
    if (obj) {
        T const& value = *obj;
        // etc.
    }
    else {
        // Nil
    }
}

The advantage here is that the option type is a value type, and you can easily express a "value" of nothing (e.g. your optional<int*> can store nullptr as a value, as separate from "Nil"). Also this can work with any type, not just pointers - it's just that you have to pay for the added functionality. An optional<T> will be larger than a T and be more expensive to use (although only by a little, although that little could matter a lot).

A C++ Nil

We can combine those ideas together to actually make a Nil in C++, at least one that works with pointers and optionals.

struct Nil_t { };
constexpr Nil_t Nil;

// for pointers
template <typename T>
bool operator==(const T* t, Nil_t ) { return t == nullptr; }

template <typename T>
bool operator==(Nil_t, const T* t ) { return t == nullptr; }

// for optionals, rhs omitted for brevity
template <typename T>
bool operator==(const boost::optional<T>& t, Nil_t ) { return !t; }

(Note that we can even generalize this to anything that implements operator!

template <typename T>
bool operator==(const T& t, Nil_t ) { return !t; }

, but it would be better to limit ourselves to the clear-cut cases and I like the explicitness that pointers and optionals give you)

Thus:

int* i = 0;
std::cout << (i == Nil); // true
i = new int(42);
std::cout << (i == Nil); // false

Answer 3

C++ follows the principle that you don't pay for what you don't use. For example, if you want a 32-bit integer to store the full range of 32-bit values and an additional flag about whether it is Nil, this will take more than 32-bits of storage. Certainly you can create clever classes to represent this behaviour, but it's not available "out of the box".