SICP 読書ノート#4 - 1.3 高階手続きによる抽象 (pp.31-44)
§1.3 「高階手続きによる抽象」から
高階手続きとは
引数に手続きをとり戻値で手続きを返す手続き。これをつかうことで言語の表現力が大幅に広がる。 全部解くパワーはなかったので、数学っぽいものはパスして、高階手続きに関する問題だけをチョイスした。
問題 1.30
sumの反復的プロセス版を作る。
(define (sum term a next b) (define (iter a result) (if (> a b) result (iter (next a) (+ result (term a))))) (iter a 0)) ; テスト (define (identify x) x) (define (inc x) (+ x 1)) (map (lambda (x) (sum identify 1 inc x)) (range 1 11)) ; => '(1 3 6 10 15 21 28 36 45 55)
問題 1.31
まずはa-b区間の総積について。
;; 再帰的プロセス (define (product term a next b) (if (> a b) 1 (* (term a) (product term (next a) next b)))) ;; 反復的プロセス (define (product term a next b) (define (iter a result) (if (> a b) result (iter (next a) (* result (term a))))) (iter a 1))
πの近似値を得てみる。
(* (product (lambda (n) (/ (* n (+ n 2)) (* (+ n 1) (+ n 1)))) 2 (lambda (n) (+ n 2)) 100) 4.0) ; => 3.15703...
問題 1.32
sumとproductをもう１段抽象化する。
;; (a) 再帰的プロセス (define (accumulate combiner null-value term a next b) (if (> a b) null-value (combiner (term a) (accumulate combiner null-value term (next a) next b)))) ;; (b) 反復的プロセス (define (accumulate combiner null-value term a next b) (define (iter a result) (if (> a b) result (iter (next a) (combiner result (term a))))) (iter a null-value)) ;; accumulateを使ってsumとproductを実装 (define (sum term a next b) (accumulate + 0 term a next b)) (define (product term a next b) (accumulate * 1 term a next b))
lambda
名前のない手続きを作る。そのままでは環境へ名前の対応付けが行われない。
以下の2つは等価となる。（大域環境で宣言する分には）
(define (plus4 x) (+ x 4)) (define plus4 (lambda (x) (+ x 4)))
let
局所変数を生成する。すなわちスコープはletの内側で閉じる。 let式はベースとなるlambda式のsyntax sugar。
問題 1.33
accumulateに述語を追加しtrueの場合のみ積算するfiltered-accumulateを実装。
;; 再帰的プロセス (define (filtered-accumulate combiner null-value term a next b predicate) (if (> a b) null-value (combiner (if (predicate a) (term a) null-value) (filtered-accumulate combiner null-value term (next a) next b predicate)))) ;; 反復的プロセス (define (filtered-accumulate combiner null-value term a next b predicate) (define (iter a result) (if (> a b) result (iter (next a) (combiner result (if (predicate a) (term a) null-value))))) (iter a null-value))
a-b区間の素数の二乗の和でテスト。
(define (prime-square-sum a b) (filtered-accumulate + 0 square a inc b prime?)) (prime-square-sum 1 10) ; => 88
問題 1.34
(define (f g) (g 2))
において (f f) と評価するとどうなるか。
置き換えモデルで考えると、
(f f) (f 2) (2 2)
となり2が手続きでないためエラー。動作確認してOK。
問題 1.37
(define (cont-frac n d k) ; nとdは手続き (define (helper i) (if (> i k) 0 (/ (n i) (+ (d i) (helper (+ i 1)))))) (helper 0))
結果をチェックしてみる。
(map (lambda (k) (list k (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) k))) (range 20)) ;; => ;; '((0 1.0) ;; (1 0.5) ;; (2 0.6666666666666666) ;; (3 0.6000000000000001) ;; (4 0.625) ;; (5 0.6153846153846154) ;; (6 0.6190476190476191) ;; (7 0.6176470588235294) ;; (8 0.6181818181818182) ;; (9 0.6179775280898876) ;; (10 0.6180555555555556) ;; (11 0.6180257510729613) ;; (12 0.6180371352785146) ;; (13 0.6180327868852459) ;; (14 0.6180344478216819) ;; (15 0.6180338134001252) ;; (16 0.6180340557275542) ;; (17 0.6180339631667064) ;; (18 0.6180339985218034) ;; (19 0.6180339850173578))
k=10を超えた辺りで誤差が小数点4桁以下になる模様。
反復プロセス版は以下。なかなか思いつかずに苦労した。
(define (cont-frac n d k) (define (iter i result) (if (= i 0) result (iter (- i 1) (/ (n i) (+ (d i) result))))) (iter k 0))
抽象と第一級手続き
Schemeでは手続きをファーストクラスのオブジェクトとして扱える。
以下、本文からの引用。
われわれはプログラマとして, プログラムの根底にある抽象を見つけ, より強力な抽象化が出来るよう, その上に構成し, 一般化するよう努めなければならない. これはプログラムを可能な限り抽象的に書くべしというのではない; 経験を積んだプログラマは, 自分の仕事に適した抽象のレベルを選ぶことを知っている. しかし抽象を使って考えることが出来るのは, 新しい状況になった時に, すぐ応用出来るため, 大切である. 高階手続きの重要さは, それにより抽象をプログラム言語の要素として確かに表せ, 他の計算要素のように扱えるという点にある.
一般にプログラム言語には, 計算要素を扱う方法にいろいろな制限があるものだ. 制限の殆んどない要素は 第一級(first-class)身分を持つという. 第一級要素の「権利と特権」は
• 変数として名前がつけられる..
• 手続きに引数として渡せる..
• 手続きの結果として返される.
• データ構造に組み込める.
である. Lispは他の通常のプログラム言語と違い, 手続きに完全な第一級身分を授与した. そのため, 効率のよい実装は難しくなったが, 表現力として得たものは絶大である.
「データ構造への組み込み」は2章での重要なファクターになる。
問題1.41
(define (double f) (lambda (x) (f (f x)))) (define (inc x) (+ x 1))
とした場合、以下の結果は？
(((double (double double)) inc) 5) ; => 21
最初は全く理解できなかったが、置換えモデルを書けてようやく納得。
i. (double inc)の置換えモデルを考える
(double inc) ; => (lambda (x) (inc (inc x)))
5を適用する。
((lambda (x) (inc (inc x))) 5) ; => 7
ii. (double double)の置き換えモデルを考える
(double double) ; => (lambda (x) (double (double x)))
incを適用する。
((lambda (x) (double (double x))) inc) ; => (double (double inc)) ; => (double (lambda (x) (inc (inc x)))) ; => (lambda (x) ((lambda (x) (inc (inc x))) ((lambda (x) (inc (inc x))) x)))
さらに5を適用。
((lambda (x) ((lambda (x) (inc (inc x))) ((lambda (x) (inc (inc x))) x))) 5) ; => ((lambda (x) (inc (inc x))) ((lambda (x) (inc (inc x))) 5)) ; => ((lambda (x) (inc (inc x))) 7) ; => 9
iii. (double (double double)) の置換モデルを考える
(double (double double)) ; => (double (lambda (x) (double (double x)))) ; => (lambda (x) ((lambda (x) (double (double x))) ((lambda (x) (double (double x))) x)))
incを適用する。
((lambda (x) ((lambda (x) (double (double x))) ((lambda (x) (double (double x))) x))) inc) ; => ((lambda (x) (double (double x))) ((lambda (x) (double (double x))) inc)) ; => ((lambda (x) (double (double x))) (double (double inc))) ; => ((lambda (x) (double (double x))) (lambda (x) ((lambda (x) (inc (inc x))) ((lambda (x) (inc (inc x))) x)))) ; => (lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) (inc (inc x))) ((lambda (x) (inc (inc x))) x))) ((lambda (x) ((lambda (x) (inc (inc x))) ((lambda (x) (inc (inc x))) x))) x))) ((lambda (x) ((lambda (x) ((lambda (x) (inc (inc x))) ((lambda (x) (inc (inc x))) x))) ((lambda (x) ((lambda (x) (inc (inc x))) ((lambda (x) (inc (inc x))) x))) x))) x)))
さらに5を適用する。
((lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) (inc (inc x))) ((lambda (x) (inc (inc x))) x))) ((lambda (x) ((lambda (x) (inc (inc x))) ((lambda (x) (inc (inc x))) x))) x))) ((lambda (x) ((lambda (x) ((lambda (x) (inc (inc x))) ((lambda (x) (inc (inc x))) x))) ((lambda (x) ((lambda (x) (inc (inc x))) ((lambda (x) (inc (inc x))) x))) x))) x))) 5) ; => 21
解けた。
問題 1.42
関数合成について。
(define (compose f g) (lambda (x) (f (g x)))) ((compose inc square) 2) ; => 5 ((compose square inc) 2) ; => 9
せっかくなので複数関数の関数合成も。
(define (compose . f) (define (helper funcs) (let ((func (car funcs)) (rest (cdr funcs))) (if (null? rest) func (lambda (x) ((helper rest) (func x)))))) (helper (reverse f))) ((compose inc square inc) 2) ; => 10 ((compose square inc inc) 2) ; => 16
問題 1.43
;; 再帰的プロセス (define (repeated f n) (if (= n 1) f (compose (repeated f (- n 1)) f))) ;; 反復的プロセス (define (repeated f n) (define (iter count result) (if (= count n) result (iter (+ count 1) (compose f result)))) (iter 1 f)) ((repeated square 2) 5) ; => 625
次回は2章へ突入。
