Journal of the ACM Bibliography

Abstract

We propose a novel formalism, called Frame Logic (abbr., F-logic), that accounts in a clean and declarative fashion for most of the structural aspects of object-oriented and frame-based languages. These features include object identity, complex objects, inheritance, polymorphic types, query methods, encapsulation, and others. In a sense, F-logic stands in the same relationship to the object-oriented paradigm as classical predicate calculus stands to relational programming. F-logic has a model-theoretic semantics and a sound and complete resolution-based proof theory. A small number of fundamental concepts that come from object-oriented programming have direct representation in F-logic; other, secondary aspects of this paradigm are easily modeled as well. The paper also discusses semantic issues pertaining to programming with a deductive object-oriented language based on a subset of F-logic. Copyright 1995 by ACM, Inc.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Categories and Subject Descriptors: H.2.1 [Database Management]: Logical Design -- query languages; I.2.3 [Artificial Intelligence]: Deduction and Theorem Proving; F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic

General Terms: Languages, Theory

Additional Key Words and Phrases: Object-oriented programming, frame-based languages, deductive databases, logic programming, semantics, proof theory, typing, nonmonotonic inheritance

Selected papers that cite this one

• A. Bossi, M. Bugliesi, M. Gabbrielli, G. Levi, and M. C. Meo. Differential logic programs: Programming methodologies and semantics. Science of Computer Programming, 27(3):217-262, November 1996.

• Jan Van den Bussche, Dirk van Gucht, and Gottfried Vossen. Reflective programming in the relational algebra. Journal of Computer and System Sciences, 52(3):537-549, June 1996.

• Jan Van den Bussche and Jan Paredaens. The expressive power of complex values in object-based data models. Information and Computation, 120(2):220-236, 1 August 1995.

• Luca Cabibbo. The expressive power of stratified logic programs with value invention. Accepted for publication in Information and Computation. Final manuscript received for publication February 19, 1998.

Selected references

• Hassan Aït-Kaci and Roger Nasr. LOGIN: A logic programming language with built-in inheritance. Journal of Logic Programming, 3(3):185-215, October 1986.

• Hassan Aït-Kaci and Andreas Podelski. Towards a meaning of LIFE. Journal of Logic Programming, 16(3-4):195-234, August 1993.

• Robert Anderson and W. W. Bledsoe. A linear format for resolution with merging and a new technique for establishing completeness. Journal of the ACM, 17(3):525-534, July 1970.

