WO2005071609A1

WO2005071609A1 - 制約条件解決方法、制約条件解決装置、及び制約条件解決システム

Info

Publication number: WO2005071609A1
Application number: PCT/JP2005/000752
Authority: WO
Inventors: Toshio Fukui
Original assignee: Metalogic Inc
Current assignee: Metalogic Inc
Priority date: 2004-01-21
Filing date: 2005-01-21
Publication date: 2005-08-04
Anticipated expiration: 2006-07-21
Also published as: KR20060120188A; CA2554580C; KR100916745B1; EP1710736A4; JPWO2005071609A1; CN1910601B; US7499764B2; CA2554580A1; CN1910601A; JP4669788B2; US20070010901A1; EP1710736A1

Abstract

　計算機上でのデータ処理手順であるアルゴリズムを記述することなく、対象問題を少ない計算時間で確実に解決することを目的とする。解決手段としては、対象問題に関する制約条件及び当該制約条件に用いられる変数の初期値または変動値が変数値設定手段２により設定されると、制約条件抽出手段３はその変数に関連した制約条件を抽出して、制約条件解算出手段４は各制約条件ごとの解を順次求め、変数値再設定手段５はこの求めた解を新たな変数値として各制約条件の解を求めることを繰り返すように構成したので、解を求める道筋が明確になるとともに、格段に単純化された各制約条件を解けばよいことから最終的な解まで確実に到達することが可能となり、これにより演算処理を格段に高速化させることができるようになる。

Description

明細書

制約条件解決方法、制約条件解決装置、及び制約条件解決システム技術分野

[0001] 本発明は、任意の制約条件力構成される問題に対する効率的な解決に関し、特に、制約伝播の処理手順が考慮された制約条件及び変数値の設定のみで実行可能な制約条件解決方法、制約条件解決装置、及び制約条件解決システムに関するものである。

背景技術

[0002] 様々なアプリケーションプログラムに対する現在の一般的なプログラミング手法は、例えば、 C言語、 JAVA等のようなプログラミング言語を使って、データ構造を手続き的に宣言した上でそのデータの処理手順 (アルゴリズム）をユーザが逐次記述する手続き型プログラミング手法が主流である。コンパイラの最適化機能により最適化が図られること等を除けば、この手続き型プログラミング手法によるデータの処理手順は、計算機が実際に実行する処理手順と一致しているのが原則である。したがって、手続き型プログラミング手法は、計算機 (CPU)の動きを詳細に記述することによって各種の問題に柔軟に対応できる解決方法である。

[0003] このような CPUの動きを記述する手続き型プログラミング手法に対するものとして、宣言的プログラミング手法がある。これは、対象問題に対応した制約条件がユーザにより定義されるとその後の実際のデータ処理手順については、 CPUにすベて任せてしまう手法であり、特定の問題領域には好都合な問題解決手法であるとして従来より用いられて、る（例えば、特許文献 1または特許文献 2)。

前記宣言的プログラミングにおいては、ユーザは、制約条件を記述するのみで解が出力されるのを待つだけで良い半面、 CPUがデータ処理をどのような手順で行うかについては干渉できないという特徴を有している。現在の計算機環境では、前述したような大きく 2つに分けられるプログラミング手法のうち、手続き型プログラミング手法が主に使用されている。

[0004] この手続き型プログラミング手法によってプログラム開発を行う場合、ユーザがデータ構造の定義を行った時点で、そのデータ構造によって記述すべきアルゴリズムも連動して事実上決定されてしまうのが殆どである。しかもそのアルゴリズムは類似した対象問題では同様な手順で表現され、パターン化することが可能である。

[0005] このため、各アプリケーションで同じようなプログラミング作業が重複して行われることが多ぐプログラム開発の非効率ィ匕が従来より問題となっていた。この問題に対処するため、現在では汎用的に使用されるプログラミング部分のライブラリイ匕やオブジェタト指向に基づくソフトウェア開発によってソフトウェアの部品化を積極的に導入し、既存のプログラムにない部分に集中したプログラム作業の高効率ィ匕が推進されている。

[0006] 特許文献 1：特開平 5— 3548号公報

特許文献 2：特開平 9 81387号公報

発明の開示

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

[0007] し力しながら、現実的にはライブラリ化されるソフトウェア部品は膨大であってし力も年々その数は増カロしている。各プログラマーが、この膨大な部品群力も対象問題に最適なものを抽出する際には選択ミスが少な力ずあり、再度選択し直すことで開発作業をやり直さなければならない危険性があることを考慮すると、ソフトゥア部品を利用せずに始め力も各プログラマーがコーディング作業を行うケースも多々あるという問題があった。

また、オブジェクト指向によるソフトウェア開発は一定のスキルが要求されることから、どのプログラマーでもオブジェクト指向のプログラミング作業ができるとはかぎらず、全体的にみれば作業効率の向上がさほど上がらないという問題があった。

このように、プログラム開発作業には、個人技量に依存した閉鎖的な面や非効率的な面が依然として解消してヽなヽと、う問題があるのが現状である。

[0008] 一方、前述したように、宣言的プログラミング手法では、少なくとも制約条件の記述と、当該制約条件で用いるデータ値とが必要であって、実際の問題に適用した場合、その制約条件及びデータの数は非常に多くなる。ここで、実際の問題とは、例えば f (X , X , · ··, X )≤b (k= l, 2, · ··, m)の連立式を満たし、且つ、評価関数 f ( k 1 2 n k 0

X , X , · ··, X )を最小値にするような組合せ最適化問題である。つまり、図 17に示

1 2 η

すように、 m個の連立式及び評価関数 fで表した制約条件を計算機側に与えると、

0

計算機（図 17の制約解消系）は全ての制約条件を同時に満たすデータを一括して探索することが行われる。

[0009] この組合せ最適化問題は、変数 X及び連立式の数が増加するほど解空間における組合せの可能性が指数関数的に増加することから、計算機上での処理が複雑かつ膨大となる。しかも、特に関数 f

kが非線形関数の場合は、分散した複数の解空間が存在することもあり、解が存在しない解空間をひたすら探索してしまって無限ループに陥ることのないよう効率的に解を求める工夫等が必要になる。なお、組合せ最適化問題の他にも、組合せ充足問題、整数計画法などについても同様の問題点がある。

[0010] さらに、制約条件の条件式または入力データの一部を変更する必要が生じたときは

、先に計算した同様の制約条件問題をまた最初力計算し直さなければならず、リソースの無駄使いになるとともに非常に非効率的であるという問題があった。

[0011] そこで、本発明は前述した問題点に鑑み、計算機上でのデータ処理手順であるァルゴリズムを記述することなぐ対象問題を少ない計算時間で確実に解決することを目的としている。

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

[0012] 本発明の制約条件解決方法は、ユーザにより対象問題に関する制約伝播の処理手順が考慮された制約条件を入力する制約条件入力処理と、前記制約条件入力処理により入力された制約条件に用いられる変数の初期値または変動値を設定する変数値設定処理と、前記制約条件入力処理により入力された制約条件の中から、前記変数値設定処理により設定された値に関係する制約条件を抽出する制約条件抽出処理と、前記制約条件抽出処理により抽出された制約条件全てに対して、前記ユーザにより考慮された制約伝播の処理手順に基づいて前記変数の初期値または変動値を代入して当該制約条件の解を算出する制約条件解算出処理と、前記制約条件解算出処理により算出された解を前記変数値設定処理での新たな変動値として設定する変数値再設定処理とを含み、前記変数値再設定処理は、再設定される新たな変動値が存在する間は、前記制約条件抽出処理及び前記制約条件解算出処理を繰り返し行うことを特徴とする。

[0013] 本発明の制約条件解決方法は、制約条件を入力する制約条件入力処理と、前記制約条件入力処理により入力された制約条件に用いられる変数の値を設定する変数値設定処理と、前記制約条件入力処理により入力された制約条件の中から、前記変数値設定処理により設定された値に関係する制約条件を抽出する制約条件抽出処理と、前記制約条件抽出処理により抽出された制約条件の解を算出する制約条件解算出処理とを含む制約条件解決方法において、前記制約条件は、現在の配列要素数を含んでいること、前記変数に複数個の値を持たせること、構造体配列の要素値による検索を含んでいること、及びデフォルト規則による文字列数値変換の少なくとも何れかを特徴として構成される。

[0014] 本発明の制約条件解決装置は、ユーザにより対象問題に関する制約伝播の処理手順が考慮された制約条件を入力する制約条件入力手段と、前記制約条件入力手段により入力された制約条件に用いられる変数の初期値または変動値を設定する変数値設定手段と、前記制約条件入力手段により入力された制約条件の中から、前記変数値設定手段により設定された値に関係する制約条件を抽出する制約条件抽出手段と、前記制約条件抽出手段により抽出された制約条件全てに対して、前記ユーザにより考慮された制約伝播の処理手順に基づいて前記変数の初期値または変動値を代入して当該制約条件の解を算出する制約条件解算出手段と、前記制約条件解算出手段により算出された解を前記変数値設定手段での新たな変動値として設定する変数値再設定手段とを含み、前記変数値再設定手段は、再設定される新たな変動値が存在する間は、前記制約条件抽出手段及び前記制約条件解算出手段が繰り返し行うことを特徴とする。

[0015] 本発明の制約条件解決装置は、制約条件を入力する制約条件入力手段と、前記制約条件入力手段により入力された制約条件に用いられる変数の値を設定する変数値設定手段と、前記制約条件入力手段により入力された制約条件の中から、前記変数値設定手段により設定された値に関係する制約条件を抽出する制約条件抽出手段と、前記制約条件抽出手段により抽出された制約条件の解を算出する制約条件解算出手段とを含む制約条件解決方法において、前記制約条件は、現在の配列要素数を含んでいること、前記変数に複数個の値を持たせること、構造体配列の要素値による検索を含んでいること、及びデフォルト規則による文字列数値変換の少なくとも何れかを特徴として構成される。

[0016] 本発明の制約条件解決システムは、複数の機器が互いに通信可能に接続されている制約条件解決システムであって、上記機器のうち少なくとも 1つの機器は、前記何れかに記載の制約条件解決装置の機能を有することを特徴とする。

発明の効果

[0017] 本発明によれば、対象問題に対する制約伝播の処理手順が考慮された制約条件、及び制約条件に用いられる変数の値 (初期値)を入力すると、当該変数の値に関連する制約条件を抽出した上でその制約条件のそれぞれを満たす解を導くとともに、導かれた解を変数の新たな値 (変動値)として代入して前記各制約条件の解を求める処理を繰り返すように構成したので、他の制約条件との AND関係をもつことなく各制約条件単独での解を求めることが可能となり、計算処理を高速に行いながら最終解を得ることができる。

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

[0018] 以下、本発明の好適な実施の形態について図面を参照しながら詳細に説明する。

図 18は、従来のプログラミング言語環境と、本発明の制約条件の解を求める制約解消系との位置付けを概念的に示した図である。図 18に示すように、従来のプロダラミング言語環境には、プログラム言語処理系と、プログラムコードと、データとがあって、プログラム言語処理系がプログラムコード及びデータを制御する形態になって、る。本発明では従来のプログラミング言語環境におけるデータの他に、制約式 (制約条件)及び制約解消系を備え、それぞれが相互に情報のやり取りを行うことができるように接続される構成である。

また、図 19も従来のプログラミング言語環境であるが、前記従来の制約解消系をライブラリの形で構成したときの構成図である。

