プログラム理論と言語 Part2-1-3
インタフェース
Java
インタフェース： クラスとしての解釈
(*)
：
『指定された型のメソッド群を持つ「もの」』
インタフェースのメソッド：
メソッド名と型情報のみの「抽象メソッド」
実装クラスでの実装（具体化）の義務
インタフェースの利用： 「もの」そのものでなく、
「もの」が持つ操作の名前と型のみで処理を記述
⇒ 処理コードの抽象化 ⇒ 汎用で再利用度が高い
⇒ 多態性：同一の言葉・表現だが様々な振る舞い
「実装クラス」におけるメソッド定義に依存
役割・機能の部品化：
特定の役割・機能を実装クラスに。呼び出して使う
(*) インタフェースは言語仕様上はクラスと区別されるが、コンパイル した後の実行時の扱いはクラスと同じ。実際、コンパイル後のイン タフェースの拡張子はクラスと同じ .class 実際の Java インタフェースは、抽象メソッド以外にも、 定数（public static final）を持てる。インタフェースの意味である、『ある役割・機能を果たすもの』と 特定の定数が一体化している場合は、一緒に書いてよい
多態性のお話風の例示について
いくつかの教科書に掲載されている多態性の喩
『動物に鳴けと言えば、猫なら「ニャン」と鳴
き、犬なら「ワン」と鳴く（吼える？）』
1.
「鳴け」というコマンド自体は 抽象的
2.
対象指示物（犬や猫）を具体に与えた上で、
「鳴け」と命令
3.
対象物は「鳴け」を 具体化した動作 を持ち
それを実行する
インタフェースを用いた多態性：
1.
メソッド自体は名前と型情報のみ
抽象メソッド
2.
メソッド適用時： 操作の対象物 が与えられ、
3.
対象物が所有する
名前と型が同一な具体的なメソッド が起動
メソッド定義のオーバーロード（引数の数や型が異なる同一名のメソッ ドを別のメソッドとして定義）も多態性と言うこともある シグネチャ ＝ メソッドの名前と型（パラメータ型、出力型） 文献には 出力型を省いた定義のものもあるが、Java では出力型の 一致も（コンパイラが）要求。したがって、本講義では、出力型も少しは実用的な例： ヒープソートで例示
ソーティングのプログラム：
対象が持つ大小の比較情報のみに依存
Therefore,
比較操作のみインタフェースにしておけば、任意
のソーティングプログラムは対象クラスと独立に書ける
java.util.Collections
でインタフェースを用いたソート
は提供されているが、この程度は自分で書けること
ヒープソートは、固定配列で２分木を単純に操作
配列インデックスの算術計算でＯＫ
一般に２分木は、参照変数（ポインタ）を用いた再帰的
データ構造
(recursively defined data structure)
class BinaryTreeNode { private Object content;
private BinaryTreeNode leftChild;// 参照型の初期化の private BinaryTreeNode rightChild;// デフォルトは null BinaryTreeNode(Object obj) {content = obj;}
// 部分木を参照すると考えれば、BinaryTree へのポインタでも良い // ここでは、木のノードが独立したオブジェクトとの立場
boolean leaf() {
return leftChild == null && rightChild == null; }
Object getContent() {return content;}
BinaryTreeNode getLeftChild() {return leftChild;} ...
}
class BinaryTree {
private BinaryTreeNode root; ...
ヒープソートの復習（抽象的に
...
）
ヒープソートの方法は、対象となるデータがなんであって
も、比較できることだけを認めれば、説明・理解できる。
プログラムの場合も同じこと。
コーディング
//
先んず、大小比較のためのインタフェース
//
他パッケージに公開が前提。よって
public
//
メソッドは名前と型情報（シグネチャ）のみ
package mytools; // Heap
のプログラムと同一パッケージ
public interface ObjectWithLessThan {
boolean lessThan(Object y);
void show();
} //
「
lessThan
メソッドを持つもの」
//
「
lessThan
の操作対象となるもの」
既に作成済みのプログラムを「抽象化」
「
int x
」 を 「
ObjectWithLessThan x
」 に
「
(x < y)
」 等の比較判定は「
x.lessThan(y)
」等に
もちろん、実装クラスは完全に無視し、シグネチャ
boolean ObjectWithLessThan(Object)
のみを想定して
”
抽象的に
”
コーディングしても良い
インタフェースの抽象メソッドおよび実装クラスにおける実装メソッド は、must be public i.e. インタフェースはパッケージ化を想定している インタフェースの抽象メソッド記述において public は省略可 実装メソッドでは、省略不可。必ず public をつける上記では、lessThan のパラメータ型は Object にしたが、ObjectWith-LessThan でも可。Object にした理由は、他の異なるインタフェース の実装を考慮したため。generic type を使ってもよい（Java 2 Plat-form Standard Edition 5.0 ）。generic type では、キャストが不要 になる（対応する型推論をシステムが行う）
実装クラス： 具体に処理対象となるクラス
class ClassName implements Interface1, ...
（複数可）
実装の義務：
implements
する全ての抽象メソッドに対し
同一シグネチャの
public
メソッド（実装メソッド）を持つこと
実装としての使用をシグネチャの同一性で暗に識別
「実装」という、特別なメソッド定義法があるわけではない
定義済みの一部のメソッドを抽象メソッドの具体化として識別
class MyRecord implements ObjectWithLessThan{
private String name;
private int score;
public boolean lessThan(Object y) {//
シグネチャで識別
MyRecord mrec = (MyRecord)y;
//
「キャスト」は後で説明
if (name.compareTo(mrec.name) < 0) return true;
else return false;
}
public void show() {
System.out.print("
【
"+name+","+score+"
】
");
}
MyRecord(String name, int score) {
this.name=name; this.score=score;
}
抽象的なプログラムがなぜ動作するのか？
-
１
抽象メソッド＝具体化を義務づけられたメソッド
一般原則： 下位クラスのオブジェクトに対し適用できるメ
ソッドが優先（同じメソッド名と同じ型）
上位クラスで定義されたメソッドは結果的に下位クラス
のメソッドで「上書き（オーバーライド）」される
インタフェースの場合もしかり：
実装クラスのメソッドが（インタフェースの抽象メソッ
ドを必ず具体化し）実行される。
実装クラスにおける実装の義務
抽象メソッドは定義が空で、実行時に実装クラスメソッドでオーバーラ イドされると考えてＯＫ。実際、コンパイラはオーバライドされる べく実装メソッドが定義されているかをチェックする。 この事情は後述する抽象クラスにおける抽象メソッドの場合も全く同じキャスト（明示的、型縮小）
上位クラスの参照変数に下位クラスのメソッドは適用不可
そもそも変数が下位クラスのオブジェクトを指している場合、
下位クラスのメソッドを適用可にするためキャストする
キャスト後は、
mrec.getName()
がＯＫ。実際にキャスト可
能か（下位のオブジェクトか？）は、実行時に決まる
属性
mrec.name
に関しても同じ
Note: 基本データ型のキャスト： 例: x が double のとき、 int ix = (int)x; 少数点以下を切捨て、int にキャスト（副作用）// Heap sort: 基準ディレクトリ： /home/lecture/pl/java/ package mytools;
public class Heap {
private ObjectWithLessThan[] heap;
public ObjectWithLessThan get(int index) {return heap[index];} private int size;
public int size() {return size;} private int capacity;
public 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
public void insert(ObjectWithLessThan element){
if (++size > capacity) seriousError("Heap.insert: exceed capacity"); 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 childs if (!heap[branch].lessThan(heap[pt])) break;
swap(branch,pt); pt = branch; };
return min; }
public void showInTheOrder() {
while (size > 0) deleteMin().show(); System.out.println();
}
private void seriousError(String message) {
System.out.println("*** "+message); System.exit(1);} }
// ヒープソート テスト用サンプル
// 基準： /home/lecture/pl/java/ : this directory //
import mytools.Heap;
import mytools.ObjectWithLessThan; class heaptest {
public static void main(String args[]){ Heap heap = new Heap(1000);
for (int i=0;i<args.length;i++)
heap.insert(new MyInt(Integer.parseInt(args[i]))); heap.showInTheOrder();
MyRecord[] records = {
new MyRecord("mh",10), new MyRecord("keiko",50), new MyRecord("kenichi",100), new MyRecord("taro",70),
};
Heap heap2 = new Heap(10);
for (int i=0; i<records.length; i++) heap2.insert(records[i]); heap2.showInTheOrder();
} }
class MyInt implements ObjectWithLessThan{// int のラップクラス private int x; // Integer は拡大できない MyInt(int x) {this.x=x;}
public boolean lessThan(Object y) {return x < ((MyInt)y).x;} public void show() {System.out.print(" "+x);}
}
class MyRecord implements ObjectWithLessThan{ private String name;
private int score;
MyRecord(String name, int score) {this.name=name; this.score=score;} public boolean lessThan(Object y) {
MyRecord mrec = (MyRecord)y;
if (name.compareTo(mrec.name) < 0) return true; else return false; }
public void show() {
インタフェースと委譲
(delegation)
実装クラス
−→
←−
インタフェース は多対多
単に、多態性の実現（異なる異種の実装）のみならず、様々
な状況が起こりうる。下記は、共通の実装を持つ場合
複数の具体的な機能・役割を付与したい場合
インタフェースと委譲を用い、具体的な役割・機能を付与
インタフェース：
「Ａ２Ｃの役割・機能を持つもの」
シグネチャ情報＋具体的な実装を実質的に持たせる
インタフェースでは、メソッドの実装はシグネチャが一致すれば何でも よい。上記では、その実装の仕方を委譲先で定義・指定する。その 結果、インタフェースの実装クラスは、書き方のルール＝「実装を 必ず委譲する」を守って書く限りにおいて指定された具体な動作を 行うことになる多重継承に関するコメント： 階層化への導入
一部の教科書・
Web
ページには
『インタフェースはクラス階層での多重継承問題を解決する』とある
インタフェース階層では、シグネチャ（型情報）を継承（集める）
クラス階層では、定義・実装を継承し集める
同じ「継承」だが、集める対象が異なり意味が違う
階層種別
継承し集める対象
意味
インタフェース階層 メソッドの型情報
役割・機能の型を宣言
定義済みの動作を複数の役割で使う
クラス階層
メソッドの定義
動作を定義する
同じシグネチャの動作を複数定義すると困る
つまり、定義の問題と使い方の問題は、問題として違うという話
継承問題の扱いはオブジェクト指向言語によっても、扱いが異なる。各 言語の仕様を確認したうえで使うこと 本格的・体系的分類が必要でない場合、クラス階層利用は限定的 実際の Java ではクラス階層の中にインタフェースを組み込んだ「抽象 クラス」があり、話がさらに紛らわしい 本講義では： ⇒ 抽象クラスは単にインスタンス化できないクラス ⇒ 抽象クラスの抽象メソッドは、単に便宜を図るため （本当は全てインタフェースとしてきちんと書くとの立場）本日の課題１
下記は 文字列の「スタック」を、固定配列で行うものである： class MyStack {
private String[] stack;
private int capacity, size = 0; //
MyStack(int capacity) {
stack = new String[capacity]; this.capacity=capacity; }
void pushdown(String x) {
if (size >= capacity) System.out.println(" Sorry, no space"); else stack[size++] = x; } boolean empty() { return size==0; } String popup() { String str = null;
if (size==0) System.out.println(" Sorry, no element"); else str = stack[--size]; return str; } } 上記を、文字列に限定されない汎用のスタックにしたいとして、例題の ようなインタフェースが必要であるかを論じなさい。
本日の課題２
下記プログラムは、凸多角形（任意の頂点を結ぶ線分が多角形の内部もし くは外周上にある）のクラス ConvexPolygon において、外周の長さを求める （double boudaryLength()）。プログラムの動作を説明しなさい（ヒープソー トを使っているので、当然、何かをソートしている）。ただし、ヒープから要素 を順次読込むために、public ObjectWithLessThan read() {
if (size > 0) return deleteMin(); else return null; } を Heap クラスのメンバーとして追加している。なお、点や多角形のデータ読 み込みと、その方法に依存するコンストラクタは省略している。 また、オブジェクト指向の考え方からは不適切なコードを下記は含んでいる（効 率上は下記でＯＫだが ...）。それがどこかを指摘しなぜ不適切かを論じなさな い。解決策を提案できればなお良い。
import mytools.Heap;import mytools.ObjectWithLessThan; //
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) {
if (Math.abs(x - p.x) < PRECISION) return true; else return false; }
public boolean lessThan(Object 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) {// 点の同一性
if (Math.abs(x-p.x)<PRECISION && Math.abs(y-p.y)<PRECISION) return true; else return false;
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); }
参考（凸多角形と凸包形成）
凸なことが既知の場合の処理を 考えた 凸でない場合の処理、例えば、 点集合に対し凸包（点集合 を内部に含む最小の凸多角 形）を求めるアルゴリズム 例示したプログラムの簡単な拡 張で済む： 1. 順序 lessThan の定義を修正 2. その上で、凸包外周上の点候補を列挙し、凹になる候補点を除去する 凸包を求めるアルゴリズムは応用上も重要 （数理計画法、最適化問題） 膨大な点集合に対する最適解を上包（下包） 上の点に限定して算出 （目的関数の凸性も必要だが ...）（Graham の方法、Jarvis の方法、Quickhull 法など）
