Detection and optimization of functional computations in Prolog

Saumya K. Debray, David S. Warren

Research output: Chapter in Book/Report/Conference proceedingConference contribution

26 Scopus citations


While the ability to simulate nondeterminism and return multiple outputs for a single input is a powerful and attractive feature of Prolog, it is expensive both in time and space. Since Prolog programs are very often functional, i.e. do not produce more than one distinct output for a single input, this overhead is especially undesirable. This paper describes how a program may be analyzed statically to determine which literals and predicates are functional, and how the program may then be optimized using this information. Our notion of “functionality” subsumes the notion of “determinacy” that has been considered by various researchers. Our algorithms are less reliant on features such as cut, and thus extend more easily to parallel execution strategies than others that have been proposed.

Original languageEnglish (US)
Title of host publication3rd International Conference on Logic Programming - Imperial College of Science and Technology, Proceedings
EditorsEhud Shapiro
Number of pages15
ISBN (Print)9783540164920
StatePublished - 1986
Event3rd International Conference on Logic Programming, ICLP 1986 - London, United Kingdom
Duration: Jul 14 1986Jul 18 1986

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume225 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd International Conference on Logic Programming, ICLP 1986
Country/TerritoryUnited Kingdom

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Detection and optimization of functional computations in Prolog'. Together they form a unique fingerprint.

Cite this