(define -ayalog '())

括弧に魅せられて道を外した名前のないプログラマ

SICPを読む_(5)1章_手続きによる抽象の構築(p14-20)

1.1.8ブラックボックス抽象としての手続き(p14-17)

  • 再帰的であることに注意
    • それ自身を使って手続きが定義出来るという考えは紛らわしい
    • 再帰については後で触れる
  • sqrtのプログラムは手続きの"束"であるといえる
    • 問題の部分問題への分割を反映している
  • 手続きをブラックボックスとしてみる
    • "どう"計算するかに感心を持たない
    • 関心があるのは計算する事実だけ
    • 前項までの例で言えばgood-enough?に関するsquareは手続きではなく、「手続き抽象」
局所名
  • 手続き定義の中で仮パラメタはどんな名前を持っていても構わない
    • そういう名前を「束縛変数」という
    • 手続き定義は仮パラメタを「束縛」する <=> 束縛されていなければ「自由」である
  • 名前が束縛されている式の範囲を「有効範囲(スコープ)」という

仮パラメタの名前は本当になんでもいいのが、凄くあれ…。
既にある手続きの名前(例えばsqrt)とかをつけると、その対象の手続きの中では当然ながら束縛変数として扱われるので、
対象の手続きのスコープの中では、その手続きは使えなくなるという…。

;;既にある手続きsquare
(define (square x)
  (* x x))
;;この手続きの中でのsquareは束縛変数であり、手続きではない。
(define (square-sum square)
  (+ square square))
内部構造とブロック構造
  • 手続きをバラバラに書き続けると名前が衝突しやすくなる
  • 他の同名の手続きと共存する為に、下請けの手続きを呼び出し元の手続きに局所的な内部定義にする

ということで、実際にはこんな感じで宣言できる。素敵。

(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
	guess
	(sqrt-iter (improve guess))))
  (sqrt-iter 1.0))
  • こういった定義の入れ子を「ブロック構造」という
  • 上の例の"x"はsqrtの定義に束縛されているので、内部定義の中では自由変数として扱える
    • 「静的有効範囲(レキシカルスコープ)」という

レキシカルスコープってなんか素敵ですよね...

1.2手続きとその生成するプロセス(p17-20)

  • プログラムによってプロセスを制御する
  • プロセスを視覚化することを学ぶ
  • 手続きは計算プロセスの「局所的進化」のパターン

1.2.1線形再帰と反復(p18ー20)

slib使って実行時のパラメタとか見るとわかりやすいですね。

;;再帰的プロセス
(define (fact n)
  (cond
   ((= n 1) 1)
   (else
    (* n (fact (- n 1))))))

(fact 6)

(use slib)
(require 'trace)
(trace fact)
;;反復的プロセス
(define (fact n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (cond
   ((> counter max-count) product)
   (else
    (fact-iter (* counter product)
	       (+ counter 1)
	       max-count))))

(fact 6)

ここらへんは用語が一気に出てきて(しかも似たような名前の)ちょっと混乱するけど、
「再帰的」と「反復的」の違いを理解すればだいたいokな気がする。