Content deleted Content added
Nowhere man (talk | contribs) |
m Maintain {{WPBS}}: 3 WikiProject templates. Keep majority rating "Start" in {{WPBS}}. Remove 3 same ratings as {{WPBS}} in {{WikiProject Computing}}, {{WikiProject Computer science}}, {{WikiProject Software}}. Tag: |
||
| (42 intermediate revisions by 27 users not shown) | |||
Line 1:
{{Talk header}}
{{WikiProject banner shell|class=Start|
{{WikiProject Computing|importance=Low}}
{{WikiProject Computer science|importance=Mid}}
{{WikiProject Software|importance=Low}}
}}
==Origin of the concept==
Line 44 ⟶ 51:
(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]] [http://www.aldor.org/docs/HTML/chap9.html]
*[[Icon programming language|Icon]] (already done)
*[[Panacea programming language|Panacea]] (mentioned in [[Randall Hyde]]'s ''Art of Assembly Language'', [http://webster.cs.ucr.edu/AoA/DOS/ch12/CH12-6.html Ch. 12.5 Iterators])
*[[Unicon programming language|Unicon]]
*[[Raku (programming language)|Raku]] ... lazy lists?
== Generators versus continuations ==
Line 62 ⟶ 71:
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...
: 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? --[[User:Piet Delport|Piet Delport]] 14:13, 30 June 2006 (UTC)
Line 110 ⟶ 119:
</pre>
[[User:CheyenneWills|CheyenneWills]] 05:20, 28 November 2006 (UTC)
The Generator expression example for Icon can be simplified and does not require a co-expression.
<syntaxhighlight lang=pascal>
local j
every j := (|seq(0) \ 20) ^2 do # Produced the first 20 squares
write(j)
</syntaxhighlight>
If the idea is to demonstrate really what Icon can do in terms of using generators outside a loop construct, the following may be a better example
<syntaxhighlight lang=pascal>
# find the first matching element
a := [1,2,3,4]
b := [5,6,2,7]
c := ( !a = !b ) | &null # assign first matching element, or set to &null
</syntaxhighlight>
[[User:CheyenneWills|CheyenneWills]] ([[User talk:CheyenneWills|talk]]) 20:01, 16 June 2010 (UTC)
== Generator in Ruby ==
Line 202 ⟶ 229:
: 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. [[User:Dmeranda|Dmeranda]] 16:56, 16 March 2007 (UTC)
: I agree, the quality of the content overrules the character of the contributor. However, the Python example's prime number generator is beyond me. In particular, the line "if not any( n % f == 0 for f in p ):" uses the variable "f" which is never created in the code. Any help?
[[User:Dblanchard|dblanchard]] ([[User talk:Dblanchard|talk]]) <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|undated]] comment added 16:22, 5 October 2009 (UTC).</span><!--Template:Undated--> <!--Autosigned by SineBot-->
::Hi, the code within the brackets of the call to <code>any</code> is itself a generator expression. It iterates through p, the list of primes so far, assigning each to f and returns the value of <code>n %f == 0</code> for each iteration.So it could be read colloquially as:<br> "''if there are not any instances of a multiple of already found primes in n''"<br> --[[User:Paddy3118|Paddy]] ([[User talk:Paddy3118|talk]]) 17:06, 5 October 2009 (UTC)
==Fuzzy definition?==
Line 212 ⟶ 244:
[[User:Nowhere man|Nowhere man]] 09:53, 24 April 2007 (UTC)
: First of all, [[Generator (computer science)|generators]] and [[iterator]]s 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
::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.
Line 241 ⟶ 273:
[[User:Dmeranda|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? [[User:Nowhere man|Nowhere man]] 20:25, 24 April 2007 (UTC)
:Although I understand there is confusion that needs rectified, I disagree that this article's topic is too narrow in definition. [[Generator (computer science)]] generally agrees with most of the computer science literature in it's use of that term, as an iterator-like function. I've not seen any comp sci literature which defines what a ''generator'' (unqualified) is otherwise, except for the apparent convention of using the word in specific instances such as ''random number generator'', ''code generator'', ''name generator'', ''character generator'', etc. that are just a consequence of the common English meaning of the word, rather than a non-English teachnical meaning specific to the comp sci community. Many of those specific uses are listed on [[Generator (disambiguation)]] (although the disambig page seems to have been renamed to just [[Generator]] now). Would it suffice to just make a more verbose disambiguation statement at the top of the article, maybe something like:
:: ''This article is about a type of function in computer science that behaves like an iterator. For other uses of the term in computing in general see [[Generator]].''
::You say that the article "generally agrees with most of the computer science literature in it's use of that term". Could you give references of actual CS publications going in this direction? The article in itself is in contradiction with this claim, as it takes PRNG as an example, whereas PRNG typically don't behave like iterators, but are simply non referentially transparent functions of no argument.
::The first reference cited in the article says:
:::Generators first appeared in CLU (1975)[1]
::Although, the given article, "Iteration Abstraction in Sather", doesn't deal with generators at all. It's very subjects is named ''iterators'', and the term ''generator'' only appear a few times, in the last sections were the article makes comparisons with existing approaches of its subject. So long for the agreement of litterature in its use of that term...
::[[User:Nowhere man|Nowhere man]] 23:31, 24 April 2007 (UTC)
:Would that work? We could of course try to invent a broader-scoped definition, but I'm hesitant to do so. -- [[User:Dmeranda|Dmeranda]] 21:39, 24 April 2007 (UTC)
===Fuzzy or Hairy?===
The definition at the very start of the article is very hard to parse. It overuses analogy and is quite confusing. Perhaps later in the intro section it might be comprehensible, but at 0300 in the morning w/ a non-working GRUB2 EFI configuration hanging over my head, I just ditched trying to read the article and leave this short note waiting for the rest of my update to download.
The definition/intro is ambiguous and seems to muddle up the notion of what is being iterated, what the iterator is, and how it is implemented. Try to stay at a very non-computer science language level with the initial definition or include the WP article link for every bit of jargon you need to be clear. You could, however, start by saying that a generator is specific case of an [[Iterator]]... However, nearly every CS topic has, someplace, a fairly clear definition using basic mathematics/logic terms that most reasonable educated individuals without a degree in CS can understand.
What you should not say is that it is like an array, since it isn't anything like an array. You might use a generator to access values in an array, but it isn't the array. You can use a bucket to empty a bathtub full of soapy water, but don't confuse the bucket with the bathwater (and for heaven's sake, take the baby out first!).
Sorry, but most of my programming experience is with Java (w/o generators as a built in, but I am sure I have had to write thousands of them w/o ever knowing what the hell I was doing), or I would try my hand at a new intro. <!-- Template:Unsigned IP --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/75.73.1.89|75.73.1.89]] ([[User talk:75.73.1.89#top|talk]]) 09:16, 13 January 2017 (UTC)</small> <!--Autosigned by SineBot-->
== Needs verification ==
OK, I declared the article as needing verification from actual facts.
* The CLU paper cited just talks about iterators, and ''compares'' them to generators.
* Some contributor stated that the article "''generally agrees with most of the computer science literature in it's use of that term''", without being able to show any verifiable references.
I'll wait some time for people to be able to gather and show references to backup the article. If that doesn't happen, I'll edit it to describe the concept of generators in general. [[User:Nowhere man|Nowhere man]] 12:54, 29 April 2007 (UTC)
:I even found a contradictory source. In "Iterators: Signs of Weakness in Object-Oriented Languages" (1992), H. Baker states the following about iterators as found in CLU and C++:
::''Iterators are a 1980's version of the 1950's concept of generators. A generator is a subroutine which is called like a function, but returns a "new" value every time it is called (i.e., it is emphatically not a mathematical function). The "random number generator" is prototypic of a generator.''
:With this new information in hands, I will not wait to modify the article. [[User:Nowhere man|Nowhere man]] 17:38, 29 April 2007 (UTC)
OK, I claimed the article was inconsistent with reachable publications, so with not a single attempt to counter that claim in nearly one year, I eventually rewrote the article. [[User:Nowhere man|Nowhere man]] ([[User talk:Nowhere man|talk]]) 21:18, 12 March 2008 (UTC)
: I'm not sure that the claim was clear enough to provoke a counter.
: Regarding [http://www.pipeline.com/~hbaker1/Iterator.html Baker's paper], it's entirely consistent with the article. The sentence quoted is a simplified introduction, taken somewhat out of context; two paragraphs later, Baker unambiguously explains the difference between generators and functions/iterator classes: <blockquote>One is tempted to think that every co-routine generator can be emulated by a function which has access to some persistent local state (e.g., an Algol-60 "own" variable), but this is not the case. The standard counter-example is the "samefringe" problem, which can be solved by two co-routined "fringe" generators, but cannot be solved by a function with only a bounded amount of persistent local state.</blockquote>
: The paper as a whole is an argument against iterator classes, and for functional generators. <span style="white-space:nowrap">—[[User:Piet Delport|Piet Delport]] <small>2008-03-18 06:30</small></span>
:: How could I make the claim more clear: a banner, examination of cited papers and quotation with links to another contradictory paper! As for Baker's paper, the quote you give doesn't say that generators have any relationship with loops or control structures, and clearly state that a PRNG is a classical example of generator. So I maintain that the article is plain false. It still cites papers that are contradictory to itself. If you can find a reachable reference that clearly support the old version, there's room to improve it based on those references. Until then, I'll revert to my modification.
:: I gave plenty of time to counter my claim, so don't revert to the previous state of the article without a strong reference. just saying that noone saw the long-standing claim isn't enough. [[User:Nowhere man|Nowhere man]] ([[User talk:Nowhere man|talk]]) 21:24, 25 March 2008 (UTC)
::: I find the paper clear, unambiguous, and non-contradictory. It meets all the qualifications of a [[Wikipedia:Reliable sources|reliable source]]. If you disagree with the paper, Wikipedia is ''not'' the avenue to pursue it: Wikipedia's threshold for inclusion is [[Wikipedia:Verifiability|verifiability]], not truth, and [[Wikipedia:No original research|not original research]].
::: Regarding your individual points:
:::* I don't know what you're trying to imply about the text i quoted; it doesn't directly say anything about generators and their relationship with loops / control structures, but that's the subject of the rest of the paper.
:::* Baker's paper does not say that PRNGs are ''examples'' of generators, it says that PRNGs are ''prototypic of'' generators, which includes the sense of being precursory or inspirational to. (Indeed, PRNGs are generally well-implementable both as "plain" procedures and as generators in the sense of this article.) You could quibble over which sense of "prototypic" was meant in the introductory sentence, taken out of context, but any doubt is rendered moot by the body of the paper, which is quite precise, and never mentions PRNGs.
:::* The article is not backed by the Baker citation alone, but by Kiselyov, Omohundro (Sather), Liskov (CLU), Shaw (Alphard) and the rest (Python, C#, JavaScript). There are no grounds for reverting the article without a convincing argument that these citations are all invalid.
::: If you wish to continue this further, the next [[Wikipedia:Dispute resolution|dispute resolution]] step is probably to solicit a third opinion, or informal mediation. <span style="white-space:nowrap">—[[User:Piet Delport|Piet Delport]] <small>2008-04-01 00:07</small></span>
== Suggestion for clarifications, definitions, etc. ==
The Icon programming language, while not the first language to implement generators, was one of the first to fully integrate the concept into the language. Within Icon, generators are not only used within the scope of loops, but are available throughout the language. In addition while in a certain sense one could say that a generator returns a list of values, a better term is that a generator returns a result sequence. Specifically, a generator could return an infinite number of values (e.g. a random number generator).
There was a lot of research and many papers written on generators. In doing a date sorted search of the string "generator" in the ACM portal, the earliest reference I found (outside random number generators, and a couple of references to code generators) was
<code><pre>
Mary Shaw, William A. Wulf, Ralph L. London
August 1977
Communications of the ACM, Volume 20 Issue 8
Publisher: ACM Press
Full text available: pdf(1.28 MB)
Additional Information: full citation, abstract, references, citings
The Alphard “form” provides the programmer with a great deal of control
over the implementation of abstract data types. In this paper the
abstraction techniques are extended from simple data representation and
function definition to the iteration statement, the most important point
of interaction between data and the control structure of the language
itself. A means of specializing Alphard's loops to operate on abstract
entities without explicit dependence on the representation ...
Keywords: abstraction and representation, abstraction data types,
assertions, control specialization, correctness, generators, invariants,
iteration statements, modular decomposition, program specifications,
programming languages, programming methodology, proofs of correctness,
types, verification
</pre></code>
Of interest, is that immediately following the above article in the same issue of the Communications of the ACM, was an article on CLU.
The next real reference to generators was the article written by the late Dr Ralph Griswold
<code><pre>
Generators in Icon
Full text pdf formatPdf (1.03 MB)
Source ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 3 , Issue 2 (April 1981) table of contents
Pages: 144 - 161
Year of Publication: 1981
ISSN:0164-0925
Authors
Ralph E. Griswold Department of Computer Science, The University of Arizona, Tucson, AZ
David R. Hanson Department of Computer Science, The University of Arizona, Tucson, AZ
John T. Korb Xerox Corporation, 3333 Coyote Hill Road, Palo Alto, CA
Publisher
ACM Press New York, NY, USA
</pre></code>
Quoting from the above
<code><pre>
5. RELATED WORK
The concept of generators has appeared in various forms in many languages. An
early language that has generators is IPL-V [31], in which a generator is a
subroutine that calls a processing routine to operate on each object in a data
structure. Other languages, such as ALGOL 68 [38] and COBOL, use the term
generator to describe various language features, but this use is unrelated to the
Icon notion.
Languages that support coroutines frequently use the term generator to describe
a particular coroutine usage. SIMULA [1] is the oldest of such languages;
more recent examples include extensions to POP-2 [24] and SL5 [20] and
coroutine additions to PASCAL [27]. There also has been a substantial amount
of work on the "lazy evaluation" approach to the incremental generation of
sequences, usually in LISP or APL frameworks [7, 17, 22].
More recently, ALPHARD [43] and CLU [28] have been developed to support
data structure abstraction. In these languages generators are used to iterate over
the elements of programmer-defined data structures [35]. Included with the
definition of a data abstraction (or "cluster" in CLU) is a procedure for generating
the elements of the abstraction. In CLU, this procedure, called an iterator,
produces its values using the yield statement. When another element is required,
execution of the iterator continues where the yield statement left off. In each of
these languages, generators are only accessible in a specific context: a particular
type of for statement. This is significantly more restricted than in Icon, where
generators may appear anywhere.
Superficially, generators in ALPHARD and CLU appear to correspond to the
every expression in Icon. But while every has the syntactic appearance of a
standard control structure, the nonstandard goal-directed evaluation mechanism
makes its semantics more general than the corresponding ALPHARD and CLU
constructs. It is the restricted applicability and the lack of goal-directed evaluation
that differentiate these constructs from generators in Icon.
ACM Transactions on Programming Languages and Systems, Vol. 3, No. 2, April 1981.
158 R.E. Griswold, D. R. Hanson, and J. T. Korb
</pre></code>
[[User:CheyenneWills|CheyenneWills]] 20:49, 25 June 2007 (UTC)
==C++ generators==
I don't think C++ properly supports generators. There is no way to have the compiler save
the stack frame; as in the example, the object must remember its own state. Overloading
the function call operator makes it look somewhat like a (hypothetical) C++ generator,
but a constructor call is still needed. It's close, but this can done, with vary degrees
of syntactical success, in most object-oriented languages. <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/67.122.120.62|67.122.120.62]] ([[User talk:67.122.120.62|talk]]) 10:49, 2 March 2008 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
: Right, the section described an iterator class, not a generator. I removed it. <span style="white-space:nowrap">—[[User:Piet Delport|Piet Delport]] <small>2008-03-18 06:35</small></span>
==D Generators==
In D generators can be done by implementing an opApply function (overload for a 'foreach'). This page shows a good example at the end with primes numbers: [http://the-free-meme.blogspot.com/2009/06/power-of-foreach.html].
Could this page include a D example thanks.
Tim M. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/125.238.96.209|125.238.96.209]] ([[User talk:125.238.96.209|talk]]) 09:22, 6 July 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
==Iterator confusion==
<s>I think the current text is messed up to deserve rewrite. I think that generators have little in common with iterators, except a common usage. A generator is a function with a static persistent environment, which is preserved from call to call, cf. local <code>static</code> declaration in C and <code>own</code> in good old Algol-60. Whether used as iterator or not is irrelevant. You cannot create different instances of generators like you can when dealing with iterators, or put it another way: there's ''only one'' generator instance ''ever'', and it is "created" at startup. Iterator instances are always created to dynamically produce a sequence, while the generator just preserves a state. When created, the iterators take an argument, often an array or some other enumerable, but not always – this in opposition to the generator, which is not "reset/reinitialized" in a call different from a normal generator call producing the next item. [[User:Rursus|Rursus]] dixit. ([[User talk:Rursus|<span style="color: red; background: #FFFF80"><sup>m</sup><u>bork<sup>3</sup></u></span>]]!) 07:04, 21 June 2010 (UTC)</s>
:No, I'm confused by the [http://docs.python.org/tutorial/classes.html#generators Python generators definition]. Forget it! [[User:Rursus|Rursus]] dixit. ([[User talk:Rursus|<span style="color: red; background: #FFFF80"><sup>m</sup><u>bork<sup>3</sup></u></span>]]!) 07:33, 21 June 2010 (UTC)
== ICON as a language ==
the article opens by characterizing ICON as a string manipulation language.
I think that if you look at ICON 9.5 this will not seem an appropriate characterization. Was ICON not the first expressly free language (after accidental SNOBOL 'release'? )
ObjectIcon at code.google.com/p/objecticon is surely more than a string manipulation language
ICON is better characterized as a free expression-based language with goal-directed facilities
For ICON for pythonistas, see convergepl.org
G. Robert Shiplett 14:34, 29 November 2010 (UTC) <small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Grshiplett|Grshiplett]] ([[User talk:Grshiplett|talk]] • [[Special:Contributions/Grshiplett|contribs]]) </span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
== Standard or common implementation of generators at the low-level ==
This article should describe in-detail the most common ways generators are implemented at the low-level. This means information such as if a program with generators is compiled to an assembly language, what would it look like? What happens to the control flow? What happens to the stack? Is a new stack created? Where does it keep the information about where in the generator control flow is resumed to after the yield statement?
--[[User:Eboyjr|Eboyjr]] ([[User talk:Eboyjr|talk]]) 17:02, 16 June 2011 (UTC)
== Needs common example; Should be an infinite sequence ==
(Disclaimer: my view of "what a generator is" and "what they are good for" comes chiefly from my experience with Python.)
The article -- and its examples -- are very scattered. They even include examples of "generating the numbers from 10 to 1". To someone who doesn't understand the power of or purpose of generators, this will be a highly deluminating example, as they could [correctly] disparage the whole idea: "why wouldn't I just do that in a loop, decrementing a counter?"
My suggestions:
* Point out that generators are really good for generating INFINITE sequences... just a little bit at a time, as the "consumer" needs the "next" item.
* Point out that most useful generators need to store a complicated state. (It is not just a simple unary test like "is this number even", which -- again -- can be accomplished declaratively and used as a test in a loop.)
* Point out that languages that "support generators" do so by giving the programmer a simple way to do BOTH of those: generate "infinite sequences incrementally" and "save their state between calls".
* Pick a simple example that uses BOTH of those features. Such as: calculating the Fibonacci sequence. Let's see a Fib() generator in all the languages discussed.
* Point out that recursion and generation can each be used on certain calculations, but they are NOT synonymous.
* Compare and contrast a generator with a memoized recursive routine. (You can quickly calculate Fib(10000000) with a memoized recursive Fib, at the expense of the memory for the 1000000 prior entries. However, with a generator-based Fib(), constant memory (just two state variables) will serve to walk through all the values of Fib forever.)
If I have time someday, I may attempt to update the article with some of these suggestions.
[[User:Dharasty|Dharasty]] ([[User talk:Dharasty|talk]]) 13:10, 3 May 2012 (UTC)
== Dates are incorrect. Fix or maybe even remove? ==
The dates in this refer to the date the programming language first appeared, which is often *not* the same date as when generators appeared for this language.
For example if you would glance at this article, you would get the impression that:
* Generators were first introduced in Lisp in 1958 (not so, generators are a recent addition to Lisp, and AFAIK not even standardized in Common Lisp)
* PHP has generators since 1995 (It's implemented and available in the `latest source', but available in a general release yet).
etc... IMHO this is rather misleading ... Someone should fix the dates to reflect whenever this feature was added to a language (if it wasn't there from the start) or the dates should just be removed.
[[User:Carpetsmoker|Carpetsmoker]] ([[User talk:Carpetsmoker|talk]]) 10:00, 11 March 2013 (UTC)
Just passing by, but came here to write this exact same thing - The Ruby section says 1995 but also says "starting from version 1.9" which was released in 2007. [[User:Galestar|Galestar]] ([[User talk:Galestar|talk]]) 17:21, 22 April 2013 (UTC)
Corrected the date for Python. [[User:Tlesher|tlesher]] ([[User talk:Tlesher|talk]]) 20:13, 19 August 2013 (UTC)
| |||