Abstract
The debuggers of Ref. 11) and most of their derivatives are of themeta-interpreter type. The computation of the debugger tracks the computation of the program to be diagnosed at the level of procedure call. This is adequate if the intuitive understanding of the programmer is in terms of procedure calls; as is indeed the case in Prolog.
InLDL however, while the semantics of the language are described in a bottom-up, fixpoint model of computation,8) theactual execution of a program is a complex sequence of low-level procedure calls determined (and optimized) by the compiler. Consequently, a trace of these procedure calls is of little use to the programmer. Further, one cannot “execute” anLDL program as if it was a Prolog program; the program may simply not terminate in its Prolog reading and severalLDL constructs have no obvious Prolog counterparts.
We identify the origin of a fault in theLDL program by a top-down, query/subquery approach. The basic debugger, implemented in Prolog, is a shell program between the programmer and theLDL program: it poses queries and uses the results to drive the interaction with the user. It closely resembles the one presented in Ref. 11). The core of a more sophisticated debugger is presented as well.
Several concepts are introduced in order to quantify debugging abilities. One is that of agenerated interpretation, in which the structureless intended interpretation of Ref. 11) is augmented with causality. Another is the (idealized) concept of areliable oracle. We show that given an incorrect program and a reliable oracle which uses a generated interpretation, a cause for the fault will be found in finitely many steps. This result carries over to the more sophisticated debugger.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Beeri, C., Naqvi, S., Shmueli, O. and Tsur, S., “Set Constructors in a Logic Database Language,”Journal of Logic Programming, 10, 3–4, pp. 181–232, April/May 1991.
Chimenti, D. and Gamboa, R., “The SALAD Cookbook; A User/Programmers’ Guide,”MCC Technical Report, ACT-ST-346-89.
Dershowitz, N. and Lee, Y., “Deductive Debugging,” inProceedings Fourth IEEE Symposium on Logic Programming, San Francisco, California, pp. 298–306, Aug. 1987.
Drabent, W., Nadjim-Tehrani, S. and Maluszynski, J., “Algorithmic Debugging with Assertions,” inProceedings Workshop on Meta-Programming in Logic Programming, University of Bristol, June 1988.
Ferrand, G., “Error Diagnosis in Logic Programming: An Adaptation of E. Y. Shapiro’s Method,”Reporte de Recherche, 375, INRIA, France, 1985.
Lloyd, J. W., “Declarative Error Diagnosis,”New Generation Computing, 5, pp. 133–154, 1987.
Lloyd, J. W.,Foundations of Logic Programming (2nd Edition), Springer-Verlag, 1987.
Naqvi, S. and Tsur, S.,A Logical Language for Data and Knowledge Bases, W. H. Freeman, 1989.
Naish, L., “Declarative Error Diagnosis of Missing Facts,”Technical Report, 88/9, Department of Computer Science, University of Melbourne.
Pereira, L. M., “Rational Debugging in Logic Programming,” inProceedings Third International Conference on Logic Programming, London, England, Springer-Verlag, LNCS 225, pp. 203–210, July 1986.
Shapiro, E. Y.,Algorithmic Program Debugging, MIT Press, Cambridge, Massachusettes, 1983.
Shmueli, O. and Tsur, S., “Logical Diagnosis of LDL Programs,” inProceedings Seventh International Conference on Logic Programming, Jerusalem, Israel, pp. 112–129, June 1990.
Sterling, L. and Shapiro, E. Y.,The Art of Prolog, MIT Press, Cambridge, Massachusettes, 1986.
Author information
Authors and Affiliations
Additional information
Research partially supported by the Fund for Promotion of Research at the Technion.
About this article
Cite this article
Shmueli, O., Tsur, S. Logical diagnosis ofLDL programs. New Gener Comput 9, 277–303 (1991). https://doi.org/10.1007/BF03037166
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF03037166