Tutorial on Program Specialisation
John Wylie Lloyd · 1995
We give a broad and general introduction to program specialisation, including motivating examples for partial deduction ([8]), partial evaluation of Prolog ([16]) and other forms of specialisation, such as functor elimination and generation of most specific programs. We then provide some insight into the foundations of partial deduction, including correctness and completeness conditions from [12]. We illustrate ways in which they can be ensured ([1])As a main focus of the tutorial, we elaborate the issues related to the control of partial deduction. We briefly discuss off-line control, where program annotations guide the transformation ([15]). For on-line control, we motivate and illustrate the distinction between local and global control in partial deduction algorithms, point out some trade-offs and briefly sketch a generic approach based on well-founded orderings ([13], [14]), and an approach based on characteristic treesWe then discuss some specific problems related to specialisation of metaprograms ([11]) and indicate some solutions. We further point out relations between partial deduction and program termination ([2]), abstract interpretation ([5], [10]), unfold/fold transformation and compile-time optimisation. We give a brief overview of existing systems ([4], [16], [15], [10], [6]) and successful applications ([17], [9], [3], [11]). We end with the presentation of some open problems