DIFFERENCE-LIST TRANSFORMATION FOR PROLOG

Difference-lists are terms that represent lists. The use of difference -lists can speed up most list-processing programs considerably. Prolog programmers routinely use ''difference-list versions'' of programs, b ut very little investigation has taken place into difference-list tran sformation. Thus, to most programmers it is either unknown that the us e of difference-lists is far from safe in all contexts, or else this f act is known but attributed to Prolog's infamous ''occur check problem .'' In this paper we study the transformation of list-processing progr ams into programs that use difference-lists. In particular we are conc erned with finding circumstances under which the transformation is saf e. We show that dataflow analysis can be used to determine whether the transformation is applicable to a given program, thereby allowing for automatic transformation. We prove that our transformation preserves strong operational equivalence.