Combining partial evaluation and staged interpretation in the implementation of domain-specific languages

We propose a combination of partial evaluation and staged interpretation with MetaOCaml for rapid prototyping of domain-specific languages. Interpretation is an easy way to implement such languages. MetaOCaml can eliminate the overhead of interpretation at run time, if the interpreter is written in a staged form, i.e., takes the source program separate from the input data in a first stage. Partial evaluation of the source program with values known at compile time can further improve the target code performance. Additional aggressive optimizations are possible due to the absence of general recursion. Algebraic simplifications can even achieve binding-time improvements during the online partial evaluation. Our approach both saves the application programmer completely from binding-time considerations and exploits staged interpretation with MetaOCaml for target code generation. The example domain presented in this paper is image processing, in which the domain-specific language permits the specification of convolution matrices, summations, case distinctions and non-local pixel accesses. All expressions known at compile time are simplified and all remaining expressions are turned into MetaO-Caml code parts, which are combined to form the compiled application program. The example specifications deal with filtering by convolution and iterations in a series of images for wave effects and temperature distribution. The experimental results show significant speedups if online partial evaluation with algebraic simplifications is used for elimination of interpretation overhead and optimization of code expressions. Key words: binding-time improvement, compilation, domain-specific languages, meta-programming, partial evaluation, staged interpretatio