gargamelle-effect — Arrow Rope Orchestration, \(O(1)\) Variant Router & Coyoneda Fusion

1. Executive Summary & Problem Framing

Extensible effect systems in modern Haskell typically suffer from three fundamental limitations:

1. \(O(N)\) Dynamic Dispatch Overhead: Conventional extensible effect stacks (such as freer-simple or polysemy) route effects by walking type-level lists at runtime via Member eff r dictionaries, incurring linear traversals, pointer indirection, and heap allocation on the hot path.
2. Coupled Execution and Inability to Fail-Fast: Monadic effect frameworks interleave computation with interpretation. Workflows cannot statically audit host dependencies (e.g., verifying whether /usr/bin/bwrap or SQLite database paths exist) prior to executing side effects.
3. Intermediate Arrow Pipeline Allocations: Chaining pure post-processing transformations onto arrow pipelines introduces intermediate arr lifting frames and redundant compositions.

gargamelle-effect solves these challenges by combining the Kernmantle Arrow Rope model with Polytropos \(O(1)\) jump-table dispatch:

• Hardware-Level \(O(1)\) Variant Routing: Dispatches open sum variants through an unboxed array jump-table in \(O(1)\) CPU time.
• Pure Profunctor Optics: Views and updates structural records and variants in-place via Polytropos.Profunctors.
• Coyoneda Pipeline Fusion: Defers and fuses pure post-processing transformations into a single atomic composition step via the Coyoneda lemma.
• Config-Time Environment Auditing: Inspects required capabilities and verifies physical host prerequisites before executing a single workflow effect.

2. Mathematical Foundations & Theoretical Invariants

2.1 The Arrow Rope Functor

A Kernmantle Rope separates the computation arrow from the effect interpreter mantle:

                  ┌─────────────────────────────────────────┐
                  │          Handlers core (Mantle)         │
                  └────────────────────┬────────────────────┘
                                       │ (Supplied at invocation)
                                       ▼
  Input a ════════════════════► [Rope core mantle] ════════════════════► Output b
                     (Arrow Pipeline Composition: >>>, ***, &&&)

Formally, Rope is a reader over the mantle of handlers: \[\operatorname{Rope}(\operatorname{core}, \operatorname{mantle}, a, b) \cong \operatorname{Handlers}(\operatorname{core}) \to \operatorname{core}(a, b)\]

This guarantees that the pipeline topology is purely structural, allowing the exact same workflow to run under pure in-memory mock handlers during unit tests and production OS sandboxes during execution.

2.2 \(O(1)\) Variant Jump-Table Physics

In Polytropos, open sums (variants) are represented by an unboxed constructor tag and a flat SmallArray of payload slots: \[\operatorname{Rep} = \langle \operatorname{tag} : \operatorname{Int}, \operatorname{slots} : \operatorname{SmallArray} \, \operatorname{Any} \rangle\]

The VariantRouter constructs a contiguous lookup table of handler arrows indexed by tag:

Incoming Variant: [Tag = 1 | Slots = [Any "payload"]]
                         │
                         ▼  (O(1) Array Indexing)
VariantRouter Table:
  ┌───┬───────────────────────────────────────────────────────┐
  │ 0 │ Handler 0: \rep -> Kleisli (handleTag0 (getSlot 0 rep))│
  ├───┼───────────────────────────────────────────────────────┤
  │ 1 │ Handler 1: \rep -> Kleisli (handleTag1 (getSlot 0 rep))│ ──► Dispatched in O(1)
  ├───┼───────────────────────────────────────────────────────┤
  │ 2 │ Handler 2: \rep -> Kleisli (handleTag2 (getSlot 0 rep))│
  └───┴───────────────────────────────────────────────────────┘

The CPU executes a single indirect jump: \[\operatorname{handler} = \operatorname{indexSmallArray} \, \operatorname{table} \, \operatorname{tag}\] \[\operatorname{action} = \operatorname{handler}(\operatorname{slots})\]

Dispatch executes in \(O(1)\) time with zero heap allocation on the hot path.

2.3 Coyoneda Pipeline Fusion

By the Coyoneda lemma, any functorial or arrow transformation can be accumulated purely: \[\operatorname{Coyoneda}(F, A) \cong \exists B.\, (B \to A) \times F(B)\]

  fmap f          fmap g          fmap h
