ck_macro.rs

#![recursion_limit = "256"]

// スタックは以下のような形。
// [(マクロ名, (まだ評価していない引数...), (評価が終わった引数...)), ...]
//
// ck(スタック, 式)という形で評価していく。なんとなく継続を起動してるイメージ
// 評価が終わったら`q!(値)`という形で目印を付ける
//
// ただしここで受け取るマクロは全てスタックを第一引数に取るものとする。CPSでいう継続にあたる。
macro_rules! ck {
    // スタックが空で値が出来ているなら値を返す
    ([], q!($value:tt)) => {
        $value
    };
    // 評価対象がマクロ呼び出しならスタックに積んで第一引数から評価を始める
    ([$($stack:tt),*], $name:ident ! ($argn:ident ! $arga:tt, $($args: tt)*)) => {
        ck!([($name, ($($args)*), ()) $(,$stack)*], $argn!$arga)
    };
    // コンマの扱いのために1引数の場合も別途定義
    ([$($stack:tt),*], $name:ident ! ($argn:ident ! $arga:tt)) => {
        ck!([($name, (), ()) $(,$stack)*], $argn!$arga)
    };
    // 無引数マクロは即時評価
    ([$($stack:tt),*], $name:ident ! ()) => {
        name!([$($stack),*])
    };
    // 1つの引数の評価が終わって、まだ評価していない引数があるなら
    // 評価が終わったリストにその値を加えてまだ評価していない引数を評価する
    ([($name:ident, ($todon:ident ! $todoa:tt, $($todos:tt)*), ($($dones:tt),*)) $(, $stack:tt)*], q!($value:tt)) => {
        ck!([($name, ($($todos)*), ($($dones,)* $value)) $(, $stack)*], $todon ! $todoa)
    };
    // コンマの扱いのためにTODOが1つの場合も別途定義
    ([($name:ident, ($todon:ident ! $todoa:tt), ($($dones:tt),*)) $(, $stack:tt)*], q!($value:tt)) => {
        ck!([($name, (), ($($dones,)* $value)) $(, $stack)*], $todon ! $todoa)
    };
    // 全ての引数を評価したなら満を持してマクロを呼ぶ。
    ([($name:ident, ( ), ($($dones:tt),*)) $(, $stack:tt)*], q!($value:tt)) => {
        $name!([$($stack),*], $($dones,)* $value)
    };
}

macro_rules! add {
    ($s:tt, ($($l:tt),*), ()) => {
        ck!($s, q!(($($l),*)))
    };
    ($s:tt, ($($l:tt),*), (1)) => {
        ck!($s, q!((1, $($l),*)))
    };
    ($s:tt, ($($l:tt),*), (1 $(, $r:tt)*)) => {
        ck!($s, add!(q!((1, $($l),*)), q!(($($r),*))))
    };
}

macro_rules! sub {
    ($s:tt, ($($l: tt),*), ()) => {
        ck!($s, q!(($($l),*)))
    };
    ($s:tt, (1 $(, $l: tt)*), (1)) => {
        ck!($s, q!(($($l),*)))
    };
    ($s:tt,  (1 $(, $l:tt)*), (1 $(, $r: tt)*)) => {
        ck!($s, sub!(q!(($($l),*)), q!(($($r),*))))
    };
}

macro_rules! fib {
    ($s: tt, ()) => {ck!($s, q!((1)))};
    ($s: tt, (1)) => {ck!($s, q!((1)))};
    ($s: tt, ($($n:tt),*)) => {
        ck!($s, add!(fib!(sub!(q!(($($n),*)), q!((1)))), fib!(sub!(q!(($($n),*)), q!((1, 1))))))
    };
}

fn main() {
    let n = ck!([], fib!(q!((1, 1, 1, 1, 1))));
    println!("{:?}", n);
}