Signature matching: a tool for using software libraries

ABSTRACT

Signature matching is a method for organizing, navigating through, and retrieving from software libraries. We consider two kinds of software library components—functions and modules—and hence two kinds of matching—function matching and module matching. The signature of a function is simply its type; the signature of a module is a multiset of user-defined types and a multiset of function signatures. For both functions and modules, we consider not just exact match but also various flavors of relaxed match. We describe various applications of signature matching as a tool for using software libraries, inspired by the use of our implementation of a function signature matcher written in Standard ML.

REFERENCES

• 1: W. W. Agresti , F. E. McGarry, The Minnowbrook workshop on software reuse: a summary report, Software reuse: emerging technology, IEEE Computer Society Press, Los Alamitos, CA, 1988
• 2: S. P. Arnold , S. L. Stepoway, The Reuse system: cataloging and retrieval of reusable software, Software reuse: emerging technology, IEEE Computer Society Press, Los Alamitos, CA, 1988
• 3: ~ATT. 1993 The Standard ML of New Jersey hbrary reference manual. Tech. Rep., AT & T Bell ~Laboratories, Murray Hill, N.J.
• 4: ~BERRY, D. 1991. The Edinburgh SML Library Tech Rep ECS-LFCS-91-148, Univ of Edin- ~burgh, U.K. April.
• 5: Ted J. Biggerstaff , Alan J. Perlis, Software reusability: vol. 1, concepts and models, ACM Press, New York, NY, 1989
• 6: ~BISCHOFBERGER, W.a. 1992 Sniff--a pragmatic approach to a C ++ programming environ- ~ment. In USENIX C++ Conference. USENIX Assoc., Berkeley, Cahf., 67 81.
• 7: Mariano Consens , Alberto Mendelzon , Arthur Ryman, Visualizing and querying software structures, Proceedings of the 14th international conference on Software engineering, p.138-156, May 11-15, 1992, Melbourne, Australia [doi>10.1145/143062.143106]
• 8: Robero Di Cosmo, Type isomorphisms in a type-assignment framework, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.200-210, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143208]
• 9: ~FIELD, A. J. AND HARRISON, P. G. 1988. Functl. onal Programming. Addison-Wesley, Reading, ~Mass.
• 10: ~FISCHER, B, KIEVERNAGEL, M., AND STRUCKMANN, W. 1994. VCR: A VDM-based software ~component retrieval tool. Tech. Rep. 94-08, Technical Univ. of Braunschweig, Germany Nov.
• 11: ~FONTANA, M. AND NEATH, M. 1991. Checked out and long overdue: Experiences in the design of ~a C 4% class library. In USENIX C44- Conference. USENIX Assoc., Berkeley, Calif., 179-191.
• 12: GARLanD, S. J. AND GUTTAG, J.V. 1991. A guide to LP, the Larch Prover. Rep. 82, DEC ~Sys~ems Research Center, Palo Alto, Calif. Dec.
• 13: John V. Guttag , James J. Horning, Larch: languages and tools for formal specification, Springer-Verlag New York, Inc., New York, NY, 1993
• 14: Richard Helm , Yoëlle S. Maarek, Integrating information retrieval and domain specific approaches for browsing and retrieval in object-oriented class libraries, Conference proceedings on Object-oriented programming systems, languages, and applications, p.47-61, October 06-11, 1991, Phoenix, Arizona, United States
• 15: ~JENG, J. J. AND CHENG, B. H.C. 1992. Formal methods applied to reuse. In Proceedings of the ~5th Workshop on Software Reuse.
• 16: S. Katz , C. A. Richter , K.-S. The, PARIS: a system for reusing partially interpreted schemas, Proceedings of the 9th international conference on Software Engineering, p.377-385, March 1987, Monterey, California, United States
• 17: Yoëlle S. Maarek , Daniel M. Berry , Gail E. Kaiser, An Information Retrieval Approach for Automatically Constructing Software Libraries, IEEE Transactions on Software Engineering, v.17 n.8, p.800-813, August 1991 [doi>10.1109/32.83915]
• 18: A. Mili , R. Mili , R. Mittermeir, Storing and retrieving software components: a refinement based system, Proceedings of the 16th international conference on Software engineering, p.91-100, May 16-21, 1994, Sorrento, Italy
• 19: ~MILNEa, R. 1978. A theory of type polymorphism in programming J. Comput. Syst. Scf. 17, 3 ~(Dec.), 348-375.
• 20: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 21: Eduardo Ostertag , James Hendler , Rubén Prieto Díaz , Christine Braun, Computing similarity in a reuse library system: an AI-based approach, ACM Transactions on Software Engineering and Methodology (TOSEM), v.1 n.3, p.205-228, July 1992 [doi>10.1145/131736.131739]
• 22: S. Paul , A. Prakash, A Framework for Source Code Search Using Program Patterns, IEEE Transactions on Software Engineering, v.20 n.6, p.463-475, June 1994 [doi>10.1109/32.295894]
• 23: Dewayne E. Perry, The inscape environment, Proceedings of the 11th international conference on Software engineering, p.2-11, May 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/74587.74588]
• 24: R. Prieto-Diaz, Classification of reusable modules, Software reusability: vol. 1, concepts and models, ACM Press, New York, NY, 1989 [doi>10.1145/73103.73107]
• 25: ~RAMAMOORTHY, C. V., Ed. 1984. IEEE Trans. Softw. Eng. SE-IO, 5 (Sept.).
• 26: Mikael Rittri, Using types as search keys in function libraries, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.174-183, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99384]
• 27: ~RITTRI, M. 1992. Retrieving library identifiers via equational matching of types. Tech. Rep. 65, ~Programming Methodology Group, Dept. of Computer Sciences, Chalmers Univ. of Technology ~and Univ. of Gi)teborg. (Reprinted with corrections May 1992).
• 28: ~ROLLINS, E. J. AND WING, J.M. 1991. Specifications as search keys for software libraries. In ~Proceedings of the 8th International Conference on Logic Programming. MIT Press, Cambridge, ~Mass.
• 29: Colin Runciman , Ian Toyn, Retrieving re-usable software components by polymorphic type, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.166-173, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99383]
• 30: ~STRINGER-CALVERT, D. W.J. 1994. Signature matching for Ada software reuse. Master's thesis, ~Univ. of York, York, England.
• 31: Gregor Snelting , Franz-Josef Grosch , Ulrik Schroeder, Inference-Based Support for Programming in the Large, Proceedings of the 3rd European Software Engineering Conference, p.396-408, October 21-24, 1991
• 32: Richard M. Stallman, GNU EMACS Manual, iUniverse, Incorporated, 2000
• 33: Guy L. Steele, Jr., Common LISP: the language, Digital Press, Newton, MA, 1984
• 34: TESLEa, L. 1981. The Smalltalk environment. BYTE 6, 8 (Aug.), 90-147.
• 35: ~TARDtTI, D. AND ROLLINS, G. 1993. Local guide to Standard ML. Tech. Rep., CMU, Pittsburgh, ~Pa. March.
• 36: Jeannette M. Wing , Eugene J. Rollins , Amy Moormann Zaremski, Thoughts on a Larch/ML and a New Application for LP, Proceedings of the first First International Workshop on Larch, p.297-312, July 13-15, 1992
• 37: Daniel M. Yellin , Robert E. Strom, Interfaces, protocols, and the semi-automatic construction of software adaptors, ACM SIGPLAN Notices, v.29 n.10, p.176-190, Oct. 1994
• 38: Amy Moormann Zaremski , Jeannette M. Wing, Specification matching of software components, Proceedings of the 3rd ACM SIGSOFT symposium on Foundations of software engineering, p.6-17, October 12-15, 1995, Washington, D.C., United States

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Modules and interfaces

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Software libraries
      D.2.m Miscellaneous
          Subjects: Reusable software**
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

General Terms:
Design

Keywords:
signature matching, software retrieval