Higher-order Transformations and Type Simulations

We examine higher-order program transformations in the context of a typed, pattern-directed, higher-order, lazy functional language. We introduce the notions of higher-order accumulation and type simulation as transformational techniques. Our main illustration of these techniques concerns the transformation of a description of a small programming language into a code generator. In this example we show how our techniques tackle important questions regarding the circumstances under which data, in a functional program, can be destructively updated with impunity.