Practical continuation passing style in C?

Question

I have been writing a lot of C code recently, and I've been running into a problem similar to the one I ran into with Go where I have a lot of code that looks like this:

if (foo() != 0) {
  return -1;
}
bar();

which is similar to the constant if err != nil checks I see in Golang. I think I've come up with an interesting pattern for dealing with these error-prone sequences. I was inspired by functional languages that have andThen sequences for chaining together computations which may or may not succeed. I tried implementing a naive callback setup, but I realized this is practically impossible in C without lambdas, and it would be callback hell even with them. Then I thought about using jump, and I realized there might be a good way to do it. The interesting part is below. Without using this pattern, there would be a lot of if (Buffer_strcpy(...) != 0) checks or a mess of callback hell.

switch (setjmp(reference)) {
    case -1:
        // error branch
        buffer->offset = offset;
        Continuation_error(continuation, NULL);
    case 0:
        // action 0
        Buffer_strcpy(buffer, "(", andThenContinuation);
    case 1:
        // action 1 (only called if action 0 succeeds)
        Node_toString(binaryNode->left, buffer, andThenContinuation);
    case 2:
        Buffer_strcpy(buffer, " ", andThenContinuation);
    case 3:
        Node_toString(binaryNode->right, buffer, andThenContinuation);
    case 4:
        Buffer_strcpy(buffer, ")", andThenContinuation);
    case 5:
        Continuation_success(continuation, buffer->data + offset);
}

And here is a self-contained program which runs it:

#include <string.h>
#include <stdio.h>
#include <setjmp.h>

/*
 * A continuation is similar to a Promise in JavaScript.
 * - success(result)
 * - error(result)
 */
struct Continuation;

/*
 * The ContinuationVTable is essentially the interface.
 */
typedef struct {
    void (*success)(struct Continuation *, void *);

    void (*error)(struct Continuation *, void *);
} ContinuationVTable;

/*
 * And the Continuation is the abstract class.
 */
typedef struct Continuation {
    const ContinuationVTable *vptr;
} Continuation;

void Continuation_success(Continuation *continuation, void *result) {
    continuation->vptr->success(continuation, result);
}

void Continuation_error(Continuation *continuation, void *result) {
    continuation->vptr->error(continuation, result);
}

/*
 * This is the "Promise" implementation we're interested in right now because it makes it easy to
 * chain together conditional computations (those that should only proceed when upstream
 * computations succeed).
 */
typedef struct {
    // Superclass (this way the vptr will be in the expected spot when we cast this class)
    Continuation super;

    // Stores a reference to the big struct which contains environment context (basically a bunch
    // of registers). This context is pretty similar to the context that you'd need to preserve
    // during a function call.
    jmp_buf *context;

    // Allow computations to return a result.
    void **result;

    // The sequence index in the chain of computations.
    int index;
} AndThenContinuation;

void AndThenContinuation_success(Continuation *continuation, void *result) {
    AndThenContinuation *andThenContinuation = (AndThenContinuation *) continuation;
    if (andThenContinuation->result != NULL) {
        *andThenContinuation->result = result;
    }
    ++andThenContinuation->index;
    longjmp(*andThenContinuation->context, andThenContinuation->index);
}

void AndThenContinuation_error(Continuation *continuation, void *result) {
    AndThenContinuation *andThenContinuation = (AndThenContinuation *) continuation;
    if (andThenContinuation->result != NULL) {
        *andThenContinuation->result = result;
    }
    longjmp(*andThenContinuation->context, -1);
}

const ContinuationVTable andThenContinuationVTable = (ContinuationVTable) {
        .success = AndThenContinuation_success,
        .error = AndThenContinuation_error,
};

void AndThenContinuation_init(AndThenContinuation *continuation, jmp_buf *context, void **result) {
    continuation->super.vptr = &andThenContinuationVTable;
    continuation->index = 0;
    continuation->context = context;
    continuation->result = result;
}

This part is an example of its use:

