いきなりSICPをやってみることにした

SICPというと、有名なコンピュータサイエンスの本で、諸大学の教科書として使われている本だったりします。CじゃなくてScheme扱ってるところが風変わりな予感。

いろんな人がネット上でこの本読んで関数型プログラミングなり他もろもろを勉強して、いろんな知見を得てらっしゃる感じなので、ぼくもその流れに乗っちまおうという目論見です。時間があるときに問題でも解いていこうかなぁと思ってるのですが、時間を作るのも大きな問題だったりするのかもしれません。

とりあえず第一章なのですが、第一章でもやってること結構むずい。問題は易しめなのかもしれないけど、関数型に慣れてない上、まず本文がむずい。

問題1-10

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y)
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

で、以下定義された関数の意味を書けと．これアッカーマン関数だそうな．名前しかしらない．

(define (f n) (A 0 n))

(f n)=2*n

(define (g n) (A 1 n))

(g n)=2**n

(define (h n) (A 2 n))

(h n)=2**(h (n-1)) (if n>1), 2 (n=1)
2**(2**(2**....))と肩に2がn個のる感じ

問題1-11

再帰的プロセス

(define (recursive-f n)
  (if (< n 3) n
      (+ (recursive-f (- n 1)) (recursive-f (- n 2)) (recursive-f (- n 3)))))

反復的プロセス

(define (iterative-f n)
  (sub-iterative-f 2 1 0 n))

(define (sub-iterative-f a b c count)
  (cond ((= count 0) c)
        ((= count 1) b)
        ((= count 2) a)
        (else (sub-iterative-f (+ a b c) a b (- count 1)))))

計算機プログラムの構造と解釈