プログラムの可調デフォルマシオン

はじめに

本稿では、制御依存関係に基づくプログラムの 可調デフォルマシオン(tunable deformation) の手法について論ずる。 これは、与えられたプログラムの各部分に対する重み付けとプログラムの剪定という二つのステップから構成されており、 重み付けや剪定に於ける閾値の指定を調整可能なものとすることで、状況に応じてデフォルメの度合いを変更出来るようにしたものである。

動機

プログラムが大規模になれば、そのコードを上から下まで具に追っていくことは困難になるが、 たとえそうであっても、それが「どのような」プログラムなのかを把握しなければ、取り扱うことはできない。

プログラムをデバッグする、プログラムから仕様を抽出する、またはプログラムのテストケースを作成する、 どれを行うにあたっても、プログラムの正体が全くわからない状態よりはその姿形が見えていた方が見通しは良くなるだろう。

本稿で論ずるプログラムデフォルマシオンの手法は、 プログラムのユーザが対象のプログラムを理解し把握するための助けとなることを目的として考案されたものである。

デフォルマシオン

デフォルマシオン(déformation) とは、ある対象を 作り手の主観を反映した 形で意図的に変形させた表現のことを言う。 似顔絵に於ける部位の強調などはこの代表例である。

すると、プログラムのデフォルマシオンとは即ち ある人の主観で以って プログラムを変形させた表現のことだ。 本稿の手法に於ける「主観」とは、プログラム中の着目すべき要素とその重要度である。 プログラムにデフォルメを施すことで、その概形が強調される。 それは実行可能なプログラムとはならずとも、プログラムが「どんな形をしているのか」という情報を与えてくれる。 この情報は、改めてプログラムそのものを眺めるときの良いガイドとなることが期待できる。

それゆえ、デフォルメに際して「どこに着目するのか」というのは重要な情報だが、 「どのようにしてデフォルメを行うか」ということはそれ以上に大きな意味を持つ。 理論的な裏付けの無い方法で矢鱈とプログラムを変形させた場合、 そこから意味のある情報を得られるかどうかという意味で、信頼性が失われてしまう。

本稿では「プログラムの制御構造の概形を把握すること」をデフォルメの目的に据え、 その変形の基準として制御依存関係を用いることにした。

以降では、制御依存関係について簡単に述べた後にデフォルマシオンの手法の詳細について解説する。

制御依存関係

プログラムに於ける制御依存関係とは、ある文の実行が(自分を含む)他の文の実行結果如何に左右されるような関係である。 ある文 C がその実行結果に依って 2 つの遷移を持ち、その一方の遷移でのみ実行される文 S があったとすれば、 C と S は制御依存関係にある。

プログラムに対する制御依存関係の計算は、プログラムから得られる制御フローグラフ(Control Flow Graph、以下CFG)を元にして行う。 本稿では制御依存解析についての詳細は述べないが、デフォルマシオンの例示の準備も兼ねて、具体例で以って説明を行う。

以下のようなプログラムがあったとする。

initialize( x, y );
if y < 3 then
   fun( z );
   w := 5
   while w <> 0 do
      callDB( w, z );
      w := w + 1
else
   z := y + 1;
   while z < 5 do
      w := getData( z )
push( w );
return x;

このプログラムから得られる CFG は次のようなグラフになる。

./dot_cfg.png

各ノードの左側の数字はノードの識別のための番号である。 制御依存関係は、例えばこのグラフに於けるノード 2 とノード 3 の間に見られる。 式 y < 3 が真であれば式 fun( z ) は実行されるが、偽であれば実行されない。 この状況を「ノード 3 はノード 2 に制御依存する」と言う。

これらの制御依存関係をすべて計算し、 CFG に反映したものが次の図である。

./dot_cfg_with_cd.png

ノード m がノード n に制御依存している状況を、 n から m へ点線の矢印を引くことで表している。

この図から、ノード 2 に制御依存するノードがノード 3 の他にノード 4, 5, 8, 9 と4つ存在していることが分かる。

また、ノード 6 やノード 7 はノード 2 に制御依存していない。 これらのノードに辿り着けるかどうかがノード 2 の式 y < 3 の実行結果に左右されるのは確かだが、 ノード 5 の式 w <> 0 の結果の方がより直接的にその実行を制御しているので、 ノード 6, 7 が制御依存するのはノード 5 にということになる。

もう一つ重要な点としては、ノードは自身に制御依存しうる、ということである。 この例ではノード 5, 9 がそれに該当する。これらは元々 while 文の条件部の式であった。 この構造は、後に各ノードの優先度を計算方法を考えるにあたって注意すべきポイントとなる。

デフォルマシオン

プログラムから得た CFG を元に制御依存解析を行ったので、デフォルマシオンの準備が整った。

制御依存に基づいたデフォルメを施す手順は、 重みの伝播(weight spreading)フロー剪定(flow pruning) の二つに分けられる。

重みの伝播とは、プログラムのある部分に与えられた重みから他の部分の重みを計算することである。 本稿のデフォルマシオンは、プログラムの制御構造という観点から重み付けをを行う。

フロー剪定は、与えられた閾値を基に CFG のノードを刈り取っていく。 重みの伝播の仕組みは単純だが、閾値を変動させることでデフォルメする度合いを変えることが出来る。 本手法の 可調(tunable) たる所以である。

重みの伝播

重みの伝播は、

  1. 一部の式に初期重みを付与
  2. 制御依存関係に基づき、すべての式に対する重みを計算

という流れで行われる。 初期重みの付与は、特定の式への明示的な指定や、一定の基準に基づく自動的な付与などによって為されることになる1

プログラムデフォルマシオンに於いては、 重みとして非負整数を用い、重みを伝播する際には制御依存関係にある式の重みの最大値を用いることにする。 これは、ノード n の重みを p(n) と書くとすると、

という等式が全てのノードに対して成り立つように重み付けを行うということである。 なお、 ノード m がノード n に制御依存することを `` m c.d n ''と略記した。

ここでは、先に取り上げたプログラムを用いた具体例で以って、重みの伝播を見ていく。

まず、プログラムの一部の式に初期重みを付与し、それを CFG のノードに付記したものが次の図である。

./dot_cfg_with_w.png

プログラム中の全ての式に対して初期重みを付与する必要はない。この例では、分岐を担う式には重みが与えられていない。

初期重みの付与された状態から、等式(1)を満たすように他の式の重みを伝播させたものが次の図である。

./dot_cfg_with_w_calc.png

先ほどは重みが未定義であったノードに重みが与えられていることがわかる。 本稿では重みの伝播の仕組みをどのように実装するかの説明は省くが、 基本的には様々なデータフロー解析と同様のアプローチで実現できることだけ述べておく。

これでフロー剪定を行う準備は整った。 しかし、重みの伝播を行うにあたって一つ注意すべきことがあるので、最後にそれを説明する。

グラフを見てみると、ノード 7 とノード 12 も元々は重みの与えられていなかった式だが、今は 0 が付与されている。 これら二つのノードに制御依存するノードは存在しないので、 等式 (1) に基づく限り、本来ならばこれら二つのノードの重みは計算出来ないはずである。

ここで、重みを非負整数に制限したことを思い出して欲しい。 非負整数上では、最大値を求める演算 max は単位元 0 を持つ。

この事実を利用し、重みの伝播に際しては未定義の重みを演算の単位元、ここでは 0 と読み替えていたのである。 非負整数という制限がない場合は、未定義の重みを負の無限大と解釈しておけばよい。

重みの伝播をどのような計算式に基づいて行うかについては、色々な可能性が考えられる。 その点に関する議論は割愛するが、どのような方式を採るにせよ、用いる演算に対しての ``単位元'' たるものが必要となる。

フロー剪定

フロー剪定は、与えられた 閾値(threshold) を下回る重みのノードを刈り取るという手続きである。 これによって、プログラムの各部分への重み付けを可視化することができる。 そうして剪定されたプログラムこそが、デフォルメされたプログラムとなる。

さきほどのグラフを閾値 4 で剪定すると、以下のグラフが得られる。

./dot_cfg_with_w_calc_4.png

このグラフと元のプログラムとを比較すると、 while 文が一つ姿を消していることがわかる。 このことは、 push(w)callDB(w,z) に注目してプログラムの制御構造を捉えようとするときには、 その while 文がもはや関係ないものであることを意味している。

プログラムデフォルマシオンでは、各ノードに切り落とされるか否かのフラグを与えるのではなく、重みというパラメータを与えている。 これはデフォルメのチューニングを可能とする。

元のグラフを今度は閾値 3 で剪定したものが次のグラフである。

./dot_cfg_with_w_calc_3.png

閾値 4 で剪定したグラフとの違いは、ノード 9 の式が担う while 文が表れている点だ。 他の重要な式に加え、式 w <- getData( z ) にも注目することにしたと捉えることが出来る。 その結果、ノード 10 の実行を左右するノード 9 を伴いグラフに現れたのである。

このようにして、閾値を下げて剪定をすることで注目すべき部分を増やし、プログラムの構造をより詳細に表すことができた。 逆に、閾値を上げることで注目すべき部分を絞ることも出来る。 以下は、閾値 5 で剪定したグラフである。

./dot_cfg_with_w_calc_5.png

元々の CFG と比べると、ほとんどのノードが刈り取られていることがわかる。 fun(z)push(w) にのみ注目した結果である。

おわりに

ここまで、制御依存関係に基づくプログラムの可調デフォルマシオンについて述べてきた。

この手法では重みの伝播に於いて制御依存関係のみを用いることで目的を制御構造に絞ったデフォルメを施したが、 データ依存関係等を組み込むことでどのようなデフォルメが得られるのかも興味深い。

プログラムスライシングは、制御依存関係とデータ依存関係を組み合わせて得られるプログラム依存関係に基づいたプログラムの変形だが、見方によってはこれもデフォルマシオンの一種である2

可調デフォルマシオンは現在、Common Lisp を用いて試験的な実装を終えたところである。 次回のレポートにて、プログラムデフォルマシオンの実装に関する詳細を纏める予定。

Footnotes:

1 重みの自動付与の例としては、 OS や DB との遣り取りが発生する式には大きな重みを付与する、といったものが考えられる。

2 プログラムスライシングをデフォルマシオンとみなす場合、 デフォルメに反映される「主観」とはスライシング基準に他ならない。

Author: SUDA Keishi

Date: 2013-11-12 16:17:22 JST

Generated by Org version 7.8.11 with Emacs version 24

© Mathematical Systems Inc. 2013