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 MetaOCaml 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 speed-ups if online partial evaluation with algebraic simplifications is used for the elimination of interpretation overhead and optimization of code expressions.