以CPS样式重写Ackermann函数

Question

出于简单的好奇心和渴望加深对CPS样式（continuation passing style）的了解，我想知道是否有一种方法可以根据此方案重写此功能。

困难可能在于延续的设计，通常一个延续只接受一个参数，但在这种情况下，应接受两个参数，对吧？

这是我要练习的功能：

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));
}

如果这种“不可能”，还有另一种相对类似的非平凡手段吗？

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首先执行，因此现在它成为“外部”确认ack_cps(m, n - 1, ...)。在...中，我们传递上下文以继续使用外部ack执行。 （嗯，这是一个可怕的解释，但我不知道如何更好地解释它。）>