SICP 読書会 #22008年06月10日 23時23分

yukky さん主催の SICP 読書会、その第 2 回に参加しました。今回はあらかじめ予習範囲を提示し、最初の 30 分間でそこを読み進めた上で、後はもっぱら範囲内の問題にあてるという形式でした。私の分も含め各人の解答は当日のチャットログから参照できます。

開始前の空き時間で最初のほうの問題をやっておいたのですが、それでも時間がぜんぜん足りなくて息切れしてしまいそうでした。予習復習をしっかりしておかないとちょっとつらいかもしれませんね。

丸括弧と角括弧

Gauche では (Scheme では?) 丸括弧の代わりに角括弧も使えるので、cond の条件節に使うと読みやすいと教えてもらいました。確かに読みやすくはなりますが、なんだか美しくないような気がするのは私だけでしょうか。

(define (square x) (* x x))

; b の n 乗を求める
(define (expt b n)
  (cond [(= b 0) 1]
        [(even? b) (square (expt (/ n 2)))]
        [else (* b (expt b (- n 1)))]))

ユークリッドの互除法

最大公約数を求めるアルゴリズムとして有名なユークリッドの互除法ですが、英語では Euclidean algorithm といって、「互いに割る」というようなニュアンスは直接的には含まれてないのですね。

反復的プロセスへの変換

累乗と乗算を求める関数を、再帰的プロセスから反復的プロセス (末尾再帰) に直せという問題が出てきます。いろいろ悩んだすえ、以下のように考えにたどり着きました。

; b の n 乗を求める
(define (expt a b)
  (define (iter b n acc)
    (cond ((= n 0) acc)
          ((even? n)
           ; ここをどう書くか
           )
          (else
           ; ここをどう書くか
           )))
  (iter b n 1))

iter はどういう関数かを考えます。S 式表記から離れますが、acc = 1 のとき exp-iter(b, n, 1) は b^n を返します。n = 0 のとき、iter(b, 0, acc) は acc を返します。これらから考えていくと、iter は iter(b, n, acc) = b^n * acc という関数であることが推測されます。n が偶数のときは n / 2 が整数ですから、

  b^n * acc
= b^(n / 2 * 2) * acc
= (b^(n / 2))^2 * acc
= (b^2)^(n / 2) * acc

という変形が成り立ちます。n が奇数のときは、

  b^n * acc
= b^(n - 1 + 1) * acc
= (b^(n - 1) * b) * acc
= b^(n - 1) * (b * acc)

となります。つまり、

  • n が偶数なら iter(b, n, acc) = iter(b^2, n / 2, acc)
  • n が奇数なら iter(b, n, acc) = iter(b, n - 1, b * acc)

となるのです。後はこれを S 式に戻してやれば以下のように完成します。

; b の n 乗を求める
(define (expt a b)
  (define (iter b n acc)
    (cond ((= n 0) acc)
          ((even? n) (iter (square b) (/ n 2) acc))
          (else (iter b (- n 1) (* b acc)))))
  (iter b n 1))

フィボナッチ数の対数的ステップでの計算

問題 1.19 は線形写像の行列表現を利用してフィボナッチ数を O(log N) のステップ数で求める問題です。(bq+aq+ap bp+aq)T = Tpq (a b)T から行列 Tpq が求められるので、Tp′q′ = Tpq2 より p′、q′ も求められますね (行列の右肩の T転置を表します)。

四元数

なぜか SICP とはあまり関係のない四元数の話も出ました。四元数は応用として 3 次元空間での回転を表現するのに用いられますが、四元数そのものは実 4 次元ですよね。