初回から迷走している『ひとりSICP読書会』の第2回目です。隔週で投稿できればと思っていますが、早くも息切れ気味です。。
さて、前回行き詰まった 練習問題 1.6 は、前回の考察以外に思いつかないのでそれを解答とし、1.7, 1.8 は特に問題なく解いて、次の 1.1.8 節に進みます。
束縛 (bind)
束縛とは変数の局所化のための仕組みで、「初めての人のためのLISP (以降『竹内本』)」では『代入』の流れから出てきてます1。関数 (手続き) を実行するときに新しい変数を用意して引数を代入し、関数の評価が終わればその変数は捨ててしまう、と。そして、
束縛によって名前が定義される式のセットは、その名前のスコープ (scope) と呼ばれます。
これは多くの言語でいう『関数スコープ』ですね。
と スコープ という語が出たところで、前回 環境 (environment) が出てきて『スコープのようなもの？』として進めたのですが、やはり違っていたようです。第3章で明らかになる2ようですが、それまではふわっとした理解で進めます。
また、試しに ブロック構造 (block structure) / レキシカルスコーピング (lexical scoping) で練習問題 1.8 を書き換えてみると、
(define (square x) (* x x))
(define (cube x) (* x x x))
(define (cbrt x)
(define (good-enough? guess)
(< (abs (- (cube guess) x)) 0.001))
(define (improve guess)
(/ (+ (/ x (square guess)) (* 2 guess)) 3))
(define (cbrt-iter guess)
;for debug
(display (string-append (number->string guess) " "
(if (good-enough? guess) "#t" "#f") "\n"
))
(if (good-enough? guess)
guess
(cbrt-iter (improve guess))))
(cbrt-iter 1.0))
こんな感じ (前回入れたデバッグ出力付き) 。実行すると、
> (cbrt 8)
1.0 #f
3.3333333333333335 #f
2.462222222222222 #f
2.081341247671579 #f
2.003137499141287 #f
2.000004911675504 #t
2.000004911675504
>
です。たぶんポイントは「引数 x に対しての『再代入』が行われてない」ことだと思います。
1.2.1 線形再帰と反復
再帰と反復と言っても、どちらも "再帰手続き" で実装されています (LISP でいう prog 形式ではない)。違いは、
- 再帰プロセス: まず展開して、展開が完了すると (計算しつつ) 縮約して結果を求める
- 反復プロセス: 都度計算を実行して、末尾に達したときの値を結果とする
です。私は2つの区別を、前者が (縮約時に) 計算結果を戻り値で渡しているのに対して、後者は都度計算した値を (再帰呼び出し時に) 引数として渡している、と考えました。そして、
- "再帰プロセス" と "再帰手続き" の概念を混同しない: それぞれの内部の処理とメモリ/計算量を理解する
- 反復プロセスは 状態 を持つ
- Scheme の反復プロセスは、再帰手続きとして記述されていても、固定の (メモリ) 空間で実行できる: (末尾再帰)
がポイントと思います。
練習問題 1.9
これは特に問題ないと思います。ちょっと邪道かもしれませんが、デバッグ出力をつけて実行すると、よくわかります。
> (define (+ a b)
(display (string-append "a:" (number->string a) " b:" (number->string b) "\n"))
(if (= a 0)
b
(inc (+ (dec a) b))))
> (+ 3 4)
a:3 b:4
a:2 b:4
a:1 b:4
a:0 b:4
7
> (define (+ a b)
(display (string-append "a:" (number->string a) " b:" (number->string b) "\n"))
(if (= a 0)
b
(+ (dec a) (inc b))))
> (+ 3 4)
a:3 b:4
a:2 b:5
a:1 b:6
a:0 b:7
7
前者が a = 0 となった後に縮約して結果を出しているのに対し、後者は b の値を返して終了します。
余談ですが、このように『+という基本的な演算すら再定義できる』ということから、
> (define (+ a b) (- a b))
> (+ 3 4)
-1
> (define (+ a b) (* a b))
> (+ 3 4)
12
ということが出来てしまうわけですね。。
(2022-09-20 追記) 再定義できてしまいますが『言語仕様としては規定されてない』とコメントでお教えいただきました。そちらもご参照ください！
練習問題 1.10
ここで行き詰まりました。else 時の手続き (A (- x 1) (A x (- y 1))) と、その手続きの引数 (A x (- y 1)) で再帰呼び出しされていますので、先に引数 (A x (- y 1)) が評価されるのだと思うのですが、処理を追うのに頭が追いつきません。。例によってデバッグ出力を入れて動作を追っても、どうもわからず。
そもそも『アッカーマン関数って、何？』と調べてみたら、なんか練習問題の定義と違うような。。SICPでは、
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1) (A x (- y 1))))))
ですが、Wikipedia によると
A(m, n) = \left\{
\begin{array}{ll}
n + 1, & \textrm{if } m = 0 \\
A(m - 1, 1), & \textrm{if } n = 0 \\
A(m -1, A(m, n - 1)), & \textrm{otherwise}
\end{array}
\right.
で、コードに起こすと下記です。
(define (A x y)
(cond ((= x 0) (+ y 1))
((= y 0) (A (- x 1) 1))
(else (A (- x 1) (A x (- y 1))))))
実行して アッカーマン関数の値の表 と見比べたところ、これで正しいようです。
といっても、条件分岐はシンプルになっているものの (= y 0) 時にも再帰呼び出ししたり、キモの 手続きと、その手続きの引数で再帰呼び出し は変わらないですね。ということは行き詰まりポイントも変わらないということで、、
今回はここまでにします。進まないニャー。
※ 本稿で使用した画像 Cover of the book Structure and Interpretation of Computer Programs (second edition). Harold Abelson and Gerald Jay Sussman with Julie Sussman — MIT Press は CC 表示-継承 4.0 で公開されています。