specter-navigator-gadget

Core Concept

Integration of Specter (bidirectional navigation), Navigator (compiled path objects), and 3-MATCH (constraint satisfaction) into a unified system for structure traversal and transformation.

A Navigator is a compiled path expression that can be used for both selecting and transforming values within nested data structures. Each Navigator encodes one or more constraints (Gadgets) from a 3-SAT-like problem space.

Architecture

Key Components

1. Navigator - Compiled path expressions

struct Navigator
    path::Vector{NavigationStep}  # Steps in the traversal
    constraints::Vector{Gadget}   # 3-MATCH constraints
    cache_key::UInt64            # Hash for inline caching
end

2. Gadget - Individual constraint unit

struct Gadget
    name::String
    predicate::Function           # Selection/filtering predicate
    compose_strategy::Symbol      # :all, :any, :sequential
end

3. Navigation Steps (various types)

• ALL - Navigate to all collection members
• keypath(key) - Navigate to dictionary key
• pred(predicate) - Filter by predicate
• SEXP_HEAD / sexp_nth(n) - S-expression navigation
• INDEX(i) - Direct indexing

Compilation Pipeline

Path Expression
    ↓
coerce_nav() - converts to Navigator objects
    ↓
Constraint checking - verifies 3-MATCH satisfiability
    ↓
Inline caching via @late_nav / @compiled_select
    ↓
nav_select() / nav_transform() - execution

API

Macros

@late_nav(path_expr) Compiles and caches a navigation path, returning a reusable Navigator:

nav = @late_nav([ALL, pred(iseven)])
results = nav_select(nav, [1,2,3,4,5], x -> [x])
# => [2, 4]

@compiled_select(path, structure) Combines compilation, caching, and selection in one call:

results = @compiled_select([ALL, pred(iseven)], [1,2,3,4,5])
# => [2, 4]

Core Functions

coerce_nav(path_expr) :: Navigator Converts a path expression to a compiled Navigator object.

nav_select(nav::Navigator, structure, result_fn) :: Vector Selects all values matching the path, applies result_fn to each.

nav_transform(nav::Navigator, structure, transform_fn) :: Structure Transforms all values matching the path in-place.

compose_navigators(nav1, nav2) :: Navigator Composes two Navigators into one. Verifies 3-MATCH constraint satisfiability.

Performance Characteristics

| Operation | Time | Notes | |-----------|------|-------| | First @late_nav call | O(|path|) | Compilation + caching | | Subsequent @late_nav | O(1) | Cache lookup | | nav_select | O(n⋅|path|) | n = structure size, linear in path length | | Constraint checking | O(m) | m = number of gadgets, linear in constraint count |

Integration with 3-MATCH

Each path expression can encode constraints that are verifiable via 3-SAT:

# Constraint 1: values must be even
# Constraint 2: values must be > 2
# Constraint 3: XOR of above (either even or >2, but not both)
nav = @late_nav([ALL, pred(x -> (iseven(x) && x ≤ 2) || (!iseven(x) && x > 2))])

The 3-MATCH system can:

• Verify path compositions are satisfiable before execution
• Detect infeasible path combinations early
• Optimize constraint ordering for faster filtering

Bidirectionality

The same Navigator works for both selection and transformation:

# Select even numbers
selected = nav_select(nav, [1,2,3,4,5], x -> [x])

# Transform even numbers (multiply by 10)
transformed = nav_transform(nav, [1,2,3,4,5], x -> x * 10)
# => [1, 20, 3, 40, 5]

Caching Strategy

Global Cache: Dict{UInt64, Navigator}()

• Key: hash(path_expr) - computed at compile time
• Value: compiled Navigator object
• Per-callsite - different code locations maintain separate entries

Cache Invalidation: Never (by design)

• Paths are immutable after compilation
• Cache entries are safe indefinitely
• Memory is the only constraint

Composition with Möbius Filtering

See möbius-path-filtering skill for how non-orientable filtering eliminates invalid paths before Navigator compilation.

Composition with Color Envelopes

See color-envelope-preserving skill for how GF(3) color conservation is enforced across Navigator compositions.

Usage Patterns

Nested Dictionary Navigation

data = Dict(
  "users" => [
    Dict("name" => "Alice", "age" => 30, "active" => true),
    Dict("name" => "Bob", "age" => 25, "active" => false)
  ]
)

# Select all active users' names
nav = @late_nav([keypath("users"), ALL, pred(u -> u["active"]), keypath("name")])
active_names = nav_select(nav, data, x -> [x])
# => ["Alice"]

S-expression Navigation

sexp = :(define (square x) (* x x))

# Navigate to function definition head
nav = @late_nav([sexp_nth(1), SEXP_HEAD])
func_name = nav_select(nav, sexp, x -> [x])
# => :square

Constraint-based Filtering

# Find numbers that are odd AND greater than 5
nav = @late_nav([
  ALL,
  pred(x -> isodd(x) && x > 5)
])
results = nav_select(nav, [1,3,5,7,9,11], x -> [x])
# => [7, 9, 11]

Error Handling

InvalidPathError - Path expression doesn't compile UnsatisfiableConstraintError - 3-MATCH constraints are contradictory TypeMismatchError - Structure doesn't match expected shape for path

Related Skills

• möbius-path-filtering - Eliminates topologically invalid paths
• color-envelope-preserving - Maintains GF(3) color invariants
• three-match - Core 3-SAT constraint satisfaction engine

References

• Clojure Specter: https://github.com/redplanetlabs/specter
• SpecterACSet.jl: /Users/bob/ies/music-topos/lib/specter_acset.jl
• Inline caching paper: "Just in Time Specialization" - Bolz et al.