!standard A.18.27 11-02-01 AI05-0159-1/11 !standard A.18.28 !standard A.18.29 !standard A.18.30 !standard A.18.31 !standard A.18.32 !class Amendment 05-10-24 !status Amendment 2012 10-08-04 !status ARG Approved 10-0-0 10-10-29 !status work item 10-07-06 !status ARG Approved 10-0-0 10-06-18 !status work item 10-04-29 !status ARG Approved 11-0-0 10-02-27 !status work item 06-03-15 !status received 05-10-02 !priority Medium !difficulty Hard !subject Queue containers !summary Add task-safe queues to the set of containers. !problem The Ada 2005 containers only allow a single task to access them at a time, leaving it to the users to manage access by multiple tasks. There is a need for task-safe containers. !proposal Add a synchronized interface and four implementations of task-safe queues. We have both regular queues and priority queues. There are bounded and unbounded versions of both kinds of queues. In addition, add another interface for indefinite queues, with two implementations: unbounded regular queues and priority queues. !wording A.18.27 The Generic Package Containers.Synchronized_Queue_Interfaces The language-defined generic package Containers.Synchronized_Queue_Interfaces provides interface type Queue, and a set of operations for that type. Interface Queue specifies a first-in, first-out queue. Static Semantics The generic library package Containers.Synchronized_Queue_Interfaces has the following declaration: generic type Element_Type is private; package Ada.Containers.Synchronized_Queue_Interfaces is pragma Pure(Synchronized_Queue_Interfaces); type Queue is synchronized interface; procedure Enqueue (Container : in out Queue; New_Item : in Element_Type) is abstract with Is_Synchonized => By_Entry; procedure Dequeue (Container : in out Queue; Element : out Element_Type) is abstract with Is_Synchronized => By_Entry; function Current_Use (Container : Queue) return Count_Type is abstract; function Peak_Use (Container : Queue) return Count_Type is abstract; end Ada.Containers.Synchronized_Queue_Interfaces; procedure Enqueue (Container : in out Queue; New_Item : Element_Type) is abstract; A queue type that implements this interface may have a bounded *capacity*. If the queue object has a bounded capacity, and the number of existing elements equals the capacity, then Enqueue blocks until storage becomes available; otherwise Enqueue does not block. In any case, it then copies New_Item onto the queue. procedure Dequeue (Container : in out Queue; Element : out Element_Type) is abstract; If the queue is empty, then Dequeue blocks until an item becomes available. In any case, it then returns a copy of the element at the head of the queue, and removes it from the container. function Current_Use (Container : Queue) return Count_Type is abstract; Returns the number of elements currently in the queue. function Peak_Use (Container : Queue) return Count_Type is abstract; Returns the maximum number of elements that have been in the queue at any one time. A.18.28 The Generic Package Containers.Unbounded_Synchronized_Queues Static Semantics The language-defined generic package Containers.Unbounded_Synchronized_Queues provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue. with System; with Ada.Containers.Synchronized_Queue_Interfaces; generic with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>); Default_Ceiling: System.Any_Priority := System.Priority'Last; package Ada.Containers.Unbounded_Synchronized_Queues is pragma Preelaborate(Unbounded_Synchronized_Queues); package Implementation is ... –- not specified by the language end Implementation; protected type Queue (Ceiling: System.Any_Priority := Default_Ceiling) with Priority => Ceiling is new Queue_Interfaces.Queue with overriding entry Enqueue (New_Item: in Queue_Interfaces.Element_Type); overriding entry Dequeue (Element: out Queue_Interfaces.Element_Type); overriding function Current_Use return Count_Type; overriding function Peak_Use return Count_Type; private ... -- not specified by the language end Queue; private ... -- not specified by the language end Ada.Containers.Unbounded_Synchronized_Queues; The type Queue is used to represent task-safe queues. The capacity for instances of type Queue is unbounded. AARM Ramification: Enqueue never blocks; if more storage is needed for a new element, it is allocated dynamically. We don't need to explicitly specify that Queue needs finalization, because it is visibly protected. A.18.29 The Generic Package Containers.Bounded_Synchronized_Queues Static Semantics The language-defined generic package Containers.Bounded_Synchronized_Queues provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue. with System; with Ada.Containers.Synchronized_Queue_Interfaces; generic with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>); Default_Capacity : Count_Type; Default_Ceiling: System.Any_Priority := System.Priority'Last; package Ada.Containers.Bounded_Synchronized_Queues is pragma Preelaborate(Bounded_Synchronized_Queues); package Implementation is ... –- not specified by the language end Implementation; protected type Queue (Capacity : Count_Type := Default_Capacity; Ceiling: System.Any_Priority := Default_Ceiling) with Priority => Ceiling is new Queue_Interfaces.Queue with overriding entry Enqueue (New_Item: in Queue_Interfaces.Element_Type); overriding entry Dequeue (Element: out Queue_Interfaces.Element_Type); overriding function Current_Use return Count_Type; overriding function Peak_Use return Count_Type; private ... -- not specified by the language end Queue; private ... -- not specified by the language end Ada.Containers.Bounded_Synchronized_Queues; The semantics are the same as for Unbounded_Synchronized_Queues, except: - The capacity for instances of type Queue is bounded and specified by the discriminant Capacity. AARM Ramification: Since this type has a bounded capacity, Enqueue might block if the queue is full. Implementation Advice Bounded queue objects should be implemented without implicit pointers or dynamic allocation. A.18.30 The Generic Package Containers.Unbounded_Priority_Queues Static Semantics The language-defined generic package Containers.Unbounded_Priority_Queues provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue. with System; with Ada.Containers.Synchronized_Queue_Interfaces; generic with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>); type Queue_Priority is private; with function Get_Priority (Element: Queue_Interfaces.Element_Type) return Queue_Priority is <>; with function Before (Left, Right : Queue_Priority) return Boolean is <>; Default_Ceiling: System.Any_Priority := System.Priority'Last; package Ada.Containers.Unbounded_Priority_Queues is pragma Preelaborate(Unbounded_Priority_Queues); package Implementation is –- Not specified by the language end Implementation; protected type Queue (Ceiling: System.Any_Priority := Default_Ceiling) with Priority => Ceiling is new Queue_Interfaces.Queue with overriding entry Enqueue (New_Item: in Queue_Interfaces.Element_Type); overriding entry Dequeue (Element: out Queue_Interfaces.Element_Type); not overriding entry Dequeue_Only_High_Priority (Low_Priority : in Queue_Priority; Element : out Queue_Interfaces.Element_Type); overriding function Current_Use return Count_Type; overriding function Peak_Use return Count_Type; private -- not specified by the language end Queue; private -- not specified by the language end Ada.Containers.Unbounded_Priority_Queues; The type Queue is used to represent task-safe priority queues. The capacity for instances of type Queue is unbounded. Two elements E1 and E2 are equivalent if Before(Get_Priority(E1), Get_Priority(E2)) and Before(Get_Priority(E2), Get_Priority(E1)) both return False. Enqueue inserts an item according to the order specified by the Before function on the result of Get_Priority on the elements. If the queue already contains elements equivalent to New_Item, then it is inserted after the existing equivalent elements. AARM Ramification: Enqueue never blocks; if more storage is needed for a new element, it is allocated dynamically. We don't need to explicitly specify that Queue needs finalization, because it is visibly protected. Dequeue_Only_High_Priority is the same as Dequeue, except that it blocks until the element E at the head of the queue satisfies Before(Get_Priority(E), Low_Priority). The actual functions for Get_Priority and Before are expected to return the same value each time they are called with the same actuals, and should not modify their actuals. Before should define a strict weak ordering relationship (see A.18). If the actual functions behave in some other manner, the behavior of Unbounded_Priority_Queues is unspecified. A.18.31 The Generic Package Containers.Bounded_Priority_Queues Static Semantics The language-defined generic package Containers.Bounded_Priority_Queues provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue. with System; with Ada.Containers.Synchronized_Queue_Interfaces; generic with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>); type Queue_Priority is private; with function Get_Priority (Element: Queue_Interfaces.Element_Type) return Queue_Priority is <>; with function Before (Left, Right : Queue_Priority) return Boolean is <>; Default_Capacity : Count_Type; Default_Ceiling: System.Any_Priority := System.Priority'Last; package Ada.Containers.Bounded_Priority_Queues is pragma Preelaborate(Bounded_Priority_Queues); package Implementation is ... –- not specified by the language end Implementation; protected type Queue (Capacity : Count_Type := Default_Capacity; Ceiling: System.Any_Priority := Default_Ceiling) with Priority => Ceiling is new Queue_Interfaces.Queue with overriding entry Enqueue (New_Item: in Queue_Interfaces.Element_Type); overriding entry Dequeue (Element: out Queue_Interfaces.Element_Type); not overriding entry Dequeue_Only_High_Priority (Low_Priority : in Queue_Priority; Element : out Queue_Interfaces.Element_Type); overriding function Current_Use return Count_Type; overriding function Peak_Use return Count_Type; private ... -- not specified by the language end Queue; private ... -- not specified by the language end Ada.Containers.Bounded_Priority_Queues; The semantics are the same as for Unbounded_Priority_Queues, except: - The capacity for instances of type Queue is bounded and specified by the discriminant Capacity. AARM Ramification: Since this type has a bounded capacity, Enqueue might block if the queue is full. Implementation Advice Bounded priority queue objects should be implemented without implicit pointers or dynamic allocation. A.18.32 Indefinite Synchronized Queues There are three generic packages Containers.Indefinite_Synchronized_Queue_Interfaces, Containers.Indefinite_Unbounded_Synchronized_Queues, and Containers.Indefinite_Unbounded_Priority_Queues. These are identical to Containers.Synchronized_Queue_Interfaces, Containers.Unbounded_Synchronized_Queues, and Containers.Unbounded_Priority_Queues, respectively, except except that the generic formal Element_Type is indefinite. !discussion We considered making protected forms of all of the existing containers, but determined that there are various problems with such an approach: (1) What kind of protection is needed (multiread, single write vs. multi anything)? (2) Some of the operations (especially those with callbacks) could potentially deadlock. How do we handle those cases (allow a single task to do anything while it holds the lock vs. always locking). (3) Can we actually do better performance-wise than the user wrapping the operations that they need? Note that the existing containers are not potentially blocking, so they can be called from protected operations. A well-designed protected type will have much better abstraction than anything we could provide, and probably would not have as large a performance cost. Thus, we decided to provide task-safe queue abstractions (which are commonly needed) and let the users create any others that they need. !example declare -- First we create the queue interface. package Widgets is type Widget is new Integer; -- for example ... end Widgets; package Widget_Queue_Types is new Ada.Containers.Synchronized_Queue_Interfaces (Widgets.Widget); -- Now we design an algorithm around our interface. Here -- we have a set of assembly lines that fabricate widgets, -- adding them to a common queue. We also have a task that -- removes widgets from the queue for delivery. task type Assembly_Line_Task (Q : access Widget_Queue_Types.Queue'Class := null, N : Natural := 0) -- number of widgets is end; function New_Assembly_Line_Task (Q : not null access Widget_Queue_Types.Queue'Class; N : Natural) return Assembly_Line_Task is begin return T : Assembly_Line_Task (Q, N); end New_Assembly_Line_Task; type Assembly_Line_Task_Array is array (Positive range <>) of Assembly_Line_Task; task type Delivery_Service_Task (Q : not null access Widget_Queue_Types.Queue'Class; N : Natural) -- number of assembly lines is end; -- An assembly line task fabricates widgets until the -- requisite number have been made, and then it puts a -- distinguished value into the queue to indicate to -- the delivery service that there are no more widgets -- from this assembly line. task body Assembly_Line_Task is begin for I in 1 .. N loop delay 0.5; Q.Enqueue (Widget (I)); end loop; Q.Enqueue (Widget'(0)); -- no more widgets end Assembly_Line_Task; -- The delivery service task continually dequeues widgets -- from the queue (dispensing widget objects as necessary), -- and keeps track of how many assembly lines have -- finished making widgets. When all of the assembly lines -- are done, the delivery service task terminates. task body Delivery_Service_Task is W : Widget; Done : Natural := 0; begin loop Q.Dequeue (W); if W > 0 then Put_Line ("Delivering widget" & Widget'Image (W)); else Done := Done + 1; exit when Done >= N; end if; end loop; end Delivery_Service_Task; -- None of what we have done so far depends on any specific widget -- queue type. Here we instantiate the unbounded queue package -- for use as our widget queue object. package Widget_Queues is new Ada.Containers.Unbounded_Synchronized_Queues (Queues => Widget_Queue_Types); Q : aliased Widget_Queues.Queue; -- Now we elaborate our assembly line and delivery service task -- objects, binding them to the widget queue object. Assembly_Lines : Assembly_Line_Task_Array (1 .. 5) := (others => New_Assembly_Line_Task (Q'Access, 10)); Delivery_Service : Delivery_Service_Task (Q'Access, Assembly_Lines'Length); begin -- activate tasks null; end; !corrigendum A.18.27 The language-defined generic package Containers.Synchronized_Queue_Interfaces provides interface type Queue, and a set of operations for that type. Interface Queue specifies a first-in, first-out queue. @s8<@i> The generic library package Containers.Synchronized_Queue_Interfaces has the following declaration: @xcode<@b @b Element_Type @b; @b Ada.Containers.Synchronized_Queue_Interfaces @b @b Pure(Synchronized_Queue_Interfaces); @b Queue @b; @b Enqueue (Container : @b Queue; New_Item : @b Element_Type) @b @b Is_Synchronized =@> By_Entry; @b Dequeue (Container : @b Queue; Element : @b Element_Type) @b @b Is_Synchronized =@> By_Entry; @b Current_Use (Container : Queue) @b Count_Type @b; @b Peak_Use (Container : Queue) @b Count_Type @b; @b Ada.Containers.Synchronized_Queue_Interfaces;> @xcode<@b Enqueue (Container : @b Queue; New_Item : @b Element_Type) @b;> @xindent. If the queue object has a bounded capacity, and the number of existing elements equals the capacity, then Enqueue blocks until storage becomes available; otherwise Enqueue does not block. In any case, it then copies New_Item onto the queue.> @xcode<@b Dequeue (Container : @b Queue; Element : @b Element_Type) @b;> @xindent @xcode<@b Current_Use (Container : Queue) @b Count_Type @b;> @xindent @xcode<@b Peak_Use (Container : Queue) @b Count_Type @b;> @xindent !corrigendum A.18.28 @dinsc @s8<@i> The language-defined generic package Containers.Unbounded_Synchronized_Queues provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue. @xcode<@b System; @b Ada.Containers.Synchronized_Queue_Interfaces; @b @b Queue_Interfaces @b Ada.Containers.Synchronized_Queue_Interfaces (<@>); Default_Ceiling: System.Any_Priority := System.Priority'Last; @b Ada.Containers.Unbounded_Synchronized_Queues @b @b Preelaborate(Unbounded_Synchronized_Queues); @b Implementation @b ... –- not specified by the language @b Implementation; @b Queue (Ceiling: System.Any_Priority := Default_Ceiling) @b Priority =@> Ceiling @b @b Queue_Interfaces.Queue @b @b @b Enqueue (New_Item: @b Queue_Interfaces.Element_Type); @b @b Dequeue (Element: @b Queue_Interfaces.Element_Type); @b @b Current_Use @b Count_Type; @b @b Peak_Use @b Count_Type; @b ... -- not specified by the language @b Queue; @b ... -- not specified by the language @b Ada.Containers.Unbounded_Synchronized_Queues;> The type Queue is used to represent task-safe queues. The capacity for instances of type Queue is unbounded. !corrigendum A.18.29 @dinsc @s8<@i> The language-defined generic package Containers.Bounded_Synchronized_Queues provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue. @xcode<@b System; @b Ada.Containers.Synchronized_Queue_Interfaces; @b @b Queue_Interfaces @b Ada.Containers.Synchronized_Queue_Interfaces (<@>); Default_Capacity : Count_Type; Default_Ceiling: System.Any_Priority := System.Priority'Last; @b Ada.Containers.Bounded_Synchronized_Queues @b @b Preelaborate(Bounded_Synchronized_Queues); @b Implementation @b ... –- not specified by the language @b Implementation; @b Queue (Capacity : Count_Type := Default_Capacity; Ceiling: System.Any_Priority := Default_Ceiling) @b Priority =@> Ceiling @b @b Queue_Interfaces.Queue @b @b @b Enqueue (New_Item: @b Queue_Interfaces.Element_Type); @b @b Dequeue (Element: @b Queue_Interfaces.Element_Type); @b @b Current_Use @b Count_Type; @b @b Peak_Use @b Count_Type; @b ... -- not specified by the language @b Queue; @b ... -- not specified by the language @b Ada.Containers.Bounded_Synchronized_Queues;> The semantics are the same as for Unbounded_Synchronized_Queues, except: @xbullet @s8<@i> Bounded queue objects should be implemented without implicit pointers or dynamic allocation. !corrigendum A.18.30 @dinsc @s8<@i> The language-defined generic package Containers.Unbounded_Priority_Queues provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue. @xcode<@b System; @b Ada.Containers.Synchronized_Queue_Interfaces; @b @b Queue_Interfaces @b Ada.Containers.Synchronized_Queue_Interfaces (<@>); type Queue_Priority is @b; @b Get_Priority (Element: Queue_Interfaces.Element_Type) @b Queue_Priority is <@>; @b @b Before (Left, Right : Queue_Priority) @b Boolean @b <@>; Default_Ceiling: System.Any_Priority := System.Priority'Last; @b Ada.Containers.Unbounded_Priority_Queues @b @b Preelaborate(Unbounded_Priority_Queues); @b Implementation @b ... –- not specified by the language @b Implementation; @b Queue (Ceiling: System.Any_Priority := Default_Ceiling) @b Priority =@> Ceiling @b @b Queue_Interfaces.Queue @b @b @b Enqueue (New_Item: @b Queue_Interfaces.Element_Type); @b @b Dequeue (Element: @b Queue_Interfaces.Element_Type); @b @b Dequeue_Only_High_Priority (Low_Priority : @b Queue_Priority; Element : @b Queue_Interfaces.Element_Type); @b @b Current_Use @b Count_Type; @b @b Peak_Use @b Count_Type; @b ... -- not specified by the language @b Queue; @b ... -- not specified by the language @b Ada.Containers.Unbounded_Priority_Queues;> The type Queue is used to represent task-safe priority queues. The capacity for instances of type Queue is unbounded. Two elements @i and @i are equivalent if Before(Get_Priority(@i), Get_Priority(@i)) and Before(Get_Priority(@i), Get_Priority(@i)) both return False. Enqueue inserts an item according to the order specified by the Before function on the result of Get_Priority on the elements. If the queue already contains elements equivalent to New_Item, then it is inserted after the existing equivalent elements. Dequeue_Only_High_Priority is the same as Dequeue, except that it blocks until the element @i at the head of the queue satisfies Before(Get_Priority(@i), Low_Priority). The actual functions for Get_Priority and Before are expected to return the same value each time they are called with the same actuals, and should not modify their actuals. Before should define a strict weak ordering relationship (see A.18). If the actual functions behave in some other manner, the behavior of Unbounded_Priority_Queues is unspecified. !corrigendum A.18.31 @dinsc @s8<@i> The language-defined generic package Containers.Bounded_Priority_Queues provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue. @xcode<@b System; @b Ada.Containers.Synchronized_Queue_Interfaces; generic @b Queue_Interfaces @b Ada.Containers.Synchronized_Queue_Interfaces (<@>); type Queue_Priority is @b; @b Get_Priority (Element: Queue_Interfaces.Element_Type) @b Queue_Priority is <@>; @b Before (Left, Right : Queue_Priority) @b Boolean is <@>; Default_Capacity : Count_Type; Default_Ceiling: System.Any_Priority := System.Priority'Last; @b Ada.Containers.Bounded_Priority_Queues @b @b Preelaborate(Bounded_Priority_Queues); @b Implementation @b ... –- not specified by the language @b Implementation; @b Queue (Capacity : Count_Type := Default_Capacity; Ceiling: System.Any_Priority := Default_Ceiling) @b Priority =@> Ceiling @b @b Queue_Interfaces.Queue @b @b Queue (Capacity : Count_Type := Default_Capacity; Ceiling: System.Any_Priority := Default_Ceiling) is new Queue_Interfaces.Queue @b @b Priority(Ceiling); @b @b Enqueue (New_Item: @b Queue_Interfaces.Element_Type); @b @b Dequeue (Element: @b Queue_Interfaces.Element_Type); @b @b Dequeue_Only_High_Priority (Low_Priority : @b Queue_Priority; Element : @b Queue_Interfaces.Element_Type); @b @b Current_Use @b Count_Type; @b @b Peak_Use @b Count_Type; @b ... -- not specified by the language @b Queue; @b ... -- not specified by the language @b Ada.Containers.Bounded_Priority_Queues;> The semantics are the same as for Unbounded_Priority_Queues, except: @xbullet @s8<@i> Bounded priority queue objects should be implemented without implicit pointers or dynamic allocation. !corrigendum A.18.32 @dinsc There are three generic packages Containers.Indefinite_Synchronized_Queue_Interfaces, Containers.Indefinite_Unbounded_Synchronized_Queues, and Containers.Indefinite_Unbounded_Priority_Queues. These are identical to Containers.Synchronized_Queue_Interfaces, Containers.Unbounded_Synchronized_Queues, and Containers.Unbounded_Priority_Queues, respectively, except except that the generic formal Element_Type is indefinite. !ACATS test ACATS Tests are needed for these new packages. !ASIS There is no impact on ASIS. !appendix From: Martin Dowie Date: Tuesday, July 28, 2009 2:53 AM 1. For the priority queue, what is the expected behaviour of trying to add 2 identical elements to the queue? It would seem that the 2nd would not be added (as "Before (x, x) = False"). I appreciate that to get both messages added would probably require "multiset" support - are "Multi" variants of the existing containers planned? 2. For the bounded variants, is the intent that they should not use dynamic memory (same as the new bounded containers)? If so, should there be some words added to state this? 3. The queues are all specified to be FIFO - could LIFO also be added relatively cheaply? Not as common but still useful. **************************************************************** From: Randy Brukardt Date: Tuesday, August 11, 2009 1:42 PM Sorry about the long delay on posting this one; it got blocked by a useless filter in the mailing list software (that unfortunately can't be turned off) and I was on vacation. > 1. For the priority queue, what is the expected behaviour of trying to > add 2 identical elements to the queue? It would seem that the 2nd > would not be added (as "Before (x, x) = False"). I appreciate that to > get both messages added would probably require "multiset" support - > are "Multi" > variants of the existing containers planned? I would have expected the reverse: that two identical elements get queued (probably in an unspecified order). That's how the queues in my mail filter work (the only time I've used priority queues in practice) [They're actually more like delay queues, as the "priority" is the retry time. Surely you don't want to loose a message just because it happens to have the same retry time as another.] In any case, this will need to be clarified. > 2. For the bounded variants, is the intent that they should not use > dynamic memory (same as the new bounded containers)? > If so, should there be some words added to state this? That is my understanding, and yes, of course, they will need all of the appropriate wording that AI05-0001-1 uses for bounded forms. > 3. The queues are all specified to be FIFO - could LIFO also be added > relatively cheaply? Not as common but still useful. Not sure it is worth it. We're really only trying to provide the most basic and common of protected containers because generally the "protection" needed is something that depends on the entire algorithm; naively dropping in protected containers could easily generate race or deadlock conditions. In any case, "LIFO" is a stack, which is generally thought of as a totally different data structure, with different names for the operations. Trying to use queue terminology for it would be pretty unnatural. So there wouldn't be much if any reuse potential here. **************************************************************** From: Simon Wright Date: Tuesday, August 11, 2009 3:45 PM >> 1. For the priority queue, what is the expected behaviour of trying >> to add 2 identical elements to the queue? It would seem that the 2nd >> would not be added (as "Before (x, x) = False"). I appreciate that to >> get both messages added would probably require "multiset" support - >> are "Multi" >> variants of the existing containers planned? > > I would have expected the reverse: that two identical elements get > queued (probably in an unspecified order). As a data point here, the BC ordered queue queues 'identical' items in FIFO order (preferring defined behaviour). Whether an unspecified order is satisfactory must, I think, depend on the application. **************************************************************** From: Jeffrey R. Carter Date: Tuesday, August 11, 2009 4:12 PM > I would have expected the reverse: that two identical elements get > queued (probably in an unspecified order). That's how the queues in my > mail filter work (the only time I've used priority queues in practice) > [They're actually more like delay queues, as the "priority" is the > retry time. Surely you don't want to loose a message just because it > happens to have the same retry time as another.] If they're specified as FIFO, the priority queue must really be FIFO-within-priorities, so it must queue the 2nd after the 1st. **************************************************************** From: Martin Dowie Date: Monday, August 24, 2009 7:03 AM Thanks for all that - making more sense now... Would it be useful to add a "Peek" operation too? One that returned the highest priority element in the queue without actually removing it from the queue? **************************************************************** From: Matthew Heaney Date: Thursday, October 8, 2009 12:28 AM > 1. For the priority queue, what is the expected behaviour of trying to > add 2 identical elements to the queue? It would seem that the 2nd > would not be added (as "Before (x, x) = False"). I appreciate that to > get both messages added would probably require "multiset" support - > are "Multi" > variants of the existing containers planned? There are two separate issues here. The first issue is the matter of the priority queue. Yes, you should be able to add multiple items that are equivalent. And yes, new elements that are equivalent to existing elements should probably go after existing elements. (But this will have to be decided at the ARG meeting next month.) The second issue is multiset support. This is orthogonal to priority queues (because the language doesn't specify how the queues are implemented). On the specific matter of multiset support, I lobbied last year for their inclusion in the language standard, but wasn't able to make my case with sufficient cogency, so they didn't make the cut. However, an unbounded multiset is part of the GNAT distribution, so if you're using GNAT then you have one already. I am in the process of integrating the bounded forms into GNAT, and so GNAT will have a bounded multiset too. For now I have implemented the bounded priority queues using the multisets, but eventually I'll probably replace that implementation with a proper heap. > 2. For the bounded variants, is the intent that they should not use > dynamic memory (same as the new bounded containers)? If so, should > there be some words added to state this? Right, the bounded forms do not use dynamic memory allocation. > 3. The queues are all specified to be FIFO - could LIFO also be added > relatively cheaply? Not as common but still useful. That's just a stack. Use a vector or a list container, wrapped in a protected object. **************************************************************** From: Randy Brukardt Date: Monday, April 5, 2010 8:29 PM I recently had a discussion with Martin Dowie. He was concerned that the lack of a Peek operation in the priority queues makes it difficult to implement some common situations. In particular, cases where the reader wants to defer processing until an item of sufficient priority is available. (Obviously, this case only applies to priority queues.) Using Peek requires a busy-wait loop of some sort, which is obviously suboptimal. In addition, Peek is very hard to use safely, as in general you can assume nothing at all about the item retrieved by a Dequeue after executing a Peek. (Another task may have put a higher-priority item on the queue, or another task may have removed the item at the head of the queue, between the Peek and a Dequeue.) As such, it's like leaving a loose razor blade in a toolchest. Moreover, in the bounded queue case (without any dynamic memory management) it is not any more efficient than doing a Dequeue (both require copying the element). So it probably is a wash in terms of efficiency and safer to do a Dequeue followed by a Enqueue if you don't want to process the element (the element will end up in the same relative place on the queue since it is sorted by priority). (Enqueue might be more expensive if the queue has a lot of elements on it or the Before function is unusually expensive, but in normal circumstances it costs about the same as a Peek would, one element copy.) I had a similar problem in my spam filter, for which Peek would not have worked (there are multiple readers). The "priority' is the time when an item ought to be processed (most are ready to process immediately, but after a failed operation you have to wait a random amount of time and try again). I used a combination of timed entry calls and a high-priority-only dequeue operations. For the AI05-0159-1 queues, this routine would look like: procedure Dequeue_Only_High_Priority (Container : in out Queue; Minimum_High_Priority : Element_Type; Element : out Element_Type); This routine would block if there wasn't an element with the minimum priority available. This was used like (I've left out some parts): type Queued_Item is tagged private; type Queued_Item_Ptr is access all Queue_Node'Class; type Queue_Node is record Item : Queued_Item_Ptr; Process_After : Ada.Calendar.Time; -- Use like "delay until". end record; function Before (Left, Right : Queue_Node) return Boolean is use type Ada.Calendar.Time; begin return Left.Process_After < Right.Process_After; end Before; package Message_Queue is Ada.Containers.Unbounded_Priority_Queues (Queue_Node, Before => Before); --- declare Node : Queue_Node; begin loop select accept Send_Queue.Dequeue_Only_High_Priority (Element => Node, Minimum_High_Priority => (Item => null, After => Ada.Calendar.Clock)); Send (Node); or accept Shutdown; or delay 10.0; end loop; end loop; end; Note that I had to use the timeout because the "high-priority" value is based on the clock, and thus has to be reevaluated occasionally. That wouldn't happen if the priority didn't involve an exterior actor (and barriers that depend on globals are bad practice for this reason). Since we don't need to do retries on any particular schedule, this is a non-issue in this application. Also note that I also used that code to handle shutdown requests, since blocking forever would prevent shutdowns from being recognized. --- Anyway, the lack of such an operation would make using the AI05-0159-1 priority queues suboptimal for this use. Without the Dequeue_Only_High_Priority operation, I would have to use a faster loop (so that newly queued operations are checked reasonably quickly). There also would be a reordering of nodes that have the same sending time (not a major problem in this use, but not optimal). This would look something like: declare Node : Queue_Node; begin loop select accept Send_Queue.Dequeue (Element => Node); if Node.Process_After < Ada.Calendar.Clock then Send (Node); else Send_Queue.Enqueue (Element => Node); end if; or accept Shutdown; or delay 1.0; end loop; end loop; end; While this is not great, it might be good enough. So, is this problem worth addressing? If so, do we want to add an operation like this to the priority queues (only)? Or is there some other idea (not involving a race condition)? **************************************************************** From: Bob Duff Date: Tuesday, April 6, 2010 12:43 PM > I recently had a discussion with Martin Dowie. He was concerned that > the lack of a Peek operation in the priority queues makes it difficult > to implement some common situations. In particular, cases where the > reader wants to defer processing until an item of sufficient priority is available. > (Obviously, this case only applies to priority queues.) I have mixed feelings about such race-condition-causing features. If we have Peek, there should probably be a NOTE warning of the danger. There is precedent: Function Current_Use in this package has the same property. (By the way, there's no rationale for why we have Current_Use and Peak_Use -- seems like we ought to say something.) And Ada.Synchronous_Task_Control has Current_State, with the mild AARM-only warning, "This state can change immediately after the operation returns." > procedure Dequeue_Only_High_Priority > (Container : in out Queue; > Minimum_High_Priority : Element_Type; > Element : out Element_Type); How about this: procedure Conditional_Dequeue (Container : in out Queue; Element : out Element_Type; Condition : function (Element_Type) return Boolean) is abstract; pragma Implemented (Conditional_Dequeue, By_Entry); ? where "function (Element_Type) return Boolean" of course stands for "not null access function (Element: Element_Type) return Boolean". It dequeues an element if and only if Condition returns True for the element to be dequeued. Never blocks. Hmm. I guess we'd need another Boolean 'out' param to indicate whether it succeeded. > select > accept Send_Queue.Dequeue_Only_High_Priority (Element => Node, > Minimum_High_Priority => (Item => null, After => Ada.Calendar.Clock)); That doesn't look right -- you can only "accept" your own entries. **************************************************************** From: Martin Dowie Date: Tuesday, April 6, 2010 1:12 PM There are certainly loads of precedents, e.g. the attributes wrt to tasking are race conditions ('Callable, 'Count and 'Terminated). Randy helpfully suggested alternatives without something akin to a 'peek' (e.g. a 2 queue solution; 1 high priority, 1 low priority) but they wouldn't work when using these in high-integrity systems - i.e. Ravenscar profile environments - as they required 'select' statements. I'm sure some version of 'peek' - either a blocking or a non-blocking-with-success or blocking-for-period-with-success - would help in such environments. **************************************************************** From: Bob Duff Date: Tuesday, April 6, 2010 2:36 PM What do you think of my Conditional_Dequeue suggestion? **************************************************************** From: Randy Brukardt Date: Tuesday, April 6, 2010 3:05 PM > What do you think of my Conditional_Dequeue suggestion? It's better than Peek (much less trouble with race conditions), but I think it has two negatives: * The need to write a function when the condition is likely to be a simple expression (Obj.After < Ada.Calendar.Clock in my example) is annoying; * The lack of blocking semantics means almost all uses will need a busy-wait loop. Neither of these is critically important, but they do suggest that there might be a better solution out there. For the first, the fact that we are talking about priority queues means we already have an ordering, so it isn't clear that there is any value to having a second one. For the second, I see the issue that Ravenscar uses will necessarily have to use a busy-wait loop, but it is annoying to force everyone to live by the limitations of Ravenscar. (Indeed, as with SPARK, I would hope that we be able to move to larger subsets of the language for verification purposes; we shouldn't be tied to these overly limiting subsets forever.) Peek itself is just too dangerous in normal use: it can only be used safely on a priority queue if there is only a single peeking/dequeuing task AND the peeked item is tested then immediately discarded (there can be no assumption that it will be the one dequeued) AND getting a higher-priority item from Dequeue than the one expected is OK. I'm sure there are applications that fit into that profile, but there are many that don't (such as my "flock of senders" problem). Moreover, there is no practical way to enforce safe use of Peek (since there is no way to enforce the immediate discarding of the retrieved value). I don't think it would even be possible for a static analysis tool to figure out Peek misuse (other than the obvious: "ERROR: Use of Peek detected" :-). So we need a better solution (or none, as we currently have). **************************************************************** From: Bob Duff Date: Tuesday, April 6, 2010 3:36 PM > It's better than Peek (much less trouble with race conditions), but I > think it has two negatives: I just had a discussion with someone at AdaCore who pointed out another negative: Presumably the implementation of these queues is a protected type. You normally want all operations of a protected type to have a short bounded time. Normally, you can determine that by analyzing the protected body. But if the protected body is calling my suggested Condition function, which is passed in by the client, you need to do a more global analysis. **************************************************************** From: Randy Brukardt Date: Tuesday, April 6, 2010 3:48 PM You could say that about any priority queue in general, however, as the ordering function (Before in this case) is passed in and could take an unknown amount of time. Moreover, the number of calls will depend (in some way) upon the number of items in the queue. In practice, both of these functions would be short and execute quickly, but there is a real concern if you need strong bounds. Of course, Before is fundamental to the Queue, while your Condition function is less so. Still, it seems that this is a problem with the entire idea of generic priority queues, and not specific to your suggestion. **************************************************************** From: Bob Duff Date: Tuesday, April 6, 2010 3:54 PM Good point. **************************************************************** From: Martin Dowie Date: Wednesday, April 7, 2010 3:24 AM > What do you think of my Conditional_Dequeue suggestion? It looks good to me! A 'kitchen-sink' addition could be: procedure Conditional_Dequeue (Container : in out Queue; Element : out Element_Type; Success : out Boolean; Condition : not null access function (Element : Element_Type) return Boolean; Timeout : Duration) is abstract; pragma Implemented (Conditional_Dequeue, By_Entry); Where this blocks for up to a 'Timeout' period. That also mitigates Randy's 2nd point ("The lack of blocking semantics means almost all uses will need a busy-wait loop"). [Alternative: 'Timeout : Duration := 0.0' offers non-blocking option.] Randy's 1st point ("The need to write a function when the condition is likely to be a simple expression (Obj.After < Ada.Calendar.Clock in my example) is annoying") is true and a small 'lamba' expression would be great here! ;-) But for (ordered) container use and, to a less extent, just using general ADTs with primary keys, we end up writing those little functions _all_the_time_. Still saves a heck of a time over rolling-your-own, so I know which I prefer. I'm not sure I understand Randy's point "it is annoying to force everyone to live by the limitations of Ravenscar" - this would be 'adding to' rather than 'replacing' any functionality, so it will be safely ignored by those who don't need it (I ignore entire packages of the standard library quite happily ;-). I appreciate there are concerns about how this could be used appropriately but you could say the same for 'goto' or ATC or Unchecked_ or overlaying with 'Address or etc...the above seems a lot less (potentially) harmful to me... **************************************************************** From: Randy Brukardt Date: Wednesday, April 7, 2010 1:06 PM ... > Where this blocks for up to a 'Timeout' period. That also mitigates > Randy's 2nd point ("The lack of blocking semantics means almost all > uses will need a busy-wait loop"). > [Alternative: 'Timeout : Duration := 0.0' > offers non-blocking option.] I thought of something like this, but I don't think it can be implemented with a standard Ada protected object. You'd have to have a subprogram with a timed or conditional entry call, but then it couldn't be an entry (so it couldn't be used in a requeue or conditional entry call). And the internal conditional entry call wouldn't be allowed by Ravenscar. My original idea (not posted to Ada Comment, just in our e-mail discussion) had the same problem. ... > I'm not sure I understand Randy's point "it is annoying to force > everyone to live by the limitations of Ravenscar" - this would be > 'adding to' rather than 'replacing' any functionality, so it will be > safely ignored by those who don't need it (I ignore entire packages of > the standard library quite happily ;-). I was referring to forcing everyone to use busy-wait loops because Ravenscar programs have to be coded that way (no conditional entry calls). If we have a non-blocking operation here (as Bob proposed), we're essentially forcing all uses to use busy-wait loops. That's a lack of capability caused by Ravenscar concerns, not *extra* capability (which I wouldn't have a concern about). > I appreciate there are concerns about how this could be used > appropriately but you could say the same for 'goto' or ATC or > Unchecked_ or overlaying with 'Address or etc...the above > seems a lot less (potentially) harmful to me... I agree, this is a lot less harmful than Peek. It strikes me, though, that the separate Condition function introduces a new race condition hazard that doesn't exist in the original ones. It's less serious than the original one, but it still exists. Consider a numeric priority with a Before function of Left.Priority > Right.Priority. Assume Condition is defined as Element.Priority in 10..15. Consider the following two execution orders: Task 2 inserts an item with priority 10. Task 1 executes Conditional_Dequeue, receiving success and the item with priority 10. Task 2 inserts an item with priority 20. vs. Task 2 inserts an item with priority 10. Task 2 inserts an item with priority 20. Task 1 executes Conditional_Dequeue, receiving failure. There is a race between task 1 reading the queue and task 2's insertion of the second item. Of course, one could say that such a condition is bad (it IS bad), but I suspect that in practice the problem could be much more subtle. It might be hard to detect. This implies to me that it is only safe to use the same comparison function for Conditional_Dequeue. Which makes me think that my original proposal is (slightly) better: procedure Dequeue_Only_High_Priority (Container : in out Queue; Minimum_High_Priority : Element_Type; Element : out Element_Type); because this race condition cannot happen here (meaning that there doesn't need to be any analysis to prove that). If we wanted to insist on a non-blocking version, that would be: procedure Dequeue_Only_High_Priority (Container : in out Queue; Minimum_High_Priority : Element_Type; Element : out Element_Type; Success : out Boolean); It would be nice to have both. (That goes for regular Dequeue as well, a non-blocking version would be usable in a Ravenscar context where a blocking one might not be.) Of course, this all might be considered feeping creaturism. :-) The need to construct a complete element here for just the priority portion is indeed annoying, but there isn't any alternative since Before takes elements. **************************************************************** From: Martin Dowie Date: Wednesday, April 7, 2010 1:18 PM Thankfully, we now have the 'others => <>' option to keep the construction of the element to a minimum... I don't mind the creeping...but I'm biased by having seen the need for this sort of operation! ;-) **************************************************************** From: Mark Lorenzen Date: Wednesday, April 7, 2010 3:14 PM > I thought of something like this, but I don't think it can be > implemented with a standard Ada protected object. You'd have to have a > subprogram with a timed or conditional entry call, but then it > couldn't be an entry (so it couldn't be used in a requeue or > conditional entry call). And the internal conditional entry call > wouldn't be allowed by Ravenscar. In my opinion, tasks and protected objects should not be a part of a re-usable library. I think it's better to provide functionality for registering a call-back subprogram, which will be called in case an element (that fulfills a certain condition) is put on the queue, and at the same time dequeue the element. procedure Set_Conditional_Pass_Through_Handler (Container : in out Queue; Condition : in not null access function (Element : Element_Type) return Boolean; Handler : in not null access procedure (Element : in Element_Type)); The idea is to enable elements to "pass through" the normal priority queue mechanism. The element is never stored in the queue, but passed directly to the user as parameter Element in subprogram Handler, if Condition is fulfilled. It is up to the user to implement an optional time-out mechanism, using whatever language constructs that are appropriate for the program in question. **************************************************************** From: Randy Brukardt Date: Wednesday, April 7, 2010 4:47 PM > In my opinion, tasks and protected objects should not be a part of a > re-usable library. It has to be in this case. We've defined the queue as s synchronized interface, in order to provide task-safe access. If it wasn't synchronized (or visibly protected), it wouldn't be task-safe by the definitions in the Ada Standard. In addition, the definition declares Enqueue and Dequeue to be blocking if items cannot be added or removed respectively. Note that a synchronized interface can only be implemented with a task or protected object. Even if we decided to redefine everything without the visible synchonization (and that by adding a bunch of wording to describe what operations have to be supported -- which would be a major pain to do), we also have a principle that the containers need to be implementable in standard Ada. That could only be done by implementing the queues as a protected object of some sort (pragma Atomic is only required to be supported on "small" types, so it could not be used on a generic element type). Thus, while I agree with your principle in general for the containers, the queue containers exist *only* for the purpose of multitasking (it is trivial to create a queue using of the list container if task safety isn't needed, just rename Append to be Enqueue, and define Dequeue to be First_Element followed by Delete_First), and thus must be task-safe. And that implies that they have to be implementable with a protected object. > I think it's better to provide functionality for registering a > call-back subprogram, which will be called in case an element (that > fulfills a certain condition) is put on the queue, and at the same > time dequeue the element. > > procedure Set_Conditional_Pass_Through_Handler > (Container : in out Queue; > Condition : in not null access function (Element : Element_Type) return Boolean; > Handler : in not null access procedure (Element : in Element_Type)); > > The idea is to enable elements to "pass through" the normal priority > queue mechanism. The element is never stored in the queue, but passed > directly to the user as parameter Element in subprogram Handler, if > Condition is fulfilled. It is up to the user to implement an optional > time-out mechanism, using whatever language constructs that are > appropriate for the program in question. This does not solve the use case in question, which is a delay queue (the "priority" is the time to process the element). In that case, the element will be on the queue for a while before it becomes high enough priority (the time is reached) to remove it. It also doesn't work when multiple high priority items are queued at about the same time and there is a single consumer (this is similar to Martin's original use case); the consumer will want to get one item and come back when it is finished to get the other high priority item. With the scheme you are proposing, you would have to have a second queue to store "extra" items in this case. If that is going to be the case, you might as well have used two queues in the first place. (Martin notes that such an extra queue would imply an extra task in a Ravenscar environment, as conditional entry calls aren't allowed.) **************************************************************** From: Mark Lorenzen Date: Thursday, April 8, 2010 8:50 AM > It has to be in this case. We've defined the queue as s synchronized > interface, in order to provide task-safe access. If it wasn't > synchronized (or visibly protected), it wouldn't be task-safe by the > definitions in the Ada Standard. In addition, the definition declares > Enqueue and Dequeue to be blocking if items cannot be added or removed > respectively. Note that a synchronized interface can only be > implemented with a task or protected object. > ... I recently wrote a re-useable module containing both POs and tasks. It worked as expected in my test setup, until it had to be used in an actual application. The problems were 1) the PO priorities were not configurable and 3) the task priorities were not configurable and 3) the task stack sizes were not configurable. So if the Synchronized_Queue makes use of either, it is important that the user is able to define priorities and stack sizes e.g. by supplying them as formal parameters. Unfortunately the formal generic parameters must then of course cater for all kinds of implementations using PO(s), task(s) or PO(s) + task(s). This is messy and may result in generic parameters not being used etc. A solution is to demand that an implementation uses e.g. exactly one PO and exactly one task if this is feasible and require that an implementation documents the necessary timings and task behavior (cyclic, sporadic etc.) for perfoming a schedulability analysis. Another approach is to use suspension objects, but that is probably not an acceptable solution to the Ravenscar users and suspension objects cannot implement a synchronized interface. I'm therefore still sceptical about the useability of the proposed generic package. **************************************************************** From: Randy Brukardt Date: Thursday, April 8, 2010 12:19 PM ... > So if the Synchronized_Queue makes use of either, it is important that > the user is able to define priorities and stack sizes e.g. by > supplying them as formal parameters. > Unfortunately the formal generic parameters must then of course cater > for all kinds of implementations using PO(s), > task(s) or PO(s) + task(s). This is messy and may result in generic > parameters not being used etc. A solution is to demand that an > implementation uses e.g. exactly one PO and exactly one task if this > is feasible and require that an implementation documents the necessary > timings and task behavior (cyclic, sporadic etc.) for perfoming a > schedulability analysis. Humm, I hadn't thought of priorities, and I don't think anyone else has either. (I personally have never used them in an Ada program, although I've used plenty of tasks.) Thanks for bringing that up. In any case, a queue (or other container) should use exactly zero tasks in general, so I wouldn't worry about that. Implementers could do stupid things, but I think their customers would set them straight in a hurry. So I think what you are saying is that the generic that defines the interface also needs a priority parameter (to set the ceiling priority of the protected object(s)); the parameter would presumably be defaulted so that it doesn't have to be given unless you care. [You also seem to be saying that the entire idea of synchronized interfaces is flawed because they don't include the priorities of the implementation, which makes it impossible to reason about the behavior.] None of the predefined containers are intended to be used when timing is critical (for that, you need visibility into the implementation, which is exactly what we don't want for the containers -- we want to allow implementers to make the best implementations possible and to be able to change them freely), so actually documenting timings does not make sense. But there are a lot of systems out there (like my web server and spam filter) that just need "good enough" implementations -- where timings aren't critical. > Another approach is to use suspension objects, but that is probably > not an acceptable solution to the Ravenscar users and suspension > objects cannot implement a synchronized interface. > > I'm therefore still sceptical about the useability of the proposed > generic package. Would you prefer no predefined queue at all? There is no value to a predefined queue that isn't implemented with protected objects (it's trivial to write yourself, as I showed yesterday), so we don't want to do that. I also think that the blocking semantics is important (although that is less clear-cut). **************************************************************** From: Jeffrey R. Carter Date: Thursday, April 8, 2010 2:45 PM > Humm, I hadn't thought of priorities, and I don't think anyone else > has either. (I personally have never used them in an Ada program, > although I've used plenty of tasks.) Thanks for bringing that up. I agree that client control of priorities is important. > In any case, a queue (or other container) should use exactly zero > tasks in general, so I wouldn't worry about that. Implementers could > do stupid things, but I think their customers would set them straight in a hurry. Then perhaps it should be a protected interface rather than synchronized? > Would you prefer no predefined queue at all? There is no value to a > predefined queue that isn't implemented with protected objects (it's > trivial to write yourself, as I showed yesterday), so we don't want to > do that. I also think that the blocking semantics is important > (although that is less clear-cut). It's also trivial to wrap a protected type around a list (or ordered set) and write your own protected (priority) queue, with blocking semantics if desired. I don't think that's a reason for a library not to provide them. FWIW, the protected data structures in the PragmAda Reusable Components (Ada 95) define a protected type with a defaulted Ceiling_Priority discriminant that is used to set the priority of objects of the type. **************************************************************** From: Randy Brukardt Date: Wednesday, April 7, 2010 9:36 PM We didn't define an indefinite version of the queues, unlike all other containers forms. This seems weird to me; I can't think of any good reason to not have an indefinite unbounded queue (other than that it doesn't fit well with the interface definition -- maybe another reason that the interface isn't that good of an idea??), and it surely is inconsistent. **************************************************************** From: Bob Duff Date: Monday, May 10, 2010 10:50 AM Here's a new version of AI05-0159-1, modified as per the April 29 telephone meeting. Everything is heavily modified, except the !example, which I didn't change (nor even read). One way in which I disobeyed my marching orders: I gave the Ceiling priority discriminant a default even in the Bounded case. This requires giving a default for Capacity. I chose 1. Most users will want to specify some other value, but I don't see that as a problem. Objections? There are two levels of default -- you pass in a Ceiling (and Capacity in the bounded case) as generic formals with defaults. Then these are used as the default for the discriminant(s). Anyway, a single-element queue is not entirely nonsensical. I also tried to remove some duplicated verbiage. For example, the "interfaces" part says that Enqueue blocks if and only of the thing is bounded and is full. We don't need to mention that again in AARM notes for the concrete types, which are only a small distance away. [This is version /06 - Editor.] **************************************************************** From: Tucker Taft Date: Monday, May 10, 2010 11:06 AM I don't see why you need a default for the generic formal object Default_Capacity. It seems reasonable to require that the user specify a Default_Capacity when instantiating, rather than allowing it to unintentionally become one, which turns the "queue" into a mailbox. That seems error-prone. Otherwise, looks good... **************************************************************** From: Bob Duff Date: Monday, May 10, 2010 11:38 AM > I don't see why you need a default for the generic formal object > Default_Capacity. > It seems reasonable to require that the user specify a > Default_Capacity when instantiating, rather than allowing it to > unintentionally become one, which turns the "queue" into a mailbox. > That seems error-prone. OK, I'm convinced. > Otherwise, looks good... Thanks for reviewing. **************************************************************** From: Randy Brukardt Date: Wednesday, May 19, 2010 10:40 PM ... > I also tried to remove some duplicated verbiage. For example, the > "interfaces" part says that Enqueue blocks if and only of the thing is > bounded and is full. We don't need to mention that again in AARM > notes for the concrete types, which are only a small distance away. Yes, we do. The intent is that this is reference information, so that someone can look up just the definition of the single package that they care about (prehaps by clicking on the page) and get the important information. The blocking/non-blocking seems important enough to put in each place (in the AARM only, of course). Indeed, I would argue that a user note in each place might be appropriate. Remember that in the HTML version, that "short distance" is on a different HTML page that the user probably will not see (printed is different, but there is less use of that version every year). **************************************************************** From: Randy Brukardt Date: Wednesday, May 19, 2010 10:53 PM ... > The generic library package > Containers.Synchronized_Queue_Interfaces has the following > declaration: > > generic > type Element_Type is private; > > package Ada.Containers.Synchronized_Queue_Interfaces is > pragma Pure; This wasn't your mistake, but the name of the package is always included in the pragma Pure or Preelaborate. ... > with System; > with Ada.Containers.Synchronized_Queue_Interfaces; > generic > with package Queue_Interfaces is new > Ada.Containers.Synchronized_Queue_Interfaces (<>); > type Queue_Priority is private; > with function Get_Priority > (Element: Queues.Element_Type) return Queue_Priority is <>; > with function "<" > (Left, Right : Queues.Element_Type) return Boolean is <>; It took me forever to understand this; I finally realized that the English wording makes no sense because you actually meant: with function "<" (Left, Right : Queue_Priority) return Boolean is <>; ... > Enqueue inserts an item according to the order specified by the "<" > function. > If the queue already contains elements equivalent to New_Item, then it > is inserted after the existing equivalent elements. I don't think this quite works. I think you need to mention Get_Priority somewhere. Maybe: Enqueue inserts an item according to the order specified by the "<" function on the result of Get_Priority on the elements. I've made these changes (and Tucker's suggestion) in a separate version (so we can recover yours if necessary). [This is version /07 - Editor.] **************************************************************** From: Bob Duff Date: Thursday, May 20, 2010 7:15 AM > It took me forever to understand this; I finally realized that the > English wording makes no sense because you actually meant: > > with function "<" > (Left, Right : Queue_Priority) return Boolean is <>; Right, sorry about that. > ... > > Enqueue inserts an item according to the order specified by the "<" > > function. > > If the queue already contains elements equivalent to New_Item, then > > it is inserted after the existing equivalent elements. > > I don't think this quite works. I think you need to mention > Get_Priority somewhere. Maybe: > > Enqueue inserts an item according to the order specified by the "<" > function on the result of Get_Priority on the elements. Seems slightly less readable (albeit more correct), to me. Can we keep my wording, but add "Get_Priority returns the priority (duh)."? Or "...is expected to..."? > I've made these changes (and Tucker's suggestion) in a separate > version (so we can recover yours if necessary). You always make a separate version, right? It's in CVS... **************************************************************** From: Randy Brukardt Date: Thursday, May 20, 2010 1:52 PM > You always make a separate version, right? It's in CVS... Not always; I make editorial corrections as I find them, which often means while I'm loading the file. So the original submission is never saved anywhere. I made a special point to do that this time, which is what I meant above. **************************************************************** From: Martin Dowie Date: Friday, May 21, 2010 2:55 AM Couple of minor points / questions and revision 1.10 The example references "Ada.Containers.Synchronized_Queues" and not "Ada.Containers.Synchronized_Queue_Interfaces". The Enqueue / Dequeue entries all have a "Container: Queue" paramater - but "Queue" is the name of the protected type containing these entries. I've had a look through the AI's referencing section 3.09 but didn't see anything that would make this allowable. I'm not sure it even makes sense - isn't the PT the queue?... In a number of the PTs, e.g. "Ada.Containers.Unbounded_Synchronized_Queues", the discriminent takes a default - is that allowed now? Also, for "Element_Type", shouldn't it be "Queue_Interfaces.Element_Type"? **************************************************************** From: Bob Duff Date: Friday, May 21, 2010 1:29 PM > Couple of minor points / questions and revision 1.10 > > The example references "Ada.Containers.Synchronized_Queues" and not > "Ada.Containers.Synchronized_Queue_Interfaces". Right. > The Enqueue / Dequeue entries all have a "Container: Queue" paramater > - but "Queue" is the name of the protected type containing these entries. > I've had a look through the AI's referencing section 3.09 but didn't > see anything that would make this allowable. I'm not sure it even > makes sense - isn't the PT the queue?... That's a mistake I made while converting from the old version to the new visibly-protected type. Those parameters should be removed. We made it visible so the ceiling priority stuff would make sense. > In a number of the PTs, e.g. > "Ada.Containers.Unbounded_Synchronized_Queues", the discriminent takes > a default - is that allowed now? Good point! I had forgotten that this type is tagged. I wonder if we should allow defaulted discriminants on limited types. > Also, for "Element_Type", shouldn't it be > "Queue_Interfaces.Element_Type"? Yes. Thanks for your comments. **************************************************************** From: Bob Duff Date: Friday, May 21, 2010 1:35 PM Randy, are you going to fix the editorial issues pointed out recently by Martin Dowie? Here's another one: There is one reference to Queues.Element_Type, and several to Element_Type, which should all be Queue_Interfaces.Element_Type. The defaulted discriminants issue is substantive -- we need to discuss that. **************************************************************** From: Randy Brukardt Date: Saturday, June 12, 2010 11:39 PM I just did that after I realized that you hadn't in your version of June 7th. I also noticed that the abstract functions Current_Use and Peak_Use were never defined in any of the concrete versions. I'd expect any decent Ada compiler to throw up on that, so I fixed that too. **************************************************************** From: Martin Dowie Date: Monday, June 28, 2010 5:10 PM Just wondering what I'm missing in the latest version of this AI... How are the queues expected to be implemented? e.g. with System; with Ada.Containers.Synchronized_Queue_Interfaces; generic with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>); package Ada.Containers.Bounded_Synchronized_Queues is pragma Preelaborate (Bounded_Synchronized_Queues); -- ****************************************************** -- No mention of an array type to hold the elements here -- e.g. could have written: -- type Queue_Elements_Type is private; -- ****************************************************** protected type Queue (Capacity : Count_Type; Ceiling : System.Any_Priority) is new Queue_Interfaces.Queue with pragma Priority (Ceiling); entry Enqueue (New_Item : Queue_Interfaces.Element_Type); entry Dequeue (Element : out Queue_Interfaces.Element_Type); function Current_Use return Count_Type; function Peak_Use return Count_Type; private -- ****************************************************** -- Can't define an array type to hold the elements here -- Can't use an anonymous array type -- Can't instantiate a bounded container package -- ****************************************************** Q : ; end Queue; end Ada.Containers.Bounded_Synchronized_Queues; **************************************************************** From: Randy Brukardt Date: Monday, June 28, 2010 8:53 PM The same would be true of the access types needed to implement the root of the data structures for the unbounded forms - they can't be written in the private part of the protected types either. (Anonymous types can't be used, you need to be able to deallocate them.) Generally, the rule for language-defined packages is that it is OK to add things that don't change the semantics of the package as viewed from a client. That means that pragmas, incomplete type declarations for visible entities, and a few other things are allowed. But adding type declarations are not. It would be a very bad idea to change this (it would defeat the entire point of privacy). The most important point about the predefined containers is that there is no restriction or requirements on how they are implemented. Thus, the contents of private parts have to be left totally to implementors, and that has to include the ability to declare any types they need. The private parts of protected types don't support that (for good reasons: nested type declarations cause various language nightmares). The only options that I can come up with: (1) Have the implementors put the types into the private part of the interface package. But those aren't visible in the protected object's private part unless it is (a) a parent unit and (b) some visibility rules are changed for the language as a whole. Not very promising. (2) Add some junk private type(s) to the definition to be used in the private part of the protected objects (and for no other purpose). [This is my understanding of your suggestion.] But then, those type(s) have to be documented (what are they for? what are the requirements on their streaming and equality operators? etc.). And that would be *very* limiting, as it would mean that the components could only have one particular design. (That would be completely inappropriate for the unbounded versions, and probably would be annoying even for the bounded versions as the implementation would be wildly different than the other containers.) There is no way this would even fly. (3) Get rid of the explicit protected objects and switch back to private types. However, there then is no sane way to require these to be implemented by protected objects -- there is no such thing as private protected (or task for that matter) types. None of these seem remotely like good ideas. My initial reaction is to completely give up and junk the entire thing. I suppose that is more frustration than logic talking, but the only one of the above that can even be considered is (3) -- and that means reintroducing the priority issues that we just tried to address (there being no way to require such private types to be implemented by protected objects, thus there is no sane way to specify the priority. Other ideas are welcome, but any idea has to allow for any arbitrary implementation of the private part of the protected objects, and can't make the contents of that part (or any of the types used to declare it) visible to clients of the queues. Those requirements don't allow many organizations of these packages. **************************************************************** From: Edmond Schonberg Date: Monday, June 28, 2010 9:12 PM Shouldn't the structure be: with System; with Ada.Containers.Synchronized_Queue_Interfaces; generic with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>); package Ada.Containers.Bounded_Synchronized_Queues is pragma Preelaborate (Bounded_Synchronized_Queues); type Queue (Capacity : Count_Type; Ceiling : System.Any_Priority) is new Queue_Interfaces.Queue with private; ... private -- whatever auxiliary types are needed. protected type Queue (Capacity : Count_Type; Ceiling : System.Any_Priority) is new Queue_Interfaces.Queue with pragma Priority (Ceiling); ... end Ada.Containers.Bounded_Synchronized_Queues; **************************************************************** From: Randy Brukardt Date: Monday, June 28, 2010 10:26 PM That's the structure I was talking about as choice (3) - (although I think you need the keyword "synchronized" in the private type), but we don't ever give any of the contents of the private part. So I don't see any way to require the implementation with a protected type or the meaning of the priority. Well, other than text to that effect, but I don't recall any other of the predefined libraries where we required a particular implementation. So that seems wrong to me (maybe it cannot be helped); if something is important, it ought to be in the contract, not in words. All of this implies to me that there is something wrong with the design of Ada and interfaces so far as requiring the implementation by a protected type. That seems to be important semantic information, yet Ada has no way to declare that a private type must be implemented by a protected type. Well, there is one way to do that: make the interface protected, which was rejected the last time. Perhaps we ought to add: type Protected_Queue is protected interface and Queue; and then derive the concrete types from Protected_Queue?? That would eliminate the need for word for at least the requirement to implement as a protected type. (We'd still have to add wording to require the ceiling priority to be that of the Ceiling discriminant.) In any case, this is very aggravating to do, as it will require reverting the entire AI to the previous version and then trying to apply the other changes back to it (the profiles of the routines being so different that it isn't sensible to try to repair them all individually; it took three iterations to get this set of protected changes right). And this is such a major change that the entire thing will have to go back for another vote, no way to treat this as a "typo"!! **************************************************************** From: Martin Dowie Date: Tuesday, June 29, 2010 1:45 AM Or... ...resurrect (some form of) AI05-0074!! E.g. with System; with Ada.Containers.Synchronized_Queue_Interfaces; generic with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>); package Ada.Containers.Bounded_Synchronized_Queues is pragma Preelaborate (Bounded_Synchronized_Queues); private -- Declarations for private part of protected type end private; protected type Queue (Capacity : Count_Type; Ceiling : System.Any_Priority) is new Queue_Interfaces.Queue with pragma Priority (Ceiling); entry Enqueue (New_Item : Queue_Interfaces.Element_Type); entry Dequeue (Element : out Queue_Interfaces.Element_Type); function Current_Use return Count_Type; function Peak_Use return Count_Type; private -- Uses previously declared types / instantiations / whatever end Queue; end Ada.Containers.Bounded_Synchronized_Queues; **************************************************************** From: Randy Brukardt Date: Tuesday, June 29, 2010 2:01 PM > Or... > ...resurrect (some form of) AI05-0074!! There are 4 very different alternatives in AI05-0074, and you are suggesting only a single one (AI05-0074-2). None of the others provide any sort of solution to this problem. Also note that this solution doesn't work, because the second visible part does not have visibility into the private part; that includes inside of the private part of the protected types. Recall that while child units have visibility into their parent's private part, that is not true for visible nested units. --- In any case, please do not resurrect this historically bad idea, which breaks the model for Ada syntax (putting "end" and a semicolon) into the middle of a construct, and destroys the reading model of Ada specifications (that clients can stop reading when they reach the "private" of the spec). The latter is also an important part of the implementation model of Ada compilers (especially when dealing with generic children). In addition, this construct does nothing to solve the actual problem that the series of AI05-0074-x proposals were trying to solve; a nested package works just as well (which is to say, not very well). **************************************************************** From: Simon Wright Date: Tuesday, June 29, 2010 3:51 PM >(2) Add some junk private type(s) to the definition to be used in the private >part of the protected objects (and for no other purpose). [This is my >understanding of your suggestion.] But then, those type(s) have to be >documented (what are they for? what are the requirements on their streaming and >equality operators? etc.). And that would be *very* limiting, as it would mean >that the components could only have one particular design. (That would be >completely inappropriate for the unbounded versions, and probably would be >annoying even for the bounded versions as the implementation would be wildly >different than the other containers.) There is no way this would even fly. Would this be so very bad? with System; generic type Element_Type is private; package Queues is type Representation_Type (Capacity : Positive) is limited private; protected type Queue (Capacity : Positive; Ceiling : System.Any_Priority) is pragma Priority (Ceiling); entry Enqueue (New_Item : Element_Type); entry Dequeue (Element : out Element_Type); function Current_Use return Natural; private Representation : Representation_Type (Capacity => Capacity); end Queue; private type Representation_Array is array (Positive range <>) of Element_Type; type Representation_Type (Capacity : Positive) is record -- Something to indicate which parts of Contents are -- occupied. Contents : Representation_Array (1 .. Capacity); end record; end Queues; **************************************************************** From: Randy Brukardt Date: Tuesday, June 29, 2010 4:20 PM "Very Bad"? -- Probably not. But it is lousy Ada design (because the type Representation_Type has no purpose for the client, and indeed it would be dangerous to declare an object of that type), and one of the things we always try to do is have the Ada standard library be good examples of Ada usage. (Obviously, we don't always succeed: see Strings, Unbounded). In any case, it would need a detailed description of what it is for, what a default initialized object does, we'd have to consider whether it must stream, how "=" works, does it need finalization, and so on. Moreover, the intended implementation is completely opaque (given that we don't give private parts in Ada). I suppose we could explain it in the AARM, but the causal reader of Ada will be completely mystified (as I was when I originally saw your suggestion - I had written a different initial response). Making the interface protected somehow and declaring an ordinary private type from seems like a less invasive solution to me (even thought we'll still need to use wording to explain the Ceiling priority - at least that would make sense). Both of the other workable solutions are ugly and would require a lot of new wording. **************************************************************** From: Simon Wright Date: Tuesday, June 29, 2010 11:43 PM Yes, I included a full implementation because I wanted to be sure that it would actually compile with the current language. Would there be any mileage in replacing my "type Representation_Type (Capacity : Positive) is limited private;" which is clearly much over-specified by (in italics) "Any types needed for the private part of protected type Queue. Not specified by the language."? **************************************************************** From: Martin Dowie Date: Wednesday, June 30, 2010 2:49 AM "Any types" => "Any declarations". This seems like a reasonable compromise to me - without starting a brand new AI on 'private to the outside world but visible to all'. Perhaps the "Implementation Advice" could be to use a 'mangled' name that would not be legal Ada in client code? Non-standard additions to standard packages have been the bane of many a project...yes, I'm looking at you XD-Ada!!! **************************************************************** From: Randy Brukardt Date: Wednesday, June 30, 2010 9:58 PM That would be a worse idea, because adding declarations to a language-defined package potentially causes incompatibilities. The effect of allowing random implementation-defined names in these packages is to reduce portability, even if the names aren't used by clients. (Names of types can make other things disappear via use-clause cancelation, if there is an identical name in some other package which is also "used".) That's why it is rare that the language allows the introduction of implementation-defined identifiers in language-defined packages. For instance, there have been several instances where allowing the addition of implementation-defined enumeration literals to extend a language-defined enumeration type would have seemed reasonable. But that has been deemed a bad idea and thus has not been allowed. **************************************************************** From: Bob Duff Date: Tuesday, July 6, 2010 10:21 AM > How are the queues expected to be implemented? e.g. >... > protected > type Queue (Capacity : Count_Type; >... > private > -- ****************************************************** > -- Can't define an array type to hold the elements here > -- Can't use an anonymous array type > -- Can't instantiate a bounded container package Thanks for pointing out this serious flaw in the AI! I worked on this AI, and I'm embarrassed that I didn't notice it. Randy wrote: > The same would be true of the access types needed to implement the > root of the data structures for the unbounded forms - they can't be > written in the private part of the protected types either. (Anonymous > types can't be used, you need to be able to deallocate them.) That's a good point. Couldn't an anon access type be used, and converted back and forth to/from a named access type used for [de]allocation? But that doesn't really solve the problem. The real issue is that the implementer should have freedom to use whatever (correct) implementation they like without polluting the client's name space. Martin's comment "instantiate a bounded container" above is relevant. > My initial reaction is to > completely give up and junk the entire thing. Well, we can't accuse Randy of being overly optimistic. ;-) Seriously, I'm not ready to junk it yet. Later Randy came up with this: > Perhaps we ought to add: > type Protected_Queue is protected interface and Queue; and then > derive the concrete types from Protected_Queue?? That would eliminate > the need for word for at least the requirement to implement as a > protected type. (We'd still have to add wording to require the ceiling > priority to be that of the Ceiling discriminant.) which is the best idea I've seen so far. Any fatal flaws in that? I think it's important that timed and conditional calls be allowed, which this solution provides. > In any case, this is very aggravating to do, as it will require > reverting the entire AI to the previous version and then trying to > apply the other changes back to it (the profiles of the routines being > so different that it isn't sensible to try to repair them all > individually; it took three iterations to get this set of protected changes right). Yes, it's aggravating, but if we can agree on the above solution (or some other), I'm willing to rewrite the AI. And I'm willing to try to get it right this time. ;-) >...And this is such a > major change that the entire thing will have to go back for another >vote, no way to treat this as a "typo"!! Agreed -- not a typo. > ...one of the things we > always try to do is have the Ada standard library be good examples of > Ada usage. True, but Ada has a flaw here: you can't declare hidden stuff to be used only in the private part of a protected or task type. We've always said, "Oh, well, it's not SO horrible to expose such stuff to clients, and put a comment '-- For internal use only'." But when it's language defined, it DOES seem horrible. Is there any support for fixing this flaw? E.g. make the private part of a package visible in the private part of a nested protected unit? Tricky to do, without incompatibilities and implementation problems rearing their ugly heads. I guess I don't recommend it. **************************************************************** From: Bob Duff Date: Tuesday, July 6, 2010 10:24 AM > That would be a worse idea, because adding declarations to a > language-defined package potentially causes incompatibilities. I agree. Polluting the client's namespace is bad, polluting it with impl-def stuff is worse. >... The effect of > allowing random implementation-defined names in these packages is to >reduce portability, even if the names aren't used by clients. (Names >of types can make other things disappear via use-clause cancelation, >if there is an identical name in some other package which is also >"used".) > > That's way it is rare that the language allows the introduction of > implementation-defined identifiers in language-defined packages. For > instance, there have been several instances where allowing the > addition of implementation-defined enumeration literals to extend a > language-defined enumeration type would have seemed reasonable. Can you remind me of some such case(s)? I'm curious. Note that enum lits aren't as bad, since they are overloadable, and therefore less likely to cause portability problems. >... But that has been deemed a > bad idea and thus has not been allowed. **************************************************************** From: Randy Brukardt Date: Tuesday, July 6, 2010 1:31 PM > > The same would be true of the access types needed to implement the > > root of the data structures for the unbounded forms - they can't be > > written in the private part of the protected types either. (Anonymous > > types can't be used, you need to be able to deallocate them.) > > That's a good point. Couldn't an anon access type be used, and > converted back and forth to/from a named access type used for > [de]allocation? The problem isn't so much with the access type as what it points at. Typically, that would be a node record of some sort, with an element object and some pointers to link nodes together. But there is no way to declare the node record. > But that doesn't really solve the problem. The real issue is that the > implementer should have freedom to use whatever > (correct) implementation they like without polluting the client's name > space. Martin's comment "instantiate a bounded container" above is > relevant. Right. **************************************************************** From: Martin Dowie Date: Tuesday, July 6, 2010 11:43 AM I agree. Polluting the client's namespace is bad, polluting it with impl-def stuff is worse. It's only worse if it's a legal Ada name that clients can use...my suggestion is to advise using a 'mangled' name for such thing. I'e be a bit surprised if there are compilers out there that don't use/allow 'special' internal names anyway. p.s. Hmmm wonder if there is anything in that the two people saying "just add a declaration and say something about it being special" are users and those say "don't" are compiler writers... :-) **************************************************************** From: Bob Duff Date: Tuesday, July 6, 2010 5:09 PM > It's only worse if it's a legal Ada name that clients can use...my > suggestion is to advise using a 'mangled' name for such thing. Ah, I see. I guess I didn't understand 'mangled' in this sense. So you mean a name that is not a legal Ada identifier, but that the compiler accepts given some special switch, right? Yes, that can easily work. It is somewhat unsatisfying, because the intent of ARG is that all container packages should be implementable in pure standard Ada. Preferably Ada in "good style", as Randy noted earlier. There is of course no RM requirement that the predefined stuff be implemented in Ada. It could be "magic". But it's nice if it's implementable in Ada. > I'e be a bit surprised if there are compilers out there that don't > use/allow 'special' internal names anyway. GNAT doesn't do that. The compiler does generate 'special' internal names, to be fed to the back end and linker, but it doesn't allow them in source code. > p.s. Hmmm wonder if there is anything in that the two people saying > "just add a declaration and say something about it being special" are > users and those say "don't" are compiler writers... :-) Or language lawyers. ;-) **************************************************************** From: Randy Brukardt Date: Tuesday, July 6, 2010 7:04 PM > GNAT doesn't do that. The compiler does generate 'special' > internal names, to be fed to the back end and linker, but it doesn't > allow them in source code. Janus/Ada doesn't have any special sort of identifier either. My theory always has been that if it can't be written in Ada, it isn't worth writing. (OK, that's not quite true, but we never saw any need for non-usable identifiers in source code. Link-time is a different story, as Bob noted.) So, Martin, don't be surprised, but those things probably don't exist in most compilers. **************************************************************** From: Martin Dowie Date: Wednesday, July 7, 2010 8:29 AM I shall consider myself slightly surprised! :-) Randy: you mentioned in a (much) earlier post that you particularly didn't want "end private" - how about "not private"? No new keyword and the parsing is still ad you described. Kind of in keeping with existing Ada style too, eg 'not null'. ps sorry for all the typos, I'm on holiday and tapping this all out on a very small screen! **************************************************************** From: Martin Dowie Date: Wednesday, July 7, 2010 8:33 AM > There is of course no RM requirement that the predefined stuff be implemented > in Ada. It could be "magic". But it's nice if it's implementable in Ada My guess is that users don't care about 'magic' - so long as it is a useful addition to the language that's making use of a feature. If 'magic' indicates a hole in the language (as this case seems to be) then it can always be fixed and the 'magic' removed in a later language revision. **************************************************************** From: Matthew Heaney Date: Wednesday, July 7, 2010 8:53 AM > Thanks for pointing out this serious flaw in the AI! > I worked on this AI, and I'm embarrassed that I didn't notice it. I don't understand any of this. The full view of the bounded queues type goes in the private part of the bounded queues spec. The partial view is a synchronized derivation from the abstract Queues type. I still don't see what the problem is. Ed S. posted the implementation in his last message. Here's what I have from an older draft of this AI: with Ada.Containers.Queues; generic with package Queues is new Ada.Containers.Queues (<>); package Ada.Containers.Bounded_Queues is pragma Pure; type Queue (Capacity : Count_Type) is synchronized new Queues.Queue with private; private type Elements_Type is array (Count_Type range <>) of Queues.Element_Type; protected type Queue (Capacity : Count_Type) is new Queues.Queue with overriding entry Enqueue (New_Item : Queues.Element_Type); overriding entry Dequeue (Element : out Queues.Element_Type); overriding function Is_Empty return Boolean; overriding function Is_Full return Boolean; private Elements : Elements_Type (1 .. Capacity); First : Count_Type; -- applies only when queue not empty Last : Count_Type := 0; -- queue is empty end Queue; end Ada.Containers.Bounded_Queues; Why is Martin saying the full view of the implementation of type (bounded) Queue is in the public part of the spec? Since when do we ever expose the implementation of the type? **************************************************************** From: Martin Dowie Date: Wednesday, July 7, 2010 9:44 AM That's an old proposal - check the latest revision for the new proposal. I think the problem was associating the priority with the type. With the 'old' proposal you need to say it in words - not in Ada (I think). **************************************************************** From: Matthew Heaney Date: Wednesday, July 7, 2010 8:48 AM Ed had written: > type Queue (Capacity : Count_Type; > Ceiling : System.Any_Priority) is > new Queue_Interfaces.Queue with private; Don’t you need to say “synchronized new” or “protected new” here? > >... >private > -- whatever auxiliary types are needed. > protected > type Queue (Capacity : Count_Type; > Ceiling : System.Any_Priority) is > new Queue_Interfaces.Queue with > pragma Priority (Ceiling); > > ... > >end Ada.Containers.Bounded_Synchronized_Queues; Yes, agreed -- I had simply assumed that this was how the concrete type was declared. **************************************************************** From: Randy Brukardt Date: Wednesday, July 7, 2010 11:15 AM > type Queue (Capacity : Count_Type; > Ceiling : System.Any_Priority) is > new Queue_Interfaces.Queue with private; > > Don't you need to say "synchronized new" or "protected new" here? You have to say "synchronized new". There is no "protected new". Which is the problem. We need to require that the implementation is a protected type, and we need to specify its ceiling priority is that of the discriminant. There is no way in the current language to do either for the private extension. It was pointed out that given that, there is no need for the private type, since a protected type has its own private part. But we missed the fact that you can't actually declare types in that private part, and it doesn't have visibility on private children, so there is no way to hide the types used there. This is generally a problem with Ada protected types, one that we were not able to find a solution to because of the mess of additional operations that would have to appear inside of another type. > Yes, agreed -- I had simply assumed that this was how the concrete > type was declared. That was not the proposal; it would help if you actually read the AIs from time to time. :-) Requiring this to be the implementation is extremely ugly and lousy Ada style, but it appears we don't have much choice. One thing that would help is to create a protected interface (which then requires the implementation to be protected). Bob is planning to rewrite the AI this way, if I understand the e-mail correctly. **************************************************************** From: Bob Duff Date: Wednesday, July 7, 2010 12:20 PM > Bob is planning to rewrite the AI this way, if I understand the e-mail > correctly. If there's a consensus on the solution. **************************************************************** From: Randy Brukardt Date: Wednesday, July 7, 2010 1:06 PM Is there any other viable alternative? I haven't heard one. **************************************************************** From: Bob Duff Date: Wednesday, July 7, 2010 1:48 PM > Is there any other viable alternative? I haven't heard one. Well, some people have suggested that compiler magic is viable. That is, the compiler processes predefined units in a special mode that allows normally-illegal identifiers, thus avoiding polluting the client's namespace. I don't much like that solution, but it's certainly easy to implement. **************************************************************** From: Simon Wright Date: Wednesday, July 7, 2010 2:08 PM As I understand it, the idea is that the standard should say something like "declarations necessary to implement the private part of the protected type, not defined by the language" with implementation advice that measures should be taken to ensure that such declarations aren't available to users of the package. If that was the case, then instead of mangling names an implementation might choose to use an implementation-defined pragma, eg Package_Visibility_Only, to make this happen. **************************************************************** From: Randy Brukardt Date: Wednesday, July 7, 2010 2:15 PM > I don't much like that solution, but it's certainly easy to implement. That seems completely bogus as a "solution" to me; we've never required that in any other case for the specifications of Ada predefined units, and it seems bad to start now. If Ada isn't powerful enough to describe some packages, the solution is to fix Ada, not require implementers to create some sort of hack. **************************************************************** From: Randy Brukardt Date: Wednesday, July 7, 2010 3:00 PM > If that was the case, then instead of mangling names an implementation > might choose to use an implementation-defined pragma, eg > Package_Visibility_Only, to make this happen. No Ada implementer is going to fiddle with the extremely delicate visibility machinery if any easier solution is available. And pragmas are particularly annoying when they change the properties of some declaration, because they come after the declaration and that generally means having to alter the declaration after the fact (with all of the complications of freezing rules in order to avoid problems). It's way more machinery than the problem is worth, especially when a relatively simple solution (allowing '$' in identifiers, for instance) is available. So this is a long-winded way to say the same thing. Also note that Implementation Advice (which implementers are allowed to ignore, and commonly do) is not strong enough here. The implementation shall not pollute the client's namespace, ever -- this is *not* Advice, it would have to be a Requirement. The point is, that this would save nothing over the private type solution. The reason for avoiding that solution was to reduce the amount of English text needed. If we have to put in a number of Implementation Permissions and Implementation Requirements to allow these extra declarations, we've gained nothing over simply having an Implementation Requirement that the private type be implemented with a protected type with a ceiling priority of Ceiling. The latter is probably shorter and does not require compiler magic. Given two equal length alternatives, one that requires compiler magic and one that does not, we've be insane to chose the one requiring magic. Which is why I don't understand why we're even discussing this... **************************************************************** From: Bob Duff Date: Wednesday, July 7, 2010 3:45 PM > As I understand it, the idea is that the standard should say something > like "declarations necessary to implement the private part of the > protected type, not defined by the language" with implementation > advice that measures should be taken to ensure that such declarations > aren't available to users of the package. > > If that was the case, then instead of mangling names an implementation > might choose to use an implementation-defined pragma, eg > Package_Visibility_Only, to make this happen. If that's the desired solution, then no RM verbiage is needed. Compilers are always allowed to use magic to implement predefined stuff. And they are required to avoid polluting the client's namespace (as Randy said, that's not mere "Advice"). Any such verbiage would belong in the AARM. The easiest such magic is to allow syntactically illegal identifiers in a special mode. But pragmas could work, too -- that's just harder to implement. But I agree with Randy that it is undesirable to require the use of magic to implement these queue packages. **************************************************************** From: Bob Duff Date: Wednesday, July 7, 2010 3:53 PM > That seems completely bogus as a "solution" to me; ... I agree it's undesirable (maybe not quite "completely bogus"). >...we've never required that > in any other case for the specifications of Ada predefined units, ... Well, magic is required to implement type Wide_Wide_Character. ;-) >...and it > seems bad to start now. If Ada isn't powerful enough to describe some >packages, the solution is to fix Ada, not require implementers to >create some sort of hack. To me, "fix Ada" would mean "provide a mechanism for declaring the necessary types such that they are visible in the private part of the protected type, but not visible to clients". Users have definitely complained about the lack of such a feature. But I think that would require major surgery to the language, and also to implementations, so I'm not in favor of that. Historical note: I think Tucker's original Ada 9X proposal involved a solution to this problem. **************************************************************** From: Randy Brukardt Date: Wednesday, July 7, 2010 4:15 PM ... > >...we've never required that > > in any other case for the specifications of Ada predefined units, ... > > Well, magic is required to implement type Wide_Wide_Character. ;-) I don't see that. Character literals are part of the language, no magic there. And whatever is in the compiler's symboltable is irrelevant, given that users can't see it (one could consider anything there "magic" if you want). You probably do need magic to implement Wide_Wide_Character'Image and 'Value (else the needed table gets really large), but there again exactly how such things are represented is really implementation-defined and irrelevant clients. So I think we need a better definition of "magic" to settle this. I would argue that it is some feature that is visible to clients that they cannot implement/use themselves. By that definition, all uses of 'Image are magic. > >...and it > > seems bad to start now. If Ada isn't powerful enough to describe > >some packages, the solution is to fix Ada, not require implementers > >to create some sort of hack. > > To me, "fix Ada" would mean "provide a mechanism for declaring the > necessary types such that they are visible in the private part of the > protected type, but not visible to clients". Users have definitely > complained about the lack of such a feature. > > But I think that would require major surgery to the language, and also > to implementations, so I'm not in favor of that. I agree, especially at this late point. But by "fix Ada", I also meant to include "changing the (predefined) packages such that the problem is eliminated". After all, Ada doesn't allow you to write every possible program in every possible way; sometimes some restructuring is needed to get a good solution. Just because restructuring is needed doesn't mean that Ada is broken. I'm more concerned about the lack of "protected" and "task" as possibilities in private types. It seems strange to me that you can require a private type to be implemented by a limited or synchronized type, but you can't be more specific than that even though there are massive differences in active and passive implementations (and it is commonly the case that one or the other will not work properly, especially if priorities matter). If we could define a protected private extension, we'd only need one additional sentence of English (to describe the priority), which seems OK to me. I suggested using a protected interface as a workaround for this omission, but that also clutters the name-space a bit. **************************************************************** From: Bob Duff Date: Wednesday, July 7, 2010 4:47 PM > I don't see that. Character literals are part of the language, no > magic there. I meant that it is impractical to type in the text of package Standard, with all 2**31 or however many characters are in Wide_Wide_Character. Also, the control characters are written in italics to indicate that they're not real identifiers. GNAT concocts the Standard symbol table out of whole cloth, rather than compiling some psuedo source text. ... > So I think we need a better definition of "magic" to settle this. Well, we don't really need to settle it, since we both agree that requiring magic for the queues packages is a bad idea. My definition of "magic" is anything that's not written in pure standard Ada. There's lots of magic required in predefined package BODIES, but we try to keep it out of visible parts. ... > But by "fix Ada", I also meant to include "changing the (predefined) > packages such that the problem is eliminated". After all, Ada doesn't > allow you to write every possible program in every possible way; > sometimes some restructuring is needed to get a good solution. Just > because restructuring is needed doesn't mean that Ada is broken. OK. > I'm more concerned about the lack of "protected" and "task" as > possibilities in private types. It seems strange to me that you can > require a private type to be implemented by a limited or synchronized > type, but you can't be more specific than that even though there are > massive differences in active and passive implementations (and it is > commonly the case that one or the other will not work properly, > especially if priorities matter). If we could define a protected > private extension, we'd only need one additional sentence of English > (to describe the priority), which seems OK to me. I suggested using a > protected interface as a workaround for this omission, but that also clutters the name-space a bit. If the clutter is standard, then it's not a big problem. **************************************************************** From: Randy Brukardt Date: Thursday, August 5, 2010 7:21 PM > To me, "fix Ada" would mean "provide a mechanism for declaring the > necessary types such that they are visible in the private part of the > protected type, but not visible to clients". Users have definitely > complained about the lack of such a feature. > > But I think that would require major surgery to the language, and also > to implementations, so I'm not in favor of that. Interestingly, I've been thinking about this, and I've concluded its not that bad (although I may have forgotten some Baird-cases). More importantly, it's better than the alternatives that we previously discussed, which all require some form of name-space pollution and (in most cases) loss of readability. I mistakenly spent all day yesterday formatting the current version of AI05-159-1 for the Standard, having forgotten about this thread. When I remembered it this morning, I was very annoyed. I then tried to figure out what the change would have to be, and realized that virtually all of them are in fact illegal for one reason or another. But let me refresh everyone as to what the problem was. The proposed specification for Unbounded_Synchronized_Queues is as follows: with System; with Ada.Containers.Synchronized_Queue_Interfaces; generic with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>); Default_Ceiling: System.Any_Priority := System.Priority'Last; package Ada.Containers.Unbounded_Synchronized_Queues is pragma Preelaborate(Unbounded_Synchronized_Queues); protected type Queue (Capacity : Count_Type := Default_Capacity; Ceiling: System.Any_Priority := Default_Ceiling) is new Queue_Interfaces.Queue with pragma Priority(Ceiling); overriding entry Enqueue (New_Item: in Queue_Interfaces.Element_Type); overriding entry Dequeue (Element: out Queue_Interfaces.Element_Type); overriding function Current_Use return Count_Type; overriding function Peak_Use return Count_Type; private ... -- not specified by the language end Queue; private ... -- not specified by the language end Ada.Containers.Unbounded_Synchronized_Queues; Martin Dowie pointed out that this isn't implementable, because there is nowhere to define the "helper" types needed to implement the protected queue. For the bounded forms, this would be (at least) an array of elements; for the unbounded forms, this would be (at least) some sort of queue node [we can use anonymous access types for the pointers, but the node will need a record]. This is a problem because types are not allowed to be declared in the private part of a protected type, and there is nowhere else to put them that would have the appropriate visibility (there is no visibility into the private part of a formal package, for instance, and the private part of this package is too late). The easiest fix is to add type Queue_Implementation_Type is private; before protected type Queue. This type could be completed by whatever the implementer needed, and with sufficient cleverness, would suffice for virtually any possible data structure. We would have to add some wording to explain it (this is used to implement the queue and should be ignored by users), and that is ugly. It also adds some name pollution to the user's name space (which can be minimized by selecting a name that could never conflict with anything real: type Queue_Implementation_Type_Do_Not_Use_In_Client_Code is private; Because this was so ugly, we pretty much decided to revert to a private version of the type. We proposed adding type Protected_Queue is protected interface and Queue; to the interface package, and then revising the package to look like: with System; with Ada.Containers.Synchronized_Queue_Interfaces; generic with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>); Default_Ceiling: System.Any_Priority := System.Priority'Last; package Ada.Containers.Unbounded_Synchronized_Queues is pragma Preelaborate(Unbounded_Synchronized_Queues); type Queue (Capacity : Count_Type := Default_Capacity; Ceiling: System.Any_Priority := Default_Ceiling) is synchronized new Queue_Interfaces.Protected_Queue with private; overriding procedure Enqueue (Container : in out Queue; New_Item : in Element_Type); overriding procedure Dequeue (Container : in out Queue; Element : out Element_Type); overriding function Current_Use (Container : Queue) return Count_Type; overriding function Peak_Use (Container : Queue) return Count_Type; private ... -- not specified by the language end Ada.Containers.Unbounded_Synchronized_Queues; However, this structure also cannot be implemented, at least with the rules of Ada as they are today. There are two problems. First, the declaration of procedure Enqueue and Dequeue are illegal, because they are not entries, and the original declaration has pragma Implemented (By_Entry). We could fix that by putting the pragma on these declarations as well, or by changing the rules for pragma Implemented. But the big problem is the second one: there is no way to complete these procedure declarations with an entry. We presume a protected type like the original type Queue is given in the private part. That would have the appropriate entries, but there is no way to connect them to these explicit declarations. That's because the entire "implemented by" mechanism is defined to *override* inherited routines, not to *complete* explicit routines. Indeed, 9.4(11.4/3) makes the declaration of subprograms like Dequeue these *illegal* because of the conflict. We could try to fix this, but it would be an earthquake in the language definition (pretty much the entire model would have to be blown up and done over more generally). I suspect the implementation changes wouldn't be as bad (there isn't much difference between an inherited routine and an explicitly declared specification of a routine), but it would take forever to get the bugs out of any major standard rewrite (it's not clear that we've gotten all of the bugs out of the current model!). We can fix this problem by omitting the declarations of subprograms altogether, since the language does allow overriding abstract routines in the private part (and there the "implemented by" would be in place of overriding, which is OK). That would make the specification look like: with System; with Ada.Containers.Synchronized_Queue_Interfaces; generic with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>); Default_Ceiling: System.Any_Priority := System.Priority'Last; package Ada.Containers.Unbounded_Synchronized_Queues is pragma Preelaborate(Unbounded_Synchronized_Queues); type Queue (Capacity : Count_Type := Default_Capacity; Ceiling: System.Any_Priority := Default_Ceiling) is synchronized new Queue_Interfaces.Protected_Queue with private; private ... -- not specified by the language end Ada.Containers.Unbounded_Synchronized_Queues; While this is legal, we've lost all readability. One of the big advantages of the original design is that while we had interfaces involved, you could completely ignore them unless you wanted to use them. But this this structure, everyone has to understand how interfaces inherit operations in order to have any idea of what is going on. I would guess that 98% of Ada programmers would be completely mystified by this specification! We could of course put the inherited declarations into comments or into text in order to reduce this problem, but that is ugly and not necessarily any less confusing. (It might help the 25% of Ada programmers that have some understanding of derivation and/or OOP, but the rest will still be lost.) The priority queues make this into an even worse problem. As you may recall, the priority queues have an additional operation that is not inherited. This operation is also supposed to be implemented by an entry, so just adding: procedure Dequeue_Only_High_Priority (Container : in out Queue; Low_Priority : in Queue_Priority; Element : out Queue_Interfaces.Element_Type); to the above specification just brings up the same set of problems as the original private specification. The only way that this can be solved is to add yet another interface that has this operation: type Protected_Priority_Queue is protected interface and Queue; procedure Dequeue_Only_High_Priority (Container : in out Protected_Priority_Queue; Low_Priority : in Queue_Priority; Element : out Queue_Interfaces.Element_Type) is abstract; Note that this solution also has a name-space pollution problem, because here we've added two interfaces that we didn't really need. -------- Finding neither of these solutions very palatable, I decided to look back at the original problem. It's unnatural to try to hide a protected type in the private part; such types are by their nature private (anything you want to hide can be hidden in the private part of the type) and given that we want to insist that it is implemented by a protected type (which is almost always the case for such interfaces, especially if priorities are to be supported meaningfully), it makes no sense to try hide the type. So the original specifications are preferable. So what could we do to allow the original specifications to be implementable? After all, the inability to declare types in a protected type's private part has been a long-standing headache. The main reason for not allowing types inside of other types is that nesting of type declarations causes various semantic problems (mostly having to do with "additional operations"). But in thinking about this, I don't think this case is anything like the cases that we've previously worried about (as in record types), as a protected type is a unit with its own visibility. So I wonder if this limitation could be lifted (or partially lifted) without any major problems. I'll explore that in my next message. **************************************************************** From: Randy Brukardt Date: Thursday, August 5, 2010 8:14 PM As noted in my previous message, the Queue containers could be implemented directly if we allowed (some) type declarations in the private part of a protected type. We would need to allow at a minimum array types, untagged record types, and access types. The idea of allowing anonymous array types in record components has been explored in the past. Allowing that brings up various problems, mostly because the location of the declaration of the predefined operators is not well-defined. (Unfortunately, I haven't been able to find any discussion of this problem in the AARM or in any Rationale, so I'm not sure exactly what the problem is.) [Note that allowing anonymous array types alone would not be enough to make these packages implementable, it's just an example.] Generally, we've considered record types and protected types as similar. As such, since we can't allow this for record types, we've not even considered it for protected types. But in actuality, there isn't much in common between record and protected types: * A protected type is a unit, with a separate private part and body; a record is completely visible; * A protected type only allows declaring private components; a record only allows visible components; * A consequence of the previous is that a protected type does not allow an aggregate naming any components, nor is there any other way to name components outside of the protected type. These differences mean that any type declared in the private part of a protected type could only be visible in that protected part and the body of the protected type. That also extends to any predefined or inherited operations. Thus, if there are any anomalies, they would have to be limited to the protected type itself. One clear area of confusion would be whether exclusion would apply to any primitive routines. Note that there cannot be any new primitive subprograms (those can only exist in a package specification, which this is not), but new routines could be created via overriding. Routines declared within a protected type have a different profile (with an implicit PO parameter), which complicates overriding as well. But this is easily solved by simply not allowing any overriding of primitive operations for any type declared within a protected object. Once we've banned overriding, it's clear that tagged types have become useless (there can be no useful dispatching, and derivation does nothing but create a new tag), so we could simply ban them rather than try to figure out the implications. We surely don't want to add new kinds of unit nesting, so we also would ban type and protected types. Existing rules prevent the outer protected type itself from appearing in one of these declarations (other than as the designated type of an access type). What else could happen? It would be possible for "additional operations" to be declared at the start of the protected body. That doesn't seem to cause any hardship beyond what "additional operations" already do. There isn't any way for them to appear anywhere else (it's not possible to change the outer visibility while inside of the protected type). So it appears to me that a couple of additional rules would allow useful untagged type declarations within the private part and body of a protected type. In order to give Steve something to chew on, here is a concrete proposal. (Note: I think we would want to also allow anonymous array types here, in order to be consistent, but I didn't attempt to work out what was needed to do that.) ------------- Modify 9.4(6) to: protected_element_declaration ::= protected_operation_declaration | component_declaration | type_declaration | subtype_declaration Modify 9.4(8/1) to: protected_operation_item ::= subprogram_declaration | subprogram_body | entry_body | aspect_clause | type_declaration | subtype_declaration Add after 9.4(11.13/2): [Legality Rules] A type_declaration that appears in a protected_element_declaration or a protected_operation_item shall not be for a tagged, protected, or task type. No subprogram shall override an inherited or predefined operation of the type declared by a type_declaration that appears in a protected_element_declaration or a protected_operation_item. ------------ Note that I added subtypes as well; I can't think of any problem with them. Do we need to say that any inherited or predefined operation of the type declared by a type_declaration that appears in a protected_element_declaration or a protected_operation_item does not have any special exclusion properties? I don't think so, given that it is an internal operation that can only be called from some other existing operation. How bad is the implementation of this? If the compiler represents a protected type as a unit in its symbol table, I would be surprised if there is a significant hardship to implement the visibility needed: it is just more declarations in a scope. Code needed would be limited; the main effect would be on finalization (as controlled components could be used in a record or array type, and access type collections might have to be finalized). I don't want to predict how bad that would be for other implementations, as they vary so much on this part. But compilers already have to deal with controlled components in protected types, so additional kinds of finalization at least have a clear place to be added. All-in-all, this would appear to be a big win for the usability of Ada (assuming no Steve Baird showstoppers...). It is more complex than just restructuring the Queue packages yet again, but it also fixes a long-standing Ada complaint. So I guess I'd like a serious look at it. **************************************************************** From: Martin Dowie Date: Saturday, March 5, 2011 3:22 AM I see that the latest revision has the default discriminant back: package Ada.Containers.Unbounded_Synchronized_Queues is ... protected type Queue (Ceiling: System.Any_Priority := Default_Ceiling) ... I can't find the AI that allows this - can someone please tell me what I'm missing? **************************************************************** From: Randy Brukardt Date: Saturday, March 5, 2011 11:00 PM See AI05-0214-1. This AI was approved at the most recent ARG meeting, but I haven't posted the approved version yet (it's essentially unchanged except for the addition of an AARM note to explain the intent for 'Constrained of an untagged type derived from an ultimately tagged type. ****************************************************************