TY - GEN
T1 - Optimizing almost-tail-recursive Prolog programs
AU - Debray, Saumya K.
N1 - Publisher Copyright:
© 1985, Springer-Verlag.
PY - 1985
Y1 - 1985
N2 - There is a wide class of problems for which the natural Prolog specification, as a top-down, recursive computation, is significantly less efficient than an iterative bottom-up version. However, the transformation from the top-down specification to the bottom-up implementation is not always obvious, principally due to problems with nondeterminism and the order in which variables get bound — problems which do not arise in comparable situations in functional languages. This paper illustrates how these problems can be handled in certain cases, and the transformation mechanized, using algebraic properties of operators such as associativity and distributivity. The resulting programs are tail-recursive, and hence significantly more efficient in space usage, with no deterioration in execution speed.
AB - There is a wide class of problems for which the natural Prolog specification, as a top-down, recursive computation, is significantly less efficient than an iterative bottom-up version. However, the transformation from the top-down specification to the bottom-up implementation is not always obvious, principally due to problems with nondeterminism and the order in which variables get bound — problems which do not arise in comparable situations in functional languages. This paper illustrates how these problems can be handled in certain cases, and the transformation mechanized, using algebraic properties of operators such as associativity and distributivity. The resulting programs are tail-recursive, and hence significantly more efficient in space usage, with no deterioration in execution speed.
UR - http://www.scopus.com/inward/record.url?scp=9944233625&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=9944233625&partnerID=8YFLogxK
U2 - 10.1007/3-540-15975-4_38
DO - 10.1007/3-540-15975-4_38
M3 - Conference contribution
AN - SCOPUS:9944233625
SN - 9783540159759
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 204
EP - 219
BT - Functional Programming Languages and Computer Architecture
A2 - Jouannaud, Jean-Pierre
PB - Springer-Verlag
T2 - 2nd International Conference on Functional Programming Languages and Computer Architecture, 1985
Y2 - 16 September 1985 through 19 September 1985
ER -