Bill Homer writes:
> Before the current discussion dies away, I'd like to pursue the
> question of what could be done with the restrict qualifier alone,
> and whether higher level constructs are required.
Great, lets continue!
> Let me make some claims, and invite your comments.
>
> 1. There is a straightforward extension of the restrict
> qualifier, based on its specification in C, allowing it to
> qualify reference types and the "this" pointer.
>
> 2. The restrict qualifier is compatible with the iterator style
> of programming. In particular:
>
> typedef double * restrict T;
>
> void f(T a, T a_end, T b) {
> while(a != a_end) {
> *a++ = *b++;
> }
> }
Ok, lets look at a generic version of this example:
template <class Iter1, class Iter2>
void f(Iter1 a, Iter1 a_end, Iter2 b) {
while (a != a_end)
*a++ = *b++;
}
We want to be able to make the same kind of aliasing assertion as in
the non-generic version. That is, that "a" doesn't alias with "b".
First off, you can't make the same kind of assertion if you use the
technique suggested in part 4 below. In the above example we aren't
dealing with a container, and don't have a choice between using the
const_iterator, restrict_iterator, or const_restrict_iterator
typedefs. Instead, we need to express something more like this:
template <class Iter1, class Iter2>
void f(restrict Iter1 a, Iter1 a_end, Iter2 b) {
while (a != a_end)
*a++ = *b++;
}
However, this is a *big* step from the non-generic case. Why? Because
the iterator can (often will) be a user-defined type. The iterator
operations are now functions:
operator++()
operator*()
operator!=()
which could potentially have side-effects and do all kinds of nasty
things. In addition the iterator object may contain pointers to a
bunch of different things.
In addition, lots of people in the OO community prefer a different
syntax (horrors) for iterators:
template <class Iter1, class Iter2>
void f(restrict Iter1 a, Iter2 b) {
while (! a.finished()) {
a.set(b.get());
a.next();
b.next();
}
}
Also note that we're not only talking about member functions, the
operators like != are often defined as globals that take two
arguments.
So the generalization to iterators really means generalizing to any
object and any function.
I don't see how to handle generic algorithms and iterators without
opening a whole can of worms. However, I think it is still worth while
to attack this problem.
In the above example, what the compiler needs to know is a summary of
the effects (ref,kill,etc.) of each of the iterator's operator
functions. Also it needs to know that whatever lvalues can be access
directly or indirectly via the object returned by operator*() do not
alias between "a" and "b". I'm a bit doubtful that all of this
information can be summed up with a single restrict keyword.
> 4. For generic programming, the restrict qualifier can be
> packaged in much the same way as the const qualifier.
> In particular, we could add a typedef for, say,
> restrict_iterator to those for iterator and const_iterator
> in an STL-style container. So, for example, if an
> implementation uses (void *) members for the links in the
> iterator class for list, then it would use (void * restrict)
> members for the links in the restrict_iterator class.
> (Those members will have to be cast to other types, but the
> semantics of the restrict qualifier is not affected by that.)
>
> Note that only a new typedef name is added, not new
> semantics for the restrict qualifier.
>
> Note that restrict_const_iterator might also be interesting,
> because traversing a list with such an iterator asserts that
> its nodes (both values and links) will not be modified,
> either in that loop or anywhere else during the execution of
> the block in which the iterator is declared.
Actually, the fact that we are required to have typedefs for both
iterators and const_iterators is already annoying. And don't forget
reverse iterators: so we'd have restrict_const_reverse_iterator's.
Cheers,
Jeremy
----------------------------------------------------------------------
Jeremy Siek
Ph.D. Candidate email: jsiek@engr.sgi.com
Univ. of Notre Dame work phone: (650) 933-8724
and cell phone: (415) 377-5814
C++ Library & Compiler Group fax: (650) 932-0127
SGI www: http://www.lsc.nd.edu/~jsiek/
----------------------------------------------------------------------
--------------------- Object Oriented Numerics List --------------------------
* To subscribe/unsubscribe: use the handy web form at
http://oonumerics.org/oon/
* If this doesn't work, please send a note to owner-oon-list@oonumerics.org
This archive was generated by hypermail 2b29 : Wed Feb 20 2002 - 03:20:11 EST