Version 1.3 of ai05s/ai05-0251-1.txt

Unformatted version of ai05s/ai05-0251-1.txt version 1.3
Other versions for file ai05s/ai05-0251-1.txt

!standard A.18.27(0)          11-07-20 AI05-0251-1/02
!standard A.18.30(0)
!standard A.18.31(0)
!class Amendment 11-06-15
!status Amendment 2012 11-07-20
!status ARG Approved 11-0-1 11-06-25
!status work item 11-06-15
!status received 11-06-13
!priority Medium
!difficulty Medium
!subject Problems with queue containers
!summary
There are no indefinite versions of the queue containers.
Dequeue_Only_High_Priority is non-blocking.
!question
(1) It seems very hard to use the indefinite version of Dequeue, since it requires knowing the tag/constraints of the item before it is retrieved. Is this intended? (No.)
(2) It seems that the implementation of Dequeue_Only_High_Priority probably requires the use of requeue if an item of the appropriate priority is not available. What is the intended interaction with simultaneous calls to Dequeue? (Unknown.)
(3) The parameter name Low_Priority in Dequeue_Only_High_Priority seems dubious; it represents the highest priority that will not be dequeued.
!proposal
(See wording.)
!wording
For (1), remove A.18.32 (the indefinite queues).
Add a user note at the end of A.18.27:
Note: Unlike other language-defined containers, there are no queues whose element types are indefinite. Elements of an indefinite type can be handled by defining the element of the queue to be a holder container (see A.18.18) of the indefinite type, or to be an explicit access type that designates the indefinite type.
AARM Reason: There are no indefinite queues as a useful definition for Dequeue is not possible. Dequeue cannot be a function as Ada does not have entries that are functions (thus conditional and timed calls would not be possible) and moreover protected functions do not allow modifying the queue object (thus it doesn't work even if we decided we didn't care about conditional and timed calls). If Dequeue is an entry, then the dequeued object would have to be an out parameter and that would require the queue client to guess the tag and constraints of the value that will be dequeued (otherwise Constraint_Error would be raised), and that is rarely going to be possible.
For (2) and (3), replace A.18.30(6/3) and A.18.31(6/3) by:
not overriding procedure Dequeue_Only_High_Priority (At_Least : in Queue_Priority; Element : in out Queue_Interfaces.Element_Type; Success : out Boolean);
Replace A.18.30(17/3):
For a call on Dequeue_Only_High_Priority, if the head of the non-empty queue is E, and the function Before(At_Least, Get_Priority(E)) returns False, then E is assigned to Element and then removed from the queue, and Success is set to True; otherwise Success is set to False and Element is unchanged.
AARM Ramification: Unlike Dequeue, Dequeue_Only_High_Priority is not blocking; it always returns immediately.
AARM Reason: The use of Before is "backwards" so that it acts like ">=" (it is defined similarly to ">"); thus we dequeue only when it is False.
Modify A.18.27(12/3) to use wording consistent with the above:
If the queue is empty, then Dequeue blocks until an item becomes available. In any case, it then [returns a copy of]{assigns} the element at the head of the queue {to Element}, and removes it from the [container]{queue}.
!discussion
Properly implementing Dequeue_Only_High_Priority as blocking would require the use of requeue onto two different queues so that the calls are serviced in the order received when the Low_Priority is equivalent. This is pretty complex.
Moreover, the majority of examples that we've seen for this routine require some sort of polling (a delay queue, for example, has to be polled because the time is always changing). Thus we simplify the definition and implementation of the language by making this routine return immediately along with a success or failure indication.
!ACATS test
No additional ACATS Tests should be needed, but the test for Dequeue_Only_High_Priority needs to take the new definition into account.
!ASIS
No effect on ASIS (this is a predefined package).
!corrigendum A.18.27(0)
Insert new clause:
Force a conflict; real text found in the conflict file.
!corrigendum A.18.30(0)
Insert new clause:
Force a conflict; real text found in the conflict file.
!corrigendum A.18.31(0)
Insert new clause:
Force a conflict; real text found in the conflict file.
!appendix

