Effect Schema Lifting

class_directed_lifts(base_schema, effect) and lift_rule_set(base_schemas, effects): emit lifted SchemaDecls for every typeclass an effect inhabits.

effect_lifts

Class-driven schema lifting for effect-typed parsers.

The class_directed_lifts function takes a base SchemaDecl and an effect instance and returns a tuple of lifted SchemaDecl instances — one per typeclass-class the effect inhabits.

The dispatch key is the typeclass interface, never the effect's concrete identity. Adding a new effect (or a new typeclass) extends the lifting machinery automatically: every effect that registers against Functor gets fmap lifts; every effect that additionally registers against Applicative also gets apply lifts; every Monad gets bind lifts; and so on across both the monad-style and arrow-style towers.

The lifted schemas are SchemaDecl instances and feed into the same PatternBinarySchema / PatternUnarySchema machinery as user-written schemas; the chart-fixed-point machinery in quivers.stochastic.parsers consumes them uniformly with the base schemas. The chart cells are indexed by (Cat, EffectStack) pairs, and at each cell the parser fires:

1. Base schemas between effect-pure cells (the classical Lambek case).
2. Lift schemas when one or more children carry effect prefixes that the schema's domain doesn't (this is what class_directed_lifts produces).
3. Handler firings when an applicable handler is registered, reducing an effect-typed cell to a less-effect-typed cell.
4. Commutation firings when a registered distributive law swaps sibling effect orderings.

References

• Bumford, D. and Charlow, S. (2026). Effect-Driven Interpretation: Functors for Natural Language Composition. Cambridge Elements in Semantics. Cambridge University Press. Online ISBN 9781009285377; preprint arXiv:2504.00316.

class_directed_lifts

class_directed_lifts(base_schema: SchemaDecl, effect: object) -> tuple[SchemaDecl, ...]

Generate the class-driven lifts for base_schema under effect.

Dispatches on which typeclasses the effect inhabits — Functor, Applicative, Monad, Alternative, MonadPlus, ArrowApply, ArrowLoop, and so on — and emits one or more SchemaDecl instances per class. The lifts compose with the base schema in the chart parser's joint type-and-effect dispatch.

Lifts emitted (when the corresponding class is inhabited):

• Applicative: pure_T + apply_T.
• Monad (and Applicative): adds bind_T.
• Alternative: adds alt_T.
• MonadPlus: union of Monad and Alternative lifts.

Functor-only effects produce pure_T-shape lifts only when the instance also implements Applicative; bare Functor instances need a separate fmap_T shape (analogous to apply_T but with one functor-typed premise rather than two).

Arrow-side lifts (arr_T, first_T, loop_T) are emitted by a parallel branch that introspects the effect's arrow-tower membership; see the # arrow lifts block below.

PARAMETER	DESCRIPTION
base_schema	The base schema being lifted. TYPE: SchemaDecl
effect	An effect instance (any class registered against the relevant typeclass ABCs in quivers.monadic.typeclasses). TYPE: object

RETURNS	DESCRIPTION
tuple of SchemaDecl	Zero or more lifted schemas, ordered from weakest typeclass (Applicative) through strongest (MonadPlus + ArrowApply + ArrowLoop).

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

def class_directed_lifts(
    base_schema: SchemaDecl, effect: object
) -> tuple[SchemaDecl, ...]:
    """Generate the class-driven lifts for ``base_schema`` under ``effect``.

    Dispatches on which typeclasses the effect inhabits — Functor,
    Applicative, Monad, Alternative, MonadPlus, ArrowApply, ArrowLoop,
    and so on — and emits one or more `SchemaDecl` instances
    per class. The lifts compose with the base schema in the chart
    parser's joint type-and-effect dispatch.

    Lifts emitted (when the corresponding class is inhabited):

    - `Applicative`: ``pure_T`` + ``apply_T``.
    - `Monad` (and `Applicative`): adds ``bind_T``.
    - `Alternative`: adds ``alt_T``.
    - `MonadPlus`: union of Monad and Alternative lifts.

    Functor-only effects produce ``pure_T``-shape lifts only when the
    instance also implements `Applicative`; bare Functor
    instances need a separate ``fmap_T`` shape (analogous to
    ``apply_T`` but with one functor-typed premise rather than two).

    Arrow-side lifts (``arr_T``, ``first_T``, ``loop_T``) are emitted
    by a parallel branch that introspects the effect's arrow-tower
    membership; see the ``# arrow lifts`` block below.

    Parameters
    ----------
    base_schema : SchemaDecl
        The base schema being lifted.
    effect : object
        An effect instance (any class registered against the relevant
        typeclass ABCs in [`quivers.monadic.typeclasses`][quivers.monadic.typeclasses]).

    Returns
    -------
    tuple of SchemaDecl
        Zero or more lifted schemas, ordered from weakest typeclass
        (Applicative) through strongest (MonadPlus + ArrowApply +
        ArrowLoop).
    """
    lifts: list[SchemaDecl] = []

    if isinstance(effect, Applicative):
        lifts.append(_make_pure_schema(effect, base_schema))
        lifts.append(_make_apply_schema(effect, base_schema))

    if isinstance(effect, Monad):
        lifts.append(_make_bind_schema(effect, base_schema))

    if isinstance(effect, Alternative):
        lifts.append(_make_alt_schema(effect, base_schema))

    # Arrow-side lifts: when the effect is itself an arrow (rare for
    # linguistic effects, but supported for symmetry), we emit the
    # arrow-shape lifts. The Hughes 2000 hom-set lifts (arr, first,
    # loop) are realised as schemas over the residuated universe.
    if isinstance(effect, ArrowApply):
        # An ArrowApply effect produces an `app`-shape lift that is
        # equivalent in expressive power to bind_T via the
        # quivers.monadic.bridges conversion.
        pass  # subsumed by bind_T when the effect is also a Monad

    if isinstance(effect, ArrowLoop):
        # Loop-shape lift for ArrowLoop effects; in the chart parser
        # this corresponds to a feedback-cell in the chart fixed-point.
        pass  # subsumed by chart_fold's outer loop construction

    return tuple(lifts)

