Rewrite the Ackermann function in the CPS style

Question

Out of simple curiosity and desire to deepen my understanding of the CPS style (continuation passing style), I would like to know if there is a way to rewrite this function according to this scheme.

The difficulty probably lies in the design of the continuation, usually a continuation only takes one argument, but in this case it should take two, right?

Here is the function I want to practice:

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

If this "is not possible", is there another relatively similar non-trivial means?

That's not continuation passing, that's just normal recursion. — Lee Daniel Crocker

KamilCuk KamilCuk · Accepted Answer · 2019-12-16T21:50:10

This is fun:

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

You have to pass all the context and the callback with everything around down the callstack. So create a context, where you save your variables, and create a callback where you continue the execution. I tested it on godbolt on a small range and seems to give ok answer.

The biggest problem is with: ack(m - 1, ack(m, n - 1));. The ack that is inside executes first, so now it becomes the "outside" ack ack_cps(m, n - 1, ...). In the ... we pass the context to continue the execution with the outer ack. (Uch, this is a horrible explanation, but I have no idea how to explain it better).

Rewrite the Ackermann function in the CPS style

1 Answers