Into CPS, Never to Return
bernsteinbear.com
bernsteinbear.com
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...
If it does have state, it’s probably a stack allocated closure…
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.
Alternatives include:
- thread per-client
- thread per-client (but
green threads)
- co-routines
> Update the state object associated with the I/O event in place (and unregister/re-register it with the event loop as needed)?
I have a simple data structure to represent the continuation, which is really more like a closure, consisting of `{fd, data, handler_function}` (this being C). Events are typically one-shots. When queuing I/O I just update the handler_function of that struct and then register the one-shot event with epoll, re-using this "closure" object. When it comes time to close a connection and we're done handling events we free (or, rather, put on a free-list) the closure, and destruct the client data structure.
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.
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!
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.
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!
Instead, the normal loops are used, and the subresults are accumulated in some builder structure which is then finalized to produce a complete tree of a CPS expression. The main trick is to figure out just what this builder structure should be, and it turns out it's a tree zipper of sorts!
The margins of this comment are not big enough to sketch the whole thing but it's actually not as formidable as it sounds ("tree zipper", wooooh): it's mostly just a stack of tree-building instructions which can be easily extended/completed. An alternative would be to have a mutable CPS expression as the result, and keep appending things into it, but it requires lots of tree traversal and lot of care to not accidentally leave the thing in not quite constructed state which is way too easy in my experience.
I think I'll make and publish a gist with it when I get home because I don't believe I've ever seen it done this way anywhere.
The main point of interest is the use of CpsExprBuilder as an accumulator and explicit looping over sub-expressions instead of using meta-continuations, as is popular in most papers on CPS transformations. This is not the only possible way to implement such CpsExprBuilder: another option would be to have a mutable CPS expression with a pointer into it, and gradually grow it. But since you can't just take a pointer to a list's element in Python, you would probably have to keep a whole path (as, say, an array of indexes), and re-traverse the tree every time you append to it, like this:
result = {
'expr': ['let', [['#t0', 2], ['@k0', ['cont', ['#t1'], None]]], ['f', '#t0', '@k0']],
'path': [1, 1, 1, 2],
}
cursor = result['expr']
for index in result['path'][:-1]:
cursor = cursor[index]
cursor[result['path'][-1]] = ['g', '@halt', '#t1']
[0] https://gist.github.com/Joker-vD/7cddcfada042ed486dd74690ae9...
[1] https://www.microsoft.com/en-us/research/wp-content/uploads/...
* Why give literal ints their own temporaries? * Why not support lambda expressions? Is it tricky in this approach or just accidentally missing?
Just following the paper's convention (their justification being that now they only need to substitute variables for variables which is simpler), plus this gist is a trimmed down version of my hobby project which had full-blown algebraic data types: the integers were handled by that case as well. You absolutely can merge "int" case with the "var" case above, and use ints as themselves:
if isinstance(expr, str) or isinstance(expr, int):
result = CpsExprBuilder()
return maybe_tail(result, expr)
> Why not support lambda expressions?
They were missing in your write-up as well :) I just went by your text, and look at the code snippets in it. But adding them looks like this:
if what == 'lambda':
args, body = rest
result = CpsExprBuilder()
tmp_name, ret = gen_tmp(), gen_cont()
fun = ['fun', [*args, ret], cps(body, ret)]
result.add_let_without_body([[tmp_name, fun]])
return maybe_tail(result, tmp_name)
['lambda', ['x'], 'x'] =>
let
#t0 = fun(x, @k1):
$ret @k1(x)
in $ret @halt(#t0)
[['lambda', ['x'], 'x'], 2] =>
let
#t0 = fun(x, @k1):
$ret @k1(x)
#t2 = 2
in #t0(#t2, @halt)
['let', ['f', ['lambda', ['x'], 'x']], ['f', 2]] =>
let
@k0 = cont(f):
let
#t3 = 2
in f(#t3, @halt)
#t1 = fun(x, @k2):
$ret @k2(x)
in $ret @k0(#t1)
[['lambda', ['x'], 'x'], 2] =>
let
#t0 = fun(x, @k1):
$ret @k1(x)
#t2 = 2
in #t0(#t2, @halt)
['let', ['f', ['lambda', ['x'], 'x']], ['f', 2]] =>
let
#t1 = fun(x, @k2):
$ret @k2(x)
#t3 = 2
in #t1(#t3, @halt)
However it sounds like a very portable technique, would be interested to see it.
Just wanted to add that this is very similar to how async/await JavaScript code was compiled for runtimes that didn't support generators back in the day: http://facebook.github.io/regenerator/
But CPS isn't really the state of the art for functional compilers anymore. It's complex for a human to read and hard to optimize. Something like A-normal form is much easier to work with for a compiler intermediate representation
This isn’t identical to floating the call to E inside the “if”, obviously, but would have (within predictable boundaries) the same performance. If this code went through LLVM to produce machine code I suspect it would wind up identical as LLVM will likely rewrite the duplicated call to be outside the “if”.
Let's say E[h] is "if h == 1 then 2 else 3", a is 1, and b is 2. Then before:
if (if x then 1 else 2) == 1 then 2 else 3
After:
if x then (if 1 == 1 then 2 else 3) else (if 2 == 1 then 2 else 3)
which trivially simplifies to if x then 2 else 3
Your proposed rewrite is "let a0 = if x then 1 else 2 in if a0 == 1 then 2 else 3" which is not a simplification at all - it makes the expression longer and actually introduces a variable indirection, making the expression harder to analyze. The call will require some sort of non-local analysis to pierce through the variable and do the duplication and elimination.
if x then
let a0 = a in E a0
else
let a0 = b in E a0
What happens to E isn’t so straightforward. In your example, though, it’s a small expression tree and would just be duplicated inline with the same obvious constant reductions available.
If it’s ‘large’ (heuristically) it might instead be assigned to a “let” binding outside the “if”, to avoid duplicating a large block of code.
CPS should be making that same determination on E.
let
x k = if x then k 1 else k 2
E k h = if h == 1 then k 2 else k 3
in
\k -> x (E k)
let
E k h = if h == 1 then k 2 else k 3
in
\k -> if x then E k 1 else E k 2
\k -> if x then k 2 else k 3
If E were a different expression, perhaps "E h = let F i = if z == i + h then 7 else 8 in if y then F 1 else F 2", then the inlining choice (made twice, here) would be very poor - F would be inlined four times all up, and since "z" is a free variable here there's no constant case/if to fold, and everything would wind up worse.
The ANF transforms should look something like:
let
a0 = if x then 1 else 2
E h = if h == 1 then 2 else 3
in
E a0
let
a0 = if x then 1 else 2
in
if a0 == 1 then 2 else 3
let
a0 = if x then 1 else 2
a1 = a0 == 1
in
if a1 then 2 else 3
let
a0 = case x of { True -> 1; False -> 2 }
a1 = case a0 of { 1 -> True; _ -> False }
in
case a1 of { True -> 2; False -> 3 }
let
a1 = case (case x of { True -> 1; False -> 2 }) of
{ 1 -> True; _ -> False }
in
case a1 of { True -> 2; False -> 3 }
let
a1 = case x of
True -> case 1 of { 1 -> True ; _ -> False }
False -> case 2 of { 1 -> True ; _ -> False }
in
case a1 of { True -> 2; False -> 3 }
let
a1 = case x of { True -> True ; False -> False }
in
case a1 of { True -> 2; False -> 3 }
case x of
True -> case True of { True -> 2; False -> 3 }
False -> case False of { True -> 2; False -> 3}
case x of { True -> 2; False -> 3 }
edit: it looks like there's distinct Core join points now, never mind!
It's somewhat like when Jack Skelington is trying to explain the meaning of Christmas to the residents of Halloween Town[2] and somehow it hasn't stuck yet.
The way I think about it is kind of like software versions. Say you want to do some kind of reproducible software. You can write that your software depends on jazzinator==3.0.0 but that's kind of unsatisfying because it relies either on tools or people to make sure that versions are immutable. It also relies on jazzinator to specify its own dependencies pretty strictly. So maybe you end up inventing the concept of a lockfile to partially solve that problem, but you still have the issue of relying on a third party to not change things up on you.
However, if you can address a library by a name that is computed from its code (a hash), things get interesting. You end up with this tree/DAG of dependencies where every dependency is immutable--you can't change the code without also changing the name. It's a Merkle DAG like Git. You do lose the ability to say things like "above version 2.5"... sort of.
If you also build a ref or tag system (similar to Git refs), you can kinda do normal style versioning on top of this content addressable world. But again, that relies on someone or something (maybe your hash-based store) to keep a map point-version names to hash names.
The other thing that's interesting with scrapscript in particular is since everything is addressable, you can use (sort of implicitly import/download) any value from any other program in a repository readable by you. But no scrapscript implementation fully does this yet, as far as I'm aware. For a fully working system, check out Unison.
Much appreciated!
* https://bernsteinbear.com/blog/scrapscript/
* https://bernsteinbear.com/blog/scrapscript-baseline/
* https://bernsteinbear.com/blog/scrapscript-tricks/
* https://bernsteinbear.com/blog/type-inference/
* https://bernsteinbear.com/blog/row-poly/
and the repo for the main implementation: https://github.com/tekknolagi/scrapscript