以 CPS 风格重写 Ackermann 函数

Question

出于单纯的好奇心和想加深对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"，还有没有其他比较类似的不平凡的手段？

Answer 1

这很有趣：

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 风格重写 Ackermann 函数

Rewrite the Ackermann function in the CPS style

c

tail-recursion

continuations

continuation-passing