Version 1.3 of ais/ai-00345.txt

Unformatted version of ais/ai-00345.txt version 1.3
Other versions for file ais/ai-00345.txt

!standard 3.04.03 (00)          03-09-28 AI95-00345/01
!class amendment 03-08-07
!status work item 03-09-28
!status received 03-06-12
!priority Medium
!difficulty Hard
!subject Protected and task interfaces
!summary
protected and task interfaces are proposed. A protected or task type may specify one or more interfaces as ancestors. The synchronizing operations of these interfaces are inherited by the protected or task type. if the operations are declared abstract in the interface, they must be overridden in the inheriting type.
!problem
The object-oriented features of Ada 95 are essentially disjoint with the multi-tasking features of Ada 95. This means that it is difficult to combine synchronization with type extension and polymorphism. Although there are some approaches to doing so using access discriminants, they tend to be a bit awkward, and they don't actually prevent unsynchronized access to the object designated by the access discriminant.
!proposal
Augment the syntax for tasks and protected type declarations to allow task and protected interfaces, as follows:
task_interface_declaration ::= task interface defining_identifier is [new task_interface_name {and task_interface_name} with] task_interface_definition;
task_interface_definition ::= {abstract_entry_declaration} end [task_identifier]
task_type_declaration ::= task type defining_identifier [known_discriminant_part] [is [new task_interface_name {and task_interface_name} with] task_definition];
protected_interface_declaration ::= protected interface defining_identifier is [new protected_interface_name {and protected_interface_name} with] protected_interface_definition;
protected_interface_definition ::= {protected_interface_item} end [protected_identifier]
protected_interface_item ::= abstract_subprogram_declaration | null_procedure_declaration | abstract_entry_declaration
protected_type_declaration ::= protected type defining_identifier [known_discriminant_part] is [new protected_interface_name {and protected_interface_name} with] protected_definition;
protected_operation_declaration ::= subprogram_declaration | null_procedure_declaration | entry_declaration | aspect_clause
abstract_entry_declaration ::= entry defining_identifier [(discrete_subtype_definition)] parameter_profile is abstract;
As with "normal" interfaces, a "concrete" type that inherits from an interface must override all abstract operations, but may inherit null procedures. We have not proposed null entries, since it is unclear what would be the barriers for those (True or False) or how they would fit into a task body (no accept statement?).
Objects of type <protected/task_interface>'Class could be used as the prefix in a call on a synchronizing operation, and a run-time dispatch would occur to the "appropriate" entry/protected subprogram.
Question: Should we allow declaration of operations outside the protected/task_interface definition that take directly a a protected or task interface, as opposed to the corresponding class-wide type?
Suggested answer: No, do not allow operations that directly take protected or task interfaces. This means we avoid the whole issue of non-synchronizing dispatching operations for these types, which would require something analogous to tagged-type dispatching tables. By limiting ourselves to synchronizing operations, the implementation burden for supporting protected and task interfaces should be minimized.
!wording
!example
protected interface Queue is -- Interface for a protected queue entry Enqueue(Elem : in Element_Type) is abstract; entry Dequeue(Elem : out Element_Type) is abstract; function Length return Natural is abstract; end Queue;
type Queue_Ref is access all Queue'Class;
protected type Bounded_Queue(Max: Natural) is new Queue with -- Implementation of a bounded, protectected queue entry Enqueue(Elem : in Element_Type); entry Dequeue(Elem : out Element_Type); function Length return Natural; private Data: Elem_Array(1..Max); In_Index: Positive := 1; Out_Index: Positive := 1; Num_Elems: Natural := 0; end My_Queue;
task interface Worker is -- Interface for a worker task entry Queue_To_Service(Q : Queue_Ref) is abstract; end Server;
type Worker_Ref is access all Worker'Class;
task type Cyclic_Worker is new Worker with -- Implementation of a cyclic worker task entry Queue_To_Service(Q : Queue_Ref); end Cyclic_Server;
task Worker_Manager is -- Task that manages servers and queues. entry Add_Worker_Task(W : Worker_Ref); entry Add_Queue_To_Be_Serviced(Q : Queue_Ref); end Worker_Manager;
task body Worker_Manager is Worker_Array : array(1..100) of Worker_Ref; Queue_Array : array(1..10) of Queue_Ref; Num_Workers : Natural := 0; Next_Worker : Integer := Worker_Array'First; Num_Queues : Natural := 0; Next_Queue : Integer := Queue_Array'First; begin
loop
select accept Add_Worker_Task(W : Worker_Ref) do Num_Workers := Num_Workers + 1; Worker_Array(Num_Workers) := Worker_Ref(W); end Add_Worker_Task; -- Assign new task a queue to service if Num_Queues > 0 then -- Assign next queue to this worker Worker_Array(Num_Workers).Assign_Queue_To_Service( Queue_Array(Next_Queue)); -- Dynamically bound entry call
-- Advance to next queue Next_Queue := Next_Queue mod Num_Queues + 1;
end if;
or
accept Add_Queue_To_Be_Serviced(Q : Queue_Ref); Num_Queues := Num_Queues + 1; Queue_Array(Num_Queues) := Queue_Ref(Q); end Add_Queue_To_Be_Serviced;
-- Assign queue to worker if enough workers if Num_Workers >= Num_Queues then
-- This queue should be given one or more workers
declare Offset : Natural := Num_Queues-1;
begin while Offset < Num_Workers loop
-- (re) assign queue to worker Worker_Array((Next_Worker + Offset - Num_Queues)
mod Num_Workers + 1).
Assign_Queue_To_Service(Queue_Array(Num_Queues)); -- Dynamically bound entry call
Offset := Offset + Num_Queues;
end loop;
-- Advance to next worker Next_Worker := Next_Worker mod Num_Workers + 1;
end;
end if;
or
terminate;
end select;
end loop;
end Worker_Manager;
My_Queue : aliased Bounded_Queue(Max => 10); My_Server : aliased Cyclic_Server;
begin Worker_Manager.Add_Worker_Task(My_Server'access); Worker_Manager.Add_Queue_To_Be_Serviced(My_Queue'access); ...
!discussion
During the Ada 95 design process, it was recognized that type extension might be useful for protected types (and possibly task types) as well as for record types. However, at the time, both type extension and protected types were somewhat controversial, and expending energy on a combination of these two controversial features was not practical.
Since the design, however, this lack of extension of protected types has been identified as a possible target for future enhancements. In particular, a concrete proposal appeared in the May 2000 issue of ACM Transactions on Programming Languages in Systems (ACM TOPLAS), and this has formed the basis for a language amendment (AI-00250).
However, in ARG discussions, the complexity of this proposal has been of concern, and more recently a simpler suggestion was made that rather than supporting any kind of implementation inheritance, interfaces for tasks and protected types might be defined, and then concrete implementations of these interfaces could be provided. Class-wide types for these interfaces would be defined, and calls on the operations (protected subprograms and entries) defined for these interfaces could be performed given only a class-wide reference to the task or protected object.
An important advantage of eliminating inheritance of any code or data for tasks and protected types is that the "monitor"-like benefits of these constructs are preserved. All of the synchronizing operations are implemented in a single module, simplifying analysis and avoiding any inheritance "anomolies" that have been associated in the literature with combining inheritance with synchronization.
--!corrigendum 03.0x.0x(0x)
!ACATS test
!appendix

