This article was migrated from http://rails.office.drecom.jp/takiuchi/archive/21

今週も、同僚のよしてつさんと一緒に素人くさいSICP読書会に参加してきました。

今回は404 Blog Not Foundでお馴染みの小飼さんのご自宅で開催されました。
非常に素晴らしい環境を利用させていただいことに感謝いたします。

参加者は、だいたい前回と同じくらいで23名。
最近各所で遭遇するようになってきた面々や、CNetブロガーの山下さん、そしてもちろん小飼さんも参加されていました。

今回も前回同様、演習問題を黙々と解いていくという形式で進められました。
実際に解いた演習問題は1.32と1.33です。

何問か問題を解いてみて、ようやく括弧が見えなくなる感覚が芽生えてきました。

演習問題1.33については、過去の演習問題で作成した関数 'prime?' を利用する必要がある（しなくても良いけれど、時間が掛かりそうな）ため、Wikiからコピーしてきました。

filtered-accumulate を構成する問題の答え合わせを行っているときに、filterを使わないで同じ事をする事は可能かどうか、というテーマでいろいろな意見が出て盛り上がっていました。

(define (filtered-accumulate combiner null-value term a next b filter)
　(if (> a b)
　　　null-value
　　　(combiner (if (filter a) (term a) null-value)
　　　　　　　　(filtered-accumulate combiner null-value term (next a) next b filter))))

combiner が受け取るのは a ではなく (term a) なので、term が全単射でないかぎり、逆写像が存在しないので、元の a の値が何だったのかわからず、combiner の定義の仕方だけでは filter と同等のものを構成できない場合もあるかなー、と思います。
どうでしょう。

というわけで、とても楽しい時間がすごせました。

帰り際に小飼さんの奥様からコーヒーを振舞って頂きました。
ありがとうございます。

小飼さん自身からも、壁面を覆う巨大な書架（うらやましい！）よりお勧めの本を何冊か紹介していただきました。ロジャー・ペンローズ氏の著書は読んだことが無かったですが、機会があったらぜひ読んでみたいですね。恥ずかしながらペンローズ・タイリングのペンローズ氏が同氏と同一人物であると初めて知りました。もっと昔の別なペンローズさんかとばかり思っていました。

ということで、次週は演習1.34から開始。各自写経をすませておくべしとの事。

最後に、今回使ったコードを置いておきます。 ----
;; -*- Mode: scheme; indent-tabs-mode: nil; coding: utf-8; -*-

;; 1.2.6 素数性のテスト
(define (square x) ^*1)

(define (smallest-divisor n)
　(find-divisor n 2))

(define (divides? a b)
　(= (remainder b a) 0))

(define (find-divisor n test-divisor)
　(cond ((> (square test-divisor) n) n)
　　　　((divides? test-divisor n)　 test-divisor)
　　　　(else (find-divisor n (+ test-divisor 1)))))

(define (prime? n)
　(if (< n 2)
　　　#f
　　　(= n (smallest-divisor n))))

;; Fermatの小定理
;(begin　　　　　　　　　　　　　　　　　; for gauche
;　(define (square x) ^*2)
;　(use srfi-27)
;　(define random random-integer))

(define (expmod a n m)
　(cond ((= n 0) 1)
　　　　((even? n)
　　　　 (remainder (square (expmod a (/ n 2) m)) m))
　　　　(else
　　　　 (remainder ^*3 m)) m))))

(define (fermat-test n)
　(define (try-it a)
　　(= (expmod a n n) a))
　(try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
　(cond ((= times 0) #t)
　　　　((fermat-test n) (fast-prime? n (- times 1)))
　　　　(else #f)))

;; 問題 1.22
;; gauche用runtime (microsecを返す)
(define (runtime)
　(use srfi-11)
　(let-values (((a b) (sys-gettimeofday)))
　　　　　　　(+ ^*4 b)))

(define (timed-prime-test n)
　(newline)
　(display n)
　(start-prime-test n (runtime)))

(define (start-prime-test n start-time)
　(if (prime? n)
　　　(report-prime (- (runtime) start-time))))

(define (report-prime elapsed-time)
　(display " *** ")
　(display elapsed-time))

(define (search-for-primes beg end)
　(let loop ((i beg))
　　(cond ((> i end) #f)
　　　　　(else
　　　　　 (if (odd? i) (timed-prime-test i))
　　　　　 (loop (+ i 1))))))
;
; ここから下が僕の書いたコード


(define (cube x) ^*5)
(define (sum-integers a b)
　(if (> a b)
　　　0
　　　(+ a (sum-integers (+ a 1) b))))
(define (sum-cubes a b)
　(if (> a b)
　　　0
　　　(+ (cube a) (sum-cubes (+ a 1) b))))
(define (pi-sum a b)
　(if (> a b)
　　　0
　　　(+ (/ 1.0 ^*6)) (pi-sum (+ a 4) b))))
(define (sum term a next b)
　(if (> a b)
　　　0
　　　(+ (term a)
　　　　 (sum term (next a) next b))))
(define (identity x) x)
(define (inc x) (+ x 1))
(define (integral f a b dx)
　(define (add-dx x) (+ x dx))
　^*7) add-dx b)
　　 dx))
(define (even n)
　(= (remainder n 2) 0))
(define (integral_s f a b n)
　(define h (/ (- b a) n))
　(define (y k)
　　(define c (if (or (= k 0) (= k n))
　　　　　　　　　1
　　　　　　　　　(if (even k) 2 4)))
　　^*8))))
　^*9
　　 (/ h 3.0)))
(define (sum_i term a next b)
　(define (iter a result)
　　(if (> a b)
　　　　result
　　　　(iter (next a) (+ result (term a)))))
　(iter a 0))
(define (integral_i f a b dx)
　(define (add-dx x) (+ x dx))
　^*10) add-dx b)
　　 dx))
(define (product factor a next b)
　(if (> a b)
　　　1
　　　^*11
　　　　 (product factor (next a) next b))))
(define (product_i factor a next b)
　(define (iter a result)
　　(if (> a b)
　　　　result
　　　　(iter (next a) ^*12))))
　(iter a 1))
(define (factorial n)
　(product identity 1 inc n))
(define (sq x) ^*13)
(define (approx_pi n)
　(define (y k) (/ (sq (+ k 4)) (sq (+ k 3))))
　(define (next x) (+ x 2))
　^*14) (product_i y 0 next n)))

; ここから下が今回書いたコード
;
(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))))
(define (accumulate_i 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))
(define (filtered-accumulate combiner null-value term a next b filter)
　(if (> a b)
　　　null-value
　　　(combiner (if (filter a) (term a) null-value)
　　　　　　　　(filtered-accumulate combiner null-value term (next a) next b filter))))
(define (e_1_33_a n)
　(filtered-accumulate + 0 sq 1 inc n prime?))
(define (e_1_33_b n)
　(define (relatively-prime? i)
　　(= (GCD i n) 1))
　(filtered-accumulate * 1 identity 1 inc n relatively-prime?))

This article was migrated from http://rails.office.drecom.jp/takiuchi/archive/21

1. 1 x x

2. 2 x x

3. 3 a (expmod a (- n 1

4. 4 a 1000000

5. 5 x x x

6. 6 a (+ a 2

7. 7 (sum f (+ a (/ dx 2.0

8. 8 c (f (+ a (* k h

9. 9 (sum y 0 inc n

10. 10 (sum_i f (+ a (/ dx 2.0

11. 11 (factor a

12. 12 result (factor a

13. 13 x x

14. 14 4 (/ 2.0 (+ n 4