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.
Click here for an awesome infographic explaining what CPS is and how our transform works.
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.
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)
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.
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.
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 resultA 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) continuationWe 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
discardCalling 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 continuationThese 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 laterContinuations 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"examples/coroutine.nim (walkthrough): A simple coroutine implementation of coroutines on top of CPS communicating with each other.
See the documentation for the cps module as generated directly from the source.
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.
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.
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 |
Here are a few projects which demonstrate CPS library integration.
| 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 |
| 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 |
See this list of open Nim issues surfaced by CPS development; some repercussions include the following:
-
Exceptions are evaluated differently under
panics:onandpanics:off, so you may need to usepanics:onin 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
cppbackend often doesn't work, particularly due to faulty codegen but also, perhaps, due toexceptions:gotoassumptions that we rely upon. -
var/openArray/varargsparameters to procedures with thecpspragma are not supported. -
Nim's
forloops work, but you cannot perform any CPS control-flow inside of them; if in doubt, use awhileloop instead.
Use --define:cpsNoCallOperator to explicitly disable the () operator.
If you are not running with define:danger and gc:arc and panics:on then
performance considerations really aren't your primary consideration, right?
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 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.
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.
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:
cpsTransformcpsResolvercpsJumpcpsContinuationJumpcpsManageExceptioncpsTryFinally- etc.
Note that only one --define:cpsDebug=... can be enabled at a time - multiple defines will use only the final one.
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.
MIT