Re: Equality operator overloading in ADA 83

[bobduff@world.std.com (Robert A Duff)]

In article <01bc5244$315f1560$28f982c1@xhv46.dial.pipex.com>,
Nick Roberts <Nick.Roberts@dial.pipex.com> wrote:
>The Ada language makes no specifications for the efficiency of the
>implementation of any construct anyway.

True.  I don't know of any programming language that does.  It's too
hard, especially with modern hardware that confuses things with all
kinds of caching and whatnot.

However, in a language at the level of Ada, you can usually guess
roughly how efficient a given operation will be.  For example, I can be
pretty sure that arrays are laid out as contiguous storage in memory,
and so indexing is implemented as a constant-time algorithm.  In a
higher-level language that has associative arrays, it's harder to guess
about the efficiency of array indexing.

I must admit that case statements are not quite so easy to guess about.
Surely any decent compiler will use a jump table when appropriate, but
if the choices are sparse, a compiler could do a binary search of an
ordered table, or an elsif sequence, for example.

One other exception to my claim above is generics -- sharing vs. not
sharing vs. sometimes sharing is enough of an efficiency issue that it
strongly affects the sort of code you write.  But I still think that for
*most* features of Ada, you can make a pretty good guess about
efficiency based on the source code, despite the fact that the RM
doesn't say anything about it.  (E.g. I expect an assignment of integers
to normally take about 1 instruction or so.)

>... Most programmers would be aware
>that a case statement applied to a non-discrete type would (probably) have
>to be implemented as a sequence of comparisons.

You mean a series of "if .. elsif .. elsif..."?  That's certainly not
the best approach, in general.  For testing large numbers of strings,
you might want some sort of table lookup (binary search, hash table, or
whatever).  The general style of Ada is to allow the *programmer* to
make that choice.

>As to the property of mutual exclusion - this is the 'essence' of the case
>statement

Yes.  Mutual exclusion and no duplicates.  So the reader need not worry
about the order in which the choices appear (which is necessary for
elsif sequences).

>... - the implementation would probably have to test every choice at
>run time in order to check that only one choice evaluates to True (and
>raise an exception otherwise).

You're mixing two things here.  The suggestion was to allow composite
types in case statements.  In addition, you could (1) retain the rule
that the choices have to be static, and change the rules of static
expressions so that more things are static (e.g. a constant initialized
to a record aggregate containing all compile-time-known stuff), or (2)
do as you say here, and do a run-time check.  Extending case statements
to composite types doesn't *require* number (2), and my example used
only static string expressions as choices.  (1) vs. (2) is the usual
trade-off about compile-time vs. run-time checks -- the former gives you
error messages earlier, which is good, but reduces flexibility.  Note
that number (2) could involve some very slow checks, which is again not
the style of Ada.  If I were adding this feature to Ada, I would
probably go with number (1).

>... In all other respects, I cannot see any
>reason why the suggested extension to the case statement would be
>impracticable. It would surely be a boon to programmers, as it would be a
>neat way express the mutual exclusion implied in certain situations, and,
>at the same time, have a runtime check (which could perhaps be removed by a
>pragma Suppress where necessary) to enforce this exclusion. Programmers
>would have to be taught not to use the facility inappropriately (as with
>many other Ada features).
>
>Maybe in a future revision.

I doubt it.  This is the sort of feature you might find in a language
like perl or SETL, but Ada is too low-level for this sort of feature,
IMHO.

- Bob