Deductive Systems, Rule Schemas, and Span Components¶

The abstract framework for weighted deductive parsing, organized into three layers:

Deductive Systems¶

Five abstract primitives for weighted deductive parsing (Shieber, Schabes & Pereira 1995; Goodman 1999). The parsers in this package are instances of this framework.

Axiom: Creates and populates the initial chart from input.
Deduction: A weighted inference step (chart → chart).
Goal: Extracts the result from a completed chart.
Schedule: Evaluation strategy (CKY bottom-up, Earley, agenda-based).
DeductiveSystem: Ties axiom, deductions, goal, schedule, and semiring into a single nn.Module.

For the full surface, see api/stochastic/deduction. The primitives themselves are documented at api/stochastic/deduction/primitives.

Rule Schemas¶

Composable functors CategorySystem → RuleSystem. Schemas are the abstract building blocks of grammar formalisms: each schema defines a structural rule pattern, and concrete rule instances are generated by instantiating the pattern over a finite category inventory.

Schemas compose via | (union) and can carry default weights via .weighted(w). Grammar formalisms are specific compositions:

CCG = EVALUATION | HARMONIC_COMPOSITION | CROSSED_COMPOSITION
LAMBEK = EVALUATION | ADJUNCTION_UNITS | TENSOR_INTRODUCTION | TENSOR_PROJECTION
NL = EVALUATION
LP = EVALUATION | COMMUTATIVE_EVALUATION | ADJUNCTION_UNITS

The ~20 atomic schemas (e.g. ForwardApplication, BackwardApplication) compose into 13 bundled schemas (e.g. EVALUATION, HARMONIC_COMPOSITION), which compose into grammar presets (CCG, LAMBEK, NL, LP).

schema ¶

Rule schemas: composable functors from CategorySystem to RuleSystem.

A RuleSchema is a functor that maps a CategorySystem to a RuleSystem. Schemas are the abstract building blocks of grammar formalisms: each schema defines a structural rule pattern, and concrete rule instances are generated by instantiating the pattern over a finite category inventory.

The two atomic schema types are:

BinaryRuleSchema: defined by a match predicate on category pairs: match(left, right) -> result | None.
UnaryRuleSchema: defined by a match predicate on single categories: match(cat, system) -> list[result].

Schemas compose via | (union) and can carry default weights via .weighted(w). Grammar formalisms are specific compositions::

CCG = EVALUATION | HARMONIC_COMPOSITION | CROSSED_COMPOSITION
LAMBEK = EVALUATION | ADJUNCTION_UNITS | TENSOR_INTRODUCTION | TENSOR_PROJECTION

The 13 bundled schemas (EVALUATION, HARMONIC_COMPOSITION, etc.) are themselves composed from ~20 atomic schemas (ForwardApplication, BackwardApplication, etc.), giving fine-grained control::

# only forward application, no backward
MY_GRAMMAR = ForwardApplication() | ForwardComposition()

RuleSchema ¶

Bases: ABC

A functor CategorySystem -> RuleSystem.

Schemas are the abstract specification of structural rules. They compose via | (union) and + (alias for |).

weighted ¶

weighted(weight: float) -> RuleSchema

Attach a default weight to all rules from this schema.

PARAMETER	DESCRIPTION
`weight`	The weight every binary and unary rule receives. TYPE: `float`

RETURNS	DESCRIPTION
`RuleSchema`	A `WeightedSchema` wrapping this schema.

Source code in src/quivers/stochastic/schema.py

def weighted(self, weight: float) -> RuleSchema:
    """Attach a default weight to all rules from this schema.

    Parameters
    ----------
    weight : float
        The weight every binary and unary rule receives.

    Returns
    -------
    RuleSchema
        A `WeightedSchema` wrapping this schema.
    """
    return WeightedSchema(self, weight)

UnionSchema ¶

UnionSchema(left: RuleSchema, right: RuleSchema)

Bases: RuleSchema

Union of two schemas (composes their rule systems via +).

PARAMETER	DESCRIPTION
`left`	The first schema. TYPE: `RuleSchema`
`right`	The second schema. TYPE: `RuleSchema`

Source code in src/quivers/stochastic/schema.py

def __init__(self, left: RuleSchema, right: RuleSchema) -> None:
    self._left = left
    self._right = right

WeightedSchema ¶

WeightedSchema(inner: RuleSchema, weight: float)

Bases: RuleSchema

Schema wrapper that attaches a default weight to all rules.

PARAMETER	DESCRIPTION
`inner`	The schema whose rules are weighted. TYPE: `RuleSchema`
`weight`	The weight every rule of `inner` receives. TYPE: `float`

Source code in src/quivers/stochastic/schema.py

def __init__(self, inner: RuleSchema, weight: float) -> None:
    self._inner = inner
    self._weight = weight

BinaryRuleSchema ¶

Bases: RuleSchema

Schema for binary rules, defined by a match predicate.

Subclasses implement match(left, right) -> result | None. The schema iterates over all category pairs and collects matches.

match `abstractmethod` ¶

match(left: Category, right: Category) -> Category | None

Test whether (left, right) triggers this rule.

PARAMETER	DESCRIPTION
`left`	Left antecedent. TYPE: `Category`
`right`	Right antecedent. TYPE: `Category`

RETURNS	DESCRIPTION
`Category or None`	Result category if the pair matches, else None.

Source code in src/quivers/stochastic/schema.py

@abstractmethod
def match(
    self,
    left: Category,
    right: Category,
) -> Category | None:
    """Test whether (left, right) triggers this rule.

    Parameters
    ----------
    left : Category
        Left antecedent.
    right : Category
        Right antecedent.

    Returns
    -------
    Category or None
        Result category if the pair matches, else None.
    """
    ...

UnaryRuleSchema ¶

Bases: RuleSchema

Schema for unary rules, defined by a match predicate.

Subclasses implement match(cat, system) -> list[result]. The schema iterates over all categories and collects matches.

match `abstractmethod` ¶

match(cat: Category, system: CategorySystem) -> list[Category]

Find all valid results for a given input category.

PARAMETER	DESCRIPTION
`cat`	Input category. TYPE: `Category`
`system`	The full category inventory (needed for some schemas that must check existence of intermediate categories). TYPE: `CategorySystem`

RETURNS	DESCRIPTION
`list[Category]`	Valid result categories.

Source code in src/quivers/stochastic/schema.py

@abstractmethod
def match(
    self,
    cat: Category,
    system: CategorySystem,
) -> list[Category]:
    """Find all valid results for a given input category.

    Parameters
    ----------
    cat : Category
        Input category.
    system : CategorySystem
        The full category inventory (needed for some schemas
        that must check existence of intermediate categories).

    Returns
    -------
    list[Category]
        Valid result categories.
    """
    ...

ForwardApplication ¶

Bases: BinaryRuleSchema

C/B ⊗ B → C (right evaluation / forward application).

match ¶

match(left: Category, right: Category) -> Category | None

Return the conclusion this rule derives from a pair, if any.

PARAMETER	DESCRIPTION
`left`	The left antecedent. TYPE: `Category`
`right`	The right antecedent. TYPE: `Category`

RETURNS	DESCRIPTION
`Category or None`	The conclusion category, or `None` when the pair does not match this rule.

