JPH0916389A - プログラム部品自動生成方法及び装置 - Google Patents

Abstract

(57)【要約】 【課題】 従来は、部品変更は変更を受けた箇所を特定
する操作と、要求に応じて実際に変更を施す操作を人手
で行わなければならないため、ソフトウェア開発者に対
して大きな負担が発生する。 【解決手段】 本発明は、仕様に応じてプログラム部品
案を生成する部品案生成手段２０と、生成されたプログ
ラム部品案を逐次整理保存し、かつ変更履歴を管理する
部品ライブラリ３０と、部品ライブラリ３０内に存在す
るプログラム部品がそれぞれもつ機能の一部を変換する
変換手段４０とを有し、検索要求に適合する新たな機能
を持つプログラム部品を生成する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、プログラム部品自
動生成方法及び装置に係り、特に、ソフトウェア開発時
において部品化されたプログラムを自動的に構築するた
めのプログラム部品自動生成方法及び装置に関する。

【０００２】

【従来の技術】従来は、手続き型プログラムのソースコ
ードを再利用の対象とする際には、組み立て技術という
再利用技術が適用される。最初に部品化再利用技術につ
いて説明する。

【０００３】手続き型のプログラムソースコードを再利
用対象とする組み立て技術という再利用技術では、部品
作成者が予めプログラム部品を作成し、部品ライブラリ
に登録しておく。ソフトウェア開発者は、部品ライブラ
リ内に存在する再利用部品を検索・合成することにより
目的のプログラムを作成する。

【０００４】組み立て技術による再利用工程を図２５に
示す。同図において、矢印は、プログラム部品に対する
操作の流れを示す。同図に示す構成は、部品作成部１、
部品ライブラリ２、部品検索部３、部品変更部４、部品
合成部５、及び目的のプログラム６よりなる。

【０００５】部品作成者が予めプログラム部品を作成
し、部品ライブラリ２に登録する。ソフトウェア開発者
は、部品ライブラリ２内に存在する再利用部品を検索、
変更、合成することで目的のプログラム６を作成する。
部品作成部１は、特定の機能を満たすのに必要なコード
を集め、実際に再利用されるソースコードをプログラム
部品として作成する。

【０００６】部品ライブラリ２は、プログラム部品を蓄
積する。部品検索部３は、部品ライブラリ２からソフト
ウェア開発者の要求する機能を満たすプログラム部品を
探す。また、検索時に要求を完全に満たすプログラム部
品だけでなく、その部品に近い類似部品も見つける。

【０００７】部品変更部４は、要求を完全に満たすプロ
グラム部品が見つからなかったとき、類似部品から要求
する部品を作成する。なお、プログラム部品を変更する
際には、変更箇所と変更方法を特定するために、その部
品がどのような機能をもつのかを理解する必要がある。

【０００８】部品合成部５は、部品検索や変更によって
得られたプログラム部品を組み合わせて、目的のプログ
ラム６を作成する。プログラム部品は単純に結合するだ
けではプログラムとしては実行不可能であるので、組み
合わせた後のプログラムに対しても変更が必要となる。

【０００９】このような再利用技術においては、プログ
ラム部品は理想的には、再利用時に変更されないという
性質を持つ。つまり、これらの部品は再利用前後で不変
であることが前提で利用される。しかし、ソフトウェア
開発者の要求は、多種多様であり、プログラム部品を単
独で再利用したり、単純に組み合わせるだけでは目的の
プログラムを作成することはできない。

【００１０】図２６、図２７にソースコードを再利用対
象としたプログラム部品の例を示す。図２６（ａ）に示
すプログラム部品Ａは、『入力されたテキストに対し
て、英字と数字の出現頻度を求める』機能を持つ部品で
あり、図２６（ｂ）のプログラム部品Ｂは、『入力され
たテキストに対して、英字とその他の文字の出現頻度を
求める』機能を持つ部品である。また、図２７に示すプ
ログラム部品Ｃは、『プログラム部品Ａに対して英字の
大文字と小文字を区別して出現頻度を求める』よう変更
を加えた部品である。図２７において、「＊」が付与さ
れている部分がプログラム部品Ａからプログラム部品Ｃ
に変更した際の変更コードである。

【００１１】組み立て技術では、図２６、図２７に示す
プログラム部品は単独で利用するか、単純に組み合わせ
て利用する。よって、部品ライブラリにプログラムＡ，
Ｂ，Ｃだけが存在する場合、『英字の大文字と小文字を
区別し、英字とその他の文字の出現頻度を求める』機能
を持つ部品を要求すると、部品検索は失敗する。このよ
うに従来は、ソフトウェア開発者がソースコードを適時
変更することが必要であり、変更部分を明確にする手段
が要求されている。また、部品に対する変更を抑えると
いう目的で再利用領域の特性を分析する手段も要求され
ているが、従来の技術でこの要求を満足に満たすものは
存在しない。

【００１２】

【発明が解決しようとする課題】上記のように従来の組
み立て技術による再利用では、プログラム部品の機能が
再利用前後で変化しないことが前提とされている。しか
し、プログラム部品を単純に結合するだけでは、実行可
能な目的のプログラムを得ることはできない。よって、
ソフトウェア開発者が組み合わせた後のプログラムを適
時変更する必要がある。部品変更は変更を受けた箇所を
特定する操作と、要求に応じて実際に変更を施す操作に
分けられる。従来は、これらの操作を人手で行わなけれ
ばならないため、ソフトウェア開発者に対して大きな負
担が発生する。

【００１３】また、ソフトウェア開発者が再利用を行う
環境は動的に変化し、それに応じてプログラム部品に対
する要求も多種多様に及ぶ。よって、再利用に必要なプ
ログラム部品を予め全て作成し、用意しておくことは不
可能である。また、要求するプログラム部品が部品ライ
ブラリに存在しないことは、部品検索の失敗を引起し、
再利用の効果を低下させる。そこで、部品作成者は、今
後利用される可能性の高いプログラム部品を推測して部
品を作成することになる。部品作成者にとって、どのよ
うなプログラム部品を用意しておくべきか推測すること
に費やす負担は大きい。

【００１４】さらに、用意するプログラム部品の数を無
意味に増加させることは、部品管理及び部品検索におい
て、保存領域や検索時間の増大を引き起こす。本発明
は、上記の点に鑑みなされたもので、ソフトウェア開発
者の再利用要求に対して、部品ライブラリ内に予め存在
するプログラム部品と異なる機能を持つ新規プログラム
部品を自動的に生成し、ソフトウェア開発者が部品を変
更する負担や部品作成者が必要な部品を推測する負担を
軽減することが可能なプログラム部品自動作成方法及び
装置を提供することを目的とする。

【００１５】

【課題を解決するための手段】図１は、本発明の原理を
説明するための図である。本発明は、プログラム部品に
修正があった場合に、変更箇所及び内容を随時データベ
ース化し、新規プログラム部品を作成する場合には、デ
ータベースから同様な機能をもつ類似の変更事例を検索
し、同様な機能が得られた場合には、該当機能を既存の
プログラム部品の機能から補填することにより、既存の
プログラム部品ライブラリから新規のプログラム部品を
生成する。

【００１６】また、本発明は、プログラムのソースコー
ドをグラフに変換するグラフ化ステップ（ステップ１）
と、プログラムのソースコードをソースコードの依存関
係を用いて分割するスライシングステップ（ステップ
２）と、希望する機能のソースコードに関して、過去に
類似のソースコード変更履歴があるかを検索する履歴検
索ステップ（ステップ３）と、変更履歴をもつ既存のプ
ログラムのソースコードを表すグラフと、希望する機能
のソースコードのもつグラフが同一か否かを判定する同
型写像比較ステップ（ステップ４）と、両グラフが同一
グラフ形状を有した場合は、既存のプログラムのソース
コードから同一の部品機能を自動補填する補填ステップ
（ステップ５）よりなる。

【００１７】また、本発明では、ソースコードの依存関
係は、ソースコードにおける代入文及び条件式を割り当
てた節点の集合及び、各節点間の参照・非参照関係を表
す矢印からなるグラフを利用して表現する。また、本発
明では、同型写像比較ステップ（ステップ４）は、グラ
フにおける各節点に割当られた代入文及び条件式が内包
する変数を抽象化し、一方のグラフの節点と矢印を他方
のグラフに写像したとき、依存関係の種類及び属性を含
む節点の接続関係と抽象化したラベルが完全に等価であ
るか否かによりグラフ間の比較を行う。

【００１８】図２は、本発明の原理構成図である。本発
明のプログラム部品自動生成装置は、仕様に応じてプロ
グラム部品案を生成する部品案生成手段２０と、生成さ
れたプログラム部品案を逐次整理保存し、かつ変更履歴
を管理する部品ライブラリ３０と、部品ライブラリ３０
内に存在するプログラム部品がそれぞれもつ機能の一部
を変換する変換手段４０とを有し、検索要求に適合する
新たな機能を持つプログラム部品を生成する。

【００１９】また、上記の変換手段４０は、部品ライブ
ラリから過去に同型の写像をもつ部品ならびに変更履歴
があるか否かを検索する部品検索手段４１と、同型の写
像を持つ部品があった場合は該当部品を使って新たな部
品を合成する部品合成手段４２と、部品に部分変更があ
った場合は、部品検索手段により検索された部品ならび
に変更履歴を利用して部品ライブライリの内容を更新す
る部品更新手段４３とを有する。

【００２０】また、上記の変換手段４０は、部品検索手
段４１により部品ライブラリ内のプログラム部品の変更
を検出すると、プログラムのソースコード依存関係によ
って分割するプログラムスライシング手段と、グラフの
同型写像比較により変更の影響箇所を含むソースコード
を特定し、部品変更事例として前記部品ライブラリ３０
に蓄積するソースコード特定手段とを含む。

【００２１】また、上記の部品更新手段４３は、過去に
変更を受けたプログラム部品と機能の一部を共有するプ
ログラム部品をグラフの同型写像比較により特定し、部
品変更事例を適用して部品の一部の機能を交換する交換
手段を有する。

【００２２】一般に、プログラム部品の受けた変更の事
例を別の部品に単純に適用することは不可能であり、従
来の方法だけで新たな機能を持つプログラム部品を生成
することは難しい。本発明では、ソースコードをプログ
ラム・スライシングによって細かく分割することが特徴
である。スライシングは、部品変更事例を蓄積する際の
変更前後のソースコードを比較する前、及び部品変更事
例を別のソースコードに適用することでコードを変換す
る前に実行される。これにより、各ソースコード断片毎
に機能交換の適用が可能となり、新規プログラム部品が
生成可能となる。

【００２３】さらに、本発明では、細かく分割したソー
スレコード断片を１つのソースコードに合成及び再構成
する操作を行う。これにより、再利用の要求が生じた際
に動的にかつ自動的にプログラム部品を生成し、ソフト
ウェア開発者に提供可能となる。

【００２４】また、本発明は、変更箇所を特定する手段
を用いることにより、過去の部品変更の変更差異が形式
的に部品変更を含む変更前後のソースコードの断片の対
（交換可能スライス対）で記録できる。また、交換可能
スライス対を用いることで直接変更を受けたことがない
プログラム部品が他のプログラム部品の変更を模倣する
ことができる。従って、これらの２つの手段を組み合わ
せて適用することにより、部品ライブラリに存在しない
プログラム部品を新たに自動生成することが可能であ
る。さらに、区間を限定して作成した区間限定スライス
を変更差異、交換及び合成対象の単位とすることで、区
間限定スライスを作成する際に着目する変数に関して依
存関係を壊さずに、新規のプログラム部品が生成でき
る。つまり、新たに生成されたプログラム部品は、元の
プログラム部品の一部の機能に関して実行結果を保証す
る。

【００２５】

【発明の実施の形態】本発明は、過去の部品変更事例を
部品ライブラリに蓄積しておき、既存の部品ライブラリ
内に存在するプログラム部品がそれぞれ持つ機能の一部
を交換することにより、検索要求に適合する新たな機能
を持つプログラム部品を生成するものである。

【００２６】以下の説明に先立って、前提となる事柄を
説明する。本発明で扱うプログラムは、一般手続き型プ
ログラムのコードであり、プログラム・スライシングが
適用可能であることが前提となる。 ・プログラム部品とは、再利用対象となる部品の機能を
実現するソースコードを指す。これらのプログラム部品
をデータとして集めてメモリに保存したデータベースが
部品ライブラリである。

【００２７】・プログラム・スライシングとは、指定し
た変数に関してソースコードを依存関係に基づき細かく
分割することを指す。 ・機能とは、ソースコード内に表れる変数の値を決定す
る計算を指す。これは、変数の値を決定するのに必要な
コードをプログラム・スライシングによって集めたもの
である。

【００２８】・グラフの同型写像比較とは、２つのグラ
フにおいて、一方のグラフの節点及び矢印を他方のグラ
フに写像することで、同型かどうか判断することを指
す。節点の接続関係が完全に一致するとき、２つのグラ
フは同型であるという。 ・部品変更事例とは、あるプログラム部品に対して部品
利用者が変更を与えたときの、変更前後のソースコード
の差異を指す。本発明では、ソースコードをグラフに変
換し、グラフの同型写像比較を行うことで、変更前後の
ソースコードの差異を求める。

【００２９】・プログラム部品に対する機能の交換と
は、プログラム部品の機能を担うコードを別のコードに
置き換えることを指す。本発明は、以下の２つの処理に
より新規プログラム部品を自動生成する。 部品ライブラリ内のプログラム部品が変更を受けた
際、プログラム・スライシングにより変更前後のソース
レコードを分割し、グラフの同型写像比較により変更の
影響箇所を含むコードを特定し、部品変更事例として蓄
積する。

【００３０】 過去に変更を受けたプログラム部品と
機能の一部を共有する部品をグラフの同型写像比較によ
り特定し、部品変更事例を適用して一部の機能を交換す
ることで新たな機能を持つプログラム部品を自動生成す
る。以下に、本発明で用いる手法を説明する。

【００３１】（１） 制御フローグラフ 次に、プログラムの依存関係の解析用の制御フローグラ
フを用いる場合について説明する。本発明では、プログ
ラムの依存関係を解析するために、制御フローグラフ
（ＣＦＧ）を導入する。制御フローグラフＧ_CFG ＝（Ｎ
_CFG ，Ｆ_CFG ，start ）は、基本ブロックと呼ぶ節点の
集合Ｎ_CFG ，基本ブロック間の制御の流れを表す矢印の
集合Ｅ_CFG からなる有向グラフである。ここでは、基本
ブロックにソースコードの代入文や条件式を割り当て
る。また、制御フローグラフは、プログラムを実行する
時に最初に制御が移される開始節点start と制御が移る
先を持たない停止節点stopが必ず１つずつ存在する。制
御フローグラフにおいて、節点ｐから節点ｑへの矢印の
存在は、節点ｐの命令を実行した後、プログラム制御が
直ちに節点ｑに移る可能性があることを指す。このと
き、節点ｐは節点ｑの直接先行（predecessor)、節点ｐ
は節点ｑの直接後行（successor ）と呼ぶ。

【００３２】制御フローグラフは、プログラムの制御の
流れを静的に解析することで得られる。制御フローグラ
フを用いることで、ソースコードは逐次実行（連接構
造：sequence）、条件分岐（選択構造：selection ）、
繰り返し（反復構造：iteration ）の３つで表現され
る。

【００３３】図２６（ａ）のプログラム部品Ａを制御フ
ローグラフで表したものを図３に示す。各節点には、節
点を識別するための順序関係を持つ節点番号（ａ１，ａ
２，…，ａ１１）を割り当てる。また、節点の横に記述
されているラベル（例えば、ａ１: alphabet＝０）は、
節点が表す基本ブロックにおける代入文及び条件文であ
る。

【００３４】（２） 制約付き到達可能経路 制御フローグラフにおいて、２つの節点間の到達可能性
を判断するために、到達可能経路（Reachable Path）を
導入する。いま、節点ｎ_u から節点ｎ_h にプログラム制
御が流れる向きに経路をたどるとき、通過する節点の集
合を到達可能経路ＲＰ（ｎ_u ，ｎ_h ）と表す。節点ｎ_u
から節点ｎ_h に到達する経路が存在しないとき、ＲＰ
（ｎ_u ，ｎ_h ）＝φ（空集合）である。

【００３５】また、本発明では、ソースコード内部の任
意の断片をプログラム・スライシングの対象とするため
に、制御フローグラフを辿る際に、制約を付けた制約付
き到達可能経路（ＣＲＰ：Constrainted Reachable Pat
h)を導入する。いま、制御フローグラフにおいて、上限
節点ｎ_u から下限節点ｕ_h に上限節点ｎ_u を中間節点と
して通らずプログラム制御の流れの向きに経路を辿ると
き通過する節点の集合をＣＲＰ_f （ｎ_u ，ｎ_h ）、下限
節点ｎ_h から上限節点ｎ_u に下限節点ｎ_h を中間節点と
して通らずプログラム制御の流れと反対の向きに経路を
辿るとき通過する節点の集合をＣＲＰ_b （ｎ_u ，ｎ_h ）
とする。このとき、制約付き到達可能経路ＣＲＰ
（ｎ_u ，ｎ_h ）は、ＣＲＰ_f （ｎ_u ，ｎ_h ）とＣＲＰ_b
（ｎ_u ，ｎ_h ）の和集合をとることで求める。

【００３６】このように制約付き到達可能経路を導入す
ることで、上限節点や下限節点が条件文や繰り返し文の
内部にあるのか、外部にあるのかを意識せずにスライシ
ングの対象区間を指定することが可能である。 （３） プログラム依存グラフ プログラム・スライシングを実行するため、及びプログ
ラム・スライシングによって作成したソースコードの断
片を合成するために、プログラム依存グラフ（ＰＤＧ）
を導入する。プログラム依存グラフＧ_PDG ＝（Ｎ_PDG ，
Ｅ_PDG ，entry）は、ソースコードにおける代入文や条
件式を割り当てた節点の集合Ｎ_PDG （＝Ｎ_CFG ）、各節
点間の依存を表す矢印の集合Ｅ_PDG からなる有向グラフ
である。プログラム依存グラフには、どの節点からも依
存を受けない入口節点entry （＝start ）が存在する。
節点ｐから節点ｑへの矢印は、以下に示す依存関係のど
ちらか一方を表す。