[0019] (第 1の実施形態）

まず、本発明の第 1の実施形態における制約条件解決装置の基本構成及びその基本動作について説明する。

<制約条件解決装置 100の基本構成 >

図 1は制約条件解決装置 100の基本的な構成要素を示す全体構成図である。図 1に示すように制約条件解決装置 100は、制約条件入力手段 1と、変数値設定手段 2と、制約条件抽出手段 3と、制約条件解算出手段 4と、変数値再設定手段 5とを含んでいる。

[0020] 制約条件入力手段 1は、ユーザが計算機 (CPU)による制約伝播の処理手順を頭に思い浮かべて決定した制約条件を入力するためのものである。

変数値設定手段 2は、制約条件入力手段 1により入力された制約条件を構成する各変数にユーザが指定した具体的な初期値を設定するためのものである。また、詳細は後述するが、各変数に対して初期値以外の値 (以下、変動値と称する）を設定することも行う。

また、制約条件入力手段 1及び変数値設定手段 2は、いわゆるデータ入力用の U ZIであり特に限定するものではなぐ入力を容易に行える様々なツールを含むものであり、ユーザが入力した値を確認することができる表示 (モニタ）画面を備えることができる。なお、制約条件解決装置 100により計算された値をユーザに提示する出力表示手段 (不図示)を含む構成にしてもよい。この出力表示手段も出力値を確認することができる表示 (モニタ)画面を備えることができる。さらに、制約条件入力手段 1 (変数値設定手段 2を含む)及び出力表示手段の一つにして、データを入出力が行える入出力手段であってもよい。

[0021] 制約条件抽出手段 3は、入力された制約条件の中から、初期値または変動値が設定された各変数を構成要素として有する制約条件を抽出する。本実施形態では、制約条件抽出手段 3は、該当する制約条件をまとめて抽出するように構成したが、後述する制約条件解算出手段 4によってある 1つの制約条件の解を求めた後、次の制約条件を抽出することを順次繰り返すように、一つずつ抽出するようにしても構わな、。

[0022] 制約条件解算出手段 4は、初期値または変動値を代入した各制約条件を解くが、本発明の特徴として、制約条件すべてを満足するようないわゆる連立解として一括して解くのではなぐ各制約条件の一つずつを対象にして解くようにしている。このため、ある変数の値が設定または変更されると、制約条件の 1回目の解がシーケンス的に所定の順序に従って順次求まることになる。ここで、前記所定の順序とは、ユーザ (プログラマー)が制約伝播の処理手順を考慮して入力した制約条件で示す順序である

[0023] ここで、制約条件の具体例を以下に示す。

(A)制約条件の例 1

宣言的プログラミング手法を容易に理解するために説明として使用される典型的な例題としては、以下の会計計算問題が挙げられる。

いま、 4つの物品の値段と個数をそれぞれ、（1) 100円， 2個、（2) 200円， 3個、（3 ) 300円， 2個、（4) 50円， 3個としたとき、値段、個数、及び小計の配列変数を用いて、本発明のいう制約条件をあらわせば、

値段 [1] = 100、値段 [2] = 200、値段 [3] = 300、値段 [4] = 50 …(式 1) 個数 [1] = 2、個数 [2] = 3、個数 [3] = 2、個数 [4] = 3 · · ·(式 2)

小計 [i] =値段 [i] X個数 [i] (i= 1一 4) · · · (式 3)

合計 =∑小計 [i] (i= l一 4) …(式 4)

となる。（式 1)及び (式 2)は、制約条件のうちの特に変数データの設定である。

[0024] 前記 (式 1)一（式 4)の記述から明らかなように、手続き型プログラミングの場合に必要な 0→合計 (→は代入を表す、以下同じ)、合計 +小計 [1]→合計、合計 +小計 [2] →合計、合計 +小計 [3]→合計、合計 +小計 [4]→合計という繰り返しループの記述力宣言的プログラミングの場合には不要である。

[0025] (B)制約条件の例 2

string name, message, outputs, output; ··· (式 5ノ

name = "特許太郎" · · ·（式 6)

message = "こんにちは。この文章は HTML文書の本です。 " …（式 7) outputs = 名目 ιΤ & name & メッセージ & message; …(式 8)

output = " < HTML > < BODY > " & outputs &く/ BODY > < /HTML > · · · ( 式 9)

前記 (式 5)が変数データの定義、（式 6)—（式 7)が変数への値代入、及び前記 (式 8)— (式 9)が具体的な実行式である。また、 &演算子は文字列連結演算子である。前記（式 6)—（式 7)のように、文字列 name、 messageを任意に書き換えて outputで出力される HTML用テキストが生成される。

[0026] (C)制約条件の例 3

文字列 strに別の文字列 addを次々連結して!/、く動作を記述した制約条件を次に示す。

string str; … CIO)

string add; ··· (式 1丄ノ

str = str & add ··· (式 12)

前記 (式 10)及び (式 11)は変数データの定義であり、前記 (式 12)が具体的な実行式である。本例での文字列 strの値変更による制約伝播は、文字列 addの値が変更されるたびに、文字列 strへ文字列 addの値が追加されることが繰り返される。

[0027] ここで、制約条件は、前記 (A)— (C)で示すような等号または不等号で表される式である必要はないことに留意されたい。そして、制約式の評価は最終的に真カ為を答えとし、 C言語等と同様に例えば f (x)だけが制約条件として記述されていた場合にはこの f (X)を実行し、結果が真または偽かによつて判断され処理される。

[0028] 変数値再設定手段 5は、制約条件抽出手段 3及び制約条件解算出手段 4により 2 回目以降の解を求めるために、制約条件解算出手段 4で求めた 1回目の解を各変数の新たな値、すなわち変動値として設定する。そして、一連の制約条件の解を求める処理は、制約条件解算出手段 4で変更される解が存在しなくなって最終解に到達した後、制約条件解決装置 100が別途終了指令を受信したときに終了する。

[0029] 前述したように、本発明の特徴の 1つは、抽出した各制約条件の変数に値を代入して制約条件 1つずつを順次解、て、くことを繰り返すことである。このためには制約伝播の処理手順を考慮して制約条件にあらかじめユーザが設定しておくことが前提となる。

[0030] なお、制約条件解算出手段 4による処理中に、解を求めることができない解不能、または解を特定することができない解不定の状態に陥った場合は、計算機に予め定義した適切な例外処理を実行するようにしておくことで、プログラムエラーとして出力されるようにするが、これはユーザが解けない制約条件を定義したことを意味する。本実施形態の制約条件解決装置 100において、ユーザは、本来解ける答の処理手順になるように、計算機の処理手順を考慮した制約条件を設定しなければならな！/、負担を負うが、これは従来の手続き型プログラミング作業に較べはるかに楽な作業である。

[0031] <制約条件解決装置 100の全体動作 >

次に、前述した構成の制約条件解決装置 100の全体動作について説明する。図 2は、制約条件解決装置 100の動作手順を示すフローチャートである。まず、ステップ S 20で、制約条件に用いられる変数に初期値が設定されているか否かを判断する。前記判断の結果、制約条件入力手段 1により入力された制約条件を構成する各変数に対してまだ初期値が設定されていない場合、ステップ S21で、変数値設定手段 2は、ユーザが指定した初期値を設定する。

[0032] 次に、ステップ S22で、制約条件抽出手段 3は、各変数の値が変更されていないかを判断する。制約条件として変数に初期値を設定したときは、最初の変更であるとして次のステップ S22へ進む。一度、初期値を設定後、後述するステップの処理が終了すると、制約条件解決装置 100は、このステップ S22で新たな変数の値変更があるまで待ちの状態が維持されている。なお、本フローチャートには「終了」を示していないが、動作終了指示命令が外部から入力されたとき、制約条件解決装置 100は、所定の動作処理 (不図示）を実行して一連の動作を終了するように制御されて、る。

[0033] ステップ S23では、制約条件抽出手段 3は、ステップ S22で変更された変数を要素とする集合 Sを生成する。ここで集合 Sを生成するとは、例えば、計算機上のある記憶領域に、前記変更された変数の名前や、または変数の配列要素を識別できるサフィックスを書き込むこと等を意味する。

さらに、制約条件抽出手段 3は、前記集合 Sに要素が存在する力否か、すなわち、変数値設定手段 2により値を変更した変数があるか否かを判断する (ステップ S24)。前記判断の結果、集合 Sに要素があるとき (集合 Sが空集合でないとき)は、制約条件抽出手段 3は、集合 Sから要素 Smを 1つずつ取り出す (ステップ S25)。

[0034] 次に、ステップ S26で、前記取り出した要素 Smに関連した制約条件の集合 Qを生成する。つまり、要素 Smを含んで構成される制約条件があれば、制約条件抽出手段 3はこれを集合 Qに出力する。次に、ステップ S27で前記集合 Qに要素がある間は、以下のステップ S28—ステップ S30を繰り返して行う。

[0035] ステップ S28で、制約条件解算出手段 4は、集合 Qから 1つの制約条件 Qmを取り出す。そして、制約条件解算出手段 4は、ステップ S28で取り出した制約条件 Qmを解、て、制約条件 Qmを満たすために変更するべき変数及びその値を求める (ステツプ S29)。

ここで、ステップ S29における処理の詳細な内容は以下に示す通りである。

(1)制約条件 Qmが満たされているかどうかをチェックして、満たされているときは本ステップ S29を終了する。

(2)制約条件 Qmを満たすために変更するべき変数とその値を求める。

(3)前記（2)で求めた変数の値が正、かどうかを検証する。

前記（2)はステップ S29の処理として必須である力その他の（1)及び（3)につヽては必ずしもそうとは限らない。対象問題に応じてユーザが必要力否かを判断し、制約条件として明示的または黙示的に指示するように構成してよい。

[0036] さらに、ステップ S30で、変数値再設定手段 5は、ステップ S29で求めた変数に求めた値を再設定して、その後の処理ではその再設定した値を基に制約条件が解かれる。

したがって、ある変数が変更される場合、その変数に関連する複数個の制約条件があれば、 1つずつ取り出された制約条件ごとの解が順次求まり、同時に、得られた解によって集合 Sの最後部にその変数が追加されるようになる。

[0037] 一方、ステップ S28によって制約条件 Qmが取り出された結果、集合 Qに要素がないとステップ S27で判断された場合、一連の処理はステップ 24へ戻り、集合 Sから次の変数 Smが取り出されて同様の処理が繰り返される。

この結果、集合 Sに要素がなくなったとき、制約条件解決装置 100の処理としては安定状態に入った状況に相当することになり、前述したように、制約条件に用いられる任意の変数に新たな値が設定されるまでステップ S22で待ちの状態になる。

[0038] 本実施形態では、ステップ S 25において集合 Sに複数の変数 Smを含んでいたときの変数 Smを取り出す順序や、ステップ S 28にお、て制約条件 Qmを取り出す順序は、制約伝播の処理手順を考慮して、ユーザがその順序 (優先順位)を明示的に指定して計算機に行わせる制約条件の設定方法にしている。具体的には例えば、その優先順位は制約条件の記載した順序であると、うようにあら力じめ決めておくことで達成される。この具体例を以下に示す。

[0039] 前述した会計計算問題を再び用いる。

制約条件は、

値段 [1] = 100、値段 [2] = 200、値段 [3] = 300、値段 [4] = 50…(式 1) 個数 [1] = 2、個数 [2] = 3、個数 [3] = 2、個数 [4] = 3 · · ·(式 2)

小計 [i] =値段 [i] X個数 [i] (i= 1一 4) · · · (式 3)

合計 =∑小計 [i] (i= l一 4) …(式 4)

である。

前記 (式 1)一（式 4)の記載順序には意味がある。例えば、 1番目に記載した制約条件 (制約式)が最も優先順位が高ぐ以下順に低くなるものとする。この場合、（式 1) 及び (式 2)により各変数に値を設定することが優先的に行われ、（式 3)、（式 4)はその後に制約式を計算機内部へ登録することを意味している。

