それでは、実際にソフトウェアの系統樹を復元（推定）してみましょう。ここでは、Emacsと呼ばれるエディターを例に、系統樹を復元してみます。Emacsは、1970年代にその原型が作られてから後、多くの派生種が生み出されました。2012年現在も幾つかの子孫の開発が続けられています。まさに題材として打って付けです。系統樹の復元には、生物系統学（分子系統学）ではおなじみの、距離行列法を用います。ここで言う距離（進化距離と呼ばれる）とは、生物の場合はDNAの塩基配列の違いを表す数値です。ソフトウェアの場合は、ここではソースコードの違いを表す数値と考えます。距離行列とは、系統樹の要素となる「種」の間の距離を網羅的に記した行列です。分子系統学では、距離行列から系統樹を生成するソフトウェアが用いられますが、ここではその一つであるPHYLIPと呼ばれるソフトウェアを流用します。今回の系統樹復元の手順をまとめると次のようになります。

サンプルの収集

サンプル（派生種も含む）のソースコードを収集します。新しいサンプルは収集が容易ですが、古いサンプルの収集は骨が折れます。それでもなんとか、1985年にリリースされたGNU Emacsの13.8.15を筆頭に、26の初期Emacsのサンプルを集める事ができました。収集したサンプルは、

• GNU Emacs: 13.8.15, 16.56, 18.41, 18.51, 18.55, 18.57, 18.58, 18.59, 19.7, 19.8, 19.18, 19.23, 19.28, 19.34
• Lucid Emacs: 19.0.23, 19.6, 19.8, 19.10
• XEmacs: 19.11
• Epoch: 3.2, 4.0p2, 4.1, 4.2
• NEmacs: 3.3.2
• Mule: 1.1, 2.3

です。

距離行列の計算

サンプル間の進化距離を網羅的に計算し、距離行列を作ります。ソフトウェアの進化距離の測り方は様々ですが、ここでは、ソースコードのAST（Abstract Syntax Tree、抽象構文木）の編集距離（edit distance）を考えます。AST間の編集距離の計算には、Diff/TSと呼ばれる木構造間差分計算システムを利用します。

系統樹の推定

PHYLIPには分子系統学に纏わる多くのアルゴリズムが実装されています。距離行列法のアルゴリズムも幾つか実装されていますが、ここではFITCHと呼ばれるFitch-Margoliash法の実装を利用します。FITCHに上述の距離行列を与えるだけで、系統樹が出力されます。

さて、次回はいよいよ復元されたEmacsの系統樹をご紹介します。