Crate propagators_chirho

Crate propagators_chirho 

Source
Expand description

§Propagators Chirho

A Rust implementation of propagator networks for constraint propagation and bidirectional computation.

§Overview

Propagators are a programming paradigm where autonomous agents (propagators) watch cells containing partial information and update other cells when they learn something new. Information flows in all directions, enabling powerful constraint-based programming.

This implementation is based on the seminal work:

Radul, A., & Sussman, G. J. (2009). The Art of the Propagator. MIT Computer Science and Artificial Intelligence Laboratory Technical Report. https://dspace.mit.edu/handle/1721.1/44215

§Key Concepts

§Partial Information

Cells hold partial information that can only grow monotonically. For numeric values, we use intervals [lo, hi] that narrow as we learn more:

use propagators_chirho::{IntervalChirho, NumericInfoChirho};

// "I know the value is between 0 and 100"
let partial_chirho = NumericInfoChirho::interval_chirho(0.0, 100.0);

// "Actually, it's between 20 and 50" - more precise!
let refined_chirho = partial_chirho.merge_chirho(&NumericInfoChirho::interval_chirho(20.0, 50.0));

§Bidirectional Constraints

Unlike traditional programming where data flows one way, propagators enforce constraints in all directions:

use propagators_chirho::prelude_chirho::*;

// Create a constraint system
let mut system_chirho = ConstraintSystemChirho::new_chirho();

// Create cells for Fahrenheit and Celsius
let f_chirho = system_chirho.make_cell_chirho("fahrenheit");
let c_chirho = system_chirho.make_cell_chirho("celsius");

// F = C * 9/5 + 32 works BOTH ways!
// (Implementation would use adder/multiplier propagators)

§Truth Maintenance

Track beliefs with their supporting premises, enabling hypothetical reasoning:

use propagators_chirho::{BeliefChirho, WorldviewChirho, NumericInfoChirho};

// Create a belief supported by premise "sensor_a"
let belief_chirho = BeliefChirho::with_premises_chirho(
    NumericInfoChirho::exact_chirho(25.0),
    vec!["sensor_a".to_string()].into_iter().collect(),
    "temperature reading",
);

// Query under different worldviews
let worldview_chirho = WorldviewChirho::new_chirho();
let with_sensor_chirho = worldview_chirho.assume_chirho("sensor_a".to_string());

§Features

  • Interval Arithmetic: Proper interval math with +, -, *, /, sqrt, square
  • Bidirectional Propagators: Constraints work in all directions
  • Truth Maintenance System (TMS): Track beliefs and their justifications
  • Worldviews: Hypothetical reasoning with fork/assume/retract
  • Amb Operator: Nondeterministic choice with backtracking
  • Scheduler: Runs propagators to fixpoint

§Cargo Features

  • arena: High-performance arena-based cells (reduces Rc overhead)
  • parallel: Parallel propagation using rayon
  • serde: Serialization support for intervals and cells
  • tracing: Debugging instrumentation (adds overhead)
  • tms-full: Full TMS with justification tracking (memory overhead)
  • no-std: Embedded/no_std support (see below)

§no_std Support

Enable the no-std feature for embedded or bare-metal environments:

[dependencies]
propagators-chirho = { version = "0.1", default-features = false, features = ["no-std"] }

In no_std mode, only core modules are available:

  • IntervalChirho and NumericInfoChirho for interval arithmetic
  • algebra_chirho traits (SemigroupChirho, MonoidChirho, etc.)
  • simd_chirho for batch SIMD operations

The full propagator network (cells, schedulers, TMS) requires std.

Note: The no-std feature is mutually exclusive with other features.

§References

  1. Radul, A., & Sussman, G. J. (2009). The Art of the Propagator. MIT CSAIL Technical Report. https://dspace.mit.edu/handle/1721.1/44215

  2. Radul, A. (2009). Propagation Networks: A Flexible and Expressive Substrate for Computation. PhD Thesis, MIT. https://dspace.mit.edu/handle/1721.1/54635

  3. Stallman, R. M., & Sussman, G. J. (1977). Forward Reasoning and Dependency-Directed Backtracking in a System for Computer-Aided Circuit Analysis. Artificial Intelligence, 9(2), 135-196.

  4. de Kleer, J. (1986). An Assumption-based TMS. Artificial Intelligence, 28(2), 127-162.

  5. Moore, R. E. (1966). Interval Analysis. Prentice-Hall.

§Example: Temperature Conversion

use propagators_chirho::prelude_chirho::*;

// Create scheduler and cells
let scheduler_chirho = SchedulerChirho::new_chirho();
let celsius_chirho: std::rc::Rc<CellChirho<NumericInfoChirho>> =
    CellChirho::new_chirho("celsius");

// Add a known Celsius value
celsius_chirho.add_content_chirho(
    NumericInfoChirho::exact_chirho(100.0),
    &scheduler_chirho
);

// With proper propagators set up, fahrenheit would become 212.0

Re-exports§

pub use algebra_chirho::BoundedJoinSemilatticeChirho;
pub use algebra_chirho::CommutativeSemigroupChirho;
pub use algebra_chirho::IdempotentSemigroupChirho;
pub use algebra_chirho::JoinSemilatticeChirho;
pub use algebra_chirho::MonoidChirho;
pub use algebra_chirho::PropagatorErrorChirho;
pub use algebra_chirho::PropagatorResultChirho;
pub use algebra_chirho::SemigroupChirho;
pub use interval_chirho::IntervalChirho;
pub use interval_chirho::NumericInfoChirho;
pub use simd_chirho::batch_add_chirho;
pub use simd_chirho::batch_intersect_chirho;
pub use simd_chirho::batch_mul_chirho;
pub use simd_chirho::batch_sqrt_chirho;
pub use simd_chirho::batch_square_chirho;
pub use simd_chirho::batch_sub_chirho;
pub use simd_chirho::IntervalVecChirho;

Modules§

algebra_chirho
Algebraic structures for propagator networks.
interval_chirho
Interval arithmetic for partial numeric information.
prelude_chirhono-std
Minimal prelude for no_std mode. Minimal re-exports for no_std mode.
simd_chirho
SIMD-accelerated interval arithmetic operations.