DVIOUT-oolin

Transcription

1 オブジェクト指向 操作対象の理解と言語の効率性 プログラム理論と言語 Part2-1-1 関連したデータの塊を1つの もの として認識 (1) クラス= もの と もの に付随した操作系 (2) クラスのことはクラス内部で処理ブラックボックス化し 外部仕様を明確化 部品としての再利用 安全性 (3) もの と処理の独立性を高め処理も部品化操作そのものでなく 操作の型情報のみで処理を記述 コードの抽象化 再利用 役割 機能と もの を分離し独立性を高める (4) 複雑さに対処するために階層として体系化 修正 追加 利用 ( 特にライブラリ ユーティリティ ) 人の対象理解 言語的表現と合致する特に個別事例に依存しない抽象表現 言語の効率性 1

2 JAVA はオブジェクト指向言語か? その気になれば オブジェクト指向でプログラムが書ける一般に長くなるが 可読性 安全性 再利用性は高まるそうでないプログラムも書ける 体系的でない ものも多い簡単な場合はそれでもすむが 複雑になると 修正 拡張 再利用が困難プログラムを書くという観点からは オブジェクト指向は処理対象と処理を体系化するための作法であり オブジェクト指向言語はそのための言語的装置 (*) (*) 本講義において Java を題材にする理由 : 1. オブジェクト指向の主要な概念は全て Java で説明できること 2. プログラム言語において重要な型概念を十分に講述できること 3. 様々な場所で実際に良く使われている言語であること 4. CS 実験等をとおして C 言語の理解が進みつつあることを考慮し C と構文的に近いオブジェクト指向言語であること ポインタについて : Java: 実際は ポインタのお化け状態 ポインタを駆使するプログラミングは一般に難しい Java: 比較的に安全にかつ容易に実現本講義 : 上記の事情をある程度説明する 2

3 はじめにオブジェクトありき まず処理において如何なるオブジェクトが必要かを考える対象の分析 理解 その理解を言語的に顕在化させるプロセス もの の定義書としてのクラス もの に付随したメソッド( 演算 基本操作 ) 群 メソッドを持つ もの として体系的に扱うその後に メソッドにより もの を操作 処理する手続きオブジェクト指向言語 =オブジェクト定義 操作言語では もの とは何か? 哲学論議はここではしない計算機の中での出来事 メモリ上の構造物として表現 翻訳される もの 3

