TY - JOUR
T1 - Automatic mode inference for logic programs
AU - Debray, Saumya K.
AU - Warren, David S.
N1 - Funding Information:
*This work was supported in part by the National Science Foundation DC%8407688. $This is a revised version of a paper presented at the Third Symposium on Logic Programming, Lake City, Utah, Sept. 1986. Address correspondence to Saumya K. Debray, Department Arizona, Tucson, AZ 85721. Received 15 May 1987; accepted 15 October 1987.
PY - 1988/9
Y1 - 1988/9
N2 - In general, logic programs are undirected, i.e., there is no concept of "input" and "output" arguments to a procedure. An argument may be used either as an input or as an output argument, and programs may be executed either in a "forward" direction or in a "backward" direction. However, it is often the case that in a given program, a predicate is used with some of its arguments used consistently as input arguments and others as output arguments. Such mode information can be used by a compiler to effect various optimizations. This paper considers the problem of automatically inferring the models of the predicates in a program. The dataflow analysis we use is more powerful than approaches relying on syntactic characteristics of programs. Our work differs from that of Mellish in that (1) we give a sound and efficient treatment of variable aliasing in mode inference; (2) by propagating instantiation information using state transformations rather than through dependencies between variables, we achieve greater precision in the treatment of unification, e.g. through =/2; and (3) we describe an efficient implementation based on the dynamic generation of customized mode interpreters. Several optimizations to improve the performance of the mode inference algorithm are described, as are various program optimizations based on mode information.
AB - In general, logic programs are undirected, i.e., there is no concept of "input" and "output" arguments to a procedure. An argument may be used either as an input or as an output argument, and programs may be executed either in a "forward" direction or in a "backward" direction. However, it is often the case that in a given program, a predicate is used with some of its arguments used consistently as input arguments and others as output arguments. Such mode information can be used by a compiler to effect various optimizations. This paper considers the problem of automatically inferring the models of the predicates in a program. The dataflow analysis we use is more powerful than approaches relying on syntactic characteristics of programs. Our work differs from that of Mellish in that (1) we give a sound and efficient treatment of variable aliasing in mode inference; (2) by propagating instantiation information using state transformations rather than through dependencies between variables, we achieve greater precision in the treatment of unification, e.g. through =/2; and (3) we describe an efficient implementation based on the dynamic generation of customized mode interpreters. Several optimizations to improve the performance of the mode inference algorithm are described, as are various program optimizations based on mode information.
UR - http://www.scopus.com/inward/record.url?scp=0024085102&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0024085102&partnerID=8YFLogxK
U2 - 10.1016/0743-1066(88)90010-6
DO - 10.1016/0743-1066(88)90010-6
M3 - Article
AN - SCOPUS:0024085102
SN - 0743-1066
VL - 5
SP - 207
EP - 229
JO - The Journal of Logic Programming
JF - The Journal of Logic Programming
IS - 3
ER -