図面 (/)

技術 複数の意味レベルによるアスペクト指向プログラミングのための方法

出願人 ゼロックス・コーポレーション
発明者 ジョンオーランピング
出願日 2003年1月15日 (17年10ヶ月経過) 出願番号 2003-006816
公開日 2003年8月22日 (17年2ヶ月経過) 公開番号 2003-233499
状態 特許登録済
技術分野 ストアードプログラム制御 ストアードプログラム ストアードプログラム
主要キーワード 形式構造 レベル関数 命令的 処理程度 入力アレイ 織込み 例示的実施 特定ループ
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2003年8月22日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (8)

課題

複数の意味レベルによるアスペクト指向プログラミングの方法を提供する。

解決手段

アスペクトには、1つまたは複数のオブジェクトプログラム・データに関して、基本レベル利用可能な情報よりも多くの情報へのアクセスを必要とするものがある。アスペクト指向プログラミング・システム、方法、および環境のアスペクトは、1段階で計算結果を調べる。このアスペクトは、後続計算段階だけに影響を及ぼし、したがって循環は存在しない。また、局所的または大域的カスタムフロー分析を各段階で実施して、非局所的な情報をプロパゲートすることもできる。コード・ブロックを操作することではなく、様々な計算段階の結果を操作することからみてプログラミングを容易にすることができるので、「マクロスタイルのプログラミングを削減または回避することができる。

概要

背景

現在、複雑なソフトウェア・システムを構成する際の主要な概念は、オブジェクト指向プログラミングパラダイムである。オブジェクト指向プログラミングの背後にある考え方は、ソフトウェア・システムをクラス、オブジェクトメソッド(すなわち関数)などの小さなモジュラーユニットに細分するものである。コンパイル時、オブジェクト指向プログラミングで使用される各モジュラー・ユニットは、別々のコード・ブロックにおよそ対応する。これらのコード・ブロックは他のブロックの構造に関係なく実行されるので、不要な冗長演算がしばしば生じる。したがって、メソッド同士が「話す」ことができれば、ソフトウェア・システムの速度全体を向上させることができる。時間に依存する大きなソフトウェア・システムの中には、メソッド同士が「話す」ことから大きな利益を得ることができるものがある。

アスペクト指向プログラミングでは、プログラマは、オブジェクト指向プログラミングと同様に、抽象化および分解を用いて大きな問題をより小さい管理可能な下位部分に分割することができる。ただし、問題は、関数に基づく分解ではなくアスペクトに基づく分解に従って細分する。アスペクトは、メソッド間の「会話」を容易にする。さらに、アスペクト同士が「話す」または横断することができ、その結果、横断的実行可能プログラムが得られる。

概要

複数の意味レベルによるアスペクト指向プログラミングの方法を提供する。

アスペクトには、1つまたは複数のオブジェクトのプログラム・データに関して、基本レベル利用可能な情報よりも多くの情報へのアクセスを必要とするものがある。アスペクト指向プログラミング・システム、方法、および環境のアスペクトは、1段階で計算結果を調べる。このアスペクトは、後続計算段階だけに影響を及ぼし、したがって循環は存在しない。また、局所的または大域的カスタムフロー分析を各段階で実施して、非局所的な情報をプロパゲートすることもできる。コード・ブロックを操作することではなく、様々な計算段階の結果を操作することからみてプログラミングを容易にすることができるので、「マクロスタイルのプログラミングを削減または回避することができる。

目的

効果

実績

技術文献被引用数
1件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

データ処理デバイスを操作する命令コンパイル可能なプログラミング要素を単純化する方法であって、プログラミング要素が少なくとも1つの部分を有し、前記方法が、プログラミング要素を、その少なくとも1つの部分がすべて第1段階に達するまで単純化して、現段階の単純化済みプログラミング要素を生み出す工程と、現段階の単純化済みプログラミング要素について少なくとも1つのプロパゲータを決定することであって、プロパゲータがプログラミング要素中に記述される工程と、決定した少なくとも1つのプロパゲータを使用して、少なくとも1つのプロジェクションを現段階の単純化済みプログラミング要素に関連付ける工程と、現段階の単純化済みプログラミング要素および関連するプロジェクションに少なくとも部分的に基づいて、現段階の単純化済みプログラミング要素を、その少なくとも1つの部分がすべて次の段階に達するまで単純化して、次段階の単純化済みプログラミング要素を生み出す工程とを含むことを特徴とする方法。

請求項2

プログラミング要素を、データ処理デバイスを操作する命令にコンパイル可能な複数の織込みコード・ブロックに変換する方法であって、(a)プログラミング要素中で、少なくとも1つの共通の変数と少なくとも1つの共通のプロセスとのうちの少なくとも1つを識別する工程と、(b)識別した、少なくとも1つの共通の変数と少なくとも1つの共通のプロセスとのうちの少なくとも1つに基づいて、プログラミング要素を少なくとも1つの意義簡約する工程と、(c)少なくとも1つの意義を第1の織込みコード・ブロックに組み込むこと、(d)組み込んだ意義のうち、方法の後続のステップ更新可能なものを0個、1個、または複数決定する工程と、(e)決定の結果に基づいて、第1の織込みコード・ブロックの決定された更新可能な意義に対して任意の所望の更新を実施するのに使用できるプロパゲータを呼び出す工程と、工程(a)〜(e)を少なくとも1回繰り返して、直前に生み出された織込みコード・ブロックに基づいて後の織込みコード・ブロックを生み出す工程とを含み、さらに、(f)前に生み出された少なくとも1つの織込みコード・ブロックのプロパゲータと通信して、前記前に生み出された少なくとも1つの織込みコード・ブロックの意義のいずれかが後の織込みコード・ブロックと共通かどうかを決定する工程と、および(g)少なくとも1つの後の織込みコード・ブロックおよび前に生み出された少なくとも1つの織込みコード・ブロック中で、後の織込みコード・ブロックと前記前に生み出された少なくとも1つの織込みコード・ブロックとに共通の意義があればそれを更新する工程とを含むことを特徴とする方法。

技術分野

0001

本発明は、汎用の意味不変コンストラクト言語を使用したアスペクト指向プログラミングのための方法およびシステムに関する。

