Program transformations in terms of abstract syntax trees compromise referential integrity by introducing variable capture. Variable capture occurs when in the generated program a variable declaration accidentally shadows the intended target of a variable reference. Existing transformation systems either do not guarantee the avoidance of variable capture or impair the implementation of transformations. We present an algorithm called name-fix that automatically eliminates variable capture from a generated program by systematically renaming variables. name-fix is guided by a graph representation of the binding structure of a program, and requires name-resolution algorithms for the source language and the target language of a transformation. name-fix is generic and works for arbitrary transformations in any transformation system that supports origin tracking for names. We verify the correctness of name-fix and identify an interesting class of transformations for which name-fix provides hygiene. We demonstrate the applicability of name-fix for implementing capture-avoiding substitution, inlining, lambda lifting, and compilers for two domain-specific languages.
Additional Metadata
Keywords hygienic transformation, name binding, language workbenches
ACM PROGRAMMING LANGUAGES (acm D.3), Processors (acm D.3.4)
THEME Software (theme 1)
Publisher Springer
Persistent URL dx.doi.org/10.1007/978-3-662-44202-9_20
Conference European Conference on Object-Oriented Programming
Citation
Erdweg, S, van der Storm, T, & Dai, Y. (2014). Capture-avoiding and hygienic program transformations. In Proceedings of European Conference on Object-Oriented Programming 2014 (ECOOP 0) (pp. 489–514). Springer. doi:10.1007/978-3-662-44202-9_20