関数型言語の勉強にSICPを読もう - (3) 1章 - 手続きによる抽象の構築(1-30ページ)

1章の途中までは演習問題をノートに書いていたので記録が残っていないです。ごめんなさい。

9ページ

(+ 5 1)と(* 5 2)に置き換えて簡約された。
→簡約ってなんだろうか?

原文

This gives the same answer as our previous evaluation model, but the process is different. In particular, the evaluations of (+ 5 1) and (* 5 2) are each performed twice here, corresponding to the reduction of the expression

(* x x)

with x replaced respectively by (+ 5 1) and (* 5 2).

置き換えによって、(* x x)という表記が減ったと言いたいらしい。
→後日Haskellのドキュメントを読んでいても「簡約」という言葉が似たような文脈で出てきていたのでそういう用語みたいです。

16ページ

bindの対義語はfreeとの事。
対義語を提示してくれると概念が理解しやすいということですね。
勉強になりました。

17ページ

最後の3行が分からない。
原文

A procedure is a pattern for the local evolution of a computational process. It specifies how each stage of the process is built upon the previous stage. We would like to be able to make statements about the overall, or global, behavior of a process whose local evolution has been specified by a procedure. This is very difficult to do in general, but we can at least try to describe some typical patterns of process evolution.

22ページ

両替の話。本当に動くのかなと思ったが動いた。
結構感動した。

(define  (count-charge amount)
  (cc amount 5))

(define (cc amount kind-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kind-of-coins 0)) 0)
        (else (+ (cc amount (- kind-of-coins 1))
                 (cc (- amount (first-denomination kind-of-coins))
                     kind-of-coins)
                 ))))

(define (first-denomination kind-of-coins)
  (cond ((= kind-of-coins 1) 1)
        ((= kind-of-coins 2) 5)
        ((= kind-of-coins 3) 10)
        ((= kind-of-coins 4) 25)
        ((= kind-of-coins 5) 50)))

ちょっと改造して

(define (first-denomination kind-of-coins)
  (cond ((= kind-of-coins 1) 1)
        ((= kind-of-coins 2) 5)
        ((= kind-of-coins 3) 10)
        ((= kind-of-coins 4) 50)))

とすれば日本の100円の両替に使えそう。

問題 1.11

再帰的なのはすぐ解ける。

(define (f n)
  (cond ((< n 3) n)
        (else (+ (f (- n 1))
                 (* 2 (f (- n 2)))
                 (* 3 (f (- n 3)))))))

反復が分からない。
答えを見ても

(define (f-iter n)
  (define (iter a b c count)
    (cond ((= count 0) c)
          ((= count 1) b)
          (else (iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))
  (iter 2 1 0 n))

うーん。うーん。
久々だなぁ。分からなくて途方にくれる。。
自分の頭が良くないことが痛感させられる。
スラスラと理解できるようになりたい。

問題1.12

(define (pascal x y)
  (cond ((or (= x 1) (= x y)) 1)
        (else (+
               (pascal (- x 1) (- y 1))
               (pascal x (- y 1))))))

関数を書き終わった後に動く気がしないという不思議な感覚にとらわれる。
手続き型の言語だったら、関数が動くイメージが映像として浮かぶんだけど、この関数では浮かばない。
式を定義したら勝手に動いている、自分がこの関数を生み出したんだという感覚が全然ない。
不思議!

問題1.14

手で木構造を描いた。
ステップ数は^n。スペースはn。

問題1.15

12.15を3で割っていくので 5回。
プロセス・スペースはa

問題1.16

逐次平方という用語がいまいち分からなかった。
でも答えや例を見れば、プロセスの増加数を抑えられることも分かるしそのためにとっている方法も理解できる。

パス

1.17
1.18
1.19
数学っぽいのでパス。
ここが本質ではないことを祈る。

1.20
作用的順序のほうがプロセス数が少ないんだな。
1.28まで演習パス


※「SICPを読もう」の目次はこちら


計算機プログラムの構造と解釈
Gerald Jay Sussman Julie Sussman Harold Abelson 和田 英一
ピアソンエデュケーション (2000/02)
売り上げランキング: 56,404