What is CPS and why is it the next big thing™

[alaviss]

We have plenty of hype behind CPS and no easy to understand explanation to hook people in. This thread is to figure out the best way to teach Nim programmers what CPS is.

[alaviss]

I have this incomplete draft done to prep for "This month in Nim", though not sure if its any good.

CPS is a library which allows any procedure to be rewritten using continuations as control-flow. In short, a procedure like this:

proc foo(i: int) {.cps: Cont.} =
  ## Sleep for `i` millisecond
  let x = "Hello, world after "
  sleep i
  echo x, i

Can be rewritten into:

type Env = ref object of Cont
  i: int
  x: string

proc afterSleep(c: Cont): Cont =
  echo Env(c).x, Env(c).i

proc foo(c: Cont): Cont =
  Env(c).x = "Hello, world after "
  Env(c).fn = afterSleep
  result = sleep(c, Env(c).i)

proc foo(i: int): Cont =
  result = Env(fn: foo, i: i)

What do we achieve with this rewrite?

We can now decide when will afterSleep be run, at runtime. This is extremely useful for a task scheduler:

type
  Cont = ref object of RootObj
    fn: proc(c: Cont): Cont {.nimcall.}

proc sleep(c: Cont; ms: int): Cont {.cpsMagic.} =
  ## Take a continuation and queue it for `ms` milliseconds
  # insert queuing operation here

[disruptek]

I think the right way to do it is to work in reverse:

1. start with a simple sync program and explain why it needs moar concurrency
2. turn it into a state machine and explain how that works; in particular, how it's efficient
3. lift the states into functions and explain what this buys us from a compositional view
4. lift the function arguments into a continuation and explain the memory considerations
5. explain how this works with the trampoline and maybe talk about tail-calls a bit
6. finally show how cps does all this bullshit for you

And perhaps additionally:

1. start with a simple sync program
2. turn it into async/await and show how that works; walk through the macro output and dispatcher
3. turn it into cps and show how it differs; efficiency, composability, customization, etc.

Also, yes, we need a better demonstration. I think the chat bot idea is pretty good, but another good demo might be an async process i/o monitor. I implemented this in golden and much later discovered that it doesn't work -- at least, that's my memory -- so it might not be a good demo for async/await. 😉

BTW, I know that asynctools that has an async/await process monitor in it. I don't know if that one is any better.

[disruptek]

Also, I just saw the title... If you want to explain why CPS is the next big thing, you have to explain about what you can actually do with a continuation, which you cannot do in async/await -- I'm talking movement among threads, different dispatchers, etc.