Re: Look what I caught! was re:Ada paper critic

["Matthew Heaney" <mheaney@on2.com>]

"Hyman Rosen" <hyrosen@mail.com> wrote in message
news:3D10E366.2010303@mail.com...
> Robert A Duff wrote:
> >
> > Really?  I thought the above was OK.  The STL of C++ depends heavily on
> > this idiom.  Is this a difference between C and C++?  If so, what's the
> > rationale (in C)?
>
> It's not OK, and the STL never uses this idiom. The
> STL uses half-open intervals [begin,end) where the
> begin iterator points to the start of the sequence
> being manipulated, and the end iterator points to
> one past the end of the sequence being manipulated,
> and the canonical STL algorithm loop is
>
> while (begin != end) { operate_on(*begin++); }

STL iterators are a generalization of normal pointers.

It is true that you can't address the element "before" the start of the
array, because the compiler can allocate the array at the base of a segment,
which doesn't have a "before" address.

To iterate in reverse, and use a sentinel allowing you to fall off the
beginning of the sequence to terminate the iteration, the STL uses a reverse
iterator which is implemented as a wrapper around a normal, forward iterator
(which you can always recover using the base() member function of the
reverse iterator class).

You don't really use roaming pointers in Ada; rather, you use an array
object and a separate index.  You never index the array prior to the first
element of the array (nor past the last element, for that matter), but of
course the value of the index can have a value the preceeds the T'First of
the array.

This has precedent in Ada; for example, you often see string searches
implemented this way:

   function Find (S : String; C : Character) return Natural;

Here, the function returns the value 0 to indicate that the character C
wasn't found in array (string) S.

In Charles, I have generalized the STL iterator behavior, such that you're
allowed to have an iterator that designates the element "before" the start
of the sequence.

The Front iterator value has the sense of Index_Subtype'Pred
(Array_Object'First), and the Back iterator value has the sense of
Index_Subtype'Succ (Array_Object'Last).  The First and Last iterators have
their traditional sense.

The complete mapping is:

   Charles      STL
   --------      ---
   Front        <no analog>
   First          begin()
   Last          iter = end(), --iter;
   Back        end()

The loop above can be written as:

declare
   I : Iterator_Type := First (C);
   J : constant Iterator_Type := Back (C);
begin
   while I /= J loop
      E := Element (I);
     <do something with E>
      I := Succ (I);
   end loop;
end;

Of course, it's often simpler to just use a passive iterator, similer to an
STL algorithm:

declare
   procedure Process (E : T) is
   begin
      <do something with E>
   end;

   procedure Iterate is new Generic_Select_Elements (Process);
begin
   Iterate (First (C), Back (C));
end;

In C++, (non-const) iterators return T&.  You don't have reference types in
Ada, but you can accomplish something very similar using access types.  All
the containers in Charles have a generic operation for returning an access
type designating the container element (which are always aliased).

For example, given a subprogram like this:

procedure Do_Something (E : in out T);

then you can do this:

type T_Access is access all T;
for T_Access'Storage_Size use 0;

function To_Access is new Generic_Element (T_Access);

I : Iterator_Type := First (C);
J : constant Iterator_Type := Back (C);

while I /= J loop
   declare
      E : Element_Type renames To_Access (I).all;
   begin
      Do_Something (E);
   end;

   I := Succ (I);
end loop;

which is exactly analogous to this STL fragment:

void do_something(t& e);

iterator i = c.begin();
const iterator j = c.end();

while (i != j)
{
   t& e = *i;
   do_something(e);
   ++i;
}


> The "one past the end" pointer can be logical instead
> of physical, depending on the underlying container, but
> the algorithms don't care.

That's also true in Charles.  For example, the copy algorithm spec looks
like this:

generic

   type Source_Type is private;

   type Target_Type (<>) is limited private;

   with procedure Assign
     (Target : in Target_Type;
      Source : in Source_Type) is <>;

   with procedure Succ (Source : in out Source_Type) is <>;

   with procedure Succ (Target : in out Target_Type) is <>;

   with function "=" (L, R : Source_Type) return Boolean is <>;

procedure Charles.Algorithms.Generic_Copy
  (First, Back : in     Source_Type;
   Target        : in out Target_Type);

You don't have automatic instantiation in Ada as you have in C++, but you
don't really need it.  An instantiation of the algorithm above would look
like this:

declare
   procedure Assign (T : P1.Iterator_Type; S : P2.Iterator_Type) is
   begin
      Replace_Element (T, By => Element (S));
   end;

   procedure Copy is
      new Generic_Copy
        (P2.Iterator_Type;
         P1.Iterator_Type);  --everything else defaults

   I : P1.Iterator_Type := First (C2);
begin
   ...
   Copy (First (C1), Back (C1), I);
end;

This is why reverse iterators aren't needed, either.  All you need to do to
iterate over the source in reverse is supply a different function as the
generic actual:

declare
   procedure Assign (T : P1.Iterator_Type; S : P2.Iterator_Type) is
   begin
      Replace_Element (T, By => Element (S));
   end;

   procedure Copy is
     new Generic_Copy
      (P2.Iterator_Type;
       P1.Iterator_Type,
       Assign,
       Pred);   -- this line is different

   I : P1.Iterator_Type := First (C2);
begin
   ...
   Copy (Last (C1), Front (C1), I);   --this is dif't too
end;

Of course, it's usually simpler to just use a passive iterator:

declare
   I : P1.Iterator_Type := First (C2);

   procedure Process (E : T) is
   begin
      Replace_Element (I, By => E);
      I := Succ (I);
   end;

   procedure Iterate is
     new P2.Generic_Reverse_Select_Elements (Process);
begin
   Iterate (First (C1), Back (C1));
end;

You can even iterate over the target container in reverse using this
technique:

declare
   I : P1.Iterator_Type := Last (C2);

   procedure Process (E : T) is
   begin
      Replace_Element (I, By => E);
      I := Pred (I);
   end;

   procedure Iterate is
      new P2.Generic_Select_Elements (Process);
begin
   Iterate (First (C1), Back (C1));
end;


> The code one writes for something like copy (copy itself is
> part of the standard library) is completely ignorant of these
> shenaningans. It looks like a simple pointer loop -
>
> template<typename II, typename OI>
> OI copy(II begin, II end, OI to)
> {
> while (begin != end)
> *to++ = *begin++;
> return to;
> }


The copy algorithm in Charles is implemented this way:

procedure Charles.Algorithms.Generic_Copy
  (First, Back : in     Source_Type;
   Target      : in out Target_Type) is

   Source : Source_Type := First;
begin
   while Source /= Back loop

      Assign (Target, Source);

      Succ (Source);

      Succ (Target);

   end loop;
end Charles.Algorithms.Generic_Copy;

which is basically the same as in the C++ example above.

You can get the latest version of Charles at my home page:

http://home.earthlink.net/~matthewjheaney/charles-20020923.zip

I'll probably submit a paper to the Ada-Europe conference about Charles.