米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> ヒューレット・パッカード・カンパニー

発明の名称 コード検証システム
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2003−36188(P2003−36188A)
公開日 平成15年2月7日(2003.2.7)
出願番号 特願2002−138053(P2002−138053)
出願日 平成14年5月14日(2002.5.14)
代理人 【識別番号】100081721
【弁理士】
【氏名又は名称】岡田 次生 (外2名)
【テーマコード(参考)】
5B042
5B076
【Fターム(参考)】
5B042 GA03 HH08 HH12 
5B076 EC03
発明者 クリストファー・ドリン / ヴェイズウォー・ゴパラクリシュナン
要約 課題
コンパイル済みのコードの型チェックを行うコード検証システム及び方法を提供する。

解決手段
コード検証システムはメモリ(15)とコード検証器(20)を含む。メモリ(15)はコンパイル済みのプログラム(12)を格納するために使用される。コード検証器(20)はプログラム(12)の命令を分析し、該命令に基づいて複数の型シグネチャを生成する。型シグネチャは、前記命令の入力型制約と出力型記述を含み、コード検証器(20)は型シグネチャを分析して型エラーを検出する。
特許請求の範囲
【請求項1】コンパイル済みのプログラムを格納するメモリと、前記プログラムの命令を分析し、該命令に基づいて複数の型シグネチャを生成し、該型シグネチャを分析することにより型エラーを検出するように構成されたコード検証器と、を含み、前記型シグネチャはそれぞれ前記命令の1つについて入力型制約と出力型記述を示す、コード検証システム。
発明の詳細な説明
【0001】
【発明の属する技術分野】本発明は、一般にコード妥当性検査または検証技術に関し、特に、コンパイル済みコードに対し型(タイプ)エラーがないかチェックを行うコード検証システム及び方法に関する。
【0002】
【従来の技術】コンパイル中、コンピュータコードの実行を許可する前にエラーの有無をチェックすることが多い。このようなテストは、実行中にデータエラーが発生しないことを確実なものとする助けとなる。しかしながら、コンピュータコードのセットは、信頼のあるソースによってコンパイルされるとは限らない。例えば、ユーザのコンピュータによって実行されるコンパイル済みのコンピュータコード(例えば、バイトコード)が、そのコードをコンパイルした未知のまたは信頼のないコンピュータからダウンロードされることがある。このような状況は、ユーザがインターネットを利用する場合に発生することが多い。この点に関し、インターネットのオンラインユーザが、信頼のないサーバからコンパイル済みのコードをダウンロードし、ユーザのコンピュータ上でそのダウンロードしたコードを実行することは一般的である。
【0003】ダウンロードされたコードは、信頼のあるソースによってコンパイルされていないことがあるため、一般にコンパイル中に実行される適切なエラーチェックにより検出できるエラーを含んでいる可能性がある。これらのエラーは、例えばダウンロードプロセス中に不注意のデータ送信エラーが発生した場合のように、不注意によるものである場合もあり、あるいは、例えばハッカーがユーザのコンピュータの動作やセキュリティの損傷を試みて意図的にコードにエラーを導入する場合のように、意図的なものである場合もある。このように、ユーザのコンピュータで実行するためにコンパイル済みのコンピュータコードがユーザのコンピュータにダウンロードされたとき、とりわけコンパイル済みのコードが信頼のないソースからダウンロードされたとき、特定の潜在的なデータエラーがコードに含まれないことを保証するために、コードのチェックを行うことが望ましい場合が多い。このようなチェックは、「コード検証(verification)」または「コード妥当性検査(validation)」と呼ばれることもあり、ダウンロードしたコードを実行する前に行うのが通常である。
【0004】ダウンロードしたコードが信頼のあるソースから送信されたか否かを確認するために、コードの暗号署名を利用することがあることに注意されたい。この点に関して、ユーザのコンピュータにより信頼のあるソースとして認識されたソースによって、ダウンロードしたコードに署名がなされているときは、ダウンロードしたコードについてコード検証の実行が不要である場合もある。しかし、ダウンロードしたコードがこのようなシグネチャ(署名)を含まないときは、ユーザのコンピュータは、コードを実行する前にそのコードについてコード検証を実行することが望ましい。
【0005】コード検証により典型的に実行される重要なテストは、型チェックである。型チェックでは、コードを分析し、そのコードの消費している命令の各々に少なくとも正しい型の入力(例えば、引数)が提供されることを保証する。この点に関して、コンピュータによって処理される値には一般に型が割当てられること、及びある命令は特定の型の入力に基づいてのみ実行されなければならないことは周知である。異なる値の型の一般的な例には、int型(整数型)、floating型(浮動小数点型)、double型(倍精度浮動小数点型)、及びString型(文字列型)等が含まれるが、これに限定されるものではない。例えば、加算命令は、実行に2つのint型入力を必要とする。実行中、加算命令に異なる型(例えば、double型)の入力が与えられると、実行エラーが発生する。このため、型チェックでは、誤った入力型が与えられている命令によって生じる潜在的エラーが検出される。
【0006】オブジェクト指向プログラミング言語(例えば、C++またはJAVA(登録商標))では、値型は、プログラム内で定義されるクラスであることに注意されたい。さらに、種々のサブクラスによってクラスを拡張しまたは派生することがある。実行中に命令が特定クラスの入力を受け取るべきであるとき、命令に特定クラスの引数または特定クラスのサブクラスの引数が与えられれば、エラーは発生しないはずである。しかしながら、コード検証を行ったときに、異なるクラスまたは型の入力が実行時に命令に与えられることが決まると、コード検証プロセスによって潜在的な型エラーが検出されるであろう。与えられなければ、コード検証プロセスによって実行される型チェックをその命令はパスするであろう。
【0007】従来のコンピュータでは、コンパイル済みのコードのコード検証は、コードを実際に実行する前にコンパイル済みのコードの記号実行(すなわち、シミュレーション)によって達成されることが多い。このようなコード検証は、米国特許第5,740,441号、同第5,668,999号及び同第5,748,964号において一般に述べられており、その開示内容は参照により本明細書に援用される。記号実行中に、各記号実行済み命令に対していずれの型の値がコンピュータのスタックから記号的にプルされ及びそこにプッシュされるかに関する決定を行うことができる。記号実行中に誤った型の入力が命令に与えられると決定されると、エラーが検出される。
【0008】
【発明が解決しようとする課題】本発明は、コンパイル済みのコードの型チェックを行うコード検証システム及び方法を提供することを目的とする。
【0009】
【課題を解決するための手段】アーキテクチャにおいて、本発明のコード検証システムは、メモリとコード検証器(ベリファイヤ)を利用する。メモリは、コンパイル済みのプログラムを格納するために利用される。コード検証器は、プログラムの命令を分析し、これら命令に基づいて複数の型シグネチャを生成する。型シグネチャは、命令の入力型制約と出力型記述とを表示し、コード検証器は、型シグネチャを分析して型エラーを検出する。
【0010】
【発明の実施の形態】本発明は、一般に効率的なコード検証システム及び方法に関する。本発明のコード検証システムは、コードのセット内の各命令について型シグネチャを作成する。本明細書において、命令の「型シグネチャ」とは、命令の入力型制約と出力型記述とを示す情報のセットである。入力型制約は、もしあれば命令の適切な実行に必要な入力の型を示し、出力型記述は、もしあれば命令の実行によって生成される出力値の型を示す。コードの命令について型シグネチャを形成した後、型シグネチャは合成される。2つのシグネチャの合成の間、これら2つのシグネチャの間に検出可能な型の不整合がないかチェックされる。いかなる型の不整合も検出されないとき、これら2つのシグネチャの合成は、正常に完了することができる。しかし、何らかの型の不整合が検出されたとき、当該コードはコード検証プロセスに不合格であるという指示が生成され、コードの実行が行われない。
【0011】図1は、本発明によるコンピュータシステム10(以下、単にシステム10とする)を示す。システム10は、メモリ15に格納されるコンパイル済みのプログラム12(例えば、バイトコード)を含む。プログラム12は、他のシステム(図示せず)によってコンパイルされ、周知の技術によりシステム10にダウンロードすることができる。このため、プログラム12についてコード検証を実行することが望ましい。この目的のために、コード検証器20は、プログラム12についてコード検証を実行するように、より具体的には検出可能な型エラーがないかプログラム12をチェックするように構成されている。このようなエラーが検出されると、コード検証器20はエラーハンドラ24を呼び出すのが好ましく、エラーハンドラ24は所定のアルゴリズムに従って検出された任意の型エラーを処理する。
【0012】コード検証器20及びエラーハンドラ24は、ソフトウェア、ハードウェアまたはそれらの組合せで実現することができる。好ましい実施形態においては、図1の例に示すように、コード検証器20及びエラーハンドラ24は関連する方法とともにソフトウェアで実現されメモリ15に格納される。
【0013】コード検証器20及び/またはエラーハンドラ24は、ソフトウェアで実現されるとき、命令実行システム、装置または機器から命令をフェッチしその命令を実行することができるコンピュータベースシステム、プロセッサ内蔵システム、あるいは他のシステムのような、命令実行システム、装置または機器により、またはこれらに接続して使用される任意のコンピュータ読取り可能媒体に格納され移送されることが可能であることに注意されたい。この文書の文脈では、「コンピュータ読取り可能媒体」は、命令実行システム、装置または機器によるかまたはこれらに接続して使用されるプログラムを包含し格納し通信し伝播しまたは移送することができる任意の手段である。コンピュータ読取り可能媒体は、例えば電子、磁気、光、電磁気、赤外線または半導体のシステム、装置、機器または伝播媒体とすることができ、またこれに限定されない。コンピュータ読取り可能媒体のより具体的な例(非網羅的リスト)は、以下のものを含む。すなわち、1つまたは複数のワイヤを有する電気的接続、ポータブルコンピュータディスケット、ランダムアクセスメモリ(RAM)、読み出し専用メモリ(ROM)、消去可能プログラム可能読み出し専用メモリ(EPROMまたはフラッシュメモリ)、光ファイバ及びポータブルコンパクトディスク読み出し専用メモリ(CDROM)である。なお、コンピュータ読取り可能媒体は、プログラムが印刷された用紙または他の適当な媒体であってもよいことに注意されたい。なぜなら、例えば用紙または他の媒体の光学的走査によりプログラムを電子的に捕捉し、その後コンパイルし、解釈し、必要な場合は適当な方法で処理し、コンピュータメモリに格納することができるからである。例えば、コード検証器20及び/またはエラーハンドラ24は、従来のポータブルコンピュータディスケットに磁気的に格納し移送することができる。
【0014】図1のシステム10の好ましい実施形態は、例えば、1つまたは複数のバスを含むことができるローカルインターフェイス31を介して、システム10内の他の要素と通信しそれらを駆動するデジタル信号プロセッサ(DSP)または中央処理装置(CPU)等の1つまたは複数の従来の処理要素27を備える。処理要素27は、処理要素27によって処理されている値を一時的に格納する「スタック」と呼ばれる後入れ先出し(LIFO)メモリ要素28を含む。
【0015】システム10は、システム10のユーザがデータの入力に使用するキーボードまたはマウス等の入力装置34と、ユーザへのデータの出力に使用するスクリーンディスプレイまたはプリンタ等の出力装置36を備える。ディスク記憶装置39は、ローカルインターフェイス31にが接続されて、不揮発性ディスク(例えば、磁気、光等)との間でデータを転送することができる。システム10はネットワークインターフェイス42に接続され、例えばインターネット等のネットワーク44とデータを交換することができる。
【0016】図2は、メモリ15に格納されるプログラム12内のコード49のセットのより詳細な図である。プログラム12は、一般に「メソッド(method)」、「関数(function)」または「手続き(procedure)」として知られる部品から構成されることは周知であり、コード49のセットはこのような部品の1つである。このような部品の呼び出しをチェックする周知の技術は存在しており、本発明は一般にこのような部品内のコードについて型エラーをチェックすることに関連する。
【0017】図2に示すように、コード49のセットは命令A〜Vで表される複数の命令を含む。命令は、既知のプログラミング言語(例えば、C、C++、Java(登録商標)、Fortran)からのコンパイル済みの命令の任意のセットを含むことができる。コード49は任意の数の命令を含むことができ、図2に示す命令の数は例示の目的で適当に選択されていることに注意されたい。
【0018】コンパイル済みのコード49について型エラーをチェックするために、コード検証器20は、初めに従来技術によりコード49を分析し、コード49のプログラムフローを決定する。コード49を分析する間、コード検証器20は、図3に示す異なるコードブロック52〜56に命令をグループ化する。各ブロック52〜56は、実行時に逐次実行される1つまたは複数の命令を含むことが好ましい。従って、ブロック52〜56の最初の命令が実行時に実行されると、同じブロック52〜56の他の命令の各々が最初の命令後に逐次実行される。
【0019】実行時のシステム10のマシン状態によって、プログラムフローは条件付き分岐命令により複数の可能な命令のうちの1つに分岐することに注意されたい。従って、コード検証プロセス中、条件付き分岐命令後にどの命令が逐次実行されるかを決定することはできない。従って、ブロック52〜56が条件付き分岐命令を含むとき、条件付き分岐命令がブロック52〜56の最後の命令であるように定義される(すなわち、ブロック52〜56の境界が設定される)ことが好ましい。また、コードブロック52〜56の各々が逐次命令のみを含むことを保証するために、いかなる単一のコードブロック52〜56も2つ以上の条件付き分岐命令を含まないことがこのましい。コード49のプログラムフローを決定し、コード49を種々のコードブロック52〜56に細分する技術は、1999年8月27日に出願され出願番号第09/384,812号が付与された米国特許出願「Code Verification by Tree Reconstruction」に述べられており、その開示内容は参照により本明細書に援用される。また、プログラムの制御フローに関連する情報を分析し決定する従来技術は多数存在し、このような技術は上述の機能を実現するために採用することができる。「Connected, Limited Device Configuration Specification Version 1.0 Java(登録商標) 2 Platform Micro EditionSun Microsystems2000」は、プログラムの制御フローを分析するために1つの従来からのプロセスによって提供される情報の型について記述しており、その開示内容は参照により本明細書に援用される。
【0020】コード検証器20が上述したようにコード49を分析した後、コード49は、図3に示すように複数のコードブロック52〜56に細分されるかまたはグループ化され、コード検証器20は、ブロック52〜56が実行時に実行される順序を知らなければならない。例示のために、コード検証器20によって決定されたプログラムフローは、実行時にブロック52が最初に実行されることを示していると仮定する。そして、ブロック54が実行された後にブロック53が実行される。最後に、ブロック55が実行された後にブロック56が実行される。
【0021】上述したようにコード49を細分することに加えて、コード検証器20は、コード49の各命令を分析し、コード49の各命令をその命令の対応する型シグネチャに変換する。これによって、コードブロック52〜56は、図4に示す型シグネチャブロック62〜66にそれぞれ変換される。
【0022】命令の型シグネチャは、もしあれば命令が実行時にどの入力型を消費するとコード検証器20が予測するかを示すことが好ましく、型シグネチャは、もしあれば命令が実行時にどの出力型を生成するとコード検証器20が予測するかを示すことが好ましい。さらに、命令が変数型のメモリロケーションを参照する(例えば、ロケーションの値をフェッチしたり更新する)とき、型シグネチャは、その変数のアドレスと要求される型とを示すことができる。本技術分野において周知であるように、その変数をその寿命の間に複数の関連のない型として使用することが許されるとき、ロケーションは変数型を有すると言う。例えば、Java(登録商標)マシンコードにおけるメソッドのローカル変数は、変数型である。
【0023】例えば、コード49の命令Dは、処理要素27によって実行される時、変数型の第1のメモリアドレスに格納されている値を消費し、他の数値を消費すると仮定する。また、命令Dは、変数型の第2のメモリアドレスに格納される数値を生成し、他の数値を生成すると仮定する。さらに、コード検証器20は、命令Dによって消費される数値がともにdouble型であり、命令Dによって生成される数値がint型であると決定すると仮定する。このような命令の例は、消費された値の一方を消費された値の他方によって除算し、余りをスタック28にプッシュしその一方で除算の結果を第2のメモリアドレスに書き込む除算命令である。
【0024】上記命令の型シグネチャを生成する際、コード検証器20は、命令の実行中にdouble型(double)の数値がスタック28から消費され、命令の実行中にdouble型の数値が第1のメモリアドレスから消費されることを示すデータを生成することが好ましい。データは、命令の実行中、int型の数値が生成されスタック28にプッシュされることを示すのが好ましく、また、命令の実行中、int型の数値が生成され第2のメモリアドレスに格納されることを示すのが好ましい。
【0025】コード検証器20によって生成される型シグネチャは、種々の構文表現で表すことができる。例えば、コード検証器20によって生成される型シグネチャを定義する構文表現は、以下の式に従う。
【0026】inBind|inType→outType|outBindここで、inBindは消費された変数の型記述を表し、inTypeはスタック28から消費された値の型記述を表し、outBindは生成された変数の型記述を表し、outTypeはスタック28にプッシュされた生成値の型記述を表す。inBind及びoutBindは、vを変数のアドレス、Tを変数の型とするとき、v:Tと表現することができることに注意されたい。
【0027】上述した命令Dの例に従った上記構文式を説明するために、命令Dによって消費される変数のアドレスを「0001」、命令Dによって生成される変数のアドレスを「0010」であるとする。この例では、命令Dの型シグネチャは以下のように表現することができる。
【0028】0001:double|double→int|0010:intコード49における命令の型シグネチャを生成する際に利用することができる構文には他の型があり、コード49の型シグネチャを表現するために採用する構文は、例示の目的で与えているにすぎないことに注意されたい。
【0029】他の実施例では、命令は変数を消費せずint型の2つの数値を消費すると仮定する。また、命令はアドレス「1000」に格納されるdouble型の数値のみを生成するものとする。この例では、命令の型シグネチャは以下のように表現することができる。
【0030】|int,int→ |1000:doubleinBindにある(「|int,int」の前の)スペースは、消費された変数がないことを示し、outTypeにある(「→」と「|1000:double」との間の)スペースの存在は、スタック28にプッシュされる結果(product)がないことを示すことに注意されたい。さらに、最初の「int」後のコンマは、命令によって消費される最初の「int」の他に値があることを示す。より具体的には、第2の「int」(すなわち、コンマに続く「int」)は、スタック28から消費された他の値もまたint型であることを示す。
【0031】命令の実際の実行中に値をプルしプッシュする順序に関らず、inType内の入力値の型記述の位置は命令の実行前のスタック28におけるその値の位置を示し、outType内の出力値の型記述の位置は命令の実行後のスタック28におけるその値の位置を示すことに注意されたい。この点に関して、inTypeにおける右端の型記述は入力スタック(すなわち、命令の実行前のスタック28)の最上値に対応し、inTypeに残っている各ステップは入力スタックの次に深い値に対応する。さらに、outTypeにおける右端の型記述は出力スタック(すなわち、命令の実行後のスタック28)の最上値に対応し、outTypeに残っている各ステップは出力スタックの次に深い値に対応する。入力スタックにおいてinTypeにより記述される値より下にある追加の値と、出力スタックにおいてoutTypeにより記述される値よりしたにある追加の値は、命令によって変更されずに保持されることに注意されたい。
【0032】上述したことを説明するために、命令は以下の型シグネチャを有すると仮定する。
【0033】|String,int→double,float|この命令は、入力スタックの最上部にあるint型の値と、int型の値の直下にあるString型の値を期待する。これらの値はともにこの命令によって消費され、一方は出力スタックの最上部にあるfloat型でありもう一方はfloat値の直下にあるdouble型である2つの他の値によって置き換えられる。
【0034】コード検証器20は、コード49の命令の型シグネチャを定義した後、個々のブロック62〜66の型シグネチャを合成して、個々のブロックの最終の型シグネチャを表す単一の型シグネチャにするように設計される。例えば、コード検証器20は、ブロック62(図4)の型シグネチャを図5において合成シグネチャ72として参照される単一の合成型シグネチャに合成する。また、コード検証器20は、ブロック63〜66の型シグネチャを図5において合成シグネチャ73〜76として参照される単一の型シグネチャにそれぞれ合成する。
【0035】型シグネチャブロック62〜66を合成するために、コード検証器20は、連続する型シグネチャのみを合成するように設計される。2つのシグネチャが「連続する」のは、コード49のプログラムフローに従って、一方のシグネチャが導出された命令と連続する命令からシグネチャの他方が導出された場合のみであることに注意されたい。
【0036】例えば、図3の命令A〜Cが型シグネチャA〜Cにそれぞれ変換されるものとする。この例では、命令Aと命令Bは連続しており、また命令Bと命令Cは連続している。この点に関して、実行時、命令Bは命令Aの直後に実行され、命令Cは命令Bの直後に実行される。さらに、型シグネチャAは命令Aから導出され、型シグネチャBは命令Bから導出される。さらに、命令Aと命令Bは連続している。このように、型シグネチャAと型シグネチャBは連続するので合成することが可能である。しかしながら、命令Aと命令Cは連続しないので、型シグネチャAを命令Cから導出される型シグネチャCと直接合成することは適当でない。
【0037】ブロック62を合成するとき、コード検証器20は、型シグネチャAと型シグネチャBを合成して、結果として合成シグネチャを形成すると仮定する。この合成シグネチャは型シグネチャA及び型シグネチャBから導出されており、従って命令A及び命令Bから導出されている。さらに、命令Bと命令Cは連続するので、上記合成シグネチャは型シグネチャCと連続し、従って型シグネチャCと合成することができる。ブロック62のシグネチャのすべてが単一の合成シグネチャに合成されると、ブロック62の合成は完了する。
【0038】各シグネチャブロック62〜66に対し上述した技術を実行することにより、コード検証器20は、ブロック62〜66を単一の合成シグネチャ72〜76にそれぞれ変換する。そしてコード検証器20は、ブロック62〜66に対する上述と同様の技術を利用して、シグネチャ72〜76を単一の合成シグネチャに合成する。合成プロセス中に連続するシグネチャのみが合成されるのであれば、コード検証器20がシグネチャ72〜76を合成する順序は任意である。
【0039】2つの型シグネチャを合成する場合、コード検証器20は、先の(earlier)型シグネチャの出力型記述が後の(later)型シグネチャの入力型制約にとって受け入れ可能であるか否かを決定するように設計される。プログラムフローにおいて他の型シグネチャの命令より先にある命令のシグネチャであるとき、その型シグネチャは他の型シグネチャより「先」であるということに注意されたい。また、後の型シグネチャの入力型制約を先の型シグネチャの出力型記述と比較することによっていかなる型エラーも検出することができないとき、先の型シグネチャの出力型記述は後の型シグネチャの入力型制約にとって受け入れ可能であるという。
【0040】この点に関して、コード検証器20は、2つの型シグネチャを合成するとき、先の型シグネチャのoutTypeの型記述を後のシグネチャのinTypeの対応する型記述と比較することができる。先のシグネチャのoutTypeの型記述と後のシグネチャのinTypeの型記述とが同じスタック値を示すとき、先のシグネチャのoutTypeの型記述は後のシグネチャのinTypeの型記述に「一致する(correspond)」。例えば、第1の命令を分析することによって、第1の命令がスタック28から「type1」型の値をプルすると決定することができると仮定する。また、その命令が「type2」型の値をスタック28にプッシュし、その後「type3」型の値をスタック28にプッシュすると決定することができると仮定する。さらに、次に連続する命令を分析することによって、その命令がスタック28から「type4」型の値をプルし、その後スタック28から「type5」型の値をプルすると決定することができると仮定する。この命令は、「type6」型の値をスタック28にプッシュすると決定することも可能である。なお、「type1」ないし「type6」は、int型やString型等の型またはクラスをそれぞれ表現している。
【0041】これらの2つの命令は、以下のように表現される2つの型シグネチャに変換することができる。
【0042】|type1→type2,type3||type5,type4→type6|この例では、「type2」と「type5」は同じスタック値(すなわち、先の命令によりスタックにプッシュされた第1の値)を指しており、従って互いに「一致する」。さらに、「type3」と「type4」は同じスタック値(すなわち、先の命令によりスタック28にプッシュされた第2の値)を指しており、従って互いに「一致する」。
【0043】なお、後により詳細に説明する合成技術に従うことにより、後の型シグネチャのinTypeと先の型シグネチャのoutTypeにおける対応する型記述は、inType及びoutTypeにおいて右から同じ位置を占めることが好ましいことに注意されたい。これを他の方法により表現すれば、inTypeが左から右へ一続きの型記述U1〜Unとして表され、outTypeが左から右へ一続きの型記述T1〜Tmとして表される場合(n及びmは等しいかまたは等しくない値の整数値)、n−i=m−jであるとき、UiがTjに対応するということである。さらに、上記実施例において、「type3」は、先のシグネチャのoutTypeにおける右端位置を占め、「type4」は後のシグネチャのinTypeにおける右端位置を占める。このように、「type3」と「type4」は、先のシグネチャのoutTypeと後のシグネチャのinTypeにおける右から同じ位置をそれぞれ占める。結果として、上記シグネチャを分析することによって、「type3」が「type4」に一致すると決定することができる。
【0044】同様に、「type2」と「type5」はともに、先のシグネチャのoutTypeと後のシグネチャのinTypeにおいてそれぞれ右から2番目の位置を占める。従って、上記シグネチャを分析することによって、「type2」は「type5」に一致すると決定することができる。さらに、上述したようにコード検証器20は、inType及びoutTypeにおける型記述の位置を分析するだけで、第1のシグネチャのoutTypeにおける型記述が次に連続するシグネチャのinTypeにおける型記述と一致するか否かを決定する。
【0045】先のシグネチャがoutTypeにおいて後のシグネチャのinTypeの型記述と同じ位置に型記述を含まないとき、上記inTypeの型記述に一致する型記述は先のシグネチャのoutTypeにはないことに注意されたい。このようなinTypeの型記述は、2つのシグネチャの合成中に型エラーのチェックがされない。さらに、後のシグネチャがinTypeにおいて先のシグネチャのoutTypeの型記述と同じ位置に型記述を含まないとき、上記outTypeの型記述に一致する型記述は後のシグネチャのinTypeにはない。このようなoutTypeの型記述は、2つのシグネチャの合成中に型エラーのチェックがされない。
【0046】先に述べたように、2つの連続するシグネチャを合成するとき、コード検証器20は先のシグネチャのoutTypeにおける型記述と後のシグネチャのinTypeにおける対応する型記述を比較する。より具体的には、コード検証器20は、いかなる型エラーも検出できないように、先のシグネチャのoutTypeにおける型記述が後のシグネチャのinTypeにおける対応する型記述にとって受け入れ可能であるか否かを決定する。この点において、命令が第1の型記述によって記述される型の値を生成することができるとき、及び第2の型記述によって記述される型の値を利用するように設計された他の命令が、型エラーを生成することなく、その生成された値を利用することができるとき、第1の型記述は、第2の型記述にとって受け入れ可能である。
【0047】例えば、Java(登録商標)において、int型とString型はともにクラス「オブジェクト」のサブ型であることは周知である。結果として、オブジェクト型の入力を消費するように設計されている命令は、型エラーを引き起こすことなく、String型を生成する命令の結果(product)を消費し、またはint型を生成する命令の結果を消費することが可能である。従って、int型記述とString列型記述はともにオブジェクト型記述にとって受け入れ可能である。
【0048】Java(登録商標)では、int型とdouble型とが異なるクラスであることも周知である。また、int型の入力を消費するように設計されている命令は、型エラーを引き起こすことなくdouble型の入力を消費することはできない。従って、int型記述はdouble型記述にとって受け入れ可能ではない。
【0049】2つのシグネチャが合成されているとき及び先のシグネチャのoutTypeにおける型記述が後のシグネチャのinTypeにおける型記述と一致するとき、先のシグネチャのoutTypeにおける型記述は後のシグネチャのinTypeにおける対応する型記述に対して型チェックされ、その後2つの対応する型記述は除去される(すなわち、合成シグネチャには現れない)。また、先のシグネチャのoutTypeにおける型記述が後のシグネチャのinTypeにおける型記述に一致しないとき、先のシグネチャのoutTypeにおける型記述は合成シグネチャのoutTypeに現れ、後のシグネチャのinTypeにおける型記述が先のシグネチャのoutTypeにおける型記述に一致しないとき、後のシグネチャのinTypeにおける型記述は合成シグネチャのinTypeに現れる。
【0050】加えて、2つのシグネチャを合成するとき、コード検証器20は合成シグネチャに先のシグネチャのinTypeの型記述と後のシグネチャのoutTypeの型記述とを単に挿入する。より具体的には、コード検証器20は先のシグネチャからのinTypeの各型記述を合成シグネチャのinTypeに挿入し、後のシグネチャからのoutTypeの各型記述を合成シグネチャのoutTypeに挿入する。
【0051】従って、上述した実施例では、「type2」が「type5」にとって受け入れ可能である場合、及び「type3」が「type4」にとって受け入れ可能である場合に、2つのシグネチャを正しく合成することができる。上述したことが真であれば、合成シグネチャは以下のようになる。
【0052】|type1→type6|他の実施例では、最先から最後まで連続する4つの型シグネチャを以下のように表現する。
【0053】
|type1→type2,type3| (シグネチャA.1)
|type4→type5| (シグネチャB.1)
|type6→| (シグネチャC.1)
|type7→| (シグネチャD.1)
ここで、「type1」ないし「type7」は、int型やString型等の型記述をそれぞれ表すものとする。この実施例では、シグネチャA.1は、「type1」型の値が「type2」型及び「type3」型の値によりこの順序で置換されることを示している。シグネチャB.1は、「type4」型の値が「type5」型の値によって置換されることを示している。シグネチャC.1は、新たな値を生成することなく「type6」型の値が消費されることを示している。同様に、シグネチャD.1は、「type7」型の値が消費されることを示している。
【0054】シグネチャA.1とB.1とを合成するために、コード検証器20はまず、先のシグネチャのoutTypeと後のシグネチャのinTypeにおけるそれぞれの位置から、「type3」が「type4」に一致することを決定する。こうして、コード検証器20は、「type3」が「type4」にとって受け入れ可能であるか否かを決定する。「type3」が「type4」にとって受け入れ可能でない場合、コード検証器20はエラーを検出する。受け入れ可能である場合、コード検証器20はエラーを検出せず、合成を行うことができる。合成シグネチャを以下のように表現することができる。、|type1→type2,type5|この合成シグネチャは、シグネチャC.1と合成することができる。これら2つのシグネチャを合成するために、コード検証器20はまず、先のシグネチャのoutTypeと後のシグネチャのinTypeにおけるそれぞれの位置から、「type5」が「type6」に一致することを決定する。こうして、コード検証器20は、「type5」が「type6」にとって受け入れ可能であるか否かを決定する。「type5」が「type6」にとって受け入れ可能でない場合、コード検証器20はエラーを検出する。受け入れ可能である場合、合成を行うことができ、合成シグネチャを以下のように表現することができる。
【0055】|type1→type2|この合成シグネチャは、シグネチャD.1と合成することができる。これら2つのシグネチャを合成するために、コード検証器20はまず、先のシグネチャのoutTypeと後のシグネチャのinTypeにおけるそれぞれの位置から、「type2」が「type7」に一致することを決定する。こうして、コード検証器20は、「type2」が「type7」にとって受け入れ可能であるか否かを決定する。「type2」が「type7」にとって受け入れ可能でない場合、コード検証器20はエラーを検出する。受け入れ可能である場合、コード検証器20はエラーを検出せず、合成を行うことができ、合成シグネチャを以下のように表現することができる。
【0056】|type1→|なお、連続したシグネチャのみが合成されるならば、上述した順序でシグネチャが合成される必要はない。例えば、上述したように、コード検証器20は、まずシグネチャA.1とシグネチャB.1を合成して以下のように表される第1の合成シグネチャを生成することができる。
【0057】|type1→type2,type5|第1の合成シグネチャを形成した後、コード検証器は、シグネチャC.1をシグネチャD.1と合成して第2の合成シグネチャを形成することができ、第2の合成シグネチャは以下のように表すことができる。
【0058】|type6,type7→|そして、コード検証器20は、第1の合成シグネチャと第2の合成シグネチャを合成することができる。
【0059】これら2つのシグネチャを合成するために、コード検証器20は、先のシグネチャのoutTypeと後のシグネチャのinTypeにおけるそれぞれの位置に基づいて、「type5」が「type7」に一致することを決定する。また、コード検証器20は、先のシグネチャのoutTypeと後のシグネチャのinTypeにおけるそれぞれの位置に基づいて、「type2」が「type6」に一致することも決定する。こうしてコード検証器20は、「type5」が「type7」にとって受け入れ可能であるか否か、及び「type2」が「type6」にとって受け入れ可能であるか否かを決定する。「type5」が「type7」にとって受け入れ可能でない場合または「type2」が「type6」にとって受け入れ可能でない場合、コード検証器20はエラーを検出する。しかし、「type5」が「type7」にとって受け入れ可能である場合または「type2」が「type6」にとって受け入れ可能である場合は、いかなるエラーも検出されず、合成が可能である。第1の合成シグネチャ及び第2の合成シグネチャの合成は、以下のようになる。
【0060】|type1→|このように、シグネチャを異なる順序で合成しても、上記実施例のどちらの場合でも実質上同じ結果となる。
【0061】2つのシグネチャを合成する際、コード検証器20は、型シグネチャに含まれるあらゆるローカル変数の型記述間に一貫性があるかもチェックする。例えば、特定の型の値がローカル変数に格納されていることをシグネチャが示すと仮定する。そのローカル変数からこの同じ値が後に検索されることを他のシグネチャが示す場合、先のシグネチャによって示される特定の型は、他のシグネチャによって示されるように、その値の型記述にとって受け入れ可能でなければならない。
【0062】好ましい実施形態において上述したことを達成するために、コード検証器20は、合成中に型シグネチャのinBind及びoutBindを分析する。この点に関して、コード検証器20は、2つのシグネチャを合成するとき、後のシグネチャのinBindにおける型記述と先のシグネチャのoutBindにおける型記述を比較する。ある変数の型記述が後のシグネチャのinBindに存在する場合、及び同じ変数の型記述が先のシグネチャのoutBindに存在する場合、2つの型記述は一貫していなければならない。この点に関して、上記outBindの型記述がinBindの型記述にとって受け入れ可能でない場合、コード検証器20はエラーを検出する。受け入れ可能である場合、エラーを検出することなく合成を継続することができる。
【0063】後のシグネチャのinBindと先のシグネチャのoutBindが同じ変数に対して受け入れ可能な型記述を有する場合、コード検証器20は、得られる合成シグネチャに、後のシグネチャのinBindからの型記述を含まない。しかしながら、コード検証器20は、後のシグネチャがoutBindにおいて同じ変数に対する型記述を同様に含まない限り、得られる合成シグネチャのoutBindに先のシグネチャのoutBindからの型記述を挿入する。後のシグネチャがoutBindに同じ変数の型記述を含む場合、コード検証器20は、先のシグネチャのoutBindからの型記述ではなく、後のシグネチャのoutBindからの型記述を挿入する。このような場合、コード検証器20は、先のシグネチャのoutBindにおける変数の型記述と後のシグネチャのoutBindにおける変数の型記述との間に一貫性があるかを必ずしもチェックする必要はない。
【0064】同じ変数の型記述が先のシグネチャのoutBindと後のシグネチャのoutBindの両方に存在する場合、及び同じ変数の型記述が後のシグネチャのinBindに存在しない場合、コード検証器20は、得られる合成シグネチャのoutBindに後のシグネチャの型記述を含むだけである。先のシグネチャの型記述は得られる合成シグネチャには含まれない。このような場合、コード検証器20は、先のシグネチャと後のシグネチャの2つの型記述の間の一貫性をチェックする。この点に関して、先のシグネチャの型記述が後のシグネチャの型記述にとって受け入れ可能でない場合、コード検証器20はエラーを検出する。受け入れ可能である場合、エラーを検出することなく合成を継続することができる。
【0065】さらに、先のシグネチャと後のシグネチャの両方のinBindが同じ変数に対する型記述を有する場合、及び先のシグネチャのoutBindがこの変数に対する型記述を有していない場合、コード検証器20は、得られる合成シグネチャのinBindに先のシグネチャの型記述を含むだけである。後のシグネチャの型シグネチャは得られる合成シグネチャには含まれない。このような場合、コード検証器20は、先のシグネチャと後のシグネチャの2つの型記述の間の一貫性をチェックする。この点に関して、先のシグネチャの型記述が後のシグネチャの型記述にとって受け入れ可能でない場合、コード検証器20はエラーを検出する。受け入れ可能である場合、エラーを検出することなく合成を継続することができる。
【0066】上述した条件のうちの1つが先のシグネチャまたは後のシグネチャのinBindにおける特定の型記述について発生しない場合、コード検証器20は、得られる合成命令のinBindに特定の型記述を含む。さらに、上記条件のうちの1つが先のシグネチャまたは後のシグネチャのoutBindにおける特定の型記述について発生しない場合、コード検証器20は、得られる合成命令のoutBindに特定の型記述を含むことが好ましい。
【0067】合成中のシグネチャのinBind及びoutBindにおける型記述を処理する上述の技術を説明するために、連続する命令のブロックが以下の説明に従って値を消費し生成するものとする。
【0068】第1の命令は、スタック28からの2つの値を消費し、第1のメモリロケーション(例えば、メモリロケーション「0001」)に格納されている第1の変数の値を生成する。第2の命令は、メモリロケーション「0001」に格納されている第1の変数の値を消費し、スタック28にプッシュされる値を生成する。またこの命令は、第2のメモリロケーション(例えば、メモリロケーション「0010」)に格納されている第2の変数に対する値も生成する。第3の命令は、スタック28からの値を消費し、第2の変数に対して他の値を生成する。第4の命令は、メモリロケーション「0001」に格納されている第1の変数の値を消費し、スタック28にプッシュされる2つの値を生成する。最後の命令は、メモリロケーション「0010」に格納されている第2の変数の値を消費し、さらにスタック28からの値を消費する。この最後の命令は、第1の変数に対する値も生成する。
【0069】上述の命令セットの型シグネチャは、以下のように表すことができる。
【0070】|type1,type2→|0001:type3 (シグネチャA.2)
0001:type4|→type5|0010:type6 (シグネチャB.2)
|type7→|0010:type8 (シグネチャC.2)
0001:type9|→type10,type11|(シグネチャD.2)
0010:type12|type13→|0001:type14(シグネチャE.2)
ここで、「type1」ないし「type14」は、int型やString型等の型記述をそれぞれ表す。上述したように、上記型シグネチャは異なる順序で合成することができるが、コード検証器20はこれらシグネチャを最後から最先に(すなわち、シグネチャE.2からシグネチャA.2に)合成すると仮定する。こうして、コード検証器20はまず、シグネチャE.2をシグネチャD.2と合成する。
【0071】これら2つのシグネチャを合成する際、コード検証器20は、「type11」が「type13」と一致することを決定する。従って、コード検証器20は、「type11」が「type13」と一貫するか、または言い換えれば「type11」が「type13」にとって受け入れ可能であるか否かを決定する。これら2つの型が一貫しない場合、コード検証器20はエラーを検出する。一貫する場合は、合成を継続することができる。
【0072】合成を実行する際、コード検証器20は、合成シグネチャのinBindに、シグネチャD.2のinBindからの型記述と、SinatureE.2のinBindからの型記述を含む。コード検証器20は、合成シグネチャのoutBindに、シグネチャE.2のoutbindからの型記述も含む。コード検証器20は、これら型記述の間でいかなる一貫性チェックをも実行する必要はない。合成シグネチャは以下のように表すことができる。
【0073】0001:type9,0010:type12|→type10|0001:type14コード検証器20は、この合成シグネチャをシグネチャC.2と合成する。上記合成シグネチャのinBindは、第2の変数に対する型記述を含み、シグネチャC.2(すなわち、この合成における先のシグネチャ)のoutBindは、同じ変数についての型記述を含む。従って、合成を実行する際、コード検証器20は、これら型記述が一貫しているか否かを決定する。より具体的には、コード検証器20は、「type8」が「type12」にとって受け入れ可能であるか否かを決定する。「type8」が「type12」にとって受け入れ可能でない場合、コード検証器20はエラーを検出する。受け入れ可能である場合は、コード検証器20は、合成の継続を許可する。
【0074】合成を継続する場合、新たに合成されたシグネチャに上述したinBind型記述を含む必要はないことに注意されたい。この新たに合成されたシグネチャは以下のように表すことができる。
【0075】0001:type9|type7→type10|0001:type14,0010:type8コード検証器20は、この合成シグネチャをシグネチャB.2と合成する。この合成において、「type5」は「type7」と一致し、従って、コード検証器20は、「type5」が「type7」にとって受け入れ可能であるか否かを決定する。「type5」が「type7」にとって受け入れ可能でない場合、コード検証器20はエラーを検出する。受け入れ可能である場合、コード検証器20は合成の継続を許可する。
【0076】上記合成を実行する際、コード検証器20は、先のシグネチャ(すなわち、シグネチャB.2)のinBindが変数(すなわち、アドレス「0001」に関連する変数)の型記述を含むことを決定し、後のシグネチャ(すなわち、上記合成シグネチャ)のinBindが同じ変数に対する型記述を含むことを決定する。従って、コード検証器20は、これら型記述に一貫性があるかをチェックする。より具体的には、コード検証器20は、「type4」が「type9」にとって受け入れ可能であるか否かを決定する。「type4」が「type9」にとって受け入れ可能でない場合、コード検証器20はエラーを検出する。受け入れ可能である場合、コード検証器20は、合成の継続を許可し、得られる合成シグネチャのinBindに先のシグネチャからの型記述(すなわち、「0001:type4」)を含み、後のシグネチャからの型記述(すなわち、「0001:type9」)を破棄する。
【0077】コード検証器20はまた、先のシグネチャ(すなわち、シグネチャB.2)のoutBindが変数(すなわち、アドレス「0010」に関連する変数)の型記述を含むことを決定しなければならず、コード検証器20は、後のシグネチャ(すなわち、上記合成シグネチャ)のoutBindが同じ変数についての型記述を含むことを決定しなければならない。従って、コード検証器20は、これら型記述の一貫性があるかをチェックする。より具体的には、コード検証器20は、「type6」が「type8」にとって受け入れ可能であるか否かを決定する。「type6」が「type8」にとって受け入れ可能でない場合、コード検証器20はエラーを検出する。受け入れ可能である場合、コード検証器20は、合成の継続を許可し、得られる合成シグネチャのoutBindに後のシグネチャからの型記述(すなわち、「0010:type8」)を含み、先のシグネチャからの型記述(すなわち、「0001:type6」)を破棄する。新たに合成されたシグネチャは以下のように表すことができる。
【0078】0001:type4|→type10|0001:type14,0010:type8コード検証器20は、この合成シグネチャをシグネチャA.2と合成する。この合成において、先のシグネチャ(すなわち、シグネチャA.2)のoutBindは、アドレス「0001」に関連する変数の型記述を含み、後のシグネチャ(すなわち、上記合成シグネチャ)のinBindは、この同じ変数についての型記述を含む。従ってコード検証器20は、これら型記述に一貫性があるかをチェックする。より具体的には、コード検証器20は、「type3」が「type4」と一貫するか、または言い換えれば「type3」が「type4」にとって受け入れ可能であるか否かを決定する。「type3」が「type4」にとって受け入れ可能でない場合、コード検証器20はエラーを検出する。受け入れ可能である場合、コード検証器20は、合成の継続を許可する。なお、コード検証器20は、「type3」と「type8」との間に一貫性があるかをチェックしないことに注意されたい。新たに合成されたシグネチャ、つまりシグネチャブロック全体について得られるシグネチャは、以下のように表すことができる。
【0079】|type1,type2→type10|0001:type14,0010:type8この時点で、シグネチャブロックの合成は完了する。
【0080】命令のうちあるものは値を消費するかまたは生成することができ、その値の型は型変数によって示されることは周知である。値を消費しまたは生成する命令を分析するのみでは、このような値に二特定の型記述を割り当てることはできない。しかし、型変数を他のシグネチャの型記述と比較することによって、その値に関連する型エラーがあるかチェックすることは可能である。このような型チェックを実行する方法の一例を以下で説明する。
【0081】好ましい実施形態では、型変数の型シグネチャにおける型記述として型変数の名前が使用される。従って、「0001」として参照される特定のメモリロケーションに格納される、「example」という名の型変数によって示される型を有する入力をある命令が消費すると仮定する。また、その命令はスタック28に上記値をプッシュすると仮定する。型シグネチャは、以下のように表すことができる。
【0082】
0001:example|→example|合成中に他の型記述に対して一貫性があるか型変数をチェックする場合、型変数の名前は任意の名前に置き換えられ、この名前は他の型記述と相関付けられる。例えば、次に連続する命令が実行時にスタック28からの値を消費し、この次の命令を分析することによってスタック28からプルされたこの値が「type1」と呼ばれる特定の型であることを決定することができると仮定する。なお、「type1」は、例えばString型、int型またはdouble型等の任意の型またはクラスでよいことに注意されたい。次に連続する命令の型シグネチャは、以下のように表すことができる。
【0083】|type1→|この実施例では、型変数「example」は、先のシグネチャのoutTypeと後のシグネチャのinTypeのそれぞれの位置により、型記述「type1」に一致する。従って、型エラーがない場合、型変数「example」は「type1」にとって受け入れ可能でなければならない。
【0084】2つのシグネチャを合成する際、コード検証器20は、型変数を「example1」等の任意の名前に改名するように構成される。コード検証器20は、2つのシグネチャの合成を以下のように表すことができる。
【0085】location1:example1|→example1:type1このように、コード検証器20は、エラーを検出することなく合成を行うことを可能にするが、型変数に対する制約があることを示す。より具体的には、「example1:type1」は、シグネチャの型変数が「type1」に制約されることを示している。
【0086】上述したことを説明するために、連続する命令のブロックが実行時に以下の説明に従って値を消費し生成すると仮定する。
【0087】第1の命令は、スタック28からの値を消費し、第1のメモリロケーション(例えば、メモリロケーション「0001」)に格納される値を生成する。第2の命令は、メモリロケーション「0001」からの型変数「example」によって示される型を有する値を消費し、スタック28にプッシュされる値を生成する。第3の命令は、スタック28からの値を消費し、メモリロケーション「0001」に格納される値を生成する。第4の命令は、メモリロケーション「0001」からの型変数「example」によって示される型を有する値を消費し、スタック28にプッシュされる値を生成する。最後の命令は、スタック28から値を消費し、第2のメモリロケーション(例えば、「0010」)に格納される値を生成する。
【0088】上記の命令セットの型シグネチャは、以下のように表すことができる。
【0089】
|type1→|0001:type2 (シグネチャA.3)
0001:example|→example|(シグネチャB.3)
|type3→|0001:type4 (シグネチャC.3)
0001:example|→example|(シグネチャD.3)
|type5→|0010:type6 (シグネチャE.3)
ここで、「type1」ないし「type6」は、int型、String型等の型記述を表す。上述した型シグネチャは、上述したように異なる順序で合成することができるが、コード検証器20は最後から最先へこれらのシグネチャを合成すると仮定する。このため、コード検証器20はまず、SinatureE.3をシグネチャD.3と合成する。
【0090】上述した2つのシグネチャを合成する際、コード検証器20は、型変数を「example1」等の任意の名前に改名し、型変数「example1」が「type5」に制約されていることを示す。得られる合成シグネチャは以下のように表すことができる。
【0091】0001:example1|→|0010:type6example1:type5コード検証器20は、上記シグネチャをシグネチャC.3と合成する。これらシグネチャを合成する際、コード検証器20は、「type4」が「type5」にとって受け入れ可能であるか否かを決定する。「type4」が「type5」にとって受け入れ可能でない場合、コード検証器20はエラーを検出する。しかし、「type4」が「type5」にとって受け入れ可能である場合、コード検証器20はエラーを検出せず、合成の継続を許可する。得られるシグネチャは、以下のように表すことができる。
【0092】|type3→|0010:type6,0001:type4コード検証器20は、上記シグネチャをシグネチャB.3と合成する。2つのシグネチャを合成する際、コード検証器20は、シグネチャB.3の型変数「example」を「example2」等の任意の名前に改名し、「example2」が「type3」に制約されることを示す。得られる合成シグネチャは、以下のように表すことができる。
【0093】0001:example2|→|0010:type6,0001:type4example2:type3コード検証器20は、上記シグネチャをシグネチャA.3と合成する。これらシグネチャを合成する際、コード検証器20は、「type2」が「type3」にとって受け入れ可能であるか否かを決定する。「type2」が「type3」にとって受け入れ可能でない場合、コード検証器20はエラーを検出する。しかし、「type2」が「type3」にとって受け入れ可能である場合、コード検証器20はエラーを検出せず、合成の継続が可能となる。なお、コード検証器20は、「type2」と「type4」との間の型チェックは実行しないことに注意されたい。得られるシグネチャは、以下のように表すことができる。
【0094】|type1→|0010:type6,0001:type4この時点で、シグネチャブロックの合成は完了する。
【0095】型エラーを検出すると、エラーハンドラ24を呼び出すようにコード検証器20を構成してもよいことに注意されたい。エラーハンドラ24は、種々の方法によって検出された型エラーを処理するように構成することができる。好ましい実施形態では、エラーハンドラ24は、エラーが検出されたことを示す通知メッセージを送信する。このメッセージは、出力装置36を介してユーザに表示される。また、エラーハンドラ24は、チェックされているコード49をシステム10が実行しないことを保証するために何らかの必要なステップをとる。
【0096】本明細書で説明する型シグネチャの構文に従って型シグネチャを表現することは必ずしも必要ではない、ということにも注意されたい。また、各命令について入力型制約と出力型記述を表すために多数の方法及び構文を採用することができる。従って、型シグネチャを定義し合成するために、多数の方法及び構文を採用することができる。
【0097】本明細書で説明する技術を利用することにより、コード検証器20は、コード49を複数の型シグネチャに変換し、これらのシグネチャを単一の型シグネチャに合成する。さらに上述したように、コード49は、プログラム12内のメソッドであってよく、プログラム12内の各メソッドは、本明細書で説明する技術に従って検査される。コード49がプログラム12内のメソッドを表す場合、このプログラムについて決定される制御フローの要件に対してメソッドの最終的な合成シグネチャをチェックすることが可能であることに注意されたい。
【0098】例えば、メソッド全体に対する入力型制約を表す最後のシグネチャの入力型記述をチェックすることにより、そのメソッドの入力型制約がメソッドの引数型によって満足されることを保証することができる。また、メソッド全体に対する出力型結果を表す最後のシグネチャの出力型記述をチェックすることにより、メソッドの結果型が満足されることを保証することができる。さらに、異なる命令ブロックの最後のシグネチャを比較することにより、同時に生じるいくつかの制御フロー(例えば、条件文または条件式から生じる制御フロー)の出力型の結果が共存することを保証することができる。また、異なる命令ブロックの最後のシグネチャを比較することにより、異なる制御フロー間での選択に利用する値の出力型がそれらの使用と共存することを保証することができる。例えば、IF文または式から生じる異なる制御フロー間での選択に利用する値の出力型をチェックすることにより、出力型がブール型であることを保証することができる。
【0099】周知のコード検証技術を利用する従来からのコンパイラは、上記内容と同じかまたは同様の条件について一般にチェックを行うことに注意されたい。当業者には、この開示により、異なるメソッドの最後のシグネチャを利用することで、これらの同じまたは同様の条件についてチェックを行うことが可能であることは明らかであろう。
【0100】(動作)ブロッキングシステム20の好ましい使用及び動作と関連する方法を以下に説明する。
【0101】従来技術により、コンパイル済みのコード49のセットがメモリ15にダウンロードされる。システム10によってコード49が実行される前に、コード検証器20はまず、コード49に型エラーがないかチェックする。この点に関して、図6のブロック105で示すように、コード検証器20はコード49を分析してコード49のプログラムフローを決定し、コード49を複数のコードブロック52〜56(図3)に細分またはグループ化する。ブロック107において、コード検証器20は、コード49の各命令を型シグネチャに変換することによって、コードブロック52〜56をシグネチャブロック62〜66に変換する。次いで、ブロック111及び115で示すように、コード検証器20はシグネチャブロック62〜66のうちの1つを選択し、選択したブロック62〜66のシグネチャの各々を合成して、選択したブロック62〜66について単一の型シグネチャを形成する。ブロック121及び123で示すように、ブロック115で型エラーが検出された場合、コード検証器20はエラーハンドラ24を呼び出し、コード検証プロセスは終了する。
【0102】一例として、ブロック52〜56のうちの1つが以下のJava(登録商標)命令を含むと仮定する。
【0103】aload_0000 //ローカル型変数0000からロードinvoke string_length //文字列の長さを計算するJava(登録商標)関数呼出しiload_0001 //ローカル変数0001からint型をロードiadd //2つの整数の合計を計算istore_0010 //ローカル変数0010に整数を格納上記命令は、コード検証器20により以下の型シグネチャを有するシグネチャブロック62〜66に変換される。
【0104】
0000:example|→example|(シグネチャA.4)
|String→int| (シグネチャB.4)
0001:int|→int| (シグネチャC.4)
|int,int→int| (シグネチャD.4)
|int→|0010:int (シグネチャE.4)
ここで、「example」は型変数である。コード検証器20は上述したシグネチャブロック62〜66を選択し、連続するシグネチャのみがいずれかの単一シグネチャに合成される限り任意の順序で上記シグネチャを合成する。この点に関して、コード検証器20はまず、シグネチャA.4及びB.4を単一のシグネチャに合成すると仮定する。この合成中、コード検証器20は型変数名「example」を「example1」に変更すると仮定する。合成後、シグネチャは以下のように表される。
【0105】
0000:example1|→int| example1:String (シグネチャAB.4)
0001:int|→int| (シグネチャC.4)
|int,int→int| (シグネチャD.4)
|int→|0010:int| (シグネチャE.4)
次に、コード検証器20がシグネチャE.4とD.4とを合成すると仮定する。この合成中、コード検証器20は、シグネチャD.4のoutTypeについての型記述「int」がシグネチャE.4のinTypeについての型記述「int」にとって受け入れ可能であることを決定する。これら型記述が受け入れ可能でなかった場合(例えば、シグネチャE.4のinTypeがint型ではなくdouble型であった場合)、コード検証器20は、型エラーを検出しブロック115を終了する。そしてコード検証器20は、エラーハンドラ24を呼び出す。しかしながら、この実施例では上記型記述は受け入れ可能であるため、コード検証器20はシグネチャD.4とE.4との合成を完了し、選択したブロック62〜66のシグネチャは以下のように表される。
【0106】
0000:example1|→int| (シグネチャAB.4)
example1:String 0001:integer|→int| (シグネチャC.4)
|int,int→|0010:int (シグネチャDE.4)
次に、コード検証器20はシグネチャAB.4をシグネチャC.4と合成すると仮定する。この合成の完了後、選択したブロック52〜56のシグネチャは、以下のように表される。
【0107】
0000:example1,0001:int|→int,int| (シグネチャABC.4)
example1:String |int,int→|0010:int (シグネチャDE.4)
次に、コード検証器20は残りの2つのシグネチャを合成すると仮定する。この合成中、コード検証器20は、シグネチャABC.4のoutTypeの型記述「int,int」がシグネチャDE.4のinTypeの型記述「int,int」にとって受け入れ可能であると決定する。これら型記述が受け入れ可能で無かった場合(例えば、最後のシグネチャのinTypeが「int,int」ではなく「double,int」かまたは「int,double」であった場合)、コード検証器20は型エラーを検出し、ブロック115を終了する。そしてコード検証器24は、エラーハンドラ24を呼び出す。しかしながら、この実施例において上記型記述は受け入れ可能であるため、コード検証器20は、残りの2つのシグネチャの合成を完了し、選択したブロック62〜66の最後のシグネチャは以下のように表される。
【0108】0000:example1,0001:int|→|0010:int他の実施例では、、コードブロック52〜56を定義するために命令の他のセットを利用することができることに注意されたい。このような実施例では、異なる命令は異なるシグネチャに変換され、従って、選択されたブロック62〜66の型シグネチャの合成プロセスは異なる。しかしながら、当業者には、このような選択されたブロック62〜66のシグネチャを合成するために同様の技術を採用することができることは明らかであろう。
【0109】図6のブロック115で選択されたシグネチャブロック62〜66のシグネチャを正しく合成した後、図6のブロック112、115、121、125及び127によって示すように、新たなシグネチャブロック62〜66が選択され、この新たなシグネチャブロック62〜66に対して上記プロセスが繰返される。このように、各シグネチャブロック62〜66は、それぞれ単一の型シグネチャに合成される。
【0110】各シグネチャブロック62〜66が単一の型シグネチャにそれぞれ合成された後、コード検証器20は、図6のブロック132で、ブロック62〜66のすべてについての単一の型シグネチャが残るまでシグネチャブロック62〜66の型シグネチャを合成し始める。ブロック115でシグネチャを合成するために採用されたのと同じ技術を、ブロック132でシグネチャを合成するために採用することができる。ブロック132で型エラーが検出されると、ブロック123及び135で示すように、コード検証器20はブロック132を終了しエラーハンドラ24を呼び出す。ブロック132が型エラーを検出することなく完了すると、コード検証プロセスは完了し、プログラム12はコード検証器20によりエラーがないと立証される。これにより、システム10はプログラム12を実行することができる。
【0111】ブロック115と同様にブロック132において、コード検証器20は、連続するシグネチャのみが単一の合成シグネチャに合成される限り、任意の順序で型シグネチャを合成することができる。例えば、ブロック52が最初に実行されるコードブロックであることをプログラム12のプログラムフローが示すと仮定する。ブロック52の実行後、次に実行されるブロックはブロック54である。ブロック53は、ブロック55に続いて実行される。ブロック56は最後に実行されるブロックである。
【0112】ブロック132において、コード検証器20は、プログラム順にブロック62〜66のシグネチャを合成することができる。この実施例では、コード検証器20は、ブロック62のシグネチャをブロック64のシグネチャと合成することにより合成シグネチャを形成する。この合成シグネチャをブロック63のシグネチャと合成することにより新たな合成シグネチャを形成する。この新たな合成シグネチャをブロック65のシグネチャと合成することにより別の新たな合成シグネチャを形成する。この新たな合成シグネチャをブロック66のシグネチャと合成することにより、プログラム12全体に対する最後の合成シグネチャである最後のシグネチャを形成する。しかし、例えばブロック62とブロック63がプログラム12のプログラムフロー内で連続しないために、コード検証器20はブロック62のシグネチャをブロック63のシグネチャと直接合成しない場合もあることに注意されたい。
【0113】別の実施例では、コード検証器20は、逆のプログラム順序でブロック62〜66のシグネチャを合成することができる。この実施例では、コード検証器20は、ブロック66のシグネチャをブロック65のシグネチャと合成することにより合成シグネチャを形成する。この合成シグネチャをブロック63のシグネチャと合成することにより新たな合成シグネチャを形成する。この新たな合成シグネチャをブロック64のシグネチャと合成することにより、別の新たな合成シグネチャを形成する。この新たな合成シグネチャをブロック62のシグネチャと合成することにより、プログラム12全体に対する最後の合成シグネチャである最後のシグネチャを形成する。
【0114】さらに別の実施例では、コード検証器20は、連続するシグネチャのみが合成されるのであれば任意の方法でブロック62〜66のシグネチャを合成することができる。例えば、コード検証器20はまず、ブロック62と64のシグネチャを合成することにより第1の合成シグネチャを形成する。ブロック66と65のシグネチャを合成することにより第2の合成シグネチャを形成する。ブロック63と64のシグネチャを合成することにより第3の合成シグネチャを形成する。第1の合成シグネチャを第3の合成シグネチャと合成することにより、第4の合成シグネチャを形成する。最後に、コード検証器20は、第4の合成シグネチャを第2の合成シグネチャと合成することにより、プログラム12全体に対する最後の合成シグネチャである最後のグネチャを形成する。
【0115】Java(登録商標)で記述された命令を処理するものとして本発明を多数の実施例で説明してきた。しかしながら、本発明はこれに限定されず、他のタイプの言語からの命令も同様に、本明細書で説明した技術に従って、型シグネチャに変換され型チェックを受けることができることは明らかであろう。
【0116】本発明には、例として以下の実施形態が含まれる。
【0117】1.コンパイル済みのプログラム(12)を格納するメモリ(15)と、前記プログラム(12)の命令を分析し、該命令に基づいて複数の型シグネチャを生成し、該型シグネチャを分析することにより型エラーを検出するように構成されたコード検証器(20)と、を含み、前記型シグネチャはそれぞれ前記命令の1つについて入力型制約と出力型記述を示す、コード検証システム。
【0118】2.前記コード検証器(20)は、前記複数の型シグネチャのうちの1つの型シグネチャを他の型シグネチャと合成することにより単一の合成シグネチャを形成し、前記1つの型シグネチャの入力型制約が前記他の型シグネチャの出力型記述にとって受け入れ可能であるか否かの決定を行い、該決定に基づいて前記型エラーを検出するように構成される、上記1に記載のコード検証システム。
【0119】3.前記コード検証器(20)は、前記プログラムを分析して該プログラムの命令を複数のコードブロック(52〜56)にグループ化し、それぞれが1つまたは複数の型シグネチャを有する型シグネチャブロック(62〜66)に前記コードブロック(52〜56)を変換し、前記型シグネチャブロック(62〜66)の型シグネチャを単一の合成型シグネチャに合成するようにさらに構成される、上記1に記載のコード検証システム。
【0120】4.前記コード検証器(20)は、前記型シグネチャブロック(62〜66)のうちの1つを合成する際、該1つの型シグネチャブロック(62〜66)内に含まれる第1の型シグネチャと第2の型シグネチャを合成することにより単一の合成シグネチャを形成し、前記第1の型シグネチャの入力型制約が前記第2の型シグネチャの出力型記述にとって受け入れ可能であるかの決定を行い、該決定に基づいて前記型エラーを検出するようにさらに構成される、上記3に記載のコード検証システム。
【0121】5.複数の命令を含む少なくとも1つのコードブロック(52〜56)を有するコンパイル済みのプログラム(12)を格納するステップと、前記命令を複数の型シグネチャに変換するステップと、前記型シグネチャを単一の合成型シグネチャに合成するステップと、前記型シグネチャを分析するステップと、前記分析するステップに基づいて型エラーを検出するステップと、を含むコード検証方法。
【0122】6.前記複数の型シグネチャのうちの1つの型シグネチャは、前記複数の命令のうちの1つの命令が実行されるときに該1つの命令によって消費される入力の型を示す型記述を含み、前記複数の型シグネチャのうちの別の型シグネチャは、前記複数の命令のうちの別の命令が実行されるときに該別の命令によって生成される出力の型を示す型記述を含み、前記分析するステップは、前記2つの型記述を比較するステップを含む、上記5に記載のコード検証方法。
【0123】7.前記プログラム(12)の命令を複数のコードブロック(52〜56)にグループ化するステップと、前記コードブロック(52〜56)をそれぞれが1つまたは複数の型シグネチャを有する型シグネチャブロック(62〜66)に変換するステップと、前記型シグネチャブロック(62〜66)のそれぞれの型シグネチャを単一の合成型シグネチャに合成するステップと、をさらに含む上記5に記載のコード検証方法。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013