Source code in src/quivers/stochastic/schema.py

def match(self, left: Category, right: Category) -> Category | None:
    """Return the conclusion this rule derives from a pair, if any.

    Parameters
    ----------
    left : Category
        The left antecedent.
    right : Category
        The right antecedent.

    Returns
    -------
    Category or None
        The conclusion category, or ``None`` when the pair does
        not match this rule.
    """
    if (
        isinstance(left, SlashCategory)
        and left.direction == "/"
        and left.argument == right
    ):
        return left.result

    return None

BackwardApplication ¶

Bases: BinaryRuleSchema

A ⊗ A\C → C (left evaluation / backward application).

match ¶

match(left: Category, right: Category) -> Category | None

Return the conclusion this rule derives from a pair, if any.

PARAMETER	DESCRIPTION
`left`	The left antecedent. TYPE: `Category`
`right`	The right antecedent. TYPE: `Category`

RETURNS	DESCRIPTION
`Category or None`	The conclusion category, or `None` when the pair does not match this rule.

Source code in src/quivers/stochastic/schema.py

def match(self, left: Category, right: Category) -> Category | None:
    """Return the conclusion this rule derives from a pair, if any.

    Parameters
    ----------
    left : Category
        The left antecedent.
    right : Category
        The right antecedent.

    Returns
    -------
    Category or None
        The conclusion category, or ``None`` when the pair does
        not match this rule.
    """
    if (
        isinstance(right, SlashCategory)
        and right.direction == "\\"
        and right.argument == left
    ):
        return right.result

    return None

ForwardComposition ¶

Bases: BinaryRuleSchema

C/B ⊗ B/A → C/A (right harmonic composition).

match ¶

match(left: Category, right: Category) -> Category | None

Return the conclusion this rule derives from a pair, if any.

PARAMETER	DESCRIPTION
`left`	The left antecedent. TYPE: `Category`
`right`	The right antecedent. TYPE: `Category`

RETURNS	DESCRIPTION
`Category or None`	The conclusion category, or `None` when the pair does not match this rule.

Source code in src/quivers/stochastic/schema.py

def match(self, left: Category, right: Category) -> Category | None:
    """Return the conclusion this rule derives from a pair, if any.

    Parameters
    ----------
    left : Category
        The left antecedent.
    right : Category
        The right antecedent.

    Returns
    -------
    Category or None
        The conclusion category, or ``None`` when the pair does
        not match this rule.
    """
    if (
        isinstance(left, SlashCategory)
        and left.direction == "/"
        and isinstance(right, SlashCategory)
        and right.direction == "/"
        and left.argument == right.result
    ):
        return SlashCategory(
            result=left.result, argument=right.argument, direction="/"
        )

    return None

BackwardComposition ¶

Bases: BinaryRuleSchema

A\B ⊗ B\C → A\C (left harmonic composition).

match ¶

match(left: Category, right: Category) -> Category | None

Return the conclusion this rule derives from a pair, if any.

PARAMETER	DESCRIPTION
`left`	The left antecedent. TYPE: `Category`
`right`	The right antecedent. TYPE: `Category`

RETURNS	DESCRIPTION
`Category or None`	The conclusion category, or `None` when the pair does not match this rule.

Source code in src/quivers/stochastic/schema.py

def match(self, left: Category, right: Category) -> Category | None:
    """Return the conclusion this rule derives from a pair, if any.

    Parameters
    ----------
    left : Category
        The left antecedent.
    right : Category
        The right antecedent.

    Returns
    -------
    Category or None
        The conclusion category, or ``None`` when the pair does
        not match this rule.
    """
    if (
        isinstance(left, SlashCategory)
        and left.direction == "\\"
        and isinstance(right, SlashCategory)
        and right.direction == "\\"
        and right.argument == left.result
    ):
        return SlashCategory(
            result=right.result, argument=left.argument, direction="\\"
        )

    return None

ForwardCrossedComposition ¶

Bases: BinaryRuleSchema

C/B ⊗ B\A → C\A (right-left crossed composition).

match ¶

match(left: Category, right: Category) -> Category | None

Return the conclusion this rule derives from a pair, if any.

PARAMETER	DESCRIPTION
`left`	The left antecedent. TYPE: `Category`
`right`	The right antecedent. TYPE: `Category`

RETURNS	DESCRIPTION
`Category or None`	The conclusion category, or `None` when the pair does not match this rule.

Source code in src/quivers/stochastic/schema.py

def match(self, left: Category, right: Category) -> Category | None:
    """Return the conclusion this rule derives from a pair, if any.

    Parameters
    ----------
    left : Category
        The left antecedent.
    right : Category
        The right antecedent.

    Returns
    -------
    Category or None
        The conclusion category, or ``None`` when the pair does
        not match this rule.
    """
    if (
        isinstance(left, SlashCategory)
        and left.direction == "/"
        and isinstance(right, SlashCategory)
        and right.direction == "\\"
        and left.argument == right.result
    ):
        return SlashCategory(
            result=left.result, argument=right.argument, direction="\\"
        )

    return None

BackwardCrossedComposition ¶

Bases: BinaryRuleSchema

A/B ⊗ B\C → A/C (left-right crossed composition).

match ¶

match(left: Category, right: Category) -> Category | None

Return the conclusion this rule derives from a pair, if any.

PARAMETER	DESCRIPTION
`left`	The left antecedent. TYPE: `Category`
`right`	The right antecedent. TYPE: `Category`

RETURNS	DESCRIPTION
`Category or None`	The conclusion category, or `None` when the pair does not match this rule.

Source code in src/quivers/stochastic/schema.py

def match(self, left: Category, right: Category) -> Category | None:
    """Return the conclusion this rule derives from a pair, if any.

    Parameters
    ----------
    left : Category
        The left antecedent.
    right : Category
        The right antecedent.

    Returns
    -------
    Category or None
        The conclusion category, or ``None`` when the pair does
        not match this rule.
    """
    if (
        isinstance(left, SlashCategory)
        and left.direction == "/"
        and isinstance(right, SlashCategory)
        and right.direction == "\\"
        and right.argument == left.result
    ):
        return SlashCategory(
            result=right.result, argument=left.argument, direction="/"
        )

    return None

CommutativeForwardApplication ¶

Bases: BinaryRuleSchema

B ⊗ C/B → C (commutative right evaluation).

match ¶

match(left: Category, right: Category) -> Category | None

Return the conclusion this rule derives from a pair, if any.

PARAMETER	DESCRIPTION
`left`	The left antecedent. TYPE: `Category`
`right`	The right antecedent. TYPE: `Category`

RETURNS	DESCRIPTION
`Category or None`	The conclusion category, or `None` when the pair does not match this rule.

Source code in src/quivers/stochastic/schema.py

def match(self, left: Category, right: Category) -> Category | None:
    """Return the conclusion this rule derives from a pair, if any.

    Parameters
    ----------
    left : Category
        The left antecedent.
    right : Category
        The right antecedent.

    Returns
    -------
    Category or None
        The conclusion category, or ``None`` when the pair does
        not match this rule.
    """
    if (
        isinstance(right, SlashCategory)
        and right.direction == "/"
        and right.argument == left
    ):
        return right.result

    return None

