Improving CPS-based partial evaluation: writing cogen by hand

Abstract

It is well-known that self-applicable partial evaluation can be used to generate compiler generators: cogen = mix(mix;mix), where mix is the specializer (partial evaluator) . However, writing cogen by hand gives several advantages: (1) Contrasting to when writing a self-applicable mix, one is not restricted to write cogen in the same language as it treats [HL91]. (2) A handwritten cogen can be more efficient than a cogen generated by self-application; in particular, a handwritten cogen typically performs no (time consuming) environment manipulations whereas one generated by self-application does. (3) When working in statically typed languages with user defined data types, the self-application approach requires encoding data type values [Bon88, Lau91, DNBV91], resulting in relatively inefficient (cogen-generated) compilers that spend much of their time on coding and decoding. By writing cogen by hand, the coding problem is eliminated [HL91, BW93]. Specializers written in continuation p...