On the completeness of naive memoing in Prolog |
| |
Authors: | Suzanne Wagner Dietrich Changguan Fan |
| |
Affiliation: | (1) Department of Computer Science and Engineering, College of Engineering and Applied Sciences, Arizona State University, Box 875406, 85287-5406 Tempe, AZ, USA |
| |
Abstract: | Memoing is often used in logic programming to avoid redundant evaluation of similar goals, often on programs that are inherently
recursive in nature. The interaction between memoing and recursion, however, is quite complex. There are several top-down
evaluation strategies for logic programs that utilize memoing to achieve completeness in the presence of recursion. This paper’s
focus, however, is on the use ofnaive memoing in Prolog. Using memoingnaively in conjunction with recursion in Prolog may not produce expected results. For example, adding naive memoing to Prolog’s evaluation
of a right-recursive transitive closure may be incomplete, whereas adding naive memoing to Prolog’s evaluation of a left-recursive
transitive closure may be terminating and complete. This paper examines the completeness of naive memoing in linear-recursive,
function-free logic programs evaluated with Prolog’s top-down evaluation strategy. In addition, we assume that the program
is definite and safe, having finite base relations and exactly one recursive predicate. The goal of the paper is a theoretical
study of the completeness of naive memoing and recursion in Prolog, illustrating the limitations imposed even for this simplified
class of programs. The naive memoing approach utilized for this study is based on extension tables, which provide a memo mechanism
with immediate update view semantics for Prolog programs, through a source transformation known as ET. We introduce the concept
ofET-complete, which refers to the completeness of the evaluation of a query over a Prolog program that memos selected predicates through
the ET transformation. We show that left-linear recursions defined by a single recursive rule are ET-complete. We generalize
the class of left-linear recursions that are ET-complete by introducing pseudo-left-linear recursions, which are also defined
by a single linear recursive rule. To add left-linear recursions defined bymultiple linear recursive rules to the class of ET-complete recursions, we present a left-factoring algorithm that converts left-linear
recursions defined by multiple recusive rules into pseudo-left-linear recursions defined by a single recursive rule. Based
on these results, the paper concludes by identifying research directions for expanding the class of Prolog programs to be
examined in future work.
This work was partially supported by the National Science Foundation under Grant CCR-9008737.
Suzanne Wagner Dietrich, Ph.D.: She is an Associate Professor in the Department of Computer Science and Engineering at Arizona State University. Her research
emphasis is on the evaluation of declarative logic programs especially in the context of deductive databases, including materialized
view maintenance and condition monitoring in active deductive databases. More recently, her research interests include the
integration of active, object-oriented and deductive databases as well as the application of this emerging database technology
to various disciplines such as software engineering. She received the B. S. degree in computer science in 1983 from the State
University of New York at Stony Brook, and as the recipient of an Office of Naval Research Graduate Fellowship, earned her
Ph.D. degree in computer science at Stony Brook in 1987.
Changguan Fan, M.S.: He is a Ph.D. candidate in the Department of Computer Science and Engineering at Arizona State University and a software
engineer at the Regenisys Corporation in Scottsdale, AZ. His research interests include the evaluation of logic programs,
deductive database systems and database management systems. He received his B.S. in Computer Science from the Shanghai Institute
of Railway Technology, Shanghai, China in 1982 and his M.S. in the Department of Computer Science and Engineering at Arizona
State University in 1989. |
| |
Keywords: | Memoing Logic Programming Recursion |
本文献已被 SpringerLink 等数据库收录! |
|