Continuation-Passing Style

TL;DR

It's a cps pragma you annotate a procedure declaration with in order to automagically rewrite it as a type which holds 1) all the procedure's locals, and 2) a pointer to run the continuation.

You instantiate continuations by calling your function with arguments, or via typed continuation callbacks. You may extend the Continuation type to add custom data and functionality.

The macro provides comfort for automatic chaining, stack tracing, drying up function color, and handling exceptions. Hooks enable precisely-scoped control of much of the machinery, including memory management.

What Is CPS?

<details> <summary>Click here for an awesome infographic explaining what CPS is and how our transform works. </summary> <img alt="The Nim CPS Transform" src="/docs/cps.svg"/> </details>

A cps proc macro enables enjoyment of the CPS abstraction for free, hiding all the verbosity and spaghetti code paths of hand-written continuation passing. It takes your standard procedure and rewrites it at compile-time into a continuation form.

The macro performs only the control-flow rewrite. You may define your own continuation types. To manage them, you can choose from available dispatchers or customize your own.

As CPS is essentially a safe transformation of Nim to equivalent Nim, you can use it anywhere you can use Nim, or more accurately, C, C++, or JavaScript.

Why Do I Want It?

The continuations produced by this macro are tiny -- as little as 32 bytes each -- and run at the speed of any native function call; they…

compose efficient and idiomatic asynchronous code
are over a thousand times lighter than threads
are leak-free under Nim's modern memory management
may be extended with custom inheritance-based types
may be managed using custom dispatchers (executors)
may be moved between threads to parallelize execution
have no backend or runtime library requirements
exploit no unsafe features of the language (cast, ptr, addr, emit)

Why Haven't I Heard of It?

The project isn't dead; it simply hasn't needed much development. We have a few small improvements we want to make before a 1.0 major release, but the general consensus is that the current implementation accomplishes our original goals quite well.

Major future development will revolve around implementing CPS directly in the Nimskull compiler.

How Does It Work?

A substantial effort to demystify this style of programming, and what it may enable, lives in the docs/ subdirectory.

We also have a tutorial to help new users on their way to get starting with CPS.

For a description of the origins of our approach, see the included papers and https://github.com/nim-lang/RFCs/issues/295, where we write in more depth about why the implementation exists, goals for future development, etc.

Architecture

The implementation is comprised of two moving parts:

a continuation is a bespoke type made to carry all locals in a procedure -- the environment -- plus a function pointer with which the continuation is poised to continue, or resume:

type
  Continuation = ref object   # all continuations inherit from this
    next: proc(c: Continuation): Continuation

a dispatcher is a procedure which resumes a continuation by invoking the continuation's function pointer with the continuation itself as input. It follows that to suspend, the function simply returns control to the dispatcher.

c = c.next(c)           # we often replace the continuation with its result

A trampoline is common form of dispatcher which resumes a continuation in a loop; it bounces control up to the continuation, which returns back down to the trampoline when it's ready to suspend.

while true:
  if c.isNil:           # 'dismissed': a nil continuation result
    break
  if not c.next.isNil:  # 'finished': a nil continuation function
    break
  c = c.next(c)         # resuming a 'running' (suspended) continuation

Application

We use a procedure definition to define the continuation. The type we want to base the continuation upon is supplied as the only argument to our cps pragma macro. You can simply use the Continuation type itself, if you prefer.

proc zoom() {.cps: Continuation.} =
  ## a very fast continuation
  discard

Calling the procedure (with arguments, if required) runs the continuation to completion.

zoom()
echo "that was fast!"

You can extend the Continuation type to carry state during the execution of your continuation.

type
  Count = ref object of Continuation
    labels: Table[string, ContinuationFn]

Here we've introduced a table that maps strings to a continuation "leg", or slice of control-flow that is executed as a unit.

Now we'll introduce two magical procedures for manipulating the table.

proc label(c: Count; name: string): Count {.cpsMagic.} =
  ## Record a label by `name` which we can later goto().
  c.labels[name] = c.fn
  return c  # control resumes in the continuation

proc goto(c: Count; name: string): Count {.cpsMagic.} =
  ## Resume execution at the `name` label in the code.
  c.fn = c.labels[name]
  return c  # control resumes in the continuation

These pragma'd procedures act as continuation legs and we can use them in our continuations without supplying the initial Count continuation argument.

Some people call this "colorless" syntax, since calls look the same whether made inside or outside of a continuation.

proc count(upto: int): int {.cps: Count.} =
  ## deploy the Count to make counting fun again;
  ## this continuation returns the number of trips through the goto
  var number = 0
  label: "again!"
  inc number
  echo number, "!"
  echo number, " loops, ah ah ah!"
  if number < upto:
    goto "again!"
  echo "whew!"
  return number

const many = 1_000_000_000
assert many + 1 == count(many)  # (this might take awhile to finish)

Sometimes you don't want to do a lot of counting right away, but, y'know, maybe a bit later, after your nap. In that case, you can use whelp to instantiate your continuation with arguments, without actually invoking it.

When you're ready, the trampoline will run your continuation to completion and bounce it back to you.

var later = whelp count(1_000_000)
sleep 30*60*1000
echo "it's later!  time to count!"
later = trampoline later

Continuations have a simple state(c: Continuation): State enum that is helped into running(), finished(), and dismissed() boolean predicates.

assert later.finished, "counting incomplete!"

Continuations can themselves be called in order to retrieve their result.

echo "i counted ", later(), " trips through the goto"

Such a call will run the continuation on your behalf if it has not already run to completion.

var later = whelp count(1_000_000)
echo "we counted ", later(), " trips through the goto"

Installation

$ nimble install https://github.com/nim-works/cps

Documentation

Ready For More?

examples/coroutine.nim (walkthrough): A simple coroutine implementation of coroutines on top of CPS communicating with each other.

Complete API Documentation

See the documentation for the cps module as generated directly from the source.

Extensive Test Suite

At last count, there are no less than 211 unique tests of the cps library which confirm successful handling of myriad semantic forms and complex continuation composition. The tests are arguably the most valuable piece of code in the project and, as per usual, serve as the most complete documentation of the specification.

Dispatchers

An example dispatcher with support for yields, I/O, and timers was included in the past, but demonstrating dispatch conflated the roles of continuation and dispatcher, confusing newcomers.

For a robust dispatcher implementation targeting broad OS support and modern async features, take a look at https://github.com/alaviss/nim-sys.

Examples

A small collection of examples provides good demonstration of multiple patterns of CPS composition. Each example runs independently, with no other requirements, yet demonstrates different exploits of cps.

Cps

Install / Use

README