Version 1.2 of ais/ai-00096.txt

Unformatted version of ais/ai-00096.txt version 1.2
Other versions for file ais/ai-00096.txt

!standard 05.04 (00)          98-06-12 AI95-00096/02
!class confirmation 95-09-29
!status WG9 approved 98-06-12
!status ARG Approved 11-0-0 97-11-14
!status work item 95-10-12
!status received 95-09-29
!priority Low
!difficulty Easy
!subject sparse case statements
!summary 95-09-29
Implementations must support sparse case statements.
!question 95-09-29
1.1.3 says:
1 A conforming implementation shall:
2 Translate and correctly execute legal programs written in Ada,
provided that they are not so large as to exceed the capacity of the implementation;
... 6 Contain no variations except those explicitly permitted by this
International Standard, or those that are impossible or impractical to avoid given the implementation's execution environment;
Does this imply that an implementation need not support sparse case statements -- that is, case statements that, if implemented as a jump table, would not fit in the available memory?
!response 95-09-29
In order to avoid implementing sparse case_statements by 1.1.3(2,6), an implementer would have to argue that such case_statements are too "large", or are "impossible or impractical" to implement. Since many compilers for many languages have implemented sparse case statements, such an argument would not be correct. Thus an implementation must support sparse case statements. An implementation that chooses to implement all case statements using a jump table is incorrect.
!appendix

!section RM-5.4(00)
!subject sparse case statements
!reference RM95-5.4
!reference RM95-1.1.3(2)
!reference 94-4309.a Dan Eilers  94-5-24
!from Dan Eilers 95-09-19
!reference as: 95-5297.a Dan Eilers  95-9-19>>
!discussion
Are implementations required to support arbitrarily sparse case statements?

There was no support at the time for mrtcomment 94-4309.a:

> The ACVC goes beyond the RM in enforcing an implementation requirement
> that arbitrarily sparse case statements are supported, including:
>    when integer'first | integer'last => ...
>
> It seems appropriate to state such an implementation requirement
> in RM9X as well.

However, despite the decision not to include such an implementation
requirement in RM 5.4, and the permission in 1.1.3(2) to reject
programs that exceed the implementation's capacity, there is significant
opposition on the acvc review group to the following proposal to remove
these ACVC tests:

> -- CHECK THAT A  CASE_STATEMENT  CORRECTLY HANDLES A SPARSE SET OF
> --    POTENTIAL VALUES (OF TYPE INTEGER) IN A LARGE RANGE.
>
> Consistent with the removal of other capacity/invalid-goal
> tests from 9X-Basic, the tests for arbitrarily sparse case
> statements spanning integer'first..integer'last should be removed.
> These are: c54a42{a,c,d,g}.ada.
>
> Such capacity tests should be turned over to the ACES developers
> for consideration as evaluation tests.

Note:  these tests are not boundary tests checking that integer'first
or integer'last are allowed, but are tests to ensure that both
integer'first and integer'last are allowed in the same case statement,
causing implementations using a jump table to exceed memory capacity.

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

!section 5.4(00)
!subject sparse case statements
!reference RM95-5.4
!reference RM95-1.1.3(2)
!reference 94-4309.a Dan Eilers  94-5-24
!reference 95-5297.a Dan Eilers  95-9-19
!from Erhard Ploedereder
!reference as: 95-5312.a Erhard Ploedereder  95-10-5>>
!discussion

> Are implementations required to support arbitrarily sparse case
> statements?

To summarize: Dan Eilers argues that such support (with choices involving
a sufficiently wide spread to make a jump-table implementation infeasible)
is not a question of mandatory semantics, but of implementation capacity,
which an implementation may choose (within reason) rather arbitrarily.

I disagree. Strategies for avoiding jump-tables as the one and only
implementation method for case statements have been known for decades.
Sensible implementations of many case statements do not use jump-tables.
This is not a capacity question, but a question of competent implementation.
Even for choice ranges of 2**8 or 2**16 it is a really bad idea in most cases
to use a jump table.

If one were to specifically identify all language semantics that require
competent implementations, the RM would be full of statements "We really
mean it".



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

!section 5.4(00)
!subject sparse case statements
!reference RM95-5.4;6.0
!reference RM95-1.1.3(2);6.0
!reference 94-4309.a Dan Eilers  94-5-24
!reference 95-5297.a Dan Eilers 95-09-19
!from Robert Dewar
!reference as: 95-5325.c Tucker Taft 95-10-11>>
!discussion

I see no reason for a special implementation requirement here. These are
perfectly valid case statements, and there is no special reason in the RM
to mention that they should work.