From: Matthew Heaney
Sent: Monday, June 13, 2011  7:28 AM

I had a couple of questions about the semantics of the new queue containers,
described in AI05-0159.

(1) The Dequeue operation is described this way:

    procedure Dequeue
      (Container : in out Queue;
       Element   :    out Element_Type) is abstract
          with Is_Synchronized => By_Entry;


There are variants of the queue packages that accept an indefinite element type.
How does Dequeue work for an indefinite type?


(2) The priority queues have an additional dequeue operation:

    not overriding
    entry Dequeue_Only_High_Priority
       (Low_Priority : in     Queue_Priority;
        Element      :    out Queue_Interfaces.Element_Type);


Suppose the priority queue is empty and there's a task waiting on each
of Dequeue and Dequeue_Only_High_Priority.  Does this AI say which
waiting task gets priority, when an element is enqueued?

I'm having a bit of trouble with the entry barriers for the priority
queues.  I think Dequeue_Only_High_Priority must be implemented using
some form of requeue statement (I don't think the Low_Priority parameter
can be used in the entry barrier expression), and that got me thinking
about the relative priorities of the dequeue entries.

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

From: Tucker Taft
Sent: Monday, June 13, 2011  10:32 AM

> I had a couple of questions about the semantics of the new queue
> containers, described in AI05-0159.
>
> (1) The Dequeue operation is described this way:
>
> procedure Dequeue
> (Container : in out Queue;
> Element : out Element_Type) is abstract with Is_Synchronized =>
> By_Entry;
>
>
> There are variants of the queue packages that accept an indefinite
> element type. How does Dequeue work for an indefinite type?

Excellent question.  It will be annoying if the caller has to predict the
constraints of the next item in the queue.  I suspect we should eliminate the
"indefinite" versions of this package, and require any discriminants to have
defaults.

By the way "Is_Synchronized" has become "Synchronization."

>
>
> (2) The priority queues have an additional dequeue operation:
>
> not overriding
> entry Dequeue_Only_High_Priority
> (Low_Priority : in Queue_Priority;
> Element : out Queue_Interfaces.Element_Type);
>
>
> Suppose the priority queue is empty and there's a task waiting on each
> of Dequeue and Dequeue_Only_High_Priority. Does this AI say which
> waiting task gets priority, when an element is enqueued?

That seems like a general queuing policy issue, and hopefully the general
queuing policy mechanisms are used.  E.g. if the Priority_Queuing policy
applies:

When more than one condition of an entry_barrier of a protected object becomes
True, and more than one of the respective queues is nonempty, the call with the
highest priority is selected. If more than one such call has the same priority,
the call that is queued on the entry whose declaration is first in textual order
in the protected_definition is selected. For members of the same entry family,
the one with the lower family index is selected.

As you suggest below, a requeue is probably required, so that makes it hard to
determine the textual order of the entry declaration, since it will probably end
up in the private part.  That is a further argument for eliminating the need for
a requeue by making Low_Priority parameter into an entry family index (see
below).

> I'm having a bit of trouble with the entry barriers for the priority
> queues. I think Dequeue_Only_High_Priority must be implemented using
> some form of requeue statement (I don't think the Low_Priority
> parameter can be used in the entry barrier expression), and that got me
> thinking about the relative priorities of the dequeue entries.

That argues for making the Low_Priority parameter into an entry family index
rather than leaving it as a parameter.  I will admit I never noticed this
operation before.  At which ARG meeting was it discussed?

...

Good questions!

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

From: Matthew Heaney
Sent: Monday, June 13, 2011  11:59 AM

> That argues for making the Low_Priority parameter into an entry family
> index rather than leaving it as a parameter. I will admit I never
> noticed this operation before. At which ARG meeting was it discussed?

Except that the generic formal Queue_Priority type is a non-limited private
type, not a scalar type.

