(57)【要約】【課題】フォーカスした文法を用いてコンピュータプログラムの自動生成を容易にすることが可能なシステム及び方法の提供。【解決手段】フォーカスした文法の実施により、生成的プログラミング又は自動プログラミングと呼ばれる新形式の記号再帰が可能になる。可能なプログラムの空間を通しての探索は、現在のストリークを向上させる特定された候補プログラムを使用して、更なる局所化探索を方向付けるフォーカスされた文法を作成可能なストリーク探索方法によって導かれる。候補プログラムは、開始規則からフォーカスした文法をランダムに巡回し、その後完全な候補プログラム構文解析木が構築されるまで文法を通して巡回することによって生成される。次いで、例えば評価器によって候補プログラムを実行し、評価器はスタック処理言語又は他のインタプリタ型言語と併用するようになされたインタプリタを採用する。【選択図】図１
2007528538.tif 000002
【特許請求の範囲】
【請求項１】
可変パラメータを定義する文法を受け取る工程と、
該文法を使用して候補プログラムを生成する工程と、
該候補プログラムを所定の基準に従って評価する工程と、
該生成する工程と及び該評価する工程とを選択的に繰り返す工程と
を備えたことを特徴とする生成的プログラミング方法。
【請求項２】
最適な候補プログラムが該評価する工程に従って特定されるまで、該選択的に繰り返す工程を継続する工程を更に備えたことを特徴とする請求項１記載の生成的プログラミング方法。
【請求項３】
該評価する工程は、該候補プログラムを実行する工程と、得点を割り当てる工程とを備えることを特徴とする請求項１記載の生成的プログラミング方法。
【請求項４】
該実行する工程は、インタプリタを使用することを特徴とする請求項３記載の生成的プログラミング方法。
【請求項５】
選択された候補プログラムをモジュレーティングプログラムとして指定する工程を更に備えたことを特徴とする請求項３記載の生成的プログラミング方法。
【請求項６】
該指定する工程は、該割り当てる工程に従って実行されることを特徴とする請求項５記載の生成的プログラミング方法。
【請求項７】
該モジュレーティングプログラムを使用して該文法を選択的に変更する工程を更に備えたことを特徴とする請求項５記載の生成的プログラミング方法。
【請求項８】
フォーカスした文法を利用する生成的プログラミング方法であって、
可変パラメータを定義する文法を受け取る工程と、
該文法を使用して候補プログラムを生成する工程と、
所定の基準に従って該候補プログラムを評価する工程と、
該文法を変更する工程と、
該生成する工程、該評価する工程、及び該変更する工程を選択的に繰り返す工程を備えたことを特徴とする生成的プログラミング方法。
【請求項９】
該変更する工程は該評価する工程に反応することを特徴とする請求項８記載の生成的プログラミング方法。
【請求項１０】
最適な候補プログラムが該評価する工程に従って特定されるまで、該選択的に繰り返す工程を継続する工程を更に備えたことを特徴とする請求項８記載の生成的プログラミング方法。
【請求項１１】
該評価する工程は、該候補プログラムを実行する工程と得点を割り当てる工程とを備えることを特徴とする請求項８記載の生成的プログラミング方法。
【請求項１２】
該実行する工程は、インタプリタを使用することを特徴とする請求項１１記載の生成的プログラミング方法。
【請求項１３】
データ及び命令を装置に実行させるためのコンピュータ可読媒体であって、
該データ及び命令はフォーカスした文法を使用する生成的プログラミングを可能にするためのものであり、
該データ及び該命令により、該命令を実行する該装置が可変パラメータを定義する文法を受け取り、該文法を使用して候補プログラムを生成し、所定の基準に従って該候補プログラムを評価し、該評価の結果に従ってフォーカスした文法を作成することを特徴とするコンピュータ可読媒体。
【請求項１４】
別のデータ及び別の命令が格納されており、該別のデータ及び該別の命令により該別の命令を実行する該装置が、該フォーカスした文法を実施して更なる候補プログラムを生成させることを特徴とする請求項１３記載のコンピュータ可読媒体。
【請求項１５】
文法を確立するように動作する文法モジュールと、
該文法に従って候補プログラムを生成するように動作するプログラムジェネレータと、
該候補プログラムを所定の基準に従って評価するように動作する評価器と
を備えたことを特徴とする生成的プログラミングシステム。
【請求項１６】
該評価器は、シミュレートされた環境で該候補プログラムを実行し、且つ該候補プログラムに得点を割り当てるようにさらに動作することを特徴とする請求項１５記載の生成的プログラミングシステム。
【請求項１７】
該評価器は、インタプリタ型プログラミング言語に従って動作するインタプリタを備えることを特徴とする請求項１６記載の生成的プログラミングシステム。
【請求項１８】
該評価器は、評価に関連するデータを該プログラムジェネレータに提供するように更に動作することを特徴とする請求項１６記載の生成的プログラミングシステム。
【請求項１９】
該プログラムジェネレータは、該データを該文法モジュールに提供するように更に動作することを特徴とする請求項１８記載の生成的プログラミングシステム。
【請求項２０】
該文法モジュールは、該データに応答して該文法を変更するように更に動作することを特徴とする請求項１９記載の生成的プログラミングシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高度記号再帰プログラミング技法（ａｄｖａｎｃｅｄ  ｓｙｍｂｏｌｉｃ  ｒｅｇｒｅｓｓｉｏｎ  ｐｒｏｇｒａｍｍｉｎｇ  ｔｅｃｈｎｉｑｕｅ）に関し、特に、フォーカスした文法を採用してコンピュータプログラム又はコンピュータ化すなわち電子化されたソリューションの自動生成を容易にする生成的プログラミングのシステム及び方法に関する。
【０００２】
本願は、２００４年２月１４日に出願された「ＧＥＮＥＲＡＴＩＶＥ  ＰＲＯＧＲＡＭＭＩＮＧ  ＴＨＲＯＵＧＨ  ＦＯＣＵＳＥＤ  ＧＲＡＭＭＡＲＳ：  Ａ  ＮＥＷ  ＭＥＴＨＯＤ  ＯＦ  ＡＵＴＯＭＡＴＥＤ  ＰＲＯＧＲＡＭＭＩＮＧ」という名称の米国仮特許出願第６０／５４４，９５３号の利益を主張するものである。
【背景技術】
【０００３】
従来の帰納的解析技術及び記号再帰技法には種々の欠点がある。端的に言えば、従来の戦略は、反復計算プロセスを呼び出して多数の候補プログラムを生成し、これらの候補プログラムを、所与の評価方式に対して許容できるパフォーマンスレベルを示す単一のプログラム又はプログラム群を特定することによって評価する。
【０００４】
ランダム探索を採用して優良候補解を特定する従来の方法は、局所探索エリア、すなわち探索空間内の、他の優良候補解の付近にある、又はその近傍にあるエリアを扱わない傾向があるという点で不備がある。逆に、遺伝的プログラミング技法は、潜在的に局所探索に長けているが、採用されるアルゴリズムが、より広くより有望な探索方向ではなく局所極小に陥る危険性があるという点で不備がある。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
そこで本発明は、フォーカスした文法を採用してコンピュータプログラム又はコンピュータ化すなわち電子化されたソリューションの自動生成を容易にする生成的プログラミングシステム及び方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明による生成的プログラミング方法は概して、可変パラメータを定義する文法を受け取る工程、当該文法を使用して候補プログラムを生成する工程、当該候補プログラムを所定の基準に従って評価する工程、並びに、生成する工程及び評価する工程を選択的に繰り返す工程を含んでもよい。いくつかのこのような方法は、選択的に繰り返す工程を、最適な候補プログラムが、評価する工程に従って特定されるまで続ける工程をさらに含んでもよい。
【０００７】
ある実施の形態によれば、評価する工程は、候補プログラムを実行する工程、及び、得点を割り当てる工程を含み、実行する工程はインタプリタを採用する工程を含んでもよい。以下に詳述するように、生成的プログラミング方法は、選択された候補プログラムをモジュレーティングプログラムとして指定する工程をさらに含んでもよい。指定する工程は割り当てる工程に従って実行されてもよい。１つの例示的な方法は、モジュレーティングプログラムを使用して文法を選択的に変更する工程をさらに含む。
【０００８】
別の実施の形態によれば、フォーカスした文法を使用する生成的プログラミング方法は、可変パラメータを定義する文法を受け取る工程、当該文法を使用して候補プログラムを生成する工程、当該候補プログラムを所定の基準に従って評価する工程、文法を変更する工程、並びに、生成する工程、評価する工程、及び変更する工程を選択的に繰り返す工程を含んでもよい。変更する工程は、評価する工程又はいくつかの他の基準に応答してもよい。
【０００９】
このような方法は、選択的に繰り返す工程を、最適な候補プログラムが評価する工程に従って特定されるまで続ける工程をさらに含んでもよい。１つの例示的な方法によれば、評価する工程は、候補プログラムを実行する工程、及び、得点を割り当てる工程を含み、上述したように、実行する工程はインタプリタを採用する工程を含んでもよい。
【００１０】
別の実施の形態によれば、フォーカスした文法を使用する生成的プログラミングを可能にするデータ及び命令が符号化されるコンピュータ可読媒体は、装置に、可変パラメータを定義する文法を受け取る命令と、当該文法を使用して候補プログラムを生成する命令と、当該候補プログラムを所定の基準に従って評価する命令と、当該評価の結果に従ってフォーカスした文法を作成する命令とを実行させてもよい。コンピュータ可読媒体は、データ及び命令がさらに符号化され、フォーカスした文法を実施してさらなる候補プログラムを生成させる命令を装置にさらに実行させてもよい。
【００１１】
より詳細に後述するように、１つの例示的な生成的プログラミングシステムは概して、文法を確立するように動作する文法モジュールと、文法に従って候補プログラムを生成するように動作するプログラムジェネレータと、候補プログラムを所定の基準に従って評価するように動作する評価器とを備えてもよい。
【００１２】
あるシステムにおいて、評価器は、シミュレートされた環境で候補プログラムを実行し、且つ得点を候補プログラムに割り当てるようにさらに動作する。評価器は、インタプリタ型プログラミング言語に従って動作するインタプリタを備えてもよい。
【００１３】
評価器が評価に関連するデータをプログラムジェネレータに提供するようにさらに動作する例示的なシステムが開示され、このような実施の形態において、プログラムジェネレータはデータを文法モジュールに提供するようにさらに動作する。文法モジュールはデータに応答して文法を変更するようにさらに動作してもよい。
【発明を実施するための最良の形態】
【００１４】
本発明の実施の形態による生成的プログラミングシステム及び方法について図面を参照しながら説明する。本願において、「自動プログラミング」及び「生成的プログラミング」という用語は概して、候補「プログラム」又は候補「解」を生成するプロセス、及びこれらの候補解の、たとえば他の候補解に対して等の、又はたとえば客観的に所定の基準に従っての得点付け、ランク付け、分類、又は他の方法で評価を行うプロセスのいくつかの実施形態のうちの任意の実施形態を指す。特に、本明細書に記載する生成的プログラミング技法は記号再帰解析の高度に進化した形を表し、これに従って多数の候補解を、１つ又は複数の文法において指定された規則及び可変パラメータに従ってフォーカスした方向で「ランダムに」生成することができる。各候補解又は候補プログラムを測定又は評価して、たとえば、所望の、所要の、又は指定された目的関数に関してパフォーマンス特性を測ることができる。より詳細に後述するように、本明細書において採用する用語「解」は、用語「プログラム」と類似していてもよく、本開示の範囲はコンピュータ実行可能プログラミングコードに限定されず、用語「プログラム」及び用語「解」はいずれも、他の可能性を除外してコンピュータ実行可能プログラミングコードを意味するものではないことが理解されよう。
【００１５】
パフォーマンスの優良な候補プログラムは、たとえば、後で使用又は処理するために保存すること、パフォーマンスの向上を図って変更すること、後述するように１つ又は複数のフォーカスした文法を作成するために採用すること、又はこれらの或る組み合わせが可能である。逆に、パフォーマンスの優良でない候補プログラムは破棄又は無視することができ、いくつかの実施形態では、パフォーマンスのさらによくない候補プログラムを使用して、後続の探索に影響を及ぼし得る１つ又は複数のフォーカスした文法を作成することができる。したがって、本開示に従って構成され、本開示に従って動作する生成的プログラミングのシステム及び方法は、大きな母集団（ｕｎｉｖｅｒｓｅ：領域）（又は「空間」）の可能解にわたって探索することができる。十分な計算時間があれば、優良な候補プログラム（すなわち、所定の基準によって測定される、パフォーマンスが優良な候補プログラム）を生成し、特定することができる。より詳細に後述するように、先に生成された候補プログラムのパフォーマンス評価からのフィードバックを、有望な方向でのさらなる又は改良された候補プログラムの探索を導くように動作する新規フォーカスした文法の構築に役立てることができる。
【００１６】
生成的プログラミング手法は、近代コンピュータの上がり続ける速度により、少なくとも部分的に実行可能（また、場合によっては特に効率的）なことが当業者により理解されよう。今日のコンピュータは、毎秒数十億もの計算を実行することが可能であり、コンピュータの世代が新しくなる都度、前世代よりも多くのデータをより高速に処理することができるようになる（生成的プログラミング戦略を時間とともにますます可能にできることを約束する傾向）。その点において、本明細書に記載する例示的な生成的プログラミング方法は、相当なデータ処理能力又は帯域幅、すなわち多数の候補プログラムを高速且つ自動的に評価する能力により最大化又は容易にすることができる。
【００１７】
これより図面を参照すると、図１は、生成的プログラミングシステムの一実施形態の構成要素を示す簡略化した高レベルブロック図である。図１に示すように、例示的な生成的プログラミングシステム１００は概して、文法モジュール１１０、プログラムジェネレータ１２０、及び評価器１３０を備える。
【００１８】
文法モジュール１１０は概して、探索空間、すなわち生成し得る可能な候補プログラムの母集団を定義することができる。その点において、文法モジュール１１０は、より詳細に後述するように、可変パラメータを定義する規則群を含む文法を受け取る、確立する、又は変更することを特徴とすることができる。これらの可変パラメータに、たとえば、生成された候補プログラムが解くことを目的とする問題を関連付けることもでき、又は可変パラメータはその他の方法で候補プログラムの構造及び機能に影響を及ぼすこともできる。いくつかの実施形態では、文法モジュール１１０はまず、ユーザにより定義される、又はユーザ入力に従って指定される「基本文法」を採用することができる。さらに、文法モジュール１１０は、候補プログラムの改良の探索が進むにつれて、文法を動的に変更又は再構成（すなわち、フォーカス）することができ、このような変更は、プログラムジェネレータ１２０からのフィードバック（図１において破線矢印で示す）に応答することができる。その点において、文法モジュール１１０が独立して、又はプログラムジェネレータ１２０と協働して受け取った、確立した、変更した、若しくは生成された例示的な文法は、確率的、すなわち或る予め定義された、又は動的に調整される統計的確率により影響を受け得る、又は影響され得る或る程度のランダム性を特徴とすることができ、これについてはより詳細に後述する。
【００１９】
プログラムジェネレータ１２０は概して、文法モジュール１１０により供給される文法によって規定される規則及び可変パラメータを使用して、有効な候補プログラムを構築するように構成することができ、またそのように動作することができ、プログラムジェネレータ１２０はこの機能を、たとえば独立して、又は、図３を参照して後述する１つ又は複数の処理システムと併せて実行することができる。図１の構成では、プログラムジェネレータ１２０は、生成された候補プログラムを、たとえば評価器１３０に送って実行し、評価することができる。特に、評価器１３０（独立して、或いは１つ又は複数の処理システムと併せて）は概して、候補プログラムを実行し、各候補プログラムに得点又は重みを割り当てるように構成することができ、またそのように動作することができ、このような得点又は重みは、各候補プログラムそれぞれの各適応性又は適合性を表すことができる。この文脈の中での候補プログラムの適合性は、ユーザ定義、或いは手元にある問題をモデリング（すなわち、推定）すること、若しくは解くことに関する正確性、計算オーバヘッド若しくは負荷管理考慮事項、実行速度若しくは解くまでに予想されるサイクル、又はこれら及び他の要因の或る組み合わせを含むがこれらに限定されない他の所定の基準に従って測定することができる。
【００２０】
図１において破線矢印で示すように、プログラムジェネレータ１２０は、後続の、若しくはさらなる候補プログラムを生成するに際して、後続のフォーカスした文法の動的変更のために情報を文法モジュール１１０に提供するに際して、又はこれら両方に際して、評価器１３０からのフィードバックを採用することができる（たとえば、各候補プログラムの適合性又は動作実行時特性に関して）。特に、評価器１３０は、候補プログラムの評価に関連するデータをプログラムジェネレータ１２０に提供するように構成することができ、またそのように動作することができる。このようなデータの提供はたとえば、プログラムジェネレータ１２０から送られる要求に応答してのものであることができ、これに加えて、又はこれに代えて、評価に関連するデータを、所定の出来事又は指定された他の基準が満たされることに従って自発的（ｕｎｂｉｄｄｅｎ）に、すなわち自動的にプログラムジェネレータ１２０に提供することができる。
【００２１】
上記のように、また図２に示すように、候補プログラムは、たとえば所定の反復回数、又は満足のいくパフォーマンスを達成する、若しくは或る客観的なパフォーマンス特性しきい値を満たす候補プログラムが生成されるまで等、繰り返し生成し、得点付けし、又は評価することができる。その点において、図２は、生成的プログラミング方法の例示的な実施形態の全体的な動作の流れを示す簡略化したフローチャートである。
【００２２】
規則文法は、候補プログラムの生成を支配する可変パラメータを定義し、ブロック２１１において示すように受け取る、又は確立することができる。手短に上述したように、またより詳細に後述するように、文法は、少なくとも最初は、ユーザ指定であることができ、いくつかの実施形態では、文法は、各候補プログラムのそれぞれに関連する動作特性及びパフォーマンス測度に関するフィードバックに応答して、動的に調整又は変更することができる。候補プログラムは、現在の規則文法を使用して生成することができ（ブロック２１２）、所定の基準に従って評価することができる（ブロック２１３）。ブロック２１２及び２１３に示す動作の詳細について後述する。
【００２３】
判断ブロック２９０に示すように、生成された候補プログラムが満足のいくものである、又は最適なものであるかに関して判断することができる。この判断は、相対的（たとえば、候補プログラムを別の候補プログラムと直接比較する）であっても、純粋に客観的（たとえば、いくつかの所定の基準のうちの任意の基準に従って候補プログラムを測定する）であってもよい。判断ブロック２９０における判断は、ブロック２１３における評価動作に付随して、又はほぼ同時に行うことができ、評価器１３０により独立して、或いは１つ又は複数のデータ処理システム若しくはデータ処理装置と協働して達成する、又は進めることができる。いくかの実施形態では、たとえば、得点又は重みを、評価動作中に候補プログラムに割り当てることができ、ブロック２９０における判断は、このような得点又は重みを所定のしきい値又は他の或る客観的な測度と比較することを含むことができる。
【００２４】
図２によれば、候補プログラムが、判断ブロック２９０における判断に基づいて満足のいくものではない、又は最適に満たないとみなされる場合、生成的プログラミング方法の一実施形態は、ブロック２１２にループバックする実線矢印で示すように、生成すること（ブロック２１２）及び評価すること（ブロック２１３）を選択的に繰り返すことができる。これに加えて、又はこれに代えて、生成的プログラミング方法は、ブロック２１１にループバックする破線矢印で示すように、文法を変更すること（ブロック２１１）、現在の文法を使用して候補プログラムを生成すること（ブロック２１２）、及び生成された候補プログラムを評価すること（ブロック２１３）を選択的に繰り返すことができる。この例示的な実施形態では、現在の文法は、たとえば、ブロック２１３における評価動作中又はその後に提供されるフィードバックに従って選択的に変更することができる。
【００２５】
候補プログラムは、判断ブロック２９０における判断に基づいて許容できるものであるとみなされる場合、後で処理又は使用するために保存若しくはその他の方法で記録するか、後に処理又は使用するために適した装置、システム、若しくは他の装置に送信又は通信するか、或いはこれら両方の或る組み合わせが可能である（ブロック２９９）。図２に示す手法に対する代替が多くの用途で有用であり得ることが理解されよう。たとえば、許容できる、又は或る点で優れていることが（たとえば、ブロック２１３における評価又は判断ブロック２９０における判断に基づいて）分かった候補プログラムを、ブロック２１１におけるフォーカスした文法の生成に役立てるものとして特に選択することができる。このような代替の一実施態様では（明確にするために図２に示さず）、図２に示すプロセスは、所定の反復回数だけ、又は停止基準を満たすまで、ブロック２９９からブロック２１１にループバックすることができる。文法の変更に使用する優良又は優れた候補プログラムのこのような選択は、図２に示す目的に向けて候補プログラムを選択する戦略に加えて、又はこれに代えて行うことができる。
【００２６】
図３は、生成的プログラミングシステムの要素を採用することができる例示的な環境を示す簡略化した機能ブロック図である。特に、図１及び図２を参照して上述した構成要素及び動作は、デジタルコンピュータ又は他の適した電子データ処理システム（図３での参照符号３１０）に概して具現される、又はこれを含むコンピュータ環境３００と併せて採用又は動作することができる。図３の構成は例示のみを目的として提示され、処理システム３１０は、電子処理技術及びデータ処理技術の分野において概して既知のもの等の、任意の数の追加の構成要素、モジュール、又は機能ブロックを使用してインプリメントしてもよく、処理システム３１０に組み込まれる、又は処理システム３１０と併せて利用される構成要素の数及び種類は、とりわけ、システム全体の要件、ハードウェアの性能若しくは相互運用性考慮事項、所望のパフォーマンス特性、又は用途に特定の要因に従って可変であることが理解されよう。
【００２７】
例示的な図３の構成では、処理システム３１０は、汎用コンピューティング装置又は汎用コンピューティングシステム（すなわち、ワークステーション、タワーコンピュータシステム、デスクトップコンピュータシステム、ラップトップコンピュータシステム、又はハンドヘルドポータブルコンピュータシステム等のパーソナルコンピュータ（ＰＣ））で具現することができる。ブレードサーバ、ラックマウントサーバ、マルチプロセッササーバ等のコンピュータサーバは、パーソナルコンピュータと比較して、特に計算集約的な動作又は用途に関して優れたデータ処理能力を提供することができるため、処理システム３１０は、このようなサーバにおいて具現する、又はこのようなサーバを備えることができる。本明細書に記載の生成的プログラミング技法は、完全にハードウェア及びソフトウェアに「とらわれない（ａｇｎｏｓｔｉｃ）」ものと見なすことができ、すなわち、図示し説明する生成的プログラミングシステム及び生成的プログラミング方法はあらゆるハードウェア構成と互換性を持つことができ、またオペレーティングシステム及びソフトウェアプラットフォームから独立できることが理解されよう。
【００２８】
処理システム３１０は概して、プロセッサ３９０、データ記憶媒体（メモリ３８０）、入出力インタフェース３４０、通信インタフェース又はポート通信３２０、及び電源３３０を備える。図３に示すように、処理システム３１０はさらに、図１を参照して上述したような、生成的プログラミングシステム１００の構成要素（すなわち、文法モジュール１１０、プログラムジェネレータ１２０、及び評価器１３０を含む）を備えることができ、したがって、図２を参照して上述したような生成的プログラミングシステム１００の機能を可能にする、又はその機能に役立てることができる。
【００２９】
図３に各種組み合わせで示す各種構成要素は、その他の構成要素のうちの１つ又はすべてと動作可能に直接或いは間接的に、たとえばデータバス、又は他のデータ伝送経路若しくは経路の組み合わせ（図示せず）を介して結合し得ることを理解されたい。同様に、動作電力を電源３３０から各種システム構成要素に供給する電力線又は他のエネルギー伝送導路は、簡明化のために図３に示さず、これらの電力線は、当該技術分野において概して既知のように、データバスに組み込む、又はデータベースに関連付けることができる。
【００３０】
動作に際して、プロセッサ３９０は、メモリ３８０等のコンピュータ可読記憶媒体に符号化されたソフトウェア又は他のプログラミング命令を実行することができ、またさらに、プログラムジェネレータ１２０と通信して、本明細書において述べる候補プログラムの生成に役立つことができる。その点において、プロセッサ３９０は１つ又は複数のマイクロプロセッサ又はマイクロコンピュータを備える、又は組み込むことができ、また、プロセッサ３９０のコンフィギュレーション、初期化、メモリアービトレーション、及び他の動作特性に影響を及ぼすデータ及び命令セットを記憶するように動作する一体化されたデータ記憶媒体（たとえば、キャッシュメモリ）を備えることができる。
【００３１】
たとえばビデオディスプレイ及びキーボード等の任意の数又は種類の周辺機器を、本発明の働きなしで、インタフェース３４０を介して処理システム３１０に結合し得ることは概してよく理解されている。このような周辺機器の例としては、入力装置、出力装置、外付けメモリ若しくはデータ記憶媒体、プリンタ、プロッタ、ルータ、ブリッジ、カメラ若しくはビデオモニタ、センサ、アクチュエータ等が挙げられるがこれらに限定されない。たとえば、処理システム３１０の他の構成要素の動作に影響を与える、又は影響を及ぼすユーザ入力をインタフェース３４０において受け取り、プロセッサ３９０、プログラムジェネレータ１２０、評価器１３０、文法モジュール１１０、メモリ３８０、又はこれらの或る組み合わせに選択的に配布することができる。
【００３２】
処理システム３１０は、通信ポート３２０を介して双方向データ通信可能であり得る。したがって、処理システム３１０は、ローカルエリアネットワーク（ＬＡＮ）、広域ネットワーク（ＷＡＮ）、仮想プライベートネットワーク（ＶＰＮ）、インターネット等（すなわち、ネットワーク対応装置間の双方向データ通信を可能にするか、又はこれに対応する任意のシステム又はインフラ）のネットワークを介して結合される、又はアクセス可能な任意の数又は種類のサーバ、コンピュータ、ワークステーション、端末、電気通信装置、及び他の機器に常駐する、又はこれらにより送信されるデータにアクセスすることができる。
【００３３】
上記から、図２を参照して上述したような初期のユーザ定義の基本文法は、たとえば通信ポート３２０を介して受け取る、又はインタフェース３４０を介して受け入れることができることを理解されよう。
【００３４】
プログラムジェネレータ１２０、文法モジュール１１０、及び評価器１３０の動作は、プロセッサ３９０、メモリ３８０に常駐するデータ若しくは命令セット、又はこれらの組み合わせの制御下で、又はこれらと併せて実行することができる。特に、処理システム３１０は、図１及び図２を参照して上述した機能を可能にするように構成することができ、またそのように動作することができる。プログラムジェネレータ１２０、文法モジュール１１０、及び評価器１３０は、説明を簡明にするために図３には別個の要素として示されるが、それぞれの機能のうちのいくつか又はすべてを、互いに、或いは処理システム３１０の他の各種構成要素と選択的に組み合わせる、又は統合し得ることが理解されよう。
【００３５】
たとえば、プログラムジェネレータ１２０、文法モジュール１１０、及び評価器１３０（又はこれらの或る組み合わせ）は、単一の要素又は機能モジュールに統合することができ、また、たとえばメモリ３８０に常駐するソフトウェアアプリケーションにおいて具現してもよく、又は特定用途向け集積回路（ＡＳＩＣ）等のハードウェア構成要素において具現してもよい。ハードウェアソリューションに関しては、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、プログラマブルロジックコントローラ（ＰＬＣ）、プログラマブル単電子トランジスタ（ＳＥＴ）ロジック構成要素、或いは他の電子デバイス又は構成要素の組み合わせをインプリメントし、プログラムジェネレータ１２０、文法モジュール１１０、及び評価器１３０の機能のうちのいくつか又はすべてを独立して、或いは組み合わせて提供するように適宜構成し得ることを当業者は理解しよう。当該技術分野において概して既知の、又は既知の原理に従って開発され動作する、任意の選択的に構成可能若しくは適宜プログラム可能なハードウェア要素又は複数の要素の組み合わせを採用することができる。
【００３６】
例示的な一実施形態では、評価器１３０又はその機能は処理システム３１０に常駐しても、又はそうでない場合には処理システム３１０の外部にあってもよく、このような構成では、プログラムジェネレータ１２０及び評価器１３０の上述したフィードバック通信及び相互運用性は、プロセッサ３９０及び通信ポート３２０からの助けにより可能にする、又は進めることができる。この構成は、プロセッサ３９０の性能（たとえば、計算帯域幅、動作周波数等）が外部の、又はそうでない場合には専用のデータ処理システム（図３に示さず）と比較して限られている場合に特に有用であり得る。別法として、評価器１３０及びプログラムジェネレータ１２０の各機能を単一の機能ブロックに組み込んでもよく、又は図２を参照して上述したように連係してインプリメントしてもよく、この構成は、たとえば、概して処理システム３１０、特にプロセッサ３９０が、重いデータ処理負荷を処理するとともに、毎秒当たり多くの浮動小数点演算を実行することが可能な状況において特に有用であり得る。別の代替の構成では、文法モジュール１１０及びプログラムジェネレータ１２０の各機能を、ソフトウェア若しくは命令セット構造体、又はハードウェア構成要素若しくはファームウェア構成要素において具現される単一の機能ブロックに組み込んでよい。
【００３７】
処理システム３１０の環境内の生成的プログラミングシステム１００の特定の構成及び具体的な実施態様（プログラムジェネレータ１２０、評価器１３０、及び文法モジュール１１０により例示されるもの等）は、無数の変形が可能である。本開示は、生成的プログラミングシステム１００の任意の特定の構成若しくは実施態様（たとえば、ハードウェアとソフトウェア）に限定されるものではなく、又は処理システム３１０の動作性能、構造的構成、若しくは機能特性によって限定されるものではない。
【００３８】
候補プログラムの生成様式が、代替の各種生成的プログラミング方法に差異を生じさせることが理解されよう。たとえば、一実施形態では、スクラッチから候補プログラムをランダムに生成する方法を使用し得る。文法の開始規則節から、非終端規則リファレンスを巡回する生成物をランダムに選択し、有効な構文解析木が形成されるまで終端を付加することができる。この段階において、構文解析木の深さ優先巡回を行うことによってプログラム列を生成することができる。上記の手法は単純、きれい、且つ高速であるが、欠点も有する。
【００３９】
特に、純粋にランダムな探索戦略では、パフォーマンスが優良であると評価された、特定された候補プログラムが、手法のランダム性により後続の探索に利用されない場合がある。したがって、局所探索の試み（すなわち、特定された候補プログラムの近傍にあるもの）がランダム探索戦略により考慮もされず実行もされなかったため、優れたパフォーマンス特性を示していた可能性のある同様の候補プログラムが、決して考慮されず、したがって決して特定されないことがある。ランダム探索方法は概して、特定された候補プログラムがわずかな変更により益を受け得る可能性を探索しない。したがって、優れている可能性のある候補プログラムが見落とされることがあり、すなわち、このような優れた候補プログラムが存在する可能性さえも無視され得る。当業者により概して受け入れられている１つの仮定は、以下の主義に準拠することによってランダム方法を改良しようとする。すなわち、パフォーマンスの優良な候補プログラムは、パフォーマンスの優良な他の候補プログラムの周囲又は近傍（すなわち、探索空間内の大まかな近傍）に存在する傾向がある。
【００４０】
上記の仮定は、遺伝的プログラミング（ＧＰ）技法として知られているもののささやかな進歩を促した。端的に言えば、ＧＰ法は、生物学的進化の過程を模倣することによってプログラム空間を探索する。その点において、進化する候補プログラム群は遺伝物質のように扱われ、有望なプログラムがプログラムプールから選択され、部分木の交換を通して交雑育種が施され、節の置換を通してランダムな突然変異を受ける。上記の様式で生成された候補プログラムは、候補プログラムプールの中に再び入れられ、さらに選択される確率が、それぞれの適応性（１つ又は複数の所定の基準によって測定される）の関数として割り当てられる。上述したランダム手法と正に対照的に、ＧＰ技法は局所探索戦略を組み込み、先に特定された最良候補プログラム群に対して小さな変更を施すことによって優良な候補プログラムのすぐ近くのエリアを探索する。この戦略は、或る点で優れていると先に特定された候補プログラム周囲の局所エリアを完全に探索するという点で有用であり、この戦略もまた、ヒューリスティック手法が、進化中の候補プログラムの多数の「世代」の局所極小に陥る恐れがあるという点で不備がある。
【００４１】
解くべき特定の問題、制御すべき特定のシステム又は動作環境、又は他の任意のプログラミングパラメータ（すなわち、機能特性又は動作挙動を文法により適宜定義するか、又は記述することができる任意の環境、システム、又はエンティティについて）があれば、本明細書において図示し説明する生成的プログラミング技法を採用して、たとえば、行うべき特定の関数呼び出しを判断するとともに関数を呼び出す特定の順序を指示すること、フリーパラメータを適合させること、カスタムアルゴリズムを構築すること、式を曲線適合させること、又はこれらの手法の或る適切な組み合わせを採用することができる。十分な計算帯域幅があれば、１つ又は複数のコンピュータプログラム又は他の機械実行可能命令セットを、動作環境の変化に適合するように自動的にリアルタイムで書き換えることができる。限定ではなく例として、生成的プログラミング方法から益を受け得るいくつかの用途を以下にまとめる。
【００４２】
設計について
生成的プログラミングは、構造、産業、電気、又は他の設計最適化問題に関わる一部又は完全に自動の設計作業に使用することができる。このような用途では、目標は概して、最低材料コスト、最高引張強度又は最高圧縮強度、剛性考慮事項、静的、動的、若しくは振動の耐負荷性、組み立て若しくは構成の容易さ、又は上記若しくは他の要因の或る組み合わせを含むがこれらに限定されない或る客観的な工学測度に従ってパフォーマンスが最良の設計（構造設計であれ、機能設計であれ、又は両方であれ）を見つけることである。候補設計解は、たとえば、材料の種別、強度、及び硬度、構成要素又は構造要素の形状、寸法、重量、相対位置、及び相互接続、材料又は構成要素の電気的若しくは電磁的な特性、個々に考えられるか、それとも組み合わせて考えられるかに関わりなく、個々の又は相互接続された要素の機能特性、システムへの予想動作エンベロープ及び予想ストレス、或いはこれら又は他の要因の或る組み合わせを定義し相互に関係づける文法から生成することができる。設計用途のいくつかの例としては、とりわけ、工学部品又はシステム構成要素、建造物又は他の構造設計、半導体のレイアウト、設計、又は製造戦略、制御システムインプリメンテーション、及び属性レイアウトを挙げることができる。
【００４３】
予測について
時系列予測用途は概して、可能な限り低い誤差率で一連の将来の値を予測しようとする。本明細書に記載する生成的プログラミング技法によれば、時系列関数の特性、たとえば、移動平均等を定義又は記述する文法から、候補式を生成することができる。本システム及び本方法によって生成された各候補式を、所与の過去又は履歴のデータセットに対して、ターゲットとした一連の値をどの程度良好に予測するかに関してテストすることができる。このような予測のいくつかの例としては、とりわけ、販売予測、利率予測、市場予測、経済の見通し、及び不動産評価予測を挙げることができる。
【００４４】
モデリングについて
多くの場合、物理的なシステムの挙動を支配する数式は、計算コストが高（ｃｏｍｐｕｔａｔｉｏｎａｌｌｙ  ｅｘｐｅｎｓｉｖｅ）すぎて計算することができない、又は他の場合には直接解くことができない。その代わりに、近似モデルが妥当な時間量でシミュレーションを行おうとする。生成的プログラミングを採用して、ターゲットとする環境の近似モデルを構築することができる。このような用途では、システムの動き又は他の動的な局面を記述又は統制する文法規則から、候補モデルを生成することができる。候補モデルは、既知の例群に従って、根底にあるシステムをどの程度正確にモデリング又は近似するかに関して得点付けることができる。いくつかのモデリング例としては、タンパク質フォールディングダイナミクス、アミノ酸相互作用、化学反応、波動及び他の２次元又は３次元ダイナミック流体フロー、伝熱問題、及びナノスケールメカニクスを挙げることができるがこれらに限定されない。
【００４５】
最適化について
資源割り振りのジレンマは概して、目的関数に従って可能な資源費用の間でのトレードオフが最良又は最適な解を探す。この文脈の中では、生成的プログラミング方法を採用して、個々の、明確に定義されていない、任意の目的を持った最適化問題を解く、又は最適化問題の多くの事例を解くアルゴリズムを構築することができる。その点において、候補解は、無数の資源利用法の波及効果を定義又は指定する文法から生成することができる。最高又は最低の得点を有する（目的関数の方向に応じて）候補解を保持して、後続の処理、後続の使用、又は後続の探索に影響を及ぼし得る１つ又は複数のフォーカスした文法を生成することができる。例示的な最適化用途としては、資産配分及び産業又は他の自動制御システム問題が挙げられる。
【００４６】
テストについて
テストは概して、アサーションを有効化（又は無効化）する試みを特徴とする。アサーションが、製造業者が要求したように実行する製品であるというアサーションであるか、それとも製品を壊すことができないことのアサーションであるかに関わらず、生成的プログラミングシステム及び方法は、このようなアサーションのテストに役立つことができる。その点において、テスト環境、及びテスト中の品物又はシステムの期待される又は要求される挙動を特徴付ける選択された各種パラメータを定義する文法規則から候補テストを生成することができる。生成的プログラミング技法が利用され得るいくつかのテスト例としては、ソフトウェアテスト、ハードウェアテスト、設計バッシング又は「神話崩壊（ｍｙｔｈ  ｂｕｓｔｉｎｇ）」、及びモデルテストが挙げられる。
【００４７】
上記から、本明細書において述べるフォーカスした文法を採用した生成的プログラミングの新規のシステム及び方法は、無数の用途で有用である可能性があり、種々の用途に固有の変更を行いやすいことが理解されよう。例示的な一実施形態によれば、候補プログラムは、確率文法を巡回することによってランダムに生成することができる。特に図２を参照して上述したように、文法は静的でなくてもよく、すなわち、適した又は最適な解を特定する過程全体を通して、文法は、「改良」又は「モジュレーティング」プログラムのパフォーマンスに従って提供されるフィードバックによってモジュレートすることができる。この変更又はモジュレーティングは、探索空間の有望なエリアの方向での後続の候補プログラムに向かうように、現在の文法又は複数の文法の組み合わせをフォーカスし直すことができる。
【００４８】
したがって、フォーカスした文法の利用により、探索空間内の局所探索戦略を組み込んで、又はそれに役立てて、モジュレーティングプログラムと同様の候補プログラムの生成を可能にすることができる。探索中、候補プログラムを生成し、且つ評価することができ、その後、より優良又はより適した候補プログラムが特定されると、文法を再帰的にフォーカスし直すことができる。多くのこのような探索は、たとえば、或るユーザ定義の停止基準（最大反復回数等）が満たされるまで、又は満足のいく候補プログラム若しくは最適な候補プログラムが或る所定の客観的な目標に従って特定されるまで行うことができる。
【００４９】
これより、特に文法に目を向けると、図４及び図５は、記述文法の一実施形態及び候補プログラムの生成に文法を採用する方法の一実施形態の全体的な動作のそれぞれを示す簡略図であることが留意される。図４の文法（及びそれ以降の続く図面に示すもの）はバッカス−ナウア記法（ＢＮＦ）で提示されていることが理解されよう。背景として、ＢＮＦとは、当該技術分野において概して既知のように、コンピュータプログラミング言語の文法、コマンド、又は命令セット、及び通信プロトコルを記すために一般に採用されるメタシンタックスである。ＢＮＦ規則は、明確にするため、また本発明のシステム及び方法の諸態様を容易に理解可能なように伝えるために、単なる例として本明細書において採用される。文法の他の各種形式、構造、シンタックス、及び表現様式が、現在採用可能であり、又は将来に開発される可能性があり、本開示はいずれの特定の文法シンタックスにも限定されず、又は文法を表現することができる特定の形式に限定されない。
【００５０】
本明細書において採用する用語「文法」は概して、ＢＮＦ或いは他の或る適したメタシンタックス又は形式化された表現のいずれかで提供又は指定される規則セット及び関連する生成物を指す。その点において、文法は、所与の言語の「文章」の生成又は認識を指定し、候補プログラムの生成を支配する多くの可変パラメータを定義することができる。用語「基本文法」は概して、図２及び図３を参照して上述したようにユーザ定義の文法又は予め定義された或る文法、ユーザ指定の文法、若しくは初期文法を指す。これに加えて、又はこれに代えて、基本文法という用語は、後続する、又は追加のフォーカスした文法又は基本文法を形成する過程において「モジュレーティングプログラム」と組み合わせられる「フォーカスした文法」を指し得る。
【００５１】
この文脈の中での用語「フォーカスした文法」は概して、基本文法とモジュレーティングプログラムを結合することによって生成される文法を指し、フォーカスした文法は、或る点では、フォーカスした文法の構築に使用されたモジュレーティングプログラムと同様に候補プログラムを生成するように構築することができ、またそのように動作することができる。より詳細に後述するように、フォーカスした文法は、モジュレーティングプログラムを分解することにより特定することができるように、１つ又は複数の追加の生成物（基本文法と比較して）を含むように構築することができ、これに加えて、又はこれに代えて、フォーカスした文法は、単に、基本文法内に存在する生成物に関連する確率を操作することにより、すなわち追加の生成物をフォーカスした文法に追加することなく生成することができる。フォーカスした文法は、上述したように基本文法として採用し得る。所与の候補プログラムと所与のモジュレーティングプログラムとの「類似性」を、後述する各種基準に従って測定できることが理解されよう。
【００５２】
本明細書において意図し、プログラム又は解を記述又は特徴付けるために使用する用語「同様に」は概して、性質又は特性の点で近い、関連する、若しくは類似する状態を指し、この文脈の中での「類似性」は、各候補プログラム、モジュレーティングプログラム、又は解の容易に突き止めることができる或る特性に従って測定又は定量化することができる。たとえば、列編集距離を使用して、各候補プログラムの各列を比較し、たとえば互いに対するそれぞれの類似性を測定し、又はそれぞれの各類似性をモジュレーティングプログラムと比較することができる。互いに同様であるとみなされるプログラム又は解は概して、たとえば列編集距離評価によって定量化されるように、統計的に同様であると特徴付けることができる。上述したように、類似性を求める他のメカニズムが当該技術分野において概して既知であり、用途に固有であり得る。
【００５３】
本明細書において採用する用語「文章」は概して、文法によって規定又は指定される規則及び生成物に従って生成される文字列リテラルインスタンス（ｓｔｒｉｎｇ  ｌｉｔｅｒａｌ  ｉｎｓｔａｎｃｅ）を指し、本開示の文脈の中では、文章は、文法によって指定される規則及び生成物に従って生成される候補プログラム又は候補解に類似する。
【００５４】
本明細書において採用する用語「プログラム」は、限定の意味で解釈されるものではないことが理解されよう。特に、本開示の文脈の中では、プログラムは概して、たとえば、アプリケーションプログラム、インタフェース、アプレット、又は他の機械可読命令セットを通常具現するもの等の実行可能プログラムコードを特徴とする（又は、それを指す）ことができる。これに加えて、又はこれに代えて、プログラムという用語は、文字の有限シーケンス（たとえば、文法によって指定される規則及び生成物に従って生成される文字列リテラルインスタンス）によって表す、又は表現することができるもの等、他の種類の解も意図し、包含する。したがって、プログラムは、たとえば、エグゼキュータブル（ｅｘｅｃｕｔａｂｌｅ）又は他の命令セット、数学的な各種の表現、式、関数、又は式系、機能的、物理的、又は有機化学的な関係の化学的な記述、式、又は表現、数学的又は構造的なモデル表現、物理的なレイアウト（たとえば、半導体ウェハ及び他のシリコン又はハードウェア設計を記述する、Ｖｅｒｉｌｏｇ又は他のハードウェア記述言語（ＨＤＬ）コードで表すことができるもの等）、或いは本明細書に述べるように文法を巡回することによって生成される文字の有限列として表すことができる他の任意の用途に固有の解において具現し得るが、これに限定されない。概して上述したように、本開示の文脈の中では、用語「解」は、プログラムという用語と同様であることができ、その点において、この用語は概して、プログラムという用語を参照して上述したものと同じ範囲を共有する。
【００５５】
用語「モジュレーティングプログラム」は概して、基本文法の確率を再整形又はフォーカスするために使用され、その結果として、基本文法の確率を使用した場合よりも、モジュレーティングプログラムにより類似するさらなる候補プログラムの生成に向けてフォーカスされた確率を有するフォーカスした文法を生成する候補プログラム又は候補解を指す。ここでも、プログラムの相対的な類似性は、たとえば、列編集距離に従って求めてもよく、又は他の或る適した測度に従って特徴付けてもよい。
【００５６】
初期文法すなわち基本文法（たとえば、図４参照）を使用して、生成的プログラミングのシステム及び方法は、基本文法をランダムに巡回することによって候補プログラムを生成し、このプロセスにより、有効で完全な文章又は候補プログラム（たとえば、図５参照）を生成することができる。その点において、乱数（たとえば、図５の左から３列目に示す０．００〜１．００の実数）を生成することができ、この乱数は、許容し得る各生成物の各確率に従って特定の規則に選択される生成物に影響する。たとえば、図５に示すステップ３において、乱数０．６７の生成は、＜ａｓｓｅｒｔｉｏｎ＞規則に生成物２が選択されることに繋がり得る（すなわち、図４での＜ａｓｓｅｒｔｉｏｎ＞＝＜ｄｅｓｃｒｉｐｔｉｏｎ＞＜ｃｏｎｊｕｎｃｔｉｏｎ＞）。これは、乱数値０．６７が０．５０よりも大きいためである。同様に、図５に示すステップ６において、乱数０．７１の生成は、＜ｄｅｓｃｒｉｐｔｉｏｎ＞規則に生成物３が選択されることに繋がり得る（すなわち、図４での＜ｄｅｓｃｒｉｐｔｉｏｎ＞＝“ｆｕｎ”）。これは、乱数値０．７１が０．５０と０．７５の間にあるためである。
【００５７】
図５の「距離」列中の値は概して、図４に示す各生成物のそれぞれに記される生成物確率に関連することができ、ここで距離＝１／（基本文法内の生成物確率）である。たとえば、ステップ２において参照される＜ｃｉｔｙ＞規則に関して、生成物“Ｓａｎ  Ｄｉｅｇｏ”は、図４に示すように確率０．３３を有するため、距離は（図５のステップ２に示すように）１／０．３３＝３である。距離を採用して、より詳細に後述するモジュレーティングプログラムの構造及び性質に従って生成される後続の文法をフォーカスすることができる。
【００５８】
上述のようにして、候補プログラムを、図５に示すようにステップ毎に文法を巡回することにより、図４に記すもの等の規則群、生成物群、及び関連する確率群に従って生成することができる。図４に記す規則及び生成物は、単に例示を目的として提示され、図５を参照しての説明を容易にするために大幅に簡略化されていることが理解されよう。多くの用途で、複雑な文法に関連するこのような規則及び生成物は、関数呼び出し、変数の定義又は初期化、テーブルのルックアップ及び更新等を伴い得る。
【００５９】
上述したように、候補プログラムはユーザ提供の基準又は他の或る客観的な測度を対照して得点付けることができる。生成的プログラミングのシステム及び方法のいくつかの実施形態によれば、選択された候補プログラム（特によい得点のもの、又はパフォーマンスが特によいもの等）がモジュレーティングプログラムになることができ、これから、図１〜図３を参照して上述したようにフォーカスした文法を生成することができ、これに加えて、又はこれに代えて、いくつかの候補プログラムを、パフォーマンス評価に関わることなくモジュレーティングプログラムとして選択し得る。特に、基本文法及びモジュレーティングプログラムは、たとえば、文法モジュール１１０、プログラムジェネレータ１２０、又はこれら両方の組み合わせにより組み立てることができ、組み合わせでは、基本文法及びモジュレーティングプログラムは、モジュレーティングプログラムの近傍、すなわち、比較的近くでの（たとえば、列編集距離評価によって判断することができるような）、又は探索空間内のモジュレーティングプログラムの近接での後続の候補プログラムの生成に役立つフォーカスした文法を形成することができる。
【００６０】
いくつかの実施形態によれば、あり得る候補プログラム又は解の空間を通しての探索は、より詳細に後述する「ストリーク探索方法（ｓｔｒｅａｋ  ｓｅａｒｃｈ  ｍｅｔｈｏｄ）」によって導く、又は概して方向付けることができる。端的に言えば、ストリーク探索方法を採用して、基本文法からいくつかの候補解を生成することができ（基本文法はフォーカスした文法であってもよい）、候補解又は候補プログラムを評価し、その後、モジュレーティングプログラムの得点を高める得点又は他の客観的な測度を有する候補解又は候補プログラムを、再帰的探索のモジュレーティングプログラムとして使用することができる。上述したように、プログラムという用語は、実行可能プログラミングコード以外の解を包含し、本明細書において述べるストリーク探索方法を採用し、再帰的探索技法を用いて各種の候補解を特定することができる。
【００６１】
モジュレーティングプログラムを採用して基本文法をフォーカスし直す上記のプロセスは独自のものであることが理解されよう。いくつかの用途では、１つの目標は、モジュレーティングプログラムと同様の候補プログラムを生成する新しいフォーカスした文法を構築することであり得る。この方法は、可能な候補プログラムの空間内で、比較的優良な結果をもたらすことが分かっている基本文法によって生成される候補プログラムに近接して局所探索を行うメカニズムを提供する。
【００６２】
例示的な一実施形態では、フォーカスした文法を構築することは、基本文法を新しいフォーカスした文法にコピーすること、モジュレーティングプログラムの分解に基づいて自動定義生成物（ＡＤＰ）を追加すること、及び影響を受けた生成物の確率をリスケーリングすることを含み得る。その点において、ＡＤＰは、自動定義変数（ＡＤＶ）若しくは自動定義関数（ＡＤＦ）から生成する、又はＡＤＶ若しくはＡＤＦを特徴とすることができ、モジュレーティングプログラムの分解中及び以下に概ね述べるモジュレーティングプログラムの構文解析木の詳細な解析中に特定することができる。
【００６３】
一般に、フォーカスした文法を採用して、基本文法の確率特性を、たとえば列編集距離測度に従って、又は他の或る基準を使用して決定される、モジュレーティングプログラムと統計的に同様のプログラムの生成に向けて再整形することができる。このような再整形又はリフォーカスは単純な、基本文法の確率の原位置での変更を通して（すなわち、基本文法に存在する規則にいかなる新しい生成物も追加することなく）実現可能であり得るが、このような手法に起こり得る１つの副作用により、モジュレーティングプログラムと比較して長いプログラムが生成されるという膨張の危険性、ひいては列編集距離の増大に繋がる恐れがある。新しい生成物（ＡＤＰ）を基本文法に追加することで（フォーカスした文法作成プロセス中に）、プログラムサイズの増大という問題を軽減、最小化、又はなくすことができる。
【００６４】
その点において、ＡＤＶをフォーカスした文法に追加することで、フォーカスした文法を巡回することによって生成される候補プログラム内での再利用のために潜在的に有用な部分木を共通化することができる。たとえば、モジュレーティングプログラムの生成中に直面する各規則参照毎に、参照中の規則に新しい生成物を追加することができる（その後構築されるフォーカスした文法において）。新しい生成物の右側は、モジュレーティングプログラムの構文解析木の、その規則から開始する深さ優先巡回からの結果である単一の終端トークン又は文字列リテラルであってもよい。
【００６５】
ＡＤＶをフォーカスした文法に追加することの利点と同様に、ＡＤＦをフォーカスした文法に追加することで、フォーカスした文法を巡回することによって生成される候補プログラム内での再利用のために潜在的に有用な木構造を共通化することができる。たとえば、モジュレーティングプログラムの生成中に直面する各規則参照毎に、その規則の選択された生成物内の規則参照の各拡張により作成される組み合わせ順列群毎に、順列を新しい生成物として規則に追加することができる。これは、選択された各生成物のすべての関数形式を展開する。上記の戦略は、指数的な数の新しい生成物をフォーカスした文法に追加することができるが、上記又は他の順列の部分集合を挿入することが、結果生成されるフォーカスした文法を単純化するために実用的な代替であり得る。たとえば、このような１つの単純化は、単一レベルの参照拡張により作成される順列のみを追加することを含み、別の手法は、終端生成物よりも１レベル上の最も深い拡張のみを追加することを含み得る。
【００６６】
ＡＤＶ及びＡＤＦを基本文法に追加する（結果としてフォーカスした文法になる）上述したプロセスの例示的な結果を図６に示す。特に、図６は、等確率フォーカスした文法の一実施形態を示す簡略図である。
【００６７】
図６に示すフォーカスした文法は、モジュレーティングプログラムの構造及び合成（ｃｏｍｐｏｓｉｔｉｏｎ）に従って選択されたＡＤＶ及びＡＤＦで変更された基本文法（図４に示す）の変更（この例では、図５に示す候補プログラム“Ｓａｎ  Ｄｉｅｇｏ  ｉｓ  ｈｏｔ，  ｆｕｎ  ａｎｄ  ｂｅａｕｔｉｆｕｌ”）を表す。特に、モジュレーティングプログラムの分解を採用して、フォーカスした文法に挿入する関数及び変数を特定することができる。その点において、図６のＡＤＶ列及びＡＤＦ列中の数は、各ＡＤＶ及びＡＤＦのそれぞれを生み出す規則が参照されたモジュレーティングプログラムの生成中のステップ（図５参照）をそれぞれ表す。図６において「ＡＤＶ」及び「ＡＤＦ」と示される列（すなわち、左からそれぞれ２列目及び３列目）は、単に例証を目的として提供されるに過ぎないことが理解されよう。列自体も、またそこに表されているデータも、フォーカスした文法の構築又はインプリメンテーションに必要ない。
【００６８】
例として、図６の＜ａｓｓｅｒｔｉｏｎ＞規則は、モジュレーティングプログラムの生成中にステップ３〜８において最終的に生成された＜ａｓｓｅｒｔｉｏｎ＞（図５のステップ３において参照される）に対応するＡＤＶ生成物（“ｈｏｔ，  ｆｕｎ  ａｎｄ  ｂｅａｕｔｉｆｕｌ”）を含むように変更されている（すなわち、＜ａｓｓｅｒｔｉｏｎ＞＝“ｈｏｔ，  ｆｕｎ  ａｎｄ  ｂｅａｕｔｉｆｕｌ”）。特に、生成される乱数及び図５の候補プログラムを生成する際に選択される生成物に基づいて、＜ａｓｓｅｒｔｉｏｎ＞規則は最初に＜ｄｅｓｃｒｉｐｔｉｏｎ＞＜ｃｏｎｊｕｎｃｔｉｏｎ＞（ステップ３）を生成し、１番目の＜ｄｅｓｃｒｉｐｔｉｏｎ＞は“ｈｏｔ”を生成し（ステップ４）、＜ｃｏｎｊｕｎｃｔｉｏｎ＞規則の１番目のインスタンスは＜ｄｅｓｃｒｉｐｔｉｏｎ＞＜ｃｏｎｊｕｎｃｔｉｏｎ＞を生成し（ステップ５）、２番目の＜ｄｅｓｃｒｉｐｔｉｏｎ＞は“ｆｕｎ”を生成し（ステップ６）、＜ｃｏｎｊｕｎｃｔｉｏｎ＞規則の２番目のインスタンスは“ａｎｄ”＜ｄｅｓｃｒｉｐｔｉｏｎ＞を生成し（ステップ７）、最後に、３番目の＜ｄｅｓｃｒｉｐｔｉｏｎ＞は“ｂｅａｕｔｉｆｕｌ”を生成した（ステップ８）。
【００６９】
さらに、図６の＜ａｓｓｅｒｔｉｏｎ＞規則は、モジュレーティングプログラムの生成中のステップ３及び５に示す動作に対応するＡＤＦ生成物（＜ｄｅｓｃｒｉｐｔｉｏｎ＞“”＜ｄｅｓｃｒｉｐｔｉｏｎ＞＜ｃｏｎｊｕｎｃｔｉｏｎ＞）を含むようにも変更されている。特に、＜ａｓｓｅｒｔｉｏｎ＞規則（図５のステップ３において参照される）は最初に、＜ｄｅｓｃｒｉｐｔｉｏｎ＞＜ｃｏｎｊｕｎｃｔｉｏｎ＞を生成し（ステップ３）、ここで、＜ｃｏｎｊｕｎｃｔｉｏｎ＞規則の１番目のインスタンスは“”＜ｄｅｓｃｒｉｐｔｉｏｎ＞＜ｃｏｎｊｕｎｃｔｉｏｎ＞を生成した（ステップ５）。同様に、図６の＜ｃｉｔｙ  ｄｅｓｃｒｉｐｔｉｏｎ＞規則も、ステップ１において参照される規則に対応するＡＤＦ生成物を含むように変更されている。モジュレーティングプログラムの生成中、＜ａｓｓｅｒｔｉｏｎ＞規則は最終的に、図５のステップ３に示すように＜ｄｅｓｃｒｉｐｔｉｏｎ＞＜ｃｏｎｊｕｎｃｔｉｏｎ＞を生成し、図６の＜ｃｉｔｙ  ｄｅｓｃｒｉｐｔｉｏｎ＞規則はこの新しい生成物を反映するように変更されている。図６に示すように、＜ｃｏｎｊｕｎｃｔｉｏｎ＞、＜ｃｉｔｙ＞、及び＜ｄｅｓｃｒｉｐｔｉｏｎ＞規則は、たとえば、モジュレーティングプログラムの分解に従って、又はユーザ指定の基準に従って同様に変更することができる。
【００７０】
上述したように、フォーカスした文法を生成又は作成する方法は、影響を受ける生成物の確率をリスケーリング又はリファクタリングすることを含み得る。最も単純なリファクタリング方式は概して、図６に示すように、生成されるフォーカスした文法内の特定の規則のすべての生成物確率を等確率に設定することを含む。ＡＤＶ、ＡＤＦ、又はこれら両方を受け取るあらゆる規則について、１をその規則の生成物の新たな総数で割ると、各生成物の確率を等しくすることができる。しかし、このような手法の潜在的な一欠点は、大きな部分木の列の再利用に比較的高い確率が関連付けられることがあることであり、結果として列編集距離が大きくなり、これはモジュレーティングプログラムとの類似性が低いことを表す。
【００７１】
よりバランスのとれた手法の一例は、概して、等確率ではない一対のフォーカスした文法のうちの一方又は両方を利用することを含み得る。その点において、図７は、再利用に向けて整形されたフォーカスした文法の一実施形態を示す簡略図であり、図８は、たとえば、モジュレーティングプログラムに対して類似した終端に向けて整形されたフォーカスした文法の一実施形態を示す簡略図である。ＡＤＰを、図６を参照して実質的に上述したように図７及び図８のフォーカスした文法に追加することができる。図６でのように、図７及び図８のＡＤＶ列及びＡＤＦ列中の数は、ＡＤＶ又はＡＤＦのそれぞれを生み出す規則が参照されたモジュレーティングプログラムの生成中のステップをそれぞれ表し、これらの列は単に例示を目的として提供されるに過ぎず、フォーカスした文法の作成に対しても、またその動作に対しても関係がない。
【００７２】
以下の説明では、図７のフォーカスした文法及び図８のフォーカスした文法の両方を協働して利用する一実施形態を扱うが、図６〜図８に示したフォーカスした文法の実施形態のいずれも、モジュレーティングプログラムと同様の候補プログラムを作成する間に個々に採用し得ることが理解されよう。特に、図６〜図８に示すフォーカスした文法は、生成物確率を計算することができるいくつかの例示的な代替の方法を表す。たとえば、単独で考える場合であっても、図６〜図８に示すフォーカスした文法の実施形態のいずれか１つを実質的にインプリメントして、候補プログラムを生成することができる。
【００７３】
マルチフェーズ又はマルチステージの実施形態によれば、「第１フェーズ」文法（たとえば、図７に示すような）を、多数の候補プログラムを生成するようにフォーカスされた生成物確率を含むように構築することができる。逆に、「第２フェーズ」文法（たとえば、図８に示すような）は、特に、第１フェーズ文法よりも高速に（たとえば、列編集総距離又は他の或る客観的な測度に関して）新しい候補プログラムの生成を終了するようにフォーカスされた生成物確率を含むように構築することができる。この戦略によれば、候補プログラムの生成は２フェーズプロセスを特徴とすることができるが、フェーズの追加も同様に可能であり得る。第１フェーズのフォーカスした文法を採用して、ＡＤＰを訪れるまで新しい候補プログラムを生成することができ、ＡＤＰを訪れた時点で、第２フェーズのフォーカスした文法を採用して、必要であれば候補プログラムを完成させることができる。
【００７４】
「距離」列中の値（図７及び図８に示すような）は、いくつかの異なる方法で計算することができ、いくつかの実施形態では、特定の生成物の距離を計算する様式は、たとえば、考慮中の生成物の種別又は他の要因に依存し得る。フォーカスした文法は、上述したように、モジュレーティングプログラムの分解を通して特定されたさらなる生成物を基本文法に添付又は挿入することによって生成することができ、したがって、基本文法に存在する生成物のいくつか又はすべては、変更することなくフォーカスした文法にコピーすることができる。たとえば、図７及び図８では、＜ａｓｓｅｒｔｉｏｎ＞規則の最初の２つの生成物、＜ｃｏｎｊｕｎｃｔｉｏｎ＞規則の最初の２つの生成物、及び＜ｄｅｓｃｒｉｐｔｉｏｎ＞規則の最初の４つの生成物（以下同様）は、基本文法（図４）に存在する生成物を特徴とすることができる。
【００７５】
距離が、基本文法内の所与の生成物確率の逆数として定義される場合、いくつかの第１フェーズのＡＤＰの確率は、モジュレーティングプログラムの総距離から部分木の総距離を差し引くことによって計算することができ、逆に、いくつかの第２フェーズのＡＤＰの確率は、単に各部分木の総距離を合計するだけで計算することができる。こういった戦略について、限定ではなく例としてより詳細に後述する。
【００７６】
他の可能性も考えられるが、基本文法に存在する生成物の距離は、基本文法と同じ様式でフォーカスした文法において定義することができ、ここで距離は概して、上述したように、基本文法での所与の生成物の確率の逆数として表すことができ、すなわち、距離＝１／（基本文法での生成物確率）である。たとえば、図４の基本文法での＜ｄｅｓｃｒｉｐｔｉｏｎ＞規則の“ｈｏｔ”生成物は生成物確率０．２５を有し、その結果、図７及び図８において（その生成物の）距離は４になる。同様に、図４の基本文法での＜ｃｉｔｙ＞規則の“Ｌｏｓ  Ａｎｇｅｌｅｓ”生成物は生成物確率０．３３を有し、その結果、図７及び図８において（その生成物の）距離は３になる。
【００７７】
いくつかの実施形態では、ＡＤＦに、それを生成する元になった生成物と同じ距離を割り当てることができる。元の距離、すなわち１／（基本文法での生成物確率）を、再利用（図７）及び終端（図８）のフォーカスした文法の両方に採用することができ、これは部分的に、この種のＡＤＰは実質的に、基本文法と同様の列編集距離にむしろ自然になり得るためである。図４を参照して図７及び図８を調べることで、各ＡＤＦに、対応する規則の元となった生成物と同じ距離を割り当てられることが示される。特に、図７及び図８の＜ａｓｓｅｒｔｉｏｎ＞規則に挿入されたＡＤＦには、図４での＜ａｓｓｅｒｔｉｏｎ＞規則の生成物と同じ距離（２＝１／０．５）が割り当てられており、これらはそれぞれ、基本文法において生成物確率０．５を有する。
【００７８】
これに加えて、又はこれに代えて、距離は、フォーカスした文法の所望又は所要の性質に応じて、より複雑な戦略に従ってＡＤＶに割り当てることができる。図７に示すように再利用文法の場合、ＡＤＶの距離は、モジュレーティングプログラムの総距離からＡＤＶの部分木距離を差し引くことによって計算することができる。たとえば、再利用文法ＡＤＶ−５（すなわち、図７での“，  ｆｕｎ  ａｎｄ  ｂｅａｕｔｉｆｕｌ”）の距離は以下のように計算することができる。
［プログラム距離］−［部分木距離］＝
［図５のステップ１からの部分木］−［図５のステップ５からの部分木］＝
［２２］−［２＋４＋２＋４］＝１０
【００７９】
逆に、図８に示すような終端文法では、ＡＤＶの距離は単に、部分木の総距離として示すことができる。たとえば、終端文法ＡＤＶ−５（すなわち、図８での“，  ｆｕｎ  ａｎｄ  ｂｅａｕｔｉｆｕｌ”）の距離は以下のように計算することができる。
［部分木距離］＝［図５のステップ５からの部分木］＝［２＋４＋２＋４］＝１２
【００８０】
「１／距離」列は、図７及び図８において自明である。この列の値は単に、考慮中の生成物の距離値の逆数をとることによって計算することができる。たとえば、距離１２は１／１２＝０．０８３３になる。
【００８１】
図７及び図８に概して示すように、「生成物確率」列中の値は、各規則で再び１に向けてリスケーリングされている「１／距離」列中の値から導き出される。特に、所与の規則のすべての生成物確率の和を１に等しくすることができる。したがって、特定の規則の「１／距離」列中のすべての値を合算することができ、各生成物の「１／距離」値をその和で除算して、各生成物のリスケーリングされた「生成物確率」値を計算することができる。たとえば、図８の終端文法の＜ａｓｓｅｒｔｉｏｎ＞規則をリスケーリングすると、「１／距離」値の和は以下のようになる。０．５００＋０．５００＋０．５００＋０．０６３＝１．５６３。最初の３つの生成物（それぞれ「１／距離」値０．５００を有する）には生成物確率０．５００／１．５６３＝０．３２０が割り当てられることになる。ステップ３中に追加されるＡＤＶには、新しい生成物確率０．０６３／１．５６３＝０．０４０を割り当てることができる。
【００８２】
上述したように、フォーカスした文法は概して、局所探索戦略で採用され、モジュレーティングプログラムの方向にフォーカスされた確率文法を特徴とすることができる。モジュレーティングプログラムの構文解析木（通常、探索中に特定された改良を表す）を、基本文法の２つのコピーに挿入して、上述したように異なる生成物確率を有する新しいフォーカスした文法対を形成することができる。上述した実施形態に対する例示的な１つの代替形態では、一対のフォーカスした文法を組み合わせて使用して、モジュレーティングプログラムの近傍にプログラムを以下のように生成することができる。
【００８３】
確率基本文法を２つの文法、すなわち第１フェーズ及び第２フェーズにコピーする。
【００８４】
モジュレーティングプログラム内の規則参照毎に、選択された規則からのモジュレーティングプログラムの構文解析木の深さ優先巡回から生じる列を、両方のフォーカスした文法の対応規則に挿入された新しい生成物内の終端列として追加する。これは、自動定義変数（ＡＤＶ）の明確な実現性を付加する。
【００８５】
モジュレーティングプログラム内の規則参照毎に、新しい生成物を両方のフォーカスした文法の対応規則に追加する。新しい生成物の右側要素は、深さ優先巡回中に訪れたモジュレーティングプログラムの構文解析木からのものであり、列自体ではなく終端列を訪れている場合には規則参照を用いる。これは、自動定義関数（ＡＤＦ）の明確な実現性を付加する。
【００８６】
非終端の開始点からのモジュレーティングプログラムの総距離を計算する。
【００８７】
上記の動作中に追加された各生成物に、新しい確率を実質的に上述したように距離に従って割り当てる。
【００８８】
各規則に、たとえば上述したような生成物確率をリスケーリングする。
【００８９】
この実施形態によれば、また図７及び図８に示すように、第１フェーズの文法と第２フェーズの文法との差を新しい生成物確率で明らかにすることができる。第１フェーズの文法を使用して新しい候補プログラムを生成する場合、モジュレーティングプログラム全体に類似した生成物ほど高い確率を有する。このことは、たとえば新たに追加された生成物の１つを巡回するまで望ましいであろう。仮に第１フェーズの文法の巡回がこの点から続けられたとすると、第１フェーズのフォーカスした文法は、モジュレーティングプログラムのかなり大きい部分を、端と端とを繋げて添付するという強い傾向を示し得る。その結果生成される候補プログラムは、モジュレーティングプログラムの近傍にある可能性が低いであろう。新たに追加された生成物の１つを、第１フェーズの文法を使用して巡回した後、候補プログラム構造を、第２フェーズの文法を使用して完成することができる。第２フェーズの文法の確率は、変数又は関数の総距離を反映することができ、これは、その特定のシーケンスが巡回済みであるという元々の確率に沿ったものである。
【００９０】
別の実施形態によれば、生成的プログラミングの単一フェーズシステム及び方法が、ＡＤＶ、ＡＤＦ、又はその両方を含むフォーカスした文法を採用することができる。上述したように、強制的に等確率生成物にする（図６）ことが、新たに生成されたフォーカスした文法の生成物確率を割り当てる最も単純な方法である。わずかにより込み入った戦略では、距離に関しても同様に近傍候補プログラムを生成するように確率を調整しようとし得る。このような２つの手法は、実質的に図７及び図８を参照して上述したように確率を調整又はフォーカスすることができる。特に、図６〜図８の例示的な実施形態のいずれか１つ並びに他の各種実施態様が、単一フェーズの生成的プログラミング戦略に適し得る。
【００９１】
その点において、影響を受けた規則の生成物に確率を割り当てる、潜在的により正確又は他の場合にはより適切な戦略が存在し得ることが理解されよう。可能ではあるが上述したメカニズムよりはるかに複雑なこのような１つの戦略では、目標は、モジュレーティングプログラムとフォーカスした文法によって生成された候補プログラムとの列編集距離が、確率の低下に従って大きくなるように確率を生成物に割り当てることである。この問題は、未知の確率を解くために最適化式の形にすることができる。
【００９２】
詳細に上述したように、フォーカスした文法は、モジュレーティングプログラムの分解を通して特定されたＡＤＰを追加することによって構築することができ、いくつかの代替の実施態様では、フォーカスした文法は単に、基本文法に存在する生成物に関連する確率を操作する（たとえば、モジュレーティングプログラムの生成中に巡回された生成物の確率を選択的に増減、又は調整する）だけで、追加の生成物をフォーカスした文法に追加することなく生成することができる。増大した生成物確率を採用する一実施形態では、候補プログラムを生成することは、増大した確率を元の基本文法で規定された対応する確率に向けて選択的に弱める又はバイアスすることを含むことができ、候補解の生成中の生成物確率のこのような動的な変更又は選択的な操作により、モジュレーティングプログラムからはるかに離れて存在する（すなわち、モジュレーティングプログラムに類似する可能性が低い）候補プログラムを生成する危険性を最小化又はなくすことができる。
【００９３】
たとえば、図４を参照して、基本文法の＜ａｓｓｅｒｔｉｏｎ＞規則は概して、以下のように表すことができる。
2007528538.tif 000003
【００９４】
生成物２は、図５を参照して上述したようにモジュレーティングプログラムの構築中に訪れられているため、生成物２の確率は、増大する、又は押し上げる等、選択的に調整することができる。確率を選択的に押し上げることを採用するこのような一実施形態では、押し上げを通してのフォーカスした文法の初期状態を以下のように表現することができる。
2007528538.tif 000004
【００９５】
生成物２を後続の候補プログラムの構築中に巡回した後、上述したように、押し上げられた生成物を再び、基本文法の元の生成物確率に向けて弱めることができる。各種弱化戦略によれば、所与の生成物確率を、元の生成物確率に即座にリセット（たとえば、単一動作で）してもよく、又は元の生成物確率に徐々に近づくように操作してもよい（たとえば、段階的に、又は中間段階を含み得る他の増分様式で）。
【００９６】
端的に上述したように、ストリーク探索方法は、プログラム又は他の解を求めて探索を行う方法を特徴とすることができる。特に「プログラム」を参照して後述するように、上述のようにストリーク探索方法を採用して、各種解（式、化学構造、式系等）を特定することができる。特に、このような方法は概して、局所エリア（すなわち、優良な候補プログラム又はモジュレーティングプログラムの近傍）を探索するニーズと、さらなる局所改良の可能性が低い場合に探索空間の別の部分に移るニーズとの間でバランスをとろうとする。一実施形態によれば、ストリーク探索方法は、有効な「基本」プログラム（候補プログラム又はモジュレーティングプログラム）の特定又は選択から開始することができる。比較的局所の（又は類似する）代替の候補プログラム群を、基本プログラムに従ってモジュレート又は変更されたフォーカスした文法から生成することができる。次いで、これらの代替の候補プログラムを評価することができる。所望の目的関数に関して得点が優良の候補プログラムは、候補プログラムの新しい局所群に対する新しいモジュレーティングプログラムになることができる。
【００９７】
次いで、新しい局所群内の各候補プログラムが、後続の探索のモジュレーティングプログラムになり得る。上記のプロセスは再帰的に続けることができ、探索は、満足のいく結果が得られたとき、又は所定の時間期間が経過したときに終了し得る。実際に、より優良な候補プログラムが特定されると、探索は改良方向において続けられる。或る時点で、たとえばさらなる局所改良の可能性が低いとき、又はさらなる改良が所定の繰り返し回数中に見られなかったとき、ストリークを放棄し、探索を別の基本プログラムを使用して新たに開始することができる。
【００９８】
動作に際して、図１及び図３を参照して上述したようなプログラムジェネレータ１２０は、１つのフォーカスした文法又は複数のフォーカスした文法を採用して、そのフォーカスした文法の構築に使用されたモジュレーティングプログラムに類似する新しい候補プログラムを生成することができる（多数の構築済み候補プログラムを引き継ぐ場合）。いくつかの実施形態では、プログラムジェネレータ１２０は、２フェーズプロセス又は他のマルチフェーズプロセスを実施することができる。その点において、プログラムコード又は他のコンピュータ実行可能命令セットにより、プログラムジェネレータ１２０は、第１フェーズのフォーカスした文法をランダムに巡回し（確率に従って）、新しい生成物の１つを巡回するまで新しい候補プログラム構文解析木を構築することができ、第１の新しい生成物が巡回されると、プログラムジェネレータ１２０は、完全な構文解析木が構築されるまで第２フェーズのフォーカスした文法を使用し続け得る。別法として、上述したような各種の洗練されたフォーカスした文法を単一フェーズ動作で採用してもよい。
【００９９】
プログラム又は解を表すコンピュータ実行可能言語又は機械実行可能言語は、いずれのコンピュータアプリケーションでも重要な考慮事項であり得ることが理解されよう。たとえば、コンパイル型言語は、エグゼキュータブルの作成に余分な時間が必要なことに加えて、結果生成された候補プログラムを実行する時間が、単にプログラムを解釈するためにかかる時間を容易に超え得るため生成的プログラミング技法にあまり適さない場合がある。さらに、従来の言語は、人間のプログラマが効率的且つ素早く読み書き解析するように設計された。要件が最小の機械可読言語と比較して、従来のプログラミング言語は不必要なシンタックス、冗長な構造体、長いコードセグメント、また時には曖昧ささえも導入する。
【０１００】
インタプリタ型言語の方が、高負荷なコンパイル型言語よりも生成的プログラミング方法に適する可能性があることが理解されよう。インタプリタ型言語との併用に向けて最適化されたインタプリタを、たとえば評価器１３０と併せて採用するいくつかの実施形態では、生成的プログラミングのシステム及び方法は単純に、コンパイルに関わる処理オーバヘッド及び時間なしで、生成された候補プログラムを実行することができる。
【０１０１】
それ故に、新しい言語が特に生成的プログラミング方法と併用するように設計された。スタック処理言語（ＳＭＬ）は、単純、容易、高速、且つその結果として必ずしもヒューマンフレンドリとは限らないように設計されたインタプリタ型言語である。ＳＭＬは概して、スタックセット（各データ型に１つずつ）、大域変数セット（各データ型に１つずつ――概して文字列鍵によって特定される）、関数セット、及びインタプリタ（評価器１３０により独立して、或いはプログラムジェネレータ１２０、プロセッサ３９０、又はその両方と協働して実行可能であり得るような）を含む。スタックは、ユーザ定義関数に利用することもでき、又はユーザ定義関数により直接使用することもできる。さらに、関数自体が、スタックから必要なデータを取得すること、及び生成された結果を再びスタックに返すことを受け持つことができる。ユーザ定義関数は、関数名の下に登録することができ、以下の形式に従って使用することができる。
ｆｕｎｃｔｉｏｎｎａｍｅ（ネストされた関数呼び出し）、又は
ｆｕｎｃｔｉｏｎｎａｍｅ｛構造体引数｝（ネストされた関数呼び出し）
【０１０２】
次いで、構造列を永続性のために使用することができ、これは構築フェーズ中に関数オブジェクト内に渡される。たとえば、評価器１３０で機能するインタプリタは、プログラム列を一連の関数呼び出しとして構文解析し、その後、各関数呼び出しが呼び出されると各関数呼び出しを順に実行することができる。
【０１０３】
これより、上記の説明を鑑みて図９を参照すると、生成的プログラミング方法が、記号再帰及び帰納解析での大変革を表すことが理解されよう。特に、図９は、生成的プログラミング方法の一実施形態の全体的な動作の流れを示す簡略化したフローチャートである。
【０１０４】
基本文法を、ブロック９１０に示すようにユーザ入力に従って初期化、確立、又は受け取ることができる。モジュレーティングプログラムセットが空の（すなわち、モジュレーティングプログラムが現在存在しない）場合、判断ブロック９２０における判断により、ブロック９２１に示すように候補プログラムを生成することができ、上述したように、ブロック９２１における動作は、ブロック９１０において与えられる基本文法（たとえば、図４参照）によって規定される規則、生成物、及び各確率に従って候補プログラム（たとえば、図５参照）を生成することができる。その点において、プログラムジェネレータ（図１及び図３を参照して上述したような）は、文法を巡回し、その文法に指定されている規則、生成物、及び確率に従って列リテラルインスタンスを構築又は組み立てることによって候補プログラムを生成するように構成することができ、またそのように動作することができる。
【０１０５】
候補プログラムを実行し、所定の基準又は客観的な測度に従って評価することができる（ブロック９２３）。この動作は、実質的に上述したように、評価器、インタプリタ、又はその両方によって進めることができる。その点において、評価器（図１及び図３を参照して上述したような）は、シミュレートされた環境で候補プログラムを実行し、そのパフォーマンス又は他の特性を測る、定量化する、又は評価するように構成することができ、またそのように動作し得ることが理解されよう。候補プログラムのこのような実行は、インタプリタ型プログラミング言語の使用から益を受けることができ、評価器は、このためにインタプリタを採用する、又はインタプリタと協働することができる。別法として、候補プログラムは、１つ又は複数のコンパイル型プログラミング言語の要件に従ってコンパイルし実行することができ、このような実施態様は、たとえば、厳密な互換性要件を有するアプリケーション又はデータ処理能力が限られていない場合に適切であり得る。
【０１０６】
候補プログラムを客観的に評価する各種方法、並びに得点又は重みを候補プログラムに割り当てる技法が概して既知であり、通常、用途に固有であり、ブロック９２３及びブロック９４４に示す動作（後述）に関して、本開示が特定の評価方式又は得点付け法のいずれにも限定されないものであることが理解されよう。
【０１０７】
候補プログラムは、モジュレーティングプログラムセットに挿入することができる（ブロック９２５）。いくつかの実施形態では、候補プログラムは、評価（すなわち、得点、ランク、又は他の示差的な客観的タグ）に関連するデータと共にモジュレーティングプログラムセットに挿入することができ、それにより、モジュレーティングプログラムセット内の複数の候補プログラムを、パフォーマンス特性に従ってランク付け又は特定することができる。別法として、候補プログラムは、得点を表す関連するデータなしで、又は評価情報にこだわることなくモジュレーティングプログラムセットに挿入することができ、このような一実施形態では、候補プログラムは、たとえばランダムに、先入れ先出しベースで、先入れ後出しベースで、又は他の或る所望の任意の戦略に従ってモジュレーティングプログラムセットに挿入、またモジュレーティングプログラムセットから選択することができる。
【０１０８】
候補プログラムは、モジュレーティングプログラムセットから選択し、現在のモジュレーティングプログラムとして割り当てることができ（ブロック９２７）、概ね図４〜図８を参照して上述したように、１つ又は複数のフォーカスした文法を現在のモジュレーティングプログラム及び現在の基本文法から生成することができる（ブロック９２９）。
【０１０９】
所定の繰り返し回数分、又はユーザ定義若しくは自動的に生成される停止規則が満たされるまで、判断を判断ブロック９４０において繰り返し行い、１つ又は複数のフォーカスした文法を使用して候補プログラムを生成し（ブロック９４２）、生成された候補プログラムを評価することができる（ブロック９４４）。図９の下にあるループは概して、上述したストリーク探索技法の一実施形態によって採用される局所探索法を表す。判断ブロック９５０において判断されるように、現在のモジュレーティングプログラムよりも「優良」な（すなわち、ブロック９４４における評価に従ってより適している、又はより適切であると考えられる）プログラムを、さらなる、又はその後の局所探索を導き出すことができるモジュレーティングプログラムとして、その後の選択及び割り当てのためにモジュレーティングプログラムセットに挿入することができる（ブロック９５２）。
【０１１０】
さらなる改良の可能性がもはやない場合のように、又は指定の繰り返し回数に従って、現在の反復ループを終了することができる、又は終了すべきだという判断が判断ブロック９４０において行われる場合、現在のストリークを終了することができ、モジュレーティングプログラムセットを、判断ブロック９２０にループバックする実線矢印で示すように再び調べることができる。
【０１１１】
上記の様式では、探索空間内の、有望な候補解近傍の局所性を完全に調べることができ、これは、探索が、或る点で優れていると先に評価された候補解による影響を受ける変更済み文法に従って再帰的にフォーカスされるためである。
【０１１２】
図９に示す機能ブロックの配置は多くの変形が可能であり、動作順を示唆して他の可能性を除外するものではないことが理解されよう。たとえば、図９の上にあるループ（判断ブロック９２０から下の判断ブロック９４０への）は、図９の下にある動作ループ（判断ブロック９４０から判断ブロック９５０を通り、そして再び判断ブロック９４０に戻る）と並列に進めることができる。これに加えて、又はこれに代えて、図９の下に示す動作ループの複数のインスタンスを、たとえば並列に、又はほぼ同時に、又は同時に実行することができ、このような一実施形態は、マルチタスク高速コンピュータ又はデータ処理システムの並列処理及び他の増大しつつある性能を利用することができる。
【０１１３】
本発明による生成的プログラミングシステム及び方法は上述した実施の形態に限定されず、特許請求の範囲に記載した範囲で種々の変形や改良が可能である。
【図面の簡単な説明】
【０１１４】
【図１】本発明の実施の形態による生成的プログラミングシステムの構成要素を示す簡略化したハイレベルブロック図。
【図２】生成的プログラミング方法の例示的な実施形態の全体的な動作の流れを示す簡略化したフローチャート。
【図３】生成的プログラミングシステムの要素を採用することができる例示的な環境を示す簡略化した機能ブロック図。
【図４】記述文法の一実施形態を示す簡略図。
【図５】候補プログラムの生成に文法を採用する方法の一実施形態の全体的な動作を示す簡略図。
【図６】等確率フォーカスした文法の一実施形態を示す簡略図。
【図７】再利用に向けて整形されたフォーカスした文法の一実施形態を示す簡略図。
【図８】類似した終端に向けて整形されたフォーカスした文法の一実施形態を示す簡略図。
【図９】生成的プログラミング方法の一実施形態の全体的な動作の流れを示す簡略化したフローチャート。
【符号の説明】
【０１１５】
１００・・・生成的プログラミングシステム
１１０・・・文法モジュール
１２０・・・プログラムジェネレータ
１３０・・・評価器
３００・・・コンピュータ環境
３１０・・・処理システム
３２０・・・ポート通信
３２０・・・通信ポート
３３０・・・電源
３４０・・・インタフェース
３４０・・・入出力インタフェース
３８０・・・メモリ
３９０・・・プロセッサ
【図１】
2007528538.tif 000005
【図２】
2007528538.tif 000006
【図３】
2007528538.tif 000007
【図４】
2007528538.tif 000008
【図５】
2007528538.tif 000009
【図６】
2007528538.tif 000010
【図７】
2007528538.tif 000011
【図８】
2007528538.tif 000012
【図９】
2007528538.tif 000013