canrun/core/
unify.rs

1use std::any::Any;
2use std::fmt::Debug;
3use std::rc::Rc;
4
5use crate::core::State;
6
7/**
8How compatible values are matched with each other.
9
10See
11[Unification](https://en.wikipedia.org/wiki/Unification_(computer_science))
12for a formal and probably more correct definition. This will attempt to
13describe unification as implemented (and understood by me).
14
15The simplest example of unification looks like equality or variable
16assignment. In `x=1`, if the variable `x` is unbound, the statement succeeds
17and `x` is considered equal to `1`. `1=1` is also valid, though slightly
18silly. Unification does not care about direction, so `1=x` is equally valid
19and has the same effect.
20
21A follow-up assertion that `x=2` would fail, because `x` is already bound to
22`1`.
23
24Unifying structures containing other types of values can get interesting
25very fast. Unifying a free (unbound) variable with a structure simply binds
26that variable to the entire structure (e.g. `x=(1,2)`). However, binding two
27compatible structures with each other allows binding to values inside the
28structures. In `(x,2)=(1,2)`, the `x` in the first structure is bound to the
29`1` in the second. Structurally incompatible values will fail immediately: `(x,2,3)=(1,2)`.
30
31Arbitrarily nested structures can be unified by recursively applying this
32simple pattern matching.
33
34For simple types, unification is essentially the same thing as equality (and
35implementations are provided for most simple primitive types). The general pattern
36for structures is to define a way to match up their component parts and
37recursively attempt to unify them.
38
39# Implementation
40
41Default implementations are provided for most primitive types, and a few general
42"logic collections". You can also implement it for your own types.
43
44TODO: Create a derive macro
45```
46use canrun::core::{State, Unify, Value};
47use std::rc::Rc;
48
49#[derive(Debug)]
50struct MyType<T: Unify> {
51    inside: Value<T>
52}
53
54impl<T: Unify> Unify for MyType<T> {
55    fn unify(state: State, a: Rc<Self>, b: Rc<Self> ) -> Option<State> {
56        state.unify(&a.inside, &b.inside)
57    }
58}
59# fn main() {}
60```
61*/
62pub trait Unify: Any + Debug {
63    /**
64    Attempt to unify two fully resolved values.
65
66    This function accepts `Rc<T>`s to simplify the borrow checking. The
67    `Option<_>` return type allows recursive unification of structures that
68    hold additional values.
69    */
70    fn unify(state: State, a: Rc<Self>, b: Rc<Self>) -> Option<State>;
71}
72
73macro_rules! impl_unify_eq {
74    ($($type:ty),+) => {
75        $(
76            impl Unify for $type {
77                fn unify(state: State, a: Rc<$type>, b: Rc<$type>) -> Option<State> {
78                    if a == b {
79                        Some(state)
80                    } else {
81                        None
82                    }
83                }
84            }
85        )+
86    };
87}
88
89impl_unify_eq!(i8, i16, i32, i64, u8, u16, u32, u64, isize, usize, f32, f64);
90impl_unify_eq!(String, &'static str, bool, char);
91impl_unify_eq!(std::ops::Range<usize>);
canrun/core/unify.rs

canrun/core/
unify.rs
