µ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
Iteratortrait. - State representation using a persistent vector with triangular substitutions.
- Conjunction, disjunction, and
freshbased on traits (macro-free API). - Lazy goal evaluation using inverse-η delay.
- Integer,
bool,char,&str, and unit type atoms. - Explicit
ToValuetrait that converts vectors and arrays into cons-lists. - Convenience macro
state!to inspect and specify state.
Usage
Here's a simple example, which defines and uses 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, res: Value| {
eq(&(a.clone(), d.clone()), &first)
.and(eq(&(a, res.clone()), &out))
.and(appendo(d, second.clone(), res))
}))
.boxed()
}
let iter = run(|x, y| appendo(x, y, [1, 2, 3, 4, 5].to_value()));
assert_eq!(
iter.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.
Made by Eric Zhang for CS 252r. All code is licensed under the MIT License.
3 Dec 14, 2022
0 Dec 24, 2021
1 Jan 10, 2022
1 Feb 7, 2022
2 May 21, 2022
6 Oct 6, 2022
16 Dec 27, 2022
3 Nov 1, 2022
3 Jan 7, 2023
2 Nov 8, 2022
3 Mar 6, 2022
5 Sep 4, 2022
1 Dec 14, 2021
2 Jan 17, 2022
3 Dec 31, 2022
3 Mar 15, 2024
17 Jul 18, 2022
6 Jun 12, 2022
11.2k Jan 8, 2023