Difference-list transformation for Prolog

Kim Marriott, Harald Søndergaard

Research output: Contribution to journalArticleResearchpeer-review

7 Citations (Scopus)


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, but very little investigation has taken place into difference-list transformation. Thus, to most programmers it is either unknown that the use of difference-lists is far from safe in all contexts, or else this fact is known but attributed to Prolog's infamous "occur check problem." In this paper we study the transformation of list-processing programs into programs that use differencelists. In particular we are concerned with finding circumstances under which the transformation is safe. 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.

Original languageEnglish
Pages (from-to)125-157
Number of pages33
JournalNew Generation Computing
Issue number2
Publication statusPublished - 1 Jun 1993


  • Logic Programs
  • Program Analysis
  • Program Optimization

Cite this