無限ループ

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

専門用語としては一応きちんとした意味があるが、刺激的に感じられる他の用語（例えばメモリリーク）と同様に、通俗的な使い方もされる（「日常会話での使用」を参照）。専門的な意味としての無限ループは、通常プログラマが原因を突き止めることができる、と簡単に考える者もいるようだが、実際のところそうではないこともある（#無限ループの検出）。

ループ

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

但し、慣用的な用法としては、ループの先頭部分でも終端部分でもない手続きの中途半端な部分でループから抜け出す必要があり、抜け出す条件が入り組んでいる、といったような場合に使うような、ループ自体は無限ループ風に書いておき（たとえばC言語なら「for (;;) { ... }」と書くのがイディオムである）、途中脱出機能を使って脱出する（C言語なら break 文）というような場合を指しても「無限ループの形」のように言ったりもする。

無限ループのよくある原因の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つの浮動小数点数の厳密な一致をテストしていることである。多くのコンピュータの（2進の）浮動小数点の計算では 0.1 という値は正確に表現できないため、それを11回足した値がリテラルの 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 のどちらのボタンも無いために、そのダイアログボックスが表示されると必ずプログラム全体が停止してしまった、ということである。

その他

一見無限ループに見えるが、例外や大域ジャンプ（en:setjmp.h）により抜け出している、というパターンもある。サーバのように、本来無限に処理すべきである場合であればともかく、普通は、例外的ではない通常の処理（たとえば、ファイルの終了が返されているにもかかわらず続きを読もうとしたのであれば例外を使うべきだが、単にファイルの終了に到達しただけならばそうすべきでないのが普通）の流れに例外処理を使うのは良くない作法とされる。

ジャーゴンファイルに収録されている「The Story of Mel」には、どう見ても無限ループに見えるが、オーバーフローにより隣のメモリが書き換わることを利用してジャンプ命令を自己書き換えし終了する、という技を見た、という話が紹介されている。

無限ループの検出

無限ループは、通常、プログラマが原因を突き止めることができると簡単に考える者もいるようだが、次のような例を考えればそうでないことがわかる（簡単のため、数値は無限に大きな値を扱えるものとする）。

1. 入力として、正の整数であるnをとる。
2. nが偶数の場合、nを2で割る。
3. そうでなければ、nを3倍して、さらに1を加える。
4. nが1なら終了する。
5. ステップ2に戻る。

上記はごく簡単なプログラムであるが、たとえば最初のnを27とすると、途中でnは最大9232となる。そして、このプログラムがどんなnに対しても終了するか、あるいはあるnで始めると無限ループとなってしまうかという問題はコラッツの問題と呼ばれ、2014年時点で未解決の問題である。

理論上、プログラムが必ず停止するのか動き続けるのかを見付け出す「一般的」な方法は無い。これは停止問題の決定不能性からの結論である。

日常会話での使用

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

その他

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

クラシック曲では普通は無いが、近年のポピュラー音楽等では、進行が終止せず、終止に向けた一定のフレーズを繰り返しながらフェードアウトして終わる、といった曲や、ゲームのBGMのように曲自体は何度でも繰返して終わりがないといった曲もある。

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

ジョーク

無限ループをx秒で実行し終えることができる、というスーパーコンピュータの性能をネタにした定番ジョークがある（チャック・ノリス・ファクトのコンピュータ業界版みたいなもの）。ジャーゴンファイルの "infinite loop" の項目にある例では「Cray-3はとても速くて、無限ループを2秒で実行できるくらいだって！」（"The Cray-3 is so fast it can execute an infinite loop in under 2 seconds!"）。

関連項目

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