Skip to content

Latest commit

 

History

History
387 lines (284 loc) · 14.8 KB

README.md

File metadata and controls

387 lines (284 loc) · 14.8 KB

Continuation-Passing Style

Test Matrix GitHub release (latest by date) Minimum supported Nim version Recommended Nim version Maximum supported Nim version License Matrix IRC

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?

Click here for an awesome infographic explaining what CPS is and how our transform works. The Nim CPS Transform

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 nim-lang/RFCs#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:

  1. 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
  1. 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"

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.

Example Description
Channels A channel connects sender and receiver continuations
Goto Implementation of label and goto statements using CPS
Iterator A simple demonstration of a CPS-based iterator
Coroutines A pair of continuations communicate as coroutines. Walkthrough.
Lazy Lazy streams are composed by continuations in a functional style
Pipes Coroutines compose streams which connect arbitrarily
TryCatch Exception handling is reimplemented using only CPS
CpsCps Continuations can efficiently call other continuations
Work Implementation of a simple continuation scheduler
LuaCoroutines Coroutines implemented in the style of Lua
ThreadPool 1,000,000 continuations run across all your CPU cores

Demonstration Projects

Here are a few projects which demonstrate CPS library integration.

Smaller

Project Description
WebServer Zevv's "Real World Test" WebServer And More
Background Run any function on a background thread
Passenger Compose graph visualizations of CPS control-flow
HttpLeast A simple web-server for benchmarking CPS
solo5_dispatcher A simple CPS scheduler for Solo5 unikernels

Larger

Project Description
Balls A threaded test runner based upon CPS
Sys Next-generation operating system service abstractions
Actors Zevv's experimental project to create a threaded, share-nothing actor based framework on top of CPS
InsideOut Another experimental concurrency library which supports CPS over threads
Taps A portable, asynchronous, network abstraction library
Syndicate The Syndicated Actor Model for Nim

Debugging

Expectations

See this list of open Nim issues surfaced by CPS development; some repercussions include the following:

  • Exceptions are evaluated differently under panics:on and panics:off, so you may need to use panics:on in order to produce reliably correct code.

  • Expressions are evaluated differently under gc:[ao]rc, so you may need to use those memory managers in order to produce reliably correct code.

  • The cpp backend often doesn't work, particularly due to faulty codegen but also, perhaps, due to exceptions:goto assumptions that we rely upon.

  • var/openArray/varargs parameters to procedures with the cps pragma are not supported.

  • Nim's for loops work, but you cannot perform any CPS control-flow inside of them; if in doubt, use a while loop instead.

Call Syntax

Use --define:cpsNoCallOperator to explicitly disable the () operator.

Performance

If you are not running with define:danger and gc:arc and panics:on then performance considerations really aren't your primary consideration, right?

Tracing

There are two tracing systems that are enabled by default via Nim's built-in stackTrace:on compiler option, which defaults to on outside of release and danger builds.

Stack Frames

Stack semantics are implemented by a single TraceFrame object stored on each continuation and these serve to capture the progress of control-flow through multiple levels of CPS calls just as they do so for normal stack-based code.

The renderStackFrames() and writeStackFrames() procedures return a sequence of strings or write them to the standard message stream, respectively. You can run these procedures without arguments in any continuation.

You can extend the Stack hook to alter its behavior.

Force-enable the stack frame support with --define:cpsStackFrames=on.

Trace Deque

The trace deque system stores the last N hooks executed by the continuation, where N defaults to 4096 (see below). A single continuation has multiple hooks executed during its lifecycle, so these traces can be very detailed.

The renderTraceDeque() and writeTraceDeque() procedures return a sequence of strings or write them to the standard message stream, respectively. You can run these procedures without arguments in any continuation.

You can extend the Trace hook to alter its behavior.

Force-enable the trace deque support with --define:cpsTraceDeque=on and alter the size of the deque with e.g. --define:traceDequeSize=100.

Using cpsDebug

Add --define:cpsDebug=SomePass where SomePass matches one of the CPS transformation passes; this will output Nim codegen corresponding to the rewrite phase. Interesting places to start include the following:

  • cpsTransform
  • cpsResolver
  • cpsJump
  • cpsContinuationJump
  • cpsManageException
  • cpsTryFinally
  • etc.

Note that only one --define:cpsDebug=... can be enabled at a time - multiple defines will use only the final one.

Using trace

Implement trace and it will be called at each continuation leg; see the documentation for details.

Use --define:cpsNoTrace to disable the trace code generation.

License

MIT