!standard  9.5.4(3)                                   07-09-27    AI05-0030-1/02
!class Amendment 06-10-13
!status work item 06-10-13
!status received 06-10-13
!priority Medium
!difficulty medium
!subject Requeue on synchronized interfaces

!summary

Requeue is permitted to a synchronized, task, or protected interface. It
is a bounded error if the actual target procedure is not implemented as
an entry.

!problem

The inability to requeue to a synchronized, task or protected interface
is a serious drawback when trying to produce general-purpose real-time
utilities. Its inclusion would further the integration of the
OO and concurrency features of the language. 

!proposal

The proposal is to allow requeue to procedures defined in synchronized,
task, or protected interfaces. If it turns out that the target procedure
is not implemented as an entry then it is a bounded error. Possible
consequences of the bounded error are

*  Program_Error is raised at the point of the requeue, or

*  if the procedure is implemented as a protected procedure, then
   it behaves as if the procedure were an entry with a True barrier, or

*  if the procedure is implemented as a normal procedure, then after
   leaving the enclosing callable context, the procedure is executed.


!wording

Change 9.5.4(2-5) to

   requeue_statement ::= requeue *procedure_or_entry_*name [with abort];

          Name Resolution Rules

The *procedure_or_entry_*name of a requeue_statement shall resolve to
denote a procedure or an entry (the target procedure or entry). In the
case of an entry, the entry shall have a profile that has no parameters,
or that is type conformant (see 6.3.1) with the profile of the innermost
enclosing entry_body or accept_statement. In the case of a procedure,
the name shall denote a rename of an entry whose profile satisfies the
above requirement, or shall denote a prefixed view of a primitive 
subprogram of a synchronized interface where the profile of the prefixed 
view satisfies the above requirement, and the first parameter of the 
unprefixed view of the primitive subprogram shall be a controlling 
parameter.

           Legality rules

A requeue_statement shall be within a callable construct that is 
either an entry_body or an accept_statement, and this construct shall 
be the innermost enclosing body or callable construct.

If the target procedure (view) or entry has parameters, then its 
profile shall be subtype conformant with the profile of the innermost 
enclosing callable construct.

Modify 9.5.4(7) as follows

The execution of a requeue_statement proceeds by first evaluating the
[*entry_*name]{*procedure_or_entry_*name} ...

Modify 9.5.4(12) as follows

If the new {procedure or }entry named in the requeue_statement has 
parameters, then during the execution of [the]{an} accept_statement 
or entry_body corresponding to [the]{a} new entry ...

Add after 9.5.4(16)

                Bounded (Run-Time) Errors

It is a bounded error to requeue to an interface procedure not 
implemented as an entry. Program_Error is raised at the point of the
requeue if the error is detected by the implementation; otherwise, if 
the procedure is implemented by a protected procedure then the requeue 
statement behaves as if the procedure were an entry whose barrier is 
True, and if the procedure is not a protected procedure then, after 
leaving the enclosing callable context, the procedure is executed. In 
both cases of implementation by a procedure, the formal parameters 
denote the same objects as the corresponding formal parameters of the 
original call.


!discussion

The key problem to be resolved is what should happen if the target turns 
out to be implemented as a subprogram and not as an entry.

There are three possible situations.

1) The target is a function inside or outside a protected object -
this is an error condition that can be caught at compile time;
there are no circumstances whereby a function in an interface
can be implemented by an entry. This is similar to the illegal case
where a function call is used as the target of a timed/conditional
entry call or as a triggering event in a select-then-abort statement.

2) The target is a procedure inside a protected object - this is similar
to the case where the target of a timed/conditional entry call or
select-then-abort triggering event turns out to be a procedure that has
been implemented inside of a protected type implementing the associated
interface. The corresponding interpretation might be to view the procedure
as an entry with a True barrier. 

3) The target is a regular procedure (i.e. outside a protected 
object/task) -this is similar to the case where the target of a 
timed/conditional entry call or select-then-abort triggering event 
turns out to be a procedure outside of the protected object/tasks 
implementing the associated interface. As this would succeed in this 
case, so should it succeed in the requeue case. However, to execute 
the procedure immediately would mean that the procedure would
be executed at the ceiling priority of the original protected type 
(or the priority of the original rendezvous). This would seem to be 
wrong. Hence, the accept statement or entry code body of the calling 
task or protected object should be "completed, finalized and left" 
(ARM, Section 9.5.4) and then the procedure called with the priority 
of the original thread.

The difference between 2) and 3) is the observed order of execution 
in certain circumstances. Consider a protected object PO from which a
requeue occurs; the PO also has a blocked entry that is now open 
(as the task leaves the PO) - this will allow the entry E1 to execute. 
If the requeue were to another protected entry, E2, that is open (or to a 
protected procedure) then E2 would execute before E1 as the target 
protected object has a higher or equal priority. However if the target 
were an ordinary procedure, P, then E1 would execute before P.

To cater for this circumstance the run-time would have to deal with 
ordinary procedures in a different way - they could not be executed by
another thread on behalf of the caller - the genuine caller thread 
(without an inherited priority) should execute the procedure.

However, it was concluded that it would be too much of an 
implementation burden to insist on this and accordingly it was 
decided that it is a bounded error to requeue to a non-entry.

Of course, where the programmer knows that the intended target is 
an entry, ideally there should be a mechanism to indicate this 
(perhaps by a pragma). This would allow the compiler to check, 
thereby avoiding the bounded error. Such a possibility has been 
left for possible further consideration in another AI in the 
future. (Javier Miranda has indicated that he is prepared
to develop a prototype implementation to evaluate the impact of 
such a proposal.)

When discussed at the IRTAW the need to requeue via interface 
procedures implemented by entries was strongly supported. However 
there was no wish to have requeue to a procedure so the proposal 
of this present AI covers the perceived need.

!example

See the paper 'Integrating OOP and Tasking - the missing requeue' by
Wellings and Burns (IRTAW2007), previously circulated. Find it at
http://www.ada-auth.org/ai-files/grab_bag/requeue.pdf.

!corrigendum

!ACATS test

Create an ACATS test to check that the above changes work.

!appendix

From: Alan Burns
Sent: Friday, October 13, 2006  5:54 AM

Andy and I have been developing some real-time 'patters' for common
idioms; for example periodic tasks with deadline overrun detection and
budget rationing. We can do this in quite an abstract way by the use of
task, protected and synchronized interfaces. However, we have come
across a couple of situations where we want to requeue to another entity
and the inability to 'requeue to a procedure' has impacted on the expressive
power of what we are trying to do.

When task, protected and synchronized interfaces were introduced the
provision was made to be able to make a timed call on an interface 
procedure.
I believe it was a simple omission for Ada 2005 to fail to allow requeues on
interface procedures. Is there anyway of putting this omission right?

The language rules would seem to be straightforward - if the 'procedure'
was not implemented as an entry then an exception should be raised
at the point of the requeue.

To give a simple example:
Given:

type Server is synchronized interface;
procedure Register(S: in out Server) is abstract;
type Any_Server is access all Server'Class;

We now define:
protected type X(S : Any_Server) is
 entry Y;
end X;

protected body X is
 entry Y when True is
 begin
      requeue S.Register;
 end
end X;

You know that S must be a task or a PO.
Consequently, this would seem to us to be
a valid thing you would want to do (ie requeue
to S.Register).

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

From: Pascal Leroy
Sent: Friday, October 13, 2006 6:26 AM

> The language rules would seem to be straightforward - if the 
> 'procedure' was not implemented as an entry then an exception 
> should be raised at the point of the requeue.

Is there any reason why you want to raise an exception in this case?  In
all the other cases where some "procedure" may or may not be an entry we
defined some reasonable semantics that doesn't involve exceptions.  Why
would requeue be different?  My concern is that users would have to handle
predefined exceptions in order to prevent their code from dying if the
procedure is not implemented by an entry.  This doesn't seem right.

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

From: Tucker Taft
Sent: Friday, October 13, 2006  7:25 AM

One of the issues with requeue is that the semantics are
relatively tightly tied to there actually being a queue
on which to place the entry call, since the requeue may
be executed by an entry body that is being run on some
"convenient" thread.  You probably wouldn't want to
allow the requeue to involve invoking synchronously
an arbitrarily complicated procedure with possibly
multiple nested blocking actions.  That works OK
at an original call point, but for a requeue, it
would not work in any straightforward way.  Requeue
pretty explicitly specifies the presence of a queue,
and if there isn't one, raising an exception seems
like about the only recourse.

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

From: Alan Burns
Sent: Friday, October 13, 2006  7:57 AM

Yes this was our conclusion, fundamental to requeue is that control
passes from the current context. When the entry is completed, control
does not return to the point of the requeue, so executing the procedure and
returning does not seem right. An exception seems like the right action
as tuck says

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

From: Pascal Leroy
Sent: Friday, October 13, 2006  7:44 AM

I understand, but given that (1) we are not capable of defining proper
semantics in the case where the procedure is not an entry and (2) we have
no way to specify on the interface that the procedure has to be
implemented by an entry, I conclude that the entire idea is a bad
violation of the Substitution Principle and that it is a good thing that
requeue-through-interfaces are disallowed.

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

From: Tucker Taft
Sent: Friday, October 13, 2006  8:56 AM

I was concerned about the same thing, and so I was very
interested in seeing realistic examples.  I believe that
Alan and Andy came up with several.  Once you start using
polymorphism with tasking, it seems inevitable that if
you do an "external" requeue, you will want to be able
to do it through an interface.

Perhaps we need some way of requiring
a procedure to be implemented by an entry?
We could make it an optional pragma (analogous to pragma
Convention) which if absent, leaves open the possibility
of a run-time exception, but if present, ensures that no
run-time exception would occur at the point of requeue.
Adding new syntax is of course a possibility, but then
this no longer looks like a "binding interpretation"
style of AI, but rather clearly an amendment.

Alternatively, we figure out a way to implement this
by treating a procedure as equivalent to an entry with
a "true" barrier, and have a pseudo "queue" created
as needed upon invocation of the requeue.  This latter
approach seems to require more implementation work
and more tricky wording.

My conclusion was that there *was* an oversight in this
area, and the "simple" solution of raising an exception
would be sufficient for a quick fix, but that next
time we get into "amendment" mode, we could work out a
more sophisticated model, while remaining effectively
compatible with this simple exception-raising approach.
Admittedly not ideal, but I hate to "orphan" requeue
as we move into a polymorphic synchronization world.

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

From: Pascal Leroy
Sent: Friday, October 13, 2006  9:49 AM

> I was concerned about the same thing, and so I was very 
> interested in seeing realistic examples.  I believe that Alan 
> and Andy came up with several.  Once you start using 
> polymorphism with tasking, it seems inevitable that if you do 
> an "external" requeue, you will want to be able to do it 
> through an interface.

I would certainly like to see realistic examples, if Alan is willing to
share them with the rest of us.

> Perhaps we need some way of requiring
> a procedure to be implemented by an entry?

That might be a nice extension in the future, but I think we first want to
see synchronized interfaces used in real life.  And we are not in
amendment mode anymore.

> Alternatively, we figure out a way to implement this
> by treating a procedure as equivalent to an entry with
> a "true" barrier, and have a pseudo "queue" created
> as needed upon invocation of the requeue.  This latter
> approach seems to require more implementation work
> and more tricky wording.

I still don't understand what would be wrong with the following: if the
procedure is not an entry, the requeue statement calls the procedure, and
when the procedure returns it immediately leaves the enclosing accept
statement or entry body.  True, the procedure called that way could do all
sorts of nasty things like potentially blocking operations, but this is a
general danger with dispatching calls.  At least with such a scheme the
user could give a reasonable semantics to the call if they so desire (or
they could raise an exception in the classes that don't implement the
procedure as an entry).

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

From: Tucker Taft
Sent: Friday, October 13, 2006  9:58 AM

Another way to view this requeue restriction would be to think of it as
similar to the rules that forbid calling a potentially
blocking operation from inside a protected operation.  I.e.:

   If you *call* a procedure through a synchronized
   interface from inside a protected operation, if
   the procedure turns out to be implemented (directly
   or indirectly) via an entry, then that would be
   violating the no-potentially-blocking rules.  If you
   *requeue* on a procedure through a synchronized
   interface then you would get an exception if it
   is *not* an implemented by an entry.

There seems a pretty close analogy, where you have
to have some knowledge of how the procedure of
a synchronized interface is implemented to know whether
to call or to requeue.  If you are wrong in either
way, you could get Program_Error at the point of the
call/requeue.

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

From: Tucker Taft
Sent: Friday, October 13, 2006  10:05 AM

> I still don't understand what would be wrong with the following: if the
> procedure is not an entry, the requeue statement calls the procedure, and
> when the procedure returns it immediately leaves the enclosing accept
> statement or entry body.  True, the procedure called that way could do all
> sorts of nasty things like potentially blocking operations, but this is a
> general danger with dispatching calls.  At least with such a scheme the
> user could give a reasonable semantics to the call if they so desire (or
> they could raise an exception in the classes that don't implement the
> procedure as an entry).

Those semantics don't seem too bad to me.  As you say, if the
procedure involves a blocking operation, you are in trouble
and will possibly get a Program_Error
If it doesn't, then you are OK.

But I also think my message that crossed in the
e-mail with yours provides some justification
for raising Program_Error at the requeue point.

I could go either way.  If we do want it to "work"
when requeuing on a procedure, I agree yours is the
more straightforward implementation model.

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

From: Alan Burns
Sent: Friday, October 13, 2006 11:49 AM

Andy and I can produce some examples - but not immediately
as I am about to go off traveling for a week, by which time
I'm sure Pascal and Tuck will have agreed on the right language
model! We were concerned with the implementation overhead
of anything other than raising an exception.

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

From: Robert A. Duff
Sent: Friday, October 13, 2006  3:41 AM

A protected procedure is a lot like an entry with an always-True barrier.
Therefore, I agree with the following:

> I still don't understand what would be wrong with the following: if the
> procedure is not an entry, the requeue statement calls the procedure, and
> when the procedure returns it immediately leaves the enclosing accept
> statement or entry body.

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

From: Randy Brukardt
Sent: Friday, October 13, 2006  6:25 PM

Alan Burns wrote:

...
> When task, protected and synchronized interfaces were introduced the
> provision was made to be able to make a timed call on an interface
> procedure. I believe it was a simple omission for Ada 2005 to fail
> to allow requeues on interface procedures. Is there anyway of putting
> this omission right?

I don't want to comment on whether or not it is a good idea, but this was
not "a simple omission". We specifically considered whether we wanted to
allow requeue at the Paris meeting (Feb. 2005), and rejected the idea. The
minutes of that meeting say (under AI-397):

"Steve Baird asks if you can requeue on a synchronized procedure. No, we
don't allow that, because the synchronized procedure doesn't necessarily
denote an entry. And what such a requeue would do if the procedure wasn't
an entry is rather unclear."

(My memory was that there was more issues beyond the one recorded, but since
I don't remember any details, at this point that would be just FUD.)

I can imagine that new information could make it worthwhile to make a
different decision on requeue, but not having it was certainly *not* an
omission. It was completely intentional. As such, I think we would have to
classify this as an Amendment (I don't think "we changed our mind" is a
legitimate reason to classify something as a bug)!

Personally, I think requeueing to a procedure makes no sense at all, and
thus Program_Error seems to be appropriate. It is already devilishly hard to
implement (external) requeue, and this will be worse -- I don't see much
reason to try hard to make useless cases work.

I'd like to see a real example, too. Not that I doubt that Alan has one, but
it would be valuable to get it on the record and try to judge its
importance. Especially if we want to lie about this being a bug -- in that
case, I think it had better be quite important.

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

From: Alan Burns
Sent: Tuesday, November 14, 2006  2:32 AM

I note the following on the agenda.

>Requeue on synchronized interfaces [AI not made yet.]

After I raised this point about requeue on interfaces Randy noted that 
this was not an 'omission' but a clear decision at some meeting or other
not to allow requeue. Hence I assume the issue is closed. However if the
ARG is at least open to consider this topic I will produce an AI for a
future meeting.

If the current meeting has time to at least decide if such an AI is 'in 
scope' I would appreciate it.

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

From: John Barnes
Sent: Wednesday, November 22, 2006  2:01 AM

It was suggested at the meeting last weekend that the topic should be
considerd by the next IRTAW in Vermont and then reported back to the ARG in
Geneva.

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

From: Alan Burns
Sent: Wednesday, May 2, 2007  3:49 AM

Re AI05-0030 - requeue on synchronized interfaces

I understand that the ARG asked the IRTAW to look at the
issue of allowing, in some form, requeue via procedures
defined in synchronized (and task and protected) interfaces.

The workshop discussed this at length, following a position
paper from Wellings and Burns that contained an example of
usage (I can email this paper to the ARG if you wish).
The workshop adopted the following position

1. That requeue through synchronized interfaces is a useful primitive and
should be supported in Ada. It furthers the integration of the
OO and concurrency features of the language.

2. That requeue and the other (existing) 2005 features such as making
a timed entry call on a synchronized interface procedure should be
dealt with in the same way.

3. That a static scheme in which a procedure is identified as
being 'implemented as an entry' is an acceptable solution.
If the term 'entry' cannot be introduced into an interface
definition then the use of a pragma to identify a procedure that must be
implemented as an entry is a possible scheme.

4. That it is possible to define the semantics for requeue to a
procedure but that the implementation cost of such a model
on existing run-times be investigated.

In conclusion, the workshop favoured a static approach that only
allowed requeue on procedures implemented as entries (point 3)
and that the definition of timed entry calls etc should be changed
to be similarly restricted. If however the existing definitions were
to remain then requeue should be allowed on 'entries' and 'procedures'
if the implementation (run-time) overhead is not prohibitive.

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

From: Pascal Leroy
Sent: Wednesday, May 2, 2007  5:00 AM

> The workshop discussed this at length, following a position 
> paper from Wellings and Burns that contained an example of 
> usage (I can email this paper to the ARG if you wish).

This would be a useful thing to do, Alan.  At the last meeting we briefly
discussed this topic, but since nobody other than Tuck had seen an example
of usage, it was hard to make progress.

> In conclusion, the workshop favoured a static approach that 
> only allowed requeue on procedures implemented as entries 
> (point 3) and that the definition of timed entry calls etc 
> should be changed to be similarly restricted.

Keep in mind that we are no longer in Amendment mode, and that we have to
worry about compatibility.  We can compromise compatibility to fix
language holes, but we are no allowed to just change our mind.  If you
want to restrict timed entry calls, you'll have make a strong case that it
was a blunder to allow them in the first place.  

> If however the 
> existing definitions were to remain then requeue should be 
> allowed on 'entries' and 'procedures' if the implementation 
> (run-time) overhead is not prohibitive.

It would be good to explain to us what the semantics should be if we allow
requeueing to a procedure.

I suppose that you are going to update the AI and answer these questions
and more, right?

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

From: Alan Burns
Sent: Friday, May 4, 2007  3:03 AM

Attached is the paper from Andy and I on requeue. It does discuss what the semantics
for requeue to a procedure could be (there will also be more detail in the IRTAW
session summary to be published soon). [Editor's note: the paper can be found in the
ARG grab bag at http://www.ada-auth.org/ai-files/grab_bag/requeue.pdf.]

As the IRTAW is not the ARG, it felt it should express the ideal situation (ie requeue and
timed entry calls dealt with in an identical way), the ARG can/will obvious see what this
means in terms of the Ada 'process'.

You asked me to update the AI - as we do not have a specific recommendation how should
this be done? Shall I just add a report?

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

From: Randy Brukardt
Sent: Friday, May 4, 2007  8:03 PM

It's ultimately Pascal's call, but I think you should write up a *complete* proposal
of what you think the ideal solution is. (Complete means including at least a
determination of where wording changes will be needed.) Then we (the ARG) can
decide if/when it can be implemented and any modifications. (In particular, if
it is too large for a Corrigendum change and if it is too incompatible.)

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

From: Alan Burns
Sent: Monday, May 7, 2007  3:13 AM

I'll await Pascal's advice, but I would rather have a discussion at the 
ARG that decides on the 'best way forward', which I can then write up as
an AI. If I  write one now the first minute of discussion will open up
all the issues anyway. Also there are procedural as well as technical issues
that I am not fully conversant with.

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

From: Pascal Leroy
Sent: Monday, May 7, 2007  3:46 AM

I agree with Randy: we cannot discuss this topic in a vacuum, we need an
AI on the table.  On the face of it what you propose in your paper seems
to make sense, but in order to evaluate the impact on the language and on
implementations, we need an AI with a fairly detailed description of what
changes are needed where.

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

From: Alan Burns
Sent: Monday, May 7, 2007  7:36 AM

OK, but our paper (and the subsequent discussion at IRTAW) did not really
propose a complete solution, but it did strongly noted that:

The workshop would wish to see Ada support requeue to a synchronized procedure
implemented as an entry - but this leaves two big issues

1) How to make this 'change' to Ada, ie can it be done now or must it wait
   until 2015?
2) What should happen if the synchronized procedure is not implemented 
   as an entry; this is needed to complete the definition - there are three
   possibilities
  a) statically prevent via some language rule - or the use of a pragma
  b) define it to be an error giving rise to an exception at run-time
  c) allow and define what the semantics are.
  The workshop's priority order was a), c) then b)

The workshop also thought it desirable (though not essential) for timed 
entry calls and ATCs to be dealt with in the same way as requeue.

These two issues are linked (a solution now might be different from the solution
for 2015), so I feel the ARG needs to decide what sort of solution (if any) it is 
prepared to consider and how this would result in a language change. Perhaps
some email discussion would help define what is possible - I could then write
up the AI.

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

From: Pascal Leroy
Sent: Monday, May 7, 2007  9:39 AM

> 1) How to make this 'change' to Ada, ie can it be done now or must it 
> wait until 2015?

It seems to me that we should at least consider making the change now.
Otherwise there is no point in even discussing the issue until some time
in 2014.  It may turn out that we collectively decide that the change
would be too big or that the language is insufficiently broken, but I am
in favor of at least having a discussion.  We must all keep in mind that
we are in Corrigendum mode, though.

> 2) What should happen if the synchronized procedure is not 
> implemented 
> as an entry;
> this is needed to complete the definition - there are three 
> possibilities
> a) statically prevent via some language rule - or the use of a pragma
> b) define it to be an error giving rise to an exception at run-time
> c) allow and define what the semantics are.
> The workshop's priority order was a), c) then b)

My own feeling (which may not be shared by the rest of the ARG) is that
(a) is either going to be too big (requiring new syntax and many new
rules) or ugly (violating the rules of good taste for pragmas).  The three
rules that you mention in section 4 of your paper appear to correspond to
(c), and I'd say that we should at least give it a shot.  The alternative
(b) looks very inconsistent with what we decided (for better or for worse)
to do for timed entry calls and the like.

So I suggest writing up the AI using approach (c).

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

From: Robert I. Eachus
Sent: Monday, May 7, 2007  1:45 PM

I agree.  As I see it, option (c) may take some work by implementors, 
but it should be relatively minor, compared to the other options.  I 
wrote about a page of detailed analysis, then deleted it as irrelevant.  
I realized that any concern about difficultly can be reduced to one 
case.  For the purpose of requeue, you may want to call a procedure of 
another protected object.  If you can't use requeue, in that case, it 
makes deadlock avoidance harder.  Sure you can modify the protected 
object to have an entry similar to the current procedure, but have fun 
trying to fix the semantics to get the same queuing behavior. So there 
is a real, if accidental, hole here.

What about requeuing on a procedure that really actually is a procedure, 
and not part of a protected object?  I suspect that the right fix is to 
change 9.5.4 (3) so that /entry/_name is defined as an entry name, a 
procedure of a protected object, or a procedure from a task, protected 
or interface type.  You should probably change /entry/_name as well, 
here and in the paragraph above to /procedure_or_entry/_call and copy 
the static semantics paragraph at 9.7.2(3.3/2).

Oh, there is one other detail, but I hope not a big one.  What happens 
if a requeue is made to a dispatching procedure of an interface type?  
The actual type is not required to be an entry, or a subprogram of a 
protected type.  What do compilers do now for other entry calls to such 
procedures?  Should this be fixed in 3.9.4 and if so how?  Is this 
another AI?  

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