7. 設計の抽象化 プログラミング論 I.

Presentation on theme: "7. 設計の抽象化 プログラミング論 I."— Presentation transcript:

1 7. 設計の抽象化 プログラミング論 I

2 関数における類似性：関数抽象 設計レシピに沿って対象データの定義に基づき関数のテンプレートを決定し，その後，詳細化を行った．
→ 同じ種類のデータを処理する関数は類似する． 類似した複数の関数を，すぐには定義しない． → 不要な反復(間違いの主要因)を排除，生産性向上 関数抽象 (Functional Abstraction) 複数の類似した計算手順を単一の関数定義へ統合 単一の定義とすることで複数の関連問題を一度に解決

3 例題1.関数における類似性(要素探索) 例：シンボルのリストが要素‘doll を含むかを調べる関数contains-doll?とシンボルのリストが要素‘car を含むかを調べる関数 contains-car? (同じデータ定義を使う) シンボルのリスト los (list-of-symbols) は以下のいずれか 1. 空のリスト empty，もしくは 2. (cons s los) ここで s はシンボル，los はシンボルのリスト 'doll と 'car の両方を探せる単一の関数を定義する 　　(参考：第5回資料 課題3)

4 例題1.関数における類似性(要素探索) 例：シンボルのリストが要素 'doll を含むか調べる データ定義 に基づくテ
;; contains-doll? : los -> boolean ;; determine if a list of symbols (alos) contains 'doll (define (contains-doll? alos) (cond [(empty? alos) …] [else … (first alos) … … (contains-doll? (rest alos)) …])) 基底ケースの答は false (空のリストに'dollは含まれない) 第2節は first 項の要素を調べる必要がある → 入れ子の cond (cond [(empty? alos) false] [else (cond [(symbol=? (first alos) 'doll ) true] [else (contains-doll? (rest alos))]) ])) データ定義 に基づくテ ンプレート 具体化され た関数定義 探索終了(不成功) 探索終了(成功)

5 例題1.関数における類似性(要素探索) 例：シンボルのリストが要素 'car を含むか調べる データ定義 に基づくテ
;; contains-car? : los -> boolean ;; determine if a list of symbols (alos) contains 'car (define (contains-car? alos) (cond [(empty? alos) …] [else … (first alos) … … (contains-car? (rest alos)) …])) 基底ケースの答は false (空のリストに'carは含まれない) 第2節は first 項の要素を調べる必要がある → 入れ子の cond (cond [(empty? alos) false] [else (cond [(symbol=? (first alos) 'car ) true] [else (contains-car? (rest alos))]) ])) データ定義 に基づくテ ンプレート 具体化され た関数定義 探索終了(不成功) 探索終了(成功)

6 例題1.関数における類似性(要素探索) 設計レシピによる設計では対象データの定義をもとに関数のテンプレートを決定 → 同じ種類のデータを処理する関数は類似。 (define (contains-doll? alos) (cond [(empty? alos) false] [else (cond [(symbol=? (first alos) 'doll) true] [else (contains-doll? (rest alos))])])) (define (contains-car? alos) (cond [(empty? alos) false] [else (cond [(symbol=? (first alos) 'car) true] [else (contains-car? (rest alos))])]))

7 例題1.関数における類似性(要素探索) シンボル'dollを含むか調べる関数 contains-doll?と シンボル'carを含むか調べる関数 contains-car?は類似 異なるのは関数名と，調べる(比較する)対象のシンボル： 関数名は統一すれば良い (正しく使えば名前そのものは任意) 比較するシンボルは個別に異なる → 追加引数 ;; contains? : symbol los -> boolean ;; determine whether alos contains the symbol s (define (contains? s alos) (cond [(empty? alos) false] [else (cond [(symbol=? (first alos) s) true] [else (contains? s (rest alos))])])) 追加データ片(探すシンボル) 以外は2つのもとの関数と類似

8 練習1.関数における類似性(要素探索) 整数のリストが要素 5を含むか調べる関数contains-5? と整数のリストが要素 8を含むか調べる関数 contains-8? をそれぞれ定義せよ。次にこれらをひとつの関数定義にせよ。 (define (contains-5? alon) (cond [(empty? alon) false] [(= 5 (first alon)) true] [else (contains-5? (rest alon))])) (define (contains-8? alon) (cond [(empty? alon) false] [(= 8 (first alon)) true] [else (contains-8? (rest alon))])) (define (contains? n alon) (cond [(empty? alon) false] [(= n (first alon)) true] [else (contains? n (rest alon))]))

9 C言語だと.. #define SUCCESS 1 #define FAILURE 0 // contains: node_t *, int -> int int contains(node_t *p, int d){ if (p == NULL) return FAILURE; if (p->data == d) return SUCCESS; else return contains(p->next, d); }

10 例題2.関数における類似性(フィルタ) 以下の関数は何を計算するか? また類似と相違はどうか?
;;below : lon number -> lon ;;return a list of those numbers on alon that are below t (define (below alon t) (cond [(empty? alon) empty] [else (cond [(< (first alon) t) (cons (first alon) (below (rest alon) t))] [else (below (rest alon) t)])])) ;;above : lon number -> lon ;;return a list of those numbers on alon that are above t (define (above alon t) (cond [(empty? alon) empty] [else (cond [(> (first alon) t) (cons (first alon) (above (rest alon) t))] [else (above (rest alon) t)])]))

11 実行例 (below (list 6 5 4) 5) = (cond [(empty? (list 6 5 4)) empty]
[else (cond [(< (first (list 6 5 4)) 5) (cons (first (list 6 5 4)) (below (rest (list 6 5 4)) 5))] [else (below (rest (list 6 5 4)) 5)])]) = …(中略) = (below (list 4) 5) = (cons 4 (below empty 5)) = (list 4) (above (list 6 5 4) 5) = …(中略) = (cons 6 (above (list 4) 5)) = (cons 6 (above empty 5)) = (list 6)

12 例題2.関数における類似性(フィルタ) リストの要素がある数より小さいか(大きいか)でふるいにかける．相違は関数の名前と，比較に使う演算子。
;;below : lon number -> lon ;;return a list of those numbers on alon that are below t (define (below alon t) (cond [(empty? alon) empty] [else (cond [(< (first alon) t) (cons (first alon) (below (rest alon) t))] [else (below (rest alon) t)])])) ;;above : lon number -> lon ;;return a list of those numbers on alon that are above t (define (above alon t) (cond [(empty? alon) empty] [else (cond [(> (first alon) t) (cons (first alon) (above (rest alon) t))] [else (above (rest alon) t)])]))

13 C言語でbelowを定義 typedef struct _node{ int data; struct _node *next;
//below: node_t*, node_t **, int -> int int below(node_t *p, node_t** pp, int t){ int append(int, node_t**); if (p == NULL) return SUCCESS; if ((p->data) < t) if (append(p->data, pp) == FAILURE) return FAILURE; return below(p->next, pp, t); } void main(){ node_t *p = NULL; node_t *np = NULL; append(10, &p); append(20, &p); append(30, &p); below(p, &np, 25); // [10, -]->[20, NULL] printList(np); typedef struct _node{ int data; struct _node *next; }node_t; // append: int, node_t ** -> int int append(int d, node_t **pp){ node_t *p = NULL; p = newNode(d, NULL); if (p == NULL) return FAILURE; while (*pp != NULL) pp = &((*pp)->next); *pp = p; return SUCCESS; }

14 例題2.関数における類似性(フィルタ) リストの要素がある数より小か(大か)でふるいにかける． 相違は関数の名前に加え比較する演算子：
関数名は統一 (正しく使えば名前そのものは任意) 比較演算子は個別に異なり，個別に指定する必要 →追加引数 ;;filter1: (number number -> boolean) lon number -> lon ;;return a list of those numbers n on alon ;; for which (rel_op n t) evaluates to true (define (filter1 rel_op alon t) (cond [(empty? alon) empty] [else (cond [(rel_op (first alon) t) (cons (first alon) (filter1 rel_op (rest alon) t))] [else (filter1 rel_op (rest alon) t)])])) 追加引数(比較演算子)以外 は2つのもとの関数と類似

15 C言語でfilter1を定義 int lt(int a, int t){ return (a<t); }
//filter1: ((int, int)->int), node_t*, node_t **, int -> int int filter1(int (*relop)(int, int), node_t *p, node_t** pp, int t){ int append(int, node_t**); if (p == NULL) return SUCCESS; if ((*relop)(p->data, t)==SUCCESS) if (append(p->data, pp) == FAILURE) return FAILURE; return filter1((*relop), p->next, pp, t); } void main(){ node_t *p = NULL; node_t *np = NULL; append(10, &p); append(20, &p); append(30, &p); filter1(lt, p, &np, 25); // [10, -]->[20, NULL] printList(np); int lt(int a, int t){ return (a<t); } int gt(int a, int t){ return (a>t); } int below(node_t *p, node_t **p, int t){ return filter1(lt, p, pp, t); } int above(node_t *p, node_t **p, int t){ return filter1(gt, p, pp, t); // append: int, node_t ** -> int int append(int d, node_t **pp){ node_t *p = NULL; p = newNode(d, NULL); if (p == NULL) return FAILURE; while (*pp != NULL) pp = &((*pp)->next); *pp = p; return SUCCESS; }

16 実行例 (filter1 < (list 6 4) 5) = (cond [(empty? (list 6 4)) empty]
[else (cond [(< (first (list 6 4)) 5) (cons (first (list 6 4)) (filter1 < (rest (list 6 4)) 5))] [else (filter1 < (rest (list 6 4)) 5)])]) = …(中略) = (filter1 < (list 4) 5) = (cons 4 (filter1 < empty 5)) = (list 4) (filter1 > (list 6 4) 5) = …(中略) = (cons 6 (filter1 > (list 4) 5)) = (cons 6 (filter1 > empty 5)) = (list 6)

17 例題2.関数における類似性(フィルタ) 抽象関数 filter1 で他の類似の関数も定義できる。
filter1 を使って，もとの below と above を定義 (filter1 < alon t) が (below alon t) と同じ結果を計算 (filter1 > alon t) が (above alon t) と同じ出力を計算 抽象関数 filter1 で他の類似の関数も定義できる。 1. (filter1 = alon t): t に等しい alon 中の全ての数を抽出 2. (filter1 <= alon t): alon 中の t 以下の数のリストを生成 3. (filter1 >= alon t): alon 中の t 以上の数のリストを生成 比較には既定義の演算子だけでなく規約(contract)が合う ユーザ定義関数も使える: (number number -> boolean) ;;filter1: (number number -> boolean) lon number -> lon ;;return a list of those numbers n on alon ;; for which (rel_op n t) evaluates to true (define (filter1 rel_op alon t) ...略)

18 練習2.関数における類似性(フィルタ) 以下の filter1 の規約(contract)を日本語で説明せよ
;;filter1: (number number -> boolean) lon number -> lon ;;return a list of those numbers n on alon ;; for which (rel_op n t) evaluates to true (define (filter1 rel_op alon t) ...略) filter1 を使い,もとの below と above を定義できた。 (define (below alon t) (filter1 < alon t)) (define (above alon t) (filter1 > alon t)) 抽象関数 filter1 で他の類似の関数も定義せよ。 1. num_equal: alon 中の t に等しい全要素を抽出したリストを生成 2. below_or_eq: alon 中の t 以下の数を抽出したリストを生成 3. above_or_eq: alon中の t 以上の数を抽出したリストを生成

19 データ定義における類似性 類似のデータ定義を持つ関数定義の多くは類似性がある
類似のデータ定義例：シンボルのリストと数のリストの定義． 違いはデータのクラス名と，リスト要素の型 (「シンボル」と「数」) 例：シンボルのリスト los (list-of-symbols) はいずれか 1. 空のリスト empty もしくは 2. (cons s los) ここで s はシンボル、los はシンボルのリスト 例：数のリスト lon (list-of-numbers) はいずれか 2. (cons n lon) ここで n は数、lon は数のリスト (間違いの主要因にもなり得る)不要な反復を排除し，生産性の向上を目指す

20 例題3.データ定義の類似性(リスト長) 設計レシピに沿って、対象データの定義関数のテンプレートを決定後、詳細化をしてきた
→ 同じ種類のデータを処理する関数は類似 例：シンボルのリストの要素数、数のリストの要素数を求める length-los と length-lon (参考：第5回how-many) シンボルのリスト los (list-of-symbols) はいずれか 1. 空のリスト empty, もしくは 2. (cons s los) ここで s はシンボル、los はシンボルのリスト 数のリスト lon (list-of-numbers) はいずれか 2. (cons n lon) ここで n は数、lon は数のリスト

21 例題3.データ定義の類似性(リスト長) 例：関数 length-los (シンボルリストの要素数を計算)
;; length-los : los (list-of-symbols) -> number ;; to determine how many symbols are on an los (alos) (define (length-los alos) (cond [(empty? alos) …] [else … (first alos) … … (length-los (rest alos)) …])) 基底ケースの答は0 (空のリストの要素数は0) 第2節は first 項の要素数と rest 項の要素数を計算して結合 → alos の要素数は後者の式の値に1を加えるだけ： (cond [(empty? alos) 0] [else (+ 1 (length-los (rest alos)))])) データ定義 に基づくテ ンプレート 具体化され た関数定義

22 例題3.データ定義の類似性(リスト長) 例：関数 length-lon (数のリストの要素数を計算)
;; length-lon : lon (list-of-numbers) -> number ;; to determine how many numbers are on an lon (alon) (define (length-lns alon) (cond [(empty? alon) …] [else … (first alon) … … (length-lon (rest alon)) …])) 基底ケースの答は0 (空のリストの要素数は0) 第2節は first 項の要素数と rest 項の要素数を計算して結合 → alon の要素数は後者の式の値に1を加えるだけ： (define (length-lon alon) (cond [(empty? alon) 0] [else (+ 1 (length-lon (rest alon)))])) データ定義 に基づくテ ンプレート 具体化され た関数定義

23 例題3.データ定義の類似性(リスト長) シンボルリストの要素数を求める関数 length-los と数リストの要素数を求める関数 length-lon の相違点 　　関数と 引数変数の名前→ これらを統一して一般化 リスト要素の具体的種類（型）を問わない関数を，多相的 Polymorphic 関数，またはGeneric 関数という． ;;length-general : list-of-any-items -> number ;;determine how many items are on a list (alist) (define (length-general alist) (cond [(empty? alist) 0] [else (+ 1 (length-general (rest alist)))]))

24 例題3.データ定義の類似性(リスト長) (パラメトリックな) ITEM リストの定義： ITEM のリストは次のどちらかである
length のような関数の正確な規約を書くにはパラメータを持つデータ定義が必要 → パラメトリックなデータ定義 (パラメトリックな) ITEM リストの定義： ITEM のリストは次のどちらかである 1. empty あるいは 2. (cons s l) ここで s は ITEM ，l は ITEM のリスト ITEM：は任意のSchemeデータを表す型変数 (Type Variable) で，シンボル, 数, ブール値などの型を表す． ITEM をシンボル, 数, ブール値などの1つの型で置換すると，抽象的リストデータ定義から具体的リストデータ定義を得る．

25 例題3.データ定義の類似性(リスト長) 規約の記法：(listof ITEM) 前記の抽象リストデータ定義
* (listof symbol) はシンボルの全てのリストのクラス * (listof number) は数の全てのリストのクラス、 * (listof (listof number)) は数のリストの全てのリストのクラス。 (listof X) を使った例：全てのリストに対し機能する規約 ;;length-general : (listof X) -> number ;;determine how many items are on a list (alist) (define (length-general alist) (cond [(empty? alist) 0] [else (+ 1 (length-general (rest alist)))])) 型変数(単なる変数で、データ のあるクラスを表す名前) 具体的なデー タの種類(型)

26 例題4. 具体例からの抽象化(レシピ) 抽象化の手順を定式化し(レシピ)，以下の例に適用
;; convertCF : lon -> lon (define (convertCF alon) (cond [(empty? alon) empty] [else (cons (C2F (first alon)) (convertCF (rest alon)))])) C2F は摂氏から華氏への変換を行う関数(参考：第1回の課題2) (define (C2F c) (+ 32 (* 9/5 c))) ;; hours->wages : lon -> lon (define (hours->wages alon) (cond [(empty? alon) empty] [else (cons (wage (first alon)) (hours->wages (rest alon)))])) 関数 wage は勤務時間に対する賃金を計算：12ドル×勤務時間

27 例題4. 具体例からの抽象化(レシピ) 比較：名前といくつかの箇所を除き，ほぼ同じ2つの関数 → 相違にマークを付ける
;; convertCF : lon -> lon (define (convertCF alon) (cond [(empty? alon) empty] [else (cons ( C2F (first alon)) (convertCF (rest alon)))])) ;; hours->wages : lon -> lon (define (hours->wages alon) (cond [(empty? alon) empty] [else (cons ( wage (first alon)) (hours->wages (rest alon)))])) 定義している関数の名前以外で相違している点

28 例題4. 具体例からの抽象化(レシピ) 抽象化：対応するマーク対の内容を新しい名前で置換 パラメータリストにこれらの名前を加える．
;; convertCF : lon -> lon (define (convertCF f alon) (cond [(empty? alon) empty] [else (cons ( f (first alon)) (convertCF f (rest alon)))])) ;; hours->wages : lon -> lon (define (hours->wages f alon) (cond [(empty? alon) empty] [else (cons ( f (first alon)) (hours->wages f (rest alon)))])) マークを付けた名前を fで置き換え，f をパラメータとして加えた．

29 例題4. 具体例からの抽象化(レシピ) 抽象化：関数名を1つの新しい名前で置換． 入力は (list x1 x2 ... xn ) と f
　convertCF と hours->wages を新しい名前で置換し抽象的な関数を得る (関数名 map ：この特定の機能に対する慣習的な名前) (define ( map f lon) (cond [(empty? lon) empty] [else (cons (f (first lon)) ( map f (rest lon)))])) 入力は (list x1 x2 ... xn ) と f → 出力は (list f(x1) f(x2) ... f(xn))

30 例題4. 具体例からの抽象化(レシピ) テスト：抽象関数が具体的関数の正しい抽象化か? 抽象化関数定義を利用し，オリジナル関数を定義
オリジナル関数の例で抽象化関数版をテスト ;; convertCF_from_map : lon -> lon (define (convertCF_from_map alon) (map C2F alon)) ;; hours->wages_from_map : lon -> lon (define (hours->wages_from_map alon) (map wage alon)) 上記2つを，元のconvertCF と hours->wages 用の例でテスト

31 例題4. 具体例からの抽象化(レシピ) 規約：抽象化を真に有用にするため規約を一般化 マークをつけた値が関数なら規約は矢印を使うタイプ
広く有用な規約を得るため，(パラメトリックなデータ定義を使用する)パラメトリック型で定式化する必要性 convertCF や hours->wages の抽象として map を見ると ;; map: (number -> number) (listof number) -> (listof number) 第6回の例題2，AddressNote 構造体のリストから名前のリスト(文字列のリスト)を得る関数 select_name にも mapが使える． このselect_nameの抽象として map を見ると ;; map: (AddressNote -> string) (listof AddressNote) -> (listof string) これらを矛盾なく扱うために， map が何をするかを理解し，必要があれば規約を修正する (全ての場合を扱える規約は?)

32 例題4. 具体例からの抽象化(レシピ) 規約：抽象化を真に有用にするため規約を定式化
map はリスト(第2引数)の各項目に関数(第1引数)を適用 関数はリストが含むデータクラスに適用される もし リストの要素が X なら f は以下の規約を持つ ;; f : X -> ??? map はリストの各項目に f を適用し，結果のリストを生成 もし f が Y を生成するなら，map は Y のリストを生成。 map は Xのリストと，X からYへの関数を受取り，Yのリストを生成する (XとYが具体的に何かに関わらず) ;; map : (X -> Y) (listof X) -> (listof Y)

33 練習3. map 関数の利用 第6回の例題2で AddressNote 構造体のリストから名前のリスト(文字列のリスト)を得る関数 select_name を作った．同様の機能の関数 select_name_from_map を，mapを使って作成せよ． ;; select_name_from_map : ;; (listof AddressNote) -> (listof string) (define (select_name_from_map alist) … map …) (define (select_name_from_map alist) (map AddressNote-name alist) )

34 課題

35 課題1. ユーザ定義関数によるフィルタ 例題1 の filter1 の第一引数は Scheme の既定義演算に限らず，2つの数からブール値を生成する関数でよい． 1. 条件 x2 > c の成立をテストする関数squared>?を定義せよ． ;; squared>? : number number -> boolean (define (squared>? x c) … ) 2. リスト L中の要素で，その平方が c より大きい数を抽出する関数 filter_ squared> を filter1を使って定義せよ．

36 課題1. ユーザ定義関数によるフィルタ 例題1 の filter1 の第一引数は Scheme の既定義演算に限らず，2つの数からブール値を生成する関数でよい． 1. 条件 x2 > c の成立をテストする関数squared>?を定義せよ． ;; squared>? : number number -> boolean (define (squared>? x c) (> (* x x) c) ) 2. リスト L中の要素で，その平方が c より大きい数を抽出する関数 filter_ squared> を filter1を使って定義せよ． (define (filter_squared> alon) (filter1 squared>? alon)

37 課題2. 規約(contract)の理解と定式化
((listof number) -> number) ((listof number) -> boolean) 2. 次のような関数の規約を定式化せよ． fold-num：数のリストと，2つの数を受け取り1つの数を返す関数の2つを入力として受け取り，1つの数を出力として返す． 3. 次の関数の一般的な規約を定式化せよ(型変数を使う) fold： Yのリスト，および関数(リスト項目Yから X への関数)という2つの引数を受け取り，X を出力として返す．

38 課題2. 規約(contract)の理解と定式化
((listof number) -> number) ((listof number) -> boolean) 数のリストを入力とし，数もしくはブール値を返す 2. 次のような関数の規約を定式化せよ． fold-num：数のリストと，2つの数を受け取り1つの数を返す関数の2つを入力として受け取り，1つの数を出力として返す． fold-num: (listof number) (number number ->number) -> number 3. 次の関数の一般的な規約を定式化せよ(型変数を使う) fold： Yのリスト，および関数(リスト項目Yから X への関数)という2つの引数を受け取り，X を出力として返す． fold: (listof Y) (Y->X) -> X

39 課題3. 抽象化(要素選択) 次の2つの関数を単一の関数select_one へ抽象化せよ
課題3. 抽象化(要素選択) 次の2つの関数を単一の関数select_one へ抽象化せよ ;; min : nelon -> number ;; to determine the smallest number on alon (define (min alon) (cond [(empty? (rest alon)) (first alon)] [else (cond [(< (first alon)(min (rest alon))) (first alon)] [else (min (rest alon))])])) ;; max : lon -> number ;; to determine the largest number on alon (define (max alon) (cond [(empty? (rest alon)) (first alon)] [else (cond [(> (first alon) (max (rest alon)] (first alon)] [else (max (rest alon))])])) 抽象化した関数select_oneを用いて，上記と同等の min1 と max1 を定義せよ．

40 select_one ;; select_one: (number number -> true, false) alon ;; (select_one < (list 1 2 3)) => 1 (define (select_one rel_op alon) (cond [(empty? alon) empty] [(empty? (rest alon)) (first alon)] [(relop (first alon) (select_one rel_op (rest alon))) (first alon)] [else (select_one rel_op (rest alon))]))

41 課題4. 抽象化(fold) 次の2つの関数を1つの単一の関数 fold へ抽象化せよ．
;; sum : (listof number) -> number ;; to compute the sum of the numbers on alon (define (sum alon) (cond [(empty? alon) 0] [else (+ (first alon) (sum (rest alon)))])) ;; product : (listof number) -> number ;; to compute the product of the numbers on alon (define (product alon) (cond [(empty? alon) 1] [else (* (first alon) (product (rest alon)))])) 抽象化した関数 fold を用いて，上記と同等の sum1 と product1 を定義せよ．

42 fold ;; fold: (number number -> number) number (listof number) -> number ;; (fold + 0 (list 1 2 3)) => 6 (define (fold f base alon) (cond [(empty? alon) base] [else (f (first alon) (fold f base (rest alon)))]))