Talk:Generator (computer science)

From Wikipedia, the free encyclopedia

Contents

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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... —the preceding comment is by 216.254.142.195 (talk • contribs) 2006-06-29 19:13: Please sign your posts!.

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)

[edit] 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
>>>
--Piet Delport 12:28, 30 August 2006 (UTC)
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)
Retrieved from "http://en.wikipedia.org../../../g/e/n/Talk%7EGenerator_%28computer_science%29_d660.html"