背景技術

0002

現在、複雑なソフトウェア・システムを構成する際の主要な概念は、オブジェクト指向プログラミングパラダイムである。オブジェクト指向プログラミングの背後にある考え方は、ソフトウェア・システムをクラス、オブジェクトメソッド(すなわち関数)などの小さなモジュラーユニットに細分するものである。コンパイル時、オブジェクト指向プログラミングで使用される各モジュラー・ユニットは、別々のコード・ブロックにおよそ対応する。これらのコード・ブロックは他のブロックの構造に関係なく実行されるので、不要な冗長演算がしばしば生じる。したがって、メソッド同士が「話す」ことができれば、ソフトウェア・システムの速度全体を向上させることができる。時間に依存する大きなソフトウェア・システムの中には、メソッド同士が「話す」ことから大きな利益を得ることができるものがある。

0003

アスペクト指向プログラミングでは、プログラマは、オブジェクト指向プログラミングと同様に、抽象化および分解を用いて大きな問題をより小さい管理可能な下位部分に分割することができる。ただし、問題は、関数に基づく分解ではなくアスペクトに基づく分解に従って細分する。アスペクトは、メソッド間の「会話」を容易にする。さらに、アスペクト同士が「話す」または横断することができ、その結果、横断的実行可能プログラムが得られる。

0004

米国特許第5,882,593号

発明が解決しようとする課題

0005

既存の様々な汎用アスペクト指向プログラミング技法によれば、基本プログラムの演算をインターセプトおよび調停することが可能である。しかし、これらの技法は、オブジェクトまたはメソッドの基本レベル現在利用可能なプログラム・データの限られた同じ視点によって制限される点で、制約を受ける。アスペクトには、1つまたは複数のオブジェクトのプログラム・データに関して、基本レベルで利用可能な情報よりも多くの情報へのアクセスを必要とするものもある。

0006

以上に示したアスペクト指向プログラミングの例のコンテキストでは、アスペクトの目的およびその要件循環があるせいで、望まれる多くの実装形態で、従来のアスペクト指向プログラミング技法の実施に明白な困難があることは明らかである。すなわち、特定のアスペクトは、そのアスペクトが必要とするデータを得るための計算にアクセスする必要がある。しかし、アスペクト自体が計算に影響を及ぼす。言い換えれば、アスペクトは、その演算を実施するために、アスペクトがそれに対して後で何をするかによって少なくとも部分的に決定されることになるオブジェクトまたはモジュールによって何かを見る必要がある。

課題を解決するための手段

0007

オブジェクトがオブジェクト指向プログラム中の独特のコード・セットであるのと同様に、「アスペクト」は、アスペクト指向プログラム中の独特のコード・セットである。本発明によるシステム、メソッド、およびアスペクト指向プログラミング言語環境の、様々な例示的実施形態では、アスペクトは、1段階で計算結果を調べる。このアスペクトは、後続計算段階だけに影響を及ぼし、したがって循環は存在しない。

0008

本発明の一つの側面によれば、データ処理デバイスを操作する命令にコンパイル可能なプログラミング要素を単純化する方法であって、プログラミング要素が少なくとも1つの部分を有し、前記方法が、プログラミング要素を、その少なくとも1つの部分がすべて第1段階に達するまで単純化して、現段階の単純化済みプログラミング要素を生み出す工程と、現段階の単純化済みプログラミング要素について少なくとも1つのプロパゲータを決定することであって、プロパゲータがプログラミング要素中に記述される工程と、決定した少なくとも1つのプロパゲータを使用して、少なくとも1つのプロジェクションを現段階の単純化済みプログラミング要素に関連付ける工程と、現段階の単純化済みプログラミング要素および関連するプロジェクションに少なくとも部分的に基づいて、現段階の単純化済みプログラミング要素を、その少なくとも1つの部分がすべて次の段階に達するまで単純化して、次段階の単純化済みプログラミング要素を生み出す工程とを含む。

発明を実施するための最良の形態

0009

図1に、従来のアスペクト指向プログラミング環境100の例示的な一実施形態を示す。図1には特に、従来のアスペクト指向プログラミング言語を使用してどのようにプログラミング要素が実行可能ソフトウェア・モジュールに変換されるかを示す。図1に示すように、1つまたは複数の高レベルコンピュータ・プログラミング要素120が、アスペクト指向ウィーバ(weaver)110に提供される。アスペクト指向プログラミング環境100内のアスペクト指向ウィーバ110は、高レベル・コンピュータ・プログラム要素120のそれぞれを1つまたは複数の実行可能モジュールにコンパイルする。アスペクト指向ウィーバ110は、静的と動的のいずれかとすることができる。自動アスペクト指向ウィーバ110は、静的な織込みプロセス(weaving process)を実装する。静的な織込みプロセスは、クラス・ソース・コードなどの高レベル・プログラミング要素120中のジョインポイントにアスペクト特有ステートメントを挿入することにより、このような高レベル・プログラミング要素120を修正する。本質的に、アスペクト指向ウィーバ110は、所望のアスペクト・コードをクラスにインラインする。この結果、高度に最適化された織込みコード(woven code)が得られる。

0010

図1には、汎用アスペクト指向プログラミング言語環境100のアスペクト指向ウィーバ110に1つまたは複数の高レベル・プログラミング要素120が入力されるのが示されている。第1段階で、アスペクト指向ウィーバ110は、織込みコードすなわち混ざり合ったコードを生み出す。図1に示すように、高レベル・コンピュータ・プログラミング要素120のうちの1つからのプログラミング・ブロック122は、変数123と、変数123の1つまたは複数に作用する1つまたは複数のプロセスまたはメソッド124とに細分される。次いでアスペクト指向ウィーバ110は、このプログラミング・ブロック122を調べ、このプログラミング・ブロック122の様々なプロセス124の1つまたは複数の内部で1つまたは複数の変数123が重複する箇所を決定する。次いでアスペクト指向ウィーバ110は、コードを結合して、すなわち「織り込んで」、混ざり合ったソース・コード・ブロック130を生み出す。

0011

