CPython's NotImplemented Implementation in C

Python’s NotImplemented is not an exception and not a function result that means “I gave up.” It is a real singleton object of type NotImplementedType, returned from operator implementations to tell the interpreter: “this operand combination is not supported by me – try the other operand, or fall back.” In CPython that is implemented in Objects/object.c as a single static PyObject struct, _Py_NotImplementedStruct, whose type is _PyNotImplemented_Type. This article traces that implementation through the 3.15 source.

The type object

NotImplementedType is a plain, non-subclassable-in-practice type whose slot table is almost entirely zero. The few slots that are set define its identity and its role as a sentinel:

c
// Objects/object.c
PyTypeObject _PyNotImplemented_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "NotImplementedType",
    0,                          /* tp_basicsize: sizeof(PyObject) */
    0,                          /* tp_itemsize */
    notimplemented_dealloc,     /* tp_dealloc */ /*never called*/
    0,                          /* tp_vectorcall_offset */
    0,                          /* tp_getattr */
    0,                          /* tp_setattr */
    0,                          /* tp_as_async */
    NotImplemented_repr,        /* tp_repr */
    &notimplemented_as_number,  /* tp_as_number */
    0,                          /* tp_as_sequence */
    0,                          /* tp_as_mapping */
    0,                          /* tp_hash */
    0,                          /* tp_call */
    0,                          /* tp_str */
    ...
    Py_TPFLAGS_DEFAULT,         /* tp_flags */
    notimplemented_doc,         /* tp_doc */
    ...
    0,                          /* tp_base */   /* filled in by PyType_Ready -> object */
    ...
    notimplemented_methods,     /* tp_methods */
    ...
    0,                          /* tp_init */
    0,                          /* tp_alloc */
    notimplemented_new,         /* tp_new */
};

tp_basicsize is 0, which PyType_Ready turns into sizeof(PyObject): the singleton carries no payload at all, it is just a head. tp_base is 0, so PyType_Ready makes object the base, which is why NotImplemented inherits the default identity equality and identity hash from object.

The type is exported to Python as types.NotImplementedType:

c
// Modules/_typesmodule.c
EXPORT_STATIC_TYPE("NotImplementedType", _PyNotImplemented_Type);

The singleton

There is exactly one instance, statically allocated at compile time:

c
// Objects/object.c
PyObject _Py_NotImplementedStruct = _PyObject_HEAD_INIT(&_PyNotImplemented_Type);

_PyObject_HEAD_INIT initializes the refcount to an immortal value, sets the static-allocation flag, and points ob_type at _PyNotImplemented_Type. No runtime allocation ever happens.

The public macro resolves to that struct (or, in the limited API 3.13+, to a borrowed reference from the interpreter’s constant table):

c
// Include/object.h
PyAPI_DATA(PyObject) _Py_NotImplementedStruct; /* Don't use this directly */

#if defined(Py_LIMITED_API) && Py_LIMITED_API+0 >= 0x030D0000
#  define Py_NotImplemented Py_GetConstantBorrowed(Py_CONSTANT_NOT_IMPLEMENTED)
#else
#  define Py_NotImplemented (&_Py_NotImplementedStruct)
#endif

Py_RETURN_NOTIMPLEMENTED is the convenience macro for returning it from a C function. In the limited API older than 3.12 it returns a new reference; in 3.12+ it returns the immortal singleton directly:

c
// Include/object.h
#if defined(Py_LIMITED_API) && Py_LIMITED_API+0 < 0x030c0000
#  define Py_RETURN_NOTIMPLEMENTED return Py_NewRef(Py_NotImplemented)
#else
#  define Py_RETURN_NOTIMPLEMENTED return Py_NotImplemented
#endif

Because the object is in the interpreter’s constant table, it is immortal (PEP 683) like None, True, and False:

