Combinatory Logic in Rust `macro_rules!`

combinatory-logic.rs

macro_rules! eq_ident {
  ($a:ident, $b:ident, $t:expr, $f:expr) => {{
    macro_rules! check_equal {
      ($a) => { $t };
      ($b) => { $f };
    }
    check_equal!($b)
  }};
}

macro_rules! lambda {
  (impl (($($x:tt)*)) extract $v:ident ($($next:tt)*)) => {
    lambda!(impl ($($x)*) extract $v ($($next)*))
  };
  (impl ($x:tt) extract $v:ident ($($next:tt)*)) => {
    eq_ident!($x, $v, lambda!(impl (I) true $($next)*), lambda!(impl ($x) false $($next)*))
  };
  (impl ($a:ident, $($b:tt)*) extract $v:ident ($($next:tt)*)) => {
    eq_ident!($a, $v, lambda!(impl ($($b)*) extract $a (finish_extract (false $($next)*))), lambda!(impl ($($b)*) extract $a (finish_extract (extract $v ($($next)*)))))
  };
  (impl $a:tt true finish_extract ($($next:tt)*)) => {
    lambda!(impl $a $($next)*)
  };
  (impl $a:tt false finish_extract ($($next:tt)*)) => {
    lambda!(impl (K $a) $($next)*)
  };
  (impl ($a:tt $b:tt, $($c:tt)+) extract $v:ident ($($next:tt)*)) => {
    lambda!(impl ($a ($b, $($c)*)) extract $v ($($next)*))
  };
  (impl ($a:tt $b:tt $($c:tt)+) extract $v:ident ($($next:tt)*)) => {
    lambda!(impl (($a $b) $($c)*) extract $v ($($next)*))
  };
  (impl ($a:tt $b:tt) extract $v:ident ($($next:tt)*)) => {
    lambda!(impl ($a) extract $v (call_with_extract $b $v ($($next)*)))
  };
  (impl $a:tt $u:ident call_with_extract $b:tt $v:ident ($($next:tt)*)) => {
    lambda!(impl ($b) extract $v (finish_call_extract $a $u ($($next)*)))
  };
  (impl $b:tt true finish_call_extract $a:tt true ($($next:tt)*)) => {
    lambda!(impl (S $a $b) true $($next)*)
  };
  (impl $b:tt false finish_call_extract $a:tt true ($($next:tt)*)) => {
    lambda!(impl (C $a $b) true $($next)*)
  };
  (impl ($b:tt) true finish_call_extract $a:tt false ($($next:tt)*)) => {
    lambda!(impl $b true finish_call_extract $a false ($($next)*))
  };
  (impl I true finish_call_extract $a:tt false ($($next:tt)*)) => {
    lambda!(impl ($a) true $($next)*)
  };
  (impl $b:tt true finish_call_extract $a:tt false ($($next:tt)*)) => {
    lambda!(impl (D $a $b) true $($next)*)
  };
  (impl $b:tt false finish_call_extract $a:tt false ($($next:tt)*)) => {
    lambda!(impl ($a $b) false $($next)*)
  };
  (impl ($($x:tt)*) false done) => {
    term!($($x)*)
  };
  (impl $($x:tt)*) => {
    compile_error!("Invalid internal call")
  };
  ($($x:tt)*) => {
    lambda!(impl ($($x)*) extract ____ (done))
  };
}

macro_rules! term {
  (impl (($($x:tt)*) $($y:tt)*) reduce ($($next:tt)*)) => {
    term!(impl ($($x)* $($y)*) reduce ($($next)*))
  };
  (impl (S $x:tt $y:tt $z:tt $($n:tt)*) reduce ($($next:tt)*)) => {
    term!(impl ($x $z ($y $z) $($n)*) reduce ($($next)*))
  };
  (impl (K $x:tt $y:tt $($n:tt)*) reduce ($($next:tt)*)) => {
    term!(impl ($x $($n)*) reduce ($($next)*))
  };
  (impl (I $x:tt $($n:tt)*) reduce ($($next:tt)*)) => {
    term!(impl ($x $($n)*) reduce ($($next)*))
  };
  (impl (C $x:tt $y:tt $z:tt $($n:tt)*) reduce ($($next:tt)*)) => {
    term!(impl ($x $z $y$($n)*) reduce ($($next)*))
  };
  (impl (D $x:tt $y:tt $z:tt $($n:tt)*) reduce ($($next:tt)*)) => {
    term!(impl ($x ($y $z) $($n)*) reduce ($($next)*))
  };
  (impl ($c:ident $($n:tt)*) reduce ($($next:tt)*)) => {
    term!(impl $c iter () ($($n)*) ($($next)*))
  };
  (impl $c:tt iter ($($p:tt)*) ($x:tt $($n:tt)*) ($($next:tt)*)) => {
    term!(impl ($x) reduce (iter ($($p)* $c) ($($n)*) ($($next)*)))
  };
  (impl $c:tt iter ($($p:tt)*) () ($($next:tt)*)) => {
    term!(impl ($($p)* $c) $($next)*)
  };
  (impl ($($x:tt)*) done) => {
    stringify!($($x)*)
  };
  (impl $($x:tt)*) => {
    compile_error!("Invalid internal call")
  };
  ($($x:tt)*) => {
    term!(impl ($($x)*) reduce (done))
  };
}

fn main() {
  println!("{}", term!((S I I) K)); // "K (K)"
  println!("{}", lambda!(a, b, i, z, a i (b i z))); // "S (D)"
}