無限ループ

無限ループ（むげんループ、英語: infinite loop）は、コンピュータ・プログラムの一連の命令が無限に繰り返される（ループする）ことである。永久ループ（えいきゅうループ）ともいう。

プログラマにとっては特別な意味があり、また刺激的に感じられる他の用語（例えばメモリリーク）と同様に、誤った使い方をされることが時々ある（「日常会話での使用」を参照）。実際の無限ループは、通常プログラマが原因を突き止めることができるものだけである。

ループ

ループとは、特定の条件が満たされるまで一連の命令を繰り返すことである。あるループに内在する特性により、条件が決して満たされない時に無限ループが発生する。こうした挙動が必要とされる状況もわずかに存在する。例えば、インターネットやデータベースなどのサーバプログラムの多くは「リクエストを待ってサービスする」ことをいつまでも繰り返しているが、これは厳密には無限ループとは見なされない。ループの脱出条件として手動でプログラムを終了させることができるからである。ほとんどの場合、「無限ループ」という言葉は意図した結果ではない状況を指して使われる。つまりバグである。そういったミスは初級のプログラマでよく見られるが、経験豊富なプログラマでも間違いを犯すことはあり、その原因はかなり微妙で難解なことがある。

例えばよくある原因の1つとしては、プログラマが線形リストのような項目のコレクションで繰り返しを行おうとして、各項目ごとに1回のループを実行する。この時にリンクが適切でないと「参照ループ」ができてしまい、プログラムはリストの末尾に到達せず、結果的にコードが永遠に続いてしまう。

BASICでの簡単な例：

10 x = x + 1
20 Print x
30 GoTo 10

ここでのループは明らかで、最終行の実行後、無条件に先頭行が実行される。終了条件を評価する時の予想外の挙動でも、この問題は発生する。以下は、C言語での例である：

float x = 0.1;
while (x != 1.1) {
    printf("x = %f\n", x);
    x = x + 0.1;
}

このループはあるシステムでは期待通りに10回実行されるだろうが、他のシステムでは決して終了しないことがある。ここでの問題は、ループの終了条件 (x != 1.1) が2つの浮動小数点値の厳密な一致をテストしていることである。多くのコンピュータでの浮動小数点値の表現では 1.1 という値を正確に表現することができないため、このテストは成立しない。

浮動小数点値を使う時には、等式でテストを行うと予想外に失敗する可能性があるため、不等式でテストすると安全である。例えば x が 1.1 と等しいかどうかをテストする代わりに (x < 1.1) や (x <= 1.0) でテストする。そのどちらでも、有限回数の繰り返しで脱出できる。しかし、実行回数が不確実であることに変わりはなく、別の方法でこの例を修正するとしたら、ループインデックスに整数型を使って繰り返しの回数を数えることが確実である。

int i; /* 整数型のループインデックス */
float x = 0.1;
for (i = 0; i < 10; i++) {
    printf("x = %f\n", x);
    x = x + 0.1;
}

同様の問題は、数値解析でも頻繁に発生する。ある結果を計算するには、ある許容値に誤差が収まるまで繰り返す。しかし、繰り返しの最中での丸め誤差のため、その許容値に達することなく、結果として無限ループになることがある。

ほとんどの無限ループはコードをよく調べれば発見できるが、プログラムが必ず停止するのか動き続けるのかを見付け出す「一般的」な方法は無い。これは停止問題の決定不能性である。

複数間でのループ

単体のプログラムでの無限ループは通常予測しやすいが、複数の要素が相互に影響しあったループは遥かに予測しにくい。ここで、リクエストを理解できない時にはいつもエラーメッセージを返すサーバについて考えてみる。明らかに、そのサーバには無限ループの可能性は全く無いが、そのようなサーバが2つ（AとB）あるとする。サーバAがサーバBから受け取ったメッセージを理解できなかった時、AはBにエラーを返す。Bがメッセージを理解できなかったらそのエラーをAに返し、そのエラーメッセージをAが理解できなければまた別のエラーメッセージを返し、これが永遠に繰り返される（デッドロック）。このような事態のよくある例がメールループである。

