% Ook!
このマクロは Ook! 難解プログラミング言語の実装であり、Brainfuck 難解プログラミング言語と同型です。
この言語の実行モデルは非常に単純です。メモリは、何らかの不定個数（通常は少なくとも30,000個）の「セル」（一般に少なくとも8ビット）の配列として表現されます。メモリへのポインターがあり、位置0から開始します。最後に、実行スタック（ループを実装するために使用）とプログラム内へのポインターがありますが、これら最後の2つは実行中のプログラムには公開されません。これらはランタイム自体のプロパティです。
この言語自体は、Ook.、Ook?、Ook! の3つのトークンだけで構成されています。これらはペアで組み合わされ、8つの異なる操作を形成します。
Ook. Ook?- ポインターをインクリメントする。Ook? Ook.- ポインターをデクリメントする。Ook. Ook.- ポインターの指すメモリセルをインクリメントする。Ook! Ook!- ポインターの指すメモリセルをデクリメントする。Ook! Ook.- ポインターの指すメモリセルを標準出力に書き込む。Ook. Ook!- 標準入力から読み取り、ポインターの指すメモリセルに格納する。Ook! Ook?- ループを開始する。Ook? Ook!- ポインターの指すメモリセルが0でない場合はループの先頭に戻る。それ以外の場合は続行する。
Ook! はチューリング完全であることが知られているため興味深いです。つまり、これを実装できるどのような環境も、それ自体もチューリング完全でなければならないということです。
実装
#![recursion_limit = "158"]
実はこれは、最後に示すサンプルプログラムが実際にコンパイルされる、可能な限り低い再帰制限です。何がこれほど途方もなく複雑で、デフォルト制限の5倍近い再帰制限を正当化するのか疑問に思っているなら……当ててみてください。
type CellType = u8;
const MEM_SIZE: usize = 30_000;
これらは、マクロ展開から見えるようにすることだけを目的としてここにあります。1
macro_rules! Ook {
名前は標準的な命名規約に合わせて ook! にするべきだったのかもしれませんが、この機会はあまりにも魅力的で見逃せませんでした。
このマクロのルールは、内部ルールパターンを使ってセクションに分割されています。
これらの最初は @start ルールで、残りの展開が行われるブロックのセットアップを担当します。ここには特に興味深いものはありません。いくつかの変数とヘルパー関数を定義し、その後、展開の大部分を行います。
いくつか小さな注意点:
- 主に、エラー処理を簡素化するために
try!を使えるよう、関数へ展開しています。 - アンダースコアで始まる名前を使っているのは、たとえばユーザーがI/Oを行わないOok!プログラムを書いた場合でも、未使用の関数や変数についてコンパイラーが警告しないようにするためです。
(@start $($Ooks:tt)*) => {
{
fn ook() -> ::std::io::Result<Vec<CellType>> {
use ::std::io;
use ::std::io::prelude::*;
fn _re() -> io::Error {
io::Error::new(
io::ErrorKind::Other,
String::from("ran out of input"))
}
fn _inc(a: &mut [u8], i: usize) {
let c = &mut a[i];
*c = c.wrapping_add(1);
}
fn _dec(a: &mut [u8], i: usize) {
let c = &mut a[i];
*c = c.wrapping_sub(1);
}
let _r = &mut io::stdin();
let _w = &mut io::stdout();
let mut _a: Vec<CellType> = Vec::with_capacity(MEM_SIZE);
_a.extend(::std::iter::repeat(0).take(MEM_SIZE));
let mut _i = 0;
{
let _a = &mut *_a;
Ook!(@e (_a, _i, _inc, _dec, _r, _w, _re); ($($Ooks)*));
}
Ok(_a)
}
ook()
}
};
オペコード解析
次は「execute」ルールで、入力からオペコードを解析するために使用されます。
これらのルールの一般形は (@e $syms; ($input)) です。@start ルールから分かるように、$syms はプログラムを実際に実装するために必要なシンボルの集合です: 入力、出力、メモリ配列、など。これらのシンボルを後続の中間ルールへ転送するのを簡単にするため、TTバンドリングを使用しています。
まず、再帰を終了させるルールです。入力がもうなくなったら停止します。
(@e $syms:tt; ()) => {};
次に、各オペコードのほぼそれぞれに対して1つのルールがあります。これらでは、オペコードを取り除き、対応するRustコードを出力し、その後、入力の残り部分に対して再帰します: 典型的なインクリメンタルTT muncherです。
// ポインターをインクリメントする。
(@e ($a:expr, $i:expr, $inc:expr, $dec:expr, $r:expr, $w:expr, $re:expr);
(Ook. Ook? $($tail:tt)*))
=> {
$i = ($i + 1) % MEM_SIZE;
Ook!(@e ($a, $i, $inc, $dec, $r, $w, $re); ($($tail)*));
};
// ポインターをデクリメントする。
(@e ($a:expr, $i:expr, $inc:expr, $dec:expr, $r:expr, $w:expr, $re:expr);
(Ook? Ook. $($tail:tt)*))
=> {
$i = if $i == 0 { MEM_SIZE } else { $i } - 1;
Ook!(@e ($a, $i, $inc, $dec, $r, $w, $re); ($($tail)*));
};
// ポインターの指すセルをインクリメントする。
(@e ($a:expr, $i:expr, $inc:expr, $dec:expr, $r:expr, $w:expr, $re:expr);
(Ook. Ook. $($tail:tt)*))
=> {
$inc($a, $i);
Ook!(@e ($a, $i, $inc, $dec, $r, $w, $re); ($($tail)*));
};
// ポインターの指すセルをデクリメントする。
(@e ($a:expr, $i:expr, $inc:expr, $dec:expr, $r:expr, $w:expr, $re:expr);
(Ook! Ook! $($tail:tt)*))
=> {
$dec($a, $i);
Ook!(@e ($a, $i, $inc, $dec, $r, $w, $re); ($($tail)*));
};
// stdout に書き込む。
(@e ($a:expr, $i:expr, $inc:expr, $dec:expr, $r:expr, $w:expr, $re:expr);
(Ook! Ook. $($tail:tt)*))
=> {
try!($w.write_all(&$a[$i .. $i+1]));
Ook!(@e ($a, $i, $inc, $dec, $r, $w, $re); ($($tail)*));
};
// stdin から読み取る。
(@e ($a:expr, $i:expr, $inc:expr, $dec:expr, $r:expr, $w:expr, $re:expr);
(Ook. Ook! $($tail:tt)*))
=> {
try!(
match $r.read(&mut $a[$i .. $i+1]) {
Ok(0) => Err($re()),
ok @ Ok(..) => ok,
err @ Err(..) => err
}
);
Ook!(@e ($a, $i, $inc, $dec, $r, $w, $re); ($($tail)*));
};
ここから物事はより複雑になります。このオペコード Ook! Ook? はループの開始を示します。Ook! のループは次のRustコードに変換されます:
> **注記**: これは、より大きなコードの一部では*ありません*。
>
> ```ignore
> while memory[ptr] != 0 {
> // ループの内容
> }
> ```
もちろん、実際には不完全なループを出力することはできません。これは [pushdown](../pat/README.html#push-down-accumulation) を使えば解決*できるかもしれません*が、より根本的な問題があります。つまり、`while memory[ptr] != {` を*どこにも*、まったく*書けない*のです。なぜなら、そうすると対応の取れていない波括弧が導入されてしまうためです。
これに対する解決策は、実際に入力を 2 つの部分、すなわちループの*内側*にあるすべてと、その*後*にあるすべてに分割することです。`@x` ルールが前者を処理し、`@s` が後者を処理します。
```ignore
(@e ($a:expr, $i:expr, $inc:expr, $dec:expr, $r:expr, $w:expr, $re:expr);
(Ook! Ook? $($tail:tt)*))
=> {
while $a[$i] != 0 {
Ook!(@x ($a, $i, $inc, $dec, $r, $w, $re); (); (); ($($tail)*));
}
Ook!(@s ($a, $i, $inc, $dec, $r, $w, $re); (); ($($tail)*));
};
ループ抽出
次は @x、つまり「抽出」ルールです。これらは入力 tail を受け取り、ループの内容を抽出する役割を持ちます。これらのルールの一般的な形式は (@x $sym; $depth; $buf; $tail) です。
$sym の目的は上記と同じです。$tail は解析対象の入力であり、$buf はループの内側にあるオペコードを収集するための push-down accumulation buffer です。では、$depth は何でしょうか。
ここで複雑なのは、ループがネストできるという点です。そのため、現在どれだけ深いレベルにいるのかを追跡する何らかの方法が必要です。解析を早く止めすぎることも、遅く止めすぎることもなく、レベルがちょうどよいときに止められる程度に、これを正確に追跡しなければなりません。2
マクロでは算術を行えず、明示的な整数マッチングルールを書き出すのも現実的ではありません（自明でない数の正の整数に対して、以下のルールをすべてコピー & ペーストすることを想像してください）。そのため、代わりに歴史上最も古く由緒ある数え方の 1 つ、つまり指で数える方法に戻ることにします。
しかし、マクロには指がありません。そこで代わりに token abacus counter を使います。具体的には @ を使い、それぞれの @ が深さの追加レベル 1 つを表します。これらの @ をグループ内に収めておけば、必要な 3 つの重要な操作を実装できます。
- インクリメント:
($($depth:tt)*)にマッチし、(@ $($depth)*)に置換する。 - デクリメント:
(@ $($depth:tt)*)にマッチし、($($depth)*)に置換する。 - ゼロとの比較:
()にマッチする。
最初は、解析中のループを閉じる、対応する Ook? Ook! シーケンスを見つけたことを検出するルールです。この場合、蓄積されたループ内容を、前に定義した @e ルールに渡します。
残りの入力 tail に対して何かを行う必要はないことに注意してください（それは @s ルールによって処理されます）。
(@x $syms:tt; (); ($($buf:tt)*);
(Ook? Ook! $($tail:tt)*))
=> {
// 最外側のループが閉じられた。バッファ済みのトークンを処理する。
Ook!(@e $syms; ($($buf)*));
};
次に、ネストしたループに入るためのルールと、そこから出るためのルールがあります。これらはカウンターを調整し、オペコードをバッファに追加します。
(@x $syms:tt; ($($depth:tt)*); ($($buf:tt)*);
(Ook! Ook? $($tail:tt)*))
=> {
// 1 レベル深くなる。
Ook!(@x $syms; (@ $($depth)*); ($($buf)* Ook! Ook?); ($($tail)*));
};
(@x $syms:tt; (@ $($depth:tt)*); ($($buf:tt)*);
(Ook? Ook! $($tail:tt)*))
=> {
// 1 レベル浅くなる。
Ook!(@x $syms; ($($depth)*); ($($buf)* Ook? Ook!); ($($tail)*));
};
最後に、「それ以外すべて」に対するルールがあります。$op0 と $op1 のキャプチャに注意してください。Rust から見れば、私たちの Ook! トークンは常に 2 つの Rust トークン、すなわち識別子 Ook と、もう 1 つのトークンです。そのため、!、?、. を tt としてマッチすることで、ループ以外のすべてのオペコードを一般化できます。
ここでは、$depth には手を加えず、単にオペコードをバッファに追加します。
(@x $syms:tt; $depth:tt; ($($buf:tt)*);
(Ook $op0:tt Ook $op1:tt $($tail:tt)*))
=> {
Ook!(@x $syms; $depth; ($($buf)* Ook $op0 Ook $op1); ($($tail)*));
};
ループスキップ
これは、ループ抽出とおおむね同じですが、ループの内容には関心がありません（したがって、蓄積バッファも不要です）。知る必要があるのは、いつループを通過したかだけです。その時点で、@e ルールを使って入力の処理を再開します。
したがって、これらのルールはこれ以上の説明なしで提示します。
// ループの終わり。
(@s $syms:tt; ();
(Ook? Ook! $($tail:tt)*))
=> {
Ook!(@e $syms; ($($tail)*));
};
// ネストしたループに入る。
(@s $syms:tt; ($($depth:tt)*);
(Ook! Ook? $($tail:tt)*))
=> {
Ook!(@s $syms; (@ $($depth)*); ($($tail)*));
};
// ネストしたループを抜ける。
(@s $syms:tt; (@ $($depth:tt)*);
(Ook? Ook! $($tail:tt)*))
=> {
Ook!(@s $syms; ($($depth)*); ($($tail)*));
};
// ループのオペコードではない。
(@s $syms:tt; ($($depth:tt)*);
(Ook $op0:tt Ook $op1:tt $($tail:tt)*))
=> {
Ook!(@s $syms; ($($depth)*); ($($tail)*));
};
エントリーポイント
これは唯一の非内部ルールです。
この定式化は、渡されたすべてのトークンに単純にマッチするため、極めて危険であることは注目に値します。何らかの間違いによって呼び出しが上記すべてのルールにマッチできなくなると、このルールまで落ちてきて、無限再帰を引き起こします。
このようなマクロを書いている、変更している、またはデバッグしているときは、このルールのようなものに一時的に @entry のような接頭辞を付けるのが賢明です。これにより無限再帰のケースを防ぎ、適切な場所でマッチャーエラーを得られる可能性が高くなります。
($($Ooks:tt)*) => {
Ook!(@start $($Ooks)*)
};
}
使用法
これが、最後に、私たちのテストプログラムです。
fn main() {
let _ = Ook!(
Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook! Ook? Ook? Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook? Ook! Ook! Ook? Ook! Ook? Ook.
Ook! Ook. Ook. Ook? Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook! Ook? Ook? Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook?
Ook! Ook! Ook? Ook! Ook? Ook. Ook. Ook.
Ook! Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook! Ook. Ook! Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook! Ook. Ook. Ook? Ook. Ook?
Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook! Ook? Ook? Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook?
Ook! Ook! Ook? Ook! Ook? Ook. Ook! Ook.
Ook. Ook? Ook. Ook? Ook. Ook? Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook! Ook? Ook? Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook? Ook! Ook! Ook? Ook! Ook? Ook.
Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook.
Ook? Ook. Ook? Ook. Ook? Ook. Ook? Ook.
Ook! Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook! Ook. Ook! Ook! Ook! Ook! Ook! Ook!
Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook.
Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook!
Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook!
Ook! Ook. Ook. Ook? Ook. Ook? Ook. Ook.
Ook! Ook. Ook! Ook? Ook! Ook! Ook? Ook!
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook! Ook.
);
}
実行したときの出力（コンパイラが数百回もの再帰的なマクロ展開を行うため、かなり待たされた後）は次のとおりです。
Hello World!
これにより、macro_rules! がチューリング完全であるという恐ろしい真実を示したことになります！
余談
これは "Hodor!" という同型の言語を実装するマクロをベースにしています。その後、Manish Goregaokar が Hodor! マクロを使って Brainfuck インタープリターを実装しました。つまり、これは macro_rules! を使って実装された Hodor! で書かれた Brainfuck インタープリターです。
伝説によれば、再帰制限を 300万 まで引き上げ、4日間 実行し続けた後、ついに完了したそうです。
...スタックをオーバーフローさせて異常終了することで。今日に至るまで、マクロとしての esolang は Rust における開発手法として明らかに実用に耐えないままです。