C中的实用延续传递风格？
Practical continuation passing style in C?
我最近写了很多 C 代码，我 运行 遇到了一个类似于我 运行 使用 Go 遇到的问题，我有很多代码看起来像这样：
if (foo() != 0) {
return -1;
}
bar();
这类似于我在 Golang 中看到的常量 if err != nil 检查。我想我想出了一个有趣的模式来处理这些容易出错的序列。我受到函数式语言的启发，这些语言具有 andThen 序列，用于将可能成功也可能不成功的计算链接在一起。我尝试实现一个简单的回调设置，但我意识到在没有 lambda 的情况下这在 C 中几乎是不可能的，即使有它们也会是回调地狱。然后我想到了使用跳转，我意识到可能有一个很好的方法来做到这一点。有趣的部分在下面。如果不使用此模式，将会有很多 if (Buffer_strcpy(...) != 0) 检查或一团乱麻的回调地狱。
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);
}
这是一个运行它的独立程序：
#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;
}
这部分是它的使用示例：
/*
* 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;
}
真的，我只是想更多地了解这种风格——我应该查找哪些关键字？这种风格真的有人用过吗？
只是为了把我的评论放在一个答案中，这里有一些想法。在我看来，第一个也是最重要的一点是，您正在使用一种过程式编程语言，在这种语言中，跳转是不受欢迎的，内存管理是一个众所周知的陷阱。因此，可能最好采用一种更广为人知且更简单的方法，这将很容易被您的编码人员阅读:
if(foo() || bar() || anotherFunctions())
return -1;
如果您需要 return 不同的错误代码，那么可以，我会使用多个 ifs。
关于直接回答问题，我的第二点是这不太实用。您正在实现（我可能会非常巧妙地添加）一个基本的 C++ classing 系统以及几乎看起来像异常系统的东西，尽管是一个基本的系统。问题是，你严重依赖框架的用户自己做很多管理 - 设置跳转，初始化所有 classes 并正确使用它们.它可能在一般 class 中是合理的，但在这里你正在实现一些不是该语言“本地”的东西（并且对于它的许多用户来说是陌生的）。 "class" 与您的异常处理无关的事实（树）需要引用您的 Continuation 直接是红旗。一个主要的改进可能是 提供一个 try 函数 ，这样用户就可以使用
if(try(f1, f2, f3, onError)) return -1;
这将包装您的结构的所有使用，使它们不可见，但仍然不会断开您的延续与树的连接。当然，这与上面的常规 if 非常接近，如果你做得好，你有 很多内存管理要做 - 线程，信号，什么支持吗？你能保证不漏水吗？
我的最后一点，不是发明轮子。如果你想要 try-except 系统，改变一种语言，或者如果你必须使用一个预先存在的库（我通过 SO 看到 exception4c 在 Google 上很高，虽然从未使用过）。如果 C 是首选工具，return 值、参数 return 值和信号处理程序将是我的目标（双关语？）。
我会避免 setjmp/longjmp:
- 它们使资源管理变得困难。
- 使用不常见，这使得代码更难理解和维护。
对于您的特定示例，您可以使用状态机避免 setjmp/longjmp：
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;
}
虽然我个人会选择 if 检查 goto 进行错误处理，这在 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.
...
}```
我最近写了很多 C 代码，我 运行 遇到了一个类似于我 运行 使用 Go 遇到的问题，我有很多代码看起来像这样：
if (foo() != 0) {
return -1;
}
bar();
这类似于我在 Golang 中看到的常量 if err != nil 检查。我想我想出了一个有趣的模式来处理这些容易出错的序列。我受到函数式语言的启发，这些语言具有 andThen 序列，用于将可能成功也可能不成功的计算链接在一起。我尝试实现一个简单的回调设置，但我意识到在没有 lambda 的情况下这在 C 中几乎是不可能的，即使有它们也会是回调地狱。然后我想到了使用跳转，我意识到可能有一个很好的方法来做到这一点。有趣的部分在下面。如果不使用此模式，将会有很多 if (Buffer_strcpy(...) != 0) 检查或一团乱麻的回调地狱。
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);
}
这是一个运行它的独立程序：
#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;
}
这部分是它的使用示例：
/*
* 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;
}
真的，我只是想更多地了解这种风格——我应该查找哪些关键字？这种风格真的有人用过吗？
只是为了把我的评论放在一个答案中，这里有一些想法。在我看来，第一个也是最重要的一点是，您正在使用一种过程式编程语言，在这种语言中，跳转是不受欢迎的，内存管理是一个众所周知的陷阱。因此，可能最好采用一种更广为人知且更简单的方法，这将很容易被您的编码人员阅读:
if(foo() || bar() || anotherFunctions())
return -1;
如果您需要 return 不同的错误代码，那么可以，我会使用多个 ifs。
关于直接回答问题，我的第二点是这不太实用。您正在实现（我可能会非常巧妙地添加）一个基本的 C++ classing 系统以及几乎看起来像异常系统的东西，尽管是一个基本的系统。问题是，你严重依赖框架的用户自己做很多管理 - 设置跳转，初始化所有 classes 并正确使用它们.它可能在一般 class 中是合理的，但在这里你正在实现一些不是该语言“本地”的东西（并且对于它的许多用户来说是陌生的）。 "class" 与您的异常处理无关的事实（树）需要引用您的 Continuation 直接是红旗。一个主要的改进可能是 提供一个 try 函数 ，这样用户就可以使用
if(try(f1, f2, f3, onError)) return -1;
这将包装您的结构的所有使用，使它们不可见，但仍然不会断开您的延续与树的连接。当然，这与上面的常规 if 非常接近，如果你做得好，你有 很多内存管理要做 - 线程，信号，什么支持吗？你能保证不漏水吗？
我的最后一点，不是发明轮子。如果你想要 try-except 系统，改变一种语言，或者如果你必须使用一个预先存在的库（我通过 SO 看到 exception4c 在 Google 上很高，虽然从未使用过）。如果 C 是首选工具，return 值、参数 return 值和信号处理程序将是我的目标（双关语？）。
我会避免 setjmp/longjmp:
- 它们使资源管理变得困难。
- 使用不常见，这使得代码更难理解和维护。
对于您的特定示例，您可以使用状态机避免 setjmp/longjmp：
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;
}
虽然我个人会选择 if 检查 goto 进行错误处理，这在 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.
...
}```