A Pattern Calculus for Rule Languages: Expressiveness, Compilation, and Mechanization (Artifact)

Avraham Shinnar, Jérôme Siméon, Martin HirzelDagstuhl Artifacts Ser 2015 · OpenReview

TL;DR

This paper presents a formal, mechanized system for reasoning about three rule-based languages: CAMP, NRA, and NNRC. The artifact provides verified implementations and proofs of correctness for translations between these languages, including type system mechanization and complexity analysis, offering a robust foundation for understanding and building rule-based systems.

What Problem Does This Paper Address?

The paper addresses the challenge of formally verifying the correctness and understanding the expressiveness of rule-based languages. Rule languages are widely used in various domains, from databases to expert systems, but their complexity can make it difficult to guarantee their behavior, especially when dealing with nested structures and translations between different formalisms. The authors aim to provide a rigorous, machine-checked foundation for a family of rule languages, ensuring that translations preserve meaning and that type systems are sound.

Methods

The core of this work is the mechanization of three rule languages – CAMP (Calculus for Aggregating Matching Patterns), NRA (Nested Relational Algebra), and NNRC (Named Nested Relational Calculus) – using the Coq proof assistant. This involves:

  • Formal Definitions: Defining the syntax and semantics of each language within Coq.
  • Translations: Implementing and proving the correctness of translations between CAMP, NRA, and NNRC. This ensures that a rule expressed in one language can be accurately converted to another without loss of meaning.
  • Type System Mechanization: Developing and verifying a type system for the main languages. This includes proving type preservation, meaning that if a program is well-typed, its execution will not lead to type errors.
  • Complexity Analysis: Mechanizing proofs of the time complexity of the compilers (translation processes) between the languages.

The artifact is presented as a verifiable implementation, with proofs generated by Coq.

Datasets

Not discussed in the paper. The artifact focuses on formal verification of language constructs and translations, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Unified Formalism: The paper demonstrates that a family of powerful rule languages can be unified under a single, formally verified framework, enabling rigorous comparison and translation.
  • Trustworthy Translations: By mechanizing the translations and their proofs of correctness, the authors provide a high degree of confidence that these transformations are sound and preserve the intended semantics.
  • Verified Type Safety: The mechanization of the type system offers a strong guarantee of type safety for the rule languages, which is crucial for building reliable systems.
  • Complexity Guarantees: Proving the time complexity of the compilation process provides valuable insights into the performance characteristics of these rule languages and their transformations.

Key Results

The artifact provides a complete, verified implementation of the formalisms described in the paper, including:

  • Source files for the mechanization of CAMP, NRA, and NNRC.
  • Verified translations between these three languages.
  • Mechanized proofs of correctness for these translations.
  • A mechanized type system for the main languages, with bidirectional proofs of type preservation.
  • Mechanized proofs of the time complexity of the various compilers.

The artifact is available as a 392 KB download and has been tested on Linux and macOS.

Limitations and Future Work

The authors explicitly state that the original JRules language is outside the scope of their mechanization. Additionally, the type inference theorem from Section 7.6 of the paper is not included in the mechanization. Future work could involve extending the mechanization to include these aspects, as well as exploring further applications and optimizations of the pattern calculus.

Summary updated

Abstract

This artifact contains the accompanying code for the ECOOP 2015 paper: "A Pattern Calculus for Rule Languages: Expressiveness, Compilation, and Mechanization". It contains source files for a full mechanization of the three languages presented in the paper: CAMP (Calculus for Aggregating Matching Patterns), NRA (Nested Relational Algebra) and NNRC (Named Nested Relational Calculus). Translations between all three languages and their attendant proofs of correctness are included. Additionally, a mechanization of a type system for the main languages is provided, along with bidirectional proofs of type preservation and proofs of the time complexity of the various compilers.
BibTeX
@inproceedings{shinnar2015pattern,
  author = {Avraham Shinnar and Jérôme Siméon and Martin Hirzel},
  title = {{A Pattern Calculus for Rule Languages: Expressiveness, Compilation, and Mechanization (Artifact)}},
  booktitle = {Dagstuhl Artifacts Ser},
  year = {2015},
  url = {https://openreview.net/forum?id=tjuywtTTd0},
}
Figure