【００３７】・制御依存（control dependence） 節点ｐの文ｓ１は、条件分岐文（ｉｆ文）か繰り返し文
（ｗｈｉｌｅ文）であり、文ｓ２を実行するかどうかが
文ｓ１の実行結果に直接依存する場合、節点ｐから節点
ｑに制御依存があるという。

【００３８】・データ依存（data dependence/flow dep
endence) 節点ｐの文ｓ１における、ある変数ｖの定義が、変数ｖ
を参照する文ｓ２を持つ節点ｑに到達する場合、節点ｐ
から節点ｑにデータ依存があるという。即ち、 １）文ｓ１において変数ｖの値を定義し、かつ、 ２）文ｓ２において変数ｖの値を参照している、かつ ３）変数ｖの値を再定義しない文ｓ１から文ｓ２への実
行可能な経路が存在するときにデータ依存を持つ。

【００３９】プログラム依存グラフは、上記の２つの依
存関係をプログラムに対して静的に解析することで作成
可能である。プログラム部品Ａの制御フローグラフ（図
３）をプログラム依存グラフで表したものを図４に示
す。図４において、一点鎖線矢印は制御依存を、実線矢
印はデータ依存を表す。プログラム依存グラフと制御フ
ローグラフにおいて、同じ識別番号を持つ節点は割り当
てられている代入文及び条件文が等しい。

【００４０】また、プログラム依存グラフには直接明記
しないが、プログラム依存グラフから制御フローグラフ
を再構成する際に、以下に示す出力依存を利用する。 ・出力依存（output dependence) 節点ｐの文ｓ１における、ある変数ｖの定義が同じ変数
ｖを定義する文ｓ２を持つ節点ｑに到達する場合、節点
ｐから節点ｑに出力依存があるという、即ち、 １）文ｓ１において変数ｖの値を定義し、かつ ２）文ｓ２において変数ｖの値を定義している、かつ ３）変数ｖの値を再定義しない文ｓ１から文ｓ２への実
行可能な経路が存在するときに、出力依存を持つ。

【００４１】（４） プログラム依存グラフの同型 ソースコードの一部を変換するために、２つのプログラ
ム依存グラフをラベル付き同型写像により比較する。ラ
ベルとは、各節点に割り当てられた代入文と条件式内の
変数を抽象化したものを指す。グラフの形、つまり、一
方のグラフの節点と矢印を他方のグラフに写像し（同型
写像）、依存の種類及び属性を含む節点の接続関係と抽
象化したラベルが完全に等価であるとき、２つのグラフ
は一致するという。図５に、ラベル付き同型写像比較に
よってプログラム依存グラフが一致する例を示す。図５
において、一点鎖線矢印（ｃ_i ）は制御依存、（ｄ_j ）
は、データ依存を表す。

【００４２】（５） プログラム・スライシング ソースコードを機能毎に分割するために、プログラム・
スライシングを導入する。ここで、機能とは、変数の値
を決定する計算を指す。プログラム・スライシングと
は、着目する変数に影響を与える一部のコードだけをも
とのソースコードから抜き出すことである。プログラム
・スライシングによって作成されたソースコードの断片
をスライスと呼ぶ。節点ｎにおける文ｓの変数ｖに関す
る静的スライスは、プログラム依存グラフにおける制御
依存関係及びデータ依存関係を辿り、文ｓの変数ｖに到
達するすべての節点の集合である。これは、文ｓの変数
ｖから制御及びデータ依存関係をプログラム制御の流れ
る向きと反対（プログラム依存グラフにおいて矢印を逆
向き）に辿ることで得られる。ここで、節点ｎにおける
文の変数ｖに関する静的逆方法スライスをＳ（ｎ，ｖ）
と表す。この静的逆方向スライスＳ（ｎ，ｖ）は、節点
ｎにおける文の変数ｖの実行結果を保存する完全なプロ
グラムを構成する。つまり、静的スライスにおいて節点
ｎの文の変数ｖの値は、もとのソースコードにおける節
点ｎの文の変数ｖの値と等価であることが保証される。

【００４３】本発明では、制約付き到達可能経路を用い
ることで、静的逆方向スライスに対象区間の制限を与え
ることが可能な区間限定スライスを導入する。区間限定
スライスとは、もとのプログラムの指定した区間におい
て、依存関係を辿る際に通過する節点を集めたものであ
る。区間限定スライスを作成するためには、着目する区
間と変数を同時に指定する。これは、スライシング基準 Ｃ_c ＝＜ｎ_u ，ｎ_h ，ｖ＞ で表現され、作成される区間限定スライスは、 Ｓ^# （ｎ_u ，ｎ_h ，ｖ） となる。ここで、ｎ_u ，ｎ_h は区間を表す節点で、これ
らの節点で決定される制約付き到達可能経路がプログラ
ム・スライシングの対象区間である。

【００４４】図６は、プログラム部品Ａから作成される
区間限定スライスの例を示す。同図（ａ）は制約付き到
達可能経路、（ｂ）はプログラム依存グラフ、（ｃ）は
制御フローグラフ、（ｄ）はソースコードを示す。同図
（ａ）においてａ３を上限節点、ａ７を下限節点とい
う。同図に示す区間限定スライスは、 Ｓ^# （ａ３，ａ７，｛alphabet｝） を示す。

【００４５】さらに、本発明では、スライスの合成を行
うために補スライスを導入する。補スライスＳ^* （ｎ，
ｖ）とは、もとのソースコードから静的逆方向スライス
Ｓ（ｎ，ｖ）を取り除いたものである。さらに、区間限
定スライスについても静的逆方向スライスと同様に、区
間限定補スライスを導入する。区間限定補スライスは指
定された区間に含まれる節点集合ＣＲＰ（ｎ_u ，ｎ_h ）
の要素から区間限定スライスＳ^# （ｎ_u ，ｎ_h ，ｖ）の
要素を取り除くことで作成する。

【００４６】図７は、区間限定補スライスの例を示す。
同図は、プログラム部品Ａの区間限定補スライスを示し
ており、（ａ）はプログラム依存グラフ、（ｂ）は制御
フローを示す。同図は、プログラム部品Ａの区間限定ス
ライス（図６）に対する区間限定補スライス Ｓ^#*（ａ３，ａ７，｛alphabet｝) を示す。

【００４７】ここで、補スライスだけでは完全なプログ
ラム依存グラフ及び制御フローグラフが形成できないた
め、ヌル節点を導入する。ヌル節点とは、節点の実行前
後でプログラムの状態を変化させない節点である。図７
において、点線節点はヌル節点、実線節点は区間限定補
スライスＳ^#*（ａ３，ａ７，｛alphabet｝）を表す。

【００４８】

【実施例】以下に、本発明の実施例を説明する。図８
は、本発明の一実施例の部品化再利用によるプログラム
作成装置の構成を示す。同図において、図２５と同一部
分には、同一符号を付しその説明を省略する。

【００４９】部品化再利用によるプログラム作成装置１
０は、部品生成部１１０、部品ライブラリ１２０、部品
検索部３、部品変更部１３０及び部品合成部５より構成
される。部品ライブラリ１２０は、部品作成部１より提
供された特定の機能を満たすのに必要なコードを集め、
実際に再利用されるソースコードをプログラム部品及び
過去に行われた変更事例をデータとし、それらを纏めて
保持するデータベースである。また、プログラム部品の
みならず、変更事例に対しても追加、削除の操作が可能
である。

【００５０】部品生成部１１０は、変更事例を用いるこ
とにより新規再利用部品を生成する。内部の詳細につい
ては後述する。部品変更部１３０は、部品の変更操作に
ついては従来の動作と同様であるが、変更前後の再利用
部品を対応付けて記録する。この記録された内容は、部
品生成部１１０の入力となる。

【００５１】図８において、一点鎖線で囲まれている部
品自動生成装置１００は、部品生成部１１０と部品ライ
ブラリ１２０から構成される。以下に、部品自動生成装
置１００について説明する。図９は、本発明の一実施例
の部品自動生成装置の概要を示す。部品生成装置１００
の部品生成部１１０は、交換可能スライス対特定部１１
１、スライス作成部１１２、スライス置換部１１３、ス
ライス合成部１１４、スライス再構成部１１５より構成
される。

【００５２】なお、本発明の部品ライブラリ１２０や、
部品変更部１３０より入力されるプログラム部品とは、
ソースコードであり、逐次実行、条件分岐、繰り返しの
みの良構造であるとする。良構造とは、条件分岐や繰り
返しのネストに交差がないことを指す。

【００５３】部品ライブラリ１２０に格納される変更事
例は、変更前後のプログラム部品で変更差異を含む区間
限定スライスの対、つまり、部品変更時に、交換可能な
スライス対を記録したものである。交換可能スライス対
特定部１１１は、変更前後の区間限定補スライスを同型
写像により比較することで、変更前後で影響を受けた範
囲を特定し、変更事例として部品ライブラリ１２０に記
録する。

【００５４】スライス作成部１１２は、与えられたソー
スコードを分割し、区間限定スライス及び区間限定補ス
ライスを作成する。スライス置換部１１３は、過去に変
更を直接受けていないプログラム部品から作成した区間
限定スライスと変更事例に含まれる変更後の区間限定ス
ライスを交換する。この処理は、交換対象の区間限定ス
ライスの節点の対応関係に基づいて、プログラム部品の
節点の一部を入れ換えることで達成される。