c
// Objects/object.c
static PyObject* constants[] = {
    &_Py_NoneStruct,                   // Py_CONSTANT_NONE
    (PyObject*)(&_Py_FalseStruct),     // Py_CONSTANT_FALSE
    (PyObject*)(&_Py_TrueStruct),       // Py_CONSTANT_TRUE
    &_Py_EllipsisObject,               // Py_CONSTANT_ELLIPSIS
    &_Py_NotImplementedStruct,         // Py_CONSTANT_NOT_IMPLEMENTED
    ...
};

The dealloc guard

The singleton’s refcount should never reach zero, but CPython defends against accidental decref-to-zero by re-immortalizing instead of freeing:

c
// Objects/object.c
static void
notimplemented_dealloc(PyObject *notimplemented)
{
    /* This should never get called, but we also don't want to SEGV if
     * we accidentally decref NotImplemented out of existence. Instead,
     * since NotImplemented is an immortal object, re-set the reference count. */
    _Py_SetImmortal(notimplemented);
}

This mirrors bool_dealloc and the None/Ellipsis guards: a statically allocated immortal object has no real deallocator.

Boolean context is an error

NotImplemented is deliberately unusable as a truth value. Its tp_as_number only fills nb_bool, and that slot raises TypeError:

c
// Objects/object.c
static int
notimplemented_bool(PyObject *v)
{
    PyErr_SetString(PyExc_TypeError,
                    "NotImplemented should not be used in a boolean context");
    return -1;
}

static PyNumberMethods notimplemented_as_number = {
    .nb_bool = notimplemented_bool,
};

So if NotImplemented:, not NotImplemented, and bool(NotImplemented) all raise TypeError: NotImplemented should not be used in a boolean context. This prevents a common bug where a binary operator returns NotImplemented and the caller forgets to check for it, treating it as a truthy result.

repr and pickling

repr(NotImplemented) is the string "NotImplemented" (a fresh str, not a cached one), and __reduce__ returns the same string so unpickling resolves to the singleton by name:

c
// Objects/object.c
static PyObject *
NotImplemented_repr(PyObject *op)
{
    return PyUnicode_FromString("NotImplemented");
}

static PyObject *
NotImplemented_reduce(PyObject *op, PyObject *Py_UNUSED(ignored))
{
    return PyUnicode_FromString("NotImplemented");
}

static PyMethodDef notimplemented_methods[] = {
    {"__reduce__", NotImplemented_reduce, METH_NOARGS, NULL},
    {NULL, NULL}
};

Construction: no arguments

NotImplementedType() returns the singleton; passing arguments is an error:

c
// Objects/object.c
static PyObject *
notimplemented_new(PyTypeObject *type, PyObject *args, PyObject *kwargs)
{
    if (PyTuple_GET_SIZE(args) || (kwargs && PyDict_GET_SIZE(kwargs))) {
        PyErr_SetString(PyExc_TypeError, "NotImplementedType takes no arguments");
        return NULL;
    }
    Py_RETURN_NOTIMPLEMENTED;
}

Note that type is ignored: there is no way to create a second instance, just like True/False for bool.

How binary operators consume it

The whole point of the sentinel is the protocol in Objects/abstract.c. A binary slot (e.g. nb_add) may return Py_NotImplemented to say “I don’t know how to do this.” binary_op1 then tries the reflected/other operand’s slot, and if everything fails, binary_op turns the sentinel into a TypeError:

c
// Objects/abstract.c
static PyObject *
binary_op1(PyObject *v, PyObject *w, const int op_slot ...)
{
    binaryfunc slotv = ...;   /* v's slot, if any */
    binaryfunc slotw = ...;   /* w's slot, if types differ */

    if (slotv) {
        PyObject *x;
        if (slotw && PyType_IsSubtype(Py_TYPE(w), Py_TYPE(v))) {
            x = slotw(v, w);          /* try w first when w is a subclass */
            if (x != Py_NotImplemented)
                return x;
            Py_DECREF(x);             /* can't do it */
            slotw = NULL;
        }
        x = slotv(v, w);
        if (x != Py_NotImplemented) {
            return x;
        }
        Py_DECREF(x);                 /* can't do it */
    }
    if (slotw) {
        PyObject *x = slotw(v, w);
        if (x != Py_NotImplemented) {
            return x;
        }
        Py_DECREF(x);                 /* can't do it */
    }
    Py_RETURN_NOTIMPLEMENTED;         /* nobody could do it */
}

