プログラム理論と言語 Part2-1-3
インターフェイス
Java
インターフェイス: クラスとしての解釈
(*)
:
『指定された型のメソッド群を持つ「もの」』
インターフェイスのメソッド:
メソッド名と型情報のみの「抽象メソッド」
実装クラスでの実装(具体化)の義務
インターフェイスの利用: 「もの」そのものでなく、
「もの」が持つ操作の名前と型のみで処理を記述
⇒ 処理コードの抽象化 ⇒ 汎用で再利用度が高い
⇒ 多態性:同一の言葉・表現だが様々な振る舞い
「実装クラス」におけるメソッド定義に依存
役割・機能の部品化:
特定の役割・機能を実装クラスに。呼び出して使う
(*)インターフェイスは言語仕様上はクラスと区別されるが、コンパイルした後の実行時の扱いはクラ スと同じ。実際、コンパイル後のインターフェイスの拡張子はクラスと同じ.class 実際のJava インターフェイスは、抽象メソッド以外にも、 定数(public static final)を持てる。抽象メソッドと定数が一体化している場合は、一緒に書いてよいが、そうでない場合は区別して 独立したインターフェイスにする
オブジェクト: メソッドを持つもの
class IntCell {private int value ;
int getValue() {return value;} private IntCell next;
IntCell next() {return next;}
IntCell(int value) {this.value = value;} IntCell(int value, IntCell cell) {
this.value = value; next = cell; }
void showValue() {System.out.print(value+" ");} }
class IntList {
private int size = 0;
private IntCell firstCell = null; void tail() {// firstCell = firstCell.next(); size--; } /* IntList オブジェクトはフィールドとして IntCell オブジェクトを参照. IntCell で公開されているメソッド(やフィールド)しか使えない. カプセル化されたクラスのオブジェクトは他クラスからは『メソッドを持つもの』 他クラスからはメソッドの定義(実装)は隠されブラックボックス so, 実装を変えれば,もちろん,動作は異なる クラスごとに実装を変えるが,実装クラスに依存しないコードを書く ⇒ 多態性(polymorphism)
多態性のお話風の例示について
いくつかの教科書に掲載されている多態性の喩
『動物に鳴けと言えば、猫なら「ニャン」と鳴
き、犬なら「ワン」と鳴く(吼える?)』
1.
「鳴け」というコマンド自体は 抽象的
2.
対象指示物(犬や猫)を具体に与えた上で、
「鳴け」と命令
3.
対象物は「鳴け」を 具体化した動作 を持ち
それを実行する
インターフェイスを用いた多態性:
1.
メソッド自体は名前と型情報のみ(定義も持たない)
抽象メソッド
2.
メソッド適用時: 操作の対象物 が与えられ、
3.
対象物が所有する
名前と型が同一な具体的なメソッド が起動
型: 外形的な仕様 メソッド名、パラメータ(引数)型、出力型 喩え:『筐体の中身・動作は異なるが、プラグやコネクタが同じなら「型」は一致』少しは実用的な例: ヒープソートで例示
ソーティングのプログラム:
対象が持つ大小の比較情報のみに依存
Therefore,
比較操作のみインターフェイスにしておけば、任
意のソーティングプログラムは対象クラスと独立に書け
る
ヒープソートは、固定配列で2分木を単純に操作
配列インデックスの算術計算でOK
新規要素は配列の最後に挿入(バランスがとれた2分木)
要素の削除: 最後の要素と置き換える
parent = (child-1)/2
(整数の割り算)
関連ユーティリティ java.util には、集合やソーティング関係のインターフェイス、クラスが提供さ れている。調べてみること。ヒープソートの動作
Heap:
高さ
O(log n)
の2分木で,
コーディング
先んず、大小比較のためのインターフェイス
【メソッドの型
=
出力型 メソッド名(引数型)】
(*)
interface ObjectWithLessThan {
boolean lessThan(ObjectWithLessThan y);
void show();
} //
「
lessThan
メソッドを持つもの」
//
「
lessThan
の操作対象となるもの」
//
自動で
public
指定(全てに公開)
既に作成済みのプログラムを「抽象化」
「
int x
」 を 「
ObjectWithLessThan x
」 に
「
(x < y)
」 等の比較判定は「
x.lessThan(y)
」等に
もちろん、実装クラスは完全に無視し、型情報
boolean lessThan(ObjectWithLessThan)
のみを想定して
”
抽象的に
”
コーディングしても良い
(*) (Java の) シグネチャ: メソッド名+引数型 オーバーロードのときの条件を与える オーバーライドの際は、メソッドの型=シグネチャ+出力型 一般に、引数型と出力型の組をシグネチャと定義することも多い 本講義: 型情報と名前を合わせて単に「型」と呼ぶ実装クラス: 具体に処理対象となるクラス
class ClassName implements Interface1,Interface2, ...
(複数可)
実装の義務:
implements
する全ての抽象メソッドに対し
同じ型の
public
メソッド(実装メソッド)を持つこと
実装としての使用を 型の同一性で暗に識別
「実装」という、特別なメソッド定義法があるわけではない
定義済みの一部のメソッドを抽象メソッドの具体化として識別
class Student implements ObjectWithLessThan{
private String name;
private int score, code;
public boolean lessThan(ObjectWithLessThan y) {//
型で識別
Student yrec = (Student)y;
//
要キャスト
/*
y
は
objectWithLessThan
の参照変数ゆえに,
y
が
Student
オブジェクトを参照している場合でも,
y.name()
はバツ
キャストして
yrec.name()
等,
Student
のメソッドを使えるようにする
*/
return name.compareTo(yrec.name) < 0;
// return code < yrec.code; //
実装を変えて別の順序も可
// return score > yrec.score; // score
の降順
}
public void show() {
System.out.print("
【
"+name+","+score+"
】
");
}
用語の整理: メソッドの型について
class ζ
{ ...
σ method (τ
1x
1, ..., τ
nx
n)
{ ... }
...
}
一般に、シグネチャ:記号のシステムで
型
: ζ, , σ
j, ...
(クラス,インターフェイス,基本データ型)
関数
: f : ζ, τ
1, ..., τ
n⇒
σ
(ζ :
self, this
の型
)
本講義:メソッド名・引数と出力型情報を、単に型と呼ぶ
σ method (τ
1, ..., τ
n)
Java
:シグネチャとは、メソッド名と引数型
τ method (τ
1, ..., τ
n)
1.
シグネチャで オーバロード を決定
型が異なるメソッドは名前が同じでも別のメソッド
2.
インターフェイスのメソッドと実装クラスにおける
実装は、オーバーライド(上書き)
型が同一なものがない場合、コンパイルエラー
動的ディスパッチ,キャスト
明示的キャスト:
Interface z; z = (C)x;
上位の変数は下位のオブジェクトを参照可.逆は×
インターフェイス参照変数は,実装クラスオブジェクトを指す
x
が
C
のインスタンスを指していれば成功
ow.
失敗(実行エラー
:
『キャストはできません』)
クラス階層の場合も全く同じ(後述)
基本データ型の場合は,
「型縮小」
ソースコード例
class Heap {
private ObjectWithLessThan[] heap;
ObjectWithLessThan get(int index) {return heap[index];} private int size;
int size() {return size;} private int capacity;
Heap(int capacity) {
heap = new ObjectWithLessThan[capacity]; size = 0; this.capacity=capacity;
}
private void swap(int pt1, int pt2) { ObjectWithLessThan tmp;
tmp=heap[pt1]; heap[pt1]=heap[pt2];heap[pt2]=tmp; }
private boolean nonRoot(int pt) {return pt > 0;} private int parent(int pt) {return (pt-1)/2;}
private int succ(int pt) {return 2*pt+1;} // left successor (child)
// right は succ+1
void insert(ObjectWithLessThan element){ if (++size > capacity) {
System.out.println(" Heap: sorry, no space any more"); return; };
int pt, parent; heap[(pt=size-1)]=element;
while(nonRoot(pt) && heap[pt].lessThan(heap[(parent=parent(pt))])) { swap(pt,parent); pt = parent;
}; }
private ObjectWithLessThan deleteMin(){ ObjectWithLessThan min = heap[0]; heap[0] = heap[--size];
int pt = 0, branch;
interface ObjectWithLessThan {
boolean lessThan(ObjectWithLessThan y);
// インターフェースメソッドは他クラスで使用されることが大前提 // よって, public と理解しておく
void show(); }
class Student implements ObjectWithLessThan{ private String name;
private int score;
Student(String name, int score) {this.name=name; this.score=score;} //
public boolean lessThan(ObjectWithLessThan y) { return score < ((Student)y).score; //成績昇順
// Student オブジェクトに対し lessThan を呼び出すときの引数は Student // so, Student にキャストし,score フィールドにアクセス
// y が Student でないオブジェクトを参照している場合は,「キャストエラー」 }
public void show() {
System.out.print("【 "+name+","+score+"】 "); }
public static void main(String args[]){ Student[] records = {
new Student("mh",10), new Student("keiko",50), new Student("kenichi",100), new Student("taro",70)
};
Heap heap = new Heap(records.length);
for (int i=0; i<records.length; i++) heap.insert(records[i]); heap.showInTheOrder();
} }
実装クラス
→
←
インターフェイス は多対多
インタフェースは複数の実装クラス を持ち,クラスは複数のインタ フェースを実装できる. C1 オ ブ ジェク ト は ,メ ソッド {m11, m12} を持つもの(イン タフェース os1)であり,かつ メソッド{m21, m22} を持つも の(インタフェース os2)でも ある.「ある機能を持つ∼ある種のことができる∼対応するメソッドを持つ」
インタフェースの実装クラスは,機能を実現しているとも理解できる
インタフェースと実装の多対多性: クラスは複数の機能を実現
多重継承に関するコメント: 階層化への導入
一部の教科書・
Web
ページには
『インターフェイスはクラス階層での多重継承問題を解決する』とある
インターフェイス階層では、メソッドの型情報を継承(集める)
クラス階層では、定義・実装を継承し集める
同じ「継承」だが、集める対象が異なり意味が違う
階層種別
継承し集める対象
意味
インターフェイス階層 メソッドの型情報 役割・機能の型を宣言
定義済みの動作を複数の役割で使う
クラス階層
メソッドの定義
動作を定義する
メソッド定義を継承すべき親は唯一
継承問題の扱いはオブジェクト指向言語によっても、扱いが異なる。各言語の仕様を確認したうえで使 うこと 本格的・体系的分類が必要でない場合、クラス階層利用は限定的 実際のJavaではクラス階層の中にインターフェイスを組み込んだ「抽象クラス」があり、話がさらに 紛らわしい 本講義では: ⇒ 抽象クラスは単にインスタンス化できないクラス ⇒ 抽象クラスの抽象メソッドは、単に便宜を図るため (本当は全てインターフェイスとしてきちんと書くとの立場)本日の課題1
下記プログラムは、凸多角形(任意の頂点を結ぶ線分が多角形の内部もし くは外周上にある)のクラス ConvexPolygon において、外周の長さを求める (double boudaryLength())。プログラムの動作を説明しなさい(ヒープソー トを使っているので、当然、何かをソートしている)。ただし、ヒープから要素 を順次読込むために、(public) ObjectWithLessThan read() {
if (size > 0) return deleteMin(); else return null; } を Heap クラスのメンバーとして追加している。なお、点や多角形のデータ読 み込みと、その方法に依存するコンストラクタは省略している。 また、オブジェクト指向の考え方からは不適切なコードを下記は含んでいる(効 率上は下記でOKだが ...)。それがどこかを指摘しなぜ不適切かを論じなさな い。解決策を提案できればなお良い。
class Point implements ObjectWithLessThan { private static final double PRECISION = 1.0e-7;
// 精度定数 PRECISION: 浮動小数点実数の等号、不等号判定に用いる private double x, y;
double distance(Point p) {//pow(x,y)=x^y (べき乗), sqrt は平方根 return Math.sqrt(Math.pow(y-p.y,2)+Math.pow(x-p.x,2));
}
private static Point standardPoint;
static void setStandardPoint(Point p) { standardPoint=p;
}
boolean eqX(Point p) {// X 座標が等しい return Math.abs(x - p.x) < PRECISION; }
public boolean lessThan(ObjectWithLessThan ap) { Point p = (Point)ap;
private double slope(Point p) { return (y-p.y)/(x-p.x);
} /* (y-p.y)/(x-p.x): 0による除算 ⇒ 非数値定数 NaN, infinity
このプログラムでは slope は Point の private メンバー
その範囲(Point クラス)で調べて、lessThan だけが使用 lessThan で分母が0になる場合は除去されている.
カプセル化がデバッグの手がかりになる一例
*/
boolean moreLeftHigher(Point p) {
if ( x + PRECISION < p.x || (eqX(p) && p.y + PRECISION < y) ) return true; else return false;
} }
class ConvexPolygon {
private int nofPoints; // 点の数 private Point[] points; //点の配列 private Point standardPoint; private void setStandardPoint() {
standardPoint = points[0]; for (int i=1;i<nofPoints;i++)
if (points[i].moreLeftHigher(standardPoint)) standardPoint = points[i]; Point.setStandardPoint(standardPoint);
}
private double boundaryLength() { Heap heap = new Heap(nofPoints-1);
//standardPoint 以外の点のヒープを形成 for (int i=0;i<nofPoints;i++)
if (!points[i].pointEQ(standardPoint)) heap.insert(points[i]); double boundaryLength = 0.0;
Point presentPoint = standardPoint, nextPoint; while ((nextPoint = (Point)heap.read())!=null) {
boundaryLength += presentPoint.distance(nextPoint); presentPoint = nextPoint;
};
return boundaryLength + presentPoint.distance(standardPoint); }
public static void main(String args[]) { ConvexPolygon cp = new ConvexPolygon();
cp.readDataFromFile(args[0]); // 点の読込プロセスは省略
// readDataFromFile 実行後、points と nofPoints が定義されたとする cp.setStandardPoint();
参考(凸多角形と凸包形成)
凸なことが既知の場合の処理を 考えた 凸でない場合の処理、例えば、 点集合に対し凸包(点集合 を内部に含む最小の凸多角 形)を求めるアルゴリズム 例示したプログラムの簡単な拡 張で済む: 1. 順序 lessThan の定義を修正 2. その順序に従い、基準点以外の点を列挙しながら、 凹になる候補点を除去する 凸包を求めるアルゴリズムは応用上も重要 (数理計画法、最適化問題) 膨大な点集合に対する最適解を上包(下包) 上の点に限定して算出 (目的関数の凸性も必要だが ...)(Graham の方法、Jarvis の方法、Quickhull 法など)