織込みプロセスの第2段階で、結合したまたは織り込んだプログラム・コード・ブロック130を1つまたは複数の実行可能モジュール140にコンパイルする。図1に示すように、この第2段階では、アスペクト指向ウィーバ110は、織込みコード・ブロック130のうちの1つをとる。アスペクト指向ウィーバ110は、この織込みコード・ブロック130の織り込まれた変数131および織り込まれたプロセス133を、1つまたは複数の実行可能モジュール140にコンパイルする。

0012

様々な例示的実施形態で、本発明によるシステムおよび方法は、エイブルソンサスマン、サスマンによる「The Structure and Interpretation of Computer Programs」に記述されているScheme言語など、ラムダ算法に基づく言語に対して機能する。この言語では、基本演算は関数生成および関数適用である。関数はラムダ式で生成され、通常これは「lambda(var*)exp」の形式である。例えば、式「lambda(xy)(+(*2x)y)」は、その第1の引数を2倍にしてから、2倍にした第1の引数をその第2の引数に加える関数を定義する。「exp」の部分はラムダ式の本体と呼ばれ、「var*」の部分はその引数と呼ばれる。関数は「fnarg*」の形式の適用式によって適用されるが、「fn」は適用される関数を指し、「arg*」は引数である。「fn」の部分は、ラムダ式でもよく、あるいは関数を評価する式ならどんなものでもよい。計算は、ラムダ式の適用を簡約することによって継続する。ラムダ式を簡約することは一般に、それらの変数の出現にそれらの引数を代入することによって行う。

0013

プログラミング言語は、式の値の考え方を中心に構築される。プログラム・モジュールは本質的に、式を値に変換することによって実行される。というのは、値はプログラム・モジュールの実行中に順に回すことができるが、式はそうすることができないからである。変数は、値を生み出す式に束縛されるのではなく、これらの値に束縛される。式が評価された後で、変数が束縛され、変数への後続の参照は、値だけにアクセスすることができる。

0014

しかし本発明は、アスペクト指向プログラミングにおいて、決定または計算された値だけではなく、値がどのように計算または決定されたかに関係する他の何らかの新生エンティティが、情報のクリティカルな要素である場合があることを発見した。値の抽象化によって廃棄されるいくつかの新生エンティティがクリティカルな情報である場合があるので、関数に関数の引数の値だけを提供すれば十分であるとは限らない。

0015

プログラム・ブロックに関するちょうどよい種類の情報だけを保存して、そのプログラム・ブロックに関する残りの情報は単純化する、プログラミング言語またはプログラミング言語環境が必要とされている。当然、本発明によれば、「ちょうどよい」ものは、どんなプログラム要素が情報を使用しているかに応じて異なることになる。値だけよりも多くの情報が必要とされるとき、本発明によるシステム、メソッド、およびアスペクト指向プログラミング環境は、必要とされる情報だけを提供すべきである。

0016

式を評価するときは、値だけが欲しいときもあるが、より多くの情報が必要なときもある。例えば、ループの結果であるアレイだけが欲しいときもあり、アレイが特定のループまたは関数の結果であることを知ることが重要なときもある。言い換えれば、式はアレイを意味するときもあり、アレイだけよりも多くのものを意味するときもある。本発明によるシステム、方法、およびプログラミング環境では、これらのあり得る意味のそれぞれを、式の意義(significance)と呼ぶ。式の値は、情報提供が最も少ない意義である。その他の意義はどれも、値によって取り込まれる情報よりも多くの情報を取り込むことになる。

0017

本発明によるプログラミング・システム、方法、およびプログラミング環境は、意義の概念を、計算が作用することのできるものに変える。本発明によるプログラミング・システム、方法、およびプログラミング環境では、計算プロセスは、式をその意義のカノニカル表現になるまで単純化するものと考えることができる。当然、効率的な実装形態は、中間式をそれぞれ明示的に構築することを避けるが、このような実装形態が行う作業は、連続する中間式の間を進む作業に似ている。

0018

計算の各ステップは、結果としての最終的な意義を保存するので有効である。2つの意義に違いがある場合は、この2つの意義は同じ単純化ステップを許可しないことになる。

0019

本発明は、任意の2つの意義の違いが、どの計算単純化ステップがこの2つの意義によって許可されるかという点だけにあると認識するシステム、方法、およびプログラミング環境を実現する。このことは、式の意義を決定することが、その意義によって許可される計算単純化を実施することと等価であることを意味する。さらに、いくつかの意義が、より多くの情報を提供するものからより少ない情報を提供するものまで順序付けられる場合は、これらの意義を順に決定することができる。これは、まず最も多くの情報を提供する意義によって許可される単純化を実施し、次いで、次に多くの情報を提供する意義によって許可される単純化を実施し、以下同様にすることを含む。

0020

個別に書かれた各ライブラリがそれ自体の意義を導入できるようにし、これらの導入された意義をそのプログラム中で使用できることが望ましいので、すべての意義に対する総合的な順序は必要ないことを理解されたい。この結果、あらゆる意義は対応する処理段階を有することになる。したがって、計算は、連続的な諸段階を通して式を単純化することに対応し、各段階は、連続的な意義の1つについての、式のカノニカル表現である。

0021

本発明によるシステム、方法、およびプログラミング環境はまた、ある意義で利用可能な情報にアクセスするだけでなく、いずれかの意義に対してどの単純化を行うべきかを指定する言語コンストラクトも必要とする。さらに、どの単純化を行うべきかを決定することは、どの関数呼出し展開すべきかを決定することを含む。後述するように、本発明によるシステムおよび方法は、どの段階で関数を簡約すべきかを指定するプログラミング形式を導入する。本質的にラムダ式は、簡約される段階まではデータ・オブジェクトのようにふるまう。簡約された時点で、ラムダ式は関数のようにふるまう。

0022

他方で、意義によって提供される追加の情報は、簡約されない関数呼出し中に含まれる。この情報へは、式の意義が特定の関数の適用であるかどうかをプログラムがテストすることのできる形式によってアクセスする。式の意義は、関数のデータへのアクセス主体のようにふるまう。

0023

