無限ループ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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

ループ[編集]

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

但し、慣用的な用法としては、ループの先頭部分でも終端部分でもない手続きの中途半端な部分でループから抜け出す必要があり、抜け出す条件が入り組んでいる、といったような場合に使うような、ループ自体は無限ループ風に書いておき(たとえば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つの浮動小数点値の厳密な一致をテストしていることである。多くのコンピュータでの浮動小数点値の表現では 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 のどちらのボタンも無いために、そのダイアログボックスが表示されると必ずプログラム全体が停止してしまった[1]、ということである。

その他[編集]

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

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

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

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

フェルマーの大定理の反例となるような x^3 + y^3 = z^3 を探すプログラム、というものを考えてみよう。(x, y, z) が (1, 1, 1) から始めて (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), ... と、試すべき組合せは系統的に生成できるので、プログラムとして書き下すことは可能である。このプログラムは止まらない=無限ループになる。ここで、なぜこのプログラムが無限ループになる・止まらないのかを説明することは、フェルマーの大定理を証明することと同じことである。

もちろんワイルズにより定理が証明された以降の世界にいる我々なら「ワイルズによりこの定理は証明されているので」の一言で済ませることができるわけだが、1980年代以前にいるプログラマにとっては(当時の予想に従って、常識的な判断は可能だが)無限ループだ、と断言することは不可能だったわけである(厳密にはワイルズが証明したのは任意のnについてで、3乗に限った場合は以前から証明されているが、考え方として、の話)。

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

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

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

その他[編集]

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

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

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

ジョーク[編集]

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

出典[編集]

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

関連項目[編集]