while リスト、popメソッドの使い方

Question

前提・実現したいこと

pythonの勉強本でわからないことがあったので質問させてください。
「ゼロから作るDeep Learning3 フレームワーク編」で質問です。
https://zenn.dev/koki0702/books/a2f1689cb67723433e22/viewer/4c31b5b7c1786037df9c
読んだことのある人教えてください。

該当のソースコード

class Variable:
    def __init__(self, data):
        self.data = data
        self.grad = None
        self.creator = None

    def set_creator(self, func):
        self.creator = func

    def backward(self):
        f = self.creator
        if f is not None:
            x = f.input
            x.grad = f.backward(self.grad)
            x.backward()

をループを使った実装に変更して下記のよう(目的はメモリの節約)に変えるらしいのです。

class Variable:
    def __init__(self, data):
        self.data = data
        self.grad = None
        self.creator = None

    def set_creator(self, func):
        self.creator = func

    def backward(self):
        funcs = [self.creator]
        while funcs:
            f = funcs.pop()  # 関数を取得
            x, y = f.input, f.output  # 関数の入出力を取得
            x.grad = f.backward(y.grad)  # backwardメソッドを呼ぶ

            if x.creator is not None:
                funcs.append(x.creator)  # 1つ前の関数をリストに追加

わからないこと

while func: はどういう意味ですか。
funcsはリストです。while 変数 <5なら
変数が5以下の時だけループするとわかるのですが、whileリストだとリストがどうなるかよくわらないです。
while 変数<5なら変数 +=1として
送っていきますが、while リストの場合送っていくこともしているように見えないのが疑問です。
もう一つ、このコードでpopメソッドとappendメソッドがどういう役割を果たしているのかもわからないです。
popメソッドとappendメソッド、それぞれ単体での意味は分かります。

わかりやすい説明いただけると助かります。よろしくお願いします。

Answer 1

他の方の捕捉として回答します。
スタックに関する言及がされてなさそうだったので、

このコードでpopメソッドとappendメソッドがどういう役割を果たしているのかもわからないです。

「再帰」から「ループ」へと実装方式の切り替えにおける、
再帰 関数呼び出しでの「スタックの役割」を果たします。

• 前提: データ構造としてのスタック

　FILO (first-in-last-out) の PUSH と POP が ​list の append, pop

• 「関数」呼び出し時のコールスタック, スタックフレーム
• 「再帰」呼び出し時のスタック操作を、リストとループ処理で模倣する。

関数やメソッドを呼び出した時に、
処理系内部でどのようなデータの操作が行われているかが、理解の鍵です。

関数呼び出しには通常、引き数と戻り値があり、
呼び出し毎に独自のローカル変数の領域を持ちます。

Python では、これを Frame オブジェクトに纏めて、

• stack (積み上げる) の用語通り、関数呼び出し時に

　関数の戻り先の情報を積み上げていきます。(append)

• 関数の実行が終わった時(return/raise もしくは終端に到達)に

　スタックの一番上を取り除きます (pop)

質問のコードでは、スタックに入れる内容は、独自実装なので異なりますが、
funcs のリストがこのスタックに該当します。

嚙み砕いて説明すると、
再帰呼び出しの時に処理系内部で行われてるような「スタック操作」を、
独自にリストとループ処理で行う事で、再帰呼び出しを模倣 しています。 出来るようになります。

追記1:

• 現状のコードでは、スタックは直ぐに消化されているので、

　再帰呼び出しを模倣しているわけではありません。

• 関数内での関数呼び出しを実装する時にスタックが必要になります。

追記2: 「再帰」から「ループ」へと実装方式の切り替えに関して

「連結リスト」のデータ構造の理解が学習のヒントです。

• 再帰では、引数を変えて同じ関数を実行します。
• ループで、引数を変えて同じ処理を実行に書き換え可能。

class Node:
    """
    Sample data:
    +---------+--------+  +---------+--------+  +---------+------------+
    | data: 1 | next: --> | data: 2 | next: --> | data: 3 | next: None |
    +---------+--------+  +---------+--------+  +---------+------------+
    """
    def __init__(self, data, next_node=None):
        self.data = data
        self.next = next_node

    def __repr__(self):
        return f"<Node data={self.data}>"

