以 CPS 风格重写 Ackermann 函数
Rewrite the Ackermann function in the CPS style
出于单纯的好奇心和想加深对CPS风格的理解(continuation passing style),想知道有没有办法按照这个方案重写这个函数
难点大概在continuation的设计上,通常一个continuation只接受一个参数,但在这种情况下应该有两个,对吧?
这里是我要练习的函数:
long int ack(int m, int n)
{
if (!m) return n + 1;
if (!n) return ack(m - 1, 1);
return ack(m - 1, ack(m, n - 1));
}
如果这个"is not possible",还有没有其他比较类似的不平凡的手段?
这很有趣:
struct ctx {
int m;
void (*cb)(long int val, void *arg);
void *arg;
};
void ack_cps(int m, int n, void (*cb)(long int val, void *arg), void *arg);
void _ack_cps_change_n_cb(long int val, void *arg) {
struct ctx *ctx = arg;
ack_cps(ctx->m, val, ctx->cb, ctx->arg);
}
void ack_cps(int m, int n, void (*cb)(long int val, void *arg), void *arg)
{
if (!m) {
cb(n + 1, arg);
} else if (!n) {
ack_cps(m - 1, 1, cb, arg);
} else {
ack_cps(m, n - 1, _ack_cps_change_n_cb,
&(struct ctx){ m - 1, cb, arg });
}
}
您必须将所有上下文和回调以及周围的所有内容传递到调用堆栈中。因此,创建一个上下文,您可以在其中保存变量,并在您继续执行的地方创建一个回调。我在 godbolt 上进行了小范围测试,似乎给出了不错的答案。
最大的问题是:ack(m - 1, ack(m, n - 1));
。里面的 ack
先执行,所以现在它变成了 "outside" ack ack_cps(m, n - 1, ...)
。在 ...
中,我们传递上下文以继续执行外部 ack
。 (呃,这是一个可怕的解释,但我不知道如何更好地解释它)。
出于单纯的好奇心和想加深对CPS风格的理解(continuation passing style),想知道有没有办法按照这个方案重写这个函数
难点大概在continuation的设计上,通常一个continuation只接受一个参数,但在这种情况下应该有两个,对吧?
这里是我要练习的函数:
long int ack(int m, int n)
{
if (!m) return n + 1;
if (!n) return ack(m - 1, 1);
return ack(m - 1, ack(m, n - 1));
}
如果这个"is not possible",还有没有其他比较类似的不平凡的手段?
这很有趣:
struct ctx {
int m;
void (*cb)(long int val, void *arg);
void *arg;
};
void ack_cps(int m, int n, void (*cb)(long int val, void *arg), void *arg);
void _ack_cps_change_n_cb(long int val, void *arg) {
struct ctx *ctx = arg;
ack_cps(ctx->m, val, ctx->cb, ctx->arg);
}
void ack_cps(int m, int n, void (*cb)(long int val, void *arg), void *arg)
{
if (!m) {
cb(n + 1, arg);
} else if (!n) {
ack_cps(m - 1, 1, cb, arg);
} else {
ack_cps(m, n - 1, _ack_cps_change_n_cb,
&(struct ctx){ m - 1, cb, arg });
}
}
您必须将所有上下文和回调以及周围的所有内容传递到调用堆栈中。因此,创建一个上下文,您可以在其中保存变量,并在您继续执行的地方创建一个回调。我在 godbolt 上进行了小范围测试,似乎给出了不错的答案。
最大的问题是:ack(m - 1, ack(m, n - 1));
。里面的 ack
先执行,所以现在它变成了 "outside" ack ack_cps(m, n - 1, ...)
。在 ...
中,我们传递上下文以继续执行外部 ack
。 (呃,这是一个可怕的解释,但我不知道如何更好地解释它)。