ctail-recursioncontinuationscontinuation-passing

Rewrite the Ackermann function in the CPS style


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?


Solution

  • 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).