It is true that a simple minded incompetent implementation approach will
result in an implementation with a capacity limitation that forbids
certain valid case statements.

As always (qua AI 325), capacity restrictions of this case need evaluating
to see if they are reasonable, i.e. dictated by the hardware or software
environment.

In this case, the capacity restriction is not justified, since it is 
perfectly straightforward for an implementation to properly process
these case statements. All validated Ada compilers have done so previously
(I am not aware of accepted challenges in this area).

I do not understand Dan's special case pleading here, I don't even see that
a technical case has been made to allow the capacity limitation.

We certainly do not need to have the RM full of "this must be implemented
according to the rules given above" implementation requirements, that makes
no sense at all.

Dan, I don't see the validity of your fundamental claim here that the ACVC
goes beyond the RM in requiring these case statements to work. Can you be
clear as to why you make this claim. What wording in the RM implies to you
that these case statements are somehow not expected to work.

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

!section 5.4(00)
!subject sparse case statements
!reference RM95-5.4;6.0
!reference RM95-1.1.3(2);6.0
!reference 94-4309.a Dan Eilers  94-5-24
!reference 95-5297.a Dan Eilers 95-09-19
!from Dan Eilers
!reference as: 95-5325.d Tucker Taft 95-10-11>>
!discussion

>I see no reason for a special implementation requirement here. These are
>perfectly valid case statements, and there is no special reason in the RM
>to mention that they should work.
>
>It is true that a simple minded incompetent implementation approach will
>result in an implementation with a capacity limitation that forbids
>certain valid case statements.
>
>As always (qua AI 325), capacity restrictions of this case need evaluating
>to see if they are reasonable, i.e. dictated by the hardware or software
>environment.
>
>In this case, the capacity restriction is not justified, since it is
>perfectly straightforward for an implementation to properly process
>these case statements. All validated Ada compilers have done so previously
>(I am not aware of accepted challenges in this area).
>
>I do not understand Dan's special case pleading here, I don't even see that
>a technical case has been made to allow the capacity limitation.

Well, at least we seem to agree we're talking about a capacity
restriction.  I don't claim that the capacity restriction is
clearly justified, just that it's sufficiently unclear that
based in 1.1.3(2) it doesn't belong in an ACVC test (absent an ARG
ruling). There's no point having dispute-bait tests in the suite.

AI83-325's criteria of "impossible or impractical", incorporated
in RM95-1.1.3(7), _could_ arguably apply.  It's not necessarily
"perfectly straightforward" to process sparse case statements.
Do you use a binary search method? a hash table? a linear search?
Do your efficiency minded customers care that their O(1) algorithm
can turn into an O(n) or O(log n) algorithm without warning?

If the compiler is expected to provide reasonable implementations
of sparse cases, then why limit case statements to discrete types?

I'm not aware of what other languages expect for sparse cases,
but I checked the Jovial validation suite, and it doesn't include
such extremes.

>We certainly do not need to have the RM full of "this must be implemented
>according to the rules given above" implementation requirements, that makes
>no sense at all.

I don't think this is a tip of the iceberg situation that will set
some kind of precedent, filling up the RM with such vacuous rules.
If you think otherwise, I'd like to hear where else the language
silently requires multiple implementation strategies to handle
extreme cases.

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

!section 5.4(00)
!subject sparse case statements
!reference RM95-5.4;6.0
!reference RM95-1.1.3(2);6.0
!reference 94-4309.a Dan Eilers  94-5-24
!reference 95-5297.a Dan Eilers 95-09-19
!from Dan Eilers
!reference as: 95-5325.e Tucker Taft 95-10-11>>
!discussion

p.s.
 ACVC 2.0 User's Guide (6 February 1995) 1.3

  "The ACVC tests do not check performance parameters (e.g.,
compile-time capacities or run-time speed)."

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

!section 5.4(00)
!subject sparse case statements
!reference RM95-5.4;6.0
!reference RM95-1.1.3(2);6.0
!reference 94-4309.a Dan Eilers  94-5-24
!reference 95-5297.a Dan Eilers 95-09-19
!from Robert Dewar
!reference as: 95-5325.f Tucker Taft 95-10-11>>
!discussion

to me it seems perfectly standard to handle case statements in  a manner
consistent with the range of values present. All C compilers I have ever
worked with do it, including GCC. I would consider an Ada compiler that
did not handle arbitrary case statements to have a defect and be non
conformant. These are valid programs, and I repeat that I see no reason
for a compiler to reject these valid programs on bogus capacity grounds.

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

Questions? Ask the ACAA Technical Agent