Recently I've read couple of articles about generators in Phyton. I
like the idea.
GNU Smalltalk added generators (implemented with using of
continuations) in its last version.
I've just ported it in dolphin 6.1, keeping original comments, and
added some samples.
Below is sources of this small package.
--------------------------------------------------------------------------- --------------------
| package |
package := Package name: 'Generators'.
package paxVersion: 1;
basicComment: ''.
package basicPackageVersion: '0.002'.
package classNames
add: #Generator;
add: #GeneratorSamples;
yourself.
package methodNames
add: #Continuation -> #callCC;
add: 'Continuation class' -> #escapeDo:;
yourself.
package binaryGlobalNames: (Set new
yourself).
package globalAliases: (Set new
yourself).
package setPrerequisites: (IdentitySet new
add: '..\Object Arts\Dolphin\Base\Dolphin';
add: '..\Object Arts\Dolphin\System\Continuations\Dolphin
Continuations';
yourself).
package!
"Class Definitions"!
Object subclass: #GeneratorSamples
instanceVariableNames: ''
classVariableNames: ''
poolDictionaries: ''
classInstanceVariableNames: ''!
Stream subclass: #Generator
instanceVariableNames: 'next genCC consCC atEnd'
classVariableNames: ''
poolDictionaries: ''
classInstanceVariableNames: ''!
"Global Aliases"!
"Loose Methods"!
!Continuation methodsFor!
callCC
"Activate the original continuation, passing back in turn a
continuation
for the caller. The called continuation becomes unusable, and
any attempt to reactivate it will cause an exception. This is not
a limitation, in general, because this method is used to replace a
continuation with another (see the implementation of the Generator
class)."
| cont |
cont := Continuation fromContext: Processor activeProcess topFrame
sender.
^self continue: stack with: cont! !
!Continuation categoriesFor: #callCC!public! !
!Continuation class methodsFor!
escapeDo: aBlock
"Pass a continuation to the one-argument block, knowing that aBlock
does not fall off (either because it includes a method return, or
because it yields control to another continuation). If it does,
an exception will be signalled and the current process terminated."
aBlock value: (self fromContext: Processor activeProcess topFrame
sender).
self error: 'Error in continuation'.
Processor activeProcess terminate! !
!Continuation class categoriesFor: #escapeDo:!instance creation!
public! !
"End of package definition"!
"Source Globals"!
"Classes"!
GeneratorSamples guid: (GUID fromString: '{99B83CDC-C6F0-4BDE-
B6EC-71C0875EE08A}')!
GeneratorSamples comment: ''!
!GeneratorSamples categoriesForClass!Kernel-Objects! !
!GeneratorSamples class methodsFor!
excludeMultipliersOf: multiplier from: aStreamOfInts
^Generator on:
[:gen |
| each |
[each := aStreamOfInts next.
(each rem: multiplier) ~= 0 ifTrue: [gen yield: each]] repeat]!
fibonacciGenerator
"
self showFirst: 30 ofStream: self fibonacciGenerator.
"
^Generator on:
[:gen |
| pair |
pair := Array with: 1 with: 1.
[pair at: 2 put: pair first + pair last.
pair at: 1 put: pair last - pair first.
gen yield: pair first]
repeat]!
powersOfTwo
"
self showFirst: 100 ofStream: self powersOfTwo.
"
^Generator inject: 2 into: [:num | num * 2]!
primeNumbersGenerator
"
self showFirst: 50 ofStream: self primeNumbersGenerator.
This implementation is using the Eratosthenes sieve algorithm.
"
| primeGen |
primeGen := Generator inject: 2 into: [:x | x + 1].
^Generator on:
[:gen |
| prime |
[prime := primeGen next.
gen yield: prime.
primeGen := self excludeMultipliersOf: prime from: primeGen]
repeat]!
showFirst: elements ofStream: gen
elements timesRepeat:
[Transcript
print: gen next;
cr]! !
!GeneratorSamples class categoriesFor: #excludeMultipliersOf:from:!
private! !
!GeneratorSamples class categoriesFor: #fibonacciGenerator!public! !
!GeneratorSamples class categoriesFor: #powersOfTwo!public! !
!GeneratorSamples class categoriesFor: #primeNumbersGenerator!
public! !
!GeneratorSamples class categoriesFor: #showFirst:ofStream:!public! !
Generator guid: (GUID fromString: '{58F0F6E3-4B37-455C-
BB23-4F3E3B33E3C7}')!
Generator comment: 'Original GNU Smalltalk comments:
-------------------------------------------
A Generator object provides a way to use blocks to define a Stream
of many return values. The return values are computed one at a time,
as needed, and hence need not even be finite.
A generator block is converted to a Generator with "Generator
on: [...]". The Generator itself is passed to the block,
and as soon as a message like #next, #peek, #atEnd or #peekFor: is
sent to the generator, execution of the block starts/resumes and
goes on until the generator''''s #yield: method is called: then the
argument of #yield: will be the Generator''''s next element. If the
block goes on to the end without calling #yield:, the Generator
will produce no more elements and #atEnd will return true.
You could achieve the effect of generators manually by writing your
own class and storing all the local variables of the generator as
instance variables. For example, returning a list of integers could
be done by setting a variable to 0, and having the #next method
increment it and return it. However, for a moderately complicated
generator, writing a corresponding class would be much messier (and
might lead to code duplication or inefficiency if you want to support
#peek, #peekFor: and/or #atEnd): in general, providing a #do:-like
interface is easy, but not providing a Stream-like one (think binary
trees).
The idea of generators comes from other programming languages, in
particular this interface looks much like Scheme streams and Python
generators. But Python in turn mutuated the idea for example from
Icon, where the idea of generators is central. In Icon, every
expression and function call behaves like a generator, and if a
statement manages scalars, it automatically uses up all the results
that the corresponding generator provides; on the other hand, Icon
does not represent generators as first-class objects like Python and
Smalltalk do.'!
!Generator categoriesForClass!Collections-Streams! !
!Generator methodsFor!
atEnd
"Answer whether more data can be generated."
atEnd isNil ifTrue: [genCC := genCC callCC].
^atEnd!
forkOn: aBlock
"When initializing, we just store the current continuation and exit;
the ^self is where the control flow is actually split. When #next
is
called first, the code after the continuation is executed, which
executes the generator block and finally resumes execution of the
consumer when the block leaves.
This is the only time we create a continuation with a block; after
this, we just replace a continuation with another through
Continuation>>#callCC."
consCC := Continuation escapeDo:
[:cc |
genCC := cc.
atEnd := nil.
^self].
atEnd := true.
genCC := nil.
aBlock value: self.
consCC oneShotValue!
next
"Evaluate the generator until it generates the next value or
decides that nothing else can be generated."
| result |
self atEnd ifTrue: [^self errorEndOfStream].
result := next.
next := nil.
atEnd := nil.
^result!
peek
"Evaluate the generator until it generates the next value or
decides that nothing else can be generated, and save the value
so that #peek or #next will return it again."
self atEnd ifTrue: [^nil].
^next!
peekFor: anObject
"Evaluate the generator until it generates the next value or
decides that nothing else can be generated, and if it is not equal
to anObject, save the value so that #peek or #next will return it
again."
self atEnd
ifTrue:
[self pastEnd.
^false].
^next = anObject
ifTrue:
[next := nil.
atEnd := nil.
true]
ifFalse: [false]!
yield: anObject
"When entering from the generator the code in the block is executed
and
control flow goes back to the consumer. When entering from the
consumer,
the code after the continuation is executed, which resumes execution
of
the generator block."
atEnd := false.
next := anObject.
consCC := consCC callCC.
"Make sure that an exception (or any other event that causes #yield:
not
to be invoked again) terminates the generator. Also, generators
should
not reenter."
genCC := nil.
atEnd := true! !
!Generator categoriesFor: #atEnd!public!streaming! !
!Generator categoriesFor: #forkOn:!private! !
!Generator categoriesFor: #next!public!streaming! !
!Generator categoriesFor: #peek!public!streaming! !
!Generator categoriesFor: #peekFor:!public!streaming! !
!Generator categoriesFor: #yield:!public!streaming! !
!Generator class methodsFor!
inject: aValue into: aBlock
"Return an infinite generator; the first item is aValue, the
following
items are obtained by passing the previous value to aBlock."
^self on:
[:gen |
| last |
last := aValue.
[gen yield: last.
last := aBlock value: last] repeat]!
on: aBlock
"Return a generator and pass it to aBlock. When #next is sent
to the generator, the block will start execution, and will be
suspended again as soon as #yield: is sent from the block to
the generator."
^(self basicNew)
forkOn: aBlock;
yourself! !
!Generator class categoriesFor: #inject:into:!instance creation!
public! !
!Generator class categoriesFor: #on:!instance creation!public! !
"Binary Globals"!