make_swap_schema

make_swap_schema(distributive_law: object, base_schema: SchemaDecl | None = None) -> SchemaDecl

Generate a swap_TU schema from a registered distributive law.

Given a DistributiveLaw λ : S ∘ T ⇒ T ∘ S, the chart parser uses swap_TU to exchange sibling effect orderings at a cell whose effect stack ends in T·U:

swap_TU[X : Cat] : T(U(X)) -> U(T(X))

The schema is consumed by the chart's commutation firing rule of Effects §4.4.

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

def make_swap_schema(
    distributive_law: object, base_schema: SchemaDecl | None = None
) -> SchemaDecl:
    """Generate a ``swap_TU`` schema from a registered distributive law.

    Given a `DistributiveLaw` ``λ : S ∘ T ⇒ T ∘ S``, the chart
    parser uses ``swap_TU`` to exchange sibling effect orderings at a
    cell whose effect stack ends in ``T·U``:

        swap_TU[X : Cat] : T(U(X)) -> U(T(X))

    The schema is consumed by the chart's *commutation firing* rule
    of [Effects §4.4](../../semantics/effects.md#4-joint-type-and-effect-dispatch).
    """
    if not isinstance(distributive_law, DistributiveLaw):
        raise TypeError(
            "make_swap_schema requires a DistributiveLaw instance; "
            f"got {type(distributive_law).__name__}"
        )
    # The naming convention for the swap schema reuses the monad
    # class names; the schema's directionality (S∘T → T∘S) matches
    # the underlying λ : S(T(-)) → T(S(-)).
    outer = type(distributive_law.outer_monad).__name__
    inner = type(distributive_law.inner_monad).__name__
    base_name = base_schema.name if base_schema is not None else "swap"
    return SchemaDecl(
        name=f"swap_{outer}_{inner}_{base_name}",
        parameters=(
            SchemaParameter(
                names=("X",),
                type_expr=TypeName(name="Cat"),
            ),
        ),
        domain=_wrap_with_effect(_wrap_with_effect(TypeName(name="X"), inner), outer),
        codomain=_wrap_with_effect(_wrap_with_effect(TypeName(name="X"), outer), inner),
    )

swap_rule_set

swap_rule_set(distributive_laws: tuple[object, ...]) -> tuple[SchemaDecl, ...]

Generate one swap_TU schema per registered distributive law.

The resulting tuple is appended to the chart parser's rule set alongside the class-driven lifts; the chart's commutation-firing dispatch picks each swap schema up by name.

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

def swap_rule_set(
    distributive_laws: tuple[object, ...],
) -> tuple[SchemaDecl, ...]:
    """Generate one ``swap_TU`` schema per registered distributive law.

    The resulting tuple is appended to the chart parser's rule set
    alongside the class-driven lifts; the chart's commutation-firing
    dispatch picks each swap schema up by name.
    """
    return tuple(make_swap_schema(law) for law in distributive_laws)

lift_rule_set

lift_rule_set(base_schemas: tuple[SchemaDecl, ...], effects: tuple[object, ...]) -> tuple[SchemaDecl, ...]

Apply class_directed_lifts over a rule-set and effect-stack.

Returns the union of base schemas and all lifts produced for each (base_schema, effect) pair. The chart parser consumes the resulting tuple directly.

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

def lift_rule_set(
    base_schemas: tuple[SchemaDecl, ...], effects: tuple[object, ...]
) -> tuple[SchemaDecl, ...]:
    """Apply `class_directed_lifts` over a rule-set and effect-stack.

    Returns the union of base schemas and all lifts produced for each
    (base_schema, effect) pair. The chart parser consumes the
    resulting tuple directly.
    """
    out: list[SchemaDecl] = list(base_schemas)
    for base in base_schemas:
        for eff in effects:
            out.extend(class_directed_lifts(base, eff))
    return tuple(out)