テストデータ生成系 Korel 法 の調査第三回 – Korel 法の実装

Korel 法の実装

前回は、実験的に設計した P 言語と、 代表的なプログラム静的解析の一つであるプログラムスライスについて説明した。 今回は P 言語上に実装した Korel 法に基づくテストデータ生成系を紹介する。

P 言語がサポートするデータ型は整数と日付及びその配列である。 P 言語のテストデータ生成系は、プログラムと、そのプログラムが取るべきパスを入力とし、 要求されたパスを満たすような、プログラムの入力値を作る機能を提供する。 テストデータ生成器は、大きく分けて以下の部分から成る。

1. run-generator
パス確認機能付きインタプリタ。
2. try-adjust-param
指定されたパスを満たす入力値の生成を試みる。
3. exploratory-move
入力値を僅かに変更して評価することで、 分岐の成立に関連する変数かどうかを確かめる。
4. pattern-move
分岐の成立に関連する変数について、 集中的に変更することで分岐の突破を試みる。

分岐関数

プログラムが取るべきパスを満たせない状況とは、パスを誤った直前の分岐において、 指定されたパスと逆の方向に実行が進んでいることであると考えられる。 つまり、その間違って進んでしまった分岐について、 逆方向に進む入力値を探すことが出来れば、 プログラムが取るべきパスを満たすことが出来るようになるといえる。

各入力値と、注目する分岐の相関を示す指標として、 分岐関数 (Branch Function) という関数を使用する。 これは、以下のように定義される。

分岐の述語分岐関数分岐の成立
E1 > E2E2 - E1< 0
E1 >= E2E2 - E1<= 0
E1 < E2E1 - E2< 0
E1 <= E2E1 - E2<= 0
E1 == E2abs(E1 - E2)== 0
E1 /= E2abs(E1 - E2)/= 0

分岐関数は、 (/= 以外) その値が小さければ小さいほど、 分岐の成立に近づくように定義されている。 このため、以下のような手順を踏むことで、各入力値と注目する分岐との相関を調査できる:

  1. ある入力値でプログラムを実行し、注目する分岐の分岐関数を計算する。
  2. 入力値を変更してプログラムを実行し直し、注目する分岐の分岐関数を計算する。
  3. 2. での分岐関数の値と、 1. での分岐関数の値を比較する。 分岐関数の値に変化があれば、その入力値の変更は分岐に関連しているということである。 さらに、分岐関数の値が小さくなっていれば、 その入力値の変更は分岐を成立に近づけたということになる。

つまり、ある分岐を突破することを目標とする場合、 各入力値をそれぞれ変更して分岐関数を評価し直すことで、 分岐を成立に近づける入力値を発見することができる。 そのような入力値が見つかれば、あとはそれにのみ注目して変更すれば、 いつかは分岐を突破できるのである。

プログラム各所の概説

run-generator

run-generator は、一般的なインタプリタに、以下の機能を加えたものである:

  • プログラムが通るべきパスを引数にとり、 実行時のパスがそれと等しいかを確認する。
  • プログラムが要求されたパスを満たさなかった場合、 指定されたパスを満たす入力値の生成を試みる。 指定されたパスを満たせない状況とは、分岐の条件を満たせなかった場合であることから、 この時点で満たせなかった直前の分岐条件に注目し、その突破を試みる。 この仕事は、後述の try-adjust-param が行う。
(defun run-generator (pgm requested-npath &key (exploratory-mode nil))
  "pgm                  - テストデータ生成を試みるプログラム
   requested-npath      - 要求されたプログラムの実行パス (文番号のリスト)
   exploratory-mode     - exploratory mode での使用であることを示すフラグ
   *ongoing-constraint* - 間接的に参照するパラメータ情報のグローバル変数

   処理概要:
     run-generator は要求パス requested-npath と同一の実行パスが
     得られるような、プログラムパラメータ値を求める関数である。
     *ongoing-constraint* はプログラムのパラメータの値 (及びその検索範囲上下限)
     を保持するグローバル変数である。このパラメータ値から開始し、
     各実行文 (ここではブロックとも言う) をステップ実行をしていく。
     同時に、各ステップではその実行パスが、要求された requested-npath の通り
     進行していくかを監視し、食違いが検出された場合は try-adjust-param
     によりパラメータ値を修正し、再度最初から実行を試みる。

   インタフェース:
     1. 検索が成功した場合は nil を返す。
        この場合、得られたパラメータ値は *ongoing-constraint* に記録される。
     2. テストデータ生成に失敗した場合は、エラーをシグナルする。
        本 Korel 法では解を発見出来なかったことを意味する。
     3. Exploratory mode の場合は、部分的に突破出来た実行パスを返す。
        Exploratory mode は予備的な検索であり、そこでは部分的な突破も
        失敗とは扱わず、その情報を利用する。"
  (let ((rest-npath requested-npath)
                ; rest-npath は現在まだ突破出来ていない残りのパスを保持する。
        (bblk (first (program-bblks pgm)))
                ; bblk はプログラム pgm の各ステップ実行中の実行文(ブロック)を保持する
                ; ための変数、すなわちプログラムカウンタである。
                ; (program-bblks pgm) はプログラム pgm の全てのブロックリストを返す。
                ; そのリストの先頭 first は入口ブロックである。
                ; 入口ブロックとはユーザが書いたプログラムから作られた実行文の
                ; リストのさらに先頭に加えられる実行開始文を表すダミーブロックであり、
                ; フローチャートで例えれば、開始を表す楕円記号に対応する。
        (bblk-prev nil))
                ; パラメータを探索する try-adjust-param では現在の bblk の
                ; 直前の値が必要となる。それを保持する変数である。

    ;; *ongoing-constraint* からパラメータ値を取り出し、それを
    ;; プログラム pgm のパラメータ値として設定する。
    (set-program-params pgm (ongoing-var-init-list))

    ;; 現在ブロックを bblk-prev にセーブし、pexec-1 によりステップ実行。
    ;; ここで実行されたのは入り口ブロクであり、実行後 bblk は
    ;; 実際ユーザが書いたプログラムの最初の文に対応している。
    (setq bblk-prev bblk
          bblk (pexec-1 pgm bblk))

    (loop while                         ; 以下の三つの条件が満たされる間繰り返す
          (and (not (null rest-npath))  ; 1. rest-npath が空でなく
               (not (exit-bblk-p bblk)) ; 2. プログラムの終了ブロックでなく
               (= (first rest-npath) (bblk-no bblk)))
                                        ; 3. 残りパスの先頭が現ブロックと一致
        do
          ;; rest-npath の先頭は突破出来たので、残りのパスを一つ進める。
          (setq rest-npath (rest rest-npath))
          ;; 現在ブロックを bblk-prev にセーブし、ステップ実行。
          (setq bblk-prev bblk
                bblk (pexec-1 pgm bblk)))

    ;; ループ終了後は、上記条件 1., 2., 3. いずれかが満たされていない。

    (cond ((null rest-npath) nil) ; 1. が満たされていない場合。
                      ; すなわち、rest-npath が空リストであり、検索成功で nil を返す。
          ;;
          ;; 以下、2. か 3. が満たされない場合であり、いずれも *ongoing-constraint*
          ;; に記録されているパラメータ値が正しくないことを意味する。
          ;;
          (exploratory-mode rest-npath)
                      ; しかし、Exploratory mode の場合は、
                      ; 途中まで突破した情報を利用するので rest-npath を返す。
          ;;
          ;; そうでなければ、*ongoing-constraint* の値は正しくない。
          ;;
          ((exit-bblk-p bblk)  ; 2. が満たされていない場合。
           ;; ここで、終了ブロックに至ってしまった場合は、
           ;; 現在の実装では、検索をあきらめてエラーをシグナルする。
           (error "requested pass cannot be satisfied."))
          ;;
          ((/= (first rest-npath) (bblk-no bblk))  ; 3. が満たされていない場合。
           ;; この場合は、突破出来た所から継続して再検索を行う。
           (let* ((cleared-npath (ldiff requested-npath (rest rest-npath)))
                          ; 検索がうまく行ったところまでのパス、正確には最後の要素は
                          ; 失敗した個所、を cleared-npath とする。
                  (success (try-adjust-param pgm
                                             cleared-npath
                                             bblk-prev
                                             (first rest-npath))))
                          ; try-adjust-param は失敗個所を突破するパラメータを検索し、
                          ; それを *ongoing-constraint* に記録して non-nil を返す。
                          ; 失敗した場合は nil を返す。
             (if success
                 ;; try-adjust-param が成功して、当該箇所が突破出来た。
                 ;; そのパラメータは *ongoing-constraint* にセットされている。
                 ;; その状況で、再度最初から実行を試みる。
                 (run-generator pgm requested-npath)
               ;; try-adjust-param が失敗した場合は、検索全体をあきらめる。
               (error "requested pass cannot be satisfied.")))))))

try-adjust-param

try-adjust-param は、入力値を変更することで、注目している分岐について、 その突破を試みる手続きである。

まず、各入力値を少しずつ動かしてプログラムを実行し直す。 そして、プログラムの実行が注目している分岐に至った時点で、 その分岐の分岐関数の値を評価する (exploratory-move) 。

分岐関数が改善された場合、その入力値は、 注目している分岐に何らかの形で寄与していると見なせるため、 その入力値を集中的に動かすことで、分岐の突破を試みる (pattern-move) 。

一方、分岐関数が変化しなかった場合は、 その入力値は注目している分岐に関係ないといえるので、 ただちに次の入力値の調査に移る。

(defun try-adjust-param (pgm sub-goal branch-bblk requested-bblk-no)
  "pgm                  - テストデータ生成対象プログラム
   sub-goal             - データ生成して満たすべき部分的な実行パス
   branch-bblk          - 分岐条件の実行文
   requested-bblk-no    - データ生成して分岐すべき分岐先の文番号

   処理概要:
     要求された実行パス全体ではなく、その一部が満たされるような、
     プログラムのパラメータ値を求める。
     例えば、要求された実行パス全体が (1 2 3 4 5) であり、文 3 が分岐文とする。
     そして、現パラメータ値から実行してみると (1 2 3 5) と実行されたとする。
     この場合、パラメータを動かして 3 -> 4 という分岐となるよう試みるのが
     try-adjust-param である。 この場合、
     sub-gloal         には (1 2 3 4) という文番号のリスト、
     branch-bblk       には分岐文 3 のデータ (bblk 型)、
     requested-bblk-no には分岐先の文番号 4 を指定する。

  インタフェース:
    1. 検索が成功した場合は t を返す。
       この場合、得られたパラメータ値は *ongoing-constraint* に記録される。
    2. 検索が失敗した場合は nil を返す。
       この場合、テストデータ生成全体が失敗する。
       *ongoing-constraint* には正しくない(要求された実行パスを満たせない)
       パラメータ値がセットされている。"
  (let* ((branch-npath (butlast sub-goal))
                 ; 最初の失敗に対応する sub-goal の最期の要素(文番号)より前の部分、
                 ; 即ち、そこまでは成功した文番号のリストを branch-npath とする。
                 ; branch-npath の最後は誤った分岐をした条件文である。
         (bf-sign (let* ((succs (bblk-succ branch-bblk))
                             ; bblk-succ は分岐先の文(bblk 型)の長さ 2 のリスト
                             ;   succs = (条件が真の分岐先  条件が偽の分岐先)
                             ; であり、
                         (pos (position requested-bblk-no succs
                                        :key #'bblk-no)))
                             ; 要求された分岐先 requested-bblk-no と比較して
                             ; どちらかを決定する。
                    (ecase pos (0 +1) (1 -1))))
                 ; 分岐文 branch-bblk の期待する分岐方向を示す:
                 ;   bf-sign = +1  :  条件が真の方へ分岐せよ
                 ;   bf-sign = -1  :  条件が偽の方へ分岐せよ
         (bf-cmp (gen-branch-comparator (bblk-expr branch-bblk) ; 実行文条件式
                                        (program-venv pgm) ; 変数環境
                                        bf-sign)) ; 分岐方向
                 ; Korel-90 の定義に従った、分岐関数値が改善されたかどうかを
                 ; 判定するクロージャを作り、 bf-cmp とする。
         (targets (lookup-targets pgm branch-npath)))
                 ; 積極的に動かすべき順で並べられたパラメータの情報を得る。
    (loop
        with explore-range-ok = nil
        for explore-scale = 1
        then (1+ (* explore-scale *explore-retry-scale*))
        thereis
          (loop for (loc _) in targets  ; loc = 各 target の <Location>
              do
                (let ((expl-sign (ignore-errors  ; 対象プログラム実行エラー無視
                                   (exploratory-move pgm
                                                     branch-npath
                                                     bf-cmp
                                                     loc
                                                     explore-scale))))
                                 ; exploratory-move は loc で示されるパラメータ
                                 ; (配列の場合はその特定要素) を explore-scale
                                 ; に従って動かし、分岐関数が改善されたら
                                 ; その変数を動かすべき方向 (+1 or -1) を返す。
                                 ; 改善されなければ nil を返す。
                                 ;
                                 ; 注意:
                                 ; ここで、改善とは分岐関数の改善のみを意味し、
                                 ; 目標の sub-goal が達成されている保障はない。
                  threis (when expl-sign
                           ;; 改善されたので loc は分岐突破に関連しているとみなし、
                           (setq explore-range-ok t)
                           ;; explore-range-ok フラグをセットし、
                           (when (ignore-errors  ; 対象プログラム実行エラー無視
                                   (pattern-move pgm sub-goal bf-cmp loc expl-sign))
                             ;; さらに詳細に loc を動かし、 sub-goal の達成を試みる。
                             ;; 成功したら、 try-adjust-param 全体の成功であり、
                             ;; t を返して終了する。
                             t))))
          ;; ある explore-scale について、全ての loc で exploratory-move
          ;; が失敗した場合は、 try-adjust-param 全体の失敗とし、
          ;; nil を返して終了する。
          (if explore-range-ok
              (continue)
            (return nil))
        finally                         ; 全ての explore-scale に於いて検索失敗
          (return nil))))

exploratory-move

exploratory-move は、指定された入力値を変更して実行し直すことで、 その入力値が注目している分岐に寄与しているかを確認する手続きである。

まず、入力値を少し動かしてプログラムを実行し直す。この結果、 注目すべき分岐に実行が至らなかったという場合、 その入力値の変更は、実行パスの制約条件を破壊してしまうということである。 その入力値は、変更すべきではない。

注目すべき分岐まで実行がされたら、その分岐の分岐関数を評価する。 分岐関数の値が、入力値の変更前より改善されていれば、 入力値は分岐突破のため、集中的に変更する価値があると見なせる。

(defun exploratory-move (pgm branch-npath bf-cmp loc offset)
  "pgm          - テストデータ生成対象プログラム
   branch-npath - 行先を修正したい分岐文までの実行パス(文番号リスト)
   bf-cmp       - 分岐関数値が改善されたかどうかを判定するクロージャ
   loc          - パラメータ <Location> (lookup-targets のコメント参照)
   offset       - 値の変動量

   処理概要:
     loc で示される変数を offset 分動かし、分岐関数値が改善さたかを調べる。

   インタフェース:
     改善された場合にかぎり non-nil を返す。"
  (flet ((explore-1 (val)
           ;; 変数 loc に val を代入し、branch-npath を実行後
           ;; 分岐関数地が改善された場合にかぎり non-nil を返す。
           (when (target-in-range-p loc val)
             ;; 変数情報として指定される範囲外なら無視。
             (setf (get-target-init loc) val)
             ;; val を loc に対応するパラメータにセット。
             ;; このパラメータ値はグローバル変数 *ongoing-constraint*
             ;; に記録される。
             (if (null (run-generator pgm branch-npath :exploratory-mode t))
                 ;; run-generator を再帰的に呼びだし、branch-npath を満たす
                 ;; ことを試みる。ただしそれが失敗しても全体の失敗ではないので
                 ;; :exploratory-mode t で呼び出す。
                 ;; run-generator が nil を返した場合 branch-npath は
                 ;; 満たされたので、bf-cmp を呼びだして改善されたか判定する。
                 (funcall bf-cmp)
               ;; run-generator が失敗した場合は nil を返す。
               nil))))                  
    (let ((old-value (get-target-init loc)))
                              ; loc の今の値を old-value にセーブし、
      (unwind-protect
          ;; offset 分 + (-)方向に動かして改善されたら +1 (-1) を返す。
          (cond ((explore-1 (add-val old-value offset))     +1)
                ((explore-1 (add-val old-value (- offset))) -1)
                ;; 改善されなければ nil を返す。
                (t nil))
        ;; いずれにせよ、グローバル変数で管理しているパラメータ値を元に戻す。
        (setf (get-target-init loc) old-value)))))

pattern-move は、指定された入力値について、それを集中的に変更し、 注目している分岐の突破を行う手続きである。

まず、入力値を大きく動かしてプログラムを実行し直す。 それによって分岐が突破できれば、その値を新たな入力値として返す。

分岐は突破できなかったが、分岐関数は改善した場合、 もっと先に入力値を動かした方が改善の見こみがあるということである。 さらに大きく入力値を動かして、再度確認する。

一方、分岐関数が悪化したり、そもそも注目する分岐に至らなかったという場合、 入力値の変更が行き過ぎてしまったということである。 入力値の変化幅を小さくして、再度確認する。

pattern-move

(defun pattern-move (pgm sub-goal bf-cmp loc move-sign)
  "pgm        - テストデータ生成対象プログラム
   sub-goal   - データ生成して満たすべき部分的な実行パス
   bf-cmp     - 分岐関数値が改善されたかどうかを判定するクロージャ
   loc        - パラメータ <Location> (lookup-targets のコメント参照)
   move-sign  - exploratory-move で推奨された、パラメータの増減方向

   処理概要:
     要求パス sub-goal と同一の実行パスが得られるような、
     プログラムパラメータ値を求める。
     move-sign に基づき loc で示されるパラメータの新た試験値を定め、
     run-generator を再帰的に呼び出し、bf-cmp の評価結果を考慮して
     sub-goal 突破を試みる。
     bf-cmp は pattern-move の呼び出し側 generate-test-data が
     呼ばれた時点でのパラメータ値を記録しているクロージャであり、
     現在のパラメータ値における当該分岐関数値がその記録されている
     パラメータ値での分岐関数値より「改善」されたかを判定する関数である。

   インタフェース:
     1. 検索が成功した場合は t を返す。
        得られたパラメータ値は *ongoing-constraint* に記録する。
     2. 失敗した場合は nil を返す。
        この場合、*ongoing-constraint* に記録されたパラメータ値は意味が無い。"
  (let* ((amount (pattern-move-amount loc move-sign))
                            ; loc で示されるパラメータの移動量。
                            ; 以後、解検索ループ中で修正されていく。
         (old-value (get-target-init loc))
                            ; loc パラメータの移動前の値。
                            ; パラメータの値はグローバルな *ongoing-constraint*
                            ; に記録していくので、検索失敗時にこの値に戻す必要がある。
         (prev-value old-value)
                            ; 解検索ループにおける、直前の試験値を保持。
         (found nil))
                            ; 解検索ループ中に解が見つかったことを記録するフラグ
    (loop                   ; 解検索ループ
        as test-value = (add-val prev-value amount)
                            ; 解検索ループの、この繰り返しで試みる試験値
                            ; 直前の試験値 prev-value に amount を加えたもの。
                            ; 以下のいずれかが満たされるまでループする
        until (or found     ; 解発見
                  (equalp prev-value test-value) ; 値が尽きた
                  (not (target-in-range-p loc test-value))) ; 値が範囲外

        do (setf (get-target-init loc) test-value)
           ;; test-value を *ongoing-constraint* に記録し、
           (let ((r (run-generator pgm sub-goal :exploratory-mode t)))
                         ; run-generator を再帰的に呼びだし、sub-goal を満たす
                         ; ことを試みる。ただしそれが失敗しても全体の失敗ではないので
                         ; :exploratory-mode t で呼び出す。
             (cond ((null r)            ; 1. run-generator が成功した場合
                    (setq found t))     ; t を返して終了。
                   ;;
                   ;; 2. 最後の分岐のみ失敗したが、分岐関数は改善された場合
                   ;;
                   ;; このケースについての対処は Korel-90 には明記されていないが、
                   ;; 以下の考察に基づいて、本実装では試験的に導入した。
                   ;;
                   ;; run-generator に sub-goal を渡した結果が要素数 1 の場合、
                   ;; それは突破すべき最後の分岐、以下の CondExpr の評価結果のみ
                   ;; 失敗して else 側に行ってしまうという状況である。
                   ;;
                   ;;         .............
                   ;;         if (CondExpr)
                   ;;           ThenStmt; // 期待する分岐
                   ;;         else
                   ;;           ElseStmt; 
                   ;;
                   ;; しかしこの場合、もし分岐関数値が改善されたとすると、
                   ;; それは try-adjust-param が呼ばれた時点での分岐の
                   ;; 誤り度合が軽減され、現在のパラーメータ値における
                   ;; CondExpr の評価が「より ThenStmt 側に近づいた」と
                   ;; 考えるのが自然である。すなわち、失敗ではあるが
                   ;; 現在のパラメータ値はより改善されている。
                   ;;
                   ;; よって、 (funcall bf-cmp :regenerate t) により、現在の
                   ;; パラメータ値に基づいた分岐関数値を基準とするクロージャ
                   ;; で bf-cmp を置き換え。直前の試験値として現在値をセット
                   ;; し直して、やり直すという処理を行う。
                   ;;
                   ;; 補足:
                   ;; 現時点では、この処理についての十分な評価は行っていない。
                   ;;
                   ((and (= 1 (length r)) ; 満たされなかったのは最後の分岐先のみ
                         (funcall bf-cmp)) ; 分岐関数は改善された
                    (setq bf-cmp (funcall bf-cmp :regenerate t))
                                        ; bf-cmp の基準を現在のパラメータ値に更新し、
                    (setq prev-value test-value))
                                        ; やり直す。
                   ;;
                   ;; 3. その他の場合
                   ;; 最後の分岐先より前で失敗したか、分岐関数が改善されなかった。
                   ;; この場合、移動幅を縮小して再度トライする。
                   ;; この縮小を繰り返していけば、いずれ prev-value と test-value
                   ;; が等しくなり、解検索ループを抜ける
                   (t (setf amount (truncate amount 2))))))
    ;;
    (cond (found t)     ; 解が発見された場合 t を返す
                        ; パラメータ値は *ongoing-constraint* に記録されている。
          (t            ; その他の場合は失敗で nil を返すが、
           (setf (get-target-init loc) old-value)
                        ; その前に破壊した *ongoing-constraint* のパラメータ値を元に戻す。
             nil))))

その他の手続き

その他の手続きとしては、以下のようなものがある。

lookup-targets
変更すべき入力値を列挙する。 この時、動的な依存解析を用いた絞り込みも行う。
generate-test-data
P言語デバッガの 'a' コマンドからのエントリポイントである。 デバッガから指定されたパスを突破するように、 run-generator を起動する。

実験結果

ここでは配列参照と繰り返しを含む、 P プログラムについてのテストデータ生成系のパフォーマンス測定結果を示す。 使用マシンのスペックは以下の通り。

  • CPU : Intel Core i7 860 @ 2.80GHz
  • Memory : 4GB
  • OS : ubuntu Linux 12.04 (kernel 3.2.0-38-generic) x86_64
  • 処理系 : Allegro CL 8.2 [64-bit Linux (x86-64)]

各表は、以下のように動的解析の援用度合を切り替え、同データで試験した。

N.
動的解析の絞り込みを使わず、素朴に全引数を調査対象とする
D.
動的な依存関係の解析を行い、調査対象の変数を絞り込む
R.
動的な依存関係の解析を行い、さらにリスクファクタの計算を行う1

各項目は以下の通り

  • size : 配列の大きさ
  • path : 与えたパスの長さ
  • ok/ng : テストデータを生成できたか
  • eval : 内部的に式の評価を行った回数
  • real : 実経過時間 (秒)
  • non-gc : GC以外のCPU時間 (秒)
  • gc : GCに使われたCPU時間 (秒)
  • total : CPU時間の合計 (秒)
  • cons : cons は使用されたコンス数
  • other mem : コンス以外に使用されたメモリのバイト数

korel1.p

Korel-90 の例。

 1:  /* [Korel-90] RequesedPath = 8 9 10 12 13  15  17 12 13  15 16 17 12  20 21 */
 2:  
 3:  korel1(int low, int high, int step, int[101] A) {
 4:    int min;
 5:    int max;
 6:    int i;
 7:  
 8:    min = A[low];          
 9:    max = A[low];          
10:    i = low + step;        
11:  
12:    while (i < high) {     
13:      if (max < A[i])      
14:        max = A[i];        
15:      if (min > A[i])      
16:        min = A[i];        
17:      i = i + step;        
18:    }
19:  
20:    println("min = ",min); 
21:    println("max = ",max); 
22:  }

リスクファクタの計算を行わない上側二つは、 配列参照のインデックスに関わる変数を先に変更してしまうため、答が得られない。

exploratory-move は今注目している条件式に関与する変数たちを探り出すもので、 それらを「積極的に」動かすようにする。

一方、リスクファクタの高い変数とは 今注目している条件式へ至るまでの途中の条件分岐に影響を与える危険な変数たちであり、 それらは「消極的に」動かすようにする。

これら二つの評価基準は互いに相補的な条件と考えられる。 この結果はリスクファクタの評価基準が必要であることを示している。

sizepathevalrealnon-gcgctotalconsother mem
N10015ng-------
D10015ng-------
R10015ok262000010,091101,328

korel2.p

1000要素の配列に、10要素ごとにアクセスし、min, max を取り出す。

 1:  /* [Korel-90] big array 
 2:     arguments are reordered following [korel-90] example.1 */
 3:  korel1(int[1001] A, int high) {
 4:    int min;
 5:    int max;
 6:    int i;
 7:    int step;
 8:    int low;
 9:  
10:    step = 10;
11:    low = 0;
12:  
13:    min = A[low];
14:    max = A[low];
15:    i = low + step;
16:  
17:    while (i < high) {
18:      if (max < A[i])
19:        max = A[i];
20:      if (min > A[i])
21:        min = A[i];
22:      i = i + step;
23:    }
24:  
25:    println("min = ",min);
26:    println("max = ",max);
27:  }

配列の先頭何個の要素を使用するかを切りかえて計測。

指定パスは、(10 11 13 14 15 17 18 19 20 22 17 18 19 20 22 17 18 19 20 22 17 18 19 20 22 17 18 19 20 22 17 18 19 20 22 17 18 19 20 22 17 18 19 20 22 17 18 19 20 22 17 25 26)

配列の無駄な要素を調査しない分、下側二つ (動的解析を施した) の方が早くなっている。

要素数pathevalrealnon-gcgctotalconsother mem
N08ok14,052000012,13616,172,656
1058ok272,6860.20.200.2100,18643,480,800
50258ok8,460,2605.15.005.0594,700396,960,064
100508ok57,474,79033.733.50.133.61,486,9191,386,681,312
D08ok44000014,27462,176
1058ok4,5540.10.100.1677,4041,194,864
50258ok137,0161.51.501.511,616,4948,529,584
100508ok747,1566.05.906.043,788,97323,714,256
R08ok44000015,28262,176
1058ok2,5050.10.100.1530,904988,048
50258ok84,0071.501.51.58,448,76613,194,640
100508ok534,8229.49.409.432,006,55656,952,864

bubble sort

 1:  /* Bubble sort */
 2:  
 3:  bubblesort(int[100] a, int size) {
 4:    int i;
 5:    int j;
 6:    int w;
 7:  
 8:    i = 0;                       
 9:    while (i < size-1) {         
10:      j = size-1;                
11:      while (j > i) {            
12:        if (a[j-1] > a[j]) {     
13:          w = a[j-1];            
14:          a[j-1] = a[j];         
15:          a[j] = w;              
16:        }
17:        j = j-1;                 
18:      }
19:      i = i+1;                   
20:    }
21:  
22:    println("SortedData:");      
23:    i = 0;                       
24:    while (i < size) {           
25:      println("a[",i,"]=",a[i]); 
26:      i = i + 1;                 
27:    }
28:  }

bubble sort において最も多くの手数が必要となる場合のパス、 つまり、降順に並べられた配列を昇順に並びかえる際のパスを指定する事で、 降順の配列をテストデータとして生成させる。

リスクファクタを用いるものについては、50要素以上のものはあまりに時間がかかるため、打ちきった。 リスクファクタの計算が重いため、動的な依存関係の解析のみを行うものが最も早くなっている。

先の例において、リスクファクタの評価は本質的であった。 一方でリスクファクタの計算は動的なデータ依存関係に基づいており、計算コストが高い。 簡単に言えば、その計算はプログラムの静的な構造ではなく、 実行時トレースに対してデータ依存解析を行うような処理である。 よって、バブルソートのように静的な構造は小さくとも、 動的なトレースが長くなると計算コストが非常に高くなってしまう。 この例は、検索の高速化のために行う解析自体のコストも考慮し、 全体としての効率化を考えなければならないことを示している。

sizepathevalrealnon-gcgctotalconsother mem
N05ok600002,86853,856
10341ok45,753000041,820161,984
201281ok1,370,9541101339,790732,096
302821ok10,182,60587071,433,9052,889,168
507701ok128,593,25782811829,958,65419,126,592
7014981ok686,133,709418413441737,114,13870,375,600
D05ok600002,85855,024
10341ok32,3560000354,720340,256
201281ok498,33211014,088,3012,752,368
302821ok2,417,968440417,419,79411,044,880
507701ok17,776,7143535035109,374,70866,517,120
7014981ok66,614,6121541521154373,827,637223,335,120
R05ok600002,85855,024
10341ok27,1020000961,8065,068,400
201281ok455,002232202317,627,597120,610,752
302821ok2,343,7025415380539103,910,7981,024,645,984
507701ok
7014981ok

デモ

正三角形

与えられた三角形が、 正三角形二等辺三角形それ以外 かを判定するプログラムに、 正三角形データを与えたとすれば通るパス を指定して、自動的に正三角形データを生成する。

バブルソート

バブルソートプログラムに 降順データを喰わせたとすれば通るパス を指定して、 自動的に降順データを生成する。

Footnotes:

1 前々回にも少し觸れたが、Korel 法では動的解析の過程で、 各変数が目的の条件式に至るまでの途中の条件式に影響を与える度合いを計算する。 例えば目的の条件式に至るまで 10 個の条件式があったとし、 変数 X はそれらの条件式のうち 5 つの条件に関連しているとする。 一方変数 Y はただ一つの条件式ににのみ関連しているとする。 このとき、直感的には変数 Y を動かしてみる方が、X よりも安全、 即ち、途中の結果を保存する、と考えられる。 このような観点から、変数のリスクファクタという概念を導入し (今の場合 X のリスクは 5, Y は 1)、 リスクファクタの小さい変数から優先的に動かす、というヒューリスティックを使っている。 実際には、目的の条件式へ至るパスは複数あるので、 それを全て考慮する必要があり、その計算は単純ではない。 リスクファクタの厳密な定義は korel-90a を参照されたい。

Author: Yokota Yuki

Date: 2013-10-02T17:03+0900

Generated by Org version N/A-fixup with Emacs version 24

© Mathematical Systems Inc. 2013