13 ms·
Beautiful ideas in programming: generators and continuations
- Zababa 5y agoInteresting article. I knew the name "continuations", and "call/cc", but not exactly what they were, so thanks for clarifying that. Continuations seem pretty close to what I understand from algebraic effects. Are there big differences between the two? Are they the same thing? Is one a subset of the other?
- anchpop 5y agoThey are related. You can specify effects with monads (http://goto.ucsd.edu/~nvazou/koka/icfp15.pdf http://goto.ucsd.edu/~nvazou/koka/icfp15.pdf for example), and continuations can be expressed with monads (and therefore as an effect). I believe monads and effects are more general than continuations though. I’m not an expert so don’t quote me haha
- compressedgas 5y agoI think that they are each expressible with the other. Monadic reflection can be implemented with continuations. Effects, specifically effect handlers, can be implemented with delimited continuations which weren't mentioned in this article. Delimited continuations and undelimited continuations can implement each other. Both undelimited continuations and delimited continuations can be implemented as a monad. The main issue with all of this and why effects exist and why monads and delimited continuations aren't enough has to do with the fact that delimited continuations can't be easily type checked and monads aren't open for extension. I did not like that undelimited continuations were not mentioned. They are so much easier to understand than call/cc continuations as they are the rectification of some segment of the return stack as a function which when called returns through that segment and then to the caller like a regular function.
- ashton314 5y agoCan you recommend some papers on this?
- manu3000 5y agoOleg has written a lot about this: http://okmij.org/ftp/continuations/ http://okmij.org/ftp/continuations/ you can also google "oliver danvy delimited continuations" or "felleisen delimited continuations"
- hencq 5y ago> I did not like that undelimited continuations were not mentioned. call/cc continuations are undelimited continuations right? It sounds like you're talking about call/ec, escape continuations or one-shot continuations. They're essentially longjmp in C.
- compressedgas 5y agoI meant delimited. However copy and paste had other plans. All of call/cc, call/ec, call/1cc are effectively jumps to a saved stack. (The difference between these is that the first can be used more than once and both to enter and exit. The second can only be used to exit. The third can only be used once.) shift is instead captures the return stack up to the first reset and forms a function out of it that when called runs the rest of each of the frames before returning to the caller of that created function.
- a1369209993 5y ago> I did not like that undelimited continuations were not mentioned. They are so much easier to understand than call/cc continuations as they are the rectification of some segment of the return stack as a function which when called returns through that segment and then to the caller like a regular function. I think you mean delimited continuations? "Undelimited continuations" is call/cc.
- compressedgas 5y ago
- mikewarot 5y agoI did continuations back in 1987, in Turbo Pascal, but I didn't know it until today. I wrote a cooperative multi-tasking library to support some things I needed to have happen at the same time in MS-DOS. The first time my procedure "fork" returned twice, it took me a while to wrap my head around it. I don't see why you couldn't implement continuations in modern Free Pascal/Lazarus, all you really have to do is make a copy of the stack(using the heap), then adjust BP and SP, everything else on the stack is relative to those two registers.
- touisteur 5y agoPosix has getcontext / setcontext and you can probably use/bind pcl [0] to wrap that properly. Boost has boost::context [1]. For an example of a binding to pcl you can look up ada-generators [2] which I use heavily (but am not the author). I've hard a hard time using continuations in languages with not-total capture. Ada has package variables (similar to singleton without the headache) that are not captured by call/cc libraries... There's also the secondary stack (specific to GNAT, not sure) for functions that return objects of unknown size at call site, which also are a pain to capture/restore... Good luck with those. I think continuations, to be really footgun-less, need to be integrated in the language & runtime, so that when you need to serialize the current state you can 'capture all the things'. A bit like python with its generator/automaton approach. [0] http://www.xmailserver.org/libpcl.html http://www.xmailserver.org/libpcl.html [1] http://www.devdoc.net/c/boost-1.65.1/libs/context/doc/html/context/cc.html http://www.devdoc.net/c/boost-1.65.1/libs/context/doc/html/c... [2] https://github.com/pmderodat/ada-generators https://github.com/pmderodat/ada-generators
- a1369209993 5y ago> I don't see why you couldn't implement continuations in modern Free Pascal/Lazarus, all you really have to do is make a copy of the stack(using the heap), then adjust BP and SP, everything else on the stack is relative to those two registers. Easy-to-understand but nonsystematic counterexample: what happens when the stack contains a pointer to dynamically allocated memory? If you shallow copy it, you have a double free. If you deep copy it, how? Do you even know how much memory to allocate? What if it's a file descriptor instead? (Fork only works because the OS can blindly duplicate the entire process and everything in it, and even then you have problems like IO buffers.)
- BiteCode_dev 5y agoGenerators are one of the concepts that devs from other languages under use in Python. It's a natural solution to a ton of problems, since it lazily evaluates, and only stores one result out of the entire sequence at a time, and its interface is compatible with the iterator protocol. It's a mini state machine with it's own little memory world as well. If you are used to call backs, promises, tick() calls or closures, it will be natural to reach for them a lot, and be disappointed at their state in the Python ecosystem. But while I do miss better anonymous functions support sometimes in Python, it is rarely a problem because it comes with other tools to arrive to the same result. Generators are one of them. Of course, you'll have to realize that generators are way more that a lazy way of generating data. You can use them for control flow, hold state, hide complexity or delegate behavior using a common interface. The send() method is very often completely ignored by most devs, and the yield from underused. But beyond generators are a lot more things that, in the same vein, will bring you to python enlightenment once you start thinking with them instead of trying to make a Python fits into a square hole: - the functools module - the itertools module - context managers - any/all/zip/iter/next/enumerate - decorators (it can do so much more than you imagine) - type hints (take a look at fast api for awesomeness)
- drcongo 5y agoI don't know many languages, do decorators show up in any others? I _love_ them in Python.
- BiteCode_dev 5y agoYes. In fact, E.G: C# and JS have them, although they don't have exactly the same features. edit, sorry I've meant generators. Incidentally, it's also true for js decorators.
- k__ 5y agoHow do Python generators differ from JavaScript generators?
- 5y ago
- agumonkey 5y agoDo people use conts in day jobs ? It seemed to me that beside niche fp or implementation of async, kanren,etc people rarely used them. Not criticizing the concept just trying to assess the real world usage.
- bordercases 5y agoIf lower levels of the stack used them then more people would use them. https://www.cs.cornell.edu/people/egs/papers/trickles-tocs.pdf https://www.cs.cornell.edu/people/egs/papers/trickles-tocs.p... https://thelackthereof.org/docs/library/cs/continuations.pdf https://thelackthereof.org/docs/library/cs/continuations.pdf
- useerup 5y agoException handlers are continuations.
- formerly_proven 5y agoI don't think they are, unless you are talking about the few implementations of resumable exceptions. The most obvious counter-example I can think of is C++, where the stack from where the exception was thrown is unwound to the handler, i.e. it's destroyed (doubly so if the exception handler puts anything on the stack). That's also why you can't get a stacktrace from an exception in C++ unless you specifically arranged for the thrower to include that information in the exception object.
- toolslive 5y agoIn continuation passing style, a compiler technique, exceptions show up quite naturally as a second continuation. The whole thing is called "Double barrelled continuation passing style".
- miloignis 5y agoI believe exceptions are equivalent to a limited form of continuations called escape continuations where control flow can only go upwards (which is the stack unwinding). Note that this is also true of break and continue, actually, both of which can be implemented with either exceptions or escape continuations.
- intrepidhero 5y ago> But very briefly, yield in Python is often presented as a simplified method for writing generators, but what it does, suspending the execution of a function with the ability to resume it, is a much general concept than iteration. It enable a routine to do a small amount of work, and then pass the control to another routine, thus allowing them to run concurrently. I don't think that is what concurrently means. Generators allow interleaved execution or lazy evaluation. In fact the author makes this point further down so I think the above sentence was just a slip of the pen. But I point it out because that very misunderstanding is one that tripped me up for a time. > More accurately, yield in a function creates a generator, which suspends its execution at the point where yield appears in the definition. That's better.
- vanderZwan 5y agoSo what do you think concurrently means? For the record, the quoted explanation you disagree with fits Esterel and other data-flow languages perfectly, and nobody will deny that they are (synchronous) concurrent languages.
- intrepidhero 5y agoI thought it meant that two streams of instructions could be executed simultaneously. I thought it meant I needed to start worrying about shared/private memory and locks and things. Python's generators are handy for in that kind of program but not necessary. But it sounds like from the replies I was wrong.
- vanderZwan 5y agoAh, so a variation of the classic "concurrency vs paralellism" misconception. In your defense: it's considered a classic misconception for a reason, so I wouldn't feel to bad about it :)
- jtsiskin 5y agoYou are thinking of “parallel”. This is a fine usage of concurrent.
- shadowgovt 5y agoRelated to this space is algebraic effects [https://gist.github.com/yelouafi/57825fdd223e5337ba0cd2b6ed757f53 https://gist.github.com/yelouafi/57825fdd223e5337ba0cd2b6ed7...], which is the construct I'm most excited about these days. Very few languages I know offer direct support for them, but they inspire the pattern of Hooks in React functional components.
- ducaale 5y agoFor those who don't know, @yelouafi is the original author of redux-saga.
- dmux 5y agoCan anyone explain in a little more detail what's going on in the definition of the Scheme version of sum-of-squares? The previous example where the continuation of 2 + 1 + N is captured makes sense to me, but I'm having a hard time wrapping my head around the resulting continuation when a lambda is involved. To make it a little cleaner, I've replaced the "receiver" definition with a function reference instead. What's the continuation here? (define sum-of-squares (lambda (bound) (call/cc the-receiver)))
- valbaca 5y agoThe sum-of-squares isn't a continuation, rather it just loops through the squared-ints generator up to the bound. call/cc is used to allow some form control and allow the loop to exit > Before the sum-of-square function does anything, I use call/cc to capture the continuation, and assign it to the variable break. Notice that in the syntax of Scheme, this is the last step of the function. Therefore, calling break will immediately exist the function with a returned value, no matter where it is called.
- dmux 5y agoI've reread the quote you posted and think I may understand, although I'm probably misusing some terminology: since the call to call/cc is the only thing in the lambda definition, the continuation captured at that point is kind of the termination/return point of the function. If there was something after the call/cc, e.g. a (display "Done with looping") then invoking the continuation would break out of the loop and display "Done with looping."
- simiones 5y agoFirst of all, (define foo (lambda (args) body)) is just the Scheme idiom for defining functions. It's normally written `(define (foo args) body)` or Python `def foo(args): body`. In a little more detail, let's take a function that looks like this; I'll use the shorter syntax to avoid line noise: (define (sum-of-squares bound) 0) (print (sum-of-squares 100)) ;; prints "0" Now let's see what happens with a continuation: (define (sum-of-squares bound) (call/cc the-receiver)) ;; will return whatever is passed to current continuation ;; for now, it will jump to the receiver, passing the whole call stack to it (define (the-receiver cont) (cont 18)) (sum-of-squares 100) ;; will start executing sum-of-squares, then jump to the-receiver, passing it the call stack ;; then, the-receiver will jump back into sum-of-squares, replacing the value of the whole `call/cc` form with the value 18 ;; which will be returned to the top level This use is similar to the following Python code: def sum_of_squares(bound): try: the_receiver() except MyContinuation as e: return e.Value def the_receiver(): raise MyContinuation(18) To show some more power of what this can do, let's save the continuation to a global var and call it a few times: (define some-continuation '()) (define (sum-of-squares bound) (call/cc the-receiver)) ;; will return whatever is passed to current continuation ;; for now, it will jump to the receiver, passing the whole call stack to it (define (the-receiver cont) (set! some-continuation cont)) ;; the receiver stores the value of cont into some-continuation and returns control to the top level. ;; at this point, sum-of-squares and anything that was calling it has NOT finished executing: ;; it's frozen in the continuation (display (sum-of-squares 100)) ;;sets some-continuation to the continuation, doesn't print anything (some-continuation 18) ;; prints 18 (some-continuation 200) ;; prints 200 (display (+ 100 (sum-of-squares 100))) ;;sets some-continuation to a new vale, doesn't print anything (some-continuation 18) ;; prints 118 (some-continuation 200) ;; prints 300
- adamnemecek 5y agoI have been thinking about continuations recently in the context of GUIs. Has the idea been explored much? I feel like e.g. dragging things in a list should be a nice match for this but I couldn't quite figure out how to do it myself and I couldn't find any literature.
- narag 5y agoThis article sounds very familiar. I'm sure to have read an article about the very same two languages' constructs a long time ago. It's dated this year, but I wonder if the author could be recycling an old text.
- fjfaase 5y agoIn C# it is very simple to implement a generator using the 'yield return' and 'yield break' statements. Also LINQ is based on generators, allowing you to write rather complex queries with relatively compact code.
- prashnts 5y agoArticle briefly mentions: > Using yield in a function definition is not the only way in which generators can be constructed in Python Anyone can point out what do they mean by that? Googling didn’t help much.
- sherjilozair 5y agoLook up iterator, __next__, __iter__.
- prashnts 5y agoRight, thanks!
- deleted 5y ago[deleted]
- math-dev 5y agoIt’s just a goto with state…
- mr_sturd 5y agoA bit tangential, but I feel the author's pain when he says; > I skipped the entire chapter because I couldn’t understand what continuations were good for. I found that was the case when first learning other concepts in programming. It's not until you experience working on bigger projects where you find some tools become useful, and examples in the books are sometimes to concise to express their true power.
- animal_spirits 5y agoOne of the most fascinating uses of generators I've come across is a recursive generator >>> def count_binary(): ... yield "1" ... for prefix in count_binary(): ... yield prefix + "0" ... yield prefix + "1" ... >>> cb = count_binary() >>> next(cb) '1' >>> next(cb) '10' >>> next(cb) '11' >>> next(cb) '101' [0] https://www.reddit.com/r/Python/comments/ovjubg/whats_the_most_simple_elegant_piece_of_python/h7ab7ki/ https://www.reddit.com/r/Python/comments/ovjubg/whats_the_mo...
- nestorD 5y agoThey are particularly nice when processing a recursive datastructure such as a tree. The technique can make for some very short and readeable code.
- kderbyma 5y agoI like them for building VMs quickly
- ianandrich 5y agoDo you have any example code?
- billsix 5y agoWhen implementing Python's yield in scheme, I found it straightforward to add the equivalent of send! https://billsix.github.io/bug#_make_generator https://billsix.github.io/bug#_make_generator