無限ループ

**無限ループ**（むげんループ、）は、コンピュータプログラムにおいて終了条件が成立しないため処理が反復実行され続けて停止しない実行形態である。とも呼ばれる。

無限ループは常時動作する処理を目的として意図的に利用される場合がある一方、設計や実装の誤りにより発生した場合には処理の停止不能や計算資源の継続的消費を引き起こす特徴を持つ。

## ループ
無限ループは通常、意図された待機や反復ではなく、異常（バグ）などによって停止できない状態を指して用いられる。また、構文上無限ループとして記述し、途中で脱出することを前提とした形式を「無限ループの形」と呼ぶことがある。

### 明示的な無限ループの例
C言語での簡単な例を示す。

```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時間を無駄遣いする程度で済み、メモリを使い果たしてしまうようなこともないが、標準出力をファイルにリダイレクトしていた場合、ストレージを食いつぶしてしまう可能性のある危険なコードになりうる。プログラムを終了するには、+などで強制終了するしかない。

ただし、ループの脱出条件（あるいは継続条件）を記述していても、コンピュータの振る舞いの特性を正しく理解せずに書かれた条件であった場合、無限ループを引き起こしてしまうことがある。

### 浮動小数点数の比較に伴うバグによる無限ループ
浮動小数点数の値をループの条件として評価に使用するとき、誤差を考慮せずに書かれたコードは、無限ループを引き起こしてしまうことがある。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回足した値が型のリテラルの `1.1` の値と厳密に一致するとは限らない。

浮動小数点数を使うときには、等式でテストを行うと予想外に失敗する可能性があるため、不等式でテストすると安全である。例えば `x` が `1.1` と等しいかどうかをテストする代わりに `(x < 1.1)` や `(x <= 1.0)` でテストする。そのどちらでも、有限回数の繰り返しで脱出できる。

他に、ループ回数の上限を規定し、整数型のループカウンタを使うことで問題を回避する方法もある。

```c
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()`関数）が呼び出し元に制御を返す必要はない。もしメインルーチンを抜けて制御を返してしまうと、以降は機器の制御ができなくなってしまい、意味がないからである。メインルーチンには無限ループ（メインループ）を記述し、その中で機器の状態を確認しながら、その状態に応じた分岐処理を実行していくことになる。後述の古いゲーム専用機におけるゲームループもこの形態である。ただしメインループ以外で無限ループを作ると機器が応答不能になってしまうので、メインループ以外の無限ループは作らないように注意深く実装する必要がある。

### イベント駆動とメインループ
Microsoft WindowsやmacOSに代表されるGUI（Graphical User Interface）環境では、アプリケーションソフトウェアはそれぞれ「メインループ」と呼ばれるイベントループ（メッセージループ）を持っている。アプリケーションはユーザーの入力操作イベントや画面再描画イベントの発生をループで待ちながら、応答を返したり描画処理を実行したりする。このスタイルをイベント駆動型プログラミングと呼ぶ。メインループは無限ループとせず、メインウィンドウのクローズボタンが押されるなどして発生するクローズイベントや終了イベントをループの脱出条件とし、メインループを抜けて後始末をしてからアプリケーションを終了するのが一般的な作法である。なお、OpenGLを使用した古典的なアプリケーションフレームワークの1つとしてGLUTがあるが、GLUTの`glutMainLoop()`は一度呼び出すと呼び出し元に返ってくることのない無限ループである。GLUTアプリケーションはメインウィンドウのクローズボタンに応答して終了する仕組みにはなっているものの、標準Cライブラリの`exit()`関数で半強制終了し、リソースの後始末はOSに任せる形となる。

iOSやAndroidのようなモバイルOSでは通常手段でのアプリケーション終了の概念がなく、終了イベントも存在しないため、メインループは実質的に無限ループである。モバイルOS環境では、アプリケーションを終了するにはタスク（プロセス）を強制終了する必要がある。空きメモリが不足してきたときなど、OS側の判断によって強制終了されることもある。

### ゲームループ
コンピュータゲームのプログラムは、1/60秒のようなごく短時間のフレーム内で、プレイヤーの入力操作への応答を処理しつつ画面描画を繰り返すリアルタイム処理方式のプログラミングスタイルであり、メインループは「ゲームループ」と呼ばれる。ファミリーコンピュータのような古いゲーム専用機ではOSの概念がなく、電源を入れるとゲームプログラムがメモリにロードされ（あるいはロードすら無く、ROMを直接実行し）てすぐに開始される流れとなるが、ゲームループは無限ループであり、ゲームを終了・再起動するには電源を落として再投入するかリセットボタンを押すしかなかった。のちにゲーム内容が複雑化し、リソースの効率的な管理や移植性向上のために汎用PCで使われるようなOSのサブセットがゲーム専用機にも導入されたが、ゲーム機がCDやDVDといったマルチメディアの再生機能も搭載するようになり、またインターネットで購入したゲームをストレージにダウンロード・インストールしてから起動できるようになると、ゲームを終了するのに電源ボタンやリセットボタンしか手段がないようでは使い勝手が悪いため、プログラム側からゲームループを終了してシステム画面に戻ることもできるようになっている。

## 専用構文
無限ループは脱出条件にならないループを書くことにより実現することもできるが、多くのプログラミング言語では専用構文を備えている。言語の処理系や静的検査は無限ループとなりうる記述に警告を出すことができるが、意図的に書いた脱出条件が無いループと意図しない無限ループを区別できず意図の有無にかかわらず常に警告をだしてしまう。専用構文を用いることで意図した無限ループであることを言語の処理系や静的検査につたえ、正常にもかかわらず警告が出たままという状態を防ぐことができる

### C言語系統の例
C/C++/Java/C# といった共通のfor文を使う言語で使用できる。
```c++
for(;;)
{
}
```


### Smalltalkの例

```smalltalk
[
] repeat.
```


## 特異な例
### 不可能な終了条件
C言語での例：

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

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

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

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

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

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


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


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


```ada
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」のボタンと「キャンセル」のボタンのどちらも無かったため、そのダイアログボックスが表示されると必ずプログラム全体が停止してしまった、ということである。

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

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

## 無限ループの検出
無限ループは、ようだが、次のような例を考えればそうでないことがわかる（簡単のため、数値は無限に大きな値を扱えるものとする）。

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

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

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

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

## その他の無限ループ
楽曲においても、無限ループは発生する。楽譜にてダル・セーニョやダ・カーポでジャンプする指示をしながら、曲の終わりを示すフィーネがないと、曲がいつまでたっても終わらなくなる。エリック・サティのピアノ小曲集『スポーツと気晴らし』の第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" の項目にある例では「Cray-3はとても速くて、無限ループを2秒で実行できるくらいだって！」("The Cray-3 is so fast it can execute an infinite loop in under 2 seconds!")。

## 出典


## 関連項目
* 再帰
* ウロボロス
* 停止性問題の決定不能性
* デッドロック
* 循環論法
* 無限後退
* ミニマル・ミュージック
* 無限アラート事件 - 無限ループを組み込んでアラートを際限なく表示するプログラムが実行されるウェブページへのURlを掲示板に投稿したとして複数人が書類送検・補導された日本の刑事事件