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.
Keywords
algorithm composition, algorithm selection, algorithms, automated planning, automatic programming, bioinformatics, compilers, domain-specific languages, optimization, performance, plan execution, formation, generation
Date of this Version
2006
Comments
PLDI '06 Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation