Difference-list transformation for Prolog

Kim Marriott, Harald Søndergaard

Research output: Contribution to journalArticleResearchpeer-review

7 Citations (Scopus)

Abstract

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
Volume11
Issue number2
DOIs
Publication statusPublished - 1 Jun 1993

Keywords

  • Logic Programs
  • Program Analysis
  • Program Optimization

Cite this

Marriott, Kim ; Søndergaard, Harald. / Difference-list transformation for Prolog. In: New Generation Computing. 1993 ; Vol. 11, No. 2. pp. 125-157.
@article{250f71679c8f4c37a2e31a8fe5b12198,
title = "Difference-list transformation for Prolog",
abstract = "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.",
keywords = "Logic Programs, Program Analysis, Program Optimization",
author = "Kim Marriott and Harald S{\o}ndergaard",
year = "1993",
month = "6",
day = "1",
doi = "10.1007/BF03037156",
language = "English",
volume = "11",
pages = "125--157",
journal = "New Generation Computing",
issn = "0288-3635",
publisher = "Springer-Verlag London Ltd.",
number = "2",

}

Difference-list transformation for Prolog. / Marriott, Kim; Søndergaard, Harald.

In: New Generation Computing, Vol. 11, No. 2, 01.06.1993, p. 125-157.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Difference-list transformation for Prolog

AU - Marriott, Kim

AU - Søndergaard, Harald

PY - 1993/6/1

Y1 - 1993/6/1

N2 - 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.

AB - 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.

KW - Logic Programs

KW - Program Analysis

KW - Program Optimization

UR - http://www.scopus.com/inward/record.url?scp=24644513563&partnerID=8YFLogxK

U2 - 10.1007/BF03037156

DO - 10.1007/BF03037156

M3 - Article

VL - 11

SP - 125

EP - 157

JO - New Generation Computing

JF - New Generation Computing

SN - 0288-3635

IS - 2

ER -