5 ms·

In case anyone is wondering, "when would I EVER use this (in hand-written code)?", it's a trick that makes DSL (domain specific language) and small language imp

In case anyone is wondering, "when would I EVER use this (in hand-written code)?", it's a trick that makes DSL (domain specific language) and small language implementation much easier. A great reference for this is Peter Norvig's Paradigms of Artificial Intelligence Programming, when he implements a subset of Prolog and bolsters the functionality using CPS[1]. The second, although more obscure, is that you can use it in languages that do not have "non-local exits" to terminate a deeply nested computation early or return to an earlier point in the call stack. For example, Clojure does not have nonlocal exits, as only the final form of the function is returned. However, using CPS, you can terminate the expression early and return to the original caller without executing the rest of the function. You probably only want to use this in specialized cases though or it may upset your team, they are tricky to debug. Lastly and probably most controversially, you can make an extensible "if" statement using CPS if you are in a dynamic language and you have no other tools to do so. Admittedly I do sometimes use this in ClojureScript. This allows you to write "append only" code without continually growing the "cond". Again, most teams don't like this, so it depends on the circumstances, but might be nice to have in your back pocket if you need it. [1]: https://github.com/norvig/paip-lisp/blob/main/docs/chapter12.md#compiling-logic-programs https://github.com/norvig/paip-lisp/blob/main/docs/chapter12...

remexre 2y ago
It's also really helpful with defunctionalization; search "defunctionalize the continuation" for stuff on that
Vetch 2y ago
I've also used it to make a function tail recursive, which is useful in languages with TCO.
- codebje 2y ago
  If your continuation has no state to hold your recursion should already be tail called. If it does have state, it’s probably a stack allocated closure…
cryptonector 2y ago
I've used something similar to CPS in async I/O programs, where at each point that a function wants more I/O it queues up a continuation for the event and then returns to the event loop. This forces one to represent state in a compact way and to use very little stack space for state representation, all of which reduces per-client memory footprint a great deal.
- upghost 2y ago
  hey that's really clever. was this for open source or commercial? was it received well? what language? Very interesting technique
  - cryptonector 2y ago
    > was this for open source or commercial? Proprietary, though I have permission to open source it (but I need to make sure that $WORK picks a license for it). This was specifically for a poor man's Kafka as an HTTP server that implements "tail -f" semantics for GET when using `Range:` with the end offset left unspecified, and with `{URI, weak-ETag, offset}` resembling the Kafka `{topic, partition, offset}`. Non-range requests end when EOF is reached in the file being fetched. Range requests with the end offset specified end as soon as the requested range has been sent back. Range requests with the end offset left unspecified do not end until the file is unlinked or renamed away, using inotify to detect those cases, and every time data is written to the file that data is immediately sent to the clients that are waiting "at the tail". The connection acceptor in the event loop creates a client record and queues reads to call the reader continuation which is just `{client, reader}`, then when a request is fully read the reader continuation will queue up a writer continuation to write the response, and so on. The fact that the underlying abstraction is "just a file" makes this very easy to use because `write(2)` is how you publish data and `rename(2)` and `unlink(2)` is how you "commit transactions" / roll logs in your application, and clients immediately find out. All that completely asynchronously with how the data gets served. You can even script an application, like using bash, since `echo foo >> some_file` is how you publish data. It's extremely useful. > what language? C, specifically for Linux, using epoll and inotify. The server is multi-processed, with each process single-threaded, and it spawns NPROC workers (or however many you specify). But naturally this would work very well in Rust, C++, etc., and it could be multi-threaded instead of multi-processed. > Very interesting technique It's just C10K with a dash of CPS :) In this particular program the sequence of events is pretty linear. Since the progression is fairly linear all the continuation functions are one next to the other and one can just read them linearly. This makes the code quite readable.
joe_the_user 2y ago
In case anyone is wondering, "when would I EVER use this (in hand-written code)?", it's a trick that makes DSL (domain specific language) and small language implementation much easier. Sure but that's still saying "this only gets used implementing a language". And that's OK because the continuation construct (A half-executed function passed to another function, wtf) seems like something I'd be horrified to find in the code of a normal application.
- codebje 2y ago
  Callbacks with closures are continuations with bad syntax. Admittedly one could call those horrifying without being accused widely of hyperbole, so it’s not a great counter to your point.
- upghost 2y ago
  I'm not disagreeing with you. The three examples I mentioned were specifically about overcoming the limitations presented by some runtimes. If you have to reach for these, typically you know you are already swimming upstream. But sometimes the price of adopting a new tool is more expensive than using a specialized (hopefully well documented) application of CPS on the existing infrastructure. In the second example, for instance, you could throw an exception that gets caught higher up the stack. And in fact, that's often how call/cc with lexically scoped continuations are implemented in languages that do not support first class continuations. In that case, it really comes down to how you and your team feel about "exceptions as flow control". Of course, exception-based flow control doesn't help in situations where you are deeply recursing and have a limited stack. This is where "trampolining" using CPS is very effective. Typically languages implementing this go out of their way to hide the CPS though, because most people react to seeing it the way you did. And I don't blame them, it's pretty horrifying as you said!
cma 2y ago
CPS continuation-passing style
mattalex 2y ago
This is essentially the principle behind algebraic effects (which, in practice, do get implemented as delimited continuations): When you have an impure effect (e.g. check a database, generate a random number, write to a file, nondeterministic choices,...), instead of directly implementing the impure action, you instead have a symbol e.g "read", "generate number", ... When executing the function, you also provide a context of "interpreters" that map the symbol to whatever action you want. This is very useful, since the actual business logic can be analyzed in an isolated way. For instance, if you want to test your application you can use a dummy interpreter for "check database" that returns whatever values you need for testing, but without needing to go to an actual SQL database. It also allows you to switch backends rather easily: If your database uses the symbols "read", "write", "delete" then you just need to implement those calls in your backend. If you want to formally prove properties of your code, you can also do that by noting the properties of your symbols, e.g. `∀ key. read (delete key) = None`. Since you always capture the symbol using an interpreter, you can also do fancy things like dynamically overriding the interpreter: To implement a seeded random number generator, you can have an interpreter that always overrides itself using the new seed. The interpreter would look something like this ``` Pseudorandom_interpreter(seed)(argument, continuation): rnd, new_seed <- generate_pseudorandom(seed, argument) with Pseudorandom_interpreter(new_seed): continuation(rnd) ``` You can clearly see the continuation passing style and the power of self-overriding your own interpreter. In fact, this is a nice way of handeling state in a pure way: Just put something other than new_seed into the new interpreter. If you want to debug a state machine, you can use an interpreter like this ``` replace_state_interpreter(state)(new_state, continuation): with replace_state_interpreter(new_state ++ state): continuation(head state) ``` To trace the state. This way the "state" always holds the entire history of state changes, which can be very nice for debugging. During deployment, you can then replace use a different interpreter ``` replace_state_interpreter(state)(new_state, continuation): with replace_state_interpreter(new_state): continuation(state) ``` which just holds the current state.
- upghost 2y ago
  That's really interesting. This seems like it would be a really good approach to combine something like an otherwise pure finite state machine, but with state transitions that rely on communicating with external systems. Normally I emit tokens to a stack which are consumed by an interpreter but then it's a bit awkward to feed the results back into the FSM, it feels like decoupling just for the sake of decoupling even though the systems need to be maintained in parallel. I'll have to explore this approach, thank you!

remexre 2y ago

It's also really helpful with defunctionalization; search "defunctionalize the continuation" for stuff on that

Vetch 2y ago

I've also used it to make a function tail recursive, which is useful in languages with TCO.

codebje 2y ago
If your continuation has no state to hold your recursion should already be tail called. If it does have state, it’s probably a stack allocated closure…

cryptonector 2y ago

I've used something similar to CPS in async I/O programs, where at each point that a function wants more I/O it queues up a continuation for the event and then returns to the event loop. This forces one to represent state in a compact way and to use very little stack space for state representation, all of which reduces per-client memory footprint a great deal.

upghost 2y ago
hey that's really clever. was this for open source or commercial? was it received well? what language? Very interesting technique
- cryptonector 2y ago
  > was this for open source or commercial? Proprietary, though I have permission to open source it (but I need to make sure that $WORK picks a license for it). This was specifically for a poor man's Kafka as an HTTP server that implements "tail -f" semantics for GET when using `Range:` with the end offset left unspecified, and with `{URI, weak-ETag, offset}` resembling the Kafka `{topic, partition, offset}`. Non-range requests end when EOF is reached in the file being fetched. Range requests with the end offset specified end as soon as the requested range has been sent back. Range requests with the end offset left unspecified do not end until the file is unlinked or renamed away, using inotify to detect those cases, and every time data is written to the file that data is immediately sent to the clients that are waiting "at the tail". The connection acceptor in the event loop creates a client record and queues reads to call the reader continuation which is just `{client, reader}`, then when a request is fully read the reader continuation will queue up a writer continuation to write the response, and so on. The fact that the underlying abstraction is "just a file" makes this very easy to use because `write(2)` is how you publish data and `rename(2)` and `unlink(2)` is how you "commit transactions" / roll logs in your application, and clients immediately find out. All that completely asynchronously with how the data gets served. You can even script an application, like using bash, since `echo foo >> some_file` is how you publish data. It's extremely useful. > what language? C, specifically for Linux, using epoll and inotify. The server is multi-processed, with each process single-threaded, and it spawns NPROC workers (or however many you specify). But naturally this would work very well in Rust, C++, etc., and it could be multi-threaded instead of multi-processed. > Very interesting technique It's just C10K with a dash of CPS :) In this particular program the sequence of events is pretty linear. Since the progression is fairly linear all the continuation functions are one next to the other and one can just read them linearly. This makes the code quite readable.

joe_the_user 2y ago

In case anyone is wondering, "when would I EVER use this (in hand-written code)?", it's a trick that makes DSL (domain specific language) and small language implementation much easier. Sure but that's still saying "this only gets used implementing a language". And that's OK because the continuation construct (A half-executed function passed to another function, wtf) seems like something I'd be horrified to find in the code of a normal application.

codebje 2y ago
Callbacks with closures are continuations with bad syntax. Admittedly one could call those horrifying without being accused widely of hyperbole, so it’s not a great counter to your point.
upghost 2y ago
I'm not disagreeing with you. The three examples I mentioned were specifically about overcoming the limitations presented by some runtimes. If you have to reach for these, typically you know you are already swimming upstream. But sometimes the price of adopting a new tool is more expensive than using a specialized (hopefully well documented) application of CPS on the existing infrastructure. In the second example, for instance, you could throw an exception that gets caught higher up the stack. And in fact, that's often how call/cc with lexically scoped continuations are implemented in languages that do not support first class continuations. In that case, it really comes down to how you and your team feel about "exceptions as flow control". Of course, exception-based flow control doesn't help in situations where you are deeply recursing and have a limited stack. This is where "trampolining" using CPS is very effective. Typically languages implementing this go out of their way to hide the CPS though, because most people react to seeing it the way you did. And I don't blame them, it's pretty horrifying as you said!

cma 2y ago

CPS continuation-passing style

mattalex 2y ago

This is essentially the principle behind algebraic effects (which, in practice, do get implemented as delimited continuations): When you have an impure effect (e.g. check a database, generate a random number, write to a file, nondeterministic choices,...), instead of directly implementing the impure action, you instead have a symbol e.g "read", "generate number", ... When executing the function, you also provide a context of "interpreters" that map the symbol to whatever action you want. This is very useful, since the actual business logic can be analyzed in an isolated way. For instance, if you want to test your application you can use a dummy interpreter for "check database" that returns whatever values you need for testing, but without needing to go to an actual SQL database. It also allows you to switch backends rather easily: If your database uses the symbols "read", "write", "delete" then you just need to implement those calls in your backend. If you want to formally prove properties of your code, you can also do that by noting the properties of your symbols, e.g. `∀ key. read (delete key) = None`. Since you always capture the symbol using an interpreter, you can also do fancy things like dynamically overriding the interpreter: To implement a seeded random number generator, you can have an interpreter that always overrides itself using the new seed. The interpreter would look something like this ``` Pseudorandom_interpreter(seed)(argument, continuation): rnd, new_seed <- generate_pseudorandom(seed, argument) with Pseudorandom_interpreter(new_seed): continuation(rnd) ``` You can clearly see the continuation passing style and the power of self-overriding your own interpreter. In fact, this is a nice way of handeling state in a pure way: Just put something other than new_seed into the new interpreter. If you want to debug a state machine, you can use an interpreter like this ``` replace_state_interpreter(state)(new_state, continuation): with replace_state_interpreter(new_state ++ state): continuation(head state) ``` To trace the state. This way the "state" always holds the entire history of state changes, which can be very nice for debugging. During deployment, you can then replace use a different interpreter ``` replace_state_interpreter(state)(new_state, continuation): with replace_state_interpreter(new_state): continuation(state) ``` which just holds the current state.

upghost 2y ago
That's really interesting. This seems like it would be a really good approach to combine something like an otherwise pure finite state machine, but with state transitions that rely on communicating with external systems. Normally I emit tokens to a stack which are consumed by an interpreter but then it's a bit awkward to feed the results back into the FSM, it feels like decoupling just for the sake of decoupling even though the systems need to be maintained in parallel. I'll have to explore this approach, thank you!