DVIOUT-interface-he

Transcription

1 インタフェース プログラム理論と言語 Part2-1-3 Java インタフェース : クラスとしての解釈 (*): 指定された型のメソッド群を持つ もの インタフェースのメソッド : メソッド名と型情報のみの 抽象メソッド 実装クラスでの実装 ( 具体化 ) の義務インタフェースの利用 : もの そのものでなく もの が持つ操作の名前と型のみで処理を記述 処理コードの抽象化 汎用で再利用度が高い 多態性 : 同一の言葉 表現だが様々な振る舞い 実装クラス におけるメソッド定義に依存役割 機能の部品化 : 特定の役割 機能を実装クラスに 呼び出して使う (*) インタフェースは言語仕様上はクラスと区別されるが コンパイルした後の実行時の扱いはクラスと同じ 実際 コンパイル後のインタフェースの拡張子はクラスと同じ.class 実際の Java インタフェースは 抽象メソッド以外にも 定数 (public static final) を持てる インタフェースの意味である ある役割 機能を果たすもの と特定の定数が一体化している場合は 一緒に書いてよい 1

2 多態性のお話風の例示について いくつかの教科書に掲載されている多態性の喩 動物に鳴けと言えば 猫なら ニャン と鳴き 犬なら ワン と鳴く ( 吼える?) 1. 鳴け というコマンド自体は抽象的 2. 対象指示物 ( 犬や猫 ) を具体に与えた上で 鳴け と命令 3. 対象物は 鳴け を具体化した動作を持ちそれを実行するインタフェースを用いた多態性 : 1. メソッド自体は名前と型情報のみ抽象メソッド 2. メソッド適用時 : 操作の対象物が与えられ 3. 対象物が所有する名前と型が同一な具体的なメソッドが起動 メソッド定義のオーバーロード ( 引数の数や型が異なる同一名のメソッドを別のメソッドとして定義 ) も多態性と言うこともある シグネチャ = メソッドの名前と型 ( パラメータ型 出力型 ) 文献には出力型を省いた定義のものもあるが Java では出力型の一致も ( コンパイラが ) 要求 したがって 本講義では 出力型も含めてシグネチャを定義 2

