IBM Systems Journal - 2002 Copyright

IBM Skip to main content
  Home     Products & services     Support & downloads     My account  

  Select a country  
Journals Home  
  Systems Journal  
    Current Issue  
    Recent Issues  
    Papers in Progress  
    Author's Guide  
Journal of Research
and Development
  Contact Us  
  Related links:  
     IBM Research  

IBM Journal of Research and Development  
Volume 33, Number 1, Page 158 (1994)
Software Quality
  Full article: arrowPDF   arrowCopyright info


Deriving programs using generic algorithms

by V. R. Yakhnis, J. A. Farrell, S. S. Shultz
We suggest a new approach to the derivation of programs from their specifications. The formal derivation and proof of programs as is practiced today is a very powerful tool for the development of high-quality software. However, its application by the software development community has been slowed by the amount of mathematical expertise needed to apply these formal methods to complex projects and by the lack of reuse within the framework of program derivation. To address these problems, we have developed an approach to formal derivation that employs the new concept of generic algorithms. A generic algorithm is one that has (1) a formal specification, (2) a proof that it satisfies this specification, and (3) generic identifiers representing types and operations. It may have embedded program specifications or pseudocode instructions describing the next steps in the stepwise refinement process. Using generic algorithms, most software developers need to know only how to pick and adapt them, rather than perform more technically challenging tasks such as finding loop invariants and deriving loop programs. The adaptation consists of replacing the generic identifiers by concrete types and operations. Since each generic algorithm can be used in the derivation of many different programs, this new methodology provides the developer with a form of reuse of program derivation techniques, correctness proofs, and formal specifications.
Related Subjects: Mathematical Methods; Process; Programming