6 ms·
Into CPS, Never to Return
- psyclobe 2y ago[flagged]
- tekknolagi 2y agoNo, and in fact internet searching for continuation-passing style stuff is quite tricky for this reason :(
- deleted 2y ago[deleted]
- upghost 2y agoIn 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 agoIt's also really helpful with defunctionalization; search "defunctionalize the continuation" for stuff on that
- Vetch 2y agoI've also used it to make a function tail recursive, which is useful in languages with TCO.
- codebje 2y agoIf 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 agoI'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 agohey 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.
- _zoltan_ 2y agoI thought I'm going to read a piece about US's Child Protective Services, and clicked. Was a letdown :-)
- TapamN 2y agoI was hoping, but not expecting, for it to be about the Capcom arcade board.
- MobiusHorizons 2y agoI was pleased to see something properly technical, given that that is the supposed focus of this forum. I Hadn't ever heard of CPS as an IR, only SSA, and it was very interesting to learn about it.
- cryptonector 2y agoCPS is a predecessor technique to SSA, essentially.
- tekknolagi 2y agoFunnily enough, both CPS and SSA are US government services
- assbuttbuttass 2y agoCPS is a cool technique, and makes advanced constructs like call/cc trivial to implement. Using CPS techniques in code can feel like magic. 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 https://en.wikipedia.org/wiki/A-normal_form https://en.wikipedia.org/wiki/A-normal_form
- Mathnerd314 2y agoIf you think ANF is great then explain how to deal with the transformation from "E (if x then a else b)" to "if x then E a else E b".
- codebje 2y agoANF transform will rewrite that to “let a0 = if x then an else b in E a0”. 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”.
- Mathnerd314 2y agoWhat? 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.
- codebje 2y agoThe ANF form is amenable to rewriting the “if” outside the “let”. if x then let a0 = a in E a0 else let a0 = b in E a0 If a and b are simple variables or constants the new “let”s will be eliminated by ANF. 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.
- childintime 2y agoThe author references [scrapscript](https://scrapscript.org/ https://scrapscript.org/), hopefully we'll hear more about it.
- tekknolagi 2y agoSee my other blog posts and GitHub if you would like some more!
- upghost 2y agoI realize this is something I should probably know but I've never been able to pin down a definition nor have I used a language with this feature -- could you maybe explain what a "content addressable language" is and why that is important? It seems like it's really important but I have no idea why. You explain it here[1] but it's somewhat brief. I realize it probably should be self-evident why it's important but it's not clicking for me. 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. [1]: https://scrapscript.org/#ContentAddressibleEverything https://scrapscript.org/#ContentAddressibleEverything [2]: https://youtu.be/l6QZUcRJw-A https://youtu.be/l6QZUcRJw-A
- tekknolagi 2y agoTo be clear, I am not Taylor and I did not come up with scrapscript! That website belongs to him and I'm just a random guy on the internet who emailed him and built an implementation. 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.
- fovc 2y agoIt’s also useful in typed languages to introduce an existentially quantified type
- guerrilla 2y agoWhere do you recommend reading more on this? I've always wanted to understand that better. From what I understand continuations are dual to functions (of universally quantified types). It would be cool to complete the symmetry, for the aesthetics.
- fovc 2y agoMaybe this? https://www.cis.upenn.edu/~bcpierce/tapl/ https://www.cis.upenn.edu/~bcpierce/tapl/
- yapyap 2y agonot gonna lie this title made me think this was gonna be some child protective services horror story or something
- draw_down 2y ago[dead]
- purplesyringa 2y ago> If you don’t want to do any of this trampoline stuff, you can also do the One Big Switch approach which stuffs each of the funs and conts into a case in a massive switch statement. Calls become gotos. 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/ http://facebook.github.io/regenerator/
- Joker_vD 2y agoThere is actually a way to produce CPS without lots of administrative redexes, which uses the same main trick that "higher-order transform" utilizes: tracking the whether the expression being transformed is in tail context or general context, and translating accordingly — but without using meta-continuations because boy are those mind-boggling. 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.
- tekknolagi 2y agoPlease show this gist. I would enjoy linking to it
- Joker_vD 2y agoOkay, there it is: [0]. It mostly implements a version of CPS transform from "Compiling with Continuations, Continued" by A. Kennedy [1], figure 8. Two main differences in the output language from the one in your post is that, first, this version binds everything to temporaries (including literals and continuations), and second, it uses "let" (with multiple definitions, so it's actually "let*") as the primary name-binding feature instead of immediate application. And I use name "$ret" instead of "$call-cont". 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'] I've tried this approach, and even when it's encapsulated in a class, it's way too easy to accidentally end up with a random None somewhere deep inside your resulting expression. So instead, the expression's tree is turned inside out, so to speak. It's similar to using an explicit stack instead of using recursion. [0] https://gist.github.com/Joker-vD/7cddcfada042ed486dd74690ae986101 https://gist.github.com/Joker-vD/7cddcfada042ed486dd74690ae9... [1] https://www.microsoft.com/en-us/research/wp-content/uploads/2007/10/compilingwithcontinuationscontinued.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...