Hacker News new | past | comments | ask | show | jobs | submit login
Beautiful ideas in programming: generators and continuations (hhyu.org)
185 points by lukastyrychtr on Aug 3, 2021 | hide | past | favorite | 104 comments



Generators 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)


>> 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.

It's a real disappointment that Python has no answer for JavaScript fat arrow.

The fat arrow is the one construct that completely changes the structure of all the programs I write - it makes things extremely terse and I use it in nearly every function/method in some way.

I'm a big fan of Python's whitespace structure but it seems to be an obstacle to creating single line functions that are both powerful and get multiple things done, which sometimes makes a program easier to read and more understandable. Sure there's lambda functions but I find them clumsy and hard to work with compared to the beauty of the fat arrow.


The rare case where you do need a fat arrow, it is indeed elegant once misses from Python.

But I also know by experience that people from other languages are reaching for anonymous functions way too often instead of using the tools that are suitable for the use case in python.

E.G: if you use a lot of map() and filter() in python, you are doing it wrong.


> 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.

Maybe - but at the same time, generators are side-effectful and quite general. That means, when someone uses a generator, now I have to understand what happens by looking at the code. If someone uses a promise or a closure/lambda, then the scope of what can happen is much more limited.

It's like looping vs. mapping. You can use "for ... in ..." syntax or you can do "map(..., ...)" but I generally prefer the latter (minus the syntax overhead in python), simply because I easily see at a glance what the intend is.


Generators are such a game-changer for clean separation of data traversal from data processing. It's my favorite trick in python and I miss it dearly in other languages.

In languages without generators it's easy to write code that traverses some data structure in hard-coded way and does something configurable on every node, but it's hard to write code that traverses a data structure in configurable way and does some hardcoded thing on every element.

In Python it's trivial both ways and even both at once.


> it's hard to write code that traverses a data structure in configurable way and does some hardcoded thing on every element

Wouldn’t this just be a function that operates on an iterator? I suppose generators make the creation of lazy iterators easier, but generally the solution for languages without generators is to have your traversal build a list. So you lose the laziness but the code remains simple. Then map your per-node processing to the list.


> generally the solution for languages without generators is to have your traversal build a list

Yes, but then you move from O(1) to O(n) in memory usage. And if you want to optimize it you have to restructure your code, when in python lists and generators are drop-in replacements.


Also, producing a list doesn't work very well as a substitute for infinite generators.


Until you want to walk the generator twice -- stateful generators are a design flaw, in my opinion.


The C++20 coroutines has the potential of being this and much more. As with many things C++, its adoption will be very slow (they are supported by latest compiler versions, but there is no support in the standard libraries yet).


> It's my favorite trick in python and I miss it dearly in other languages.

Which other languages? Generator support is common:

https://en.m.wikipedia.org/wiki/Generator_(computer_programm...


This list really sort of stretches the imagination on what language level generator support looks like.

Certainly in Java you can use the `Iterator` interface to get generator like behavior. But that's both a whole lot more complex and more verbose. Primarily because you have to coordinate the `hasNext` method with the `next` method.

With python and yield syntax, that naturally falls out without a bunch of extra code juggling.


Sure, some of those (C, Java, C++ templates) are pretty weak, but C#, Ruby, ES6, and lots of the other language or library implementations are not. Its far from a unique Python feature.


Java methods like Stream#filter and Stream#flatMap are easier than rolling your own iterator; you can even ask that work be done in parallel.


"In Haskell, with its lazy evaluation model, everything is a generator"


It’s also trivial and easy in Haskell — you just need an instance of `Foldable` or `Traversable` on your collection, and then you can fold or traverse it in a configurable way. Or for recursive structures, use https://hackage.haskell.org/package/recursion-schemes. Or even just pass a traversal function as an argument for maximum flexibility.


How absent is generator support in languages in general? As far as I know, even PHP has had yield for something like a decade, and JS for longer (at least as far back as 2006, when Yield Prolog got discussed on LTU[0]). Or is there something about the Python approach to generators that's distinctive?

[0] http://lambda-the-ultimate.org/node/1732


