TY - GEN
T1 - Detection and optimization of functional computations in Prolog
AU - Debray, Saumya K.
AU - Warren, David S.
N1 - Publisher Copyright:
© 1986, Springer-Verlag.
PY - 1986
Y1 - 1986
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85034449796&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85034449796&partnerID=8YFLogxK
U2 - 10.1007/3-540-16492-8_97
DO - 10.1007/3-540-16492-8_97
M3 - Conference contribution
AN - SCOPUS:85034449796
SN - 9783540164920
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 490
EP - 504
BT - 3rd International Conference on Logic Programming - Imperial College of Science and Technology, Proceedings
A2 - Shapiro, Ehud
PB - Springer-Verlag
T2 - 3rd International Conference on Logic Programming, ICLP 1986
Y2 - 14 July 1986 through 18 July 1986
ER -