Folks -
One thing I really like about Python is Generators (http://docs.python.org/tutorial/classes.html#generators). They allow code to provide a stream (iterator) interface where it's not easy to provide the interface explicitly. I.e., it would allow one to provide a stream interface to an arbitrary computation like:
gen := Generator on: [:yield| 3 to: 1 by: -1 do:[:i| yield value: i]]. gen next. "=>3" gen next. "=>2" gen next. "=>1" gen next. "=>nil"
This *ought* to be really simple to do in Smalltalk by using blocks and some voodoo in the execution engine. Has anyone ever done that?
Cheers, - Andreas
Hello Andreas,
I believe Timothy A. Budd has written a paper related to that, entitled "The Generator Paradigm in Smalltalk" but I cannot find it readily. He also wrote another paper entitled "An implementation of generators in C". Isn't generators implemented in GNU Smalltalk?
Another implementation details are available in "The Implementation of the Icon Programming Language", which is also in C. You can download the book online at http://www.cs.arizona.edu/icon/books.htm
Ian.
2010/2/10 Andreas Raab andreas.raab@gmx.de:
Folks -
One thing I really like about Python is Generators (http://docs.python.org/tutorial/classes.html#generators). They allow code to provide a stream (iterator) interface where it's not easy to provide the interface explicitly. I.e., it would allow one to provide a stream interface to an arbitrary computation like:
gen := Generator on: [:yield| 3 to: 1 by: -1 do:[:i| yield value: i]]. gen next. "=>3" gen next. "=>2" gen next. "=>1" gen next. "=>nil"
This *ought* to be really simple to do in Smalltalk by using blocks and some voodoo in the execution engine. Has anyone ever done that?
Cheers, - Andreas
On 2010-02-09, at 9:27 PM, Andreas Raab wrote:
Folks -
One thing I really like about Python is Generators (http://docs.python.org/tutorial/classes.html#generators). They allow code to provide a stream (iterator) interface where it's not easy to provide the interface explicitly. I.e., it would allow one to provide a stream interface to an arbitrary computation like:
gen := Generator on: [:yield| 3 to: 1 by: -1 do:[:i| yield value: i]]. gen next. "=>3" gen next. "=>2" gen next. "=>1" gen next. "=>nil"
This *ought* to be really simple to do in Smalltalk by using blocks and some voodoo in the execution engine. Has anyone ever done that?
Generators are essentially coroutines, which makes them pretty easy to implement in Smalltalk - thisContext is all you need. They've been implemented a few times to my knowledge. GST has an implementation that is pretty similar to what Python provides:
http://smalltalk.gnu.org/faq/47
Also, Stephen Pair posted an implementation here in December:
http://n4.nabble.com/ANN-CoroutineReadStream-tt963004.html#a963004
I've done stuff like this for testing. My MockLibrary package provides a class called Mocket ("mock socket") that uses coroutines to make it easier to test network code. It's not a "generator" exactly, but it does simulate reading data off a socket by jumping back into the test case and letting it generate the data.
Colin
Colin Putney wrote:
Also, Stephen Pair posted an implementation here in December:
http://n4.nabble.com/ANN-CoroutineReadStream-tt963004.html#a963004
Brilliant! That's the ticket! Once I got down the right path it's even simpler than that. I put a version of Generator into the inbox for people to play with and give feedback. With 5 methods total you get to do fun stuff like:
| gen max | max := 10000000. gen := Generator on:[:yield| Integer primesUpTo: max do: yield]. 'Computing primes' displayProgressAt: Sensor cursorPoint from: 1 to: max during:[:bar| | prime | [prime := gen next] whileNotNil:[bar value: prime]. ].
I think we should add support for Generators. They are so incredibly useful where you have complex operations that you don't want to spend the upfront effort on to compute everything (like primes) before you can do some work with the results.
Cheers, - Andreas
On Tue, 9 Feb 2010, Andreas Raab wrote:
Colin Putney wrote:
Also, Stephen Pair posted an implementation here in December: http://n4.nabble.com/ANN-CoroutineReadStream-tt963004.html#a963004
Brilliant! That's the ticket! Once I got down the right path it's even simpler than that. I put a version of Generator into the inbox for people to play with and give feedback. With 5 methods total you get to do fun stuff like:
| gen max | max := 10000000. gen := Generator on:[:yield| Integer primesUpTo: max do: yield]. 'Computing primes' displayProgressAt: Sensor cursorPoint from: 1 to: max during:[:bar| | prime | [prime := gen next] whileNotNil:[bar value: prime]. ].
I think we should add support for Generators. They are so incredibly useful where you have complex operations that you don't want to spend the upfront effort on to compute everything (like primes) before you can do some work with the results.
I wonder how can you use generators to generate primes efficiently _and_ on the fly.
Levente
Cheers,
- Andreas
SICP to the rescue http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5.2
Probably inspiring in the context of this thread. Bye Enrico
On Wed, Feb 10, 2010 at 8:16 AM, Levente Uzonyi leves@elte.hu wrote:
On Tue, 9 Feb 2010, Andreas Raab wrote:
Colin Putney wrote:
Also, Stephen Pair posted an implementation here in December: http://n4.nabble.com/ANN-CoroutineReadStream-tt963004.html#a963004
Brilliant! That's the ticket! Once I got down the right path it's even simpler than that. I put a version of Generator into the inbox for people to play with and give feedback. With 5 methods total you get to do fun stuff like:
| gen max | max := 10000000. gen := Generator on:[:yield| Integer primesUpTo: max do: yield]. 'Computing primes' displayProgressAt: Sensor cursorPoint from: 1 to: max during:[:bar| | prime | [prime := gen next] whileNotNil:[bar value: prime]. ].
I think we should add support for Generators. They are so incredibly useful where you have complex operations that you don't want to spend the upfront effort on to compute everything (like primes) before you can do some work with the results.
I wonder how can you use generators to generate primes efficiently _and_ on the fly.
Levente
Cheers,
- Andreas
On Wed, 10 Feb 2010, Enrico Spinielli wrote:
SICP to the rescue http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5.2
Well, this is not efficient. It states that it implements the sieve of Eratosthenes, but it uses division... A smalltalk equivalent with generators would look like this (according to my minimal lisp knowledge):
primeGenerator := Generator on: [ :yield | | primes i | yield value: 2. primes := OrderedCollection with: 2. i := 3. [ (primes noneSatisfy: [ :prime | i \ prime = 0 ]) ifTrue: [ primes add: i. yield value: i ]. i := i + 2. true ] whileTrue ].
There are 9592 primes that are smaller than 100000.
[ 1 to: 9592 do: [ :i | primeGenerator next ] ] timeToRun. "===> 13061"
Compare this with a real sieve (which doesn't use division at all):
[ Integer primesUpTo: 100000 do: #yourself ] timeToRun "===> 13"
1000x faster.
Levente
Probably inspiring in the context of this thread. Bye Enrico
On Wed, Feb 10, 2010 at 8:16 AM, Levente Uzonyi leves@elte.hu wrote:
On Tue, 9 Feb 2010, Andreas Raab wrote:
Colin Putney wrote:
Also, Stephen Pair posted an implementation here in December: http://n4.nabble.com/ANN-CoroutineReadStream-tt963004.html#a963004
Brilliant! That's the ticket! Once I got down the right path it's even simpler than that. I put a version of Generator into the inbox for people to play with and give feedback. With 5 methods total you get to do fun stuff like:
| gen max | max := 10000000. gen := Generator on:[:yield| Integer primesUpTo: max do: yield]. 'Computing primes' displayProgressAt: Sensor cursorPoint from: 1 to: max during:[:bar| | prime | [prime := gen next] whileNotNil:[bar value: prime]. ].
I think we should add support for Generators. They are so incredibly useful where you have complex operations that you don't want to spend the upfront effort on to compute everything (like primes) before you can do some work with the results.
I wonder how can you use generators to generate primes efficiently _and_ on the fly.
Levente
Cheers,
- Andreas
-- Enrico Spinielli "Do Androids dream of electric sheep?"? Philip K. Dick "Hear and forget; see and remember;do and understand."?Mitchel Resnick
"Levente" == Levente Uzonyi leves@elte.hu writes:
Levente> On Wed, 10 Feb 2010, Enrico Spinielli wrote:
SICP to the rescue http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5.2
Levente> Well, this is not efficient. It states that it implements the sieve of Levente> Eratosthenes, but it uses division... A smalltalk equivalent with generators Levente> would look like this (according to my minimal lisp knowledge):
What you really want is a set of generators that produce 2, 4, 6, 8 ... 3, 6, 9, 12 ... 5, 10, 15, 20, ...
and could efficiently "merge" them in order, so that you could "subtract" that merge from a generator counting 1..n. If anything made it past that subtract, it would become a new sequence generator.
I think I saw this technique in "Higher Order Programming", a book about using Perl closures to do some really wicked stuff.
On Wed, 10 Feb 2010, Randal L. Schwartz wrote:
"Levente" == Levente Uzonyi leves@elte.hu writes:
Levente> On Wed, 10 Feb 2010, Enrico Spinielli wrote:
SICP to the rescue http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5.2
Levente> Well, this is not efficient. It states that it implements the sieve of Levente> Eratosthenes, but it uses division... A smalltalk equivalent with generators Levente> would look like this (according to my minimal lisp knowledge):
What you really want is a set of generators that produce 2, 4, 6, 8 ... 3, 6, 9, 12 ... 5, 10, 15, 20, ...
and could efficiently "merge" them in order, so that you could "subtract" that merge from a generator counting 1..n. If anything made it past that subtract, it would become a new sequence generator.
Something like this?
primeGenerator := Generator on: [ :yield | | generators i | generators := OrderedCollection new. i := 2. [ (generators noneSatisfy: [ :generator | [ generator lastValue < i ] whileTrue: [ generator next ]. generator lastValue = i ]) ifTrue: [ yield value: i. (generators add: (Generator on: [ :filterYield | | prime k | prime := i. k := prime. [ filterYield value: k. k := k + prime. true ] whileTrue ])) next. "#next ensures that prime's value is set to i's value and initializes lastValue" ]. i := i + 1. true ] whileTrue ].
[ 1 to: 9592 do: [ :i | primeGenerator next ] ] timeToRun "===> 23982"
Note that Andreas' Generator has to be changed a bit to run this code. I added a new instance variable "lastValue" and an accessor for it. I also changed #nextPut:'s last line to: ^lastValue := anObject "returns anObject to retrieverContext (i.e., #next)"
Levente
I think I saw this technique in "Higher Order Programming", a book about using Perl closures to do some really wicked stuff.
-- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 merlyn@stonehenge.com URL:http://www.stonehenge.com/merlyn/ Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc. See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion
On second thought, I guess there must be some kind of yield.
In any case, I wrote my LazyList package to implement the iCal spec. I use it to do complex things like allowing the user to specify one or more date generators (infinite list of e.g. Thursdays) and filter based on one or more other infinite sets (e.g. my families birthdays). Since the generated dates will be in order this works fine.
On Wed, Feb 10, 2010 at 9:03 AM, Andreas Raab andreas.raab@gmx.de wrote:
Colin Putney wrote:
Also, Stephen Pair posted an implementation here in December: http://n4.nabble.com/ANN-CoroutineReadStream-tt963004.html#a963004
Brilliant! That's the ticket! Once I got down the right path it's even simpler than that. I put a version of Generator into the inbox for people to play with and give feedback. With 5 methods total you get to do fun stuff like:
| gen max | max := 10000000. gen := Generator on:[:yield| Integer primesUpTo: max do: yield]. 'Computing primes' displayProgressAt: Sensor cursorPoint from: 1 to: max during:[:bar| | prime | [prime := gen next] whileNotNil:[bar value: prime]. ].
I think we should add support for Generators. They are so incredibly useful where you have complex operations that you don't want to spend the upfront effort on to compute everything (like primes) before you can do some work with the results.
Cheers, - Andreas
http://source.lukas-renggli.ch/continuations/Generator-lr.3.mcz
Lukas
On 10 February 2010 06:49, Colin Putney cputney@wiresong.ca wrote:
On 2010-02-09, at 9:27 PM, Andreas Raab wrote:
Folks -
One thing I really like about Python is Generators (http://docs.python.org/tutorial/classes.html#generators). They allow code to provide a stream (iterator) interface where it's not easy to provide the interface explicitly. I.e., it would allow one to provide a stream interface to an arbitrary computation like:
gen := Generator on: [:yield| 3 to: 1 by: -1 do:[:i| yield value: i]]. gen next. "=>3" gen next. "=>2" gen next. "=>1" gen next. "=>nil"
This *ought* to be really simple to do in Smalltalk by using blocks and some voodoo in the execution engine. Has anyone ever done that?
Generators are essentially coroutines, which makes them pretty easy to implement in Smalltalk - thisContext is all you need. They've been implemented a few times to my knowledge. GST has an implementation that is pretty similar to what Python provides:
http://smalltalk.gnu.org/faq/47
Also, Stephen Pair posted an implementation here in December:
http://n4.nabble.com/ANN-CoroutineReadStream-tt963004.html#a963004
I've done stuff like this for testing. My MockLibrary package provides a class called Mocket ("mock socket") that uses coroutines to make it easier to test network code. It's not a "generator" exactly, but it does simulate reading data off a socket by jumping back into the test case and letting it generate the data.
Colin
Lukas Renggli wrote:
http://source.lukas-renggli.ch/continuations/Generator-lr.3.mcz
Interesting, thanks. I notice you have Generator>>reset and Generator>>fork which are definitely useful, but no Generator>>close? The latter allowing to execute any unwind blocks associated with the generator, say:
gen := Generator on:[:yield| | fs | [fs := FileStream readOnlyFileNamed: 'foo.bar'. [fs atEnd] whileFalse:[yield value: fs nextLine]] ensure:[fs close] ].
Unless a close operation is provided, the file in the above will not be closed properly.
Cheers, - Andreas
On 10 February 2010 06:49, Colin Putney cputney@wiresong.ca wrote:
On 2010-02-09, at 9:27 PM, Andreas Raab wrote:
Folks -
One thing I really like about Python is Generators (http://docs.python.org/tutorial/classes.html#generators). They allow code to provide a stream (iterator) interface where it's not easy to provide the interface explicitly. I.e., it would allow one to provide a stream interface to an arbitrary computation like:
gen := Generator on: [:yield| 3 to: 1 by: -1 do:[:i| yield value: i]]. gen next. "=>3" gen next. "=>2" gen next. "=>1" gen next. "=>nil"
This *ought* to be really simple to do in Smalltalk by using blocks and some voodoo in the execution engine. Has anyone ever done that?
Generators are essentially coroutines, which makes them pretty easy to implement in Smalltalk - thisContext is all you need. They've been implemented a few times to my knowledge. GST has an implementation that is pretty similar to what Python provides:
http://smalltalk.gnu.org/faq/47
Also, Stephen Pair posted an implementation here in December:
http://n4.nabble.com/ANN-CoroutineReadStream-tt963004.html#a963004
I've done stuff like this for testing. My MockLibrary package provides a class called Mocket ("mock socket") that uses coroutines to make it easier to test network code. It's not a "generator" exactly, but it does simulate reading data off a socket by jumping back into the test case and letting it generate the data.
Colin
On 10 February 2010 08:49, Andreas Raab andreas.raab@gmx.de wrote:
Lukas Renggli wrote:
http://source.lukas-renggli.ch/continuations/Generator-lr.3.mcz
Interesting, thanks. I notice you have Generator>>reset and Generator>>fork which are definitely useful, but no Generator>>close? The latter allowing to execute any unwind blocks associated with the generator, say:
gen := Generator on:[:yield| | fs | [fs := FileStream readOnlyFileNamed: 'foo.bar'. [fs atEnd] whileFalse:[yield value: fs nextLine]] ensure:[fs close] ].
Unless a close operation is provided, the file in the above will not be closed properly.
I've fixed that. There could be more bugs, as I've never used them beyond the anecdotical examples showing off runtime reflection. I never saw a practical use of Generators in Smalltalk.
Lukas
Lukas Renggli wrote:
I've fixed that. There could be more bugs, as I've never used them beyond the anecdotical examples showing off runtime reflection. I never saw a practical use of Generators in Smalltalk.
I have had some situations where I wanted them. Eliot's compression example is one of them - wrapping the algorithm into a Generator would allow trivial use of the algorithm recursively. Of course, the algorithm could be rewritten to do that iteratively but it's just nice and convenient to have a generator at hand that does it for you.
Cheers, - Andreas
Lukas Renggli wrote:
I've fixed that. There could be more bugs, as I've never used them beyond the anecdotical examples showing off runtime reflection.
I uploaded a version that fixes two more issues, one affecting the use of reset and unwind blocks and one that affected error handling in Generators. If people want to try this, you can install:
Installer installUrl: 'http://source.lukas-renggli.ch/continuations/Generator-ar.5.mcz'
and check it out. To me this looks pretty damn ready for use, if I hear no strong objections be prepared to find this merged into the Collections package Real Soon Now.
Cheers, - Andreas
On 11 February 2010 07:11, Andreas Raab andreas.raab@gmx.de wrote:
Lukas Renggli wrote:
I've fixed that. There could be more bugs, as I've never used them beyond the anecdotical examples showing off runtime reflection.
I uploaded a version that fixes two more issues, one affecting the use of reset and unwind blocks and one that affected error handling in Generators. If people want to try this, you can install:
Installer installUrl: 'http://source.lukas-renggli.ch/continuations/Generator-ar.5.mcz'
and check it out. To me this looks pretty damn ready for use, if I hear no strong objections be prepared to find this merged into the Collections package Real Soon Now.
Into Collections? As to me, it something like stream.. Maybe its worth adding separate category?
Cheers, - Andreas
Am Thursday 11 February 2010 schrieb Andreas Raab:
Lukas Renggli wrote:
I've fixed that. There could be more bugs, as I've never used them beyond the anecdotical examples showing off runtime reflection.
I uploaded a version that fixes two more issues, one affecting the use of reset and unwind blocks and one that affected error handling in Generators. If people want to try this, you can install:
Installer installUrl: 'http://source.lukas-renggli.ch/continuations/Generator-ar.5.mcz'
and check it out. To me this looks pretty damn ready for use, if I hear no strong objections be prepared to find this merged into the Collections package Real Soon Now.
Cheers,
- Andreas
Andreas,
this generator stuff is really cool. It helped me find a solution to a problem I have using a coroutine. I couldn't use a generator because in my case the producer is the one controling the process, So I build my own version of a coroutine following your Generator class.
While studying your code I stumbled upon "[self fork] value" in method reset. Question is, why the block here? wouldn't self fork suffice?
And while comparing with the class from Stephen Pair I asked myself why you didn't implement a finalize methode. Or rather why Stephen tought it necessary to do so.
Would be nice if you could shed some more light on this.
Martin
Sorry for the late response. My LazyLists package does that sort of thing. You wouldn't use yield though, I don't remember the syntax but I think it's either very obvious or layed out in the tests. If you still need this and you can't figure out quickly from the package, then let me know and I'll have a look.
On Wed, Feb 10, 2010 at 7:27 AM, Andreas Raab andreas.raab@gmx.de wrote:
Folks -
One thing I really like about Python is Generators (http://docs.python.org/tutorial/classes.html#generators). They allow code to provide a stream (iterator) interface where it's not easy to provide the interface explicitly. I.e., it would allow one to provide a stream interface to an arbitrary computation like:
gen := Generator on: [:yield| 3 to: 1 by: -1 do:[:i| yield value: i]]. gen next. "=>3" gen next. "=>2" gen next. "=>1" gen next. "=>nil"
This *ought* to be really simple to do in Smalltalk by using blocks and some voodoo in the execution engine. Has anyone ever done that?
Cheers, - Andreas
squeak-dev@lists.squeakfoundation.org
-
Andreas Raab -
Colin Putney -
Enrico Spinielli -
Ian Trudel -
Igor Stasenko -
Jason Johnson -
Levente Uzonyi -
Lukas Renggli -
Martin Kuball -
merlyn＠stonehenge.com