Effect Schema Lifting

class_directed_lifts(base_schema, effect) and lift_rule_set(base_schemas, effects) emit lifted SchemaDecls for the typeclasses inhabited by an effect.

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.

PARAMETER	DESCRIPTION
distributive_law	The law whose outer and inner monads the schema exchanges. TYPE: DistributiveLaw
base_schema	The schema whose name the swap schema's name extends; the name swap is used when omitted. TYPE: SchemaDecl or None DEFAULT: None

RETURNS	DESCRIPTION
SchemaDecl	The swap_TU schema T(U(X)) -> U(T(X)).

RAISES	DESCRIPTION
TypeError	If distributive_law is not a DistributiveLaw.

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).

    Parameters
    ----------
    distributive_law : DistributiveLaw
        The law whose outer and inner monads the schema exchanges.
    base_schema : SchemaDecl or None
        The schema whose name the swap schema's name extends; the
        name ``swap`` is used when omitted.

    Returns
    -------
    SchemaDecl
        The ``swap_TU`` schema ``T(U(X)) -> U(T(X))``.

    Raises
    ------
    TypeError
        If ``distributive_law`` is not a `DistributiveLaw`.
    """
    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.

PARAMETER	DESCRIPTION
distributive_laws	The registered distributive laws. TYPE: tuple of DistributiveLaw

RETURNS	DESCRIPTION
tuple of SchemaDecl	One swap schema per law, in the order given.

RAISES	DESCRIPTION
TypeError	If an entry is not a DistributiveLaw.

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.

    Parameters
    ----------
    distributive_laws : tuple of DistributiveLaw
        The registered distributive laws.

    Returns
    -------
    tuple of SchemaDecl
        One swap schema per law, in the order given.

    Raises
    ------
    TypeError
        If an entry is not a `DistributiveLaw`.
    """
    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.

PARAMETER	DESCRIPTION
base_schemas	The base rule set. TYPE: tuple of SchemaDecl
effects	The effect instances to lift each base schema under. TYPE: tuple

RETURNS	DESCRIPTION
tuple of SchemaDecl	The base schemas followed by every lift, grouped by base schema and then by effect.

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.

    Parameters
    ----------
    base_schemas : tuple of SchemaDecl
        The base rule set.
    effects : tuple
        The effect instances to lift each base schema under.

    Returns
    -------
    tuple of SchemaDecl
        The base schemas followed by every lift, grouped by base
        schema and then by effect.
    """
    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)