Continuation-passing Style

To compare it to C, the current continuation is like the current state of the stack
(http://stackoverflow.com/questions/612761/what-is-call-cc)

A function written in continuation-passing style takes an extra argument: an explicit "continuation" i.e. a function of one argument. When the CPS function has computed its result value, it "returns" it by calling the continuation function with this value as the argument.

To compare it to C, the current continuation is like the current state of the stack

A programmer can discover continuation-passing style by themselves if subjected to one constraint:

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

One hint makes programming in this style possible:

When a procedure is ready to "return" to its caller, it invokes the "current continuation" callback (provided by its caller) on the return value.

below code is reference from

http://matt.might.net/articles/by-example-continuation-passing-style/

Example: Naive factorial

Here's the standard naive factorial:

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

Here it is in CPS:

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

And, to "use" the function, we pass it a callback:

fact (5, function (n) {   console.log(n) ; // Prints 120 in Firebug. })

Call graph

fact (3, function (n) { 

  console.log(n) ; 

})

call 

fact (2, function (t0) {

     console.log(3 * t0) }) ;

call

fact (1, function (t0) {   

     console.log(3 * 2* t0) }) ;

call

 

fact (0, function (t0) {   

     console.log(3 * 2*  1 * t0) }) ;

Example: Tail-recursive factorial

Here's tail-recursive factorial:

function fact(n) {   return tail_fact(n,1) ; } function tail_fact(n,a) {   if (n == 0)     return a ;   else     return tail_fact(n-1,n*a) ; }

And, in CPS:

function fact(n,ret) {   tail_fact(n,1,ret) ; } function tail_fact(n,a,ret) {   if (n == 0)     ret(a) ;   else     tail_fact(n-1,n*a,ret) ; }

They are the same style that moving result calculation wehn function calling

CPS will change program flow as continue

http://lodr.github.io/presentations/cps-javascript/index.html#/1/1

to

http://lodr.github.io/presentations/cps-javascript/index.html#/1/3

Why is useful?

good example

http://lodr.github.io/presentations/cps-javascript/index.html#/5