無限ループ

（むげんループ）は、コンピュータ・プログラム等の一連の手続き等が無限に繰り返される（ループする）ことである。（えいきゅうループ）ともいう。

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

ループ[編集]

理論的には、すなわち、計算理論と呼ばれている分野の観点からすれば、なにかについてそれが「計算可能である」とするには、無限ループになりえないことが必要である。しかし、現実のプログラムが対象とするものは必ずしも、理論がいう「計算可能」なものとは限らないし、時にはバグなどによって、決して終了することのない無限ループが発生する。また現実にはしばしば「終了することのないコンピュータ・プログラム」は必要なものですらある。例えば表計算ソフトウェアやワープロソフトウェアは利用者からの明示的な指示がない限りは起動した状態でいなければならない。またインターネットやデータベースなどのサーバプログラムの多くは「リクエストを待ってサービスする」ことをいつまでも繰り返すし、オペーレーティングシステムのようなより低い階層のシステムではそういうものが多い。しかしほとんどの場合、そういったシステムは何らかの方法で止める手段があり、それらとは異なり「無限ループ」という言葉は意図した結果ではないため割込みや強制シャットダウンといった手段でしか止められないような状況を指して使われることが多い（すなわち、原因にバグがあるといったような場合である）。

さらに、慣用的な用法としては「ループ抜け出す条件が入り組んでいて、ループの先頭部分でも終端部分でもない手続きの中間部分でループから抜け出す必要があり、そのためループ自体は無限ループの形で書いておき、ループの途中で必要に応じてから途中脱出機能を使って脱出するというような場合を「無限ループの形」と称することもある。

「#無限ループの検出」も参照

明示的な無限ループの例[編集]

BASICでの簡単な例：

10 LET 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) でテストする。そのどちらでも、有限回数の繰り返しで脱出できる。

数列の収束判定に伴う無限ループ[編集]

数値解析でも似たような状況が起きることがある。ある結果を求めるために、ある許容値に誤差が収まるまで繰り返す、という手続きを使うことがある。しかし、式に問題があって誤差がその許容値を下回ることが無ければ、結果として無限ループになる。

循環リストに起因する無限ループ[編集]

連結リストのようなデータ構造がループを持っているのに、それに対してリストに添う繰返しを行ってしまう、というようなパターンもある。データ構造のループの検出はちょっとした練習問題として知られている。簡単な例として、12、99、37の3つの整数値を格納した循環リストの中身をひとつづつリストに沿って出力する処理をすると「12、99、37、12、99、37、12、99、37、…」と無限に出力することになる。

3つの整数値を格納した循環リスト

複数のプログラム間で発生するループ[編集]

単体のプログラムでの無限ループは通常予測しやすいが、複数の要素が相互に影響しあったループは遥かに予測しにくい。ここで、リクエストを理解できない時にはいつもエラーメッセージを返すサーバについて考えてみる。明らかに、そのサーバには無限ループの可能性は全く無いが、そのようなサーバが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 をコンピュータのメモリに格納できなくなるまでループが続く。

無限再帰[編集]

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

procedure Omega () is   procedure omega_ (p : procedure) is   begin     p(p) ;   end ; begin   omega_(omega_) ; end ;

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

このような不完全な構造的再帰を次のコードで例示する。関数 sumFrom1To_ は無限再帰となる。これを修正するには、基底ケースを追加する。

function sumFrom1To_ (n : Integer) return Integer is begin   return n + sumFrom1To_ (n-1) ; end ;

この問題を修正したものが次の関数である。これは n が 1 未満か、n が大きすぎる時にだけ無限再帰となる、最初のケースはエラーチェックすれば回避できる。

function sumFrom1To (n : Integer) return Integer is begin   if n = 1 Then     return 1 ;   else     return n + sumFrom1To(sub1 n) ;   end if ; end ;

オルダーソンループ[編集]

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

その他[編集]

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

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

無限ループの検出[編集]

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

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

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

理論上、プログラムが停止するのか動き続けるのかを「どんなプログラムに対しても」「有限の時間内で」「必ず決定できる」ことを全て満たす方法は無い。これは停止問題の決定不能性からの結論である。

日常会話での使用[編集]

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

その他の無限ループ[編集]

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

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

コンピュータゲームにおいて、特定のルートを通ると、再び同じルートが登場し、先に進めなくなる仕掛けのことを無限ループと呼ぶ場合がある。これは特定のルート以外を通れば脱出できるため、厳密な意味での無限ループではない。なお、脱出できる分岐がその先には存在しなくなる一種のトラップが仕掛けてあるゲームもあり、そういったものは本物の無限ループである。また、制限内で高得点等を狙うゲームの場合、無制限に点数稼ぎを繰り返すことができてしまうと、高得点ランキングが無意味になってしまうため回避されるのだが（さらにアーケードゲーム等では、オペレータ（店）や運営元のインカム（収入）に影響するため特に忌避される）、バグ、あるいはプレイヤーの超人的な腕によって可能になる場合があり「永久パターン」と特に呼ばれている。

住所[編集]

米国カリフォルニア州クパチーノには無限ループを表す Infinite Loop という住所が存在する。IT企業であるAppleの本社敷地Apple Campus内にある楕円形の道路に「Infinite Loop」の名前が付けられており、この道路を取り囲むように最大5条の同心円状の駐車場が設けられている。

Infinite Loopの内側にはアップルが保有する6つの建物があり、それぞれ公式に 1 Infinite Loop から 6 Infinite Loop までの住所が与えられている。アップル本社の公式住所は 1 Infinite Loop, Cupertino, California である。

ジョーク[編集]

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

出典[編集]

^ Alderson Loop The Jargon File, Version 4.4.7. Accessed 5/21/2006. (Public Domain) （英語）
^ The Story of Mel "Perhaps my greatest shock came ～" から後のくだり
^ Caught in an infinite loop （無限ループにハマりました）日常会話での使用例。（英語）
^ Confession of an infinite looper （無限ルーパーの告白）ある曲だけを繰り返し聞いている人。（英語）
^ infinite loop