Witch of Git - mukan/blob - README.md

   1 # MuKan
   2
   3 ```toml
   4 mukan = { git = "https://git.witchoflight.com/mukan" }
   5 ```
   6
   7 (Micro Kanaya :3)
   8
   9 This is a Rust implementation of MicroKanren, based on the very readable
  10 original paper at:
  11 <http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf>.
  12
  13 There's a nice Clojure implementation that I also found very informative, for
  14 getting another perspective on the unification and an idea of where the natural
  15 extension points are: <https://mullr.github.io/micrologic/literate.html>.
  16
  17 ## Usage:
  18
  19 You build up goals with goal constructors, and then execute them with the
  20 `search` method of `Goal`, running that on an initial state. One of the
  21 simplest possible programs you could write is:
  22
  23 ```rust
  24 use mukan::{Goal, call_fresh, State, eq};
  25
  26 fn main() {
  27     let goal = call_fresh(|x| eq(413, x));
  28     for soln in goal.search(State::new()) {
  29         println!("{}", soln);
  30     }
  31 }
  32 ```
  33
  34 This will create a goal that wants to solve `413 = X`, and then show you all of
  35 the solutions starting with an empty state. You can get slightly fancier, with
  36 problems that have multiple solutions:
  37
  38 ```rust
  39 let goal = call_fresh(|x| or(eq(612, x), eq(1025, x)));
  40 ```
  41
  42 This will produce two solutions, assigning x to 612 and 1025 in them,
  43 respectively. There are macros that make several of the features easier to
  44 use. Here, we can use `fresh!` to create multiple variables, and `all!` to and
  45 together an arbitrary number of goals. You can also work with pairs of
  46 variables, letting you produce some more interesting cases.
  47
  48 ```rust
  49 let goal = fresh!((a, b, c) => all! {
  50     eq((a, b), c),
  51     eq((b, 8), c),
  52 });
  53 ```
  54
  55 Here this should solve to `a = 8`, `b = 8`, and `c = (8, 8)`.  Of course, the
  56 solution that gets printed is messier, so you might want to ask for a solution
  57 in terms of the raw values. You can get the entire state evaluated like this
  58 with the `reify` function, but if you just want to get a few particular
  59 variables, then you can use `reify_vars` with variables that you own.
  60
  61 One way to get those variables, is make your variables in a particular state:
  62 ```rust
  63 let (vars, state) = State::with_vars(2);
  64 let (a, b) = (vars[0], vars[1]);
  65 let goal = fresh!((c) => all! {
  66     eq((a, b), c),
  67     eq((b, 8), c),
  68 });
  69 for soln in goal.search(state) {
  70     println!("{:?}", reify_vars(&vars, soln));
  71 }
  72 ```
  73
  74 You can write recursive goals as rust functions, as well!
  75
  76 ```rust
  77 fn peano(n: impl Into<Term>) -> impl Goal {
  78     let n = n.into();
  79     or(
  80         eq(n.clone(), 0),
  81         fresh!((x) => and(
  82             eq(n.clone(), (1, x)),
  83             delay(move || peano(x)),
  84         )),
  85     )
  86 }
  87 ```
  88
  89 We need the `delay()` in order to prevent the goal from being constructed
  90 forever without being searched at all. If you try to solve `peano` with a
  91 variable, then you'd get an infinite stream of assignments that satisfy it.
  92
  93 ```rust
  94 let (vars, state) = State::with_vars(1);
  95 let goal = peano(vars[0]);
  96 for soln in goal.search(state).take(10) {
  97     println!("{:?}", reify_vars(&vars, soln));
  98 }
  99 ```