制約式の実行順序は実行時に決まるが、集合 S、集合 Q力要素を取り出す順番が不確定である。これを決定するためには明示的な方法として、記載順序で判断したり制約式に優先順位を設定する方法がある。

[0040] その他、前述した優先順位を計算機 (CPU)が自動的に行うように構成してもよ！/ヽ。

この場合、ユーザは、計算機がどのような順序で行っても計算過程で矛盾が生じないような内容及び記載順序力なる制約条件を設定する必要があるが、これはユーザがプログラマ一として通常の知識や経験を備えて、れば容易に成し得る作業である

[0041] 次に、図 2のフローチャートに示す動作手順を、前述した会計計算の例を用いて具体的な制約条件の変数値の変化を追いながら説明する。

例えば、値段 [2]を、 200→250に変更したときを想定する。初期値の設定ではなくデータの変更なので、ステップ S20力らステップ S22へ進む。ステップ S23によって、集合 S = {値段 [2]}となる。ステップ S24で集合 Sには要素があると判断されるので、ステップ S25で値段 [2]が取り出される。

[0042] 次に、ステップ S26で、値段 [2]だけに関連する制約条件である、小計 [2] =値段 [2]

X個数 [2]が集合 Qの要素となる。つまり、集合 Q= {小計 [2] =値段 [2] X個数 [2]}が生成される。

次に、ステップ S27で集合 Qには要素があると判断されるので、ステップ S28で、小計 [2] =値段 [2] X個数 [2]という制約条件が取り出される。ステップ S29で、制約条件の解、つまり、小計 [2] = 250 X 3 = 750が計算されて、ステップ 30では、小計 [2]にこの変更値 750を設定し、小計 [2]を集合 Sに追加して、集合 S= {小計 [2]}を生成する

[0043] そしてステップ S27に戻る力先の集合 Qから 1つしかな力つた要素を取り出してしま、集合 Qは空集合であるので、この後ステップ S 24へ進む。

ステップ S24では、先ほど追カ卩した集合 Sの小計 [2]を判断して、ステップ S25でこの小計 [2]を取り出す。

[0044] 次に、ステップ S26で、小計 [2]だけに関連する制約条件である、合計 =∑小計 [i] ( i= l一 4)を要素とする集合 Qを生成する。つまり、

集合 Q= {合計 =∑小計 [i] (i= l一 4) }が生成される。ステップ S28で当該制約条件を取り出し、ステップ S29で、制約条件の解、つまり、合計 = 200 + 750 + 600+ 1 50 = 1700を計算して、ステップ S30で、変数の（合計）にこの変更値 1700を設定する。同時に変数の (合計）は集合 Sへ格納される。続いて、ステップ S27、 S24、 S25、 S26が実行され、関連のある制約式が存在しないので、集合 Qには追加される要素がない。

この時、計算時間を短縮するために以下のように単純ィ匕することが可能である。すなわち、ステップ S29で、制約条件の解を求める時に加算をもう一度行うのではなぐ変化した値のみを利用して差分解消する。そして、ステップ S30では、合計に関連する制約条件は存在しな、ことがわ力つて、るので、計算時間短縮のために集合 Sには要素を追加しな、ようにする。

[0045] 再びステップ S27に戻る力先の集合 Qから 1つしかなかった要素を取り出してしまい集合 Qは空集合であるのでこの後ステップ S22へ進み、制約条件解決装置 100は次に外部力ものデータ変更があるまで待ち状態になる。

なお、前述した制約条件解決装置 100の動作におけるステップ S28の処理では、集合 Qより制約条件 Qmを 1つずつ取り出してその解を求めていく処理を説明したが、必ずしも 1つずつ取り出さなければならないことはない。制約式の解を同時に求めることが可能な場合、集合 Qから 2以上の制約条件を取り出すこととする。これにより、解決可能な対象問題をより広げることができるようになる。

さらに、制約条件 Qmの実際の解法は、会計問題のような単純な式変形で解くやり方に限っていない。既存の式に関する解法はすべて使用可能であるものとしており、これにより n次方程式の解法を導入することも認めて、る。

[0046] また、別の具体的例として、制約条件に用いるデータの件数そのものを追カ卩 ·削除するときの処理について説明する。

前述した会計計算の例では、値段及び個数の変数をそれぞれ配列で表現してデータ件数を各 4個に固定して制約条件を設定したが、データ件数そのものを変数にしたときの制約条件を考える。現在の制約条件に値段 [5]、個数 [5]を加えて以下のように変更する。

値段 [1] = 100、値段 [2] = 250、値段 [3] = 300、値段 [4] = 50、値段 [5] = 310· ··( 式 13)

個数 [1] = 2、個数 [2] = 3、個数 [3] = 2、個数 [4] = 3、個数 [5] = 3 …(式 14) 項目総数 = 5 …(式 15)

小計 [i] =値段 [i] X個数 [i] (iは任意の整数） …(式 16)

合計 =∑小計 [i] (i= l一項目総数） …(式 17)

[0047] 前述した処理を全く同様に行えば、

小計 [5] =値段 [5] X個数 [5] = 310 X 3 = 930、

合計 =∑ /J、計 [i] = 200 + 750 + 600 + 150 + 930 = 2630となり、未解決のままの制約条件を残すことなく解を導くことが可能である。このような変更は変数または制約条件の削除する場合でも同様であり、可変長配列などで表された変数の個数を変更することも可會である。 [0048] これを実際の入出力手段 (例えば、制約条件入力手段 1)を用いてユーザが制約条件及び値を入力する画面例を図 24に示す。なお、図 24の画面例は出力機能を有する制約条件入力手段 1及び変数値設定手段 2の画面例に相当し、 UNIX上へ一般的なプログラミング言語と同等の入出力インタフェースを持つ構造として実装した実行例である。図 24 (a)—（h)の入出力は一連のものである力便宜上、分けて表示している。

図 24 (a)のように、まず「 $」で示された UNIXプロンプトの後に、ユーザは「ripple」を入力する（図 24 (b) )。これにより本発明の処理が実装されたプログラムがロードされて、画面上に「％」を示してユーザにデータの入力を促す（％以降がユーザの入力データであり、改行されたその後すぐの行に、受信したデータ値や計算出力値を表示している）。

[0049] そこでユーザは、初期値制約式入力する（図 24 (c)の 241)。 242の制約式はここでは合計計算を関数配列全合計 0として抽象化しているが、図 21で示したような制約式で表現することもできる。また、手続的なループ構造を直接記述することもできる (関数型言語との融合を参照)。そしてステップ S29の処理で合計計算の差分解消を実現する時には、制約条件解決装置 100側が判断して自動処理され、ユーザは意識していない。

[0050] 次に、ユーザは初期値を設定する（図 24 (d)の 243,244)。ステップ S22—ステツプ S30に示した処理が実行される力実行の効率を図るために明らかに必要ない時には制約条件解決装置 100側の判断で実行させなヽことができる。図 24 (e)の 245 では、「load」によって残りの入力値をファイル力読み込む。この時点で小計、合計は計算されて設定済となり、 246で「合計」を入力することによって、現在の合計値が表示されて実行結果を取得できる。図 24 (f)の 247を入力すると、図 2のステップ S2 6が実行される。そして、計算途中の画面出力はないが、ステップ S22—ステップ S3 0に示した処理が実行され、 248の入力によって実行結果の合計値が表示される。 2 49, 250の入力は、制約条件に用いるデータの件数を追加設定している。そして、図 24 (g)の 251の入力よつて実行結果に合計値が表示され、図 24 (h)の 252の入力よつて、終了指令の発行を行っている。 [0051] また、いくつかのデータ定義と制約式をまとめたものをクラス化概念における 1クラスとして定義し、パラメータを与えて実例、すなわちインスタンス化させ、制約式と値をセットにするよう構成してもよい。これにより、設定される制約条件を複数に分割させることができるので、必要最小限の処理のみを実行させる場合等に好都合となる。このクラス化に関する概念を図 20に示す。このクラスは継承させることが可能であり、例えば、図 20に示す変数 1、変数 2、及び制約式 1を有するクラス Aと、変数 3を有するクラス Bとがあるとき、このクラス A及びクラス Bを継承し、さらに制約式 2を継承した図 20 のクラスを生成することができる。

[0052] なお、本実施形態の制約条件解決装置 100の構成及び動作から分かるように、本発明では、例えば、すべての制約条件が制約違反をしないという評価式 (評価条件）を設定していない。従来の宣言的プログラミングでは、制約条件の解を求める際に当該評価式に基づいて制約条件間で矛盾しないかを判断するように処理することが多い。本発明では、制約条件の設定時に、矛盾が生じないようにユーザが設定することを前提としているためである。したがって、制約条件解決装置 100は、最後に必ず解を求めることが可能であり、解が求まらないときはユーザによる制約条件の設定誤りである。

実行時に制約違反の存在に関する評価式は必要ないが、補助機能として用意することによってデバッグ時等の問題発生時の対処やミスの発見に役立つことは言うまでもない。

[0053] 本実施形態の制約条件解決装置 100によれば、対象問題に関する制約条件及び当該制約条件に用いられる変数の初期値または変動値が設定されると、その変数に関連した制約条件を抽出して各制約条件ごとの解を順次求めて、この求めた解を新たな変数値として各制約条件の解を求めることを繰り返すように構成したので、任意のデータ構造と、そのデータ構造によるデータ間を連結させる制約条件とによって対象問題を解決することができるようになる。

つまり、設定される制約条件は、従来の手続き型プログラミングのような対象問題を解決するためのアルゴリズムを記述することなくこのアルゴリズムに相当する指令をデータ構造に含ませた上で制約伝播の処理手順に沿って記載し、すべての制約条件が成立する最適解を求めずに制約条件 1つずつの解を求めるように構成したので、解を求める道筋が明確になるとともに、格段に単純化された各制約条件 (例えば、 1 元の方程式)を解けばょ、ことから最終的な解まで確実に到達することが可能で演算処理を格段に高速ィ匕させることができるようになる。

[0054] また、問題の解決方法を制約条件において直接的に記述できるため、ユーザが従来のようなプログラミング言語の特殊な専門知識を必ずしも有して、る必要はなぐ対象問題を容易に解くことができる。

[0055] (第 2の実施形態）

前述した第 1の実施形態では、制約条件解決装置 100において、制約条件入力手段 1と、変数値設定手段 2と、制約条件抽出手段 3と、制約条件解算出手段 4と、変数値再設定手段 5とを含むように構成したが、本実施形態の制約条件解決装置 200では、第 1の実施形態の制約条件解決装置 100における各構成手段 1一 5に加えて、制約条件格納手段 6及び変数値格納手段 7をさらに備えているのが特徴である。なお、本実施の形態の制約条件解決装置 200の構成と、第 1の実施の形態における制約条件解決装置 100とで共通する構成部分については同一の符号を付して、詳細な説明を省略する。

[0056] 本実施形態の制約条件解決装置 200の全体構成を図 3に示す。

制約条件格納手段 6は、制約条件入力手段 1により入力された制約条件を所定の記憶領域に格納する。また、変数値格納手段 7は、変数値設定手段 2により設定された変数値 (初期値、変動値)を格納する。

また、本実施形態の制約条件抽出手段 8は、第 1の実施形態における制約条件抽出手段 3の機能に加えて、新たに設定された制約条件または変動値を、前記記憶領域に格納された制約条件または値と比較して、両者が一致しな、場合のみ制約条件の抽出を行う機能を有している。なお、制約条件抽出手段 8は前記比較を常に行う必要はなぐ制約条件格納手段 6及び変数値格納手段 7から制約条件及び変数値を抽出するようにしてもょ、ことは言うまでもな!/、。

[0057] 図 4 (a)は、制約条件格納手段 6が計算機の記憶領域 (例えば、メモリ、磁気ディスクなど)へ制約条件を格納する形態例を示す図である。つまり、変数 Xを 3つの制約式 (制約式 1、制約式 2、制約式 3)で参照する制約条件があるとし、この変数 Xに値 2 46が設定されたときの記憶領域の表し方を示して、る。前述した会計計算問題の制約条件をこの形式によって表したときの一例を図 6及び図 5に示す。

[0058] 例えば、図 4 (b)に示すように、数式 (x=y + z)は分割して格納される。ただし、このような表し方に限定されるものではない。制約条件の格納形態として、値と制約式とでメモリ領域を必ずしも分割する必要はなぐ例えば制約式を構造として分割せずに文字列などで持ってもよい。

また、図 5に示すようなデータ構造に限らず、例えば、以下に示すような記憶領域でも構わない。

•変数の値は種類分けされ、ある値はメモリ上のみに記録される力他の値はファイルやデータベースへ記録されることで、記録領域上の値を永久的にしてもよぐまたは時刻システム等において特別の意味を持たせるようにしてもよい。

•変数名をポインタで示す必要はなく、直接持ってもょ、。

•変数の値を必ずしも直接的に保持することはな、。

•プログラムのコンパイル時等では変数を識別する必要はないので、変数名は必須ではない。

•制約条件に用いる制約式はリストでなくてもよい。

•制約式リストを持たず、図 7に示すように、変数名力制約式を検索する構成であつてもよい。ただし、図 7に示すようなメモリとポインタ構造に限定するものではない。その他、上記の変形による無数に存在するデータ型はすべて含むものとする。

[0059] 本実施形態の制約条件解決装置 200によれば、対象問題に関する制約条件及び当該制約条件に用いられる変数の初期値または変動値を所定の記録領域に一時的または永久的に保持するように構成したので、本実施形態の制約条件抽出手段 8は、制約条件または変数値に変更が生じた場合のみ、変更された変数 Smに関連する制約条件 Qmを解、て Qmを満たすために変更すべき変数及びその値を求める処理を行うことが可能となる。

これにより、制約条件に変更があつたとしても、複数の制約条件すべてについて最初力計算し直さなくても済む場合が生じ、計算時間の効率を図ることができるようになる。

[0060] (第 3の実施形態）

前述した第 1の実施形態の制約条件解決装置 100では、制約条件入力手段 1と、変数値設定手段 2と、制約条件抽出手段 3と、制約条件解算出手段 4と、変数値再設定手段 5とを含むように構成し、前述した第 2の実施形態の制約条件解決装置 20 0では、さらに、制約条件格納手段 6及び変数値格納手段 7を備えている構成にした力本実施形態の制約条件解決装置 300では、図 8に示すように、関数定義保持手段 9及び関数定義実行手段 10を備えているのが特徴である。

第 1の実施形態の制約条件解決装置 100と、第 2の実施形態の制約条件解決装置 200のどちらであっても、関数定義保持手段 9及び関数定義実行手段 10をさらに備える構成にすることができるが、説明を簡略化させるために制約条件解決装置 100 に付加した構成で説明することとする。

なお、本実施の形態の制約条件解決装置 300の構成と、第 1の実施の形態における制約条件解決装置 100とで共通する構成部分については同一の符号を付して、詳細な説明を省略する。

[0061] プログラミング手法からみた本実施形態の制約条件解決装置 300の構成が有する役割は、第 1の実施形態が、問題解決を完全な宣言的プログラミング手法で行っていたのに対し、第 3の実施形態は、従来の手続き型プログラミング手法を融合している点にある。これは、宣言的プログラミングで解決することが困難な一部の問題については、手続き型プログラミング手法を利用するようにして、どんな対象問題であっても柔軟な問題解決を果たすためである。

[0062] 本実施形態の制約条件解決装置 300の全体構成を図 8に示す。

関数定義保持手段 9は、制約条件入力手段 1及び変数値設定手段 2によりユーザが従来の手続き型プログラミングで記述する手続き、及び変数値を保持する。関数定義保持手段 9は、制約条件抽出手段 3と相互にデータの入出力を行うことが可能であるように接続されている。

なお、本実施形態の制約条件入力手段 1のような、必ずしも制約条件以外に手続き型の記述を許可する構成にする必要はない。例えば、手続き型の記述専用の入力手段を別途備えるような構成にしてもよい。変数値設定手段 2についても同様で、手続き型で記述された手続きの変数専用の変数値設定手段を備えるようにしてもよい。

[0063] 関数定義実行手段 10は、関数定義保持手段 9で保持された手続きを計算機に実際に実行させるものである。また、関数定義実行手段 10は、制約条件解算出手段 4 と相互にデータの入出力を行うことが可能であるように接続されている。

[0064] 本実施形態の制約条件解決装置 300の処理を具体例で説明する。 V、ま、制約条件として記述された制約式の中に、 y=sin (x)、または y=逆関数のない関数 (X)等が含まれて!/、る場合を想定する。

この場合、図 2に示すステップ S29において、変数 Xの値を求めるために x=sin )という式変形をして処理しょうとしたところ、逆関数 sin ¹の値領域の関係で X値を求めることが不可能なときがある。また、 y=逆関数のない関数 f (X)では、 y値から X値を求めることができない。このようなときに、従来の手続き型プログラミングによるユーザ関数を自由に取り入れて対処するようにする。

[0065] 例えば、制約式を解くにあたり、解決方法を複数の中から選択可能に記述することを許可するようにしておく。制約条件を a = f (b)とすれば、変数 bの値を求めるために、 {a = f (b) , b=f_re_V(a) }を用意し、どちらかが適用できれば制約式を解くことができるようにしておく。

また、 y=f(l, m)という制約式の変数 1, mの値が決まっていない場合、或いは y>x のような不等式の場合も、当該制約式を単純に解くことができない。不等式 y>xの場合で、 Xの値力となったとき、 yは nより大きいという情報のみが得られるだけで、変数 yの値は最終的な解が未確定とも、える。このようなケースでは制約条件の設定エラ一として処理してしまう他に、 y>nという情報^ yに関係する制約式にそのまま代入させて処理を続行させるようにしてもよ!、。 1つの方程式だけに注目すると解けな、z = x+yについても同様で、複数の式と複数の値との間で連立方程式を扱うように許可することで解決することちできる。

[0066] これにより、他の制約式の条件との関連で変数 yの値を限定できたり、より絞り込むことが可能になったり、或いは y>nがそのまま解として成立することもあるためである。このように、変数値として確定した値でなく不等式などをそのまま扱い、別の制約式で解決可能なときに可能な限り解決するようにする。つまり、このときの制約条件抽出手段 3は、図 9に示されるような関係にある解決方法を実行する。図 9における制約式の X値が変更されると、 Xへ代入する形式でな!ヽすべての式 (解決方法 1一解決方法 3)を実行していくというように、制約式の解過程に柔軟性をもたせ、手続き型プロダラミングを用いている従来のプログラムと同様、またはそれ以上の解決能力を持たせることが可能となる。

[0067] また、逆関数等の問題で制約式として表すことが困難な場合に力ぎらず、制約式として通常に表すことができる式についても図 9に示すような解決方法の形式に変形して保持するように構成すれば、処理実行時の速度を向上させることも期待できる。

[0068] このように、本実施形態の制約条件解決装置 300によれば、関数定義保持手段 9 及び関数定義実行手段 10を含むように構成したので、制約条件と従来のプログラミングで定義していた関数等とが融合し、対象問題の性質または特長に応じて制約条件としての解決方法、及び従来のプログラミング手法を用いた解決方法を、ユーザ側が自由に切替えながら設定することが可能となる。これにより、第 1の実施形態及び第 2の実施形態の制約条件解決装置 100, 200では解決できな、逆演算処理などを包含する制約条件の記述が格段に容易になる。

[0069] (第 4の実施形態）

前述した第 1の実施形態一第 3の実施形態の制約条件解決装置 100, 200, 300 の各構成手段に加え、本実施形態の制約条件解決装置 400は、データベースゃシステムリソース等力もの情報を適宜利用して変数値を設定できることを特徴としている図 10に本実施形態の制約条件解決装置 400の全体構成図を示す。

本実施形態の説明を簡略化させるために、第 2の実施形態の制約条件解決装置 2

00に付加した構成の制約条件解決装置 400により説明することとする。他の実施形態の制約条件解決装置にぉ、て、データベースやシステムリソース等からの情報を利用できることは言うまでもない。

なお、本実施の形態の制約条件解決装置 400の構成と、第 2の実施の形態における制約条件解決装置 200とで共通する構成部分については同一の符号を付して、詳細な説明を省略する。

[0070] 図 10に示すように、本実施形態の制約条件解決装置 400の構成によれば、制約条件内の変数の一部または全部が、前記データベース 11やシステムリソース 12内に記録されてヽる値や、時刻等の別の事象と連携されるシステム内の変数と連結することが可能となり、本制約条件解決装置 400外の変数と制約条件の変数との整合を図つた変数の管理を容易に行うことができるようになる。

[0071] 次に、制約条件の内容としてさらに複雑なデータ構造の変数を扱うことが可能な例をいくつか示す。以下の具体例は、前記第 1の実施形態一第 4の実施形態における制約条件解決装置 100, 200, 300, 400すべてにおいて実行可能である。

[0072] (変数に複数の値を定義した制約条件）

通常、変数へ値を代入する制約条件は、例えば、 x= 10のように記述するが、変数 Xに複数個の値を代入することを定義する。具体的には例えば、

x= { 10、 11、 12} ;

という記述を認める。この場合、変数同士の加減乗除の演算は、加算を例にすれば X +yは、各変数 X, yのそれぞれの要素について +演算を行うものとする。

[0073] (演算子が定義された配列構造の変数による制約条件）

いま、 1次元配列 vecを考える。この 1次元配列 vecを、 vec= 0, 200, 300}とし、 i番目（0≤i≤文字列長— 1)の要素に対するアクセスを vec [i]で表すこととする。 1 次元配列 vecの各要素は、 vec [0] = 50, vec [1] = 200, vec [2] = 300である。ここで、 1次元配列 vecl, vec2に対する演算子を次のように定義する。 vecl +vec2 …各々の 1次元配列の要素を全て加算した配列、

vecl-vec2 …各々の 1次元配列の要素を全て減算した配列、

vecl * vec2 …各々の 1次元配列の要素を全て乗算した配列、

vecl/vec2 …各々の 1次元配列の要素を全て除算した配列、

vecl =vec2 …各々の 1次元配列の要素が全て同一である配列の比較、もしくは代入、

vecl &vec2 …各々の 1次元配列の要素を全て連結した配列。

1次元配列に対する演算子をこのように定義することにより、前記第 1の実施形態一第 4の実施形態における制約式と同様に扱うことが可能になる。

配列構造の制約条件にアクセスするには、限定するものではないが、例えば図 21 に示すようなオペレータを用意すればよい。このオペレータには任意の関数を使用することが可能となって、る。

[0074] また、前記 1次元配列 vecの要素に対して柔軟性のあるアクセスを実現するために、 vec [i]において範囲指定が可能なようにする。具体的には、 vec [n. . m, 1. . k, i. . j]を、次元配列の n— m番目、 1一 k番目、及び i一 j番目の要素を取り出して並べた配列を表しているとすると、

vecl [0. . 3] =vec2 [0. . I] &vec2 [4. . 5] +vec3 [0. . 3]と! /、うような演算力 ^可能となり、 1次元配列を制約式 (制約条件)として扱うことができる。

[0075] 例えば、前記 1次元配列（ここでは、 strとする）の各配列要素に文字を格納すれば s trは文字列となる。文字列 str= "Hello World ！ "に対して、各 str [i]に任意の文字を代入することや、文字列 1 = "Hello "、文字列 2 = "World ！ "とすれば、文字列 str=文字列 1 &文字列 2で表される制約式を扱うことが可能となる。さらに、文字列のみの正規表現によるパターンマッチングや文字列置換を可能にするなどによつて、制約式をさらに柔軟に記述することが可能となる。

[0076] これを応用して、例えば、変数値の変更に従って出力が変化する Webによる HTM L (hypertext markup language)出力を以下のように記述することができる。

日付け ="2003/01/01" ;

名前 = "特許太郎"；

内容 = "長文文章"；

HTMLデータ = " < HTML> < BODY> "&日付 [0. . 3] &"年" &日付 [5. . 6] & "月" &日付 [8. . 9] &"日" &"名前：" &名前 &"内容：" &内容 & "く ZBODYX /HTML >，，；

[0077] (デフォルト変換規則を備えた制約条件）

任意のデータ変換についての変換規則を用意し、特にデフォルトで指定可能とする。

特に数値から文字列へ変換する場合、参照毎に変換関数を毎回用いる方法がある力データ変換規則のデフォルトを用意することにより、効率的な記述が可能となる。一例として、次のような規則を用意する。

•変換規則は必ず右詰めとする

•Sは符号を表し数が負の時のみ-を、それ以外の時は空白とする

•Xnは n桁以下の数を表す

•Ynは n桁固定の数を表す

•Znは n桁固定のゼロサプレスを表す

この時、例えば変数定義時に、

float("SX9.Y3") vail；

とすれば、符号付、仮数部 9桁以下、少数点、少数部 3桁固定で右詰めされた全 14 文字の文字列として vailを参照できる。

3;た、 unsigned int( 8 ) val2；

とすれば、 val2は符号無、ゼロサプレス付 8桁の全 8文字の文字列として val2を参照できる。

もちろん、値参照時に直接 val2("Z10")等として記述することでデフォルト規則だけではなく適用時に別の規則を適用できることとする。

このようなデフォルト変換規則を備えた制約条件による変換規則を定義することで、事務処理アプリケーション等における制約式を簡単に記述することができるようになる他のデータ構造にも同様に応用できたり、変換規則のフォーマットとして以上のものは 1例であり多種のものが存在することは言うまでもない。

(優先順位付き制約条件）

制約条件に重みを付加する場合の記述例を以下に示す。

{条件式 }[:優先順位] ;

or

{条件式 } [：優先順位]→{条件式が不成立時の処理 }；

ここで、複数の制約式条件が合致した場合、優先順位の値に従って実行すべき制約式が選択されるようにする。また、同じ優先順位の値が複数ある場合はすべて実行されるようにする。このような優先順位付き制約式を定義することで、優先順位の最も小さ、または大き、制約式のみを実行させたり、或、は制約式の実行順序を指定させたりする場合に有効になる。

[0079] (構造体による制約条件）

構造体 (抽象的なデータ構造）は、複数のデータ型をまとめて扱うことが可能である。前述した Web出力のデータをこの構造体で表現しょうとすると、

struct 構造体名 {

date 日付け；

name 名目 ij；

string 内谷；

}掲示板データ [] ;

のように表すことができる。実際の Webシステムでは、前記構造体のデータはデータベースやファイル上に存在することになり、前記構造体の場合、配列番号 5に関する "内容"に対するアクセスは、例えば、 "掲示板データ [5] .内容"により可能となる。なお、本構造体のデータのアクセスにおいて、メンバ（日付け、名前、内容、及び H TMLデータのこと）に対する文字列マッチングの演算子などを定義することによって、検索の処理を制約条件として記述することができるようになる。

[0080] (組み込み関数や追加演算子、規則追加による制約条件）

さらに前記の各種データ構造を利用して少し実用的な例題を示した図 12 (a)及び図 12 (b)を実現するために、いくつかの規則を追加する。なお、図 12 (a)及び図 12 ( b)は 1つの図で示すところ、便宜上、別図として示している。

組み込み関数や演算子、規則として、例えば以下のものを用意する。

•vsize (arg) …引数 argで与えられた配列の大きさを求める組み込み関数。

• inttostr (arg) · · '整数を文字列へ変換する組み込み関数。

•strtrunc (argl, arg2) —arglの文字列を複写する力 arg2で指定された文字列長より長い場合、その分の文字を切り捨て。

•配列範囲指定演算子 [ * ] · ··配列すベての要素を意味する。

·{}で囲まれたいくつかの制約式をブロックとしてまとめて処理する。 · [ $ i] …今までに登場した制約式のインデックス [i]と同等だ力ブロックでのみまとまった制約条件の中ですベて同じ値を持つ。ここでは通常の変数との識別のために i ではなく $ iとして記述している。

以上によって、たとえば以下のような記述が可能である。

•output_block[ * ] . output_html …配列内のすべての output_html (図 12 (a)参照)を並べた複数要素値列を意味し、文字列との比較、代入演算が行われる時は、すべての要素を連結した一つの文字列として扱われる、

•vsize (output— block) =list— count …配列数、すなわち配列サイズと変数との関係を示す制約式である。但し、 vsizeOで得られた値の参照は通常の数値である力変更は配列サイズの変更を意味する必要があるため、処理系の内部で値の変更が抽象化されたサイズ変更のための関数呼び出しを意味するように定義付ける力ォブジェクトによるメソッド呼び出し処理等の抽象化した処理が必要である。

[0081] 以上のような各種データ構造の制約条件を含む問題への入力データを与えるためには、該当の変数をユーザが直接変更したり、図 12 (a)に示した手続き型関数の bbs _additem ()を呼び出す等の処理を行うことになる。また図 12 (a) , (b)の例題では出力については前記 output— htmlを参照する。以上の処理によって、 Webサービスを実現することができるようになる。なお、出力を必ずしも HTMLフォーマットに限定する必要はなぐ任意のクライアント Zサーバシステムにおけるサーバ側の入出力サービスを同様の方法で実現することも可能である。

[0082] なお、これまで 1次元配列 vecを示して説明した力 2次元配列等の多次元配列への拡張はもちろんのこと、配列長が異なる配列同士の演算やこのような配列と数値との演算に関する定義が同様に行えることは言うまでもない。

また、前述したように、制約条件の内容としてさらに複雑なデータ構造の変数を扱うことが可能な例を示したが、これらデータ構造に完全に一致する必要はなぐ当業者であればこれら力類推できる変形例が含まれることは言うまでもない。

[0083] 以上説明したように、制約条件を単なる数値でなく各種のデータ構造をも扱えるようにしたので、現在格納されたデータと HTML出力の関係が制約条件 (制約式）によつて記述可能となり、 Webアプリケーションにおけるサーバ側のプログラムを制約条件だけで単純に記述することができるようになる。この Webサーノと組合せてデータ入力、表示を行うシステムの概念図を示したのが図 11であり、このときの関数型定義保持手段及び制約条件格納手段に格納する情報や、制約条件の一例を示したのが図 12 (a) , (b)である。

[0084] また、前述したような Webにおける HTMLに限らず、図 13に示すような一般のウインドウインタフェースでは各項目を変数にマッピングするように構成することで、データとユーザインタフェースとの関係を制約条件で記述することが可能となり、一般的なユーザインタフェースを記述しやすぐ且つ理解することが容易となる。これにより、従来のプログラミング方式と比較して高い生産性を実現することができる。

[0085] <本発明の他の適用例：アプリケーションプログラム構築、トランザクション処理 > 次に、 WEB上の入力インタフェースを用いて任意のアプリケーションプログラムを構築する問題、または任意のデータが蓄積されたデータベースを検索する際のトランザクシヨン処理問題に本発明が適用可能であることを説明する。

前記第 1の実施形態一第 4の実施形態における制約条件解決装置において、制約条件により解決していく処理手順及び処理内容を、履歴情報（更新履歴）として持つことにより、アプリケーション上のユーザインタフェースの概念の 1つにある UNDO機能、或、はデータベースのトランザクションを実現することが可能となる。

[0086] この UNDO機能、或いはデータベースのトランザクション処理を実現できるようにすることで、データの更新力始まってデータ変更に伴う制約解を求める一連の動作が行われな力つたものとすることが容易に行える。これにより、制約条件のデータ値を一部変更して入力データに含まれる誤りを発見するという入力データの確認や、そのキヤンセル時における元のデータ値に復帰させるための処理を確実かつ迅速に行うことができるようになる。

[0087] 次に、 GUI環境における基本的な画面構成要素であるウィンドウを用いたウィンドウシステムまたはマルチウィンドウシステムに本発明が適用可能であることを示す。ここでは、図 14に示すようなウィンドウシステムを一例に説明する。なお、図 14では 3つのウィンドウを示しているが、任意個のウィンドウを扱えることは言うまでもない。

[0088] 図 15は、ウィンドウシステムを実現するクライアント Zサーバシステムにおけるクライアント側の構成を概念的に示す図である。サーバ側のシステム構成については図 1、 3、 8、 10に示すものと同様であるので省略する。

図 15に示すように、 GUIクライアントは GUI処理部と GUI制御部を有し、 GUI制御部は図 16に示すような各パーツの動作を制御する。

ここでの GUI制御部の中身は、図 1、 3、 8、 10と同様の構成を持ち、各パーツの状態変更は、クライアント内の図 1、 3、 8、 10の入出力 IZFに対する IZF制御部に対して行われる。制約条件として、各パーツ間の連携規則、クライアントで処理するべき入力データの整合性チェック、入力補助、サーバ側へ渡すべきデータへの加工規則などが記述され、処理される。

GUI制御部でカ卩ェされて処理されたデータは、伝達用の変数を介してサーバへと伝えられる。

もちろん、クライアントの GUI処理部分とサーバの制約処理系をまとめて 1台で処理するなど、システム構成が柔軟に変形して使用できることは言うまでもな、。

なお、本発明の特徴である変数の値変更に応じた制約条件の逐次解法の機能は、クライアント Zサーバシステムの全体として有する他、前記 GUI制御部にお、ても有している。また、クライアント Zサーバ間のデータ転送は、独自形式でもよいが、 XML を使用する等、標準化したデータ形式を用いることで従来手法と互換性のあるォープンなプロトコルを実現することが可能である。

[0089] このように、 GUI側では、 GUIの動作制御、伝達するデータの整合性の確認、入力補助、データの状態に応じた GUIの状態変更、及びサーバ側への通知処理などを制約条件の記述に基づ、て行うことができる。

[0090] 次に、ウィンドウの動作について詳しく説明する。各ウィンドウ内の構築は、前述した各種のデータ構造の扱、を許可する制約条件の設定や、 UNDO機能或いはデータベースのトランザクション処理を実現できるユーザインタフェースによって可能である 1S このウィンドウ自体の動作は次のようにして記述する。

[0091] ウィンドウの情報として、例えば次の構造体を定義する。

struct {

x, y; サイズ x, y；

表示中フラグ；

}ウィンドウ情報 [] ;

なお、ウィンドウ情報 [0]…アプリケーションお

ウィンドウ情報 [ 1]…アプリケーション 2、

ウィンドウ情報 [2]…アプリケーション 3を表すものとする。

これらの変数値の参照更新は、図 10のシステムリソース 12と同様の扱いとし、実際の GUIシステムのウィンドウと連動させるものとする。

[0092] アプリケーションを実行する画面上に表示されて、るウィンドウの動作 (表示 Z非表示、移動、サイズ変更)を制約条件で記述しょうとする場合の一例を次に示す。

(a)ウィンドウ nの表示 Z非表示

画面上にウィンドウを開く（表示）…ウィンドウ情報 [n] .表示中フラグ =true、画面上のウィンドウを閉じる (非表示）…ウィンドウ情報 [n] .表示中フラグ =false、また、画面上にウィンドウを閉じるための「closeボタン」があるときは、例えば、ウィンドウ情報 [n] .表示中フラグ = ！ closeボタンの状態（！は not演算子）とすればよい。

(b)ウィンドウ nの移動

ウィンドウ情報 [n] .位置. x=移動したい Xサイズ；

ウィンドウ情報 [n] .位置. y=移動したい yサイズ；

(c)ウィンドウのサイズ変更

ウィンドウ情報 [n] .サイズ. x =変更したい Xサイズ；

ウィンドウ情報 [n] .サイズ. y=変更したい yサイズ；

[0093] その他、アプリケーション 1の右にアプリケーション 2を隣接するようにするには、ウィンドウ情報 [1] .位置. x=ウィンドウ情報 [0] .位置. x+ウィンドウ情報 [n] .サィズ. X；

ウィンドウ情報 [1] .位置. y=ウィンドウ情報 [0] .位置. y;とすればよい。また、ウィンドウのサイズを固定にするには、変数に変更可能 Z不可能の属性を用意した上で、ウィンドウ情報 [n] .サイズ. x、ウィンドウ情報 [n] .サイズ. y、を変更不可能にすればよい。 [0094] このように、 GUI環境におけるウィンドウシステムまたはマルチウィンドウシステムにぉ、て、従来のプログラミング手法ではウィンドウの動作及びウィンドウ内のアプリケーシヨン動作をイベントが発生したらそのイベント状況に依存する関連動作を逐一記述しなければならな力つたのに対し、本発明による動作制御によれば単純明快な制約条件に基づいてアプリケーションの複雑な動きを簡潔且つ容易に記述することがでさるよう〖こなる。

[0095] なお、ウィンドウシステムにおける動作を制約条件の記述によって制御可能なことを GUI環境で前述した力データを画面上に出力する場合に用いるだけでなぐウィンドウを用いて処理した内容を任意の媒体 (例えば、紙）に出力する出力システム (例えば、帳票印刷システム)を実現する際にも本発明を適用することができることは本発明の技術分野における当業者であれば容易に想到できることは言うまでもない。また、前述した説明では、クライアント Zサーバシステムにおける具体例を示したが、必ずしもクライアント Zサーバシステムである必要はなぐクライアントとサーバとをそれぞれ別個のシステムとして構築し、クライアントのみまたはサーバのみに前述した処理が行えるように構成してもよ、。

[0096] <本発明の他の適用例:並列化処理と構築された計算機システム >

また、本発明は、手続型プログラミングで面倒な問題である並列化処理の問題に適用することが可能である。並列処理においては、大きく分けて 2種類の動作が考えられる。すなわち、いくつかの CPUがステップ S23—ステップ S30のアルゴリズムを実行する方法と、データフローマシンのようにアーキテクチャで変数と関係式を構築してしまう方法である。

[0097] 前者の場合、通常の手続型プログラミング手法で並列処理を行おうとすれば、アルゴリズムを構築する段階で、ユーザは CPUの並列動作を意識しながらプログラミングの処理手順を分割して記述しなければならな、。これに対して本発明を用いた並列化処理の場合は、図 2のアルゴリズム中にあるステップ S22による変数値の変更から開始されるステップ S23—ステップ S30の処理を並列に動作させるだけで、ユーザは直接並列処理を意識することなく並列処理を実現できる。

[0098] 具体的には、前記第 1の実施形態一第 4の実施形態における制約条件解決装置において、ある処理に対するステップ S23—ステップ S30の実行中にも、別の処理に関してのステップ S22による変数値の変更による一連の動作を実行させることを行つている。

実際上、従来の手続き型プログラミング手法における並列アルゴリズムの実装と同様に、この並列処理の実行中においては各変数間で排他制御や同期制御を実現する必要がある力従来の手続き型プログラミングでの手法をそのまま適用することができる。

[0099] 後者のアーキテクチャで変数と関係式を構築する場合、変数間の関係式は、例えば並列計算機上に物理的に実現した時の通信路となる。この並列計算機上では、並列プロセッサが複雑な通信路によって結合されており、通信コストが経路によって異なる。この通信コストを優先度で表わすことによって、データ経路を自動的に選択することが可能である。優先順位につ、ては、制約条件の一例として挙げた (優先順位付き制約条件)を用いることができる。このような並列処理と同様の方法で、一般に構築されたシステム全体に本発明を適用することが可能である。

なお、ここでいうシステムとは、複数の特性の異なる計算機や用途別専用機と、それらを結合するネットワーク力構成される複合物を意味しており、いわゆる一般の企業システムや社会システムを旨す。

[0100] つまり、本発明をシステム全体へ適用する場合、概念的には、前記データフローマシンでの並列処理実現方法と非常に似たものとなり、本発明によって構成される計算機は、計算機間のインタフェースとなる変数を介して別の計算機のインタフェースである変数と結ばれる。変数間の関係式が通信路であり通信コストが優先度であり、したがって本発明によって前記システム全体を設計し構築することができる。

[0101] <本発明の他の適用例:既存プログラミング言語との融合 >

これまで説明してきたように、本発明は任意の制約条件から構成される問題を、外部 (ユーザ等)からの指示 (イベント)を契機に変数の値を変更して制約伝搬によって解決するイベント駆動型の計算実行原理を扱って、る。前述したように関数定義保持手段や関数定義実行手段において既存の手続型プログラミング言語を利用する等から明らかなように、図 18にも示したが既存のプログラミング言語との組み合わせ可能なことを前提としている。そこで、本発明を既存プログラミング言語へ融合することが可能であることをさらに詳述する。

[0102] なお、ここまで説明のために、プログラミング言語を分類した場合に、 1つは手続型プログラミング、別の 1つは宣言的プログラミングであるとして大別してきた力実際にはもつと細かなプログラミング言語の分類が存在する。すなわち、宣言的プロダラミング言語に対する非宣言的プログラミング言語には、手続型プログラミング言語と並ぶプログラミング言語としての関数型プログラミング言語が含まれている。以下、本発明と関数型プログラミング言語との融合にっ、て扱う。

[0103] (A)関数型プログラミング言語との融合

ここでは、関数型プログラミング言語として最も歴史があり代表と言える LISP言語 (Common LISP)との自然な融合方法について述べる。いま、 2つの変数 a, bの初期値、及び制約条件として、

a= { l l, 12, 13}

b= { l, 2, 3}

a[ $ i] = b[ $ i] + 10

を定義するとする。 a, bの値は共に 3つの要素を持つ配列である。また、本発明の実

、て制約式を定義する関数 defconstraintを新たに定義し、変数への代入をシンボルへのバインドに対応させるとすれば、 LISP言語では次のように記述できるだろう。

(set 'a # (11 12 13》

(set 'b # (1 2 3))

(defconstraint '(= (aref a $i) (+ (aref b $i) 10》 …（式 18)

[0104] ここで、関数 defconstraintは、図 9のデータ構造を実現するために引数からシンボル (変数) aと bに関する解決式を作成し、

(defconstraint2 (= (aref a $i) (+ (aref b $i) 10))

'(setf (aref a $i) (+ (aref b $i) 10))

'(setf (aref b $i) (- (aref a $i) 10)))

を実行して、関数 defconstraint2が図 9のデータ構造を維持する。式のデータ構造としては図 6等のデータ構造でよいのだ力 LISPでは LISP自体の機能のみで構造を自然に記述することができるので、ここではこの LISPの特徴を生かして上記のような式を記述している。

[0105] C言語のポインタ等についても同様なことが言えるのだ力 LISP言語においては各データが共有されている可能性があり、変数とデータとの関係が 1対 1であるとは限らない。このため、あるデータを変更する時にそれが特定のシンボルに関係している力どうかは変数へ値を代入する時にはわ力もないのが通常である。したがって、このような変数とデータとの関係構造は、本発明の制約解消を実現する際には問題となるので、これを説明する。

[0106] いま、シンボル bと同じデータを指すシンボル cをカ卩えて、シンボル a,b,cを中心とした通常の LISP言語の内部データ構造を極単純化した一例を図 22に示す。 LISP言語では、すべてのシンボルはノッケージに記録され、名前空間別に保存されているのでここではパッケージ力も記述している。また、標準の名前空間名は「user」であるため、シンボル a,b,cは「user」に登録される力この例ではシンボル bは別のパッケ一ジにも登録されている。

[0107] LISP言語で、 b[l]=12を実行する場合、

(setf (aref b 1) 12)

を実行する力値の代入を実行する関数 setfは上記の関数 defconstraint2で定義された制約式とマッチングさせる必要がある。一方、関数 setfに渡されるデータは、通常の LISPでは図 22中の（ * )で示すポインタであり、マッチングさせるべき情報は存在しない。そこでこのような単純な例の場合、関数評価時に評価結果だけではなぐ評価した式の情報を関数 setfの実行時まで持ちまわる方法が考えられる。しかし、実際には非常に複雑な式になるため持ちまわるデータが巨大になることや、（setf (aref c 1) 12)で b[l]が変更された場合に対応が難しくなる。

[0108] これを解決するためには、 LISP言語の基本データ構造をすベて双方向に迪れるように構成すればよい。そのデータ構造を一例として図に示すと、図 23のようになる。図 23中の（* )で示した関数 arefによる配列参照は、逆方向へ迪れるように配列内のポインタだけではなぐ配列そのものの情報も持つ。配列情報を含むすべてのデータは、バインドされて、るシンボルの情報を追えるように各種情報を保存する。

[0109] また、実際にはシンボルまでのみならず登録されたパッケージ情報まで迪らなければならず、したがって制約式のシンボルはパッケージを考慮する必要がある。（* )から b[l] (パッケージを含めて user:b[l])を迪る時の道順を図 23では太線の矢印で示している。

[0110] まお、 Common LISPのシンボルにはもともとホームパッケージの情報を持つ力 1つのシンボルが複数のパッケージに保存されることがある。このため登録されたすベてのパッケージを追うことができる新たなデータ構造の追カ卩が必要となる力このようにすれば、 setfの実行時に制約式のマッチングを検査することができるようになる。以上説明したように、本発明を LISP言語を代表とする関数型プログラミング言語と完全に融合させて自然に扱うことは可能である。

[0111] 前記 (A)の関数型プログラミング言語との融合によって、 LISP言語上で本発明を適用することができるようになり、関数型プログラミング言語上への実装としては理想的になる力例えば setf等の代入操作が実行される度に制約式のマッチングが必要となることから原理上、実行効率が悪くなる。特に、代入時の逆方向の制約式とのマツチング (逆方向のマッチング）に際しては、力なり上の方まで遡らなければ、該当する制約式の定義が存在するかどうかわ力もない。例えばポインタの時点でわ力るのは [1]等のインデックス情報だけである力単純な制約式でさえ _a[x]、 b[x]のような構造をして、るため、インデックス情報だけではマッチさせるべき制約条件が存在するかどうかを判断できるのは限定された特殊条件の時だけとなる。

[0112] これに対して、シンボル名（変数名）から迪るマッチングの場合、多くの場合で制約条件が存在するかどうかが最初力もわ力つており、変数 (シンボル)そのものにそれらの情報を付加させることによって処理の高速ィ匕が可能である。

また、実際の制約式は a[x]等の単純な例が登場することは少なぐ逆方向とのマツチングは常に相当に複雑な式をかなり上方、おそらくは完全に迪る必要がある。これを実際の Common LISPの複雑なパッケージ機構上に実装することを考えると、実装は実に複雑となり、実行時間については様々な方法によって多少の改善は期待できることを考慮しても、変数力開始する制約式のマッチングに比べて明らかに実行効率は非現実的なまでに悪くなつてしまう。

[0113] そこで、現実的解決方法として、完全な融合をあきらめて、制約条件を使用する場合は、専用の式処理機構を用意してその中では必ず変数 (シンボル)力し力値を参照できない制限を加えれば前述した問題を防ぐことができる。例えば、文字列データを」で括って表わして、るように、式データをデータ型の一つとして抽象化して例えば「？」で括って表現し、専用の式処理機構を実行する関数 pevalを定義し、代入式を関数 peval内で実行するならば、前記式（18)は、

(peval '？ a={ll, 12, 13}?)

(peval '？ b={l, 2, 3}?)

(defconstraint '？ a[$i]=b[$i]+10?)

と記述できる。そして、 b[l]=12を実行する場合は、（peval '？ b[l]=12?)を実行すればよい。

[0114] この場合、必ず式処理の中では変数 (記号)からの参照し力、行えないことにするため、逆方向のマッチングは必要ないので、前述した (A)で述べた LISP言語上での実装の問題は発生せず、さらに LISP言語の他の機能にはまったく影響を与えないため実行効率の問題が解決する。

[0115] ただし、プログラミング言語としては、言うまでもなくとても不自然である。そこで、プログラミング言語の文法そのものを新しく定義して、代入操作時に専用の式処理機構を自然に使わせるように解釈するパーサー (構文解析器)を用意すればょ、。これは、入力時に文法を構文解析して LISPである内部表現に置き換えるので、本来の LIS P言語とは違うものであるが、 LISP言語の良、ところと本方式を組み合わせた実行効率が著しく低下しない能力を持つプログラミング言語の実現が可能となる。

[0116] なお、ここでは、式評価は常に peval関数の中で行うことを基本とした、最もメジャーな C言語風の文法を持つプログラミング言語の基本要素を示すことによって、 peval関数を自然に使わせる方法について述べる。変換後を見ればわかるように、 C言語風の文法を持ち C言語同様の記述ができるとはいえ、本質的には LISPであり、 LISPの柔軟な記述能力を持っているという優位性がある。さらに、純粋な LISPプログラムとも完全に混在させて実行することができる。 [0117] 本システムの基本単位と言える関数を含む式の解釈実行は次のように翻訳する。なお、ここでは型宣言に関しては本質的に関係ないため省略している。

入力：

a[l] = foncl(lOO);

実行関数：

(peval '？ a[l]=foncl(100)?)

[0118] C言語の基本構造である局所変数を持つブロック構造は次のように解釈する。

入力： int X, y;

x= 10;

y=20; 実行関数：

(let (x y)

(peval '?χ=10?)

(peval '？ y=10?》

[0119] C言語の大まかな基本要素をすベて含む、局所変数とループ構造を持つ関数は次のように解釈する。

入力：

int ί( int V ) int l, n = v;

for (i = 0; iく 10; i++)

n++;

return n; 実行関数: (delun f (v)

(let (i, n)

(peval '？ n=v?)

(prog 0

(peval '？ i=0?)

loop

(if (not (peval '？ i〈10?))

(return nil))

(peval '？ n++?)

(peval '？ i++?)

(go loop)

(return- from f n)))

[0120] 式の解釈と実行方法は様々なものが考えられ、これらの変換方法はほんの一例でしかないが、変換方法についてはすでに確立された様々なコンパイラ技術が適応できることに留意されたい。このように、制約式の関係する式実行を自然に関数 pevalで置き換えて実行する、本発明と LISPの特徴を組合せた極めて強力なプログラミング言語を設計することは可能である。これを用いて、関数型言語と融合させた強力なプログラミング言語で図 12 (a) , (b)を記述することで、本発明の図 3,図 8,図 10に示した制約条件解決装置が現存する手続型、関数型プログラミングの機能を網羅しながら実際の実行効率を落とさずに実行することが可能となる。この際、図 21に示すォペレータは、関数 PEVAL内の式処理で実現されることとなる。

[0121] <本発明の他の適用例:設計手法との組み合わせ >

また、本発明は、設計手法に組合せて適用することが可能である。開発設計手法には、実に様々なものがある力どのような方法であれ、まず実現したい要求を分析し、次に要求を実現するために開発するターゲットの仕様を決定し、そしてその仕様を満たすプログラムを開発することが共通的な概念としてある。しかしながら、従来の手続き型プログラミング手法の場合、どの開発手法であっても最終的には CPUの動きをプログラムコードとして記述しなければならな力つた。一方、宣言的プログラミング手法はこの問題を解決する可能性を秘めているが、冒頭で述べたように計算機の実行効率が良くないという問題が大きい。そのため、現在の一般的プログラミング作業と V、えば、手続き型プログラミング手法のことを指すことが多、。

[0122] さて、システム設計手法のひとつとして、データ中心指向がある。データ中心指向は業務システムをうまく設計できる方法として知られて、るが、これによつて要求を実現するシステム設計を行ったとしても、最終的にはコーディング作業が必要であり、プログラムコードとして CPUの動きを記述しなければならない。 CPUの動きの記述については、ソフトウェア工学が発達した現在でも本質的にはプログラマーの経験と勘に頼っており、未だ人間の創造的作業の領域内に存在する開発設計作業が大変であるのが現状である。開発設計作業を低減させる道具として CASEツール等がある。しかし、これらは開発作業を軽減することはできても、人間が CPUの動きを記述することを不要にするという本質的な問題については依然として解決できていな力つた。

[0123] そこで従来の手法では、前記本質的問題の解決には目をつぶる代わりにプロダラムコードを再利用することに重点を置いている。例えばソフトウェアのライブラリイ匕ゃォブジェクト指向プログラミング言語は、この再利用を目的として概念化され生み出されてきたのである。

[0124] これに対して本発明は、計算機の動きを考慮する必要があるものの、従来のような複雑な動きを考慮する必要が全くない。つまり、プログラマ一は各種設計手法に共通する問題である CPUの動きを直接記述する作業力解放され、コーディング時での創造的作業を行う必要がない。したがって、本発明によれば、 CASEツール又は CA SEツールに類似したツール及びその他ツールの発展形として、仕様からプログラムコードを自動生成させることが可能となり、自動プログラミングを実現することができる

[0125] もし計算機単体ではなくシステム全体を本発明によって設計開発するならば、広大なシステム全体を自動生成させることも可能である。この場合非常に多くの変数と関係式が使用されるが、従来の設計手法と同様に、トップダウン的設計手法又はボトムアップ的設計手法が実現できたり、さらには機能による領域分割を行うことや、分割された領域を再利用することも可能であることは言うまでもない。また、本発明がどのような開発設計手法についても共通して適用できることは言うまでもない。

[0126] <本発明の他の適用例：グラフィックデータやロボットへの応用 >

本発明の更なる適用例として、コンピュータグラフィックのモデルやロボットの関節等の可動部への応用について説明する。ここではロボット制御の精度といった本発明と直接関係な、複雑な問題は省略して、連結された関節の扱いにっ、てのみ説明する。

いま、結ばれた点 a,eの間に 4つの関節 A, B, C, Dがあるとして、関節 AB間の位置を b、関節 BC間の位置を c、関節 CD間の位置を dとすれば、 a— e間の関係はこれら 5つの点で表現することができる。各点が（X, y, z)の 3つの座標を持つベクトルで表わされた 3次元の場合、各関節の回転の動きは 3 X 3の回転行列で示される。なお、この回転行列にさらに並行移動成分を入れて 4 X 4行列としてもょ、。

[0127] 本問題を単純ィ匕するために、各点間の長さ等を省略した単なる回転のみを制約式で表すとするならば、

b = a水 A · ·· (a)

c = b * B •••(b)

d=c * C - -- (c)

e = d* D · ·· ((!)

となる。ここで、 A, B, C, Dは対応する関節の回転行列を示す。

[0128] 通常、関節の移動範囲には制限があるため各回転行列 A— Dの値にも制限があり、ユーザはこの制限を制約式で記述することになる。もし、 aが固定されていて関節 B が変化した場合、前記 (b)→ (c)→ (d)の順の制約伝搬が実行されることが必要である。また、もし、固定された aに対して動力したい位置 eがある場合、この制約伝搬によつて、各回転行列 D, C, B, Aの必要な回転成分だけが修正されて自動的に定まる。ここで aが固定されていることは、制約条件として固定されていることを示す変数を追加するか、システムの変数や関係式へ属性として持たせること等で実現できる。そこで、回転行列 A— Dをそれぞれ関節を制御するモーター等の角度とするとこれは口ボット制御に適用することができる。また、 3次元座標 a— eを透視変換してディスプレイデバイス等へ描画させれば、これはコンピュータグラフィックへ適用する場合とまつたく同様にある。

[0129] このようなロボットの関節等の可動部へ本発明を適用する場合、現実的にはもつと複雑になるが、それでも手続型プログラミング手法での実現よりは格段に単純で自然な形で実現することができる。なお、ロボットの関節等の可動部への適用例はあくまでも一例に過ぎず、関節に類似した任意の問題をうまく解決できることは言うまでもない

[0130] <本発明の他の適用例:化学分野、物理分野、シミュレーション分野への応用 > また、本発明の更なる適用例として、化学分野への応用について説明する。

化学式を扱う場合には様々なモデルィ匕が考えられるが、ここでは説明のために簡単ィ匕して本発明に直接関連する内容のみを説明する。

[0131] 化学式における各元素をオブジェクトとして扱うために、元素の種類別にクラスとして定義し、使用したい元素を必要に応じてインスタンス化する。各元素オブジェクトは、制約条件として他元素との結合条件や元素の性質を持つことにする。また、元素の組合せは化合物オブジェクトで管理し、元素オブジェクトをィ匕合物オブジェクトへ登録することによって表すようにする。化合物オブジェクト内では、組合せた時の性質や組合せ条件を制約式で持つことにする。このように構成することによって、ユーザはォブジエタトの糸且合せを自由に変更できる力一方で制約条件によって不可能な糸且合せは禁止され、そして元素の変更が成功した時にはこれに応じて化合物の性質も更新されたことを知ることができる。また、この時、例えば元素オブジェクト内に電子の状態を変数 (属性)として持っているならば、電子変数に関する制約伝搬が発生して、物理現象である電子の挙動を表すことができる。

[0132] 以上説明したように、本発明は化学現象や物理現象等を効率的に表すことができるが、これはある状況のモデル化と、事象の発生に対する現象のシミュレーションであり、変数値の変更に対する制約解消それ自体が特定の現象そのものとなって、る。なお、化学現象や物理現象等に限らず多くのシミュレーション分野で本方式が効果的に使用できることは言うまでもない。

[0133] <本発明の他の適用例：線形計画法 (シンプレックス法等)への応用 >

また、これまでの説明から、本発明が、典型的にはシンプレックス法等の線形計画法、整数計画法、輸送問題などに記載される制約条件において、対象問題に関する制約伝播の処理手順が考慮された制約条件をユーザが入力することができる場合であれば適用可能であることは当業者であれば明白である。

[0134] <本発明の他の適用例：ニューラルネットワークへの応用 >

ニューラルネットワークにおける-ユーロンモデルは、閾値を変数として制約式で記述することができる。この観点で見るならば、ニューラルネットワークの-ユーロンモデルの結合は、本方式で扱う制約式関係の特殊形であり、サブセットとみなすことができる。

ニューラルネットワークでは、求めたい結果を得るためにネットワーク内の各-ユーロンモデルの閾値を決定することを学習と呼ぶ力この学習では所望の結果を得るための閾値をどのようにして設定させるかが課題であった。そしてその学習方法といえば、本方式に対する従来の制約プログラミングに概念的に近いものであった。しかし

、ニューロンモデルの閾値の設定は変数の値を設定する作業であり、本発明で述べてきた方式によるプログラミングと見なすことができる。従って、本発明をニューラルネットワークへ応用することができる。すなわち、本発明によって、値を自動調整させるだけではなぐ動きを考慮して一部あるいは全部の閾値を設定することによる学習方法を実現することができる。

[0135] なお、前述した内容はあくまでも本発明の技術思想を説明するための一例であってこれらに限定されることはなぐ本発明の技術思想を実現するにあたり、本発明の技術分野における通常の知識を有する者が、制約条件解決装置の各構成や制約条件の定義の方法を追加'変更しても本発明の根本的な技術思想は不変であることには変わりはないことは明らかである。

[0136] また、本発明の目的は、前述した実施形態の制約条件解決装置 100, 200, 300, 400の機能を実現するソフトウェアのプログラムコードを記憶した記憶媒体を、システム或、は装置に供給し、そのシステム或いは装置のコンピュータ（または CPUや MP U)が記憶媒体に格納されたプログラムコードを読みだして実行することによつても、達成されることは言うまでちな、。

[0137] この場合、記憶媒体力読み出されたプログラムコード自体が本実施の形態の機能を実現することとなり、そのプログラムコードを記憶した記憶媒体及び当該プロダラムコードは本発明を構成することとなる。プログラムコードを供給するための記憶媒体としては、 ROM、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、 CD-ROM, CD-R,磁気テープ、不揮発性のメモリカード等を用いることができる。

[0138] また、コンピュータが読みだしたプログラムコードを実行することにより、上記本実施の形態の機能が実現されるだけでなぐそのプログラムコードの指示に基づき、コンビユータ上で稼動して、る OS等が実際の処理の一部または全部を行、、その処理によって本実施の形態の機能が実現される場合も含まれることは言うまでもない。図面の簡単な説明

[0139] [図 1]本発明の第 1の実施形態における制約条件解決装置の基本的な構成要素を示す全体構成図である。

[図 2]本発明の第 1の実施形態における制約条件解決装置の動作手順を示すフローチャートである。

[図 3]本発明の第 2の実施形態における制約条件解決装置の全体構成図である。

[図 4]第 1の実施形態における制約条件解決装置の制約条件格納手段が計算機の記憶領域へ制約条件を格納する形態例を示す図である。

[図 5]会計計算問題に関するデータ構造の一例を示す図である。

[図 6]会計計算問題に関する制約条件の格納形態の一例を示す図である。

[図 7]データ構造の一例を示す図である。

[図 8]本発明の第 3の実施形態における制約条件解決装置の全体構成図である。

[図 9]制約条件抽出手段による解決方法の実行手順を示す図である。

[図 10]本発明の第 4の実施形態における制約条件解決装置の全体構成図である。

[図 ll]Webサーバと組合せてデータ表示を行うシステムの概念図である。

[図 12(a)- (b)]図 11に示すシステムにお、て、関数型定義保持手段及び制約条件格納手段に格納する情報や制約条件の一例を示した図である。

[図 13]—般のウィンドウインタフェースにおいて、データとユーザインタフェースとの関係を制約条件で記述する一例を示した図である。

[図 14]マルチウィンドウシステムの一例を示す図である。 [図 15]ウィンドウシステムを実現するクライアント Zサーバシステムにおけるクライアント側の構成を概念的に示す図である。

[図 16]GUIクライアントにおいて、 GUI制御部が各パーツの動作を制御することを説明するための図である。

圆 17]従来の宣言的プログラミング手法における解法手順を示す図である。

圆 18]従来のプログラミング言語環境と、本発明の制約条件の解を求める制約解消系との位置付けを概念的に示した図である。

[図 19]従来のプログラミング言語環境の構成を概念的に示した図である。

圆 20]データ定義と制約式をまとめたクラス化に関する概念を示じた図である。

[図 21]配列構造の制約条件にアクセス際のオペレータ例を示す図である。

[図 22]通常の LISP言語の内部データ構造を極単純ィ匕した一例を示す図である。

[図 23]LISP言語の基本データ構造を双方向に迪ることができるようにした一例を示す図である。

圆 24(a)-(h)]ユーザが制約条件及び値を入力し、計算結果などを出力する画面例を示す図である。

符号の説明

1 制約条件入力手段

2 変数値設定手段

3 制約条件抽出手段

4 制約条件解算出手段

5 変数値再設定手段

6 制約条件格納手段

7 変数値格納手段

8 制約条件抽出手段

9 関数定義保持手段

10 関数定義実行手段

11 データベース

12 システムリソース 100 制約条件解決装置 200 制約条件解決装置 300 制約条件解決装置 400 制約条件解決装置

Claims

請求の範囲

[1] ユーザにより対象問題に関する制約伝播の処理手順が考慮された制約条件を入力する制約条件入力処理と、

前記制約条件入力処理により入力された制約条件に用いられる変数の初期値または変動値を設定する変数値設定処理と、

前記制約条件入力処理により入力された制約条件の中から、前記変数値設定処理により設定された値に関係する制約条件を抽出する制約条件抽出処理と、前記制約条件抽出処理により抽出された制約条件全てに対して、前記ユーザにより考慮された制約伝播の処理手順に基づいて前記変数の初期値または変動値を代入して当該制約条件の解を算出する制約条件解算出処理と、

前記制約条件解算出処理により算出された解を前記変数値設定処理での新たな変動値として設定する変数値再設定処理とを含み、

前記変数値再設定処理は、再設定される新たな変動値が存在する間は、前記制約条件抽出処理及び前記制約条件解算出処理を繰り返し行うことを特徴とする制約条件解決方法。

[2] 前記制約条件入力処理により入力された制約条件を格納する制約条件格納処理と、

前記変数値設定処理により入力された変数の値を格納する変数値格納処理とをさらに含み、

前記ユーザにより前記制約条件または前記変数値の追加、変更、削除が行われると、前記制約条件抽出処理は、前記制約条件格納処理または前記変数値格納処理により格納されて、る制約条件または変数値と比較して、相違が生じた制約条件のみを抽出することを特徴とする請求項 1に記載の制約条件解決方法。

[3] 手続き型または関数型のアルゴリズムを設定可能な関数型定義保持処理と、前記関数型定義保持処理により設定されたアルゴリズムに基づいて、前記対象問題を手続き型または関数型で解決することを可能にする関数型定義実行処理とをさらに含むことを特徴とする請求項 1または 2に記載の制約条件解決方法。

[4] 前記変数値設定処理及び前記変数値再設定処理により設定される変数は、数値のみならず、文字、文字列、抽象的なデータ構造、組み込み関数を包含するデータ

、及びオブジェクト型データ構造の少なくとも何れかを含むことを特徴とする請求項 1 一 3の何れか 1項に記載の制約条件解決方法。

[5] 前記対象問題が、 WEB上の入力インタフェースを用いて任意のアプリケーションプログラムを構築する問題、または任意のデータが蓄積されたデータベースを検索する際のトランザクション処理問題であって、

前記対象問題を前記制約条件により解決して!/ヽく処理手順及び処理内容を、履歴情報として保持する履歴保持処理を含むことを特徴とする請求項 1一 4の何れか 1項に記載の制約条件解決方法。

[6] GUI環境における基本的な画面構成要素であるウィンドウを用いたウィンドウシステムまたはマルチウィンドウシステム、または前記 GUI環境におけるウィンドウを用いて処理した内容を出力する出力システムにおいて、前記アプリケーションプログラムの構築処理を行うことを特徴とする請求項 ₅に記載の制約条件解決方法。

[7] 制約条件を入力する制約条件入力処理と、

前記制約条件入力処理により入力された制約条件に用いられる変数の値を設定する変数値設定処理と、

前記制約条件入力処理により入力された制約条件の中から、前記変数値設定処理により設定された値に関係する制約条件を抽出する制約条件抽出処理と、前記制約条件抽出処理により抽出された制約条件の解を算出する制約条件解算出処理とを含む制約条件解決方法にお！ヽて、

前記制約条件は、現在の配列要素数を含んでいること、前記変数に複数個の値を持たせること、構造体配列の要素値による検索を含んでいること、及びデフォルト規則による文字列数値変換の少なくとも何れかを特徴として構成される制約条件解決方法。

[8] ユーザにより対象問題に関する制約伝播の処理手順が考慮された制約条件を入力する制約条件入力手段と、

前記制約条件入力手段により入力された制約条件に用いられる変数の初期値または変動値を設定する変数値設定手段と、前記制約条件入力手段により入力された制約条件の中から、前記変数値設定手段により設定された値に関係する制約条件を抽出する制約条件抽出手段と、前記制約条件抽出手段により抽出された制約条件全てに対して、前記ユーザにより考慮された制約伝播の処理手順に基づいて前記変数の初期値または変動値を代入して当該制約条件の解を算出する制約条件解算出手段と、

前記制約条件解算出手段により算出された解を前記変数値設定手段での新たな変動値として設定する変数値再設定手段とを含み、

前記変数値再設定手段は、再設定される新たな変動値が存在する間は、前記制約条件抽出手段及び前記制約条件解算出手段が繰り返し行うことを特徴とする制約条件解決装置。

[9] 前記制約条件入力手段により入力された制約条件を格納する制約条件格納手段と、

前記変数値設定手段により入力された変数の値を格納する変数値格納手段とをさらに含み、

前記ユーザにより前記制約条件または前記変数値の追加、変更、削除が行われると、前記制約条件抽出手段は、前記制約条件格納手段または前記変数値格納手段により格納されて、る制約条件または変数値と比較して、相違が生じた制約条件のみを抽出することを特徴とする請求項 8に記載の制約条件解決装置。

[10] 手続き型または関数型のアルゴリズムを設定可能な関数型定義保持手段と、前記関数型定義保持手段により設定されたアルゴリズムに基づいて、前記対象問題を手続き型または関数型で解決することを可能にする関数型定義実行手段とをさらに含むことを特徴とする請求項 8または 9に記載の制約条件解決装置。

[11] 前記変数値設定手段及び前記変数値再設定手段により設定される変数は、数値のみならず、文字、文字列、抽象的なデータ構造、組み込み関数を包含するデータ、及びオブジェクト型データ構造の少なくとも何れかを含むことを特徴とする請求項 8 一 10の何れか 1項に記載の制約条件解決装置。

[12] 前記対象問題が、 WEB上の入力インタフェースを用いて任意のアプリケーションプログラムを構築する問題、または任意のデータが蓄積されたデータベースを検索する際のトランザクション処理問題であって、

前記対象問題を前記制約条件により解決して!/ヽく処理手順及び処理内容を、履歴情報として保持する履歴保持手段を含むことを特徴とする請求項 8— 11の何れか 1 項に記載の制約条件解決装置。

[13] GUI環境における基本的な画面構成要素であるウィンドウを用いたウィンドウシステムまたはマルチウィンドウシステム、または前記 GUI環境におけるウィンドウを用いて処理した内容を出力する出力システムにおいて、前記アプリケーションプログラムの構築処理を行うことを特徴とする請求項 12に記載の制約条件解決装置。

[14] 制約条件を入力する制約条件入力手段と、

前記制約条件入力手段により入力された制約条件に用いられる変数の値を設定する変数値設定手段と、

前記制約条件入力手段により入力された制約条件の中から、前記変数値設定手段により設定された値に関係する制約条件を抽出する制約条件抽出手段と、前記制約条件抽出手段により抽出された制約条件の解を算出する制約条件解算出手段とを含む制約条件解決方法において、

前記制約条件は、現在の配列要素数を含んでいること、前記変数に複数個の値を持たせること、構造体配列の要素値による検索を含んでいること、及びデフォルト規則による文字列数値変換の少なくとも何れかを特徴として構成される制約条件解決装置。

[15] 複数の機器が互いに通信可能に接続されている制約条件解決システムであって、上記機器のうち少なくとも 1つの機器は、請求項 8— 14の何れかに記載の制約条件解決装置の機能を有することを特徴とする制約条件解決システム。