home *** CD-ROM | disk | FTP | other *** search
/ ftp.umcs.maine.edu / 2015-02-07.ftp.umcs.maine.edu.tar / ftp.umcs.maine.edu / pub / WISR / wisr6 / proceedings / ascii / hollingsworth.ascii < prev    next >
Text File  |  1993-10-19  |  10KB  |  205 lines
  1.     Hollingsworth - 1
  2.  
  3.  
  4. Uncontrolled Reference Semantics
  5.  Thwart Local Certifiability
  6.  
  7.  
  8. Joe Hollingsworth
  9.  
  10. Indiana University Southeast
  11. LF218A-4201 Grant Line Road
  12. New Albany, Indiana  47150
  13. Tel: (812)941-2425
  14. Email: jholly@ius.indiana.edu
  15.  
  16.  
  17. Abstract
  18.  
  19. This paper╒s position focuses on software component design-for-reuse 
  20. down in the trenches, similar to the focus of WISR 92╒s working group 
  21. ╥Design-for-Reuse in the Trenches.╙  The technical focus is on components 
  22. implemented using reference semantics.  The position is: components 
  23. implemented using uncontrolled reference semantics should not be allowed 
  24. into the reusable component library.  This is because they thwart local 
  25. certifiability.  This position is controversial because 1) not everybody 
  26. agrees on the necessity of locally certifiable components, and 2) most 
  27. published component libraries rely heavily on uncontrolled reference 
  28. semantics.
  29.  
  30. Keywords: design-for-reuse, design principles, local certifiability
  31.  
  32. Workshop Goals: interact; advance software engineering and reuse 
  33. technology
  34.  
  35. Working Groups: design guidelines for reuse, reuse and formal methods, 
  36. reusable component certification
  37.  
  38. 1    Background
  39.  
  40. Our recent research has concentrated on design principles that lead to the 
  41. design of high-quality software components.  The design principles focus on 
  42. the technical details of component design, not on the higher level reuse 
  43. problems (e.g., library organization, and searching).  In [4] we identified 41 
  44. explicit principles for the design and implementation of components in Ada.  
  45. Components designed by these principles are called RESOLVE/Ada components.  
  46. Since January of 1993, the author╒s Ph.D. dissertation (which contains these 
  47. principles and their justification) has been available via anonymous ftp over 
  48. the Internet.  Over 100 researchers and practitioners across world have ftp╒ed a 
  49. copy and notified the author via e-mail.  The author has continued this line of 
  50. research by developing more components in Ada which follow the discipline 
  51. outlined in [4] and has begun investigating similar design principles for 
  52. components in C++.
  53.  
  54.  
  55. 2    Position
  56.  
  57. In our research we identify local certifiability as fundamental to successful 
  58. systematic reuse of software components (see [10] and [4]).  By reuse, we mean 
  59. that the component can be reused without alteration of the code that 
  60. implements it (of course supplying different actual parameters to generic 
  61. components is allowed).  At a minimum, software components need to be 
  62. locally certifiable for correctness.  There are other properties that we want to be 
  63. locally certifiable (e.g., composability), but correctness is of the utmost 
  64. importance.  Additionally, the Certification Working Group from WISR ╒92 
  65. reported that ╥all reusable components ... should be certified╙ and ╥local 
  66. certification is necessary for non-trivial components╙ (see [5]).  In our research 
  67. on component design, we found many component designers frequently used 
  68. practices which thwart local certifiability.  One in particular is the use of 
  69. uncontrolled reference semantics in the implementation of a software 
  70. component.
  71.  
  72. [6] uses value semantics for those data types whose representation is ╥small╙ 
  73. and requires little overhead when moving the actual data around.  For 
  74. example, the data type integer is usually implemented using value semantics.  
  75. Meyer uses reference semantics for data types whose representation can be 
  76. large.  For example, a queue of 100 items.  The reference semantic 
  77. representation uses (at least) one level of indirection.  Therefore, if one were to 
  78. ╥move╙ the queue found in the previous example, it would require moving or 
  79. copying one pointer, not all 100 items.
  80.  
  81. Uncontrolled reference semantics is when the component╒s design also allows 
  82. this implementation detail (the use of reference semantics) to leak through the 
  83. component╒s abstraction barrier.  An example of this is when a client of the 
  84. component can unknowingly (or knowingly) create pointer aliases, garbage or 
  85. unwanted side-effects just by using the component╒s exported operations.  
  86. Components designed like this have been published in [1] and [7] to name a 
  87. few, so this is not an uncommon practice.
  88.  
  89. Components designed in such a manner thwart local certification of 
  90. correctness.  Basically this means certification of that kind of component must 
  91. be done every time the component is ╥reused╙ from the library in some 
  92. system.  That is, if it is not locally certifiable, then it cannot be certified just 
  93. once when it is put in the library.  On the contrary, it has to be certified each 
  94. time it is used and the certification almost always has to be done with the 
  95. code that comprises the entire system.  In the example given above using the 
  96. queue, if the client of the queue component can create aliases (either 
  97. knowingly or unknowingly), then a change to the queue (e.g., a call to 
  98. Dequeue) will change the value of the queue for all who have access because of 
  99. aliasing.  Thus what seem to be only changes to a local variable end up having 
  100. non-local effects.  This thwarts local certification of correctness [2].  In our 
  101. opinion, this is one reason why some people believe that correctness proofs will 
  102. never be developed for any non-trivial system.
  103.  
  104. Given the above, our position is: components implemented using uncontrolled 
  105. reference semantics should not be allowed into the reusable component 
  106. library.
  107.  
  108. Local certifiability is just too important to be traded away for components 
  109. designed using uncontrolled reference semantics.  This is especially true when 
  110. it has been shown that a highly useful library of components (RESOLVE/Ada 
  111. components) can be built without the use of uncontrolled reference semantics 
  112. [4].
  113.  
  114.  
  115. 3    Comparison
  116.  
  117. As a comparison to other published work in the area of component design 
  118. guidelines/principles, we provide the following table (reproduced from [4]).
  119.  
  120. The columns numbered from one to 18 represent the first 18 principles for 
  121. designing RESOLVE/Ada components.  We pick these principles because they 
  122. deal only with the component╒s interface, and not with its implementation.  
  123. These principles when followed go a long way toward controlling ╥uncontrolled 
  124. reference semantics.╙  In particular, principles 1, 5, 6, 7, 14 and 16 have direct 
  125. effect on controlling the use of reference semantics.  They do not eliminate its 
  126. use, they only control it so that it does not thwart local certifiability.
  127.  
  128. The rows represent five different published component libraries and/or 
  129. guidelines.  The authors are listed below the table.  An ╥x╙ in a particular 
  130. column indicates that column╒s principle is followed, at least most of the the 
  131. time, by that row╒s component library and/or guidelines.  Notice that no row 
  132. has an ╥x╙ for all of the principles listed above that directly effect the control 
  133. of reference semantics.
  134.  
  135.  
  136.     1    2    3    4    5    6    7    8    9    10    11    12    13    14    15    16    17    18
  137. A        x        x    x        x                        x                    x
  138. B        x    x    x    x                                x                    
  139. C        x        x                                    x        x        x    x
  140. D                                                    x                    
  141. E    x    x    x        x        x                        x                    x
  142.  
  143.     A    ╤    Booch [1]    D    ╤    St. Dennis [8]
  144.     B    ╤    Hibbard [3]    E    ╤    Wallis [9]
  145.     C    ╤    Musser [7]
  146.  
  147.  
  148.  
  149. References
  150.  
  151. [1]    [Booch, G., Software Components with Ada, Benjamin/Cummings, Menlo 
  152. Park, California, 1987.
  153.  
  154. [2]    [Ernst, G.W., Hookway, R.J., Menegay, J.A., and Ogden, W.F., ╥Modular 
  155. Verification of Ada Generics,╙  Comp. Lang. Vol. 16, No. 3/4 (1991), pp. 
  156. 259-280.
  157.  
  158. [3]    Hibbard, P., Hisgen, A., Rosenberg, J., Shaw, M., and Sherman, M., Studies in 
  159. Ada Style, Springer-Verlag, New York, New York, 1983.
  160.  
  161. [4]    Hollingsworth, J., Software Component Design-for-Reuse: A Language 
  162. Independent Discipline Applied to Ada, Ph.D. thesis, Dept. of Computer 
  163. and Information Science, The Ohio State University, Columbus, Ohio, 1992. 
  164. (A PostScript version of the dissertation is available via anonymous ftp 
  165. from ╥archive.cis.ohio-state.edu,╙ in the directory ╥pub/tech-report/TR1-
  166. 1993.╙  Source code is also available for a small set of RESOLVE/Ada 
  167. components in ╥pub/rsrg/tutorial.╙)
  168.  
  169. [5]    Knight, J., ╥WISR ╒92 Certification Working Group Report,╙ in Larry Latour, 
  170. Steve Philbrick, Mark Stevens, editors, Proceedings of the WISR ╒92 Fifth 
  171. Annual Workshop on Software Reuse, October 1992.
  172.  
  173. [6]    Meyer, B., Object-oriented Software Construction, Prentice-Hall 
  174. International, Cambridge, U.K., 1988.
  175.  
  176. [7]    Musser, D.R., Stepanov, A.A., The Ada Generic Library: Linear List Processing 
  177. Packages, Springer-Verlag, New York, New York, 1989.
  178.  
  179. [8]    St. Dennis, R., ╥A Guidebook for Writing Reusable Source Code in Ada,╙ 
  180. Technical report, Computer Sciences Center, Honeywell, Golden Valley, 
  181. Minnesota, 1986.
  182.  
  183. [9]    Wallis, P.J.L., Gautier, R.J., eds., Software Reuse with Ada, Peter Peregrinus 
  184. Ltd., London, United Kingdom, 1990.
  185.  
  186. [10]Weide, B., Hollingsworth, J., ╥Scalability of Reuse Technology to Large 
  187. Systems Requires Local Certifiability,╙ in Larry Latour, Steve Philbrick, Mark 
  188. Stevens, editors, Proceedings of the WISR ╒92 Fifth Annual Workshop on 
  189. Software Reuse, October 1992.
  190.  
  191.  
  192. 4    Biography
  193.  
  194. Hollingsworth is an assistant professor in computer science at Indiana 
  195. University Southeast.  He has a Ph.D. in software engineering from The Ohio 
  196. State University (1992).  His research focuses various aspects of software 
  197. engineering and reuse including design-for-reuse, formal methods, testing and 
  198. education, to name a few.  He has authored several technical papers on related 
  199. topics in software engineering.  Prior to receiving his Ph.D., he worked as a 
  200. software engineer at Texas Instruments (Dallas, Texas) and at Battelle Memorial 
  201. Institute (Columbus, Ohio).
  202.  
  203.  
  204.  
  205.