トップ :: G 物理学 :: G06 計算;計数

【発明の名称】 ソフトウェア生成方法
【発明者】 【氏名】荒井 攻

【要約】 【課題】Lyee方法論による設計をより的確に実行するための方法論を提供すること。

【構成】本発明は、要件定義から出力と入力の論理体単位の関係をとらえ、処理経路図に表す第1のステップと、要件の過不足を調整する第2のステップと、前記各論理体に所属する単語をとらえる第3のステップと、前記要件定義から、単語ごとの要件生成式、条件式を整える第4のステップとを実行して抽出されるソフトウェアの必須要素を単語単位にLyee自動生成ツールに入力することにより所望のソフトウェアの目的コードを得ることを特徴とするソフトウェア生成方法において、基本構造を1つとし、スタート画面のW04にすべての基本構造上の単語を置き、すべての単語と入出力作用要素に対して、その始点と基本要素との関係を有向グラフで表現し、トポロジカルソートして順序を決め前記処理経路図に配置することを特徴とする。
【特許請求の範囲】
【請求項1】
要件定義から出力と入力の論理体単位の関係をとらえ、処理経路図に表す第1のステップと、
要件の過不足を調整する第2のステップと、
前記各論理体に所属する単語をとらえる第3のステップと、
前記要件定義から、単語ごとの要件生成式、条件式を整える第4のステップと
を実行して抽出されるソフトウェアの必須要素を単語単位にLyee自動生成ツールに入力することにより所望のソフトウェアの目的コードを得ることを特徴とするソフトウェア生成方法において、
基本構造を1つとし、スタート画面のW04にすべての基本構造上の単語を置き、すべての単語と入出力作用要素に対して、その始点と基本要素との関係を有向グラフで表現し、トポロジカルソートして順序を決め前記処理経路図に配置することを特徴とするソフトウェア生成方法。
【発明の詳細な説明】【技術分野】
【0001】
本発明は、ソフトウェア生成方法に係り、特に、Lyee方法論におけるソフトウェア生成方法に関する。
【背景技術】
【0002】
高い品質を持つソフトウェアを容易に迅速に製造することは、ソフトウェア開発研究分野での基本的な関心事である。ここ数年間にわたって、ソフトウェア開発のライフサイクルに関連する1つまたは多くの局面を改善するために、種々の方法論および技術が考案され、提案されてきた。
【0003】
しかし、この研究分野における熱心な努力にもかかわらず、明確に理解でき、修正可能なシステムの製造は、困難な目標であり達成にはほど遠い。最近、Lyee(governmentaL methodologY for softwarE providencE)という新規で非常に有望な方法論が提案された。異なる分野に関する広い範囲のソフトウェアの問題を効率的に処理することを目的としたLyeeにより、単にその要件を定義するだけで、ソフトウェアを開発することができるようになった。もっと正確にいえば、開発者は、単語、計算式、計算条件(前提条件)、画面および帳票のレイアウトを与えさえすれば、後は、コンピュータが以降のすべての面倒なプログラミング・プロセス(例えば、種々の制御ロジックの局面)を行ってくれる。
【非特許文献1】荒井 攻、藤田 ハミド著、「単語単位プログラミングの数学的構造」、SSGRR2002、2002年
【非特許文献2】荒井 攻、藤田 ハミド著、「単語単位プログラミング:その数学的モデル及び実際の応用」、IOSプレス、2002年
【非特許文献3】荒井 攻、藤田 ハミド著、「単語単位プログラミングの数学的構造」、2003年11月
【非特許文献4】荒井 攻、藤田 ハミド著、「単語単位ソフトウェア開発の数学的モデル」、2003年10月
【非特許文献5】荒井 攻、藤田 ハミド著、「Lyeeソフトウェアの宣言的及び手続的表示」、IOSプレス、2004年
【非特許文献6】グリン・ウィンスケル著、「プログラミング言語の公式意味論」、MITプレス、1993年
【非特許文献7】ハンネ・リース・ニールソン、フレミング・ニールソン著、「アプリケーションについての 意味論 公式紹介」、ジョン・ワイリー ・アンド・サンズ 、1992年
【非特許文献8】根来 文生著、「Lyee ソフトウェアの原理」、21世紀( IS2000 )における情報社会についての国際会議会報、日本、会津、2000年11月5日-8日、 pp441 - 446
【非特許文献9】根来 文生著、「ソースコード生成についての高密度処理方法」、システミクス、サイバネティクス及びインフォマティクスについての第5回世界多極会議会報、( SCI2001 )、米国、オーランド、2001年7月22日-25日
【非特許文献10】J.W.Lloid, Foundation of Logic Programming, Springer-Verlag, 1987
【非特許文献11】Chris Rorres, Howard Anton, Applications of Linear Algebra, John Wiley and Sons, Inc., 1979
【非特許文献12】根来 文生著、「Lyeeの仮説的世界」、システミクス、サイバネティクス及びインフォマティクスについての第5回世界多極会議会報、( SCI2001 )、米国、オーランド、2001年7月22日-25日
【非特許文献13】Sergei Gorlatch, “The Lyee Programming Model: Analysis and Correctness in a Fixed-Point Setting”, In H. Fujita and P. Johanesson, editor, New Trends in Software Methodologies-2, Tools and Techniques, pages 214-224, IOS Press, 2003
【非特許文献14】M. Mejri, B. Ktari and M. Erhioui. Static analysis on Lyee oriented software. In H. Fujita and P. Johanesson, editor, New Trends in Software Methodologies, Tools and Techniques, pages 375-394, IOS Press,2002
【非特許文献15】M. Dincbas, P. Van Hentenryck, H. Simonis, A. Aggoun, T. Graf, F. Berthier, The Contraint Logic Programming language CHIP, Proc. Of the International Conference on Fifth Generation Computer Systems 1988, pp 693-702, 1988
【非特許文献16】J.Jaffer, JLassez and M.J.Maher, Some Issues and Trend in theSemantics of Logic Programming, Third Internal Conference on Logic Programming, Lecture Notes in Computer Science-225, Springer-Verlag, 1986
【非特許文献17】G.J.Sussman and G. L. Steele, CONSTRAINTS, A Language for Expressing Almost-Hierarchical Descriptions, Artifical Intelligence 14(1), pp. 1-39,1980
【非特許文献18】Queins S, Zimmermann G, Becker M, Kronenburg M, Peper C, Merz R, Schafer J: “The Light Control Case Study”: Program Description, J.UCS, Special Issue on Requirements Engineering, Volume 6 Issue 7 July 28, 2000
【発明の開示】
【発明が解決しようとする課題】
【0004】
その新しさにもかかわらず、Lyeeの使用結果は、Lyeeに優れた可能性があることを示している。しかしながら、要件からのソフトウェアの自動生成プロセスも、生成されたLyeeソフトウェアの意味論も、形式的でない言語によって記述されているために、この方法論を理解し、研究しようとすると、困難に遭遇し、混乱が生じる恐れがあった。
【0005】
本発明は上記の従来技術の問題を解決するためになされたもので、Lyee方法論による設計をより的確に実行するための方法論を提供することを目的とする。より具体的には、処理経路図を作成する方法を規則化することで、要件定義の内、開発対象のソフトウェアが動く環境や開発言語に依存しないソフトウェア構造の必須要素となる要件を単語単位に捉える捉え方が規則化され、Lyee方法論によるソフトウェア設計の実行性・効率性をより向上させることをその目的とする。
【0006】
さらには、処理経路図を検証することで、登録前に要件の過不足をチェックすることでLyee方法論によるソフトウェア設計の実行性・効率性をより向上させることをその目的とする。
【課題を解決するための手段】
【0007】
かかる課題を解決するため、本発明は、要件定義から出力と入力の論理体単位の関係をとらえ、処理経路図に表す第1のステップと、要件の過不足を調整する第2のステップと、前記各論理体に所属する単語をとらえる第3のステップと、前記要件定義から、単語ごとの要件生成式、条件式を整える第4のステップとを実行して抽出されるソフトウェアの必須要素を単語単位にLyee自動生成ツールに入力することにより所望のソフトウェアの目的コードを得ることを特徴とするソフトウェア生成方法において、基本構造を1つとし、スタート画面のW04にすべての基本構造上の単語を置き、すべての単語と入出力作用要素に対して、その始点と基本要素との関係を有向グラフで表現し、トポロジカルソートして順序を決め前記処理経路図に配置することを特徴とする。
【0008】
かかる構成を備える本発明によれば、ソフトウェアの必要要素として、レベル1:処理単位(処理の類型:登録型、参照型)、レベル2:入出力論理体(論理体名、媒体属性、アクセスキー、アクセス条件等)、レベル3:単語(単語名、生成式&生成条件、タイプなど)をソフトウェア環境や言語に依存することなく抽出することができる。
【0009】
また、処理経路図を作成する方法が規則化されるので、要件定義の内、開発対象のソフトウェアが動く環境や開発言語に依存しないソフトウェア構造の必須要素となる要件を単語単位に捉える捉え方が規則化され、Lyee方法論によるソフトウェア設計の実行性・効率性をより向上させることが可能となる。
【0010】
さらに、要件に示されている、処理単位ごとの出力論理体と入力論理体の関係をとらえ、わかりやく図示できるという処理経路図の本来の意義も果たされる。
【0011】
本発明は、上記において、当該第1のステップは、処理単位(処理単位の処理開始条件も含む)をとらえるステップと、該処理単位ごとの、出力データの集合である出力論理体と入力論理体とそれらに関する情報をとらえるステップと、該処理単位の処理の類型をとらえるステップと、該処理単位ごとに処理経路図を作成するステップとを具備するように構成しても良い。
【0012】
また本発明では、当該第2のステップは、該出力論理体に対して、入力論理体が不足していないかを検証するステップと、該検証の結果不足がある場合は該要件を修正し、それに伴って処理経路図を修正するステップとを具備するように構成しても良い。
【0013】
さらに本発明では、当該処理単位に係る処理の類型には、登録型及び/もしくは参照型を少なくとも含むように構成しても良い。
【0014】
また本発明では、当該前記入出力論理体に係る必要要素としては、論理体名、媒体属性、アクセスキー、アクセス条件のいずれかを少なくとも含むように構成しても良い。
【0015】
さらに本発明では、当該単語に係る必要要素としては、単語名、生成式&生成条件、タイプのいずれかを少なくとも含むように構成しても良い。
【0016】
本発明によれば、処理経路図を作成することで、要件定義の総てを捉え、かつ処理経路図を検証することで、登録前に要件の過不足をチェックした上で、たとえばLyeeALL等のLyee方法論に係る自動生成ツールに入力するので、所望とするソフトウェアを適切に生成することが可能となる。
【発明の効果】
【0017】
本発明によれば、処理経路図を作成することで、要件定義の総てを捉え、かつ処理経路図を検証することで、登録前に要件の過不足をチェックした上で、たとえばLyeeALL等のLyee方法論に係る自動生成ツールに入力するので、所望とするソフトウェアを適切に生成することが可能となる。
【発明を実施するための最良の形態】
【0018】
以下、図面を参照して本発明の最良の実施形態を説明する。
目次
<1>.序論
<2>.Lyeeの証明
1.Lyee構造の定義
1.1.モジュール構成
2.形式的証明
2.1.単語を基礎としたプログラムとは何か?
2.2.個々の単語のプログラムの構造
2.3.制御プログラムとその構造
2.4.仕様の記述
2.5.不動点方程式を設定する
2.6.汎関数の連続性
3.宣言的仕様の意味
3.1.Lyee構造の宣言的意味
3.2.Lyee構造の手続き的(操作的)意味
<3>.単語を基礎とするプログラムの数理的構造モデル
1.有向グラフと隣接行列によるモデル化
1.1.有向グラフと隣接行列
1.2.隣接行列Fと状態ベクトルXを使う状態モデル
2.モデルの活用
2.1.数学的な構造モデルを使う
2.2.不必要な単語の繰り返し処理をさける方法
2.3.単語の列のクリアと一時的な単語の数理的な原則
2.4.要件を有向グラフの理論を用いて調べる
<4>.リアクティブなプロセスのモデル
1.Lyeeの基本構造および処理経路図
1.1. 処理経路図とプログラムの動き
1.2.システムの分割
1.3.システムの基本構造への分割
1.4.経路の作用要素とその実行条件
2.プロセスモデルによるLyeeの考察
2.1.関数モデルの限界
2.2.リアクティブなシステム
2.3.プロセス・モデル
2.4.事例
2.5.プロセス・モデルのまとめ
2.6.これをLyeeで実現する
2.7.共有、単語、単語内の3レベルの変数のスコープがある
2.8.基本構造はどこまで分割すべきか
<5>.効果的なプログラムの生成
1.リアクティブなプロセスのLyeeによる実現
2.実施例と評価
<6>.結論

<1>.序論
Lyeeと呼ぶソフトウェア開発の方法論は、要件からソフトウェアを自動的に開発する新しい方法である。それはプログラムの宣言的な仕様を基にすることによって仕様設計やコーディングを容易にした。宣言される抽象化の単位をLyeeでは単語と呼ぶ。
【0019】
一般的に、仕様が宣言的であるとは、宣言される抽象化の単位は記述の順序性は排除されることと、等式として表現され右辺から左辺、左辺から右辺への双方向性があることである。Lyeeでは、単語は記述の順序性は排除されるが、双方向性をもたず、このことによって、枠組み(schema)が簡潔になっている。
【0020】
一方、Lyeeでは、基本構造と呼ぶ単位に、要件を分割して仕様を捉える。画面の遷移、データベースのキーの関係などの実行順序に関する明白な情報を単語のグループ(record)を単位として捉え、そのグループに属す単語の実行条件をまとめて把握する。現状のLyeeでは、この分割構造を、そのままコード化しているため、プログラムが大きく、実行速度も遅い。
【0021】
Lyeeシステムの役割は、x(i)=fi(x(1),…,x(n)), i=1,…,nの形をした仕様を受け入れ、その等式系の解をもたらす、すなわち、すべての等式が成立するx(i),i=1,2,…,n,の値を見出すような、プログラムを生成することである。Lyeeのプログラム生成の枠組み(schema)はただしい解を供給する責任があり、まず、この枠組み(schema)が、まさに正しい解を供給することを形式的に証明する。さらに、Lyeeという方法の基本である、そのプログラム生成の枠組みを解析するため、グラフと隣接行列とを用いて、モデル化する。このモデルにグラフに関する定理を用いて、生成されるプログラムの最適化を図り、実例で検証する。
【0022】
Lyeeでは、抽象化の単位としての単語は、どの範囲で1つの単語と見做されるかが明確でない。また、基本構造への分割の考え方の根拠は不明確であり、その適用に統一が取れていない。その原因の1つは、仕様をx(i)=fi(x(1),…,x(n)), i=1,…,nの形をした関数としてのみ捉えたことによると考えられる。仕様を複数のプロセスによる、リアクティブなシステムとして捉え、そのモデルとしてプロセス・モデルを用いることによって、単語や基本構造の単位がアクションやロケーションの単位に対応し、そこで用いられる、相互排除性やアトミックアクションの概念から、分割の根拠を示す。プロセス制御やゲーム(オセロ)の事例で、その分割法を適用し、Lyeeの適用対象の拡大を図る。
<2>.Lyeeの証明
1.Lyee構造の定義
計算機を利用してある問題を解決しようとする場合、まずその問題を厳密に記述することが必要である。そのためには、我々は、問題領域とその領域における対象、およびこれら対象間の関係を明確にしなければならない。
【0023】
コンピュータ・グラフィックスでは、問題領域は2次元空間であり、対象は各種図形であり、関係は図形間の位置関係などであり、数値計算では、問題領域は実数であり、対象は数値・変数であり、関係は等式・不等式である。問題領域における対象群は系をなす。これらの系の仕様は、対象同士の関係として与えられる。対象が数のように構造が均一で、必要とする記憶量も少なく、しかも、計算の操作が単純なとき、"手続き型"で問題解決が実現可能である。しかし、規模が大きいとき、仕様をいくつかの対象に纏めることが自然である。
【0024】
Lyeeにおける単語とは、このような対象間の関係を等式の系として、宣言的に記述したものである。Lyeeでは、抽象化の単位は、単語・入出力作用要素・経路作用要素構造・構造作用要素である。これを基本要素と呼ぶ。基本要素間の組合せによって、意味が構成される。単語による問題解決には、2つの仕様の記述能力が必要である。1つは単語それ自身である。これは対象間の関係を表すとともに、その関係の満たすような対象の性質を求めるためのなんらかの機能の存在をも含んでいる。もう1つは、どの単語を同時に満たすべきであるとか、単語を満たすような対象をどの順番で見付けだすかといった、制御情報に関する記述能力である。これは、必要ない方が望ましいが、必要であれば、容易に記述できることが望まれる。
【0025】
仕様が宣言的とは、一般に、以下の2つを満たすとき使われる。1つは対象の記述順序の自由性、2つは、対象が関係式として表現され、右辺から左辺、左辺から右辺への双方向性があることである。
【0026】
対象間の関係は通常、関係式で表され、代入式ではない。Lyeeでは、関係を、代入式で実現するため単一代入法(the single assignment property)を採用している。すなわち、はじめに、未決定(undefined)でクリアし、一度代入されると上書きしない。この方法によって、代入式によって、宣言的性質を実現しているため、双方向性はない。この点が、通常の宣言型と異なる。
【0027】
宣言的仕様の意味は仕様を書いたときにユーザが心に描いたことである。宣言型のパラダイムでは、通常、その意味をこれらの概念が展開された論理体系等に求めることができる。述語や関数の概念が、抽象化の単位となる。Lyeeではその基礎となる論理体系は持たない。Lyee型プログラミング法の意味論は、単語(基本要素)が記述される計算領域である、ある代数構造の上で展開される。この代数構造上における正しい関係が、成立する単語(基本要素)を意味している。
【0028】
Lyeeでは、等式の系によって、仕様に含まれる異なる値の間の関係を宣言的に表現する。このような宣言的に表現された仕様はそのままでは実行可能ではない。すなわち、コンピュータ上で要求された結果を得るためには命令的なプログラムが生成されなければならない。この生成されたプログラムが仕様を実行する。このプログラムが入力データを取り込み、ユーザの仕様に対応する出力データを作り出す。
【0029】
このようにして、仕様から生成された応用プログラムは、入力値を取り込み、それらの値が等式の系を満たすような、すなわち等式が成立するような出力値を作り出すことが期待される。Lyee方法論では、システムの要件を、単語と呼ぶ宣言的な抽象化の単位で表現する。Lyee方法論で自動的に生成されるLyee構造のプログラムのモジュール構成の定義を以下に示す。
1.1 モジュール構成
手続き的でない、宣言的仕様を用いてプログラム開発を達成するためにLyeeで用いられる2つの要素は、述語構造(Predicate structure schema)とよばれるプログラム構造によって表現される単語モジュールと作用要素、および制御プログラムである。基本構造モジュールは、1つの制御プログラムとその上に配置された述語構造を持つ単語等の組で構成される、要件の基本的な分割単位である。
(1)単語モジュール
単語モジュールは、1つの領域とそこに値を生成する生成式、および生成条件とからなる述語構造と呼ばれるプログラム構造を持つプログラムコードモジュールであり、値と、状態とを持つ。以降、単語と呼ぶ。状態は、未決定(undefined)、決定(decided)である。さらに、決定(decided)は、真(true)、偽(false)の2つの状態に分け、計3状態(state)である。
【0030】
一度に処理すべき単語のグループを定義体(record)と呼ぶ。プログラム上に、このグループを取り扱う領域をまとめて、つくることが必要になる。この領域を、論理レコード(logical record)と呼ぶ。論理レコードは、(定義体ID+アクセス区分)で特定する。アクセス区分とは、アクセス方法を示す記号と連番をもつ名前である。論理レコードには、それを取り扱う、同じ述語構造を持つ入出力作用要素モジュール(Input Vector およびOutput Vector)が定義される。単語と作用要素との役割の違いをしめすために、表1に単語と入出力作用要素との対比をする。作用要素には、他に経路作用要素(Routing Vector)、構造作用要素(Vector of Clear)がある。<3>章2.3で詳述する。単語や、作用要素のような述語構造を持つモジュールを、以降、基本要素と呼ぶ。
【0031】
【表1】


(2)制御プログラム
単語を制御するプログラムは、 Lyee (非特許文献8参照)では、パレット連鎖関数と呼ばれる。以降、制御プログラムと呼ぶ。それ以上の反復をしても、どんな単語の値も変えないときまで、制御プログラムがただ単語プログラムの実行を繰り返す。適切に繰り返しプロセスを行なう機能はこのプログラムの中で実現される。
(3)基本構造モジュール
基本構造モジュールは、1つの制御プログラムとその上に配置された述語構造を持つ単語等の組で構成される、プログラムの基本的な分割単位である。必要時、単語のグループ単位に分割される。基本構造モジュールは、さらに、3つのパレットに分割される。出力、入力、計算の3パレットは、それぞれW04, W02, W03 パレットと呼ばれ、この順序で連続して実装される。各パレットに単語モジュール、作用要素モジュール等の基本要素が置かれる。
2.形式的証明
単語を基礎としたプログラミングでは、要件が単語の集合として表される。単語は、述語構造(Predicate structure schema)とよばれるプログラム構造によって表現される。単語が文(statements)を使って定義される。まず単語を基礎としたプログラムのコンセプトを説明する。
2.1. 単語を基礎としたプログラムとは何か?
単語を基礎としたプログラムは2つの主な要素で構成されている。1つ目の要素は単語である。単語を基礎としたプログラミングの中で、要件はそれらの名前、計算式の定義、それらの計算条件、属性(入力/ 出力、型、他の性質)を含む、単語の集合として宣言的方法で与えられる。要件の例が表2に示される。他の要素は制御プログラムである。それ以上の反復をしても、どんな単語の値も変えないときまで、制御プログラムがただ単語プログラムの実行を繰り返す。
【0032】
【表2】


単語aの定義が単語bを使うとき、単語bが単語aの後に与えられるにもかかわらず、ユーザは、これらの定義が実行される順序を指定しなくてもよい。論理プログラミングでは、プログラム項の順序は実行の結果に影響を与える。
【0033】
初めに、単語aが実行される。d、b、cという単語がまだ実行されていないので、aは、その値を決定することができない。次に、cという入力単語が実行される。それは実行条件を持っていないので、その値は決定される。例えば、単語cの値が + 3であると考えよう。それから、bが実行されて、cの値が決定しているので、値を決定することができる。単語dは入力単語であって、実行条件を持っていないので、d = trueである。すべての単語が処理され、aの値については、未決定(undecided)のままでいる。結果として、プログラムは先頭に戻って、そして再び実行される。そして、d = trueであることと、bとcがそれぞれ+ 11と + 3と値を持っていることからaは、+ 14という値を適切な装置にそれを出力する。単語c、bとdの値は事前に計算されたので、単語の値のすべてが決定された。単語の型は、コンピュータ上で使うことのできる、数、文字、 boolean などである。
【0034】
単語の論理的な順序を制御するために、それぞれの単語に存在する状態の概念を導入する。状態は、真(true)、偽(false)、そして未決定(undecided)の3つの状態のうち1つの値をとる。それぞれの意味は次の通りである。
【0035】
真(true):値は決定されている、そしてそれはユーザ要件を満たす。
【0036】
偽(false):値は決定されている、しかしそれはユーザ要件を満たさない。
【0037】
未決定(undecided):値は決定されていない。
【0038】
単語の最初の状態は、単語の値がまだ転送されていない、あるいは計算されていないことを意味して、常に未決定である。名前によって定義された単語を終点単語と呼び、他の単語を定義するために使われる単語の集合を、始点単語と呼ぶ
要件上の、すべての単語を1度実行する処理を一巡処理と呼ぶ。始点単語の状態がすべてtrueであるとき、終点単語の値が決定され、その状態はtrueになる。始点として使われない単語の状態は、終点単語の状態に関係しない。一巡処理が繰り返される処理は繰り返し処理と呼ばれる。一巡処理を繰り返し、繰り返し処理を通して、単語の状態に変更がなくなると、単語の値を出力のために使うことが可能である。それぞれの単語の状態は、真(true)、偽(false)、であるか、あるいは未決定(undecided)で残る。もし未決定(undecided)の単語が残るときは、必要な入力単語がこのシステムに存在するかどうか、あるいは、いずれかの単語がその定義式や計算条件の中でそれ自身を直接的にあるいは間接的に使用したことを意味する「閉じたループ」があるかどうか、を調べなくてはならない。あるいは要件が完全ではない場合である。1つの単語にかかわる複数の計算条件は互いに排他的であるべきである。そして「否定」は、明示的に定義されなくてはならない。単語を基礎としたプログラムでは、ソフトウェアの実行制御部分は自動的に生成される。
2.2. 個々の単語のプログラムの構造
単語は、述語構造(Predicate structure schema)とよばれるプログラム構造によって表現される。述語構造とは、7つのプログラム文(statements)からなるプログラム構造を持つプログラムであり、図1に示す。
【0039】
単語を基礎としたプログラムで、すべての単語L(α)のプログラムコードは次のように記述される:
(1)Box1:プログラム文を遂行するべきかどうか決定する。もし、α=undecidedならBox2へすすむ。
(2)Box2:単語αの状態が未決定(undecided)であるとき、プログラム文は実行される。プログラム文を実行して、もし始点単語のすべてが真(true)であるなら、一時的な領域にそれを記憶する。したがって、一時的な領域が必要である。もし始点単語(s-word)が未決定(undecided)であるか、あるいは偽(false)であるなら、通過する。
(3)Box3:Box2のプログラム文を実行することによって、結果として単語αの値が決定されたかどうか判定する。全部の始点単語が真(true)であるとき、値が決定される。しかしながら、たとえ全部の始点単語が真(true)であるとしても、単語α(一時的領域t_α)の値がユーザの要件(u-req.)に適合しない場合は偽(false)になるかもしれない。
(4)Box4:単語αの値が真(true)であるとき、一時的領域(t_α)にある値を正規領域に記憶する。決定された値を記録するために正規領域が必要である。
(5)Box5:単語αの状態が偽(false)か未決定(undecided)であるかどうか判断する。単語αがユーザの要件を満たさない状態、あるいは始点単語の値が1つでも偽(false)のとき、状態は偽(false)である。
(6)Box6:Box5の判定結果が偽(false)であるとき、状態が偽(false)であることを意味するフラグをセットする。フラグの記憶領域はすべての単語に必要である。あるいは、状態が偽(false)であることを意味する値を正規領域に記憶する。
(7)Box7:Box5の判定結果が未決定(undecided)であるときは、繰り返し処理を実行するかどうか判断するために用いる「繰り返しカウンタ」に1を加える。繰り返しカウンタが必要である。
【0040】
この述語構造は、単語とその仲間である作用要素に統一して用いられ、制御プログラムとともに、単語を基礎とするプログラムの中心的モジュールを構成する。
2.3. 制御プログラムとその構造
単語を制御するプログラムは、 Lyee (非特許文献8参照)ではパレット連鎖関数と呼ばれる。以降、制御プログラムと呼ぶ。適切に繰り返しプロセスを行なう機能はこのプログラムの中で実現される。
【0041】
もし始点単語の状態が偽(false)であるなら、終点単語の状態は、偽(false)になる。
【0042】
たとえ始点単語の全部の状態が真(true)であっても、ユーザ要件によって偽(false)と判断される終点単語の状態が偽(false)になる。
【0043】
そのために、繰り返し処理が必要かを決定するためには、ただ、単語に未決定(undecided)の状態を持つ始点単語が含まれているかどうかを判断すればよい。もし始点単語の1つでも未決定(undecided)なら、繰り返し処理が必要である。
【0044】
しかしながら、有向グラフによって表現したとき、閉じたループを含んでいると、終点単語の状態が未決定(undecided)から変化しないことが分かる。さらに、このシステムに、その始点単語を持っていないなら終点単語の状態は未決定(undecided)から変化しない。
【0045】
このような状況では、繰り返し処理は終了せず、永久のループに入る可能性がある。
【0046】
この状況を避けるために、制御プログラム (Φ) に、繰り返しを制御するために使われる再帰カウンタを扱うプログラムコードがある。その単語が未決定(undecided)になる時はいつも、それぞれの単語プログラムが再帰カウンタに1を加える。一連の繰り返し処理を実行するか否かを判断するために、このカウンタの値をその前回値と比較する。今回値が前回値と同じ場合は、繰り返し処理を実行しない。この状態を、「状態変化がない」を言う。
【0047】

論理プログラミングで、特に標準的な Prolog では、バックトラックが、永久ループにはいることがある。他の改善された Prolog では、永久のループを避けるために、wait、あるいはfreezeなどの機能がある。
【0048】
単語を基礎としたプログラミングでは、上記の通り、このようなメカニズムによってこのループを避けることができる。図2にLyee 方法論で使われる、繰り返し処理制御プログラムの例を示す。
【0049】
「 Ctr の値は、その状態が未決定(undecided)である単語モジュールL(α)の数である」という性質を「ループ不変の性質」として使って、このプログラムは、 ホーア(Hoare )のロジックを使って、その正しさが、証明できる。このプログラムは以下のことを意味する:
プログラムは停止する。
停止したとき、可変的な Ctr の値はその状態が未決定(undecided)であるL(α)の数である。
[証明]
以下のプログラムをCとする;
PCtr = Ctr
Ctr = 0
L(x)
L(y)
L(z)
すると、
【0050】
【数1】


である。ここで、Pは、すべての前条件(precondition)である。ループ不変の性質としては“The value of Ctr is the number of L(α) whose state undecided.”を用い、Loop invariant と表す。すると;
【0051】
【数2】


である。したがって、繰り返しの規則により、
【0052】
【数3】


である。
【0053】
【数4】


not (Ctr ¹
PCtr)の論理的帰結として、Ctr = PCtr が得られる。帰結(2)を用いることによって;
初期状態でCtr=0であるので、帰結(1)を用いることによって;
【0054】
【数5】


である。初めの実行時点では、未決定単語(undecided word)が存在しなければ、すなわち単語プログラムの実行の結果すべての単語が成立すれば、プログラムは停止し、Ctrは0になる。2回目以降の実行では、単語の性質から、未決定 (undecided) の単語の数が前回の数と等しい、あるいは減少する。一度等しくなると、それ以上は変化しない。したがって、このプログラムは停止しCtr (= PCtr )は未決定 (undecided)の単語の数となる。ここで、
【0055】
【数6】


[証明終わり]
停止したとき、単語の定義によれば、通常の場合では、その始点単語がこのシステムに存在する単語αの状態には、真に決定(decided true)か、偽に決定(decided false)のいずれかの値が割り当てられる。
【0056】
単語αの状態は以下の場合に、未決定(undecided)である。
(1)単語αは閉じたループにある、あるいは閉じたループの後にある。
(2)単語αが排他的な条件を持っていない。排他的な条件とは、もし
【0057】
【数7】


が常にtrueで、そして
【0058】
【数8】


が常にfalseであるなら、xとyについて排他的である。
(3)その始点単語がこのシステムに存在しない。
2.4. 仕様の記述
Lyeeの要求仕様をよりいっそう形式的に扱うためには、仕様は、1,2,…,nのそれぞれの点で、定数や他の点での関数xの値を使って、関数xを定義する、等式の系であると見なすことができる:
x(i) = fi ( x(1),x(2),¼
,x(n)), i = 1, 2,¼
, n (2-2-1)
一般性を失うこと無く、すべての単語が同じ型であると想定することができる。それをRによって示す。値の一部が未決定(undecided)であるという場合に適切に対処するために、出力領域Rに特別な未決定(undecided)の値 ^
(“bottom”)を追加する。すると、全域関数xが以下の型を持つ:
【0059】
【数9】


Lyeeシステムの役割は、(2-2-1)の形をした仕様をもとに、等式の系の解をもたらすプログラムを作ることである。すなわちこのプログラムはすべてに等式が成立するようなx(i),i=1,…,n,の値を見付ける。
2.5. 不動点方程式を設定する
Lyeeの方法に、不動点を設定するために、いわゆる不動点汎関数(関数に作用する関数)を使って仕様を再定式化する。(2-2-1)の右辺は汎関数 Fに引数xと iとを適用した結果、以下のようになる:
【0060】
【数10】


関数x に適用すると、汎関数は関数h(i)、h(i) = F(x(i))となる:
ここで、h(i) = fi ( x(1),x(2),¼
,x(n)), i = 1,2,¼
,nである。
【0061】
この結果、(2-2-1)の形をしたLyeeの仕様は、
x(i) = F ( x(i)), i = 1,2,¼
,n,
のように書き直される。もっと簡単に:
x = F ( x) (2-2-3)
である。ここで、汎関数Fは(2-2-2)で定義されたものである。
【0062】
式(2-2-3)は、不動点方程式(再帰方程式)と呼ばれ、その解は、もし存在すれば汎関数Fによって関数をそれ自身に射影する関数である。このようにして、方程式の系(2-2-1)を解く仕事は、式(2-2-3)によって定義される、対応する汎関数の不動点を見付ける仕事になる。
2.6 汎関数の連続性
表示的意味論で用いられる、完全半順序は、計算の入力、出力に用いる、データの型に対応する。計算可能な関数は、それらの間の連続な関数としてモデル化される。完全半順序の要素は情報の点(単位、幅、範囲、量)と考える。順序
【0063】
【数11】


はxはyを近似する(xはyと同じか少ない情報をもつ)。ここで⊥は最小の情報を意味する。
【0064】
有限な前提に基づくに帰納法で表示的意味をあたる方法(非特許文献6参照)をこの一般的枠組みに再構築する。ここでは、コマンド(プログラム)を状態から状態への部分関数によって表示する。一見したところ、これは一つのコマンドによって計算される関数は連続であるべきという考えと調和しない。しかしながら状態上の部分関数は連続な全域関数とみなせる。新しい要素⊥によって、すべての状態σに対して⊥⊆σによって順序つけられた
【0065】
【数12】


なる完全半順序に状態Rを進展させる。完全半順序(数12)は、未決定 (undecided)の状態を表現する(より正確には、状態に関する情報がないことを示す)特別な要素⊥を含む。この要素は、計算が進んだ結果、特別な最終状態が決定される情報に成長する。部分関数R→Rは全域関数
【0066】
【数13】


と1:1対応するとみなすことができる。この場合には、どんな全域関数も連続である。すなわち、部分関数間の包含順序は、全域関数(数13)の
【0067】
【数14】


である、近似順序に対応する。部分関数間の順序は完全半順序を形作るので、関数の集合
【0068】
【数15】


