The Role of Trace Abstractions in Program Specialisation Algorithms

We summarise the role of concepts such as neighbourhoods, characteristic trees, characteristic atoms, and trace terms in the design of program specialisation algorithms. These are techniques, developed in different programming languages, of describing abstractions that can be termed the “shape” of computations. They have been introduced into program specialisation algorithms mainly for the control of generalisation and polyvariance (the number of different specialised versions of a procedure). We argue that these methods can play a more fundamental role and point the way towards language-independent algorithms for program specialisation, which rely only only a general notion of a program trace. Categories and Subject Descriptors: I.2.2 [Articial Intelligence]: Program Transformation.