NAVAL POSTGRADUATE SCHOOL Monterey, California DISSERTATION REUSABLE SOFTWARE COMPONENT RETRIEVAL VIA NORMALIZED ALGEBRAIC SPECIFICATIONS by ROBERT ALLEN STEIGERWALD December, 1991 Thesis Advisor: Dr. Luqi Approved for public release; distribution unlimited If260314 UNCLASMhlfcD CURITYCLASSIFICATIONOF THIS PAGE REPORT DOCUMENTATION PAGE a. RETORTSECURITY CLASSIFICATION UNCLASSIFIED lb. RESTRICTIVE MARKINGS a SECURITY CLASSIFICATION AUTHORITY S. DISTRIBUTION/AVAILABILITYOF REPORT Approved for public release; b. dECLAssIHCATION/dOWNGRAdINGSCHEDULE distribution is unlimited PERFORMINGORGANIZATION REPORT NUMBER(S) 5 MONITORINGORGANIZATION REPORT NL)mbER(S) . ia. NAME OF PERFORMINGORGANIZATION eb. OFFICE SVMBOL la. NAME OF MONITORINGORGANIZATION _omputer Science Dept. (ifapplicable) Naval Postgraduate School cs ^aval Postgraduate School »c. ADDRESS(City, State, andZIPCode) 7b. ADDRESS(City, State, andZIPCode) Monterey, CA 93943-5000 Monterey, CA 93943-5000 a NAMEOF FUNDING/SPONSORING 8b OFFICE SVMBOL 9. PROCUREMENT INSTRUMENT IDENTIFICATION NUMBER ORGANIZATION (ifapplicable) CCR-9058453 National Science Foundation/AJPO ;c. ADDRESS(CitDy,CState, andZIPCode) P10ROSGORUARMCE OF FUPNRDOIJNEGCNTUMBERS7*STT WORk UKliT Washington, 20550 ELEMENT NO. NO. NO. ACCESSION N R1.ETUITSLAEB(LInEcluSdeOSFecTurWitAyRClEassCifOicaMtiPonO)NENT RETRIEVAL VIA NORMALIZED ALGEBRAIC SPECIFICATIONS (U) 5 PERSONALAUTHOR(S) >teigerwald, Robert A. mJW oF REPORT 13b. TIME COVERED 14. DATE OF REPORT(Year, Month, Day) 15. PAGE COUNT 'hDDidissertation FROM TO December, 1991 2ZL 6. supplementary notation The views expressed in this thesis are those of the authors and'dio not reflect the )fficial policy orposition ofthe Department ofDefense or the United States Government. 7. COSATI CODES 18. SUBJECTTERMS (Continueonreverseifnecessaryandidentifybyblocknumber) Reusability, Reusable Software Components, Component Retrieva FIELD GROUP SUB-GROUP Algebraic Specifications, Rapid Prototyping, Computer Aided Prototypir 9. ABSTRACT(Continueonreverseifnecessaryandidentifybyblocknumber) ifforts in the software engineering community to reuse code are hampered by a lack oftools. Reusability is particularlyben icialinarapidprototypingenvironment. Rapidprototyping withautomated reusable softwarecomponent retrievalis asoftwa levelopmentmethodto rapidlyconstructand adaptsoftware,validate and refinerequirements, andcheckthe consistencyofpr wsed designs. This dissertationdescribes atool used withinthe ComputerAided Prototyping System (CAPS), developed attl ^avalPostgraduate School,which retrieves reusablecomponents from a softwarebaseusingaformal specificationas the sean :ey. The query specification that represents adesign requirement iscompared to formal specificationsofAdareusablesoftwa components stored in an object-oriented database management system. A syntactic search compares specification interface dentifying reusable candidates based on types ofparameters. The semantic search rank orders a set ofcandidate componer )ased on semantic similarity to the query. The method, called query by consistency, compares terms that are reduced inthe a oms ofeach specification. Specifications are normalized to facilitate the matchingbetween query specifications and reusab component specifications in the retrieval. A formal proof verifies that query by consistency can retrieve components guara eed to meet specified requirements. 20. DISTRIBUTION/AVAILABILITYOF ABSTRACT 21. ABSTRACT SECURITY CLASSIFICATION fj UNCLASSIFIED/UNLIMITED [] SAMEAS RPT. fj DTIC USERS UNCLASSIFIED '2a NAME OF RESPONSIBLE iNdiViduaL 22b. TELEPHONEJ/nc/udeAreaCode) 22c CE SYMBOL Luqi (408) 646-2735 )DFORM 1473,84 MAR 83APRedition may be used untilexhausted SECURITY CLASSIFICATIONOFTHIS PAGE All othereditionsareobsolete UNCLASSIFIED Approved for public release; distribution is unlimited REUSABLE SOFTWARE COMPONENTRETRIEVAL VIANORMALIZEDALGEBRAIC SPECIFICATIONS by Robert Allen Steigerwald Captain, United States Air Force B.S., United States Air Force Academy, 1981 M.S., University of Illinois, 1985 M.B.A., Rennselaer Polytechnic Institute, 1986 Submitted in partial fulfillment ofthe requirements for the degree of DOCTOROFPfflLOSOPHYIN COMPUTERSCIENCE from the NAVAL POSTGRADUATE SCHOOL December 1991 ABSTRACT Efforts in the software engineering community to reuse code are hampered by a lack of tools. Reusability is particularly beneficial in a rapid prototyping environment. Rapid prototyping with automated reusable software component retrieval is a software development method to rapidly construct and adapt software, validate and refine requirements, and check the consistency of proposed designs. This dissertation describes a tool used within the Computer Aided Prototyping System (CAPS), developed at the Naval Postgraduate School, which retrieves reusable components from a software base using a formal specification as the search key. The query specification that represents a design requirement is compared to formal specifications of Ada reusable software components stored in an object-oriented database management system. A syntactic search compares specification interfaces, identifying reusable candidates based on types of parameters. The semantic search rank orders a set of candidate components based on semantic similarity to the query. The method, called query by consistency, compares terms that are reduced in the axioms ofeach specification. Specifications are normalized to facilitate the matching between query specifications and reusable component specifications in the retrieval. A formal proof verifies that query by consistency can retrieve components guaranteed to meet specified requirements. 111 ... . TABLE OF CONTENTS INTRODUCTION I. 1 A. THE NEED FOR A RETRIEVAL MECHANISM 1 CONTRIBUTION B. 2 C. ORGANIZATION OF CHAPTERS 2 TECHNICAL BACKGROUND AND PREVIOUS RESEARCH II. 3 A. INTRODUCTION 3 REUSABLE SOFTWARE COMPONENTS B. 3 1 Definition 3 2. Advantages of Code Reuse 3 C. INFORMATION RETRIEVAL 4 1. Representation and Search 4 2. Measures of Performance 5 D APPROACHES TO RETRIEVING REUSABLE COMPONENTS 6 . 1. Browsers 6 2. Informal Specifications 7 a. Keyword Search 7 b. Multi-attribute Search 8 c Natural Language Interfaces 8 3 Formal Specifications 8 a. Types of Formal Specifications 8 b. Advantages and Disadvantages 9 E SYSTEMS AND TOOLS SUPPORTING CODE REUSE 10 . 1. Draco 10 RAPID 2. 11 3. Proto 12 4. The Reusable Software Library 12 ROPE 5. 13 6. The Programmer's Apprentice 13 7. Common Ada Missile Packages (CAMP) 14 8. Object-Oriented Systems 16 9 Operation Support System 16 IV