私が歌川です

@utgwkk が書いている

関数の再帰深度を制限するデコレータ / おまじない再び

技術

4ヶ月ぐらい前の話題だったけど、こういう感じで、関数の再帰深度を制限するデコレータは書けないのだろうか、とふと思った。@max_depth(10) なら同じ再帰呼び出し内で10回まで呼び出してよくて、10回を超えたらエラー。

@max_depth(10)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

fib(10) # => 55
fib(11) # => Error!!

なんかうまく書けないものかな、と試行錯誤してたら id:nonylene に教えてもらった。クロージャを使うと書ける。nonlocal を使うと modified のひとつ外のスコープの変数を参照できる。f の中でも結局wrapされた modified が呼び出されることになって、再帰呼び出しをするたびにどんどん count が大きくなる。

def max_depth(i):
    def d(f):
        count = 0
        def modified(*args):
            nonlocal count
            # print(args, count)
            count = count + 1
            if count <= i:
                result = f(*args)
                count -= 1
                return result
            else:
                count = 0
                raise Exception("Too many recursion!!!")
        return modified
    return d

@max_depth(10)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

フィボナッチ数とか計算しようとすると fib(10) までは計算できてお得。6行目のコメントを外すと引数と再帰深度の様子が見れます。

計算の様子を見る

(10,) 0
(9,) 1
(8,) 2
(7,) 3
(6,) 4
(5,) 5
(4,) 6
(3,) 7
(2,) 8
(1,) 9
(0,) 9
(1,) 8
(2,) 7
(1,) 8
(0,) 8
(3,) 6
(2,) 7
(1,) 8
(0,) 8
(1,) 7
(4,) 5
(3,) 6
(2,) 7
(1,) 8
(0,) 8
(1,) 7
(2,) 6
(1,) 7
(0,) 7
(5,) 4
(4,) 5
(3,) 6
(2,) 7
(1,) 8
(0,) 8
(1,) 7
(2,) 6
(1,) 7
(0,) 7
(3,) 5
(2,) 6
(1,) 7
(0,) 7
(1,) 6
(6,) 3
(5,) 4
(4,) 5
(3,) 6
(2,) 7
(1,) 8
(0,) 8
(1,) 7
(2,) 6
(1,) 7
(0,) 7
(3,) 5
(2,) 6
(1,) 7
(0,) 7
(1,) 6
(4,) 4
(3,) 5
(2,) 6
(1,) 7
(0,) 7
(1,) 6
(2,) 5
(1,) 6
(0,) 6
(7,) 2
(6,) 3
(5,) 4
(4,) 5
(3,) 6
(2,) 7
(1,) 8
(0,) 8
(1,) 7
(2,) 6
(1,) 7
(0,) 7
(3,) 5
(2,) 6
(1,) 7
(0,) 7
(1,) 6
(4,) 4
(3,) 5
(2,) 6
(1,) 7
(0,) 7
(1,) 6
(2,) 5
(1,) 6
(0,) 6
(5,) 3
(4,) 4
(3,) 5
(2,) 6
(1,) 7
(0,) 7
(1,) 6
(2,) 5
(1,) 6
(0,) 6
(3,) 4
(2,) 5
(1,) 6
(0,) 6
(1,) 5
(8,) 1
(7,) 2
(6,) 3
(5,) 4
(4,) 5
(3,) 6
(2,) 7
(1,) 8
(0,) 8
(1,) 7
(2,) 6
(1,) 7
(0,) 7
(3,) 5
(2,) 6
(1,) 7
(0,) 7
(1,) 6
(4,) 4
(3,) 5
(2,) 6
(1,) 7
(0,) 7
(1,) 6
(2,) 5
(1,) 6
(0,) 6
(5,) 3
(4,) 4
(3,) 5
(2,) 6
(1,) 7
(0,) 7
(1,) 6
(2,) 5
(1,) 6
(0,) 6
(3,) 4
(2,) 5
(1,) 6
(0,) 6
(1,) 5
(6,) 2
(5,) 3
(4,) 4
(3,) 5
(2,) 6
(1,) 7
(0,) 7
(1,) 6
(2,) 5
(1,) 6
(0,) 6
(3,) 4
(2,) 5
(1,) 6
(0,) 6
(1,) 5
(4,) 3
(3,) 4
(2,) 5
(1,) 6
(0,) 6
(1,) 5
(2,) 4
(1,) 5
(0,) 5
55

引数を取るデコレータみたいなのを書くのはちょっと難しくて、デコレータを作って返す関数、デコレータ、wrapされた関数、みたいな構造になるのが難しい。

デコレータは最初はおまじないに見えて、関数を取って関数を返す関数なのだけど、私はPythonを書き始めてからそれが分かるまでに少なくとも3年かかった。Flaskを使ってて @app.route('/') とか書くと思うけど、あれも最初はそういうおまじないだと思ってた。

デコレータの文法はシンタックスシュガーです。次の2つの関数定義は意味的に同じものです: 
def f(...):
    ...
f = staticmethod(f)

@staticmethod
def f(...):
    ...
用語集 — Python 3.8.6rc1 ドキュメント

おまじないの概念については昔いい記事を書いてたのでこっちも読んでください。高度に発展した科学技術が魔術と区別できない、みたいな感じで、原理が分からない間は不思議な力に見えるだろう、科学技術の全てを知らなくても生活はできるのでそれと同じようなものではないか、と受け止めている。それが気味悪いのであればやっていくしかない気もする。

blog.utgw.net

おまじない、というと、原義では不思議な力による云々らしいけれど、プログラミング言語におけるおまじないは、別に不思議な力でも神仏でもなくて、そういう機能がちゃんとあって、みたいな、ずっとおまじないのままにしておくのは何だかつらい感じがある。でもまぁ、正直なところ、おまじないがおまじないのままであっても、ある程度、ライブラリを読み込むおまじないとか、クラスっていう便利なかたまりが定義できるおまじないとか、そういう感じでも、ある程度は何とかなるかもしれないんだよなぁー、みたいな気分になっていて、うーん。

1年後も同じようなことについて話してた。

blog.utgw.net

入門するにあたって本質でないところ，たとえば少しやってくるとハマる可能性があるようなところは，入門の段階でやるのはまだ早いのではないか？？ と思った． 我々が使いたいのはその言語とかライブラリであって，現状はこうすればいいという道筋があってやっているし，いちおうの言語の入門もある． 言語の入門では，言語が使えるようになることが第一であって，言語の詳細を知るのは第二なのではなかろうかと思う．