は近似順序で順序づけられる。その結果、表示的意味は、連続関数(数15)の完全半順序の要素によってコマンド(プログラム)を表示することと同等であるとみなされる。whileプログラムの表示を与えるためには、部分関数の完全半順序上の連続関数の最小不動点をとることによって再帰的方程式が解ける(非特許文献6参照)。これを一般化して、(部分関数の完全半順序上から)全域関数の完全半順序(数15)上の連続関数の最小不動点をとることに、再構築したことになる。
【0069】
完全半順序(数15)に関しては、部分関数のそれとの同値性から、「より多くの情報」は、一つの関数のより多くの入出力動作に対応し、この完全半順序の⊥である「情報がない」は、入出力対を含まない空の部分関数に対応する。関数それ自身を(入力され使うことができる、あるいは計算によって作られた)データとみなすことができる。そのような関数についての情報は入出力対という離散的な単位からなる。そのような離散的性質はコンピュテーション(計算)をモデル化するときに起こる多数の完全半順序に共有される。計算可能な関数の出力の1単位の情報の出現は、入力の有限多数の存在に依存することからすると、計算可能な関数は当然、連続であるべきということになる。別の言い方をすると、関数のコンピュテーション(計算)は出力の(情報)単位を生成完了する前に、無限に多数の情報単位を利用しなければならないかもしれない。このような場合に一般化は有効である。
【0070】
連続性が有意義なのは完全半順序集合R上の単調増加列Xが無限集合である場合であり、特に完全半順序集合Rが有限集合なら、Rは有限な階数を持つので連続性は単調性で保証される。Lyeeの構造では、繰り返し(iteration)は有限で停止する。すなわちRが有限集合であるので、連続性は単調性によって保証される。一般化された不動点定理を用いるためには、連続性を必要とするが、Lyeeの構造の証明では、単調性は重要であるが、連続性は本質的ではない。
3.宣言的仕様の意味
Lyeeの表示的意味論の研究は進んできた。Lyeeの構造の正しさの証明は、ホーア(Hoare)の論理によって行なわれ(非特許文献3参照)、より形式的には不動点意味論によって、完成した(非特許文献13参照)。
3.1. Lyee構造の宣言的意味
表示的意味論における証明の中で単語に求められる性質は、以下に示す(A)(B)(C)(D)のみである。
【0071】
ある基本要素の領域に値を決定するのはその基本要素だけである。 (A)
単語に、等価条件として、If文がある場合は、このIf文は排他的(exclusive)であることが必要である。条件が重なっていると、先取り優先になる。
【0072】
基本要素の状態のクリアはスタート時点のみである。 (B)
単語の領域は、変数であるが、一度決定されると、値は変化しない。the single assignment propertyと呼ばれる。基本要素の状態がUndecidedのときにしか代入できないことで、上書きを禁止する。
【0073】
単語の値の計算に用いる始点は、他の単語(の名前identifier)である。したがって単語の領域は、その系の全域(global)変数である。 (C)
Lyeeの単語は、関数として表され、その変数は、他の単語である。send(write)は、自分の領域へ行いreceive(read)は、全体から行なう。図3に、単語の領域を示す。変数のスコープについては、<4>.2.7で再び論ずる。
【0074】
Lyeeでは、基本的に単語に内部状態はない。 (D)
Lyeeの単語は、関数であり、いわゆる“object”ではなく、”method”である。対象は、単語名である全域(global)変数だけである。単語内の局部(local)変数は対象ではない。
【0075】
作用要素の内、入出力の作用要素、経路の作用要素は単語と同様に宣言的意味を実現するための基本的要素である。
【0076】
入出力作用要素では、生成式は、外部への値の伝送、外部からの値の入力である。その実行結果、すなわち作用要素の状態決定(decided)は作用要素のフラグに反映される。単語のように値があることでの表現法ではない。値としてはEOFなどがあり、単語と同様に、代数構造上における生成条件等で用いられる。
【0077】
経路の作用要素は、仕様上、実行を制御するとき、宣言、定義する必要がある。
【0078】
経路の作用要素の実行条件は、同一の実行条件を持つ単語の実行条件の同一部分をまとめて独立させたものとみなせる。
【0079】
以上のように、証明に用いた単語や入出力作用要素、経路作用要素の持つべき性質は、すべて宣言的に実現されている。
3.2 Lyee構造の手続き的(操作的)意味
手続き的意味論は、動きとしての正しさの証明である。宣言的(表示的)意味を保ちつつ、操作的(手続き的)意味を実現することが望ましい。Lyee構造では、これを実現していることを示す。Lyeeでは、代入式を用いてこの制御を実現するための制御構造をもつ。その構造は、基本要素の状態を監視し、状態変化が無くなるまで、繰り返す構造である。ここで使用されるのは、単なる計算代入と値の成立の判定である。
【0080】
単語の実行条件は、その単語のすべての始点が決定(decided)になることである。 (E)
その単語のすべての始点が決定(decided)になるまで、評価を遅延する。その単語のすべての始点が決定(decided)になると、その単語は値を持つ、あるいは値を持たない。
【0081】
繰り返しは、状態変化が無くなれば、終了する。 (F)
これによって、単語の再帰的利用(自分自身を用いて定義すること)がなければ、プログラムは停止する。単語の再帰的利用があるかは、有効グラフ上の探索, 静的分析(非特許文献14参照)によって静的に、調べることができる。
<3>.単語を基礎とするプログラムの数理的構造モデル
1.有向グラフと隣接行列によるモデル化
単語を基礎としたプログラムの構造、すなわち述語構造を持つ基本要素と制御プログラムが手続き的に正しく機能することをホーア(Hoare )の定理によって証明した。しかしながら、このようなアプローチによる分析法では、論理的表現の複雑さのために、意味を検証することや、要求仕様の不備を修正することが難しい。この論文では、有向グラフ技術を用いたもう1つのアプローチを使い、より使いやすい数学的な構造モデルを構築する。この目的のため、有向グラフとその隣接行列を用いてモデルを構築する。<3>章2で、このモデルを使った、成果が示される。
1.1 有向グラフと隣接行列
始点単語と終点単語の間の関係は、図4に示されるようにそれぞれの単語がノードによって表され、関係が矢印によって表される有向グラフによって書くことができる。 矢が始点単語から終点単語への関係を示すために使われる。 それが関係a < bを持っている順序を定義する。 単語bが単語aから作られることを、関係a < bは定義する。 換言すれば、単語bがaを始点単語として使って定義される。 単語は、関係a < bを持つ、半順序集合をなす。
図5が例1の画面イメージを示す。 単語a, b, e,及び sが入力単語である。 単語 x, y, z, u 及び vは出力単語である。 単語は次に示すように定義される。

事例1の要件定義

Name
Attributes
Condition
Definition

Word
a
Input, numeric

Word
b
Input, numeric

Word
x
Output, numeric
e
y + z

Word
y
Output, numeric
e
b + z

Word
z
Output, numeric
e
a

Word
u
Output, numeric
e
2 ´
x

Word
v
Output, numeric
e
y + u

Word
e
Input, boolean

Word
s
Input, boolean

上に定義された出力単語が有向グラフを使って表現すると、それは図6のようになる。 有向グラフは隣接行列を使って表現することができる。 我々は、横列におけるこの終点単語と縦列におけるn個のの始点単語からなるn ´
nの行列を隣接行列Fと呼ぶ。もしi番目の単語がその始点単語としてj番目の単語を使うなら、Fの要素 fij of F は1である。 もし使わなければ、fij of F は0である。例1の隣接行列は次のように示される:
【0082】
【数16】


1.2 隣接行列Fと状態ベクトルXを使う単語のための状態モデル
ベクトルX(1つの縦列の行列)にn個の単語の状態を記録する。状態が単語の順序に従ってXに記録される。繰り返し処理を行なった状態が、隣接行列Fと状態ベクトルXを使って計算された状態と同じになるように、算術演算子が定義される。
【0083】
【数17】


要素xm, i of Xmは積をとる。そこで Xmのi 番目の横列ベクトルは次の通りである:
【0084】
【数18】


乗算算術演算子・が次のように定義される:
0・(&#45;
1) = (+1), 0・(null) = (+1), 0・(+1) = (+1),
1・(&#45;
1) = (&#45;
1), 1・(null) = (null), 1・(+1) = (+1). (3-1-4)
加算算術演算子 + が次のように定義される:。
(&#45;
1) + (&#45;
1) = (&#45;
1), (&#45;
1) + (null) = (&#45;
1), (&#45;
1) + (&#45;
1) = (&#45;
1),
(null) + (&#45;
1) = (&#45;
1), (null) + (null) = (null), (null) + (+1) = (null),
(+1) + (&#45;
1) = (&#45;
1), (+1) + (null) = (null), (+1) + (+1) = (+1) or (&#45;
1). (3-1-5)
したがって、等式(3-1-5)から、
n・(&#45;
1) = (&#45;
1), n・(null) = (null), n・(+1) = (+1) or (&#45;
1).
【0085】
【数19】


は +と同じ意味で使われる。したがって等式(3-1-3)は、以下のように表現される:
【0086】
【数20】


加算算術演算子 + の意味については、もし等号の左辺にただ1つでも(&#45;
1)があるなら、その右辺は(&#45;
1)である。そして、もし左辺に(&#45;
1)がないなら、たった1つの(null)さえあれば、右辺は(null)である。もし全部の左辺が(+1)であるなら、右辺は、ユーザの必要条件に依存して、(+1)あるいは(&#45;
1)である。
【0087】
true(+1)の状態、false(&#45;
1)の状態、そして未決定(undecided or null)の状態は、最小要素として(null)の状態を持つ、平坦な半順序を構成する。 (+1)、(&#45;
1)は同じレベルであり、すなわち、それはbool0(ブールゼロ)と呼ばれる領域である。制御のためには、未決定(undecided or null)の概念だけを使う。true(+1)の状態とfalse(&#45;
1)の状態とは、決定(decided) と呼ぶ同じレベルにあり、制御には用いられない。
【0088】
この数学的な構造を使って、全ての始点単語の状態が真(true or +1)であるとき、終点単語の状態は真(true or +1)になる。始点単語の状態が偽(false or &#45;
1)であるとき、あるいは全部の始点単語が真(true)であっても、ユーザの要件によって否定されるとき、終点単語の状態は偽(false or &#45;
1)になる。1つあるいはそれ以上の始点単語の状態が未決定(undecided or null)であり、始点単語の残りの状態が真(true or +1)であるとき、終点単語の状態が未決定(undecided or null)になる。
【0089】
一巡処理は Xm = FXm-1と表現される。 繰り返し処理は、次のように、連続的に処理を繰り返す:
【0090】
【数21】


Fm は普通の行列の積として、定義される。 Fm の( i, j )要素は非負の整数である。
【0091】
終点単語の状態は、一巡処理を繰り返す繰り返し処理を通して、未決定(null)から真(+1) or 偽(&#45;
1)のいずれかに変化する。ある特別な状態では、たとえ繰り返し処理の間に始点単語の状態が真(true 0r +1)、偽(false or &#45;
1)に変化しても、終点単語の状態は変化しない。閉じたループが有向グラフに存在し、始点単語がその閉じたループにあるとき、あるいはもしこのシステムが始点単語を持っていないなら、何度繰り返しても、終点単語の状態は未決定(undecided or null)のまま変化しない。「状態変化がない」(すなわち「不動点に到達した」)状態は


と表現される。そこで、等式(3-1-2)を使って、この状態は次のように示される:
【0092】
【数22】


この等式が成立するとき、プログラムが停止する。
2.モデルの活用
2-1. 数学的な構造モデルを使う
<3>.1で、数学的な構造モデルが確立された。ユーザ要件のすべての特性が隣接行列でだけ表現される。そこで、この隣接行列の特性を調べることは非常に重要で、そして有用である。隣接行列Fの特性を使って、不必要な繰り返しを避ける方法を示す。どんなプログラム(アルゴリズム)も、再帰的な方法を使うだけで実現できる。手続き上は、再帰は、whileループによって実現される。しかしながら、 単語を基礎としたプログラムでは、自分自身を始点単語として使用する割り当ては使うことができない。この状況を避けるために、一時的な論理レコードを導入する。それによって、手続き言語で表現されるすべての通常のアルゴリズムは単語を基礎としたプログラミングの構造で実現することができる。グラフ理論と隣接行列を使うこのモデルの多くの有用な特性は、システムの要件を検証するために使うことができる。
【0093】
行列Fはどのような特性を持っているか、行列 Fm の特性は何であるか、これらを調べるために、隣接行列の性質を示す定理 1 (非特許文献7参照)を導入する。
【0094】
空でない有限集合VとV*Vの部分集合Eとの対G=(V,E)のことを有向グラフという。Vの元は頂点あるいは単に点と呼ばれ、Fの元(u, v)は辺、矢と呼ばれる。Gの頂点の有限列
【0095】
【数23】


は各iについて
【0096】
【数24】


であるときvからvへの道といい、nをこの道の長さという。


をPの始点、


を終点と呼ぶ。


も長さ0の道である。道とは、Gの頂点の上を辺の矢印の向きに沿ってたどった経路のことである。
定理 1 Vなる有向グラフG =(V,E)の隣接行列をAとすると、Anの(i, j)成分はGにおけるviからvjへの長さnの相異なる道の個数である。
[証明] nに関する数学的帰納法で証明する。
【0097】
【数25】


とする。n=0のとき、長さ0の道の定義
【0098】
【数26】


によりviからvjへの道は〈vi〉のみであり、ならviからvjへの長さ0の道は存在しないから、
【0099】
【数27】


は定理の主張を満たす(Iは単位行列)。
【0100】
【数28】


の(i, j)成分は、
【0101】
【数29】


だから、
【0102】
【数30】


である。vjへ隣接する頂点をvkとすると、Gにおけるviからvjへの長さn+1の道はviからvjへの長さnの道に辺(vk, vj)をつなげたものである。帰納法の仮定から
【0103】
【数31】


はviからvjへの長さnの道の個数であるから、上式の右辺はviからvjへの長さn+1の道の個数を表していることがわかる。
[証明終わり]
m = 1, m = 2, &#188;
,から計算し、
【0104】
【数32】


が成立するとプログラムが停止する。
【0105】
X0のすべての要素が常にnullであるので、Fがシステムのすべての特性を表現する。
(1)F=0 where m≦nの場合
Fm のすべての要素が0である。定理1を使って、この隣接行列の有向グラフに、閉じたループが存在しないことが証明される。変数mはその有向グラフ上の最も長い道の長さを表す。Fの 固有値はすべて0である。べき零行列(Fm = 0)の特性から、正則行列Pを用いてF’=P-1FPとして、Fを対角要素が0である下三角行列F' に、書き替えることができる。
【0106】
【数33】


