Context-sensitive domain-independent algorithm composition and selection

ABSTRACT

Progressing beyond the productivity of present-day languages appears to require using domain-specific knowledge. Domain-specific languages and libraries (DSLs) proliferate, but most optimizations and language features have limited portability because each language's semantics are related closely to its domain. We explain how any DSL compiler can use a domain-independent AI planner to implement algorithm composition as a language feature. Our notion of composition addresses a common DSL problem: good library designers tend to minimize redundancy by including only fundamental procedures that users must chain together into call sequences. Novice users are confounded by not knowing an appropriate sequence to achieve their goal. Composition allows the programmer to define and call an abstract algorithm (AA) like a procedure. The compiler replaces an AA call with a sequence of library calls, while considering the calling context. Because AI planners compute a sequence of operations to reach a goal state, the compiler can implement composition by analyzing the calling context to provide the planner's initial state. Nevertheless, mapping composition onto planning is not straightforward because applying planning to software requires extensions to classical planning, and procedure specifications may be incomplete when expressed in a planning language. Compositions may not be provably correct, so our approach mitigates semantic incompleteness with unobtrusive programmer-compiler interaction. This tradeoff is key to making composition a practical and natural feature of otherwise imperative languages, whose users eschew complex logical specifications. Compositions satisfying an AA may not be equal in performance, memory usage, or precision and require selection of a preferred solution. We examine language design and implementation issues, and we perform a case study on the BioPerl bioinformatics library.

REFERENCES