/*
 * I defined a buffer class here which has methods to write to the buffer, which might fail if the
 * buffer is out of bounds.
 */
typedef struct {
    char *data;
    size_t offset;
    size_t capacity;
} Buffer;

void Buffer_strcpy(Buffer *buffer, const void *src, Continuation *continuation) {
    size_t size = strlen(src) + 1;
    if (buffer->offset + size > buffer->capacity) {
        Continuation_error(continuation, NULL);
        return;
    }
    memcpy(buffer->data + buffer->offset, src, size);
    buffer->offset += size - 1; // don't count null character
    Continuation_success(continuation, NULL);
}

/*
 * A Node is just something with a toString method.
 */
struct NodeVTable;

typedef struct {
    struct NodeVTable *vptr;
} Node;

typedef struct NodeVTable {
    void (*toString)(Node *, Buffer *, Continuation *);
} NodeVTable;

void Node_toString(Node *node, Buffer *buffer, Continuation *continuation) {
    node->vptr->toString(node, buffer, continuation);
}

/*
 * A leaf node is just a node which copies its name to the buffer when toString is called.
 */
typedef struct {
    Node super;
    char *name;
} LeafNode;

void LeafNode_toString(Node *node, Buffer *buffer, Continuation *continuation) {
    LeafNode *leafNode = (LeafNode *) node;
    Buffer_strcpy(buffer, leafNode->name, continuation);
}

NodeVTable leafNodeVTable = (NodeVTable) {
        .toString = LeafNode_toString,
};

void LeafNode_init(LeafNode *node, char *name) {
    node->super.vptr = &leafNodeVTable;
    node->name = name;
}

/*
 * A binary node is a node whose toString method should simply return
 * `(${toString(left)} ${toString(right)})`. However, we use the continuation construct because
 * those toString calls may fail if the buffer has insufficient capacity.
 */
typedef struct {
    Node super;
    Node *left;
    Node *right;
} BinaryNode;

void BinaryNode_toString(Node *node, Buffer *buffer, Continuation *continuation) {
    BinaryNode *binaryNode = (BinaryNode *) node;

    jmp_buf reference;
    AndThenContinuation andThen;
    AndThenContinuation_init(&andThen, &reference, NULL);
    Continuation *andThenContinuation = (Continuation *) &andThen;

    /*
     * This is where the magic happens. The -1 branch is where errors are handled. The 0 branch is
     * for the initial computation. Subsequent branches are for downstream computations.
     */
    size_t offset = buffer->offset;
    switch (setjmp(reference)) {
        case -1:
            // error branch
            buffer->offset = offset;
            Continuation_error(continuation, NULL);
        case 0:
            // action 0
            Buffer_strcpy(buffer, "(", andThenContinuation);
        case 1:
            // action 1 (only called if action 0 succeeds)
            Node_toString(binaryNode->left, buffer, andThenContinuation);
        case 2:
            Buffer_strcpy(buffer, " ", andThenContinuation);
        case 3:
            Node_toString(binaryNode->right, buffer, andThenContinuation);
        case 4:
            Buffer_strcpy(buffer, ")", andThenContinuation);
        case 5:
            Continuation_success(continuation, buffer->data + offset);
    }
}

NodeVTable binaryNodeVTable = (NodeVTable) {
        .toString = BinaryNode_toString,
};

void BinaryNode_init(BinaryNode *node, Node *left, Node *right) {
    node->super.vptr = &binaryNodeVTable;
    node->left = left;
    node->right = right;
}

