A syntactic approach to program transformations
Zena M. Ariola · 1991
Kid, a language for expressing compiler optimizations for functional languages is introduced. The language is λ-calculus based but treats let-blocks as first class objects. Let-blocks and associated rewrite rules provide the basis to capture the sharing of subexpressions precisely. The language goes beyond λ-calculus by including I-structures which are essential to express efficient translations of list and array comprehensions. A calculus and a parallel interpreter for Kid are developed. Many commonly known program transformations are also presented. A partial evaluator for Kid is developed and a notion of correctness of Kid transformations based on the syntactic structure of terms and printable answers is presented.