プログラミング特論 (11)
データ抽象化とモジュール
話題
◆ モジュールプログラム開発
• 段階的詳細化 (step-wise refinement)
• インタフェイス、仕様、および実装
◆ 言語によるモジュール化支援
• 手続き抽象 (procedural abstraction)
• 抽象データ型
櫻井彰人
– 表現の独立性 (representation independence)
– データ型の帰納 (datatype induction)
• パッケージとモジュール
• 汎用抽象化 (generic abstractions)
Course web site: http://www.sakurai.comp.ae.keio.ac.jp/
段階的詳細化 (stepwise refinement)
◆ Wirth, 1971
• “…プログラム… は、一連の詳細化段階を経て、次第に
開発される”
– 型パラメータをもつ関数やモジュール
Dijkstra の例
(p.35)
begin
print first 1000 primes
end
– “… program ... gradually developed in a sequence of
refinement steps”
(Introduction より)
(1969)
begin
variable table p
fill table p with first 1000
• 各段階では、命令は … より詳細な命令に分解される
– In each step, instructions … are decomposed into more
detailed instructions.
(Introduction より)
primes
begin
int array p[1:1000]
end
print table p
make for k from 1 to 1000
p[k] equal to k-th prime
N. Wirth, Program Development by Stepwise Refinement,
CACM, Vol. 14, No. 4, April 1971, pp. 221-227.
プログラム構造
Sub-program
•Dijkstra, E. W. Notes on structured programming. EWD
249 Technical U. Eindhoven, The Netherlands, 1969.
データの詳細化
◆ Wirth, 1971 再び:
Main Program
Sub-program
end
print p[k] for k from 1 to 1000
Sub-program
Sub-program
• 作業が詳細化されるとともに、データも同様に詳細化
され、 分解され、または構造化されるであろう. プロ
グラム仕様とデータ仕様を並行して詳細化するのは
自然である。
– As tasks are refined, so the data may have to be refined,
decomposed, or structured, and it is natural to refine
program and data specifications in parallel.
(Introduction より)
Sub-program
1
例
モジュールプログラム設計
◆ トップダウン設計
銀行取引
• 主たる作業を手始めに、次々と詳細化していく
◆ ボトムアップ設計
預金
引出し
印字
• 基礎概念を実装し、次にそれを結合
◆ プロトタイピング
◆ レベル 2 のためには, 口座残高
を整数型変数で表す必要あり
◆ レベル 3 のためには, 過去の取
引リストを保持する必要がある
• 全体システムの荒い近似を作成する
• 次第に、機能を追加していく
取引履歴の印字
モジュール性
例: 関数部品 (function component)
◆ 部品 (component)
◆ 部品
• 意味のあるプログラム単位
– 機能、データ構造、モジュール, …
◆ インタフェイス
• ある部品内で定義された型と操作のうち、部品の外から見えるもの
◆ 仕様
• 目論んだ部品の動作で、インタフェイスを通じて観測可能な性質とし
て表現されたもの
◆ 実装
• 部品内のデータ構造と機能
例: データ型
◆ 部品
• 優先順位付き待ち行列: 優先順位が減少する順序で要素を返すデ
ータ構造
◆ インタフェイス
• 型
pq
• 操作 empty
: pq
insert
: elt * pq → pq
deletemax : pq → elt * pq
◆ 仕様
• Insert は要素 elt を記憶した要素 pq に付け加える
• Deletemax は優先順位最高の要素 elt と残りの要素の pq を返す
• 平方根を計算する関数
◆ インタフェイス
• float sqroot (float x)
◆ 仕様
• If x>1, then sqrt(x)*sqrt(x) ≈ x.
◆ 実装
float sqroot (float x){
float y = x/2; float step=x/4; int i;
for (i=0; i<20; i++){if ((y*y)<x) y=y+step; else y=y-step; step = step/2;}
return y;
}
データ構造ライブラリを用いたヒープソート
◆ 優先順位つき待行列: 3つの操作をもつ構造
empty
: pq
insert
: elt * pq → pq
deletemax : pq → elt * pq
◆ 優先順位付き待行列を用いたアルゴリズム（ヒープソート）
begin
pq s を empty
配列から各要素を s に insert
減少順に要素を取り除き、配列におき戻す
end
これにより O(n log n) のソートアルゴリズムが得られる
2
情報隠蔽を支援する言語特徴
◆ 手続き抽象化
• 手続きや関数のもつ機能性を隠蔽
◆ データ抽象化
• データ構造の表現および操作の実装について決定したこ
とを隠す
• 例: 優先順位付き待ち行列は、二進探索木または部分ソ
ート済み配列でありうる
手続き型言語では、手続きやデータの詳細化は、それらを書
換えることにより行う（隠すことはできない）. 再利用については
、オブジェクト指向で.
抽象データ型 (abstract data types)
◆ 1970年代に目覚しく発展
◆ 主たるアイデア:
• インタフェイスを実装から分離する
–例
• 集合のインタフェイスには、empty, insert, union,
is_member?, …
• 集合の実装には、 … リンクによるリスト (linked list) …
• 型チェックを用いて、分離を強制する
– クライアントプログラムは、インタフェイス中の操作にしかアクセス
できない
– 実装は, 抽象データ型の構成子のなかにカプセル化される
抽象データ型の源流
組み込み型 (built-in types) との比較
◆ 構造化プログラミング、データ詳細化
◆ 例: int
• あるべき操作を仮定してプログラムを書く
• 後に、この操作を実装する
• 例:
– ある記号表を仮定して、式の解析プログラムを書く
– 後に、記号表データ構造を実装
◆ 拡張可能言語に関する研究
• 組み込み型の本質的性質は何か?
• 同様の性質をもったユーザ定義型を提供したい
• 例:
• この型の変数が宣言できる x: int
• この型特有の組込み演算 +, -, *, …
• 整数値に対しては、それ以外の演算は適用できない
◆ 類似の性質が、抽象データ型にも望ましい
• 変数宣言ができる x : abstract_type
• 演算の集合が定義できる (インタフェイスを与える)
• 言語は、このabstract_type にはこの演算（操作）のみが
適用できることを保証する。
– 組み込みのリストと同じリスト型を定義する
ML の Abstype
複素数の abstype
◆ 値と演算をもつ新しい型を宣言する
◆ 入力
abstype t = <tag> of <type>
with
val <pattern> = <body>
...
fun f(<pattern>) = <body>
...
end
◆ 表現
t = <tag> of <type> ML データ型の宣言と類似
abstype cmplx = C of real * real with
fun cmplx(x,y: real) = C(x,y)
fun x_coord(C(x,y)) = x
fun y_coord(C(x,y)) = y
fun add(C(x1,y1), C(x2,y2)) = C(x1+x2, y1+y2)
end
◆ 型 (コンパイラ出力)
type cmplx
val cmplx = fn : real * real -> cmplx
val x_coord = fn : cmplx -> real
val y_coord = fn : cmplx -> real
val add = fn : cmplx * cmplx -> cmplx
3
有限集合の abstype
カプセル化の原則
◆ 宣言
◆ 表現独立 (Representation Independence)
abstype 'a set = SET of 'a list with
val empty = SET(nil)
fun insert(x, SET(elts)) = ...
fun union(SET(elts1), Set(elts2)) = ...
fun isMember(x, SET(elts)) = ...
end
◆型
(コンパイラ出力)
type 'a set
val empty = - : 'a set
val insert = fn : 'a * ('a set) -> ('a set)
val union = fn : ('a set) * ('a set) -> ('a set)
val isMember = fn : 'a * ('a set) -> bool
◆ データ型帰納法 (Datatype Induction)
• 抽象データ型に関する推論方法
• インタフェイスと実装とが分離されていることに基づく
現実か理想か?
表現独立
◆ Integers
• 0,1,2, …, -1,-2, … が表現できる限り、どんな方法でもよい
• ただし、演算は正しく動作しないといけない
+, -, *, /, print, …
• 例
1の補数 v.s. 2の補数
◆ Finite Sets
• {x, y, z, … } が表現できる限り、どんな方法でもよい
• ただし、演算は正しく動作しないといけない
empty, ismember?, insert, union
• 例
リンクによるリスト vs 二進木 vs ビット・ベクトル
帰納法
• 抽象データ型の各要素は、様々な方法で実装可能
• インタフェイスが制限される -> クライアントプログラムは
ある 良い 実装を他の実装と区別することはできない
(データ型帰納法へ向けて)
◆ 主たるアイデア
• 0 は自然数である
• もし x が自然数であれば, x+1 も自然数である
• こうして得られるもののみが自然数である
◆ 全ての n について p(n) を証明せよ
• p(0) を証明せよ
• 「もし p(x) が正しいなら p(x+1) が正しい」を証明せよ
• これだけができればよい
◆ Clu, ML, … においては、表現独立は定理
• 証明できる。というのも、言語が実装へのアクセスを制限
しているから. アクセスはインタフェイスを通じてのみ
◆ C, C++, においては、表現独立は理想
• “良いプログラミング・スタイル” に従えば表現独立性が
得られる
• 言語はそれを強制しはしない
例: -1 のビット表現が印字可能
1の補数か2の補数かが分かる
整数リストに関する帰納法
◆ 原理
• nil はリストである
• もし y がリストで x が int であれば cons(x,y) はリストである
• これがリストのすべてである
◆ p(y) を全てのリストy について証明する
• p(nil) を証明する
• 「もし p(y) なら p(cons(x,y)) である」を証明する
• これだけがすべきこと
◆ 例: 次のスライド
• 注: car や cdr を考える必要はない
• なぜ? 新リストなし. (整数の帰納法に引き算がないのと同様.)
4
リストを用いた帰納法の例
◆ リストをソートする関数
• fun sort(nil) = nil
• |
sort(x::xs) = insert(x, sort(xs))
◆ ソート済みリストへの挿入
• fun insert(x, nil) = [x]
• | insert(x, y::ys) = if x<y then x::(y::ys)
•
else y::insert(x,ys)
データ型帰納法のためのインタフェイス
◆ データに対する操作を分類
• 構成子(constructors): そのデータ型の要素を作成
• 演算子(operators): 要素を結合, しかし「新」要素生成せず
• 観測子(observers): 他の型の値を生成
◆ 例:
• 集合
◆ これらの関数の正しさを証明せよ
• リスト上の帰納法を使用 (易しい、というのも ML が我々
にそのように書かせているから)
empty : set
insert : elt * set -> set
union : set * set -> set
isMember : elt * set -> bool
• 分類
構成子: empty, insert
演算子:
union
構成子上の帰納法
集合上の帰納の例
◆ 演算子: 新要素は生成しない
◆ 仮定： map 関数
• 例: 有限集合上の union
union を使って定義されたどんな集合も union なしに定義できる:
union(empty, s) = s
union(insert(x,y), s) = insert(x, union(y,s))
◆ 性質は帰納法によって証明
• 構成子によって生成される全ての要素について示す
集合の例: 「 P(empty) と P(y) => P(insert(x,y)) 」を証明
観測子:
isMember
• map(f,empty) = empty
• map(f, insert(y,s)) = union(f(y), map(f,s))
◆ 集合の共通部分を求める関数
• fun intersect(s,s’) = if empty(s’) then s’
else let f(x) = if member(x,s) then {x} else empty
in map(f, s’) end;
◆ これでよいことを証明せよ:
• s’ 上の帰納を使用:
– 正しい、もし s’ = empty
– 正しい、もし s’ = insert(y, s’’)
• これはこの型のすべての要素をカバーする
以上の帰納法のポイントは?
モジュール
◆ データ抽象は詳細を隠蔽
◆ 抽象データ型を使用するプログラムに関する推論
は、抽象的に行える
◆ 情報隠蔽のための一般的な構成要素
◆ ２個の部分からなる
• データ型の基礎的な性質を使用
• データ型がどう実装されたかは無視
• インタフェイス (interface):
名前とそれらの型の集合
• 実装 (implementation):
インタフェイス中の要素すべての宣言
隠蔽された要素に対する追加の宣言
◆ 例:
• Modula modules, Ada packages, ML structures, ...
5
モジュールとデータ抽象
総称的抽象化 (generic abstractions)
module Set
interface
type set
val empty : set
fun insert : elt * set -> set
fun union : set * set -> set
fun isMember : elt * set -> bool
implementation
type set = elt list
val empty = nil
fun insert(x, elts) = ...
fun union(…) = ...
...
end Set
◆ 型や他モジュールでパラメータ化したモジュール
◆ 汎用的な実装が可能となる
抽象データ型が定義可能
Private な型
Public な操作
より一般的
関連した型と操作をい
くつか
ある言語では
インタフェイスと実装を
分離
一つのインタフェイスで
複数の実装が可能
• 多くの方法で実体化する(instantiate)ことができる
◆ 言語の例:
• Ada generic packages, C++ templates, ML functors, …
• C++ Standard Template Library (STL) には、広範囲の
例がある
C++ Templates
例
◆ 型パラメータ化機構
◆ 単相型 (monomorphic) swap 関数
• template<class T> … が型パラメータ T を示す
• C++ にはクラステンプレートと関数テンプレートがある
– 関数の場合をこれから見る
◆ リンク時の実体化 (instantiation)
• 個々の型ごとに、テンプレートの実体が別々に作られる
• コードを重複させるのはなぜ?
– 起動記録内の局所変数の大きさが異なる
– パラメータの型ごとに異なる演算へリンクする
総称的な sort 関数
◆ 関数にはパラメータの型に対応した < が必要
template <class T>
void sort( int count, T * A[count] ) {
for (int i=0; i<count-1; i++)
for (int j=I+1; j<count-1; j++)
if (A[j] < A[i]) swap(A[i],A[j]);
}
◆ 関数 < はどうやって見つけるのか?
• sort 関数と呼出側プログラムとをリンクする
• リンク時に実際の T が決まる
• もし < が T 上で定義されていば OK, さもなくばエラー
void swap(int& x, int& y){
int tmp = x; x = y; y = tmp;
}
◆ 多態型 (polymorphic) 関数テンプレート
template<class T>
void swap(T& x, T& y){
T tmp = x; x = y; y = tmp;
}
◆ 呼出しは普通の関数のように
float a, b; … ; swap(a,b); …
ML の多態型との比較
fun insert(less, x, nil) = [x]
| insert(less, x, y::ys) = if less(x,y) then x::y::ys
else y::insert(less,x,ys)
fun sort(less, nil) = nil
| sort(less, x::xs) = insert(less, x, sort(less,xs))
◆ 多層型 (polymorphic) sort 関数
• 演算を関数として渡す
• 実体化はなし. 全てのリストは同じ方法 (Lisp のように cons セルを
用いて)で表現されているから.
◆ 一様なデータ表現
• コードは小さく, 効率は落ちるかもしれないが, リンクは複雑ではない
– オーバーローディングを解決する必要もあるであろう, etc.
6
C++ Standard Template Library
STL における主たる要素
◆ 多くの総称的抽象化
◆ コンテナ(container): 型付きオブジェクトの集合
• 多態的な抽象データ型と演算
◆ 多くの目的に有用
• 優れた例 generic programming
◆ 実行時間は効率的 (しかし空間についてはいつもではない)
◆ 記述は C++
• テンプレート機構とオーバーローディングをしよう
• オブジェクトには依存せず
アーキテクト: Alex Stepanov
• 例: array, list, associative dictionary, ...
◆ イタレータ(iterator): ポインタや番地の一般化
◆ アルゴリズム
◆ アダプタ (adapter): ある形から別の形への変換
• 例: 更新可能なコンテナからイタレータを作る
◆ 関数オブジェクト:
閉包 (“手作り”)
◆ アロケータ (allocator): カプセル化したメモリプール
• 例: GC 付きメモリ, 参照カウント付きメモリ, ...
STL を用いた例
STL でのマージ
◆ 2個のソート済みリストのマージ
◆ 範囲(range)はイタレータにより表現
• merge : range(s) × range(t) × comparison(u)
→ range(u)
概念的には正しいが, STL 構文に沿っていない.
◆ 使用される基本概念
• range(s) – 型 s の順序付き “list”, 先頭と最終要素への
ポインタで与えられる
• comparison(u) – 型 u の上のブール値関数
• subtyping - s と t は u の部分型でなければならない
• イタレータ (iterator) はポインタの一般化
• ++ (次の要素へ動く) のサポート
◆ 比較 (comparison) 演算子は Compare クラスのオ
ブジェクト
◆ テンプレートを用いた多態型 (polymorphism)
template < class InputIterator1, class InputIterator2,
class OutputIterator, class Compare >
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator1 last2,
OutputIterator result, Compare comp)
STL と他のライブライとの比較
STL の効率性
◆ C:
◆ sort の実行時間
qsort( (void*)v, N, sizeof(v[0]), compare_int );
◆ C++, ただし、元々の C 配列を用いる:
int v[N];
sort( v, v+N );
◆ C++, ただし、vector クラスを用いる:
vector v(N);
sort( v.begin(), v.end() );
C
C++ (raw arrays)
C++ (vector class)
N = 50000
1.4215
0.2895
0.2735
N = 500000
18.166
3.844
3.802
◆ ポイント
• 総称的な抽象化は、便利で効率的なりうる !
• しかし、コードサイズには気をつけよ、もし C++ テンプレ
ートを用いるなら…
7
© Copyright 2024 ExpyDoc