【００５５】スライス合成部１１４は、交換対象の区間
限定スライスに対する節点の対応関係により、接続元及
び接続先が決定していない矢印を接続する。この処理に
より、交換前の区間限定補スライスと交換後の区間限定
スライスが合成され、新規プログラム部品のプログラム
依存グラフが生成される。

【００５６】スライス再構成部１１５は、新たに生成さ
れたプログラム依存グラフから、前述の制御フローグラ
フを作成し、新規プログラム部品のソースコードを再構
成する。以下に、過去にソフトウェア開発者によって行
われた部品変更箇所を交換可能スライス対特定部１１１
により特定し、変更事例を部品ライブラリ１２０に記録
する処理と、変更事例を用いて、スライス置換部１１
３、スライス合成部１１４、スライス再構成部１１５に
より区間限定スライス同士の交換、合成、再構成を行う
ことでプログラム部品の機能の一部を交換する処理を説
明する。

【００５７】［変更箇所の特定］まず、交換可能スライ
ス対特定部１１１の変更箇所の特定処理について説明す
る。部品ライブラリ１２０内のプログラム部品は部品合
成前及び合成時に数々の変更を受ける。そこで、過去に
おける部品変更は類似するプログラム部品に対しても将
来行われる可能性が高いと判断し、新規部品を自動生成
するために部品変更事例を記録する。プログラム部品が
変更された際の変更誤差の特定に、スライシングを適用
し、区間限定補スライス同士の同型写像比較を用いるの
が特徴である。本発明では、これにより特定された２つ
のスライスを交換可能スライスと呼ぶ。

【００５８】プログラム部品Ｐをプログラム部品Ｑに変
更したときの、変更箇所を特定する処理手順を以下に示
す。部品化再利用によるプログラム作成装置１０におけ
る処理は、プログラム部品Ｐ（図９）（部品ライブラリ
１２０）→部品検索部３→部品変更部１３０→プログラ
ム部品Ｑ→交換可能スライス対特定部１１１→変更事例
（部品ライブラリ１２０）の順に実行される。

【００５９】図１０は、本発明の一実施例の変更箇所の
特定手順を示すフローチャートである。 ステップ１１０） 変更前後のソースコードＰ，Ｑに対
して、それぞれ入力節点集合Ｎ_Pi，Ｎ_Qi及び出力節点集
合Ｎ_Po，Ｎ_Qoを求める。また、ソースコードＰ，Ｑ内に
それぞれ含まれる変数のベキ集合（ρ：power set)
Ｖ_P ，Ｖ_Q を求める。ここで、入力節点とはプログラム
依存グラフにおいてentry 節点に接続されている節点，
出力節点はどの矢印の接続元にもならない節点である。

【００６０】ステップ１２０） すべての入出力節点及
び変数集合の各要素の組合せに対してステップ１３０か
らステップ１９０を繰り返す。 ステップ１３０） プログラム部品Ｐ，Ｑに対してそれ
ぞれスライシング基準〈ｎ_Pi，ｎ_Po，ｖ_P 〉，〈ｎ_Qi，
ｎ_Qo，ｖ_Q 〉でスライシングを適用し、区間限定スライ
スＳ_P ，Ｓ_Q と区間限定補スライスＳ ^* _P ，Ｓ ^* _Q を作
成する。

【００６１】ここで、ｎ_Pi∈Ｎ_Pi，ｎ_Po∈Ｎ_Po，ｎ_Qi∈
Ｎ_Qi，ｎ_Qo∈Ｎ_Qoである。 ステップ１４０） 各区間限定スライス及び区間限定補
スライスをプログラム依存グラフに変換する（Ｓ_P →Ｇ
_P ，Ｓ ^* _P →Ｇ ^* _P ，Ｓ_Q →Ｇ_Q ，Ｓ ^* _Q →Ｇ ^* _Q ）。

【００６２】ステップ１５０） プログラム依存グラフ
において、区間限定補スライスは不必要な矢印を含むの
で、区間限定補スライスＧ ^* _P ，Ｇ ^* _Q を以下のように
変形する。 （Ｇ ^* _P →Ｇ ^* _P ′，Ｇ ^* _Q →Ｇ ^* _Q ′） ステップ１６０） 変形後の区間限定補スライス
Ｇ ^* _P ′，Ｇ ^* _Q ′同士のラベル付き同型写像による比
較を行なう。

【００６３】ステップ１７０） 変更箇所を含む変更前
後で影響を受けた範囲を特定する。同型写像比較により
２つの区間限定補スライスが一致、かつ、それらの節点
集合が空集合でない（Ｇ ^* _P ′＝Ｇ ^* _Q ′≠φ）のと
き、それぞれの区間限定補スライスＧ ^* _P ′，Ｇ ^* _Q ′
に対する２つの区間限定スライスの対〈Ｇ_P ，Ｇ_Q 〉を
交換可能スライス対と定義する。

【００６４】ステップ１８０） 変更前後のプログラム
部品Ｐ，Ｑから他の区間限定スライス （Ｇ_Pv，Ｇ_Qv） を作成し、交換可能スライス対に包含される区間限定ス
ライス同士 （Ｇ_Pv⊆Ｇ_P ，Ｇ_Qv⊆Ｇ_Q ） の同型写像比較により、交換可能スライス対の２つの区
間限定スライスにおける節点の対応を決定する。

【００６５】ステップ１９０） 節点の対応関係を持つ
交換可能スライス対 〈Ｇ_P ，Ｇ_Q 〉 を部品ライブラリ１２０に記録する。区間限定補スライ
スの変形手順は以下のようになる。

【００６６】図１１は、本発明の一実施例の区間限定補
スライス変形処理の手順を示すフローチャートである。 ステップ１５１） すべての矢印に対して、ステップ１
５１〜ステップ１５３の処理を繰り返す。すべての矢印
の処理が終了したら、ステップ１５４に移行する。

【００６７】ステップ１５２） 矢印の接続元及び接続
先節点の節点についてラベルを持つかどうか検査する。
矢印を検査する際、entry 節点はラベルを持つ節点とみ
なす。ラベルを持つ場合には、ステップ１５１に移行
し、ラベルを持たない場合には、ステップ１５３に移行
する。

【００６８】ステップ１５３） 接続元及び接続先節点
のどちらかがラベルを持たない節点のとき、その矢印を
削除する。ステップ１５１に移行する。 ステップ１５４） すべての節点に対して、ステップ１
５４〜ステップ１５６の処理を繰り返す。

【００６９】ステップ１５５） 節点が矢印を持つかど
うかを検査して、持たない場合にはステップ１５６に移
行し、持つ場合にはステップ１５４に移行する。 ステップ１５６） 節点が矢印を一つも持たないとき、
その節点を削除する。 ［機能の一部交換処理］次に、機能の一部交換の処理に
ついて説明する。

【００７０】上記の変更箇所の特定処理によって得た交
換可能スライス対を用いることで、区間限定スライス同
士を実際に交換し、交換後の区間限定スライスと交換前
の区間限定補スライスを合成する。従来のテキストにお
ける行単位での交換や関数単位での交換と異なり、再利
用部品の機能に着目し、区間限定スライスを単位として
交換を行なうことで交換差異を別の部品に適用する点が
特徴である。

【００７１】プログラム部品Ｐ，Ｑから作成した交換可
能スライス対〈Ｇ_P ，Ｇ_Q 〉を用いて、部品ライブラリ
１２０内に存在するプログラム部品Ｒから新規プログラ
ム部品を生成するときの機能交換の処理手順を以下に示
す。図９に示す部品自動生成装置においてその動作は次
の順序で実行される。

【００７２】変更事例とプログラム部品Ｒ（部品ライブ
ラリ１２０）→スライス置換部１１３→スライス合成部
１１４→スライス再構成部１１５→部品検索部３。図１
２は、本発明の機能交換処理の手順を示すフローチャー
トである。 ステップ２００） 交換可能スライス対を用いて、ソー
スコードＲにおけるスライスＧ_R を交換可能スライス対
の変更後の区間限定スライスＧ_Q に置換する。置換後の
プログラム依存グラフをＰＤＧ_R ''' とする。

【００７３】ステップ３００） 置換後のプログラム依
存グラフＰＤＧ_R ''' において接続先及び接続元を決定
し、区間限定スライスＧ_Q と区間限定補スライスＧ ^* _R
を合成する。合成によって生成されたプログラム依存グ
ラフをＰＤＧ_new とする。ここで、区間限定補スライス
Ｇ ^* _R は、区間限定スライスＳ_R に対する区間限定補ス
ライスＳ ^* _R をプログラム依存グラフに変換したもので
ある。

【００７４】ステップ４００）プログラム依存グラフＰ
ＤＧ_new から、制御フローグラフＣＦＧ_new を生成し、
新規プログラム部品Ｒ’を再構成する。区間限定スライ
スＧ_R とＧ_P の置換手順（ステップ２００）は以下のよ
うになる。図１３は、本発明の一実施例の置換処理の手
順を示すフローチャートである。

【００７５】ステップ２１０） ソースコードＲに対し
て、入力節点集合Ｎ_Ri及び出力節点集合Ｎ_Roを求める。
また、ソースコードＲに含まれる変数のベキ集合Ｖ_R を
求める。 ステップ２２０） すべての入出力節点及び変数集合の
各要素の組合せに対して、ステップ２３０〜ステップ２
９０を繰り返す。