であるから、
【0107】
【数34】


が成立する。Xm のすべての要素は、(+1)あるいは(&#45;
1)である。
(2)F≠0 where m≦nの場合
この隣接行列の有向グラフに、もし閉じたループが存在するなら、F rの対角要素である
【0108】
【数35】


に1つ以上の整数が現れることが定理1を使って、証明される。したがって、変数rは閉じたループの最も短い長さを表す。Fの固有値はすべてが0ではない。すなわち、固有値の1つは0ではない。
【0109】
【数36】


は X0 のすべての要素がnullであるので成立する。変数m は、その有向グラフのループの前の最も長い道の長さを表す。 Xm の例は
【0110】
【数37】


などである。
2.2 不必要な単語の繰り返し処理をさける方法
<3>章2.1に示されたように、隣接行列が対角項0の下三角行列になるように単語の順序を並べ替えることで、繰り返し処理を避けることができる。解析的に正則行列Pを得ることは難しい。これを実現するために、我々は
【0111】
【数38】


を使う代わりにトポロジカルソートを使うことができる。半順序関係が与えられたデータに対し、比較不能なものは順序を構わず、比較可能なもの同士については半順序関係を満たすように並べることをトポロジカルソートと呼ぶ。半順序関係であるから、解がひとつとは限らない。トポロジカロソートは、有向グラフに対し、深さ優先の探索を行ない、行き着いたところから探索経路を戻るときに節点を拾っていくことで実現できる。単語を一列に並べる順序は得られた結果を逆順にすればよい。
図6に示された有向グラフの隣接行列は次の通りである:
ここで、a,b,x,y,z,u,vをこの順序でx、x、x、x、x、x、xと表現する。
【0112】
【数39】


トポロジカルソートの結果は(x1,x2,x3,x4,x5,x6,x7)&#174;
(x2,x1,x5,x4,x3,x6,x7)である。
【0113】
Fがトポロジカルソートされたとき、F' (sorted F )は次の通りである:
【0114】
【数40】


この行列を使うこと、すなわち、式(3-1-8)を上からそれぞれの行を実行することによって、処理は1回で完了する。プログラムの構造が要件を正確に把握するために分割されているなら、それをひとつに統合し、したがって隣接行列もひとつに統合されると、この方法を使うことによって単語の順序を並べ替え、処理時間を短縮することができる。
【0115】
個々の単語を作るプログラムの構造と単語の実行を制御する制御プログラムの構造を有向グラフとその隣接行列を基にした構造モデルで表現した。
単語の列のクリアと一時的な単語の数理的な原則
どんなプログラム(アルゴリズム)でも再帰的な方法だけによって記述することができる。手続き型のプログラミング言語(例えば、C、 java など)によって書かれたどんなプログラムでも、再帰プログラムと同じ役割を果たすwhileプログラムによって書くことができる。このことは、whileプログラムは理論的には、なんでもできることを示している。
【0116】
しかしながら、 単語を基礎とするプログラム法では、自分自身を始点単語として使用することができない。例えば、a = a + bを 単語を基礎とする プログラムでは使うことはできない。なぜなら、aは、一度決定(decided)になるとaの値は変化しない。したがって、再帰的使用のためには、一時的にaの値を保持する領域とクリアする方法が必要となる。保持された値を始点として使用する。この目的のために一時的に内容が保持される領域を持つことが必要である。この領域を一時的な単語と呼ぶ。クリアするために構造作用要素(Vector of Clear)が定義される。
【0117】
Lyeeでは一般に、作用要素は述語構造を持つ一種の単語である。プログラムコードの構造は単語と同じである。単語との主な相違は同時にふたつあるいはもっと多くの単語を扱っている。その意味は外部とのインターフェースおよび制御構造のための経路や領域のクリアである。表3は作用要素の定義である。
【0118】
【表3】


システムの隣接行列(システム全体の行列)は分割された隣接行列とただ状態を移すだけの接続行列とを使って、1つの行列に統合化される。接続行列は、他のグループ上の単語を始点単語として使うことを示している。したがって、単語を基礎とするプログラムの数学的なモデルを使うことが可能である。 それによって、手続き型の言語で表現することができるすべての通常のアルゴリズムは、単語を基礎とするプログラムの構造で表現することができる。
【0119】
前述のa=a+bのような、一時的な単語を必要とする集計処理の例である(例3)を用いて、接続行列による隣接行列の統合を説明する。
(例3)ファイルのある単語のそれぞれのレコードx、xの値は先頭から順番に合計し、集計結果を単語x、xに集計する。
【0120】
Lyeeでは、一度決定した値は上書きできないので、x=x+xのように記述しこれを再利用する。xは前回のxの値を代入するための単語である。xの値を、次の再利用時にxに代入するために、一時的な領域x4に転送される。「一時的な単語」と呼ぶ。この例3を有向グラフに表すと図7になる。単語x1、x2、 x3は、x3がxに転送されたときにクリアされる。単語x、単語x、単語xは、それぞれ単語x、単語x、単語xの再使用である。
【0121】
図7の再使用されるプログラムの部分の隣接行列(one path matrix)は以下に示すF1である。
【0122】
【数41】


F1を再利用するため、F1と再利用されたF1とを統合する接続行列(connection matrix)がF2 と F3である。これらは状態を伝達するだけの機能である。それぞれの終点単語が、始点単語としてどの単語を使用するかを示す。
【0123】
【数42】


F2は x1, x2, x3 からx4.への接続行列である。F3 は x4 から x5, x6, x7 への接続行列である。F2はx3 からx4.への出力、F3はxからx.への入力、のための作用要素として理解される。F1を再利用する全体システムの隣接行列がFである。
【0124】
【数43】


全体システムの隣接行列は一巡行列と接続行列とを使って表現される。したがって、単語を基礎とするプログラムの数学的なモデルを使うことが可能である。それによって、手続き型の言語で表現されることができるすべての通常のアルゴリズムは、単語に基礎とするプログラミングによって、その構造で実現することができる。
2.4 要件を有向グラフの理論を用いて調べる
単語の集合に有向グラフとその隣接行列を使うことによって、要件の正当性を論じることができる。このモデルで確認することができる要件は、制御特性についてだけに限定されている。すなわち:
(1)条件が排他的であること。xとyが排他的であるとは、 ((x &#179;
y) or (x < y))は常に真(true)であり、((x &#179;
y) and (x < y))は常に偽(false)であることである。
(2)定義されていない単語は始点単語として使えない。
(3)定義された単語はすべて出力単語の値の生成に関与すべきである。
(4)自分自身をその定義や条件として使わないこと。
【0125】
以下の3つの調査の方法を使うことができる、すなわち、半順序をなす単語の有向グラフ上を横断する方法と、隣接行列を調査する方法と、プログラムを実行する方法である。有向グラフにおいて、入ってくる矢のない節を始点節(initial)、出て行く矢のない節を終点節(terminal)と呼ぶ。DFSは深さ優先探索(depth first search)である。調査の方法は以下の通りである。
(1)すべての始点節(initial)は、入力単語であるべき。有向グラフで調べる。
(2)すべての終点節(terminal)は、出力単語であるべき。有向グラフで調べる。
(3)最後の出力単語より終点節側にある単語は無効である。もし、単語が有効なら、その単語の終点節側に出力単語が存在する。図8にこの状態を図示する。
<4>.リアクティブなプロセスのモデル
Lyee方法論では、プログラムの機能を、いくつかの基本構造の組み合わせで実現する。プログラムを基本構造に分割する目的は、単語の実行順序が仕様上明白なとき、その情報を積極的に活用し、設計を効率化するためである。リアクティブな仕様に現れる、画面の遷移、画面のコマンドによる処理の選別、データベースのアクセスキーの依存関係(データベースの親子関係)などには、明白な実行順序がある。画面の遷移の方法、データベースのテーブル構成定義等の仕様を、基本構造の組合せの選択をパラメータの選択で表現できるようにしたものが処理経路図である。これは、図として表現されるため、静的に表現されたパラメータの機能を、動的に追うことができるので、見てわかりやすく、追加・修正などの処理も、容易にできる。
【0126】
処理経路図を描くことは、基本構造の実行順序を制御するための宣言をすることであり、以下のように実施する。
(1)画面の遷移、データベースのアクセスキーの依存関係、画面のコマンドによる処理の選別等の、仕様上の要件にあわせ、基本構造を配置する。記述順によって実行順序を表現する。経路の実行条件は定義が必要である。経路の実行条件は、その経路上にあるすべての基本要素の実行に影響する。言い換えれば、その経路上にあるすべての基本要素の実行条件をまとめて、括りだしたものと考えられる。経路の実行条件は排他的でなければならない。排他的になっていないと、実行されない経路が宣言される可能性があり、これは、基本要素の実行条件(等価条件)と同様である。
(2)基本構造の配置が決まると、深さ優先探索を実現するように経路の作用要素が自動的に配置される。訪問済みフラグのような、実行を制御する制御フラグの設定も自動的に行われる。
(3)部分的繰り返しのための経路の実行条件は、仕様に従って定義し、経路の作用要素の実行条件として入力する必要がある。すなわち、いつまで繰り返し実行を続けるかの、条件である。また、繰り返しを実行するためには、基本構造内の基本要素を未決定の状態にしなければならない。単語、入出力作用要素のクリアの設定(クリアの対象領域の決定と実行条件の設定)は自動的に行われる。
(4)集計する必要があるときは、集計単語を配置する。集計であることを示す宣言が必要である。この領域のクリアは出力時、自動的に行われる。部分的繰り返しにおいて、前回実行結果の値を次回使用するときは、それを保存するための領域の確保する必要がある。これが集計単語である。内部記憶の代わりである。
【0127】
部分的繰り返しや集計の機能を、ひとまとまりの機能として、少数のパラメータによって宣言することができず、手続き的に、多くのパラメータを設定せざるを得ない部分があり、ツールの改善が期待される。また、無駄な探索を省略するための、深さ優先探索をそこなう経路の作用要素があり、その使用には、注意が必要である。
1.1 処理経路図とプログラムの動き
図9に示す、画面イメージを持つアプリケーション・システムを例に取り、処理経路図とプログラムの動きを説明する。この画面ではプログラムは、始動されると、初期表示として、ファイルからaとbとを読み取り表示して、停止する。ここで、cに入力して、Enterボタンを押すと、cの値が、ファイルに記憶されるものとする。Exitボタンを押すとプログラムが終了する。このプログラムの動きは、図10のように表現され、処理経路図(非特許文献8参照)では、図11に示したものになる。
【0128】
図10及び11において、一番外が、基本構造(Basic Structure)S1のループ、その中に、S1R1、それと同列でさらに、S1R2ループがはいっている。S1R2ループには、その中に、S1R3ループが入っている。処理経路図(図11)で右へと展開されているのは、ループの中であり、下へと展開されているのは、同列の処理である。右への展開は、サブルーティンのように考えられる。下への展開は、並んだ順序で、順番に実行される。画面のコマンド、Exitに対応し、もしEnterボタンが押されたならS1R2へ、ExitボタンならEXITへという使い方が一般的である。すなわち、下への展開は処理の選択である。
【0129】
プログラムは、基本的に、繰り返して使用される。上の例では、プログラム全体が、繰り返し使用される例である。最後のS1に戻って、出力後、クリアしているのが、この準備である。部分的に繰り返す場合は、繰り返すところに、自分に帰る経路を置く。これによって、これより右の部分が繰り返される。このときは、何をもって繰り返しを終了するかを、示す必要がある。これは、たとえば、EOFを検出したら、Write件数(カウンタ値)=定数を満たすまで繰り返せのように、表現する。Lyeeの構造が、値が決まっているか否かということをフラグとして使っているため、繰り返すためには、領域を、未決定を示す値でクリアし、かつ入力の作用要素のもつ実行済みフラグをクリアする必要がある。Lyeeでは、領域がクリアされているか否かが、フラグのように、実行するか否かの判断に、使用されている。
【0130】
ある項目(単語)を、複数のレコードに渡って集計するためには、1レコードを読むという入力作用要素を複数回使う必要がある。それぞれの回の結果は積算する必要があり、そのための単語モジュールをつくる。これを集計単語と呼ぶ。平均をつくるためには、何回集計したかを数えるカウンタも必要である。これは、入力作用要素で準備される。Lyeeでは、これらの機能は、単語モジュールの定義と経路の選択とで実現する。すなわち、集計単語をおく、繰り返しの経路を選択して、繰り返しの範囲と終了条件などを設定する、などである。これらは、入出力作用要素、経路作用要素、構造作用要素(クリアを行う)に展開される。
1.2 システムの分割
単語を基礎とするプログラムでは、要件は単語の集合として捉えられる。すべての要件は単語として捉えられる。単語は記述された順序で実行されるが、結果はその記述順序に影響されないという1つの特徴がある。しかし、単語の定義時点で、とくに単語の生成条件を決定することは大きな困難を伴う。条件には2つの種類がある。ひとつは例1のC > 0のような個々の単語につく実行条件である。単語の値を生成する条件は、単語の実行条件として、単語の内部に置かれる。もうひとつは、単語のグループにつく条件で、Read、Write、Clearなどの条件がある。実際の要件を現す単語において多くの単語が同じ条件をもつ。たとえば、
(1)機能ボタンを用いて、画面から同時に入力された単語
(2)ファイルの1レコードから入力された単語、ひとつのキーによって、ファイルの1レコードに同時に出力される単語
などは、同じ条件をもつ。
【0131】
我々は単語のグループという概念を導入する。それは論理レコード(logical record)と呼ぶ。ロジカルレコードを有効に機能させるため、Lyeeでは、基本構造、経路の作用要素、そして表現の手段として処理経路図が導入されている。これらの概念はいずれも単語のグループという考えを実現する手段を与えている。
【0132】
要件を定義する初期の段階で、処理経路図を描き、要件から論理レコード(単語のグループ)を見つけ出し、基本構造を作り出すことは、単語の定義、とくに実行条件の定義に有効である。この考えは、Lyeeの方法論の中心にあり、我々も、Lyeeの命名法にしたがう。これらの概念を説明し、前に述べた我々のモデルをこれらの概念に合わせて修正し、このモデルを用いて、Lyeeの改善を行う。
1.3 システムの基本構造への分割
Lyeeでは、類似の条件をもつ単語をグループとして分割する。それを我々は論理レコード(logical record)と呼ぶ。出力のために同時に生成される単語のグループはひとつの基本構造に配置される。これはLyeeの原則(ルール) (非特許文献6参照)である。したがって、システムはいくつかの基本構造に分割される。これを表現する手段として、処理経路図が使われる。基本構造のつながり方を示す図を処理経路図(Process Route Diagram)、または、PRDと呼ぶ。図12はその例である。
【0133】
第1基本構造にある単語の、ある始点単語が未決定(undecided)であり、したがって出力単語の状態が未決定(undecided)ならば、次の基本構造が、深さ優先で探索され、下位の第2基本構造に到達する。第2基本構造が実行されもし未決定(undecided)の出力単語が無くなると、初めに、未決定(undecided)の出力単語の現れた第1基本構造に戻る。そして処理は繰り返される。処理はすべてのシステムの状態の変化が終わるまで続く。
1.4 経路の作用要素とその実行条件
次に実行する基本構造を選択するために、経路の作用要素の実行条件が用いられる。経路の作用要素の実行条件はそれによって指定された基本構造上のすべての単語の実行条件の一部である。このことは、この基本構造上のすべての単語がこの条件をみたすことを意味する。経路の作用要素の実行条件は作用要素からそれぞれの単語へ移動することができる。このように移動すると、経路の作用要素の役割はただ、基本構造がどの時点で稼動すべきかを示すだけになる。深さ優先で探索されことによって、隣接行列上から経路の作用要素を取り除くことができる。
【0134】
経路の作用要素とその条件の、隣接行列モデルとの関係を説明するため、例を示す。図13はこの事例のシステムの画面イメージである。c、dは、入力である。この事例では、ボタンaが押されると、式e = c + dを用いてeが計算されgに出力される。ボタンbが押されると、f= c ´
dを用いてfが計算されgに出力される。経路の作用要素の役割を説明するため、3つの基本構造を導入する。BS1は画面用、BS2はe = c + dの計算用、BS3はf = c ´
dの計算用の基本構造である。gは、if a, then g=e, if b, then g=f.を意味する。図14はシステムの有向グラフであり、ボタンaとボタンbとを含んでいる。BS1(入力)の隣接行列F1、BS2とBS3の隣接行列F2、BS1(出力)の隣接行列F3を以下に示す。
【0135】
【数43】


