(57)【特許請求の範囲】
【請求項１】
ユーザにより対象問題に関する制約伝播の順序を有する２以上の制約条件であり、当該２以上の制約条件の記載順序が制約伝播の順序を示す、または当該２以上の制約条件に設定されている優先順位が制約伝播の順序を示す２以上の制約条件を入力する制約条件入力手段と、
前記制約条件に用いられる変数の初期値を設定する変数値設定手段と、
初期値の設定を含む、値が変更された１以上の変数を特定する情報を第一の記憶領域（集合Ｓ）に書き込む処理、
前記第一の記憶領域に値が変更された１以上の変数を特定する情報が存在するか否かを判断し、当該変数を特定する情報が前記第一の記憶領域に存在する場合に、前記１以上の各変数を一つずつ取り出し、前記１以上のいずれかの変数を構成要素として有する１以上の制約条件を、前記制約条件入力手段により入力された制約条件の中から抽出する処理、
および当該抽出した１以上の制約条件を特定する情報を、第二の記憶領域（集合Ｑ）に書き込む処理を行う制約条件抽出手段と、
前記制約条件抽出手段により抽出された１以上の制約条件のすべてに対して、前記制約伝播の順序に基づいて、順次、制約条件を取り出し、当該制約条件を満たすために変更するべき変数を決定し、当該変数の値を算出する制約条件解算出手段と、
前記制約条件解算出手段により算出された変数の値であり、当該変数の新たな値である変動値を、当該変数に設定する変数値再設定手段とを具備し、
前記制約条件抽出手段は、
前記変数値再設定手段が設定した変動値に対応する前記変数を特定する情報をも前記第一の記憶領域に書き込む処理をも行い、
前記第一の記憶領域から、取り出されていない変数を特定する情報が存在しなくなるまで、１以上の変数の取り出し、前記１以上のいずれかの変数を構成要素として有する１以上の制約条件を、前記制約条件入力手段により入力された制約条件の中から抽出する処理、および当該抽出した１以上の制約条件を特定する情報を、第二の記憶領域（集合Ｑ）に書き込む処理を繰り返し行い、
前記制約条件解算出手段は、
前記第二の記憶領域に抽出されていない制約条件がなくなるまで、前記制約条件抽出手段により抽出された１以上の制約条件のすべてに対して、前記制約伝播の順序に基づいて、前記変数の変動値を代入して、当該制約条件の解を算出するコンピュータシステム。
【請求項２】
コンピュータが具備する制約条件入力手段、変数値設定手段、制約条件抽出手段、制約条件解算出手段、および変数値再設定手段により実現される制約条件解決方法であって、
前記制約条件入力手段が、ユーザにより対象問題に関する制約伝播の順序を有する２以上の制約条件であり、当該２以上の制約条件の記載順序が制約伝播の順序を示す、または当該２以上の制約条件に設定されている優先順位が制約伝播の順序を示す２以上の制約条件を入力する制約条件入力処理と、
前記変数値設定手段が、前記制約条件に用いられる変数の初期値を設定する変数値設定処理と、
前記制約条件抽出手段が、初期値の設定を含む、値が変更された１以上の変数を特定する情報を第一の記憶領域（集合Ｓ）に書き込み、前記第一の記憶領域に値が変更された１以上の変数を特定する情報が存在するか否かを判断し、当該変数を特定する情報が前記第一の記憶領域に存在する場合に、前記１以上の各変数を一つずつ取り出し、前記１以上のいずれかの変数を構成要素として有する１以上の制約条件を、前記制約条件入力手段により入力された制約条件の中から抽出し、および当該抽出した１以上の制約条件を特定する情報を、第二の記憶領域（集合Ｑ）に書き込む処理を行う制約条件抽出処理と、
前記制約条件解算出手段が、前記制約条件抽出処理により抽出された１以上の制約条件のすべてに対して、前記制約伝播の順序に基づいて、順次、制約条件を取り出し、当該制約条件を満たすために変更するべき変数を決定し、当該変数の値を算出する制約条件解算出処理と、
前記変数値再設定手段が、前記制約条件解算出処理により算出された変数の値であり、当該変数の新たな値である変動値を、当該変数に設定する変数値再設定処理とを含む制約条件解決方法であって、
前記制約条件抽出処理において、
前記変数値再設定処理により設定された変動値に対応する前記変数を特定する情報をも前記第一の記憶領域に書き込み、前記第一の記憶領域から、取り出されていない変数を特定する情報が存在しなくなるまで、１以上の変数の取り出し、前記１以上のいずれかの変数を構成要素として有する１以上の制約条件を、前記制約条件入力手段により入力された制約条件の中から抽出する処理、および当該抽出した１以上の制約条件を特定する情報を、第二の記憶領域（集合Ｑ）に書き込む処理を繰り返し行い、
前記制約条件解算出処理において、
前記第二の記憶領域に抽出されていない制約条件がなくなるまで、前記制約条件抽出処理により抽出された１以上の制約条件のすべてに対して、前記制約伝播の順序に基づいて、前記変数の変動値を代入して、当該制約条件の解を算出する制約条件解決方法。
【請求項３】
コンピュータを、
ユーザにより対象問題に関する制約伝播の順序を有する２以上の制約条件であり、当該２以上の制約条件の記載順序が制約伝播の順序を示す、または当該２以上の制約条件に設定されている優先順位が制約伝播の順序を示す２以上の制約条件を入力する制約条件入力手段と、
前記制約条件に用いられる変数の初期値を設定する変数値設定手段と、
初期値の設定を含む、値が変更された１以上の変数を特定する情報を第一の記憶領域（集合Ｓ）に書き込む処理、
前記第一の記憶領域に値が変更された１以上の変数を特定する情報が存在するか否かを判断し、当該変数を特定する情報が前記第一の記憶領域に存在する場合に、前記１以上の各変数を一つずつ取り出し、前記１以上のいずれかの変数を構成要素として有する１以上の制約条件を、前記制約条件入力手段により入力された制約条件の中から抽出する処理、
および当該抽出した１以上の制約条件を特定する情報を、第二の記憶領域（集合Ｑ）に書き込む処理を行う制約条件抽出手段と、
前記制約条件抽出手段により抽出された１以上の制約条件のすべてに対して、前記制約伝播の順序に基づいて、順次、制約条件を取り出し、当該制約条件を満たすために変更するべき変数を決定し、当該変数の値を算出する制約条件解算出手段と、
前記制約条件解算出手段により算出された変数の値であり、当該変数の新たな値である変動値を、当該変数に設定する変数値再設定手段として機能させるためのプログラムであって、
前記制約条件抽出手段は、
前記変数値再設定手段が設定した変動値に対応する前記変数を特定する情報をも前記第一の記憶領域に書き込む処理をも行い、
前記第一の記憶領域から、取り出されていない変数を特定する情報が存在しなくなるまで、１以上の変数の取り出し、前記１以上のいずれかの変数を構成要素として有する１以上の制約条件を、前記制約条件入力手段により入力された制約条件の中から抽出する処理、および当該抽出した１以上の制約条件を特定する情報を、第二の記憶領域（集合Ｑ）に書き込む処理を繰り返し行い、
前記制約条件解算出手段は、
前記第二の記憶領域に抽出されていない制約条件がなくなるまで、前記制約条件抽出手段により抽出された１以上の制約条件のすべてに対して、前記制約伝播の順序に基づいて、前記変数の変動値を代入して、当該制約条件の解を算出するものとして、コンピュータを、
機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、任意の制約条件から構成される問題に対する効率的な解決に関し、特に、制約伝播の処理手順が考慮された制約条件及び変数値の設定のみで実行可能な制約条件解決方法、制約条件解決装置、及び制約条件解決システムに関するものである。
【背景技術】
【０００２】  様々なアプリケーションプログラムに対する現在の一般的なプログラミング手法は、例えば、Ｃ言語、ＪＡＶＡ等のようなプログラミング言語を使って、データ構造を手続き的に宣言した上でそのデータの処理手順（アルゴリズム）をユーザが逐次記述する手続き型プログラミング手法が主流である。コンパイラの最適化機能により最適化が図られること等を除けば、この手続き型プログラミング手法によるデータの処理手順は、計算機が実際に実行する処理手順と一致しているのが原則である。したがって、手続き型プログラミング手法は、計算機（ＣＰＵ）の動きを詳細に記述することによって各種の問題に柔軟に対応できる解決方法である。【０００３】  このようなＣＰＵの動きを記述する手続き型プログラミング手法に対するものとして、宣言的プログラミング手法がある。これは、対象問題に対応した制約条件がユーザにより定義されるとその後の実際のデータ処理手順については、ＣＰＵにすべて任せてしまう手法であり、特定の問題領域には好都合な問題解決手法であるとして従来より用いられている（例えば、特許文献１または特許文献２）。
前記宣言的プログラミングにおいては、ユーザは、制約条件を記述するのみで解が出力されるのを待つだけで良い半面、ＣＰＵがデータ処理をどのような手順で行うかについては干渉できないという特徴を有している。現在の計算機環境では、前述したような大きく２つに分けられるプログラミング手法のうち、手続き型プログラミング手法が主に使用されている。【０００４】  この手続き型プログラミング手法によってプログラム開発を行う場合、ユーザがデータ構造の定義を行った時点で、そのデータ構造によって記述すべきアルゴリズムも連動して事実上決定されてしまうのが殆どである。しかもそのアルゴリズムは類似した対象問題では同様な手順で表現され、パターン化することが可能である。【０００５】  このため、各アプリケーションで同じようなプログラミング作業が重複して行われることが多く、プログラム開発の非効率化が従来より問題となっていた。この問題に対処するため、現在では汎用的に使用されるプログラミング部分のライブラリ化やオブジェクト指向に基づくソフトウェア開発によってソフトウェアの部品化を積極的に導入し、既存のプログラムにない部分に集中したプログラム作業の高効率化が推進されている。【０００６】
【特許文献１】特開平５−３５４８号公報
【特許文献２】特開平９−８１３８７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、現実的にはライブラリ化されるソフトウェア部品は膨大であってしかも年々その数は増加している。各プログラマーが、この膨大な部品群から対象問題に最適なものを抽出する際には選択ミスが少なからずあり、再度選択し直すことで開発作業をやり直さなければならない危険性があることを考慮すると、ソフトウェア部品を利用せずに始めから各プログラマーがコーディング作業を行うケースも多々あるという問題があった。
また、オブジェクト指向によるソフトウェア開発は一定のスキルが要求されることから、どのプログラマーでもオブジェクト指向のプログラミング作業ができるとはかぎらず、全体的にみれば作業効率はさほど向上しないという問題があった。
このように、プログラム開発作業には、個人技量に依存した閉鎖的な面や非効率的な面が依然として解消していないという問題があるのが現状である。
【０００８】  一方、前述したように、宣言的プログラミング手法では、少なくとも制約条件の記述と、当該制約条件で用いるデータ値とが必要であって、実際の問題に適用した場合、その制約条件及びデータの数は非常に多くなる。ここで、実際の問題とは、例えば、
ｆｋ（Ｘ１，Ｘ２，…，Ｘｎ）≦ｂｋ（ｋ＝１，２，…，ｍ）の連立式を満たし、且つ、評価関数ｆ０（Ｘ１，Ｘ２，…，Ｘｎ）を最小値にするような組合せ最適化問題である。つまり、図１７に示すように、ｍ個の連立式及び評価関数ｆ０で表した制約条件を計算機側に与えると、計算機（図１７の制約解消系）は全ての制約条件を同時に満たすデータを一括して探索することが行われる。【０００９】  この組合せ最適化問題は、変数Ｘ及び連立式の数が増加するほど解空間における組合せの可能性が指数関数的に増加することから、計算機上での処理が複雑かつ膨大となる。しかも、特に関数ｆｋが非線形関数の場合は、分散した複数の解空間が存在することもあり、解が存在しない解空間をひたすら探索してしまって無限ループに陥ることのないよう効率的に解を求める工夫等が必要になる。なお、組合せ最適化問題の他にも、組合せ充足問題、整数計画法などについても同様の問題点がある。【００１０】  さらに、制約条件の条件式または入力データの一部を変更する必要が生じたときは、先に計算した同様の制約条件問題をまた最初から計算し直さなければならず、リソースの無駄使いになるとともに非常に非効率的であるという問題があった。【００１１】  そこで、本発明は前述した問題点に鑑み、計算機上でのデータ処理手順であるアルゴリズムを記述することなく、対象問題を少ない計算時間で確実に解決することを目的としている。
【課題を解決するための手段】
【００１２】  本発明の制約条件解決方法は、ユーザにより対象問題に関する制約伝播の処理手順が考慮された制約条件を入力する制約条件入力処理と、前記制約条件入力処理により入力された制約条件に用いられる変数の初期値または変動値を設定する変数値設定処理と、前記制約条件入力処理により入力された制約条件の中から、前記変数値設定処理により設定された値に関係する制約条件を抽出する制約条件抽出処理と、前記制約条件抽出処理により抽出された制約条件全てに対して、前記ユーザにより考慮された制約伝播の処理手順に基づいて前記変数の初期値または変動値を代入して当該制約条件の解を算出する制約条件解算出処理と、前記制約条件解算出処理により算出された解を前記変数値設定処理での新たな変動値として設定する変数値再設定処理とを含み、前記変数値再設定処理は、再設定される新たな変動値が存在する間は、前記制約条件抽出処理及び前記制約条件解算出処理を繰り返し行うことを特徴とする。【００１３】  本発明の制約条件解決方法は、制約条件を入力する制約条件入力処理と、前記制約条件入力処理により入力された制約条件に用いられる変数の値を設定する変数値設定処理と、前記制約条件入力処理により入力された制約条件の中から、前記変数値設定処理により設定された値に関係する制約条件を抽出する制約条件抽出処理と、前記制約条件抽出処理により抽出された制約条件の解を算出する制約条件解算出処理とを含む制約条件解決方法において、前記制約条件は、現在の配列要素数を含んでいること、前記変数に複数個の値を持たせること、構造体配列の要素値による検索を含んでいること、及びデフォルト規則による文字列数値変換の少なくとも何れかを特徴として構成される。【００１４】  本発明の制約条件解決装置は、ユーザにより対象問題に関する制約伝播の処理手順が考慮された制約条件を入力する制約条件入力手段と、前記制約条件入力手段により入力された制約条件に用いられる変数の初期値または変動値を設定する変数値設定手段と、前記制約条件入力手段により入力された制約条件の中から、前記変数値設定手段により設定された値に関係する制約条件を抽出する制約条件抽出手段と、前記制約条件抽出手段により抽出された制約条件全てに対して、前記ユーザにより考慮された制約伝播の処理手順に基づいて前記変数の初期値または変動値を代入して当該制約条件の解を算出する制約条件解算出手段と、前記制約条件解算出手段により算出された解を前記変数値設定手段での新たな変動値として設定する変数値再設定手段とを含み、前記変数値再設定手段は、再設定される新たな変動値が存在する間は、前記制約条件抽出手段及び前記制約条件解算出手段が繰り返し行うことを特徴とする。【００１５】  本発明の制約条件解決装置は、制約条件を入力する制約条件入力手段と、前記制約条件入力手段により入力された制約条件に用いられる変数の値を設定する変数値設定手段と、前記制約条件入力手段により入力された制約条件の中から、前記変数値設定手段により設定された値に関係する制約条件を抽出する制約条件抽出手段と、前記制約条件抽出手段により抽出された制約条件の解を算出する制約条件解算出手段とを含む制約条件解決方法において、���記制約条件は、現在の配列要素数を含んでいること、前記変数に複数個の値を持たせること、構造体配列の要素値による検索を含んでいること、及びデフォルト規則による文字列数値変換の少なくとも何れかを特徴として構成される。【００１６】  本発明の制約条件解決システムは、複数の機器が互いに通信可能に接続されている制約条件解決システムであって、上記機器のうち少なくとも１つの機器は、前記何れかに記載の制約条件解決装置の機能を有することを特徴とする。
【発明の効果】
【００１７】  本発明によれば、対象問題に対する制約伝播の処理手順が考慮された制約条件、及び制約条件に用いられる変数の値（初期値）を入力すると、当該変数の値に関連する制約条件を抽出した上でその制約条件のそれぞれを満たす解を導くとともに、導かれた解を変数の新たな値（変動値）として代入して前記各制約条件の解を求める処理を繰り返すように構成したので、他の制約条件とのＡＮＤ関係をもつことなく各制約条件単独での解を求めることが可能となり、計算処理を高速に行いながら最終解を得ることができる。
【発明を実施するための最良の形態】
【００１８】  以下、本発明の好適な実施の形態について図面を参照しながら詳細に説明する。
図１８は、従来のプログラミング言語環境と、本発明の制約条件の解を求める制約解消系との位置付けを概念的に示した図である。図１８に示すように、従来のプログラミング言語環境には、プログラム言語処理系と、プログラムコードと、データとがあって、プログラム言語処理系がプログラムコード及びデータを制御する形態になっている。本発明では従来のプログラミング言語環境におけるデータの他に、制約式（制約条件）及び制約解消系を備え、それぞれが相互に情報のやり取りを行うことができるように接続される構成である。
また、図１９も従来のプログラミング言語環境であるが、前記従来の制約解消系をライブラリの形で構成したときの構成図である。【００１９】（第１の実施形態）
まず、本発明の第１の実施形態における制約条件解決装置の基本構成及びその基本動作について説明する。
＜制約条件解決装置１００の基本構成＞
図１は制約条件解決装置１００の基本的な構成要素を示す全体構成図である。
図１に示すように制約条件解決装置１００は、制約条件入力手段１と、変数値設定手段２と、制約条件抽出手段３と、制約条件解算出手段４と、変数値再設定手段５とを含んでいる。【００２０】  制約条件入力手段１は、ユーザが計算機（ＣＰＵ）による制約伝播の処理手順を頭に思い浮かべて決定した制約条件を入力するためのものである。
変数値設定手段２は、制約条件入力手段１により入力された制約条件を構成する各変数にユーザが指定した具体的な初期値を設定するためのものである。また、詳細は後述するが、各変数に対して初期値以外の値（以下、変動値と称する）を設定することも行う。
また、制約条件入力手段１及び変数値設定手段２は、いわゆるデータ入力用のＵ／Ｉであり特に限定するものではなく、入力を容易に行える様々なツールを含むものであり、ユーザが入力した値を確認することができる表示（モニタ）画面を備えることができる。なお、制約条件解決装置１００により計算された値をユーザに提示する出力表示手段（不図示）を含む構成にしてもよい。この出力表示手段も出力値を確認することができる表示（モニタ）画面を備えることができる。さらに、制約条件入力手段１（変数値設定手段２を含む）及び出力表示手段の一つにして、データを入出力が行える入出力手段であってもよい。【００２１】  制約条件抽出手段３は、入力された制約条件の中から、初期値または変動値が設定された各変数を構成要素として有する制約条件を抽出する。本実施形態では、制約条件抽出手段３は、該当する制約条件をまとめて抽出するように構成したが、後述する制約条件解算出手段４によってある１つの制約条件の解を求めた後、次の制約条件を抽出することを順次繰り返すように、一つずつ抽出するようにしても構わない。【００２２】  制約条件解算出手段４は、初期値または変動値を代入した各制約条件を解くが、本発明の特徴として、制約条件すべてを満足するようないわゆる連立解として一括して解くのではなく、各制約条件の一つずつを対象にして解くようにしている。このため、ある変数の値が設定または変更されると、制約条件の１回目の解がシーケンス的に所定の順序に従って順次求まることになる。ここで、前記所定の順序とは、ユーザ（プログラマー）が制約伝播の処理手順を考慮して入力した制約条件で示す順序である。【００２３】  ここで、制約条件の具体例を以下に示す。
（Ａ）制約条件の例１
宣言的プログラミング手法を容易に理解するために説明として使用される典型的な例題としては、以下の会計計算問題が挙げられる。
いま、４つの物品の値段と個数をそれぞれ、（１）１００円，２個、（２）２００円，３個、（３）３００円，２個、（４）５０円，３個としたとき、値段、個数、及び小計の配列変数を用いて、本発明のいう制約条件をあらわせば、
値段［１］＝１００、値段［２］＝２００、値段［３］＝３００、値段［４］＝５０  …（式１）
個数［１］＝２、個数［２］＝３、個数［３］＝２、個数［４］＝３  …（式２）
小計［ｉ］＝値段［ｉ］×個数［ｉ］（ｉ＝１〜４）  …（式３）
合計＝Σ小計［ｉ］（ｉ＝１〜４）  …（式４）
となる。（式１）及び（式２）は、制約条件のうちの特に変数データの設定である。【００２４】  前記（式１）〜（式４）の記述から明らかなように、手続き型プログラミングの場合に必要な０→合計（→は代入を表す、以下同じ）、合計＋小計［１］→合計、合計＋小計［２］→合計、合計＋小計［３］→合計、合計＋小計［４］→合計という繰り返しループの記述が、宣言的プログラミングの場合には不要である。【００２５】  （Ｂ）制約条件の例２
ｓｔｒｉｎｇ  ｎａｍｅ，ｍｅｓｓａｇｅ，ｏｕｔｐｕｔｓ，ｏｕｔｐｕｔ；  …（式５）
ｎａｍｅ＝”特許太郎”  …（式６）
ｍｅｓｓａｇｅ＝”こんにちは。この文章はＨＴＭＬ文書の本です。”…（式７）
ｏｕｔｐｕｔｓ＝”名前”＆  ｎａｍｅ  ＆”メッセージ”＆  ｍｅｓｓａｇｅ；  …（式８）
ｏｕｔｐｕｔ＝”＜ＨＴＭＬ＞＜ＢＯＤＹ＞”＆  ｏｕｔｐｕｔｓ  ＆  ＜／ＢＯＤＹ＞＜／ＨＴＭＬ＞  …（式９）
前記（式５）が変数データの定義、（式６）〜（式７）が変数への値代入、及び前記（式８）〜（式９）が具体的な実行式である。また、＆演算子は文字列連結演算子である。前記（式６）〜（式７）のように、文字列ｎａｍｅ、ｍｅｓｓａｇｅを任意に書き換えてｏｕｔｐｕｔで出力されるＨＴＭＬ用テキストが生成される。【００２６】  （Ｃ）制約条件の例３
文字列ｓｔｒに別の文字列ａｄｄを次々連結していく動作を記述した制約条件を次に示す。
ｓｔｒｉｎｇ  ｓｔｒ；            …（式１０）
ｓｔｒｉｎｇ  ａｄｄ；            …（式１１）
ｓｔｒ＝ｓｔｒ  ＆  ａｄｄ        …（式１２）
前記（式１０）及び（式１１）は変数データの定義であり、前記（式１２）が具体的な実行式である。本例での文字列ｓｔｒの値変更による制約伝播は、文字列ａｄｄの値が変更されるたびに、文字列ｓｔｒへ文字列ａｄｄの値が追加されることが繰り返される。【００２７】  ここで、制約条件は、前記（Ａ）〜（Ｃ）で示すような等号または不等号で表される式である必要はないことに留意されたい。そして、制約式の評価は最終的に真か偽を答えとし、Ｃ言語等と同様に例えばｆ（ｘ）だけが制約条件として記述されていた場合にはこのｆ（ｘ）を実行し、結果が真または偽かによって判断され処理される。【００２８】  変数値再設定手段５は、制約条件抽出手段３及び制約条件解算出手段４により２回目以降の解を求めるために、制約条件解算出手段４で求めた１回目の解を各変数の新たな値、すなわち変動値として設定する。そして、一連の制約条件の解を求める処理は、制約条件解算出手段４で変更される解が存在しなくなって最終解に到達した後、制約条件解決装置１００が別途終了指令を受信したときに終了する。【００２９】  前述したように、本発明の特徴の１つは、抽出した各制約条件の変数に値を代入して制約条件１つずつを順次解いていくことを繰り返すことである。このためには制約伝播の処理手順を考慮して制約条件にあらかじめユーザが設定しておくことが前提となる。【００３０】  なお、制約条件解算出手段４による処理中に、解を求めることができない解不能、または解を特定することができない解不定の状態に陥った場合は、計算機に予め定義した適切な例外処理を実行するようにしておくことで、プログラムエラーとして出力されるようにするが、これはユーザが解けない制約条件を定義したことを意味する。本実施形態の制約条件解決装置１００において、ユーザは、本来解ける筈の処理手順になるように、計算機の処理手順を考慮した制約条件を設定しなければならない負担を負うが、これは従来の手続き型プログラミング作業に較べはるかに楽な作業である。【００３１】＜制約条件解決装置１００の全体動作＞
次に、前述した構成の制約条件解決装置１００の全体動作について説明する。
図２は、制約条件解決装置１００の動作手順を示すフローチャートである。
まず、ステップＳ２０で、制約条件に用いられる変数に初期値が設定されているか否かを判断する。前記判断の結果、制約条件入力手段１により入力された制約条件を構成する各変数に対してまだ初期値が設定されていない場合、ステップＳ２１で、変数値設定手段２は、ユーザが指定した初期値を設定する。【００３２】  次に、ステップＳ２２で、制約条件抽出手段３は、各変数の値が変更されていないかを判断する。制約条件として変数に初期値を設定したときは、最初の変更であるとして次のステップＳ２２へ進む。一度、初期値を設定後、後述するステップの処理が終了すると、制約条件解決装置１００は、このステップＳ２２で新たな変数の値変更があるまで待ちの状態が維持されている。なお、本フローチャートには「終了」を示していないが、動作終了指示命令が外部から入力されたとき、制約条件解決装置１００は、所定の動作処理（不図示）を実行して一連の動作を終了するように制御されている。【００３３】  ステップＳ２３では、制約条件抽出手段３は、ステップＳ２２で変更された変数を要素とする集合Ｓを生成する。ここで集合Ｓを生成するとは、例えば、計算機上のある記憶領域に、前記変更された変数の名前や、または変数の配列要素を識別できるサフィックスを書き込むこと等を意味する。
さらに、制約条件抽出手段３は、前記集合Ｓに要素が存在するか否か、すなわち、変数値設定手段２により値を変更した変数があるか否かを判断する（ステップＳ２４）。前記判断の結果、集合Ｓに要素があるとき（集合Ｓが空集合でないとき）は、制約条件抽出手段３は、集合Ｓから要素Ｓｍを１つずつ取り出す（ステップＳ２５）。【００３４】  次に、ステップＳ２６で、前記取り出した要素Ｓｍに関連した制約条件の集合Ｑを生成する。つまり、要素Ｓｍを含んで構成される制約条件があれば、制約条件抽出手段３はこれを集合Ｑに出力する。次に、ステップＳ２７で前記集合Ｑに要素がある間は、以下のステップＳ２８〜ステップＳ３０を繰り返して行う。【００３５】  ステップＳ２８で、制約条件解算出手段４は、集合Ｑから１つの制約条件Ｑｍを取り出す。そして、制約条件解算出手段４は、ステップＳ２８で取り出した制約条件Ｑｍを解いて、制約条件Ｑｍを満たすために変更するべき変数及びその値を求める（ステップＳ２９）。
ここで、ステップＳ２９における処理の詳細な内容は以下に示す通りである。
（１）制約条件Ｑｍが満たされているかどうかをチェックして、満たされているときは本ステップＳ２９を終了する。
（２）制約条件Ｑｍを満たすために変更するべき変数とその値を求める。
（３）前記（２）で求めた変数の値が正しいかどうかを検証する。
前記（２）はステップＳ２９の処理として必須であるが、その他の（１）及び（３）については必ずしもそうとは限らない。対象問題に応じてユーザが必要か否かを判断し、制約条件として明示的または黙示的に指示するように構成してよい。【００３６】  さらに、ステップＳ３０で、変数値再設定手段５は、ステップＳ２９で求めた変数に求めた値を再設定して、その後の処理ではその再設定した値を基に制約条件が解かれる。
したがって、ある変数が変更される場合、その変数に関連する複数個の制約条件があれば、１つずつ取り出された制約条件ごとの解が順次求まり、同時に、得られた解によって集合Ｓの最後部にその変数が追加されるようになる。【００３７】  一方、ステップＳ２８によって制約条件Ｑｍが取り出された結果、集合Ｑに要素がないとステップＳ２７で判断された場合、一連の処理はステップ２４へ戻り、集合Ｓから次の変数Ｓｍが取り出されて同様の処理が繰り返される。
この結果、集合Ｓに要素がなくなったとき、制約条件解決装置１００の処理としては安定状態に入った状況に相当することになり、前述したように、制約条件に用いられる任意の変数に新たな値が設定されるまでステップＳ２２で待ちの状態になる。【００３８】
本実施形態では、ステップＳ２５において集合Ｓに複数の変数Ｓｍを含んでいたときの変数Ｓｍを取り出す順序や、ステップＳ２８において制約条件Ｑｍを取り出す順序は、制約伝播の処理手順を考慮して、ユーザがその順序（優先順位）を明示的に指定して計算機に行わせるように制約条件を設定している。具体的には例えば、その優先順位は制約条件の記載した順序であるというようにあらかじめ決めておくことで達成される。この具体例を以下に示す。
【００３９】  前述した会計計算問題を再び用いる。
制約条件は、
値段［１］＝１００、値段［２］＝２００、値段［３］＝３００、値段［４］＝５０…（式１）
個数［１］＝２、個数［２］＝３、個数［３］＝２、個数［４］＝３  …（式２）
小計［ｉ］＝値段［ｉ］×個数［ｉ］（ｉ＝１〜４）  …（式３）
合計＝Σ小計［ｉ］（ｉ＝１〜４）  …（式４）
である。
前記（式１）〜（式４）の記載順序には意味がある。例えば、１番目に記載した制約条件（制約式）が最も優先順位が高く、以下順に低くなるものとする。この場合、（式１）及び（式２）により各変数に値を設定することが優先的に行われ、（式３）、（式４）はその後に制約式を計算機内部へ登録することを意味している。
制約式の実行順序は実行時に決まるが、集合Ｓ、集合Ｑから要素を取り出す順番が不確定である。これを決定するためには明示的な方法として、記載順序で判断したり制約式に優先順位を設定する方法がある。【００４０】  その他、前述した優先順位を計算機（ＣＰＵ）が自動的に行うように構成してもよい。この場合、ユーザは、計算機がどのような順序で行っても計算過程で矛盾が生じないような内容及び記載順序からなる制約条件を設定する必要があるが、これはユーザがプログラマーとして通常の知識や経験を備えていれば容易に成し得る作業である。【００４１】  次に、図２のフローチャートに示す動作手順を、前述した会計計算の例を用いて具体的な制約条件の変数値の変化を追いながら説明する。
例えば、値段［２］を、２００→２５０に変更したときを想定する。初期値の設定ではなくデータの変更なので、ステップＳ２０からステップＳ２２へ進む。ステップＳ２３によって、集合Ｓ＝｛値段［２］｝となる。ステップＳ２４で集合Ｓには要素があると判断されるので、ステップＳ２５で値段［２］が取り出される。【００４２】  次に、ステップＳ２６で、値段［２］だけに関連する制約条件である、小計［２］＝値段［２］×個数［２］が集合Ｑの要素となる。つまり、集合Ｑ＝｛小計［２］＝値段［２］×個数［２］｝が生成される。
次に、ステップＳ２７で集合Ｑには要素があると判断されるので、ステップＳ２８で、小計［２］＝値段［２］×個数［２］という制約条件が取り出される。ステップＳ２９で、制約条件の解、つまり、小計［２］＝２５０×３＝７５０が計算されて、ステップ３０では、小計［２］にこの変更値７５０を設定し、小計［２］を集合Ｓに追加して、集合Ｓ＝｛小計［２］｝を生成する。【００４３】  そしてステップＳ２７に戻るが、先の集合Ｑから１つしかなかった要素を取り出してしまい集合Ｑは空集合であるので、この後ステップＳ２４へ進む。
ステップＳ２４では、先ほど追加した集合Ｓの小計［２］を判断して、ステップＳ２５でこの小計［２］を取り出す。【００４４】  次に、ステップＳ２６で、小計［２］だけに関連する制約条件である、合計＝Σ小計［ｉ］（ｉ＝１〜４）を要素とする集合Ｑを生成する。つまり、
集合Ｑ＝｛合計＝Σ小計［ｉ］（ｉ＝１〜４）｝が生成される。ステップＳ２８で当該制約条件を取り出し、ステップＳ２９で、制約条件の解、つまり、合計＝２００＋７５０＋６００＋１５０＝１７００を計算して、ステップＳ３０で、変数の（合計）にこの変更値１７００を設定する。同時に変数の（合計）は集合Ｓへ格納される。続いて、ステップＳ２７、Ｓ２４、Ｓ２５、Ｓ２６が実行され、関連のある制約式が存在しないので、集合Ｑには追加される要素がない。
この時、計算時間を短縮するために以下のように単純化することが可能である。すなわち、ステップＳ２９で、制約条件の解を求める時に加算をもう一度行うのではなく、変化した値のみを利用して差分解消する。そして、ステップＳ３０では、合計に関連する制約条件は存在しないことがわかっているので、計算時間短縮のために集合Ｓには要素を追加しないようにする。【００４５】  再びステップＳ２７に戻るが、先の集合Ｑから１つしかなかった要素を取り出してしまい集合Ｑは空集合であるのでこの後ステップＳ２２へ進み、制約条件解決装置１００は次に外部からのデータ変更があるまで待ち状態になる。
なお、前述した制約条件解決装置１００の動作におけるステップＳ２８の処理では、集合Ｑより制約条件Ｑｍを１つずつ取り出してその解を求めていく処理を説明したが、必ずしも１つずつ取り出さなければならないことはない。制約式の解を同時に求めることが可能な場合、集合Ｑから２以上の制約条件を取り出すこととする。これにより、解決可能な対象問題をより広げることができるようになる。
さらに、制約条件Ｑｍの実際の解法は、会計問題のような単純な式変形で解くやり方に限っていない。既存の式に関する解法はすべて使用可能であるものとしており、これによりｎ次方程式の解法を導入することも認めている。【００４６】  また、別の具体的例として、制約条件に用いるデータの件数そのものを追加・削除するときの処理について説明する。
前述した会計計算の例では、値段及び個数の変数をそれぞれ配列で表現してデータ件数を各４個に固定して制約条件を設定したが、データ件数そのものを変数にしたときの制約条件を考える。現在の制約条件に値段［５］、個数［５］を加えて以下のように変更する。
値段［１］＝１００、値段［２］＝２５０、値段［３］＝３００、値段［４］＝５０、値段［５］＝３１０…（式１３）
個数［１］＝２、個数［２］＝３、個数［３］＝２、個数［４］＝３、個数［５］＝３  …（式１４）
項目総数＝５  …（式１５）
小計［ｉ］＝値段［ｉ］×個数［ｉ］（ｉは任意の整数）  …（式１６）
合計＝Σ小計［ｉ］（ｉ＝１〜項目総数）  …（式１７）【００４７】  前述した処理を全く同様に行えば、
小計［５］＝値段［５］×個数［５］＝３１０×３＝９３０、
合計＝Σ小計［ｉ］＝２００＋７５０＋６００＋１５０＋９３０＝２６３０となり、未解決のままの制約条件を残すことなく解を導くことが可能である。このような変更は変数または制約条件の削除する場合でも同様であり、可変長配列などで表された変数の個数を変更することも可能である。【００４８】  これを実際の入出力手段（例えば、制約条件入力手段１）を用いてユーザが制約条件及び値を入力する画面例を図２４に示す。なお、図２４の画面例は出力機能を有する制約条件入力手段１及び変数値設定手段２の画面例に相当し、ＵＮＩＸ上へ一般的なプログラミング言語と同等の入出力インタフェースを持つ構造として実装した実行例である。図２４（ａ）〜（ｈ）の入出力は一連のものであるが、便宜上、分けて表示している。
図２４（ａ）のように、まず「＄」で示されたＵＮＩＸプロンプトの後に、ユーザは「ｒｉｐｐｌｅ」を入力する（図２４（ｂ））。これにより本発明の処理が実装されたプログラムがロードされて、画面上に「％」を示してユーザにデータの入力を促す（％以降がユーザの入力データであり、改行されたその後すぐの行に、受信したデータ値や計算出力値を表示している）。【００４９】  そこでユーザは、初期値制約式入力する（図２４（ｃ）の２４１）。２４２の制約式はここでは合計計算を関数配列全合計（）として抽象化しているが、図２１で示したような制約式で表現することもできる。また、手続的なループ構造を直接記述することもできる（関数型言語との融合を参照）。そしてステップＳ２９の処理で合計計算の差分解消を実現する時には、制約条件解決装置１００側が判断して自動処理され、ユーザは意識していない。【００５０】  次に、ユーザは初期値を設定する（図２４（ｄ）の２４３，２４４）。ステップＳ２２〜ステップＳ３０に示した処理が実行されるが、実行の効率を図るために明らかに必要ない時には制約条件解決装置１００側の判断で実行させないことができる。図２４（ｅ）の２４５では、「ｌｏａｄ」によって残りの入力値をファイルから読み込む。この時点で小計、合計は計算されて設定済となり、２４６で「合計」を入力することによって、現在の合計値が表示されて実行結果を取得できる。図２４（ｆ）の２４７を入力すると、図２のステップＳ２６が実行される。そして、計算途中の画面出力はないが、ステップＳ２２〜ステップＳ３０に示した処理が実行され、２４８の入力によって実行結果の合計値が表示される。２４９，２５０の入力は、制約条件に用いるデータの件数を追加設定している。そして、図２４（ｇ）の２５１の入力よって実行結果に合計値が表示され、図２４（ｈ）の２５２の入力よって、終了指令の発行を行っている。【００５１】  また、いくつかのデータ定義と制約式をまとめたものをクラス化概念における１クラスとして定義し、パラメータを与えて実例、すなわちインスタンス化させ、制約式と値をセットにするよう構成してもよい。これにより、設定される制約条件を複数に分割させることができるので、必要最小限の処理のみを実行させる場合等に好都合となる。このクラス化に関する概念を図２０に示す。このクラスは継承させることが可能であり、例えば、図２０に示す変数１、変数２、及び制約式１を有するクラスＡと、変数３を有するクラスＢとがあるとき、このクラスＡ及びクラスＢを継承し、さらに制約式２を継承した図２０のクラスを生成することができる。【００５２】  なお、本実施形態の制約条件解決装置１００の構成及び動作から分かるように、本発明では、例えば、すべての制約条件が制約違反をしないという評価式（評価条件）を設定していない。従来の宣言的プログラミングでは、制約条件の解を求める際に当該評価式に基づいて制約条件間で矛盾しないかを判断するように処理することが多い。本発明では、制約条件の設定時に、矛盾が生じないようにユーザが設定することを前提としているためである。したがって、制約条件解決装置１００は、最後に必ず解を求めることが可能であり、解が求まらないとき���ユーザによる制約条件の設定誤りである。
実行時に制約違反の存在に関する評価式は必要ないが、補助機能として用意することによってデバッグ時等の問題発生時の対処やミスの発見に役立つことは言うまでもない。【００５３】  本実施形態の制約条件解決装置１００によれば、対象問題に関する制約条件及び当該制約条件に用いられる変数の初期値または変動値が設定されると、その変数に関連した制約条件を抽出して各制約条件ごとの解を順次求めて、この求めた解を新たな変数値として各制約条件の解を求めることを繰り返すように構成したので、任意のデータ構造と、そのデータ構造によるデータ間を連結させる制約条件とによって対象問題を解決することができるようになる。
つまり、設定される制約条件は、従来の手続き型プログラミングのような対象問題を解決するためのアルゴリズムを記述することなくこのアルゴリズムに相当する指令をデータ構造に含ませた上で制約伝播の処理手順に沿って記載し、すべての制約条件が成立する最適解を求めずに制約条件１つずつの解を求めるように構成したので、解を求める道筋が明確になるとともに、格段に単純化された各制約条件（例えば、１元の方程式）を解けばよいことから最終的な解まで確実に到達することが可能で演算処理を格段に高速化させることができるようになる。【００５４】  また、問題の解決方法を制約条件において直接的に記述できるため、ユーザが従来のようなプログラミング言語の特殊な専門知識を必ずしも有している必要はなく、対象問題を容易に解くことができる。【００５５】（第２の実施形態）
前述した第１の実施形態では、制約条件解決装置１００において、制約条件入力手段１と、変数値設定手段２と、制約条件抽出手段３と、制約条件解算出手段４と、変数値再設定手段５とを含むように構成したが、本実施形態の制約条件解決装置２００では、第１の実施形態の制約条件解決装置１００における各構成手段１〜５に加えて、制約条件格納手段６及び変数値格納手段７をさらに備えているのが特徴である。
なお、本実施の形態の制約条件解決装置２００の構成と、第１の実施の形態における制約条件解決装置１００とで共通する構成部分については同一の符号を付して、詳細な説明を省略する。【００５６】  本実施形態の制約条件解決装置２００の全体構成を図３に示す。
制約条件格納手段６は、制約条件入力手段１により入力された制約条件を所定の記憶領域に格納する。また、変数値格納手段７は、変数値設定手段２により設定された変数値（初期値、変動値）を格納する。
また、本実施形態の制約条件抽出手段８は、第１の実施形態における制約条件抽出手段３の機能に加えて、新たに設定された制約条件または変動値を、前記記憶領域に格納された制約条件または値と比較して、両者が一致しない場合のみ制約条件の抽出を行う機能を有している。なお、制約条件抽出手段８は前記比較を常に行う必要はなく、制約条件格納手段６及び変数値格納手段７から制約条件及び変数値を抽出するようにしてもよいことは言うまでもない。【００５７】  図４（ａ）は、制約条件格納手段６が計算機の記憶領域（例えば、メモリ、磁気ディスクなど）へ制約条件を格納する形態例を示す図である。つまり、変数Ｘを３つの制約式（制約式１、制約式２、制約式３）で参照する制約条件があるとし、この変数Ｘに値２４６が設定されたときの記憶領域の表し方を示している。前述した会計計算問題の制約条件をこの形式によって表したときの一例を図６及び図５に示す。【００５８】
例えば、図４（ｂ）に示すように、数式（ｘ＝ｙ＋ｚ）は分割して格納される。ただし、このような表し方に限定されるものではない。制約条件の格納形態として、値と制約式とでメモリ領域を必ずしも分割する必要はなく、例えば制約式を構造として分割せずに文字列などで持ってもよい。
また、図５に示すようなデータ構造に限らず、例えば、以下に示すような記憶領域でも構わない。
・変数値は種類分けされ、ある値はメモリ上のみに記憶されるが、他の値はファイルやデータベースへ記憶されることで、記憶領域上の値を永久的にしてもよく、または時刻システム等において特別の意味を持たせるようにしてもよい。
・変数名をポインタで示す必要はなく、直接持ってもよい。
・変数値を必ずしも直接的に保持することはない。
・プログラムのコンパイル時等では変数を識別する必要はないので、変数名は必須ではない。
・制約条件に用いる制約式はリストでなくてもよい。
・制約式リストを持たず、図７に示すように、変数名から制約式を検索する構成であってもよい。ただし、図７に示すようなメモリとポインタ構造に限定するものではない。
その他、上記の変形による無数に存在するデータ型はすべて含むものとする。
【００５９】
本実施形態の制約条件解決装置２００によれば、対象問題に関する制約条件及び当該制約条件に用いられる変数の初期値または変動値を所定の記憶領域に一時的または永久的に保持するように構成したので、本実施形態の制約条件抽出手段８は、制約条件または変数値に変更が生じた場合のみ、変更された変数Ｓｍに関連する制約条件Ｑｍを解いてＱｍを満たすために変更すべき変数及びその値を求める処理を行うことが可能となる。
これにより、制約条件に変更があったとしても、複数の制約条件すべてについて最初から計算し直さなくても済む場合が生じ、計算時間の効率を図ることができるようになる。
【００６０】（第３の実施形態）
前述した第１の実施形態の制約条件解決装置１００では、制約条件入力手段１と、変数値設定手段２と、制約条件抽出手段３と、制約条件解算出手段４と、変数値再設定手段５とを含むように構成し、前述した第２の実施形態の制約条件解決装置２００では、さらに、制約条件格納手段６及び変数値格納手段７を備えている構成にしたが、本実施形態の制約条件解決装置３００では、図８に示すように、関数定義保持手段９及び関数定義実行手段１０を備えているのが特徴である。
第１の実施形態の制約条件解決装置１００と、第２の実施形態の制約条件解決装置２００のどちらであっても、関数定義保持手段９及び関数定義実行手段１０をさらに備える構成にすることができるが、説明を簡略化させるために制約条件解決装置１００に付加した構成で説明することとする。
なお、本実施の形態の制約条件解決装置３００の構成と、第１の実施の形態における制約条件解決装置１００とで共通する構成部分については同一の符号を付して、詳細な説明を省略する。【００６１】  プログラミング手法からみた本実施形態の制約条件解決装置３００の構成が有する役割は、第１の実施形態が、問題解決を完全な宣言的プログラミング手法で行っていたのに対し、第３の実施形態は、従来の手続き型プログラミング手法を融合している点にある。これは、宣言的プログラミングで解決することが困難な一部の問題については、手続き型プログラミング手法を利用するようにして、どんな対象問題であっても柔軟な問題解決を果たすためである。【００６２】
本実施形態の制約条件解決装置３００の全体構成を図８に示す。
関数定義保持手段９は、制約条件入力手段１及び変数値設定手段２によりユーザが従来の手続き型プログラミングで記述する手続き、及び変数値を保持する。関数定義保持手段９は、制約条件抽出手段３と相互にデータの入出力を行うことが可能であるように接続されている。
なお、本実施形態の制約条件入力手段１のような、必ずしも制約条件以外に手続き型の記述を許可する構成にする必要はない。例えば、手続き型の記述専用の入力手段を別途備えるような構成にしてもよい。変数値設定手段２についても同様で、手続き型で記述された手続き専用の変数値設定手段を備えるようにしてもよい。
【００６３】  関数定義実行手段１０は、関数定義保持手段９で保持された手続きを計算機に実際に実行させるものである。また、関数定義実行手段１０は、制約条件解算出手段４と相互にデータの入出力を行うことが可能であるように接続されている。【００６４】  本実施形態の制約条件解決装置３００の処理を具体例で説明する。いま、制約条件として記述された制約式の中に、ｙ＝ｓｉｎ（ｘ）、またはｙ＝逆関数のない関数（ｘ）等が含まれている場合を想定する。
この場合、図２に示すステップＳ２９において、変数ｘの値を求めるためにｘ＝ｓｉｎ−１（ｙ）という式変形をして処理しようとしたところ、逆関数ｓｉｎ−１の値領域の関係でｘ値を求めることが不可能なときがある。また、ｙ＝逆関数のない関数ｆ（ｘ）では、ｙ値からｘ値を求めることができない。このようなときに、従来の手続き型プログラミングによるユーザ関数を自由に取り入れて対処するようにする。【００６５】  例えば、制約式を解くにあたり、解決方法を複数の中から選択可能に記述することを許可するようにしておく。制約条件をａ＝ｆ（ｂ）とすれば、変数ｂの値を求めるために、｛ａ＝ｆ（ｂ），ｂ＝ｆ＿ｒｅｖ（ａ）｝を用意し、どちらかが適用できれば制約式を解くことができるようにしておく。
また、ｙ＝ｆ（ｌ，ｍ）という制約式の変数ｌ，ｍの値が決まっていない場合、或いはｙ＞ｘのような不等式の場合も、当該制約式を単純に解くことができない。不等式ｙ＞ｘの場合で、ｘの値がｎとなったとき、ｙはｎより大きいという情報のみが得られるだけで、変数ｙの値は最終的な解が未確定ともいえる。このようなケースでは制約条件の設定エラーとして処理してしまう他に、ｙ＞ｎという情報をｙに関係する制約式にそのまま代入させて処理を続行させるようにしてもよい。１つの方程式だけに注目すると解けないｚ＝ｘ＋ｙについても同様で、複数の式と複数の値との間で連立方程式を扱うように許可することで解決することもできる。【００６６】
これにより、他の制約式の条件との関連で変数ｙの値を限定できたり、より絞り込むことが可能になったり、或いはｙ＞ｎがそのまま解として成立することもあるためである。このように、変数値として確定した値でなく不等式などをそのまま扱い、別の制約式で解決可能なときに可能な限り解決するようにする。つまり、このときの制約条件抽出手段３は、図９に示されるような関係にある解決方法を実行する。図９における制約式のｘ値が変更されると、ｘへ代入する形式でないすべての式（解決方法１〜解決方法３）を実行していくというように、制約式の解過程に柔軟性をもたせ、従来の手続き型プログラミング手法と同等、またはそれ以上の解決能力を持たせることが可能となる。
【００６７】  また、逆関数等の問題で制約式として表すことが困難な場合にかぎらず、制約式として通常に表すことができる式についても図９に示すような解決方法の形式に変形して保持するように構成すれば、処理実行時の速度を向上させることも期待できる。【００６８】  このように、本実施形態の制約条件解決装置３００によれば、関数定義保持手段９及び関数定義実行手段１０を含むように構成したので、制約条件と従来のプログラミングで定義していた関数等とが融合し、対象問題の性質または特長に応じて制約条件としての解決方法、及び従来のプログラミング手法を用いた解決方法を、ユーザ側が自由に切替えながら設定することが可能となる。これにより、第１の実施形態及び第２の実施形態の制約条件解決装置１００，２００では解決できない逆演算処理などを包含する制約条件の記述が格段に容易になる。【００６９】（第４の実施形態）
前述した第１の実施形態〜第３の実施形態の制約条件解決装置１００，２００，３００の各構成手段に加え、本実施形態の制約条件解決装置４００は、データベースやシステムリソース等からの情報を適宜利用して変数値を設定できることを特徴としている。
図１０に本実施形態の制約条件解決装置４００の全体構成図を示す。
本実施形態の説明を簡略化させるために、第２の実施形態の制約条件解決装置２００に付加した構成の制約条件解決装置４００により説明することとする。他の実施形態の制約条件解決装置において、データベースやシステムリソース等からの情報を利用できることは言うまでもない。
なお、本実施の形態の制約条件解決装置４００の構成と、第２の実施の形態における制約条件解決装置２００とで共通する構成部分については同一の符号を付して、詳細な説明を省略する。【００７０】
図１０に示すように、本実施形態の制約条件解決装置４００の構成によれば、制約条件内の変数の一部または全部が、前記データベース１１やシステムリソース１２内に記憶されている値や、時刻等の別の事象と連携されるシステム内の変数と連結することが可能となり、本制約条件解決装置４００外の変数と制約条件の変数との整合を図った変数の管理を容易に行うことができるようになる。
【００７１】  次に、制約条件の内容としてさらに複雑なデータ構造の変数を扱うことが可能な例をいくつか示す。以下の具体例は、前記第１の実施形態〜第４の実施形態における制約条件解決装置１００，２００，３００，４００すべてにおいて実行可能である。【００７２】
（変数に複数の値を定義した制約条件）
通常、変数へ値を代入する制約条件は、例えば、ｘ＝１０のように記述するが、ここでは、１つの変数ｘに複数個の値を代入することを定義する。具体的には例えば、
ｘ＝｛１０、１１、１２｝；
という記述を認める。この場合、変数同士の加減乗除の演算は、加算を例にすればｘ＋ｙは、各変数ｘ，ｙのそれぞれの要素について＋演算を行うものとする。
【００７３】
（演算子が定義された配列構造の変数による制約条件）
いま、１次元配列ｖｅｃを考える。この１次元配列ｖｅｃを、ｖｅｃ＝｛５０，２００，３００｝とし、ｉ番目（０≦ｉ≦文字列長−１）の要素に対するアクセスをｖｅｃ［ｉ］で表すこととする。１次元配列ｖｅｃの各要素は、ｖｅｃ［０］＝５０、ｖｅｃ［１］＝２００、ｖｅｃ［２］＝３００である。
ここで、１次元配列ｖｅｃ１，ｖｅｃ２に対する演算子を次のように定義する。
ｖｅｃ１＋ｖｅｃ２  …各々の１次元配列の要素を全て加算した配列、
ｖｅｃ１−ｖｅｃ２  …各々の１次元配列の要素を全て減算した配列、
ｖｅｃ１＊ｖｅｃ２  …各々の１次元配列の要素を全て乗算した配列、
ｖｅｃ１／ｖｅｃ２  …各々の１次元配列の要素を全て除算した配列、
ｖｅｃ１＝ｖｅｃ２  …各々の１次元配列の要素が全て同じかどうかを比較するか、もしくは配列内の各要素を代入した配列、
ｖｅｃ１＆ｖｅｃ２  …各々の１次元配列の要素を全て連結した配列。
１次元配列に対する演算子をこのように定義することにより、前記第１の実施形態〜第４の実施形態における制約式の一種として問題なく扱うことが可能になる。
配列構造の制約条件にアクセスするには、限定するものではないが、例えば図２１に示すようなオペレータを用意すればよい。このオペレータには任意の関数を使用することが可能となっている。
【００７４】  また、前記１次元配列ｖｅｃの要素に対して柔軟性のあるアクセスを実現するために、ｖｅｃ［ｉ］において範囲指定が可能なようにする。具体的には、ｖｅｃ［ｎ．．ｍ，ｌ．．ｋ，ｉ．．ｊ］を、次元配列のｎ〜ｍ番目、ｌ〜ｋ番目、及びｉ〜ｊ番目の要素を取り出して並べた配列を表しているとすると、
ｖｅｃ１［０．．３］＝ｖｅｃ２［０．．１］＆ｖｅｃ２［４．．５］＋ｖｅｃ３［０．．３］というような演算が可能となり、１次元配列を制約式（制約条件）として扱うことができる。【００７５】
例えば、前記１次元配列（ここでは、ｓｔｒとする）の各配列要素に文字を格納すればｓｔｒは文字列となる。文字列ｓｔｒ＝”Ｈｅｌｌｏ  Ｗｏｒｌｄ  ！”に対して、各ｓｔｒ［ｉ］に任意の文字を代入したり、文字列１＝”Ｈｅｌｌｏ  ”、文字列２＝”Ｗｏｒｌｄ  ！”とすれば、文字列ｓｔｒ＝文字列１＆文字列２で表される制約式を扱うことが可能となる。さらに、文字列のみの正規表現によるパターンマッチングや文字列置換を導入するなどによって、制約式をさらに柔軟に記述することが可能となる。
【００７６】  これを応用して、例えば、変数値の変更に従って出力が変化するＷｅｂによるＨＴＭＬ（ｈｙｐｅｒｔｅｘｔ  ｍａｒｋｕｐ  ｌａｎｇｕａｇｅ）出力を以下のように記述することができる。
日付け＝”２００３／０１／０１”；
名前＝”特許  太郎”；
内容＝”長文文章”；
ＨＴＭＬデータ＝”＜ＨＴＭＬ＞＜ＢＯＤＹ＞”＆日付［０．．３］＆”年”＆日付［５．．６］＆”月”＆日付［８．．９］＆”日”＆”名前：”＆名前＆”内容：”＆内容＆”＜／ＢＯＤＹ＞＜／ＨＴＭＬ＞”；【００７７】（デフォルト変換規則を備えた制約条件）
任意のデータ変換についての変換規則を用意し、特にデフォルトで指定可能とする。
特に数値から文字列へ変換する場合、参照毎に変換関数を毎回用いる方法があるが、データ変換規則のデフォルトを用意することにより、効率的な記述が可能となる。
一例として、次のような規則を用意する。
・変換規則は必ず右詰めとする
・Ｓは符号を表し数が負の時のみ−を、それ以外の時は空白とする
・Ｘｎはｎ桁以下の数を表す
・Ｙｎはｎ桁固定の数を表す
・Ｚｎはｎ桁固定のゼロサプレスを表す
この時、例えば変数定義時に、
ｆｌｏａｔ（″ＳＸ９．Ｙ３″）Ｖａｌ１；
とすれば、符号付、仮数部９桁以下、少数点、少数部３桁固定で右詰めされた全１４文字の文字列としてＶａｌ１を参照できる。
また、ｕｎｓｉｇｎｅｄ  ｉｎｔ（″Ｚ８″）Ｖａｌ２；
とすれば、ｖａｌ２は符号無、ゼロサプレス付８桁の全８文字の文字列としてｖａｌ２を参照できる。
もちろん、値参照時に直接ｖａｌ２（″Ｚ１０″）等として記述することでデフォルト規則だけではなく適用時に別の規則を適用できることとする。
このようなデフォルト変換規則を備えた制約条件による変換規則を定義することで、事務処理アプリケーション等における制約式を簡単に記述することができるようになる。
他のデータ構造にも同様に応用できたり、変換規則のフォーマットとして以上のものは１例であり多種のものが存在することは言うまでもない。【００７８】  （優先順位付き制約条件）
制約条件に重みを付加する場合の記述例を以下に示す。
｛条件式｝［：優先順位］；
ｏｒ
｛条件式｝［：優先順位］→｛条件式が不成立時の処理｝；
ここで、複数の制約式条件が合致した場合、優先順位の値に従って実行すべき制約式が選択されるようにする。また、同じ優先順位の値が複数ある場合はすべて実行されるようにする。このような優先順位付き制約式を定義することで、優先順位の最も小さいまたは大きい制約式のみを実行させたり、或いは制約式の実行順序を指定させたりする場合に有効になる。【００７９】  （構造体による制約条件）
構造体（抽象的なデータ構造）は、複数のデータ型をまとめて扱うことが可能である。前述したＷｅｂ出力のデータをこの構造体で表現しようとすると、
ｓｔｒｕｃｔ  構造体名｛
ｄａｔｅ  日付；
ｎａｍｅ  名前；
ｓｔｒｉｎｇ  内容；
｝掲示板データ［］；
のように表すことができる。実際のＷｅｂシステムでは、前記構造体のデータはデータベースやファイル上に存在することになり、前記構造体の場合、配列番号５に関する”内容”に対するアクセスは、例えば、”掲示板データ［５］．内容”により可能となる。
なお、本構造体のデータのアクセスにおいて、メンバ（日付け、名前、内容、及びＨＴＭＬデータのこと）に対する文字列マッチングの演算子などを定義することによって、検索の処理を制約条件として記述することができるようになる。【００８０】  （組み込み関数や追加演算子、規則追加による制約条件）
さらに前記の各種データ構造を利用して少し実用的な例題を示した図１２（ａ）及び図１２（ｂ）を実現するために、いくつかの規則を追加する。なお、図１２（ａ）及び図１２（ｂ）は１つの図で示すところ、便宜上、別図として示している。
組み込み関数や演算子、規則として、例えば以下のものを用意する。
・ｖｓｉｚｅ（ａｒｇ）  …引数ａｒｇで与えられた配列の大きさを求める組み込み関数。
・ｉｎｔｔｏｓｔｒ（ａｒｇ）  …整数を文字列へ変換する組み込み関数。
・ｓｔｒｔｒｕｎｃ（ａｒｇ１，ａｒｇ２）  …ａｒｇ１の文字列を複写するが、ａｒｇ２で指定された文字列長より長い場合、その分の文字を切り捨て。
・配列範囲指定演算子［＊］  …配列すべての要素を意味する。
・｛｝で囲まれたいくつかの制約式をブロックとしてまとめて処理する。
・［＄ｉ］  …今までに登場した制約式のインデックス［ｉ］と同等だが、ブロックでのみまとまった制約条件の中ですべて同じ値を持つ。ここでは通常の変数との識別のためにｉではなく＄ｉとして記述している。
以上によって、たとえば以下のような記述が可能である。
・ｏｕｔｐｕｔ＿ｂｌｏｃｋ［＊］．ｏｕｔｐｕｔ＿ｈｔｍｌ  …配列内のすべてのｏｕｔｐｕｔ＿ｈｔｍｌ（図１２（ａ）参照）を並べた複数要素値列を意味し、文字列との比較、代入演算が行われる時は、すべての要素を連結した一つの文字列として扱われる、
・ｖｓｉｚｅ（ｏｕｔｐｕｔ＿ｂｌｏｃｋ）＝ｌｉｓｔ＿ｃｏｕｎｔ  …配列数、すなわち配列サイズと変数との関係を示す制約式である。但し、ｖｓｉｚｅ（）で得られた値の参照は通常の数値であるが、変更は配列サイズの変更を意味する必要があるため、処理系の内部で値の変更が抽象化されたサイズ変更のための関数呼び出しを意味するように定義付けるか、オブジェクトによるメソッド呼び出し処理等の抽象化した処理が必要である。【００８１】
以上のような各種データ構造の制約条件を含む問題へ入力データを与えるためには、該当の変数をユーザが直接変更したり、図１２（ａ）に示した手続き型関数のbbs＿additem（）を呼び出す等の処理を行うことになる。また図１２（ａ）,（ｂ）の例題では出力については前記output＿htmlを参照する。以上の処理によって、Ｗｅｂサービスを実現することができるようになる。なお、出力を必ずしもＨＴＭＬフォーマットに限定する必要はなく、任意のクライアント／サーバシステムにおけるサーバ側の入出力サービスを同様の方法で実現することも可能である。
【００８２】  なお、これまで１次元配列ｖｅｃを示して説明したが、２次元配列等の多次元配列への拡張はもちろんのこと、配列長が異なる配列同士の演算やこのような配列と数値との演算に関する定義が同様に行えることは言うまでもない。
また、前述したように、制約条件の内容としてさらに複雑なデータ構造の変数を扱うことが可能な例を示したが、これらデータ構造に完全に一致する必要はなく、当業者であればこれらから類推できる変形例が含まれることは言うまでもない。【００８３】
以上説明したように、制約条件を単なる数値でなく各種のデータ構造をも扱えるようにしたので、現在格納されたデータとＨＴＭＬ出力の関係が制約条件（制約式）によって記述可能となり、Ｗｅｂアプリケーションにおけるサーバ側のプログラムを制約条件だけで単純に記述することができるようになる。このＷｅｂサーバと組合せてデータ入力、表示を行うシステムの概念図を示したのが図１１であり、このときの関数定義保持手段及び制約条件格納手段に格納するデータや、制約条件の一例を示したのが図１２（ａ）,（ｂ）である。
【００８４】  また、前述したようなＷｅｂにおけるＨＴＭＬに限らず、図１３に示すような一般のウィンドウインタフェースでは各項目を変数にマッピングするように構成することで、データとユーザインタフェースとの関係を制約条件で記述することが可能となり、一般的なユーザインタフェースを記述しやすく、且つ理解することが容易となる。これにより、従来のプログラミング方式と比較して高い生産性を実現することができる。【００８５】＜本発明の他の適用例：アプリケーションプログラム構築、トランザクション処理＞
次に、ＷＥＢ上の入力インタフェースを用いて任意のアプリケーションプログラムを構築する問題、または任意のデータが蓄積されたデータベースを検索する際のトランザクション処理問題に本発明が適用可能であることを説明する。
前記第１の実施形態〜第４の実施形態における制約条件解決装置において、制約条件により解決していく処理手順及び処理内容を、履歴情報（更新履歴）として持つことにより、アプリケーション上のユーザインタフェースの概念の１つにあるＵＮＤＯ機能、或いはデータベースのトランザクションを実現することが可能となる。【００８６】  このＵＮＤＯ機能、或いはデータベースのトランザクション処理を実現できるようにすることで、データの更新から始まってデータ変更に伴う制約解を求める一連の動作が行われなかったものとすることが容易に行える。これにより、制約条件のデータ値を一部変更して入力データに含まれる誤りを発見するという入力データの確認や、そのキャンセル時における元のデータ値に復帰させるための処理を確実かつ迅速に行うことができるようになる。【００８７】  次に、ＧＵＩ環境における基本的な画面構成要素であるウィンドウを用いたウィンドウシステムまたはマルチウィンドウシステムに本発明が適用可能であることを示す。ここでは、図１４に示すようなウィンドウシステムを一例に説明する。なお、図１４では３つのウィンドウを示しているが、任意個のウィンドウを扱えることは言うまでもない。【００８８】  図１５は、ウィンドウシステムを実現するクライアント／サーバシステムにおけるクライアント側の構成を概念的に示す図である。サーバ側のシステム構成については図１、３、８、１０に示すものと同様であるので省略する。
図１５に示すように、ＧＵＩクライアントはＧＵＩ処理部とＧＵＩ制御部を有し、ＧＵＩ制御部は図１６に示すような各パーツの動作を制御する。
ここでのＧＵＩ制御部の中身は、図１、３、８、１０と同様の構成を持ち、各パーツの状態変更は、クライアント内の図１、３、８、１０の入出力Ｉ／Ｆに対するＩ／Ｆ制御部に対して行われる。制約条件として、各パーツ間の連携規則、クライアントで処理するべき入力データの整合性チェック、入力補助、サーバ側へ渡すべきデータへの加工規則などが記述され、処理される。
ＧＵＩ制御部で加工されて処理されたデータは、伝達用の変数を介してサーバへと伝えられる。
もちろん、クライアントのＧＵＩ処理部分とサーバの制約処理系をまとめて１台で処理するなど、システム構成が柔軟に変形して使用できることは言うまでもない。
なお、本発明の特徴である変数の値変更に応じた制約条件の逐次解法の機能は、クライアント／サーバシステムの全体として有する他、前記ＧＵＩ制御部においても有している。また、クライアント／サーバ間のデータ転送は、独自形式でもよいが、ＸＭＬを使用する等、標準化したデータ形式を用いることで従来手法と互換性のあるオープンなプロトコルを実現することが可能である。【００８９】  このように、ＧＵＩ側では、ＧＵＩの動作制御、伝達するデータの整合性の確認、入力補助、データの状態に応じたＧＵＩの状態変更、及びサーバ側への通知処理などを制約条件の記述に基づいて行うことができる。【００９０】  次に、ウィンドウの動作について詳しく説明する。各ウィンドウ内の構築は、前述した各種のデータ構造の扱いを許可する制約条件の設定や、ＵＮＤＯ機能或いはデータベースのトランザクション処理を実現できるユーザインタフェースによって可能であるが、このウィンドウ自体の動作は次のようにして記述する。【００９１】  ウィンドウの情報として、例えば次の構造体を定義する。
ｓｔｒｕｃｔ｛
位置  ｘ，ｙ；
サイズ  ｘ，ｙ；
表示中フラグ；
｝ウィンドウ情報［］；
なお、ウィンドウ情報［０］…アプリケーション１、
ウィンドウ情報［１］…アプリケーション２、
ウィンドウ情報［２］…アプリケーション３を表すものとする。
これらの変数値の参照更新は、図１０のシステムリソース１２と同様の扱いとし、実際のＧＵＩシステムのウィンドウと連動させるものとする。【００９２】
アプリケーションを実行する画面上に表示されているウィンドウの動作（表示／非表示、移動、サイズ変更）を制約条件で記述しようとする場合の一例を次に示す。
（ａ）ウィンドウｎの表示／非表示
画面上にウィンドウを開く（表示）…ウィンドウ情報［ｎ］．表示中フラグ＝true、
画面上のウィンドウを閉じる（非表示）…ウィンドウ情報［ｎ］．表示中フラグ＝false、
また、画面上にウィンドウを閉じるための「closeボタン」があるときは、例えば、ウィンドウ情報［ｎ］．表示中フラグ＝！closeボタンの状態（！はnot演算子）とすればよい。
（ｂ）ウィンドウｎの移動
ウィンドウ情報［ｎ］．位置．ｘ＝＜移動したいｘサイズ＞；
ウィンドウ情報［ｎ］．位置．ｙ＝＜移動したいｙサイズ＞；
（ｃ）ウィンドウのサイズ変更
ウィンドウ情報［ｎ］．サイズ．ｘ＝＜変更したいｘサイズ＞；
ウィンドウ情報［ｎ］．サイズ．ｙ＝＜変更したいｙサイズ＞；
【００９３】  その他、アプリケーション１の右にアプリケーション２を隣接するようにするには、
ウィンドウ情報［１］．位置．ｘ＝ウィンドウ情報［０］．位置．ｘ＋ウィンドウ情報［ｎ］．サイズ．ｘ；
ウィンドウ情報［１］．位置．ｙ＝ウィンドウ情報［０］．位置．ｙ；とすればよい。
また、ウィンドウのサイズを固定にするには、変数に変更可能／不可能の属性を用意した上で、ウィンドウ情報［ｎ］．サイズ．ｘ、ウィンドウ情報［ｎ］．サイズ．ｙ、を変更不可能にすればよい。【００９４】  このように、ＧＵＩ環境におけるウィンドウシステムまたはマルチウィンドウシステムにおいて、従来のプログラミング手法ではウィンドウの動作及びウィンドウ内のアプリケーション動作をイベントが発生したらそのイベント状況に依存する関連動作を逐一記述しなければならなかったのに対し、本発明による動作制御によれば単純明快な制約条件に基づいてアプリケーションの複雑な動きを簡潔且つ容易に記述することができるようになる。【００９５】  なお、ウィンドウシステムにおける動作を制約条件の記述によって制御可能なことをＧＵＩ環境で前述したが、データを画面上に出力する場合に用いるだけでなく、ウィンドウを用いて処理した内容を任意の媒体（例えば、紙）に出力する出力システム（例えば、帳票印刷システム）を実現する際にも本発明を適用することができることは本発明の技術分野における当業者であれば容易に想到できることは言うまでもない。
また、前述した説明では、クライアント／サーバシステムにおける具体例を示したが、必ずしもクライアント／サーバシステムである必要はなく、クライアントとサーバとをそれぞれ別個のシステムとして構築し、クライアントのみまたはサーバのみに前述した処理が行えるように構成してもよい。【００９６】＜本発明の他の適用例：並列化処理と構築された計算機システム＞
また、本発明は、手続型プログラミングで面倒な問題である並列化処理の問題に適用することが可能である。並列処理においては、大きく分けて２種類の動作が考えられる。すなわち、いくつかのＣＰＵがステップＳ２３〜ステップＳ３０のアルゴリズムを実行する方法と、データフローマシンのようにアーキテクチャで変数と関係式を構築してしまう方法である。【００９７】  前者の場合、通常の手続型プログラミング手法で並列処理を行おうとすれば、アルゴリズムを構築する段階で、ユーザはＣＰＵの並列動作を意識しながらプログラミングの処理手順を分割して記述しなければならない。これに対して本発明を用いた並列化処理の場合は、図２のアルゴリズム中にあるステップＳ２２による変数値の変更から開始されるステップＳ２３〜ステップＳ３０の処理を並列に動作させるだけで、ユーザは直接並列処理を意識することなく並列処理を実現できる。【００９８】  具体的には、前記第１の実施形態〜第４の実施形態における制約条件解決装置において、ある処理に対するステップＳ２３〜ステップＳ３０の実行中にも、別の処理に関してのステップＳ２２による変数値の変更による一連の動作を実行させることを行っている。
実際上、従来の手続き型プログラミング手法における並列アルゴリズムの実装と同様に、この並列処理の実行中においては各変数間で排他制御や同期制御を実現する必要があるが、従来の手続き型プログラミングでの手法をそのまま適用することができる。【００９９】  後者のアーキテクチャで変数と関係式を構築する場合、変数間の関係式は、例えば並列計算機上に物理的に実現した時の通信路となる。この並列計算機上では、並列プロセッサが複雑な通信路によって結合されており、通信コストが経路によって異なる。この通信コストを優先度で表わすことによって、データ経路を自動的に選択することが可能である。優先順位については、制約条件の一例として挙げた（優先順位付き制約条件）を用いることができる。このような並列処理と同様の方法で、一般に構築されたシステム全体に本発明を適用することが可能である。
なお、ここでいうシステムとは、複数の特性の異なる計算機や用途別専用機と、それらを結合するネットワークから構成される複合物を意味しており、いわゆる一般の企業システムや社会システムを指す。【０１００】  つまり、本発明をシステム全体へ適用する場合、概念的には、前記データフローマシンでの並列処理実現方法と非常に似たものとなり、本発明によって構成される計算機は、計算機間のインタフェースとなる変数を介して別の計算機のインタフェースである変数と結ばれる。変数間の関係式が通信路であり通信コストが優先度であり、したがって本発明によって前記システム全体を設計し構築することができる。【０１０１】＜本発明の他の適用例：既存プログラミング言語との融合＞
これまで説明してきたように、本発明は任意の制約条件から構成される問題を、外部（ユーザ等）からの指示（イベント）を契機に変数の値を変更して制約伝搬によって解決するイベント駆動型の計算実行原理を扱っている。前述したように関数定義保持手段や関数定義実行手段において既存の手続型プログラミング言語を利用する等から明らかなように、図１８にも示したが既存のプログラミング言語との組み合わせ可能なことを前提としている。そこで、本発明を既存プログラミング言語へ融合することが可能であることをさらに詳述する。【０１０２】  なお、ここまで説明のために、プログラミング言語を分類した場合に、１つは手続型プログラミング、別の１つは宣言的プログラミングであるとして大別してきたが、実際にはもっと細かなプログラミング言語の分類が存在する。すなわち、宣言的プログラミング言語に対する非宣言的プログラミング言語には、手続型プログラミング言語と並ぶプログラミング言語としての関数型プログラミング言語が含まれている。以下、本発明と関数型プログラミング言語との融合について扱う。【０１０３】  （Ａ）関数型プログラミング言語との融合
ここでは、関数型プログラミング言語として最も歴史があり代表と言えるＬＩＳＰ言語（Ｃｏｍｍｏｎ  ＬＩＳＰ）との自然な融合方法について述べる。いま、２つの変数ａ，ｂの初期値、及び制約条件として、
ａ＝｛１１，１２，１３｝
ｂ＝｛１，２，３｝
ａ［＄ｉ］＝ｂ［＄ｉ］＋１０
を定義するとする。ａ，ｂの値は共に３つの要素を持つ配列である。また、本発明の実施例において制約式を定義する関数ｄｅｆｃｏｎｓｔｒａｉｎｔを新たに定義し、変数への代入をシンボルへのバインドに対応させるとすれば、ＬＩＳＰ言語では次のように記述できるだろう。
（ｓｅｔ’ａ  ＃（１１  １２  １３））
（ｓｅｔ’ｂ  ＃（１  ２  ３））
（ｄｅｆｃｏｎｓｔｒａｉｎｔ’（＝（ａｒｅｆ  ａ  ＄ｉ）（＋（ａｒｅｆ  ｂ  ＄ｉ）１０））    …（式１８）【０１０４】  ここで、関数ｄｅｆｃｏｎｓｔｒａｉｎｔは、図９のデータ構造を実現するために引数からシンボル（変数）ａとｂに関する解決式を作成し、
（ｄｅｆｃｏｎｓｔｒａｉｎｔ２’（＝（ａｒｅｆ  ａ  ＄ｉ）（＋（ａｒｅｆ  ｂ  ＄ｉ）１０））
’（ｓｅｔｆ（ａｒｅｆ  ａ  ＄ｉ）（＋（ａｒｅｆ  ｂ  ＄ｉ）１０））
’（ｓｅｔｆ（ａｒｅｆ  ｂ  ＄ｉ）（−（ａｒｅｆ  ａ  ＄ｉ）１０）））
を実行して、関数ｄｅｆｃｏｎｓｔｒａｉｎｔ２が図９のデータ構造を維持する。式のデータ構造としては図６等のデータ構造でよいのだが、ＬＩＳＰではＬＩＳＰ自体の機能のみで構造を自然に記述することができるので、ここではこのＬＩＳＰの特徴を生かして上記のような式を記述している。【０１０５】  Ｃ言語のポインタ等についても同様なことが言えるのだが、ＬＩＳＰ言語においては各データが共有されている可能性があり、変数とデータとの関係が１対１であるとは限らない。このため、あるデータを変更する時にそれが特定のシンボルに関係しているかどうかは変数へ値を代入する時にはわからないのが通常である。したがって、このような変数とデータとの関係構造は、本発明の制約解消を実現する際には問題となるので、これを説明する。【０１０６】  いま、シンボルｂと同じデータを指すシンボルｃを加えて、シンボルａ，ｂ，ｃを中心とした通常のＬＩＳＰ言語の内部データ構造を極単純化した一例を図２２に示す。ＬＩＳＰ言語では、すべてのシンボルはパッケージに記録され、名前空間別に保存されているのでここではパッケージから記述している。また、標準の名前空間名は「ｕｓｅｒ」であるため、シンボルａ，ｂ，ｃは「ｕｓｅｒ」に登録されるが、この例ではシンボルｂは別のパッケージにも登録されている。【０１０７】
ＬＩＳＰ言語で、b[1]=12を実行する場合、
(setf (aref b 1) 12)
を実行するが、値の代入を実行する関数setfは上記の関数defconstraint2で定義された制約式とマッチングさせる必要がある。一方、関数setfに渡されるデータは、通常のＬＩＳＰでは図２２中の（＊）で示すポインタであり、マッチングさせるべき情報は存在しない。そこでこのような単純な例の場合、関数評価時に評価結果だけではなく、評価した式の情報を関数setfの実行時まで持ちまわる方法が考えられる。しかし、実際には非常に複雑な式になるため持ち続けるデータが巨大になることや、(setf (aref c 1) 12)でb[1]が変更された場合に対応が難しくなる。
【０１０８】  これを解決するためには、ＬＩＳＰ言語の基本データ構造をすべて双方向に辿れるように構成すればよい。そのデータ構造を一例として図に示すと、図２３のようになる。図２３中の（＊）で示した関数ａｒｅｆによる配列参照は、逆方向へ辿れるように配列内のポインタだけではなく、配列そのものの情報も持つ。配列情報を含むすべてのデータは、バインドされているシンボルの情報を追えるように各種情報を保存する。【０１０９】  また、実際にはシンボルまでのみならず登録されたパッケージ情報まで辿らなければならず、したがって制約式のシンボルはパッケージを考慮する必要がある。（＊）からｂ［１］（パッケージを含めてｕｓｅｒ：ｂ［１］）を辿る時の道順を図２３では太線の矢印で示している。【０１１０】
なお、Common LISPのシンボルにはもともとホームパッケージの情報を持つが、１つのシンボルが複数のパッケージに保存されることがある。このため登録されたすべてのパッケージを追うことができる新たなデータ構造の追加が必要となるが、このようにすれば、setfの実行時に制約式のマッチングを検査することができるようになる。以上説明したように、本発明をＬＩＳＰ言語を代表とする関数型プログラミング言語と完全に融合させて自然に扱うことは可能である。
【０１１１】
（Ｂ）  （Ａ）方式の問題点と解決方法
前記（Ａ）の関数型プログラミング言語との融合によって、ＬＩＳＰ言語上で本発明を適用することができるようになり、関数型プログラミング言語上への実装としては理想的になるが、例えばsetf等の代入操作が実行される度に制約式のマッチングが必要となることから原理上、実行効率が悪くなる。特に、代入時の逆方向の制約式とのマッチング（逆方向のマッチング）に際しては、かなり上の方まで遡らなければ、該当する制約式の定義が存在するかどうかわからない。例えばポインタの時点でわかるのは[1]等のインデックス情報だけであるが、単純な制約式でさえa[x]、b[x]のような構造をしているため、インデックス情報だけではマッチさせるべき制約条件が存在するかどうかを判断できるのは限定された特殊条件の時だけとなる。
【０１１２】  これに対して、シンボル名（変数名）から辿るマッチングの場合、多くの場合で制約条件が存在するかどうかが最初からわかっており、変数（シンボル）そのものにそれらの情報を付加させることによって処理の高速化が可能である。
また、実際の制約式はａ［ｘ］等の単純な例が登場することは少なく、逆方向とのマッチングは常に相当に複雑な式をかなり上方、おそらくは完全に辿る必要がある。これを実際のＣｏｍｍｏｎ  ＬＩＳＰの複雑なパッケージ機構上に実装することを考えると、実装は実に複雑となり、実行時間については様々な方法によって多少の改善は期待できることを考慮しても、変数から開始する制約式のマッチングに比べて明らかに実行効率は非現実的なまでに悪くなってしまう。【０１１３】  そこで、現実的解決方法として、完全な融合をあきらめて、制約条件を使用する場合は、専用の式処理機構を用意してその中では必ず変数（シンボル）からしか値を参照できない制限を加えれば前述した問題を防ぐことができる。例えば、文字列データを「″」で括って表わしているように、式データをデータ型の一つとして抽象化して例えば「？」で括って表現し、専用の式処理機構を実行する関数ｐｅｖａｌを定義し、代入式を関数ｐｅｖａｌ内で実行するならば、前記式（１８）は、
（ｐｅｖａｌ’？ａ＝｛１１，１２，１３｝？）
（ｐｅｖａｌ’？ｂ＝｛１，２，３｝？）
（ｄｅｆｃｏｎｓｔｒａｉｎ’？ａ［＄ｉ］＝ｂ［＄ｉ］＋１０？）
と記述できる。そして、ｂ［１］＝１２を実行する場合は、（ｐｅｖａｌ’？ｂ［１］＝１２？）を実行すればよい。【０１１４】  この場合、必ず式処理の中では変数（記号）からの参照しか行えないことにするため、逆方向のマッチングは必要ないので、前述した（Ａ）で述べたＬＩＳＰ言語上での実装の問題は発生せず、さらにＬＩＳＰ言語の他の機能にはまったく影響を与えないため実行効率の問題が解決する。【０１１５】  ただし、プログラミング言語としては、言うまでもなくとても不自然である。そこで、プログラミング言語の文法そのものを新しく定義して、代入操作時に専用の式処理機構を自然に使わせるように解釈するパーサー（構文解析器）を用意すればよい。これは、入力時に文法を構文解析してＬＩＳＰである内部表現に置き換えるので、本来のＬＩＳＰ言語とは違うものであるが、ＬＩＳＰ言語の良いところと本方式を組み合わせた実行効率が著しく低下しない能力を持つプログラミング言語の実現が可能となる。【０１１６】
なお、ここでは、式評価は常に関数pevalの中で行うことを基本とした、最もメジャーなＣ言語風の文法を持つプログラミング言語の基本要素を示すことによって、関数pevalを自然に使わせる方法について述べる。変換後を見ればわかるように、Ｃ言語風の文法を持ちＣ言語同様の記述ができるとはいえ、本質的にはＬＩＳＰであり、ＬＩＳＰの柔軟な記述能力を持っているという優位性がある。さらに、純粋なＬＩＳＰプログラムとも完全に混在させて実行することができる。
【０１１７】  本システムの基本単位と言える関数を含む式の解釈実行は次のように翻訳する。なお、ここでは型宣言に関しては本質的に関係ないため省略している。
入力：
ａ［１］＝ｆｕｎｃ１（１００）；
実行関数：
（ｐｅｖａｌ’？ａ［１］＝ｆｕｎｃ１（１００）？）【０１１８】  Ｃ言語の基本構造である局所変数を持つブロック構造は次のように解釈する。
入力：
｛
ｉｎｔ  ｘ，ｙ；
ｘ＝１０；
ｙ＝２０；
｝
実行関数：
（ｌｅｔ（ｘｙ）
（ｐｅｖａｌ’？ｘ＝１０？）
（ｐｅｖａｌ’？ｙ＝１０？））【０１１９】  Ｃ言語の大まかな基本要素をすべて含む、局所変数とループ構造を持つ関数は次のように解釈する。
入力：
ｉｎｔ  ｆ（ｉｎｔ  ｖ）
｛
ｉｎｔ  ｉ，ｎ＝ｖ；
ｆｏｒ（ｉ＝０；ｉ＜１０；ｉ＋＋）
ｎ＋＋；
ｒｅｔｕｒｎ  ｎ；
｝
実行関数：
（ｄｅｆｕｎ  ｆ（ｖ）
（ｌｅｔ（ｉ，ｎ）
（ｐｅｖａｌ’？ｎ＝ｖ？）
（ｐｒｏｇ（）
（ｐｅｖａｌ’？ｉ＝０？）
ｌｏｏｐ
（ｉｆ（ｎｏｔ（ｐｅｖａｌ’？ｉ＜１０？））
（ｒｅｔｕｒｎ  ｎｉｌ））
（ｐｅｖａｌ’？ｎ＋＋？）
（ｐｅｖａｌ’？ｉ＋＋？）
（ｇｏ  ｌｏｏｐ）
（ｒｅｔｕｒｎ−ｆｒｏｍ  ｆ  ｎ）））【０１２０】  式の解釈と実行方法は様々なものが考えられ、これらの変換方法はほんの一例でしかないが、変換方法についてはすでに確立された様々なコンパイラ技術が適応できることに留意されたい。このように、制約式の関係する式実行を自然に関数ｐｅｖａｌで置き換えて実行する、本発明とＬＩＳＰの特徴を組合せた極めて強力なプログラミング言語を設計することは可能である。これを用いて、関数型言語と融合させた強力なプログラミング言語で図１２（ａ），（ｂ）を記述することで、本発明の図３，図８，図１０に示した制約条件解決装置が現存する手続型、関数型プログラミングの機能を網羅しながら実際の実行効率を落とさずに実行することが可能となる。この際、図２１に示すオペレータは、関数ＰＥＶＡＬ内の式処理で実現されることとなる。【０１２１】＜本発明の他の適用例：設計手法との組み合わせ＞
また、本発明は、設計手法に組合せて適用することが可能である。開発設計手法には、実に様々なものがあるが、どのような方法であれ、まず実現したい要求を分析し、次に要求を実現するために開発するターゲットの仕様を決定し、そしてその仕様を満たすプログラムを開発することが共通的な概念としてある。しかしながら、従来の手続き型プログラミング手法の場合、どの開発手法であっても最終的にはＣＰＵの動きをプログラムコードとして記述しなければならなかった。一方、宣言的プログラミング手法はこの問題を解決する可能性を秘めているが、冒頭で述べたように計算機の実行効率が良くないという問題が大きい。そのため、現在の一般的プログラミング作業といえば、手続き型プログラミング手法のことを指すことが多い。【０１２２】  さて、システム設計手法のひとつとして、データ中心指向がある。データ中心指向は業務システムをうまく設計できる方法として知られているが、これによって要求を実現するシステム設計を行ったとしても、最終的にはコーディング作業が必要であり、プログラムコードとしてＣＰＵの動きを記述しなければならない。ＣＰＵの動きの記述については、ソフトウェア工学が発達した現在でも本質的にはプログラマーの経験と勘に頼っており、未だ人間の創造的作業の領域内に存在する開発設計作業が大変であるのが現状である。開発設計作業を低減させる道具としてＣＡＳＥツール等がある。しかし、これらは開発作業を軽減することはできても、人間がＣＰＵの動きを記述することを不要にするという本質的な問題については依然として解決できていなかった。【０１２３】  そこで従来の手法では、前記本質的問題の解決には目をつぶる代わりにプログラムコードを再利用することに重点を置いている。例えばソフトウェアのライブラリ化やオブジェクト指向プログラミング言語は、この再利用を目的として概念化され生み出されてきたのである。【０１２４】  これに対して本発明は、計算機の動きを考慮する必要があるものの、従来のような複雑な動きを考慮する必要が全くない。つまり、プログラマーは各種設計手法に共通する問題であるＣＰＵの動きを直接記述する作業から解放され、コーディング時での創造的作業を行う必要がない。したがって、本発明によれば、ＣＡＳＥツール又はＣＡＳＥツールに類似したツール及びその他ツールの発展形として、仕様からプログラムコードを自動生成させることが可能となり、自動プログラミングを実現することができる。【０１２５】  もし計算機単体ではなくシステム全体を本発明によって設計開発するならば、広大なシステム全体を自動生成させることも可能である。この場合非常に多くの変数と関係式が使用されるが、従来の設計手法と同様に、トップダウン的設計手法又はボトムアップ的設計手法が実現できたり、さらには機能による領域分割を行うことや、分割された領域を再利用することも可能であることは言うまでもない。また、本発明がどのような開発設計手法についても共通して適用できることは言うまでもない。【０１２６】＜本発明の他の適用例：グラフィックデータやロボットへの応用＞
本発明の更なる適用例として、コンピュータグラフィックのモデルやロボットの関節等の可動部への応用について説明する。ここではロボット制御の精度といった本発明と直接関係ない複雑な問題は省略して、連結された関節の扱いについてのみ説明する。
いま、結ばれた点ａ，ｅの間に４つの関節Ａ，Ｂ，Ｃ，Ｄがあるとして、関節ＡＢ間の位置をｂ、関節ＢＣ間の位置をｃ、関節ＣＤ間の位置をｄとすれば、ａ〜ｅ間の関係はこれら５つの点で表現することができる。各点が（ｘ，ｙ，ｚ）の３つの座標を持つベクトルで表わされた３次元の場合、各関節の回転の動きは３×３の回転行列で示される。なお、この回転行列にさらに並行移動成分を入れて４×４行列としてもよい。【０１２７】  本問題を単純化するために、各点間の長さ等を省略した単なる回転のみを制約式で表すとするならば、
ｂ＝ａ＊Ａ              …（ａ）
ｃ＝ｂ＊Ｂ              …（ｂ）
ｄ＝ｃ＊Ｃ              …（ｃ）
ｅ＝ｄ＊Ｄ              …（ｄ）
となる。ここで、Ａ，Ｂ，Ｃ，Ｄは対応する関節の回転行列を示す。【０１２８】  通常、関節の移動範囲には制限があるため各回転行列Ａ〜Ｄの値にも制限があり、ユーザはこの制限を制約式で記述することになる。もし、ａが固定されていて関節Ｂが変化した場合、前記（ｂ）→（ｃ）→（ｄ）の順の制約伝搬が実行されることが必要である。また、もし、固定されたａに対して動かしたい位置ｅがある場合、この制約伝搬によって、各回転行列Ｄ，Ｃ，Ｂ，Ａの必要な回転成分だけが修正されて自動的に定まる。ここでａが固定されていることは、制約条件として固定されていることを示す変数を追加するか、システムの変数や関係式へ属性として持たせること等で実現できる。そこで、回転行列Ａ〜Ｄをそれぞれ関節を制御するモーター等の角度とするとこれはロボット制御に適用することができる。また、３次元座標ａ〜ｅを透視変換してディスプレイデバイス等へ描画させれば、これはコンピュータグラフィックへ適用する場合とまったく同様にある。【０１２９】  このようなロボットの関節等の可動部へ本発明を適用する場合、現実的にはもっと複雑になるが、それでも手続型プログラミング手法での実現よりは格段に単純で自然な形で実現することができる。なお、ロボットの関節等の可動部への適用例はあくまでも一例に過ぎず、関節に類似した任意の問題をうまく解決できることは言うまでもない。【０１３０】＜本発明の他の適用例：化学分野、物理分野、シミュレーション分野への応用＞
また、本発明の更なる適用例として、化学分野への応用について説明する。
化学式を扱う場合には様々なモデル化が考えられるが、ここでは説明のために簡単化して本発明に直接関連する内容のみを説明する。【０１３１】  化学式における各元素をオブジェクトとして扱うために、元素の種類別にクラスとして定義し、使用したい元素を必要に応じてインスタンス化する。各元素オブジェクトは、制約条件として他元素との結合条件や元素の性質を持つことにする。また、元素の組合せは化合物オブジェクトで管理し、元素オブジェクトを化合物オブジェクトへ登録することによって表すようにする。化合物オブジェクト内では、組合せた時の性質や組合せ条件を制約式で持つことにする。このように構成することによって、ユーザはオブジェクトの組合せを自由に変更できるが、一方で制約条件によって不可能な組合せは禁止され、そして元素の変更が成功した時にはこれに応じて化合物の性質も更新されたことを知ることができる。また、この時、例えば元素オブジェクト内に電子の状態を変数（属性）として持っているならば、電子変数に関する制約伝搬が発生して、物理現象である電子の挙動を表すことができる。【０１３２】  以上説明したように、本発明は化学現象や物理現象等を効率的に表すことができるが、これはある状況のモデル化と、事象の発生に対する現象のシミュレーションであり、変数値の変更に対する制約解消それ自体が特定の現象そのものとなっている。なお、化学現象や物理現象等に限らず多くのシミュレーション分野で本方式が効果的に使用できることは言うまでもない。【０１３３】＜本発明の他の適用例：線形計画法（シンプレックス法等）への応用＞
また、これまでの説明から、本発明が、典型的にはシンプレックス法等の線形計画法、整数計画法、輸送問題などに記載される制約条件において、対象問題に関する制約伝播の処理手順が考慮された制約条件をユーザが入力することができる場合であれば適用可能であることは当業者であれば明白である。【０１３４】＜本発明の他の適用例：ニューラルネットワークへの応用＞
ニューラルネットワークにおけるニューロンモデルは、閾値を変数として制約式で記述することができる。この観点で見るならば、ニューラルネットワークのニューロンモデルの結合は、本方式で扱う制約式関係の特殊形であり、サブセットとみなすことができる。
ニューラルネットワークでは、求めたい結果を得るためにネットワーク内の各ニューロンモデルの閾値を決定することを学習と呼ぶが、この学習では所望の結果を得るための閾値をどのようにして設定させるかが課題であった。そしてその学習方法といえば、本方式に対する従来の制約プログラミングに概念的に近いものであった。しかし、ニューロンモデルの閾値の設定は変数の値を設定する作業であり、本発明で述べてきた方式によるプログラミングと見なすことができる。従って、本発明をニューラルネットワークへ応用することができる。すなわち、本発明によって、値を自動調整させるだけではなく、動きを考慮して一部あるいは全部の閾値を設定することによる学習方法を実現することができる。【０１３５】  なお、前述した内容はあくまでも本発明の技術思想を説明するための一例であってこれらに限定されることはなく、本発明の技術思想を実現するにあたり、本発明の技術分野における通常の知識を有する者が、制約条件解決装置の各構成や制約条件の定義の方法を追加・変更しても本発明の根本的な技術思想は不変であることには変わりはないことは明らかである。【０１３６】  また、本発明の目的は、前述した実施形態の制約条件解決装置１００，２００，３００，４００の機能を実現するソフトウェアのプログラムコードを記憶した記憶媒体を、システム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読みだして実行することによっても、達成されることは言うまでもない。【０１３７】  この場合、記憶媒体から読み出されたプログラムコード自体が本実施の形態の機能を実現することとなり、そのプログラムコードを記憶した記憶媒体及び当該プログラムコードは本発明を構成することとなる。プログラムコードを供給するための記憶媒体としては、ＲＯＭ、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード等を用いることができる。【０１３８】  また、コンピュータが読みだしたプログラムコードを実行することにより、上記本実施の形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳ等が実際の処理の一部または全部を行い、その処理によって本実施の形態の機能が実現される場合も含まれることは言うまでもない。
【図面の簡単な説明】
【０１３９】
［図１］本発明の第１の実施形態における制約条件解決装置の基本的な構成要素を示す全体構成図である。
［図２］本発明の第１の実施形態における制約条件解決装置の動作手順を示すフローチャートである。
［図３］本発明の第２の実施形態における制約条件解決装置の全体構成図である。
［図４］第１の実施形態における制約条件解決装置の制約条件格納手段が計算機の記憶領域へ制約条件を格納する形態例を示す図である。
［図５］会計計算問題に関するデータ構造の一例を示す図である。
［図６］会計計算問題に関する制約条件の格納形態の一例を示す図である。
［図７］データ構造の一例を示す図である。
［図８］本発明の第３の実施形態における制約条件解決装置の全体構成図である。
［図９］制約条件抽出手段による解決方法を示す構造図である。
［図１０］本発明の第４の実施形態における制約条件解決装置の全体構成図である。
［図１１］Ｗｅｂサーバと組合せてデータ表示を行うシステムの概念図である。
［図１２（ａ）−（ｂ）］図１１に示すシステムにおいて、関数定義保持手段及び制約条件格納手段に格納するデータや制約条件の一例を示した図である。
［図１３］一般のウィンドウインタフェースにおいて、データとユーザインタフェースとの関係を制約条件で記述する一例を示した図である。
［図１４］マルチウィンドウシステムの一例を示す図である。
［図１５］ウィンドウシステムを実現するクライアント／サーバシステムにおけるクライアント側の構成を概念的に示す図である。
［図１６］ＧＵＩクライアントにおいて、ＧＵＩ制御部が各パーツの動作を制御することを説明するための図である。
［図１７］従来の宣言的プログラミング手法における解法手順を示す図である。
［図１８］従来のプログラミング言語環境と、本発明の制約条件の解を求める制約解消系との位置付けを概念的に示した図である。
［図１９］従来のプログラミング言語環境の構成を概念的に示した図である。
［図２０］データ定義と制約式をまとめたクラス化に関する概念を示じた図である。
［図２１］配列構造の制約条件にアクセスする際のオペレータ例を示す図である。
［図２２］通常のＬＩＳＰ言語の内部データ構造を極単純化した一例を示す図である。
［図２３］ＬＩＳＰ言語の基本データ構造を双方向に辿ることができるようにした一例を示す図である。
［図２４（ａ）−（ｈ）］ユーザが制約条件及び値を入力し、計算結果などを出力する画面例を示す図である。
【符号の説明】
【０１４０】１  制約条件入力手段
２  変数値設定手段
３  制約条件抽出手段
４  制約条件解算出手段
５  変数値再設定手段
６  制約条件格納手段
７  変数値格納手段
８  制約条件抽出手段
９  関数定義保持手段
１０  関数定義実行手段
１１  データベース
１２  システムリソース
１００  制約条件解決装置
２００  制約条件解決装置
３００  制約条件解決装置
４００  制約条件解決装置
【図１】
0004669788.tif 000002
【図２】
0004669788.tif 000003
【図３】
0004669788.tif 000004
【図４】
0004669788.tif 000005
【図５】
0004669788.tif 000006
【図６】
0004669788.tif 000007
【図７】
0004669788.tif 000008
【図８】
0004669788.tif 000009
【図９】
0004669788.tif 000010
【図１０】
0004669788.tif 000011
【図１１】
0004669788.tif 000012
【図１２（ａ）】
0004669788.tif 000013
【図１２（ｂ）】
0004669788.tif 000014
【図１３】
0004669788.tif 000015
【図１４】
0004669788.tif 000016
【図１５】
0004669788.tif 000017
【図１６】
0004669788.tif 000018
【図１７】
0004669788.tif 000019
【図１８】
0004669788.tif 000020
【図１９】
0004669788.tif 000021
【図２０】
0004669788.tif 000022
【図２１】
0004669788.tif 000023
【図２２】
0004669788.tif 000024
【図２３】
0004669788.tif 000025
【図２４】
0004669788.tif 000026