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 / wisr4 / proceedings / ascii / luqi.ascii < prev    next >
Internet Message Format  |  1991-10-31  |  22KB
  1. From luqi@taurus.cs.nps.navy.mil Thu Oct 31 20:37:31 1991
  2. Received: from taurus-campus.cs.nps.navy.mil by gandalf.umcs.maine.edu (5.59/1.34-seg070391)
  3.     id AA00735; Thu, 31 Oct 91 20:01:16 EST
  4. Received: from sun60.cs.nps.navy.mil.nps.navy.mil by taurus.cs.nps.navy.mil (4.1/cs.nps-1.0)
  5.     id AA16784; Thu, 31 Oct 91 14:10:44 PST
  6. Date: Thu, 31 Oct 91 14:10:44 PST
  7. From: luqi@taurus.cs.nps.navy.mil (Lucia Luqi)
  8. Message-Id: <9110312210.AA16784@taurus.cs.nps.navy.mil>
  9. To: frakes@software.org
  10. Subject: Re:  latour email
  11. Cc: larry@gandalf.umcs.maine.edu, luqi@taurus.cs.nps.navy.mil
  12. Status: RO
  13.  
  14. Hi, Bill:
  15.  
  16. I will have to send my paper and bio to you since Prof. Latour's machine 
  17. has problems. I'd appreciate it if you could forward my paper and bio to
  18. him as soon as his e-mail is available.
  19.  
  20. Many thanks!!
  21.  
  22.  
  23.                                                           -Luqi
  24.  
  25. ------------------------------bio follows, ascii-------------------------
  26.  
  27.  
  28.  
  29.           Dr. Luqi received the B.S.  degree  from  Jilin  University,
  30.           China,  received the M.S. and Ph.D. degrees in Computer Sci-
  31.           ence from University of Minnesota, and is currently an asso-
  32.           ciate  professor  at  the  Naval  Postgraduate  School.  She
  33.           worked on software research & development  for  the  Science
  34.           Academy  of  China,  University  of Minnesota, University of
  35.           Maryland, International Software Systems Inc., and etc.  She
  36.           is  a  technical  consultant for the computer industry.  Her
  37.           research interests include rapid prototyping, real-time sys-
  38.           tems, design of computer languages, software reuse, specifi-
  39.           cations,   software   configuration   management,   software
  40.           development  tools,  and scientific computing.  Her research
  41.           is supported by the National Science Foundation, the  Office
  42.           of  Naval Research and many other agencies.  She received an
  43.           Engineering Initiation Award and a Presidential Young Inves-
  44.           tigator  Award  from NSF.  She has published more than fifty
  45.           technical papers in professional journals and conferences as
  46.           well  as co-authored several books. She is an associate edi-
  47.           tor for IEEE Expert and the Journal of Systems  Integration.
  48.           She  has  supervised more than twenty-eight M. S. and Ph. D.
  49.           theses in software engineering.
  50.  
  51.           Her current address is NPS CS/Lq, Monterey, CA 93943.
  52.  
  53.  
  54.  
  55.  
  56.  
  57. ------------------------------paper follows, ascii------------------------
  58.  
  59.  
  60.  
  61.                Software Reuse in Specification-Based Prototyping
  62.  
  63.                                       Luqi
  64.                                   J. McDowell
  65.  
  66.                           Computer Science Department
  67.                            Naval Postgraduate School
  68.                                Monterey, CA 93943
  69.                               luqi@cs.nps.navy.mil
  70.  
  71.                                     ABSTRACT
  72.  
  73.             This  paper  explains  the  mechanisms  for  retrieving
  74.             reusable  software components used by CAPS, a computer-
  75.             aided prototyping system  for  embedded  and  real-time
  76.             software  systems.   The  software retrieval system has
  77.             been designed to  provide  retrievals  with  both  high
  78.             precision   and   high   recall   by   exploiting   the
  79.             specifications associated with these prototypes.   This
  80.             speeds  up  software  reuse  by  enabling the system to
  81.             reduce the amount of information that a  designer  must
  82.             examine to find an appropriate reusable component.
  83.  
  84.            Keywords: prototyping, component specification, software
  85.            retrieval, normalization, syntactic & semantic matching
  86.  
  87.           1.  Introduction
  88.  
  89.                This paper addresses the design and implementation  of
  90.           the  automated  reusable  software  retrieval system in the
  91.           Computer Aided Prototyping System (CAPS) [1].  The  purpose
  92.           of  CAPS  is to speed up prototyping for large Ada programs
  93.           that can have hard real-time constraints.   CAPS  addresses
  94.           these  goals  via  software reuse, partial code generation,
  95.           automatic  construction   of   real-time   schedules,   and
  96.           computer-aided   design  tools.   CAPS  supports  automated
  97.           retrieval of software components  based  on  specifications
  98.           expressed  in  the  prototyping  language  PSDL [2].  These
  99.           specifications  serve  a  dual  purpose:  to  document  the
  100.           requirements  and  design  of  a  prototype, and to support
  101.           accurate  retrieval  of   appropriate   reusable   software
  102.           components.
  103.  
  104.           2.  Relation to Previous Work
  105.  
  106.                Almost all of the tools developed to assist in reusing
  107.           software  components use one or more of the following three
  108.           approaches:  interactive  browsers,  automated   retrievals
  109.           based  on informal specifications, and automated retrievals
  110.           based on  formal  specifications.   Browsers  are  easy  to
  111.           implement  and  they are provided as backup methods by many
  112.           systems, including  CAPS,  but  they  rely  on  the  user's
  113.           knowledge  of  the structure of the library and can require
  114.           examination of  the  entire  library  in  the  worst  case.
  115.  
  116.  
  117.                                        1
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.           Automated    retrieval   facilities   based   on   informal
  129.           specifications are also provided by many systems.  The most
  130.           popular  variants are keyword searches (CAPS, the Operation
  131.           Support  System  OSS),  multi-attribute  queries  based  on
  132.           faceted   classification  (CAPS,  DRACO,  RAPID,  OSS,  the
  133.           Reusable Software Library, the Common Ada Missile  Packages
  134.           project  CAMP),  and  natural  language  searches (Reusable
  135.           Software Library).  CAPS also supports retrievals based  on
  136.           formal  specifications.   Formal specifications can support
  137.           more  accurate  retrievals  than  informal  specifications,
  138.           although retrievals can be potentially time consuming.  The
  139.           CAPS system alleviates this problem via a  layered  set  of
  140.           increasingly   refined  filters,  so  that  the  more  time
  141.           consuming methods are applied only to relatively small sets
  142.           of components.
  143.  
  144.           3.  Software Base Functions
  145.  
  146.                The CAPS software base management system must  perform
  147.           three   main   tasks:  query  by  specification,  component
  148.           browsing, and component  transformation.   The  ability  to
  149.           query   the  software  base  to  find  software  components
  150.           satisfying a given PSDL specification is an essential  part
  151.           of   the   rapid  prototyping  method  supported  by  CAPS.
  152.           Component browsing gives the designer the ability to locate
  153.           and  view  components in a manner other than by PSDL query,
  154.           and provides  interim  bottom-up  guidance  for  developing
  155.           decompositions until automated assistance for this function
  156.           can be developed.   Component  transformation  is  required
  157.           once  a  reusable  component  is located to materialize any
  158.           needed generic instantiations in a form consistent with the
  159.           coding conventions of the CAPS execution support system.
  160.  
  161.           3.1.  Query by Specification
  162.  
  163.                The  CAPS  software  base  stores  components  in   an
  164.           object-oriented  database  and  uses PSDL specifications as
  165.           the basis for high recall queries.  Each  stored  component
  166.           consists of a PSDL specification, a PSDL description of the
  167.           implementation, the implementation code, and  a  normalized
  168.           version of the PSDL specification. The syntax and semantics
  169.           of the PSDL specification are used to direct the search for
  170.           a component.
  171.  
  172.                Figures 1 and 2 summarize the steps necessary to store
  173.           components  in the software base and to retrieve them using
  174.           a given query specification. Components to be  stored  must
  175.           first  pass  through  syntactic  and semantic normalization
  176.           (see Figure 1).  The normalization processes transform  the
  177.           component's PSDL specification to facilitate later matching. 
  178.           Syntactic normalization  involves primarily format  changes 
  179.           and  statistical calculations  while semantic normalization   
  180.           involves specification expansion and transformations.
  181.  
  182.  
  183.                                        2
  184.  
  185.  
  186.  
  187.  
  188.           
  189.  
  190.  
  191.  
  192.  
  193.  
  194.                Figure 2  shows  the  general  process  for  component
  195.           retrieval.  A  query  for  a library component is formed by
  196.           constructing  the  PSDL  specification  for   the   desired
  197.           component.  The  query  specification  is syntactically and
  198.           semantically normalized and then matched against the stored
  199.           specifications.
  200.  
  201.                The  retrieval   process   starts   with   a   faceted
  202.           classification  step  in  which attributes that are derived
  203.           from the PSDL specification are used as  a  multi-attribute
  204.           index  to  select  a subset of the database to serve as the
  205.           starting point for  the  rest  of  the  process.   A  major
  206.           difference between the CAPS approach and other systems that
  207.           use multi-attribute searches is that the  attribute  values
  208.           are  derived  from the formal specification by a repeatable
  209.           and  completely  automatic  process.   This  ensures   that
  210.           components  are  eliminated from consideration only if they
  211.           could not possibly satisfy the query.
  212.  
  213.                After selection of a database partition based  on  the
  214.           multi-attribute   index,   the  partition  is  exhaustively
  215.           scanned and passed through the syntactic  matching  filter.
  216.  
  217.           ___________________________________________________________
  218.  
  219.                               +-------------+      +-------------+
  220.            Component          |  Syntactic  |      |  Semantic   |
  221.            Specification----->|Normalization|----->|Normalization|
  222.                      |        +-------------+      +-------------+
  223.                      |        +-------------+        |
  224.                      +------->|  Database   |<-------+
  225.                               |   Storage   |
  226.                               +-------------+
  227.            Implementation          ^   ^          Implementation
  228.            Specification  ---------^   ^--------- Body
  229.  
  230.                 Fig. 1  Process for Adding a Software Component
  231.           ___________________________________________________________
  232.  
  233.  
  234.           ___________________________________________________________
  235.  
  236.           PSDL           Syntactic      Software    Semantic       Component  Query
  237.           Specification->Normalization->Base Query->Normalization->Ranking  ->Result
  238.  
  239.               Fig. 2  Process for Retrieving a Software Component
  240.           ___________________________________________________________
  241.  
  242.  
  243.                                        3
  244.  
  245.  
  246.  
  247.  
  248.  
  249.  
  250.  
  251.  
  252.  
  253.  
  254.           The components that remain are then passed through  several
  255.           semantic matching filters.  Syntactic matching of the query
  256.           component takes  place  before  semantic  matching  because
  257.           syntactic  matching is faster than semantic matching and is
  258.           used to partition the software base  quickly  in  order  to
  259.           narrow  the  list  of possible candidates that the semantic
  260.           matching algorithm must consider. Semantic matching is time
  261.           consuming  and must be applied to as small a candidate list
  262.           as possible.
  263.  
  264.                The  main  benefit  of  syntactic  matching  is  speed
  265.           whereas  the  advantage  of  semantic matching is accuracy.
  266.           Accuracy is required in  order  to  reduce  the  number  of
  267.           reusable  components  that a designer will have to evaluate
  268.           before making a selection. Many  functions  or  types  with
  269.           different   behaviors   can  have  syntactically  identical
  270.           interfaces.  Clearly we cannot  rely  on  syntax  alone  to
  271.           provide us a sufficiently fine grained search.
  272.  
  273.                A semantic process alone would be unacceptable because
  274.           semantic  matching  would  have  to  be  applied  to  every
  275.           software base component causing the search  process  to  be
  276.           impractically   time   consuming.   For   a  more  detailed
  277.           discussion of the semantic matching mechanisms used by  the
  278.           software base see [4].
  279.  
  280.           3.1.1.  Syntactic Matching
  281.  
  282.                The  purpose  of  syntactic  matching  is  to  rapidly
  283.           eliminate  from consideration those modules in the software
  284.           base that cannot match the query specification's interface.
  285.           This  matching  process  [3]  uses  the type information in
  286.           query module's PSDL interface specification to formulate  a
  287.           query.
  288.  
  289.                The  attributes  of  a  PSDL  specification  p  for  a
  290.           software  component  c  that are important to the syntactic
  291.           matching process are the following:
  292.  
  293.           S(p)= ({In(t, n) : there are n>0 occurrences of type  t  as
  294.           input parameters to c },
  295.  
  296.                  {Out(t, m) : there are m>0 occurrences of type t  as
  297.           output parameters from c },
  298.  
  299.                  {E : E is an exception defined in c},
  300.  
  301.                  {St : St is a state variable in c} )
  302.  
  303.           S(p) is the interface subset of the PSDL specification  for
  304.           module  c  and  is  the only part of the specification that
  305.           pertains to the syntactic matching process.
  306.  
  307.  
  308.                                        4
  309.  
  310.  
  311.  
  312.  
  313.  
  314.  
  315.  
  316.  
  317.  
  318.  
  319.                Given a software base module c, and a query module  q,
  320.           along  with  their respective PSDL interface specifications
  321.           S[c] and S[q] c is a syntactic match for q if and  only  if
  322.           all of the following constraints are met:
  323.  
  324.           (1) Exists f[i] : S[q] --> S[c] such that
  325.                 [f[i](In[q](t, n)) = In[c](t', m)
  326.                  and m = n
  327.                  and (t = t' or t' is a generic match of t)
  328.                  and f[i] is bijective]
  329.  
  330.           (2) Exists f[o] : S[q] --> S[c] such that
  331.                 [f[o](Out[q](t, n)) = Out[c](t', m)
  332.                  and m = n
  333.                  and (t = t' or t' is a generic match of t)
  334.                  and f[o] is injective]
  335.  
  336.           (3) if |{ST[q]}| > 0 then |{ST[m]}| > 0 else (|{ST[q]}| = 0
  337.           = |{ST[m]}|)
  338.  
  339.                To improve efficiency, we use the  matching  rules  to
  340.           derive  a  set  of  module  attributes  that can be used to
  341.           rapidly  identify  and  reject  modules   with   unsuitable
  342.           interfaces.  Some  examples  of  these  derived  attributes
  343.           include:
  344.  
  345.                If the number of input parameters in S[q] is not equal
  346.           to  the  number input parameters in S[c], then there can be
  347.           no function f[i] to satisfy rule 1. Therefore S[c]  can  be
  348.           eliminated from the search.
  349.  
  350.                If the number of output parameters in S[q] is  greater
  351.           than  the  number  of output parameters in S[c], then there
  352.           can be no function f[o] to satisfy rule 2.  Therefore  S[c]
  353.           can be eliminated from the search.
  354.  
  355.                If S[q] has state variables defined (i.e. q defines  a
  356.           state  machine)  but S[c] has no state variables, then S[c]
  357.           can be eliminated from the search.
  358.  
  359.                The rules for the syntactic matching of  type  modules
  360.           are similar to those for operator modules with the addition
  361.           of a mapping function to map the operators of S[q]  to  the
  362.           operators  of  S[c]  and  an additional check to ensure the
  363.           generic  parameter  substitutions  used  for  this  mapping
  364.           function are consistent for all operators in S[c].
  365.  
  366.           3.1.2.  Semantic Matching
  367.  
  368.                Semantic matching is based on test cases and  symbolic
  369.           inference.   The  set of components that pass the syntactic
  370.           matching all have interfaces that are type-consistent  with
  371.           the  query.   These  components are passed through a set of
  372.  
  373.  
  374.                                        5
  375.  
  376.  
  377.  
  378.  
  379.  
  380.  
  381.  
  382.  
  383.  
  384.  
  385.           filters  defined  by  test  cases  derived  from  the  PSDL
  386.           specification.  Additional test cases and additional filter
  387.           passes are generated until either the set of candidates  is
  388.           small  enough  or  the last new test case did not eliminate
  389.           any components.  At this point the remaining candidates are
  390.           likely  candidates  for  satisfying  the  query.  The final
  391.           phase consists  of  a  set  of  automated  theorem  proving
  392.           techniques  that  attempt  to conclusively show that one of
  393.           the   retrieved   components   does   satisfy   the   query
  394.           specification.     These    are    based    on    algebraic
  395.           specifications,  term  rewrite  systems,  and  a  fast  but
  396.           limited inference method.
  397.  
  398.           3.2.  Component Browsing
  399.  
  400.                Although  browsing  by  component  name  and   keyword
  401.           browsing are not the preferred methods for finding reusable
  402.           components in a large software base,  they  are  needed  to
  403.           allow  users  to familiarize themselves with the components
  404.           in the  software  base  and  to  allow  the  software  base
  405.           administrators  to  maintain  them.   The software base was
  406.           designed and implemented to support  both  keyword  queries
  407.           and named look up.  The result of a keyword query is a list
  408.           of those components that possess one or more of  the  query
  409.           keywords.   The  list is ordered with those components that
  410.           satisfy the most query keywords coming first.
  411.  
  412.           3.3.  Component transformation
  413.  
  414.                The goal of the software base is to provide to CAPS  a
  415.           component implementation that is an exact match for a query
  416.           specification and meets the needs  of  the  CAPS  execution
  417.           support  system.   To  accomplish  this,  once  a  reusable
  418.           software component has been located it must be  transformed
  419.           into  a  form that matches all of these requirements.  This
  420.           transformation  involves  changing  parameter,  type,   and
  421.           operator  names  of the library component to match those of
  422.           the  query  specification  as  well  as  instantiating  any
  423.           generics.
  424.  
  425.                The  CAPS  software  base  cannot  directly   generate
  426.           implementation  code  because  it is not language specific.
  427.           It can generate  an  abstract  representation  of  how  the
  428.           library  component  satisfies the syntax and semantics of a
  429.           query component.  This representation can then be used by a
  430.           translation  tool  specific  to a particular implementation
  431.           language to generate the implementation code.  This  method
  432.           of  component  integration  is  preferable since components
  433.           coded in additional implementation languages can  be  added
  434.           to  the  software  base  as  long  as a translation tool to
  435.           generate the final implementation for  each  implementation
  436.           language is provided.
  437.  
  438.  
  439.                                        6
  440.  
  441.  
  442.  
  443.  
  444.  
  445.  
  446.  
  447.  
  448.  
  449.  
  450.           4.  Position
  451.  
  452.                We believe that specification-based software retrieval
  453.           is  feasible  and  necessary  for  effective reuse in large
  454.           libraries, to prevent the designer from  being  swamped  by
  455.           mountains of irrelevant components.
  456.  
  457.  
  458.  
  459.           REFERNCES:
  460.  
  461.           1.   Luqi and M. Ketabchi, "A  Computer  Aided  Prototyping
  462.                System", IEEE Software 5, 2 (March 1988), 66-72.
  463.  
  464.           2.   Luqi, V. Berzins and R. Yeh, "A  Prototyping  Language
  465.                for  Real-Time Software", IEEE Trans. on Software Eng.
  466.                14, 10 (October, 1988), 1409-1423.
  467.  
  468.           3.   J. McDowell, "A Reusable  Component  Retrieval  System
  469.                for  Prototyping",  M.  S.  Thesis,  Computer Science,
  470.                Naval Postgraduate School, Monterey, CA, Sep. 1991.
  471.  
  472.           4.   R. Steigerwald, Luqi and J. McDowell, "A CASE Tool for
  473.                Reusable  Software  Component Storage and Retrieval in
  474.                Rapid   Prototyping",   Information    and    Software
  475.                Technology 38, 11 (Nov. 1991).
  476.  
  477.           5.   Luqi,  "Normalized  Specifications   for   Identifying
  478.                Reusable  Software",  Proc.  ACM-IEEE Computer Society
  479.                1987 Fall Joint Computer Conference, p. 46-49, Dallas,
  480.                TX, October, 1987.
  481.  
  482.           6.   M.   Griss,   "Software   Reuse  at  Hewlett-Packard",
  483.                Position paper for Workshop on Reuse, OOPSLA'91,  Oct.
  484.                6, 1991.
  485.  
  486.           7.   T. Biggerstaff and A. Perlis,  "Software Reusability",
  487.                Addison-Wesley, 1989.
  488.  
  489.           8.   V.  Berzins  and  Luqi,  "Software  Engineering   with
  490.                Abstractions", Addison-Wesley, 1991.
  491.  
  492.           9.   P.  Freeman,  "Tutorial:  Software  Reusability", IEEE
  493.                Computer Society, 1986.
  494.  
  495.           10.  Proceedings,  Workshop  on Reusability in Programming,
  496.                ITT Programming, Stratford, Connecticut, Sep. 1983.
  497.  
  498.  
  499.  
  500.  
  501.  
  502.  
  503.  
  504.  
  505.  
  506.                                        7
  507.  jj.
  508.  
  509.  
  510.