この行列はeとfとが独立していることを表している。すなわち、それぞれの終点単語は、互いに他の基本構造の単語を始点として使わない。
【0136】
【数44】


接続行列は、
【0137】
【数45】


これらの行列が統合され、1つのシステム行列F.となる。
【0138】
【数46】


経路作用要素の実行条件はその経路作用要素が指定する基本構造のすべての単語の実行条件の一部である。すなわち、その基本構造のすべての単語は経路作用要素の実行条件を満たしている。経路の実行条件”if a”はXrからeのようなBS2のそれぞれの単語へ移動できる。”if b”はfのようなBS3のそれぞれの単語へ移動できる。そうすると、1回の実行で完了する単語の再配置の後に、隣接行列から経路作用要素Xrを取り除くことができる。
【0139】
【数47】


システム行列Fは


と表現される。
【0140】
【数48】


この事実に従って、それぞれの単語の条件を探す代わりに、経路作用要素の実行条件を付けることはユーザが要件を定義する作業の効率を上げる。経路作用要素の実行条件を付けることは、結果的に、あらかじめ、どの基本構造を実行するかを決めることになる。
この事例からいえることは、a、bは、画面のボタンであり、a、bは互いに素で排他的な集合である。a=true, b=true状態は、同時には成立しない。aがtrueなら、bはfalseである。単語a、bはどの基本構造をactiveにするかを決定するために用いられる。もし、BS1の経路の作用要素の実行条件がa = trueであれば、BS2のみが実行される。逆に、もしb = trueなら、BS3が実行される。
【0141】
次章では、プロセス・モデルを用いて、要件の把握のため、さらに良い方法をさぐる。単語の実行条件の把握の困難さの原因を、単語を基礎とするプログラミングをプロセス制御やゲームに試験適用する体験から、外部との対話性にあると考えた。リアクティブなシステムのモデルとしてよく用いられるプロセス・モデルで、要件を捉えたとき、その要件を単語を基礎とするプログラミングであるLyeeで、どのように実現するかを示す。そのとき、リアクティブなシステムのプロセス・モデルとLyeeで用いられている処理経路図との関係を検討し、基本構造単位に分割して仕様を捉えることの意義を明確にする。
2.プロセスモデルによるLyeeの考察
ビジネスアプリケーションでは要件定義として
(1)画面、帳票、外部DBレイアウト
(2)画面遷移、外部DB 構成定義
(3)単語の定義
が、あたえられる。
【0142】
単語の定義とは、if C then A:=Bのような生成条件と生成式とを定義することである。
【0143】
ここで、問題は生成条件が正確に把握できるかである。
【0144】
生成条件には、
1.単語の生成式を選択するもの
2.この単語を実行するか否かを判断するもの
がある。後者を個々の単語ごとに、要件から判断することは難しい。そのため、上記、(1)(2)によって、単語の定義以外に、単語のグループ毎にそのグループ分けと実行の順序を要求している。これは、単語の定義がすべてであるという、Lyeeの原則に矛盾する。
【0145】
これを解決するのが処理経路図を描くこと、すなわち基本構造への分割することで実行条件を捉える方法である。しかし、分割の根拠、方法が明確に規定されていない。ビジネスアプリケーション以外のシステムにLyeeを適用する事例から、この原因は、要件がリアクティブであることを明示的に捉えていないことにある、と想定した。そこで、リアクティブ・システムのモデルとして、プロセス・モデルを導入し、基本構造およびその分割について解析し、分割の根拠(どのように分割すれば単語の条件が捉えられるか)を明らかにする。さらに、どう基本構造に分割したまま実装するかという問題に対して、解決を与える。
2.1関数モデルの限界
数値計算やバッチ処理、プログラムのコンパイル、野球のシミュレーションなどを行なうシステムは、入力値から出力値への関数としてとらえられる。ここでは途中状態は重要ではない。
【0146】
【数49】


一方、オペレーティング・システム、現金の自動支払機などのリアクティブ・システムを同じように関数としてはとらえることはできない。画面で人と会話し、サービスの提供を行ない続けることが要求される通常のビジネス・システムもリアクティブなシステムである。実現しようとしているのは、サービスの提供を行ない続けることが要求されるシステム、外部からの入力に対する反応を継続するシステム、すなわちリアクティブなシステムである。実現したいシステムの要件が、関数だけで表現できない、リアクティブなシステムであることに原因があると推定した。
2.2. リアクティブなシステム
リアクティブなシステムは以下の特徴を持つ。
計算の継続性
「プログラムの実行停止時の出力」を考えることは目的にかなわない
システムの外部との対話性
画面を通じて人と対話する
データベースシステムを通じてファイルと対話する
多くの場合、並行性、すなわち、複数の計算主体(プロセス)を持つ
リアクティブ・システムは、単一の計算主体から構成されることもある。しかし、リアクティブ・システムが意図したとおりに動作することを確かめるために、このシステムと、システムと対話を行なう外部とから構成さえるより大きなシステムを考え、その性質を調べることは、有効である。対象とするシステムを、人とシステムとの2つのプロセスをもつリアクティブ・システムと捉え、モデル化する。
2.3 プロセス・モデル
プロセスは、計算主体である。それぞれのプロセス(計算主体)は、他のプロセスと通信を行ないながら並列に動作し、そのロケーション(プロセスの実行状況)を変える。このような、プロセスの動作(アクション)を以下のように表現する。
【0147】
【数50】


