Microsoft PowerPoint L10-Imperative Programming Languages pptx

Transcription

1 プログラミング言語論 (Concepts on Programming Languages) 趙建軍 情報知能工学部門 1

2 第 10 回 : 命令型言語 (4) (Imperative Programming Languages) 抽象データ型 ( データの抽象などについて解説する )

3 今日の講義 抽象とは 抽象データ型とは 抽象データ型の諸概念 利点 ADTのバリエーション データ不変条件 3

4 抽象 (abstraction) とは 多くの物や事柄や具体的な概念から それらの範囲の全部に共通な属性を抜き出し これを一般的な概念としてとらえること 事物や表象を, ある性質 共通性 本質に着目し, それを抽き出して把握すること ( 三省堂大辞林から ) 反対語は 具体的 具象 (concrete) 4

5 抽象 (abstraction): 例 1 5

6 抽象 (abstraction): 例 2 6

7 制御流れグラフ (ControlFlowGraph) 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); } Enter sum = 0 i = 1 while(i < 11) printf(sum) printf(i) T F sum = sum + i i = i + i 7

8 プログラム依存性グラフ (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); } Enter T T T Control dependence Flow dependence sum = 0 i = 1 while(i < 11) printf(sum) printf(i) T T T T sum = sum + i T i = i + i 8

9 QUIZ TIME! 2017/6/15 9

10 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 value written by definition may be read by use

11 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

12 抽象化とは 抽象化 (Abstraction) とは 思考における手法のひとつで 対象から注目すべき要素を重点的に抜き出して他は無視する方法である 反対に ある要素を特に抜き出して これを無視したり 切り捨てる意味もあり この用法については捨象するという 従って 抽象と捨象は盾の両面といえる 12

13 抽象化 : 例 13

14 プログラミングでの 2 つの抽象 抽象はプログラミングで 2 つの側面 から使われる = 具体的な実現方法を捨象して 機能に注目 プロセスの抽象 process abstraction データ ( 型 ) の抽象 data abstraction 14

15 15

16 プロセスの抽象 (processabstraction) 一連の手続きを括りだして 抽象化する サブルーチン 手続き 関数 そのルーチンの実現方法 ( 実装 ) を抽象し ( 気にせずに ) 次のことのみに注目 そのルーチンの機能 そのルーチンの呼出し方 : プロトコル インターフェース 16

17 プロセスの抽象 : 例 機能 : リストを順番に並べる 呼出し方 : sort( リスト, リストの長さ ) 順番に並べるための方法は気にしない 17

18 クイックソート (Quick Sort) 18

19 データ抽象 (dataabstraction) データの情報内容と情報内容の操作のみを気にすればよい仕掛け どのようにメモリー内で記憶されているか どのような型定義によって実現されているか は気にしない これを実現するための考え方 : 抽象データ型 (abstract data type) オブジェクト指向プログラミング (Objectoriented programming) 19

20 抽象データ型 (ADT) とは 抽象データ型 (abstract data type, ADT) とは データ構造とそれを直接操作する手続きをまとめてデータ型の定義とすることでデータ抽象を実現する手法またはそのひとまとまりとして定義されたデータ型を言う ADT = properties + operations ADT= データ型 + データに対する操作 20

21 抽象データ型 (ADT) とは データ構造とそれに付随する操作をひとまとまりに表現したもの 型とそれに付随する操作からなる これは 言語が提供する型 (int 型など ) と同様に新たな型を定義することができる機構である これと同様に抽象データ型の値を使うプログラムは抽象データ型の実装が変わっても影響を受けない 21

22 抽象データ型 抽象データ型は次の 2 組からなる : データ型 ( その型の変数の取りうる値の範囲 ) そのデータ型のデータに対する操作 ( 手続き 関数 ) 抽象データ型を定めると クライアントはそのデータ型を宣言することができる 与えられた手続きによってデータを操作できる ADT をサポートする言語は ADTの具体的な実現方法 (=その抽象データ型の実装 ) を記述できる ADTの実装を隠蔽することができる クライアント =ADT を利用する側のルーチン 22

23 抽象データ型の例 スタックを扱う ADT stack 型を考える クライアントは stack 型の変数を宣言できる var stk1: stack; stack 型のデータを操作する手続きがある create(stk1) stk1を新たなスタックとして用意し 初期化する destroy(stk1) stk1の使用をやめる ( メモリーを解放する ) empty(stk1) push(stk1,elm) elm := pop(stk1) stk1 を空のスタックに初期化する 要素 elm を stk1 に積む stk1 に積まれている最上位の要素を取り出す 23

24 抽象データ型の例 :Stack スタックポインタの指している個所が データの先頭 PUSH DOWN POP UP データ3 データ2 データ1 スタックポインタ (SP) スタックポインタ (SP) 24

25 抽象データ型の例 :Stack 25

26 抽象データ型の例 :Stack 26

27 スタック型の実現 (1) 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; content 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]; max -size 3 a b c top c b a 27

