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.
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.
"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.
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.
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'
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 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.
Can you recommend some papers on this?
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...
> 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.
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.
I'm guessing you're trying to equate
try{
foo()
}catch(Exception e){
bar(e)
}
void foo() {
throw new exception();
}
(bar (call/cc foo))
(defun foo (cont)
(cont (make-exception))
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?
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..."
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?
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.
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 :)
Get a daily email with the the top stories from Hacker News. No spam, unsubscribe at any time.