なぜ、C言語にはgotoが必要なのか?

(注:以下の文章において、C言語とはC/C++をさすものとお考えください)


gotoは今から30年以上も前のダイクストラ先生による撲滅運動の
甲斐もあってかどうなのか、今日では良くないものの代名詞のように
なっている。良くないということの主な理由はプログラムの流れが
見えにくくなる、等のようなのだが、実際のところどの程度のものかは
よく分からない。C言語において、例えばループ構文を使わずにすべてを
gotoでまかなおうとするとこれはほとんど自明に、確かに大変である。
例えばfor文なら、

for (A;B;C) body

というものは、これを形式的に

A
_continue_for:
if (B) goto _break_for;
C
goto _continue_for;
_break_for:;

このように変換することが出来る。
bodyの中にbreakがあれば、goto _break_for;に、
continueがあれば goto _continue_for;に変換すれば良い。
そういうわけではあるが、for文一つにつき管理しなければならないラベルが2つ増えるので
やはりプログラマの負担が増えるだろう。
(さらにネストを考えると頭が痛い)


私自身、このような自明なケースをわざわざgotoを使って書くことはもちろん
皆無だし、大体の場合においてgotoを使うことはなるべく避ける。
具体的には、gotoを使わずとも綺麗に書ける表現があれば
そっちを使おうとなるべくは考えている。
しかし、gotoを完全に排斥しようとは考えていない。
というのも、どうやってもCの構文だけでは綺麗にかけないものが
存在するからである。しかも、その例というのが極めて恣意的な、
実例から大きく離れているような類のものでなくて、
至極頻繁に現れうるようなものだからである。
これはCの文法が制御構文のみに関しても十分な表現力を
もっていないからであり、以下にそれを示すことにする。


典型的な例、二重ループの脱出について。
具体的に、二次元配列の中に0以外のものが入っているか?
という問題を考える。これを適当にCで実装しようとすると、

int mat[HEIGHT][WIDTH];

...

