Liking cljdoc? Tell your friends :D

me.lomin.sinho.bipartite

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.
raw docstring

me.lomin.sinho.matcher

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.

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.
raw docstring

me.lomin.sinho.matcher-test-macros

No vars found in this namespace.

me.lomin.sinho.pred

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.'
raw docstring

me.lomin.sinho.rank

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.
raw docstring

me.lomin.sinho.timeout

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

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

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.
raw docstring

cljdoc builds & hosts documentation for Clojure/Script libraries

Keyboard shortcuts
Ctrl+kJump to recent docs
←Move to previous article
→Move to next article
Ctrl+/Jump to the search field
× close