もはやRustのマクロはチューリング完全だから

# はじめに

**Rustの `macro_rules!` はチューリング完全か？**

結論：**チューリング完全です**

# 手法

2 状態 18 記号、固定された遷移ルールのチューリングマシン $T$ がチューリング完全[^1]であることはよく知られていますが、Rust のマクロ上でそれを実行可能とすることでチューリング完全であることを示します。

```Rust
fn main() {
    let t = tm0!("F", "A", "A", "A", 
        "F", "F", "A", "A", "A", "A", "A", "A", "F", "A", "A", 
        "F", "F", "Q", "Q"; "F", "A", "A", "A",
        "M", "A", "M");

    print!("{}", t);
}
```

:::note warn
**ああ！待ってください！**

「結局マクロで置き換えてRustの処理を実行しているだけか、舐めプ乙」と思った方、もう少し話をお聞きください。実際、１つの遷移ルールを表すマクロの宣言はこんな感じになります。

```Rust
    ($left:tt; "A", $($rights:tt),*) => {
        tm1!("C"; $left, "R", $($rights),*)
    };
```

ね？**Rustの処理は入っていない** でしょう？
:::

以降では、チューリングマシンをどのようにマクロに畳み込んだのかを説明していきます。

# どうやって動くの？

まず、マクロの仕様面の話から始めます。

マクロは `tm1!` と `tm2!` があります。これは $T$ の内部状態に対応しており、内部状態が $q_1$ の時は `tm1!` を、そうでないときは `tm2!` を解決します。これにより、状態遷移も内部で別の`tm` マクロを呼び出すことで行うことができます。

```Rust
macro_rules! tm1 {
    ($left:tt; "A", $($rights:tt),*) => {
        tm1!("C"; $left, "R", $($rights),*)
    };
    
    //...
}

macro_rules! tm2 {
    ($($lefts:tt),*; "A", $right:tt) => {
        tm2!("C", $($lefts),*; $right, "C")
    };
    //...
}
```

テープの埋め込みは、単に文字列リテラルを "," で並べて行います。例えば最初に出した以下のコードはテープ `"…CQQFFAAFAAAAAAFFAAAF*FAAAMAMC…"` を表しています(`*F` が初期ヘッド位置)。なお、マクロ上では `;` の右の記号が現在ヘッド位置であり、**ヘッドの左側の記号は逆順に記載します。**

```Rust:再掲
fn main() {
    let t = tm0!("F", "A", "A", "A", 
        "F", "F", "A", "A", "A", "A", "A", "A", "F", "A", "A", 
        "F", "F", "Q", "Q"; "F", "A", "A", "A",
        "M", "A", "M");

    print!("{}", t);
}
```

以上で、状態・テープの取り扱い方が明確になったので、改めて遷移ルールの実装を記述できます。

## 遷移ルール？

$T$ の、ある１つの遷移ルールを抜き出してきました。これは、「状態 $q_1$ の時に 記号 $A$ を読んだら、記号$R$に書き換えて左に移動する」というルールを表しています。（２つでひとかたまりです。)

```Rust
macro_rules! tm1 {
    ($left:tt; "A", $($rights:tt),*) => {
        tm1!("C"; $left, "R", $($rights),*)
    };
    ($left:tt, $($lefts:tt),*; "A", $($rights:tt),*) => {
        tm1!($($lefts),*; $left, "R", $($rights),*)
    };
    
    //...
}
```

なんとなくヘッドの位置 (`;` の位置) が動いていることを感じてください。

:::note
`"C"` は空白記号（テープの左右に無限にある記号）です。ヘッドがテープの外に出ないよう、適宜`"C"`を補います。
:::

また、右に移動する場合、

```Rust
macro_rules! tm1 {

    //...

    ($($lefts:tt),*; "B", $right:tt) => {
        tm1!("E", $($lefts),*; $right, "C")
    };
    ($($lefts:tt),*; "B", $right:tt,  $($rights:tt),*) => {
        tm1!("E", $($lefts),*; $right, $($rights),*)
    };
    
    //...
}
```

です。ちょうど `left` と `right` が逆になった形となっています。（前述のとおり、`;` より左の記号は逆順で記載されています。）

## 停止ルール？ (ツッコミポイント)

マクロがチューリング完全な系であるためには、停止ルールを定める必要があります。停止ルールは以下です。

```Rust
macro_rules! tm1 {

    //...

    ($($lefts:tt),*; "Q", $($rights:tt),*) => {{
        let mut t = vec![$($lefts),*];
        t.reverse();
        t.extend(vec!["*Q", $($rights),*]);
        t.join("")
    }};
    
    //...
}
```

「おい！Rustの式が出てるやんけ！」...ごもっともです。マクロの `tt` 要素をそのまま取り出す方法が皆目見当つきませんでしたので、妥協した面があります。

一方で、ここに至るまでマクロ上の `tt` のみで演算をしているので、その意味で私はチューリング完全の要件を満たしているとも考えています[^2]。

# 制限

チューリング完全性に関するいくつかの制限・議論点を述べます。ただし、他のチューリング完全と言われている系もだいたい同じ問題を孕んでいます。

- 上述の、「停止ルール問題」
- 真にチューリングマシンを再現するためには、再帰の深さが無限である必要があります（そして、Rustはそうではありません）。特に、この方法であると$T$ の１ステップが１再帰に相当するため、すぐに上限に達します。ということで、`#![recursion_limit = "1024"]` をコードの先頭に補っています。他の言語も同じことですが
- 真に〃メモリが無限に必要ですが、他の言語も同じです

# 補遺
### 停止ルールのバリアントについて (3/15 追記)

$T$のテープ記号を表すものとして、文字列の代わりに以下のマクロを使用することにすれば...

``` Rust
macro_rules! A {() => {print!("A")}}
macro_rules! B {() => {print!("B")}}
macro_rules! C {() => {print!("C")}}
// ...
macro_rules! P {() => {print!("P")}}
macro_rules! Q {() => {print!("Q")}}
macro_rules! R {() => {print!("R")}}

macro_rules! head {() => {print!(";")}}
```

停止ルールは ↓ のようになりますね。こちらの方がマクロだけで構成する記法としては自然でしょうか。

```Rust
macro_rules! tm1 {

    //...

    ($($lefts:tt),*; Q, $($rights:tt),*) => {{
        $($lefts!();)*head!();Q!();$($rights!();)*
    }};
    
    //...
}
```

# 終わりに

**形式言語をこねくり回すのは楽しい**

# リンク集（Playground 含む）

オリジナル：

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=346e8205e5bd3e31bdbed0bbdebfded7  

「停止ルールのバリアントについて」を適用したもの (3/15 追記)：

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=e09006e821036d33090ddd812240ee91

Rustの型システムがチューリング完全である、という主張の記事　（マクロがチューリング完全である...という記事は現在なさそう？）

https://sdleffler.github.io/RustTypeSystemTuringComplete/

[^1]: つまり、すべてのチューリングマシン $S$ について、$S$ の状態やテープや遷移ルールを"上手く" $T$ の入力テープに変換でき、また $T$ を実行して停止した時のテープを "上手く" 解釈した結果として $S$ の受理状態でのテープを得られるということ。詳しくは Yurii Rogozhin 氏による論文「Small universal Turing machines」を参照。

[^2]: つまり、出力の解釈方法は系に含める必要がなく、外でやればいいことである...というわけです。