プログラムの構造合成

プログラムの構造的合成(SSP) は、命題計算に基づく(自動)プログラム合成の特殊な形式です。より正確には、直観的なロジックを使用してプログラムの構造を詳細に記述し、サブルーチンやコンピューター コマンドなどの部分からプログラムを自動的に構成できるようにします。これらの部分は正しく実装されていると想定されているため、これらの部分の正確性の検証は必要ありません。 SSP は、サービス指向アーキテクチャのサービス[1]の自動構成や大規模なシミュレーションプログラムの合成に適しています。 [2] [3]

歴史

自動プログラム合成は、問題の自動解決を目的としたソフトウェアとして人工知能の分野で始まりました。最初のプログラム シンセサイザーは1969 年にコーデル グリーンによって開発されました。 [4]ほぼ同時に、R. コンスタブルZ. マナ、およびR. ウォルディンガーを含む数学者は、自動プログラム合成に形式論理を使用できる可能性を説明しました。実用的なプログラムシンセサイザーが登場したのはかなり後になってからです。

プログラムの構造合成のアイデアは、1979 年にAndrey ErshovDonald Knuthが主催した現代数学とコンピュータ サイエンスのアルゴリズムに関する会議[5]で導入されました。このアイデアは、G. Pólyaの問題解決に関する有名な本に由来しています。 [6] SSP における問題解決の計画を立てる方法が正式な体系として提示された。システムの推論ルールは、1982 年に G. Mints と E. Tyugu [7] によって再構成され、論理的に正当化されました。SSP使用するプログラミング ツール PRIZ [8]は 1980 年代に開発されました。

SSP をサポートする最近の統合開発環境は CoCoViLa [9]です。これは、ドメイン固有の言語を実装し、大規模なJavaプログラム を開発するためのモデルベースのソフトウェア開発プラットフォームです。

SSPのロジック

プログラムの構造合成は、機能とみなせるすでに実装されているコンポーネント (コンピュータ コマンドやソフトウェア オブジェクト メソッドなど) からプログラムを構成する方法です。合成の仕様は、関数の適用可能性に関する公理を書くことによって直観主義的な命題論理で与えられます。関数fの適用可能性に関する公理は論理的含意である

X 1X 2 ∧ ... ∧ X mY 1Y 2 ... Y n

ここで、X 1X 2、... X m は関数f の適用の前提条件Y 1Y 2、... Y nは事後条件です。直観主義的論理では、関数fはこの式の実現と呼ばれます。前提条件は、入力データが存在することを示す命題にすることができます。たとえば、X i は「変数x iが値を受け取った」 という意味を持ちますが、他の条件、たとえば関数fを使用するために必要なリソースが利用可能であることも示す場合があります。前提条件は、上記の公理と同じ形式の含意である場合もあります。それはサブタスクと呼ばれます。サブタスクは、関数fが適用されるときに入力として使用可能でなければならない関数を示します。この関数自体は SSP のプロセスで合成する必要があります。この場合、公理の実現は高次関数、つまり別の関数を入力として使用する関数です。たとえば、次の式は

(状態次の状態) ∧初期状態結果

2 つの入力と 1 つの出力結果を持つ高次関数を指定できます。最初の入力は、 stateからnextStateを計算するために合成する必要がある関数で、2 番目の入力は、initialStateです。高次関数は SSP に汎用性を与えます。合成されたプログラムに必要な制御構造は事前にプログラムして使用することができ、それぞれの仕様に合わせて自動的に使用されます。特に、ここで提示される最後の公理は、複雑なプログラム、つまりシステムの 状態からnextStateを計算できるモデル上で動的システムをシミュレートするためのシミュレーション エンジンの仕様です。

参考文献

  1. ^ メグレ、リイナ;クンガス、ピープら。 (2009年)。連合政府情報システムの大規模サービス モデルでの動的なサービス統合。インテリジェント システムの進歩に関する国際ジャーナル、2(1)、181 ~ 191。
  2. ^ コトカス、ヴァフール;オジャマ、アンドレス。グリゴレンコ、パベルら。 (2011年)。多機能シミュレーションプラットフォーム「CoCoViLa」。掲載: SIMUTOOLS 2011 - シミュレーション ツールと技術に関する第 4 回国際 ICST 会議: 3 月 21 ~ 25 日 - スペイン、バルセロナ: ブリュッセル: ICST、2011 年、[1 - 8]。
  3. ^ グロシュミット、グンナール;ハーフ、メイト (2009)。 COCO-SIM - 流体力システム用のオブジェクト指向の多極モデリングおよびシミュレーション環境。パート 1: 基本。国際流体力ジャーナル、10(2)、91 - 100。
  4. ^ コーデル、グリーン (1969) 問題解決への定理証明の応用。人工知能に関する国際合同会議の議事録。 Donald E. Walker および Lewis M. Norton、編集者、Gordon and Breach Science Publishers、ニューヨーク、ニューヨーク、219–239。
  5. ^ Tyugu、EH (1981)。プログラムの構造合成。 In: 現代数学とコンピュータ サイエンスのアルゴリズム: 議事録、ウズベク ソビエト社会主義共和国ウルゲンチ、1979 年 9 月 16 ~ 22 日: Ershov、AP。 DE Knuth (編) ベルリン: Springer、1981 (コンピュータ サイエンスの講義ノート; 122)、290 - 303。
  6. ^ Pólya, G. (1957) それを解決する方法。プリンストン大学出版局。
  7. ^ ミント、G. Tyugu、E. (1982)。プログラムの構造合成の正当化。コンピュータプログラミングの科学、2(3)、215 - 240。
  8. ^ ミント、G. Tyugu、E. (1988)。プログラミングシステム PRIZ.記号計算ジャーナル、5(3)​​、359 - 375。
  9. ^ http://www.cs.ioc.ee/cocovila

外部リンク

  • 自動化されたソフトウェア エンジニアリングのホームページ
Retrieved from "https://en.wikipedia.org/w/index.php?title=Structural_synthesis_of_programs&oldid=1104542557"