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).
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 2006-06-29 19:13 (talk • contribs)
- 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! :-)
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)