Merging Objects and Logic Programming: Relational Semantics

Hervé GallaireAAAI 1986

Abstract

This paper introduces POL (Programming in Object and Logic), a system that integrates object-oriented features into Prolog by treating method calls as relational predicates rather than functional procedures. By introducing "success/failure" semantics and backtrackable inheritance, it enables powerful associative retrieval where even the object being queried can be a variable.

Introduction

This 1986 paper from the AAAI proceedings represents a landmark in the history of knowledge representation. During an era when the AI community was divided between the procedural strengths of Object-Oriented Programming (OOP) and the declarative elegance of Logic Programming (LP), Herve Gallaire proposed a way to marry the two without compromising the core principles of either. The result was POL, a system that bridges the gap between structured hierarchies and declarative inference.

The Integration Challenge

In the mid-1980s, developers sought to combine the structured hierarchies of objects (found in languages like Smalltalk) with the inference capabilities of Prolog. Most contemporary attempts merely "bolted" OOP onto Prolog using a functional "call/return" mechanism. Gallaire identified this as a missed opportunity, arguing for a truly relational semantics for objects—one where method calls could fail, backtrack, and return multiple results, mirroring the behavior of standard Prolog predicates.

The POL System: Methods and Innovations

POL is designed as a superset of Prolog, introducing several technical innovations to facilitate this integration:

  • Relational Method Calls: Using the syntax X:Y (where X is an object and Y is a method), POL follows a success/failure paradigm. If a method fails to find a solution, the system backtracks to explore other branches of the inheritance tree.
  • Variable Object Calls: POL allows queries where the object itself is an uninstantiated variable (e.g., ?- X:topic(logic)). The system searches the entire hierarchy to find all objects satisfying the condition.
  • Specialized Method Types: To manage multiple inheritance and non-monotonic reasoning, Gallaire introduced Default Methods (executing only if standard methods fail) and Deterministic Methods (acting as a global cut to prune the search space).
  • Higher-Order Operators: Predicates like laocwc and dfaor enable efficient set-oriented operations, such as aggregating data across multiple objects within the logic framework.

Illustrative Framework

As a theoretical and architectural work, the paper demonstrates its logic through an illustrative hierarchy involving researchers, students, and staff. This structure highlights how POL handles complex inheritance paths and multiple inheritance.

A sample object hierarchy in POL, illustrating multiple inheritance.

A central insight of the paper is the conceptualization of inheritance as a search process rather than a simple lookup. In a multiple inheritance lattice, POL can explore multiple paths to yield multiple valid answers. This approach effectively unifies AI "frames" with database "entities and relationships," turning an object hierarchy into a queryable relational database.

Examples of relational queries and their resolution logic in the POL system.

The introduction of deterministic methods provides a mechanism for local and global control, allowing programmers to selectively prune the "search explosion" inherent in logic programming.

Results and Limitations

The paper successfully establishes a formal syntax and semantics for a unified Object-Logic language, demonstrating powerful associative retrieval capabilities. The "Default" method mechanism also provides a clean logical framework for handling exceptions in inheritance (e.g., "all birds fly, except penguins") within a strictly logical context.

However, the author acknowledges several challenges:

  • Implementation Complexity: Efficiently implementing variable object calls in complex lattices remains difficult.
  • Sequential Nature: The system does not address parallel execution, which was a burgeoning interest in the 1980s.
  • Performance Metrics: The paper lacks quantitative performance comparisons against standard Prolog or OOP systems.

Gallaire concludes that POL represents a significant step toward a "better breed of logic languages" capable of meeting the demands of semantic data modeling and database integration.

Summary updated

BibTeX
@inproceedings{gallaire1986merging,
  author = {Hervé Gallaire},
  title = {{Merging Objects and Logic Programming: Relational Semantics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}

Loading related content...

Figure