Bipartite-matching primitives for structural subset reasoning.
Implements Kuhn's augmenting-paths algorithm — a graph traversal that finds the maximum number of schema clauses that can be paired without reuse. Used by me.lomin.sinho.matcher to check structural exhaustiveness in set and map matching.
This is purely graph-algorithmic and is not coinductive in the type-theory sense.
Bipartite-matching primitives for structural subset reasoning. Implements Kuhn's augmenting-paths algorithm — a graph traversal that finds the maximum number of schema clauses that can be paired without reuse. Used by me.lomin.sinho.matcher to check structural exhaustiveness in set and map matching. This is purely graph-algorithmic and is not coinductive in the type-theory sense.
Coinductive IR decision engine for structural subset matching.
v3 replaces sinho 2.2's A* search with a direct structural walk:
The coinductive assumption set (seen pairs) prevents infinite loops on recursive structures, analogous to sinho 2.2's seen map.
Coinductive IR decision engine for structural subset matching. v3 replaces sinho 2.2's A* search with a direct structural walk: - Maps: O(n) via key lookup (no pairings search) - Sets: O(n^3) via Kuhn's augmenting-paths for verdicts; greedy O(n^2 log n) for diffs - Sequences: O(m*n) via tree-edit-distance DP - Atoms: O(1) direct equality - Predicates: (pred f) wrapper dispatch The coinductive assumption set (seen pairs) prevents infinite loops on recursive structures, analogous to sinho 2.2's seen map.
No vars found in this namespace.
Predicate wrapper for sinho's structural matcher.
(pred f) wraps a 1-arg predicate for use in expected positions.
Bare functions in expected positions are compared by value equality,
not interpreted as predicates. This eliminates ambiguity between
'predicate-on-actual' and 'literal function-value equality.'
Predicate wrapper for sinho's structural matcher. `(pred f)` wraps a 1-arg predicate for use in expected positions. Bare functions in expected positions are compared by value equality, not interpreted as predicates. This eliminates ambiguity between 'predicate-on-actual' and 'literal function-value equality.'
A total-ordering comparator for Clojure values, after mvxcvi/arrangement
2.1.0's arrangement.core/rank (public domain), with a ClojureDart branch.
A total-ordering comparator for Clojure values, after mvxcvi/arrangement 2.1.0's `arrangement.core/rank` (public domain), with a ClojureDart branch.
Adaptive Self-Clocking Timeout Guard for CLJ/CLJS
This implementation provides a cooperative timeout mechanism that can efficiently stop CPU-bound computations after a specified timeout period without requiring external watchdog threads or complex coordination.
The timeout guard uses an A* search-inspired adaptive algorithm that automatically adjusts how frequently it checks the system clock based on observed timing patterns. This minimizes the overhead when far from the timeout deadline while ensuring responsive detection near the timeout boundary.
Instead of checking the clock on every call, the algorithm dynamically calculates a 'stride' - the number of calls to skip before the next time check. This stride is continuously adapted based on:
The algorithm aims to detect timeouts within a bounded overshoot envelope:
p99 overshoot ≤ max(S, min(5% × timeout, 10ms))
where S is the p99 cost of a single atomic step between checks.
To prevent excessively long periods without sampling, the stride calculation includes a time-based ceiling that ensures samples occur at least every 10ms of wall-clock time.
(let [timeout? (make-timeout 200)] ; 200ms timeout
(reduce (fn [acc x]
(if (timeout?) ; Check at natural boundaries
(reduced acc) ; Return current value on timeout
(expensive-step acc x))) ; Continue processing
initial-value
large-dataset))
Each timeout guard is designed for single-threaded use (one guard per compute thread). Multiple guards can run concurrently in different threads without coordination.
The algorithm uses fixed constants tuned for general-purpose workloads:
These constants are intentionally not configurable to maintain API simplicity and ensure consistent behavior across deployments.
Adaptive Self-Clocking Timeout Guard for CLJ/CLJS
This implementation provides a cooperative timeout mechanism that can efficiently
stop CPU-bound computations after a specified timeout period without requiring
external watchdog threads or complex coordination.
## Overview
The timeout guard uses an A* search-inspired adaptive algorithm that automatically
adjusts how frequently it checks the system clock based on observed timing patterns.
This minimizes the overhead when far from the timeout deadline while ensuring
responsive detection near the timeout boundary.
## Key Algorithm Components
### Adaptive Stride-Based Sampling
Instead of checking the clock on every call, the algorithm dynamically calculates
a 'stride' - the number of calls to skip before the next time check. This stride
is continuously adapted based on:
- **EWMA (Exponentially Weighted Moving Average)**: Tracks mean time per step
- **EWVAR (Exponentially Weighted Variance)**: Estimates timing variability
- **Decayed Maximum**: Hedges against occasional long steps that could cause overshoot
- **Panic Mode**: Forces frequent sampling when time is being consumed too rapidly
### Target Overshoot Envelope
The algorithm aims to detect timeouts within a bounded overshoot envelope:
```
p99 overshoot ≤ max(S, min(5% × timeout, 10ms))
```
where S is the p99 cost of a single atomic step between checks.
### Time-Based Ceiling
To prevent excessively long periods without sampling, the stride calculation
includes a time-based ceiling that ensures samples occur at least every 10ms
of wall-clock time.
## Usage Pattern
```clojure
(let [timeout? (make-timeout 200)] ; 200ms timeout
(reduce (fn [acc x]
(if (timeout?) ; Check at natural boundaries
(reduced acc) ; Return current value on timeout
(expensive-step acc x))) ; Continue processing
initial-value
large-dataset))
```
## Performance Characteristics
- **Fast Path**: Simple counter increment and comparison (zero allocation)
- **Sample Path**: Single monotonic time read plus statistical updates
- **Steady-State Overhead**: Target <1-2% when far from deadline
- **Cross-Platform**: Works on JVM, Node.js, and modern browsers
## Thread Confinement Model
Each timeout guard is designed for single-threaded use (one guard per compute thread).
Multiple guards can run concurrently in different threads without coordination.
## Constants and Tuning
The algorithm uses fixed constants tuned for general-purpose workloads:
- Z95 = 1.64485 (95th percentile multiplier for normal distribution)
- ALPHA = 0.05 (EWMA/EWVAR smoothing factor)
- SAFETY = 2.0 (conservative stride multiplier)
- DECAY = 0.98 (decayed maximum decay rate per sample)
- BURN_RATIO = 0.33 (panic threshold: >33% of remaining time consumed)
These constants are intentionally not configurable to maintain API simplicity
and ensure consistent behavior across deployments.cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |