パスワードを忘れた? アカウント作成
15181249 journal
日記

route127の日記: 末尾再帰最適化? 5

日記 by route127

公式サイトがドメイン乗っ取りに遭っていたPerlタレこまれてもいた)だが、stackoverflowではHigher Order Perl(HOP)読んでPerl使ってみたhaskellの人に浅い再帰でビビり過ぎでは、みたいな問いが発されていた。
日本語コメントで、

とあったが末尾再帰最適化にはそんな副作用もあるのか。
その辺のメモリ保護の話はよく分からん。

そもそも末尾再帰最適化がよく分かってなくて培風館のCommonLISP本だかOn Lisp日本語訳)かで再帰による階乗

(defun fact (n)
  (cond ((< n 2) 1)
    (t (* n (fact (1- n))))))

を、

(defun fact2 (n &optional (acc 1))
  (cond ((< n 2) acc)
    (t (fact2 (1- n) (* n acc)))))

みたいな形に書き換えていたのを末尾再帰のようにとらえていた。

ただ最近ECMAScript6の処理系で末尾再帰最適化(末尾呼出し最適化)を仕様上サポートしているという記事を目にして、そこに

とあって混乱した。
関数を末尾再帰で書き下すことが末尾再帰最適化だと思い込んでいたが末尾再帰で関数を書くまでが人間の担当で、末尾再帰最適化は処理系の仕事なのか。

実際末尾再帰で書かれたフィボナッチ関数の、babelによるES6からES5へのトランスパイルを例を見ると再帰がwhileループに変換されていたりするが、この書き換えが末尾再帰最適化なのか。
再帰をループに書き換えることは原理的に可能だみたいなことは本に書いてあるのを読んだ覚えはあるがその具体的な手順まで解説されてはいなかった気がする。
ECMA-262 5.1版の邦訳とかECMAScript2020言語仕様をパラ見したけどそれらしい記述を見つけられなかった。
ただこれは世間では関数のトランポリン化として知られているようで、再帰関数をクロージャを返す関数に書き換えるものらしい。
値がスタックではなくクロージャ内部に保存されるからスタックは溢れないみたいな話なのか。

songmuの人が2010年にPerlでのフィボナッチ数計算高速化をやっていたが、その中でSub::Recursiveが出てきた。
metapan見ると

Recursive closures suffer from a severe memory leak.

という一文がある。
使い終わったクロージャはGCかかるからメモリはリークしないんじゃないかと思ってたがそうでもないのか。
そうするとトランポリン化も安泰ではないような気もするがまあなんにせよよく分かんねえな。

  • by Anonymous Coward on 2021年02月09日 0時23分 (#3974618)

    末尾再帰の最適化は関数コール命令をジャンプ命令に置き換える処理です

    C言語で書くと、たとえば

    int foo(int x){
          if (x==1)
                return x;
          else
                return x * foo(x-1);
    }

    これを

    int foo(int x){
            int ret = x;
    loop:
            if (x==1)
            return ret;
            else {
                    x = x-1;
                    ret *= x;
                    goto loop;
            }
    }

    と変換していることに相当します。

    原理的には、関数呼び出しがスタックを浪費するから、ジャンプ命令に置き換えましょう、って事です

    C言語のコンパイラ的には、最適化前のfoo()に対応するアセンブラと
    最適化後のfoo()に対応するアセンブラはかなり似たものになります。
    上記の例だと int ret = x; に対応する機械語は最適化前のfoo()にも含まれているので
    最適化による違いは goto の部分だけになります。

    ここに返信
    • by Anonymous Coward

      しれっといい加減なことを書くな。

      そのループに展開したものに相当するのは、

      int foo(int x) {
        loop(x, x);
      }
       
      int loop(int x, int ret) {
        if (x == 1) return ret;
        else return loop(x - 1, (x - 1) * ret);
      }

      元のコードは末尾再帰ではない。末尾再帰は呼び出した関数の戻り値がそのまま呼び出した側の関数の戻り値になる場合。元のコードでは"x * "が関数の呼び出し後に実行されるため、呼び出した関数の戻り値が来るまでxをスタックに残す必要があり、最適化はできない。

      元のコードの末尾再帰バージョンは、

      int foo(int x) {
        loop(x, 1);
      }
       

typodupeerror

未知のハックに一心不乱に取り組んだ結果、私は自然の法則を変えてしまった -- あるハッカー

読み込み中...