From: Randy Brukardt
Sent: Thursday, June 12, 2003  7:43 PM

Tucker wrote me:

Here is an article I have submitted to
the Ada User Journal.  It might be of interest
to ARG members.  Rather than filling all of their
mailboxes with it, I thought I would just fill
yours ;-).  Once you get it posted, could you send
out an e-mail with a URL pointing to it?

---

The article is posted at
http://www.ada-auth.org/ai-files/grab_bag/oop_200y.pdf.

Happy reading!

[Editor's note: This article proposes protected interfaces.]

****************************************************************

From: Robert I. Eachus
Sent: Thursday, June 12, 2003  11:19 PM

I was interested to compare the three cyclic type structure proposals as
they appear in Tuck's examples.  They all occupy about the same volume
in number of lines, but the generalized incomplete type approach
definitely looks the cleanest/most Ada-like.  There are of course,
plenty of reasons why any one of the three proposals might turn out to
be problematical for other reasons, but I think this causes me to lean a
little more in the direction I was leaning anyway.

Oh, and the write-up of protected interfaces seems to me to be the best
argument for adding interfaces to the language.  I'll have to think
about it (a lot).  I like the idea of having all queue types match a
potentially tasking safe interface.  Some implementations could be
tasking safe and others assume they are only visible in a single thread.
  A wonderful extension to Ada as an expository language for algorithm
design.  Now all we have to do is figure out how to actually implement
it. ;-)