3 少しは実用的な例 : ヒープソートで例示 ソーティングのプログラム : 対象が持つ大小の比較情報のみに依存 Therefore, 比較操作のみインタフェースにしておけば 任意のソーティングプログラムは対象クラスと独立に書ける java.util.collections でインタフェースを用いたソートは提供されているが この程度は自分で書けることヒープソートは 固定配列で2 分木を単純に操作配列インデックスの算術計算でOK 一般に2 分木は 参照変数 ( ポインタ ) を用いた再帰的データ構造 (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;... 3

4 ヒープソートの復習 ( 抽象的に...) ヒープソートの方法は 対象となるデータがなんであっても 比較できることだけを認めれば 説明 理解できる プログラムの場合も同じこと 4

5 コーディング // 先んず 大小比較のためのインタフェース // 他パッケージに公開が前提 よって 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 を使ってもよい (Java2Platform Standard Edition 5.0 ) generic type では キャストが不要になる ( 対応する型推論をシステムが行う ) 5

6 実装クラス : 具体に処理対象となるクラス 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; 6

7 抽象的なプログラムがなぜ動作するのか? - 1 インタフェース参照変数は 実行時には具体物を指している 7

8 抽象的なプログラムがなぜ動作するのか? - 2 8

9 抽象メソッド = 具体化を義務づけられたメソッド 一般原則 : 下位クラスのオブジェクトに対し適用できるメソッドが優先 ( 同じメソッド名と同じ型 ) 上位クラスで定義されたメソッドは結果的に下位クラスのメソッドで 上書き ( オーバーライド ) されるインタフェースの場合もしかり : 実装クラスのメソッドが ( インタフェースの抽象メソッドを必ず具体化し ) 実行される 実装クラスにおける実装の義務 抽象メソッドは定義が空で 実行時に実装クラスメソッドでオーバーライドされると考えて OK 実際 コンパイラはオーバライドされるべく実装メソッドが定義されているかをチェックする この事情は後述する抽象クラスにおける抽象メソッドの場合も全く同じ 9

10 キャスト ( 明示的 型縮小 ) 上位クラスの参照変数に下位クラスのメソッドは適用不可そもそも変数が下位クラスのオブジェクトを指している場合 下位クラスのメソッドを適用可にするためキャストする キャスト後は mrec.getname() がOK 実際にキャスト可能か ( 下位のオブジェクトか?) は 実行時に決まる属性 mrec.name に関しても同じ Note: 基本データ型のキャスト : 例 : x が double のとき int ix = (int)x; 少数点以下を切捨て int にキャスト ( 副作用 ) 10

11 // 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); 11

12 // ヒープソートテスト用サンプル // 基準 : /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() { System.out.print(" "+name+","+score+" "); 12

13 インタフェースと委譲 (delegation) 実装クラス インタフェースは多対多単に 多態性の実現 ( 異なる異種の実装 ) のみならず 様々な状況が起こりうる 下記は 共通の実装を持つ場合 13

14 複数の具体的な機能 役割を付与したい場合 インタフェースと委譲を用い 具体的な役割 機能を付与インタフェース : A2Cの役割 機能を持つもの シグネチャ情報 + 具体的な実装を実質的に持たせる インタフェースでは メソッドの実装はシグネチャが一致すれば何でもよい 上記では その実装の仕方を委譲先で定義 指定する その結果 インタフェースの実装クラスは 書き方のルール = 実装を必ず委譲する を守って書く限りにおいて指定された具体な動作を行うことになる A2C 等において 各インタフェースの機能 役割に関連する内部状態があれば 委譲時に 各実装クラスからパラメータで渡すとする インタフェースと委譲の組合せの重要性から その骨子だけを解説した ただし 私自身は委譲を真に必要とするプログラムを書いたことがないので インタフェースと委譲の例題は今回はつけない ( 人工的な例題はほとんど意味がないから ) 14

15 多重継承に関するコメント : 階層化への導入 一部の教科書 Web ページには インタフェースはクラス階層での多重継承問題を解決する とあるインタフェース階層では シグネチャ ( 型情報 ) を継承 ( 集める ) クラス階層では 定義 実装を継承し集める同じ 継承 だが 集める対象が異なり意味が違う階層種別継承し集める対象意味インタフェース階層メソッドの型情報役割 機能の型を宣言定義済みの動作を複数の役割で使うクラス階層メソッドの定義動作を定義する同じシグネチャの動作を複数定義すると困るつまり 定義の問題と使い方の問題は 問題として違うという話 継承問題の扱いはオブジェクト指向言語によっても 扱いが異なる 各言語の仕様を確認したうえで使うこと 本格的 体系的分類が必要でない場合 クラス階層利用は限定的 実際の Java ではクラス階層の中にインタフェースを組み込んだ 抽象クラス があり 話がさらに紛らわしい本講義では : 抽象クラスは単にインスタンス化できないクラス 抽象クラスの抽象メソッドは 単に便宜を図るため ( 本当は全てインタフェースとしてきちんと書くとの立場 ) 15

16 本日の課題 1 下記は文字列の スタック を 固定配列で行うものである : 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; 上記を 文字列に限定されない汎用のスタックにしたいとして 例題の ようなインタフェースが必要であるかを論じなさい 16

17 本日の課題 2 下記プログラムは 凸多角形 ( 任意の頂点を結ぶ線分が多角形の内部もしくは外周上にある ) のクラス ConvexPolygon において 外周の長さを求める (double boudarylength()) プログラムの動作を説明しなさい ( ヒープソートを使っているので 当然 何かをソートしている ) ただし ヒープから要素を順次読込むために public ObjectWithLessThan read() { if (size > 0) return deletemin(); else return null; を Heap クラスのメンバーとして追加している なお 点や多角形のデータ読み込みと その方法に依存するコンストラクタは省略している また オブジェクト指向の考え方からは不適切なコードを下記は含んでいる ( 効率上は下記で OK だが...) それがどこかを指摘しなぜ不適切かを論じなさない 解決策を提案できればなお良い 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; public void show() {System.out.println("x="+x+", y="+y); 17

18 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(); System.out.println(" 外周長 :"+cp.boundarylength()); 18

19 参考 ( 凸多角形と凸包形成 ) 凸なことが既知の場合の処理を考えた 凸でない場合の処理 例えば 点集合に対し凸包 ( 点集合を内部に含む最小の凸多角形 ) を求めるアルゴリズム 例示したプログラムの簡単な拡張で済む : 1. 順序 lessthan の定義を修正 2. その上で 凸包外周上の点候補を列挙し 凹になる候補点を除去する 凸包を求めるアルゴリズムは応用上も重要 ( 数理計画法 最適化問題 ) 膨大な点集合に対する最適解を上包 ( 下包 ) 上の点に限定して算出 ( 目的関数の凸性も必要だが...) (Graham の方法 Jarvis の方法 Quickhull 法など ) 19