• Malcolm P. Atkinson, François Bancilhon, David J. DeWitt, Klaus R. Dittrich, David Maier, and Stanley B. Zdonik. The object-oriented database system manifesto. In Won Kim and Jean-Marie Nicolas and Shojiro Nishio, editors, Deductive and Object-Oriented Databases, Proceedings of the First International Conference on Deductive and Object-Oriented Databases (DOOD'89), pages 223-240, Kyoto research Park, Kyoto, Japan, 4-6 December 1989. North-Holland/Elsevier Science Publishers, 1990.

• François Bancilhon. Object-oriented database systems. In Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 152-162, Austin, Texas, 21-23 March 1988.

• Jay Banerjee, Won Kim, and Kyung-Chang Kim. Queries in object-oriented databases. In Proceedings of the Fourth International Conference on Data Engineering, pages 31-38, Los Angeles, California, USA, 1-5 February 1988. IEEE Computer Society.

• Catriel Beeri. Formal models for object oriented databases. In Won Kim and Jean-Marie Nicolas and Shojiro Nishio, editors, Deductive and Object-Oriented Databases, Proceedings of the First International Conference on Deductive and Object-Oriented Databases (DOOD'89), pages 405-430, Kyoto research Park, Kyoto, Japan, 4-6 December 1989. North-Holland/Elsevier Science Publishers, 1990.

• Catriel Beeri and Raghu Ramakrishnan. On the power of magic. Journal of Logic Programming, 10(1/2/3-4):255-299, January 1991.

• Stefan Brass and Udo W. Lipeck. Semantice of inheritance in logical object specifications. In Claude Delobel and Michael Kifer and Yoshifumi Masunga, editors, Deductive and Object-Oriented Databases, Second International Conference, DOOD'91, volume 566 of Lecture Notes in Computer Science, pages 411-430, Munich, Germany, 16-18 December 1991. Springer.

• Luca Cardelli. A semantics of multiple inheritance. Information and Computation, 76(2/3):138-164, February/March 1988.

• Weidong Chen, Michael Kifer, and David Scott Warren. HILOG: A foundation for higher-order logic programming. Journal of Logic Programming, 15(3):187-230, February 1993.

• Weidong Chen and David Scott Warren. C-logic of complex objects. In Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 369-378, Philadelphia, Pennsylvania, 29-31 March 1989.

• William R. Cook, Walter L. Hill, and Peter S. Canning. Inheritance is not subtyping. In Conference Record of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, pages 125-135, San Francisco, California, January 1990.

• Richard Fikes and Tom Kehler. The role of frame-based representation in reasoning. Communications of the ACM, 28(9):904-920, September 1985.

• Allen Van Gelder. The alternating fixpoint of logic programs with negation. In Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 1-10, Philadelphia, Pennsylvania, 29-31 March 1989.

• Allen Van Gelder, Kenneth A. Ross, and John S. Schlipf. The well-founded semantics for general logic programs. Journal of the ACM, 38(3):620-650, July 1991.

• Setrag Khoshafian and George P. Copeland. Object identity. In Norman K. Meyrowitz, editor, Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'86), pages 406-416, Portland, Oregon, 1986. SIGPLAN Notices, 21(11), November 1986.

• Michael Kifer and V. S. Subrahmanian. Theory of generalized annotated logic programming and its applications. Journal of Logic Programming, 12(3-4):335-367, 1992.

• Michael Kifer and James Wu. A first-order theory of types and polymorphism in logic programming. In Proceedings, Sixth Annual IEEE Symposium on Logic in Computer Science, pages 310-321, Amsterdam, The Netherlands, 15-18 July 1991. IEEE Computer Society Press.

• Michael Kifer and James Wu. A logic for object-oriented logic programming (Maier's O-logic revisited). In Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 379-393, Philadelphia, Pennsylvania, 29-31 March 1989.

• Won Kim, Jay Banerjee, Hong-Tai Chou, Jorge F. Garza, and Darrell Woelk. Composite object support in an object-oriented database system. In Norman Meyrowitz, editor, Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'87), pages 118-125, Orlando, Florida, 4-8 October 1987. SIGPLAN Notices, 22(12), December 1987.

• Phokion G. Kolaitis and Christos H. Papadimitriou. Why not negation by fixpoint? In Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 231-239, Austin, Texas, 21-23 March 1988.

• Gabriel M. Kuper and Moshe Y. Vardi. A new approach to database logic. In Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pages 86-96, Portland, Oregon, 25-27 March 1984.

• E. Laenens and D. Vermier. A fixpoint semantics for ordered logic. Journal of Logic and Computation, 1(2):159-185, December 1990.

• Dale Miller. A logical analysis of modules in logic programming. Journal of Logic Programming, 6(1-2):79-108, January/March 1989.

• John C. Mitchell. Toward a typed foundation for method specialization and inheritance. In Conference Record of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, pages 109-124, San Francisco, California, January 1990.

• Teodor C. Przymusinski. Every logic program has a natural stratification and an iterated least fixed point model. In Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 11-21, Philadelphia, Pennsylvania, 29-31 March 1989.

• Kenneth A. Ross. Relations with relation names as arguments: Algebra and calculis. In Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 346-353, San Diego, California, 2-4 June 1992.

• Jeffrey D. Ullman. Database theory: Past and future. In Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 1-10, San Diego, California, 23-25 March 1987.

• David S. Warren. Memoing for logic programs. Communications of the ACM, 35(3):93-111, March 1992.

Shortcuts: