Generators in Smalltalk?
Locked
 
|
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 <[hidden email]>: > 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 > > -- http://mecenia.blogspot.com/ |
|
|
In reply to this post by Andreas.Raab
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 |
Re: Generators in Smalltalk?
|
|
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 > > |
|
|
In reply to this post by Colin Putney
http://source.lukas-renggli.ch/continuations/Generator-lr.3.mcz
Lukas On 10 February 2010 06:49, Colin Putney <[hidden email]> 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 http://www.lukas-renggli.ch |
|
|
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 <[hidden email]> 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 <[hidden email]> 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 http://www.lukas-renggli.ch |
|
|
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 |
|
|
In reply to this post by Levente Uzonyi-2
SICP to the rescue
<a href="http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5.2">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 <[hidden email]> wrote:
-- Enrico Spinielli "Do Androids dream of electric sheep?"— Philip K. Dick "Hear and forget; see and remember;do and understand."—Mitchel Resnick |
Re: Generators in Smalltalk?
|
|
On Wed, 10 Feb 2010, Enrico Spinielli wrote:
> SICP to the rescue > <a href="http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5.2">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 <[hidden email]> 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 > |
Re: Generators in Smalltalk?
|
|
>>>>> "Levente" == Levente Uzonyi <[hidden email]> writes:
Levente> On Wed, 10 Feb 2010, Enrico Spinielli wrote: >> SICP to the rescue >> <a href="http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5.2">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. -- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 <[hidden email]> <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 |
Re: Generators in Smalltalk?
|
|
On Wed, 10 Feb 2010, Randal L. Schwartz wrote:
>>>>>> "Levente" == Levente Uzonyi <[hidden email]> writes: > > Levente> On Wed, 10 Feb 2010, Enrico Spinielli wrote: >>> SICP to the rescue >>> <a href="http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5.2">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 > <[hidden email]> <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 > |
|
|
In reply to this post by Lukas Renggli
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 <[hidden email]> 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. > Maybe its worth adding separate category? > Cheers, > - Andreas > > -- Best regards, Igor Stasenko AKA sig. |
|
|
In reply to this post by Andreas.Raab
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 |
|
|
In reply to this post by Andreas.Raab
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 <[hidden email]> 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 > > |
|
|
In reply to this post by Andreas.Raab
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 <[hidden email]> 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 > > |
«
Return to Squeak - Dev
|
1 view|%1 views
| Free forum by Nabble | Edit this page |