Re: signature like constructions

["Robert I. Eachus" <rieachus@attbi.com>]

Dmitry A. Kazakov wrote:

> The actual problem is that we know very little about future ADT.
> Before we start to implement MI, MD, supertyping, op-disallowing etc
> in Ada, we should clearly understand how it supposed to work. We
> cannot just make Ada++ and leave programmers with that. It should be
> consistent, easy to understand and efficient.

I definitely agree, but I think you are heading in the wrong direction. 
  Multiple inheritance of interfaces will probably be a feature of 
Ada0Y, but the issues being discussed in this article will not be 
'fixed' by interface inheritance.  It is the old saw about if all you 
have is a hammer, every problem starts to look like a nail.  But since 
Ada already offers several different fasteners, part of the solution has 
to be educating users.

Let's look at the example from the right perspective.  The problem is 
not "I need to be able to associate hash values with 2D points."  That 
is a solution.  The problem statement/requirement looks something like:

The system shall have a representation of cartesian points with 
assoicated data for...

There shall a method to create sets of cartesian points.

There shall be an efficient method to determine if a particular point is 
a member of a set...

Now we are getting some meat to deal with.  Three issues should 
immediately come to mind, and should be resolved in the requirements stage:

Can the co-ordinates of the cartesian point objects vary?  If so, how do 
you determine the identity of an object?

Can a particular cartesian point be a member of more than one set?  If 
so, is there a limit on how many sets it can be a member of?

Is there any requirement to easily determine whether a point is not a 
member of a particular set?

The answer to the first question leads to two different potential 
solutions.  It should be obvious that if the point's co-ordinates can 
change without losing its identity, the hash value, if that is the 
solution chosen, must be precalculated and stored in the object.  Or the 
hash value has to be based on some other attribute of the object which 
doesn't change, perhaps its address.

The second question deals with a issue going the other direction.  If an 
object can be a member of several different sets, then any solution that 
embeds the links in the cartesian point objects will be at best, a kludge.

The third question is one of assumptions.  If the author of the 
requirements has a hash table implementation in mind, then there may be 
a 'hidden' requirement.  There may be an algorithm where affirmatively 
determining membership is easy but the negation is hard.  For example, 
if you use a small number of hash values pointing at linked lists, then 
the time to determine an element is not there will on average be twice 
what it is to determine that it is there.  Of course, you can maintain 
the lists in sorted order, and the average times will be the same.

In fact you could go the other way.  Have two hash functions.  (For this 
example assume that the 'real' hash function omits the last five bits.) 
  Now the fine grained hash maps to a bit vector.  If the corresponding 
bit is off, the point is not in the set.  If it is set, then you have to 
walk the linked list.  Now the average response to a query is much 
faster when the point is not in the set.  If you don't ask the right 
question, you won't know which implementation is preferred.

Only after you have resolved these requirements issues is it possible to 
decide what are the best data structures and relationships to use.  It 
may be that there is a "better" solution in some language other than Ada.

I got sick 20 years ago of playing the game where someone would design a 
problem to show off the superiority of some language or other.  Then I 
would propose a better solution, usually stated in Ada, and they would 
go back to the drawing board to fix the problem statement.  The people 
who played this game never figured out that I would always win.  Not 
because Ada was a superior programming language, but because I was able 
to look at the problem WITHOUT going through the filter of a particular 
programming language.  Of course, from their point of view, "and it must 
be programmed in C" would be cheating on their part.  But since I and 
others forced to play the game were much better at finding the right 
algorithms and data structures because we didn't limit ourselves to a 
single programming view.

My favorite example involved the LALR parser generator on Multics.  Pat 
Prange was about to go through the gory effort to allow an array of 
Boolean data to span multiple segments.  I asked why he didn't use a 
packed representation, and he answered at length.  But once we got all 
the requirements written down, it turned out that the major operation on 
the array was a search in a particular row for the first set bit.  After 
another half hour of discussion Pat ran off to implement the new 
version.  To make a long story short, it used the translate and test 
instruction in the character string processing unit.  The single 
instruction generated used a 512-element table to look up the first 
non-zero (9-bit) byte detected, and of course the values in the table 
were the index of the first set bit.  Six lines of PL/I carefully 
written so the code generator would emit a single instruction!

The net result was to decrease the running time for the tool by over 
90%, from just over 20 minutes to generate an optimized LALR1 parser for 
Ada, to just under two minutes.  But the point to take away is not that 
PL/I was great for this purpose, or Multics.  I could write the same 
code in COBOL for an IBM mainframe, or C for an x86 or 680x0 chip. (Or 
in Ada, or just about any language that let you get close to the metal 
when necessary.) The expertise required is in first figuring out the 
actual machine code you want generated, then knowing the compiler 
internals well enough to make it happen.

-- 
"As far as I'm concerned, war always means failure." -- Jacques Chirac, 
President of France
"As far as France is concerned, you're right." -- Rush Limbaugh