Talk:Generator (computer programming)
Origin of the concept
The article claims that generator were invented in Sather, but they date back significantly further. Jeremy Hylton gives a short historical overview. I could track them down as far as:
I couldn't find enough information about Alphard and IPL-v to know how they compare to later conceptions of generators. --Piet Delport 13:55, 7 November 2005 (UTC)
- Changed article to say CLU instead of Sather. CLU iterators are clearly generators. Not sure about Alphard. From Ms Liskov's article it sounds like Alphard didn't have
yield. But regardless, the new page is at least marginally more accurate. ;) Jorend 23:01, 5 January 2006 (UTC)
Generators in Icon
Icon has had generators since I believe it's initial public implementation. The 1st edition of the book "Icon Programming Language" by Griswold and Griswold, Prentice-Hall 1983, states in the preface.
"... It is worth noting here that a number of other programming languages have constructions called generators. CLU [5] is an example. In most languages, however, generators are confined to particular operations on certain kinds of values. In Icon, generators are completely general and may occur in any computation. Generators in themselves lend conciseness and expressive power. ... CheyenneWills 21:17, 12 December 2005 (UTC)
- If i'm not mistaken, Icon was quite influential in terms of popularizing generators. If so, it definitely deserves a good mention in the article. Tangentially: i get the impression that Icon's generator support goes hand in hand with its backtracking support; how much does this influence the "flavor" of Icon's generator use, compared to other languages that don't natively support backtracking? --Piet Delport 13:35, 13 December 2005 (UTC)
- I believe that you are correct. As for the influence of the "flavor", I believe that the use of generators in Icon can be broken down into 2 main areas, the first is the pure generation of "things", such as all the elements of a list
every write(!biglist)
- The second is within the confines of backtracking where alternatives are required. (here the find function is a generator). In this situation, string pattern matching relies heavily on generators
if find("i",string) = (3 | 10) then ...
- One of the other interesting areas is preserving the state of a generator by using Icon's coexpressions. The usual example is generating labels.
label := create "L" || seq() ... newlabel := @label nextlabel := @label ...
- where newlabel would be assigned L1 and nextlabel would get L2 (assuming the first and second invocations of the coexpression). CheyenneWills 18:53, 13 December 2005 (UTC)
Other languages implementing generators
(excluding languages which can implement generator functionality (via more general support for continuations or coroutines), but don't really support them as a native idiom)
- Aldor [5]
- Icon
- Panacea (mentioned in Randall Hyde's Art of Assembly Language, Ch. 12.5 Iterators)
Generators versus continuations
I've backed out this recent edit that introduces the wording "[Generators can be thought of as containing] a continuation (a programming language structure which can be thought of as a "frozen stack frame")". It was well-intended (thanks!), but a bit misleading, as generators and continuations are quite different. Tim Peters wrote a most excellent impromptu essay on generators, coroutines and continuations, and how they compare, but i'll attempt to summarize here:
- While a generator contains a single stack frame, a continuation contains a complete call stack.
- Invoking a generator resumes it on top of its caller's stack, and suspending/returning from the generator resumes the caller again (working almost exactly like normal function calls, in both cases (which is why generators are often explained as "resumable functions")). Invoking a continuation, on the other hand, is like discarding the old call stack entirely, and replacing it with the one stored in the continuation (with no way to return to the "caller", unless its stack was previously saved as another continuation).
--Piet Delport 16:54, 12 February 2006 (UTC)
Poor choice of example code
The generator code is recursive!!! In order to use the example to confirm my understanding of how a generator works is correct, I must first correctly understand ... generators! Clearly, that's a problem!
Could someone please provide a non-recursive example of the code, preferablely with a comment that describes what the expected mathematical outcome should be (ie. which mathematical "sum" is being calculated?). In that way, the reader can confirm for themselves that their understanding of the code matches the author's intent; and that their understanding of generators is therefore correct.
Right now, I *think* I understand what the code does, but since it doesn't include comments and I don't have a python compiler in front of me, I can't be sure that I've got it right... — Preceding unsigned comment added by 216.254.142.195 (talk • contribs) 2006-06-29 19:13 (UTC)
- I agree, the example is nearly uselessly opaque. I replaced it with an infinite incrementing integer sequence generator (it's not as scary as its name :), which hopefully neatly illustrates generators' laziness and statefulness. What do you think? --Piet Delport 14:13, 30 June 2006 (UTC)
- That's much better! Thank you! :-)
Just to provide another example in Icon... (using the same "logic" as the python code)..
procedure countfrom(n)
repeat {
suspend n
n +:= 1
}
end
# Example use: printing out the integers from 10 to 20.
# Note that this iteration terminates normally, despite countfrom() being
# written as an infinite loop.
every i := countfrom(10) do {
if i <= 20 then
write(i)
else
break
}
Another popular example is a generator for the Fibonacci sequence
procedure fibseq()
local i, j, n
i := 1
j := 1
suspend (i | # Generate the 1st value
j | # Generate the 2nd value
|{ # Repeatedly generate the next values
n := i + j # This value is returned
i := j # i and j to the "next" value
j := n
} )
end
...
every write(|fibseq() \20) # Will generate the first 20 numbers of the fibonacci sequence
CheyenneWills 05:20, 28 November 2006 (UTC)
Generator in Ruby
Piet - why do you think that Ruby does not support generators (iterators) directly?
#!/usr/bin/ruby
#
def countdown(n)
while n>=0
yield n
n-=1
end
end
countdown(10) { |count|
print "#{count}\n"
print "Ignition!\n" if count==3
print "Liftoff!\n" if count==0
}
IMHO, unless I am required to "include" or "use" or "import" something to work with a functionality, it is supported by the language. I'd vote for including Ruby to the list of languages that support generators aka iterators. If you'd not have removed ruby twice from the language list I would simply insert it, but let's discuss this. --The emm 15:21, 29 August 2006 (UTC)
- What's happening in the Ruby example is that you're creating and passing a block into
countdown, which calls it for each value produced, and returns once at the end. Translated to Python (with some decorator syntax abuse), this would look more or less like:
from functools import partial @partial(partial, partial) # curry countdown def countdown(n, block): while 0 <= n: block(n) n -= 1 @countdown(10) def receive(count): print count if count == 3: print 'Ignition!' if count == 0: print 'Liftoff!'
- By contrast, generators are called, and return/yield to their caller (which might be somewhere different each time), once for every value they produce. This means they can yield infinite sequences, and be composed together, passed around, and partially consumed, without worry. To try and illustrate:
def count(): """Generate all the natural numbers.""" n = 0 while True: yield n n += 1 def divisible(seq, n): """Yield all items from seq that are divisible by n.""" for x in seq: if x % n == 0: yield x >>> evens = divisible(count(), 2) >>> from itertools import islice >>> list(islice(evens, 5)) # pull 5 items from evens [0, 2, 4, 6, 8] >>> for n in evens: ... if n < 20: ... print n, ... else: ... break ... 10 12 14 16 18 >>>
- Iterators, generators and coroutines seem to be related but different. The coroutine article mentions: "Coroutines in which subsequent calls yield additional results are often known as generators." Is that the right way to define what a generator is? The article also has a link to a Japanese page about coroutines in Ruby. --TuukkaH 13:55, 30 August 2006 (UTC)
- That's probably not entirely inaccurate, but it should be understood that, generally speaking, coroutines are a superset of generators. (A generator is more-or-less a suspendable/resumable stack frame; a coroutine is more-or-less a suspendable/resumable call stack.) --Piet Delport 19:21, 30 August 2006 (UTC)
Python primes generator contributed by banned user
It was contributed by User:PWnsivander the Great, who, while a nonobjectionable user, was blocked by User:Rspeer as a reincarnation of (unjustly, in the opinion of most of the board) banned user Mike Church. Shouldn't it, as the contribution of a banned user, be removed? Sentinel89 06:07, 13 March 2007 (UTC)
- I would say no. The content should be judged on it's own merits regardless of any activity involving the user who initially contributed it. I've reviewed the code and see nothing wrong with it, and in fact believe it to be an great example for demonstrating Python generators (in terms of ease of understanding, not necessarily efficiency). My only hesitation would be the policy of WP:BAN, in that if these edits were made while the user was banned, then perhaps they could be reverted. But the policy doesn't say such edits have to be reverted, only that they may be. So I believe the content in this case is good enough to keep. Dmeranda 16:56, 16 March 2007 (UTC)
Fuzzy definition?
Coming from the STL, I find this definition quite fuzzy. Mixing generators and iterators seems strange, as I saw them serve different purposes:
- generators are functions with no argument and returning an object, and are not referentially transparents
- iterators are objects whose designate an element within a collection, and whose methods allow to access that element or designate another one, according to the access mode of the collection
Nowhere man 09:53, 24 April 2007 (UTC)
- First of all, generators and iterators do have separate articles, specifically because they are not the same thing. However the external behavior of generators does share a lot in common with that of iterators, so it is worth discussing on this article. Note also that the C++/STL concept of an iterator is much richer and more specialized that the general concept of iterator; so the difference between the two will appear much more pronounced if you have a C++ perspective. It may make it easier to realize that a generator is basically an iterator over a collection; it's just that the collection happens to be algorithmically defined rather than having to physically exist in a memory-resident data structure. Also generators in as much as they act like iterators only support the most fundamental behavior; referencing the current element and getting to the next one (although the next function is implicit); it by no means acts like many rich C++-style iterators with all their additional behaviors. -- Dmeranda 16:25, 24 April 2007 (UTC)
- OK, generators and iterators do have similarities, but the following text has no justification: "Generators are usually invoked inside loops. The first time that a generator invocation is reached in a loop, an iterator object is created that encapsulates the state of the generator routine at its beginning, with arguments bound to the corresponding parameters." Where does that come from? I never saw an iterator created when using a generator, be it in C++ or nay other language I use.
- There are a lot of generators that are not meant to be used in loops, like random or prime numbers generators.
- Also, generators' purpose is not to control loops. They are not to be mistaken as some sort of functional control structure! Nowhere man 18:50, 24 April 2007 (UTC)
- Yes, that quoted sentence is perhaps misleading in that it implies a specific implementation of generators, using iterators, which doesn't necessarily have to be true. Note though as an example, in the Python language, invoking a generator function does in fact create a real iterator object (it has a next() method, and raises a StopIteration error when/if the generator terminates). But it's not fair to say that just because that's how Python does it that it is how all languages must do it. As far as other types of generators, yes there are undoubtedly a lot of them. Most fall into the more casual use of the Engligh word generator, as in something that produces something else. Many of these are listed on the Generator (disambiguation) article. It probably would be worthwhile to put a little reference to these other types someplace. In terms of the specific type of generator discussed in this article (which is iterator-like), use in loops is quite common. Although a prime number generator or random number generator could be implmented as an interator-style generator, they don't have to be as you pointed out. But that's not what this article is about. I guess we just need to tighten up some language. -- Dmeranda 19:43, 24 April 2007 (UTC)
- Here's a python example showing how a generator really results is a true iterator (i.e., it obeys the standard Python iterator-protocol):
>>> def count_to_ten(n): # Define a generator function ... while n <= 10: ... yield n ... n = n + 1 ... return ... >>> gen = count_to_ten(7) # Invoke the generator >>> gen.next() # Treat the invocation as an iterator object 7 >>> gen.next() 8 >>> gen.next() 9 >>> gen.next() 10 >>> gen.next() Traceback (most recent call last): File "<stdin>", line 1, in <module> StopIteration
Dmeranda 19:52, 24 April 2007 (UTC)
- This article should not, as it is named, be about a specific subtype of generators, namely iterator-like generators. If you want to described them, and there is obviosuly much to say about them, then, fine, go ahead, but in a specific article. The article about generators in CS should about generators in CS. So what about refactoring this article in a general one (that I'm willing to write) and a specific one about iterator-like generators and their variants like list comprehensions?