むげん‐ループ【無限ループ】
無限ループ
無限ループ
無限ループ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/12/22 14:24 UTC 版)
 |
（むげんループ）は、コンピュータ・プログラム等の一連の手続き等が無限に繰り返される（ループする）こと。（えいきゅうループ）ともいう。プログラムの都合上、意図的に無限ループを使用することもあるが、意図せず無限ループに陥ってしまった場合は通例プログラムのフリーズといった異常動作あるいは暴走を引き起こす。ループ内でメモリ確保やファイル書き込みを実行している場合、無限ループによって生じる問題は深刻なものとなる。コンピュータのCPUが無限ループによって休みなく稼働し続ける場合、電力の無駄遣いが発生するだけでなく、オーバーヒート対策が甘いと異常発熱からの故障につながることもある。
英語ではendless loopまたはinfinite loopだが、コンピュータ関連では主に後者が用いられる[1]。
専門用語としての他、刺激的に感じられる他の用語（例えばメモリリーク）と同様に、不正確な通俗的な使い方もされている（「#日常会話での使用」を参照）。専門的な意味としての無限ループは、通常プログラマが原因を突き止めることができる、と簡単に考える者もいる[要出典]ようだが、実際のところそうではないこともある（#無限ループの検出）。
ループ
 | この節の文章は日本語として不自然な表現、または文意がつかみづらい状態になっています。 |
