Propagators Chirho - Bidirectional Constraint Networks

What are Propagator Networks?

Propagator networks are a computational model for bidirectional constraint propagation, inspired by the work of Gerald Jay Sussman and Alexey Radul at MIT. Unlike traditional functions that compute outputs from inputs, propagators work with partial information that flows in all directions through a network of cells.

Interval Arithmetic

Each cell contains an interval [lo, hi] representing a range of possible values. As constraints propagate, these intervals narrow toward exact answers.

[a, b] + [c, d] = [a+c, b+d] [a, b] \times [c, d] = [min(ac, ad, bc, bd), max(ac, ad, bc, bd)]

Bidirectional Flow

The magic of propagators is that constraints work both ways. If you know a + b = c, you can compute any variable from the other two.

Monotonic Refinement

Information only grows—intervals narrow but never widen. This guarantees termination.

Lattice Theory

Values form a join-semilattice with partial order. ⊥ = no info, ⊤ = contradiction.

SIMD Optimized

Batch operations use explicit loops for auto-vectorization on modern CPUs.

Formally Verified

Key properties proven with Kani bounded model checking.

Interactive Demo

Loading WebAssembly module...

Pythagorean Theorem: a² + b² = c²

Enter any two values and the propagator network computes the third!

Side a (leave empty to compute)

Side b (leave empty to compute)

Hypotenuse c (leave empty to compute)

Result

Temperature Conversion: °C ↔ °F

The constraint F = C × 9/5 + 32 works bidirectionally.

Temperature in Celsius

Temperature in Fahrenheit

Conversion Result

Interval Arithmetic Demo

See how operations on intervals produce interval results.

Interval A

Interval B

Click "Calculate" to see interval arithmetic in action.

Usage

Rust

use propagators_chirho::prelude_chirho::*;

let mut network_chirho = PropagatorNetworkChirho::new_chirho();

let a_chirho = network_chirho.make_cell_chirho();
let b_chirho = network_chirho.make_cell_chirho();
let c_chirho = network_chirho.make_cell_chirho();

network_chirho.add_adder_chirho(a_chirho, b_chirho, c_chirho);
network_chirho.set_exact_chirho(a_chirho, 3.0);
network_chirho.set_exact_chirho(b_chirho, 4.0);
network_chirho.propagate_chirho();

// c_chirho = 7.0

JavaScript (via WASM)

import init, { WasmNetworkChirho } from './propagators_chirho.js';

await init();

const networkChirho = new WasmNetworkChirho();
const aChirho = networkChirho.makeCell();
const bChirho = networkChirho.makeCell();
const cChirho = networkChirho.makeCell();

networkChirho.addAdder(aChirho, bChirho, cChirho);
networkChirho.setExact(aChirho, 3.0);
networkChirho.setExact(bChirho, 4.0);
networkChirho.propagate();

console.log(networkChirho.getExact(cChirho)); // 7.0

Installation

Cargo

[dependencies]
propagators-chirho = "0.1"