Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

The type-level landscape

This chapter is the design-level account of how the library’s functional concepts sit on top of Rust’s type system. It assumes familiarity with the Lift, Wrap dispatch, and SeedNode<N> chapters — and an interest in why those shapes are what they are, beyond just what they do.

The library is a type-level functional kernel. Every transformation — fold-phase rewrite, axis change, seed-closure — is a categorical construct (natural transformation, type-level function, indexed family) encoded in Rust’s syntax. Where the encoding works smoothly the library reads like ordinary Rust; where it doesn’t, the friction shows up as verbose projection chains, deliberate (bi-suffixed) bidirectionality, or the per-domain split. Each of those is structural, not stylistic.

GATs are higher-order functions

The first principle (lifted directly from Crichton, “GATs are HOFs”): a Generic Associated Type is a type-level function. A GAT type Of<X>; on a trait T is a function X ↦ T::Of<X>, where the function’s body is the impl’s expansion.

In hylic, the canonical GAT is Wrap::Of:

#![allow(unused)]
fn main() {
/// Type-level dispatch for the chain's input N. Each
/// [`Stage2Base`](super::Stage2Base) declares which `Wrap` it uses;
/// `WrapShared` / `WrapLocal` impls carry the per-domain lift
/// construction.
pub trait Wrap {
    /// The wrapped node type for a given user-facing N.
    type Of<UN: Clone + 'static>: Clone + 'static;
}
}

Wrap is a trait with a single GAT. Two impls give two functions:

Identity::Of  : Type → Type   ≡  λUN. UN              -- identity
SeedWrap::Of  : Type → Type   ≡  λUN. SeedNode[UN]    -- one-tag wrap

These are not “associated types you happen to read off an impl”; they are first-class type-level functions. The library uses them where a Haskell library would use f a quantified over f, or a Scala 3 library would use [F[_]]. In Rust, the type lambda is encoded as a trait with a GAT, and applied via the projection <W as Wrap>::Of<UN>.

Lift as a triple of natural transformations

A Fold<N, H, R> has three phases:

init        :  N → H
accumulate  :  (H, R) → ()       (mutates H)
finalize    :  H → R

A Lift transforms one fold algebra into another. Per the categorical intuition, that is a triple of natural transformations — one per phase. The general primitive Shared::phases_lift exposes exactly that structure: it takes three phase mappers, each a function that takes the prior fold’s phase as a value and returns the new fold’s phase:

init_mapper  :  (N → H)              → (N₂ → H₂)
acc_mapper   :  ((H, R) → ())        → ((H₂, R₂) → ())
fin_mapper   :  (H → R)              → (H₂ → R₂)

Compare with the wrap_init user closure:

W : (N, prior_init) → H        -- curried form of the init_mapper

prior_init is the prior fold’s init phase, currying init_mapper into a friendlier shape: instead of “give me a function, get a function,” “give me a node and a function-on-nodes, get a value.” The user’s orig argument is not a callback; it is the prior phase as a first-class value, which composition needs as input. Drop the parameter and you no longer have a phase mapper; you have a phase replacement. Lift composition would stop being categorical.

This is the answer to “why does every wrap_* sugar take an orig argument I sometimes don’t use.” The closure is a phase mapper. The user not consulting orig is an identity-mapped composition — the no-op natural transformation at that phase, which is structurally fine but textually looks redundant.

Why CPS in Lift::apply

A direct apply signature would return the transformed triple:

apply : (Grow[Seed, N], Graph[N], Fold[N, H, R])
      → (Grow[Seed, N₂], Graph[N₂], Fold[N₂, H₂, R₂])

Each component is a domain-associated GAT and each axis is an associated type of the lift. After three composed lifts the return type involves three nested levels of associated-type projection, and no single name in the language admits the result without spelling all of them out. Rust’s type inference does not span that distance.

CPS — continuation-passing style — sidesteps the unnameable.