def search_recursive(node, value):
    if node.data == value:
        return node
    else:
        return search_recursive(node.next, value)

def search_loop(node, value):
    while node:
        if node.data == value:
            return node
        node = node.next

if __name__ == '__main__':
    top = Node(1, Node(2, Node(3, None)))
    print(search_recursive(top, 2))
    print(search_loop(top, 2))

Comments

[tomomonX]

補足ありがとうございます。まだ初心者でちょっと難しそうなので、まずはwhileの抜け出し方を理解してからスタックの役割しっかりしたいと思います。

[teamikl]

すみません、一点勘違いがありました。

- python 実装での backward() の再帰構造 ← 記事の説明はこちら
- 記事で実装してる処理系上の関数での再帰 ← 私の説明で想定してた

pop/append の説明としては「スタック」が適切だと思いますが、
再帰呼び出しを模倣～は、ミスリードになるかもしれないので
「連結リストの走査」がコードの説明としては適切だったかな。
後で、回答文も訂正します。

----
funcs リストの内容が蓄積されないなら、スタックとしての役割は薄いので
問題のコード（リンク参考元のコード）の実装は、
pop/append は省いて以下の様に書けたりしませんか。
※コメント内なので、インデントは全角スペースを使ってます。

func = self.creator
while func:
　x, y = func.input, func.output
　x.grad = func.backward(y.grad)
　func = x.creator

[tomomonX]

ご丁寧に説明いただきありがとうございます。大変参考になりました。じっくり考えてやっと納得行きました。

Answer 2

読んだ事がないので、このクラスが何をしているか、また変数の中身が何であるかは分かりませんが、これを見て分かる部分だけ。

while funcs:はどういう意味ですか。

whileは条件式（今回の場合funcs）が真である間ループし、偽であればループから抜けます。
で、funcsはリストです。
pythonではbool型以外のオブジェクトも真偽値で判定できます。
数値型の0や要素の無い文字列、リスト、タプル、辞書等は偽
それ以外は真です。
なので、今回の場合はfuncsというリストに要素がある（真）限りループとなります。
ループ内でfuncs.pop()しているので、backward()が呼ばれた時はfuncsに要素がいくつかあって段々減っていって最後は要素が無くなってループを抜けるという動作と思います。

popとappendの役割は

• pop()とappend()単体の意味が分かる
• 変更前のコードが理解できている
• 説明通り変更目的はメモリ節約であり、変更前後で結果は変わらない
• while リスト:の意味を理解した

なら、コードを追えば分かると思います。

Comments

[tomomonX]

ありがとうございます。このコードの意味が分からなくなってしまったのは、
pop()はリストの末尾を削除し、append（）は末尾に追加するため、消して加えてを繰り返してしまうのではないかと思いました。そのため、whileを抜け出すにはfuncsがfalseになるのではなく、１番目,2番目とリストの右側へ移行していくものだと勘違いしてしまいました。消して増えてで、どうループから抜け出せるのかはいまだ疑問ですが、while funcsが偽（空）でループから抜け出せるという昨日まで想像だったことが合っているということを知れただけで１歩進歩で来た気がします。

[udon-ken]

> 消して増えてで、どうループから抜け出せるのかはいまだ疑問ですが、

無条件にappendしているならそういう疑問になるでしょうけど・・・append()については、
if x.creator is not None:
funcs.append(x.creator)
となっていて、条件に適合した時にしか行われません。
逆にpop()は無条件に行われます。
つまり、ループごとに100%の確率で要素が削除されて、100%未満の確率で要素が追加されるのですから、いつかは要素が全部なくなり、ループから抜けるという事です。

[tomomonX]

丁寧に説明いただき、ありがとうございます。やっと理解できました。

Answer 3

こちらの記事に参考になる情報が載っています。

[Python] listが空かどうか判定する方法2つ

pythonでは、空配列([])を条件式に入れるとFalseを返すようです。
つまり、funcsが空配列になったら、条件式がFalseとなり、while文から抜け出すということです。