CommutativeBackwardApplication ¶

Bases: BinaryRuleSchema

A\C ⊗ A → C (commutative left evaluation).

match ¶

match(left: Category, right: Category) -> Category | None

Return the conclusion this rule derives from a pair, if any.

PARAMETER	DESCRIPTION
`left`	The left antecedent. TYPE: `Category`
`right`	The right antecedent. TYPE: `Category`

RETURNS	DESCRIPTION
`Category or None`	The conclusion category, or `None` when the pair does not match this rule.

Source code in src/quivers/stochastic/schema.py

def match(self, left: Category, right: Category) -> Category | None:
    """Return the conclusion this rule derives from a pair, if any.

    Parameters
    ----------
    left : Category
        The left antecedent.
    right : Category
        The right antecedent.

    Returns
    -------
    Category or None
        The conclusion category, or ``None`` when the pair does
        not match this rule.
    """
    if (
        isinstance(left, SlashCategory)
        and left.direction == "\\"
        and left.argument == right
    ):
        return left.result

    return None

TensorIntroduction ¶

Bases: BinaryRuleSchema

A ⊗ B → A⊗B (product formation).

match ¶

match(left: Category, right: Category) -> Category | None

Return the conclusion this rule derives from a pair, if any.

PARAMETER	DESCRIPTION
`left`	The left antecedent. TYPE: `Category`
`right`	The right antecedent. TYPE: `Category`

RETURNS	DESCRIPTION
`Category or None`	The conclusion category, or `None` when the pair does not match this rule.

Source code in src/quivers/stochastic/schema.py

def match(self, left: Category, right: Category) -> Category | None:
    """Return the conclusion this rule derives from a pair, if any.

    Parameters
    ----------
    left : Category
        The left antecedent.
    right : Category
        The right antecedent.

    Returns
    -------
    Category or None
        The conclusion category, or ``None`` when the pair does
        not match this rule.
    """
    return ProductCategory(left=left, right=right)

LeftUnitElimination ¶

Bases: BinaryRuleSchema

I ⊗ A → A (left unitor).

match ¶

match(left: Category, right: Category) -> Category | None

Return the conclusion this rule derives from a pair, if any.

PARAMETER	DESCRIPTION
`left`	The left antecedent. TYPE: `Category`
`right`	The right antecedent. TYPE: `Category`

RETURNS	DESCRIPTION
`Category or None`	The conclusion category, or `None` when the pair does not match this rule.

Source code in src/quivers/stochastic/schema.py

def match(self, left: Category, right: Category) -> Category | None:
    """Return the conclusion this rule derives from a pair, if any.

    Parameters
    ----------
    left : Category
        The left antecedent.
    right : Category
        The right antecedent.

    Returns
    -------
    Category or None
        The conclusion category, or ``None`` when the pair does
        not match this rule.
    """
    if isinstance(left, UnitCategory):
        return right

    return None

RightUnitElimination ¶

Bases: BinaryRuleSchema

A ⊗ I → A (right unitor).

match ¶

match(left: Category, right: Category) -> Category | None

Return the conclusion this rule derives from a pair, if any.

PARAMETER	DESCRIPTION
`left`	The left antecedent. TYPE: `Category`
`right`	The right antecedent. TYPE: `Category`

RETURNS	DESCRIPTION
`Category or None`	The conclusion category, or `None` when the pair does not match this rule.

Source code in src/quivers/stochastic/schema.py

def match(self, left: Category, right: Category) -> Category | None:
    """Return the conclusion this rule derives from a pair, if any.

    Parameters
    ----------
    left : Category
        The left antecedent.
    right : Category
        The right antecedent.

    Returns
    -------
    Category or None
        The conclusion category, or ``None`` when the pair does
        not match this rule.
    """
    if isinstance(right, UnitCategory):
        return left

    return None

ModalApplication ¶

ModalApplication(modality: str = '◇')

Bases: BinaryRuleSchema

◇(C/B) ⊗ ◇B → ◇C (modal function application).

PARAMETER	DESCRIPTION
`modality`	The modality symbol (e.g. "◇", "□"). TYPE: `str` DEFAULT: `'◇'`

Source code in src/quivers/stochastic/schema.py

def __init__(self, modality: str = "◇") -> None:
    self._modality = modality

match ¶

match(left: Category, right: Category) -> Category | None

Return the conclusion this rule derives from a pair, if any.

PARAMETER	DESCRIPTION
`left`	The left antecedent. TYPE: `Category`
`right`	The right antecedent. TYPE: `Category`

RETURNS	DESCRIPTION
`Category or None`	The conclusion category, or `None` when the pair does not match this rule.

Source code in src/quivers/stochastic/schema.py

def match(self, left: Category, right: Category) -> Category | None:
    """Return the conclusion this rule derives from a pair, if any.

    Parameters
    ----------
    left : Category
        The left antecedent.
    right : Category
        The right antecedent.

    Returns
    -------
    Category or None
        The conclusion category, or ``None`` when the pair does
        not match this rule.
    """
    if (
        not isinstance(left, ModalCategory)
        or left.modality != self._modality
        or not isinstance(right, ModalCategory)
        or right.modality != self._modality
    ):
        return None

    inner_left = left.inner
    inner_right = right.inner

    # ◇(C/B) ⊗ ◇B → ◇C
    if (
        isinstance(inner_left, SlashCategory)
        and inner_left.direction == "/"
        and inner_left.argument == inner_right
    ):
        return ModalCategory(modality=self._modality, inner=inner_left.result)

    # ◇A ⊗ ◇(A\C) → ◇C
    if (
        isinstance(inner_right, SlashCategory)
        and inner_right.direction == "\\"
        and inner_right.argument == inner_left
    ):
        return ModalCategory(modality=self._modality, inner=inner_right.result)

    return None

RightLifting ¶

Bases: UnaryRuleSchema

A → C/(A\C) (right adjunction unit / type raising).

match ¶

match(cat: Category, system: CategorySystem) -> list[Category]

Return the conclusions this rule derives from a category.

PARAMETER	DESCRIPTION
`cat`	The antecedent category. TYPE: `Category`
`system`	The category inventory; conclusions outside it are dropped. TYPE: `CategorySystem`

RETURNS	DESCRIPTION
`list of Category`	The conclusion categories, empty when the rule does not apply.

Source code in src/quivers/stochastic/schema.py

def match(self, cat: Category, system: CategorySystem) -> list[Category]:
    """Return the conclusions this rule derives from a category.

    Parameters
    ----------
    cat : Category
        The antecedent category.
    system : CategorySystem
        The category inventory; conclusions outside it are dropped.

    Returns
    -------
    list of Category
        The conclusion categories, empty when the rule does not
        apply.
    """
    results = []

    for c in system:
        inner = SlashCategory(result=c, argument=cat, direction="\\")

        if inner in system:
            raised = SlashCategory(result=c, argument=inner, direction="/")

            if raised in system:
                results.append(raised)

    return results

LeftLifting ¶

Bases: UnaryRuleSchema

A → (C/A)\C (left adjunction unit / type raising).

match ¶

match(cat: Category, system: CategorySystem) -> list[Category]

Return the conclusions this rule derives from a category.

