Generators in Eiffel?
John Pinto
iterator/generator capability and also the recent addition to Eiffel
of agents in order to write generic iterators.
There is usually a strong connection between iterators and generators
in that many iterators can be written very simply using generators.
This lead me to a question, is there a way in Eiffel to write
generators in the spirit found in the new Python 2.2 release? (Which
was based on the idea of generators in Icon. See
http://www.amk.ca/python/2.2/index.html#SECTION000400000000000000000
for a gentle introduction to this new Python feature)
If not, is this an appropriate new language extension for Eiffel?
I suspect that utilizing SCOOP maybe a solution to this question, but
I'm not that proficient in Eiffel to say for sure.
I have had to write generators in C and they're not pretty. If I have
to write them in Eiffel (which I plan on doing soon), I'd like to know
there is a simple and elegant way to do it (just as writing almost
anything in Eiffel tends to be!).
Thanks for any light that can be shed on this conundrum.
--> John
Friedrich Dominicus
> I was recently reading about the recent additions to Python(2.2) of an
> iterator/generator capability and also the recent addition to Eiffel
> of agents in order to write generic iterators.
>
> There is usually a strong connection between iterators and generators
> in that many iterators can be written very simply using generators.
Well may I ask what is so wonderful about iterators and generators?
see e.g Iterators: Signs of Weakness in Object Oriented Languages
what about agents or higher order functions?
With anonymous agents you get IMHO a much nicer solution.
>
> This lead me to a question, is there a way in Eiffel to write
> generators in the spirit found in the new Python 2.2 release? (Which
> was based on the idea of generators in Icon. See
> http://www.amk.ca/python/2.2/index.html#SECTION000400000000000000000
> for a gentle introduction to this new Python feature)
Well it certainly can be done. The question is why should one do it?
>
> If not, is this an appropriate new language extension for Eiffel?
IMHO no. The right things seems to me using higher order functions on
different datastructures.
>
> I suspect that utilizing SCOOP maybe a solution to this question, but
> I'm not that proficient in Eiffel to say for sure.
I doubt it, IIRC is SCOOP about concurrency in Eiffel.
Regards
Friedrich
Eirik Mangseth
"Friedrich Dominicus" <fr...@q-software-solutions.com> wrote in message
news:87sncuz...@frown.here...
> pint...@yahoo.com (John Pinto) writes:
>
> > I was recently reading about the recent additions to Python(2.2) of an
> > iterator/generator capability and also the recent addition to Eiffel
> > of agents in order to write generic iterators.
> >
> > There is usually a strong connection between iterators and generators
> > in that many iterators can be written very simply using generators.
> Well may I ask what is so wonderful about iterators and generators?
>
> see e.g Iterators: Signs of Weakness in Object Oriented Languages
Links, if any? ISBN?
-- eirik
"If I can't Eiffel in heaven, I won't go"
Friedrich Dominicus
> "Friedrich Dominicus" <fr...@q-software-solutions.com> wrote in message
> news:87sncuz...@frown.here...
> > pint...@yahoo.com (John Pinto) writes:
> >
> > > I was recently reading about the recent additions to Python(2.2) of an
> > > iterator/generator capability and also the recent addition to Eiffel
> > > of agents in order to write generic iterators.
> > >
> > > There is usually a strong connection between iterators and generators
> > > in that many iterators can be written very simply using generators.
> > Well may I ask what is so wonderful about iterators and generators?
> >
> > see e.g Iterators: Signs of Weakness in Object Oriented Languages
Sorry
Iterators: Signs of Weakness in Object-Oriented Languages
ftp://ftp.netcom.com/pub/hb/hbaker/Iterator.html
ftp://ftp.netcom.com/pub/hb/hbaker/Iterator.ps.Z
Don't know if one can get it there but I have read it some days ago
somewhere
Regards
Friedrich
Dan Andersson
Dan Andersson
have much to do with iterators, apart from a supeficial resemblace. So
the paper you refer to is kind of mooth. To properly mimic generators
you need functions as first class values and the ability to capture
continuations. That Eiffel does not have. But most computer languages
are turing complete. So it is possible to do the same using Agents.
MvH Dan Andersson
Greg C
A reference that works for the paper "Iterators: Signs of Weakness in
Object-Oriented Languages" is here:
http://citeseer.nj.nec.com/55669.html
Access the PDF cached version from the upper right corner.
At least two Eiffel compilers suppor agents, SmallEiffel and ISE, and
I believe the other vendors have committed to supporting this feature
in the future.
Agents are function closures, referred to in Baker's paper above. I've
been working a bit with agents and as far as I can tell they could
emulate the Python generator feature you cite.
But having agents, or closures, can eliminate the need for iterators
altogether. For example, the agent-enabled Eiffel compilers have
container classes that provide functions like "do_all" which takes an
agent that can then be applied to all the elements of an array.
Since the agent is a closure, the agent can be defined with some of
its parameters set at the time its created, and others set at the time
its executed.
Here's a simple example that will run with a recent version of the
SmallEiffel beta.
--------------------------------
indexing
purpose:
"A simple example of using an agent with%N%
%the do_all feature from ARRAY. The feature%N%
%exclaim will print out each element of an%N%
%integer array, and if the valu of the element%N%
%exceeds its excitement threshold, it will%N%
%write out an exclamation. In this case,%N%
%the agent is a feature of the current class,%N%
%but it could just as easily reside in a%N%
%separate class.%N"
class EXAMPLE
creation make
feature
numbers: ARRAY[INTEGER] is -- our test array
once
create Result.from_collection(<<1,100,20,4,75>>)
end
exclaim(threshold, value: INTEGER) is
-- print out an integer, exclaim if its big
do
print(value.out)
if value >= threshold then
print(" -- WOW!%N")
else
print("%N")
end
end
feature
make is
do
-- apply the feature exclaim
-- as an agent on all the elements
-- in numbers.
--
numbers.do_all(exclaim(25,?))
end
end
------- output -----------
1
100 -- WOW!
20
4
75 -- WOW!
---------------------------
The things worth noting: the agent, "exclaim" receives the two
parameters, but one, the threshold, is set when the agent is created
in the call to do_all. The second parameter is passed by do_all down
to exclaim as do_all iterates over the container. Third, there's no
need for looping logic. Essentially, the guts of a loop have been
placed into a self-contained routine, and the container handles all
the looping and iteration issues.
Patrick Doyle
John Pinto <pint...@yahoo.com> wrote:
>
>I was recently reading about the recent additions to Python(2.2) of an
>iterator/generator capability and also the recent addition to Eiffel
>of agents in order to write generic iterators.
>
>There is usually a strong connection between iterators and generators
>in that many iterators can be written very simply using generators.
Does anyone have a reference that explains the difference between
generators and coroutines?
--
--
Patrick Doyle
doy...@eecg.toronto.edu
Frank Mitchell
> Sorry
>
> Iterators: Signs of Weakness in Object-Oriented Languages
> ftp://ftp.netcom.com/pub/hb/hbaker/Iterator.html
> ftp://ftp.netcom.com/pub/hb/hbaker/Iterator.ps.Z
>
> Don't know if one can get it there but I have read it some days ago
> somewhere
There are cached copies at http://citeseer.nj.nec.com/55669.html (PS and PDF).
Frank Mitchell
Greg C
Dan, what do you mean by "the ability to capture continuations"?
Darren New
> are turing complete. So it is possible to do the same using Agents.
FWIW, it's kind of useless to say "well, yes we can do that in Eiffel,
because Eiffel is turing complete." All that means is that Eiffel is
powerful enough to write an interpreter for a language that *does* have
completions (or whatever). Which is almost always overkill for solving
the problem at hand.
--
Darren New
San Diego, CA, USA (PST). Cryptokeys on demand.
Who is this Dr. Ibid anyway,
and how does he know so much?
John Pinto
> > iterator/generator capability and also the recent addition to Eiffel
> > of agents in order to write generic iterators.
> >
> > There is usually a strong connection between iterators and generators
> > in that many iterators can be written very simply using generators.
> >
>
>
> The things worth noting: the agent, "exclaim" receives the two
> parameters, but one, the threshold, is set when the agent is created
> in the call to do_all. The second parameter is passed by do_all down
> to exclaim as do_all iterates over the container. Third, there's no
> need for looping logic. Essentially, the guts of a loop have been
> placed into a self-contained routine, and the container handles all
> the looping and iteration issues.
OK, that was an example of using an agent but that's not quite what I
had in mind when I was speaking of a generator.
Baker gives a nice example regarding summing an array of integers:
Let's suppose we have a function that needs the values of the
intermediate sums of an array(let's say its going to print them out in
a table), let's also suppose we want to write a second function that
returns the intermediate sums of the summation process which the first
function will call successively to get those intermediate values. [A
more classic example is to return a sequence of Random Numbers]
Without a generator like facility, in order to code the second
function returning the intermediate sums you'd need to either:
1) save state between calls to the second function so that it can pick
up where it left off.
or
2) run the second function concurrently, writing the intermediate sums
to a queue, with the first function reading them from the queue. [
This is the co-routines solution that someone was looking for a
defintion of ]
However, with a generator facility, the compiler arranges for the
state of the second funtion to be saved and restored automatically.
(In Python, this is indicated by using a "yield" rather than a
"return")
I'm not quite sure how you get that kind of behaviour using agents.
Friedrich seems to indicate that a re-formulation of the problem using
agents maybe more appropriate but I'm not quite sure how to do that.
Can you shed some light Greg on how to accomplish this?
Thanks!
John
Darren New
> to a queue, with the first function reading them from the queue. [
> This is the co-routines solution that someone was looking for a
> defintion of ]
Not really. That would be a multithreaded solution. A coroutine is more
like having a "return" statement that when you call the function again,
it picks up after the return statement rather than at the beginning
again. There's still only one thread of control. Of course, you can
simulate coroutines with threads by having one thread in the function
tracing the program counter, and basically using synchronization
primitives to block the progress of one thread or the other. But
coroutines aren't really threads any more than exceptions or
once-functions are.
Doug Pardee
I would say that, no, it is not appropriate for Eiffel.
A generator is the antithesis of Command-Query Separation. It is a
query feature which returns a different result each time that it is
called. In addition, most generators would need the ability to return
some special value to indicate that the end of the sequence has been
reached. This is another technique which is considered undesirable.
Design by Contract(tm) is difficult to practice under these
circumstances.
To correct these problems, one would instead create a separate class
for the generator. This class would have query features something like
"exists", "at_end", and "item", and a command feature of "forth". The
result looks, not surprisingly, like an iterator class.
-- Doug Pardee dougp...@yahoo.com
John Pinto
Doug,
I still think the idea of a "co-routine" facility would be helpful in
implementing this kind of generator, even in a Design By Contract
style(or Command/Query Separation).
What would make it very helpful is it would relieve the programmer
from figuring out how to save/restore state between calls to forth().
Instead the compiler would arrange to save the state automatically, so
that when forth() is called again it could pickup where it left off in
its generation algorithm.
Now obviously this is totally un-necessary when its simple to
save/restore state between calls to forth(), but for many algorithms
its not so simple to do that. If the algorithm has deeply nested
loops and the generated result is generated in the middle of the most
deeeply nested of the loops, then its hard to save that state so it
can pickup where it left off on the next call to forth(). This is
where a "generator" or "co-routine" solution might be really
helpful/useful.
Thoughts?
Thanks!
John
Greg C
> > > iterator/generator capability and also the recent addition to Eiffel
> > > of agents in order to write generic iterators.
> > >
> > > There is usually a strong connection between iterators and generators
> > > in that many iterators can be written very simply using generators.
> > >
> >
> > <snip> ... Greg's code example ... <snip>
> >
>
> OK, that was an example of using an agent but that's not quite what I
> had in mind when I was speaking of a generator.
>
> Baker gives a nice example regarding summing an array of integers:
>
>
> Without a generator like facility, in order to code the second
> function returning the intermediate sums you'd need to either:
>
> 1) save state between calls to the second function so that it can pick
> up where it left off.
>
> or
>
> 2) run the second function concurrently, writing the intermediate sums
> to a queue, with the first function reading them from the queue. [
> This is the co-routines solution that someone was looking for a
> defintion of ]
>
> However, with a generator facility, the compiler arranges for the
> state of the second funtion to be saved and restored automatically.
> (In Python, this is indicated by using a "yield" rather than a
> "return")
>
> I'm not quite sure how you get that kind of behaviour using agents.
>
> Friedrich seems to indicate that a re-formulation of the problem using
> agents maybe more appropriate but I'm not quite sure how to do that.
>
> Can you shed some light Greg on how to accomplish this?
Well...
I could wave my hands and say that a if a generator is like a
coroutine which is like cooperative threading, then one could use
threads, assuming one has a compiler that supports them. But that
would be cheating, and is essentially your option #2.
Alternatively, if the generator or coroutines could be defined in such
a way that control to is always transfered at the end of the feature,
then it would be possible to agents as pointers to the object and the
features that define the coroutines. When the feature finishes its
work, it would set an agent to define the next coroutine to be
executed. Or turn control over to a coroutine scheduler which then
determines if there are any coroutines ready to execute. Any local
state would be stored in the ohject that defines the generator. This
implements your option #1.
Going back to option #2, a lot of the work that would need to be done
to set up generators could be done, I believe, with an appropriate
support library (including modifications to the GC) without any
fundamental change to the compiler. A generator would then be an
object that can be arbitrarily executed, has a readable state, and
"local" variables or state would be in private data.
Doing all this provides several basic features needed for
multithreading.
I'm going to noodle with this a bit more, and see if I can get a
better handle on how Baker's example is supposed to work.
Greg
Patrick Doyle
Dan Andersson <rhq...@tninet.se> wrote:
>
>But most computer languages are turing complete. So it is possible
>to do the same using Agents.
I'd just like to say once and for all that Turing equivalence has
nothing whatsoever to do with the desirability of language features.
One may define the expressive power of a language as the set of
algorithms which it can express. However, since any self-respecting
programming language is Turing equivalent (modulo finite memory),
this is a practically useless definition.
How, then should we define the "power" of a language? I think it
is appropriate to take inspiration from physics, in which power
is defined as work per unit time. A powerful language can be defined
as one which allows the programmer to cause the computer to do more
work in less time. That is, more computer work for less programmer
effort.
Effort could be expressed in terms of code complexity. By complexity,
I don't mean some touchy-feely notion of how hard code is to understand.
I mean asymptotic complexity of the appearance of language constructs
in a program text with respect to the tasks that program performs.
For instance, imagine using agents as iterators. Normal iterators
typically require a new iterator class for each collection class.
Thus, normal iterators require O(n) classes to be written, where
n is the number of collection classes. In contrast, the same effect
could be achieved by writing some small number (possibly zero) of
infrastructure classes, and then using an agent for each collection
class. The agents solution requires O(1) classes. This demonstrates
that Eiffel-with-agents is, in some sense, more powerful than
Eiffel-without-agents.
Granted, this is still not a very concrete measure yet, but it's
lightyears ahead of Turing equivalence, under which practically
all programming languages would be considered equally powerful;
while, of course, everyone knows that no language can compare to
the awesome power of Lisp. :-)
Patrick Doyle
>
>Let's suppose we have a function that needs the values of the
>intermediate sums of an array(let's say its going to print them out in
>a table), let's also suppose we want to write a second function that
>returns the intermediate sums of the summation process which the first
>function will call successively to get those intermediate values. [A
>more classic example is to return a sequence of Random Numbers]
>
>Without a generator like facility, in order to code the second
>function returning the intermediate sums you'd need to either:
>
>1) save state between calls to the second function so that it can pick
>up where it left off.
>
>or
>
>2) run the second function concurrently, writing the intermediate sums
>to a queue, with the first function reading them from the queue. [
>This is the co-routines solution that someone was looking for a
>defintion of ]
or
3) support lazy evaluation in your language, and then write a function
which returns an array whose nth element is the sum of the first n elements
in the input array.
John Pinto
>Alternatively, if the generator or coroutines could be defined in
such
>a way that control to is always transfered at the end of the feature,
>then it would be possible to agents as pointers to the object and the
>features that define the coroutines. When the feature finishes its
>work, it would set an agent to define the next coroutine to be
>executed.
Greg,
Usually in situations where "co-routines" are helpful, its difficult
to arrange for the control to be transferred at the end of the
feature; usually the appropriate point is in the middle of deeply
nested loops. So I'm not sure if an approach based on your
assumption would be the right approach.
Take a look at my reply to Doug earlier today in which I've tried to
give a little more detail about the kinds of situations where
"co-routines" are helpful. I still don't see how agents help in
anyway to solve the problems that "co-routines" were designed to
solve, except maybe as described below in building some kind of
COROUTINE class.
It still seems to me that the only general way to solve this problem
in Eiffel is to go down avenue #2 in my post, ie. having the
generating function run concurrently and putting its results into a
queue that is read by whatever features need the generated values from
the generator function.
Maybe its possible to create a COROUTINE class that would have all of
the mechanisms to make this work, so that it could be used whenever we
needed a generator function. Maybe its creation feature would get
passed an agent which generates the data and the COROUTINE class takes
care of putting the data into the queue and making it available to any
other features that need them. Maybe it could also take care of the
concurrency issues of running the agent. [ Not that I know how to do
any of this, or even if it could be done! ]
Thoughts?
Thanks!
John
Friedrich Dominicus
>
> 3) support lazy evaluation in your language, and then write a function
> which returns an array whose nth element is the sum of the first n elements
> in the input array.
Which is IMHO the "right thing"... ;)
Regards
Friedrich
Friedrich Dominicus
>
> Now obviously this is totally un-necessary when its simple to
> save/restore state between calls to forth(), but for many algorithms
> its not so simple to do that.
What is unclear about this:
(hack !)
class GENERATOR
creation
make
feature
make is
do
item := 0;
end;
next is
do
item := item + 1;
end
exhausted : BOOLEAN is False;
item: INTEGER;
end -- class GENERATOR
>If the algorithm has deeply nested
> loops and the generated result is generated in the middle of the most
> deeeply nested of the loops, then its hard to save that state so it
> can pickup where it left off on the next call to forth().
Again why?
class GENERATOR_USER
creation
make
feature
make is
local
i :INTEGER;
do
create gen.make;
from i := 1
until i > 10
loop
print ("gen.item = ");
print (gen.item);
print ('%N');
gen.next;
i := i + 1;
end;
end
feature {NONE}
gen: GENERATOR;
end
Generator is a perfect encapsulated object and wherever it is called
it has it's right state.
>This is
> where a "generator" or "co-routine" solution might be really
> helpful/useful.
No generators are IMHO the wrong solution. They are limited in
comparisoin to lazy evaluation and they are interchangeble with an own
Iterator object as pointed out in this dirty Eiffel.
Regards
Friedrich
Jim Weirich
> Here's a simple example that will run with a recent version of the
> SmallEiffel beta.
[... example elided ...]
Nice example, thanks.
Its been a while since I have read Meyer's paper on agents, but I
recall that anonymous agents are possible. Am I recalling correctly?
And if so, does SmallEiffel support that yet?
I've been doing some Ruby programming lately, and the ability to
create anonymous blocks (closures/agents) as needed has turn out to be
one of the attractive features of that language.
John Pinto
> pint...@yahoo.com (John Pinto) writes:
>
> >
> > Now obviously this is totally un-necessary when its simple to
> > save/restore state between calls to forth(), but for many algorithms
> > its not so simple to do that.
> What is unclear about this:
> (hack !)
>
> class GENERATOR
>
> creation
> make
>
> feature
> make is
> do
> item := 0;
> end;
>
> next is
> do
> item := item + 1;
> end
> exhausted : BOOLEAN is False;
>
> item: INTEGER;
>
>
>
> end -- class GENERATOR
Friedrich,
Its not that your example is unclear, but it is too simple. Its so
easy to save the state of the computation between calls to next() in
your example, thus its not really a candidate for showing the need for
"co-routines".
Something more like the following (C-hack) is where I might consider
co-routines:
next() is
do
for (i=0; i<100000000000; ++i)
for (j=0; j<i; ++j)
for (k=0; k<i+j; ++k)
last_value:= last_value + i*j*k; yield;
end
Then some other feature might need the sequence of values that
last_value takes on with each call to next(), assuming "yield" was the
"co-routine" interruption and continuation mechanism.
BTW, for everyone's benefit who's been following this. I went back to
OOSCv2 and saw that Meyer's dealt with co-routines in 2 chapters, the
one on concurrency(which has a partial implementation for co-routines)
and the other on Simula(which has an example of co-routine use).
Looking at Meyer's discussion, I don't see how agents contribute to
the solution of this kind of problem. I also don't think lazy
evaluation is the answer either, because without a "co-routine"
mechanism, you can't just call next() whenever you need to compute the
next last_value, even lazily.
So, I think the answer to my original question is (according to
Meyers) that "generators" can be programmed using the more generic
techniques of concurrency already present in Eiffel.
--> John
Friedrich Dominicus
>
> Its not that your example is unclear, but it is too simple. Its so
> easy to save the state of the computation between calls to next() in
> your example, thus its not really a candidate for showing the need for
> "co-routines".
Well it should not show the needs for co-routines but how useless IMHO
generators are.
The examples pointed to in Python looke like that:
for i in range(x):
yield i
That was called a generator.
>
> So, I think the answer to my original question is (according to
> Meyers) that "generators" can be programmed using the more generic
> techniques of concurrency already present in Eiffel.
Well it would be nice to know generators should be and what the other
things are.
Friedrich
e toffi
or just use iterators?
what really is the percieved benefit of generators/coroutines?
--
etoffi
Friedrich Dominicus
> why not instead pass an agent to the next function/feature?
> or just use iterators?
That sounds reasonable for me.
>
> what really is the percieved benefit of generators/coroutines?
Well I do not think that generators are necessary. It seems as if all
have agreed that having coroutines is a good thing....
Regards
Friedrich
Patrick Doyle
Friedrich Dominicus <fr...@q-software-solutions.com> wrote:
>eto...@bigfoot.com (e toffi) writes:
>
>> what really is the percieved benefit of generators/coroutines?
>
>Well I do not think that generators are necessary. It seems as if all
>have agreed that having coroutines is a good thing....
Not I. They're too stateful. Lazy evaluation is better.
Friedrich Dominicus
>
> Not I. They're too stateful. Lazy evaluation is better.
Well than I or you are not alone ;-)
Regards
Friedrich