Pepe's Braindump

By example: Continuation-passing style in JavaScript

tags
Continuation Passing Style, Programming Languages

CPS can be discovered by using one particular constraint:

No procedure is allowed to return to its caller–ever.

Programming in CPS is possible because functions (that never return) take a callback that they call upon their return value.

Example: Identity functions

Take the direct style identity function:

function id(x) {
    return x;
}

It can be easily translated to CPS:

function id(x, cc) {
    cc(x);
}

Example: Naive factorial

Direct style:

function factorial(n) {
    if (n == 0) {
        return 1;
    } else {
        return n * *factorial(n - 1);
    }
}

CPS style:

function factorial(n, cc) {
    if (n == 0) {
        cc(1);
    } else {
        factorial(n - 1, function(t0) {
            cc(n * t0);
        });
    }
}

Example: Tail call factorial

function factorial(n) {
    return tailCallFact(n, 1);
}

function tailCallFact(n, acc) {
    if (n == 0) {
        return acc;
    } else {
        return tailCallFact(n - 1, acc * n);
    }
}
function factorial(n, cc) {
    tailCallFact(n, 1, cc);
}

function tailCallFact(n, acc, cc) {
    if (n == 0) {
        cc(acc);
    } else {
        tailCallFact(n - 1, acc * n, cc);
    }
}

Cortex theme by Jethro Kuan. Built with org-mode, org-roam and Hugo