PARAMETER	DESCRIPTION
`cat`	The antecedent category. TYPE: `Category`
`system`	The category inventory; conclusions outside it are dropped. TYPE: `CategorySystem`

RETURNS	DESCRIPTION
`list of Category`	The conclusion categories, empty when the rule does not apply.

Source code in src/quivers/stochastic/schema.py

def match(self, cat: Category, system: CategorySystem) -> list[Category]:
    """Return the conclusions this rule derives from a category.

    Parameters
    ----------
    cat : Category
        The antecedent category.
    system : CategorySystem
        The category inventory; conclusions outside it are dropped.

    Returns
    -------
    list of Category
        The conclusion categories, empty when the rule does not
        apply.
    """
    results = []

    for c in system:
        inner = SlashCategory(result=c, argument=cat, direction="/")

        if inner in system:
            raised = SlashCategory(result=c, argument=inner, direction="\\")

            if raised in system:
                results.append(raised)

    return results

LeftProjection ¶

Bases: UnaryRuleSchema

A⊗B → A (left tensor projection).

match ¶

match(cat: Category, system: CategorySystem) -> list[Category]

Return the conclusions this rule derives from a category.

PARAMETER	DESCRIPTION
`cat`	The antecedent category. TYPE: `Category`
`system`	The category inventory; conclusions outside it are dropped. TYPE: `CategorySystem`

RETURNS	DESCRIPTION
`list of Category`	The conclusion categories, empty when the rule does not apply.

Source code in src/quivers/stochastic/schema.py

def match(self, cat: Category, system: CategorySystem) -> list[Category]:
    """Return the conclusions this rule derives from a category.

    Parameters
    ----------
    cat : Category
        The antecedent category.
    system : CategorySystem
        The category inventory; conclusions outside it are dropped.

    Returns
    -------
    list of Category
        The conclusion categories, empty when the rule does not
        apply.
    """
    if isinstance(cat, ProductCategory) and cat.left in system:
        return [cat.left]

    return []

RightProjection ¶

Bases: UnaryRuleSchema

A⊗B → B (right tensor projection).

match ¶

match(cat: Category, system: CategorySystem) -> list[Category]

Return the conclusions this rule derives from a category.

PARAMETER	DESCRIPTION
`cat`	The antecedent category. TYPE: `Category`
`system`	The category inventory; conclusions outside it are dropped. TYPE: `CategorySystem`

RETURNS	DESCRIPTION
`list of Category`	The conclusion categories, empty when the rule does not apply.

Source code in src/quivers/stochastic/schema.py

def match(self, cat: Category, system: CategorySystem) -> list[Category]:
    """Return the conclusions this rule derives from a category.

    Parameters
    ----------
    cat : Category
        The antecedent category.
    system : CategorySystem
        The category inventory; conclusions outside it are dropped.

    Returns
    -------
    list of Category
        The conclusion categories, empty when the rule does not
        apply.
    """
    if isinstance(cat, ProductCategory) and cat.right in system:
        return [cat.right]

    return []

UnitCoercion ¶

Bases: UnaryRuleSchema

A → I (unit elimination / weakening).

match ¶

match(cat: Category, system: CategorySystem) -> list[Category]

Return the conclusions this rule derives from a category.

PARAMETER	DESCRIPTION
`cat`	The antecedent category. TYPE: `Category`
`system`	The category inventory; conclusions outside it are dropped. TYPE: `CategorySystem`

RETURNS	DESCRIPTION
`list of Category`	The conclusion categories, empty when the rule does not apply.

Source code in src/quivers/stochastic/schema.py

def match(self, cat: Category, system: CategorySystem) -> list[Category]:
    """Return the conclusions this rule derives from a category.

    Parameters
    ----------
    cat : Category
        The antecedent category.
    system : CategorySystem
        The category inventory; conclusions outside it are dropped.

    Returns
    -------
    list of Category
        The conclusion categories, empty when the rule does not
        apply.
    """
    unit = UnitCategory()

    if unit in system:
        return [unit]

    return []

ModalInjection ¶

ModalInjection(modality: str = '◇')

Bases: UnaryRuleSchema

A → ◇A (modal introduction).

PARAMETER	DESCRIPTION
`modality`	The modality symbol (e.g. "◇", "□"). TYPE: `str` DEFAULT: `'◇'`

Source code in src/quivers/stochastic/schema.py

def __init__(self, modality: str = "◇") -> None:
    self._modality = modality

match ¶

match(cat: Category, system: CategorySystem) -> list[Category]

Return the conclusions this rule derives from a category.

PARAMETER	DESCRIPTION
`cat`	The antecedent category. TYPE: `Category`
`system`	The category inventory; conclusions outside it are dropped. TYPE: `CategorySystem`

RETURNS	DESCRIPTION
`list of Category`	The conclusion categories, empty when the rule does not apply.

Source code in src/quivers/stochastic/schema.py

def match(self, cat: Category, system: CategorySystem) -> list[Category]:
    """Return the conclusions this rule derives from a category.

    Parameters
    ----------
    cat : Category
        The antecedent category.
    system : CategorySystem
        The category inventory; conclusions outside it are dropped.

    Returns
    -------
    list of Category
        The conclusion categories, empty when the rule does not
        apply.
    """
    modal = ModalCategory(modality=self._modality, inner=cat)

    if modal in system:
        return [modal]

    return []

ModalProjection ¶

ModalProjection(modality: str = '◇')

Bases: UnaryRuleSchema

◇A → A (modal elimination).

PARAMETER	DESCRIPTION
`modality`	The modality symbol (e.g. "◇", "□"). TYPE: `str` DEFAULT: `'◇'`

Source code in src/quivers/stochastic/schema.py

def __init__(self, modality: str = "◇") -> None:
    self._modality = modality

match ¶

match(cat: Category, system: CategorySystem) -> list[Category]

Return the conclusions this rule derives from a category.

PARAMETER	DESCRIPTION
`cat`	The antecedent category. TYPE: `Category`
`system`	The category inventory; conclusions outside it are dropped. TYPE: `CategorySystem`

RETURNS	DESCRIPTION
`list of Category`	The conclusion categories, empty when the rule does not apply.

Source code in src/quivers/stochastic/schema.py

def match(self, cat: Category, system: CategorySystem) -> list[Category]:
    """Return the conclusions this rule derives from a category.

    Parameters
    ----------
    cat : Category
        The antecedent category.
    system : CategorySystem
        The category inventory; conclusions outside it are dropped.

    Returns
    -------
    list of Category
        The conclusion categories, empty when the rule does not
        apply.
    """
    if (
        isinstance(cat, ModalCategory)
        and cat.modality == self._modality
        and cat.inner in system
    ):
        return [cat.inner]

    return []

GeneralizedComposition ¶

GeneralizedComposition(max_depth: int = 2)

Bases: RuleSchema

Generalized composition through nested slashes (B^n).

C/B ⊗ (B|₁Z₁)|₂Z₂...|ₙZₙ → (C|₁Z₁)|₂Z₂...|ₙZₙ

This is a special schema because the match recurses into nested slash structure. At depth 1 it is ordinary harmonic composition; this schema only generates rules for depth >= 2.