#![allow(unused)]
fn main() {
/// Domain-generic transformer over the `(treeish, fold)` pair.
///
/// A `Lift` rewrites the graph side and/or the fold side, possibly
/// changing their carrier types, and hands the result to a
/// continuation. The caller's continuation-return type `T` flows
/// through, so the chain of output types stays inferred across
/// composition (`ComposedLift<L1, L2>`).
///
/// Grow is deliberately absent from this signature. Only the Seed
/// finishing lift ([`SeedLift`](super::SeedLift)) needs a grow
/// input; it is composed internally by
/// `hylic_pipeline::PipelineExecSeed::run` and does not travel as
/// a 3-slot signature through the `Lift` trait.
///
/// See [Lifts](https://hylic.balcony.codes/concepts/lifts.html).
pub trait Lift<D, N, H, R>
where D: Domain<N> + Domain<Self::N2>,
      N: Clone + 'static, H: Clone + 'static, R: Clone + 'static,
{
    /// Output node type after the lift has been applied.
    type N2:   Clone + 'static;
    /// Output heap type after the lift has been applied.
    type MapH: Clone + 'static;
    /// Output result type after the lift has been applied.
    type MapR: Clone + 'static;

    /// Apply the lift to `(treeish, fold)` and invoke `cont` with
    /// the transformed pair.
    fn apply<T>(
        &self,
        treeish: <D as Domain<N>>::Graph<N>,
        fold:    <D as Domain<N>>::Fold<H, R>,
        cont: impl FnOnce(
            <D as Domain<Self::N2>>::Graph<Self::N2>,
            <D as Domain<Self::N2>>::Fold<Self::MapH, Self::MapR>,
        ) -> T,
    ) -> T;
}
}

apply takes a continuation cont: impl FnOnce(triple) -> T. The continuation’s return type T flows out unchanged. Inference threads each intermediate triple through the continuation locally; nothing has to be named at the top level. The composition reads as nested closure calls; the executor’s final T propagates outward through every intermediate apply.

This is the same trick categorically: instead of returning a value of some object in a category, take a hom-set element (a morphism out of that object) and apply it. Rust’s impl Trait argument is a way of saying “a morphism from this object to something”; the something is whatever shows up in the call chain.

The two-hop projection

Stage2Pipeline<Base, L> is one struct. Base is Stage2Base:

#![allow(unused)]
fn main() {
/// A Stage-1 pipeline that can drive a Stage-2 chain. Carries the
/// `Wrap` selection plus the run-time machinery (pre-lift, root
/// reference, run-input shape).
///
/// Inherits `TreeishSource` so the `(treeish<N>, fold<N, H, R>)` pair is
/// yielded through one canonical path; `with_treeish` is the single
/// place per-base storage shapes are read.
///
/// `PreLift` is intentionally unbounded at the trait level. The
/// `Stage2Pipeline::run` impl adds the `Lift<…, N2 = <Wrap>::Of<N>>`
/// bound at use time; that keeps the supertrait surface free of the
/// `Domain<<Wrap>::Of<N>>` obligation that would otherwise propagate
/// through every site naming `Stage2Base`.
pub trait Stage2Base: TreeishSource + Sized {
    /// Type-level dispatcher for the chain's input N.
    /// `Identity` → `Of<UN> = UN` (treeish-rooted).
    /// `SeedWrap` → `Of<UN> = SeedNode<UN>` (seed-rooted).
    type Wrap: Wrap;

    /// The user-facing N (the type user lambdas type at). Equal to
    /// `Self::N` for every shipped base; kept distinct for
    /// documentation symmetry with the sugar surface, which threads
    /// `UN` as a method-level parameter.
    type UserN: Clone + 'static;

    /// What `.run(...)` accepts as its second argument. Parameterised
    /// by `CurN`, the user-facing N at the chain tip (i.e. after any
    /// `map_n_bi` lifts; `CurN = Self::N` if the chain doesn't change
    /// the user N).
    ///
    /// `Identity`-Wrap bases: `&'i CurN` (a borrowed post-chain root).
    /// `SeedWrap` bases: an owned `(seeds, entry_heap)` pair (the
    /// `CurN` parameter is unused at the value level — `EntryRoot` is
    /// constructible at any inner type).
    type RunInputs<'i, CurN: Clone + 'static>;

    /// The lift composed at the head of the run-time chain.
    /// `IdentityLift` for treeish-rooted, `SeedLift` for seed-rooted.
    /// Pre-lift transforms `(treeish<N>, fold<N,H,R>)` into
    /// `(treeish<Wrap::Of<N>>, fold<Wrap::Of<N>, H, R>)` without
    /// touching H or R.
    ///
    /// Unbounded at the trait level — see the trait-level note.
    /// The `Stage2Pipeline::run` impl adds
    /// `Self::PreLift: Lift<…, N2 = <Wrap>::Of<N>, MapH = H, MapR = R>`
    /// at use time.
    type PreLift;

    /// Build the pre-lift from inputs (consuming the parts of inputs
    /// the lift captures), then yield it together with the executor's
    /// post-chain root reference to the continuation.
    ///
    /// The continuation receives the pre-lift by value (consumed when
    /// applied to the (treeish, fold) pair) and the root by reference,
    /// at the post-chain type `<Self::Wrap as Wrap>::Of<CurN>`. The
    /// reference is valid for the entire duration of `cont`.
    ///
    /// `Identity` case: pre-lift is `IdentityLift`; the root is the
    /// `&CurN` extracted from `inputs`.
    /// `SeedWrap` case: pre-lift is `SeedLift::from_*_grow(...)`,
    /// consuming `inputs.0` (entry seeds) and `inputs.1` (entry heap);
    /// the root is `&SeedNode::entry_root::<CurN>()`, constructed
    /// locally in this frame and alive for `cont`'s lifetime.
    fn provide_run_essentials<CurN: Clone + 'static, T>(
        &self,
        inputs: Self::RunInputs<'_, CurN>,
        cont: impl FnOnce(Self::PreLift,
                          &<Self::Wrap as Wrap>::Of<CurN>) -> T,
    ) -> T;
}
}

