How do I convert the following functions in JavaScript to continuation passing style (CPS)?

Question

Suppose I have the following functions:

function f(x) { return x + 1; }

function g(x) { return x * 2; }

function h() { return 5; }

How could I convert the expression f(g(h())) into continuation passing style? I know that h is transformed to:

function h(ret) { ret(5); }

However, I don't know how to convert the expression f(g(h())) into CPS.

In addition, what if f takes 2 arguments instead of 1? How would that look in CPS?

Furthermore, what if f and g don't take any arguments at all? How does that look in CPS?

Answer 1

Continuation passing style is really simple. For example, suppose you have the following functions which you want to convert to CPS:

function f(x) {
    return x + 1;
}

function g(x) {
    return x * 2;
}

function h() {
    return 3;
}

alert(f(g(h())));

Written in CPS:

function f(k) {
    return function (x) {
        return k(x + 1);
    };
}

function g(k) {
    return function (x) {
        return k(x * 2);
    };
}

function h(k) {
    return k(3);
}

h(g(f(alert)));

When f takes two arguments:

function f(k) {
    return function (x) {
        return function (y) {
            return k(x + y);
        };
    };
}

function g(k) {
    return function (x) {
        return k(x * 2);
    };
}

function h(k) {
    return k(3);
}

h(h(g(f(alert))));

In the case f and g don't take any arguments, they are not functions (in the mathematical sense of a function). Hence, they are just constants:

function f(k) {
    return k(1);
}

function g(k) {
    return k(2);
}

function h(k) {
    return k(3);
}

h(alert);
g(alert);
f(alert);

There is no way to compose constants using CPS. Think about it: f(g(h())) doesn't really make any sense when f and g don't take any arguments. It's better to just write h(), g(), f().

Continuation passing style is especially nice when used in conjunction with currying:

var f = curry(function (k, x, y) {
    return k(x + y);
});

var g = curry(function (k, x) {
    return k(x * 2);
});

function h(k) {
    return k(3);
}

h(h(g(f(alert))));

function curry(f, l, a) {
    var len = l;
    var args = a;

    switch (arguments.length) {
    case 1: len = f.length;
    case 2: args = [];
    }

    if (args.length + 1 === len) {
        return function (a) {
            return f.apply(null, args.concat([a]));
        };
    } else {
        return function (a) {
            return curry(f, len, args.concat([a]));
        };
    }
}

Hope that helps.