popやappendは、funcsという配列変数の中にある値の数を増減させることで、結果的に、while文が終わるか終わらないかに影響を与えていると考えることができます。

Comments

[tomomonX]

ありがとうございます。listを空にするのは想像（リストの一つ目から一つずつ右にずらす）と違っていたので、間違った考えのままではなく、正していただき助かりました。popはリストの末尾が削除され、その要素が取得され、appendは末尾に付け加えると考えています。
たとえばfunc=[1,2,3]の時、x=funcs.pop()でfuncは[1,2]となりますが、そのあとに、append(x.creator)とした場合、func=[1,2,x.creator]になる。
→whileで1周して、popでfunc=[1,2]→appendで[1,2,x.creator]
→whileで1周して、popでfunc=[1,2]→appendで[1,2,x.creator]
→・・
といった感じになり、whileを永遠に抜け出せなくなる気がしたのですが、考え方のどこが間違っていますか。

Answer 4

whileについて

whileはwhileに続く式の真偽値判定を行い、真（True）であればブロック内のループを1回実行し、偽（False）であればループを実行せず次の処理へ進みます。

この式はTrue/Falseを返すような式以外にも、オブジェクトそのものを判定対象にできます。
公式ドキュメントから引用すると、

どのようなオブジェクトでも真理値として判定でき、 if や while の条件あるいは以下のブール演算の被演算子として使えます。

オブジェクトは、デフォルトでは真と判定されます。ただしそのクラスが __bool__() メソッドを定義していて、それが False を返す場合、または __len__() メソッドを定義していて、それが 0 を返す場合は偽と判定されます。

https://docs.python.org/ja/3/library/stdtypes.html#index-1

となっています。funcはリストなのは理解していますね。リストは__len__()が定義されており、リストの要素数を返します。それが0になったら偽と判断されるので、リストが空になったらwhileループから抜けることができるわけです。

関数のpop, appendについて

再帰の実装では、creatorから取り出した1つ前のVariableのbackward関数を同関数内でどんどん呼んでいきます。これが再帰処理になります。
ループの実装では、同じくcreatorから関数を取り出しますが、それをfuncsという配列の中にいったん入れます。
ループの最初でfuncs配列から関数を取り出し、再帰の実装と同じようにFunction側のbackward関数を実行して1つ前のVariableを処理します。
その1つ前のVariable x にcreatorが存在する（すなわち、まだbackward可能）場合、x.creatorをfuncs配列に追加します。ここでループが1回転終了します。
whileに戻ってループを実行する判定をもう一度行います。まだbackward可能な場合、funsにさっき追加した x.creator が入っているのでそれを取り出してまた同じように処理します。

最終的にVariableが終端（というか先頭？）に達するとfuncsにcreatorをappendせずループが終了するので、その時点でfuncsが空になり、先ほど説明した通り、空のリストは真偽値判定で偽となりループが終了します。
こうすることで、Variable.backwardメソッドの実行が1回で済むようになっています。

Comments

[tomomonX]

回答ありがとうございます。popメソッドでせっかくリストのlenを減らしても、appendメソッドで増やしたらpopとappendが喧嘩をしてwhileから抜け出せなくなるような気がするのですが、解釈間違っていますか。

[hope_mucci]

ちゃんと書籍の中身を理解していれば抜け出せなくなるようなことにはならないのは理解できるはずですが...

popで減る要素も、appendで増える要素も1つずつです。
Variableが持つ導関数Creatorは1つなので、1つ前の導関数をpopし、次のVariableの導関数をappend
するわけで、while中の計算が1周するとfuncsの中身は1つ減って1つふえるので結果1つだけになります。
チェインルールの終端のVariableはcreatorを持たないので、一番最後は導関数をappendできません。
よって、最終的にfuncsの中身は空になることが保証されます。

[tomomonX]

ご説明ありがとうございます。
昨日、どんなに考えても分からなかったのですが、1晩立つと不思議と理解出来ました。リストの中身が複数だったりcreatorが複数の複雑なことを考えてしまっていましたがよくよく考えると本の序章で関数が並列でないシンプルな形である前提でした。解決に導いていただきありがとうございました。