PARAMETER	DESCRIPTION
`max_depth`	Maximum nesting depth to traverse. TYPE: `int` DEFAULT: `2`

Source code in src/quivers/stochastic/schema.py

def __init__(self, max_depth: int = 2) -> None:
    self._max_depth = max_depth

PatternBinarySchema ¶

PatternBinarySchema(left_pattern, right_pattern, conclusion_pattern, variables: frozenset[str], name: str = '')

Bases: BinaryRuleSchema

Binary rule schema from a DSL rule declaration.

Matches category pairs against two premise patterns and instantiates the conclusion pattern with bound variables.

PARAMETER	DESCRIPTION
`left_pattern`	Category pattern for the left antecedent. TYPE: `ObjectExpr`
`right_pattern`	Category pattern for the right antecedent. TYPE: `ObjectExpr`
`conclusion_pattern`	Category pattern for the consequent. TYPE: `ObjectExpr`
`variables`	Universally quantified pattern variables. TYPE: `frozenset of str`
`name`	The rule's name (for description). TYPE: `str` DEFAULT: `''`

Source code in src/quivers/stochastic/schema.py

def __init__(
    self,
    left_pattern,
    right_pattern,
    conclusion_pattern,
    variables: frozenset[str],
    name: str = "",
) -> None:
    self._left = left_pattern
    self._right = right_pattern
    self._conclusion = conclusion_pattern
    self._variables = variables
    self._name = name

match ¶

match(left: Category, right: Category) -> Category | None

Return the conclusion this rule derives from a pair, if any.

PARAMETER	DESCRIPTION
`left`	The left antecedent. TYPE: `Category`
`right`	The right antecedent. TYPE: `Category`

RETURNS	DESCRIPTION
`Category or None`	The conclusion category, or `None` when the pair does not match this rule.

Source code in src/quivers/stochastic/schema.py

def match(self, left: Category, right: Category) -> Category | None:
    """Return the conclusion this rule derives from a pair, if any.

    Parameters
    ----------
    left : Category
        The left antecedent.
    right : Category
        The right antecedent.

    Returns
    -------
    Category or None
        The conclusion category, or ``None`` when the pair does
        not match this rule.
    """
    bindings: dict[str, Category] = {}

    if not _match_pattern(self._left, left, bindings, self._variables):
        return None

    if not _match_pattern(self._right, right, bindings, self._variables):
        return None

    return _instantiate_pattern(
        self._conclusion,
        bindings,
        self._variables,
    )

PatternUnarySchema ¶

PatternUnarySchema(premise_pattern, conclusion_pattern, variables: frozenset[str], name: str = '')

Bases: UnaryRuleSchema

Unary rule schema from a DSL rule declaration.

Matches a single category against a premise pattern and instantiates the conclusion pattern with bound variables.

PARAMETER	DESCRIPTION
`premise_pattern`	Category pattern for the antecedent. TYPE: `ObjectExpr`
`conclusion_pattern`	Category pattern for the consequent. TYPE: `ObjectExpr`
`variables`	Universally quantified pattern variables. TYPE: `frozenset of str`
`name`	The rule's name (for description). TYPE: `str` DEFAULT: `''`

Source code in src/quivers/stochastic/schema.py

def __init__(
    self,
    premise_pattern,
    conclusion_pattern,
    variables: frozenset[str],
    name: str = "",
) -> None:
    self._premise = premise_pattern
    self._conclusion = conclusion_pattern
    self._variables = variables
    self._name = name

match ¶

match(cat: Category, system: CategorySystem) -> list[Category]

Return the conclusions this rule derives from a category.

PARAMETER	DESCRIPTION
`cat`	The antecedent category. TYPE: `Category`
`system`	The category inventory; conclusions outside it are dropped. TYPE: `CategorySystem`

RETURNS	DESCRIPTION
`list of Category`	The conclusion categories, empty when the rule does not apply.

Source code in src/quivers/stochastic/schema.py

def match(
    self,
    cat: Category,
    system: CategorySystem,
) -> list[Category]:
    """Return the conclusions this rule derives from a category.

    Parameters
    ----------
    cat : Category
        The antecedent category.
    system : CategorySystem
        The category inventory; conclusions outside it are dropped.

    Returns
    -------
    list of Category
        The conclusion categories, empty when the rule does not
        apply.
    """
    bindings: dict[str, Category] = {}

    if not _match_pattern(self._premise, cat, bindings, self._variables):
        return []

    result = _instantiate_pattern(
        self._conclusion,
        bindings,
        self._variables,
    )

    if result is None:
        return []

    return [result]

generalized_composition ¶

generalized_composition(max_depth: int = 2) -> RuleSchema

Create a generalized composition schema.

PARAMETER	DESCRIPTION
`max_depth`	Maximum nesting depth. TYPE: `int` DEFAULT: `2`

RETURNS	DESCRIPTION
`RuleSchema`	The generalized composition schema.

Source code in src/quivers/stochastic/schema.py

def generalized_composition(max_depth: int = 2) -> RuleSchema:
    """Create a generalized composition schema.

    Parameters
    ----------
    max_depth : int
        Maximum nesting depth.

    Returns
    -------
    RuleSchema
        The generalized composition schema.
    """
    return GeneralizedComposition(max_depth)

Bundled schemas¶

Stochastic morphisms: Markov kernels over finite sets.

This module provides the probabilistic layer for quivers, implementing the category FinStoch of finite sets and stochastic maps (Markov kernels). This is the Kleisli category of the Giry monad restricted to finite sets, where:

Objects are finite sets (same as the base category).
Morphisms A -> B are stochastic matrices: tensors of shape (|A|, |B|) whose rows sum to 1.
Composition is standard matrix multiplication.
Identity is the Kronecker delta.

The package also re-exports MarkovAlgebra and its singleton MARKOV from quivers.core.algebras, the algebra these morphisms compose under.

Submodules

morphisms : StochasticMorphism, CategoricalMorphism families : Discretized distribution families transforms : condition, mix, factor, normalize queries : prob, marginal_prob, expectation giry : GiryMonad, FinStoch categories : Category types including atoms, slashes, products, unit, modals semiring : Chart semiring abstractions (LogProb, Viterbi, Boolean, Counting) schema : Composable rule schemas (functors CategorySystem -> RuleSystem) rules : Rule systems and the CCG / Lambek presets span : Span-based CKY components (LexicalAxiom, BinarySpanDeduction, etc.) parsers, ccg, lambek : Chart parsers inside : The inside algorithm over a rule system agenda : The agenda-driven weighted-deduction engine effect_lifts : Effect-lifted rule schemas for deduction systems deduction : Abstract weighted deductive system framework and its operations stdlib : Pre-registered deduction systems

EVALUATION `module-attribute` ¶

EVALUATION = ForwardApplication() | BackwardApplication()

Forward and backward application, the evaluation maps of a biclosed category.

HARMONIC_COMPOSITION `module-attribute` ¶

HARMONIC_COMPOSITION = ForwardComposition() | BackwardComposition()

Forward and backward harmonic composition.

CROSSED_COMPOSITION `module-attribute` ¶

CROSSED_COMPOSITION = ForwardCrossedComposition() | BackwardCrossedComposition()

Forward and backward crossed composition.

COMMUTATIVE_EVALUATION `module-attribute` ¶

