Suspendable function semantics

[mratsim]

Introduction

Looking at this example: https://github.com/disruptek/cps/blob/1bae506/stash/standalone_tcp_server.nim#L38-L45

# CPS 'io' primitive, registers the fd with epoll and stashes the continuation.
# Will be revived later by the main loop when the fd gets ready

proc io(c: Cont, fd: SocketHandle, event: int): Cont =
  var epv = EpollEvent(events: event.uint32)
  epv.data.u64 = fd.uint
  discard epoll_ctl(epfd, EPOLL_CTL_ADD, fd.cint, epv.addr)
  evq.readers[fd] = c

and used like this

var n = 0

proc doClient(fdc: SocketHandle) {.cps:Cont} =

  while true:
    cps io(fdc, POLLIN)
    let s: string = sockRecv(fdc)
    if s.len == 0:
      return
    cps io(fdc, POLLOUT)
    sockSend(fdc, response)
    inc n


# CPS server handler

proc doServer(port: int) {.cps:Cont} =
  let fds: SocketHandle = sockBind(port)
  while true:
    cps io(fds, POLLIN)
    let fdc: SocketHandle = sockAccept(fds)
    # Create new client and add to work queue
    evq.work.addLast doClient(fdc)

This is significantly more flexible than coroutines because
it is hard to design a coroutine (or a closure iterator) that can accept an argument after suspension.
For instance in my initial design I proposed this syntax: https://github.com/weavers-guild/weave-io/blob/master/design/design_1_coroutines.md#asynchronous-stream-with-coroutines

coro asyncReader(path: string, buf {.resume.}: var array[4 * 1024, byte]): int =
  # <---- Implicit suspension
  let f = openFile(path)
  var curIdx = 0
  while true:
    let numBytes = f.readBytes(curIdx, buf)
    curIdx += numBytes
    yield numBytes # <---- Explicit suspension
    if numBytes == 0:
      break

let reader = asyncReader("path/to/greatness")
var buf: array[4 * 1024, byte]
for numBytes in reader.resume(buf): # <- accepts args at resume locations
  expensiveWork(buf, numBytes)

This looks very elegant at first but there are issues I spotted:

• This is not a "resumable function" anymore, it's a function that mutates its signature upon resume, a function arguments doesn't change during it's lifetime normally. While this is certainly possible with macro, I don't have a function anymore but a state machine and I certainly tread in uncharted territory while plain coroutines have a lot of theory behind, so it's even more experimental that what we are doing.
• What if for the first yield we want an array of byte and for another yield we want something else, that would need some {.resume: 1.} and {.resume: 2.} tags or something in that spirit.

So, this shows an important use case of continuations over coroutines.

Continuation ergonomic

Then I am quite uncomfortable at exposing the Cont type to users, even to core libraries developers, it seems like something that is magic and the cps name doesn't help. In that case I would rewrite the code like this:

# CPS 'io' primitive, registers the fd with epoll and stashes the continuation.
# Will be revived later by the main loop when the fd gets ready

proc io(fd: SocketHandle, event: int) {.suspend.} =
  var epv = EpollEvent(events: event.uint32)
  epv.data.u64 = fd.uint
  discard epoll_ctl(epfd, EPOLL_CTL_ADD, fd.cint, epv.addr)
  evq.readers[fd] = getCurrentContinuation()

We provide an easily grepable getCurrentContinuation that works with the {.suspend.} pragma which rewrites the signature to include the Continuation, allows getCurrentContinuation and adds a suspendable or resumable effect.

Then, I think the cps name should be replaced with the more established name callCC (call with current continuation)

var n = 0

proc doClient(fdc: SocketHandle) {.suspend.} =

  while true:
    callCC io(fdc, POLLIN)
    let s: string = sockRecv(fdc)
    if s.len == 0:
      return
    callCC io(fdc, POLLOUT)
    sockSend(fdc, response)
    inc n


# CPS server handler

proc doServer(port: int) {.suspend.} =
  let fds: SocketHandle = sockBind(port)
  while true:
    callCC io(fds, POLLIN)
    let fdc: SocketHandle = sockAccept(fds)
    # Create new client and add to work queue
    evq.work.addLast doClient(fdc)

Concerns

I have 2 concerns, one fundamental and one ergonomic:

Fundamental concern: callCC

Fundamental concern, is callCC too powerful? (delimited continuation = coroutine, undelimited continuation = what we could have)

• http://okmij.org/ftp/continuations/against-callcc.html
• http://okmij.org/ftp/continuations/undelimited.html#delim-vs-undelim
• Ruby continuation considered harmful http://www.atdot.net/~ko1/pub/ContinuationFest-ruby.pdf
• Scheme discussion on callCC: http://scheme-reports.org/mail/scheme-reports/msg02780.html

As a summary: callCC is a very powerful operator with pitfalls, in particular multishots continuations (resuming multiple times from the same point) is error prone in terms of memory management, control flow and isn't used in practice

So one first step we want, is to make continuations Isolated and ensure that they are moved and never copied so that you can't trigger a continuation twice which is likely to lead to double-free and use-after-free bugs and other hard to debug problems, making it mutable and replacing itself works as well. But is it enough?

Note: I do believe we should still provide coroutine besides first-class continuations, they are more familiar to people, and would make it easy to port asyncdispatch and Chronos to it.

Important: I'm not totally clear whether my callCC proposal is an undelimited continuation like Scheme, or some form of delimited continuation that no language as implemented up to now. If the latter maybe we should change the name to something else. This is because it seems like a delimitation continuation is "a proc + a mutable cell" while undelimited continuation are naked? No type/functional/language theorist so hopefully I convey my confusion right.

Ergonomic concern: {.suspend.}

Ergonomic concern, the suspend pragma here assumes that there is no continuation returned. And that the case where we want to chain continuations are only for proc generated by the CPS-transform. I will look into that, if I'm wrong this means we need 2 variations of the suspend pragma, with and without continuation.

[mratsim]

This paper introduces runCC which matches with what I want to do

• A Monadic Framework for DelimitedContinuations
  https://legacy.cs.indiana.edu/~dyb/pubs/monadicDC.pdf

Also it comforts me that we are in a delimited continuation case since our continuations do not capture the whole "rest of the program" but only a subset, the subroutine/function that we CPS-transformed.

runCC seems like a good name, we have theory and implementation to back us, so I think problem 1 is solved. Only thing left is the ergonomic concern. Alternatively another paper is using callPC (call partial continuation)

[mratsim]

On a second thought, I think suspendWith is more descriptive than runCC and I think bindCurrentContinuation would convey more nicely the fact that they are move-only values (rather than getCurrentContinuation).

[disruptek]

I do think we shouldn't worry about matching the lingo from other langs/domains; it's more important to capture what this means to the Nim programmer and help them form a mental map. We may also want to break some assumptions offered by reuse of a name...

[disruptek]

Then I am quite uncomfortable at exposing the Cont type to users, even to core libraries developers, it seems like something that is magic and the cps name doesn't help.

• The cps name is the macro, so it must stay in some capacity. Someone else can choose the name.
• We expose the Cont type because, in fact, the user supplies it to us in the first place. It's not hard for us to do and it may afford value to the user, so we do it.