Language tends to converge on good features, luckily.

Although some generator implementations are not as complete as python ones, and the ecosystem generally donc have much support for it

E.g : Very few languages have an equivalent to itertools.


The Ecmascript 4 proposal included the `yield` keyword, but the proposal as a whole was abandoned in 2008. That’s why the version names jump from ES3 to ES5. Some of the features then returned in later versions, including generators with ES6 in 2015.


This sounds interesting. An example would really be helpful, I have a vague idea of what you're talking about but have a hard time concretizing it.


You have (psuedo)code like this:

    def print_every_file_in(root_path):
       for path in children(root_path):
           if is_file(path):
              print("file: " + path + ", size:" + get_size(path))
           else:
              print_every_file_in(root_path)
If you want to extract the printing part it's trivial in any language:

    def print_file(path):
       print("file: " + path + ", size:" + get_size(path))

    def print_every_file_in(root_path):
       for path in children(root_path):
           if is_file(path):
              print_file(path)
           else:
              print_every_file_in(path)
And you can easily parametrize what function to call on each node.

But in Python it's equally trivial to extract the traversal:

     def every_file_in_path(root_path):
       for path in children(root_path):
           if is_file(path):
              yield path
           else:
              yield from every_file_in_path(path)

     def print_every_file_in(root_path):
        for file in every_file_in_path(root_path):
           print("file: " + path + ", size:" + get_size(path))
or even extract both:

     def print_every_file_in(root_path):
        for file in every_file_in_path(root_path):
           print_file(file)
which for me is a very clean way to implement this and it's nontrivial to do in languages without generators.


A big problem with many of these features is that they almost always end up getting used in ways that makes the code more convoluted when there are simpler alternatives.

needing to store state - use a class

needing lazy evalutaion - use a class (though this is a common enough use case to be a primitive, e.g. Kotlin)

decorators - if you pass decorated methods around -> now you have to remember the context the methods hold. Instead, refactor your code to be more direct so that you don't need decorators.

type hints - they are not fully enforceable at compile time, unless everything in your codebase has type hints. This is never the case and type hints can easily lull you into a false sense of security.

functools module - generally I'm ok with this but sonetimes you have to be aware of when you need to deep copy vs when you don't etc.


I don't know many languages, do decorators show up in any others? I _love_ them in Python.


In C#:

    static IEnumerable<int> Fibonacci()  
    {  
        int first = 0;  
        int second = 1;  
      
        yield return first;  
        yield return second;  
      
        while (true)  
        {  
            (first, second) = (second, second + first);  
            yield return second;  
        }  
    }


Interesting use of tuples I had never considered before, a lot of state is packed in that `(first, second)...` block! Pretty fun though.


Emacs Lisp* has a system called "advice" that's maybe a bit clumsier than Python's, but is also more powerful. The relationship between decorator and decorated [is configurable][0]. For example, the decorated function could be called conditionally on the result of applying the decorator to the arguments, something like:

   def _combined(args):
     return decorator(args) and original(args)
It can also be applied retroactively, not just at the decorated function's definition. This is extremely handy in the context of configuring your text editor, but I admit I wouldn't like it in a program I was working on with other people. (Basically a form of monkeypatching.)

* Granted not really used for general-purpose programming like Python.

[0]:https://www.gnu.org/software/emacs/manual/html_node/elisp/Ad...


Emacs Lisp has macros which are a lot more elegant (not to mention powerful) than Python decorators which comparatively, are nothing more than a kludge.


Depends on what you mean. I often hear claims that you can use decorators in language X, which are formally true, since decorator is just a function accepting and returning another function, so any language that has anonymous functions (which is a lot of languages by now) "has decorators". But for me this is kind of false marketing, because there's nothing impressive about that, and the killer feature of Python's decorators is the syntactic sugar, which makes them so easy to use. And in this sense not so many languages "have decorators". You can do something similar with annotations in PHP, but I've never actually done this in a real project, because that feels like abusing the language.


Yes. 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.


