Version 1.1 of ai05s/ai05-0030-2.txt

Unformatted version of ai05s/ai05-0030-2.txt version 1.1
Other versions for file ai05s/ai05-0030-2.txt

!standard 9.5.4(3)          08-01-04 AI05-0030-2/01
!class Binding Interpretation 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 if an appropriate pragma is provided.
!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 provided that the pragma Implemented specifies that the procedure is implemented by an entry.
!wording
Add after 9.5(9)
Syntax
The form of a pragma Implemented is as follows
pragma Implemented(procedure_local_name, implementation_kind); implementation_kind ::= By_Entry | By_Protected_Procedure | By_Any
Legality Rules
The procedure_local_name of a pragma Implemented shall denote a dispatching operation of a synchronized interface. The dispatching operation shall not be a function.
A pragma Implemented with implementation_kind By_Protected shall not be applied to a dispatching operation of a task interface.
Static Semantics
An operation for which the implementation_kind is specified as By_Entry shall be implemented by an entry. An operation for which the implementation_kind is specified as By_Protected_Procedure shall be implemented by a protected procedure.
If a dispatching operation overrides an inherited operation to which a pragma Implemented applies then any pragma Implemented applied to the overriding operation shall not conflict with regard to the implementation_kind. Both implementation_kinds shall be the same or the inherited implementation_kind shall be By_Any. If an overriding operation does not have a pragma Implemented then any pragma Implemented applying to the inherited operation shall apply to the overriding operation.
NOTE
18 The implementation_kinds By_Protected_Procedure and By_Any may be used
as documentation aids.
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, the first parameter of the unprefixed view of the primitive subprogram shall be a controlling parameter, and the pragma Implement with implementation_kind By_Entry shall apply to the primitive subprogram.
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] {target procedure or }entry named in the requeue_statement has parameters, then during the execution of an accept_statement or entry_body corresponding to a new entry ...
Annex L (pragmas) will need updating as well.
!discussion
A previous version of this AI (0030-1) regarding this problem permitted the requeue syntactically and then had to resolve what would happen if the target turned out to be implemented by a procedure and not by an entry. This introduced bounded errora and looked difficult to implement.
Accordingly, this version takes a more syntactic view. We need to ensure that the requeue will always turn out to be on an entry and not on a procedure or protected procedure.
Ideally, this should be done by new syntax which introduces entry into the profile of the interface. For example
type Server is synchronized interface; entry Q(S: in out Server; X: Item);
However, this approach could not be classed as a binding interpretation but would have to be an Amendment.
Accordingly a pragma is proposed which can be used thus
type Server is synchronized interface; procedure Q(S: in out Server; X: Item); pragma Implemented(Q, By_Entry);
For completeness, the pragma can also take parameters, By_Protected_Procedure or By_Any. By_Protected_Procedure means that it has to be implemented by a protected procedure and By_Any means it can be implemented by a normal procedure, a protected procedure or by an entry (these might be useful documentation aids). In particular, if it is known that an operation is implemented by a protected procedure then it can be deduced that the operation will not block under normal circumstances (eg on a monoprocessor).
The pragma can also be applied to task and protected interfaces. In the former case By_Protected_Procedure is not permitted.
If an interface inherits an operation from another interface and the inherited operation is subject to a pragma Implemented then that property is inherited. It can be specified again but must not conflict. By_Any can be overridden by By_Entry or By_Protected_Procedure but in other cases the parameter must match. And of course a task interface cannot inherit operations to which By_Protected_Procedure applies.
For example if we have
type Server is synchronized interface; procedure Q(S: in out Server; X: Item); pragma Implemented(Q, By_Protected_Procedure);
then it is illegal to write
type T_Server is task interface and Server; -- illegal
Since it is statically determined we now permit a requeue on an entry renamed as a procedure.
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?  

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


Questions? Ask the ACAA Technical Agent