疑似無限ループ

疑似無限ループとは、無限に見えるが、実際には非常に長いだけのループのことである。

不可能な終了条件

C言語での例：

unsigned int i;
for (i = 1; i > 0; i++)
{ loop code }

これは永遠に動き続けるように見えるが、実際には i の値はいずれ unsigned int に格納できる最大値に達し、その値に 1 を加えることで 0 に巻き戻され、ループから脱出する。実際の i の限界は、使っているシステムやコンパイラの仕様による。多倍長整数では、i をコンピュータのメモリに格納できなくなるまでループが続く。

無限再帰

無限再帰とは、無限ループの特例で、再帰で発生する無限ループである。最も些細な例としては、次のSchemeで示したラムダ計算の Ω項である。

(define Ω
(let ([ω (lambda (f) (f f))])
(ω ω)))

Ω は無限再帰なので、正規形を持たない。基底ケースが無かったり、帰納段階が不完全な構造的再帰では、普通は無限再帰になってしまう。このような不完全な構造的再帰の例は次の通り。

(define (sum-from-1-to n)
(+ n (sum-from-1-to (sub1 n))))

関数 sum-from-1-to は決して再帰が止まることはなく、スタックを使い尽くすだろう。これを修正するには、基底ケースを追加する。

(define (sum-from-1-to' n)
(cond
[(= n 1) 1]
[else (+ n (sum-from-1-to' (sub1 n)))]))

修正した関数は、n が 1 未満か、n が大きすぎる時にだけ、スタックを使い尽くすが、最初のケースはエラーチェックすれば回避できる。スタックを使い尽くすことのない再帰関数については、末尾再帰を参照のこと。

オルダーソンループ

「オルダーソンループ（Alderson Loop）」とは、ある特別な無限ループを表す隠語・俗語で、終了条件は存在するのだが、そのコードの実装ではアクセスできないもの（通常はプログラマのミス）である。ユーザーインターフェイスのデバッグ中にはよく目にする。例えば「1から3を選択するか9で終了する」というメニューなのに9が選択できるようになっていない、といったものであり、一般によくあるタイプのバグである。この言葉はプログラマの名前に由来すると言われており、その人物は Microsoft Access のモーダルダイアログボックスのコードを書いたのだが、そこには OK と Cancel のどちらのボタンも無いために、そのダイアログボックスが表示されると必ずプログラム全体が停止してしまった、ということである。

日常会話での使用

「無限ループ」という言葉は他のプログラミング用語（例えばメモリリーク）と同様に非プログラマにも魅力的とされていて、プログラミングエラー以外の状況を表現するのにも使われている。例えば、コンピュータを使う上で一連の手順を求められ、最後には振り出しに戻ってしまうような状況である。特に、目的を達成するか回避するか、その手段がどちらも無いような場合に使われることがある。自発的に何かを繰り返すようにすることを指して使われることもある。

その他

楽曲においても、無限ループは発生する。楽譜にてダル・セーニョやダ・カーポでジャンプする指示をしながら、曲の終わりを示すフィーネがないと、曲がいつまでたっても終わらなくなる。エリック・サティのピアノ小曲集『スポーツと気晴らし』の第16曲「タンゴ」のように、意図的にしている例も存在するが、これを意図せずやってしまうと無限ループとなる。

コンピュータゲームにおいて、特定のルートを通ると、再び同じルートが登場し、先に進めなくなる仕掛けのことを無限ループと呼ぶ場合がある。これは特定のルート以外を通れば脱出できるため、厳密な意味での無限ループではない。

関連項目

• Goto文
• 再帰
• ウロボロス
• いたちごっこ
• 停止性問題の決定不能性
• デッドロック
• 循環論法
• 無限後退