ビジターはフラクタルの森を保全する特命調査員
このワークシートはMath by Codeの一部です。
前回は探索3兄弟と題してイテレタ、インタプリタを学んだ。
イテレタという共通探索仕様パタンはいろんな言語のモジュールで普通にある。
インタプリタという通訳一式パタンは電卓やDSLドメイン専用ミニ言語として普通に使われている。
今回学ぶビジターは、ファイルシステムというスマホ・PCで普通に使われているものが舞台になる。
そもそも、ファイルシステム自体が、コンポジットCompositeパタンによるものなので、
さきにコンポジットパタンから軽い見ていこう。
すでにあるものを学ぶ時って、どうしても新しい感動がないので、数学との関係を考えながら、
楽しく学んでいこう。
１．コンポジットはフラクタルイメージ
＜コンポジットはフラクタル＞
フラクタルというと、
シダの葉の拡大図や巻貝などのらせんのイメージで語られます。
自己相似と言ったりもしますね。
部分を拡大したらさっきの全体と同じ模様が出てくる。
つまり、部分と全体が同じ形になる。
だから、自己相似というネーミングがあるのですね。
コンポジットというパタンはまさに自己相似です。
部分も全体も同じアクセスができる要素の集合体のことですね。
GOF本では、
コンポジット：
部分ー全体階層を表現するために、オブジェクトを木構造に組み立てる。このパタンを使うと、ユーザーはオブジェクト単体と複数オブジェクトの合成物を一様に扱えるようになる。
とあります。
木構造はノードの下にノードがいくつに分かれます。いつかはノードはリーフという端末要素にいきつきます。この枝分かれ構造が木構造ですね。
一番上のノードをルート、木の根っこというのだから、木をさかさまにかくのですね。
木構造をBNFでかいてみよう。
＜木＞ ::= ＜要素＞ | ＜要素＞ ＜木＞
＜要素＞::= "(" <木> ")" | ＜末端＞
この末端がファイル、要素がフォルダ、木がファイルシステムと読み替えもできます。
＜木＞の定義に＜木＞で出てきました。自己参照ですね。
この要素ｘsに対するメソッドを考えてみよう。
要素xsの名前を表示する。getName(xs)
要素xsに名前をｙに変更する。reName(xs, y)
要素xsに要素ｘを追加する。add(x)
要素xsから要素ｘを取り除く。remove(x)
要素xsの名前を再帰的に表示する。show_tree(xs)
ｘｓがルートでｘはその直下という必要はありません。
どの階層でも上がｘｓその真下がｘです。
追加のときだけはフォルダ、ノードでないと下に追加はできないですが、基本ｘはノードでもリーフでも
同じ処理方法で書けます。
コンポジットパタンの実装例を見てみよう。
＜ファイル探索・操作の実装＞
# ==========================================
# 【共通規格】ファイルもフォルダも等価に扱うための抽象クラス
# ==========================================
class FileSystemNode:
"""【要素】ノード（フォルダ）でもリーフ（ファイル）でも同じ方法で扱える共通仕様"""
def __init__(self, name):
self.name = name
def getName(self):
return self.name
def reName(self, new_name):
self.name = new_name
def add(self, node):
raise NotImplementedError("端末要素（ファイル）の下に、要素を追加することはできません。")
def remove(self, node):
raise NotImplementedError("端末要素（ファイル）から、要素を削除することはできません。")
def show_tree(self, depth=0):
"""ツリー構造を画面に表示するための共通メソッド"""
raise NotImplementedError()
# ==========================================
# 【末端（リーフ）】中身が「ファイル」のクラス
# ==========================================
class FileLeaf(FileSystemNode):
"""＜末端＞を表す具体的なクラス"""
def __init__(self, name, size):
super().__init__(name)
self.size = size # ファイル固有の属性
def show_tree(self, depth=0):
# インデントをつけてファイル名を表示
print(" " * depth + f"・{self.getName()} ({self.size}KB)")
# ==========================================
# 【複合体（コンポジット）】中身が「フォルダ」のクラス
# ==========================================
class FolderComposite(FileSystemNode):
"""＜木＞を表す具体的なクラス。自分の中にさらに＜要素＞の集合体を持つ"""
def __init__(self, name):
super().__init__(name)
self.children = [] # 【自己参照の受け皿】FileSystemNode（ファイルかフォルダ）を格納するリスト
def add(self, node: FileSystemNode):
"""xsが末端でなければ、xを追加する"""
self.children.append(node)
return self # メソッドチェーン（連続追加）ができるように自分を返す
def remove(self, node: FileSystemNode):
"""xsにxがあれば、xを取り除く（どの階層であっても、見つけたら削除）"""
if node in self.children:
self.children.remove(node)
return True
# 自分の直下になければ、さらに下層のフォルダ（自己相似）に「xを持ってる？」と探索をお願いする
for child in self.children:
if isinstance(child, FolderComposite):
if child.remove(node):
return True
return False
def show_tree(self, depth=0):
"""フォルダの中身を再帰的に全件走査して表示する（フラクタル展開）"""
print(" " * depth + f"□{self.getName()}/")
for child in self.children:
# 相手がファイルかフォルダかを一切気にせず、同じ「show_tree」を呼び出すだけ！
child.show_tree(depth + 1)
# ==========================================
# 【実行・ユーザー側のコード】部分と全体を一様に操作する
# ==========================================
print("コンポジットアルゴリズムスタート：\n")
# 1. PCでおなじみの木構造（ファイルシステム）を構築
root_dir = FolderComposite("デザインパタン")
gener_dir = FolderComposite("生成系")
behav_dir = FolderComposite("振る舞い系")
# 端末要素（ファイル）の作成
file_a = FileLeaf("f a c t o r y .py", 12)
file_b = FileLeaf("m e d i a t o r .py", 45)
file_c = FileLeaf("i t e r a t o r .py", 8)
# フォルダ構造へ追加（どの階層でも、上がxs、真下がxの関係）
root_dir.add(gener_dir).add(behav_dir)
gener_dir.add(file_a)
behav_dir.add(file_b).add(file_c)
print("--- 1. 最初に構築したツリー構造を表示 ---")
root_dir.show_tree()
print("\n--- 2. 名前の変更（reName）を『ファイル』と『フォルダ』に一様に適用 ---")
# ユーザーは相手がリーフかノードかを意識せず、全く同じメソッドを叩ける
gener_dir.reName("工場系") # フォルダの名前変更
file_c.reName("List Access Interface .py") # ファイルの名前変更
root_dir.show_tree()
print("\n--- 3. 要素の削除（remove）を発動 ---")
print(f"削除実行： {file_c.getName()} を消去します。")
root_dir.remove(file_c) # ルートフォルダに丸投げすれば、下層まで勝手に探して消してくれる
root_dir.show_tree()
[OUT]
コンポジットアルゴリズムスタート：
--- 1. 最初に構築したツリー構造を表示 ---
□デザインパタン/
□生成系/
・f a c t o r y .py (12KB)
□振る舞い系/
・m e d i a t o r .py (45KB)
・i t e r a t o r .py (8KB)
--- 2. 名前の変更（reName）を『ファイル』と『フォルダ』に一様に適用 ---
□デザインパタン/
□工場系/
・f a c t o r y .py (12KB)
□振る舞い系/
・m e d i a t o r .py (45KB)
・List Access Interface .py (8KB)
--- 3. 要素の削除（remove）を発動 ---
削除実行： List Access Interface .py を消去します。
□デザインパタン/
□工場系/
・f a c t o r y .py (12KB)
□振る舞い系/
・m e d i a t o r .py (45KB)２。ビジターは特命工作員
＜ビジターは特命工作員＞
コンポジットの実装としてのファイルシステムを思い出してください。
名前の表示と変更、要素の追加と削除はできました。
show_treeはかなり役立ちましたが、表示して終わりでした。
そこで、VISITORパタンの登場です。
GOF本では、
あるオブジェクト集合体の構造に変更を加えないで、オブジェクトの要素に新しいオペレーションを定義できるようにする。
ようするに、ビジターは会員ではないお客様という意味で使われもします。
デザインパタンでは、全然意味がちがいます。
特命工作員をコンポジットの森に突入させるということですね。
たとえば現実的にありうる要望としては、
ファイルサイズの大きいファイルやフォルダを見つけたいことです。
そこで、
特命工作員を作りましょう。
工作員Aはフォルダごとに合計サイズを計算して表示します。
工作員Bはサイズの大きい順にファイルのランキングを表示します。
しかし、特命工作員のインターフェースは共通であり、
ファイル調査するvisit_file
フォルダ調査するvisit_folder
結果報告するshow_result
この３つです。
コンポジットの森は次のようになっているとしましょう。
root_dir = FolderComposite("デザインパタン")
gener_dir = FolderComposite("生成系")
behav_dir = FolderComposite("振る舞い系")
file_a = FileLeaf("f a c t o r y .py", 12)
file_b = FileLeaf("m e d i a t o r .py", 45)
file_c = FileLeaf("i t e r a t o r .py", 8)
file_af = FileLeaf("f a c t o r y Fat .py", 123)
file_bf = FileLeaf("m e d i a t o r Fat .py", 456)
file_cf = FileLeaf("i t e r a t o r Fat .py", 89)
root_dir.add(gener_dir).add(behav_dir)
gener_dir.add(file_a).add(file_af)
behav_dir.add(file_b).add(file_c).add(file_bf).add(file_cf)
必要ならば、フォルダアイコンに変わり□を使います。
＜特命工作員を実装する＞
泥棒が外から侵入するわけではないので、システムに入れるかどうかの認証が必要です。
それが、窓口です。コンポジットの森の要素にはもれなくacceptメソッドをつけます。
そして、受け入れたらビジターに教える情報と手順を決めておきます。
特命工作員が侵入して、まごまごしているようでは困りますからね。
また、フォルダ探索のときは、フォルダ全体の特性を調べるには、帰りがけに集計が必要になります。
ファイル単体の調査だけなら不要なのですが、インターフェースを統一するためには、工作員は
visit_folder_postもつけてあげましょう。必要なら実装します。
# ==========================================
# Composite構造＋窓口
# ==========================================
class FileSystemNode:
"""共通規格：名前の管理と、工作員を受け入れる窓口（accept）を定義"""
def __init__(self, name):
self.name = name
def getName(self):
return self.name
def accept(self, agent):
raise NotImplementedError()
class FileLeaf(FileSystemNode):
"""[末端] を表すファイルクラス"""
def __init__(self, name, size):
super().__init__(name)
self.size = size
def accept(self, agent):
# 工作員がファイルに接触した瞬間、自身のデータを工作員に調べさせる
# 戻り値として、自身のファイルサイズを親（フォルダ）に返す
return agent.visit_file(self)
class FolderComposite(FileSystemNode):
"""[木] を表すフォルダクラス"""
def __init__(self, name):
super().__init__(name)
self.children = []
def add(self, node):
self.children.append(node)
return self
def accept(self, agent):
# 1. まずはフォルダに入ったことを工作員に通知する（行きがけの処理）
agent.visit_folder(self)
# 2. [再帰的巡回] フォルダの中にある子どもたちへ、工作員を次々と突入させる
# 各子どもたちが持っているサイズをボトムアップで回収し、合計（マージ）していく
total_sub_size = 0
for child in self.children:
total_sub_size += child.accept(agent)
# 3. すべての子どもの調査が終わったら、工作員にそのフォルダの最終報告をさせる（帰りがけの処理）
# このフォルダの合計サイズを、さらに上位の親フォルダへと返していく
return agent.visit_folder_post(self, total_sub_size)
# ==========================================
# 【工作員の共通規格】共通のインターフェース
# ==========================================
class AgentInterface:
"""すべての特命工作員が必ず持つ能力（メソッド）"""
def visit_file(self, file_node): raise NotImplementedError()
def visit_folder(self, folder_node): raise NotImplementedError()
def visit_folder_post(self, folder_node, sub_size): raise NotImplementedError()
def show_result(self): raise NotImplementedError()
# ==========================================
# 【特命工作員A】フォルダごとに合計サイズを計算して表示する任務（修正版）
# ==========================================
class SizeAggregationAgent(AgentInterface):
"""工作員A：ボトムアップで各フォルダの「中身すべての合計サイズ」を暴く職人"""
def __init__(self):
# 各フォルダの最終的な集計結果を記録する辞書
self.results = {}
def visit_folder(self, folder_node):
# 行きがけ：特に何もする必要はありません（通過通知のみ）
pass
def visit_file(self, file_node):
# ファイルを発見：そのファイルのサイズをそのまま上に返す
return file_node.size
def visit_folder_post(self, folder_node, sub_size):
# 帰りがけ：子どもたちの合計サイズを記録し、さらに上の親フォルダへとそのサイズを引き渡す
self.results[folder_node.getName()] = sub_size
return sub_size
def show_result(self):
# 最後に、蓄積されたすべてのフォルダの集計結果を報告
print(" --- フォルダサイズの集計 ---")
for folder_name, total_size in self.results.items():
print(f" □ {folder_name} 内の合計: {total_size} KB")
# ==========================================
# 【特命工作員B】サイズの大きい順にファイルランキングを表示する任務
# ==========================================
class SizeRankingAgent(AgentInterface):
"""工作員B：森全体をくまなくスキャンし、巨大なファイルの上位ランキングを抽出する"""
def __init__(self):
self.file_list = [] # 発見したすべての(ファイル名, サイズ)を記録する
def visit_folder(self, folder_node):
pass
def visit_file(self, file_node):
# ファイルを見つけたら、名前とサイズをメモに記録してサイズを上に返す
self.file_list.append((file_node.getName(), file_node.size))
return file_node.size
def visit_folder_post(self, folder_node, sub_size):
# ランキング班は、合計サイズを上の親に引き渡す案内係だけを行う
return sub_size
def show_result(self):
# メモに集まったファイルを、サイズが大きい順（降順）にソーティング
ranking = sorted(self.file_list, key=lambda x: x[1], reverse=True)
print(" --- ファイルサイズでかいTOP3 ---")
for idx, (name, size) in enumerate(ranking[:3], 1):
print(f" No.{idx}: {name} ({size} KB)")
# ==========================================
# 【作動テスト】コンポジットの森に、工作員を順次投入
# ==========================================
print("=== Visitor Agent Algorithm: Start ===\n")
# 1. コンポジットの森の構築
root_dir = FolderComposite("デザインパタン")
gener_dir = FolderComposite("工場")
behav_dir = FolderComposite("行動")
file_a = FileLeaf("f a c t o r y .py", 12)
file_b = FileLeaf("m e d i a t o r .py", 45)
file_c = FileLeaf("i t e r a t o r .py", 8)
file_af = FileLeaf("f a c t o r y Fat .py", 123)
file_bf = FileLeaf("m e d i a t o r Fat .py", 456)
file_cf = FileLeaf("i t e r a t o r Fat .py", 89)
root_dir.add(gener_dir).add(behav_dir)
gener_dir.add(file_a).add(file_af)
behav_dir.add(file_b).add(file_c).add(file_bf).add(file_cf)
print("[特命 1] ")
agent_A = SizeAggregationAgent()
root_dir.accept(agent_A) # ルートから突入agent_A.show_result() # 結果報告
print("\n" + "="*50 + "\n")
print("[特命 2]")
agent_B = SizeRankingAgent()
root_dir.accept(agent_B) # ルートから突入
agent_B.show_result() # 結果報告
[OUT]
=== Visitor Agent Algorithm: Start ===
[特命 1]
--- フォルダサイズの集計 ---
□ 工場 内の合計: 135 KB
□ 行動 内の合計: 598 KB
□ デザインパタン 内の合計: 733 KB
==================================================
[特命 2]
--- ファイルサイズでかいTOP3 ---
No.1: m e d i a t o r Fat .py (456 KB)
No.2: f a c t o r y Fat .py (123 KB)
No.3: i t e r a t o r Fat .py (89 KB)
３．振り返り
＜振り返り＞
探検3兄弟の役目が明確になりましたか。
・イテレタ
イテレタというは順序的な集合を地味に全件調査するための、共通仕様だったね。
仕様が共通であるため、調査対象の実装が混ざったり、変わったりしても大丈夫だった。
こういうニーズがなければ、ふつうに言語の要素をfor文で回せばよい。
そしてイテレタが必要になったら、車輪から作らずインポートして使えばよいでしょう。
・インタプリタ
インタプリタは通訳一式だった。
インタプリタは万能の通訳ではなく、インタプリタに対応するデータにだけ実行できます。
それが中置記法の数式なら中置記法の電卓が、
それが後置記法の数式ならRPNのインタプリタが活躍する。
これも数式を分数対応にしたり、関数対応にしたり、行列対応にたりと読ませるニーズが高まると、
インタプリタもそれができるようにしつつ、インタプリタが読める形式も決めないといけないね。
・ビジター
ファイル構造のように入れ子になったような複雑な対象でも
その構造を壊さずに構造に入り込んで、オペレーションを追加したいときにオペレーションごとに
調査員、工作員を作れば目的が達成できる。だから、複雑なデータを解析したかったら、ビジターを
受け入れるアクセプトの内容と対にして工作員のインターフェースを作り込むだけ、複雑なデータ構造の
クラスを大改造する必要がなくなるということだね。
・ビジターにみる上位互換性
その実装の場面では、
平坦な道、つまりイテラブルな集まりではイテレタ的に地味に直進してもらう。
フォルダとファイルの違いのように、意味の違いがあるときはインタプリタ的な反応の違いを盛り込む。
だから、3兄弟のいいところが、ビジターの中にギュッとつまっている感じがするね。
課題：geogabraで探索3兄弟を実感するためにはどうしたらいでしょう。
べき関数の微分は（ax^n)'=anx^(n-1)
和の微分は微分の和 (f+g)'=f'+g'
積の微分は片方だけ微分した積の和＝(fg)'=f'g+fg'
べき関数を端末ファイル、和をイテラブルな集まり、積をフォルダのように見よう。
すると、
和の微分はイテレタ的、
端末の微分はファイルサイズの取得、
積の微分はフォルダ全体の微分と見れなくもないですね。
f=x
g=x^3
h=2x
j=f(g+h)の微分をしたい。
このテーマに3兄弟が挑みます。
イテレタ君は積の微分公式は苦手だべき関数の微分だけは使える。
インタプリタ君は積と和で対応を変えるのが好きだ。式を解釈するのが得意だ。
ビジター君は和も積も微分公式も知っていて、分解合成の発想が好きだ。
iter=derivative[expand(j)]と展開してからベターっと微分するがイテレタ君
inter=f'(g+h)+f(g+h)'と積と和を区別を意識して段階的に処理するのがインタプリタ君
visit=f'g+f'h+fg'+fh'と全体像が見えるので必要な末端だけ微分して、あとで合成するのがビジター君
イテレタ君のやり方が一番スマートで単純ですけれど、
インタプリタ君やビジタ君のような発想は、微分の逆である積分のときに力を発揮します。
部分的に微分と積分を行ったり来たりするという発想は、部分積分では不可欠ですね。
特に、微分方程式が必要な分野ではよく使うでしょう。
という、フォローを入れておきます。
そうしないと、
なんて、しょうもない別解作ってんの？
暇な人だね。あんたは。
で終わる危険があるから、かきました。