Brainfuck interpreter in Rust type system

bf.rs

use bf::*;

type Program = bf![>[<[->+<]>>]<];
type Input = tape![7 7 7 7 7 7];

fn main() {
    println!("{}", Eval::<Program, Input>::default())
}

mod bf {
    use std::fmt::Display;

    #[derive(Default)]
    pub struct Z;
    #[derive(Default)]
    pub struct S<N>(N);

    pub struct Left;
    pub struct Right;
    pub struct Incr;
    pub struct Decr;
    pub struct Loop<T>(T);

    pub trait Exec<M> {
        type End;
    }

    impl<T> Exec<()> for T {
        type End = T;
    }

    impl<R> Exec<Left> for ((), R) {
        type End = ((), (Z, R));
    }

    impl<L, X, R> Exec<Left> for ((X, L), R) {
        type End = (L, (X, R));
    }

    impl<L, X> Exec<Right> for (L, (X, ())) {
        type End = ((X, L), (Z, ()));
    }

    impl<L, X, Y, R> Exec<Right> for (L, (X, (Y, R))) {
        type End = ((X, L), (Y, R));
    }

    impl<L, N, R> Exec<Incr> for (L, (N, R)) {
        type End = (L, (S<N>, R));
    }

    impl<L, N, R> Exec<Decr> for (L, (S<N>, R)) {
        type End = (L, (N, R));
    }

    impl<P, Q, T> Exec<(P, Q)> for T
    where
        T: Exec<P>,
        <T as Exec<P>>::End: Exec<Q>,
    {
        type End = <<T as Exec<P>>::End as Exec<Q>>::End;
    }

    impl<P, L, R> Exec<Loop<P>> for (L, (Z, R)) {
        type End = (L, (Z, R));
    }

    impl<P, L, N, R> Exec<Loop<P>> for (L, (S<N>, R))
    where
        (L, (S<N>, R)): Exec<P>,
        <(L, (S<N>, R)) as Exec<P>>::End: Exec<Loop<P>>,
    {
        type End = <<(L, (S<N>, R)) as Exec<P>>::End as Exec<Loop<P>>>::End;
    }

    #[macro_export]
    macro_rules! bf {
    () => { () };
    (< $($p:tt)*) => { (Left, bf!($($p)*)) };
    (<< $($p:tt)*) => { (Left, (Left, bf!($($p)*))) };
    (> $($p:tt)*) => { (Right, bf!($($p)*)) };
    (>> $($p:tt)*) => { (Right, (Right, bf!($($p)*))) };
    (+ $($p:tt)*) => { (Incr, bf!($($p)*)) };
    (- $($p:tt)*) => { (Decr, bf!($($p)*)) };
    (-> $($p:tt)*) => { (Decr, (Right, bf!($($p)*))) };
    ([ $($p:tt)* ] $($q:tt)*) => { (Loop<bf!($($p)*)>, bf!($($q)*)) };
}

    #[macro_export]
    macro_rules! tape_ {
    () => { () };
    (0 $($p:tt)*) => { (Z, tape_!($($p)*)) };
    (1 $($p:tt)*) => { (S<Z>, tape_!($($p)*)) };
    (2 $($p:tt)*) => { (S<S<Z>>, tape_!($($p)*)) };
    (3 $($p:tt)*) => { (S<S<S<Z>>>, tape_!($($p)*)) };
    (4 $($p:tt)*) => { (S<S<S<S<Z>>>>, tape_!($($p)*)) };
    (5 $($p:tt)*) => { (S<S<S<S<S<Z>>>>>, tape_!($($p)*)) };
    (6 $($p:tt)*) => { (S<S<S<S<S<S<Z>>>>>>, tape_!($($p)*)) };
    (7 $($p:tt)*) => { (S<S<S<S<S<S<S<Z>>>>>>>, tape_!($($p)*)) };
    (8 $($p:tt)*) => { (S<S<S<S<S<S<S<S<Z>>>>>>>>, tape_!($($p)*)) };
    (9 $($p:tt)*) => { (S<S<S<S<S<S<S<S<S<Z>>>>>>>>>, tape_!($($p)*)) };
}

    #[macro_export]
    macro_rules! tape {
    ($($p:tt)*) => {((), tape_!($($p)*))};
}

    impl<'a> From<&'a Z> for usize {
        fn from(_: &'a Z) -> Self {
            0
        }
    }

    impl<'a, N> From<&'a S<N>> for usize
    where
        usize: From<&'a N>,
    {
        fn from(S(n): &'a S<N>) -> Self {
            1 + <usize as From<&'a N>>::from(n)
        }
    }

    impl Display for Z {
        fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
            write!(f, "0")
        }
    }

    impl<N> Display for S<N>
    where
        usize: for<'a> From<&'a N>,
    {
        fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
            write!(f, "{}", <usize as From<&S<N>>>::from(self))
        }
    }

    #[derive(Default)]
    pub struct Tape<T>(T);

    impl<L, R> Display for Tape<(L, R)>
    where
        L: DisplayHalf,
        R: DisplayHalf,
    {
        fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
            self.0 .0.fmt_half(f)?;
            write!(f, "> ")?;
            self.0 .1.fmt_half(f)
        }
    }

    trait DisplayHalf {
        fn fmt_half(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result;
    }

    impl<N: Display, T: DisplayHalf> DisplayHalf for (N, T) {
        fn fmt_half(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
            self.0.fmt(f)?;
            write!(f, " ")?;
            self.1.fmt_half(f)
        }
    }

    impl DisplayHalf for () {
        fn fmt_half(&self, _: &mut std::fmt::Formatter) -> std::fmt::Result {
            Ok(())
        }
    }

    impl Display for Tape<()> {
        fn fmt(&self, _: &mut std::fmt::Formatter) -> std::fmt::Result {
            panic!("oops")
        }
    }

    pub type Eval<P, T> = Tape<<T as Exec<P>>::End>;
}