Decorators are still a pending proposal in ECMAScript, so they would only be available to transpilers. That makes them non-standard until the proposal is approved, where the implementation could change.


How do Python generators differ from JavaScript generators?


Yield from comes to mind.


Isn't JS yield* the same as yield from in Python


Unless I'm mistaken, it propagate pulling, but not pushing with send(). I haven't checked though.


One thing that really annoys me about PySpark is Python's lack of tuple unpacking in lambdas. It turns what should be relatively readable pipelines of transformations into an unreadable mess.


Alas, Python 2 had tuple unpacking, but they removed it in Python 3 :(


One 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_mo...


They are particularly nice when processing a recursive datastructure such as a tree. The technique can make for some very short and readeable code.


I like them for building VMs quickly


Do you have any example code?


Interesting 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?


They are related. You can specify effects with monads (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


I 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.


> 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.


I 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.


> 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.


I edited that sentence when I forgot the 'not' but I missed removing the 'un'. Yes, shift and reset, delimited continuations were not mentioned.


Can you recommend some papers on this?


Oleg has written a lot about this: http://okmij.org/ftp/continuations/

you can also google "oliver danvy delimited continuations" or "felleisen delimited continuations"


I 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.


Posix 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

[1] http://www.devdoc.net/c/boost-1.65.1/libs/context/doc/html/c...

[2] https://github.com/pmderodat/ada-generators


> 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.)


This is quite similar to an unsafe use of a variable in a thread, and would have the same consequences.

You have to make certain assumptions about the nature of the program as compiled, if those assumptions are wrong, poof!


The problem in this case is that the assumptions will be wrong for any nontrivial program. (Edit: pedantically, any nontrivial use of continuations in a program.)


Related to this space is algebraic effects [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.


For those who don't know, @yelouafi is the original author of redux-saga.


Do 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.


From a high level, iterators are basically just generators (which themselves are just simple continuations). Rust is a good example since pretty much all looping is done via iterators, and most implementations of the Iterator[0] trait look similar to the examples in the article. If you squint hard, calling `iter.next()` in Rust is just like the Scheme example, where you're continuously calling the generator function to get the next value. So, the people who use Rust at their day job definitely use (a form of) continuations at their day jobs.

[0]: https://doc.rust-lang.org/std/iter/trait.Iterator.html


Well one could argue that any strucured process with more than one thing/node will embed a continuation to connect the two parts.


They show up often in writing interpreters. If you find yourself writing a parser / interpreter for a domain specific language, a good way to approach it is often to build the chain of commands to evaluate as a hierarchy of continuations.

Otherwise, you may find yourself having to implement break, continue, and return using the exception system in your implementing language, and that can end up being either aesthetically unpleasing or downright messy (I painted myself into a corner once writing an evaluation engine in Go and, to meet a deadline, implemented break using panic and recover!).


I'm using them with SimPy, a discrete event simulation library. It took me some time to understand how it works (not an expert) but I finally managed to simulate several operations of an assembly process. It really made think of concurrency and shared state. I think it's cool to know about this stuff, and I'll probably recognize when to use it in future situations.


Exception handlers are continuations.


I 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.


I 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.


Even resumable exceptions are/can be much more bounded than continuations. Exceptions always respect the scope structure of the code (even though they can jump between scope levels), whereas continuations can break this arbitrarily.

In particular, in Common Lisp, restarts are only valid in the dynamic environment where they were created by restart-bind. In contrast, call/cc captures this dynamic environment and makes it available later. You can't store restarts and invoke them later the way you can with call/cc.


In 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".


You can get the stack trace by breaking in "throw". Maybe you meant something else.


Breakpoints on throw are triggered before unwinding (you are effectively setting a breakpoint on the function called to unwind).

You simply cannot create a stack trace from within a C++ exception handler because that state is gone. Hence my argument that exceptions are not a continuation, there is nothing to continue.


All true. But also a bit of a diversion, because the information you wanted "from within" the exception handler is available at the throw site. Ergo, if you're trying to get it from within the handler, you're just trying to get it from the wrong place.


I'm guessing you're trying to equate

  try{
    foo()
  }catch(Exception e){
    bar(e)
  }
  
  void foo() {
    throw new exception();
  }
with

  (bar (call/cc foo))

  (defun foo (cont)
    (cont (make-exception))
However, this ignores most details of the problem. In fact, (re-entrant) continuations and exceptions can't be mixed in the same language: Common Lisp has not adopted `call/cc` for one because it's impossible or at least much harder to implement `unwind-protect` (`finally`) in the presence of `call/cc` [0].

The major difference is that continuations allow you to do this:

  (defparam *global*)
  (defparam *shadow-list* (list))
  (defun foo (cont)
    (setf *global* cont))
  (with-open-file (f "~/file.log")
    (loop
      for line = (read-line stream nil 'eof)
      until (eq line 'eof)
      collect (cons line (call/cc foo)))

  (*global* *shadow-list*)
  (*global* *shadow-list*) ;; what is the state of the file here? what if there was an exception reading from the file?
[0] https://groups.google.com/g/comp.lang.lisp/c/1Ggl_BUi3Yg/m/V...


Naw, it's not impossible; you just use dynamic-wind. But to me this has a bit of the spirit of "Now, you have two problems..."


Well, dynamic-wind itself does not do what unwind-protect does. You have to manually "save/resume" the dynamic environment with the after/before clauses of dynamic-wind.

To be fair, it's probably relatively easy to use dynamic-wind to raise some runtime error when trying to resume the continuation after the original context "ended".


It doesn't, no, but yes, that was my thought: write a version of with-open-file implemented in terms of dynamic-wind that raises a runtime error if you try to reenter. Better hope people are using call/cc for exception handling and not threading though...

Pitman's comments on this are in http://www.nhplace.com/kent/PFAQ/unwind-protect-vs-continuat..., Sitaram's response is at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.79.3..., and Pitman's final response is at http://www.nhplace.com/kent/PFAQ/unwind-protect-vs-continuat....


I have seen exceptions implemented with setjmp/longjmp, and I have seen continuations implemented with setjmp/longjmp/memcpy. So they are definitely related, but equivalent? Or are you saying something else?


Go coroutines (and any implementation of stackfull coroutines) are equivalent to one-shot continuations.


Go doesn't have coroutines-the-flow-control-construct. It has goroutines, which are lightweight preemptively scheduled threads. You can, on top of this thing, arrange for a bunch of goroutines only one of which is not blocked at a time, which is a bit like having coroutines, but probably involves more synchronization code than a typical implementation of coroutines-the-flow-control-construct.


Well channels do randez-vous, conceptually similar yield. Having only one coroutine running at any time is really not required.

Disclaimer: I have never written a line of Go in my life.



A 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.


> 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.


Seems like the standard definition of concurrent to me. Concurrency is a programming model, not an execution model. It means writing multiple pieces of code in a simple linear model that can have their execution interleaved with execution of other code. The primary contrast is managing a complex state machine by hand. coughNodecough

Given that concurrency is often implemented with a state machine, the difference is not what happens at run time. The difference is the programming model used.

Parallel execution is a fully separate matter.


That's really interesting. Perhaps the gap in my knowledge is the difference between programming model and execution model.

But let me ask another question: What's the difference between yielding from a function and returning? Why is yielding considered concurrent programming and returning sequential?

I guess I had associated concurrent programming with threads but maybe multi-threaded programming is better called parallel execution?


A programming model is what the programmer has to think about in order to write a program.

Brainfuck probably has the simplest model I can think of - you have an instruction pointer referring to the next byte in the program to execute, and a flat array of memory cells that program instructions may read and write. Every command in the language is about working with those two elements.

C has a much more complex model consisting of statements that are stepped through, functions that may be called (including recursively) with parameters, local variables, global variables, static local variables, constness vs mutability, pointer types, names for symbolic access to those things... And probably a lot more that I've neglected.

Concurrency is a thing that might be part of a programming model where you are allowed to interleave execution of multiple logical workflows but still write each logical workflow as a single unit of code. The programming model model tells you what properties you are guaranteed to get.

An execution model is something that describes implementation of a programming model. A related example is how concurrency is implemented in a particular system. Is it multiple threads running simultaneously? Is it a complex state machine jumping between logical workflows as demanded by their semantics? Is it an even-more-complex m:n model involving both threads and state machines?

Execution models aren't irrelevant to programming. They can have a significant impact on performance and edge-case behavior that the programming model doesn't clearly specify. But you should be able to write programs with only the programming model in mind and get correct code in most circumstances. (I'd call it a specification failure if you can't.)

A programming model describes the tools the programmers have available, their semantics and interactions. An execution model describes how those things run on the hardware that is present.


Concurrent usually refers to any kind of control flow in which separate (logical) threads of execution can be interleaved, and where the particular interleaving can affect the final result. For example, event systems are inherently concurrent, even if they are single threaded: the order of events affects normally affects the final state of the system (for example, if you receive a request to SET X=0 and a request to INCREMENT X, the final result may be 0 or 1 depending on the order, even if you have a single thread of execution actually handling the events).

In contrast, parallel programming usually refers to program flows where multiple instruction streams can be interleaved arbitrarily without changing the final result. For example, when using mapping a pure function on a list, the execution of the function for each element of the list can be executed in parallel without any concurrency.

Alternatively, parallel execution can refer to any case where multiple instruction streams are actually executed in parallel, regardless of their order.

Concurrency often has pitfalls even with single-threaded execution models. For example, if two generators share some common state, even if they are executed in a single thread, the final result depends on how they are used and may be unexpected.


I don't think there is a gap in your knowledge so much as a clash in terminology between different (programming) communities. What the Go community here is referring to as "concurrency" sounds to me like the traditional definition of "multithreading", while "parallel execution" meets the definition I've seen before for "concurrency". This was probably done to distinguish operating-system threads (preemptive multitasking, possibly involving multiple CPU cores) from asynchronous application code (user-mode cooperative multitasking on a single core), but to me a form of "concurrency" without concurrent execution, i.e. operations from different threads executing in parallel at the same time, seems like a contradiction.


Return terminates the function or thread of execution. Yield (may) provides a value but leaves the thread of execution alone otherwise, only pausing it. It’s resumable where a return is not (without a lot of extra bookkeeping).

https://blog.golang.org/waza-talk

A good talk that expresses the current sentiment and helped establish it. Concurrency may be parallel, but doesn’t need to be. This does go against the common (outside programming) notion of the meaning of concurrent which means it provides a strong potential for confusion.


Equivalently, both yield and return invoke the calling function continuation, but while return discards the current one, yield saves it somewhere for resumption.


You are thinking of “parallel”. This is a fine usage of concurrent.


I would say concurrency is more of a way of organizing code into independent parts.

If you have multiple contexts, logically separable, and they can execute independently you end up with some form of concurrent design.

The reason people often think of coroutines (like generators resuming) vs routines (functions) as concurrent vs not concurrent has everything to do with contexts that can be thought of as executing in a non-deterministic order. Certainly there might be external dependencies that "force" an ordering to execution, but at the end of the day, it's the independence of an operation/computation that makes it concurrent with another.

Concurrency can give rise to opportunities for things to execute in parallel, but it does not require them. Parallelism is therefore a condition of execution/evaluation.

On a uniprocessor unix kernel, processes execute concurrently. On a multiproccessor unix kernel, you hope for parallel execution of processes (though they may be totally unrelated in context or goal), but you always maintain the concurrency. The scheduler pauses and switches contexts.

The ability to switch contexts seems fairly equivalent to concurrency. And I don't think much else is needed.

I'm not sure that's 100% correct, but it's how I like to think of this situation.


So 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.


I 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.


Ah, 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 :)


Can 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)))


First 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


The 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.


I'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."


Article 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.


Look up iterator, __next__, __iter__.


Right, thanks!


I 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.


When implementing Python's yield in scheme, I found it straightforward to add the equivalent of send!

https://billsix.github.io/bug#_make_generator


In 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.


This 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.


It’s just a goto with state…




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: