大域脱出 (Non Local Exits) について調べた

Rubyのtimeout.timeoutのソースコードに、Kernel.catch が使われていた。これはrubyで大域脱出するために使用されるメソッドである。

大域脱出について(恥ずかしながら)あまりよく知らなかったのでまとめた。

大域脱出とは

構造化プログラミングの考え方では、 goto 文のように、ブロック構造を無視して制御を移すのはよくないとされる。しかし、アルゴリズムによってはそういう書き方をしたい時もある。例えば、多くの言語では、 return 文を実行すると、繰り返しブロックの中であっても直ちに関数の実行を終了して呼び出し元へ戻る。

大域脱出(Non-local exits)は、それを一般化して、複数回の繰り返しや関数呼び出しが重なっていても、すべて終了して最初に設定したところまで戻る。

⏫プログラミングドキュメント、制御構文より

Pythonの場合

大域脱出は言語レベルでサポートされていない。
実装方法は例えば以下が考えられる。

(1) for-else構文を使用する

for i in range(3):
    print("i = {}".format(i))
    for j in range(3):
        print("    j = {}".format(j))
        if (i, j) == (1, 2):
            break
    else:
        # for loopがbreakされることなく最後までiterateされた場合のみここが実行される
        continue
    break

(2) ループの箇所を関数に切り出し、大域脱出の代わりにreturnする

def iterate_until(x, y):
    for i in range(3):
        print("i = {}".format(i))
        for j in range(3):
            print("    j = {}".format(j))
            if (i, j) == (x, y):
                return

iterate_until(2, 3)

(出力はいずれも以下)

i = 0
    j = 0
    j = 1
    j = 2
i = 1
    j = 0
    j = 1
    j = 2

Rubyの場合

Rubyの場合、Kernel.#catchを用いて、catch-throwで大域脱出を行うことができる。
(例外処理のbegin-rescueとは別のもの。Javaだと、try-catchで例外処理なので混合しないこと)

ref. module function Kernel.#catch。
https://docs.ruby-lang.org/ja/latest/method/Kernel/m/catch.html

result = catch do |tag|
  for i in 1..2
    for j in 1..2
      for k in 1..2
        throw tag, k
      end
    end
  end
end

p result #=> 1

なお、大域脱出は複数のメソッドコールを跨ぐことができる。

他の言語の場合

深ぼって調べていないが、ざっと関連記事のリンクを貼っておく。

• Javaは大域脱出の言語レベルでサポートされている(?)。ref. https://shoutm.hatenablog.com/entry/2013/01/02/205328
• Goは大域脱出の言語レベルでサポートされておらず(?)、panicを用いて大域脱出をするらしい。