µKanren-rs

This is a Rust implementation of µKanren, a featherweight relational programming language. See the original Scheme implementation here for reference.

Features

• Structural unification of Scheme-like cons cells.
• Streams implemented with the Iterator trait.
• Conjunction, disjunction, and fresh based on traits (macro-free API).
• Integer, bool, char, &str, and unit type atoms.
• Explicit ToValue trait that converts vectors and arrays into cons-lists.
• Convenience macro state! to inspect and specify state.

Usage

Here's a simple example, defining and using the appendo predicate.

use ukanren::*;

fn appendo(first: Value, second: Value, out: Value) -> BoxedGoal<impl Iterator<Item = State>> {
    eq(&first, &())
        .and(eq(&second, &out))
        .or(fresh(move |a: Value, d: Value| {
            let out = out.clone();
            let second = second.clone();
            eq(&(a.clone(), d.clone()), &first).and(fresh(move |res: Value| {
                eq(&(a.clone(), res.clone()), &out).and(appendo(d.clone(), second.clone(), res))
            }))
        }))
        .boxed()
}

let goal = fresh(|x, y| appendo(x, y, [1, 2, 3, 4, 5].to_value()));
assert_eq!(
    goal.run(2).collect::<Vec<_>>(),
    vec![
        state![(), [1, 2, 3, 4, 5]],
        state![[1], [2, 3, 4, 5]],
        state![[1, 2], [3, 4, 5]],
        state![[1, 2, 3], [4, 5]],
        state![[1, 2, 3, 4], [5]],
        state![[1, 2, 3, 4, 5], ()],
    ],
);

More examples can be found in the tests/ folder and the API documentation.