murali@tut.cis.ohio-state.edu (S Muralidharan) (08/01/90)
I am surprised to read that the need for multiple implementations of an abstraction (specifically, almost constant function) is not obvious. The almost constant function is an excellent example to demonstrate why you need multiple implementations. There are several implementations (e.g., BST, hashed search, etc.), and no one has better performance behavior than others in all repects. A client of this abstracion will choose one of the several implementations based on performance requirements. Murali
johnson@m.cs.uiuc.edu (08/02/90)
murali@tut.cis.ohio-state.edu writes: >I am surprised to read that the need for multiple implementations of an >abstraction (specifically, almost constant function) is not obvious. >The almost constant function is an excellent example to demonstrate why you >need multiple implementations. There are several implementations (e.g., >BST, hashed search, etc.), and no one has better performance behavior than >others in all repects. A client of this abstracion will choose one of the >several implementations based on performance requirements. Your argument is logical. However, it goes counter to my experience. Smalltalk has ONE implementation of the almost constant function. It has one implementation of sequence and set. Of course, it is easy to add new implementations and to use them in addition to or in place of the old ones. However, the Smalltalk library designers did not do so. In fact, I find that I rarely need a different implementation of these basic abstractions. Smalltalk has very good performance analysis tools, so I am easily able to find where the bottlenecks are in my programs. There have been a few times where I found that I needed to make a new definition of sequence or the almost constant function, so I am not saying that it never happens. I am just saying that it is not nearly as big a deal as people make it out to be. What is important is multiple extensions of an abstraction. Thus, sets and sequences are both extensions of collection. This has a much bigger impact than the ability to make multiple implementations of sequences. Ralph Johnson - University of Illinois at Urbana-Champaign
paul@athertn.Atherton.COM (Paul Sander) (08/02/90)
In article <82613@tut.cis.ohio-state.edu> murali@tut.cis.ohio-state.edu (S Muralidharan) writes: >I am surprised to read that the need for multiple implementations of an >abstraction (specifically, almost constant function) is not obvious. >The almost constant function is an excellent example to demonstrate why you >need multiple implementations. There are several implementations (e.g., >BST, hashed search, etc.), and no one has better performance behavior than >others in all repects. A client of this abstracion will choose one of the >several implementations based on performance requirements. There is some truth to this; hashing is much faster for insertion and retrieval (usually) than a tree structure is. In those applications where retrieval is done much more often than traversal, a hashing implementation would be more suitable than a tree structure. But some of the discussion in the "What is a software component?" thread has been along the lines of "not only should there be multiple implementations of an abstraction, they should be interchangeable", which I personally don't believe. I guess there are many levels of abstraction, some of which are more suited to having reusable implementations written than others. For example, a data structure with very well-defined performance characteristics but that might require some implementation details or configuration switches be visible to its client might be more suitable for a reusable implementation than an almost constant function, which might use any of a number of data structures. To replace the underlying data structure of an almost constant function might necessarily require tweaking some code below the interface of the function, but above the interface to the data structure. Looking at the problem from a different perspective, the data structure may not know enough about its client's data to effectively implement an almost constant function. Abstraction at such a high level seems to require an intimacy with the client's data that a truly reusable component just wouldn't have. So, there is a trade-off. A reusable component must have a general enough interface that it can be used with a wide variety of data types that might be stored in it. A client must have a very high level abstraction that can be tuned for good performance and resource utilization without changing its interface. Either can be met in practice, but not both at the same time. So people write thin wrappers (or "glue" logic) for reusable data structures (or reimplement data structures) that meet the specification of their abstract function, and complain that there are no good reusable implementations of their abstractions. -- Paul Sander (408) 734-9822 | "Passwords are like underwear," she said, paul@Atherton.COM | "Both should be changed often." {decwrl,pyramid,sun}!athertn!paul | -- Bennett Falk in "Mom Meets Unix"
lgm@cbnewsc.att.com (lawrence.g.mayka) (08/04/90)
In article <71800006@m.cs.uiuc.edu> johnson@m.cs.uiuc.edu writes: >In fact, I find that I rarely need a different implementation of these >basic abstractions. Smalltalk has very good performance analysis tools, >so I am easily able to find where the bottlenecks are in my programs. >There have been a few times where I found that I needed to make a new >definition of sequence or the almost constant function, so I am not >saying that it never happens. I am just saying that it is not nearly >as big a deal as people make it out to be. Compiler optimization can also play a major role in discouraging homegrown implementations of basic abstractions. For example, Common Lisp implementations on both conventional and Lisp-directed processors are typically designed to handle certain popular datatypes (e.g., small integers, lists, symbols) with high efficiency yet full safety. Homegrown equivalents, even if specialized to the immediate problem, may not actually exhibit better performance (or worse, sacrifice safety). Lawrence G. Mayka AT&T Bell Laboratories lgm@iexist.att.com Standard disclaimer.