式の意義は、式の値の決定に向けた段階なので、意義は常に、少なくとも値と同量の情報を含む。しかし、式の値の決定に向けた方向にない、式に関する他の情報にも用途がある可能性がある。これをサポートするために、本発明によるシステム、方法、およびプログラミング環境は、プロジェクションを用いてこのような情報をカプセル化する。プロジェクションは、意義に対して相対的に定義され、追加情報(通常、所与の計算の残りにおけるその意義の役割に関する)を提供する。プロジェクションの結果は値とすることができる。ただし、結果は、プロジェクションがある段階の意義とすることもできる。これは、プロジェクションが、後で総計算に組み込むことのできる計算断片を覚えていることができることを意味する。

0024

式の意義は基本的にその式に局所的なものだが、プロジェクションはこれとは異なり、より大きな計算における式の役割を反映する。これは、フロー分析と同種の技法を用いてプロジェクションが計算されることを意味する。これをサポートするために、本発明によるシステム、方法、およびプログラミング環境は、「プロパゲータ」と呼ぶ機構を提供する。プロパゲータは、マッチする意義それぞれに対して実行され、そのようなマッチする意義と、そのようなマッチする意義の引数との、1つまたは複数のプロジェクションを調査および更新する。

0025

プロパゲータは、上方向と下方向の両方のデータ・フローを行うことができる。上方向プロパゲータは、引数プロジェクションを調べ、式全体のプロジェクションを更新する。対照的に、下方向プロパゲータは、所与の式全体のプロジェクションを調べ、引数プロジェクションを更新する。

0026

プロパゲータは更新を実施するので、特定の意義の中に埋め込まれた識別の意味を公開する。プロパゲータが所与の意義のプロジェクションを更新するとき、この更新は、同じ意義への他の参照からしか見えない。プロパゲータは意義に対して定義されるので、意義の識別が問題となる。

0027

図2に示すように、本発明によるシステム、方法、およびプログラミング環境では、織込みプロセスはいくつかの段階を通して行われる。所与のプログラム要素が、連続する意義段階を通して単純化されるが、これらの段階の多くはコンパイル時に行われる。異なる程度の処理が様々な段階によって表されているが、最も単純な織込みは、2つの段階、すなわち第1段階および最終段階を生成するだけである。

0028

図2に示すように、様々な例示的実施形態で、第1段階は構文段階210である。この構文段階210では、所与の高レベル・コード・ブロック122からの局所的情報は廃棄されておらず、コンテキスト情報利用不可能である。これは、この高レベル・コード・ブロック122の元の構文に対応する。本発明によるシステム、方法、およびアスペクト指向プログラミング環境では、アスペクト指向ウィーバ110は、高レベル・コード・ブロック122から構文段階210を「織り込む」。構文段階210は、織込みコード・ブロック220を含む。次いで構文段階210は、構文段階210で生成した織込みコード・ブロック220を次の中間段階230に出力する。次の中間段階230は、アスペクト指向ウィーバ110によって織込みコード・ブロック220から織り込まれる。各段階210、230、250、270の後、段階210、230、または250に対応する織込みコード・ブロック220、240、または260中で定義された1つまたは複数のプロパゲータが実行されて、その段階210、230、または250で定義されるプロジェクションが決定される。次いで、これらのプロジェクションは、後続の段階230、250、および270でそれぞれ利用可能である。

0029

図2に示すように、第1段階210が織り込まれた後で、第1の中間段階230が織り込まれる。これは、高レベル・コード・ブロック122に含まれるプログラム・コードをさらに最適化することにつながる。前と同様、この第1の中間段階230の織込みコード・ブロック240は、次の中間段階に入力される。最後の中間段階250が前の中間段階(図示せず)から織込みコード・ブロック245を受け取るまで、これが繰り返し行われる。

0030

図2に示すように、最後の中間段階250で、すべての最適化織込みが完了する。この最後の中間段階250から出力される織込みコード・ブロック260が、最終織込み段階270に入力される。最終織込み段階270は、処理済み値の段階である場合が多いことを理解されたい。次いで、最終織込み段階270から出力される織込みコード280が、実行可能プログラム・モジュールに、または実行可能プログラム・モジュールのセットにコンパイルされる。

0031

式が値に簡約されていないときであって、その式の適用を簡約すべきかどうかを本発明によるシステム、方法、およびプログラミング環境が知る必要があるとき、本発明によるシステム、方法、およびプログラミング環境は、その式を現段階中に簡約すべきでないと推定する。

0032

プロパゲータが完全に実行されるように、プロパゲータは、プログラムまたはプログラム要素セットが中間段階にある間は、プログラムまたはプログラム要素セットと距離を置いた関係を維持する。プロパゲータは、プログラムまたはプログラム要素セットからの、意義に束縛された変数を有することになる。しかしプロパゲータは、制約された方式でしかこれらの変数を使用することができない。最初にプロパゲータは、プロパゲータが動作する段階まで論理的に実行されるが、これらの変数の束縛にはアクセスできない。すなわち、このような変数は本質的に、未束縛の変数として扱われる。次いで、プログラムまたはプログラム要素セットから、各変数が適切な意義に束縛され、プロパゲータは実行を終了する。しかし、プロパゲータは一般に、プログラムまたはプログラム要素セットに束縛された変数に後の意義を要求することができない。後の意義にアクセスしようとしても、やはりこのような変数を未束縛と見なすことになる。プロパゲータがその結果として意義を出力できるようにするために、プロパゲータは、後述する特別な形式を用いて、プロパゲータがアクセスしている意義以上に単純化すべきでないコードを囲むことができる。

0033

プログラマが、様々な演算をアレイに対して実施するコードを書きたいと思っているとする。通常、プログラマは、各アレイにわたってループして新しいアレイを生み出すコードを書くことになる。プログラマは、様々なプリミティブ演算を行うルーチンを定義し、次いで、定義したプリミティブ演算を使用する高レベル演算を構築する。プログラマは、あるルーチンの出力アレイを別のルーチンの入力アレイとして使用することはしばしばある。この場合、プログラマは、融合ループを使用して結合演算を行いたい。これは、普通の関数プログラミングでは行うことができない。というのは、第2の演算を実行できるようになる前に第1の演算を実行しなければからである。ループ融合を自動的に行うオプティマイザもあるであろうが、オプティマイザは通常、不明瞭である。したがって、様々な例示的実施形態で、先に概説したシステム、方法、およびプログラミング環境を使用して、プリミティブ演算のライブラリを生み出すことができる。このライブラリ中では、演算はどのように相互と融合するかを知っており、ライブラリ・ルーチンが組み合わせて使用されるときに融合が起こる。したがって、様々な例示的実施形態で、先に概説したシステム、方法、およびプログラミング環境によれば、ライブラリ・プログラマが、ルーチンが共に融合するように定義することができる。

