From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,c9629eba26884d78 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2003-08-08 03:13:27 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!headwall.stanford.edu!newshub.sdsu.edu!elnk-nf2-pas!newsfeed.earthlink.net!wn14feed!worldnet.att.net!204.127.198.203!attbi_feed3!attbi_feed4!attbi.com!rwcrnsc52.ops.asp.att.net.POSTED!not-for-mail Message-ID: <3F337798.2030008@attbi.com> From: "Robert I. Eachus" User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.0.2) Gecko/20021120 Netscape/7.01 X-Accept-Language: en-us, en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: signature like constructions References: <3F2BA9C8.9030700@noplace.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit NNTP-Posting-Host: 66.31.71.243 X-Complaints-To: abuse@comcast.net X-Trace: rwcrnsc52.ops.asp.att.net 1060337567 66.31.71.243 (Fri, 08 Aug 2003 10:12:47 GMT) NNTP-Posting-Date: Fri, 08 Aug 2003 10:12:47 GMT Organization: Comcast Online Date: Fri, 08 Aug 2003 10:12:47 GMT Xref: archiver1.google.com comp.lang.ada:41246 Date: 2003-08-08T10:12:47+00:00 List-Id: 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