Exploiting Efficient Control and Data Structures in Logic Programs

R Yang, S Gregory

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)


One of the distinguishing features of declarative languages is the separation of control and logic. Ideally, this allows us to improve the efficiency of an algorithm by changing only the control but not the logic. In this work, we investigate new control strategies and data structures in logic programs. Our main focus is on logic programs which contain dependent non-determinate computation. We propose a new type of finite domain variables, which allow any kind of compound terms in their domain. A compound term in the domain may contain unbound variables which can also become domain variables, leading to nested domain variables. With nested domain variables, we can represent the Cartesian product of several domains as a tree structure. That is, disjunctive constraints stores can be constructed as a nested domain. The consistency of a nested domain can then be checked simultaneously by different parts of computations. Two forms of lookahead are used to perform the consistency checking: deep lookahead and shallow lookahead. It is hoped that, with our lookahead techniques and nested domains, many unnecessary or-branches can be pruned at an early stage. We have tested our ideas by an experimental implementation under SICStus Prolog, and obtained very encouraging results.
Translated title of the contributionExploiting Efficient Control and Data Structures in Logic Programs
Original languageEnglish
Title of host publication4th International Symposium on Practical Aspects of Declarative Languages, PADL 2002, Portland, Oregon, 19-20 January
Pages318 - 331
Number of pages14
ISBN (Print)354043092X
Publication statusPublished - Jan 2002

Bibliographical note

Other: http://www.cs.bris.ac.uk/Publications/pub_info.jsp?id=2000286. Lecture Notes in Computer Science 2257

Fingerprint Dive into the research topics of 'Exploiting Efficient Control and Data Structures in Logic Programs'. Together they form a unique fingerprint.

Cite this