FHJ: A Formal Model for Hierarchical Dispatching and Overriding

Yanlin Wang, Haoyuan Zhang, Bruno C. d. S. Oliveira, Marco ServettoECOOP 2018 · DOI

TL;DR

This paper introduces FHJ, a formal model for handling unintentional method conflicts in multiple inheritance. It proposes "hierarchical dispatching" and "hierarchical overriding" to allow methods with the same name and signature from different, unrelated parent classes to coexist and be resolved unambiguously, preserving code reuse and extensibility.

What Problem Does This Paper Address?

Object-Oriented Programming (OOP) languages often face challenges with multiple inheritance, particularly when methods with the same name and signature are inherited from different parent classes. While "diamond inheritance" (conflicts from a common ancestor) has been extensively studied, "unintentional method conflicts" (conflicts from unrelated parents) pose a significant problem. Existing solutions are often inadequate, leading to compilation errors or forcing awkward workarounds that break modularity and extensibility. This paper aims to provide a formal and robust solution to these unintentional conflicts, allowing for more flexible and powerful multiple inheritance.

Methods

The paper introduces Featherweight Hierarchical Java (FHJ), a formal calculus inspired by Featherweight Java. FHJ addresses unintentional method conflicts through two key mechanisms:

  • Hierarchical Dispatching: This mechanism combines static and dynamic type information to resolve method calls. When a method call is potentially ambiguous due to multiple inheritance, the static type of the receiver (e.g., from an explicit cast) guides the dispatch to a specific inheritance branch, while the dynamic type ensures the most specific implementation within that branch is chosen. This is formalized through the mbody function, which orchestrates the lookup.
  • Hierarchical Overriding: This novel feature allows methods to be overridden on individual branches of the inheritance hierarchy, rather than requiring a single merge of all conflicting methods. This is denoted using an override keyword with a specific target interface (e.g., void draw() override Drawable). This preserves the independent extensibility of each branch.

The paper formalizes FHJ with syntax, typing rules, and small-step semantics, and proves its type soundness.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Distinguishing Intentional vs. Unintentional Conflicts: The paper clearly differentiates between "diamond inheritance" (where conflicts are often intentional and require merging) and "unintentional method conflicts" (where methods have different semantics and should ideally coexist).
  • The Power of Static and Dynamic Type Combination: Hierarchical dispatching highlights how a combination of static (compile-time) and dynamic (run-time) type information can resolve ambiguities that neither can solve alone.
  • Hierarchical Overriding for Granular Control: The introduction of hierarchical overriding provides a powerful mechanism for fine-grained control over inheritance, allowing developers to selectively refine behavior along specific inheritance paths without breaking other parts of the hierarchy.
  • Formalization as a Foundation: The formalization of FHJ provides a rigorous basis for understanding and implementing these complex inheritance features, ensuring type safety and preventing ambiguity.

Key Results

The paper presents a formal model (FHJ) that:

  • Accepts definitions with unintentional method conflicts.
  • Provides a mechanism for unambiguous method dispatching using hierarchical dispatching.
  • Supports hierarchical overriding, allowing individual branches to be refined.
  • Is proven to be type sound, ensuring that well-typed programs reduce to values without type errors.
  • A prototype interpreter in Scala is implemented to validate the model.

Limitations and Future Work

The authors acknowledge several areas for future work:

  • Orthogonal Features: Extending FHJ with features like primitive types, assignments, method overloading, covariant return types, and static dispatch.
  • Non-Orthogonal Extensions: Exploring more complex features like multiple hierarchical method overriding (where a single method can override multiple branches simultaneously) and supporting fields in multiple inheritance.
  • Loosening the Model: Investigating ways to relax the strictness of interface definitions, potentially allowing more flexibility similar to C++, while still ensuring type safety through checks at later stages (e.g., during upcasts).
  • Abstract Methods: While FHJ handles abstract methods, further exploration into how they interact with conflicts and overriding, especially in comparison to Java 8's behavior, is suggested.
  • State and Fields: Incorporating fields into the model, potentially by borrowing ideas from interface-based programming or exploring techniques used in languages like C++.

Summary updated

BibTeX
@inproceedings{wang2018fhj,
  author = {Yanlin Wang and Haoyuan Zhang and Bruno C. d. S. Oliveira and Marco Servetto},
  title = {{FHJ: A Formal Model for Hierarchical Dispatching and Overriding}},
  booktitle = {ECOOP},
  year = {2018},
  doi = {10.4230/lipics.ecoop.2018.20},
}
Figure