【００７６】ステップ２３０） プログラム部品Ｒに対
してスライシング基準〈ｎ_Ri，ｎ_Ro，ｖ_R 〉でスライシ
ングを適用し、区間限定スライスＳ_R を作成する。ここ
で、ｎ_Ri∈Ｎ_Ri，ｎ_Ro∈Ｎ_Ro，ｖ_R ∈Ｖ_R である。 ステップ２４０） 区間限定スライスをプログラム依存
グラフに変換する（Ｓ _R →Ｇ_R ）。

【００７７】ステップ２５０） 前述の変更箇所の特定
処理により記録された交換可能スライス対〈Ｇ_P ，
Ｇ_Q 〉の変更前の区間限定スライスＧ_P と区間限定スラ
イスＧ_R同士のラベル付き同型写像による比較を行な
う。不一致の場合にはステップ２２０に移行し、一致す
る場合にはステップ２６０に移行する。

【００７８】ステップ２６０）同型写像比較により２つ
の区間限定スライスが一致する（Ｇ _P ＝Ｇ_R ）とき、区
間限定スライスＳ_R に対する区間限定補スライスＳ ^* _R
を作成し、プログラム依存グラフに変換する（Ｓ ^* _R →
Ｇ ^* _R ）。 ステップ２７０） Ｇ_P とＧ_R の同型写像比較の際の節
点の対応関係により、ソースコードＲのプログラム依存
グラフＰＤＧ_R におけるＧ_R をＧ_P に置き換える。置き
換え後のプログラム依存グラフＰＤＧ_R ’はＧ_P とＧ_R
が混合された形となる。

【００７９】ステップ２８０） 交換可能スライスＧ_P
とＧ_Q の節点の対応関係により、置き換え後のプログラ
ム依存グラフＰＤＧ_R ’内部でＧ_P の節点の一部を対応
するＧ_Q の節点に置き換える。置き換え後のプログラム
依存グラフＰＤＧ_R ”は、Ｇ _Q とＧ_R が混合された形と
なる。