(───────►)      (───────►)      (───────►)
   Coyoneda id r  ──► Coyoneda f r ──► Coyoneda (g . f) r ──► Coyoneda (h . g . f) r
                                                                    │
                                                 fuseRope           ▼
                                                     arr (h . g . f) <<< r

Rather than inserting 3 intermediate arr lifting frames, fuseRope materializes the accumulated Haskell function composition \((h \circ g \circ f)\) in a single composition step.

3. Module Architecture & Repertoire Breadth

The package exports 9 modules bridging Kernmantle arrows and Polytropos structural semantics:

4. Executable Worked Examples

4.1 Constructing and Running an Arrow Rope Pipeline

{-# LANGUAGE OverloadedStrings #-}

module ExampleRope where

import Control.Arrow (Kleisli(..))
import Control.Category ((.))
import Prelude hiding ((.))
import Data.Text (Text)
import Data.Word (Word64)
import Effect.Rope
import Effect.Handlers

-- Compose a sequential effect pipeline: log initialization then fetch random seed
samplePipeline :: Rope (Kleisli (Either Text)) mantle () Word64
samplePipeline = getRandomWordRope . logInfoRope "Initializing workflow pipeline"

-- Execute using pure in-memory mock handlers
runMock :: Either Text Word64
runMock = runKleisli (runRope samplePipeline pureMockHandlers) ()
-- Returns: Right 42

4.2 Fusing Pure Post-Processing Transformations via Coyoneda

module ExampleFusion where

import Control.Arrow (arr, Kleisli(..))
import Data.Text (Text)
import Effect.Rope
import Effect.Handlers
import Gargamelle.Effect.Fusion

-- Base arrow multiplying input by 2
baseArrow :: Rope (Kleisli (Either Text)) mantle Int Int
baseArrow = ropeFromCore (arr (* 2))

-- Fuse pure arithmetic without intermediate arrow frames
fusedPipeline :: Rope (Kleisli (Either Text)) mantle Int Int
fusedPipeline = fuseRope $
  fuseRopeMap (+ 10) $
    fuseRopeMap (+ 5) $
      liftCoyoneda baseArrow

-- Executing: ((10 * 2) + 5) + 10 = 35
runFusedPipe :: Either Text Int
runFusedPipe = runKleisli (runRope fusedPipeline pureMockHandlers) 10
-- Returns: Right 35

5. Integration Points & Subsystem Boundaries

gargamelle-effect sits at Tier 3 (Substrate & Semantics) of the architecture:

┌────────────────────────────────────────────────────────┐
│               Downstream Consumers                     │
│  - gargamelle-workflow: Sheaf-Gated CEGIS Loop         │
│  - gargamelle-sandbox: Bubblewrap Execution Strands    │
│  - gargamelle-persistence: Beam SQLite Transactions    │
└──────────────────────────▲─────────────────────────────┘
                           │
                 [gargamelle-effect]
                           │
┌──────────────────────────▼─────────────────────────────┐
│               Upstream Substrates                      │
│  - kernmantle (>= 0.1.0.1): Core Rope Arrow abstraction│
│  - polytropos-core (>= 0.1.0.1): Flat SmallArray Rep   │
│  - polytropos-profunctors (>= 0.1.0.1): Lenses, Prisms │
│  - kan-extensions (>= 5.2): Coyoneda construction      │
└────────────────────────────────────────────────────────┘

6. Diagnostic & Troubleshooting Guide

6.1 Host Sandbox Binary Missing at Configuration Time

• Symptom: validateWorkflowResources returns Left ["Sandbox binary missing: /usr/bin/bwrap"].
• Root Cause: Bubblewrap (bwrap) is not installed or not in the specified path.
• Remedy: Ensure Bubblewrap is installed (sudo apt-get install bubblewrap or Nix environment pkgs.bubblewrap).

6.2 Variant Router Tag Bounds Overflow

• Symptom: indexSmallArray: index out of bounds during variant routing.
• Root Cause: A variant with tag \(K \ge N\) was routed through a VariantRouter built with \(N\) handlers.
• Remedy: Ensure makeRouter receives handlers for all possible tags in the open variant row.

Part of the Gargamelle Verification Suite.