COMMUTATIVE_EVALUATION = CommutativeForwardApplication() | CommutativeBackwardApplication()

Application with the argument on either side, for commutative (LP) grammars.

ADJUNCTION_UNITS `module-attribute` ¶

ADJUNCTION_UNITS = RightLifting() | LeftLifting()

Right and left type raising, the units of the slash adjunctions.

TENSOR_INTRODUCTION `module-attribute` ¶

TENSOR_INTRODUCTION = TensorIntroduction()

Product formation, A, B -> A*B.

TENSOR_PROJECTION `module-attribute` ¶

TENSOR_PROJECTION = LeftProjection() | RightProjection()

Left and right projections out of a product category.

UNIT_INTRODUCTION `module-attribute` ¶

UNIT_INTRODUCTION = LeftUnitElimination() | RightUnitElimination()

The left and right unitors, I*A -> A and A*I -> A.

UNIT_ELIMINATION `module-attribute` ¶

UNIT_ELIMINATION = UnitCoercion()

Coercion of any category to the monoidal unit, A -> I.

MODAL_INTRODUCTION `module-attribute` ¶

MODAL_INTRODUCTION = ModalInjection()

Modal injection, A -> <>A.

MODAL_ELIMINATION `module-attribute` ¶

MODAL_ELIMINATION = ModalProjection()

Modal projection, <>A -> A.

MODAL_APPLICATION `module-attribute` ¶

MODAL_APPLICATION = ModalApplication()

Function application under a modality.

Grammar presets and the schema registry¶

Stochastic morphisms: Markov kernels over finite sets.

This module provides the probabilistic layer for quivers, implementing the category FinStoch of finite sets and stochastic maps (Markov kernels). This is the Kleisli category of the Giry monad restricted to finite sets, where:

Objects are finite sets (same as the base category).
Morphisms A -> B are stochastic matrices: tensors of shape (|A|, |B|) whose rows sum to 1.
Composition is standard matrix multiplication.
Identity is the Kronecker delta.

The package also re-exports MarkovAlgebra and its singleton MARKOV from quivers.core.algebras, the algebra these morphisms compose under.

Submodules

morphisms : StochasticMorphism, CategoricalMorphism families : Discretized distribution families transforms : condition, mix, factor, normalize queries : prob, marginal_prob, expectation giry : GiryMonad, FinStoch categories : Category types including atoms, slashes, products, unit, modals semiring : Chart semiring abstractions (LogProb, Viterbi, Boolean, Counting) schema : Composable rule schemas (functors CategorySystem -> RuleSystem) rules : Rule systems and the CCG / Lambek presets span : Span-based CKY components (LexicalAxiom, BinarySpanDeduction, etc.) parsers, ccg, lambek : Chart parsers inside : The inside algorithm over a rule system agenda : The agenda-driven weighted-deduction engine effect_lifts : Effect-lifted rule schemas for deduction systems deduction : Abstract weighted deductive system framework and its operations stdlib : Pre-registered deduction systems

CCG `module-attribute` ¶

CCG = EVALUATION | HARMONIC_COMPOSITION | CROSSED_COMPOSITION

The combinatory categorial grammar preset: application plus harmonic and crossed composition.

LAMBEK `module-attribute` ¶

LAMBEK = EVALUATION | ADJUNCTION_UNITS | TENSOR_INTRODUCTION | TENSOR_PROJECTION

The Lambek calculus preset: application, type raising, and the product rules.

NL `module-attribute` ¶

NL = EVALUATION

The non-associative Lambek calculus preset: application only.

LP `module-attribute` ¶

LP = EVALUATION | COMMUTATIVE_EVALUATION | ADJUNCTION_UNITS

The Lambek calculus with permutation preset: application in both orders and type raising.

SCHEMA_REGISTRY `module-attribute` ¶

SCHEMA_REGISTRY: dict[str, RuleSchema] = {'evaluation': EVALUATION, 'harmonic_composition': HARMONIC_COMPOSITION, 'crossed_composition': CROSSED_COMPOSITION, 'generalized_composition': GeneralizedComposition(), 'adjunction_units': ADJUNCTION_UNITS, 'tensor_introduction': TENSOR_INTRODUCTION, 'tensor_projection': TENSOR_PROJECTION, 'commutative_evaluation': COMMUTATIVE_EVALUATION, 'unit_introduction': UNIT_INTRODUCTION, 'unit_elimination': UNIT_ELIMINATION, 'modal_introduction': MODAL_INTRODUCTION, 'modal_elimination': MODAL_ELIMINATION, 'modal_application': MODAL_APPLICATION}

The bundled schemas by the name a DSL rules clause uses for each.

Span-Based CKY Components¶

Span-based instantiation of the abstract deductive framework for CKY chart parsing:

LexicalAxiom: Populates length-1 spans from a learnable lexicon.
BinarySpanDeduction: Applies binary structural rules with learnable weights.
UnarySpanDeduction: Applies unary rules to convergence.
SpanGoal: Extracts the start-symbol score for the full span.
CKYSchedule: Bottom-up evaluation by span length.

span ¶

Span-based CKY components for the deductive system framework.

This module instantiates the abstract deduction primitives (Axiom, Deduction, Goal, Schedule) for span-indexed chart parsing (CKY). Items are indexed by (i, j, A) where [i, j) is a string span and A is a category index.

The chart tensor has shape (batch, n_categories, seq_len, seq_len+1) (categories-first for efficient indexing of the start symbol).

Components

LexicalAxiom Populates length-1 spans from a learnable lexicon. BinarySpanDeduction Applies binary rules: chart[i,k,L] ⊗ chart[k,j,R] → chart[i,j,A]. UnarySpanDeduction Applies unary rules iteratively to convergence. SpanGoal Extracts chart[start_cat, 0, seq_len]. CKYSchedule Bottom-up evaluation by span length.

LexicalAxiom ¶

LexicalAxiom(n_terminals: int, n_categories: int)

Bases: Axiom

Populate length-1 spans from a learnable lexicon.

Creates the chart tensor and fills chart[b, :, i, i+1] = log_softmax(lexicon[tokens[b, i]]).

PARAMETER	DESCRIPTION
`n_terminals`	Vocabulary size. TYPE: `int`
`n_categories`	Number of category types. TYPE: `int`

Source code in src/quivers/stochastic/span.py

def __init__(self, n_terminals: int, n_categories: int) -> None:
    super().__init__()
    self._n_cat = n_categories
    self.lexicon_logits = nn.Parameter(torch.randn(n_terminals, n_categories) * 0.1)

log_lexicon `property` ¶

log_lexicon: Tensor

Log-probability lexicon, shape (n_terminals, n_categories).

forward ¶

forward(tokens: Tensor, semiring: ChartSemiring) -> SpanChart

Fill the length-1 spans from the lexicon.

PARAMETER	DESCRIPTION
`tokens`	Integer terminal indices of shape `(batch, seq_len)`. TYPE: `Tensor`
`semiring`	The scoring semiring, recorded on the chart. TYPE: `ChartSemiring`

RETURNS	DESCRIPTION
`SpanChart`	A chart whose cells `(i, i + 1)` hold the lexical log-probabilities of each token.