The chain’s input N is <Base::Wrap as Wrap>::Of<UN> — a two-hop projection: first project Base::Wrap (a type), then project that type through the Wrap::Of GAT at parameter UN. The full path:

<<Self::Base as Stage2Base>::Wrap as Wrap>::Of<UN>
   |__________ ___________|     |__ __|     |
              v                    v        v
        find Base from        find that     apply
        Self's Stage2Base     type's Wrap   Wrap::Of
        impl                  impl          at UN

For Self::Base = TreeishPipeline<…>, the chain unfolds to Identity::Of<UN> = UN. For Self::Base = SeedPipeline<…>, it unfolds to SeedWrap::Of<UN> = SeedNode<UN>. Both reduce; both are a single projection chain; both work in every position the library uses (method-return type, where-clause, GAT projection).

What broke the first attempt

The original Phase-4 attempt had the sugar trait body call into a helper trait whose return type was <Self as Helper<UN>>::N, while the sugar method’s declared return type was the full <<Base::Wrap as Wrap>::Of<UN>> projection. Both reduced to the same concrete type for any specific impl, but the paths through the type system differed. The trait solver does not bridge two extensionally equal but syntactically distinct projections inside a default body.

The fix: don’t bridge. Have the sugar body call directly through the projection that already names the chain’s input N. The same projection sits in the return-type slot, the where-clause, and the build-method call. Rust’s solver verifies syntactic equality in each position; no reduction across distinct projection chains is ever required.

Variance is structural, not friction

Every axis-change sugar with _bi in its name (map_n_bi, map_r_bi, map_node_bi, map_seed_bi) takes a pair (co, contra). That is not Rust-specific verbosity. N, H, R are all invariant in a fold algebra — N appears in init’s argument (contravariant) and in Graph<N>’s child output (covariant); R appears in finalize’s output and in accumulate’s child input. An invariant type can only be transformed by an isomorphism; an isomorphism in types is a pair of arrows.

Scala 3 needs the pair too. So does Haskell. The library’s choice is to expose the pair explicitly, named at the call site, rather than hide it behind an Iso or Bijection typeclass. The “extra” closure is the structural witness that the transform is an iso. In an invariant world, that witness can’t be elided.

Send + Sync as a per-domain axis

Domains differ on closure storage and bound:

DomainClosure cellBound on user closures
SharedArc<dyn Fn …>Send + Sync + 'static
LocalRc<dyn Fn …>'static
OwnedBox<dyn Fn …>'static (and one-shot)

The asymmetry is real: Shared parallel executors share the fold across threads, so the fold’s closures have to be Send + Sync; Local’s Rc storage actively forbids Send + Sync on captured state, allowing things like Rc<RefCell<…>> that the Shared form rejects.

Send + Sync cannot be expressed as a uniform parameterisation of one trait without macros (the bound is on a concrete closure type, not a projection-able shape). Sugars and the build dispatcher are therefore split per domain: WrapShared/WrapLocal, Stage2SugarsShared/Stage2SugarsLocal, SeedSugarsShared/SeedSugarsLocal. The trait bodies read identically line for line; only the bound differs.

