インタフェース 多態性のお話風の例示について 少しは実用的な例

プログラム理論と言語 Part2-1-3
インターフェイス
Java インターフェイス： クラスとしての解釈 (*)：
『指定された型のメソッド群を持つ「もの」』
インターフェイスのメソッド：
メソッド名と型情報のみの「抽象メソッド」
実装クラスでの実装（具体化）の義務
インターフェイスの利用： 「もの」そのものでなく、
「もの」が持つ操作の名前と型のみで処理を記述
⇒ 処理コードの抽象化 ⇒ 汎用で再利用度が高い
⇒ 多態性：同一の言葉・表現だが様々な振る舞い
「実装クラス」におけるメソッド定義に依存
役割・機能の部品化：
特定の役割・機能を実装クラスに。呼び出して使う
(*) インターフェイスは言語仕様上はクラスと区別されるが、コンパイルした後の実行時の扱いはクラ
スと同じ。実際、コンパイル後のインターフェイスの拡張子はクラスと同じ .class
実際の Java インターフェイスは、抽象メソッド以外にも、
定数（public static final）を持てる。
抽象メソッドと定数が一体化している場合は、一緒に書いてよいが、そうでない場合は区別して
独立したインターフェイスにする
1
オブジェクト： メソッドを持つもの
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）
*/
2
多態性のお話風の例示について
いくつかの教科書に掲載されている多態性の喩
『動物に鳴けと言えば、猫なら「ニャン」と鳴
き、犬なら「ワン」と鳴く（吼える？）』
1. 「鳴け」というコマンド自体は 抽象的
2. 対象指示物（犬や猫）を具体に与えた上で、
「鳴け」と命令
3. 対象物は「鳴け」を 具体化した動作 を持ち
それを実行する
インターフェイスを用いた多態性：
1. メソッド自体は名前と型情報のみ（定義も持たない）
抽象メソッド
2. メソッド適用時： 操作の対象物 が与えられ、
3. 対象物が所有する
名前と型が同一な具体的なメソッド が起動
型： 外形的な仕様
メソッド名、パラメータ（引数）型、出力型
喩え：
『筐体の中身・動作は異なるが、プラグやコネクタが同じなら「型」は一致』
3
少しは実用的な例： ヒープソートで例示
ソーティングのプログラム：
対象が持つ大小の比較情報のみに依存
Therefore, 比較操作のみインターフェイスにしておけば、任
意のソーティングプログラムは対象クラスと独立に書け
る
ヒープソートは、固定配列で２分木を単純に操作
配列インデックスの算術計算でＯＫ
新規要素は配列の最後に挿入（バランスがとれた２分木）
要素の削除： 最後の要素と置き換える
parent = (child-1)/2 （整数の割り算）
関連ユーティリティ java.util には、集合やソーティング関係のインターフェイス、クラスが提供さ
れている。調べてみること。
4
ヒープソートの動作
Heap: 高さ O(log n) の２分木で，
制約 「親の値は子の値より小さい 」を満たす
5
コーディング
先んず、大小比較のためのインターフェイス
【メソッドの型 = 出力型 メソッド名（引数型）】(*)
interface ObjectWithLessThan {
boolean lessThan(ObjectWithLessThan y);
void show();
} //
「lessThan メソッドを持つもの」
//
「lessThan の操作対象となるもの」
//
自動で public 指定（全てに公開）
既に作成済みのプログラムを「抽象化」
「int x」 を 「ObjectWithLessThan x」 に
「(x < y)」 等の比較判定は「x.lessThan(y)」等に
もちろん、実装クラスは完全に無視し、型情報
boolean lessThan(ObjectWithLessThan)
のみを想定して”抽象的に”コーディングしても良い
(*) （Java の） シグネチャ： メソッド名＋引数型
オーバーロードのときの条件を与える
オーバーライドの際は、メソッドの型＝シグネチャ＋出力型
一般に、引数型と出力型の組をシグネチャと定義することも多い
本講義： 型情報と名前を合わせて単に「型」と呼ぶ
6
実装クラス： 具体に処理対象となるクラス
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+"】 ");
}
}
7
用語の整理： メソッドの型について
class ζ { ...
σ method (τ1 x1 , ..., τn xn ) { ... }
... }
一般に、シグネチャ：記号のシステムで
型 : ζ, , σj , ...（クラス，インターフェイス，基本データ型）
関数 : f : ζ, τ1 , ..., τn ⇒ σ
(ζ : self, this の型 )
本講義：メソッド名・引数と出力型情報を、単に型と呼ぶ
σ method (τ1 , ..., τn )
Java：シグネチャとは、メソッド名と引数型 τ method (τ1 , ..., τn )
1. シグネチャで オーバロード を決定
型が異なるメソッドは名前が同じでも別のメソッド
2. インターフェイスのメソッドと実装クラスにおける
実装は、オーバーライド（上書き）
型が同一なものがない場合、コンパイルエラー
8
動的ディスパッチ，キャスト
明示的キャスト： Interface z; z = (C)x;
上位の変数は下位のオブジェクトを参照可．逆は×
インターフェイス参照変数は，実装クラスオブジェクトを指す
x が C のインスタンスを指していれば成功
ow. 失敗（実行エラー: 『キャストはできません』）
クラス階層の場合も全く同じ（後述）
基本データ型の場合は，
「型縮小」
double z = 1.0; int x = (int)z;
9
ソースコード例
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;
while((branch=succ(pt)) < size) {
if (branch+1 < size && heap[branch+1].lessThan(heap[branch]))
branch = branch+1; //take min among left and right children
if (!heap[branch].lessThan(heap[pt])) break;
swap(branch,pt); pt = branch;
};
return min;
}
void showInTheOrder() {
while (size > 0) deleteMin().show(); System.out.println();
}
10
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();
}
}
11
実装クラス →
← インターフェイス は多対多
インタフェースは複数の実装クラス
を持ち，クラスは複数のインタ
フェースを実装できる．
C1
オ ブ ジェク ト は ，メ ソッド
{m11, m12} を持つもの（イン
タフェース os1）であり，かつ
メソッド {m21, m22} を持つも
の（インタフェース os2）でも
ある．
「ある機能を持つ∼ある種のことができる∼対応するメソッドを持つ」
インタフェースの実装クラスは，機能を実現しているとも理解できる
インタフェースと実装の多対多性： クラスは複数の機能を実現
12
多重継承に関するコメント： 階層化への導入
一部の教科書・Web ページには
『インターフェイスはクラス階層での多重継承問題を解決する』とある
インターフェイス階層では、メソッドの型情報を継承（集める）
クラス階層では、定義・実装を継承し集める
同じ「継承」だが、集める対象が異なり意味が違う
階層種別
継承し集める対象
意味
インターフェイス階層 メソッドの型情報 役割・機能の型を宣言
定義済みの動作を複数の役割で使う
クラス階層
メソッドの定義
動作を定義する
メソッド定義を継承すべき親は唯一
継承問題の扱いはオブジェクト指向言語によっても、扱いが異なる。各言語の仕様を確認したうえで使
うこと
本格的・体系的分類が必要でない場合、クラス階層利用は限定的
実際の Java ではクラス階層の中にインターフェイスを組み込んだ「抽象クラス」があり、話がさらに
紛らわしい
本講義では：
⇒ 抽象クラスは単にインスタンス化できないクラス
⇒ 抽象クラスの抽象メソッドは、単に便宜を図るため
（本当は全てインターフェイスとしてきちんと書くとの立場）
13
本日の課題１
下記プログラムは、凸多角形（任意の頂点を結ぶ線分が多角形の内部もし
くは外周上にある）のクラス ConvexPolygon において、外周の長さを求める
（double boudaryLength()）。プログラムの動作を説明しなさい（ヒープソー
トを使っているので、当然、何かをソートしている）。ただし、ヒープから要素
を順次読込むために、
(public) ObjectWithLessThan read() {
if (size > 0) return deleteMin(); else return null;
}
を Heap クラスのメンバーとして追加している。なお、点や多角形のデータ読
み込みと、その方法に依存するコンストラクタは省略している。
また、オブジェクト指向の考え方からは不適切なコードを下記は含んでいる（効
率上は下記でＯＫだが ...）。それがどこかを指摘しなぜ不適切かを論じなさな
い。解決策を提案できればなお良い。
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;
if (eqX(standardPoint))
if (standardPoint.eqX(p)) return y + PRECISION < p.y;
else return false;
if (standardPoint.eqX(p)) return true;
return slope(standardPoint) > p.slope(standardPoint) + PRECISION ;
}
boolean pointEQ(Point p) {// 点の同一性
return Math.abs(x-p.x) < PRECISION && Math.abs(y-p.y) < PRECISION ;
}
public void show() {System.out.println("x="+x+", y="+y);}
14
private double slope(Point p) {
return (y-p.y)/(x-p.x);
} /* (y-p.y)/(x-p.x)： ０による除算 ⇒ 非数値定数 NaN, infinity
このプログラムでは slope は Point の private メンバー
その範囲 (Point クラス) で調べて、lessThan だけが使用
lessThan で分母が０になる場合は除去されている.
カプセル化がデバッグの手がかりになる一例
*/
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();
System.out.println("外周長："+cp.boundaryLength());
}
}
15
参考（凸多角形と凸包形成）
凸なことが既知の場合の処理を
考えた
凸でない場合の処理、例えば、
点集合に対し凸包（点集合
を内部に含む最小の凸多角
形）を求めるアルゴリズム
例示したプログラムの簡単な拡
張で済む：
1. 順序 lessThan の定義を修正
2. その順序に従い、基準点以外の点を列挙しながら、
凹になる候補点を除去する
凸包を求めるアルゴリズムは応用上も重要
（数理計画法、最適化問題）
膨大な点集合に対する最適解を上包（下包）
上の点に限定して算出
（目的関数の凸性も必要だが ...）
（Graham の方法、Jarvis の方法、Quickhull
法など）
16