Re: signature like constructions

[Dmitry A. Kazakov <mailbox@dmitry-kazakov.de>]

On Fri, 08 Aug 2003 10:12:47 GMT, "Robert I. Eachus"
<rieachus@attbi.com> wrote:

>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. 

I do not think that we really are in a big disagreement. (:-))

>  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...

Yes. But the example provided by Georg, as far as I understand it,
aims at a case where there is already an implementation of 2D points,
which has to be reused. He wished to show that it is problematic with
tagged types, but still works with generics.

Your example is a case of monolitic design, all from scratch, which is
clean and desirable, but becomes less and less frequent in modern
times. It is a right perspective, but there is a little chance that we
would climb so high. (:-))

>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?

Points as objects usually have no identity. Why should they have any?
One of real problems of OO is overuse of objects with identity.

>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.

This is true, but again unrealistic in a large, distributed, long
living project. In which case a "better" solution is one which
requires only maintainable changes in the existing infrastructure and
still works somehow...

>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.

This is a question of balance between understanding of the problem and
understanding of the software tools used to solve it. From the dawn of
computers to present day, the first component prevailed, allowing to
implement "everything [problem] in anything [language]". But in a
long-term perspective, I am talking about 20-100 years, the balance
will definitely change, otherwise we will be unable to maintain the
complexity of software [not the algorithms, note]. It will be a
virtual reality with its own virtual problems, if you wish. (:-)) And
the question is whether templates are the right tool to deal with ever
increasing complexitiy. I do not think so.

---
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de