bool found=false;
for (int y=0;y

...と、ここまで書いてはたと止まる。
二つのループを一気に抜けることが出来ないのである。
さて、ここでこれを解決するために4つほどの方法がある。
まず1つめ。

bool found=false;
bool flag=false;
for (int y=0;y

外側のループを抜けるためのフラグを用意しておくという方法。
この方法はややありがちではあるが、本来の処理を
歪め過ぎているように思われる。
ちなみにこの方法なら、今回のケースであれば、

bool found=false;
for (int y=0;y

これでもいいだろう。ただし、多少アドホックか。
次に2つめ。

bool found=false;
for (int y=0;y

今回のケースだと、別段breakする必要はないので、これでも可。
ただし、速めに0以外のものが現れる確率が高いようなデータを扱うときは
やや不利。さらに、応用範囲も狭いかもしれない。
単純な処理で、全部調べても対して時間のかからないようなときは
あえてこうするのもアリなのかもしれない。


3つめ。

bool search(int (*mat)[WIDTH])
{
  for (int y=0;y

関数にすれば、どこからでも脱出できる。
実はこの辺は今回の話の核心に絡むのだが、
そこは4つめを書いてから。
この方法はかなり綺麗なやり方だと思うが、
グローバルな関数を一つ増やす必要があるのと、
(本質的にはそんな必要はどこにもないのに)
コードが本筋と全然違う場所に配置されるのが
致命的に不利だと思う。


最後に4つめ。

bool found=false;
for (int y=0;y

単に飛びたいところにラベルを付けて、gotoするだけである。
おそらく4つの中で一番スマートな解法であると思う。
それがとりもなおさずC言語の構文の不備を表しているとも
言えるのだが…。
その1の後半で挙げた例、及び、その2はそれなりにすっきりであるが、
十分に一般的でないので、おいておくとすると、
・フラグを別に作って実行を制御、
・関数に分離
・gotoを使う
の3つに大分されるであろうか。


というわけで、ようやく核心である。
なぜこのようなことになってしまうのだろうか。
それは繰り返しになるが、やはりCの構文の欠陥による。


具体的な考察に入る。
Cのプログラムには、任意の地点に高々3の"暗黙的な"継続が存在する。
ここで継続(Continuation)とは、単にプログラムカウンタ程度の意味であるが、
まず、returnに対応する継続。これは関数の内部であればどこでも存在するし、
関数の中であればどこでもreturn;と記述することにより呼び出せる。
さらに、この継続は後の2つの継続とは違い(唯一つの)値をとることができる。
後の2つはbreakとcontinueに対する継続。これらはループ構文の中に存在する。
ループ構文の中で呼び出すことが出来、breakはそのループが終了した後の継続、
continueはそのループの先頭あたりの継続を指している。
(breakに対しては、switchの内部でも発生するが、ここでは無視ということで。)
つまるところ、C言語においては継続を自由に扱えない代わりに、
この3つ程度の継続を扱う能力を持っているといえる。
C言語において、実行されるプログラムはすべて関数内のコードなので、
基本的にreturnはいつでも利用できる。そういう意味でC言語においては
関数というものはスペシャルな存在であり、これを用いればネストしたループからも
どこからでも抜けられるということが分かる。
ところが、break、continueはループの中で定義され、もっとも内側のループに対して
呼び出される(…というよりも、break,continueのスコープ的に隠されてしまうとでも言うか)
ので、複数段のループを抜けることは不可能になってしまっている。
その点においては、ネスとされているものを見えるように名前付け、
すなわち、Javaでのラベル付きループ等のような解決法も存在する。
名前が付いていれば隠れたbreak,continueも呼び出せる。


そういう事情であるので、要するにこのような問題はC言語固有なのである。
もっともプログラム制御に対して柔軟なケース、継続を自由に扱える言語だと
この問題はやすやすと解決できる。
例えばSchemeだと、

(call/cc
  (lambda (k)
    (let loop ( (y 0))
      (if (< y HEIGHT)
        (begin
          (let loop ( (x 0))
            (if (< x WIDTH)
              (begin
                (if (<> 0 (array-ref mat x y))
                  (k #t))
                (loop (+ x 1)))))
          (lopp (+ y 1)))))))

このような感じになるだろうか。
(最近Scheme書いてないからなんか煩雑な感じになってしまったかも知れず)


Cでは継続というものが極めて簡易なケース(関数、ループ)でしか使えない
というのが、そもそもの問題だとすれば、もっと他に解決法は無いのだろうか?
実はCでも有る程度制限された形で継続というものを使える。
まず自明な例として、ラベルである。ラベルを定義するとそれを
継続とみなせなくも無く、gotoにより(同じ関数内からなら)どこからでも飛べる。
もうちょっと強力なものとしては、setjmp/longjmpがある。
setjmpにより、有る程度より継続に似たものが取得できる。
これを使って解決を図ったものを以下に示す。

jmp_buf cont;
bool found=false;
if (setjmp(cont)==0){
  for (int y=0;y

これはいささかやりすぎなような気もするが…。
さらにもう一つ解法を。
処理系限定になってしまうが、GCCでは関数内で関数が定義できる。
これを用いると実質的にどこでも継続を取ることが出来るようになる。
(…ネストは出来ないけど…)

int mat[HEIGHT][WIDTH];
...
bool search(){
  for (int y=0;y

(上のコードはどこかの関数内にかかれたものと想定)
これはかなり綺麗にまとまる。
というのも、関数からのreturnはいうなればC言語の健全な
継続利用だからであろう。
ただ、GCC限定というのと、さらにC限定(C++では無理)というのが
とても…というか、この上なく痛いので、あまり使いではないかもしれない。


というわけで、いろいろな方面から多重ループ脱出問題を考えてみたが、
皆さんいかがお感じになっただろうか。
私はここまで考えて、gotoを使おうと考える。

  • 蛇足

蛇足ではあるが、この問題を遅延評価パワーによって極めてすんなりと
記述することがHaskellには出来る。(計算量の考察は各自試みられよ。)

all (all (/=0)) mat

以上。