プログラム理論と言語 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,
比較操作のみインタフェースにしておけば、任意のソーティングプ
ログラムは対象クラスと独立に書ける
ヒープソートは、固定配列で２分木を単純に操作
配列インデックスの算術計算でＯＫ
新規要素は配列の最後に挿入（バランスがとれた２分木）
根の値の抽出： 根の値を出力し，最後の要素の値と置き換える
関連ユーティリティ java.util には、集合やソーティング関係のインタフェース、クラスが提供され ている。調べてみること。ヒープソートの動作
Heap:
高さ
O(log n)
の２分木で，
コーディング
先んず、大小比較のためのインタフェース
【メソッドの型
=
出力型 メソッド名（引数型）】
(*)
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.
シグネチャで オーバーロード
(overload)
を決定
型が異なるメソッドは名前が同じでも別のメソッド
2.
インタフェースのメソッドと実装クラスにおける実
装は、オーバーライド（上書き
, override
）
型が同一なものがない場合、コンパイルエラー
インタフェース参照変数とキャスト
明示的キャスト：
Interface z; z = (C)x;
上位の変数は下位のオブジェクトを参照可．逆は×
インタフェース参照変数は，実装クラスオブジェクトを指す
x
が
C
のインスタンスを指していれば成功
ow.
失敗（実行エラー
:
『キャストはできません』）
クラス階層の場合も全く同じ（後述）
基本データ型の場合は，
「型縮小」
ソースコード例
class Heap {
private ObjectWithLessThan[] heap;
ObjectWithLessThan get(int index) {return heap[index];} private int size = 0;
public int size() {return size;} void reset() {size=0;}
private int capacity;
Heap(int capacity) {//容量を指定するコンストラクタ
heap = new ObjectWithLessThan[capacity]; size = 0; this.capacity=capacity; }
private static int CAPACITY = 10000;//デフォルト容量（クラス定数） Heap() {//デフォルト容量の配列を確保
capacity = CAPACITY;
heap = new ObjectWithLessThan[capacity]; size = 0; }
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; }
private void insert(ObjectWithLessThan element){ if (++size > capacity) {
System.out.println("*** 容量上限を超えています "); System.exit(1); }
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(){ if (size==0) return null;
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 childs if (!heap[branch].lessThan(heap[pt])) break; swap(branch,pt); pt = branch; }; return min; } } interface Show {//インタフェース階層の例 void show(); }
interface ObjectWithLessThan extends Show { boolean lessThan(ObjectWithLessThan y); }
class Teacher implements ObjectWithLessThan{ private int salary;
private String name, division;
Teacher(String name, String div, int salary) {
this.salary=salary; this.name=name; division=div; }
public void show() {
System.out.print("<"+name+","+division+","+salary+">, "); }
public boolean lessThan(ObjectWithLessThan y) { return salary < ((Teacher)y).salary; //給与昇順 }
}
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 name.compareTo(((Student)y).name) < 0;//name 辞書式順 }
class MyInt implements ObjectWithLessThan{ private int value;
MyInt(int i) {value = i;}
public boolean lessThan(ObjectWithLessThan y) { return value > ((MyInt)y).value; //値の降順 }
public void show() {System.out.print("<"+value+">, ");} }
class test {
public static void main(String args[]){ Student[] ss = {
new Student("mh",10), new Student("keiko",50), new Student("kenichi",100), new Student("taro",70)
};
Teacher[] ts = {new Teacher("mh", "cs",400),
new Teacher("sarah","physics",1000)}; MyInt[] is = {new MyInt(100), new MyInt(300), new MyInt(200)}; ObjectWithLessThan[][] testData = {ss, ts, is};// 配列の配列 Heap heap = new Heap();
for (int i=0;i<testData.length;i++) {
// heap.reset(); // heap は空故，リセットは不要 heap.formHeap(testData[i]);
System.out.print("+++ "+i+"-th sorted data: ");
heap.showInTheOrder(); // 実行後，heap は空になっている };
ObjectWithLessThan[] objs = {new Student("satoshi",70), new MyInt(60)}; for (int i=0;i<objs.length;i++) objs[i].show();
System.out.println(); heap.formHeap(objs);// この場合，キャストエラー } } c:\Users\makoto\home\lecture\pl\resume>javac heap.java c:\Users\makoto\home\lecture\pl\resume>java test
実装クラス
→
←
インタフェース は多対多
インタフェースは複数の実装クラス を持ち，クラスは複数のインタ フェースを実装できる． C1 オ ブ ジェク ト は ，メ ソッド {m11, m12} を持つもの（イン タフェース os1）であり，かつ メソッド{m21, m22} を持つも の（インタフェース os2）でも ある．「ある機能を持つ∼ある種のことができる∼対応するメソッドを持つ」
インタフェースの実装クラスは，機能を実現しているとも理解できる
インタフェースと実装の多対多性： クラスは複数の機能を実現
多重継承に関するコメント： 階層化への導入
複数のインタフェースの階層化も可能
一部の教科書・
Web
ページには
『インタフェースはクラス階層での多重継承問題を解決する』
と書いてあるが，正確さに欠く書き方
インタフェース階層では、メソッドの型情報を継承（集める）
クラス階層では、定義・実装を継承し集める
同じ「継承」だが、集める対象が異なり意味が違う
階層種別
継承し集める対象
意味
インタフェース階層 メソッドの型情報
役割・機能の型を宣言
定義済みの動作を複数の役割で使う
クラス階層
メソッドの定義
動作を定義する
Jave
： メソッド定義を継承すべき親は唯一
C
++:
多重継承を許す
継承問題の扱いはオブジェクト指向言語によっても、扱いが異なる。各言語の仕様を確認したうえで使 うこと 本格的・体系的分類が必要でない場合、クラス階層利用は限定的 実際のJavaではクラス階層の中にインタフェースを組み込んだ「抽象クラス」があり、話がさらに紛 らわしい 本講義では：本日の課題１
下記プログラムは、凸多角形（任意の頂点を結ぶ線分が多角形の内部もし くは外周上にある）のクラス 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) {// 点の同一性
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;
参考（凸多角形と凸包形成）
凸なことが既知の場合の処理を 考えた 凸でない場合の処理、例えば、 点集合に対し凸包（点集合 を内部に含む最小の凸多角 形）を求めるアルゴリズム 例示したプログラムの簡単な拡 張で済む： 1. 順序 lessThan の定義を修正 2. その順序に従い、基準点以外の点を列挙しながら、 凹になる候補点を除去する 凸包を求めるアルゴリズムは応用上も重要 （数理計画法、最適化問題） 膨大な点集合に対する最適解を上包（下包） 上の点に限定して算出 （目的関数の凸性も必要だが ...）（Graham の方法、Jarvis の方法、Quickhull 法など）