Source code in src/quivers/stochastic/span.py

def forward(self, tokens: torch.Tensor, semiring: ChartSemiring) -> SpanChart:  # type: ignore[override]
    """Fill the length-1 spans from the lexicon.

    Parameters
    ----------
    tokens : torch.Tensor
        Integer terminal indices of shape ``(batch, seq_len)``.
    semiring : ChartSemiring
        The scoring semiring, recorded on the chart.

    Returns
    -------
    SpanChart
        A chart whose cells ``(i, i + 1)`` hold the lexical
        log-probabilities of each token.
    """
    batch, seq_len = tokens.shape
    log_lex = self.log_lexicon[tokens]  # (batch, seq_len, C)

    # build chart as list-of-lists (functional, no in-place writes)
    # stored as flat dict keyed by (i, j)
    chart_cells: dict[tuple[int, int], torch.Tensor] = {}

    for i in range(seq_len):
        chart_cells[(i, i + 1)] = log_lex[:, i, :]  # (batch, C)

    # pack into metadata for the schedule
    return SpanChart(
        cells=chart_cells,
        batch=batch,
        seq_len=seq_len,
        n_categories=self._n_cat,
        device=tokens.device,
        semiring=semiring,
    )

SpanChart ¶

SpanChart(cells: dict[tuple[int, int], Tensor], batch: int, seq_len: int, n_categories: int, device: device, semiring: ChartSemiring)

A span-indexed chart held as functional (non-in-place) cells.

This wraps a dict of (i, j) -> (batch, C) tensors. The schedule fills cells bottom-up, and to_tensor() assembles them into a dense (batch, C, seq_len, seq_len+1) tensor.

PARAMETER	DESCRIPTION
`cells`	The filled cells, keyed by span `(i, j)`, each of shape `(batch, n_categories)`. TYPE: `dict of (int, int) to torch.Tensor`
`batch`	The batch size. TYPE: `int`
`seq_len`	The sentence length. TYPE: `int`
`n_categories`	The number of categories. TYPE: `int`
`device`	The device the dense chart is built on. TYPE: `device`
`semiring`	The scoring semiring; its `zero` fills unfilled cells. TYPE: `ChartSemiring`

Source code in src/quivers/stochastic/span.py

def __init__(
    self,
    cells: dict[tuple[int, int], torch.Tensor],
    batch: int,
    seq_len: int,
    n_categories: int,
    device: torch.device,
    semiring: ChartSemiring,
) -> None:
    self.cells = cells
    self.batch = batch
    self.seq_len = seq_len
    self.n_categories = n_categories
    self.device = device
    self.semiring = semiring

to_tensor ¶

to_tensor() -> Tensor

Assemble cells into a dense chart tensor.

RETURNS	DESCRIPTION
`Tensor`	Shape `(batch, n_categories, seq_len, seq_len+1)`.

Source code in src/quivers/stochastic/span.py

def to_tensor(self) -> torch.Tensor:
    """Assemble cells into a dense chart tensor.

    Returns
    -------
    torch.Tensor
        Shape ``(batch, n_categories, seq_len, seq_len+1)``.
    """
    chart = torch.full(
        (self.batch, self.n_categories, self.seq_len, self.seq_len + 1),
        self.semiring.zero,
        device=self.device,
    )

    for (i, j), cell in self.cells.items():
        chart[:, :, i, j] = cell

    return chart

BinarySpanDeduction ¶

BinarySpanDeduction(rule_system: RuleSystem, learnable: bool = True)

Bases: Deduction

Binary rule application over span items.

For each split point k in [i+1, j), combines chart[i, k, lefts] and chart[k, j, rights] to produce chart[i, j, results].

PARAMETER	DESCRIPTION
`rule_system`	The structural rules. TYPE: `RuleSystem`
`learnable`	Whether rule weights are learnable. TYPE: `bool` DEFAULT: `True`

Source code in src/quivers/stochastic/span.py

def __init__(
    self,
    rule_system: RuleSystem,
    learnable: bool = True,
) -> None:
    super().__init__()

    results, lefts, rights = rule_system.binary_tensors()
    self.register_buffer("_results", results)
    self.register_buffer("_lefts", lefts)
    self.register_buffer("_rights", rights)
    self._n_rules = rule_system.n_binary

    weights = rule_system.binary_weight_tensor()

    if learnable and self._n_rules > 0:
        self.weights = nn.Parameter(weights)

    else:
        self.register_buffer("weights", weights)

forward ¶

forward(chart: Tensor | None, semiring: ChartSemiring, **context) -> Tensor

Apply binary rules for one span cell (i, j).

PARAMETER	DESCRIPTION
`chart`	Unused; the cells are read from `chart_cells`. TYPE: `Tensor or None`
`semiring`	The scoring semiring. TYPE: `ChartSemiring`
`**context`	`i` and `j` (the span bounds), `chart_cells` (the filled cells keyed by span), and `n_categories`. DEFAULT: `{}`

RETURNS	DESCRIPTION
`Tensor`	The `(batch, C)` scores for cell `(i, j)`, aggregated over every split point.

Source code in src/quivers/stochastic/span.py

def forward(
    self,
    chart: torch.Tensor | None,
    semiring: ChartSemiring,
    **context,
) -> torch.Tensor:
    """Apply binary rules for one span cell (i, j).

    Parameters
    ----------
    chart : torch.Tensor or None
        Unused; the cells are read from ``chart_cells``.
    semiring : ChartSemiring
        The scoring semiring.
    **context
        ``i`` and ``j`` (the span bounds), ``chart_cells`` (the
        filled cells keyed by span), and ``n_categories``.

    Returns
    -------
    torch.Tensor
        The ``(batch, C)`` scores for cell ``(i, j)``, aggregated
        over every split point.
    """
    i = context["i"]
    j = context["j"]
    chart_cells = context["chart_cells"]
    n_categories = context["n_categories"]

    _results = cast(torch.Tensor, self._results)
    _lefts = cast(torch.Tensor, self._lefts)
    _rights = cast(torch.Tensor, self._rights)

    if self._n_rules == 0:
        return torch.full(
            (chart_cells[(i, i + 1)].shape[0], n_categories),
            semiring.zero,
            device=_results.device,
        )

    parts = []

    for k in range(i + 1, j):
        left_cell = chart_cells[(i, k)]
        right_cell = chart_cells[(k, j)]

        left_scores = left_cell[:, _lefts]
        right_scores = right_cell[:, _rights]
        combined = semiring.times(left_scores, right_scores)

        if self._n_rules > 0:
            combined = semiring.times(
                combined,
                self.weights.unsqueeze(0),
            )

        parts.append(combined)

    stacked = torch.stack(parts, dim=0)
    split_scores = semiring.plus(stacked, dim=0)

    return _scatter_semiring(
        split_scores,
        _results,
        n_categories,
        split_scores.shape[0],
        device=_results.device,
        semiring=semiring,
    )

UnarySpanDeduction ¶

UnarySpanDeduction(rule_system: RuleSystem, learnable: bool = True, iterations: int = 3)

Bases: Deduction

Unary rule application, iterated to approximate fixpoint.

