I read the recent reddit question about finding the first odd number. I was going to respond with my meager knowledge about continuations that I'm trying to accumulate as I go through The Seasoned Schemer but first I thought I'd test. So after some trial and error I wrote a simple test to compare my continuation with racket's findf (mentioned in the reddit thread). Two things confuse me in the test I wrote. One, why the pasterack run them both equally as fast while my machine ran the continuation from 4 to 20 times slower. Two, if continuations are slower (or the same?) then do the advantages come in when searching trees structures (like The Seasoned Schemer seems to be indicating)? Tangentially, do continuations still work with threading (if I was out of my comfort zone before, there's no telling where I am with this question)? Finally, generally, what are some example use-cases for continuations? I like the idea but findf speed comparatively, its implementation, and my test script (above) threw me off from the speed I thought they were accomplishing.
Check "Applications of Continuations" by Daniel P. Friedman.
Continuations are extensively used "under the hood" to implement other language constructs, such as early returns, exception handling or coroutines (and many others that I don't know about).
For example, in Scheme, there is no language construct equivalent to the "return" statement that is available in other programming languages, but you can use cal/cc to implement it:
(define (early-return n)
(call-with-current-continuation
(lambda (return)
(when (< n 0)
(return -5))
(sqrt n))))
Having call/cc available, allows language designers to experiment with new language constructs without having to modify the language compiler and runtime, which is an advantage.
On the other hand, for the language user or application programmer, using call/cc usually results in code that is more difficult to understand and maintain, and I would suggest you use the higher level constructs available in Racket instead of using call/cc directly.
Alex.
let/ec is often used for this purpose:
(define (early-return n)
(let/ec return
(when (< n 0)
(return -5))
(sqrt n)))
ec is for escape continuation.
The most common use of continuations for me has been in the web server - Continue: Web Applications in Racket is great for how to use them, Web Applications in Racket is a more thorough guide. After some initial trouble, I find continuations incredibly natural and succinct for a lot of web pages.
(Disclaimer: I am not sufficiently aware of all the pros and cons, nor a sufficiently proficient programmer, so what follows are the lessons that I believe I have learned from using continuations -- but they might be pseudo-lessons).
Unfortunately, natural does not mean that it is always appropriate or easy. Using both continuations and a more standard routes-based system for managing state can be a pain and gives you the worst of both worlds if done badly. The problem is that continuations are one way of tracking state that is incredibly convenient -- but it stores the state in the url + memory rather than the (url +) database. If you use both to store state in the same part, brace your parentheses to hold off the bugs.
Thus if you go this way, either use continuations minimally for short transactions that you don't expect to live too long such as a purchase flow or submissions of forms or the like, and use routes predominantly. Or use few routes as initial starting points and go all in on continuations. I am in the all-in camp as much as I can.
If you are interested in using continuations in production with users and sessions, I recommend reading Continuations for Web Development — defn.io by Bogdan, and that you use koyo, which provides protected versions of continuations that play nice with cookies that work around some of the issues of the default continuations. Other issues to look out for are the memory use if you store lots of continuations with lots of bindings; code that is truly mind-bending (often more than macros IMO); interesting bugs, especially when it interacts with parameters, threads, etc (which it will if you are doing web stuff); and a general lack of examples for how to solve standard problems with continuations.
However, as Bogdan writes at the end of his blog post:
That may seem like a lot of “bad”, but all of those points are straightforward tradeoffs that I believe are worth it in the long run given the ergonomics that continuations on the web buy you. Plus, writing code in this way is just so. much. fun!
As Alex wrote. But let me elaborate this, as someone who has played with these things for close to 40 years.
Continuations come in two forms to manipulate the flow of control in programs:
— manually maintained versions, usually via anonymous functions (or objects), with occasional language support (monads in Haskell)
— language-supported objects, usually via control operators such as `call/cc`, `prompt`,` or `control` (see racket/control)
Thirty years ago, OS researchers noticed that they were manipulating flow of control via manually maintained continuations (via function pointers and records); indeed they were maintaining prompt-delimited continuations. Twenty years ago, a widely spread example of the first one was found in web scripts using the CGI interface. For the past decade, JavaScript programmers had to manually construct continuations to resume “processes” after an event got handled.
People trained in the use of control operators recognize this pattern immediately and, in a language that support control operators, can build abstractions that eliminate the error-prone, manual maintenance of lambda-coded continuations. The PLT Web Server is an example of a system that supports a carefully designed abstraction layer that eliminates the CGI induced manual continuation problem. The Mach 4 operating system is an example that relies on dealing with delimited continuations. Their use of C made it somewhat difficult to build the abstraction properly, though setlong jmp and such tools make it possible. (The group moved to MS from CMU as it worked on this OS, and they did use the ideas — unsuccessfully, from what I understand — in a release of Windows in the early 00s.)
Once people in design-oriented PLs figure out a good abstraction, other language implementors tend to adopt some version of it. This is how Python got generators. It’s how JS gets new features all the time (see async).
This is and should be the way new abstractions come about. If you think of the design space of sequential languages as a multi-dimensional space — with concepts such as binding, state, and control as the dimensions — then operators such as set! and call/cc form a basis. Just like people working with vector spaces, PL designers should not use the basis that randomly came about but the basis that is good for their problem. Sadly people have very little imagination of how to abstract over state manipulation, and thus set! and its := = <- friends are still around (probably due to our friends in Algorithms). The control world is much richer than that (probably because the same friends don’t really care about flow of control). You can find threads (pre-emptive and scheduled), coroutines, signal handing systems, generators, and so on in many PLs — and all of them can be implemented with call/cc and its colleagues. The Web and mobile gateways are likely to generate more such abstractions, but it will take some time for the dust to settle.
Just because a feature can be implemented as a combination of others does not mean, however, that it should be done this way. Direct (often called “primitive” support) gives compiler writes much better ideas for optimizing passes. As some have noticed, call/cc is (conceptual and performant) overkill for function returns; use let/ec instead.
For call/cc, Chez Scheme supports this feature with the best asymptotic cost in the Scheme world. SML/NJ’s approach is cheaper still, if you embrace the idea that memory is dirt cheap and essentially infinite. (I don’t know whether even Andrew still accepts this.) Racket’s control library is an example of how a pretty-cheap call/cc can become a somewhat more expensive call/cc on the language that runs on top of it. Racket/BC demonstrates just how expensive call/cc is if you think compiling thru C with the stack intact is a good idea.
Perhaps this helps — Matthias
About delimited continuation, I found Kenichi Asai's Delimited Continuations for Everyone is very helpful if you can read SML.
Note that the delimited continuation in this video is just single-prompt. Racket supports multi-prompts, which is more powerful (e.g. It can solve the problem of different effects interference with each other).
All these answers were very helpful! I tried to "like" the ones that I found especially good. I guess I'm supposed to pick a "Solution". I'll give it a shot. I also found the video Continuations: The Swiss Army Knife of Flow Control - YouTube helpful. Personally I like the idea of using continuations on the web. I'm hoping to get more into designing languages but that seems like a third job at this point. Thanks again all!
I like this talk by @jeapostrophe, I think it gives a lot of interesting perspectives:
When running it on your machine, did you save it to a separate file then run "racket ./myprok.rkt"? Just running it from DrRacket/REPL is prone to issues with performance because it keeps a bunch of stack information around. I suspect in this case the recursive function in combination with continuation tracking is the culprit.
Where continuations start to become a performance issue is if you are using features like generators that are creating and restoring many continuations.
Thank you for reading the whole question and investigating possible solutions to the slowness as well as expanding on the answers to the underlying continuation performance and usability of continuations.
After your suggestion I did run it at the terminal:
cpu time: 58 real time: 58 gc time: 54
cpu time: 3 real time: 3 gc time: 0
I then compiled it (Type: Stand-alone; Base: Racket) and it only improved slightly:
cpu time: 56 real time: 56 gc time: 53
cpu time: 3 real time: 3 gc time: 0
I'm still not getting the results of the pasterack times I got before.
This is a great paper. I'm still working through it but wouldn't have found it for a long time without you!
I tried it out on my machine and I'm getting the same times as you are. Maybe pasterack was running it quickly enough that the differences weren't apparent? However, I was able to optimize your find-first function by using for.
(define (find-first2 predicate? things)
(let/ec return
(for ([ele (in-list things)])
(when (predicate? ele)
(return ele)))
'()))
It still runs slower than findf, but it runs faster than the recursive version with continuations (let/ec vs call-with-continuation didn't make much performance difference). The for version runs about x2 slower than findf, but the recursive version runs about x6 times slower.
The reason I mentioned continuations for something like findf is that I find verifying find-first2 much easier than find-first. In fact, find-first has a bug. It gives a contract violation when no match exists such as '(2 4 6 8). I also find that it is really easy to accidentally right an infinite loop with recursion compared to a Racket for loop.
I'd be interested to know precisely why continuations perform like this? I've tested a few hypotheses, but I haven't been able to figure out why find-first is so much slower than find-first2. I tried both avoiding creating a closure inside of let/ec and using a continuation with findf to return the value (instead of relying on normal control flow), but the first experiment was still slow and the latter was still fast.
(time
(let/ec return
(findf (λ (ele) (if (odd? ele) (return ele) #f)) long-range)))
which still ran pretty fast (about as fast as find-first2) so continuations plus recursion alone aren't the culprit. Below is the example which avoid creating any closures.
(define (find-first-helper predicate? remaining got-it)
(let ([one-to-check (car remaining)])
(cond [(null? remaining) (got-it '())]
[(predicate? one-to-check) (got-it one-to-check)]
[else (find-first-helper predicate? (cdr remaining) got-it)])))
(define (find-first3 predicate? things)
(let/ec got-it
(find-first-helper predicate? things got-it)))
And of course find-first3 replicates the bug (contract-violation) present in the original, illustrating one of your points.