search
LoginSignup
0
Help us understand the problem. What are the problem?

posted at

updated at

Organization

(define ひとりSICP読書会#02 '("1.1.8" "1.2.1"))

初回から迷走している『ひとりSICP読書会』の第2回目です。隔週で投稿できればと思っていますが、早くも息切れ気味です。。
SICP_cover.jpg
さて、前回行き詰まった 練習問題 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 PressCC 表示-継承 4.0 で公開されています。

  1. ちなみに竹内本では、思わずA君が『エッ、縄で縛るのですか?それなら僕の趣味だ。』と口走ってしまうのですが、それで覚えていたというのは竹内郁雄先生の策にはまった感じです (この本は、そういうサブカルっぽいネタが多い)。

  2. 脚注で『第 3 章では、インタプリタがどのように動作しているかを理解するため、またインタプリタを実装するために、この環境という概念がキーポイントになることを示します。』と補足されています。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
0
Help us understand the problem. What are the problem?