PARAMETER	DESCRIPTION
`rule_system`	The structural rules. TYPE: `RuleSystem`
`learnable`	Whether rule weights are learnable. TYPE: `bool` DEFAULT: `True`
`iterations`	Number of fixpoint iterations. TYPE: `int` DEFAULT: `3`

Source code in src/quivers/stochastic/span.py

def __init__(
    self,
    rule_system: RuleSystem,
    learnable: bool = True,
    iterations: int = 3,
) -> None:
    super().__init__()

    unary = rule_system.unary_tensors()

    if unary is not None:
        self.register_buffer("_results", unary[0])
        self.register_buffer("_inputs", unary[1])

    else:
        self.register_buffer(
            "_results",
            torch.zeros(0, dtype=torch.long),
        )
        self.register_buffer(
            "_inputs",
            torch.zeros(0, dtype=torch.long),
        )

    self._n_rules = rule_system.n_unary
    self._iterations = iterations

    weights = rule_system.unary_weight_tensor()

    if learnable and self._n_rules > 0:
        self.weights = nn.Parameter(weights)

    else:
        self.register_buffer("weights", weights)

has_rules `property` ¶

has_rules: bool

Whether this deduction has any unary rules.

forward ¶

forward(chart: Tensor, semiring: ChartSemiring, **context) -> Tensor

Apply unary rules to a cell tensor.

PARAMETER	DESCRIPTION
`chart`	A `(batch, C)` cell tensor. TYPE: `Tensor`
`semiring`	The scoring semiring. TYPE: `ChartSemiring`
`**context`	Unused. DEFAULT: `{}`

RETURNS	DESCRIPTION
`Tensor`	The updated `(batch, C)` cell after the configured number of unary iterations.

Source code in src/quivers/stochastic/span.py

def forward(
    self,
    chart: torch.Tensor,
    semiring: ChartSemiring,
    **context,
) -> torch.Tensor:
    """Apply unary rules to a cell tensor.

    Parameters
    ----------
    chart : torch.Tensor
        A ``(batch, C)`` cell tensor.
    semiring : ChartSemiring
        The scoring semiring.
    **context
        Unused.

    Returns
    -------
    torch.Tensor
        The updated ``(batch, C)`` cell after the configured
        number of unary iterations.
    """
    cell = chart

    if not self.has_rules:
        return cell

    _results = cast(torch.Tensor, self._results)
    _inputs = cast(torch.Tensor, self._inputs)
    n_categories = cell.shape[1]

    for _ in range(self._iterations):
        input_scores = cell[:, _inputs]

        if self._n_rules > 0:
            input_scores = semiring.times(
                input_scores,
                self.weights.unsqueeze(0),
            )

        additions = _scatter_semiring(
            input_scores,
            _results,
            n_categories,
            cell.shape[0],
            device=cell.device,
            semiring=semiring,
        )

        cell = semiring.plus_pair(cell, additions)

    return cell

SpanGoal ¶

SpanGoal(start_idx: int)

Bases: Goal

Extract chart[start_cat, 0, seq_len].

PARAMETER	DESCRIPTION
`start_idx`	Index of the start category. TYPE: `int`

Source code in src/quivers/stochastic/span.py

def __init__(self, start_idx: int) -> None:
    super().__init__()
    self._start_idx = start_idx

forward ¶

forward(chart: Tensor) -> Tensor

Read the start category's score over the whole sentence.

PARAMETER	DESCRIPTION
`chart`	The dense chart of shape `(batch, C, seq_len, seq_len+1)`. TYPE: `Tensor`

RETURNS	DESCRIPTION
`Tensor`	The `(batch,)` scores at `chart[:, start, 0, seq_len]`.

Source code in src/quivers/stochastic/span.py

def forward(self, chart: torch.Tensor) -> torch.Tensor:
    """Read the start category's score over the whole sentence.

    Parameters
    ----------
    chart : torch.Tensor
        The dense chart of shape ``(batch, C, seq_len, seq_len+1)``.

    Returns
    -------
    torch.Tensor
        The ``(batch,)`` scores at ``chart[:, start, 0, seq_len]``.
    """
    seq_len = chart.shape[2]
    return chart[:, self._start_idx, 0, seq_len]

CKYSchedule ¶

Bases: Schedule

Bottom-up CKY: process spans in increasing length order.

For each span length 2..n: 1. Apply binary deductions for each cell (i, i+span_len). 2. Apply unary deductions to the resulting cell.

run ¶

run(chart: SpanChart, deductions: ModuleList, semiring: ChartSemiring) -> Tensor

Fill the chart bottom-up and return it as a dense tensor.

PARAMETER	DESCRIPTION
`chart`	The chart `LexicalAxiom` produced, with its length-1 cells filled. TYPE: `SpanChart`
`deductions`	The `BinarySpanDeduction` and `UnarySpanDeduction` steps; other deductions are ignored. TYPE: `ModuleList`
`semiring`	The scoring semiring. TYPE: `ChartSemiring`

RETURNS	DESCRIPTION
`Tensor`	The dense chart of shape `(batch, C, seq_len, seq_len+1)`.

Source code in src/quivers/stochastic/span.py

def run(  # type: ignore[override]
    self,
    chart: SpanChart,
    deductions: nn.ModuleList,
    semiring: ChartSemiring,
) -> torch.Tensor:
    """Fill the chart bottom-up and return it as a dense tensor.

    Parameters
    ----------
    chart : SpanChart
        The chart `LexicalAxiom` produced, with its length-1
        cells filled.
    deductions : nn.ModuleList
        The `BinarySpanDeduction` and `UnarySpanDeduction`
        steps; other deductions are ignored.
    semiring : ChartSemiring
        The scoring semiring.

    Returns
    -------
    torch.Tensor
        The dense chart of shape ``(batch, C, seq_len, seq_len+1)``.
    """
    span_chart = chart
    cells = span_chart.cells
    seq_len = span_chart.seq_len
    n_categories = span_chart.n_categories

    # separate binary and unary deductions
    binary_deds = [d for d in deductions if isinstance(d, BinarySpanDeduction)]
    unary_deds = [d for d in deductions if isinstance(d, UnarySpanDeduction)]

    # apply unary rules to lexical cells first
    for i in range(seq_len):
        cell = cells[(i, i + 1)]

        for ud in unary_deds:
            if ud.has_rules:
                cell = ud(cell, semiring)

        cells[(i, i + 1)] = cell

    # fill chart bottom-up
    for span_len in range(2, seq_len + 1):
        for i in range(seq_len - span_len + 1):
            j = i + span_len

            # binary step: accumulate across all binary deductions
            cell = None

            for bd in binary_deds:
                contrib = bd(
                    None,
                    semiring,
                    i=i,
                    j=j,
                    chart_cells=cells,
                    n_categories=n_categories,
                )

                if cell is None:
                    cell = contrib

                else:
                    cell = semiring.plus_pair(cell, contrib)

            if cell is None:
                cell = torch.full(
                    (span_chart.batch, n_categories),
                    semiring.zero,
                    device=span_chart.device,
                )

            # unary step
            for ud in unary_deds:
                if ud.has_rules:
                    cell = ud(cell, semiring)

            cells[(i, j)] = cell

    # assemble into dense tensor
    return span_chart.to_tensor()

Deductive Systems, Rule Schemas, and Span Components¶