プログラミング言語論
(Concepts on Programming Languages)
趙 建軍
情報知能工学部門
第10回:
命令型言語(4)
(Imperative Programming Languages)
抽象データ型
(データの抽象などについて解説する)
3
今日の講義
抽象とは
抽象データ型とは
抽象データ型の諸概念、利点
ADTのバリエーション
データ不変条件
抽象(abstraction)とは
多くの物や事柄や具体的な概念から、それ
らの範囲の全部に共通な属性を抜き出し、
これを一般的な概念としてとらえること
事物や表象を, ある性質・共通性・本質に着
目し, それを抽き出して把握すること
(三省堂 大辞林から )
反対語は、
具体的、具象
(concrete)
5
制御流れグラフ（ControlFlowGraph）
Enter
sum = 0 i = 1 while(i < 11) printf(sum) printf(i)
sum = sum + i i = i + i T F int main() { int sum = 0; int i = 1; while (i < 11) { sum = sum + i; i = i + 1; } printf(“%d\n”,sum); printf(“%d\n”,i); } 7
プログラム依存性グラフ (PDG)
int main() { int sum = 0; int i = 1; while (i < 11) { sum = sum + i; i = i + 1; } printf(“%d\n”,sum); printf(“%d\n”,i); } Entersum = 0 i = 1 while(i < 11) printf(sum) printf(i)
T T T T T
Control dependence
Flow dependence
T T TQUIZ TIME!
Reaching Definitions
• Concept of
definition
and
use
a = x+y;
//
a definition
of
a
//
a use
of
x
and
y
• A
definition
reaches a
use
if
Reaching Definitions
s = 0;
a = 4;
i = 0;
k == 0
b = 1;
b = 2;
i < n
s = s + a*b;
i = i + 1;
return s
抽象化とは
抽象
化（Abstraction）とは、思考における
手法のひとつで、対象から注目すべき要素
を重点的に抜き出して他は無視する方法で
ある
反対に、ある要素を特に抜き出して、これ
を無視したり、切り捨てる意味もあり、こ
の用法については
捨象
するという
13
プログラミングでの２つの抽象
抽象はプログラミングで２つの側面
から使われる
=具体的な実現方法を捨象して、機能に注目
プロセスの抽象 process abstraction
データ(型)の抽象 data abstraction
プロセスの抽象(processabstraction)
一連の
手続き
を括りだして、抽象化する
サブルーチン、手続き、関数
そのルーチンの実現方法 (実装) を抽象し
(気にせずに) 次のことのみに注目
そのルーチンの機能
そのルーチンの呼出し方: プロトコル、インター
フェース
17
プロセスの抽象:例
機能: リストを順番に並べる
呼出し方:
sort(リスト，リストの長さ）
順番に並べるための方法は気にしない
19
データ抽象(dataabstraction)
データの情報内容と情報内容の操作
のみを気にすればよい仕掛け
どのようにメモリー内で記憶されているか
どのような型定義によって実現されている
か
は気にしない
これを実現するための考え方：
抽象データ型（abstract data type）
オブジェクト指向プログラミング
(Object-oriented programming)
抽象データ型 (ADT)とは
抽象データ型 (abstract data type, ADT)と
は、データ構造とそれを直接操作する手続
きをまとめてデータ型の定義とすることで
データ抽象を実現する手法またはそのひと
まとまりとして定義されたデータ型を言う
21
抽象データ型 (ADT)とは
データ構造とそれに付随する操作をひと
まとまりに表現したもの
型とそれに付随する操作からなる。これ
は、言語が提供する型（int型など）と
同様に新たな型を定義することができる
機構である
これと同様に抽象データ型の値を使うプ
ログラムは抽象データ型の実装が変わっ
ても影響を受けない
抽象データ型
抽象データ型は次の２組からなる:
データ型(その型の変数の取りうる値の範囲)
そのデータ型のデータに対する操作(手続き、関数)
抽象データ型を定めると、
クライアントはそのデータ型を宣言することができ
る
与えられた手続きによってデータを操作できる
ADTをサポートする言語は、
ADTの具体的な実現方法（＝その抽象データ型の実
装）を記述できる
23
抽象データ型の例
スタックを扱うADT stack型を考える
クライアントはstack型の変数を宣言できる
var stk1: stack;
stack型のデータを操作する手続きがある
create(stk1)
stk1
を新たなスタックとして用意し、初期化
する
destroy(stk1)
stk1
の使用をやめる（メモリーを解放する）
empty(stk1)
stk1
を空のスタックに初期化する。
push(stk1,elm)
要素
elm
を
stk1
に積む。
elm := pop(stk1)
stk1
に積まれている最上位の要素を取り出す。
抽象データ型の例：Stack
スタックポインタの指している個所が
、データの先頭
データ１
データ２
データ３
PUSH DOWN
POP UP
スタック
スタック
ポインタ
(SP)
抽象データ型の例：Stack
27
スタック型の実現（１）
type stack = record top : integer; content : array[1..maxsize] of element end; proc create(s : stack); prepare memory for s; s.top :=0; proc destroy(s : stack); release memory for s; proc empty(s: stack); s.top :=0; proc push(s:stack; e:element); if top=maxsize then error else s.top:=s.top+1; s.content[s.top]:=e; func top(s:stack):element; if s.top=0 then error else s.top:=s.top-1; return s.content[s.top+1]; 3 a b c ・ ・ ・top
content
1 2 3 max -size c b aスタック型の実現（２）
type cell = record content : element; next : pointer to cell end; stack = pointer to cell proc create(s : stack); s=nil; proc destroy(s : stack); var t : pointer to cell; while s<>nil do t := s.next; release(s); s:=t; proc empty(s: stack); destroy(s); proc push(s:stack; e:element); var t : pointer to cell; new(t); t.content:=e; t.next:=s; c b a c b a nil29
スタックの操作
ADTとして定義されたデータは、実現法によらず操作
できる必要がある
var stk1 : stack create(stk1); push(stk1,a); push(stk1,b); x:=pop(stk1); push(stk1,c); push(stk1,d); x:=pop(stk1); nil a nil b a nil a nil c a nil d c a nil c a nil 0 … 1a … 2 a b … 1a … 2 a c … 3a c d … 2 a c …手続きとスタック
再帰呼出しでは、各呼出し毎に局所
変数が上書きされることなく、保存
されなければならない
呼出し毎に、スタック上にフレームを重ね
る
再帰呼出しから戻る際には、スタックフレ
ームを順に「ほぐして」戻る
31手続きとスタック
例: ｎの階乗を再帰的に計算する関
数 factにより、３の階乗を計算
fun
fact(n) =
if
n≦1 then
1 else
n*fact(n-1);
fact (3) ;
// 3の階乗
手続きとスタック
まず、fact(3)がコールされる
33
手続きとスタック
fact(3) の中で、“3*fact(2)”を計
算するため、 fact(2) をコール
fact(3)のフレーム
手続きとスタック
fact(2) の中で、“2*fact(1)”を計算
するため、 fact(1) をコール
35fact(3)のフレーム
fact(2)のフレーム
fact(1)のフレーム
SP
手続きとスタック
fact(1) が、値「1」をかえす
fact(2) が、値「2」をかえす
fact(3) が、値「6」をかえす
fact(2)のフレーム
fact(1)のフレーム
SP
37
39
Queueの操作
基本データ型とADT
基本データ型は元々ADTである
浮動小数点型が、どのようなビットパターン
で実現されているか、普段は気にしない
浮動小数点型のデータを操作する演算がはじ
めから用意されている
その演算を使用せず、直接ビット操作をする
ことは許されていない
基本データ型はクライアントがその実現を
41
抽象データ型の利点
カプセル化
(encapsulation)と
情報隠蔽
(information hiding)
クライアントに必要な情報のみにアクセスを許す
実現の隠蔽
(implementation hiding)と
表現独立
(representation independence)
データ構造に依存しない操作方法を提供する
実装方法が変わってもユーザプログラムの変更が要
らない
データ抽象は考え方であり、実際には上述の概
念を提供する仕掛けを与えることが目標
カプセル化と情報隠蔽
カプセル化
(encapsulation)
データ構造と操作を一まとめにし、
特定のインタフェースを通してのみ外部
と通信できる
抽象データ型を実現
モジュール間の独立性を保証
カプセル化と情報隠蔽
情報隠蔽
(information hiding)
データ構造を使用者から隠し、必要な情
報のみを公開する
使用者側のプログラムは、提供側の実装
に依存しない
43情報隠蔽は、カプセル化が本質的に持
つ性質である
３.１ カプセル化と情報隠蔽
情報隠蔽の利点
利用者側プログラムは、提供者側プログラ
ムの公開部分にだけ注目すればよい
提供者は、非公開部分のプログラムは自由
に変更できる
相互に、依存性が減少
カプセル化と情報隠蔽
データや操作の公開範囲
公開インタフェースと、プライベートイン
タフェースに二分される
公開範囲を多段階に制御することも多い
Javaは４種類のアクセス属性を持つ
(public, protected, private, 指定なし)
45カプセル化
スタックの例 (Java)
class ArrayStack {
private Object[] stack = new Object[100];
private int
stackPointer = 0;
public void push(Object element) {
stck[stackPointer++] = element;
}
public Object pop() {
ここは情報隠蔽
ここは情報公開
ここは情報公開
47
データの安全性とデータ不変条件
ADTはデータの操作を
安全な操作
に限
定している
データが安全とは、予め決められた条
件を満足していること
データの操作中以外は、この条件は常
に満足しているべき
これを
データ不変条件 (data invariant)
という
データ不変条件: 例
stack型のデータ不変条件:
0 ≦ top ≦ maxsize
top=０ならば、スタックは空
top=maxsizeならば、スタックは満杯
0＜top＜maxsizeなら、top個のデータが挿
49
