Pie : Prototyping Inference Engine

Pie is a Python library for building inference engines. It allows rapid prototyping of software that requires logical reasoning capabilities.

The library supports:

• Existential disjunctive rules (Disjunctive Datalog with existentially quantified variables)
• First-order queries with conjunction, disjunction, negation, and quantifiers
• Backward chaining (query rewriting)
• Rule compilation (ID and hierarchical fragments) for accelerating rewriting and evaluation
• Rule analysis for guarded/frontier-guarded/range-restricted/weakly-acyclic/sticky fragments, including disjunctive guarded-based rules and safe-negation-aware guarded checks
• DLGP parser (DLGPE version) with disjunction, negation, equality, sections, and IRI resolution for @base/@prefix (default for examples)
• View declarations and imports with @view and @import <*.vd> for virtual external sources
• Computed predicates with the standard function library via @computed
• Knowledge bases and rule bases for grouping facts and rules
• Prepared query interfaces and FOQuery factory helpers
• IRI utilities for parsing, normalization, and base/prefix management
• IO helpers with parsers and writers (DLGP export)

Installation

pip install -e .

Requires Python 3.10+ (uses match/case syntax). CI runs on CPython 3.10, CPython 3.12, and PyPy 3.10.

Progression

Quick Start

Parsing and Querying

from prototyping_inference_engine.io.parsers.dlgpe import DlgpeParser
from prototyping_inference_engine.api.fact_base.mutable_in_memory_fact_base import MutableInMemoryFactBase
from prototyping_inference_engine.query_evaluation.evaluator.fo_query.fo_query_evaluators import (
    GenericFOQueryEvaluator,
)

# Parse facts and query (DLGP)
parser = DlgpeParser.instance()
result = parser.parse("""
    @facts
    p(a,b).
    p(b,c).
    p(c,d).

    @queries
    ?(X,Z) :- p(X,Y), p(Y,Z).
""")
facts = result["facts"]
query = result["queries"][0]

# Create fact base and evaluate
fact_base = MutableInMemoryFactBase(facts)
evaluator = GenericFOQueryEvaluator()

# Get results as substitutions
for sub in evaluator.evaluate(query, fact_base):
    print(sub)  # {X -> a, Y -> b, Z -> c}, etc.

# Or get projected tuples
for answer in evaluator.evaluate_and_project(query, fact_base):
    print(answer)  # (a, c), (b, d)

Using the Session API

from prototyping_inference_engine.session.reasoning_session import ReasoningSession
from prototyping_inference_engine.io.parsers.dlgpe import DlgpeParser

with ReasoningSession.create() as session:
    # Parse DLGP content
    parser = DlgpeParser.instance()
    result = parser.parse("""
        @facts
        p(a,b).
        p(b,c).

        @queries
        ?(X) :- p(a,X).
    """)

    # Create fact base and evaluate
    fb = session.create_fact_base(result["facts"])
    for answer in session.evaluate_query(result["queries"][0], fb):
        print(answer)  # (b,)

IRI Utilities

from prototyping_inference_engine.api.iri import (
    IRIManager,
    StandardComposableNormalizer,
    RFCNormalizationScheme,
)

manager = IRIManager(
    normalizer=StandardComposableNormalizer(RFCNormalizationScheme.STRING),
    iri_base="http://example.org/base/",
)
manager.set_prefix("ex", "http://example.org/ns/")

iri = manager.create_iri("ex:resource")
print(iri.recompose())  # http://example.org/ns/resource

Exporting DLGP

from prototyping_inference_engine.io.writers.dlgpe_writer import DlgpeWriter
from prototyping_inference_engine.io.parsers.dlgpe import DlgpeParser

parser = DlgpeParser.instance()
result = parser.parse("""
    @base <http://example.org/base/>.
    @prefix ex: <http://example.org/ns/>.
    <rel>(ex:obj).
""")

writer = DlgpeWriter()
print(writer.write(result))

Computed Predicates (@computed)

To load standard functions, use @computed <prefix>: <stdfct>.. To load Python computed functions, use @computed <prefix>: <path/to/config.json>. The configuration format is documented in docs/usage.md.

@computed ig: <stdfct>.

@queries
?(X) :- ig:sum(1, X, 3).

@computed ig: <stdfct>.

@queries
?(X) :- ig:get(ig:tuple(a, b, c), 1, X).
?(U) :- ig:union(ig:set(a, b), ig:set(b, c), U).
?(D) :- ig:dict(ig:tuple(a, b), ig:tuple(b, c), D).

Analysing Rule Sets

Guarded-based properties stay meaningful on disjunctive heads, and guarded checks also handle safe negation. Sticky remains a classical positive non-disjunctive fragment, so a disjunctive rule can still be guarded while failing sticky.

from prototyping_inference_engine.io.parsers.dlgpe import DlgpeParser
from prototyping_inference_engine.rule_analysis import PropertyId, RuleAnalyser

rules = tuple(
    DlgpeParser.instance().parse_rules(
        """
        q(X) | r(X) :- p(X), not blocked(X).
        """
    )
)