【００８０】ステップ２９０） 置き換えられた一部の
節点を錨節点（anchor vertex)とし、Ｇ_Q をＰＤＧ_R ”
に投射する。投射とは、錨節点から接続をたどり、ＰＤ
Ｇ_R”上にＧ_Q を構築することを指す。投射により生成
されるプログラム依存グラフＰＤＧ_R ''' は、Ｇ_Q とＧ
^* _R が混合された形となる。

【００８１】次に、区間限定スライスＧ_Q と区間限定補
スライスＧ ^* _R の合成手順を示す。図１４は、本発明の
一実施例の合成処理の手順を示すフローチャートであ
る。 ステップ３１０） プログラム依存グラフＰＤＧ_R にお
いて、接続元を持たない制御依存を表すすべての矢印に
対して、ステップ３２０〜３７０を繰り返す。

【００８２】ステップ３２０） 条件分岐の領域を表す
領域節点（region vertex)を接続先に持つ矢印である場
合には、ステップ３３０に移行し、それ以外の矢印の場
合にはステップ３４０に移行する。 ステップ３３０） 条件分岐の領域を表す領域節点（re
gion vertex)を接続先に持つ矢印は、条件分岐文を持つ
節点に接続する。

【００８３】ステップ３４０） 繰り返しの領域を表す
領域節点を接続先に持つ矢印の場合にはステップ３５０
に移行し、それ以外の矢印の場合にはステップ３６０に
移行する。 ステップ３５０） 繰り返しの領域を表す領域節点を接
続先に持つ矢印の場合は、繰り返し文及び条件分岐文を
持つ節点に接続する。

【００８４】ステップ３６０） 領域節点を接続先に持
たない矢印の場合には、ステップ３７０に移行し、それ
以外であればステップ３１０に移行する。 ステップ３７０） 領域節点を接続先に持たない矢印の
場合には、entry 節点に接続する。

【００８５】上記の合成手順を行なうことで、区間限定
スライスＧ_Q と区間限定補スライスＧ ^* _R からプログラ
ム依存グラフＰＤＧ_new が得られる。このプログラム依
存グラフＰＤＧ_new を制御フローグラフに変換するため
の、区間限定スライスの再構成手順を以下に示す。区間
限定スライスの再構成は、Ｓ_Q にＧ ^* _R に存在する節点
を挿入することで達成する。

【００８６】図１５は、本発明の一実施例の再構成処理
の手順を示すフローチャートである。 ステップ４１０） 区間限定補スライスＧ ^* _R に存在す
るすべての節点Ｎに対して、挿入範囲集合 Insert(n), Insert(join(n)) (ｎ∈Ｎ） が変化しなくなるまで、ステップ４２０〜ステップ４４
０を繰り返す。挿入範囲集合Insert(n) とは、節点ｎを
途中に挿入可能な矢印の集合を表す。また、join(n) と
は条件分岐節点ｎの分岐の枝となる区間を限定するため
の合流節点を指す。

【００８７】ステップ４２０） 挿入する節点ｎを接続
元及び接続先とする矢印に着目し、次に示す再構成操作
ａ〜ｆに対して、節点ｎの挿入範囲集合Insert_k (n) を
決定する。再構成操作ａ〜ｆが適用可能な矢印が存在し
ない場合、また矢印の接続元及び接続先節点の挿入位置
が未決定な場合、挿入範囲集合 Insert_k (n) ＝ＰＲ（start,stop) である。また、節点ｎが条件分岐節点のときは、再構成
操作ａ〜ｆによって Insert_k (join(n)) も同時に決定する。

【００８８】ステップ４３０） 各挿入範囲集合Insert
_k (n) ，Insert_k (join(n)) の積集合をとり、節点ｎの
挿入範囲集合Insert(n) ，Insert(join(n)) を以下の定
義より求める。

【００８９】

【数１】

【００９０】ステップ４４０） 節点ｎの挿入位置が一
意に決定した場合、節点ｎに決定済み印（^* ）を付け
る。以後、この節点の挿入位置Insert^* (n) は変化させ
ない。 ステップ４５０） 挿入位置が一意に決定していない
（決定済み印のない）節点ｈの挿入位置Insert^* (h)=
｛ｉ｝を一意に決定する。ここで、ｉは挿入対象の制御
フローグラフの各矢印に順序関係を持つ識別番号を割り
当てた際、その番号が最大のものを指す。

【００９１】ステップ４６０） 再構成によって得られ
た制御フローグラフＣＦＧ_new から、プログラム依存グ
ラフＰＤＧ_new ’作成する。 ステップ４７０） 再構成前のプログラム依存グラフＰ
ＤＧ_new と再構成後のプログラム依存グラフＰＤ
Ｇ_new ’を同型写像により比較して、一致する場合には
ステップ４８０に移行し、不一致の場合には当該再構成
処理を終了する。

【００９２】ステップ４８０） 一致するとき、再構成
後の制御フローグラフＣＦＧ_new をソースコードに変換
する。挿入する際の再構成操作を以下に示す。再構成操
作において、join(start) ≡stopである。また、ＤＥＦ
(n) は節点ｎで定義される変数集合、od(n,v) は節点ｎ
の変数ｖに関する出力依存（output dependence)先の節
点を表す。ただし、od(n,v) が存在しないとき、od(n,
v) ≡stopとする。さらにod^-1(n,v) は節点ｎで変数ｖ
が定義されていると仮定したときの出力依存元の節点を
表す。ただし、od ^-1(n,v) が存在しないとき、od^-1(n,
v) ≡start とする。節点ｎが挿入可能な位置を表す集
合を求める再構成操作を以下に示す。

【００９３】［再構成操作ａ］ （制御依存ｍ→ｎに関
して） ｍは分岐条件節点を、ｎは分岐条件節点か変数代入節点
を表す。いまＭ’はｍの枝に含まれる条件分岐節点集合
とする。このとき、挿入範囲集合は以下の定義より求め
る。

【００９４】

【数２】

【００９５】［再構成操作ｂ］ （制御依存ｎ→Ｍに関
して） ｎは制御依存の接続元より条件分岐節点を、Ｍは分岐条
件節点か変数代入節点を表す。いま、Ｍ’はｍの枝に含
まれる条件分岐節点集合とする。このとき、挿入範囲集
合は以下の定義より求める。

【００９６】

【数３】

【００９７】［再構成操作ｃ］ （データ依存Ｍ→ｎに
関して） Ｍは変数代入節点を、ｎは条件分岐節点か変数代入節点
を表す。このとき、挿入範囲集合は以下の定義より求ま
る。

【００９８】

【数４】

【００９９】［再構成操作ｄ］ （データ依存ｎ→Ｍに
関して） ｎは変数代入節点を、Ｍは条件分岐節点か変数代入節点
を表す。このとき、挿入範囲集合は以下の定義より求め
る。

【０１００】

【数５】

【０１０１】［再構成操作ｅ］ （出力依存Ｍ→ｎに関
して） Ｍ，ｎは変数代数節点を表す。節点ｍはｍ∈Ｍとする。
このとき、挿入範囲集合は以下の定義より求まる。

【０１０２】

【数６】

【０１０３】［再構成操作ｆ］ （出力依存ｎ→Ｍに関
して） ｎ，Ｍは変数代入節点を表す。節点ｍはｍ∈Ｍとする。
このとき、挿入範囲集合は以下の定義より求まる。

【０１０４】

【数７】

【０１０５】次に、本発明の一実施例の具体例を用いて
説明する。部品ライブラリ１２０に、図２６（ａ）
（ｂ）に示すプログラム部品Ａ，Ｂが存在すると仮定す
る。いま、部品利用者がプログラム部品Ａを図２７に示
すプログラム部品Ｃに変更する。このとき、新規プログ
ラム部品が生成される処理の流れの概要は、図１６、図
１７に示すようになる。図１６の（１−Ａ）は、プログ
ラム部品Ａ、（１−Ｂ）は、部品Ａの区間限定スライ
ス、（１−Ｃ）は部品Ａの区間限定補スライス、（１−
Ｄ）は変形後の補スライス、（１−Ｅ）はプログラム部
品Ｃ、（１−Ｆ）は部品Ｃの区間限定スライス、（１−
Ｇ）は、部品Ｃの区間限定補スライス、（１−Ｈ）は変
形後の補スライスを示す。図１７の（２−Ａ）は、プロ
グラム部品Ｂ、（２−Ｂ）は部品Ｂの区間限定スライ
ス、（２−Ｃ）は部品Ｂの区間限定補スライス、（２−
Ｄ）は部品Ａの区間限定スライス、（２−Ｅ）は部品Ｃ
の区間限定スライス、（２−Ｆ）は新規再利用部品のプ
ログラム依存グラフ、（２−Ｇ）は新規再利用部品の制
御フローグラフ、（２−Ｈ）はプログラム部品Ｂを示
す。

【０１０６】図１６及び図１７中、

【０１０７】

【数８】

【０１０８】は、区間限定スライスと区間限定補スライ
スの合成を表す。以下に部品変更箇所の特定の処理と機
能交換処理について説明する。 ［部品変更箇所の特定処理］まず、部品変更箇所の特定
処理について説明する。

【０１０９】（１） プログラム部品Ａ（図１６（１−
Ａ）＝図２６（ａ））とプログラム部品（Ｃ）（図１６
（１−Ｅ）＝図２７）の入出力節点集合、 Ｎ_Ai＝｛ａ１，ａ２，ａ３，ａ４，ａ１０，ａ１１｝， Ｎ_A0＝｛ａ１０，ａ１１｝， Ｎ_Ci＝｛ｃ１，ｃ２，ｃ３，ｃ４，ｃ５，ｃ１３，ｃ１
４，ｃ１５，ｃ１６｝， Ｎ_CO＝｛ｃ１４，ｃ１５，ｃ１６｝ を求める。また、変数集合 Ｖ_A ＝ρ｛ch, alphabet, digit ｝， Ｖ_C ＝ρ ｛ch, alphabet, digit, capital＿alphabe
t, small ＿alphabet｝ を求める。

【０１１０】（２） プログラム部品Ａに対して、入力
節点をａ１、出力節点ａ１０、変数集合｛alphabet｝を
選び、区間限定スライス Ｓ^# （ａ１，ａ１０｛alphabet｝）（図１６（１−
Ｂ）） を生成する。また、プログラム部品Ｃに対して、入力節
点をｃ１、出力節点ｃ１４、変数集合｛alphabet｝を選
び、区間限定スライス Ｓ^# （ｃ１，ｃ１４｛alphabet｝）（図１６（１−
Ｆ）） を作成する。

【０１１１】（３） 上記の区間限定スライスに対する
区間限定補スライス Ｓ^#*（ａ１，ａ１０｛alphabet｝） と、 Ｓ^#*（ｃ１，ｃ１４｛alphabet｝） のプログラム依存グラフ（図１６（１−Ｃ），（１−
Ｇ））をそれぞれ作成する。

【０１１２】（４） 上記の区間限定補スライスをそれ
ぞれ変形し、簡単化する（図１６（１−Ｄ），（１−
Ｈ））。 （５） 変形後の２つの区間限定補スライス（図１６
（１−Ｄ），（１−Ｈ））に対してラベル付き同型写像
による比較を行う。このとき、抽象化によって各変数名
は、 ch⇒＃１、 alphabet⇒＃２、 digit ⇒＃３ と置き換えられる。また、同型写像比較結果から、節点
の対応関係は、 ａ２＝ｃ３， ａ７＝ｃ１０， ａ８＝ｃ１０， ａ１０＝ｃ１４ となる。

【０１１３】（６） 同型写像比較により区間限定補ス
ライスが一致する場合、交換可能スライス対を特定す
る。図１６において、区間限定スライス（１−Ｂ）と
（１−Ｆ）が交換可能スライス対である。 （７） 交換可能スライス対の各区間限定スライスと同
じ区間で、２つのソースコードに同時に含まれる変数に
ついて、区間限定スライスを作成する。いま、図１６
（１−Ｂ），（１−Ｆ）において、変数chと変数digit
について区間限定スライスを作成すると、 Ｓ^# （ａ１，ａ１０，｛ch｝） ＝｛ａ３，ａ４，ａ９｝⊆Ｓ^# （ａ１，ａ１０，｛alphabet｝） Ｓ^# （ｃ１，ｃ１４，｛ch｝） ＝｛ｃ４，ｃ５，ｃ１２｝⊆Ｓ^# （ｃ１，ｃ１４，｛alphabet｝）

【０１１４】

【数９】

【０１１５】となるので、Ｓ^# （ａ１，ａ１０，｛c
h｝）とＳ^# （ｃ１，ｃ１４，｛ch｝）に対してラベル
付き同型写像比較を試みる。いま、Ｓ^# （ａ１，ａ１
０，｛ch｝）とＳ^# （ｃ１，ｃ１４，｛ch｝）は同型と
なるので、節点の対応関係は、 ａ３＝ｃ４， ａ４＝ｃ５， ａ９＝ｃ１２ となる。

【０１１６】（８） 区間限定補スライス同士、及び変
数chに関する区間限定スライス同士の同型写像比較によ
り、交換可能スライス対における節点の対応関係を求め
る。制御依存矢印entry →ａ１とentry →ｃ１３, デー
タ依存矢印ａ１→ａ１０とｃ１３→ｃ１４より、ａ１＝
ｃ１３となる。

【０１１７】（９） 節点の対応関係を含む交換可能ス
ライス対 〈Ｓ^# （ａ１，ａ１０，｛alphabet｝）， Ｓ^# （ｃ１，ｃ１４，｛alphabet｝）〉 を変更事例として、部品ライブラリ１２０に記録する。
節点の対応関係は、 ａ１＝ｃ１３，ａ３＝ｃ４，ａ４＝ｃ５，ａ９＝ｃ１２ である。

【０１１８】次に、機能交換の処理について説明する。 ［機能交換処理］ （１） プログラム部品Ｂ（図１７（２−Ａ）＝図２６
（ｂ））の入出力節点集合 Ｎ_Bi＝｛ｂ１，ｂ２，ｂ３，ｂ４，ｂ９，ｂ１０｝ Ｎ_B0＝｛ｂ９，ｂ１０｝ を求める。また、変数集合 Ｖ_B ＝ρ｛ｃ，alpha, others ｝ を求める。

【０１１９】（２） プログラム部品Ｂに対して、入力
節点をｂ１，出力節点ｂ９，変数集合｛alpha ｝を選
び、区間限定スライス Ｓ^# （ｂ１，ｂ９，｛alph｝）（図１７（２−Ｂ）） を作成する。ここで、プログラム部品Ｂは変更事例（Ａ
→Ｃ）に無関係な部品である。

【０１２０】（３） 交換可能スライス対 〈Ｓ^# （ａ１，ａ１０，｛alphabet｝）， Ｓ^# （ｃ１，ｃ１４，｛alphabet｝）〉 の変更前区間限定スライスＳ^# （ａ１，ａ１０，｛alph
abet｝）（図１７（２−Ｄ）＝図１６（１−Ｂ）と上記
の区間限定スライスＳ^# （ｂ１，ｂ９，｛alph｝）（図
１７（２−Ｂ））に対してラベル付き同型写像比較を行
う。このとき、 ch＝ｃ⇒＃１， alphabet＝alpha ⇒＃２ という変数の置き換えによるラベルの抽象化を行ってい
る。図１７において、２つの区間限定スライスは同型
で、節点の対応関係は、ａ１＝ｂ１，ａ３＝ｂ３，ａ４
＝ｂ４，ａ５＝ｂ５，ａ６＝ｂ６，ａ９＝ｂ８となる。

【０１２１】（４） 図１７（２−Ｃ）は、プログラム
部品Ｂの区間限定補スライスである。このプログラム依
存グラフを図１８（ａ）に示す。図１８（ａ）におい
て、区間限定スライスＳ^# （ｂ１，ｂ９，｛alph｝）
（図１８（ａ）中の点線節点）に対して機能の変換を行
う。交換を行う区間限定スライスは、Ｓ^# （ｂ１，ｂ
９，｛alph｝）とＳ^# （ｃ１，ｃ１４，｛alphabet｝）
である。

【０１２２】（４−１） 図１７（ａ）において、上記
の（２）で求めた節点の対応関係を用いて、区間限定ス
ライスＳ^# （ｂ１，ｂ９，｛alph｝）の各節点を、Ｓ^#
（ａ１，ａ１０，｛alphabet｝）内の節点に置換する
（ｂ１←ａ１ ｂ３←ａ３，ｂ４←ａ４，ｂ５←ａ５，
ｂ６←ａ６，ｂ８←ａ９）。置換（Ｂ←Ａ）後のプログ
ラム依存グラフは、図１８（ｂ）のようになる。

【０１２３】（４−２） 図１７（２−Ｄ）、（２−
Ｅ）に示す交換可能スライス対 〈Ｓ^# （ａ１，ａ１０，｛alphabet｝）， Ｓ^# （ｃ１，ｃ１４，｛alphabet｝）〉 の節点の対応関係より、図１８（ｂ）の一部の節点をＳ
^# （ｃ１，ｃ１４，｛alphabet｝）内の節点に置換する
（ａ１←ｃ１３，ａ３←ｃ４，ａ４←ｃ５，ａ９←ｃ１
２）。また、図１８（ｂ）において、節点ａ６に対応す
る節点は、Ｓ^# （ｃ１，ｃ１４，｛alphabet｝）中に存
在しないので、削除する。置換（Ａ←Ｃ）後のプログラ
ム依存グラフは図１８（ｃ）のようになる。

【０１２４】（４−３）置換された節点ｃ４，ｃ５，ｃ
１２，ｃ１３を錨節点とし、Ｓ^# （ｃ１，ｃ１４，｛al
phabet｝）をＳ^#*（ｂ１，ｂ９，｛alph｝）に投射す
る。投射によって生成されたプログラム依存グラフを図
１９に示す。 （５） 図１９に示すプログラム依存グラフにおいて、
接続元を持たない制御依存を表す矢印を合成操作に従っ
て、適切な節点に接続する。図１９において、節点Ｔ１
を接続元に持つ矢印が、接続対象である。いま、節点Ｔ
１の接続先は、条件分岐の領域を表す領域節点なので、
合成操作ａにより、節点Ｔ１は節点ｃ６か節点ｃ８に重
ねることが可能である。いま、節点Ｔ１を節点ｃ８に重
ねたときのプログラム依存グラフを図２０（＝図１７
（２−Ｆ））に示す。図２０は、重ね合わされて生成さ
れる新規プログラム部品のプログラム依存グラフであ
る。

【０１２５】（６） 図２０に対して、再構成操作を行
うために、データ依存に関わる変数名と出力依存を付加
したものが図２１である。図２１において、網かけの節
点は挿入対象である。また、２点鎖線は出力依存、デー
タ依存矢印（実線矢印）に割り付けられたラベルは、接
続元で定義されている変数名を表す。再構成操作に対し
て、節点が挿入されるプログラム部品の制御フローグラ
フを図２２（ａ）に示す。ここで、図２２（ａ）の制御
フローグラフにおいて、各矢印をｃｃ１，ｃｃ２，…と
おく。

【０１２６】［ステップ１］ １ａ． 図２１の節点ｂ２に対して、entry →ｂ２より
再構成操作ａを適用すると、

【０１２７】

【数１０】

【０１２８】となる。ｂ２→ｂ７，ｂ２→ｂ１０に関し
ては、節点ｂ７，ｂ１０の位置が未決定なので、再構成
操作は適用しない。よって、 Insert（ｂ２）＝｛ｃｃ１，ｃｃ２，ｃｃ３，ｃｃ４，
ｃｃ１２，ｃｃ１３｝ となる。

【０１２９】１ｂ． 図２１の節点ｂ７に対して、ｃ８
［Ｆ］→ｂ７より再構成操作ａを適用すると、 Insert_a （ｂ７）＝ＲＰ（ｃ８［Ｆ］，ｃ１２）＝｛ｃｃ１１｝ となる。節点ｂ７に接続を持つ他の節点ｂ２，ｂ１０
は、位置が未決定なので、再構成操作は適用しない。ま
た、節点ｂ７の挿入位置は、一意にきまるので、決定済
印“＊”を付け、 Insert^* （ｂ７）＝｛ｃｃ１１｝ となる。

【０１３０】１ｃ． 図２１の節点ｂ９に対して、entr
y →ｂ９より再構成操作ａを適用すると、

【０１３１】

【数１１】

【０１３２】となる。また、ｃ１３→ｂ９より再構成操
作ｃを適用すると、 Insert_c （ｂ９）＝ＲＰ（ｃ１３，stop）＝｛ｃｃ１３｝ となる。よって、 Insert^* （ｂ９）＝Insert_a （ｂ９）∩Insert_c （ｂ９）＝｛ｃｃ１３｝ となる。節点ｂ９は、一意に決定するので、決定済印
“＊”を付ける。

【０１３３】１ｄ． 図２１の節点ｂ１０に対して、en
try →ｂ１０より再構成操作ａを適用すると、

【０１３４】

【数１２】

【０１３５】となる。節点ｂ１０に接続を持つ他の節点
ｂ２，ｂ７，ｂ９は位置が未決定なので、再構成操作は
適用しない。よって、 Insert（ｂ１０）＝｛ｃｃ１，ｃｃ２，ｃｃ３，ｃｃ
４，ｃｃ１２，ｃｃ１３｝ となる。

【０１３６】［ステップ２］ ２ａ． 図２１の節点ｂ２に対して、entry →ｂ２より
再構成操作ａを適用すると、 Insert_a （ｂ２）＝｛ｃｃ１，ｃｃ２，ｃｃ３，ｃｃ
４，ｃｃ１２，ｃｃ１３｝ となる。ｂ２→ｂ７により、再構成操作ｄを適用する
と、 Insert_d （ｂ２）＝ＲＰ（start,ｂ７） ＝｛ｃｃ１，ｃｃ２，ｃｃ３，ｃｃ４，ｃｃ５，ｃｃ６， ｃｃ７，ｃｃ８，ｃｃ９，ｃｃ１０，ｃｃ１１｝ となる。よって、 Insert（ｂ２）＝Insert_a （ｂ２）∩Insert_d （ｂ２） ＝｛ｃｃ１，ｃｃ２，ｃｃ３，ｃｃ４｝ となる。

【０１３７】２ｂ． 図２１の節点ｂ１０に対して、en
try →ｂ１０より再構成操作ａを適用すると、 Insert_a （ｂ１０）＝｛ｃｃ１，ｃｃ２，ｃｃ３，ｃｃ
４，ｃｃ１２，ｃｃ１３｝となる。ｂ７→ｂ１０によ
り、再構成操作ｃを適用すると、 Insert_c （ｂ１０）＝ＲＰ（ｂ７，stop） ＝｛ｃｃ５，ｃｃ６，ｃｃ７，ｃｃ８，ｃｃ９，ｃｃ１０， ｃｃ１１，ｃｃ１２，ｃｃ１３｝ となる。ｂ９→ｂ１０より再構成操作ｅを適用すると、 Insert_e （ｂ１０）＝ＲＰ（ｂ９，stop） ＝｛ｃｃ１３｝ となる。よって、 Insert^* （ｂ１０） ＝Insert_a （ｂ１０）∩Insert_c （ｂ１０）∩Insert_e （ｂ１０） ＝｛ｃｃ１３｝ となる。節点ｂ１０の挿入位置は、一意に決定したの
で、決定済印“＊”を付ける。

【０１３８】［ステップ３］ ３ａ． 節点ｂ２に対してentry →ｂ２より再構成操作
ａを適用すると、 Insert_a （ｂ２）＝｛ｃｃ１，ｃｃ２，ｃｃ３，ｃｃ
４，ｃｃ１２，ｃｃ１３｝ となる。ｂ２→ｂ７，ｂ２→ｂ１０より、再構成操作ｄ
を適用すると、 Insert_d （ｂ２）＝ＲＰ（start,ｂ７）∩ＲＰ（start ，ｂ９） ＝｛ｃｃ１，ｃｃ２，ｃｃ３，ｃｃ４，ｃｃ５，ｃｃ６， ｃｃ７，ｃｃ８，ｃｃ９，ｃｃ１０，ｃｃ１１｝ となる。よって、 Insert（ｂ２）＝Insert_a （ｂ２）∩Insert_d （ｂ２） ＝｛ｃｃ１，ｃｃ２，ｃｃ３，ｃｃ４｝ となる。

【０１３９】（７） 挿入範囲集合Insert^* （ｂ７），
Insert^* （ｂ９），Insert^* （ｂ１０）が一意に決定
し、Insert（ｂ２）がステップ２とステップ３で変化し
ないことにより、再構成操作の適用を終了する。挿入対
象節点の挿入範囲を図２２（ａ）に示す。

【０１４０】（８） Insert（ｂ２）において、識別番
号が最大の矢印ｃｃ４を選ぶと、 Insert^* （ｂ２）＝｛ｃｃ４｝ となる。節点を挿入した後の制御フローグラフを図２２
（ｂ）に示す。 （９） 節点ｂ２，ｂ７，ｂ９，ｂ１０を挿入した後の
図２２（ｂ）に示す制御フローグラフからプログラム依
存グラフを作成すると、図２１と等価となる。よって、
再構成操作は成功で、この制御フローグラフをソースコ
ードに変換する。変換後の新規プログラム部品Ｂ’のソ
ースコードを図２３に示す。プログラム部品Ｂ’は、
「英字と大文字と小文字を区別し、英字とその他の文字
の出現頻度を求める」機能を持つ。

【０１４１】図２４に前述の機能の一部変換の説明の
（５）で、Ｔ１＝ｃ６としたときに作成される新規プロ
グラム部品Ｂ”を示す。プログラム部品Ｂ”は、「英字
の大文字と小文字を区別し、英字と英字の大文字以外の
文字の出現頻度を求める」機能を持つ。この機能は、プ
ログラム部品Ｂ’と比較して変数othersに関して違いを
持つ。

【０１４２】また、プログラム部品Ｂ’とＢ”におい
て、区間限定スライス Ｓ^# （ｃ１，ｃ１４，｛alphabet｝）（交換可能スライ
ス対） に関しては、その機能が保証される。つまり、プログラ
ム部品Ｂ’とＢ”の区間ＣＲＰ（ｃ１，ｃ１４）の変数
alphabetの実行結果は、プログラム部品Ｃ（ソースコー
ドＣ）の区間ＣＲＰ（ｃ１，ｃ１４）の変数alphabetの
実行結果と等価である。

【０１４３】なお、本発明は、上記の実施例に限定され
ることなく、特許請求の範囲内で種々、変更・応用が可
能である。

【０１４４】

【発明の効果】上述のように、プログラム部品の自動生
成方法及び装置によれば、部品の変更箇所を特定する手
段と、他の再利用部品の変更事例を蓄積及び適用できる
手段を提供することで、部品変更を自動的に行い、既存
の部品ライブラリに存在するプログラム部品と異なる機
能を持つ新規プログラム部品を生成することが可能であ
る。これにより、本発明は、以下のような効果を奏す
る。

【０１４５】（１） 既存の部品ライブラリに存在しな
い部品が要求された場合であっても、新たに生成された
プログラム部品により当該要求を満たすことができるた
め、従来、検索に失敗していた要求に対しても部品検索
に成功する可能性は高くなり、ソフトウェア開発者に対
する再利用時の部品変更の負担が軽減される。

【０１４６】（２） 部品変更が自動化されたことによ
り、多種多様にわたるすべてのプログラム部品を予め部
品ライブラリに用意する必要がなくなる。従って、管理
するプログラム部品の数が削減され、部品ライブラリの
管理及び部品検索の方法が容易になると共に、膨大な資
源を必要としない。

【０１４７】（３） 部品の自動生成の様子をソフトウ
ェア開発者に提示することにより、ソフトウェア開発者
に部品変更の指針を与える。また、新規プログラム部品
の機能を明確にすることは、新しい機能を持つ別のプロ
グラム部品を作成する際に役立つ。

【０１４８】（４） 部品の変更事例をプログラム部品
が存在する部品ライブラリから動的に取得するので、再
利用環境に適した部品が自動生成され、再利用率が向上
する。また、過去の変更事例が部品ライブライリに自動
的に蓄積されるので、部品ライブラリを自動的に洗練す
ることにつながる。

【図面の簡単な説明】

【図１】本発明の原理を説明するための図である。

【図２】本発明の原理構成図である。

【図３】プログラム部品を制御フローグラフで表した例
を示す図である。

【図４】プログラム依存グラフの例を示す図である。

【図５】ラベル付き同型写像比較によりプログラム依存
グラフが一致する例を示す図である。

【図６】区間限定スライスの例を示す図である。

【図７】区間限定補スライスの例を示す図である。

【図８】本発明の一実施例の部品化再利用によるプログ
ラム作成装置の構成図である。

【図９】本発明の一実施例の部品自動生成装置の概要を
示す図である。

【図１０】本発明の一実施例の変更箇所の特定手順を示
すフローチャートである。

【図１１】本発明の一実施例の区間限定補スライス変形
処理の手順を示すフローチャートである。

【図１２】本発明の一実施例の機能交換処理の手順を示
すフローチャートである。

【図１３】本発明の一実施例の置換処理の手順を示すフ
ローチャートである。

【図１４】本発明の一実施例の合成処理の手順を示すフ
ローチャートである。

【図１５】本発明の一実施例の再構成処理の手順を示す
フローチャートである。

【図１６】本発明の一実施例の変更箇所特定時の流れを
示す図である。

【図１７】本発明の一実施例の部品利用時の流れを示す
図である。

【図１８】本発明の一実施例のスライスの置換操作を示
す図である。

【図１９】本発明の一実施例の合成操作を説明するため
の図である。

【図２０】本発明の一実施例の新規プログラム部品を示
す図である。

【図２１】本発明の一実施例のスライスの再構成操作を
説明するための図である。

【図２２】本発明の一実施例の新規プログラム部品を説
明するための図である。

【図２３】本発明の一実施例の新規プログラム部品Ｂ’
を示す図である。

【図２４】本発明の一実施例の新規プログラム部品Ｂ”
を示す図である。

【図２５】従来の組み立て技術における再利用工程を示
す図である。

【図２６】ソースコードの例（プログラム部品Ａ，Ｂ）
を示す図である。

【図２７】変更後のソースコードの例（プログラム部品
Ｃ）を示す図である。

【符号の説明】

１ 部品作成部 ３ 部品検索部 ５ 部品合成部 ６ 目的のプログラム １０ 部品化再利用によるプログラム作成装置 ２０ 部品案生成手段 ３０ 部品ライブラリ ４０ 変換手段 ４１ 部品検索手段 ４２ 部品合成手段 ４３ 部品更新手段 １００ 部品自動生成装置 １１０ 部品生成部 １２０ 部品ライブラリ １３０ 部品変更部

Claims (8)

【特許請求の範囲】
1. 【請求項１】 プログラム部品に修正があった場合に、
   変更箇所及び内容を随時データベース化し、 新規プログラム部品を作成する場合には、前記データベ
   ースから同様な機能をもつ類似の変更事例を検索し、 同様な機能が得られた場合には、該当機能を既存のプロ
   グラム部品の機能から補填することにより、既存のプロ
   グラム部品ライブラリから新規のプログラム部品を生成
   することを特徴とするプログラム部品自動生成方法。
2. 【請求項２】 プログラムのソースコードをグラフに変
   換するグラフ化ステップと、 前記プログラムのソースコードをソースコードの依存関
   係を用いて分割するスライシングステップと、 希望する機能のソースコードに関して、過去に類似のソ
   ースコード変更履歴があるかを検索する履歴検索ステッ
   プと、 変更履歴をもつ既存のプログラムのソースコードを表す
   グラフと、希望する機能のソースコードのもつグラフが
   同一か否かを判定する同型写像比較ステップと、 両グラフが同一グラフ形状を有した場合は、前記既存の
   プログラムのソースコードから同一の部品機能を自動補
   填する補填ステップよりなる請求項１記載のプログラム
   部品自動生成方法。
3. 【請求項３】 前記ソースコードの依存関係は、 前記ソースコードにおける代入文及び条件式を割り当て
   た節点の集合及び、各節点間の参照・非参照関係を表す
   矢印からなるグラフを利用して表現する請求項２記載の
   プログラム部品自動生成方法。
4. 【請求項４】 前記同型写像比較ステップは、 前記グラフにおける各節点に割り当てられた代入文及び
   条件式が内包する変数を抽象化し、 一方のグラフの節点と矢印を他方のグラフに写像したと
   き、依存関係の種類及び属性を含む節点の接続関係と抽
   象化したラベルが完全に等価であるか否かによりグラフ
   間の比較を行う請求項２記載のプログラム部品自動生成
   方法。
5. 【請求項５】 仕様に応じてプログラム部品案を生成す
   る部品案生成手段と、 生成された部品案を逐次整理保存し、かつ変更履歴を管
   理する部品ライブラリと、 前記部品ライブラリ内に存在するプログラム部品がそれ
   ぞれもつ機能の一部を変換する変換手段とを有し、 検索要求に適合する新たな機能を持つプログラム部品を
   生成することを特徴とするプログラム部品自動生成装
   置。
6. 【請求項６】 前記変換手段は、 前記部品ライブラリから過去に同型の写像をもつ部品な
   らびに変更履歴があるか否かを検索する部品検索手段
   と、 同型の写像を持つ部品があった場合に、該当部品を使っ
   て新たな部品を合成する部品合成手段と、 部品に部分変更があった場合は、前記部品検索手段によ
   り検索された部品ならびに変更履歴を利用して前記部品
   ライブライリの内容を更新する部品更新手段とを有する
   請求項５記載のプログラム部品自動生成装置。
7. 【請求項７】 前記変換手段は、 前記部品検索手段により前記部品ライブラリ内のプログ
   ラム部品の変更を検出すると、プログラムのソースコー
   ド依存関係によって分割するプログラムスライシング手
   段と、 グラフの同型写像比較により変更の影響箇所を含むソー
   スコードを特定し、部品変更事例として蓄積するソース
   コード特定手段とを含む請求項５記載のプログラム部品
   自動生成装置。
8. 【請求項８】 前記部品更新手段は、 過去に変更を受けたプログラム部品と機能の一部を共有
   するプログラム部品をグラフの同型写像比較により特定
   し、前記部品変更事例を適用して部品の一部の機能を交
   換する交換手段を有する請求項６記載のプログラム部品
   自動生成装置。