28 スタック型の実現 (2) 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; func pop(s:stack):element; var t : pointer to cell; e : element; e:=t.content; t:=s; s:=t.next; release(t); return e; c b a nil c b a 28

29 スタックの操作 ADT として定義されたデータは 実現法によらず操作できる必要がある var stk1 : stack create(stk1); push(stk1,a); push(stk1,b); 0 2 a b 1 a 1 a nil a nil b a nil x:=pop(stk1); push(stk1,c); push(stk1,d); x:=pop(stk1); 2 a c 2 a c 3 a c d a nil c a nil d c a nil c a nil 29

30 QUIZ TIME! 2017/6/15 30

31 手続きとスタック 再帰呼出しでは 各呼出し毎に局所 変数が上書きされることなく 保存 されなければならない 呼出し毎に スタック上にフレームを重ねる 再帰呼出しから戻る際には スタックフレームを順に ほぐして 戻る 31

32 手続きとスタック 例 : n の階乗を再帰的に計算する関 数 fact により 3 の階乗を計算 fun fact(n) = if n 1 then 1 else n*fact(n-1); fact (3) ; // 3 の階乗 32

33 手続きとスタック まず fact(3) がコールされる fact(3) のフレーム SP 33

34 手続きとスタック fact(3) の中で 3*fact(2) を計 算するため fact(2) をコール fact(2) のフレーム fact(3) のフレーム SP 34

35 手続きとスタック fact(2) の中で 2*fact(1) を計算 するため fact(1) をコール fact(1) のフレーム fact(2) のフレーム fact(3) のフレーム SP 35

36 手続きとスタック fact(1) が 値 1 をかえす fact(2) が 値 2 をかえす fact(3) が 値 6 をかえす fact(1) のフレーム fact(2) のフレーム fact(3) のフレーム SP 36

37 抽象データ型の例 :Queue 37

38 抽象データ型の例 :Queue 38

39 Queue の操作??? 39

40 基本データ型と ADT 基本データ型は元々 ADT である 浮動小数点型が どのようなビットパターンで実現されているか 普段は気にしない 浮動小数点型のデータを操作する演算がはじめから用意されている その演算を使用せず 直接ビット操作をすることは許されていない 基本データ型はクライアントがその実現を気にせずに使うことができるので 組み込みの ADT と考えられる 40

41 抽象データ型の利点 カプセル化 (encapsulation) と情報隠蔽 (information hiding) クライアントに必要な情報のみにアクセスを許す 実現の隠蔽 (implementation hiding) と表現独立 (representation independence) データ構造に依存しない操作方法を提供する 実装方法が変わってもユーザプログラムの変更が要らない データ抽象は考え方であり 実際には上述の概念を提供する仕掛けを与えることが目標 41

42 カプセル化と情報隠蔽 カプセル化 (encapsulation) データ構造と操作を一まとめにし 特定のインタフェースを通してのみ外部と通信できる 抽象データ型を実現 モジュール間の独立性を保証 他のソースコードに依存しない 42

43 カプセル化と情報隠蔽 情報隠蔽 (information hiding) データ構造を使用者から隠し 必要な情報のみを公開する 使用者側のプログラムは 提供側の実装に依存しない 情報隠蔽は カプセル化が本質的に持つ性質である 43

44 3.1 カプセル化と情報隠蔽 情報隠蔽の利点 利用者側プログラムは 提供者側プログラムの公開部分にだけ注目すればよい 提供者は 非公開部分のプログラムは自由に変更できる 相互に 依存性が減少 44

45 カプセル化と情報隠蔽 データや操作の公開範囲 公開インタフェースと プライベートインタフェースに二分される 公開範囲を多段階に制御することも多い Javaは4 種類のアクセス属性を持つ (public, protected, private, 指定なし ) 45

46 カプセル化 スタックの例 (Java) ここは情報隠蔽 class ArrayStack { private Object[] stack = new Object[100]; private int stackpointer = 0; public void push(object element) { stck[stackpointer++] = element; } } public Object pop() { return stack[--stackpointer]; } ここは情報公開 46

47 データの安全性とデータ不変条件 ADT はデータの操作を安全な操作に限定している データが安全とは 予め決められた条件を満足していること データの操作中以外は この条件は常に満足しているべき これをデータ不変条件 (data invariant) という 47

48 データ不変条件 : 例 stack 型のデータ不変条件 : 0 top maxsize top=0 ならば スタックは空 top=maxsize ならば スタックは満杯 0<top<maxsize なら top 個のデータが挿入順と逆に入っている 48

49 データ不変条件 データ不変条件中心に ADT を設計するとよい データ不変条件を決定する データの操作を決定する ここまででADT が決まる データ構造 操作の実装を決める ADT の理論的基礎づけ : 公理的 代数的記述と関連 49

50 まとめ 抽象はプログラミング ( だけでなく 工学 ) での重要概念 ADT はデータの機能面に注目し 実装を隠す ADT= データ型 + データに対する操作 ADT は クライアントに実装を隠蔽 プログラム開発用容易にする 実装の置き換えを容易にする 安全な操作のみをクライアントに許し データ不変条件を守る 50