Skip to content

Rust implementation of µKanren, a featherweight relational programming language.


Notifications You must be signed in to change notification settings


Folders and files

Last commit message
Last commit date

Latest commit



31 Commits

Repository files navigation


github build status

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


  • Structural unification of Scheme-like cons cells.
  • Streams implemented with the Iterator trait.
  • State representation using a persistent vector with triangular substitutions.
  • Conjunction, disjunction, and fresh based on traits (macro-free API).
  • Lazy goal evaluation using inverse-η delay.
  • 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.


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))

let iter = run(|x, y| appendo(x, y, [1, 2, 3, 4, 5].to_value()));
        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.