博士

やあ、ロボ子。今日はプログラムグラフのシリアライズについて話すのじゃ。

ロボ子

プログラムグラフのシリアライズ、ですか。それは一体何でしょう？

博士

簡単に言うと、プログラムグラフをlet束縛の系列に変換することじゃ。目的は、計算結果を共有して、より効率的なプログラムを作ること、つまりsharingじゃな。

ロボ子

なるほど。効率化が目的、ということですね。

博士

そうじゃ。最初は、グラフの各部分で自由変数を追跡して、スコープ内に入ったらすぐにlet束縛しようとしたらしいんじゃが、うまくいかなかったみたいじゃな。

ロボ子

ソース言語にletを導入する方法を追加したことで、アルゴリズムが間違ってしまった、と。

博士

そうそう。そこで、プログラムグラフでダイヤモンドパターンがどこにあるかを判断することにしたらしいぞ。

ロボ子

ダイヤモンドパターン、ですか？

博士

そうじゃ。ノードnがダイヤモンドのソースなら、nの定義をインライン化する直前に、ダイヤモンドのシンクをlet束縛する必要があるんじゃ。

ロボ子

なるほど、少しずつ分かってきました。

博士

ところが、このアルゴリズム、O(n^2)で遅かったらしいんじゃ。グラフ内のすべてのノードを調べて、その下にある到達可能なセット全体を調べる必要があったからじゃな。

ロボ子

それは大変ですね。

博士

そこで、「最小共通祖先」（LCA）の概念が登場するんじゃ！

ロボ子

最小共通祖先、ですか？

博士

そう！LSCA(x, y) = l は、「lはすべてのルートからxへのパス上にあり、lはすべてのルートからyへのパス上にあり、lの子孫はこれを持たない」というものじゃ。

ロボ子

なるほど。少し難しいですが、理解できそうです。

博士

論文によると、「最小単一祖先」（LSA）ツリーを構築することで、LSCAを計算するための前処理スキームがあるらしいぞ。ノードのLSAは、そのすべての入力エッジのLSCAじゃ。

ロボ子

LSAツリーを線形時間で計算するためのアルゴリズムもあるんですね。

博士

そうそう。Ed Kmettさんのlcaパッケージは、グラフ内の任意の2つのノードのLCAを計算するためのO(log n)アルゴリズムを実装しているらしい。

ロボ子

すごいですね！

博士

LSAツリーを使って、let束縛をどこに配置するかを判断するんじゃ。ノードからそのLSAへのマップが与えられたら、そのマップを反転して、このノードをLSAとして持つ子孫へのノードのマップを取得する。

ロボ子

なるほど。ノードをインライン化するときは、このマップ内のすべてを調べて、最初にインライン化するんですね。

博士

そう！この解決策は、以前のその場しのぎの実装の3分の1の長さで、グラフ内のノード数の線形時間で実行されるらしいぞ！

ロボ子

それは素晴らしいですね！

博士

というわけで、プログラムグラフのシリアライズの話は終わりじゃ！

ロボ子

ありがとうございました、博士！

博士

ところでロボ子、LCAって言ったら、どうしても「ローカルコンテキストアウェア」を思い出しちゃうのじゃ。全然関係ないけど！

ロボ子

博士、それはちょっと無理がありますね…。