0034

様々な例示的実施形態で、先に概説したシステム、方法、およびプログラミング環境は、ライブラリ・ルーチンがループ融合を行えるようになるにはどの機能を最低必要とするかをねることにより、ループ融合に適用することができる。概して言えば、潜在的なループは、「自分の入力が、あるループによって計算されたことになる場合は、そのループの内部演算およびそれが作用したことになるアレイを与えよ。そうすれば、それを自分のループ中で使用する。」と尋ねることができる必要がある。このように言う擬似コードの例は以下のとおりである。
(define pointwise
(lambda (fn arg)
(case arg
((ptw-loop inner-fn inner-arg) (inner-fn inner-arg)
(ptw-loop (lambda (x) (fn (inner-fn x)))
inner-arg))
(else
(ptw-loop fn arg)))))

0035

ここで、「pointwise」は、アレイにわたって関数をマッピングする関数だが、「pointwise」は、ループ融合について知っている。このケース形式は、「(ptw−loop inner−fn inner−arg)の形式の式によって「arg」が計算されたことになるか?」と言っている。構文「(inner−fn inner−arg)」は、パターン定数である「ptw−loop」に対して、「inner−fn」および「inner−arg」がパターン変数であることを示す。引数がマッチする場合は、内部ループの関数は、「pointwise」からの関数で構成されるべきである。この場合、構成された関数を使用して単一ループを実施すべきである。そうでない場合は、単純なループを使用する。具体的には、以下に示すように「ptw−loop」を定義して、実際のループを実施することができる。
ID=000003HE=030 WI=073 LX=1135 LY=1950

0036

以下のライブラリ・コードが式と共に使用される場合は、「double−plus」の実装は、各要素を2倍にしてから1を足す単一ループであるべきである。
ID=000004HE=040 WI=050 LX=0350 LY=0300

0037

「pointwise」の定義の鍵は、ケース・ステートメントの意味「...によって「arg」が計算されたことになるか」の中の「ことになる」である。このケースは、引数を計算したことになるループをテストする必要がある。具体的には、「pointwise」は、得られるアレイまでずっと見ることなく、ループによって計算される関心のある情報を、その引数の表面的な構造を通して見ることを欲する。

0038

したがって、「pointwise」は、関数とマクロとの間の何かである必要がある。具体的には、「pointwise」は、それが関心を持つ情報を見ることができるように、その引数が部分的に処理されるようにする必要がある。しかし、「pointwise」の引数が完全に評価されると、「pointwise」が関心を持つまさにその情報を除去することにつながるので、「pointwise」はそうしたくはない。したがって、様々な例示的実施形態で、先に概説した本発明によるシステム、方法、およびプログラミング環境は、これらの両極間の処理レベルを認識し、認識したこれらの処理レベルへのアクセスを提供する。

0039

以下、本発明によるシステム、方法、およびプログラミング環境の基本的な形式、すなわちステートメントおよび/またはコンストラクトを示す。本発明によるシステム、方法、およびプログラミング環境の「case」ステートメントの一般的な形式は以下のとおりである。
case stage value (model (var*) exp*)* [(else exp)]

0040

「case」ステートメントでは、各モデルは式である。変数は、モデル中では解放されており、式中では束縛されている。値は、連続して各モデルと比較される。値にマッチする第1のモデルでは、その式がケースの値として選択される。式はモデルの変数にアクセスすることができ、これらの変数は束縛されてマッチを形成する。

0041

比較は、指定の意義の値とモデルとの間で論理的に行われる。比較は、指定の処理段階の後は行われない。また、式の単純化はゆっくりと行われる。

0042

以下に示す「if」ステートメントは、ステートメント「case value exp1 (nil( ) exp3) (else exp2))」に対する追加の構文構造を提供する。

0043

if exp1 exp2 exp3
以下に示す「deconstruct」ステートメントは、ステートメント「case stage value (model (var*) exp*) (else (error))」に対する追加の構文構造を提供する。
deconstruct stage value model (var*) exp*

0044

ステートメント「reduction stage」は、「exp」の値の呼出しを指定の段階で簡約すべきであることを指定する。
reduction-stage stage exp

0045

適用ステートメントは、関数の本体がその簡約段階に達したときに簡約されることを表す。このステートメントにはキーワードがないが、単に関数「fn」を示す式で始まる。fn exp*

0046

「lambda」ステートメントは、以下の関数を定義する。
lambda (var* [.var] [=> var]) exp*

0047

形式「=>var」は、表される変数を定義される関数の結果に束縛するのに使用される。

0048

ステートメント「stage」は、段階を宣言し、宣言した段階が所与の段階よりも後であることを定義する。
stage name [:below stage]

0049

ステートメント「projection」は、段階に関する情報を提供するプロジェクションを宣言する。
projection name :depends-on stage

0050

ステートメント「propagator」は、プロパゲータを生成する関数を宣言するように働く。
propagator stage [:bottom-up | :top-down] function

0051

一般に、プロパゲータは、いくつかの項のプロジェクションを調べ、その他を更新することになる。プロジェクタの動作は、プロパゲータが調べたが更新はしなかったプロジェクションによって決まると仮定される。これらのプロジェクションがこの段階で動作する他のプロパゲータによって変更された場合は、このプロパゲータは再実行される。「:bottom−up」および「:top−down」のヒントは、再計算の必要を最小限に抑えるための、プロパゲータを実行する最も効率的な順番を識別する。

0052

プロパゲータが見る項は、ラムダ定義、ラムダ変数、適用、およびケース形式である。ラムダ式が簡約されている場合、プロパゲータは、簡約の結果を見ることになる。これにより、プログラム・ツリーは効果的に有向グラフに変わる。具体的には、ラムダ本体の中でラムダ変数を参照した各ポイントで、実際の引数が、すべて変数使用であったものの間で共用されて現れることになる。プロパゲータからは、意義に束縛された変数が見られることはなく、意義だけしか見られないことを理解されたい。

0053

ステートメント「update」は、プロパゲータの実行中だけに現れることのある形式を定義する。
update old new

0054

このステートメントは、プロパゲータが適用される段階における項プロジェクションを評価すべき「old」の値を、「new」の値で更新する。

0055

ステートメント「same frequency」は、プロパゲータの実行中だけに生じることのある形式を定義する。
same-frequency exp

0056

このステートメントは、式評価の頻度とプロパゲータが扱っている項の頻度が同じである場合に真を返す。

0057

これが意味することの例として、以下の式を考えてみる。
(let ((x (+1 2)))
(lambda (y) (*xy))

0058

「let」コマンドまたは演算は、最も早い処理段階で展開されることを理解されたい。ここで、乗算項の引数の1つは、加算演算である。ラムダが介在するので、この加算演算は、乗算演算と同じ回数にわたって実行されることにはならない。プロパゲータは、これに反応できる必要がある。実行頻度が異なる場合は他に、あるケース・ブランチ中の項がケース外の変数を参照するときにも生じる。

0059

別の見方では、プロパゲータがランタイムの前に実行されるので、プロパゲータの1つの呼出しが、それが処理する意義の多くの呼出しに対応することがある。これは、プロパゲータが処理するすべての下位項が主要項の呼出しごとに1度呼び出される限りは問題ではない。しかし、例が示すように、常にそうであるとは限らない。プロパゲータは、異なる頻度の意義に関連する情報を更新する際は注意する必要がある。「same frequency」ステートメントは、プロパゲータがこの状況を検出する方法を提供する。

0060

図3乃至5に、ループ融合を実施するためのサンプル・コード・セグメントを示す。このサンプル・コードは、あるループの結果が他のいくつかのループによって使用される場合の、すべてではないが多くを扱うものである。

0061

行1〜3は、フロー処理が作用することのできる種々の情報を記述する。この情報は、単純化の最も少ないレベルにおける、式についての異なる3つの意義と項についての固有の識別子とを含む。行2は、この値をハッシュ・テーブルから得るためのキーを定義する。行3は、おそらく他にもある中でこの値を計算することになるループを定義する。共用を可能にするために、行3で定義されるプロジェクションは、このループによって計算される値のうちの1つだけについてループを保持することになる。他の値に対するプロジェクションは、このループによって計算される他の何らかの値についての(loop−referencevalue)を保持することになる。この連鎖に従うことにより、最終的にはこのループを保持する値に至る。

0062

行4〜6は、トップレベル関数を定義する。行7〜(終わり)は、簡約されたpointwise演算を定義するサブルーチン・ライブラリを定義する。行8は、トップ・レベルのラムダ式を簡約できるようにし、効果的にand!の定義をマクロにする。行11〜39は、各形式をその値を計算するループで装飾するプロパゲータを定義する。行37が実行されたときは、これは、このケースが「pointwise」でないことを示し、留意されるように出力が必要であるようにする。行39〜46は、値を計算するpointwiseループを返す。これは、必要ならトリビアルなループを作ることを含む。行43および44は、簡約をループ融合後に簡約可能にする。行47〜50は、値がループによって計算された場合にそのループを返すことを示す。行51〜57は、引数を計算するためのループを保持するcomputing−loopを伴う値を返す。行58〜69は、結果に対するこの形式の需要を記録する。行70〜79は、引数に対する実際のアレイが必要とされることを示す。

0063

行80〜100では、pointwiseループの構造すなわち「ptw−loop」が、複数の値でループを生成することを含めて融合を容易にするように設計される。これを可能にするために、入力および出力にはキーで名前が付けられ、これにより、名前付けは融合の下でも変化する必要はない。これらのキーは、ループ融合時の間だけ存在する。すなわち、これらのキーは、ランタイムまでには単純化されて取り去られることになる。行93では、ステートメント「fn」が、キー/値の対のリストと、それに対するキー/値の対の増補リストをとる。「入力」は、「fn」によって期待されるIDを含めた、キー/アレイの対のリストである。「出力」は、キーのリストであり、これらのキーは、fnが出力するキーの中になければならない。ループは、アレイの対応要素にわたって関数をマッピングし、出力ID中の各キーに対するエントリを有するキー/アレイの対のリストを返す。行101〜103は、前段階でプロパゲータによって構築された、その結果を計算するループから、正しい結果を返すためのpointwise演算を定義する。

0064

行104〜117は、2つのpointwiseループの作業を結合して行ってそれらの入力および出力を結合するループを返す。行115は、内部定義された関数がループ融合後に簡約可能であることを示す。行118〜125は、対のリスト中にキーがあると推定して、リスト中でキーを検索する。行119は、これがランタイム前に行われることを示す。行126および127は、2つのリストをマージする動作が、リスト中でIDを見つける動作と同様にしてコード化されることを示す。

0065

ウィーバの基本動作は次のとおりである。プログラムから開始する。プログラムのすべての部分が第1段階に達するまで、プログラムを単純化する。この段階についてのプロパゲータを実行して、単純化されたプログラムをプロジェクションで装飾する。次に、プログラムのすべての部分が次の段階に達するまで、プログラムをもう少し単純化する。この単純化の間、前段階からの単純化済みプログラムと、プロパゲータによって加えられる装飾は、さらに単純化されたプログラムがどのようなものかを決定するのに利用可能なデータである。このプロセスを、プログラムの最終段階に達するまで繰り返す。プログラムの各部分は、各段階で意義を有する。問題は、プログラムのこのような部分のいずれかをある段階から次の段階まで簡約して、その部分が次の段階でその意義を正しく示すようにしなければならないかどうかである。

0066

図6に、本発明によるシステム、方法、およびプログラミング環境を用いた、プログラムのコンパイル中または織込み中における図2に示した段階間の関係の例示的な一実施形態を示す。図6に示すように、1つまたは複数のプログラミング要素のセット120が、コンパイルされるようにアスペクト指向ウィーバ110に入力される。アスペクト指向ウィーバ110は、1つまたは複数のプログラミング要素のセット120に共通の変数および演算があるかどうか調べ、1つまたは複数のプログラミング要素120を適切な意義に簡約する命令310を与える。図6に示すように、1つまたは複数のプログラミング要素のセット120中で、3つの意義A、B、Cが識別される。3つの意義A、B、Cは、図2に関して先に概説した第1段階210に対応する第1段階の分析の結果として生成される、第1段階織込みコード・ブロック320に組み込まれる。

0067

次に、アスペクト指向ウィーバ110は、プロパゲータ間可視性パス325に沿って命令を送ることにより、プロジェクタ330を呼び出す。プロジェクタ330は、第1段階織込みコード・ブロック320を調べ、意義A、B、Cのうちのどれが次の織込み中に更新可能かを決定する。例えば、図6に示す例示的な実施形態では、プロジェクタ330は、意義AおよびBが更新可能と識別する。プロジェクタ330は、意義AおよびBに対する更新が未来にあればそれらを実施するために、プロジェクタ/プロパゲータ・パス327に沿ってプロパゲータ335を生み出す。次いで、アスペクト指向ウィーバ110は次の織込み段階に進む。

0068

第2の織込み段階では、図2に関して先に概説したように、アスペクト指向ウィーバ110は、第1段階織込みコード・ブロック320を第2段階または中間段階の分析への入力として使用する。アスペクト指向ウィーバ110は、第1段階織込みコード・ブロック320を調べて、共通の変数および/または演算があれば識別し、第1段階織込みコード・ブロック320を適切な意義に簡約する命令332を送る。図6に示すように、第1段階織込みコード・ブロック320中で、3つの意義D、E、Fが識別される。3つの意義D、E、Fは、図2に関して先に概説した中間段階230に対応する第2段階の分析の結果として生成される、第2段階織込みコード・ブロック340に組み込まれる。

0069

再びアスペクト指向ウィーバ110は、プロパゲータ間可視性パス345に沿って命令を送ることにより、プロジェクタ350を呼び出す。プロジェクタ350は、未来の織込みによってもたらされるかもしれない意義が第2段階織込みコード・ブロック340中にあるかどうか調べる。例えば、図6に示す例示的な実施形態では、プロジェクタ350は、意義Eがこの基準に合うと決定する。プロジェクタ350は、プロジェクタ/プロパゲータ・パス347を使用して、意義Eについてのプロパゲータ355を生み出す。次いでプロパゲータ355は、プロパゲータ間可視性パス337を使用してプロパゲータ335と通信して、更新すべきものがあるかどうかを決定する。この特定の例では、共通の重要性はない。すなわち、第1段階織込みコード・ブロック320と第2段階織込みコード・ブロック340の両方で継続する意義はない。したがって更新は必要ない。

0070

続いて第3の織込み段階で、アスペクト指向ウィーバ110は、第2段階織込みコード・ブロック340を最後の段階の分析への入力として使用する。前述のように、アスペクト指向ウィーバ110は、第2段階織込みコード・ブロック340を調べて、共通の変数および/または演算があれば識別し、第2段階織込みコード・ブロック340を適切な意義に簡約する命令342を送る。図6に示すように、第2段階織込みコード・ブロック340中で、3つの意義A、G、Hが識別される。3つの意義A、G、Hは、図2に関して先に概説した最終段階270に対応する第3段階の分析の結果として生成される、第3段階織込みコード・ブロック360に組み込まれる。

0071

次いで、アスペクト指向ウィーバ110は、相互運用性パス365に沿って命令を送ることにより、第3のプロジェクタ370を呼び出す。プロジェクタ370は、意義AおよびHが更新可能と決定する。プロジェクタ370は、意義AおよびHについてのプロパゲータ375を、プロジェクタ/プロパゲータ・パス367に沿って生み出す。次いでプロパゲータ375は、プロパゲータ間可視性パス357に沿ってプロパゲータ355と通信する。プロパゲータ375は、第2段階コード・ブロック340と第3段階コード・ブロック360との間に共通の意義がなく、更新が必要ないと決定する。

0072

プロパゲータ375はまた、別のプロパゲータ間可視性パス377に沿ってプロパゲータ335とも通信し、第1段階織込みコード・ブロック320と第3段階織込みコード・ブロック360との間で意義Aが共通であると決定する。次いでプロパゲータ375は、第1段階織込みコード・ブロック320および第3段階織込みコード・ブロック360中の、意義Aへの参照すべてを更新する。これにより、織込みコードが後に正しく実行されることが確実になる。前述のようにこのプロセスは、すべてのコードが完全に織り込まれ、したがって完全に最適化されるまで継続する。

0073

図7に、ループ融合の例についての織込みプロセスを示す。アスペクト指向ウィーバ110は、高レベル・プログラム・コード・ブロック420を読み込む命令410を構文段階430に与える。この高レベル・プログラム・コード・ブロック420は、織込みプロセスの第1段階すなわち構文段階430で第1段階コード・ブロックとして使用されるように提供される。次いで、アスペクト指向ウィーバ110は、構文段階430で第1段階コード・ブロック420を調べて、第1段階コード・ブロック420全体で共通の変数および演算を識別する。アスペクト指向ウィーバ110は、命令435を使用して構文段階430を制御する。この例では、構文段階430と最終段階480との間に2つの中間段階がある。構文段階430から出力された織込みコード・ブロック440は、第1の中間段階450に入力されるが、この例示的な実施形態では、この第1の中間段階450はループ構造段階と呼ぶことができる。

0074

次に、アスペクト指向ウィーバ110は、第1段階織込みコード・ブロック440を調べ、ループ構造段階450に命令455を与える。ループ構造段階450の間の処理で、第1段階コード・ブロック420のループによって計算されるアレイの候補ループ構造が公開される。ループ構造段階は、第2段階織込みコード・ブロック460を出力する。ループ構造はアレイにわたって明示的なマッピング関数を実施するので、残念ながら、特定ループの値をループ構造段階450から直接計算することはできない。この状況では、ランタイム前に内部ループ関数を簡約する方が望ましい。したがって、ループ構造を簡約済みループに変形する必要がある。この変形は、計算段階470によって実現される。

0075

続いてアスペクト指向ウィーバ110は、第2段階織込みコード・ブロック460に含まれるループ構造を簡約する命令475を計算段階470に与える。これに応答して、計算段階470は、第3段階織込みコード・ブロック480を出力する。これは、完全に織り込まれた最終的な段階である。この最終段階コード・ブロック480はまた、値段階コード・ブロック480とも呼ぶ。次いで、最終段階コード・ブロック480は、コンパイラ490に出力される。コンパイラ490は、信号チャネル495を介したアスペクト指向ウィーバ110の制御下で、完全に織り込まれた値段階ブロック480をコンパイルして、実行可能コード・ブロック500を形成する。実行可能コード・ブロック500は、コンパイラ490から出力される。

0076

問題は、ライブラリがループを融合する度に、ライブラリは、その引数のループの新しい作業実行を必要とする場合があることである。引数が共用される場合、重複する計算が生じる。これに対する解決法の1つは、引数が共用される場合にはループを融合しないことである。別の解決法は、共用される引数の使用すべてを反映する単一のループを生成することである。

0077

前述の解決法のいずれかを採用する場合、引数がプログラム中の他の箇所でどのように使用されるかに関する情報を知ることが必要である。すなわち、ライブラリ・コードは、その直接の引数だけでなく、より広いコンテキストに関するいくらかの情報にアクセスできる必要がある。ライブラリ・コードは、その引数に関係する何らかのデータ・フロー情報を必要とする。これには、より多くの言語機能が必要である。

0078

より単純な回答を実現するには、引数が共用されるなら融合しない場合に、ライブラリ・コードは、「自分に渡されようとしている引数が他の箇所でも使用されるか?」といったように尋ねる必要がある。この質問には、どの段階かにかかわらず、単にその引数を計算するコードを見るだけでは回答できないことを理解されたい。この質問への回答は、引数がどのように計算されるかではなく、どのように使用されるかにある。さらに、この質問への回答は、引数識別の認識、すなわち、同じ引数が他の箇所で使用されることが意味するものの認識に依拠する。

0079

したがって、これをサポートするために、様々な例示的実施形態で、先に概説したシステム、方法、およびプログラミング環境は、項プロジェクションの概念をサポートする。プロジェクションは、項に関する情報を提供する。この情報は通常、項自体からは入手不可能だがその使用のコンテキストからは入手可能な情報である。したがって、様々な例示的実施形態で、先に概説したシステム、方法、およびプログラミング環境は、プロジェクション・コンテキスト情報を計算するために、別のコンストラクトとして前述のプロパゲータを導入する。プロパゲータは、適切な段階の項と照合され、次いで項または項の下位項のプロジェクションに関する情報を公開することができる形式である。最初、プロジェクションの値は、項が空のコンテキスト中で見られることを意味するデフォルトに設定される。プロパゲータが実行される中で、プロパゲータはコンテキストのピクチャを埋める。したがってプロパゲータは、命令的にコード化される間、項のコンテキストに関する限界インクリメンタルに上げるように動作する。

0080

以下の擬似コードは、項が2回以上使用されるかどうかを計算する。
ID=000005HE=055 WI=080 LX=0200 LY=0450

0081

この例が機能するようにするには、新しい段階として、ループ融合段階の前に実施される動作段階を導入する必要がある。ループの結合である「double」のような定義は、この段階で簡約され、それにより、ループ結果の使用が見えるようになる。このようにすれば、長い範囲のフロー分析は必要ない。問題となるのはプログラマが関心を持つプロシージャだけなので、いくつかのプロシージャを通して1つの形式に従う必要はない。ループ構造決定時に形式構造へのアクセスを有するプロシージャが、それを直接受け取るプロシージャである。

0082

ただし、この機構は、長い範囲のフロー分析を実施することもできる。これは、途中で情報を蓄積してプロパゲートすることによって行う。実際、この機構は、図2および6に関して先に論じたような、共有の第2の手法すなわち単一の大きな融合ループの生成を表すのに十分なものである。

図面の簡単な説明

0083

図1プログラミング間の従来の関係を示す図である。
図2本発明のシステムおよび方法による、意味ベースのアスペクト指向プログラミング環境でプログラミング要素の様々な段階によって表される種々の処理程度の例示的な一実施の形態である。
図3本発明によるシステムおよび方法を用いてループ融合を達成するためのプログラムの例示的な擬似コード・リストである(図3乃至5でひとつの疑似コード・リストを示す)。
図4本発明によるシステムおよび方法を用いてループ融合を達成するためのプログラムの例示的な擬似コード・リストである(図3乃至5でひとつの疑似コード・リストを示す)。
図5本発明によるシステムおよび方法を用いてループ融合を達成するためのプログラムの例示的な擬似コード・リストである(図3乃至5でひとつの疑似コード・リストを示す)。
図6図2に示した段階間の関係の例示的な一実施の形態をより詳細に示す図である。
図7本発明のシステムおよび方法による意味ベースのアスペクト指向プログラミング環境をループ融合動作に適用したときの例示的な一結果を示す図である。

--

0084

110アスペクト指向ウィーバ、120プログラミング要素、122高レベル・コード・ブロック、210構文段階(第1段階)、220,240,245,260織込みコード・ブロック、230 第1の中間段階、250最後の中間段階、270 最終織込み段階、320 第1段階織込みコード・ブロック、325,337,345,377プロパゲータ間可視性パス、327,347,367プロジェクタ/プロパゲータ・パス、330,350,370 プロジェクタ、335,355,375 プロパゲータ、340 第2段階織込みコード・ブロック、360 第3段階織込みコード・ブロック、365相互運用性パス、420 第1段階コード・ブロック、430 構文段階、450 第1の中間段階、ループ構造段階、440 第1段階織込みコード・ブロック、460 第2段階織込みコード・ブロック、470計算段階、480最終段階コード・ブロック、第3段階織込みコード・ブロック、値段階コード・ブロック、490コンパイラ、495信号チャネル、500 実行可能コード・ブロック。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