Output-constraint specialization

ABSTRACT

In component-based software development, gluing of two software components are usually achieved by defining an interface specification, and creating wrappers on the components to support the interface. We believe that interface specification provides useful information for specializing components. However, an interface may define constraints on a component's inputs, as well as on its outputs. In this paper, we propose a novel concept of program specialization with respect to output constraints. We define how an ideal specialized program should behave after such specialization, and consider a variant of partial evaluation to achieve it. In the process, we translate an output constraint into a characterization function for a component's input, and define a specializer that uses this characterization to guide the specialization process. We believe this work will broaden the scope of program specialization, and provide a framework for building more generic and versatile program adaptation techniques.

REFERENCES

• 1: Sergei M. Abramov , Robert Glück, The Universal Resolving Algorithm: Inverse Computation in a Functional Language, Proceedings of the 5th International Conference on Mathematics of Program Construction, p.187-212, July 03-05, 2000
• 2: A. Bondorf and J. Jorgensen. Efficient analyses for realistic off-line partial evaluation. Journal of Functional Programming, 3(3):315--346, July 1993.
• 3: Wei-Ngan Chin , Siau-Cheng Khoo, Calculating sized types, Proceedings of the 2000 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, p.62-72, January 22-23, 2000, Boston, Massachusetts, United States
• 4: Wei-Ngan Chin , Siau-Cheng Khoo, Calculating Sized Types, Higher-Order and Symbolic Computation, v.14 n.2-3, p.261-300, September 2001 [doi>10.1023/A:1012996816178]
• 5: Wei-Ngan Chin , Siau-Cheng Khoo , Dana N. Xu, Deriving Pre-conditions for Array Bound Check Elimination, Proceedings of the Second Symposium on Programs as Data Objects, p.2-24, May 21-23, 2001
• 6: Joseph J. Comuzzi , Johnson M. Hart, Program Slicing Using Weakest Preconditions, Proceedings of the Third International Symposium of Formal Methods Europe on Industrial Benefit and Advances in Formal Methods, p.557-575, March 18-22, 1996
• 7: Charles Consel, Program adaptation based on program transformation, ACM Computing Surveys (CSUR), v.28 n.4es, Dec. 1996 [doi>10.1145/242224.242431]
• 8: Cormac Flanagan , James B. Saxe, Avoiding exponential explosion: generating compact verification conditions, Proceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.193-205, January 2001, London, United Kingdom
• 9: Y. Futamura. Partial evaluation of computation process -- an approach to a compiler-compiler. Systems, Computers, Controls, 2(5):45--50, 1971.
• 10: Laura Lafave , John P. Gallagher, Constraint-Based Partial Evaluation of Rewriting-Based Functional Logic Programs, Proceedings of the 7th International Workshop on Logic Programming Synthesis and Transformation, p.168-188, July 10-12, 1997
• 11: William Pugh, A practical algorithm for exact array dependence analysis, Communications of the ACM, v.35 n.8, p.102-114, Aug. 1992 [doi>10.1145/135226.135233]
• 12: Jens Peter Secher , Morten Heine Sørensen, From checking to inference via driving and dag grammars, Proceedings of the 2002 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, p.41-51, January 14-15, 2002, Portland, Oregon
• 13: Norihisa Suzuki , Kiyoshi Ishihata, Implementation of an array bound checker, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.132-143, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512963]
• 14: Hongwei Xi , Frank Pfenning, Dependent types in practical programming, 1998
• 15: Zhichen Xu , Barton P. Miller , Thomas Reps, Safety checking of machine code, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.70-82, June 18-21, 2000, Vancouver, British Columbia, Canada

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.13 Reusable Software

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

General Terms:
Algorithms, Performance

Keywords:
partial evaluation, specialization, weakest pre-condition