4 配列 : プログラミングにおいて不可欠な もの これも立派なオブジェクト int[] a; a = new int[3]; データの集まり {a[0], a[1], a[2] を1つの配列として纏めて扱う new int[3] : 配列領域を割当 生成配列は要素から構成され 添字を与え要素へアクセス特に a は領域全体の名前 ( 参照 ) 領域を生成する仕掛け一般のオブジェクト : フィールド名を持つ要素からなり添字の代わりにフィールド名 ( 変数 ) で要素にアクセス特定のデータ領域を占有し 領域全体はオブジェクト参照変数で参照領域生成は コンストラクタ で行う 4

5 3 角形は 3 つの点からなる : まず 点 を定義 定義は対応するクラスの記述で与えられる class Point { // フィールド変数 double x, y, weight; // コンストラクタ ( 生成方法 ) Point(double x, double y, double w) { this.x=x; this.y=y; weight=w; // インスタンスメソッド // 各オブジェクトに直接作用フィールドアクセス : void show() { this からは フィールド名 x System.out.println( 一般に a.x "x="+x+", y="+y+ Point a が参照している " with weight "+weight); オブジェクトの x フィールド 識別子が特定する位置の実体に対し x のフィールド値をとりだす Note: オブジェクトはCの構造体 参照変数は構造体型のポインタ変数に対応する メソッド ( 関数 ) と一体化して使う点がオブジェクト指向を表しているが 上記の図ではその事情を十分説明できていない ( インスタンスの図 ) 後で詳しく述べる 5

6 C の構造体 オブジェクトと参照変数はCの構造体とそのポインタと似ている似て ( メモリ上の構造物という点は同じ ) 非なるもの ( 使い方 その作法 安全性に対する配慮が全く異なる ) struct student{ int stnum; char stname[16]; ;... struct student *stpt; /* ポインタ */... stpt->stnum (*stpt).stnum class Student{ int stnum; String stname;... Student st; // 参照変数... st.stnum stpt, st が参照する実体の stnum フィールドをゲット stpt, *stpt を区別参照変数は Student 実体 と考えてよい書き方 非なる点 としては そもそもオブジェクトがメモリの特定の領域を 占有しているか? の問題もある Java: 占有状態 ( システムが管理 ) C: アドレス計算が可能 型チェックが甘い等により上書きの危険性 プログラマの責任 6

7 参照変数はポインタか? - C との比較 答え : 広義の意味のポインタか? Yes C と同じポインタか? アドレス計算を禁止 参照機能に限定 識別子の詳細は 知る必要はない 知ったとしてもその事実をコードに反映できない 識別しアクセスできることが論理レベルで保障されていれば十分 以下 実体を特定できる論理的なものとして識別子を考える 7

8 参照関係と内部状態の変化 厳密表現 :Point の参照変数 aが参照する ( 指す ) オブジェクト略した表現 :Point a ( 単に 点 a) 仮の名前 : 変数と実体の参照関係は動的に変化 内部状態も! 計算過程 : 新規オブジェクトを生成しながら (1) 参照関係の変化 (2) オブジェクトの内部状態の更新上記はメソッド実行時 8

9 メソッド呼出とパラメータ 実体内部状態 : メソッドにより更新され変化実体の識別子 : 何ら変わることはない ( 永続性 *) 識別子 ( 名前 ) と実体は同一視基本データ型の引数 : 値を引数パラメータに代入 ( 値呼出 ) (*) 自オブジェクトを示す参照変数 this への代入 ( 代入式の左辺 ) は禁止で コンパイルエラー 9

10 つぎに 3 角形を定義する class Triangle { // スタティック変数 static final int nofpoints=3; // オブジェクトはフィールドで規定 Point[] points = new Point[nofPoints]; // インスタンスメソッド // オブジェクトに作用する関数 void show() { for (short i=0;i<nofpoints;i++) points[i].show(); // 3 角形に対する show() を点に対する show() を使って定義クラス情報 ( 型 ) で識別 static final int nofpoints=3; クラスに固有 ( インスタンスに依存しない ) 変数でクラスのスタティックメンバーともいう final 指定変数は 上書き不可 ただし 下記の注意が必要となる : 1. 基本データ型 : 文字通り 定数 2. オブジェクト : 参照先オブジェクトは変わらない しかし その内部状態は変更される可能性 定数 にするにはカプセル化が必要 10

11 コンストラクタ ( オブジェクトの占有領域を作成 ) デフォルト生成 : Triangle t = 引数なしの特別な手続き new Triangle(); Point[] points = new Point[nofPoints]; に従い実体を生成し t にセットこの場合 配列領域の確保 ( 割当 ) 明示的な生成 =デフォルト+α Triangle t = new Triangle(p0,p1,p2); 右辺実体 ( の oid) を t にセット Triangle( // 引数付の手続き Point p0, Point p1, Point p2) { points[0]=p0; points[1]=p1; points[2]=p2; クラスのインスタンス化 : コンストラクタを適用し 実体オブジェクトを生成する行為 デフォルトコンストラクタ : 引数なしで Triangle() { クラス定義におけるデフォルトコンスタラクタの扱い明示的コンストラクタを使用しない 宣言せずに使える明示的コンスタラクタを使用 デフォルト Triangle() を使うときはそれも明示する 11

12 定義 生成 操作 オブジェクトの定義をクラス記述で与え コンストラクタでオブジェクトを生成し インスタンスメソッドでオブジェクトを操作する class triangletest { public static void main(string args[]) { Triangle t = new Triangle( new Point(1,2,3), // 各点実体 ( の識別子 ) new Point(4,5,6), new Point(7,8,9) ); // 右辺のオブジェクト ( の識別子 ) を // 左辺の変数 ( に代入 ) に参照させる t.show(); // 3 角形 t に show() を適用 // オブジェクトの操作は手続きで記述 // 手続き的なオブジェクト定義 操作言語 論理型のオブジェクト指向言語 (OOLP) 関数型のオブジェクト指向言語 (Common LISP) この他 オブジェクト指向のデータベース オブジェクト指向の COBOL! などもある 扱うデータの基本単位としてオブジェクトを許すと こうなる 12

13 様々なメソッドの定義と組合せ : 手続きを記述 class クラス名 { // インスタンスメソッド : もの に対する基本操作 または 複合操作 出力型 ( クラス名または基本データ型 ) // ( 基本操作を組合せた操作 ) メソッド名 ( パラメータ型変数名,...) { メソッド本体 ( そのクラスのオブジェクトに対し行う処理 class Point { or オブジェクトがそのメソッドで振る舞う動作の記述 ) double x, y, weight; double length(point p) {// 2 点の距離 return Math.sqrt(Math.pow(x-p.x,2)+Math.pow(y-p.y,2)); // sqrt: 平方根 pow: べき乗 Math クラスで定義... class Triangle { static final int nofpoints = 3; // 大域変数 ( 定数 ) Point[] points = new Point[nofPoints]; // double sumoflength() {// 3つの辺長の総和 double sumoflength = 0.0; for (int i=0;i<nofpoints;i++) // i++ は i=i+1 の略記 sumoflength += points[i].length(points[(i+1)%nofpoints]); return sumoflength; // 整数 n, m に対し n % m は m を法とした剰余 public static void main(string args[]) { Triangle t = new Triangle( new Point(1,2,3), new Point(4,5,6), new Point(7,8,9) ); if (t.checktriangle()) System.out.println(" 辺の長さの総和 = "+ t.sumoflength()); else { System.out.println("3 角形ではありません 要データチェック "); t.show(); ; 13

14 用語の整理 1: インスタンスとオブジェクト オブジェクト : 操作の 対象 で 占有領域 ( インスタンス ) とそれを処理するメソッドを持つ C でも構造体のインスタンス化は行う しかし そのインスタンスは関数 ( メソッド ) と言語的に一体化しているわけではない プログラマが必要に応じて そのインスタンスへのポインタを関数に渡して適用 操作するだけの話 一方 Java では 最初からインスタンスはメソッドと一体化されて扱われることが大前提であり そのことがクラス定義で明示される それは体系的に操作対象を扱うための流儀であると理解すること 14

15 操作により もの をクラス分けする オブジェクトがどのようなメソッドを使用できるかはクラス定義で決まる 逆に言えば 各オブジェクト毎にメソッドを定義し保持するのは不経済オブジェクト毎に異なるメソッドが必要な場合 : 別クラスの もの メソッドがクラスを特徴づける 上図における 人 は識別子と考えてもよい 以後 概念図において 人 記号は 識別子もしくはインスタンス とする 15

16 カプセル化 クラスの利用 クラス間相互作用は一般に複雑化外部仕様 : クラスとは? のメソッドを持つ もの ~ メソッド中心の設計仕様と実装の分離独立化 仕様に関わるメソッドのみ公開外部からは公開メソッドのみで操作 内部的な実装は private に隠蔽し独立に管理 オブジェクト指向はさらなる構造化を促す : 独立したクラスの列挙から 構造化されたクラス群 1. クラス階層 インタフェース階層 2. 内部クラス ( 一般にはクラスの nesting) 16

17 アクセス制御の原則 フィールドは原則 private に ( 不用意なアクセスによる状態参照 更新を抑制する ) ゲッター getattr() +セッター setattr(...) メソッドに対するアクセス制御同一パッケージ ( 同一ディレクトリ ) を想定した場合 : 無修飾のメソッド : パッケージ内で公開 private メソッド : クラス内のみで有効一般には パッケージの作り方に依存 ( 特に public) 複数のパッケージ ( 複数のディレクトリ ) の場合 : public: 全てに公開 protected, final: クラス階層導入時 むやみに意味もなく public をつけない! パッケージ配布 公開の際の外部仕様ソースコード解読時の構文上の情報 インタフェースの定数とメソッドは must be public protected: パッケージ内 + 下位クラスに公開 final 定数 メソッド : 上書きを許さない クラスに対しても public, private, final 無修飾等の修飾が可能. 例えば public にしないと他パッケージから利用できない final にすると 継承 拡大を許可しない 17

18 パッケージと public の例 18

19 リスト : 再帰とカプセル化の例 再帰的構造は 型 で表現 ( インタフェース 後述 ) リスト ( 要素の並び )x 1,x 2..., x n boolean empty(); int head(); List tail(); List cons(int x); フィールドは上記を満たすべく設計実現手法に依存 ( 配列 ポインタ...) class List { int head() {return element; private int element; List tail() {return tail; boolean empty() {return tail == null; private List tail;// 生成時の初期値は null List cons(int x) {// this は自オブジェクト ( の識別子 ) List list = new List(); list.element = x; list.tail = this; return list; // this =...; はコンパイルエラー ( 識別子と実体の1 対 1 関係 ) 19

20 // list の付加的なメソッド定義 int sum() {// 再帰の構造はデータ構造と一致 if (empty()) return 0; else return head() + tail().sum(); // Note: 停止性 正当性は長さに関する数学的帰納法 void show() { if (tail == null) System.out.println(); else { System.out.print(element+", "); tail.show(); ;// ここでは show() と sum() は List で定義 //List の応用として別クラスのメソッド (static or not) でも良い class test { public static void main(string args[]) { List list = new List();// デフォルトコンストラクタ for (short i=0;i<args.length;i++) list = list.cons(integer.parseint(args[i])); list.show(); System.out.println(" sum=" + list.sum()); 20

21 ネータ帰納法 クラス C の実体の集合を単に C と書く (C, ¹) が順序集合 (poset) とする ( 順序の決め方は一意ではないが 実体間の部分構造関係があれば 自然に順序がはいる ) (C, ¹) :well-founded 無限下降列 def... x i 1 x i... x = x 0 が存在しないリストの場合 :[element == any, tail == null] が極小元 int element = 0; と初期化しておけば [element == 0,tail == null] が最小元ネータ帰納法 : P (x) : 証明したいこと x C ( y C(y ¹ x P (y)) P (x)) x C P(x) 線形リストは 特殊ケースである数学的帰納法部分構造関係 ~ 要素数の大小関係 21

22 構造帰納法 x C ( y C(y ¹ x P (y)) P (x)) x C P(x) ネータ帰納法が必要な場合例 : 木に対するメソッド class BinaryTreeNode { private Content content;// ノードが保持する情報 // 別クラスで定義 private BinaryTreeNode leftchild, rightchild; boolean leaf() { return leftchild==null && rightchild==null;...// 部分木 木の順序 // 極小元は 葉 最大元は 根以下の木 22

23 クラス間相互作用の例 class Polygon { private Point stdp; private Point[] points; Point getstdp() { return stdp; // アクセスメソッド... class Point { private double x, y; private Polygon cp;// 帰属多角形 boolean steeper(point ap) { return cp.getstdp().slope(ap) < cp.getstdp().slope(this); double slope(point ap) { 図における人は実体オブジェクトで 矢印は 実体間の参照 ( フィールドの実現値 ) 関係を表す 識別子間の参照関係が形成される 1. メモリ上の現象としては ポインタのお化け 2. 理論上は 複雑なグラフ 次ページの部分クラスは 参照関係の複雑さを軽減させる効果がある 23

24 内部クラス : 複雑さを軽減させるための構造化 class Polygon {// 内部クラス Point の外部クラス private Point stdp; private Point[] points;... class Point {// 多角形の内部クラス 点実体は多角形実体の属性にアクセス可 private double x,y; // 点の実体化は多角形の実体 cp の中で行う (*) boolean steeper(point ap) { return stdp.slope(ap) < stdp.slope(this);... // カプセル化を壊さずに 記述が簡潔化 // クラス間の編成上 組織上の構造を明示 後述のクラス階層とは別 (*) 実体の中に実体を作る ~ 占有領域の中でインスタンス化すると理解 Polygon のコンストラクタで多角形をインスタンス化する際 もしくは Polygon のインスタンスメソッド中で点をインスタンス化 A 外 B 内 B 外 C 内 のような外部 内部が層化される場合 外側の実体から順次生成する (A の実体から C のコンストラクタは直接呼び出せない ) 実体化に関する制限と メンバアクセスの話は別 メンバーを隠蔽するには きちんと private をつけておく 内部クラスを始め 構造化のための言語的諸機能はオブジェクト指向の大きな特徴 24

25 用語の整理 2: obj.m(p1,.., pn) の読み方 オブジェクト obj に対し メソッド m(p1,.., pn) を適用 obj に対し m(p1,.., pn) を実行 オブジェクト obj に対し メソッド m(p1,..,pn) を呼び出す メソッドはオブジェクトの所有物本講義では 特に区別しないこの他 オブジェクトをエージェント ( 処理主体 ) と考え オブジェクトにメッセージを送る 25

26 メッセージパッシング オブジェクト obj ( レシーバ ) に メッセージ m をパラメータ p1,.., pn で送る 送られた方は m を処理するメソッドを持つメッセージ ~ メソッド class Teacher {... void assignrept(student st, Task task) { Answer ans = st.report(task); // st に report せよ との // メッセージを発信し // 結果を ans で受ける if (ok(ans)) {... else {...;... class Student { // メッセージを受けたときの // 動作 ~ メソッドそのもの Answer report(task task) {... Answer myanswer = new Answer(...); return myanswer; // 解答を myanswer で返す 実際の例題は FA のシミュレーション (statisfa.java, fa.java) で示す 26

27 メッセージパッシング例 各状態をオブジェクトに状態は 受理 / 非受理の情報を持つ入力記号列 str を受け取り 次の状態に処理依頼のメッセージを投げ 以降の処理を委ねる class State { private static final short nofsymbols = 2; // 入力記号は {0,1 private String name; private boolean accept; // 受理状態情報 private State(String n, boolean f) {name = n; accept = f; private State[] nextstates = new State[nofSymbols]; void definenextstate(state next0, State next1) { nextstates[0] = next0; nextstates[1] = next1; private short head(string str) {return Short.parseShort(str.substring(0,1)); private String tail(string str) {return str.substring(1,str.length()); private void process(string input) { if (input.length()!=0) nextstates[head(input)].process(tail(input)); else if (accept) System.out.println("OK"); else System.out.println("NG"); public static void main(string args[]) { State q0 = new State("q0", false); State q1 = new State("q1", false); State q2 = new State("q2", true); State q3 = new State("q3", false); q0.definenextstate(q1, q3); q1.definenextstate(q3, q2); q2.definenextstate(q1, q3); q3.definenextstate(q3, q3); q0.process(args[0]); 27

28 Definition of A: A consists of B 1, B 2,... オブジェクト指向 : 言語的な定義のスタイルに対応 Aの定義書 : クラスAのオブジェクトはクラス (or 基本型 )B j のフィールドからなり のメソッドを使って操作します ( 構成要素 (part of, has_a 関係 ) クラスのメンバー A isa B, ora is defined as a B such that... A extends B... AはBを継承し拡大 Aに固有なフィールドやメソッドを追加 A has a role/function of B B: インタフェース A implements B 機能を持つ ~ 役割 機能を実現する手段 メソッドを具体的に持つ ( 実装 ) 多態性 ( ポリモルフィズム ) 様々な役割や機能を実装クラスで記述 ( クラスと機能の分離 独立化を促進 ) 28

29 クラス定義のまとめ class Point { private double x,y; Point(double x, double y) { this.x = x; this.y =y; void show() { System.out.println(" x="+x +", y="+y); class Triangle { private static final int nofpoints=3; private Point[] points = new Point[nofPoints]; private Triangle(Point p0, Point p1, Point p2) { points[0]=p0; points[1]=p1; points[2]=p2; private void show() { for (short i=0;i<nofpoints;i++) points[i].show(); public static void main(string args[]) { Triangle t = new Triangle( new Point(1,2), new Point(4,5), new Point(7,8) ); t.show(); //void main(string[]) は // ここでは Triangle に組み込んだ 実行時 : クラスは生成されたオブジェクトの集まり + 大域変数 (static variable) の値を管理 コンパイル時 : オブジェクトの定義書として記述の集まり 記述は クラスのメンバー ( 構成要素 ) と呼ばれる変数やメソッドの各々に対し行われる フィールド変数 : オブジェクトの属性基本データ型もしくはオブジェクト参照変数フィールド記述がコンスラクタのデフォルト動作を決める インスタンスメソッド : オブジェクトに直接作用する手続きオブジェクト : this で表記 ( 必要ならば ) スタティック (static) メンバースタティック変数 : クラスが保持し 各オブジェクトに依存しない変数スタティックメソッド : オブジェクトに依存しない手続き public static void main(string args[]) java クラス名引数そのクラスの main が実行される クラス毎につけてよい型は void main(string[]) 引数型を別にすると オーバーロード 左記では main は Triangle のメンバー別クラスで main を動作させる場合 Triangle(...) と void show() の private 指定は外す ( メソッドにアクセスできないから ) 29

30 スタティックメンバーについて オブジェクト指向では 先んずオブジェクトとクラス設計その次に手続き等の設計個々のオブジェクトに依存しない定数 変数 メソッドがあれば スタティックメンバーにする具体にスタティックメンバーが必要となる場面例 : コンストラクタに準じた作用を持つメソッドクラス固有の定数やオブジェクト (static final) 個々の もの に依存しないクラス固有の処理手続き基本データ型に関する型変換や数値関数など ラップクラス や Math で提供される int Integer.parseInt(String), double Math.sqrt(double) 30

31 再帰呼び出しに関する補足 C 同様 Java でも再帰は (static, instance methods ともに ) 使える 関数型でやったようなスタイルでのメソッド定義もOK 処理系からみると 再帰と非再帰の区別は全くない! 一般形 f の定義本体中で別のメソッド g を呼び出す再帰特に g = f なだけで何ら処理は変わらない ただし 計算量に注意すること // フィボナッチの数列 f(n)=f(n-1)+f(n-2), f(1)=f(0)=1 class Fibonacci{ static int rec_fib(int n) {// この場合 指数爆発 if (n==0 n==1) return 1; return rec_fib(n-1)+rec_fib(n-2); static int it_fib(int n) {// 繰り返し // 定数領域 線形時間 if (n==0 n==1) return 1; int nminus1 = 1, nminus2 = 1, tmp; for (int i=1;i<n;i++) { tmp = nminus1; nminus1 = nminus1 + nminus2; nminus2 = tmp; ; return nminus1; 31

32 スパゲッティプログラム : よくあるパターンその 1 static void main(string args[]) で全てを書こうとし補足的に static メソッドを用いる スパゲッティプログラムへの道 処理対象と手続きの両方が構造化されていないため バグとり 修正 再利用 機能の追加が困難 書き直した方が早い 修正箇所 機能追加 デバッグ箇所を特定しずらく ズルズルと全体がついてくる スパゲッティ ( 結局 多くの箇所を 食べないとダメ もしくは 切るのが大変 ) 32

33 スパゲッティプログラム : よくあるパターンその 2 Cで書いていたとき 構造体とポインタに苦手意識があり その惰性でつい配列だけで書いてしまう 関連する配列や変数がばらばらで 関連性を見出すためには スパゲッティ状態 コメントをつけて対処する人も多い コメントはダラダラとつければ良いというものでない OOPL 構造体と参照は簡単にかつより安全にカプセル化できる : クラスを定義し メソッドで実体を処理する 33

34 スパゲッティプログラム 3: 例 static int nofitems = 0; // 商品数 static int[] stock = new int[10000], price = new int[10000]; static String[] itemname = new String[10000];... static void additem(int initialstock, int price, String itemname) { if (nofitems == 10000) { System.out.println("sorry, full list"); return; ; stock[nofitems] = initialstock; price[nofitems] = price; itemname[nofitem++] = itemname; まず 重要な定数 のスパゲティ 後で商品コードも必要になった 追加 : static int[] code = int[10000]; 関連するメソッドの引数や本体部の修正 static void additem( int initialstock, int price, String itemname, int codenumber) {... code[nofitems] = codenumber; さらに 商品コードで商品リストをソート code の値による並び替えで 同時に stock, price, itemname 配列も操作修正箇所が増え しかもその場所が集中しているとは限らない 喩え話 : 中に色々なものが入っている箱を 他に移動するとき ある順序で並び替えるときに 箱の中身をバラバラにして移動 あるいは並べ替えますか? この場合の箱 ~ オブジェクト箱の中身 ~ フィールド クラスによるカプセル化 34

35 OOPL では class Item { private int stock, price; Item(int initialstock, int price) { stock=initialstock; this.price=price;... その他のメソッド... class ItemList { private static int MaxNof = 10000; private int nof = 0; private Item[] list = new Item[MaxNof]; void add(item item) { if (nof!= MaxNof) list[nof++] = item; else System.out.println("full list"); code や name の追加は対応するフィールドとコンストラクタの修正のみ add(item) は修正の必要なし 一般に 参照変数で実体を丸ごと渡すので 関数 メソッドの引数は少なくなる また 例えば ソートのときも item.code の大小関係で 実体そのものを並び替えればそれで OK 例えば実体の交換 : Item tmp = itemlist[i]; itemlist[i] = itemlist[j]; itemlist[j] = tmp; 使い方は 商品名フィールドが追加されたとして 例えば ItemList itemlist = new ItemList(); itemlist.add(new Item(100,1200," 製図用シャープペン ")); 集合やリストは java.util に色々定義されている 自分で適宜定義しても良い インタフェースで話す キャスト を使う class MyList { private static int MaxNof = 10000; private int nof = 0; private Object[] list = new Object[MaxNof]; void add(object obj) { if (nof!= MaxNof) list[nof++] = obj; else System.out.println("sorry, full list"); 35

36 オブジェクト指向のストーリー 最初から 必要なオブジェクトとクラスを切り出す作業 他のクラスとの切り分け 分節化 部品化先んず対象のモデリング 設計 その次にアルゴリズムの設計と解析その次の次にプログラミング技法優れたモデル 優れたパッケージ ( クラスの集合 ) 保守 拡張 利用が楽 36

37 本日の演習問題 1 整数を要素とする線形リスト ( 要素の並びを表し 参照構造が一方向のもの ) について述べた 一方 CS 実験で 双方向リストをCのポインタで実現する課題を行ったと思う 課題の手引書と本講義の線形リスト Java プログラムを参考にし 実験課題に対する Java のクラスを定めよ 37

38 本日の演習問題 2 下記の 2 つのメソッドを当該クラスに追加しなさい ただし ( 平面上の ) 点とベクトルを区別するために ベクトルのクラス MyVector を定義し それを利用した上で下記のメソッドを当該クラスに追加すること 1. Point クラスのメソッド : boolean checkpointonline(point p1, Point p2); パラメータで与えた 2 点と自オブジェクトが一直線上にあれば true, otherwise false. 2. Triangle クラスのメソッド : double computearea(); ベクトルの内積を用いて面積を計算し出力 演習問題解答 : その詳細レベル仕様をかくつもりで 1. クラス名 クラスの各メンバーの仕様 2. 各メンバーの仕様 : (a) 変数であれば その型 ( クラスもしくは基本データ型 ) およびその役割 機能の説明をつける (b) メソッドであれば 出力およびパラメータ型を明記した上で その動作について正確な日本語で記述すること ただし (1) メソッド中で ( 別のオブジェクトに対し ) メソッド呼び出しを行う場合はそのことも明記 (2) スタティックの場合は static を明示 Java 言語の構文で書けるなら なお良い 38

39 本日の演習問題 3: 有限オートマトン 右図は受理機械としての有限オートマトン F A の例である ただし q0 を初期状態 q2 を受理状態とする 受理する言語は {(01) n n 1 1. FA には {0, 1 の入力記号系列が与えられる 2. 各状態で 入力系列 σ 0 σ 1...σ n 1 (n は 入力系列長 ) を受け取る 挙動は : (1) 先頭記号 σ 0 により次の状態 q next を決め (2) q next に残りの入力系列 σ 1...σ n 1 を渡し以後の処理を委ねる 3. 入力系列が空列 ( 記号が残っていない n =0) のときは 最終状態なら 受理 それ以外の場合は 非受理 のメッセージを出力し 全体の処理が終了 課題 : FA の動作を模倣するプログラム ( クラス State) を書くとして 必要なフィールドとメソッドを与え その型ならびにその挙動を説明せよ メソッド中で 別のオブジェクトに対するメソッド呼び出しを行う場合はそのことも明記すること ヒント : 各状態をエージェントと考える ただし 依頼先 ( 次の状態 ) から結果をもらう必要はこの場合ない 完全に処理を委ねる 有限オートマトンは 演習でやったと思うが 自動販売機の状態遷移 モデル 文字列検索における正規表現など 広く使われている 39