Abstract
We propose in this paper a type inference system for extracting inheritance hierarchies from Prolog programs. The inferred types define a superset of the denotation of the program, and a subset of the least fixed point of the tuple-distributive closure of the immediate consequence operator TP (i.e., 1fp(α(TP)).
The types are described by means of their relationships with other types of the program rather than by their instances. Thus, we infer a collection of not resolved formulas that describe set relationships between the terms appearing in the program. We have nevertheless defined an interpretation function from the type relations into the Herbrand universe that allows us to actually compute the set of ground terms associated with each type.
The inferred type relations are used for defining two inheritance hierarchies. The first one is obtained through a formal comparison of the type relations, and is independent of the program's data, whereas the second one is obtained through the comparison of the interpretations of the types and is directly dependent of the program's data. These two hierarchies provide a scheme of the program that enables a better understanding of the underlying structure. Their comparison may outline some errors or incompleteness of the program.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Bruynooghe and G. Janssens. An instance of abstract interpretation integrating type and mode inferencing. In Proceedings of the Fifth International Conference and Symposium en Logic Programming, pages 669–683, 1988.
A. Colmerauer. An introduction to PrologIII. Communications of the ACM, 33(7):69–90, July 1990.
B. Cox. Object-oriented technology and the software industrial revolution ... necessary but sufficient. In OOPSLA '89, pages 510–522, 1989.
L. Cardelli and P. Wegner. On understanding types, data abstraction, and polymorphism. Computing Surveys, 17(4):471–522, December 1985.
R. Dietrich and F. Hagl. A polymorphic type system for Prolog. In Springer-Verlag, editor, 2nd European Symposium on Programming, pages 79–93, 1988.
S. Danforth and C. Tomlinson. Type theories and object-oriented programming. ACM Computing surveys, 20(1):29–72, March 1988.
P.W. Dart and J. Zobel. A regular type language for logic programs. In Frank Pfenning, editor, Types in Logic Programming, pages 157–187, 1992.
H. Gallaire. Boosting logic programming: In 4th ICLP, pages 962–988, 1987.
N. Heintze and J. Jaffar. Semantic types for logic programs. In Frank Pfenning, editor, Types in Logic Programming, pages 141–151, 1992.
T. Kanamori and T. Kawamura. Abstract interpretation based on OLDT resolution. Journal of Logic Programming, 15:1–30, 1993.
J.W. Lloyd. Foundations of Logic Programming. Springer-Verlag, 1987.
B. Legeard and M. Rueher. A scheme for prototyping in Prolog (in french). TSI, 8(5):423–438, 1989.
B. Meyer. Object-Oriented Software Construction. Prentice Hall, 1988.
P. Mishra. Towards a theory of types in Prolog. In International Logic Programming Symposium, Atlantic City, pages 289–298, 1984.
C. Pyo and U.S. Reddy. Inference of polymorphic types for logic programs. In Logic Programming — Proceedings of the North American Conference, pages 1115–1132, 1989.
C. Solnon. A type relations inference system for Prolog — application to the generation of object oriented models. Thesis (in french), I3S / University of Nice — Sophia Antipolis, Bât. 4, 250 av. A. Einstein, 06560 Valbonne, France, 1993.
H. Tamaki and T. Sato. Unfold/fold transformation of logic programs. In 2nd ICLP, pages 127–138, 1984.
E. Yardeni and E. Shapiro. A type system for logic programs. In E. Shapiro, editor, Concurrent Prolog — Collected papers — Vol. 2, pages 211–244. MIT Press Series in Logic Programming, 1987.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Solnon, C., Rueher, M. (1993). Extracting inheritance hierarchies from Prolog programs: A system based on the inference of type relations. In: Voronkov, A. (eds) Logic Programming and Automated Reasoning. LPAR 1993. Lecture Notes in Computer Science, vol 698. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56944-8_63
Download citation
DOI: https://doi.org/10.1007/3-540-56944-8_63
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56944-2
Online ISBN: 978-3-540-47830-0
eBook Packages: Springer Book Archive