static PyObject *
binary_op(PyObject *v, PyObject *w, const int op_slot, const char *op_name)
{
    PyObject *result = BINARY_OP1(v, w, op_slot, op_name);
    if (result == Py_NotImplemented) {
        Py_DECREF(result);
        return binop_type_error(v, w, op_name);   /* TypeError */
    }
    return result;
}

The same pattern appears in ternary_op (for pow with a modulus) and in do_richcompare for ordering/comparison operators:

c
// Objects/object.c
static PyObject *
do_richcompare(PyThreadState *tstate, PyObject *v, PyObject *w, int op)
{
    ...
    if (!Py_IS_TYPE(v, Py_TYPE(w)) &&
        PyType_IsSubtype(Py_TYPE(w), Py_TYPE(v)) &&
        (f = Py_TYPE(w)->tp_richcompare) != NULL) {
        checked_reverse_op = 1;
        res = (*f)(w, v, _Py_SwappedOp[op]);
        if (res != Py_NotImplemented)
            return res;
        Py_DECREF(res);
    }
    if ((f = Py_TYPE(v)->tp_richcompare) != NULL) {
        res = (*f)(v, w, op);
        if (res != Py_NotImplemented)
            return res;
        Py_DECREF(res);
    }
    if (!checked_reverse_op && (f = Py_TYPE(w)->tp_richcompare) != NULL) {
        res = (*f)(w, v, _Py_SwappedOp[op]);
        if (res != Py_NotImplemented)
            return res;
        Py_DECREF(res);
    }
    /* default: == / != compare by identity; ordering raises TypeError */
    ...
}

The default object_richcompare itself uses NotImplemented as its “I have nothing to say” return value, which is what lets two unrelated objects fall through to identity equality for ==/!= and to a TypeError for ordering:

c
// Objects/typeobject.c
static PyObject *
object_richcompare(PyObject *self, PyObject *other, int op)
{
    PyObject *res;
    switch (op) {
    case Py_EQ:
        res = Py_NewRef((self == other) ? Py_True : Py_NotImplemented);
        break;
    case Py_NE:
        ...
        res = Py_NewRef(Py_NotImplemented);
        break;
    default:
        res = Py_NewRef(Py_NotImplemented);
        break;
    }
    return res;
}

The slot-wrapper machinery in typeobject.c (SLOT1BINFULL, etc.) likewise compares returned values against Py_NotImplemented to decide whether to try the reflected dunder (__radd__ and friends) or the other operand.

Memory layout summary

NotImplemented is just a PyObject head: refcount, flags, and type pointer. There is no value, no digit array, no buffer:

text

_Py_NotImplementedStruct
+---------------------------+
| ob_refcnt  (immortal)     |
+---------------------------+
| ob_flags   (static)       |
+---------------------------+
| *ob_type  (&_PyNotImplemented_Type) |
+---------------------------+

The ABI records its size as 16 bytes on 64-bit builds, matching sizeof(PyObject).

Key takeaways

NotImplemented is a single immortal static PyObject, _Py_NotImplementedStruct, of type _PyNotImplemented_Type (NotImplementedType).
The type is a subclass of object with almost no slots: only tp_repr, tp_as_number (whose nb_bool raises TypeError), tp_methods (__reduce__), and tp_new (which takes no arguments and returns the singleton).
Py_NotImplemented resolves to the struct directly in the full API, or to a borrowed reference from the constant table (Py_CONSTANT_NOT_IMPLEMENTED, index 4) in the limited API 3.13+.
The dealloc guard re-immortalizes instead of freeing.
Binary/ternary operators and rich comparisons treat a returned Py_NotImplemented as “try the other operand”; if nobody can handle it, the sentinel is converted into a TypeError.
bool(NotImplemented) and if NotImplemented: raise TypeError by construction, catching forgotten sentinel checks.