プロセスのアクション t
ロケーション α、β
実行条件 B と コマンド A
すなわち、プロセスの動作は、「ロケーションαにいるときに、共有変数の値がBを満たせば、共有変数への値の代入Aを行ない、ロケーションβへ移動する」という形をした規則によって定義する。
【0148】
ロケーションとは、プロセスの実行状況のことである。システムの内部状態の一部である。ロケーションは、プロセスの大局的な状況である。ロケーションは全プロセスに共通する。しかし、すべてのプロセスがすべてのロケーションを持つ必要はない。ロケーションとは、プリンタがファイルを印刷中とか、自動販売機にコインが投入されジュースの選択ボタンが点灯している状態などである。ビジネス・アプリケーション・システムでのシステム・プロセスのロケーションは、画面から人プロセスの入力待ち、ファイルアクセス中、計算中等である。
【0149】
共有変数とは、すべてのプロセスで共有する変数であり、どのプロセスからも読み書きできる変数である。外部からの入力を受け取ったり、データの送受信を行なったり、計算実行のタイミングを整えたりするために、プロセス同士で行なう通信を、プロセス間通信とよぶ。共有変数は伝言板型(bulletin board type)のプロセス間通信の手段である。
2.4 事例
人と応用システムとの2つのプロセスからなるリアクティブ・システムでは、次のようなプロセス間通信が行われる。人プロセスは、Keyを画面から入力し、実行ボタンを押す。応用システムはデータベースを読んで、画面に表示する。人プロセスが再入力し実行ボタン、または、終了ボタンを押す。S はロケーションの状態を表す共有変数であり、S=0は入力中、S=1は計算中、S=2は終了を表す。共有変数の値の組み合わせがロケーションを規定する。図15にプロセス定義を示す。
【0150】
プロセスはHuman:P、および応用システムComp:Qであり、ロケーションはa, bは、それぞれ、aは、Human:Pが入力中、Comp:Qは待機中 を表し、bは、Comp:Qが計算中、Human:Pは待機中の状態を示す。初期ロケーションはaであり、図中の{S=0}は、初期状態を表す。
【0151】
以降では、応用システムのプロセス定義が、処理経路図と対応することを、3つの異なる応用システムの事例を上げて示す。
<事例1:成績管理>
この例題の要件は、学生の成績を管理するものであり、3画面、4ファイルで構成されている。ID・パスワードの確認画面、学生名の登録画面、成績の登録・参照画面と、教官のID・パスワード、学生名、試験別成績、総合評価のファイルが、存在する。
【0152】
共有変数は、OK, Exit, Stop1,Reg1,Ret1, Stop2, Reg2, Clk, Ret2, Stop3 である。OK, Exit, A, P, Reg1,Ret1, Reg2, Clk, Ret2は、画面から入力される画面の遷移情報を表し、A, Pは、ファイルから読み込まれた情報による遷移の行き先を示し、Aはアドミニストレータ、Pはプロフェッサーが次の入力を行うことを表す。Stop1、Stop2、Stop3はファイル読み込みの繰り返しの終了を意味し、DBMS(database management system)からの終了情報に対応する。図16に、成績管理システムのプロセス定義を示す。図16の初期ロケーションは1であり、{ OK=0, Exit=0, A=0, P=0, Stop1=0, Reg1=0, Ret1=0, Stop2=0, Reg2=0, Clk=0, Ret2=0, Stop3=0}は、初期状態を表す。応用システムのプロセス定義はそのまま処理経路図になる。図17に処理経路図を示す。
<事例2:オセロゲーム>
ゲーム(Othello)の事例である。盤、駒、競技者(人とコンピュータ)、対戦(交互に駒を盤に置く)、手、先手、後手、ルール (挟めるところに置くこと)、終了判定、勝負判定をプロセス・モデルでモデル化した。入力はゲームを開始すること(主催者とEnter)、先手を決めること(審判とEnter)、人が駒をおくこと(競技者とEnter)、出力は盤と駒の表示、ルール違反の再入力要請、終了時の勝負判定結果の表示である。盤に相当するひとつの領域に交互に積算し、結果を他のプロセスが終了判定に用いる。盤をあらわす領域は単語ではなく集計領域と同様に主メモリ上に行列として取っている。コンピュータのとる戦略は経験的(heuristic)な定石とミニマックス法(Minimax)との2つであり、残り10手になると、ミニマックス法で、全手を試す。この部分は関数であり、サブルーチンとして単語の生成に用いた。
【0153】
Cは盤(着手)に相当する共有変数であり、ゲームの進行状態を示す。Cを変えるプロセスは、プレイヤーとシステムであり、ロケーションが分散している。図18はプロセス定義を示す。図18の初期ロケーションは1であり、{S=0, K=0, H1=0, H2=0, C=0}は、初期状態を表す。プロセス定義はそのまま処理経路図になる。図19は処理経路図である。
<事例3:ビル監視>
図20に示す建物の、セキュリティ・省エネルギーを監視するシステムである(非特許文献18参照)。人の動きや屋外の明るさを検知し、それに応じて建物に対する外部からの侵入の警報を発したり、部屋や廊下の照明のオンオフや明るさを制御するプロセス制御システムである。入力は、人を検知するセンサ(image sensor)、ドアコンタクトセンサ(door contact)、屋外光センサ(outdoor sensor)、タイマ、部屋盤、管理盤などであり、出力は、管理盤へ警報、照明のコントローラ、タイマなどである。
【0154】
要件上の共有変数としては、人が不在になってからしばらくしてから消灯するための、みなし在室Zなどが必要である。図21には、みなし在室Zに関係するプロセスのプロセス定義を示す。ロケーションは個々のセンサの入力待ちの状態を表す。このようなプロセス定義では、同時に起こる可能性のある状態を表現できない。そこで、みなし在室Zを計算するタイミングを与えるため、Zに関与するすべての外部プロセス(センサ)からの入力によって起動されるロケーションを設置し、そこに計算する単語Zを配置する。ロケーションが同じでプロセスが異なる。Z は、照明コントローラに値を設定する屋外光センサの起動によって、値の生成に用いられるので、その単語も同じロケーションに配置する。共有変数であるみなし在室 Z を共有する各プロセスが1つのロケーションになるように、分割する。図22に示すように、コンピュータシステムは、それ自身は外部のプロセスに対して、並行性を持たない(マルチプログラミングでない)ので、ひとつのロケーションですべてのプロセスからの入力ができることが必要である。図22はプロセス定義から処理経路図への展開、図23に全体の処理経路図を示す。
2.5 プロセス・モデルのまとめ
考察の結果は以下の通り集約される。
事例1 成績管理 ひとつの共有変数を、2つのプロセスが交互に変化させる。集計、シーケンシャル・リードなどの実現方法は準備されている。
事例2 Othello ゲーム 2つのプロセスの結果が共有変数Cに積算されて、終了判定に用いられる。積算領域は共有変数Cである。
事例3 プロセス制御 複数のプロセスがひとつの共有変数を変化させ、別のプロセスが、その結果を使う。
本来、宣言的な仕様によるプログラム開発では、実行順序などの手続き的な要素は、自動的に生成されることが望ましい。要件をプロセス定義で表現することによって、捉えにくい単語の条件が容易に捉えられるようになる。
【0155】
要件をプロセス定義で表現し、それを処理経路図に展開するとき、必要なすべての情報が得られれば、Lyeeで実現可能といえる。しかしながら、処理経路図には、プロセス定義に含まれない実行順序の情報が含まれる。処理経路図は実行の順序を与える。すなわち、計算資源がスケジュールによって、与えられる必要がある。通常のシステムでは、優先度の差はあるにしても、プロセス同士の公平性はスケジュールによってある程度保たれる。ロケーションの遷移に必要な計算資源はスケジュールによって与えられるべきである。
順序に関する情報は、成績管理、ゲームでは、プロセス定義で表現がほぼそのまま,処理経路図になる。これは、アクションの実行条件が排他的かつ完備であるからであるから、すなわち、プロセスが、人、データベースマネジメントシステム(DBMS)、および応用プログラムであり、かつ個々の外部プロセスに対応する応用プログラム側のロケーション(画面、データベース入出力)が、それぞれ異なるから、実行条件がそのままスケジュールになる。
【0156】
プロセス制御のケースでは、外部プロセスからいつでも入力可能である必要があるため、ひとつの基本構造ですべての外部プロセスから入力ができることが必要である。これは、画面の設計に相当する設計作業でなされるべき判断である。また、複数のプロセスの同一ロケーションのアクションをひとつの基本構造で実現する。複数のプロセスが状態を共有する必要があるときは、1つのロケーションとする必要がある。
2.6 これをLyeeで実現する
プロセス・モデルをLyeeで実現するには、プロセス定義における共有変数を、Lyeeの構造の上で確保することが重要である。その方法は
(1)入力単語として(Functionボタン)
(2)イベントを起こしたプロセスを区別する単語であり、単語のまま、共有変数として用いる。単語であるがそのスコープは共有レベル(後述)の変数である。
(3)制御フラグとして(終了フラグ)
データベース等の内部プロセスの終了を示す制御フラグは共有変数として用いる。
(4)主メモリ上のTableとして
システムの要件から作られる共有変数は、Tableとして主メモリ上に置く。ゲームの盤(着手)のように、異なるプロセスが、異なるロケーションで、交互に共有変数を更新する場合は、上書きを許さない単語レベルのスコープでは実現できない。
である。プロセスが人とコンピュータ、画面、ファイルとからなるビジネス応用システムのための共有変数は、Lyeeでは統一された考えはないが、準備されている。これ以外の方法として、内部テーブルとして共有変数を確保することは可能である。しかし、なにを共有変数とするかは、要件の理解によるプロセス定義(設計)が必要となる。
【0157】
単語を基礎とするプログラムの構造が、単語に要求している前提条件は、ある単語領域は1つの単語だけが値を設定することであり、一度、設定されると変更されない。この条件を満たさない共有変数は、フラグやテーブルとして、配置する。システムの要件から作られる共有変数は、テーブルとして主メモリ上に置く、あるいは、内部ファイル上に置く。共有変数を、主メモリ上に置くか、内部ファイル上に置くかは、応答性によるが、論理的には同じである。現時点では、Lyeeのツールによる支援は、ビジネスアプリケーションに特化しているが、主メモリのテーブルを活用することによって、単語を基礎とするプログラミングは、プロセス・モデルによる要件の提示に対しても十分に機能する。
2.7 共有、単語、単語内の3 レベルの変数のスコープがある
Lyeeにおける、単語の実行条件の把握に困難を伴うのは、要件がリアクティブであることに起因する。リアクティブなシステムを表現するプロセス・モデルでは、プロセスで共有する共有変数が必要となる。Lyeeで用いられる変数には、共有、単語、単語内の3 レベルの変数のスコープがあると考えることによって、Lyeeは、プロセス・モデルの基に、統一的に解釈できる。共有レベルの変数(Shared variable level)はプロセス・モデルの共有変数と考えられ、他のプロセスに基づく基本構造間で共用(読み書き)される。単語(word level)はロケーションに相当する同一基本構造内で共有される(読む共有だけで書き込みは共有されない)。単語内で用いられる変数(Inside Word level)はその内部に限定され、共有されない。Lyeeにおいては、単語内のみで用いられる変数は存在しない(II章3.1の局部変数の説明参照)。プロセスに共有される変数を、ひとつの単語で表現するためには、複数のプロセスの同一ロケーションのアクションをひとつの基本構造の一つの単語で実現する。図24は、以上の変数の位置づけを図示したものである。
2.8. 基本構造はどこまで分割すべきか
単一の基本構造内(単語のグループ内)では、単語の成立順序は始点、端点の関係で決まる。一方、基本構造を単語1つにまで分割すると、すべての単語の順序は、基本構造の順序として個別に設定することになる。始点、端点の関係以外で順序が決まるのは、プロセス定義上のアクションに、他のプロセスに基づく実行条件があるときであり、このとき、基本構造の成立順序は、アクションの実行条件で決まる。複数のプロセスから共有変数が作られる(共有される、すなわち読み書きされる)とき、共有変数は、各プロセスの、そのロケーションでのアクションによって変えられる。したがって関与するプロセスはそのロケーションを取ること、これが論理上必要な基本構造である。
【0158】
分岐はひとつのロケーションに複数のアクションがある状態である。基本構造はロケーションを表現すると考えると、基本構造には、そのロケーションのそれぞれのプロセスに対するアクションが定義される。一度開始されると他の計算や動作による割り込みを許さない一連の不可分な計算や動作をアトミックアクションとよぶ。基本構造に分割すると、ロケーションが分割され、したがってアクションが分割され、アトミックアクションでなくなる。単一のロケーションでのアクションは連続実行が保証される。複数のロケーションに渡る場合は、連続実行は保証されない。このことは、並行システムでは問題である。とくに並列(物理的)システムでは、計算が複数のプロセスで実施されるため、クリティカル資源(一度にひとつのプロセスしか使用できない)である共有変数は相互排除性の検証が必要となる。共有変数はクリティカルな資源である。クリティカルな資源を取り扱うロケーションは、危険領域と呼ばれ、これは分割できない。分割すると意味が変わる。
【0159】
共有変数には、複数のプロセスから変更される、共有変数がある。これらの共有変数が同期していること、すなわち、同じロケーションの中で関連付けられて変更されることが必要である。
【0160】
分割の根拠を「複数のプロセスから変更される共有変数は、ひとつのロケーションで変更されること」におくことによって、基本構造の分割が明確に定義される。このロケーションの分割が、基本構造の分割の単位となる。
【0161】
システムの状態とは、共有変数の状態とロケーションの状態(どのプロセスがどのロケーションにいるか) の無限列であり、これを用いての、安全性、デッドロックの回避、部分的正当性、相互排除性、応答性、全体的正当性等の検証は、時制論理(命題の真偽値が、時間の経過に伴って変化する状況を扱うための数理論理学)による。状態の場合分けの少ない場合は、モデル検証法によって、すべてのケースをたどることで、検証できる。
<5>.効果的なプログラムの生成
現状では、Lyee方法論に基づくツールによって生成されるプログラムは、設計時点で分割した仕様を,分割した状態でプログラムモジュールに展開したものである。確かに、要件に明白に表されている順序に関する情報を設計に活用することは、設計の精度をあげ、効率化に役立つ。しかし、Lyee構造のプログラムは、実行前に、静的に解決できる問題点を、実行時点で動的に解決しているため、コードのサイズは大きく、処理速度も遅い。ここに改善の余地がある。設計の効率化の効果を生かしつつ、プログラムの意味を変えずに、初めから基本構造に分割せずに、プログラムを生成することが出来る。そうすることによって、単語全体は1つの領域となる。したがって、単語の関係が作り出す有向グラフ上のトポロジカルソートで、単語全体の正しい順序が決定されると、順序性を確保するための繰り返しは不要となる(非特許文献1参照)。したがって、繰り返しは、プログラムの再利用の場合に限定される。
1.リアクティブなプロセスのLyeeによる実現
具体的方法を示す前に、半順序集合の元を要素とする配列が与えられたとき、それをトポロジカルソートするひとつのアルゴリズムを示す。
Lyeeの仕様を単語の系で表現すると、第II章より、Lyeeにおける仕様は以下のように表現される。
x = F ( x) (2-1-3)
である。
ここで、汎関数Fは以下で定義されたものである。
F(x)(i) = fi ( x(1),x(2),&#188;
,x(n)), i = 1,2,&#188;
,n (2-1-2)
順序集合(A,


)の空でない部分集合Bが