• 1: Thomas Ball , Rupak Majumdar , Todd Millstein , Sriram K. Rajamani, Automatic predicate abstraction of C programs, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.203-213, June 2001, Snowbird, Utah, United States
• 2: Robert Balzer, A 15 year perspective on automatic programming, IEEE Transactions on Software Engineering, v.11 n.11, p.1257-1268, Nov. 1985 [doi>10.1109/TSE.1985.231877]
• 3: David R. Barstow, Domain-specific automatic programming, IEEE Transactions on Software Engineering, v.11 n.11, p.1321-1336, Nov. 1985 [doi>10.1109/TSE.1985.231881]
• 4: D. Batory. The Road to Utopia: A Future for Generative Programming. In C. Lengauer et al., editors, Domain-Specific Program Generation (Dagstuhl), pages 1--18, 2004.
• 5: A. W. Biermann. Approaches to Automatic Programming. Advances in Computers, 15:1--63, 1976.
• 6: J. Blythe et al. The Role of Planning in Grid Computing. In Proceedings of the International Conference on Automated Planning and Scheduling, June 2003.
• 7: Alex Borgida , John Mylopoulos , Raymond Reiter, On the Frame Problem in Procedure Specifications, IEEE Transactions on Software Engineering, v.21 n.10, p.785-798, October 1995 [doi>10.1109/32.469460]
• 8: Lionel C. Briand , Tristen Langley , Isabella Wieczorek, A replicated assessment and comparison of common software cost modeling techniques, Proceedings of the 22nd international conference on Software engineering, p.377-386, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337223]
• 9: Jack R. Buchanan , David C. Luckham, On automating the construction of programs., Stanford University, Stanford, CA, 1974
• 10: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 11: R. E. Fikes and N. J. Nilsson. STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving. Artificial Intelligence, 2(3-4):189--208, 1971.
• 12: Cormac Flanagan , Shaz Qadeer, Predicate abstraction for software verification, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.191-202, January 16-18, 2002, Portland, Oregon
• 13: M. Ghallab et al. PDDL - the Planning Domain Definition Language, Version 1.2. Technical Report DCS TR-1165, Yale Center for Computational Vision and Control, 1998.
• 14: Dana Nau , Malik Ghallab , Paolo Traverso, Automated Planning: Theory & Practice, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 15: Robert Givan, Inferring Program Specifications in Polynomial-Time, Proceedings of the Third International Symposium on Static Analysis, p.205-219, September 24-26, 1996
• 16: K. Golden. A Domain Description Language for Data Processing. In Proceedings of the International Conference on Automated Planning and Scheduling, Workshop on the Future of PDDL, 2003.
• 17: Asuncion Gomez-Perez , Oscar Corcho-Garcia , Mariano Fernandez-Lopez, Ontological Engineering, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 18: M. Gribskov. President, International Society for Computational Biology; Professor of Biological Sciences and Computer Science, Purdue University. Personal communication, September 2005.
• 19: John V. Guttag , James J. Horning, Larch: languages and tools for formal specification, Springer-Verlag New York, Inc., New York, NY, 1993
• 20: S. Z. Guyer and C. Lin. Broadway: A Compiler for Exploiting the Domain-Specific Semantics of Software Libraries. Proceedings of the IEEE, 93(2):342--357, February 2005
• 21: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 22: Elias N. Houstis , Ann C. Catlin , John R. Rice , Vassilios S. Verykios , Naren Ramakrishnan , Catherine E. Houstis, PYTHIA-II: a knowledge/database system for managing performance data and recommending scientific software, ACM Transactions on Mathematical Software (TOMS), v.26 n.2, p.227-253, June 2000 [doi>10.1145/353474.353475]
• 23: N. Jefferson and S. Riddle. Towards a Formal Semantics of a Composition Language. In Proceedings of the Workshop on Composition Languages at ECOOP, 2003.
• 24: K. Kennedy et al. Telescoping Languages: A System for Automatic Generation of Domain Languages. Proceedings of the IEEE, 93(3):387--408, 2005.
• 25: Ken Kennedy , Charles Koelbel , Robert Schreiber, Defining and Measuring the Productivity of Programming Languages, International Journal of High Performance Computing Applications, v.18 n.4, p.441-448, November 2004 [doi>10.1177/1094342004048537]
• 26: Jihie Kim , Marc Spraragen , Yolanda Gil, An intelligent assistant for interactive workflow composition, Proceedings of the 9th international conference on Intelligent user interface, January 13-16, 2004, Funchal, Madeira, Portugal [doi>10.1145/964442.964466]
• 27: Charles W. Krueger, Software reuse, ACM Computing Surveys (CSUR), v.24 n.2, p.131-183, June 1992 [doi>10.1145/130844.130856]
• 28: Sorin Lerner , Todd Millstein , Craig Chambers, Automatically proving the correctness of compiler optimizations, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 29: David Mandelin , Lin Xu , Rastislav Bodík , Doug Kimelman, Jungloid mining: helping to navigate the API jungle, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 30: Zohar Manna , Richard Waldinger, Fundamentals of Deductive Program Synthesis, IEEE Transactions on Software Engineering, v.18 n.8, p.674-704, August 1992 [doi>10.1109/32.153379]
• 31: Beniamino Di Martino , Giulio Iannello , Hans P. Zima, An Automated Algorithmic Recgnition Ttechnique to Support Parallel Software Development, Proceedings of the 2nd International Workshop on Software Engineering for Parallel and Distributed Systems, p.120, May 17-18, 1997
• 32: Vijay Menon , Keshav Pingali, A case for source-level transformations in MATLAB, Proceedings of the 2nd conference on Domain-specific languages, p.53-65, October 03-06, 1999, Austin, Texas, United States
• 33: Vijay Menon , Keshav Pingali, High-level semantic optimization of numerical codes, Proceedings of the 13th international conference on Supercomputing, p.434-443, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305230]
• 34: R. Metzger and Z. Wen. Automatic Algorithm Recognition and Replacement. MIT Press, 2000.
• 35: D. S. Nau, Y. Cao, A. Lotem, and H. Muñoz-Avila. The SHOP planning system. AI Magazine, Fall 2001.
• 36: George C. Necula, Translation validation for an optimizing compiler, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.83-94, June 18-21, 2000, Vancouver, British Columbia, Canada
• 37: E. P. D. Pednault. ADL and the State-Transition Model of Action. Journal of Logic and Computation, 4(5):467--512, 1994.
• 38: Eric S. Raymond, The Art of UNIX Programming, Pearson Education, 2003
• 39: J. R. Rice. The Algorithm Selection Problem. Advances in Computers, 15:65--118, 1976.
• 40: Charles Rich , Richard C. Waters, Automatic Programming: Myths and Prospects, Computer, v.21 n.8, p.40-51, August 1988 [doi>10.1109/2.75]
• 41: Peter Schnorf , Mahadevan Ganapathi , John L. Hennessy, Compile-time copy elimination, Software—Practice & Experience, v.23 n.11, p.1175-1200, Nov. 1993 [doi>10.1002/spe.4380231102]
• 42: Ulrik P. Schultz , Julia L. Lawall , Charles Consel, Automatic program specialization for Java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.4, p.452-499, July 2003 [doi>10.1145/778559.778561]
• 43: J. M. Siskind and D. A. McAllester. Screamer: A Portable Efficient Implementation of Nondeterministic Common Lisp. Technical Report IRCS-93-03, Institute for Research in Cognitive Science, University of Pennsylvania, 1993.
• 44: J. E. Stajich et al. The Bioperl Toolkit: Perl Modules for the Life Sciences. Genome Research, 12(10):1611--1618, October 2002.
• 45: Mark E. Stickel , Richard J. Waldinger , Michael R. Lowry , Thomas Pressburger , Ian Underwood, Deductive Composition of Astronomical Software from Subroutine Libraries, Proceedings of the 12th International Conference on Automated Deduction, p.341-355, June 26-July 01, 1994
• 46: Nathan Thomas , Gabriel Tanase , Olga Tkachyshyn , Jack Perdue , Nancy M. Amato , Lawrence Rauchwerger, A framework for adaptive algorithm selection in STAPL, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065981]
• 47: Mark T. Vandevoorde, Exploiting specifications to improve program performance, Massachusetts Institute of Technology, Cambridge, MA, 1993
• 48: Sanjiva Weerawarana , Elias N. Houstis , John R. Rice , Anupam Joshi , Catherine E. Houstis, PYTHIA: a knowledge-based system to select scientific algorithms, ACM Transactions on Mathematical Software (TOMS), v.22 n.4, p.447-468, Dec. 1996 [doi>10.1145/235815.235820]
• 49: D. S. Weld. Recent Advances in AI Planning. AI Magazine, pages 93--123, Summer 1999.
• 50: Steven Woods , Qiang Yang, The program understanding problem: analysis and a heuristic approach, Proceedings of the 18th international conference on Software engineering, p.6-15, March 25-29, 1996, Berlin, Germany
• 51: Hao Yu , Dongmin Zhang , Lawrence Rauchwerger, An Adaptive Algorithm Selection Framework, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.278-289, September 29-October 03, 2004 [doi>10.1109/PACT.2004.6]
• 52: Amy Moormann Zaremski , Jeannette M. Wing, Specification matching of software components, ACM Transactions on Software Engineering and Methodology (TOSEM), v.6 n.4, p.333-369, Oct. 1997 [doi>10.1145/261640.261641]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.2 Automatic Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Optimization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation

General Terms:
Algorithms, Languages, Performance

Keywords:
algorithm composition, algorithm selection, automated planning, bioinformatics, domain-specific languages