It’s kind of mindblowing in terms of how much attention to detail you need to put into a seemingly simple language feature to make it Just Work. Often times when I use a ForEach function in C++ I miss being able to do a non-local return, yet in Go they Just Work. And they even have a non-local defer. Amazing stuff.
struct SomeContainer
{
void ForEach(function<void(int)> yield)
{
for (int i = 0; i < 10; ++i) {
yield(i);
}
}
};
I don’t think there’s a way to turn this sort of API into something compatible with ranged for loops… So other than throwing an exception (mentioned in a sibling comment) there is, to my knowledge, no way to do a non-local return from inside the lambda passed to yield.
I don’t think there’s a way to turn this sort of API into something compatible with ranged for loops. […] no way to do a non-local return from inside the lambda passed to yield.
No, what you would do is exactly what Go does: add abruption to the loop (probably in a shape more similar to Rust’s try_fold as that’s a lot more generic). Hell you could probably even use dark template magic over that to hide the abruption support when not needed.
Or you’d just integrate with the language’s own facilities by returning a range and having the caller use either std::for_each or a range-based loop depending on the capabilities they require.
Unless I misunderstand your intent, I think this is what co_return and std::generator are for.
EDIT: I believe I did misunderstand your intent haha. std::longjmp or Boost.LEAF might be useful there. Propagating out of sum-types with monadic functions, like what std::execution does with senders/receivers, might also express something similar.
The author manages to make extremely heavy weather of this topic, somehow. It’s not really as strange, complicated, or unusual as he thinks or wants to make out that it is. (The rather condescending title suggests the latter.)
Go iterators are not called “rangefuncs”; they’re called “iterators”. They’re what Python people would call “generators”: functions that can maintain their state while periodically yielding new values. This is a useful feature, but you need coroutines, which is why not every language has them (though there are efforts to bring them to Rust).
Pull iterators are neat too, and you can trivially turn a push iterator into a pull iterator. Anyway, users who just want to consume an iterator don’t need to know or care what kind it is, or even that there’s an iterator involved.
I don’t think the post was meant to shine a negative light on Go’s iterators—I read it more as being fascinated with a cool and unusual implementation of a feature rather than being condescending about it. What’s wrong with finding something cool and writing a post about how cool you think it is?
I do think the author is right about it being unusual, in the fact that it has no magic syntax other than for x := range f, which already existed in Go in the first place. I’m not familiar with Python generators, but in JavaScript you need special function* and yield syntax to declare generators, where in Go it’s just the usual func you’re already used to.
Go iterators are not called “rangefuncs”; they’re called “iterators”. They’re what Python people would call “generators”: functions that can maintain their state while periodically yielding new values.
Generators in Python are yielding and suspending. They are basically like lightweight coroutines. Rangefuncs are not that, they are mostly normal functions. Go will use coroutines internally (which are otherwise non exposed) to convert push style iterators from rangefuncs to python style generators.
Personally I find what go does pretty odd, because it feels rather foreign to how the language otherwise operates. I’m sure they have a reason why they did it that way, but the hidden behind the scenes coroutine stuff is pretty untypical. I’m unaware of other languages that went down that particular path of converting push style iterators. Ruby sort of does, with the Enumerator system, but that uses fibers which are a core language feature of the language to perform that conversion.
Go doesn’t use coroutines internally for range over functions, iter.Pull (which is never automatic) uses them to turn an internal iterator into a pull iterator.
Incidentally, this points to a terminology problem that, as far as I understand things, was created by Russ Cox for no real reason: what Go calls “push iterators” are just normal internal iterators, which don’t have much to do with the push/pull streaming interfaces parser people have been talking about for decades. Push and pull form a short hierarchy of flexibility where making a pull interface out of a push interface is easy, but going the other way is hard. If you put internal iterators in this hierarchy they’d be at the less flexible end: you can make an internal iterator out of anything, and it’s impossible to promote an internal iterator to either of the others without some sort of context switching mechanism. I think this is a useful way to think about streaming interfaces and Go has made it needlessly difficult to talk about by naming renaming one end of the spectrum to be the same as the other end.
But back to the point. I think it’s pretty clear how you could reason yourself into this:
External pull iterators are easy to consume, but tricky to implement
Internal iterators are easy to implement, but tricky to consume
Converting an internal iterator to a pull iterator requires continuations, coroutines, or something else equivalent in power to one of those
But a for loop doesn’t use the extra power of a pull interface anyway, and can be rewritten to use internal iteration with some fiddly details but no control-inverting magic
I’m not entirely sure how I feel about this, and I don’t see myself writing much Go by choice either way so it doesn’t really matter, but writing this out has mostly convinced me that it’s a sound decision.
External pull iterators are easy to consume, but tricky to implement
Sort of, it really depends on the affordances in the language. I would argue that external iterators are trivial to implement if you have generators in the language or something similar. And go sort-of is required to do that anyways, just hidden behind the iter.Pull interface. There is another world in which they could have added generators. The odd thing is that iterator combinators in go really need to use iter.Pull and now you’re in a rather odd spot where there is some “magic” in the stdlib that you cannot replicate yourself.
Does anyone have an explanation as to why Go implemented iterators this way? I read the original proposal and this post, and neither of them offer a satisfying explaination why this implementation of iterators was chosen over the IMO much simpler version the author mentioned up front: type Iter[T any] = func() (T, bool)
I think that’s basically what the author meant by: “Using push iterators by default means that users ‘only’ need to write an ordinary for loop packaged into a function.”
One consideration could be performance. Iterators are really hot, so you don’t want the .next() to be a virtual call, which needs to move the iteration state between the registers and memory on every step.
If you are C++ or Rust, you can solve the problem by making your entire iteration protocol statically dispatched and hammering the compiler until it can reliably inline and SROA iterators.
If you are Java, then you have jit which doesn’t care at all about static function boundaries. A JIT sees a hot loop as a dynamically looping sequence of byte-code instructions, it really doesn’t care if there are some call or callvirtual instructions in between.
If you are Python, you are so slow that you genuinely don’t care about tight loops, or rather, you move the entire tight loop in C, and operate on numpy arrays in Python.
If you are Go, well, you don’t have compile-time destroying monomorphisation like Rust and C++, you also don’t get runtime speculative devirtualization like Java, and you are supposed to be much faster than Python!
But there’s this one weird trick where you can do internal iteration without a bunch of full virtual calls and without inlining/with separate compilation: you can reserver the stack space for the lambda you are passing into the internal iterator on the iterator’s caller stack frame. Not sure if Go does this already, but with the goroutine/coroutine stuff it is already doing, that would be a rather straightforward extension.
From what I can tell none of the posts that lead up to the design of go’s iterators mentioned performance. It has been seen as the better approach for the user of the language. See for instance this quote:
The vast majority of the time, push iterators are more convenient to implement and to use, because setup and teardown can be done around the yield calls rather than having to implement those as separate operations and then expose them to the caller. Direct use (including with a range loop) of the push iterator requires giving up storing any data in control flow, so individual clients may occasionally want a pull iterator instead. Any such code can trivially call Pull and defer stop.
My guess would be that the actual iterator interface allows for cleanup: if yield returns false (in case of a break or return), you get an opportunity to cleanup resources inside the iterator. I don’t think you could do it with this interface, but maybe I’m wrong
my main takeaway from this article is that nobody should use proto3 protobufs :D. some of the iterator deep diving was fun too, but i’m far too dense to understand most of the details. i can see why mcyoung likes Rust with a brain like theirs, haha.
TFA really abuses the expression “non-local” into meaninglessness. Their own desugaring literally shows Go just stashes the value in a local of the parent frame, the entire thing is a collaboration between frames in the desugaring. There’s no non-local return, Go won’t let you return through a caller the way e.g. Smalltalk actually does.
For this reason, I wish that Go had instead defined something along these lines. […] I don’t think there’s an easy way to patch this up, at this point.
Not using an interface was a major requirement point of the rangefuncs proposal, because the desugaring of range loops is entirely based on concrete types. Not the only one, but it was very much a motivator for using an internal-style.
Disclaimer: I am not going to dig into Go’s rationale for rangefuncs. Knowing how the sausage is made, most big Go proposals are a mix of understandable reasoning and less reasonable veiled post-hoc justification to compensate for either Google planning/approvals weirdness or because the design was some principal engineer’s pony.
As a not-fan of Go and not convinced by the use of internal iteration, I actually found the rangefuncs proposal pretty objective, it had its bias but I ended up with the idea push iterators were probably the better thing for the language (and I don’t think it even made the strongest case for it as IIRC it didn’t touch on optimisation / efficiency).
I think that rangefuncs are easy to learn in the way Go needs them to be. If you expect more users to want to write rangefuncs than users want to write complicated uses of rangefuncs, I think push iterators are the easiest to learn how to use.
That’s cope. Internal iterators are unusual and unfamiliar.
External iterators require a bit more setup but they’re way more intuitive and familiar to the average user, it’s how the vast majority of languages work, the desugaring is obvious, and it’s how you’d do iteration in your average procedural language as well.
This is very interesting to me because I’ve recently developed by Bluefin effect system for Haskell, which comes with both push iterators and pull iterators (called Stream and Consume – perhaps “Stream” should be called “Produce”). There’s a way of connecting them together (”consumeStream”) which is basically the same as the article’s “mechanism for converting push iterators into pull iterators” (I wouldn’t say it turns one to the other actually, I’d say it “connects” one of each type, but it depends on exactly what you mean, I guess). Like Go’s equivalent, it uses green threads to implement “concurrency without parallelism”. It’s interesting to see that both designs have converged!
find ::
e :> es =>
Consume e (Maybe a) ->
a ->
Eff es Bool
find haystack needle = withEarlyReturn $ \ret -> forever $ do
item <- await haystack
case item of
Nothing -> returnEarly False
Just item ->
when (item == needle) (returnEarly True)
And a “push” iterator is “internal”, and when a loop desugars to Bluefin’s forEach of a stream operation
inOrder ::
e :> es =>
Tree ->
Stream e Tree ->
Eff es Bool
inOrder t y = do
case left t of
Nothing -> pure ()
Just theLeft -> inOrder y theLeft
yield y t
case right t of
Nothing -> pure ()
Just theRight -> inOrder y theRight
It’s kind of mindblowing in terms of how much attention to detail you need to put into a seemingly simple language feature to make it Just Work. Often times when I use a
ForEachfunction in C++ I miss being able to do a non-local return, yet in Go they Just Work. And they even have a non-localdefer. Amazing stuff.you can though ?
The overhead of exceptions seems much higher than what Go does, + Unreal Engine doesn’t enable exceptions on all platforms.
Exceptions are not supposed to be used for control flow.
I’d rather see exceptions than setjmp / longjmp though.
Can’t you just pass the thing to a normal range loop? It’s not like you need
ForEach?If that doesn’t work in C++ it’s a problem with C++ (which it usually is). It works just fine in C#, or Rust, or probably Ruby or JS.
By
ForEachI mean this type of construct:I don’t think there’s a way to turn this sort of API into something compatible with ranged for loops… So other than throwing an exception (mentioned in a sibling comment) there is, to my knowledge, no way to do a non-local return from inside the lambda passed to
yield.No, what you would do is exactly what Go does: add abruption to the loop (probably in a shape more similar to Rust’s
try_foldas that’s a lot more generic). Hell you could probably even use dark template magic over that to hide the abruption support when not needed.Or you’d just integrate with the language’s own facilities by returning a range and having the caller use either
std::for_eachor a range-based loop depending on the capabilities they require.Unless I misunderstand your intent, I think this is what
co_returnandstd::generatorare for.EDIT: I believe I did misunderstand your intent haha.
std::longjmpor Boost.LEAF might be useful there. Propagating out of sum-types with monadic functions, like whatstd::executiondoes with senders/receivers, might also express something similar.[Comment removed by author]
The author manages to make extremely heavy weather of this topic, somehow. It’s not really as strange, complicated, or unusual as he thinks or wants to make out that it is. (The rather condescending title suggests the latter.)
Go iterators are not called “rangefuncs”; they’re called “iterators”. They’re what Python people would call “generators”: functions that can maintain their state while periodically yielding new values. This is a useful feature, but you need coroutines, which is why not every language has them (though there are efforts to bring them to Rust).
Pull iterators are neat too, and you can trivially turn a push iterator into a pull iterator. Anyway, users who just want to consume an iterator don’t need to know or care what kind it is, or even that there’s an iterator involved.
I don’t think the post was meant to shine a negative light on Go’s iterators—I read it more as being fascinated with a cool and unusual implementation of a feature rather than being condescending about it. What’s wrong with finding something cool and writing a post about how cool you think it is?
I do think the author is right about it being unusual, in the fact that it has no magic syntax other than
for x := range f, which already existed in Go in the first place. I’m not familiar with Python generators, but in JavaScript you need specialfunction*andyieldsyntax to declare generators, where in Go it’s just the usualfuncyou’re already used to.Yeah, I was going in ready to be annoyed but I was pleasantly surprised.
Generators in Python are yielding and suspending. They are basically like lightweight coroutines. Rangefuncs are not that, they are mostly normal functions. Go will use coroutines internally (which are otherwise non exposed) to convert push style iterators from rangefuncs to python style generators.
Personally I find what go does pretty odd, because it feels rather foreign to how the language otherwise operates. I’m sure they have a reason why they did it that way, but the hidden behind the scenes coroutine stuff is pretty untypical. I’m unaware of other languages that went down that particular path of converting push style iterators. Ruby sort of does, with the
Enumeratorsystem, but that uses fibers which are a core language feature of the language to perform that conversion.Go doesn’t use coroutines internally for range over functions, iter.Pull (which is never automatic) uses them to turn an internal iterator into a pull iterator.
Incidentally, this points to a terminology problem that, as far as I understand things, was created by Russ Cox for no real reason: what Go calls “push iterators” are just normal internal iterators, which don’t have much to do with the push/pull streaming interfaces parser people have been talking about for decades. Push and pull form a short hierarchy of flexibility where making a pull interface out of a push interface is easy, but going the other way is hard. If you put internal iterators in this hierarchy they’d be at the less flexible end: you can make an internal iterator out of anything, and it’s impossible to promote an internal iterator to either of the others without some sort of context switching mechanism. I think this is a useful way to think about streaming interfaces and Go has made it needlessly difficult to talk about by naming renaming one end of the spectrum to be the same as the other end.
But back to the point. I think it’s pretty clear how you could reason yourself into this:
I’m not entirely sure how I feel about this, and I don’t see myself writing much Go by choice either way so it doesn’t really matter, but writing this out has mostly convinced me that it’s a sound decision.
Sort of, it really depends on the affordances in the language. I would argue that external iterators are trivial to implement if you have generators in the language or something similar. And go sort-of is required to do that anyways, just hidden behind the
iter.Pullinterface. There is another world in which they could have added generators. The odd thing is that iterator combinators in go really need to useiter.Pulland now you’re in a rather odd spot where there is some “magic” in the stdlib that you cannot replicate yourself.That was what the GOEXPERIMENT setting was called to enable them in Go 1.22.
Does anyone have an explanation as to why Go implemented iterators this way? I read the original proposal and this post, and neither of them offer a satisfying explaination why this implementation of iterators was chosen over the IMO much simpler version the author mentioned up front:
type Iter[T any] = func() (T, bool)If I had to guess, probably this: Storing Data in Control Flow
I think that’s basically what the author meant by: “Using push iterators by default means that users ‘only’ need to write an ordinary for loop packaged into a function.”
One consideration could be performance. Iterators are really hot, so you don’t want the
.next()to be a virtual call, which needs to move the iteration state between the registers and memory on every step.If you are C++ or Rust, you can solve the problem by making your entire iteration protocol statically dispatched and hammering the compiler until it can reliably inline and SROA iterators.
If you are Java, then you have jit which doesn’t care at all about static function boundaries. A JIT sees a hot loop as a dynamically looping sequence of byte-code instructions, it really doesn’t care if there are some
callorcallvirtualinstructions in between.If you are Python, you are so slow that you genuinely don’t care about tight loops, or rather, you move the entire tight loop in C, and operate on numpy arrays in Python.
If you are Go, well, you don’t have compile-time destroying monomorphisation like Rust and C++, you also don’t get runtime speculative devirtualization like Java, and you are supposed to be much faster than Python!
But there’s this one weird trick where you can do internal iteration without a bunch of full virtual calls and without inlining/with separate compilation: you can reserver the stack space for the lambda you are passing into the internal iterator on the iterator’s caller stack frame. Not sure if Go does this already, but with the goroutine/coroutine stuff it is already doing, that would be a rather straightforward extension.
From what I can tell none of the posts that lead up to the design of go’s iterators mentioned performance. It has been seen as the better approach for the user of the language. See for instance this quote:
– rsc
My guess would be that the actual iterator interface allows for cleanup: if yield returns false (in case of a break or return), you get an opportunity to cleanup resources inside the iterator. I don’t think you could do it with this interface, but maybe I’m wrong
Yes, you can see the issue of how to close iterators sinking the prior discussion of using an interface for iterators.
my main takeaway from this article is that nobody should use
proto3protobufs :D. some of the iterator deep diving was fun too, but i’m far too dense to understand most of the details. i can see why mcyoung likes Rust with a brain like theirs, haha.TFA really abuses the expression “non-local” into meaninglessness. Their own desugaring literally shows Go just stashes the value in a local of the parent frame, the entire thing is a collaboration between frames in the desugaring. There’s no non-local return, Go won’t let you return through a caller the way e.g. Smalltalk actually does.
Not using an interface was a major requirement point of the rangefuncs proposal, because the desugaring of range loops is entirely based on concrete types. Not the only one, but it was very much a motivator for using an internal-style.
As a not-fan of Go and not convinced by the use of internal iteration, I actually found the rangefuncs proposal pretty objective, it had its bias but I ended up with the idea push iterators were probably the better thing for the language (and I don’t think it even made the strongest case for it as IIRC it didn’t touch on optimisation / efficiency).
That’s cope. Internal iterators are unusual and unfamiliar.
External iterators require a bit more setup but they’re way more intuitive and familiar to the average user, it’s how the vast majority of languages work, the desugaring is obvious, and it’s how you’d do iteration in your average procedural language as well.
The first portion, talking about the pull vs push API, reminded me of this fantastic post from Bob Nystrom where he describes external vs internal iteration: https://journal.stuffwithstuff.com/2013/01/13/iteration-inside-and-out/
The Rust snippet for the non-zero iterator doesn’t work.
https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=570cd3b67a9c3c8452059999113d4309
The other snippets looked sketchy to me too (I think “struct NonZero” in C++ doesn’t work either) but I didn’t look at them too hard.
Doesn’t look like the second C++ snippet works (haven’t checked the first). Here’s a godbolt for a working version.
it’s pretty simple to make it work though
I golfed it a bit:
Looks like there’s an upcoming
take_firstAPI that would make it even shorter.Am I misreading it, or should the first
__state := abi.RF_PANICin each decompilation beRF_READY?This is very interesting to me because I’ve recently developed by Bluefin effect system for Haskell, which comes with both push iterators and pull iterators (called
StreamandConsume– perhaps “Stream” should be called “Produce”). There’s a way of connecting them together (”consumeStream”) which is basically the same as the article’s “mechanism for converting push iterators into pull iterators” (I wouldn’t say it turns one to the other actually, I’d say it “connects” one of each type, but it depends on exactly what you mean, I guess). Like Go’s equivalent, it uses green threads to implement “concurrency without parallelism”. It’s interesting to see that both designs have converged!EDIT: After reading @dvogel’s post (https://lobste.rs/s/isx2ju/go_s_weird_little_iterators#c_zenkjq) I can say a bit more. Specifically, I think a “pull” iterator is “external”, and when a loop desugars to a use of
Consume, likeAnd a “push” iterator is “internal”, and when a loop desugars to Bluefin’s
forEachof a stream operationand you use it like
We decided to leverage
iterfor our pubsub impl and honestly they felt easy to use and mostly “just worked”: https://github.com/picosh/pubsub