Method polymorphism in C

An overdue post on polymorphism, which in C amounts to the ability to call a method on an object without knowing what the implementation is.

What is polymorphism? It’s a way of having several related types be treated as a single type, with respect to what they have in common at least. It’s most useful when there is a method that applies to objects of several types; The caller of the method often does not care about which type they’re working with, as long as it has an appropriate method implementation.

Polymorphism, in this post, is the abstraction of method implementations away from their interfaces. The implementations may be different for each type, but the interfaces are the same for all.

(Polymorphism is also applicable to the case of handling objects of various types without calling methods in them. For instance, storing objects of related types in a generic container. Implementing generic containers in C will be covered in a future post.)

Operationally, polymorphism is implemented as an algorithm that takes an object, examines its type, and determines which of a set of similar functions to call on it. C offers two fundamental mechanisms for this:

1. switch/case statements
2. function pointers

Apart from the large syntactic differences, they also differ in where the responsibility for mapping object types to method implementations is placed, and consequently on the implications of each approach for maintenance.

An example of a program where with extensive polymorphism is the PostgreSQL database engine.  SQL queries are planned as trees of nodes, each of which is a device that pulls tuples from its children (or from a source), processes them, and pushes the results to its parent.  For example, the query “SELECT COUNT(DISTINCT name) FROM person WHERE age < 10” might be planned as:

T_Agg (count)
    T_Unique (on name)
        T_SeqScan (on person, where age < 10)

There are dozens of node types; when a new method of processing data or a new optimisation is added to the engine, new node types may be added.

When executing the query, PostgreSQL will attempt to pull a tuple from the parent node.  But there are many types of node, each with a different mechanism for providing the data.  How does the engine determine which implementation to call?

Switch/case statements

As it happens, PostgreSQL uses switch-style polymorphism in many places, including query execution.  There is a function ExecProcNode like this:

TupleTableSlot* ExecProcNode (PlanState *node)
{
    TupleTableSlot *result;

    switch (nodeTag(node))
    {
        ...
        case T_SeqScanState:
            result = ExecSeqScan((SeqScanState *) node);
            break;
        case T_AggState:
            result = ExecAgg((AggState *) node);
            break;
        case T_UniqueState:
            result = ExecUnique((UniqueState *) node);
            break;
...
        default:
            elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
            break;
    }

    return result;
}

(I’ve abridged the code a bit; the original is at http://doxygen.postgresql.org/execProcnode_8c.html.)

One advantage of this is that any commonality between the calls for sets of node types can be implemented at the switch statement, instead of requiring new methods to defined for the objects.  Another minor advantage is that it is easier for the compiler to optimise — and especially line — functions when they are called directly.

The main disadvantage of switch statements that it is the caller of the method that decides which implementation to call.  The callers have to decode the type of the object.  If new object types are added, code which calls methods on those objects needs to be updated. Any given function is defined only once, but calls to that function can be scattered throughout the code. For polymorphic functions executed via switch statements, there may be many places which need to change to support a new type.  PostgreSQL mitigates this by providing a single execProcNode containing the implementation selection logic.

Finally, switch statements are notoriously prone to certain errors:

1. Omitting the break statement after a case, inadvertently allowing fallthrough to the next case.  Because fall-through is by design of the language (and is still used in some programs), it is difficult for compilers to warn about possible unintentional use of it.  (A similar problem, assignment inside tests — e.g. if (x = 5) { ...} — is easier to warn about since it’s less useful, and there is a syntactic idiom of putting the assignment in parentheses to indicate to the compiler that it is not an error.   Unfortunately there is less scope for syntactic tricks like that at the statement level.)  What C really needs to do is recognise that, most of the time, fallthrough is not intended and add a special fallthrough statement for the cases when it is. ;-)
2. Not handling (or improperly handling) the default case.  Compilers can warn about the default case if it is missing.  But there is still room for error.  If new types are added and the caller’s switch statement is not updated, then the new types will be caught by the default statement which may not be appropriate.  For this reason it is best if default statements for switch statements are used only to catch unhandled types. As shown above, the PostgreSQL switch statements tend to do this.

Function pointers

The alternative to testing the type of an object to determine which method implementation to call is to make that method implementation part of the object when it is created.  This can be done by adding function pointers as fields of the object.  When the caller wishes to call a method, it calls the function pointer.  Different object’s function pointers will point to the appropriate methods for each object.

If PostgreSQL’s execution code used function pointers, it might look something like:

typedef struct PlanState
{
    TupleTableSlot* (Exec *)(PlanState *node)
    ...
} PlanState;

/* Creation of each node type initialises its "Exec" method pointer. */
PlanState *create_unique_node(...)
{
    PlanState *node = create_node(T_UniqueState);
    node->Exec = ExecUnique;
    ...
    return node;
}

/* Node execution no longer has to look at the type, it just calls the function pointer. */
TupleTableSlot* ExecProcNode (PlanState *node)
{
    TupleTableSlot *result;

    result = node->Exec(node);

    return result;
}

Apart from giving us function pointers, C does not provide much in the way of assistance. One inconvenience is redundant syntax: to call a method f on an object x, we need to specify x twice: in locating the method to run, and in passing x to that method. C++ has the native concept of a method, where:

x.f(args);

is equivalent to C’s:

x.f(x, args);

In fact, the object x that the method is called on is provided in the method’s body as a special variable “this”. In our C equivalent, the “this” is simply the first parameter to the function, and we have to pass it explicitly each time.

Most large C programs are written to use the redundant syntax x.f(x, args). One alternative is to use a macro or helper function, to hide the fact that we’re using x twice. This is what execProcNode is effectively for.

A potential technique would be to create a closure in which the first argument is already bound, as in this non-C program:

PlanState *create_unique_node(...)
{
    PlanState *node = create_node(T_UniqueState);
    node->Exec = lambda () { ExecUnique(node); }  /* node is captured from the environment! */
    ...
    return node;
}

Closures are not directly possible in C, but if we’re willing to sacrifice portability we can use a hack to create them — this will be explained in a later post!

The main advantage of using function pointers like this is that the implemention for an object type is defined as part of the type, and not at each place in the code that wants to use the type. If a new type is created, it’s much easier to create a constructor for it that populates the function pointers with the implementations for it.

On the other hand: if a new method is added to all the types, then each object constructor needs to be changed to assign it. The compiler will not generally warn if one of the fields in a newly allocated struct is not initialised.

There is a trade off — the expression problem — between extending the the set of types, and extending the methods that each implements. This is discussed quite well on the Magpie blog, which describes the design of a more abstract language than C.

vtables

One of the features of putting function pointers directly in the object is that we can construct an object with interesting combinations of pointers. For instance, if our types were geometric shapes, we could have something like:

typedef struct Shape {
    ...
    double (* get_area)(struct Shape *shape);
    void (* draw)(struct Shape *shape);
    ...
} Shape;

Shape *make_something_interesting(void)
{
    Shape *shape = malloc(sizeof (Shape));
    shape->get_area = get_circle_area;
    shape->draw = draw_square;
    return shape;
}

In general, however, it’s highly likely that the circle methods are intended to be called on objects that implement all the circle methods, and similarly for square methods. For one thing it’s normal for methods to want to call other methods; if get_circle_area is called on an object, it seems reasonable for the implementation to assume that the object is a circle and that it can directly call other circle methods without needing to use the function pointers.

So when we design a family of types, we do not just specify a bunch of methods implementations that can be attached arbitrarily to objets. We specify a set of them for each type — a vtable (virtual method table). When an object of type T is created, it is assigned the vtable for T. We can put the function pointers in a vtable type, and create a specific vtable for each type.

typedef struct ShapeVTable {
    double (* get_area)(struct Shape *shape);
    void (* draw)(struct Shape *shape);
    ...
} ShapeVTable;

ShapeVTable circle_vtable = { get_circle_area, draw_circle, ... };
ShapeVTable rect_vtable = { get_rect_area, draw_rect, ... };

typedef struct Shape {
    char *name;
    ...
    ShapeVTable *vtable;
} Shape;

Shape *make_circle(char *name)
{
    Shape *shape = malloc(sizeof (Shape));
    shape->name = name;
    shape->vtable = circle_vtable;
    return shape;
}

Calling a method then becomes only slightly more verbose: shape->vtable.draw(shape);

But it’s now a lot harder to use inconsistent sets of methods in objects. Remember that a language’s usefulness is defined not only by what it lets you do, as what it stops you doing! That’s why type systems are useful: they let is more precisely specify what a valid program is. In this case, we’ve effectively made a type system for objects, in which we specify that valid ones are those with consistent sets of methods.

Final note. Why does PostgreSQL use the switch-style Polymorphism, rather than a simple function pointer in each node? I’m not actually sure myself. It’s left as an exercise for the reader to either a) research it and find out, or b) think of further advantages to the switch-style that I’ve omitted here. ;-)