| 10.4 途中から あるプログラムの木が一致したモデルによって生産される時、その中の一つは他の木に含まれるプログラムの親として考察できる。親から子の目的に対し適切でない特性は分けたプログラムを与えらた子孫にとってそれは全く普通である。早い時期のバージョンを完成させる中で、もし子孫プログラムが独立して発達していたとしたら作られることはなかっただろう確かな決定木が作られた。これらの決定木は子孫プログラムのみにとどまる。なぜならプログラムの移動はそれを複製するたいそうな取り扱いを伴うだろうからである。その結果、異なる環境の中や、違う負荷で関数を設計された修正プログラムから引き出されるので後発のプログラムは性能不足となる。 10.5 新しい技術 図10.2は一般的な新しいメソッドの基本概念である。これらのメソッドを使っても、新しく木に加えるために完全なプログラムを変更することはない。いつも中間の段階のものから始め、前のバージョンから進歩した地点よりあとに作られた決定木を無視した設計決定木の地点から続ける。古典のメソッドにおいてあるバージョンのプログラムは他のプログラムの先祖であると言えるだろう。そして我々は2つのバージョンは共通の先祖を持つことを知った[3]。 図10.2 ｢抽象的な決定木｣を用いたプログラム発展の表現 記号：□ははじめの可能性。○は不完全なプログラム。×は活動中のプログラム。 違うバージョンは連続して発達する必要はない。もし木のある枝の発達が他の枝からの情報を使っていないなら、二つの部分木は平行に発達できることになる。二つ目の重要な記述は、「これらのメソッドにおいてどの決定木の順序も、古典のメソッドよりもっと意味を持って作られる。」である。枝の接点より上に作られたすべての決定木はそのポイントの下にある全ての木の要素によって分けられることを思い出しなさい。木の概念に対する我々の動機付けの中では、我々は木の要素の中に一般の中でより大きな価値を占める物を強調する。我々は枝の接点より前の可能な限りの決定によって、システムの「類似」を強める。我々は確実な違いがプログラムの間に必ず存在することを知っているので、新しい設計のメソッドの狙いはそれらの木の要素と区別された決定木より前に作られた、全ての木によって分けられることが出来る決定木を認めることである。図10.2の図解で、全ての木によって分けられたよりも多くの決定木に分ける部分木について話すことは有意義である。 もし木の根がある決定木が作られる前の状態を表すなら、共通の親が根のみである二つのプログラムは何も共有しないことになる。 我々は木を使ってこのプロセスを表すことが単純化のしすぎであると記すべきだ。確実な設計決定木は他（決定行程は交換の演算子で見られる）を考慮しなくても作ることが出来る。全ての枝で設計決定木を使うことは可能である。たとえば、いくつかのかなり違うオペレーティングシステムは、たとえそれが共通の親から作られた決定木でなかったとしても、行き詰まり防止アルゴリズムを使わせることが出来ただろう。 10.6 中間の段階を表現する プログラム木の古典的メソッドで、中間の段階は上手く定義できなかった。そして不完全な設計は正確に表現できなかった。それはバージョン間の交信が完全なプログラムの形式の中のものだったという事実の原因でもあり結果でもある。もし2つのメソッドのどちらも議論されたらこれは有効に働くだろう。われわれが中間の段階（特にこれらの中間の段階が枝の点として使われたとして）の正確な表現をすることは必要である。どちらのメソッドも部分的に設計されたプログラムの記述の精度を強調する。それらは部分的な設計は表現される点で異なる。我々は記述せねばならない。それはプログラムの最終バージョンではない。それは我々の実際の結果である（まれにプログラムを修正せずに使う）。新しいメソッドで、不完全な表現のままだがいい発展をした事は、他のメソッドの仕事への貢献のように提議された。 10.7ステップワイズレファインメントによるプログラミング （問題をより小さく扱いやすい部分に分解する操作を繰り返してプログラムを分解していくプログラムをトップダウンデザインまたはステップワイズリファインメントという。） 「ステップワイズレファインメント」というメソッドはダイクストラ[3]によってはじめて形式的に導かれた。その頃はまだいろいろな貢献者[4]-[6]によってそれより遠い議論がされていた。文献の主な主張はまだまだ完全なプログラムの創造についてだが、副作用はメソッドがプログラムファミリーの創造を助長することである。早い例の一つに素数を生み出すプログラムの発展がある。そのプログラムでは最後のプログラムの次は素数を生むための極めて異なる2つのアルゴリズムを使用することが許され続ける。この不完全なプログラムが、少なくとも2つの意味のある異なる要素を含むプログラムの木を定義する。 ｢ステップワイズレファインメント｣の中では、中間の段階はプログラムで表現され、決まった演算子とオペランドのタイプの実装のために完全に除外される。プログラムはあたかも演算子とオペランドが言語に「組み込まれた」かのように書かれている。実際の言語の中でのこれらの演算子の実装はより遅い段階へと延期された。演算子の（暗黙もしくは明白な）定義の場所は色々な実装を許可するのに十分に抽象的で、早いバージョンのプログラムは、どの実装されてない演算子や非演算子の中で可能な実装のためにも要素がある木を定義する。たとえば、あるプログラムはデータはstackで、演算子はpushとpopという宣言で書かれているかもしれない。ただ最新のバージョンでは、スタックの表現やpushやpopを実行する手続きは紹介されるだろう。我々はステップワイズレファインメントの技術を、後の比較で使われる２つの例を用いて図示する。 10.7.1 例１：ダイクストラの素数プログラム ダイクストラ[3]は数字を打ち出すプログラムの発展を記述する。はじめのステップは次の通り現れる。 begin variable table p; fill table p with first thousand prime numbers; print table p; end このプログラムの中でダイクストラは非演算子"table"と２つの演算子を推量する。table（素数を計算するメソッド）と型の打ち出しの表現はすべて定義されないままになっている。事実、縛られただけの決定木（プログラムの木全体で一般的な特徴）は「すべての素数がなにも打ち出される前に明らかにされるはず」、そして「我々はいつも最初の1000の素数を望んでいるだろう」である。ダイクストラはそのとき実装したtableか作り出した"fill table"かで熟考する。結局彼は「"table"は実装されるべきだ、そして残った木のすべての要素は同じtable実装に共有する」と決めた。テーブル実装のどちらか一方と一緒の木の枝は言及されるが、発展しない。木の最新の要素はコンピュータを用いた素数の様々な可能なメソッドを考えることで発展する。 10.7.2 例2：ウルフのKWIC(keyword in context,文脈付キーワード)索引プログラム ウルフ[5]はKWIC索引プログラムについて提案されたステップワイズレファインメントの発展について次のように述べる。 Step1:PRINTKWIC 我々はこれを言語(または機械)の使用法と考えているかもしれない。その中ではKWIC索引を作ると言う考えは原始的だ。この演算が最も有用な言語の中で原始的でなかった時から我々はこれを定義することを進めていた。 Step2:PRINTKWIC:はすべての興味のある環状のシフトを生産し保護する。 は保存した分を文字化する。 は文字化された文を打ち出す。 再び我々はこれらの文のそれぞれが特有の言語の使用法を保っているかを考えるだろう。そして再び、その後それらが最も存在する言語の中で原始的でなくなってから、我々はそれらを決めなければならない。例えば Step3a:すべての興味のある環状のシフトを生産し保護する： for each line in the input do begin generate and save all interesting shift of "this line" end など。 最新の比較の目的のために、我々は残った木の要素によって共有されるべき決定木を記述する： １．すべてのシフトが蓄えられる ２．すべての環状のシフトが文字化が始まる前に生産し保護される ３．文字による整列は書き出しが始まる前に完成する ４．他の行のシフトより前に一行のすべてのシフトが展開される ５．シフトが作られる時同時に"興味ない"シフトが消去される ステップワイズレファインメントによるプログラミングで最もよく知られている例では、演算子の定義は非公式だった。公表された例はすべて個人指導の例として設計され、演算子が”古典的”であり続けたため、直感それらを理解することはプログラム開発の正確な理解に十分であった。著者に知られていた唯一の例外は[11]である。演算子の形式的定義は、プログラム検証の目的でFloydによって最初に導入された述語挿入技術のアプリケーションによって含まれる。Dijkstraが示唆したように、私たちは、演算子を"述語変換器"（演算子のアプリケーションの後のプログラム変数の状態を記述する述語を、演算子が[7]を実行する前のプログラム変数の状態を記述する述語にどうやって変換することができるのかを記述する規則）と考えることができる。 |