Protected types made of ADT's, and Passive Iterators

Protected types made of ADT's, and Passive Iterators

[John Woodruff]

I like to ask advice about an Ada programming problem I've been working.

By good fortune, I possess an inventory of well-made abstract data
types. And I want to use the objects provided by these ADT's in a
tasking-safe environment. So I determined that I might wrap the ADT into
a protected type.

Here's what I started with:

generic
    type Item is private;
package List is
    type Instance is private;
    procedure Insert (Into_List : in out Instance; The_Item : in Item);
    -- and lots more
private
    type Instance is new Integer;  -- of course not (but it compiles!)
end List;

I can make a generic package that encapsulates a protected instance of
List in a fairly straightforward way:

with List;
generic
    with package Inner_List is new List (<>);
package Prot_List is
    protected type Safe_List is
        entry Insert (The_Item : in Inner_List.Item);
    private
        In_Use : Boolean := False;
        Store : Inner_List.Instance;
    end Safe_List;
end Prot_List;

package body Prot_List is
    protected body Safe_List is
        entry Insert (The_Item : in Inner_List.Item) when not In_Use is
        begin
            In_Use := True;
            Inner_List.Insert (Into_List => Store, The_Item => The_Item);
            In_Use := False;
        exception
            when others =>
                In_Use := False;
        end Insert;
    end Safe_List;
end Prot_List;


So far, so good!

BUT the base list ADT provided a passive iterator, and I'd like to offer
that capability to the clients of my protected ADT as well.

Here is the way the base ADT specifies this ability:

generic
    type Item is private;
package List is
    type Instance is private;
    procedure Insert (Into_List : in out Instance; The_Item : in Item);

    generic
        with procedure Process
                          (The_Item : in Item; Continue : in out Boolean);
    procedure Iterate (Over_List : in Instance);
private
  -- as before
end List;

So my question is "How shall I enhance my Prot_List so it can define a
passive iterator?"

The only way I have found to now is to specify an additional parameter
when instantiating Prot_List - and let this parameter be a procedure to
be the iterating action:

with List;
generic
    with package Inner_List is new List (<>);
    with procedure Action (The_Item : in Inner_List.Item;
                           Continue : in out Boolean) is <>;
package Prot_List is
    protected type Safe_List is
    --  only change from before is to provide:
        procedure Iterate;
    end Safe_List;

end Prot_List;
 
This might be good for "partial credit" but I'm not satisfied: Iterate
in the protected list is more tightly bound to the abstract data type
than was the case in List.

Only *exactly one* iterator Action can ever be specified for an instance
of the protected list. Unlike the base ADT, it is not possible to use an
instance of the protected list object *without* specifying an Action
(that might never be used!).

And the "procedure iterate" is a part of the package Prot_List, unlike
in the base ADT where I am able to specify an Action is some far-away
scope.

Any advice that will make the full facility of passive iterator
available in the task-safe environment?

--
John Woodruff                                             N I F   \ ^ /
Lawrence Livermore National Lab                         =====---- < 0 >
925 422 4661                                                      / v \

Re: Protected types made of ADT's, and Passive Iterators

[Tom Moran]

> procedure Insert (Into_List : in out Instance; The_Item : in Item);

>    generic
>        with procedure Process
>                          (The_Item : in Item; Continue : in out Boolean);
>    procedure Iterate (Over_List : in Instance);
What happened in the single tasking version when an Insert occurred
during an Iterate?  What should happen in the multi-tasking version?
Should an Insert be locked out during an Iterate?  Or just during the
step from one item to the next? Or something else?
  How about adding to the list a protected component that was
essentially an Access_Allowed flag, ie, put a protected component into
the list, instead of putting the list into a protected record.

Re: Protected types made of ADT's, and Passive Iterators

[Matthew Heaney]

woodruff@tanana.llnl.gov (John Woodruff) writes:

> Any advice that will make the full facility of passive iterator
> available in the task-safe environment?

Can you give me a qualitative description of your problem?  

What's wrong with this:

generic
   with procedure Process 
      (Item : in out Collection_Item;
       Quit : in out Boolean);
procedure Modify_Items (Collection : in out Collection_Type);