Bounds at consumption, not construction

Stage2Pipeline::then_lift is unconstrained at the struct level — pure construction:

#![allow(unused)]
fn main() {
    /// Post-compose `outer` onto the chain. Pure struct construction;
    /// no bounds. The composition's *meaningfulness* is enforced where
    /// the chain is consumed (`.run_*`, `TreeishSource`).
    pub fn then_lift<L2>(
        self,
        outer: L2,
    ) -> Stage2Pipeline<Base, ComposedLift<L, L2>> {
        Stage2Pipeline {
            base:     self.base,
            pre_lift: ComposedLift::compose(self.pre_lift, outer),
        }
    }
}

A pipeline whose chain wouldn’t actually .run is structurally typeable. The compile-time check happens at consumption: .run_* and the TreeishSource impl carry the chain-validity bounds. Construction is a builder; validity is a runner concern. Imposing chain bounds at every .then_lift would force every intermediate composition to be runnable, which loses the “construct freely, validate at the consumption boundary” pattern that lets chained sugars compose without each one having to fully type-prove the chain so far.

What this buys at runtime

Nothing has runtime overhead. The sugar trait monomorphises into a chain of ComposedLift types; the type tree records every junction; inlining flattens the chain into a single tree walk that produces one (treeish, fold) pair. The executor never sees the chain — only its collapsed result. Wrap dispatch resolves at compile time per instantiation. The verbose projections in error messages are the price of carrying that information through the type system; the compiled binary has none of it.

What remains as friction

Three things, all structural:

  1. No first-class higher-kinded types. Wrap::Of is the closest approximation. Verbose two-hop projections are the cost.

  2. No type-level pattern matching (no Scala 3 match types). Rust cannot decompose SeedNode<UN> into UN at the type level. If a trait’s bound says L::N2 = SeedNode<UN>, UN must be supplied from elsewhere (e.g., a closure argument’s inferred type) — Rust will not invert the constructor.

  3. No macros. The Shared/Local mirror could be one file with per-domain bound sugar, but the codebase declines macro-generated trait bodies. The duplication is documented and accepted.

What is not friction: bidirectional axis transforms (universal), orig callbacks in wrap_init (structural natural-transformation shape), CPS in apply (only way to thread unnameable returns). Those are the right shapes; Rust just exposes them at the level the abstraction needs.

Wrap_init as a phase mapper

The wrap_init family deserves a closer read because the user closure looks like a callback-with-fallthrough but is actually a curried phase mapper. The sugar’s user signature is

W : (N, prior_init: dyn Fn N → H) → H

curried from the underlying

init_mapper : (N → H) → (N → H)
            ≡ Fn(prior_init) → Fn(N → H)        -- uncurried
            ≡ Fn(N, prior_init) → H              -- curried; same content

The sugar’s body in the library realises this:

#![allow(unused)]
fn main() {
    pub fn wrap_init_lift<N, H, R, W>(wrapper: W) -> ShapeLift<Shared, N, H, R, N, H, R>
    where
        N: Clone + 'static, H: Clone + 'static, R: Clone + 'static,
        W: Fn(&N, &dyn Fn(&N) -> H) -> H + Send + Sync + 'static,
    {
        let w = Arc::new(wrapper);
        // init_mapper: (N → H) → (N → H). Curries the user's W with the prior init.
        let mi = move |old: Arc<dyn Fn(&N) -> H + Send + Sync>|
                   -> Arc<dyn Fn(&N) -> H + Send + Sync> {
            let w = w.clone();
            Arc::new(move |n: &N| w(n, &*old))
        };
        Shared::phases_lift::<N, H, R, H, R, _, _, _>(
            mi,
            Shared::identity_acc_mapper::<H, R>(),
            Shared::identity_fin_mapper::<H, R>(),
        )
    }
}

Reading the body: take the user wrapper w, return a function from the prior init old to a new init that, on each n, calls w(n, &*old). The closure-passed-in is the prior phase, exposed as a value. That is the structural definition of a phase mapper. The “intercept” framing is incidental; the categorical content is compose this layer’s natural transformation with the prior layer’s.

The same shape recurs, with appropriate types, in wrap_accumulate_lift and wrap_finalize_lift. The general primitive they all collapse to is Shared::phases_lift — three phase mappers, one per phase, each taking the prior phase and producing the next.

Reading list