Path: utzoo!attcan!uunet!cs.utexas.edu!sdd.hp.com!elroy.jpl.nasa.gov!jpl-devvax!ai-jupiter!kandt
From: kandt@ai-jupiter.JPL.NASA.GOV (Kirk Kandt)
Newsgroups: comp.software-eng
Subject: Re: recap so far
Message-ID: <8581@jpl-devvax.JPL.NASA.GOV>
Date: 3 Jul 90 17:00:06 GMT
References: <30852@cup.portal.com> <102100011@p.cs.uiuc.edu> <31097@cup.portal.com> <1568@oravax.UUCP> <8488@jpl-devvax.JPL.NASA.GOV> <81688@tut.cis.ohio-state.edu> <8529@jpl-devvax.JPL.NASA.GOV> <5312@stpstn.UUCP>
Sender: news@jpl-devvax.JPL.NASA.GOV
Reply-To: kandt@AI-Cyclops.JPL.NASA.GOV
Organization: NASA/Jet Propulsion Laboratory
Lines: 42

In article <5312@stpstn.UUCP>, andyk@stpstn.UUCP (Andy Klapper) writes:
|> In article <8529@jpl-devvax.JPL.NASA.GOV>
kandt@AI-Cyclops.JPL.NASA.GOV writes:
|> >
|> >I reassert that any artifact that we build can provide components for
|> >later reuse.  I also assert that if we have built a component we can
|> >adequately describe it in a formal or informal notation so that its
|> >complete behavior is understandable by a human.  I also know that
|> >providing such information for later reuse requires much labor at great
|> >cost.  This is the impediment to software reuse.  The issue is "given
|> >that you can describe a domain, how do build a information repository in
|> >a cost-effective manner."
|> >
|> >As an example, take the domain of data structures.  It is a relatively
|> >simple domain.  It is well understood.  There are both formal and
|> >informal methods for describing modeling representations and storage
|> >structures.  We understand the complexity of them all, including special
|> >cases and programming tricks.  Yet to date, there is not one reusable
|> >data structure depository.  Why is that?  Because the costs of putting
|> >all the knowledge contained in existing data structure books and
|> >articles would be incredible.
|> >
|> 
|> Smalltalk, Objective-C and I would be willing to bet other OOP and OOP
|> like languages, have a set of basic data structure objects (Sets, stacks,
|> ...) including a sorted collection that uses quicksort.  It would seem
|> that you have been looking in the wrong place.
|> 
I've used these languages before -- having a basic set of objects is not
the issue.  The issue is that the implementation of a "type" can be done
in a variety of ways, where each implementation has certain advantages
and disadvantages in terms of time and space.  A set, for example, can
be implemented as a bit array, a simple array, a linked list, a hash
table, and so on.  Smalltalk, Objective-C, etc. generally provide only
one implementation of an "abstract type".  This one implementation is
chosen because it works reasonably well for all cases, but it may not be
optimal for a specific data set; in fact, it may be orders of magnitude
slower than one tailored for the characteristics of the data set. 
Automatic data structure selection was a hot topic in the 70s because
people realized that there were tremendous pay-offs (in terms of
efficiency) by optimizing data storage and manipulation algorithms for
the expected data.