C++で副作用のない無限ループを書くと未定義動作になります。
「未定義動作」というのは口に出すだけでC++プログラマーを震え上がらせる力を持った言葉です。「鼻から悪魔が出てくる」という言葉で説明されるように、未定義動作を含むコードを実行した結果は何も保証することができず、バグの発見やデバッグすら困難にさせます。未定義動作下においてはコンパイラの気分によってコード片が消え、trueとfalseが同時に成立し、タイムトラベルを引き起こします1。
そのためC++ではうっかり未定義動作が埋め込まれないよう注意が払われるのが普通です。
さて、以下のC++のコードは未定義動作を引き起こします。
while(true){
//Do nothing
}
以下もです。
int func(){
return func();
}
下の例は実際にclang/LLVMで最適化を有効にしてコンパイルするとでたらめな値を返す関数ができました。
この話をしたところ、何人かに驚かれたり異論を受け取ったりしたので、この話題について少しまとめてみました。
標準規格の記述
不安になったら規格を見るのが一番です。ここではC++17相当のN4659を見てみましょう。(記事の著者はC++の規格に精通していませんので、読み間違いがあったらすみません。)
無限ループと未定義動作に関する記述は4.7.2 Forward progressにみることができます。該当箇所を抜き出してみましょう。
The implementation may assume that any thread will eventually do one of the following:
(1.1) — terminate,
(1.2) — make a call to a library I/O function,
(1.3) — perform an access through a volatile glvalue, or
(1.4) — perform a synchronization operation or an atomic operation.
[ Note: This is intended to allow compiler transformations such as removal of empty loops, even when termination cannot be proven. — end note ]
(拙訳)
実装は、あらゆるスレッドについて、最終的に以下のいずれかの動作を行うものと想定して構わない。
(1.1) — 終了する。
(1.2) — ライブラリのI/O関数を呼ぶ。
(1.3) — volatile glvalueを通してアクセスを行う。
(1.4) — 同期操作あるいはアトミック操作を行う。
[注記: この記述はコンパイラに空ループの除去(ループの終了が証明できない場合を含む)などの操作を認めることを念頭に置いている。 — 注記ここまで]
というわけで、実装上のバグなどではなくむしろはじめからループの除去を目的として規格に書かれていることがわかります。
(明示的に未定義動作とは書かれていませんが、「常に~であることを想定してよい」というのはそのまま「~でない場合の挙動は未定義である」ということです。)
この点、冒頭の記述は不正確でした。正確には、
- 効力の範囲は
while(true)などの明示的な無限ループに限らない。条件が複雑なループ、再帰などを含めスレッドが終了しないあらゆるケースが対象になる。 - 冒頭では「副作用のない」と書いたが、実際に無限ループが認められる操作はかなり限定されている。無限ループ内でループのスコープ外の(volatileでない)local/global変数を触る場合でも同様に未定義動作になる。
となります。C++11の頃はループに限定した記述だったようですが、曖昧さを減らすためこの文面に変更されたそうです。
未定義動作の具体例
どういったときにこの問題に遭遇しうるのかを考えてみました。
無限ループをほんとうに使いたい場合
終了しないことを前提としたコードでは無限ループが現れることがあります。例えば組み込み機器などではメインスレッドが何らかの事情で無限ループで待機することがあります。
while(true){ }
ここで、上記のようにほんとうに空の無限ループを書いてしまうと途端に未定義ワールドに侵入することになります。(毎回volatile変数を監視するなどしていれば大丈夫でしょう。)
外部デバイスの操作など何らかの動作を行い続ける正しい無限ループを書いたときでも、環境によってコードが異なっており実装がたまたま無かったりすると同様のことが起き得ます。
C++でなくCの話ですが、linux 2.6.0にも空の無限ループがあったそうです。このときはGCCが空ループを除去しないという慈悲深い振る舞いに助けられたそうです2。
終了するか無限ループかで条件を分けようとした場合
意図的かそうでないかにかかわらず、入力によって何らかの処理が終わらなくなることはあります。ここで、処理が終わらない可能性があること自体は問題になりません。コンパイラから見て何らかの未知の値を出力して終わる可能性を捨てきれない限りは勝手にループを抜けることができないからです。そもそも一般に与えられたプログラムが終了するかどうかなど人類やコンピュータが知り得るものではありません。
問題は、うまくいった場合は単に成功フラグを立てるなど、無限ループでない限り常に同じ振る舞いをする場合です。こうなるとコンパイラから見て未知の値を返して終わる可能性がなくなるので面倒なことになります。
例えば、数論の未解決問題にコラッツの問題というものがあります。これは「任意の正整数nについてnが偶数なら2で割る、奇数なら3倍して1を足す、の動作を繰り返すとどんなnから始めても必ず1になる」という主張です。
これをコンピュータで確かめるために以下のようなコードを書いたとします。
#include <cstdlib>
#include <iostream>
template <typename T>
T collatz(T input){
auto n = input;
while(true){
if(n == 1) return 1;
if(n % 2 == 0){
n /= 2;
}else{
n = 3 * n + 1;
}
}
}
int main(int argc, char** argv){
auto n = std::atoll(argv[1]);
std::cout << collatz(n) << std::endl;
return 0;
}
書いた側の意図としては、値が1になったときにループを抜け、プログラムが終了することをもって検証を行おうというものです。しかし、コンパイラはこれを見たときに以下のようなことを考えることが認められています。
「ループを抜けることができるのはループ中のreturn 1;に到達したときだけだ。それならはじめからループ全体をreturn 1;に置き換えてしまえばよい。なぜならこのループは必ず終了することがわかっているからだ。」
これによってこのプログラムはコラッツ予想の検証を飛ばして絶対に1を返すプログラムへと書き換えられます。
手元のclang/LLVMは本当にこれをやってきました。例えば入力が0のときは素朴に考えると無限ループに入ることが予想されますが、最適化を有効にすると入力が0だろうがお構いなく1を表示して終了するプログラムが作られます。賢い！
バグによる無限ループの混入
おそらく最もありえそうな事象は単に実装にバグがあった場合でしょう。例えば再帰でフィボナッチ数を計算するプログラムについて、境界の処理をするのを忘れて無限ループになってしまったとします。
#include <iostream>
int fibonacci(int x){ //wrong implementation
return fibonacci(x-1)+fibonacci(x-2);
}
int main(){
std::cout << fibonacci(10) << std::endl;
return 0;
}
xが0や1であったときの処理を忘れて無限ループになってしまっています。いや、無限ループなら良かったのですが、未定義動作なので何をされるかわかったものではありません。
実際これも手元のclang/LLVMで最適化を有効にすると無限ループではなく不定の値を表示するプログラムができあがりました。
未定義となっている理由
まず、C++のコンパイラがこのような振る舞いをして構わないとされている背景についてです。
一般的な最適化の話ですが、コンパイラはソースコードの内容をすべて書かれたとおりに正しく実行するプログラムを出力しなければならないわけではありません。外から見た振る舞い(observable behavior)さえ合っていればいいという発想です。これにより、値が定数だったらコンパイル時に先に計算してしまったり、出力に影響しない処理があったら削ってしまったりしても構わないわけです。
では何が合っていればいいかというと、これは規格に書かれています。4.6 Program executionの該当の箇所を引用します。
7 The least requirements on a conforming implementation are:
(7.1) — Accesses through volatile glvalues are evaluated strictly according to the rules of the abstract machine.
(7.2) — At program termination, all data written into files shall be identical to one of the possible results that execution of the program according to the abstract semantics would have produced.
(7.3) — The input and output dynamics of interactive devices shall take place in such a fashion that prompting output is actually delivered before a program waits for input. What constitutes an interactive device is implementation-defined.
These collectively are referred to as the observable behavior of the program. [ Note: More stringent correspondences between abstract and actual semantics may be defined by each implementation. — end note ]
大まかに書くと、volatile変数へのアクセス(7.1)、プログラム終了時のファイルへの書き込み(7.2)、対話型デバイスの入力と出力の順序(7.3)の3種類がコンパイラが満たさなければならないobservable behaviorとして定義されています。(標準出力などもファイルの一種です。)
ここで、(7.2)ではプログラム終了時のと書かれていることがポイントです。つまり終了しないプログラムは対象から外れているのです。
無限ループを未定義動作とすることの実用上のうれしさは何があるのでしょうか。
WG14/N1528でこの話題について議論されています。そこでは以下のような例が出されました。
for (p = q; p != 0; p = p -> next) {
++count;
}
for (p = q; p != 0; p = p -> next) {
++count2;
}
ただし、ここでcountとcount2は例えばglobal変数、pは宣言したばかりのlocal変数などとしておきます。
さて、これは最適化によって
for (p = q; p != 0; p = p -> next) {
++count;
++count2;
}
とできるでしょうか？
もし1つ目のループが(qが循環リンクリストであるなどして)無限ループだったとすると、上の例では2つ目のループにはたどり着かずcount2の値は変更されません。一方で下の例ではcount2の値が変わります。ここで例えば他の並行して実行中のスレッドからcount2にアクセスがあるとすると、両者で振る舞いが変わってしまいます。つまり、ループが終了することを知らなければコンパイラは上のコードを下のように書き換えることができません。
とはいえ、コンパイラにループが終了するかどうかを証明させるのは現実的ではありません。そこで「この手のループは終了することは前提として構わない(=ループが終了することの保証は書いた人の責任とする)」とわざわざ規格で定めることでこのような最適化が可能になります。
個人的な感想
最適化とのトレードオフとはいえ、無限ループが未定義になるというのは個人的には少し苦手な振る舞いです。C++の初学者に再帰の説明をした後で「シンプルな無限再帰をコンパイルすると意味不明な値が帰ってくる関数ができあがる」振る舞いの理由を説明するのは骨が折れそうです。
C++には配列の境界外アクセスやヌルポインタの参照外しなど様々な未定義動作がありますが3、たいていの場合は局所的な問題であり、std::vectorを使うとかスマートポインタを使うなど適切な処方箋をあたることで、オーバーヘッドと引き換えに他の言語と同じように安全な取扱いが可能になります。しかし無限ループの発生というのは全体のフローにまつわる話で、うっかり関数の呼び出す手順を間違えたときに未定義ワールドに突入するのは怖さがあります。今でこそコンパイラが全知からほど遠いためにたいていの無限ループは単にそのまま無限ループになっていますが、将来十分賢いコンパイラが停止しないコードを目ざとく見つけては鼻から悪魔を出してファイルを全消ししながらCDドライブをパカパカする命令に置き換えはじめたらついていけなくなる気がします。
この振る舞いについて将来どうするかの議論はいろいろあるようですが、今のところは未定義動作でいくことになっているようです。
記述に間違いがありましたらご連絡ください。