理論的には、すなわち、計算理論と呼ばれている分野の観点からすれば、なにかについてそれが「計算可能である」とするには、無限ループになりえないことが必要である。しかし、現実のプログラムが対象とするものは必ずしも、理論がいう「計算可能」なものとは限らないし、時にはバグなどによって、決して終了することのない無限ループが発生する。また現実にはしばしば「終了することのないコンピュータ・プログラム」は必要なものですらある。例えば表計算ソフトウェアやワープロソフトウェアは利用者からの明示的な指示がない限りは起動した状態でいなければならない。またインターネットやデータベースなどのサーバプログラムの多くは「リクエストを待ってサービスする」ことをいつまでも繰り返すし、オペレーティングシステムのようなより低い階層のシステムではそういうものが多い。しかしほとんどの場合、そういったシステムは何らかの方法で止める手段があり、それらとは異なり「無限ループ」という言葉は意図した結果ではないため割込みや強制シャットダウンといった手段でしか止められないような状況を指して使われることが多い（すなわち、原因にバグがあるといったような場合である）。
さらに、慣用的な用法としては「ループ抜け出す条件が入り組んでいて、ループの先頭部分でも終端部分でもない手続きの中間部分でループから抜け出す必要があり、そのためループ自体は無限ループの形で書いておき、ループの途中で必要に応じてから途中脱出機能を使って脱出するというような場合を「無限ループの形」と称することもある。
明示的な無限ループの例
C言語での簡単な例を示す。
#include <stdio.h>
int main(void) {
unsigned int x = 0;
LoopEnter:
x += 1;
printf("%u\n", x);
goto LoopEnter;
return 0;
}
ここでのループは明らかで、goto文の実行後、ジャンプ先として指定されているループの入り口（ラベルLoopEnterが設定されている文x += 1;）まで戻り、無条件に同じ処理が繰り返される。ループを脱出する条件がないため、このプログラムは永久に終了せず、コンソール（標準出力）に値を出力し続ける。main()関数の末尾に到達することはなく、return文は到達不能コード（デッドコード）である。なお、コンソールの画面表示に使用されるバッファはある程度古いものから破棄されていくようになっているため、このプログラムを実行し続けてもせいぜいCPU時間を無駄遣いする程度で済み、メモリを使い果たしてしまうようなこともないが、標準出力をファイルにリダイレクトしていた場合、ストレージを食いつぶしてしまう可能性のある危険なコードになりうる。プログラムを終了するには、Ctrl+Cなどで強制終了するしかない。
ただし、ループの脱出条件（あるいは継続条件）を記述していても、コンピュータの振る舞いの特性を正しく理解せずに書かれた条件であった場合、無限ループを引き起こしてしまうことがある。
浮動小数点数の比較に伴うバグによる無限ループ
浮動小数点数の値をループの条件として評価に使用するとき、誤差を考慮せずに書かれたコードは、無限ループを引き起こしてしまうことがある。C言語での例を示す。
double x = 0.1;
while (x != 1.1) {
printf("x = %f\n", x);
x += 0.1;
}
このwhile文によるループは、期待通りに10回実行されるシステムもあるかもしれないが、終了しないシステムもあるかもしれない。ここでの問題は、ループの継続条件 (x != 1.1) が2つの浮動小数点数の厳密な一致をテストしていることである。多くのコンピュータの（2進の）浮動小数点の計算では 0.1 という値は正確に表現できず、誤差があるため、それを11回足した値がdouble型のリテラルの 1.1 の値と厳密に一致するとは限らない。
浮動小数点数を使うときには、等式でテストを行うと予想外に失敗する可能性があるため、不等式でテストすると安全である。例えば x が 1.1 と等しいかどうかをテストする代わりに (x < 1.1) や (x <= 1.0) でテストする。そのどちらでも、有限回数の繰り返しで脱出できる。
他に、ループ回数の上限を規定し、整数型のループカウンタを使うことで問題を回避する方法もある。
int i; /* 整数型のループインデックス */
double x = 0.1;
for (i = 0; i < 10; i++) {
printf("x = %f\n", x);
x += 0.1;
}
上記の例では、for文の条件式をi != 10と書くこともできるが、カウンタの初期値やインクリメントのステップ数によっては意図したとおりにループを脱出できなくなってしまうこともあるため、ループ継続条件に整数型の値を用いる場合であっても一般的に不等式を使うべきである。
数列の収束判定に伴う無限ループ
数値解析でも似たような状況が起きることがある。ある結果を求めるために、ある許容値に誤差が収まるまで繰り返す、という手続きを使うことがある。しかし、式に問題があって誤差がその許容値を下回ることが無ければ、結果として無限ループになる。
循環リストに起因する無限ループ
連結リストのようなデータ構造がループを持っているのに、それに対してリストに沿う繰り返しを実行してしまう、というようなパターンもある。データ構造のループの検出はちょっとした練習問題として知られている。簡単な例として、12、99、37の3つの整数値を格納した循環リストの中身をひとつずつリストに沿って出力する処理をすると「12、99、37、12、99、37、12、99、37、…」と無限に出力することになる。
3つの整数値を格納した循環リスト
複数のプログラム間で発生するループ
単体のプログラムでの無限ループは通常予測しやすいが、複数の要素が相互に影響しあったループは遥かに予測しにくい。ここで、リクエストを理解できない時にはいつもエラーメッセージを返すサーバについて考えてみる。明らかに、そのサーバには無限ループの可能性は全く無いが、そのようなサーバが2つ（AとB）あるとする。サーバAがサーバBから受け取ったメッセージを理解できなかった時、AはBにエラーを返す。Bがメッセージを理解できなかったらそのエラーをAに返し、そのエラーメッセージをAが理解できなければまた別のエラーメッセージを返し、これが永遠に繰り返される。このような事態のよくある例がメールループである。
デッドロックと無限ループ
複数のスレッドあるいはプロセスの間でメモリやファイルといった計算資源を共有するとき、データ競合や競合状態の問題を引き起こさないようにロックなどを使って共有資源へのアクセスを排他制御する必要があるが、ロック解除（アンロック）を忘れたりロックの順番を間違えたり、といったロジックミスがあるとデッドロックが発生してしまう。ロックを獲得できるまで待機する際、ループを回しながら何らかのフラグを監視しつつ待機するスピンロックという手法があるが、タイムアウト設定なしでロック獲得を待機する場合、デッドロックが発生してしまうと無限ループに陥ってしまう。ミューテックスのように、スリープおよびシグナル通知を使ってCPU時間を無駄遣いせず効率的に待機する方法もあるが、タイムアウト設定なしでデッドロックが発生してしまうと待機から脱出できず、広義の無限ループに陥ってしまう。
意図的な無限ループ
プログラムの都合上、意図的に無限ループを記述する場合もある。
組み込み環境とメインループ
OSのない組み込み環境では、電源投入後に呼ばれるメインルーチン（Cの場合はmain()関数）が呼び出し元に制御を返す必要はない。もしメインルーチンを抜けて制御を返してしまうと、以降は機器の制御ができなくなってしまい、意味がないからである。メインルーチンには無限ループ（メインループ）を記述し、その中で機器の状態を確認しながら、その状態に応じた分岐処理を実行していくことになる[2]。後述の古いゲーム専用機におけるゲームループもこの形態である。ただしメインループ以外で無限ループを作ると機器が応答不能になってしまうので、メインループ以外の無限ループは作らないように注意深く実装する必要がある。
イベント駆動とメインループ
Microsoft WindowsやmacOSに代表されるGUI（Graphical User Interface）環境では、アプリケーションソフトウェアはそれぞれ「メインループ」と呼ばれるイベントループ（メッセージループ）を持っている。アプリケーションはユーザーの入力操作イベントや画面再描画イベントの発生をループで待ちながら、応答を返したり描画処理を実行したりする。このスタイルをイベント駆動型プログラミングと呼ぶ。メインループは無限ループとせず、メインウィンドウのクローズボタンが押されるなどして発生するクローズイベント[3]や終了イベント[4]をループの脱出条件とし、メインループを抜けて後始末をしてからアプリケーションを終了するのが一般的な作法である。なお、OpenGLを使用した古典的なアプリケーションフレームワークの1つとしてGLUTがあるが、GLUTのglutMainLoop()は一度呼び出すと呼び出し元に返ってくることのない無限ループである[5]。GLUTアプリケーションはメインウィンドウのクローズボタンに応答して終了する仕組みにはなっているものの、標準Cライブラリのexit()関数で半強制終了し、リソースの後始末はOSに任せる形となる。
iOSやAndroidのようなモバイルOSでは通常手段でのアプリケーション終了の概念がなく、終了イベントも存在しないため、メインループは実質的に無限ループである。モバイルOS環境では、アプリケーションを終了するにはタスク（プロセス）を強制終了する必要がある。空きメモリが不足してきたときなど、OS側の判断によって強制終了されることもある。
ゲームループ
コンピュータゲームのプログラムは、1/60秒のようなごく短時間のフレーム内で、プレイヤーの入力操作への応答を処理しつつ画面描画を繰り返すリアルタイム処理方式のプログラミングスタイルであり、メインループは「ゲームループ」と呼ばれる[6]。ファミリーコンピュータのような古いゲーム専用機ではOSの概念がなく、電源を入れるとゲームプログラムがメモリにロードされてすぐに開始される流れとなるが、ゲームループは無限ループであり、ゲームを終了・再起動するには電源を落として再投入するかリセットボタンを押すしかなかった。のちにゲーム内容が複雑化し、リソースの効率的な管理や移植性向上のために汎用PCで使われるようなOSのサブセットがゲーム専用機にも導入されたが、ゲーム機がCDやDVDといったマルチメディアの再生機能も搭載するようになり、またインターネットで購入したゲームをストレージにダウンロード・インストールしてから起動できるようになると、ゲームを終了するのに電源ボタンやリセットボタンしか手段がないようでは使い勝手が悪いため、プログラム側からゲームループを終了してシステム画面に戻ることもできるようになっている[7]。
特異な例
不可能な終了条件
C言語での例：
unsigned int i;
for (i = 1; i > 0; i++)
{ /*loop code*/ }
これは永遠に動き続けるように見えるが、実際には i の値はいずれ unsigned int に格納できる最大値UINT_MAXに達し、その値に 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」のボタンと「キャンセル」のボタンのどちらも無かったため、そのダイアログボックスが表示されると必ずプログラム全体が停止してしまった[8]、ということである。
その他
一見無限ループに見えるが、例外あるいは大域ジャンプ（C言語ではsetjmp()関数とlongjmp()関数）や、ループの外から与えられた継続の呼び出しにより抜け出している、というパターンもある。サーバのように、本来無限に処理すべきである場合であればともかく、普通は、例外的ではない通常の処理の流れに例外処理を使うのは良くない作法とされる。たとえば、ファイルの終了が返されているにもかかわらず続きを読もうとしたのであれば例外を使うべきだが、単にファイルの終了に到達しただけならばそうすべきでないのが普通である。
ジャーゴンファイルに収録されている「The Story of Mel」には[9]、どう見ても無限ループに見えるが、オーバーフローにより隣のメモリが書き換わることを利用してジャンプ命令を自己書き換えし終了する、という技を見た、という話が紹介されている。
無限ループの検出
無限ループは、通常、プログラマが原因を突き止めることができると簡単に考える者もいる[要出典]ようだが、次のような例を考えればそうでないことがわかる（簡単のため、数値は無限に大きな値を扱えるものとする）。
- 入力として、正の整数であるnをとる。
- nが偶数の場合、nを2で割る。
- そうでなければ、nを3倍して、さらに1を加える。
- nが1なら終了する。
- ステップ2に戻る。
上記はごく簡単なプログラムであるが、たとえば最初のnを27とすると、途中でnは最大9232となる。そして、このプログラムがどんなnに対しても終了するか、あるいはあるnで始めると無限ループとなってしまうかという問題はコラッツの問題と呼ばれ、2014年時点で未解決の問題である。
理論上、プログラムが停止するのか動き続けるのかを「どんなプログラムに対しても」「有限の時間内で」「必ず決定できる」ことを全て満たす方法は無い。これは停止問題の決定不能性からの結論である。
日常会話での使用
「無限ループ」という言葉は他のプログラミング用語（例えばメモリリークやデッドロック等）と同様に非プログラマにも魅力的とされていて、プログラミングエラー以外の状況を表現するのにも使われている。例えば、コンピュータを使う上で一連の手順を求められ、最後には振り出しに戻ってしまうような状況である。特に、目的を達成するか回避するか、その手段がどちらも無いような場合[10]に使われることがある。自発的に何かを繰り返すようにすることを指して使われる[11]こともある。
その他の無限ループ
楽曲においても、無限ループは発生する。楽譜にてダル・セーニョやダ・カーポでジャンプする指示をしながら、曲の終わりを示すフィーネがないと、曲がいつまでたっても終わらなくなる。エリック・サティのピアノ小曲集『スポーツと気晴らし』の第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" の項目にある例では[12]「Cray-3はとても速くて、無限ループを2秒で実行できるくらいだって！」("The Cray-3 is so fast it can execute an infinite loop in under 2 seconds!")。
出典
- ^ 無限ループの英訳｜英辞郎 on the WEB
- ^ 組み込みソフトウェア工学 - 第６回 組み込みプログラム例題 | 神奈川工科大学
- ^ WM_CLOSE message (Winuser.h) - Win32 apps | Microsoft Learn
- ^ WM_QUIT message (Winuser.h) - Win32 apps | Microsoft Learn
- ^ 3.1 glutMainLoop
- ^ ゼロからはじめるXNAプログラミング - 更新と描画 | マイナビニュース
- ^ ゼロからはじめるXNAプログラミング - ゲームの起動とウィンドウ制御 | マイナビニュース
- ^ 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
関連項目
無限ループ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/07/23 09:22 UTC 版)
場合によっては無限にループする方がプログラムに適していることもあるし、何らかのエラーが発生するまでループするという場合もある。実際、イベント駆動型プログラム（サーバなど）はイベント制御ループを永遠に回り続け、プロセスが操作者によって終了させられたときだけループを停止する。 ただし一般には、無限ループはプログラミングのミスで発生する。すなわち、ループ終了条件がループ内で全く発生しないことが原因で意図しない無限ループとなる。
※この「無限ループ」の解説は、「制御構造」の解説の一部です。
「無限ループ」を含む「制御構造」の記事については、「制御構造」の概要を参照ください。
- 無限ループのページへのリンク