The semantics of the Deque_Only_High_Priority are also strange: the Low_Priority
parameter specifies the priority just larger than what is considered a high
priority.  So if I have this:

   type Priority_Type is (High, Medium, Low);

and I want to deque a high priority item, I have to say:

   PQ.Deque_Only_High_Priority (Medium);

This seems error-prone to me.

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

From: Tucker Taft
Sent: Monday, June 13, 2011  12:27 PM

>> That argues for making the Low_Priority parameter into an entry
>> family index rather than leaving it as a parameter. I will admit I
>> never noticed this operation before. At which ARG meeting was it
>> discussed?
>
> Except that the generic formal Queue_Priority type is a non-limited
> private type, not a scalar type.

Uggh.  Good point.  I suppose we could make it a formal discrete type.
If it is a formal private type, then the underlying requeued call would have to
wake up each time the priority of the highest priority item changes to compare
against the "Low_Priority" value. Doesn't seem very efficient.

>
> The semantics of the Deque_Only_High_Priority are also strange: the
> Low_Priority parameter specifies the priority just larger than what is
> considered a high priority. So if I have
> this:
>
> type Priority_Type is (High, Medium, Low);
>
> and I want to deque a high priority item, I have to say:
>
> PQ.Deque_Only_High_Priority (Medium);
>
> This seems error-prone to me.

I agree it seems a bit weird.  I presume we must have discussed it during some
ARG meeting, but I can't recall the discussion at all.  From the AI I can see
where Randy suggested the idea in the e-mail, but I wonder whether we ever
reviewed it in an ARG meeting, and if so what were our conclusions.

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

From: Edmond Schonberg
Sent: Monday, June 13, 2011  12:31 PM

...
> I agree it seems a bit weird.  I presume we must have discussed it
> during some ARG meeting, but I can't recall the discussion at all.
> From the AI I can see where Randy suggested the idea in the e-mail,
> but I wonder whether we ever reviewed it in an ARG meeting, and if so
> what were our conclusions.

Let's review it at the coming meeting.

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

From: Randy Brukardt
Sent: Monday, June 13, 2011  11:54 PM

> > (1) The Dequeue operation is described this way:
> >
> > procedure Dequeue
> > (Container : in out Queue;
> > Element : out Element_Type) is abstract with Is_Synchronized =>
> > By_Entry;
> >
> >
> > There are variants of the queue packages that accept an indefinite
> > element type. How does Dequeue work for an indefinite type?
>
> Excellent question.  It will be annoying if the caller has to predict
> the constraints of the next item in the queue.  I suspect we should
> eliminate the "indefinite" versions of this package, and require any
> discriminants to have defaults.

Given that the indefinite forms are by far the most important container forms
(the definite forms are trivial to write yourself, especially for queues), I'd
rather get rid of all of the queues in that case. Otherwise, we're saying that
mixing OOP (such as T'Class) and task-safe operations is not possible, and
that's a message that we never want to be sending (even if true).

It's highly unfortunate that Ada really does not allow some thing like an entry
function. Not everything can be modeled as an out parameter.

I can't think of an alternative design that would work -- is it really true that
it is impossible to have a blocking operation and return an indefinite object?

> By the way "Is_Synchronized" has become "Synchronization."

I'll need to fix that, if we keep the queues.

> > (2) The priority queues have an additional dequeue operation:
> >
> > not overriding
> > entry Dequeue_Only_High_Priority
> > (Low_Priority : in Queue_Priority;
> > Element : out Queue_Interfaces.Element_Type);
> >
> >
> > Suppose the priority queue is empty and there's a task waiting on
> > each of Dequeue and Dequeue_Only_High_Priority. Does this AI say
> > which waiting task gets priority, when an element is enqueued?
>
> That seems like a general queuing policy issue, and hopefully the
> general queuing policy mechanisms are used.  E.g. if the
> Priority_Queuing policy applies:
>
> When more than one condition of an entry_barrier of a protected object
> becomes True, and more than one of the respective queues is nonempty,
> the call with the highest priority is selected. If more than one such
> call has the same priority, the call that is queued on the entry whose
> declaration is first in textual order in the protected_definition is
> selected.
> For members of the same entry family, the one with the lower family
> index is selected.
>
> As you suggest below, a requeue is probably required, so that makes it
> hard to determine the textual order of the entry declaration, since it
> will probably end up in the private part.  That is a further argument
> for eliminating the need for a requeue by making Low_Priority
> parameter into an entry family index (see below).
>
> > I'm having a bit of trouble with the entry barriers for the priority
> > queues. I think Dequeue_Only_High_Priority must be implemented using
> > some form of requeue statement (I don't think the Low_Priority
> > parameter can be used in the entry barrier expression), and that got
> > me thinking about the relative priorities of the dequeue entries.
>
> That argues for making the Low_Priority parameter into an entry family
> index rather than leaving it as a parameter.

Unfortunately, we can't do that, because protected interface operations (like
this one) can never be implemented by an entry family.

It should be noted that the original proposal for protected interface operations
included a mechanism to handle entry families, but it was considered "too
complex" and dropped over my strong objections. A problem like this one was
precisely the sort of thing I was worried about.

> I will admit I never noticed this operation before.  At which ARG
> meeting was it discussed?

The need for the operation originally surfaced in an Ada-Comment discussion (now
filed in the AI). I think I originally proposed it, but a number of other people
vetted it. Bob created the AI version with those changes, including the new
operations, and posted in May 10, 2010. There was a discussion of that draft,
including by one Tucker Taft. We then discussed it at the June 2010 meeting. The
minutes for this AI of that meeting say:

  Reword A.18.32 to say "...except that the generic formal Element_Type is
  indefinite."

  A.18.30: Erhard asks what Minimum_Priority is. It is the parameter to the
  routine in question.

  Tucker thinks that the name Minimum_Priority is wrong since Before is ">".
  Call the parameter Low_Priority.

  The fact that the profiles of the routines differ from the interface is
  confusing. This is how Ada works, so there isn't much we   can do about it.
  But we can make it clear that these routines are overriding by adding
  overriding indicators. So, add overriding to   all of the operations that are
  overriding and not overriding to the others (Dequeue_Only_High_Priority).

  Approve AI with changes: 10-0-0.

[End extract of minutes]

Since this Tucker Taft person is the one that suggested the name change for the
parameter to Dequeue_Only_High_Priority, it seems pretty likely that you noticed
the operation. :-) I can imagine that you've since forgotten about it, and
perhaps didn't think about the implications too much at the time, but surely you
were aware of the operation at one time.

In any case, if you want to propose some other solution to the two use-cases
brought up in the e-mail threads, feel free to do so. There may be something
better out there -- but it better not introduce race conditions where there are
none in this proposal, or require using multiple queues.

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

From: Randy Brukardt
Sent: Tuesday, June 14, 2011  12:01 AM

...
> The semantics of the Deque_Only_High_Priority are also
> strange: the Low_Priority parameter specifies the priority just larger
> than what is considered a high priority.  So if I have this:
>
>    type Priority_Type is (High, Medium, Low);
>
> and I want to deque a high priority item, I have to say:
>
>    PQ.Deque_Only_High_Priority (Medium);
>
> This seems error-prone to me.

Your enumeration type is backwards, since High < Low (using predefined "<").
It doesn't surprise me that that leads to counterintuitive results.

Indeed, given that type, you *can't* dequeue only a High priority item.

So I'm not sure if there is a real problem here, or just a bad definition.
If there is a real problem, could you *please* offer a suggestion for a
definition that you think would be better? It's not obvious to me what you think
the problem is here.

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

From: Randy Brukardt
Sent: Tuesday, June 14, 2011  12:05 AM

...
> > I agree it seems a bit weird.  I presume we must have discussed it
> > during some ARG meeting, but I can't recall the discussion at all.
> > From the AI I can see where Randy suggested the idea in the e-mail,
> > but I wonder whether we ever reviewed it in an ARG meeting, and if
> > so what were our conclusions.

See my previous message.

> Let's review it at the coming meeting.

We can do that, but I'm dubious that we can fix the problems with this container
given the current state of Ada. Thus I know think that it would be much better
to delete this container now and try again next time when we presumably will
have fixed some of the underlying problems that prevent a decent design for it.
I don't think that freezing a bad design in stone just because it is the best we
can do today makes much sense.

Of course, we have to discuss *that* at the upcoming meeting.

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

From: Tucker Taft
Sent: Tuesday, June 14, 2011  9:18 AM

>>> There are variants of the queue packages that accept an indefinite
>>> element type. How does Dequeue work for an indefinite type?
>>
>> Excellent question.  It will be annoying if the caller has to predict
>> the constraints of the next item in the queue.  I suspect we should
>> eliminate the "indefinite" versions of this package, and require any
>> discriminants to have defaults.
>
> Given that the indefinite forms are by far the most important
> container forms (the definite forms are trivial to write yourself,
> especially for queues), I'd rather get rid of all of the queues in
> that case. Otherwise, we're saying that mixing OOP (such as T'Class)
> and task-safe operations is not possible, and that's a message that we
> never want to be sending (even if true).

Randy, you seem to have a bad case of "get rid of the baby with the bath water"
today.  These queues were originally designed for folks doing real-time stuff.
They don't use indefinite types all that much.  Telling them that we deleted
these features because we couldn't support indefinite types will get you a
definite "huh?" from them, I believe.

We now have these nice things called "holders", which can turn any indefinite
type into a definite type.  It seems a user could use a "holder" if they felt
desperate.  We can even provide a handy user NOTE pointing to holders as the
appropriate type to use if you really want a queue of indefinite objects.

>
> It's highly unfortunate that Ada really does not allow some thing like
> an entry function. Not everything can be modeled as an out parameter.
>
> I can't think of an alternative design that would work -- is it really
> true that it is impossible to have a blocking operation and return an
> indefinite object?

Holders seem sufficient.

>
>> By the way "Is_Synchronized" has become "Synchronization."
>
> I'll need to fix that, if we keep the queues.
>
>>> (2) The priority queues have an additional dequeue operation:
>>>
>>> not overriding
>>> entry Dequeue_Only_High_Priority
>>> (Low_Priority : in Queue_Priority;
>>> Element : out Queue_Interfaces.Element_Type);
>>>
>>>
>>> Suppose the priority queue is empty and there's a task waiting on
>>> each of Dequeue and Dequeue_Only_High_Priority. Does this AI say
>>> which waiting task gets priority, when an element is enqueued?
>>
>> That seems like a general queuing policy issue, and hopefully the
>> general queuing policy mechanisms are used.  E.g. if the
>> Priority_Queuing policy applies:
>>
>> When more than one condition of an entry_barrier of a protected
>> object becomes True, and more than one of the respective queues is
>> nonempty, the call with the highest priority is selected. If more
>> than one such call has the same priority, the call that is queued on
>> the entry whose declaration is first in textual order in the
>> protected_definition is selected.
>> For members of the same entry family, the one with the lower family
>> index is selected.
>>
>> As you suggest below, a requeue is probably required, so that makes
>> it hard to determine the textual order of the entry declaration,
>> since it will probably end up in the private part.  That is a further
>> argument for eliminating the need for a requeue by making
>> Low_Priority parameter into an entry family index (see below).
>>
>>> I'm having a bit of trouble with the entry barriers for the priority
>>> queues. I think Dequeue_Only_High_Priority must be implemented using
>>> some form of requeue statement (I don't think the Low_Priority
>>> parameter can be used in the entry barrier expression), and that got
>>> me thinking about the relative priorities of the dequeue entries.
>>
>> That argues for making the Low_Priority parameter into an entry
>> family index rather than leaving it as a parameter.
>
> Unfortunately, we can't do that, because protected interface
> operations (like this one) can never be implemented by an entry family.

But the entry family is not part of the protected interface.
The entry family is unique to the priority queue, which implements the queue
interface, but adds the Dequeue_Only_High_Priority operation.  So I think it
would work to make Priority into a formal discrete type and make this operation
into an entry family.

> It should be noted that the original proposal for protected interface
> operations included a mechanism to handle entry families, but it was
> considered "too complex" and dropped over my strong objections. A
> problem like this one was precisely the sort of thing I was worried about.
>
>> I will admit I never noticed this operation before.  At which ARG
>> meeting was it discussed?
>
> The need for the operation originally surfaced in an Ada-Comment
> discussion (now filed in the AI). I think I originally proposed it,
> but a number of other people vetted it. Bob created the AI version
> with those changes, including the new operations, and posted in May
> 10, 2010. There was a discussion of that draft, including by one
> Tucker Taft. We then discussed it at the June 2010 meeting. The minutes
> for this AI of that meeting say:
>
>    Reword A.18.32 to say "...except that the generic formal
> Element_Type is indefinite."
>
>    A.18.30: Erhard asks what Minimum_Priority is. It is the parameter
> to the routine in question.
>
>    Tucker thinks that the name Minimum_Priority is wrong since Before is ">".
> Call the parameter Low_Priority.

Given Matt's reasonable concern about the possible confusion, I think this
"Tucker" guy was wrong, and that we should change it back to "Minimum_Priority"
and say that it will ignore messages for which Minimum_Priority comes Before
their priority.

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

From: Edmond Schonberg
Sent: Tuesday, June 14, 2011  10:32 AM

> Given that the indefinite forms are by far the most important
> container forms (the definite forms are trivial to write yourself,
> especially for queues), I'd rather get rid of all of the queues in
> that case. Otherwise, we're saying that mixing OOP (such as T'Class)
> and task-safe operations is not possible, and that's a message that we
> never want to be sending (even if true).
>
> It's highly unfortunate that Ada really does not allow some thing like
> an entry function. Not everything can be modeled as an out parameter.
>
> I can't think of an alternative design that would work -- is it really
> true that it is impossible to have a blocking operation and return an
> indefinite object?

That's a little abrupt. It makes no sense to get rid of queues altogether for
this one issue.  At worst, people can do what they do in every other language,
and use access types. I know that one of the advantages of containers is to hide
storage management, but in this case it may be unavoidable, and it is certainly
the semantics that people would expect.  Maybe there is a chance for creative
use of our brand-new reference types here?  In any case, the queue container
should stay.

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

From: Randy Brukardt
Sent: Tuesday, June 14, 2011  5:06 PM

> > Given that the indefinite forms are by far the most important
> > container forms (the definite forms are trivial to write yourself,
> > especially for queues), I'd rather get rid of all of the queues in
> > that case. Otherwise, we're saying that mixing OOP (such as T'Class)
> > and task-safe operations is not possible, and that's a message that
> > we never want to be sending (even if true).
>
> Randy, you seem to have a bad case of "get rid of the baby with the
> bath water" today.

There is no baby. Perhaps there is a rubber ducky or two, but it is very unclear
whether those frills are worth putting in the language. (It should be noted that
I wrote the above under the presumption that we will have to do severe damage to
the priority queues in order to keep them, possibly to the point that I would
think that they are actively harmful -- if that turns out to not be true I would
reconsider.)

> These queues were originally
> designed for folks doing real-time stuff.  They don't use indefinite
> types all that much.  Telling them that we deleted these features
> because we couldn't support indefinite types will get you a definite
> "huh?" from them, I believe.

Folks doing "real-time stuff" are not going to use interfaces, nor are they
going to use some canned package with no timing guarantees. These packages are
not for them, but rather for the more causal programmer doing concurrency (like
me), to whom OOP is not a frill but a way of life.

> We now have these nice things called "holders", which can turn any
> indefinite type into a definite type.  It seems a user could use a
> "holder" if they felt desperate.  We can even provide a handy user
> NOTE pointing to holders as the appropriate type to use if you really
> want a queue of indefinite objects.

I thought of this last night after writing this message. But this is a horrible
kludge of a solution, and it seems terrible to me that this can only be done by
a user hack. If "holders" work so well, why isn't that folded into the
indefinite queue container? (The answer is that there doesn't appear to be a way
to do that -- again, this is a symptom of missing capabilities in Ada.)

...
> >>> I'm having a bit of trouble with the entry barriers for the
> >>> priority queues. I think Dequeue_Only_High_Priority must be
> >>> implemented using some form of requeue statement (I don't think
> >>> the Low_Priority parameter can be used in the entry barrier
> >>> expression), and that got me thinking about the relative priorities of the dequeue entries.
> >>
> >> That argues for making the Low_Priority parameter into an entry
> >> family index rather than leaving it as a parameter.
> >
> > Unfortunately, we can't do that, because protected interface
> > operations (like this one) can never be implemented by an entry
> > family.
>
> But the entry family is not part of the protected interface.
> The entry family is unique to the priority queue, which implements the
> queue interface, but adds the Dequeue_Only_High_Priority operation.
> So I think it would work to make Priority into a formal discrete type
> and make this operation into an entry family.

What? Don't we have a priority queue interface? That seems like a serious
omission (priority queues being far more useful than regular queues).

I also object because changing the Priority to discrete would mean that I could
not use the priority queues to write my delay queue. (That requires a time in
some form, which would be scalar or composite.)

...
> >    Tucker thinks that the name Minimum_Priority is wrong since
> > Before is ">".
> > Call the parameter Low_Priority.
>
> Given Matt's reasonable concern about the possible confusion, I think
> this "Tucker" guy was wrong, and that we should change it back to
> "Minimum_Priority"
> and say that it will ignore messages for which Minimum_Priority comes
> Before their priority.

That seems OK.

However, I still think that we are on shaky ground with these Queue containers.
With some language fixes, we could design *proper* containers that did not
suffer from these serious limitations (none are fatal by themselves, but the
full weight seems too much too me):

(1) No indefinite forms. As I've previously said, the indefinite forms (and the
associated memory management) is the number 1 (and 2 and 3) value of these
containers. I don't believe that there is much value to the containers
themselves (with the possible exception of the Maps) because they are easy to
write yourself, and the hand-written version is easier to read and write and/or
far more efficient. (This is the same as with the unbounded strings -- the ONLY
reason to use unbounded strings is for the memory management, they're far too
inconvenient otherwise.)

Using a holder container as an intermediary is a hack at best, and it does
nothing to make OOP more useful with blocking operations. (Indeed, the holder
container itself is a hack!)

(2) The inability to hide the implementation of the queues. The package
Implementation is far beyond a hack -- it's an ugly representation of a serious
Ada flaw. Moreover, it's clear (at least if I didn't make any mistakes in my
analysis) that there is really no major problem to allowing the declaration of
non-tagged types in the private part of a protected type. (The problems of
nested types don't really show up here, as these types are not visible to anyone
other than the protected body, and that acts more like a unit than a type.)
There might not be much of a problem with tagged types, either, but the analysis
is harder for them and I didn't try. (What generally is needed is an array of
elements, a node type of some sort, and/or an access to a node or element.)

It would be far better to bite the bullet and fix this long-standing Ada problem
properly rather than expose this serious flaw and worse yet encase it in amber.

(3) The priority queues seem like a mess. We seem to be missing a priority queue
interface, meaning that it isn't possible to write code that works with any
priority queue (only). (I don't find the interface particularly useful, but
presuming we think it is useful enough to define, it is odd to then make its
utility very limited.) Tucker is proposing changes that make my primary use case
(a delay queue) impossible (and as a side-effect, is also making a priority
queue interface impossible). Without those changes, we seem to have issues with
operation ordering; with those changes, we have a far less useful container.
Maybe there is a solution here, but I fail to see it. Given that the priority
queues are far more important than the "regular" queues (the regular queues are
trivial to write in terms of a list instance), this is a very bad sign.

This is death from a thousand cuts to me. The only thing that we are sure we
have right is the "regular" definite queue, which is so trivial to write that it
can be done in under a minute (for a non-tasking version - its an instantiation
and two renames) and in 3-4 minutes (for a tasking version - the extra time is
to write the declarations making a protected object wrapper). And even it
suffers from (2).

It is too late in the process to really fix these issues, so I think we have to
vote to remove this from Ada 2012, so we can do it right in the future. That
probably would take language changes (for (3), improvements to interfaces/entry
families and relaxing the discrete restriction on entry families of protected
types; for the other two, I mentioned them previously.)

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

From: Tucker Taft
Sent: Tuesday, June 14, 2011  7:09 PM

I think you are being overly pessimistic.
Priority queues are very useful, and are a pain to write, so I see no reason to
drop this.  I really see almost no need for a priority queue of indefinite
items, so I fail to see why that should cause the priority queue to be dropped.

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

From: Randy Brukardt
Sent: Tuesday, June 14, 2011  8:23 PM

> I think you are being overly pessimistic.
> Priority queues are very useful, and are a pain to write, so I see no
> reason to drop this.  I really see almost no need for a priority queue
> of indefinite items, so I fail to see why that should cause the
> priority queue to be dropped.

That's not remotely close to what I said. If you want to argue straw men, that's
OK but it won't help the discourse any. Otherwise, please actually respond to
what I said.

Specifically, I said that there were three separate issues with the design of
the queue containers; none of those issues by themselves were enough to kill
them, but taken together I can no longer support having them in the language.

The problem with the priority queues has nothing to do with the indefinite
items, and in fact the queues as they currently are defined would be OK -- but
the changes you have proposed would make them unusable for many of the use cases
I have (and that's completely independent of indefinite elements). In
particular, making the priority discrete is very damaging in my view. Also,
using entry families would prevent anyone from defining a priority queue
interface, which seems bad if you grant that interfaces are useful at all.

There is much more detail in my previous message. Maybe too much so, but I
wanted to lay out the case as I saw it in detail.

Note that those "Implementation" packages make me nauseous -- they are as far
from good Ada design as you can get. I was already on the fence about these
packages for that reason (recall that my first reaction to the problem that
required introducing those was to drop the Queues -- nothing whatsoever has
changed in my mind on that). I really can only accept them if the rest of the
design is near perfect, and it is now clear that is far from the case.

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

From: Edmond Schonberg
Sent: Friday, June 24, 2011  12:39 PM

Modifed wording for queues [from an ARG subgroup]:

procedure Dequeue_Only_High_Priority
   (Higher_Than : in Queue_Priority;
    Element : in out Queue_Interfaces.Element_Type;
    Success : out Boolean);
...
if the queue is non-empty and the element E at the of the queue satisfies
Before (Get_Priority (E), Higher_Than) then E is removed from the queue and
assigned to Element, and Success is set to True; otherwise Success is set to
False and Element is unchanged.

...

Note:  unlike other language-defined containers, there are no queues whose element types
are indefinite. Indefinite types can be catered for by using a holder container
(see A.18.18)  or by using explicit access types.

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

From: Tucker Taft
Sent: Saturday, June 25, 2011  3:38 AM

Unfortunately, "Not_Before" doesn't work.

procedure Dequeue_Only_High_Priority
   (At_Least : in Queue_Priority;
    Element : in out Queue_Interfaces.Element_Type;
    Success : out Boolean);

...
if the queue is non-empty and the function Before(At_Least, Get_Priority(E)) returns False,
where E is the head of the queue, then E is removed from the queue and assigned to Element,
and Success is set to True; otherwise Success is set to False and Element is unchanged.

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

Questions? Ask the ACAA Technical Agent