****************************************************************

From: Pascal Leroy
Sent: Friday, June 13, 2003  11:03 AM

Is this really what Tucker is proposing?  The way I read his paper,
protected and non-protected interfaces are distinct beasts and do not
mix.  So if a queue has a protected interface, all of its
implementations have to be protected.  I might be misreading the intent
of course, it's hard to know without an AI.  But because the calling
conventions of protected and non-protected operations are vastly
different, I don't see how a class-wide type could indifferently
designate a protected or a non-protected implementation.

****************************************************************

From: Tucker Taft
Sent: Friday, June 13, 2003  1:22 PM

I was not proposing mixing protected interfaces
and tagged interfaces.  That would seem to be
a bad idea, given that the semantics are so different.
I'm not sure exactly what Robert Eachus had in mind,
but if you want to mix protected and tagged, you
will have to "wrap" one in the other.

****************************************************************

From: Robert I. Eachus
Sent: Friday, June 13, 2003  1:22 PM

I don't think it is what Tucker is proposing, and a pragma would be
useful.   But Tucker's proposal certainly allows what I am thinking of.
  Imagine two implementations of a protected (class-wide) type. One
version, say the parent is a "normal" protected object with all of the
necessary baggage to support say a queue which is accessed by different
threads/tasks.  With Tucker's proposal you can also provide a child
implementation which will fail in one of many ways, possibly by
deadlock, if it is actually called by two different tasks.  And maybe
another child that works fine with at most two callers, but can livelock
or deadlock with three or more.

It would be nice to have a pragma that told the compiler that "this
protected body assumes a single task," if only for documentation
purposes.  Even without it, the checks/overhead in the single thread
version should be low.  With a pragma, the compiler can choose a locking
implementation which has very low overhead for passing through, and a
much higher overhead--or even Program_Error--if a caller ever blocks.
The interface is identical, and any compilers that do lock checking
outside the protected object code don't need to change.

Let me give an example.  Suppose you have a protected object type that
provides serialized access to a disk file, perhaps of a Sequential_IO
file with a (Direct_IO) associated index.  (Reading or writing would
require several calls on the protected object.) The simple
implementation would allow only one transaction in process at a time.
(Begin_Transaction, Lookup, Read or Write, Close_Transaction.)  The more
complex implementation could allow for several transactions to be in
progress at the same time.  (File locking vs. record locking.)

The key point is that this effectively adds a capability to Ada that has
been there all along, but in general becomes too difficult to use.
Right now you can customize generics, but that requires preplaning to
provide the right generic formal parameters.  A good example of this
type of customization is providing different ">" operators as parameters
to a sort routine allows the same sort routine to be used to sort on
different keys.

But allowing for full generality is just not possible.  The original
implementor of the generic has to think of all the possible
customizations ahead of time, and provide the additional generic
parameters to accomplish it.  Does this sound something like the problem
with variant records that tagged types solved?  It does to me.
Fortunately, I think that the hard work has already been done by
existing compilers, what is needed is the (trivial?) bit of effort
required to permit programmers to provide alternate bodies for generics.

I'm working on writing this up.  Basically think of it as adding derived
generics to the language.  The "new" generic has the same interface as
its parent but provides a new body.  It might be nice to allow the new
body (assuming that the generic is a package) to call operations of the
parent, but I think it is adequate to allow/require the programmer to
create an instance of the parent generic if he wants to do that.

****************************************************************


Questions? Ask the ACAA Technical Agent