int main(int argc, char **argv) {
    LeafNode a, b, c;
    LeafNode_init(&a, "a");
    LeafNode_init(&b, "b");
    LeafNode_init(&c, "c");

    BinaryNode root;
    BinaryNode_init(&root, (Node *) &a, (Node *) &a);

    BinaryNode right;
    BinaryNode_init(&right, (Node *) &b, (Node *) &c);
    root.right = (Node *) &right;

    char data[1024];
    Buffer buffer = (Buffer) {.data = data, .offset = 0};
    buffer.capacity = sizeof(data);
    jmp_buf reference;
    AndThenContinuation continuation;
    char *result;
    AndThenContinuation_init(&continuation, &reference, (void **) &result);

    switch (setjmp(reference)) {
        case -1:
            fprintf(stderr, "failure\n");
            return 1;
        case 0:
            BinaryNode_toString((Node *) &root, &buffer, (Continuation *) &continuation);
        case 1:
            printf("success: %s\n", result);
    }
    return 0;
}

Really, I just want to know more about this style--what keywords should I be looking up? Is this style ever actually used?

Answer 1

Just to put my comment in an answer, here are a few thoughts. The first and foremost point, in my opinion, is that you are working in a procedural programming language where jumping is frowned upon and memory managing is a known pitfall. As such, it is probably best to go with a more known and much easier approach, which will be easily readable to your fellow coders:

if(foo() || bar() || anotherFunctions())
    return -1;

If you need to return different error codes then yes, I would use multiple ifs.

Regarding answering the question directly, my second point is this is not very practical. You are implementing (quite cleverly I might add) a basic C++ classing systems along with something that almost looks like an exception system, albeit a basic one. The problem is, you rely heavily on the user of the framework to do a lot of management on their own - setting the jumps, initializing all the classes and using them correctly. It may be justified in the general class, but here you are implementing something not "native" to the language (and foreign to many of its users). The fact a "class" unrelated to your exception handling (the tree) needs to reference your Continuation directly is a red flag. A major improvement would probably be to provide a try function, such that the user just uses

if(try(f1, f2, f3, onError)) return -1;

Which would wrap all the usage of your structs, making them invisible, though still not disconnecting your continuation from the tree. Of course, this is getting quite close to that regular if above, and if you do it properly, you have a lot of memory management to do - threads, signals, what is supported? Can you make sure you never leak?

My final point, is not inventing the wheel. If you want try-except systems, change a language, or if you must use a preexisting library (I see exception4c is high on Google through SO, never used it though). If C is the tool of choice, return values, argument return values, and signal handlers would be my goto (pun intended?).

Answer 2

I would avoid setjmp/longjmp:

• They make resource management hard.
• Usage is uncommon, which makes code harder to understand and maintain.

For you particular example, you could avoid setjmp/longjmp with a state machine:

typedef enum {
  error,
  leftParen,
  leftAction,
  space,
  rightAction,
  rightParen,
  done,
} State;


void* BinaryNode_toString(Node *node, Buffer *buffer) {
    ...

    State state = leftParen;
    while (true) {
        switch (state) {
            case error:
                // error branch
                return NULL;
            case leftParen:
                // action 0
                state = Buffer_strcpy(buffer, "(", leftAction);
                break;
            case leftAction:
                state = Node_toString(binaryNode->left, buffer, space);
                break;
            case space:
                state = Buffer_strcpy(buffer, " ", rightAction);
                break;
            case rightAction:
                state = Node_toString(binaryNode->right, buffer, rightParen);
                break;
            case rightParen:
                state = Buffer_strcpy(buffer, ")", done);
                break;
            case done:
                return buffer->data + offset;
        }
    }
}

State Buffer_strcpy(Buffer *buffer, const void *src, State nextState) {
    size_t size = strlen(src) + 1;
    if (buffer->offset + size > buffer->capacity) {
        return error;
    }
    memcpy(buffer->data + buffer->offset, src, size);
    buffer->offset += size - 1; // don't count null character
    return nextState;
}

although personally I would just go with if checks with goto for error-handling, which is much more idiomatic in C:

void* BinaryNode_toString(Node *node, Buffer *buffer) {
    ...
    if (!Buffer_strcpy(...)) goto fail;
    if (!Node_toString(...)) goto fail;
    if (!Buffer_strcpy(...)) goto fail;
    ...

fail:
   // Unconditionally free any allocated resources.
   ...
}```