ukanren 0.0.5

Rust implementation of µKanren, a featherweight relational programming language.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

use std::fmt::{self, Debug};

use rpds::Vector;

use crate::value::{cons, Value};

/// The current variable state of the miniKanren interpreter.
///
/// We use a persistent vector both for performance reasons, and to satisfy
/// Rust's ownership rules for [`Value`],
#[derive(Clone, Default, PartialEq, Eq)]
pub struct State(Vector<Option<Value>>);

impl State {
    pub(crate) fn apply(
        &self,
        f: impl FnOnce(&Vector<Option<Value>>) -> Vector<Option<Value>>,
    ) -> State {
        State(f(&self.0))
    }

    pub(crate) fn walk(&self, u: &Value) -> Value {
        match u {
            Value::Variable(i) => match &self.0[*i] {
                Some(x) => self.walk(x),
                None => u.clone(),
            },
            _ => u.clone(),
        }
    }

    pub(crate) fn walk_full(&self, u: &Value) -> Value {
        match u {
            Value::Variable(i) => match &self.0[*i] {
                Some(x) => self.walk_full(x),
                None => u.clone(),
            },
            Value::Cons(u, v) => cons(&self.walk_full(u), &self.walk_full(v)),
            _ => u.clone(),
        }
    }

    pub(crate) fn extend(&self, x: usize, v: Value) -> State {
        self.apply(|s| s.set(x, Some(v)).expect("invalid index in extend_state"))
    }

    pub(crate) fn add_fresh(&self, n: usize) -> State {
        self.apply(|s| {
            let mut s = s.clone();
            s.extend(std::iter::repeat(None).take(n));
            s
        })
    }

    /// Lookup how many variables are in the state.
    pub fn len(&self) -> usize {
        self.0.len()
    }

    /// Check if this state is empty (the zero state).
    pub fn is_empty(&self) -> bool {
        self.0.is_empty()
    }

    /// Create a state from a collection of optional values.
    pub fn from_vec(v: impl IntoIterator<Item = Option<Value>>) -> State {
        Self(v.into_iter().collect())
    }

    /// Return the idempotent first `k` variables from the state.
    pub fn finish(&self, k: usize) -> State {
        State::from_vec((0..k).map(|i| self.0[i].as_ref().map(|v| self.walk_full(v))))
    }
}

impl Debug for State {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "state![")?;
        let mut first = true;
        for value in self.0.iter() {
            if !first {
                write!(f, ", ")?;
            }
            first = false;
            match value {
                None => write!(f, "_"),
                Some(Value::Atom(ref v)) => write!(f, "{:?}", v),
                Some(Value::Cons(ref u, ref v)) => write!(f, "({:?}, {:?})", u, v),
                Some(Value::Variable(i)) => write!(f, "(@{})", i),
            }?
        }
        write!(f, "]")?;
        Ok(())
    }
}

/// Convenience macro for making state objects using the `ToValue` trait.
#[macro_export]
macro_rules! state {
    () => {
        $crate::State::default()
    };
    ($($args:tt),+ $(,)?) => {
        {
            use $crate::ToValue;
            $crate::State::from_vec(::std::vec![
                $($crate::state_inner!(@STATE; $args)),+
            ])
        }
    };
}

#[macro_export]
#[doc(hidden)]
macro_rules! state_inner {
    (@STATE; _) => {
        None
    };
    (@STATE; (@ $x:expr)) => {
        Some(Value::Variable($x))
    };
    (@STATE; $x:expr) => {
        Some($x.to_value())
    };
}