OpenCourseWare(OCW)を勉強するWiki
6.170 Laboratory in Software Engineering Lecture 5
最終更新：
匿名ユーザー
-
view
MIT OpenCourseWare ＞ 6.170 Laboratory in Software Engineering, Fall 2001 ＞ 6.170 Laboratory in Software Engineering Lecture 5
MIT OpenCourseWare 6.170 Laboratory in Software Engineering, Fall 2001, Lecture 5: Abstract Types のまとめ
ラジオの方では vol. にあたりました。Lecture Noteを読むときの助けにしてください。
6.170 Laboratory in Software Engineering, Fall 2001のLecture NoteのPDFはこちら
(※2006年4月16日現在、上記講義は6.170 Laboratory in Software Engineering, Fall 2005にアップデートされたようですが、PDFはまだ拾うことができます。)
6.170 Laboratory in Software Engineering, Fall 2001のLecture NoteのPDFはこちら
(※2006年4月16日現在、上記講義は6.170 Laboratory in Software Engineering, Fall 2005にアップデートされたようですが、PDFはまだ拾うことができます。)
5.1 Introduction
この講義では、
- clientの抽象型(abstract types)への依存をどううまいことやるか
- 抽象型の値の考え方、操作(operation)の分類、表明(representation)のトレードオフ
について議論していきます。
5.2 User-Defined Types
初期のプログラム（おっきいやつ）は、組み込み型(built-in types, e.g. intとかbooleanとか)と組み込み関数(入出力とか)が元になってた。ユーザーはそこから自分の関数を作ってたんだけど。
その後のソフトウェア開発での主な進歩のひとつは抽象型！ ユーザーによる型の定義を可能にしたこと。 （起源が知りたい人はSimulaのDahlさんとか、‘information hiding’って言葉を作ったHoareさんとか、この講義の元を作ったMITのLiskovとかGuttagを調べてね。）
data abstractionの肝は、型はそれに対して行う操作(operation)できまるということ。例えば文字列は、文字列をくっつけたり部分文字列をとったり出来るもの。
data abstractionの今までと違ってるウリなところはその操作に注目し注力すればいいということで、ユーザーは、どんな風に値が保持されてるかなんて気にする必要がないこと。
data abstractionの今までと違ってるウリなところはその操作に注目し注力すればいいということで、ユーザーは、どんな風に値が保持されてるかなんて気にする必要がないこと。
（ちなみにJavaでは組み込み型が残っててちょっと嫌だね…。）
5.3. Classifying Types and Operations
ユーザー定義型はmutable type(変更可能型？)とimmutable type(不変型？)に分けられる。
mutableは、変更できるってこと。というのは、1つの操作をやることで、他の操作の結果が変わってきちゃうこと。※1
- Vectorはmutable。addElement()をするとsize()の値が変わる。
- Stringはimmutableで、そのmutable版はStringBuffer……なはずなんだけど、こいつらは実際は互換性がない。
immutableがいいのは、共有ができること。多くの問題がmutable型で起こるので、大きな構造のものでローカルな変更が必要なときに良いよ。
抽象型でのoperationの分類
- Constructors. その型の新しいオブジェクトを作る。引数をとることもあるが生成されるオブジェクト自体が引数にはならない。
- Producers. 古いオブジェクトから新しいオブジェクトを作る。Stringの足し算なんかそう。(2つのStringから新しい１つのStringを作る)
- Mutators. オブジェクトを変更するもの。Vectorのaddなど。
- Observers. その抽象型から、別の型の値を返す。Vectorのsize()など。
つまり、
constructor: t -> T
producer: T, t -> T
mutator: T, t -> void
observer: T, t -> t
(Tはその抽象型、tは別の型)
とはいえこれは全部厳密に出来ることもなくて、producersとmutatorsを同時に満たすoperationだってある。
とはいえこれは全部厳密に出来ることもなくて、producersとmutatorsを同時に満たすoperationだってある。
あと知っておくといいのがiterator。a collection of objects one at a time な特殊な種類の関数。
5.4. Example: List
ListってのはArrayみたいに一意のindexで持ってる要素を取り出したりできるけど、Arrayと違ってあるindexの要素を取り除ける。JavaではListはインターフェースでいっぱいメソッドを持ってるけど、ここでは以下の簡単なクラスを考えよう。
public class List {
public List ();
public void add (int i, Object e);
public void set (int i, Object e);
public void remove (int i);
public int size ();
public Object get (int i);
}
ちなみにadd、set、removeがmutatorsで、sizeとgetがobservers。producerはない。(ちなみにan immutable type certainly cannot have mutators).
次にspecification fieldsを考えよう。
seq [Object] elems;
where for a list l, the expression l.
elemsはlistにはいってる一連のオブジェクトを示し、indexは0から始まる。
また、
public void get (int i);
／／ throws
／／ IndexOutOfBoundsException if i < 0 or i > length (this.elems)
／／ returns
／／ this.elems [i]
public void add (int i, Object e);
／／ modifies this
／／ effects
／／ throws IndexOutOfBoundsException if i < 0 or i > length (this.elems)
／／ else this.elems’ = this.elems [0..i-1] ^ <e> ^ this.elems [i..]
public void set (int i, Object e);
／／ modifies this
／／ effects
／／ throws IndexOutOfBoundsException if i < 0 or i >= length (this.elems)
／／ else this.elems’ [i] = e and this.elems unchanged elsewhere
「＾」(caret)は連結を意味してます。
5.5. Designing an Abstract Type
抽象型のデザインは、よいオペレーションを選ぶということと、それらの振る舞いを決めるってのを含んでる。
- 少ない簡単な操作を持って、それらをパワフルな方法で組み合わせる
- それぞれの操作は明確な目的と首尾一貫した振る舞いを持たせる
- 操作の集合は適切である、っていうのはクライアントがやりたいことを十分カバーしてるってこと。listでgetがなかったらほしい値が取れないし、だけじゃなくてsizeとかも、クライアントが自分で数えるのは大変だし。
- 型がgenericであること、mix genericとかドメイン固有ではだめ。
5.6 Choice of Representations
いままで操作で抽象型を考えてきたけど、ここでは抽象形を実装するクラスであるrepresentation、つまり操作をサポートする実際のデータ構造、を考える。representationはそれぞれJavaの型を持ってるフィールドの集合。
リストを例にとる(p.53の図参照)。JavaだとLinkedListクラス。
- Listオブジェクト
- headerフィールド Entryオブジェクトをさす
- Entryオブジェクト
- nextフィールド 前のEntryオブジェクトを指す（もしくはnull）
- prevフィールド 後ろのEntryオブジェクトを指す（もしくはnull）
- elementフィールド 要素オブジェクトへの参照
ここではLinkedListとArrayListを比べてるので、54ページと55ページの図を見てね。
内部構造が違ってたって同じリストとして扱える。ちなみに挿入削除が頻繁なときはLinkedListがいいけど、ランダムアクセスが多いときはArrayListのがいい。
5.7 Representation Independence
Representation Independenceは、抽象型がそのrepresentationから独立してて、representationを変えても抽象型自体の外には影響しない、ってこと。
たとえば、こんなコードについて議論してる。（55ページをみてください・・・）
List l = new List ();
v.copyInto (l.elementData);
他の例としては、配列で、
public Entry getEntry (int i)
とかするときに、
Entry e = l.getEntry (i);
e.element = x;
...
e.element = y;
とかって、Listが持ってるEntryをそのまま渡しちゃだめだよね。だって配列のrepresentationを壊せちゃうからね。
クライアントはListクラスだけに依存するべき。
(編集中)
today's visitor： -
total visitor： -
total visitor： -
