Partial Evaluation for Software Engineering
by Renaud Marlet, Scott Thibault and Charles Consel
Software architectures promote flexibility at the expense of performance overhead. The COMPOSE project at IRISA/INRIA Rennes has developed automatic program transformation techniques and tools to systematically improve efficiency while retaining genericity, safety, and adaptability.
Software architectures express how systems should be built from various interacting components. As the size and complexity of software systems increase, the choice of software architectures becomes a major issue, impacting on time-to-market as well as development cost, validation, and maintenance.
Software architectures are designed to be flexible, including aspects such as genericity, extensibility, adaptability. But flexibility impairs efficiency because it is usually not only present at the design level but also in the implementation. Whereas efficiency requires tight integration of components, flexibility calls for greater separation.
Commonly used manual optimizations are ad hoc, tedious, error prone, and unpredictable; they do not scale up and defeat the purposes of software engineering. Other approaches, aiming generating and efficiently composing building blocks, are specific to architectures and component domains, and do not fully exploit all integration opportunities.
We propose a systematic method to improve the efficiency of software architectures: program specialization. This is a general program transformation that exploits information available prior to execution (such as known input values) yielding a specialized program where all computations depending on known information are being performed early. The specialized program is thus faster (due to less computation) while semantically equivalent to the original program. In particular, program specialization can exploit the gluing information and the parameterization of software components in order to better integrate them. It is not specific to a particular software architecture style.
Partial evaluation is the technique that automates program specialization. Therefore it does not conflict with software engineering purposes. We have shown that partial evaluation can improve the performance of a wide range of software architectures and mechanisms:
- In the selective broadcast (a.k.a. implicit invocation) architecture, components are independent agents that interact with each other by subscribing to certain types of events and sending broadcast messages. Specializing with respect to a subscription converts broadcasting into mere explicit calls to registered agents. Also, the selection and decoding of message arguments may rely on a pattern matching mechanism. Specializing the pattern matcher and the decoder with respect to the selection pattern generates efficient automata-like routines.
- Software layers provide services to the layers above and act as a client to the layer below. An example is Sun's implementation of the Remote Procedure Call (RPC) protocol. Specializing the process of encoding data to a network-independent representation results in bare memory transfers, with speedups up to 3.7.
- Scripting languages glue together powerful components (building blocks) written in traditional programming languages. For flexibility and simplicity, they are often interpreted. Specializing an interpreter with respect to the script yields a fast compiled-like version of the script. Typical speedups range from 10 to 100. We have a framework to apply this to Domain-Specific Languages; it has been successfully put into practice for the automatic generation of safe and efficient video card drivers.
- Tests for options in generic libraries can be evaluated by partial evaluation when these options are known early. Furthermore, such libraries often include validity tests (including bound checking) of complex data structures. Specializing with respect to the shape of the structure (as opposed to the actual content) eliminates verifications: the safety interface layer is compiled away.
Partial evaluation can also be performed at run time, thus allowing dynamic software reconfiguration. Furthermore, the program analysis embedded in the partial evaluation process ensures predictability as the user can assess the degree of specialization.
All of the above experiments have been performed using Tempo, a partial evaluator for C developed in our group. Tempo has been applied in various other domains such as operating systems, networking, graphics, and scientific computation. Besides C, Tempo is used as a back-end for specializing Java programs using Harissa, a bytecode-to-C compiler that we have also developed. Similarly, Fortran and C++ programs have been specialized using translators to C.
Our goal is to relieve the programmer of efficiency concerns, letting him concentrate on the functionalities to implement in generic and high-level way. To this end, partial evaluation provides a systematic and automatic means to improve performance while retaining flexibility. Other uses of partial evaluation in software engineering include program understanding.
For more information, see: http://www.irisa.fr/compose
Please contact:
Renaud Marlet - INRIA/IRISA
Tel: +33 2 99 84 75 01
E-mail: marlet@irisa.fr