report = RuleAnalyser(rules).analyse(
    [
        PropertyId.LINEAR,
        PropertyId.GUARDED,
        PropertyId.FRONTIER_GUARDED,
        PropertyId.STICKY,
    ]
)
statuses = {
    property_id.value: report.get(property_id).status.value
    for property_id in (
        PropertyId.LINEAR,
        PropertyId.GUARDED,
        PropertyId.FRONTIER_GUARDED,
        PropertyId.STICKY,
    )
}
print(statuses)

Expected output: {'linear': 'satisfied', 'guarded': 'satisfied', 'frontier_guarded': 'satisfied', 'sticky': 'violated'}.

Architecture

Core API (api/)

• Terms: Variable, Constant with flyweight caching
• Atoms: Predicate + terms, implements Substitutable
• Formulas: Atom, ConjunctionFormula, DisjunctionFormula, NegationFormula, ExistentialFormula, UniversalFormula
• Queries: FOQuery wrapping formulas with answer variables
• Fact Bases: MutableInMemoryFactBase, FrozenInMemoryFactBase
• Rules & Ontology: Formula-based rules with disjunctive head support
• Rule Bases & Knowledge Bases: Containers for rules, facts, and ontologies
• GRD: Graph of Rule Dependencies (disjunctive heads + safe negation) with stratification strategies backed by igraph, including minimal-evaluation stratification

Data Abstraction (api/data/)

Abstraction layer for data sources (fact bases, SQL databases, REST APIs, etc.):

• ReadableData: Abstract interface for queryable data sources
• MaterializedData: Extension for fully iterable data sources
• BasicQuery: Simple query with predicate, bound positions, and answer variables
• AtomicPattern: Describes constraints for querying predicates (mandatory positions, type constraints)
• PositionConstraint: Validators for term types at positions (GROUND, CONSTANT, VARIABLE, etc.)

Data sources declare their capabilities via AtomicPattern and implement evaluate(BasicQuery) returning tuples of terms. Evaluators handle variable mapping and post-processing.

Query Evaluation (query_evaluation/)

Hierarchical evaluator architecture:

### Rule Compilation (`rule_compilation/`)

- **ID compilation** and **hierarchical compilation** for compiled preorders
- **Compatibility and unfolding** helpers used in rewriting and evaluation
QueryEvaluator[Q]
└── FOQueryEvaluator
    ├── AtomicFOQueryEvaluator
    ├── ConjunctiveFOQueryEvaluator
    ├── DisjunctiveFOQueryEvaluator
    ├── NegationFOQueryEvaluator
    ├── UniversalFOQueryEvaluator
    ├── ExistentialFOQueryEvaluator
    └── GenericFOQueryEvaluator (dispatches by formula type)

Each evaluator provides:

• evaluate(query, data, substitution) → Iterator[Substitution]
• evaluate_and_project(query, data, substitution) → Iterator[Tuple[Term, ...]]

Evaluators work with any ReadableData source, not just in-memory fact bases.

Backward Chaining (backward_chaining/)

• BreadthFirstRewriting - UCQ rewriting algorithm
• PieceUnifierAlgorithm - computes most general piece unifiers
• RewritingOperator - applies rules to queries

Parser (parser/)

DLGP (parser/dlgpe/)

Extended Datalog+- format with disjunction, negation, and sections (recommended).

Supported features:

Usage:

from prototyping_inference_engine.io.parsers.dlgpe import DlgpeParser
from prototyping_inference_engine.io.parsers.dlgpe import DlgpeUnsupportedFeatureError

parser = DlgpeParser.instance()

# Parse DLGP content
result = parser.parse("""
    @facts
    person(alice).
    person(bob).
    knows(alice, bob).

    @rules
    [transitivity] knows(X, Z) :- knows(X, Y), knows(Y, Z).
    stranger(X, Y) :- person(X), person(Y), not knows(X, Y).

    @queries
    ?(X) :- knows(alice, X).
""")

facts = result["facts"]
rules = result["rules"]
queries = result["queries"]

# Parse specific elements
atoms = list(parser.parse_atoms("p(a). q(b)."))
rules = list(parser.parse_rules("h(X) :- b(X). p(X) | q(X) :- r(X)."))

DLGP Files (.dlgp)

DLGP files use the .dlgp extension. This version uses | for disjunction.

% Facts
p(a,b).

% Disjunctive rule
q(X) | r(Y) :- p(X,Y).

% Conjunctive query
?(X) :- p(X,Y), q(Y).

% Disjunctive query
?() :- (p(X), q(X)) | (r(X), s(X)).

CLI Tools

# Query rewriter (DLGP syntax)
disjunctive-rewriter [file.dlgp] [-l LIMIT] [-v] [-m]

Running Tests

# All tests
python3 -m unittest discover -s prototyping_inference_engine -t . -v

# Specific module
python3 -m unittest discover -s prototyping_inference_engine/query_evaluation -v

License

GNU General Public License v3 (GPLv3)