の下で全順序集合であるときBを鎖といい、Bのどの2元も比較不能であるときBを反鎖という。1回の反復処理で、右辺の始点が定義されている数以上の端点が定義されるため、Fは単調である。したがってFを繰り返すことによって、次々に生成される反復列
【0162】
【数51】


は鎖である。ここで、kは反復の回数である。最小の反復の回数は最大の鎖のサイズである。一般に、以下の定理によって、半順序集合は、反鎖に分割できる。
[定理]
半順序集合(A,


)の最大の鎖のサイズをnとすると、Aはn個の互いに素な反鎖に分割される。
この定理は、数学的帰納法によって証明される。この定理を半順序集合である全単語に適用すると、以下のことが言える。すなわち、全単語は、その中では順序がないn個の単語の集合に分割される。反復列(数51)の長さ(サイズ)nは単語の始点と端点の関係から求まる鎖のうち最大のもの、すなわち、同期するまでに必要な最小の反復回数を示す。この定理の証明は、半順序集合の元を要素とする配列が与えられたとき、それをトポロジカルソートするひとつのアルゴリズムを与えている。すなわち、Anを反鎖とすると、入力側から、A1,A2,をAn+1=0となるまで次々と求め、Anの元を適当な順序で並べ、その後にAn−1の元を適当な順序で並べ、最後にAの元を適当な順序で並べれば、昇順にトポロジカルソートできる。ここでAは極大元の集合である。ここでは、すなわち、出力側に一番近い単語の集合である。このように並べた単語はA1(入力側)から実行すれば、1度の処理で、すべての単語が次々と成立する。
基本構造を1つとし、単語の並べ替えを行なう。この方法によって生成されるプログラムは以下の構造を持つ。
1) 値の生成のためのW04論理要素はW03へ置く。
2) W03論理要素とW04論理要素とを統合した単語とする。等価単語はひとつの単語に統合したものとする。
3) スタート画面のW04にすべての基本構造上の単語を置く。このとき、経路の作用要素についている実行条件はそれぞれの単語に展開する。経路の作用要素は、展開しない。
4) すべての単語と入出力作用要素に対して、その始点と基本要素との関係を有向グラフ(Directed Graph)で表現し、上記の方法で、トポロジカルソートして順序を決め配置する。パレット内の反復は不要となるため設置しない。パレット領域のクリアも、不要となり、設置しない。
5) Control Areaのフラグ、入出力の作用要素のフラグは、クリアが必要であり、そのまま置く。
この結果、
1)同じ基本構造に属していた単語と入出力作用要素は、その基本構造の経路作用要素についていた実行条件が等しく展開されるので、同一の実行条件を持ち、従って、ソート後もひとまとまりのグループを作り出す。
2) 結果的に、経路の実行条件により、基本要素が再グループ化され、そのグループの中では、基本要素は上から実行順に並ぶ。
2. 実施例と評価
この例題の要件は、学生の成績を管理するものであり、3画面、4ファイルで構成されている。ID・パスワードの確認画面、学生名の登録画面、成績の登録・参照画面と、教官のID・パスワード、学生名、試験別成績、総合評価のファイルが、存在する。1人の学生に対して試験別成績の一覧を表示するような、同じ処理の部分的繰り返しや、平均点の算出のための、集計計算を含んでおり、上に述べた基本的な処理を網羅している。仕様言語は、C++,画面部のみC++の機能を用い、残りは、Cの文法のみで記述している。データベース・マネージメントシステムは、Access 97 (商標)with DOA である。図25に設計時点での処理経路図を示す。
【0163】
設計時、9基本構造に分割した要件を1基本構造のプログラムに統合した形で、実装した。プログラムの生成は、LyeeALL2(Lyee構造プログラムのコード自動生成ツール)を用い、そのテンプレート(基本要素および制御プログラムの雛形)を基本構造統合型Lyeeプログラム用に製作変更して、コード自動生成した。図26は、統合型新プログラムコードの一部である。新プログラムの7行目は、経路の実行条件、すなわちプロセス定義における実行条件であり、基本要素はこれによって再びグループ化している。W02 パレットにあった基本要素は、ソート後の順序に並んでいる。単語は、11,12,13,14行のように生成式のみが残る。
基本構造を分割した状態で生成したLyee構造のプログラムと、Lyee方法論による新プログラムと比較すると以下の通りである。この実行ステップ数と時間は、「7人の学生からひとりを選び、5試験の成績を表示させる」という要件のプログラムのときのものである。CPUプロセス時間はデータベースのアクセス時間を含まない値、Totalプロセス時間はデータベースのアクセス時間を含む全時間である。処理時間は、プログラムにタイムスタンプの機能を付加し、開始、終了との差として求めた。
【0164】
従来Lyee構造 新プログラム
プログラム行数 213,559 行 6,889 行 31%
CPUプロセス時間 150 msec 25 msec 15%
総プロセス時間 470 msec 345 msec 73%
実行コードの減少は主に、単語の構造が小さくなったことと、基本構造が1つになったことによる。主な変化点は、
1.述語構造はおおよそ21行から成る。これが、通常、代入式1行から成る生成式のみとなる。
2.W03の生成条件とW04の生成式とは1つに統合される。
3.作用要素については、経路の作用要素は一つのIF文となる。入出力の作用要素はほぼそのまま残る。
4.80%のクリアの作用要素は取り除かれる。
5.一つの基本構造は単語や作用要素を除いて約24KBを必要とする。この事例では、9個の基本構造が1つになる。
実行ステップ数の減少と実行時間の減少は主に繰り返しが減ったことによる。主な変化点は、
1.すべてのパレットは最低2回繰り返され、基本構造は最低3回繰り返される。これが、1回になる。
2.プログラム・コードは、31%に削減される。
3.しかし全プロセス時間は、それほど減少しない。データベースのアクセス時間が支配的であるためである。
4.前に事例として述べた、事例4:ビル監視のようなプロセス制御では、リアルタイム処理ではデータベースを用いないので、CPU時間が支配的である。新方法は、プログラムの大きさ、処理時間ともプロセス制御の場合に効果が大きい。
従来の構造型プログラミングによるプログラムと比較すると、以下のことが、言えるであろう。現時点で、この仕様に基づく従来の構造型プログラミングによるプログラムは、未完成であり、また、従来法はプログラマの技量によるため、定性的比較に留める。
1)プログラムの設計
単語の実行条件は、プロセス定義のアクションの実行条件として、捉えることができ、従来のLyeeにおける設計上の困難が減少する。Lyeeの利点である、宣言的に仕様を捉えることは、新プログラムではプロセス定義と単語の定義で実現される。従って、新プログラムでは、プロセス定義によって制御のための手続きが実現されるため、プログラムの設計は必要ない。従来法では、仕様を基に何らかの設計が必要である。
2)プログラムのサイズ
従来の構造型プログラミングによるプログラムと比較し、新プログラムにおいて、構造上明らかに増加しているコードは、ない。
3)実行速度
新プログラムでは、繰り返しの回数は必要最小な数に限られるため、従来型プログラムに比べて実行速度が遅くなる理由はない。
<6>.結論
単語を基礎とするプログラムは、Lyee方法論をその基本におき、そこから、数理的に必要かつ正しい部分を抽出し、再構築するものである。これを宣言的プログラミングの手法の1種と捉えると、Lyee構造は、受動的制約のみの制約手続き型プログラミング方法といえる。その実装は手続き型言語を用いている。Lyee方法の問題点として、繰り返しが多いこと、コードサイズが大きいことが指摘されていた。設計は、処理経路図という図を用いて基本構造に展開するという、わかりやすい方法で実施する。しかし、実行は、はやく、小さなプログラムで行うことが望まれる。現状のLyee方法のツールでは、そのLyee構造をそのまま保存した、プログラムを生成している。
本明細書では、はじめに要件を関数の系として捉え、グラフの隣接行列のよるモデルを構築した。さらに、Hoareの論理によって、ひとつの実現法を論理的に証明した。リアクティブな要件をシステム化の対象とするとき、関数モデルでは困難をともなうため、プロセス・モデルによるプロセス定義の方法を導入した。この場合でも、単語を基礎とするプログラミング法によって、実現可能であることを示した。
さらに、宣言的意味を完全に保存しつつ, はじめから効率の良いプログラムが生成できることを示した。それによって、小さい速いプログラムが実現した。
受動的制約のみの制約手続き型プログラミング方法であることは、2つの更なる可能性を示している。ひとつは、受動的制約から、能動的制約への展開、2つは、Lyee方法の論理型、関数型言語への適用である。個人的には特に、論理型、関数型言語の弱点である、外部とのインターフェースに使うことが想定される。プロセス・モデルの延長上に、並行、並列システムへの適用、インターネット上の分散システムへの適用が検討される。
【産業上の利用可能性】
【0165】
本発明は、処理経路図を作成することで、要件定義の総てを捉え、かつ処理経路図を検証することで、登録前に要件の過不足をチェックした上で、たとえばLyeeALL等のLyee方法論に係る自動生成ツールに入力するので、所望とするソフトウェアを適切に生成することが可能となるので、いかなる用途、或いはネットワークを介して配信され若しくはスタンドアローンを問わずあらゆる存在形態におけるソフトウェア、及びソフトウェアの生産方法にも適用できる。
【図面の簡単な説明】
【0166】
【図1】本発明の一実施形態に係る述語構造を示す図である。
【図2】本発明の一実施形態に係る繰り返し処理制御プログラムの例を示す図である。
【図3】本発明の一実施形態に係る単語の領域を示す図である。
【図4】本発明の一実施形態に係る始点単語と終点単語の間の関係を説明するための図である。
【図5】本発明の一実施形態に係る例1の画面イメージを示す図である。
【図6】本発明の一実施形態に係る出力単語を有向グラフを使って表現する図である。
【図7】本発明の一実施形態に係る例3を有向グラフに表す図である。
【図8】本発明の一実施形態に係る単語の終点節側に出力単語が存在する状態を示した図である。
【図9】本発明の一実施形態に係る画面イメージの一例を示す図である。
【図10】本発明の一実施形態に係るプログラムの動きを説明するための図である。
【図11】本発明の一実施形態に係る処理経路図を説明するための図である。
【図12】本発明の一実施形態に係る処理経路図の説明を行うための図である。
【図13】本発明の一実施形態に係る画面イメージの一例を示す図である。
【図14】本発明の一実施形態に係る有向グラフの一例を示す図である。
【図15】本発明の一実施形態に係るプロセス定義を示す図である。
【図16】本発明の一実施形態に係る成績管理のプロセス定義を示す図である。
【図17】本発明の一実施形態に係る成績管理の処理経路図を示す図である。
【図18】本発明の一実施形態に係るオセロのプロセス定義を示す図である。
【図19】本発明の一実施形態に係るオセロの処理経路図を示す図である。
【図20】本発明の一実施形態に係るビル監視センサの概念を示す図である。
【図21】本発明の一実施形態に係るビル監視のプロセス定義を示す図である。
【図22】本発明の一実施形態に係るビル監視の処理経路図を示す図である。
【図23】本発明の一実施形態に係る全体の処理経路図を示す図である。
【図24】本発明の一実施形態に係る変数の位置づけを示した図である。
【図25】本発明の一実施形態に係る設計時点での処理経路図を示す図である。
【図26】本発明の一実施形態に係る統合型新プログラムコードの一部を表す図である。
【符号の説明】
【0167】
stop 停止ボタン
exec 実行ボタン
【出願人】 【識別番号】396023362
【氏名又は名称】カテナ株式会社
【出願日】 平成16年9月17日(2004.9.17)
【代理人】 【識別番号】100110559
【弁理士】
【氏名又は名称】友野 英三


【公開番号】 特開2008−3641(P2008−3641A)
【公開日】 平成20年1月10日(2008.1.10)
【出願番号】 特願2004−272622(P2004−272622)