Re: Generic Package

[Georg Bauhaus <bauhaus@futureapps.de>]

On Sun, 2007-04-29 at 10:19 +0200, Dmitry A. Kazakov wrote:

> > my containers would be providing iteration if they can do one of
> > 
> > - take a subprogram (e.g.) and call it for each of a collection
> >   of elements
> > 
> > - provide access to an element and then the next if any where the
> >   meaning of "next" is specified in the collection's contract 
> >
> > The amount of determinism need not be 100%. E.g., the post-condition
> > if Iterate that each element is visited once, in no particular order,
> > seems reasonable to me.
> 
> Consider the precondition of the code performed for each element. It is
> "here is an unvisited element" You can easily state it for the second case,
> because you have the iterator's value. For the former case you have a
> problem, because the precondition of the subprogram cannot be formulated
> and hence verified in any way. 

Iteration in For_Each is controlled by the iterator For_Each, hence
the iterator will make sure that the subprogram passed to For_Each
will see each element once; that's a condition entirely outside
the reach of my generic actual subprogram (or subprogram pointer).
But so what? That's desirable.
My subprogram can hardly be arranged to be called with an element
more than once by For_Each, or not at all (instantiation not
being recursive in Ada):
"your subprogram is called with each element once" is part of the
contract of For_Each.

So it is not a question of trusting the iterator but rather
a mere consequence of trust in the iterator being defined
as required by the specification of iterator.


> > Is there iteration in the following SETL expression?
> > 
> >   Result := { x : x in {1, 3, 24, 17, 11} | P(x) };
> 
> Iteration in what? In the language construct? In Result? Consider a
> possibility that Result were computed at compile time. Would it still be
> iteration?

That's the point, there is iteration in this set former, but it
happens behind the scene: on an AS-IF basis, it does not even matter
when (or even if) iteration is happening; all that counts is that
you can explain the meaning of the set former in terms of
iteration. In fact, IIRC, SETL does say that the elements
of {1, 3, 24, 17, 11} are picked in some order and checked
against P.

You build sets and you give estimates of O(f(n)) based on the little
that is know about how iteration is performed in set formers.