procedure Modify_Items (Collection : in out Collection_Type) is

   Quit : Boolean := False;
   List : List_Type;
begin

   Seize (Collection.Guard);

   List := Collection.List;

   for Index in Positive range 1 .. Collection.Number_Of_Items loop

      Process (List.Item, Quit);

      exit when Quit;

      List := List.Next;

   end loop;

   Release (Collection.Guard);

end Modify_Items;


I noticed you used a list.  Be careful.  I list is a polylithic
structure, which is made for structure sharing.  Are you sure you don't
want a monolithic component (like a collection, or queue, etc)?

Your question "How do I make a list task safe?" is a little like asking
"What is the sound of one hand clapping?"  The question itself is all
wrong, because of an "abstraction-level mismatch."

Typically, you use a list to implement a container, you don't use a list
directly.  Make the monolithic container abstraction task safe, not a
list abstraction.

Re: Protected types made of ADT's, and Passive Iterators

[Tom Moran]

>procedure Modify_Items (Collection : in out Collection_Type) is
>...
>begin
>   Seize (Collection.Guard);
> do stuff
> Release(Collection.Guard);
>end Modify_Items;
  A way to lessen the chance of missing/excess Seize/Release is to
make a controlled type
  type Ptr_To_Collection_Type is access all Collection_Type;
  type Check_Busy_Type(P : Ptr_To_Collection_Type) is new
Ada.Finalization.Controlled with null record;.
  Inside any routine that needs to have serialized access to a
Collection_Type, put a declaration, eg
procedure Modify_Items (Collection : in out Collection_Type) is
  Grab : Check_Busy_Type(access Collection);
...
begin
  Then the Initialize of Check_Busy_Type will be certainly be called
and can do the Seize, and the Finalize can do the release.  It just
requires one line of code (the "Grab" declaration) added to existing
routines and does not depend on the programmer remembering to Seize
and Release at the right places.  (I simplify, but just slightly.)

Re: Protected types made of ADT's, and Passive Iterators

[Mats Weber]

Matthew Heaney wrote:

> What's wrong with this:

You need an exception handler to release the resource on a failure. Note that
almost anything can be raised in Process.

> generic
>    with procedure Process
>       (Item : in out Collection_Item;
>        Quit : in out Boolean);
> procedure Modify_Items (Collection : in out Collection_Type);
> 
> procedure Modify_Items (Collection : in out Collection_Type) is
> 
>    Quit : Boolean := False;
>    List : List_Type;
> begin
> 
>    [as before]
> 
>    Release (Collection.Guard);

  exception
     when others =>
        Release (Collection.Guard);
        raise;
> 
> end Modify_Items;

Re: Protected types made of ADT's, and Passive Iterators

[Mats Weber]

John Woodruff wrote:

> I can make a generic package that encapsulates a protected instance of
> List in a fairly straightforward way:

> BUT the base list ADT provided a passive iterator, and I'd like to offer
> that capability to the clients of my protected ADT as well.

This comes from Ada 95's failure to recognize generics as operations of a
type. You cannot declare generic task entries or generic protected operations.

The only way around the problem is to have a semaphore protecting the data in
your list, but there is no easy way of encapsulating your data into a task
safe construct (task or protected type).

I have discussed this issue in detail in my thesis
<http://lglwww.epfl.ch/Team/MW/Ada-Extensions/Ada-Extensions.html>.

I have some code doing what you want (implement an ADT and its protected form
with the same specification) for AVL trees. Mail me if you are interested.

Re: Protected types made of ADT's, and Passive Iterators

[Matthew Heaney]

Mats Weber <Mats.Weber@elca-matrix.ch> writes:

> You need an exception handler to release the resource on a failure. Note that
> almost anything can be raised in Process.

Agreed.  Actually, what I had in mind (and didn't show) was using a
controlled type to lock and unlock the resource automatically:

   procedure Modify_Items (...) is

      Control : Collection_Control (Collection'Access);
   ...

The Collection_Control object calls Seize during Initialize, and Release
during Finalize.

I omitted the error handling only to keep the example simple.  I should
have figured someone would catch that.

Thanks for the correction.

Matt